Papers

Distributed Consensus and Diffuse Trust Systems Samuel M. Smith Ph.D. sam@keri.one https://github.com/SmithSamuelM/Papers/blob/master/presentations/Distributed%20Consensus.pdf

« Distributed consensus enables diffuse trust systems for de-centralized computing infrastructure « Diffuse trust allows secure infrastructure outside a firewall by distributing the attack surface. « Diffuse trust systems can disruptively dis-intermediate centralized computing infrastructure. « Diffuse trust systems enable new business models

Computation nthe “fog” vs computation i the “cloud”

Distrbuted Al

smart contracts

ot

e

f

• Cellular distributed topology. P “Think clandestine spy ring or resistance organization” i [fi" ifiaifie
• Defeating each node (cell, element) requires an %ii.!l | g independent exploit. W No single point of failure. “Universal root privileges" No common mode failures. “Exploit to attain root privileges” vs
• Aslong as the majority or super majority of nodes are not exploited the system is trustworthy. @
• Cooperation between peers vs. authoritarian hierarchy ’Q‘(\@ , &

Distributed Consensus Types « Proof of Work: Simple, highly inefficient, high latency, low throughput * Proof of Stake: More complex, more efficient, lower latency, higher throughput (Asymmetric Proof of Work) * Byzantine Agreement: Most complex, most efficient, lowest latency, highest throughput. « Coin Flip (Hedera) « Verifiable Random Function (Algorand) * Hybrid: .

Distributed Consensus Components « Governance « Distributed Consensus Algorithm « Verifiable Data Structure(s)

Permissioned Distributed Consensus AKA xBFT + Permissioned Distributed Ledgers + Higher speed application-specific distributed consensus Swanson 2015 Utility Database http://www.ofnumbers.com/wp- openst content/uploads/2015/04/ pen storage Permissioned-distributed-ledgers.pdf DHT Transactions « Permissioned governance to address Settlement Sybil attack. Censorship. Smart Contracts Identity Reputation et

«Ansloy tovarin the Byzantine s HistoricalyByzantin gensrals wera prane o tratorousor duplictous act. +TheByzantine General Poblem: o st s ot i H e e ey b i, e sl e, 7 5 e corimunicaton of et otk and confrationof e 0 sl 4 ey and o o 55 st “Byzantnesgreament: Avoldconsensus s uaranteed despte raction o the partcipants behaving ina maliciousanlor v roncous mamer = E ~Consensus despite “Byzanting” faults: - Dropped packets, Emoneous pckets, Halcous Packets, Partioning Sybil Atack A consensus agorithm that solves the Byzzntine consensus roblem in the presence of malcious andlor B2, 'L ronecus behavior s called Bysantie ekt tlerant (3FT). There et festuresofany B consensus soltion: Livensss, ertis, the monfaulty s make s it decion i frie time ooty eratis the nonulty nodes sl ma the same ot decion *Althesclutonsrequie that mafory or supemloty, o he e be nonauy. +Theprablemis usullycouched 353 problem of ditrbutedreplicaton fasequence of staes, that, the non Fauly nodes wilall replicate the same sequence o staes (decions). ~For example the squence of ansactons entered ko shared pubit g or shared publc databaseis thesequenceofstates, .

Practical Byzantine Fault Tolerance (PBFT) http:/jpmg.csail.mit.edu/~castrofosdigg_htmljosdigg.html

Synchronous Systems: Al steps proceed in rounds. Al message transmissions between nodes fully complete within each round. Consensus at the end of each round. Asynchronous: Steps occur at varying times. Message transmissions happen whenever. Consensus? Fundamental Constraint: In an asynchronous system it is impossible to achieve consensus with one faulty node. Impossibility of Distributed Consensus with One Faulty Process; Fischer, Lynch, Patterson, JACM Vol. 32, No. 2, April 1985, pp.374:382. https://groups.csail.mit.edu/tds/papers/Lynchfjacm8s.pdf B

Sequential consistency among nodes: Results of any execution is the same as if the operations on all the nodes were executed in some sequential order. Linearizable: Sequential consistency that respects the real time order of events. State Machine Replication: Lots of things can be expressed as a state machine Goals: Build a linearizable replicated state machine. Agreement on operations and their order. Replication to provide availability while preventing faults including malicious ones. o

Byzantine Faults: Delay, Error, Stop, Duplicate, Reorder, Malicious Data. Honest nodes: Dishonest nodes: Faulty nodes: Liveness: Quorum of non-faulty nodes make a joint decision in finite time. Weak synchrony via timing bounds [h, H]. Delay does not grow faster than time. delay(t) = o(t) Safety: Aquorum of non-faulty nodes all make the same joint decision. Consensus despite Byzantine faults on some nodes. Consensus despite out-of-bounds delay on some of the honest nodes. B

All messages between nodes are signed (): Typically some combination of message authentication codes (MACs) with shared secrets and true digital signatures. Modern ECC digital signatures ameliorate many of the performance advantages of using MACS while enhancing security (nonrepudiation). At most f faulty nodes during any step (the salient f): Honest nodes behave deterministically: Honest nodes fail independently: No systemic or common mode failures Weakly synchronous: Bounded time to respond 2

N=cf+1 N is the total number of nodes. f is the number of allowed faulty nodes at any time (process step). N=f+1 Correct Agreement: Given at most f faults or f faulty nodes, any agreement of f+1 nodes is correct because at least one of the f+1 nodesis honest. No guarantee that any set of f+1 nodes will ever be in agreement. Ne2f#1 Correct Majority Safe Agreement: Given 2141 nodes, at least f+1 are non-faulty, ensuring an agreement with a correct non-faulty majority. Guarantees that a correct majority of f+1 nodes will agree. No guarantee that the agreement s live; the majority may not know they are in agreement. N=3f+1 Correct Majority Live Agreement: Up to f honest nodes may no longer respond, so we need 3f+1 = 2f+1+ nodes to ensure, in bounded time, that a correct majority knows that a correct majority was i agreement. N=3f+1 Correct Majority Live Safe Agreement: N+is the Quorum size that ensures a Quorurm is formed in bounded time. 2fstis the minimum Quorum size to ensure Correct Majority Safety. Given the Quorum size, N+ = 27+, find the minimum N for which the bounded time intersection of any two quorums will include atleast one honest node, e, size of intersection, 2 f+1. 5

If any two pairwise Quorums must be in agreement, then all possible Quorums will be in agreement. 2f+1is the minimum Quorum size to ensure correct majority agreement. N-fis a constraint on the Quorum size relative to N that ensures a Quorum is formed in bounded time. Given the Quorum size s N+ 2 2f+1,find the minimumm N such that the intersection of any quorum partition includes at least one honest node. Intersection contains one honest node if size of intersection, | 2 f+1 Overlapping Quorums [0, ] o,vQ, For set S, the cardinality [S]is the number of elements of S. f A1 f One honest node included in intersection if: [2) NG, 9,

[0.nQ|2f+1 "

Proof of Quorum Size Recall that the upper bound on quorum size given bounded time is N-f. Forset s, the cardinality |S|is the number of elements of S. . Phrased in terms of cardinality (size) of the quorums. Overlapping Quorums [0,.0, ] loJ=N-7 (Y] I lo|=n-7 f +1 f lovel=N~ [0} 2,nQ; [ settheoryequalty [0 +|0) =|0, L Q)|+/@ NQ)| lol+[e] e ve=lene[>F+1 (N=f)+(N-f)-N2f+1 One honest node if: N-2f2f+1 leng|zf+1 N22f+f+123f+1 min(N) > N=3f+1->N-f=2f+1 -

Fundamental Rule for Stepwise Live Agreement Given that f of the nodes that come to agreement in the current step may become unavailable in the next step, then at least 2f+1 nodes must come to agreement in the current step to ensure that at least f+1 of those nodes will remain available to correctly carry that agreement into the next step. Therefore, all steps but the last step must have at least 2f+1 nodes in agreement. Given that at most f nodes may be faulty during any step, newly non-faulty nodes in the current step may have been faulty in the previous step, and vice versa. -~

@ 7N Think step-wise racheting agreements "[j/f//‘@%/\éfi =SS A (// dy/ N LN %/Mvfl,\fl ©

Mg, <PREPREPARE,V,N,D(M)g, | PREPAREVNDIM)G, | <COMMITY,Mg, | <REPLY, i dlient c! 1 /‘ 7t ropica 0 ; SE- : , AN &7 I N N A epicaz XN A Execute Client multcasts request toreplicas . REQUEST<o.t,c>0, REPLY <v,t,c,i,r >0, Primary inates 3 phase commit . ‘ Client colects replies from repiicas, . fu1 comect replies before timeout indicates success o=operation V= view number vald signsture £ = request timestamp i=replicaid Disinct o replicas i but same tand c=clientid r=resultofo Each replica accepts request o, = clientsignature 0, = replicaisignature Verifiessgnature logs request "

Pre-Prepare i \N A R N 7/ feplica 0 SK =N e g B s | Exetute Primary replica initiates 3 phase commit PREPREPARE <v.n,d(m)>G, Multicasts pre-prepare with proposed order n v = view number Backup replicas accept and log pre-prepare = sequencenumber Verify signature and digest of request d = digest Verify backup is in same view m = request message Verify not accepted different request for n p=vmodN Enter prepare phase w ©,, = primary replicasignature

Mg, <PREPREPAREN,N.D(M), PREPAREV.NDIMPG | ccomumyim, | <REFLY., SN N AR D, "8 /4 - N ,:, €6\?,v / e Y RS/ TN NS K JEso epica > 7S topicas i H i Exetute Backups Iniiate prepare phase Multicast prepare to all replicas PREPARE <v,n,d(m),i>0, Backup replicas accept and log prepare v=view number Verlfy signatures and yn,d match i= replicaid Backup iis prepared IFF = sequence number pre-prepare and 2f matching prepares d = digest knows a safe quorum agrees on nfor minv m = requestmessage 1f prepared(m,yn,)is True, Then prepared(m,y,n,)is False for i) 0, = replicaisignature o

Mo, <PREPREPARE,V,ND(M)gy| PREPAREV,NDIMYG, | <commIrv,og, | <REFLY, Y ¥ SN ot \ S xS iz P N epica replica3 T N Exetute Backups initiate commit phase COMMIT <v,n,i >0, Multicast commit to all replicas v = view number Backup replicas accept and log commit . n=sequence number Backup i performs operation o IFF Prepared i=replicaid 2f+1 matching commits including own (quorum) o, = replicaisignature lower order n operations have been performed »

Mg, <PREPREPARE,V,N.DIM) | SPREPAREVN.DIM)G, | <coMMT, Vg, | <REPLY, Y dient e H /‘ T = . < \ o £ K o /o X =N AR = AR AN s Erekute Backups reply to client. REPLY <v,1,0,i,r >0, v = view number i=replicaid r=resultof o 0, = replicaisignature B

