Faster VID on Espresso’s critical path

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:

  1. Erasure-encode the payload. Partition the encoded payload into shares.
  2. Build a merkle tree from the shares. The root of this tree is the AVID-M commitment for this block.
  3. To each storage node send: one share and a merkle proof for that share.
  4. 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 r finalized by Espresso.
  • Sufficiently many shares s_1,...,s_k, along with their merkle paths to r.
  • Payload data p.

The statement verified by the proof is:

  • Merkle paths for the shares s_1,...,s_k all verify against r.
  • The erasure-encoding of p is consistent with the shares s_1,...,s_k.
  • The erasure-encoding of p is inconsistent with r.

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.

1 Like

a minor comment on switching to DispersedLedger VID:

I try to recall our initial justification of going with ADVZ in the first place, it comes down to the necessity of guaranteed retrievability:


(^^ P2 of original NNT22 paper: https://arxiv.org/pdf/2111.12323)

a VID certificate in ADVZ guarantees provable retrievability: all honest nodes will recover exactly the original block B′=B

a vid cert in DispersedLedger guarantees consistent retrieval: all honest nodes will recover the same block (in this case, either ⊥ or B)

the NNT paper argues that for validium, security = VID commitment with provable retrievability + a state transition proof against that VID commitment
our approach is basically saying: alternatively, security = vid commitment with consistent retrievability + state transition proof + encoding correctness proof
where the last proof has a public output that indicates if it’s a correct or incorrect encoding so that the rollup contract will know what state transition proof to accept

both approaches are secure: rollup contract will only accept new state that’s agreed among honest nodes, there won’t be ambiguity or liveness issue due to recoverability

apart from safety, we also look at preconf quality:
in both cases, a full node will receive a vid cert, retrieve the data, recompute the vid commitment to check and apply the data payload (or skip empty block in weak vid) to immediately derive the new finalized state – preconf on the strong/weak vid are the same for full nodes

for light client, weak vid cert must be supplemented with an encoding correctness proof to match the quality of a strong vid cert
but since light client need to wait for a VM state transition proof anyway to know the next state, the requirement on this additional encoding correctness doesn’t seem bad, won’t add more latency or trust assumption

in short, weak vid cert alone offers the same preconf quality as strong vid cert for full node; but weaker quality for light node.
BUT, with easy-to-generate encoding correctness proof (relative to state transition proof), there’s no material disadvantage in practice.

1 Like

Seems that we can improve the efficiency of verification for both happy-path and sad-path proofs from quasi-linear to linear runtime by employing a trick I recently noticed in an ethresear.ch post by Vitalik Buterin:

The easiest way to check the low-degree property is to choose a pseudorandom challenge value, interpret it as a coordinate, and use barycentric evaluation to check that an evaluation using the odd points and an evaluation using the even points lead to the same value. For simplicity, the Merkle root itself can be used as a challenge.

Let me translate this trick to our setting and give some detail: view the payload data as a list p(W) of evaluations of a polynomial p on some size-k roots-of-unity domain W. Similarly, view the Reed-Solomon encoded payload data as a list of evaluations of p on some larger roots-of-unity domain W'. Consider a partition W_1,...,W_n of W' so that we may write the Reed-Solomon encoded payload data as a list p(W_1),...,p(W_n) of size-k sublists. For each such sublist p(W_i) evaluate p at a pseudorandom challenge value (derived from the merkle root r) via barycentric evaluation. We conclude that the Reed-Solomon encoding is correct if and only if each of these evaluations produces the same value.

The idea is to replace the FFTs in the SNARK-friendly verification of happy-path and sad-path proofs with this barycentric evaluation check. The barycentric check takes only linear-time, whereas the FFTs are quasi-linear-time. Thus, we improve the complexity of the performance-critical SNARK-friendly computation.

In more detail: happy-path proof is as follows. Input:

  • The AVID-M merkle root r finalized by Espresso.
  • (Purported) erasure-encoded payload data p(W_1),...,p(W_n).

Statement of proof:

  • r is the correct merkle root of p(W_1),...,p(W_n).
  • The barycentric evaluations described above are all equal.

The happy-path prover might begin with only the unencoded payload data p(W). In this case she can apply FFTs to prepare encoded data p(W_1),...,p(W_n) needed for the proof input. These FFTs are not part of the SNARK-friendly verification of a happy-path proof.

Sad-path proof is as follows. Input:

  • The AVID-M merkle root r finalized by Espresso.
  • Sufficiently many shares s_1,...,s_k, along with their merkle paths to r.
  • (Purported) erasure-encoded payload data p(W_1),...,p(W_n).

Statement of proof:

  • r is not the correct merkle root of p(W_1),...,p(W_n).
  • The barycentric evaluations described above are all equal.
  • Merkle paths for the shares s_1,...,s_k all verify against r.
  • (Purported) erasure-encoded payload data p(W_1),...,p(W_n) are consistent with shares s_1,...,s_k.

The sad-path prover is given only the shares s_1,...,s_k. But, as described in the original post, she can use this data to recover the original payload data p(W), from which she can apply FFTs to prepare encoded data p(W_1),...,p(W_n) needed for the proof input. As above, this computation is not part of the SNARK-friendly verification of a sad-path proof.

2 Likes