Process of forking and extending the block tree

Dear readers,

I have a question regarding the options a honest or byzantine replicator node has about extending the current block tree.

  1. How does a honest replicator node extend the to his known block tree? (is this deterministic?)
  2. What options does a byzantine node have if he is the roundLeader? (including not sending at all?)

When looking at the example image below from the paper it explains that round k+3, times out, but the leader of that round has received at least 2f+1 votes but he is unable to send the QC to the next round reader. This means that round k does not get committed and the preferred round stays k. Now the next roundLeader forks at round k, this is allowed since the parent round_number of this proposal is at least k. Somewhere later k does get committed and then k+4 gets committed but I have many questions.

  1. What if round k never get committed but round k+4 does? Is this even possible since maybe money is spend in round k+4 that comes from round k?
  2. Could the proposer of round k+4 also choose to extend from round k+1? Its parent is also at least the preferred round.
  3. What would a honest roundLeader node choose to do?
  4. Is forking preferred?
  5. Can the forking go on forever without anything committing?
  6. I am correct that in the “happy path” there are no forks and the commit chain looks like a straight line from top to bottom?
  7. When the roundLeader from round k+3 is again the roundLeader in a later round he actually now has 2 QC’s that he can choose to embed in his next proposal, that of round k+2 and round k+6 for example.

Hopefully someone could answer this for me as I really want to understand this :wink:
And is there maybe another paper that explains this topic in more detail?

1 Like

Hi Jeanpierre,

Thank you for your insightful questions! I’ll answer one by one, first the top-level 1,2, and then the second batch 1-7.

  1. An honest node extends the highest QC it knows
  2. A byzantine node behaves arbitrarily, but honest nodes accept and vote for a proposal only if it satisfies their safety rules.

2nd batch:

  1. when a block commits, the chain prefix up to the block automatically becomes committed as well. indeed, some blocks in the chain do not commit directly, because of gaps in round numbers. they become committed when a later section of the chain becomes committed.
  2. yes
  3. I believe 1 above answers this.
  4. I do not understand the question
  5. A succession of 4 honest leaders with timely communication guarantees that the block at the head of the succession (and the chain prefix leading up to it) will become committed. This is the liveness guarantee we have.
  6. yes
  7. an honest leader will always choose the highest qc.
1 Like

Thank you Dahliamalkhi for your insightful response, this helps me a lot.

Some additional questions that comes to my mind:

  1. When due to a commit other forks are pruned, are these transactions returned back to the mempool?
  2. And is is possible to include the same transactions in two parallel forks?
    Eg: Including the same transactions in round k+5 that were also in round k+1? Since only one chain will eventually be committed.

Great questions.

  1. When due to a commit other forks are pruned, are these transactions returned back to the mempool?

The mechanism is different, but the effect is the same. It’s rather that when consensus pulls transactions from the mempool, it filters out any existing transactions in its current branch (no duplicate transactions in any branch fo the block tree). So there isn’t any returning of transactions to the mempool per se when branches are pruned due to commits.

  1. And is is possible to include the same transactions in two parallel forks?
    Eg: Including the same transactions in round k+5 that were also in round k+1? Since only one chain will eventually be committed.

Due the mechanism I mentioned above, all branches can have the same transactions, but no duplicates within the same branch.

Here’s the code - https://github.com/libra/libra/blob/master/consensus/src/liveness/proposal_generator.rs

1 Like

Thank you aching for your reply. Looking back at this post from the future I could now answer these questions myself :slight_smile:. Momentarily I am trying to understand how SyncInfo message are handled, concurrently or in a queue for instance. Maybe you can answer this one other post of mine: Validator node SyncInfo.