A simple batching scheme for shared sequencers

Just update the extraction function stop making things complicated

Background

Read my post on shared sequencers.

A lot has been made of shared sequencers allowing atomic inclusion of transactions. However, this requires protocol changes to all component rollups. Those protocol changes are unspecced, and the ideas are hairy and weird.

I suspect the shared sequencer folks are just overcomplicating it to look mysterious. So I decided to sit down and design a basic cross-rollup bundling scheme.

Fortunately we have prior art on arbitrary bundling schemes, so we know what to avoid, and generally how to construct them. Turns out it’s easy to modify the filtration function of each rollup.

Goals

• It should allow multiple transactions from multiple EOAs.

• It should be impossible to break a bundle (include a component transaction without including all other transactions in the same sequence.

• No shared TX format should be required.

• It should be cheap to sign (at worst O(n) in number of transactions c.f. the quadratic sighash problem)

Modifying the component rollup TX formats

• Omit signatures in all cases.

• Include chain id or other domain binding in the tx.

No other modifications

Bundling

For each component rollup, have a datastructure that maps an EOA address to a list of transactions from that address. The transactions should be serialized and represented as opaque bytes. The signer(s) need not understand the contents.

struct Bundle {
    arbitrum: Map<Address, Vec<OpaqueBytes>>,
    optimism: Map<Address, Vec<OpaqueBytes>>,
}

Signing

We iterate over all the transactions, inserting separators for the rollup and the sender. This ensures that a txn is bound to a specific rollup, and a specific EOA, and can’t be misinterpreted. It also ensures that the rollup and EOA information is exposed to the all observers, without requiring the observers to understand tx structure.

Signing this way ensures also ensures that all signatures commit to all transactions. This makes the bundle unmodifiable. It can be neither extended nor unbundled.

fn signing_hash(&self) -> [u8;32] {
    let mut hasher = Keccak::new();

    hasher.update(b"arb");
    for (from, txns) in self.arbitrum.iter() {
        hasher.update(&from);
        txns.for_each(|tx| hasher.update(tx.hash()));
    }

    hasher.update(b"opt");
    for (from, txns) in self.optimism.iter() {
        hasher.update(&from);
        txns.for_each(|tx| hasher.update(tx.hash()));
    }

    hasher.finalize()
}

fn sign(&self, key: &SigningKey) -> Signature {
    key.sign_raw(self.signing_hash())
}

Use some additional domain binding too if you want, idc.

Verifying

Verifying may be done without understanding tx contents.

We verify by:

1. computing the signing hash for the bundle

2. checking that each declared EOA for the bundle has a signature over the signing hash

struct SignedBundle {
    bundle: Bundle,
    signatures: Vec<Signature>,
}

fn verify(bundle: &SignedBundle) -> Result<()> {
    let signing_hash = bundle.bundle.signing_hash();

    // Collect the signers whose signatures are included
    let addresses = bundle
        .signatures
        .map(|sig| sig.recover_raw(signing_hash))
        .collect::<Result<HashSet<_>>>();

    // collect the stated EOA senders
    let eoas = bundle.arb.keys()
        .chain(bundle.opt.keys())
        .collect::<HashSet<_>>>();

    // Check that those sets are equal
    if eoas != addresses {
        return Err("missing sig or extra sig or whatever")
    }

    Ok(())
}

In this way we ensure that all signatures cover all transactions (and will be invalid if a transaction is added or removed or substituted), and no transaction is uncovered by a signature. It’s also not very expensive to make the extra check.

Serializing

Who cares it’s trivial. Just do the thing.

Filtering

Component rollups MUST filter bundles whose verification fails. Note that filtering does not require any knowledge of the contents of the transactions, just checking the signatures on them.

This means that bundles with incorrect or insufficient signatures are included in the host history, but are filtered from the rollup histories. They do not have any effect on the rollup chains. The same thing is done for invalid transactions in sequencer output in rollups on mainnet today, ofc.

Conclusion

This achieves atomic inclusion for multi-party bundles. Multiple EOAs can include transactions. Bundles can’t be split, as all sigs commit to all txns. Signing is O(n) in number of transactions. Verifying is O(n + s) where s is the number of signers. You can use an aggregatable signature scheme to wiggle that tradeoff a bit if you want.

Boom. Goals achieved.

So what does this not get us? Astute readers who have read my past blog posts and annoyed tweet threads probably realize that bundling this way can’t get you atomic execution. Yep. So you actually can’t use this to construct any interoperability scheme without a further mechanism / protocol change to handle the execution portion. MEV-extracting block builders get execution by being top of block. But you, the end user, don’t extract stuff. You get extracted.

So yes, it is trivial to construct a bundling scheme, but only because we narrowed the problem to the point of near-uselessness.

In summary, Atomic inclusion is boooooring and easy and not very good for anything except MEV extraction. Stop making a big deal of it.