Distributed Consensus and Diffuse Trust Systems Samuel M. Smith Ph.D. smith.samuel. n@gmail.com 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 Computationin he “fog” vs computationinthe “coud” ~oisrbuted A St contracts ot B ,
- Cellular distributed topology. @*“.{'@5«, g i & “Think clandestine spy ring or resistance organization” o T i ine spy ring rganizati &‘g‘{%,‘mv
- Defeating each node (cell, element) requires an & fi -8 ;[—' |\ P 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. fi
- Cooperation between peers vs. authoritarian hierarchy f)%\@ 3 &
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. * Hybrid:
Distributed Consensus Components « Governance + Distributed Consensus Algorithm Data Structure
Permissioned Distributed Consensus AKA XBFT + Permissioned Distributed Ledgers + Higher speed application specific distributed consensus Swanson 2105 Database http://lwww.ofnumbers.com/wp- Open Storage content/uploads/2015/04/ DHT Permissioned-distributed-ledgers.pdf Transactions « Permissioned governance to address Settlement Sybil attack. Censorship. Smart Contracts Identity Reputation - etc...
«Ansloy tovearin the Byzantin s ~Historically Byzentine generas were pron toteitorous orduplctous scts. +The Byzantine Genersls Proble: Twoseparated general agree toaitack . I the two utethey both win. f ether attacks alone he foses. 774 e corimuncaton of tnt 0tk and confrationof a0 sl S ey and o s 5 st ~Byzantine sgreement: Avald consensus is guaranteed despite a fraction of th partcpants behaving i malciousandior - emoneous mamner = Dropped packets, Eoneous packets, Malicious Packets, Patitonin; Sybil Attack A consensus algorithm tha olves the Byzzntine consensus problemn the presence o malicious andior £, ermoneous behavior is called Byzantine ot tolerant (87T, +There are twofeaturesofany BF consensus soltion: LUiveness,that s, the non-fauty nodies make a oint decision n e time. Safety, that i, the non faulty nodes ll make the same ont deciso. «Allth solutionsrequire that a maforiy o superalorty, of thenodes be oy +Theprablemis usullycouched 353 problem o ditrbutedrepicaton fasequence of staes, that, the ‘non-auty nodes wilal replicae th same sequence of staes (decisions). +For exampe the sequence of ransactons entered to shared publicledger or share publc databasels the sequence ofstates, [
Practical Byzantine Fault Tolerance (PBFT) http:/jpmg.csail.mit.edu/~castrofosdigg_html/osdigg.html
Synchronous Systems: Allsteps proceed in rounds. All 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/tdslpapers/Lynchijacm8s. pdf a
Sequential consistency among nodes: Results of any execution is the same as f 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 i finite time. ‘Weak synchrony via timing bounds [, H]. Delay does not grow faster than time. delay(t) = o(t) Safety: Quorum of non-faulty nodes all make the same joint decision. Consensus despite byzantine faults on some of the nodes. Consensus despite out of bounds delay on some of the honest nodes. f
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: Honest nodes behave deterministically: Honest nodes fail independently: No systemic or common mode failures ‘Weakly synchronous: Bounded time to respond »
N=cf+1 N is the total number of nodes. f is the number of allowed faulty nodes at a time (process step). N=f+1 Correct Agreement: Given at most f faults o { faulty nodes, any agreement of f+1 nodesis correct because at least one of the f+1 nodes is honest. No guarantee that any set of f+1 nodes wil ever be in agreement. N=2f+1 Correct Majority Agreement: Given 2f+1 nodes at least f+1 are non-faulty ensuring a correct non-faulty majority. Guarantees that a correct majority of f+1 nodes will be in agreement. No guarantee that the agreement islive i.e. majority may not know that they are in agreement. N=3f+1 Correct Majority Live Agreement: Up to f honest nodes may no longer respond so need 3f+1 - 2f+1+f nodes to ensure in bounded time that correct majority know thata correct majority were in agreement. N=3f+1 Correct Majority Live Safe Agreement: N5 Quorum size that ensures a Quorur is formed in bounded time. 2f+1is minimum Quorum size to ensure correct majority. Given Quorum size of N-f = 27+1 , find N for which the intersection of any two quorums willinclude at least one honest node ie. intersection of of size f+1. [
If any two pairwise quorums must be in agreement then all possible quorums will be in agreement. 2f+1is minimum Quorum size to ensure correct majority agreement. N+ s constraint on Quorum size relative to N that ensures a Quorum is formed in bounded time. Given Quorum size of N+ 2 2f+1, find minimum N such that the intersection of any quorum partition includes at least one honest node. Intersection contains one honest node if size of intersection s 2 f+1 Overlapping Quorums [@,.0;] [ Y] For set S, the cardinality |S]is the number of elements of S. f A1 f One honest node f: [2) NG, 9,
[0.nQ|2f+1 "
Proof of Quorum Size For set's, the cardinality [S|is the number of elements of S. Phrased in terms of cardinality (size) of the quorums. Overlapping Quorums [0,.0, ] lo|=N-f Q,VQ, lo|=N-r f 1 f lovol=N 0 +|Q)|=|Q,vQ,|+]0, N Q, o | ams | o lekio|-io.00 e ol lol+lo/-lo,vo=lo.nofzs+1 (N=f)+(N=)=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,
®
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 Exebute Cllent multcasts request toreplicas N . REQUEST<o.t,c>0, REPLY <v,t,c,i,r >0, Primary infiates 3 phase commit « : Client colects replies from replicas, i o b 41 comect replis before timeout ndicates success o= operation V= viewnumber Valid signature £ = request timestamp i = replicaid Disinct o replicas but same tand c=clientid r=resultofo Each replica accepts request o, = clientsignature 0, = replicaisignature Verifessignature logs request I
Pre-Prepare "~ - 17 opicac SZ =N e g B a3 | Exefute 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 - @, = primary replicasignature
Mg, <PREPREPAREN,N.D(M), PREPAREV.NDIMPG | ccommmyim, | <REFLY., SN N AR D, "8 /4 - AN ,:, €6\?,v / TN NS DT RS/ SN S iepica > 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 Verfy 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 n forminv m = requestmessage 1f prepareci(m,yn,) is True, Then prepared(m,,n,)s False for i 0, =replicaisignature ®
Mo, <PREPREPARE,V,ND(M)gy| PREPAREVNDIMYG, | <commIrv,og, | <REFLY, Y ¥ SN ot \ S & iz P N epica replica 3 T N i Exetute Backups initiate commit phase COMMIT <v,n,i >0, Multicast commit to all replicas = 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) | PREPAREVN.DIM), | <coMMT, Vg, | <REPLY, Y dient e H /‘ T = . < \ o £ K e /o X N A = 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 s
Log Checkpointing Infinite log Checkpoint Log state periodically Digest of log 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 S
Faulty Primary Primary deterministic p = vmod N VIEWCHANGE <v+1,n,,C,P,i>0; vi | ews may overlap V= fauly view number
Restart view by re-ssuing pre-prepares from failed view. 1, = sequence number of st stablecheckpoint View change request trggered by €= setof 2/ + eheckpolntmessages
Client Timeout rebroadcast request which starts replica P =setofsetsF, foreachmpreparedatiwithn, >,
Clent P, = Iprepreparc- 2 preparc
m= requestmessage
Replica Timeout generates view change request i plicnid
If primary given by va receives 2f view change plus own 0, roplicaisignature %
New View If primary given by v+1 receives 2f view change plus own
Multicasts new view to replicas NEWVIEW <v+1,V,0>0, Osset 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 o
Performance PBFT BFS about 10- 20% slower than NFS under normal operation 90% performance degradation for fault recovery view change. 5