[Resolving the Availability-Finality Dilemma](https://decentralizedthoughts.github.io/2020-11-01-ebb-and-flow-protocols-a-resolution-of-the-availability-finality-dilemma/) ## DLS and Nakamoto: Where to Go From Synchrony? *Synchrony* - assumed that all communication between honest parties suffer from a delay bounded by $\Delta$, known to the protocol Doesn't capture network partitions - periods of extraordinary delay *Partial Synchrony* - Introduces global stabilization time GST. Before this, the adversary can delay network messages arbitrarily. After, the delay is bounded by $\Delta$ Security guaranteed if less than 33% of nodes are adversary ![[Pasted image 20230912123610.png]] Bitcoin and [[Nakamoto Consensus]] is an extension of the synchrony model that's different from partial synchrony. Previously, all honest nodes were expected to always be awake Nakamoto says they can be sleepy, implicitly introduced [[sleepy model]] ## A Tale of Two Protocols These two extensions of the synchronous model have sparked two different families of protocols BFT protocols like [[PBFT]] and [[HotStuff]] designed to operate under partial synchrony Provide a strong notion of finality - once a decision is made under no circumstances will it be reverted (assuming no more than 33% of nodes adversarial) All participants asked to vote for a proposed block. Quorum needed for it to be appended to chain If there's a network partition, quorum not reached in individual parts Prevents confirmation of conflicting blocks, preserving finality On the other hand, if there's low participation, then the chain stalls. No dynamic availability Longest-chain based protocols enhanced liveness and designed to operate under [[dynamic participation]] Miners/validators run a lottery, where the winner gets to append a block with new tx If there's a network partition, both sides keep going and building The partition healing requires all but one chain to be reverted, resulting in a safety violation ## From Protocols to Trust Assumptions Participating nodes in longest chain protocols are optimistic, while those in BFT protocols are pessimistic ## [[availability-finality dilemma]] Can we have a consensus protocol that provides both dynamic availability and finality No! ## The [[ebb-and-flow]] Property In [[Nakamoto Consensus]], the k parameter of k-deep confirmation rule provides a tradeoff between confirmation latency and error probability Small k means fast latency but high error probability Each client can set their own k, and share a stabilized common account of history What if we had a protocol with 2 confirmation rules that outputs two ledgers: - One that provides availability under dynamic participation - One that provides finality even under network partitions Consider a network environment where: - Communication asynch until a GST after which comms are synch - Honest nodes sleep and wake up until a global awake time GAT afte rwhich all nodes are awake. Adversary nodes always awake *Then,* we say protocol $\Pi$ is a **($\beta_{1},\beta_{2}$)-secure ebb-and-flow protocol** if it outputs an available ledger and a finalized ledger satisfying the following properties: - Finalized ledger guaranteed to be safe at all times and like after max{GST,GAT}, provided that fewer than $\beta_{1}$ proportion of awake nodes are adversarial - Available ledger guaranteed to be safe and live at all times after GST, provided that fewer than $\beta_{2}$ proportion of awake nodes are adversarial - Finalized ledger is a prefix of the available ledger at all times Gasper was intended to do so but suffers from a liveness attack during synchrony ## The Snap-and-Chat Construction *Snap-and-Chat protocols* provably satisfy ebb-and-flow, and do so with optimal resilience Uses dynamically available protocol (longest chain) and partially synchronous BFT protocol ([[PBFT]], [[HotStuff]]) Nodes execute snap-and-chat protocol by executing the two sub-protocols in parallel Dynamically available protocol takes transactions and outputs an ever-increasing ledger generated by whatever confirmation rule is native to the protocol (ex. k-deep confirmation) Over time, nodes take snapshots of ledger based on their curent view and input them into the partially synchronous BFT protocol for finalization Final result is the dyn avail protocol appended to the finalized ledger to form the available ledger Sanitized such that the finalized transactions take precedence over the dyn avail in case of conflict To break safety, an adversary could input unconfirmed transactions into the second (finalizing) ledger. *To Mitigate:* In the BFT protocol, each honest node boycotts the finalization of snapshots not confirmed in the dynamically available ledger in its view **Theorem:** Snap-and-chat protocols are (1/3,1/2)-secure ebb-and-flow protocols This construction achieves conssitency between the two ledgers without sacrificing the best possible security guarantees of the individual ledgers.