Evacuation Commitments

Evacuation map commitments provide a way to concisely represent potentially large evacuation maps and verify operations on them in constant or logarithmic time onchain during the evacuation process.

Evacuation process

Evacuation is a cyclic process in which each step (transaction) evacuates a portion of the whole evacuation map by drawing the corresponding funds from the treasury and paying them out, leaving the rest untouched until the map is empty.

The L1 blockchain likely limits the size of each evacuation step, but by executing steps repeatedly, an evacuation map of any size can be fully evacuated.

The process begins with the commitment $comm_0$ representing the whole evacuation map as it existed when Gummiworm consensus broke down.

For each evacuation step $N$, the evacuation logic must guarantee that:

1. The evacuated funds are a subset of the current evacuation map represented by $comm_N$.
2. The commitment $comm_{N+1}$ represents the residual evacuation map after subtracting the evacuated funds from step $N$, i.e., $comm_{N+1} = commitment(evacuationMap_{N} \setminus evacuated)$.

These checks must:

• Run in constant or logarithmic time.
• Be executable onchain on the target L1 networks, primarily Cardano.
• Should be storage-efficient to keep the amount of data stored onchain limited.

Design choice: pairing-based accumulators

Traditional approaches like Merkle trees seem appealing at first — they provide logarithmic proof sizes and are well-understood. However, updating the tree structure is somewhat inconvenient: every time an element is removed during the evacuation process, the affected node in the tree must be recalculated, all intermediate hashes must be recomputed, and finally the root hash must be updated—all of which must happen onchain in the validator. Well-tested libraries like Merkle Patricia Forestry  do exist and can definitely help with implementing those checks. Still, those calculations need to be run and that limits what can be achieved in terms of number of total elements and/or elements to be evacuated and the overall code complexity.

As support for the pairing-friendly curve BLS12-381 was added to Plutus, a better approach became available on Cardano, which is the primary L1 target of Gummiworm: pairing-based accumulators  over the BLS curve using KZG commitments (see KZG commitments for details).

Pairing-based accumulators are a much better fit for this task because they allow combining checks 1 (evacuation is subset) and 2 (new commitment is unevaluated subset): the membership proof itself is the new accumulator state. Accordingly, when users evacuate funds from L2 into utxos on L1 (hereinafter this section uses EUTXO terminology for simplicity):

1. A user provides a proof that their funds exist in the current accumulator. That proof is exactly the commitment of the accumulator with the evacuated funds removed.
2. The onchain L1 script verifies the proof using bilinear pairing.
3. The proof becomes the new accumulator commitment for the next step.

This significantly simplifies the onchain part: the check is just one primitive operation, and there is no longer a need to recalculate the new state onchain.

An additional advantage of this approach is that both the commitment and the proof are constant-size—just 48 bytes each (a single BLS12-381 G1 point)—regardless of how many utxos are evacuated. In contrast, using Merkle trees requires providing a membership proof for every element.

KZG commitments

KZG (Kate-Zaverucha-Goldberg) commitments are a type of polynomial commitment scheme. The intuition is as follows:

A set of utxos can be encoded as a polynomial—a mathematical function where each utxo contributes to the polynomial’s structure. A KZG commitment is a cryptographic “fingerprint” of this polynomial that:

• Compresses the entire set into a single point on an elliptic curve (just 48 bytes for BLS12-381).
• Allows proving membership of any utxo in the set with a concise proof.
• Prevents tampering—false proofs cannot be created without breaking hard cryptographic problems.

The beauty of KZG is that it uses a one-time trusted setup to enable these efficient proofs. The commitment itself is computed as:

$commitment = g_1^{f(\tau)}$

where $f(x)$ is the polynomial encoding the utxo set, $g_1$ is a generator of group $G_1$, and $\tau$ (tau) is a secret value from the trusted setup that remains unknown.

Trusted setup

KZG commitments require a trusted setup—a one-time ceremony that generates public parameters. Rather than running our own ceremony, Gummiworm uses the parameters from Ethereum’s KZG Ceremony  (also called the “Powers of Tau” ceremony).

This 14-month ceremony involved over 141,000 contributions from participants across the globe, using diverse equipment and multiple independent software implementations. This massive collaborative effort produced a highly secure setup for KZG-BLS commitments—as long as at least one participant honestly deleted their secret contribution, the setup is secure.

This setup is universal, meaning it can be used by any application that needs polynomial commitments up to a certain degree. The Ethereum ceremony generated:

• 32,768 powers in G1: $g_1^{\tau^0}, g_1^{\tau^1}, g_1^{\tau^2}, \ldots, g_1^{\tau^{32767}}$
• 65 powers in G2: $g_2^{\tau^0}, g_2^{\tau^1}, g_2^{\tau^2}, \ldots, g_2^{\tau^{64}}$

This allows Gummiworm to support L2 state sets with up to 32k elements, which should be sufficient for most Gummiworm heads in typical usage. If the 32k limit becomes too restrictive, options exist to accommodate more elements.

The reason the Ethereum setup contains 32,768 elements in G1 and only 65 in G2 likely reflects where the computational bottlenecks actually occur in practice. In standard KZG schemes:

• Commitments are computed in G1—this happens frequently (every block in the case of Gummiworm).
• Verification uses G2 for pairing checks—this happens less frequently.

