Large Scale Consensus: Availability/Finality, Randomness Beacons, VDFs.

It seems possible to have a consensus protocol that provides both dynamic availability and finality. No, obviously not! The Ledger from a protocol that provides finality needs to stop growing during a network partition, so the protocol cannot be dynamically available. This observation is made formal in a recent variant of the notorious CAP theorem. Two families of fundamentally different protocols fall exactly on two different sides of this availability-finally dilemma.

Longest chain protocols favor Liveness over safety and provide availability while BFT(Byzantine Fault-tolerant) protocols favor safety over Liveness and provide finality.

Consensus protocols are at the core of distributed computing. Focuses on consensus protocols for realizing a " Linearly ordered log" abstraction, often referred to as state machine replication in a distributed systems literature.

Basically, participants maintain a growing ordered log of Transactions and any participant can add transactions to the end of the log.

To be a bit more precise, in a consensus protocol, each participant maintains his log of transactions, and the protocol is required to satisfy two important properties; Liveness and consistency.

Dynamic availability is a useful property of Consensus Protocol, particularly in a large scale setting with many nodes, not all are active at the same time. Nakamoto's proof-of-work (PoW) the longest chain protocol is perhaps the first such dynamically available consensus Protocol. The amount of mining power is varying in time and the system is live and safe as long as less than 50% of the online hashrate belongs to adversary miners. One limitation of dynamically available protocols is that they are not tolerant to network partition ( When network partitions, honest nodes in a dynamically available protocol will think many nodes are inactive, continue to confirm transactions and thus is not safe.

Randomness Beacons play a crucial role in Blockchains. They are services that periodically emit a random number, allowing users to base decisions on the same random value without trusting anyone they do not produce unpredictable values, but are also of low computational complexity for the users, bias resistant, and publicly verifiable.

Most random beacons in a blockchain are performed in a distributed approach to secure the generation of random numbers. However, Blockchain nodes are in an open environment and are vulnerable to adversary reboot attacks. Some attacks cost a decrease in the number of members involved. The generated numbers are insecure so, therefore, a threshold signature scheme is designed to solve problems of recovery.

A bivariate polynomial was generated among the nodes in the distributed key generation phase. While preserving the threshold, it also helps to recover lost shares and equally guarantees Security.

Secured distributed random beacons are expected to consistently generate publicly verifiable, unpredictable, bias-resistant randomness. However, distributed randomness generation participants are in open networks.

Participants may be subject to attacks by active adversaries. The active adversary may restart the honest random beacon protocol participants. Further, it poses a significant threat to the Blockchain system. This attack behavior eventually makes the Blockchain system untrustworthy.

As said earlier, in a random beacon protocol employing a threshold signature, an active adversary may launch an attack on the participants, causing it to lose its key share. After suffering an attack, the participants can no longer participate in the threshold signature generation process. This will reduce the security requirements against the bias-resistance initiated by the adversary on the randomness and the adversary can readily gain profit in the protocol.

• Large-scale Cryptocurrencies require the participation of millions of participants and support for economic activities, which has led to new lines of work in binary Byzantine Agreement and consensus. Several protocols have achieved consensus with communication efficiency, even under an adaptive adversary, but strong assumptions are still required - Proof-of-work, memory erasure, etc. All these protocols use multicast. Under this model, a new communication-efficient consensus Protocol has been provided using Verifiable Delay Functions (VDFs) that are secured against adaptive adversaries and do not require strong assumptions present in other protocols. The question here is, Can the significant protocols be extended to the partially synchronous setting??

Using multicast is not possible.

Safe communication efficient protocols cannot be achieved always even in the synchronous setting against a static adversary when honest replicas only choose to multicast their messages.

Considering this impossibility results, a new communication efficient protocol is described in a modified partially synchronous network model which is secured against adaptive adversaries with high probability.

#PoW #Web3 #Blockchain #VDFs