Log Checkpointing Infinite log Checkpoint Log state periodically Digest of og state Multicast digest of log state to other replicas CHECKPOINT <d(s),i >0, 2f+1 digests of matching state is quorum Checkpoint and discard older log entries d =digest s=logstate i=replicaid o, =replicaisignature 2

Faulty Primary Primary deterministic p =vmod N VIEWCHANGE <v+1n,C.P.i>0, Vi I fews may overlap V= faulty view number

Restart view by re-issuing pre-prepares from failed view. 1, = sequence numberof st stable checkpoint s View change request triggered by € =setof2f + Lcheckpointmessages

Client Timeout rebroadcast request which starts replica P =setofsetsF, foreachmpreparedati withn, >,

timer P, = Iprepreparc+- 2 prepare

• N = requestmessage

eplica Timeout generates view change request i repienid If primary given by v receives 2f view change plus own 0, = replicaisignature =

New View If primary given by v+1 receives 2f view change plus own

Multicasts new view to replicas NEWVIEW <v+1V,0>0, Oset of pre-prepare messages

After last stable checkpoint v = faulty view number

Contained in a least one P of view-change messages p=+1)modN

Use no-op for sequence number gaps V = set of view change messages

O = set of pre-prepare messages 0o, = primary replicasignature 2

Performance PBFT BFS about 10- 20% slower than NFS under normal operation 90% performance degradation for fault recovery view change. »