Block space allocator

Block space allocator

Note that the DKG scheme for front-running prevention is not a feature included in the first release of Namada. The block-space-allocator infrastructure still exists, but the decryption is hardcoded and does not require validator coordination.

Block space in CometBFT is a resource whose management is relinquished to the running application. This section covers the design of an abstraction that facilitates the process of transparently allocating space for transactions in a block at some height HH, whilst upholding the safety and liveness properties of Namada.

On block sizes in CometBFT and Namada

Block sizes in CometBFT (opens in a new tab) (configured through the MaxBytes consensus parameter) have a minimum value of 1 byte1\ \text{byte}, and a hard cap of 100 MiB100\ \text{MiB}, reflecting the header, evidence of misbehavior (used to slash Byzantine validators) and transaction data, as well as any potential protobuf serialization overhead. Some of this data is dynamic in nature (e.g. evidence of misbehavior), so the total size reserved to transactions in a block at some height H0H_0 might not be the same as another block's, say, at some height H1:H1H0H_1 : H_1 \ne H_0. During CometBFT's PrepareProposal ABCI phase, applications receive a MaxTxBytesMaxTxBytes parameter whose value already accounts for the total space available for transactions at some height HH. Namada does not rely on the MaxTxBytes parameter of RequestPrepareProposal; instead, app-side validators configure a MaxProposalSize parameter at genesis (or through governance) and set CometBFT blocks' MaxBytes parameter to its upper bound.

Transaction batch construction

During CometBFT's PrepareProposal ABCI phase, Namada (the ABCI server) is fed a set of transactions M:={ tx  tx in CometBFT’s mempool }M := \{\ tx\ |\ tx\text{ in CometBFT's mempool}\ \}, whose total combined size (i.e. the sum of the bytes occupied by each tx:txMtx : tx \in M) may be greater than MaxProposalBytes. Therefore, consensus round leaders are responsible for selecting a batch of transactions PP whose total combined bytes PLenP_{Len} \le MaxProposalBytes.

To stay within these bounds, block space is allotted to different kinds of transactions: decrypted, protocol and encrypted transactions. Each kind of transaction gets about 13MaxProposalBytes\frac{1}{3} MaxProposalBytes worth of allotted space, in an abstract container dubbed the TxBin. A transaction tx:txMtx : tx \in M may be dumped to a TxBin, resulting in a successful operation, or an error, if txtx is rejected due to lack of space in the TxBin or if txtx's size overflows (i.e. does not fit in) the TxBin. Block proposers continue dumping transactions from MM into a TxBin BB until a rejection error is encountered, or until there are no more transactions of the same type as BB's in MM. The BlockSpaceAllocator contains three TxBin instances, responsible for holding decrypted, protocol and encrypted transactions.

block space allocator tx bins

During occasional Namada protocol events, such as DKG parameter negotiation, all available block space should be reserved to protocol transactions, therefore the BlockSpaceAllocator was designed as a state machine, whose state transitions depend on the state of Namada. The states of the BlockSpaceAllocator are the following:

  1. BuildingDecryptedTxBatch - As the name implies, during this state the decrypted transactions TxBin is filled with transactions of the same type. Honest block proposers will only include decrypted transactions in a block at a fixed height H0H_0 if encrypted transactions were available at H01H_0 - 1. The decrypted transactions should be included in the same order of the encrypted transactions of block H01H_0 - 1. Likewise, all decrypted transactions available at H0H_0 must be included.
  2. BuildingProtocolTxBatch - In a similar manner, during this BlockSpaceAllocator state, the protocol transactions TxBin is populated with transactions of the same type. Contrary to the first state, allocation stops as soon as the respective TxBin runs out of space for some txProtocol:txProtocolMtx_{Protocol} : tx_{Protocol} \in M. The TxBin for protocol transactions is allotted half of the remaining block space, after decrypted transactions have been allocated.
  1. BuildingEncryptedTxBatch - This state behaves a lot like the previous state, with one addition: it takes a parameter that guards the encrypted transactions TxBin, which in effect splits the state into two sub-states. When WithEncryptedTxs is active, block space is filled with encrypted transactions (as the name implies). Orthogonal to this mode of operation, there exists WithoutEncryptedTxs, which, as the name implies, does not allow encrypted transactions to be included in a block. The TxBin for encrypted transactions is allotted min(R,13MaxProposalBytes)\min(R,\frac{1}{3} MaxProposalBytes) bytes, where RR is the block space remaining after allocating space for decrypted and protocol transactions.
  2. FillingRemainingSpace - The final state of the BlockSpaceAllocator. Due to the short-circuit behavior of a TxBin, on allocation errors, some space may be left unutilized at the end of the third state. At this state, the only transaction types that are left to fill the available block space are encrypted and protocol transactions, but encrypted transactions are forbidden to be included, to avoid breaking their invariant regarding allotted block space (i.e. encrypted transactions can only occupy up to 13\frac{1}{3} of the total block space for a given height HH). As such, only protocol transactions are allowed at the fourth and final state of the BlockSpaceAllocator.

