Diet Block Access Lists A low‑calorie Block Access Lists (BAL)

TL;DR

  • Diet-BAL: a 35% smaller, stripped-down BAL containing:
    • (a) {account→slot} read‑set for I/O prefetch;
    • (b) a levelised dependency graph for execution.
  • Drops per‑edge dependency data and bal_hash.
  • Validators verifies dependency graph and rejects the block its invalid.

Problem

We want a Block Access Lists that

  1. enables I/0 prefetch,
  2. enables parallel execution,
  3. never makes the worst case slower than serial,
  4. is cheap for builders, light for validators,
  5. has a reasonably small size without compromising (1)-(3) and,
  6. [Bonus] can be pruned out of history

The current BAL spec meets (1)–(3) but sends a per‑tx write‑set that validators can already discover; we can skip that payload.

Cutting calories

BAL is a hinting mechanism for EVM to better use its resources through parallelization.

The current design has a per-tx write which validators infer to determine a execution strategy:

- Account
   - Nonce Changs
         - tx_1 : new_nonce
         - tx_2 : new_nonce
         ...
   - Balance Changes
         - tx_1 : new_balance
         - tx_2 : new_balance
         ...
   - Storage Writes
          - tx_1 : {slot_1 : new_value}
          - tx_2 : {slot_1 : new_value}
         ...
   - Storage Reads
          - slot_3
          - slot_4
   - Code Changes
        - tx_1 : new_code
        - tx_2 : new_code
        ...

We can outsource tx dependency graph generation to the Builder, this significantly reduces the payload size.

A minimal BAL therefore has two fields that map to (1) and (2) of our goals:

accounts:            # (I/0 prefetch)
  - address: 0xabc…
    slots: [slot_1, slot_2, …]

transaction_batches: # (parallel execution)
  - [1, 9, 13]   # batch 0
  - [20, 30, 42] # batch 1
  …

A batch is a set of transactions that have no write‑write conflicts with each other.

Batches are listed in the order they must be executed; transactions inside a batch may run in parallel.

Optimality rule: every transaction must appear in the earliest batch in which all its dependencies are already in earlier batches.

Transaction dependency graph Transaction dependency graph sourced from dependency.pics

Lastly, drop bal_hash from header: While bal_hash once enabled execution-less state transition validation, that functionality is outside the scope of this design (see cons). In this model, validators validates the BAL through direct inspection, not by hash. And because the BAL is now just an execution hint (and not consensus-critical) it can be safely pruned from history.

SSZ Specs


# A batch is a list of non-conflicting transactions
TransactionBatch = List[Uint(16), MAX_TXS]

class Account(Container):
    address: ByteVector(20)
    slots : List[ByteVector(32), MAX_SLOTS)]

class BlockAccessLists(Container):
    accounts: List[Account, MAX_ACCOUNTS]
    transaction_batches: List[TransactionBatch, MAX_TXS]

Batching transactions

Transaction batches are a levelised topological sort of a dependency graph where edges go from an earlier transaction to a later one that writes an already‑written resource.

# pseudo‑code for batching
def levelise(txs):                    # txs in canonical order
    batches, last_writer = [[]], {}   # resource → batch index
    for idx, tx in enumerate(txs):
        b = 0
        for r in tx.write_set:
            if r in last_writer:
                b = max(b, last_writer[r] + 1)
        while len(batches) <= b:
            batches.append([])
        batches[b].append(idx)
        for r in tx.write_set:
            last_writer[r] = b
    return batches

Validating

To validate a batch, the validator needs to test:

  • ∀ tx_i, tx_j ∈ batch_k: not conflict(tx_i, tx_j) and
  • ∀ tx ∈ batch_k: all conflicting predecessors are in batches < k
# Assume: executing transactions in batch[k]

# State snapshot for conflict detection
seen_writes = {}   # resource → batch index

def validate_and_execute(tx, batch_index):
    tx_wite_set = execute_transaction(tx)
    for resource in tx_write_set:
        if resource in seen_writes:
            prev_batch = seen_writes[resource]
            if prev_batch == batch_index:
                raise InvalidBAL("Write conflict within batch")
            elif prev_batch > batch_index:
                raise InvalidBAL("Causal dependency violated")

    # Safe to proceed: record writes
    for resource in tx_write_set:
        seen_writes[resource] = batch_index

Nutritional info

⚠️ Experimental Work: This analysis represents experimental research into Diet BAL optimization. The implementation may contain bugs and results should be validated before production use.

SSZ encoded

Metric BAL Diet BAL Savings
Average size 88.9 KiB 50.9 KiB 42.8%
Median size 90.1 KiB 52.1 KiB 42.2%

SSZ encoded AND snappy compressed

Metric BAL Diet BAL Savings
Average size 53.0 KiB 34.4 KiB 35.1%
Median size 53.7 KiB 34.9 KiB 35.0%

The complete analysis with detailed results can be found here: Diet BAL Analysis Results

Pros

  • Compact: Significantly smaller in size.
  • Light for validators: Saves validator compute around resovling tx-dependency.
  • Low overhead validation: To reject a bad batch, the validator only use information already computed while executing.
  • Lossly coupled: Because bal_hash is dropped, the batches can be pruned after execution and are not consensus‑critical.

Cons

  • Optimality not proven on‑chain. Validators verify but cannot prove global maximal parallelism without exploring alternate graphs. That is usually acceptable, because “good enough” parallelism still beats serial execution. See design goal (3)
  • No support for execution-less state transition: This is due to the removal of edges with per-tx writes. While this was not a goal, it is a notable difference compared to the current specification.

References