1

Solution: https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf

Although there is a lot of material about this, I am still not sure what the answer is. I found two different statements:

  1. Yes, it does guarantee both liveness and safety as long as 66% are honest.
  2. No, if there is a certain amount of delays, it cannot guarantee safety. https://cs.nyu.edu/rgrimm/teaching/sp07-os/bft.pdf , slide 9

If it is 2., what is the intuitive reason for this to happen? Is it because if the some messages never reach the nodes, they cannot know what the majority of the other nodes are doing/communicating and therefore cannot forward their own decision?

Note: I know this is not a bitcoin specific question but there is no general blockchain forum here.

1

Lamport et al's paper describes multiple problems, each with a unique situation. Liveness is solved for all of those situation as long as the network is synchronous. The original paper doesn't attempt to solve for asynchronous networks, and in fact later work proves that it is impossible to solve consensus in asynchronous networks (FLP).

A latter paper figured out how to guarantee liveness in partially synchronous network (PBFT).

So the accurate way to restate your two bullets:

Yes, it does guarantee both liveness and safety as long as 2/3rd +1 are honest and there is a known maximum to the delays (aka the network is synchronous).

The intuition on why asynchronous networks make the problem hard is that an honest node A who has yet to receive a message from a different node B can't be sure whether B has decided not to vote, or, if B does plan to vote eventually.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.