Algorand’s Instant Consensus Protocol
At Algorand, we are committed to continual innovation and sharing our ideas with the community. Our original protocol brought to blockchains verifiable random functions, cryptographic self-selection, and ephemeral-key PoS, which are now widely adopted in the ecosystem.
Today, we are sharing our latest Byzantine agreement protocol. This new protocol presents several technical advancements that we believe are essential for Proof-of-Stake blockchains.
Algorand’s new protocol is fast. In theoretical terms, it is optimally efficient, by finalizing blocks in one voting round. Practically speaking, it will greatly increase the number of transactions per second and guarantee that every block will be instantly finalized.
Speed without safety doesn’t mean much when money is on the line. Our updated agreement protocol addresses safety as well. We are able to withstand elongated network partitions and recover very quickly from them, addressing a host of real world attacks.
In conjunction with this post we are de-committing the following roadmap hash : “1bd0d370b262d748b21c40cc7e5746642b4c06079a224c65e443e429289753c2”
Hashes are computed as follows:
hash = SHA256(SHA256(msg) || SHA256(nonce))
msg=“Arbitrary partition resilience”
nonce= “2iCIvZu5IfHpXe8Oj2dtchjYWnDDz9QxCSNrBgN_Axo=”
Our roadmap will continue on. Please stay tuned and visit www.algorand.com/roadmap for new hashes.
Below we would like to take you through the essential properties of the new protocol in more detail. If you wish a deeper technical perspective please study our whitepaper (https://eprint.iacr.org/2018/377).
Property 1: Fast Agreement On-The-Fly
In a traditional blockchain, after a block is proposed, it must first be propagated to everyone, and then agreed upon by some mechanism specific to that particular blockchain. This leads to additional work before the block can be finalized.
In our new protocol, agreement on a proposed block is reached while the block propagates. Users vote on a block the moment they receive it, while the block continues to propagate to the remaining users. By the time all users have seen the block all voting is complete. Effectively, agreement is reached in only one voting round. In contrast, prior mechanisms require additional work after propagation or multiple rounds of voting.
This instant agreement is the case when the new block is correctly propagated. In the rare case of a malicious block proposer, the new protocol ignores him and immediately proceeds to selecting a new proposer.
Thus, for correctly propagated blocks, the new protocol is optimally fast in the number of voting rounds.
Property 2: Security against arbitrary network partitioning
What is network partitioning and why should we care?
In general, the blockchain community has been mostly concerned with designing protocols that are robust against protocol level attacks. In such attacks, an adversary accumulates part of the voting power, be it computational power in a Proof-of-Work system (PoW), or stake in a Proof-of-Stake system (PoS). The adversary then proceeds to take actions contrary to the prescribed rules of the protocol, in order to double spend or disrupt the protocol execution.
Recent research has delved into network level attacks, such as network partitions. In these attacks, an adversary targets the communication links between users, making it hard or impossible for users to interact. Researchers are exposing new vulnerabilities in current propagation network designs, thus widening the known attack vectors against blockchains. A few recent research papers describe such attacks:
btc-hijack.ethz.ch/files/btc_hijack.pdf,
As interest in blockchain technology increases, we expect this trend to continue, and new attacks at the network level to be discovered in the near future. Even if these attacks are expensive to execute in absolute terms, an adversary still has incentive to attempt them when the money at stake is high.
Algorand is secure against arbitrary network attacks
The Algorand protocol is secure against an Adversary who not only deviates from the prescribed protocol rules, but can also launch arbitrary network level attacks. Even if the Adversary achieves complete control over the network and dictates which user receives which messages and when, Algorand’s agreement protocol never forks and the users’ balances remain secure.
Property 3: Fast recovery from network partitioning
Security against network partitioning is necessary but not sufficient. A practical blockchain must also be able to recover quickly from partitions. Let’s look at the following two scenarios to understand why.
Scenario 1: Slow recovery from partitions
Assume a blockchain is capable of producing a new block every 10 seconds in a healthy unpartitioned network. An Adversary intervenes and partitions the network for 10 seconds, disrupting the blockchain’s operation. After 10 seconds the network is functioning again, and the users attempt to recover the blockchain’s operation, but they take one hour to regroup before they can produce the first new block post-partition. After that, new blocks are again produced at the rate of one block every 10 seconds.
Consider now an Adversary that has the ability to partition the network for 10 seconds by paying a fixed cost $c. Such an Adversary performs the following attack: Every hour, he pays $c to partition the network for exactly 10 seconds. During the first hour, the blockchain produces no blocks. At the end of the hour, when the blockchain has nearly recovered and is about to produce a new block, the adversary attacks it again, stalling it for another hour. If the Adversary continues to spend $c every hour this attack will continue indefinitely. In this scenario, at the cost of $c/hour, the blockchain will never grow.
Scenario 2: Fast recovery from partitions
Let’s revisit the prior scenario with a few changes. Assume again we have a blockchain capable of producing blocks every 10 seconds. An Adversary partitions this network for 10 seconds. After the partition, the users regroup quickly and produce the first post-partition block in 20 seconds. After that, new blocks are again produced at the rate of one block every 10 seconds, as before.
The Adversary described in Scenario 1 can pay the same cost $c for a 10 second partition with far less impact. In our fast recovery scenario the blockchain will only be stalled for 30 seconds, 10 seconds for the partition and 20 seconds for the recovery. The number of 30 second intervals in an hour is 3600/30=120, so to stall this blockchain for an hour, the Adversary must spend $120c. To stall it forever, the Adversary must keep spending $120c/hour, which is more than two orders of magnitude higher than the associated cost in Scenario 1.
Algorand’s fast recovery from partitions
Algorand handles network partitions robustly. After a set of Algorand users sees no progress for a while, roughly the time it takes to agree on one block, the users enter partition recovery mode. In this state, the users are continuously sending out recovery messages. During a partition, these messages are not propagated properly. However, post-partition these messages are quickly propagated, and when a required threshold of messages is accumulated, the users are synchronized and the blockchain continues to move forward.
This allows Algorand to recover almost instantly from partitions. It should be noted that Algorand recovers instantly regardless of the partition duration, even if the partition last a day, a week or a year.
Network attacks can be performed on any decentralized system. Regardless of how a blockchain is designed, if an Adversary is powerful enough to maintain a network partition forever, no blocks will ever be produced. The best one can do is increase the cost for the Adversary to stall a blockchain. By recovering almost instantly from partitions, the Algorand Agreement makes it economically expensive to stall our blockchain.
