Pure Proof-of-Stake Blockchains

Secure Blockchain Decentralization via Committees

by Sergey Gorbunov & Silvio Micali

(Image Source)

Centralized Blockchains

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.

Proof-of-Work (POW) Decentralization

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.

Fixed-Committee Decentralization

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.

Pros:

• Efficiency. In the obvious deployment of this approach, each committee member essentially performs the work of the central authority in a centralized blockchain, plus some extra computation and communication, as required to have the whole committee to choose a block based on the actions on individual committee members. This amount of extra work is only proportional to the committee size, and independent on the total number of users in the system. Thus, such a system is scalable.
• Ease of implementation. Each block chosen by the committee is authenticated if digitally signed by a majority of the committee members. Alternatively, “threshold cryptography” could be used to generate a joint committee public key PK_C, whose secret key is split among committee members. Individual member digital signatures are then translated into a joint digital signature relative to PK_C.

Cons:

• Very Strong Trust Assumption. Even if the committee may start with a majority of honest members, an adversary could corrupt or bribe most of them over time.
• Strong Vulnerability. A fixed committee is easy to attack, and an adversary can eventually compromise the majority of the committee members. In addition, an adversary can immediately mount a denial of service attack against the committee members, preventing them from receiving messages from each other, or receiving the new transactions that they should include in new blocks.

Rotating-Committee Decentralization

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.

Pros:

• Efficiency. The efficiency and scalability of this approach is essentially the same as for the fixed-committee system, because the size of each committee can remain approximately the same, independent of the total number of users

Cons:

• Strong Trust Assumption. In both rotating-committee systems, most committee members remain fixed over a long period of time, and thus one must assume that they remain honest for a long time.
• Vulnerability. An adversary may not be able to attack most of the users in the system, but could successfully attack the majority of the members of a few, small committees.

Algorand: True Decentralization

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.