The following post is an adaption of the PaLa protocol description from the ThunderCore Whitepaper. It is extended with more details, diagrams and explanations.
PaLa is a blockchain consensus protocol based on partially synchronous network assumptions and tolerates up to ⅓ corruptions. Below, we describe a simplified version of the protocol called Basic Pala to illustrate its simplicity and effectiveness. Basic Pala is the foundation for understanding the complete version of our protocol which is outlined afterwards. The full details of the PaLa protocol are readily available in the PaLa research paper.
Assume a fixed committee of voters. How these nodes are chosen is described later. Each node maintains a local epoch counter e and a local view of the blockchain. Each block contains an epoch number, a list of transactions, and the hash of its parent block. The epoch number of a chain is defined as the epoch number of the last block in the chain. Each epoch has a single unique proposer which is known to all nodes in the network. In this simplified version, every voter is also a proposer for some epochs.
Consensus proceeds one block at a time. Proposers propose a block if they are eligible to propose in the current epoch. Voters vote on blocks if a set of conditions are met. A collection of ⅔ of the committee’s votes on a single block is a notarization for that block. If there is a notarization for a block, the block is notarized. Each block has an epoch which advances monotonically. If an epoch e block has an epoch e-1 parent, the block is a normal block otherwise it is a timeout block. A block is finalized if it is the parent of a notarized normal block. A finalized block is part of the immutable history of the blockchain and indicates consensus has been achieved.
Each node keeps their local current blockchain fresh. Whenever it sees a valid blockchain that is fresher than its current chain–it has higher epoch number than the epoch number of their current chain–they switch to this chain. A valid blockchain should satisfy the following conditions:
- The epoch numbers of all blocks should be strictly increasing.
- Every block in the blockchain is notarized
In addition each node will do the following:
Increase local epoch counter to e if
- Their current local epoch is smaller than e AND
- (They see a notarized chain for epoch e-1 OR
- They see at least ⅔ committee members’ validly signed clock(e) messages)
If they have stayed in epoch e-1 for more than a fixed amount of time
- Broadcast the message clock(e).
If they are the proposer of epoch e
- If their current chain ends with the block of epoch e-1, immediately propose a new block for epoch e extending their own current notarized chain
- If the epoch number of their current blockchain is e (due to a timeout), wait for a fixed period of time (hoping to receive a fresher notarized chain) and propose a new block for epoch e extending their own current chain.
- Note that it is possible for a notarized block to be orphaned if it arrives after the fixed delay.
On receiving a block proposal for epoch e from the proposer of epoch e, sign the proposal and multicast the signature if the following conditions hold:
- They have seen the notarization for the parent block of the proposal.
- The block is at least as fresh as their current chain at the beginning of epoch e.
- They have not signed any other block for epoch e.
A node reports a block as finalized if it is the parent of a notarized block
With these simple rules, the PaLa consensus protocol achieves liveness and consistency. The PaLa protocol is simple and rigorously proven. PaLa is designed based on partially synchronous network assumption. It is inherently partition tolerant and responsive. If there is ever a network partition, there is only a temporary outage in liveness. It will resume progress when the partition heals with no conflict in state.
In a real world Proof-of-Stake blockchain, we want to periodically switch committees as stake changes hands in the system. The PaLa consensus algorithm supports fast and seamless committee switches. The basic idea is that the previous committee must finalize a special reconfiguration block before the next committee may serve to ensure consistent continuity.
The following assumes a mature understanding of the PaLa consensus protocol so don’t be alarmed if you’re reading it for the first time. It’s nonetheless published here for readers to revisit as reference in the future.
So far, PaLa only guarantees consistency history with a fixed committee. It’s possible, just before a reconfiguration, that the previous committee might finalize an extension of the reconfiguration block. Remember 2 notarized normal blocks in a row are needed for the first one to be finalized. Thus timeouts allow for multiple blocks in a row to be notarized and finalized all at once when the 2 normal blocks condition is met. If the next sessions extends from the reconfig block, the extended finalized chain from the reconfig block is lost and we lose consistency. There is no guarantee the new committee will see this extended finalized chain and so we can not require that they extend from it.
ThunderCore’s implementation always extends from the reconfig block and requires that all blocks after the reconfiguration block must be empty. They only serve to finalize the reconfiguration block, and it doesn’t matter if their content is lost.
Another solution solution is to have blocks after a reconfiguration block be finalized by the next committee.
Doubly Pipelined PaLa
The full PaLa protocol described in the paper is called Doubly Pipelined Pala which supports the proposal pipeline feature. This version allows for consensus to proceed k blocks at a time where k is a protocol set parameter. The proposal pipeline allows newer blocks to be buffered while older ones are still being voted on. Based on empirical testing, we found that when network latency is high relative to block times, a higher k value can improve throughput volume.
Since a single proposer may propose multiple blocks in sequence, a more nuanced block numbering scheme is needed. Blocks now have an epoch and sequence number. Proposers are chosen based on the epoch as before and each new proposal from the same sequence advances the sequence number which starts from 0 at the beginning of each epoch. A block is now finalized if its k’th child in the same epoch is notarized.
The remainder of the protocol is very similar to PaLa. The proofs for consistency and liveness also follow suite. We’ll dive into the details of this in a future blog post comparing PaLa and Hotstuff.
From a performance standpoint, PaLa is a significant improvement on prior classical consensus protocols that require two rounds of voting per block and O(n²) messages. PaLa makes use of the pipelined BFT idea where the second round of voting in this classical consensus protocol is piggy-backed on the first round of voting for the next block. The active proposer uses BLS multi-signatures to collect votes and distribute notarizations. Together with a multi-hub-and-spoke network topology, PaLa can achieve consensus with just O(n) messages.
PaLa is the culmination of decades of distributed consensus research (spurned and funded by the emerging cryptocurrency paradigm). It brings together bold ideas from many protocols elegantly combining them into a single efficient and simple protocol. This should be apparent from the very short description of the algorithm presented above. The PaLa research paper provides simple and rigorous proofs to its security properties based on realistic network assumptions.
Newer BFT consensus algorithms such as Tendermint, FBFT, Casper FFG and Hotstuff use many of the same innovations as PaLa. However, none of these algorithms are as simple, elegant and optimal as PaLa.
We expect BFT consensus to be equated with PaLa the same way Distributed Hash Table (DHT) is equated with Kademlia.
The reference implementation of the PaLa consensus protocol is already released and contains thorough documentation and educational material.