Consensus at batch level

[hackaugusto]

One interesting design choice of miden, is that transactions proofs are aggregated into batches, and later on added to blocks. This allows for parallel batching, which increases throughput and decreases latency. Another interesting design choice, is that sequencers are a cluster of nodes, instead of a single machine. And the batch proving can be delegated to separated machines.

Keeping those two observations in mind, means that once we federate the network, and have multiple sequencers, there will be many machines available for proving, operated by different parties. Ideally these machines should not sit idle because of the consensus protocol. That is to say, we shouldn't really adopt a system were sequencers are elected to seal a single block, and not be able to do work while they are not the leader.

If we agree that every sequencer in the federation should be allowed to use their hardware to proof batches, instead of siting idle, then we have some interesting carry-on effects:

• There should be some sort of coordination among the nodes, to avoid including the same transactions in different batches, as that would cause conflicts and waste work
• There should be fees per proof, not per block. That is to say, not only the sequencer sealing the block receives payouts, but all other nodes that contributed to the batches in the block. Meaning that batches would have a payout address of sorts.
• Most likely block sealing would be the blottleneck:
  • There shouldn't be a bound on the number of batches included in a block. That is to say, if we use the capacity of the complete network to prove batches, the current leader may struggle to put it all into blocks, specially if there is a maximum number of batches in a block.
  • To bound the above, it would make sense for said nodes to construct a single batch of all transactions that they received. So the leader would have at a maximum 1 proof to verify per node in the federation. (We could put a cap on the size of said proof, it doesn't help if there is a single proof from each, but they are all too large to be verified).
• There is an alternative of cycling through the nodes in the federation quickly, but that only works to a threshold, the leadership would need to be forwarded to nodes as quickly as they can finish a batch, and that would not be possible with many nodes

[hackaugusto]

If the above is done, there is also not much of an incentive to cycle leadership over the federation, because every node is being paid fees for the batches. So leadership could be cycled slowly, and instead, what is cycled are slices of address ranges, basically sharding the ID space to each node in the federation. This also resolves issues with conflict transactions in the same batch. Things are quite simple for the locally proven transactions, but they get a bit harder with on-chain transactions, my first gut feeling is that the leader should do the network transactions, and the shards should be exclusively for the locally proven transactions. And perhaps leadership should be rotated to prevent censorship on on-chain transactions.

This needs more thought though.

[bobbinth]

Decentralized proving of batches is something that super beneficial - but I've been putting off this for now as design space is very wide and we'll probably need to spend a lot of time on thinking it through and experimenting.

One other interesting aspect of it is that distributed batching may significantly reduce amount of data that goes over the network. Specifically, each proven transaction would be somewhere in the range between 50KB - 100KB - vast majority of this being a STARK proof. However, if there is away to aggregate transactions into batches before they are fully propagated through the network, we can get rid of all the proof, except for the batch proof itself. So, a single batch containing 100 transactions would also be roughly 100KB.

How to do this correctly is still an open question though.

[bobbinth]

There shouldn't be a bound on the number of batches included in a block. That is to say, if we use the capacity of the complete network to prove batches, the current leader may struggle to put it all into blocks, specially if there is a maximum number of batches in a block.

I would actually say that we should place a limit (and probably not a big one) on the number of batches that can go into a block. The leader still build one final proof that verifies all included batches and also needs to update account and nullifier databases, and build the note tree for the block. This could be quite a lot of works - and even this may need to be distributed across multiple machines.

There are some strategies we can use to simplify this work:

• The approach we currently use for building note trees implies that most of the work is done by batch builder rather than the block builder. But this does require the that number of batches per block is limited (currently at 256 but maybe makes sense to reduce to 64 - see here).
• If we introduce account-ID-based "sharding" (i.e., a batch can include only accounts with the same prefix), updating of the account tree can be distributed as well (but probably not decentralized).
• The nullifier tree is the trickiest one, but even here, we should be able to implement concurrent tree updates of some sort.

All of these starts to matter when we get to over 100 TPS though - so, we have some time.