Skip to content

Instantly share code, notes, and snippets.

@bachase
Created February 2, 2018 14:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bachase/6f92b3907baeb3e8cf3ffd5fd8df5f31 to your computer and use it in GitHub Desktop.
Save bachase/6f92b3907baeb3e8cf3ffd5fd8df5f31 to your computer and use it in GitHub Desktop.
Uncommitted Support Definition

The example below from @ChronusZ motivates why you need to treat validators whose last validation is less than your largestIssued validation as uncommitted.

Consisder 10 nodes, 8 are honest and 2 are Byzantine. The diagrams below are the "ground truth" of the honest nodes' working ledger.

    B1 (4) --- C1
  /
A 
  \
    B2 (4) --- C2

Start with 4 honest nodes that last validated B1, and 4 honest nodes that last validated B2. Until the Byzantine nodes weigh in, this is an unbreakable tie, so the nodes prefer to stick with the branch they are on. Suppose the Byzantine nodes send validations in favor of the B1 branch to just 2 of the B2 nodes. Those 2 B2 nodes then switch over to C1:

   B1 --- C1 (6)
  /
A
  \
    B2 (2) --- C2

One of these C1 nodes receives all 6 of these C1 validations. The 2 Byzantine nodes also send it C1 validations, so it sees 8 of 10 and fully validates C1.

Meanwhile, consider the four nodes who initially validated B1. As above described above, they have yet to see any Byzantine nodes votes, so they stuck with their current branch and validated C1. But suppose they don't receive any of the C1 validations (except their own) due to network delays. Instead, the Byzantine nodes send them 2 validations for B2, so they see 6 validations for B2 and switch:

    B1  --- C1 (2)
  /
A
  \
    B2 (6) --- C2

Now all the B2 nodes stay on the second branch until

   B1 --- C1 (2)
  /
A
  \
    B2 --- C2 --- D2 (6)

If the 2 Byzantine nodes validate D2, all these nodes now see 8 of 10 votes to fully validate D2, which is a fork with the one node that fully validated D1.

The issue was that the C1 nodes didn't wait for the updated opinions of the formerly B2 nodes.

@wilsonianb
Copy link

wilsonianb commented Feb 2, 2018

To make sure I understand

The issue was that the C1 nodes didn't wait for the updated opinions of the formerly B2 nodes.

is referring to

But suppose they don't receive any of the C1 validations (except their own) due to network delays. Instead, the Byzantine nodes send them 2 validations for B2, so they see 6 validations for B2 and switch

The C1 nodes should have considered the B2 validations as uncommitted since they are for a lower a seq than C1 nodes' largestIssued. They should not have switched but instead should have stuck to their current working ledger, since the B2 branch would not be preferred.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment