Week 9 Other
distributed consensus
models and protocols
Distributed consensus problems and protocols with finality of confirmation.
Copyright By PowCoder代写 加微信 powcoder
Byzantine fault tolerance and protocols
Pros and Cons of the Longest Chain • Liveness Protocol
o Even a single honest miner with a small hash power can extend the longest chain
o Guaranteed when hash power of honest nodes is more
o But with 2 caveats
• Probabilistic guarantee
• Network must be synchronous
Byzantine Fault Tolerant (BFT) Protocols
• Deterministic safety even under asynchronous network
• Two closely related protocols: o Streamlet
o HotStuff
BFT Protocol Setting
• Number of Participants is fixed
• Identities known (signatures) to all nodes
• In other words, “permissioned”
The distributed consensus problem
• Each process i has an input vi, it requests each to output v that is one of the inputs.
• Agreement: no two processes output different values.
• Consistency: If all the inputs are the same, then it must be the
• Termination: every process eventually terminates.
BFT Steps (Round
• In each round: 131313
1. Propose a new block 2. Vote 3. Notarized
BFT Confirmation Rule
• 2N/3 is the minimum quorum size.
• This guarantees at most one block per round can be notarized
as long as number of malicious nodes is less than N/3.
• The set of distinct votes on a notarized block is called a quorum certificate (QC).
• Proceeds in lock-step rounds, each of which takes twice the communication delay
o One leader elected every round
o Leader will collect pending Tx and put a block together and
o Whenever a block is proposed
• Checks if signed by leader with rights to propose in round r
• Vote on a proposed block if the block extends the longest notarized chain (a block is
notarized if it receives at least 2N/3 votes)
• All nodes re-broadcast all messages they hear of
• A node does not vote for conflicting blocks
Block Structure
signature L
hash pointer to a parent block
Two blocks from two different rounds on the same height may both be notarized.
Confirming a block as soon as it is notarized is not safe
• Confirming a k-deep notarized block is not safe 3579
• Correct rule: On seeing three adjacent blocks in a notarized blockchain with
consecutive round numbers, a player can confirm the second of the three
blocks, and its entire prefix chain.
B2 B5 B6 B7
13X B1 B3 B
: Notarized
: Confirmed
Streamlet Liveness
When network conditions are good, Streamlet makes progress whenever there are five consecutive rounds whose leaders are all honest.
Streamlet Performance
• Communication complexity
• Confirmation latency
Communication Complexity
• Echoing incurs n3 voting messages per block
• Reducing the communication cost is non-trivial
Communication Complexity
Source: https://dahliamalkhi.github.io/posts/2020/12/what-they-didnt- teach-you-in-streamlet/
Streamlet Complexity
• Lower bound: At least n−1 messages are needed to spread the block among all nodes
• Linearity: communication complexity that is linear in the number of nodes
• Streamlet is not linear
• Guarantee liveness whenever there are 5 consecutive honest proposers
o Happens on an average once every ! ≈ 7.6 rounds,
o Recall Bitcoin latency is ((*+,’ ! ! )∆ where . is the
confirmation error probability and /∆ ≪ 1 for security
Clock Synchronization
• Responsiveness: the ability to advance at the speed of the actual network delays without waiting maximal network delays
• Streamlet is not responsive
• State of the art BFT consensus protocol
• Similar to but proposed earlier than Streamlet • HotStuff is linear and responsive
• n =3f+1, f Byzantine nodes
• Quorum certificate (QC): 2f+1 votes on one block • QCs are on chain
HotStuff Difference
• Each block is linked to its parent via the parent’s quorum certificate (QC)
• A proposer can propose a new block right after it receives a new QC
From Streamlet to
• HighQC: Every node keeps the QC with the highest round number it knows of
• As in Streamlet
• A leader proposal extends highQC
• A node votes for a leader proposal if it extends the branch
of its highQC, but only sends the vote to the leader of next
round à Linearity
• Finalization rule: same as in Streamlet:
Clock Synchronization
• HotStuff does not require round synchronization for safety • Time drivenàevent driven
• HotStuff is responsive
Conclusion
• Blockchain protocols with finality: Streamlet and HotStuff o Permissioned: fixed number of participants with known
identities
o Security: liveness is weakened in the pursuit of strengthening safety guarantee to a finality
Permissionless
finality of confirmation
protocols with
Byzantine Fault Tolerant (BFT) Protocols
• Deterministic safety even under asynchronous network
• We saw two closely related protocols: o Streamlet
o HotStuff
BFT Protocol Setting
• Number of Participants is fixed
• Identities known (signatures) to all nodes
• In other words, “permissioned”
• How do we go to permissionless?
o Unknown number of participants o Arbitary identities?
Permissionless
consensus via BFT protocols
• Known upper bound on participants, known identities but variable participation at any time
• “Strategy”: elect a committee of N nodes from the set of participants.
o The election can be verified in a distributed manner
o Can be implemented via hash functions, and randomness
from within the blockchain
• The committee proposes a block and implements consensus via a BFT protocol.
Random Committee Election
• As long as 2/3rd of the committee is live and honest, the BFT protocol is secure
• Electing a committee of fixed size (N) is hard
• Easier to elect a committee of random size o with desired mean value (N)
o Hash functions
blockchain
Random Committee Election in Practice
• Electing a committee of fixed size (N) is hard
• Easier to elect a committee of random size
• E.g., Total 1M users, E[N] = 1000, p = 0.001
o X = #honest in committee ~ Binomial(700K, 0.001)
o Y = #Byzantine in committee ~ Binomial(300K, 0.001) o Liveness: X > 2N/3
o Safety: X + 2Y < 4N/3
Probabilities of Safety and Liveness
Vulnerability to Adaptive Adversary
• Adversary is static
o So random number of Byzantine players
• Adaptive adversary
o Can turn Byzantine after being elected into the committee o Long range attacks (can turn adversarial much later in time) o Fatal
• Need for randomness even within actions of adversary o Player replaceability
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com