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: 

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

Property-based proofs does not guarantee simulation-based security in case of a dynamic adversary. 

      Related: called SMR in classical distributed systems literature

      Reduction from Consensus to Ledger consensus:

3. Communication model

Given RMT, can Diffuse; given Diffuse, cannot simulate RMT.

4. Network model

5. Setup

6. Computational assumptions

7. Results



i) IT security:  

[LSP82] n>3t is necessary and sufficient condition; optimal round complexity is t+1

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: 

No simultaneous termination. 

-> Probabilistic termination

Partial synchrony: 

bounds remain the same with no setup and public setup; bounds degrade to n/3 with private setup





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. 


    Computational security:

Partial synchrony:

Difficulty parameterization hardcoded → 

8. Ledger consensus results


Adapt standard BFTs. 


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.