Elliptic curve operations in G2 are roughly 3× slower than in G1 on the BLS12-381 curve. By putting the large setup (32k elements) in G1, Ethereum optimized for the frequent operation (commitment computation) while keeping G2 small, since verification happens rarely.

This asymmetry is well-suited for Gummiworm’s needs: commitments must be computed frequently (every minor block), but evacuation is part of the emergency regime.

Overall, Gummiworm benefits from:

• Faster G1 arithmetic for computing commitments.
• Larger G1 setup supporting up to 32,768 elements.
• Reusing battle-tested parameters from Ethereum’s ceremony.

Commitment calculation

An evacuation map is a mapping from a 32-byte key to a transaction output:

type EvacuationKey = ByteString // 32-byte key
 
case class EvacuationMap(
  map: TreeMap[EvacuationKey, TransactionOutput]
)

Computing a KZG commitment for the evacuation map involves the following steps:

1. Calculate the elements $s_i$ of the scalar field of BLS12-381 for every pair in the evacuation map (see Calculating scalars), which produces $N$ binomials of the form $(x - s_i)$.

2. Multiply all binomials to obtain the final polynomial of degree $n$ with $n+1$ coefficients $\{a_0, a_1, \ldots, a_n\}$.

3. Using the trusted setup (G1 for offchain, G2 for onchain), calculate the commitment by evaluating:

   $commitment = g_1^{f(\tau)} = (g_1^{\tau^0})^{a_0} + (g_1^{\tau^1})^{a_1} + \ldots + (g_1^{\tau^n})^{a_n}$

Calculating scalars

Scalar calculation must be performed identically both offchain when building the commitment and onchain when running the membership check. The recommended approach leverages Plutus Data serialization and hashing as follows:

1. Convert all key-value pairs from the evacuation map into Plutus pairs of (key: ByteString, output: v2.TxOut).
2. Convert into the Plutus Data representation.
3. Serialize the Data as ByteString.
4. Calculate the blake2b-224 hash of the bytestring.
5. Convert the hash into a scalar value from big-endian bytes.

Membership proof calculation

Since the proof is the commitment for the residual set, the algorithms for commitment calculation described in the previous section can be reused without modification on the set $residualMap = evacuationMap \setminus evacuated$.

Membership check

To run the membership check, the onchain validator must have access to:

1. The current accumulator commitment $Acc$ from the treasury datum.
2. The set of $m$ outputs to be evacuated, directly from the evacuating transaction outputs.
3. The evacuation keys for each output, from the script’s redeemer.
4. The membership proof $Proof$, from the script’s redeemer.
5. A sufficiently large $(m+1)$-element trusted setup for the G2 group, from the treasury datum.

The membership verification is performed by:

1. Calculating the commitment $Evac$ using the algorithm described in Commitment calculation over the subset of evacuated elements using the trusted setup for G2.
2. Running Miller’s algorithm to check the bilinear pairing: $e(Acc, g_2) \stackrel{?}{=} e(Proof, Evac)$.

Implementation notes

Offchain commitment computation

The MVP implementation may rebuild commitments from scratch for each block, which is acceptable for evacuation maps with 1,000-3,000 elements. For larger sets, incremental update strategies become necessary.

Optimization strategies that should be considered:

• Multi-scalar multiplication (MSM) optimizations from the blst library for commitment evaluation (potential 25× speedup).
• Hot-spot optimization: Leverage transaction ordering to segregate “hot” (recently created) utxos from “cold” (older) utxos. Reuse commitments for unchanged cold portions and only recompute for the active hot region.
• Incremental updates with NTT: Use Number-Theoretic Transform to convert polynomials to point-value form, where polynomial multiplication and division become pointwise operations. This reduces complexity from $O(N^2)$ to $O(N \log N)$. The BLS12-381 curve was specifically designed to support efficient NTT operations, making this optimization strategy particularly well-suited for KZG commitments.

Onchain verification primitives

Onchain membership verification requires efficient finite field arithmetic. Plutus currently lacks native support for modular arithmetic over large integers, requiring manual implementation that consumes significant execution budget.

CIP proposals for efficient verification

CIP-133: Multi-scalar multiplication

CIP-133  proposes native multi-scalar multiplication (MSM) for elliptic curves. Verification requires computing expressions like $a_1 \cdot P_1 + a_2 \cdot P_2 + \ldots + a_n \cdot P_n$. Naive implementations process each term sequentially, while MSM algorithms (such as Pippenger’s) batch operations for significant speedup.

CIP-166: Native finite field arithmetic

CIP-166  proposes native Montgomery modular multiplication for BLS12-381’s scalar field $F_r$. Montgomery multiplication is the standard approach in high-performance cryptography, working in a transformed Montgomery space where operations are cheaper—up to 62× faster on a 1,000-element set.

The CIP drafts an opaque type bls12_381_fr representing scalars in Montgomery form, with conversion functions for both big-endian and little-endian byte representations. The core operation bls12_381_fr_mul leverages the blst library already integrated into Cardano’s cryptographic stack.

Together, CIP-166 and CIP-133 transform onchain KZG verification from an expensive manual implementation into an efficient operation using native cryptographic primitives.