DAN consensus, take two
Our initial take on [Cerberus] consensus came with a massive number of learnings for the team. The variant could best be described as a coming together of chained-hotstuff and optimistic-Cerberus across overlapping VN committees. This implementation served us well as we built out the validator node, WASM template engine, and clients.
It also highlighted some shortcomings, specifically around agreement, and performance (high message complexity) with transactions that involve many objects. Today we are starting work on a new implementation that addresses these and other shortcomings.
Single-Chain Committees
In the current implementation, each transaction-object pair creates a separate 3-chain. This makes it harder to reach agreement on the state as a whole. As part of addressing this, we replaced overlapping shard committees with a simple algorithm that divides the shard space into equal “buckets” and deterministically allocates each validator node to a bucket for which they are responsible for the remainder of the epoch. The number of buckets can change with every epoch and is proportional to the number of registered validator nodes for the epoch.
\begin{align}
\text{num_buckets} &= \lfloor |\vec{V_e}|: / : \text{target_committee_size} \rfloor
\text{shard_size} &= u256_{MAX}: / :\text{num_buckets}
\end{align}
where $\vec{V_e}$ is the current validator set for epoch $e$.
Now that each validator node belongs to exactly one committee, it becomes trivial to build a single chain for each shard. In addition to the simplicity of this model, this allows each validator to easily verify Byzantine majority agreement on shard state.
Batching
Another aspect being worked on is transaction throughput. After some basic stress testing recently conducted in a test setting by Tari contributors, @Cifko and @stringhandler, we observed some expected bottlenecks in the current second layer consensus.
These bottlenecks are expected because each shard must do chained-hotstuff consensus for each object in each transaction. In consensus, what is being agreed upon is often completely decoupled from the protocol itself. It therefore follows, if we send multiple rounds of messages to agree on a single transaction, why not increase the bang-for-your-buck of these messages by coming to agreement on a bundle of transactions? Sounds like a block, doesn’t it?
As you’d expect, the reality is a little more complex and co-ordinating these batches across multiple shards is not trivial. We’ve taken some inspiration from the co-ordination described in the [chainspace] paper.
Briefly, in our protocol, validators decide to COMMIT/ABORT each applicable transaction it encounters. Not relevant here, but this usually involves running a WASM template. A shard leader proposes a block containing commands which each contain the command, a transaction hash, the decision to COMMIT/ABORT, and references to the QuorumCertificates for blocks containing transaction. A command is either ‘Prepare’, ‘SomePrepared’, ‘AllPrepared’ and is roughly a request for votes on whether a validator agrees with the decision, and the provided QC evidence is correct for the command.
The block is broadcast to all local validators who submit a vote. The leader collects the votes and produces a QuorumCertificate for this block, and broadcasts it to all involved remote shards. Once all involved shards have evidence that all global shards have made the same decision, the leader will propose a block containing the command to ACCEPT the transaction decision (either COMMIT or ABORT).
This, and more, are actively (as in right now) being worked on so expect to see some exciting developments in the near future. If you’d like to follow in detail, you can take a look here: https://github.com/tari-project/tari-dan/tree/development/dan_layer/consensus.