Byzantine Agreement/Broadcast
Authenticated, Synchronous
Deterministic
Danny Dolve, H. Raymond Strong
Byzantine broadcast
BFT:$ f < n − 1, round complexity: $ f + 1, and communication complexity:$ O(n^2f)
Randomized
Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren
Multi-valued, authenticated BA: expected 8 rounds assuming a random leader oracle
Silvio Micali, Vinod Vaikuntanathan
Ramdomized, adaptive adversary
Player replaceability (defined in Algorand) Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren
FC'19
Random leader oracle
Round complexity: 10 for a static adversary and 16 for a strongly rushing adaptive adversary (in expectation)
Ittai Abraham T-H. Hubert Chan Danny Dolev Kartik Nayak Rafael Pass Ling Ren Elaine Shi
Prove that disallowing after-the-fact removal (erasing a message that was already sent) is necessary for subquadratic-communication BA under adaptive adversary
Randomized version of Dolev-Reischuk lower bound (1982) (See this post for its background) Near-optimal subquadratic BA with minimal assumptions
Remove assumptions such as random oracles or memory-erasure
Achieve near-optimal resilience and expected constant round
Improve the above FC'19 paper to have subquadratic communication
Eventual/partial synchrony
Partha Dutta, Rachid Guerraoui and Marko Vukoli´c
Eventual synchrony
Considered in IBFT2.x as fast-path
Interactive, Vector
Interactive consistency
M. PEASE, R, SHOSTAK, AND L. LAMPORT
Synchronous and reliable channel,$ n \ge 3f + 1without authentication
Exponential message complexity
Defined Interactive consistency
Simultaneous BA (no explicit mention)
With authenticator: $ n > 2ffor BA, $ n > ffor BB
Adri`a Gasc´on and Ashish Tiwari
NFM'14
Synchronous, Non-malicious faults
Transient faults (a process that is faulty in the current step can become non-faulty in the next step and vice versa)
Key assumption: A faulty process that became non-faulty updates its internal state correctly
Show PSL78 does not achieve interactive consistency if faults are transient
Asymmetric faults (a faulty process is not forced to send the same information)
Present a solution only under an additional guaranteed delayed ack assumption
Discovered our algorithm using an automated synthesis technique that is based on bounded model checking and QBF solving
Panos Diamantopoulos, Stathis Maneas, Christos Patsonakis, Nikos Chondros and Mema Roussopoulos (University of Athens)
ICPADS'15
nrryuya.icon > Eventual synchrony?
Eventual Interactive Consistency
Vector consensus
Michael Ben-Or, Ran El-Yaniv
Both sync & asynch, randomized, $ n > 3t, no signature
Runs several multivalued consensus protocols in parallel
Zhuolun Xiang (Tsinghua University) and Nitin H.Vaidya (UIUC)
$ k-Relaxed Byzantine vector consensus :
The output must be in the convex hull of projection of the inputs onto any subset of $ k-dimensions of the vectors.
$ (δ, p)-Relaxed Byzantine vector consensus:
The output must be within distance$ δof the convex hull of the inputs of the non-faulty processes, where$ L_pnorm is used as the distance metric.
Version 1: $ δ is a constant, Version 2: $ δis a function of the inputs themselves
Eventual BA
Danny Dolev, Ruediger Reischuk, H. Raymond Strong
Define Simultaneous/Eventual BA
Prove SBA requires$ t + 1round (even only with orderly crash faults)
Prove EBA requires$ \min\{f + 2, t + 1\}rounds (optimal early stopping)
Only with crash faults, outputs a value in$ f + 1(but does not necessarily terminates)
Joseph Y. Halperny, Yoram Mosesz, Orli Waarts
Only crash/omission, no Byzantine fault
Relate continual common knowledge to eventual BA (Similar to common knowledge and simultaneous BA )
Ittai Abraham, Danny Dolev
STOC '15
First protocol with optimal early stopping ($ \min\{f + 2, t + 1\} rounds) and optimal resilience ($ n > 3t) using polynomial message size and computation
Multi-valued validity: If$ v \neq \botis the decision value then at least$ t + 1correct processes started with value$ v
Based on Exponential Information Gathering (Slide) Multi-valued consensus
Non-intrusion
Miguel Correia, Nuno Ferreira Neves and Paulo Veríssimo
Asynchrony, probabilistic termination
Define a strict validity condition (MVC3): No correct process decides a value proposed only by corrupt processes (Non-intrusion).
Prove the equivalence among multi-valued consensus, vector consensus and atomic broadcast
nrryuya.icon > This is due to the strict validity condition?
Achour Mostefaoui, Michel Raynal
OPODIS’10
Define "Non-intrusion" validity condition
Journal of ACM, 2015
Mostefaoui A., Moumen H., and Raynal M
Randomied, weak coin (Previous version with perfect coin at PODC'14)
Achour Mostéfaoui, Michel Raynal
TPDS'16
Signature free, deterministic intrusion-tolerant consensus protocols
Two-round protocols based on unreliable broadcast ($ n > 5t), no-duplicity broadcast ($ n > 4t) (Section 5)
Single-round protocol (w/ six communication steps) based on validated broadcast ($ n > 3t) (Section 6)
Asynchronous
Ittai Abraham, Dahlia Malkhi, Alexander Spiegelman (VMware Research)
PODC'19
Propose a VABA protocol, which is secure against an adaptive adversary that controls up to$ f < n/3parties, with expected$ O(n^2)word communication and expected constant running time.
Validated BA = multi-valued, with an external validity condition
Previous works:
MMR15 (Journal of ACM)
Optimal resilience and asymptotically optimal time and word communication
Signature-free, but only weak validity
External validity, optimal resilience, asymptotically optimal time but$ O(n^3)word communication
Guanfeng Liang and Nitin Vaidy (University of Illinois at Urbana-Champaign)
PODC '11
Synchronous, Deterministic,$ f < n/3, linear communication complexity$ O(nL)(for a large enough $ L,$ L-bits consensus value)
Withtout authentication
Arpita Patra (Aarhus University)
OPODIS’10
Asynchronous Byzantine broadcast/agreement
https://gyazo.com/55a15ab553c1283f42f487a0fdef8f5c
Synchronous (by reduction)
https://gyazo.com/c1515860ffc2fc2e395b466ae17d9e20
"Error-free" means no error in correctness (= validity + agreement) but termination is probabilistic in this paper
DBFT: Efficient Byzantine Consensus with a Weak Coordinator and its Application to Consortium Blockchains
Tutorials
Slide @Cornell by Siqiu Yao
James Aspnes
Survey on randomized consensus
Slide @University of Massachusetts
https://gyazo.com/aaf38ccf41cf2d4f6be689438775dd5b
Slide by BJÖRN A. JOHNSSON @LUND University
Reliable broadcast supports reliability only, that is, a message that is broadcast is delivered to all alive nodes, even if failures occur in the system.
Atomic broadcast, in addition to the reliability property, also supports the ordering property.
Causal broadcast ensures that the order in which messages are delivered. is consistent with the causal ordering of these messages.