For a fixed block height H0H_0, if at H01H_0 - 1 and H0H_0 no encrypted transactions are included in the respective proposals, the block decided for height H0H_0 will only contain protocol transactions. Similarly, since at most 13\frac{1}{3} of the available block space at a fixed height H1H_1 is reserved to encrypted transactions, and decrypted transactions at H1+1H_1+1 will take up (at most) the same amount of space as encrypted transactions at height H1H_1, each transaction kind's TxBin will generally get allotted about 13\frac{1}{3} of the available block space.

Example

Consider the following diagram:

block space allocator example

We denote D, P and E as decrypted, protocol and encrypted transactions, respectively.

  • At height HH, block space is evenly divided into three parts, one for each kind of transaction type.
  • At height H+1H+1, no encrypted transactions are included in the proposal, therefore protocol transactions are allowed to take up to 23\frac{2}{3} of the available block space.
  • At height H+2H+2, no encrypted transactions are included either. Notice that no decrypted transactions were included in the proposal, since at height H+1H+1 no encrypted transactions were committed. In sum, only protocol transactions are included in the proposal for the block with height H+2H+2.
  • At height H+3H+3, encrypted transactions are proposed once more. Just like in the previous scenario, no decrypted transactions are available. Encrypted transactions are capped at 13\frac{1}{3} of the available block space, so the remaining 1213=16\frac{1}{2} - \frac{1}{3} = \frac{1}{6} of the available block space is filled with protocol transactions.
  • At height H+4H+4, allocation returns to its normal operation, thus block space is divided in three equal parts for each kind of transaction type.

Transaction batch validation

Batches of transactions proposed during ABCI's PrepareProposal phase are validated at the ProcessProposal phase. The validation conditions are relaxed, compared to the rigid block structure imposed on blocks during PrepareProposal (i.e. with decrypted, protocol and encrypted transactions appearing in this order, as examplified above).

Define HH as the height of block BB currently being decided through Tendermint's consensus mechanism. Define PP as the batch of transactions proposed at HH as BB's payload and define VV as the current set of active validators. To vote on PP, each validator vVv \in V checks that:

  • The length of PP in bytes, defined as PLen:=txPsize_of(tx)P_{Len} := \sum_{tx \in P} \text{size\_of}(tx), is not greater than MaxProposalBytes.
  • PP does not contain more than 13\frac{1}{3} MaxProposalBytes worth of encrypted transactions.
    • While not directly checked, the batch construction invariants guarantee that decrypted transactions are constrained to occupy up to 13\frac{1}{3} MaxProposalBytes bytes of the available block space at HH (or any block height, in fact).
  • All decrypted transactions from H1H-1 have been included in the proposal PP, for height HH.
  • No encrypted transactions were included in the proposal PP, if no encrypted transactions should be included at HH.

N.b. the conditions to reject encrypted transactions are not specced out, and would be necessary should Namada incorporate the DKG scheme

Should any of these conditions not be met at some arbitrary round RR of HH, all honest validators Vh:VhVV_h : V_h \subseteq V will reject the proposal PP. Byzantine validators would be permitted to re-order the layout of PP typically derived from the BlockSpaceAllocator AA, under normal operation, however this should not be a compromising factor of the safety and liveness properties of Namada. The rigid layout of BB is simply a consequence of AA allocating in different phases.

On validator set updates

Validator set updates, one type of protocol transactions decided through BFT consensus in Namada, are fundamental to the liveness properties of the Ethereum bridge. Unfortunately, achieving a quorum of signatures for a validator set update between two adjacent block heights through ABCI alone is not feasible. Hence, the Ethereum bridge is not a live distributed system, since there is the possibility to cross an epoch boundary without constructing a valid proof for some validator set update. In practice, however, it is nearly impossible for the bridge to get "stuck", as validator set updates are eagerly issued at the start of an epoch, whose length should be long enough for consensus(*) to be reached on a single validator set update.

(*) Note that consensus was used loosely here to refer to the process of acquiring a quorum (e.g. more than 23\frac{2}{3} of voting power, by stake) of signatures on a single validator set update. "Chunks" of a proof (i.e. individual votes) are decided and batched together, until a complete proof is constructed.

Validator set updates are covered in more detail in the Ethereum bridge section.

Governance

Governance parameter update proposals for MaxProposalBytesHMaxProposalBytes_H that take effect at HH, where HH is some arbitrary block height, should be such that MaxProposalBytesH13MaxProposalBytesH1MaxProposalBytes_H \ge \frac{1}{3} MaxProposalBytes_{H-1}, to leave enough room for all decrypted transactions from H1H-1 at HH. Subsequent block heights H:H>HH' : H' > H should eventually lead to allotted block space converging to about 13MaxProposalBytesH\frac{1}{3} MaxProposalBytes_H for each kind of transaction type.