May 28, 2018
By: Sergey Gorbunov
In a centralized blockchain, a central authority always chooses and distributes the next block. While a single entity produces the block, every user locally stores all blocks, and thus block contents are tamperproof.
This approach is obviously both super-efficient and easy to implement. In addition, it guarantees fast block finality. Indeed, every user receiving a new block digitally signed by the central authority immediately knows that the block is valid and can immediately rely on the transactions it contains.
On the other side, this approach requires a super strong trust assumption. A central entity must be trusted not to censor any user and to give identical new blocks to all users. Moreover, a single entity is easily compromised or stopped by a simple denial of service attack.
A popular approach to decentralize a blockchain requires miners to elongate the longest chain via proof-of-work. This requires a lot of computational effort from the miners, which ultimately translates into high energy consumption and very high transaction costs. In addition, the PoW approach has concentrated a lot of power in the hands of a few mining pools (often just 2 or 3 mining pools), casting doubts on the decentralization of PoW-based blockchains. Also, such blockchains frequently “fork”. Hence their users cannot rely on a new block as soon as it appears. Instead, they must wait until the block is deep enough in the chain, resulting in very high latency.
For these reasons, the blockchain community has put forward alternative approaches to decentralization, where the power of the central authority is distributed over a suitably chosen committee. There are vastly many different ways to implement this approach, with various pros and cons.
In a first approach, the power to choose all new blocks is delegated forever to a small (e.g., 10-, 100-, or 1000-strong) committee, ensuring the integrity of the blockchain as long as the majority of the committee members are honest.
In another approach, the fixed committee is replaced with a “rotating-committee”. In one example, there is a set of N committees, and, for each new block, one of these committees is randomly selected to choose the block. In another example, after the current committee has chosen a block, a few of its members are removed and a few new members are added.
Of course, this approach requires a secure way to ensure that a “proper committee” is chosen for each new block.
In a truly decentralized blockchain, each new block is generated by a separate, new committee, randomly chosen from the set of all users. In principle, securely choosing a committee from all users may require a very large amount of computation and/or communication. A unique innovation introduced by Algorand to solve this problem is secret self-selection. At a high level, each user plays her own fair cryptographic lottery, at the end of which she is the only one to know whether she is a member of the committee. In the latter case, she also has a winning ticket, a digital and unforgeable proof that she is indeed the member of the committee. Anyone can immediately verify a user’s winning ticket to confirm that she is indeed a member of the committee.
Notice that, initially, the committee members themselves keep their own winning tickets, which are not seen by anyone else. Hence, an adversary does not even know who the committee members are, Thus, he cannot corrupt them or mount a denial of service against them! Suppose that Alice is chosen to be a member of a current committee and that, in this capacity, she needs to send a message M. Then, Alice propagates throughout the network both her winning ticket and M digitally signed by her. At this point, an adversary can learn that Alice is the committee member, but corrupting her is now pointless. Indeed, Alice’s winning ticket and message are virally been propagated through the network, and the adversary cannot stop them more than a government can stop a message virally propagated by WikiLeaks.
Assuming that, to produce a new block, each committee member needs to send only one message, the system remains totally secure. However, a handful of rounds are necessary for the committee to produce a new block, and in each of these rounds, a committee member needs to send a single short and easy to compute message. Thus, although the adversary cannot influence the messages of the first round, in principle he could influence the messages of the subsequent rounds. Indeed, after seeing the winning tickets, he learns who the committee members are, and could quickly attack them.
Algorand solves this problem by a separate innovation, namely making the block selection protocol player replaceable. At a high level, this means that the protocol does not require a single committee to execute all rounds. Rather, the protocol can be successfully executed by randomly selecting the committee members of each round. This novel property makes Algorand protocol extremely secure against adversaries that can immediately and successfully attack any user at any point in time.
Notice that traditional protocols are defined over the same group of players and cannot support player replaceability. In our opinion, only player-replaceable protocols are truly decentralized, because only they can withstand the powerful adversaries that will surely try to attack a global cryptocurrency.