Streamlet (2020) ================ PBFT is live under *weak synchrony* Network/node delays grow at a bounded rate (e.g., polynomially) Keep doubling timeout until eventually all nodes in same view for long enough Another model: *partial synchrony* Initially, things may be very crazy Eventually reach some global stabilization time GST After GST, nodes can communicate within some timebound Delta The catch: don't know GST (so Byz. generals still not safe) Another variation: the unknown Delta model Synchronous, but don't know what delta is Two models have same power E.g., increasing estimate of Delta is like increasing timeouts in PBFT Blockchain digression: Say we replace credit card #s w. public keys? Hold private key on cell phone Sign each transaction with amount, recipient, comment What would this fix? Credit card numbers would be harder to steal Lower fraud could lead to lower (but still non-zero) transaction fees Could also lower fraud-detection false positives Could give merchants protection (eliminate "card not present" transactions) How does this compare to cash? Worse privacy, third party trust, bank control, transaction charges Bitcoin attempts to get rid of the bank... Transfer ownership of digital BTC between different public keys Must solve 2 problems for this model to work: 1. How do you distribute Bitcoin so people believe it has value? 2. How do you prevent someone from double-spending a Bitcoin? Public key A is worth 1 BTC A pays 1 BTC to B, walks away with some goods A tries to pay 1 BTC to C, walk away with more goods Note that problem #2 is basically consensus--"timestamp server" With timestamp server, everyone agrees A->C message later than A->B Hence A->C is not valid, because A is already spent Keep ordered transaction history as a giant replicated state machine How Bitcoin do consensus? Proof-of-work mining Flood new transactions History progresses in blocks of new transactions: block = { H(previous-block), nonce, H*(new-transactions) } Note inclusion of previous block makes this a *block chain* By convention, only accept block if H(block) < target-value Currently H(block) must start with >=76 0 bits. So must try an expected 75 hextillion (75*10^21) nonces to find good one Finding these nonces, known as "mining", is computationally very hard So incentivize finding the next block with bitcoins! First transaction in block is special "coinbase" transaction Creates 6.25 new BTC paid to block miner Note: adjust target-value as more miners come on-line In practice, new blocks mined every 7-10 minutes or so Given two incompatible block chains, take one with most work (~tallest) Note we've just solved both the coin distribution and consensus problems! How does this solve the double-spending problem? Well-behaved nodes ordinarily shouldn't fork block chain Assume ill-behaved nodes have less aggregate compute than well-behaved ones (Though 49% limit is inadequate http://arxiv.org/abs/1311.0243) If bad buys don't immediately fork chain and double spend, can't catch up After receiving payment, before handing over goods, wait for several new blocks (e.g., ~1hr) to cement payment in history And note mining payouts incentivize honest behavior even by greedy miners Which of safety, liveness, and fault-tolerance does Bitcoin offer? Liveness and Fault-tolerance (anyone can unilaterally mine a block) It's also randomized (since guessing nonces), so not subject to FLP But Bitcoin not safe w/o synchrony assumption Under network partition, miners create arbitrarily deep forks Also not safe against computationally-powerful attackers Another problem: People want actual money, bank-like value guarantees E.g., facebook tried (failed) to created libra/diem currency-backed blockchain Used f-out-of-3f+1 BFT consensus among closed consortium Chose algorithm called HotStuff (chained hotsuff similar to streamlet) Are there non-payment/finance applications for blockchain? Hypothetically yes Timestamping - prove you created a document by a particular time Transparency - commit to some public append-only history, e.g., could use to improve certificate transparency iphone could refuse to install firmware not posted to blockchain Problem: mining not appropriate for non-cryptocurrency applications Streamlet motivation: support close blockchain Why not use PBFT for blockchains? Short answer: you could (e.g., hyperledger fabric supports this model) But PBFT is complicated PBFT optimizes for latency at an irrelevant level for blockchains PBFT may have bursts of requests and periods of inactivity Also with many replicas, PBFT has large message sizes and counts Streamlet paper doesn't address (but see HotStuff) Idea: take advantage of blockchain structure to simplify consensus Batching transactions into blocks anyway, so can tolerate latency Each block securely identifies all prior blocks Constantly producing blocks (e.g., can leverage block n+1 to finalize n) The setting for Streamlet: n numbered nodes, f < n/3 Byzantine faulty partially synchronous with Delta timebound after unknown GST assume all nodes *implicitly echo* all messages received (wasteful) So if a non-fault node receives a message at time r, all non-faulty nodes will receive it by time max(GST, r+Delta) proceed through epochs of duration 2*Delta agree on blocks of the form: (h, e, txs) txs are transactions to append to blockchain history e is epoch number of block - not all epochs included in finalized history h is hash of previous block or special genesis block (\bot,0,\bot) *length* of block B, |B|, is distance to genesis block (length of chain) each epoch has a pseudo-random leader determined by H(e) mod n How does the protocol work (p. 7)? For each epoch e: A block signed by 2n/3 nodes is called *notarized* Propose: Leader broadcasts signed <(h,e,txs)> h must be one of the longest notarized chains leader has seen before Vote: upon receiving the first proposal <(h,e,txs)> from epoch e's leader If h corresponds to one of the longest notarized chains received then vote for block by signing it, broadcasting signature Can't vote for previous epochs or for multiple blocks in same epoch Finalize: when you have 3 notarized blocks with successive epochs: B0=(h0, e, txs0), B1=(H(B0), e+1, txs1), B2=(H(B1), e+2, txs2) Okay to finalize B1--agreement is guaranteed What goes wrong if you just finalize every notarized block? If signature msgs delayed, nodes might not know a block is notarized Hence, might notarize multiple blocks at the same length What if you finalize first of *2* notarized blocks in consecutive epochs? B0=(h0, e, txs0), B1=(H(B0), e+1, txs1) Could have multiple blocks B0, B0' notarized at length |B0| Nodes might notarize B1 but the signatures are delayed, so don't realize Later, notarize B1'=(H(B0'), e+2, txs1'), B2=(H(B1'), e+3, txs3) So actually B0 was eventually excluded from history! So why is first 2 of 3 successive notarized epochs the answer? Honest nodes only vote once per epoch, so only one notarized block per epoch Say you notarize B0<--B1<--B2 at epochs e, e+1, e+2 respectively You might notarize multiple blocks of length |B0| But you can't notarize B!=B1 with |B|==|B1|. Why? Proof by contradiction: Say B finalized, let eB be B's epoch eB can't be e, e+1, or e+2 (only one notarized block per epoch) But also can't have eB < e: B's parent is longer than B0's parent by one block So if 2n/3 nodes saw B's parent notarized in epoch eB < e, then 2n/3-f > n/3 couldn't vote for B0 in epoch e Also can't have eB > e+2: B's parent is shorter than B2's parent by one block So if 2n/3 nodes saw B2's parent (B1) notarized in epoch e+2 then 2n/3-f > n/3 couldn't vote for B in epoch eB > e+2 Finalize B1 (+ancestors) when guaranteed only 1 notarized block of len. |B1| Now say we reach GST, and all communication happens in Delta... What happens (post-GST) after 2 honest leaders (L0,L1) in epochs e, e+1? Proposals guaranteed to increase in length--why? Say L0 proposes B0 in epoch e If B0 gets notarized, L1 will choose B1 with B0 as parent, so |B1|=|B0|+1 Otherwise, notarized B with |B|>=|B0| blocked vote for B0 at honest node By implicit echo, all nodes will recognize B notarized by e+1 So L1 will propose B1 with parent B (or some other node w. length >=|B|) Means |B1| - 1 >= |B| > |B0| Big picture: after honest leader epoch, all nodes have same honest node info Epoch e represents 2*Delta time in which nodes won't sign blocks before e By e+Delta, everyone has all signatures from honest nodes in prior rounds By e+Delta, everyone has honest leaders's latest proposal So vote/not vote by e+Delta, at e+2*Delta (start of e+1), all hear votes Of course, faulty nodes can inject last-minute votes What happens after 3 honest leaders (L0,L1,L2) in successive epochs e,...,e+2? Are they guaranteed to finalize a new block? No Imagine right before GST+honest leaders we have: B0 <-- B1 <-- B2 B0 is notarized B1 is notarized but n/3 honest nodes haven't heard B2 has 2n/3-f votes from honest notes, f nodes withholding vote L1 might not have heard about B1 by epoch e, chooses parent B0, loses vote In e+1, all nodes see B1, so L2 proposes B1 <-- B2' Bad nodes vote for B2, so by e+2, B2 is notarized L3 proposes B0 <-- B1 <-- B2 <-- B3, B3 successfully notarized by e+3 Bad: epochs in blocks not successive, can't finalize Good: B3 notarized and no other block of length |B3| can be notarized--why? because of synchrony, all honest nodes see B3 notarized by e+3 so none will ever again vote for a block that doesn't descend from B3 Note, good property holds for any configuration at start of GST By e+1, honest nodes hear all votes from known notarized blocks before e Might not know of last notarized block not seen by honest nodes before e But L1's proposal will at least tie with longest notarized blk before e Proposals get longer with each successive honest leader Therefore L2's proposal must be longest yet and get notarized What condition guarantees new block? 5 successive non-faulty leaders after GST First three leaders produce a notarized |B3| unique for its height Next two leaders produce notarized B3<-B4<-B5 w. successive epoch numbers How to keep the clocks synchronized If you see f+1 messages with higher e, jump to it immediately Maybe also reset the timer when this first happens? Still need to timeout through multiple rounds of faulty leader w/o sync How does synchronous variant work for n nodes, f < n/2? Notarization requires n/2 nodes, not 2n/3 What's to stop two partitioned of size n/2 from disagreeing? Synchrony assumption rules out network partition (Recall Byz generals--sync. model doesn't limit # of faults tolerated) To finalize block at epoch e: Need chain of *6* notarized blocks in consecutive epochs (e,...,e+5) AND Must see no conflicting notarized blocks at the same lengths Can you notarize two blocks in the same epoch? Yes But say non-faulty node v sees B is notarized in epoch e ("Fact 4") All nodes will see any messages v saw (and agree B notarized) by e+2 And say B0 <-- B1 notarized at e, e+1 respectively ("Lemma 7") Means some honest node saw B0 notarized in e+1 So no B with |B|<=|B0| can be notarized in e+3 or later Suppose two honest nodes finalize chain (ending B0...B5) and chain' Must be that B0 appears in history of B0'. Proof by contradiction Assume w.l.o.g. chain no longer than chain' Let B0,...,B5 have length l-5,...,l and epoch e-5,...,e Let B0' = chain'[l-5], B1' = chain'[l-4]; let e' be epoch of B1' By assumption, B0' != B0 By lemma 7, epoch of B1' must satisfy e' < (e-4)+3, or e' <= e-2 By lemma 4, by e'+2, all nodes will see B1' notarized But e'+2 <= e, meaning by e, all nodes see B1', preventing finalization Nits to pick: Notarization should wait for >2n/3 rather than >=2n/3 Remember quorum size T = f_S + f_L + 1 So if N = 3k and T = 2k, best to choose f_S = k, f_L = k - 1 Instead, authors chose f_L > f_s, which is not useful With multiple longest notarized chains, have leader pick largest e? More likely to be prior epoch, maybe lead to faster finalization How might you get rid of implicit echo? Like HotStuff, coordinate all messages through the leader Leader broadcast proposal, all send votes, leader broadcasts votes Threshold cryptography can make this even better Instead of sending 2n/3 signatures, combine into single threshold signature