Consensus Mechanism Reading

[libreamartists]

• MetaAnalysis of Alternative Consensus Protocols

Avalanche

• Exploring Liveness of Avalanche (… or any consensus algorithm that relies on an unstable equilibrium)
• What avalanche paper is not
• Avalanche vs The new IOTA consensus algorithm, with a touch of Spacemesh

[libreamartists]

Polygraph: Accountable Byzantine Agreement

A new Byzantine agreement algorithm among n nodes out of which t can be Byzantine with the following guarantees: (i) if t < n/3, then consensus is guaranteed, (ii) no matter the number of Byzantines nodes, if a disagreement occurs between two honest nodes, every honest node eventually produces an irrefutable proof as to the identity of some malicious users.

[libreamartists]

Privacy-Enhancing Mechanisms

Lelantus
This is a new privacy-oriented cryptocurrency protocol, developed by the Zcoin team. Lelantus claims to achieve both transaction privacy and coin amount secrecy, in the line of Monero, Zcash, Zcoin.

The authors claim short proofs and fast verification time, also the ability to batch proofs to enable fast verification of multiple proofs. The ledger is UTXO based. Each output is just a vector commitment to a secret key and the amount, and an input transaction is a commitment to an output one. When spending a set of input transactions, the spender proves for each of them that it has never been spent by providing a deterministic hash of the secret key, which is looked up in the set of spent coins, and proving knowledge of that key. The spender also provides a proof that the input transaction is a valid commitment to one of previously published outputs. Finally, the spender proves that the sum of inputs matches the sum of outputs and all values are positive and not so big.

Whereas the double-spend and the sum proof are standard (prety much like in Monero and Zcoin), the Bulletproofs range proof is proposed for the latter, the proof of input validity is novel and is the main contribution of the paper. The authors employ the 1-of-N proof technique of 1. First, they select the set of outputs that contain the one we are spending. Both Spender and Verifier are supposed to divide every output from the set by the input to spend. Then Spender proves that one of the results has effectively zero secret key, for which 1 has a logarithmic argument (performance and features similar to Bulletproofs). The resulting proof is reasonably short, but both proving and verification time grows linearly with the size of the set. Moreover, Verifier must retrieve all the outputs from the anonymity set himself to perform the division and run the proof, i.e. the communication costs are linear for him.

The actual verification time, given in the paper, is quite confusing. We see in Table 1 that the verification for the set of 60,000 takes 13 ms, and for the set of 250,000 -- 38ms. However, the 1-of-N proof takes 2 and 8 seconds, respectively! (Table 2). The answer is that the numbers in Table 1 are amortized over batches of 1000 transactions (Tables 3-6), which are indeed not much more expensive to verify than single proofs.

[libreamartists]

CBC LMD Fast Python Implementation

[libreamartists]

Synchronous Consensus with Optimal Asynchronous Fallback Guarantees
This work explores whether it is possible to design a Byzantine agreement (BA) protocol that is (1) resilient to any ts (adaptive) corruptions when run in a synchronous network and also (2) resilient to ta (adaptive) corruptions even if the network happens to be asynchronous while fixing thresholds ta,ts with 0 < ta < n/3 ≤ ts < n/2.

[libreamartists]

Secure and Efficient Asynchronous Broadcast Protocols

start reading a computational introduction to number theory and algebra

[libreamartists]

Scalable and Probabilistic Leaderless BFT Consensus through Metastability (Snow, Avalanche, Team Rocket, Emin, etc)

A family of leaderless Byzantine fault tolerance protocols, built around a metastable mechanism via network subsampling. These protocols provide a strong probabilistic safety guarantee in the presence of Byzantine adversaries while their concurrent and leaderless nature enables them to achieve high throughput and scalability. Unlike blockchains that rely on proof-of-work, they are quiescent and green. Unlike traditional consensus protocols where one or more nodes typically process linear bits in the number of total nodes per decision, no node processes more than logarithmic bits. It does not require accurate knowledge of all participants and exposes new possible tradeoffs and improvements in safety and liveness for building consensus protocols.

[libreamartists]

Sidechain Consensus

• Formalized Sidechain Consensus (vulcan)
• Sidechains and Interoperability (pegasys)

[libreamartists]

Thought Frameworks (CRITERIA)

• PREStO: A Systematic Framework for Blockchain Consensus Protocols -- basically nesting doll of goals (Optimality \in Stability \in Efficiency \in Robustness \in Persistence)

[libreamartists]

MaGPoS -- A novel decentralized consensus mechanism combining magnetism and proof of stake by Tommy Mckinnon

• MaGPoS is based on a combination of the well known physics of nano-scale magnetism, and previous implementations of proof of stake.

[libreamartists]

StakeDAG: stake-based consensus: a new family of consensus protocols that uses Proof of Stake to achieve more scalable and robust consensus in a DAG.

[libreamartists]

Classics

• Distributed Consensus Reading
• Applying the CAP Theorem to Permissioned Blockchains
• Paxos, Raft