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 , 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 , and a hard cap of , 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 might not be the same as another block's, say, at some
height . During CometBFT's PrepareProposal
ABCI phase,
applications receive a parameter whose value already accounts for
the total space available for transactions at some height . 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 , whose total combined size (i.e. the sum of the bytes occupied by each ) may be greater than MaxProposalBytes
. Therefore, consensus round
leaders are responsible for selecting a batch of transactions whose total
combined bytes 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 worth of allotted space,
in an abstract container dubbed the TxBin
. A transaction may
be dumped to a TxBin
, resulting in a successful operation, or an error,
if is rejected due to lack of space in the TxBin
or if 's size
overflows (i.e. does not fit in) the TxBin
. Block proposers continue
dumping transactions from into a TxBin
until a rejection error is
encountered, or until there are no more transactions of the same type as 's
in . The BlockSpaceAllocator
contains three TxBin
instances, responsible
for holding decrypted, protocol and encrypted transactions.
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:
BuildingDecryptedTxBatch
- As the name implies, during this state the decrypted transactionsTxBin
is filled with transactions of the same type. Honest block proposers will only include decrypted transactions in a block at a fixed height if encrypted transactions were available at . The decrypted transactions should be included in the same order of the encrypted transactions of block . Likewise, all decrypted transactions available at must be included.BuildingProtocolTxBatch
- In a similar manner, during thisBlockSpaceAllocator
state, the protocol transactionsTxBin
is populated with transactions of the same type. Contrary to the first state, allocation stops as soon as the respectiveTxBin
runs out of space for some . TheTxBin
for protocol transactions is allotted half of the remaining block space, after decrypted transactions have been allocated.
BuildingEncryptedTxBatch
- This state behaves a lot like the previous state, with one addition: it takes a parameter that guards the encrypted transactionsTxBin
, which in effect splits the state into two sub-states. WhenWithEncryptedTxs
is active, block space is filled with encrypted transactions (as the name implies). Orthogonal to this mode of operation, there existsWithoutEncryptedTxs
, which, as the name implies, does not allow encrypted transactions to be included in a block. TheTxBin
for encrypted transactions is allotted bytes, where is the block space remaining after allocating space for decrypted and protocol transactions.FillingRemainingSpace
- The final state of theBlockSpaceAllocator
. Due to the short-circuit behavior of aTxBin
, 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 of the total block space for a given height ). As such, only protocol transactions are allowed at the fourth and final state of theBlockSpaceAllocator
.
For a fixed block height , if at and no encrypted
transactions are included in the respective proposals, the block decided for
height will only contain protocol transactions. Similarly, since at most
of the available block space at a fixed height is reserved
to encrypted transactions, and decrypted transactions at will take up
(at most) the same amount of space as encrypted transactions at height ,
each transaction kind's TxBin
will generally get allotted about
of the available block space.
Example
Consider the following diagram:
We denote D
, P
and E
as decrypted, protocol and encrypted transactions,
respectively.
- At height , block space is evenly divided into three parts, one for each kind of transaction type.
- At height , no encrypted transactions are included in the proposal, therefore protocol transactions are allowed to take up to of the available block space.
- At height , no encrypted transactions are included either. Notice that no decrypted transactions were included in the proposal, since at height no encrypted transactions were committed. In sum, only protocol transactions are included in the proposal for the block with height .
- At height , encrypted transactions are proposed once more. Just like in the previous scenario, no decrypted transactions are available. Encrypted transactions are capped at of the available block space, so the remaining of the available block space is filled with protocol transactions.
- At height , 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 as the height of block currently being decided through Tendermint's consensus mechanism. Define as the batch of transactions proposed at as 's payload and define as the current set of active validators. To vote on , each validator checks that:
- The length of in bytes, defined as , is not greater than
MaxProposalBytes
. - does not contain more than
MaxProposalBytes
worth of encrypted transactions.- While not directly checked, the batch construction invariants guarantee
that decrypted transactions are constrained to occupy up to
MaxProposalBytes
bytes of the available block space at (or any block height, in fact).
- While not directly checked, the batch construction invariants guarantee
that decrypted transactions are constrained to occupy up to
- All decrypted transactions from have been included in the proposal , for height .
- No encrypted transactions were included in the proposal , if no encrypted transactions should be included at .
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 of ,
all honest validators will reject the proposal .
Byzantine validators would be permitted to re-order the layout of typically
derived from the BlockSpaceAllocator
,
under normal operation, however this should not be a compromising factor of the
safety and liveness properties of Namada. The rigid layout of is simply a
consequence of 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 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 that take effect at , where is some arbitrary block height, should be such that , to leave enough room for all decrypted transactions from at . Subsequent block heights should eventually lead to allotted block space converging to about for each kind of transaction type.