Notes for consensus in blockchain era
Reference: Garay, Juan, and Aggelos Kiayias. "Sok: A consensus taxonomy in the blockchain era." Cryptographers’ track at the RSA conference. Springer, Cham, 2020.
1. Model for protocol executions:
Interactive Turing machine (ITM) as a formal model of computation. An instance of ITM is called an ITI. ITM is TM with identity tape and outgoing tape.
Protocol \Pi is modeled as an ITM, in arbitrary setting. To have "arbitrary", the setting is produced by an adversary so that one does not need to quantify over all possible details but treat everything as environments. Adversary is also specified as an ITM and only a single adv ITM is allowed.
(Z,C): environment and control program. Env Z can spawn new ITIs using \Pi or Adv, who writes to C in its outgoing tape. Communication is routed through C, sending messages to Adv.
Functionalities: specify resources available to instances. “Ideal functionalities” are also ITMs, and can be spawned by ITIs running \Pi. Eg., secure channel functionality, message-passing functionality.
VIEW is an execution, a string concatenating all messages and all ITI states at each step of the execution of the system.
Def. Given a predicate Q, \Pi satisfies property Q is \forall A and Z, Q(VIEW) holds.
Settings: asynchronous vs synchronous execution; static vs dynamic environments (assume the total number of ITIs is known); setup (CRS, PKI) as a separate functionality.
2. Consensus definition
Properties based: validity + agreement + termination
validity:
strong validity: the value agreed on is input by at least one honest party
Simulation-based: ideal functionality
Property-based proofs does not guarantee simulation-based security in case of a dynamic adversary.
Ledger consensus:
Problem: a set of servers continuously accepting transactions from a set T and incorporate them into a data structure called ledger, which is a unique view.
Property-based security definitions: consistency / persistence + liveness
consistency: a client queries an honest node and receives ledger view L1 and then queries an honest node in a later round and receives view L2, then L1 is the prefix of L2.
liveness: if a txn is valid and given as input to all honest parties in a round r, it is included in view of round r+u where u is the rounds in a complete consensus run [more in point 9]
serializability: if a txn t1 is valid and given as input to all honest parties in a round, and txn t2 is incompatible with t1, in later rounds, txn t2, t1 cannot be included in this order.
Simulation-based: [BMTZ17]
Related: called SMR in classical distributed systems literature
Reduction from Consensus to Ledger consensus:
no setup: Strong validity and termination ensure liveness and agreement ensures consistency. Strong validity is needed because honest parties may hold disjoint transaction sets. An alternative is to have interactive consistency and validity. One other related notion is predicate-based validity.
setup in all rounds in consensus (or emulate with one initial round, non-balack-box): sequential composition
3. Communication model
point-to-point / RMT: pairwise reliable and authenticated channels; also called RMT, reliable message transmission.
peer-to-peer diffusion: messages are passed along; cannot identify source; cannot preserve order
Given RMT, can Diffuse; given Diffuse, cannot simulate RMT.
4. Network model
Synchrony: protocol executions can be divided into rounds; parties are activated in sequence; message are delivered within a known bound \Delta
rushing adversary: adv can act last in a round to decide its behavior in this round and message delivery for honest parties in the next round
relax timing:
partial synchrony: unknown \Delta
asynchrony: eventual delivery; FLP impossibility result
fully asynchronous: messages can be dropped; impossible
5. Setup
Public-state setup: parameterized by a probability ensemble D, which given input size k, specifies a distribution that is used to sample a common string s of length poly(k).
Private-state setup: parameterized by a probability ensemble D, which given input size k, specifies a distribution that is used to sample a sequence of strings (s1,…,sn), each of length poly(k). Each party has private access to the corresponding string. The strings can be independent or correlated as in “correlated randomness”.
6. Computational assumptions
IT: unbounded adv; can be perfect or statistical (only meaningful in probablistic consensus protocols, e.g., a bad coin)
Computational: polynomial adv
One-way functions
PoW
Random oracle: (not in the ITM model) limit the quota of queries granted to each party in a round
7. Results
Point-to-point
Synchrony
i) IT security:
[LSP82] n>3t is necessary and sufficient condition; optimal round complexity is t+1
Deterministic:
[FL82] round complexity lower bound t+1
[DRS90] actual number of corruptions f<t, lower bound min{t+1, f+2} rounds for non-simultaneous stop termination; lower bound is still t+1 rounds if simultaneous stop is necessary
Randomized
[BO83]
[Rabin83] linearly resilient consensus in expected constant round is possible given a common source of randomness (“coin”)
[FM97] construct the common coin in [Rabin83], n>3t, expected constant round
[FG03] for “strong validity” definition, iff n> max(3, |V|) t where V is the domain of inputs and outputs
If pre-computation phase is allowed in IT setting with reliable broadcast, broadcast and consensus can be achieved with the same bounds as in computational setting, using “pseudo-signatures”.
ii) Computational security:
[LSP82] trusted setup; n>t, t+1 rounds but with exponential time complexity; [DS83] Dolev-Strong assumes PKI, polynomial time.
[Bor96] no PKI, parties distribute keys by themselves, broadcast and consensus are impossible if n<= 3t because keys are not tied to corresponding parties
[FG03] trusted setup; for “strong validity” definition, iff n> |V| t; polynomial time; t+1 rounds
[KK09] PKI, digital signatures, based on VSS => n>2t, expected constant round (extending [FM97])
[GKKO07] expected constant round for t = n/2 + k, expected O(k^2) running time
No simultaneous termination.
-> Probabilistic termination
sequential composition [LLR06]: property based security
parallel composition [BE03]: property based security
compositions with simulation-based security [CCGZ16]
Partial synchrony:
bounds remain the same with no setup and public setup; bounds degrade to n/3 with private setup
Asynchrony:
Feasibility
without setup,
can adapt [FM97] to achieve resilience n/4
termination except with negligible probability [CR93] / termination with probability 1 [ADH08], resilience n/3
private setup:
one-way function: always terminating, n/3 resiliency [Fel88]
Practicality
PBFT [CL02] n/3 resiliency
Peer-to-peer
The total number of participants is unknown but rather is a runtime parameter. The protocol needs to tolerate different participation levels.
Assuming peer-to-peer and private setup, one can simulate point-to-point, although inefficiently.
W/o authentication, deterministic consensus is impossible [Okun05]. Probabilistic consensus is possible.
Synchrony:
Computational security:
PoW: strings PoWs in a hash chain; optimal resiliency is n/2
One-way function
Partial synchrony:
Difficulty parameterization hardcoded →
network delay is low, then max resiliency;
otherwise, degrade until dissipating entirely.
Consistency collapses when delay is arbitrarily large.
8. Ledger consensus results
Point-to-point
Adapt standard BFTs.
Peer-to-peer
With private setup, can simulate point-to-point.
Maximum resiliency n/2. In other words, ledger consensus is impossible for t>=n.
The total number of participants is unknown.
PoW:
static & synchorny / partial synchrony: n>2t; each party has a fixed quota of queries that can be performed to a hash funciton
dynamic: assume PKI and honest majority [KRDO17]
PoS Dynamic setting
assume PKI and honest majority: snow white [BPS16] ouroboros praos [DGKR18]
dynamic availability in Ouroboros genesis: arbitrary number of parties may not be fully opeartional; “bootstrap from genesis” via a chain selection rule
Algorand: identities of participants need not be known in advance; but expected participation is hardcoded