Streamlet: how can notarized chains be the same length.

[nathan-at-least]

Question

From §1.1:

Propose-Vote. In every epoch: – The epoch’s designated leader proposes a new block extending from the longest notarized chain it has seen (if there are multiple, break ties arbitrarily). The notion “notarized” is defined below. – Every player votes for the first proposal they see from the epoch’s leader, as long as the proposed block extends from (one of) the longest notarized chain(s) that the voter has seen. A vote is a signature on the proposed block. – When a block gains votes from at least 2n/3 distinct players, it becomes notarized. A chain is notarized if its constituent blocks are all notarized.

If:

• 2/3 of players are well-behaved, and
• a player considers a block notarized only when they have evidence that 2/3 or players voted for it, and
• a player does not vote for any proposed block which does not extend a longest-seen notarized chain…

-then how could any player see >1 sequences of notarized blocks of the same (longest) length?

[nathan-at-least]

Consider Figure 1:

IIUC, each box with a number here represents a block that was notarized in that epoch, because later on page 2 it says:

An example of applying the finalization rule is shown in Figure 1. In this example, imagine all blocks are notarized: we see that there is a notarized chain with 3 adjacent blocks having consecutive epoch numbers 5, 6, and 7.

So, we can ask an instance of the main question of this ticket: how could a node ever come to believe the notarization result of epoch 2?

[nathan-at-least]

Potential answer:

The numbers indicate the epoch during which a block is proposed but that is distinct from the epoch in which a block is notarized!

So for the instance above the sequence for an honest node might look like this:

1. Epoch 1: see proposed block extending genesis (which is longest known notarized chain base case).
2. Epoch 2: see proposed block extending genesis. At the time at which the node sees this proposal: the proposal from Epoch 1 has not yet been notarized.

Either after 1 and before 2, or after 2: the node votes for proposal 1, since it extends longest notarized chain (genesis). After 2 but before the node sees 1 as notarized: vote for proposal 2, since it extends longest notarized chain (genesis).

[nathan-at-least]

Hrm, in §3.2 when defining streamlet, a block is defined to contain:

e is called the epoch number of the block, which records the epoch in which the block is proposed and voted on;

This makes it sound as if proposal and voting occur within the same epoch (which is within or contains a period of synchrony, and where the epoch is larger than roundtrip message time). So this challenges my guess above.

[nathan-at-least]

In §3.5 it gives an instance of informal proof for Figure 1 analyzing two cases, one assuming X is notarized when X < 5 and two where X > 7.

I'm not yet clear why these bounds are chosen. Why not X < 4 or X > 5, …?

I'll try just writing the latter case:

Case 3 (not in paper): X > 5. Since block 5 is notarized, more than n/3 honest nodes (denoted the set S) must have seen a notarized block 2 by the time they vote for block 5 (i.e., by the end of epoch 5). As a result, by epoch X > 5, the set S of nodes must have seen block 5 notarized and will not vote for block X, since block X now fails to extend the longest notarized chain seen (which is block 5 or longer). Therefore block X cannot gain 2n/3 votes, and it cannot be notarized, which is a contradiction.

At first glance, this made up Case 3 holds given Figure 1 with all of the same assumptions and conclusions in the text. However, if we look at Figure 1 we would see that 3 is notarized at the same length as 5… which is still a mystery as to how an honest view can arrive at that state in the first place, which is the whole impetus for this ticket.

So I feel like I still have a "bootstrapping" problem to understand the argument in the paper in the first place, since it starts with a subset of Figure 1 that already seems impossible to me.

Maybe the general informal argument on the next page will clarify this (whereas the Figure 1 subset-specific instance glosses over the bootstrapping problem)?

[nathan-at-least]

After pairing on this with @daira we are fairly certain the answer to this question is that reception on votes may be delayed by an arbitrary number of epochs.

So, honest nodes can see two notarized chains of equal length by this process:

• In Epoch $T+0$:
  • Alice, an honest node, sees a single longest notarized chain of height $H_0$.
  • Bob, the proposer (whether malicious or not) proposes a block, $B$ at height $H_1 = H_0 + 1$ which extends the longest notarized chain Alice sees.
  • Alice therefore votes to notarize the proposal as the protocol requires.
  • During this epoch, at least 2/3 of nodes (who are assumed honest) also vote.
  • However these votes propagate with arbitrary delays and Alice does not see a sufficient threshold for the proposed block in $T+0$.
• In Epoch $T+1$:
  • During this epoch, Alice still does not see a sufficient threshold of votes for $B$ (for simplicity we ignore the case that she does see the votes in this epoch but only after other following events in the epoch).
  • Charlie, the proposer (whether malicious or not) proposes a block, $B'$ at height $H_1 = H_0 + 1$ which extends the same longest chain of height $H_0$ that Alice saw in $T+0$.
  • Because Alice has not yet seen a sufficient threshold for $B$ proposed in T+0, she still sees the same longest-notarized chain at $H_0$, and therefore, by following the protocol, she votes for this new block.
• After Epoch $T+1$:
  • Alice sees enough votes for $B$ to pass the threshold, so she marks it as notarized.
  • Alice sees enough votes for $B'$ to pass the threshold, so she marks it as notarized.
  • Alice now sees two chains at height $H_1$ which are both notarized by ≥2/3 of the nodes.

If this matches @daira's understanding, we can close this question as resolved.

[daira]

That matches my understanding.