Abstract
We sketch a modification of the Espresso network that we think could significantly improve throughput and latency on the critical path to consensus. We describe how this modification achieves Espresso’s security goals even when the scheme upon which it relies for verifiable information dispersal (VID) cannot guarantee recoverability of the payload at the time of finalization. This insight opens the design space, affording us the luxury to choose a much faster and simpler VID scheme built solely from any erasure code and any hash function. This article presents only an idea: we do not yet have benchmark data to quantify this improvement.
Authors (alphabetical)
Jeb Bearer, Benedikt Bünz, Binyi Chen, Ellie Davidson, Gus Gutoski, Chengyu Lin, Alex Xiong
Background
Verifiable information dispersal (VID) on the critical path
The Espresso network reaches consensus on the contents and ordering of payload data, but does not execute any instructions contained in that data. As such, it is not necessary that all nodes on the Espresso network see all payload data before the network finalizes that data. Instead it is necessary only that the network ensure data availability, so the payload is available later for anyone who wants it. By comparison, in a conventional blockchain all nodes must see all payload data in order to execute instructions in that data. Thus, Espresso faces fewer design constraints than a conventional blockchain. This freedom presents an opportunity for Espresso to achieve higher throughput and latency than a conventional blockchain.
Espresso capitalizes on this opportunity by using a scheme for verifiable information dispersal (VID) to ensure data availability without the need for all nodes to see the entire payload. Reminder: a VID scheme enables a disperser node to split payload data among many storage nodes in such a way that the full payload can be recovered later even in the presence of malicious network participants. This VID scheme appears in the Savoiardi layer of Espresso’s three-layer solution for data availability called Tiramisu. (See the white paper or article.)
Espresso’s Savioardi VID scheme has some similarity with Ethereum’s Danksharding proposal. The scheme is a variant of ADVZ, named after its authors. (See the original ADVZ article or Appendix A of Espresso’s white paper.) Like Ethereum’s Danksharding proposal, ADVZ uses a polynomial commitment scheme such as KZG in order to guarantee that the payload it disperses is always recoverable. KZG is computationally demanding, so the recoverability guarantee carries a performance penalty.
This performance penalty is especially costly because it occurs on Espresso’s critical path to consensus. Reminder: the critical path is that portion of the Espresso protocol that finalizes new payload data. The critical path is upstream of everything else in Espresso and the layer-two solutions built on Espresso. As such, the top performance priority of Espresso is to optimize the throughput and latency of the critical path.
After the critical path: the derivation pipeline
The derivation pipeline is the next step after a payload has been finalized by Espresso’s critical path. To refresh your memory, each rollup on Espresso has its own derivation pipeline that derives that rollup’s block stream from the output of the Espresso network and produces a cryptographic proof of correctness of this derivation. This proof allows rollups to “plug in” to the Espresso network without the need to alter their execution pipelines: each rollup simply swaps out its centralized sequencer for Espresso + derivation pipeline.
Espresso’s derivation pipeline:
Verification of the proof produced by the derivation pipeline should be “SNARK-friendly”, meaning that it is fast to verify in an arithmetic circuit suitable for a succinct non-interactive proof such as a SNARK.
The derivation pipeline need not prove that the payload was correctly erasure-encoded because ADVZ dispersal has already guaranteed this property. However, a proof of some type is still necessary to prove that the payload produced by the derivation pipeline is consistent with the payload commitment finalized on Espresso. This proof is called a namespace proof in Espresso’s article on the derivation pipeline.
The final step in this process is the rollup’s execution pipeline. This is where the rollup applies its own state transition function to the new rollup blocks. The details of this process are rollup-specific. For example, an optimistic rollup simply posts a new purported state root to the L1, thus initiating a challenge period. By contrast, a validium rollup also posts to the L1 a succinct proof that the new state root was correctly computed as a function of the new rollup blocks.
Each rollup must have some way to recognize when a new block is invalid and dispose of it. There are many ways for a malicious actor to prepare an invalid rollup block. For example, a payload could contain conflicting double-spend transactions, or the payload’s binary data might be malformed. A simple solution to this problem is to enact a rule that views any invalid block as an empty block. Ultimately, the decision on what to do in the event of an invalid block always belongs to the rollup.
Insight: recoverability at finalization is unnecessary
A core insight of this article is that payload data need not be recoverable at the time of finalization on Espresso. If it is later discovered that a payload finalized by Espresso is unrecoverable then any affected rollup can simply treat it the same way it would treat an invalid block.
In order to act upon this insight each rollup needs a way to identify an unrecoverable payload. Fortunately, Espresso already has all the infrastructure in place for this task: we could attach a proof of payload recoverability to the existing derivation pipeline.
Our proposal for Espresso’s derivation pipeline:
This insight opens a much larger design space for Espresso’s VID scheme. There are extremely simple and fast VID schemes such as AVID-M that trade payload recovery for vast performance improvements on Espresso’s critical path.
Our task in this article is to explain how a proof of payload recoverability works and argue that such a proof can be verified efficiently relative to today’s Espresso.
AVID-M proposal
We propose to switch Espresso’s Savoiardi VID scheme from ADVZ to a suitable variant of AVID-M. In this section we describe the new critical path and derivation pipeline, including how to make a proof of payload recoverability. In later sections we compare this proposal to Espresso in its current form.
To this end we describe the life cycle of a new payload block on the Espresso network. For simplicity we focus only on the life cycle of a single rollup’s payload block with the understanding that this description extends easily to a full, multi-rollup payload block produced by Espresso’s sequencing marketplace. We describe this extension in the Appendix.
Espresso’s critical path
A payload’s life cycle begins when the Espresso consensus leader receives the rollup’s new payload block from that rollup’s builder. This event initiates Espresso’s critical path to consensus. Espresso consensus nodes collectively execute a simplified AVID-M dispersal algorithm, where the consensus leader is the VID disperser and each other consensus node is a VID storage node. To refresh your memory on AVID-M dispersal, the disperser does:
- Erasure-encode the payload. Partition the encoded payload into shares.
- Build a merkle tree from the shares. The root of this tree is the AVID-M commitment for this block.
- To each storage node send: one share and a merkle proof for that share.
- Await a quorum of signed attestations from storage nodes.
The job of a AVID-M storage node is simple: receive a share from the disperser, verify the accompanying merkle path, and (if verification is successful) reply to the disperser with a signed attestation. Any quorum of attestations from storage nodes is cryptographic proof of successful dispersal of the payload.
Happy-path proof
Now things get interesting. As observed above, a malicious consensus leader could finalize an improperly erasure-encoded payload, in which case the payload could be unrecoverable. (This cannot happen under the ADVZ scheme in today’s Espresso.)
Our idea is to add a proof of correct erasure-encoding to the existing derivation pipeline. This proof ensures that the payload finalized by Espresso is recoverable, so it’s safe to include it in the rollup. We call it a happy-path proof.
The happy-path proof proves that a payload’s AVID-M commitment matches the commitment finalized by Espresso. Specifically, the happy-path proof proves correct execution of steps 1 and 2 from the above description of AVID-M dispersal.
Sad-path proof
But the problem is not yet solved! If a malicious consensus leader finalizes an improperly erasure-encoded payload then it is impossible to produce a happy-path proof. What then?
In this case, our idea is to add a proof of incorrect erasure-encoding to the derivation pipeline. This proof establishes that the payload is malformed, so it should be excluded from the rollup. We call it a sad-path proof.
A sad-path proof is significantly more costly to produce than a happy-path proof, but the cost to verify a sad-path proof is almost identical to the cost to verify a happy-path proof. A sad-path proof is constructed by collecting sufficiently many storage shares s_1,...,s_k to guarantee the existence of a unique payload p consistent with those shares. (The number k of shares required for this purpose is a function of the erasure code rate and the number of storage nodes.)
The sad-path prover recovers p by decoding the erasure code from the shares he collected. This decoding might be computationally costly, but it is a one-time cost paid only by the prover—the decoding computation is not part of the SNARK-friendly verification of a sad-path proof. Instead, sad-path proof verification checks that the erasure-encoding of p is consistent with the collected shares, yet inconsistent with the finalized block commitment. (This must be the case, as otherwise p is correctly erasure-encoded.)
In more detail, the input to the proof is:
- The AVID-M merkle root
rfinalized by Espresso. - Sufficiently many shares
s_1,...,s_k, along with their merkle paths tor. - Payload data
p.
The statement verified by the proof is:
- Merkle paths for the shares
s_1,...,s_kall verify againstr. - The erasure-encoding of
pis consistent with the sharess_1,...,s_k. - The erasure-encoding of
pis inconsistent withr.
Why is it secure?
For each payload finalized by Espresso it is always possible to produce either a happy-path proof or a sad-path proof, but never both. Thus, a rollup’s derivation pipeline always establishes either (i) the payload is well-formed and available, or (ii) the payload was maliciously encoded. As suggested earlier, each rollup already has a policy to handle an invalid block. We expect that it is trivial to extend that policy to also handle an improperly encoded Espresso payload.
A sad-path proof is cryptographic proof of malicious behavior by the Espresso consensus leader (or whoever did the erasure-encoding). The Espresso network could respond to this behavior the same way it currently responds to any other type of provable malicious behavior. For example, Espresso might confiscate a security deposit, sometimes called “slashing”. In any case, a malicious actor cannot compromise the safety of Espresso.
Comparison against today’s Espresso
Notation
In this section we use the following notation:
- FFT: Fast Fourier Transform. Also called the Discrete Fourier Transform (DFT) or Number Theoretic Transform (NTT). It’s used to implement the Reed-Solomon erasure-code used in most VID schemes.
- MSM: Multi-scalar multiplication. A linear combination of elliptic curve points. It’s the main performance bottleneck in computing a KZG commitment.
- FK23: The Feist-Khovratovich algorithm. It’s a FFT-inspired algorithm to compute a batch of multiple KZG proofs. It’s used by the ADVZ disperser to compute storage shares.
- Pairing: An elliptic curve pairing algorithm. It’s the main performance bottleneck in computing a KZG verification. It’s used by storage nodes to verify the correctness of their shares.
Critical path
| Actor | Task | Today’s Espresso | Our proposal |
|---|---|---|---|
| Disperser | Erasure-encoding (Reed-Solomon) | FFT | FFT |
| Merkle tree of encoded shares | fast | fast | |
| KZG commitments | MSM | - | |
| KZG proofs | FK23 | - | |
| Storage nodes | Merkle proof verification | fast | fast |
| KZG commitment aggregation | MSM, small | - | |
| KZG verification | Pairing | - |
Our proposal
The critical path in our proposal has been cut to the bare minimum needed for any VID scheme based on erasure codes. The only non-negligible cost is the FFT to compute erasure-encoding (assuming the scheme is instantiated with the Reed-Solomon erasure code).
Today’s Espresso
By contrast, the critical path in today’s Espresso must pay all the costs of our proposal, plus several additional significant costs for KZG polynomial commitments, proofs, and verification.
Conclusion
Preliminary benchmarks suggest that our proposal could deliver a 5x or greater efficiency improvement on the critical path as compared to today’s Espresso. This estimate is subject to change pending careful experiments.
Derivation pipeline
| Task | Today’s Espresso | Our proposal |
|---|---|---|
| Namespace proof | MSM | - |
| Happy-/sad-path proof | - | FFT |
Today’s Espresso
In today’s Espresso a derivation pipeline need not prove (or disprove) that the payload was correctly erasure-encoded because ADVZ dispersal has already guaranteed this property. However, a proof of some type is still necessary to prove that the payload produced by the derivation pipeline is consistent with the payload commitment finalized on Espresso. This proof is called a namespace proof in Espresso’s article on the derivation pipeline.
Verification of this namespace proof involves the computation of KZG commitments for the payload, which is a MSM task.
Our proposal
In our new proposal the namespace proof is a byproduct of the happy-path and sad-path proofs we described above, so no additional work is needed to establish the guarantee of the namespace proof.
Verification of either a happy-path proof or a sad path proof is bottlenecked by computation of the Reed-Solomon erasure-code, which, in turn, is bottlenecked by the FFT.
Conclusion
The main computation task in the verification of a namespace proof from today’s Espresso (MSM) is very different from that of a happy-path or sad-path proof from our proposal (FFT). Which of these two tasks admits the fastest solution? The answer could depend upon the computation environment (native versus SNARK) or other situation-specific details.
In a native computation environment we expect algorithms for these two tasks to have roughly equal efficiency with the understanding that this expectation allows for a large margin of error. By contrast, in a SNARK-friendly environment we speculate that the FFT is much faster than the MSM. Thus, we speculate that SNARK-friendly verification of a proof from a derivation pipeline from our proposal to be much faster than that from today’s Espresso.
Appendix: other considerations
Extension to multi-rollup payload blocks
So far we have restricted attention only to a single rollup’s payload block. It is straightforward to extend the protocol of this article to a full, multi-rollup payload block produced by Espresso’s sequencing marketplace.
An important property to maintain is that the cost to produce a happy-path or sad-path proof for rollup A must depend only on the size of rollup A’s portion of the payload, and not on the payloads for other rollups B, C, D, etc. (We are willing to tolerate a logarithmic dependence on the total number of rollups so that we may deploy basic tools such as merkle paths.)
The solution is to run a separate instance of AVID-M for each rollup in the block. This solution produces one AVID-M commitment (merkle root) for each rollup. Presumably, Espresso’s block commitment should be predictably succinct, so it makes sense to further aggregate all these AVID-M commitments into another merkle tree, the root of which shall be the commitment to the full, multi-rollup Espresso block.
Thus, we extend the protocol of this article to a multi-rollup block merely by augmenting all merkle paths to include a small number of additional steps to connect the AVID-M commitment to the top-level merkle root of all AVID-M commitments. The overhead cost to support multi-rollup blocks is negligible.
Flexibility in AVID-M: binary fields are now an option
ADVZ and other VID schemes based on KZG polynomial commitments must first transcode raw binary payload data into a sequence of elements from a 256-bit pairing-friendly prime field. This transcoding adds computational overhead to the critical path and wastes communication bandwidth and storage space.
By contrast, AVID-M is very flexible. For example, it is not necessary that the erasure-encoding in AVID-M be instantiated over a 256-bit pairing-friendly prime field. Instead, it could be instantiated with any finite field whatsoever. This freedom allows us to choose the field so as to minimize transcoding overhead or optimize erasure-encoding.
For example, it might be possible to use a binary field instead of a prime field, which completely eliminates all overhead from transcoding raw binary payload data. In order to use a binary field we require an erasure code with a fast implementation over a binary field. In the case of the Reed-Solomon code, it suffices to find a FFT-like algorithm that works with binary fields. Recent progress on “additive” FFT algorithms seems promising: see this article by Vitalik Buterin or this white paper by Irreducible.
What about fast preconfirmations?
Reminder: a preconfirmation (or “preconf”) is a signed promise from a consensus leader to an end-user that a new transaction from the user will meet certain conditions for finalization and execution. The goal is to enhance the end-user experience with ultra-fast, sub-second transaction confirmations. The Espresso network is compatible with preconfs as discussed in this article.
As described above, our proposal makes it possible for the Espresso network to finalize an improperly erasure-encoded payload block, in which case the block is invalid. At first glance it might seem that this possibility might invalidate or cast doubt on the integrity of preconfirmations. For example: what happens to a preconfirmation if it is later revealed by a sad-path proof that the block is invalid? Is it even possible to make a preconf for an invalidly encoded block? In this section we argue that the possibility that Espresso might finalize an improperly encoded payload block has no effect on the integrity of preconfirmations.
In order for our proposal to support preconfs the erasure code must be in “systematic” form, which means that the original payload data must appear as a subset of the erasure-encoded data. This condition is easy to meet: the Reed-Solomon erasure code admits a fast, FFT-based implementation for its systematic form.
Given a systematic erasure-code, it is trivial for the consensus leader to make a preconf for a user. Payload data for the user’s new transaction must appear in the clear in one or more of the storage shares from the erasure-encoded payload. The preconf proof is merely a merkle path to the storage shares touched by that transaction.
What happens if the payload was improperly encoded, resulting in a sad-path proof? As explained previously, there are many ways for a malicious actor to prepare an invalid payload independent of Espresso. Any policy to handle such cases must also address any potential preconfs associated with the invalid payload. Typically, an invalid payload also invalidates any preconf associated with that payload. This invalidation violates the consensus leader’s preconf promise to the end-user, thus triggering whatever penalty mechanism is in place to discourage promise-breaking. There is no reason why this process could not also apply in the event of a sad-path proof on Espresso.
In light of this discussion, an Espresso preconf is properly viewed as cryptographic proof that if the payload block is valid then the user’s transaction is cryptographically guaranteed to have the promised properties. For example, a preconf proof asserting that a user’s flash-loan has netted a certain profit margin must have one of the following two outcomes: (a) the block is invalid, in which case the flash-loan never occurred, or (b) the block is valid, in which case the flash-loan occurred and netted the promised profit. This way of viewing Espresso preconfs applies regardless of whether our proposal is eventually adopted. Thus, our proposal has no effect on the integrity of preconfirmations.
