Non-Interactive Optimistic Rollup

Research
1

When discussing options for VM architecture, there may be a middle ground between interactive fraud proofs and proving everything via SNARKs.

The idea in a nutshell is to use SNARKs as non-interactive fraud proofs.

In more detail, here’s how it could work:

Execution

  • There are two validator roles: “executors” and “challengers”
  • Executors register by staking funds (that will be used to penalize bad actors). The active executors for layer i execute transactions in layer i and publish a commitment to the state after layer i is executed. The commitment includes:
    • The layer hash (the set of all transactions so far). This is required in case there’s a reorg, to ensure that the executor isn’t penalized in this case (and also so that users realize the state is no longer relevant).
    • The hash of the correct executor commitment for layer i-1. This pointer forms a “state chain” consisting of the states in each layer from i to genesis.
    • The hash of the state after executing all transactions up to (including) layer i.
  • I’m not sure challengers need to register at all (this part needs to be determined). Assuming, challengers are a subset of the executors, they work as follows:
    • Challengers also execute all transactions (just like executors). If a challenger agrees with an executor on the layer hash, but computes a different state hash for layer i, it
    • Identifies the first incorrect state in the “state chain” of the bad executor. Suppose it is in layer j\le i. Let s_{j-1} be the state at layer j-1 and s^*_j be the first incorrect state in the chain.
    • The challenger publishes a SNARK that executing the transactions in layer j, starting with a state whose hash is s_{j-1} leads to a state whose hash is s_j\ne s^*_j.
    • The challenger will also publish a new correct state for layer i.

Verification

  • If there’s only a single state hash published for a layer, miners will accept it as the correct state.
  • If there are multiple state hashes published, miners will wait until successful challenges reduce the number of unchallenged state hashes to 1 (it’s possible this will take more than one round, because challengers can potentially also publish incorrect states, if the challenged states are in the past),

Advantages vs Interactive Fraud Proofs and Full SNARKs

  • Compared to interactive fraud proofs:

    • executors don’t need to respond to challenges, so there’s no need for a very long settlement period.
    • executors don’t need to do extra computation during execution (such as creating merkle trees, transpiling into a lower-level language, etc.), so this role can be performed by fairly low-powered devices.

  • Compared to full SNARKs:

    • there’s very little delay in the optimistic case, since we don’t need to wait for the SNARK to be generated.
    • there’s a much lower cost, since we don’t need to run a prover most of the time. It’s enough to spin up a cloud-based prover in an ad-hoc manner when a challenge will actually be successful (we just need to make sure that the executor’s staked funds will be sufficient to cover this cost).
2

@talm When comparing interactive fraud proofs, the issues are:

  • if there’s a long reveral that’s needed, then generating SNARK for it will be infeasible.
  • Even if it’s a short reveral for which SNARK is feasible, it will be orders of magnitude more costly for the challenger to generate the SNARK than to perform the interactive fraud proof.
  • One of your complaints was that the interactive fraud proof requires the honest challenger to have a security deposit that’s larger when the reversal length is larger. As mentioned, I think that the concern is exaggerated because (1) the deposit doesn’t need to be much larger (the long reveral requires a logarithmic number of rounds of interaction), and (2) the time-value of the deposit is low because it’s needed for only the short challenge timeframe, and (3) as previously discussed we can improve by splitting the deposit among all the honest challengers.
    ** However, with the non-interactive SNARK the cost of generating the proof for a long reversal is super-linear (as opposed to logarithmic), so your complaint (regarding the burden of the honest challenger when there’s a long reversal) is far more relevant in the non-interactive fraud proof case.
  • You’re right about “don’t need to do extra computation during execution” in the happy flow, but those aren’t demanding computations (there’s no merkle tree, only hash chain).
  • About “no need for a very long settlement period”, the opposite is true if the time to generate the SNARK is longer than the interactive proof – which is obviously what we should assume, in theory it depends on parameters such the layer time (if it’s shorter then the interactive proof is faster) and the VM instruction set (if it has complex non-algebraic-friendly instructions then the SNARK proof generation time will explode).
    ** Also, when you mention “advantages” it’s better to clarify for whom it is advantageous. Here you mean that it’s advantageous to end-users, not advantageous challengers (who need to perform a costly computation that they wouldn’t need with an interactive fraud proof). But w.r.t. to end-users it’s false both because the “long settlement period” is shorter than SNARK proof generation time and because the end-users may need to cover the cost of generating the SNARK when there’s a long reversal (the reward that the challenger needs to be higher than the cost of generating the SNARK proof).
3

No, the SNARK proofs are only for a single layer. If there’s a long reversal, then the first “wrong” state is an old layer, in which case the challenger just proves for that layer.

See previous point — the proof cost is essentially constant regardless of how long the reversal is.

I think the main reason that we need a long settlement period for the interactive proofs is we can’t distinguish a DoS on the challenged validator (or even a random failure) from a malicious validator that chooses not to answer. So even though the interactive period can technically be short, we have to wait long enough that a human could potentially resolve a failure or DoS situation (e.g., this could require purchasing a new hard drive, installing it, etc.).

When the challenge is non-interactive, this becomes irrelevant, so the only time limitation is how long it takes to generate a proof (which, for a single block, should not take long).

I think we should still choose a SNARK-friendly instruction set, both to make proving more efficient and because it leaves the door open to future improvements (e.g., using recursive SNARKs to compress history)

That’s true, but the reward is taken from the executor’s penalty, not from the end users (this is possible because the cost does not grow with the length of the history reversed).

4

@talm I think that you’re missing a point regarding the interactive fraud proof for a long reversal, there the challenger doesn’t prove that the already accepted commitment is wrong, but rather the challenger declares that the correct commitment (for the latest layer) is hers, so that if she’s right then any binary search with her challenge will end up in her favor. As we previously discussed (https://community.spacemesh.io/t/lite-client-for-spacemesh/83/14), multiple concurrent challenges are allowed, but any dishonest challenger (and/or dishonest challenged executor) will lose the security deposit to an honest challenger that can join in an intermediate round. So the outcome of the challenge (under the assumption that there’s at least one honest challenger) is that the L1 miners now know the correct state for the latest layer.

What you propose doesn’t give this outcome. We’d be at the mercy of the randomness generator (Fisher-Yates according to the most recent layer data, which is grindable unless with use low-influence function over multiple layers) in hope that the first challenger is honest, and we cannot allow concurrent challenges (if both Alice and Bob challenge concurrently and prove that the same single layer rollup is incorrect but declare different state commitments for the latest layer, then at least one of them will need to be challenged again, and so on). So if for example the first 10 randomly selected challengers are dishonest, then we will have to endure 11 challenges until getting a correct commitment for the latest layer.

Another issue is that you are assuming that there must be a rollup commitment for every layer, without skips (for simplicity let’s indeed assume that the rollup interrval is a single layer rather than longer interval). This can indeed be enforced by the core protocol, say if layer 100 to 105 are missing rollup commitments because all the executors are sleeping then the commitment for layer 100 and the following layers can be put in layer 106. However, this is less efficient than skipping the missing layers and allowing the next rollup commitment to be for the latest layer, which is natural and efficient due to the logarthimic number of challenge rounds of the fraud proof, but in the frame that you’re proposing it’s impossible because you want to enforce the property that it’s always possible to challenge a single layer (so we’d be sacrificing efficency in a scenario when there weren’t any Byzantine executors, just inactive executors).

Even if we decide that we like your frame in which we can always challenge just one single layer rollup, this still doesn’t imply that non-interactive SNARK is the best component to go along with it. The 1st alternative is to do the interactive fraud proof for a single layer (which we can treat as a constant-time blackbox), and in fact I claim that if you offer the executors the choice between snark-for-single-layer and interactive-proof-for-single-layer then they will all prefer the interactive component because it’d be miniscule in terms of how demanding it is relative to snark of say evm). The 2nd alternative is just to let L1 miners switch into full executor mode in order to confiscate the security deposit of the dishonest executor, in other words, instead of letting the L1 miners perform a verification of a single transition (with the interactive proof) or verification of a snark of single layer, the miners will perform verification of a single layer rollup in constant-time.

I think that your more significant complaint (w.r.t. being more problematic to ensure that rational participants will follow the protocol) regarding optimistic rollup was the “fraud” part rather than the “interactive” part, because the “interactive” part is still much faster and cheaper than generating SNARK in practice, whereas the “fraud” style proof system implies that any arbitrary old history can be challenged in the future (and a “validity” style proof system implies that each rollup is accompanied by a validity proof that ensures that it must be correct unless the underlying algebraic assumptions are broken).

5

This is the same as what I suggested: the challenger also makes a claim about the correct commitment to the last layer. In both cases a malicious challenger can lie about the last layer, in which case we need another fraud proof. You’re right that in the interactive case, the second challenge would require a shorter interactive phase, but it’s still an extra interactive phase that needs to wait the full settlement time to resolve, whereas the SNARK version only needs to wait for a time that depends on the SNARK proof efficiency.

We can (and should) allow several concurrent challenges. If there are 10 competing challenges in the first challenge phase, of which 9 claim an incorrect final state, then we do the following:

  • Let i^* be the last layer at which all 10 challenges agree.
  • Phase 2 challengers will generate a SNARK for every layer j>i^* such that there exists a bad challenger that agrees with the correct state chain up to layer j-1 and differs at layer j.
    • This can be done by a single challenger creating all the proofs, or by multiple challengers in parallel, each creating one (or some) of the proofs.
  • Verifiers will start with the i^*+1 SNARK verification, then follow the state chain to the next layer, and so forth. If there is at least one honest challenger in each phase, verifiers will check at most one valid SNARK proof per layer (invalid SNARK proofs won’t be gossiped, so their cost is much lower).

In each challenge phase, consensus on correct history is advanced by at least one layer. Once this happens (i.e., layer i is the earliest one challenged, and at least one challenger gave a correct state chain for i), no one can ever generate a challenge that disputes any layer \le i. This is because to generate a challenge, you must create a SNARK for an incorrect state transition at some earlier layer, but none such exists. (This holds even if there were no challenges at all — if executors agreed on the state chain at layer i, and it is correct, then no future challenges can be brought against any earlier layers).

The state chain isn’t part of the consensus state (at least, there’s no requirement for it to be there). If executors missed layers 100-105, then executors at layer 106 will just announce the state chain items for the missing layers. This just requires 2 hashes per layer (state hash + hash of previous chain item).

You’re right that this solution isn’t as good as a full SNARK proof, and that we can take some of the elements and use them with interactive fraud proofs. However, the single-layer interactive fraud proof is missing a critical component — it doesn’t protect from challenges against history (and the same is true for switching L1 miners into full executor mode). In contrast, with a non-interactive fraud proof, challenges against correct history are simply not possible.

Regarding executor’s preferences — executors who don’t want to generate SNARKs don’t register as challengers, so will never have to do so — they just execute the native code and hash the resulting state.

6

Please re-read, the challenger makes a claim only about the correct commitment.

BTW this implies that in the happy flow of the interactive optimistic rollup it’s also the case that “executors don’t need to do extra computation during execution”.

But those are the minor points in this context, the major point (which isn’t captured by “challenge would require a shorter interactive phase”) is that if there’s a single honest challenger then just a single fraud proof blackbox (implemented using interactivity in logarithmic number of rounds) will be invoked and in the end of this single invocation all the L1 miners will know the correct rollup state, and any addiotional fraud proof blackboxes will fail and cause the invoker (who is nessecarily malicious) to lose money. This major property cannot be realized with non-interactive optimistic rollup.

It is counterproductive to allow concurrent challenges with non-interactive optimisitc rolliup, because the adversary can cause us to advance by only one layer.
If you look at your previous criticism of interactive fraud proof, it was regarding its properties when a long reversal is needed. If we use non-interactive optimistic rollup and allow concurrent challenges, then it’s the worst of all worlds (if a reveral of 1000 layers is needed, then L1 miners will need to wait for 1000 consecutuve SNARKs before they know the correct rollup state).

As mentioned, it’s superior for non-interactive optmisitic rollup to disallow concurrent challenges, and instead make use of the random shuffle (that we already use anyway) to pick a uniform random challenger (if the randomness is unbiased), This way, if the challenger is honest then the long reversal is corrected via this single challenge (if a reversal of e.g. 1000 layers is required then – under the assumption that there’s a significant amount of honest challengers – this will be way faster than waiting for 1000 snarks). So we’d be at the mercy of the randomness generator, but it’s still a lot better than allowing concurrent challenges.

It needs to be sync’d somehow. The most basic scenario is a newcomer that receives a rollup state from one neighbor and a different rollup state from another neighbor, how would she know who to trust? With interactive fraud proof, the rollup states are a natural part of the contextually valid mesh.

Is this a response to ‘the "fraud” style proof system implies that any arbitrary long history can be challenged’ ? I’d say that non-interactive optimistic rollup isn’t as good as full snark rollup w.r.t. to this particular property, but it’s a minor property and the advantages of non-interactive optimistic rollup outweigh the advantages of full snark rollup (efficient happy flow is a key advantage). I’d also say that interactive optimistic rollup doesn’t have any practical disadvantages and is the most fitting here (because the input for each rollup is already on L1 anyway, unlike L2 optimistic rollup that needs to batch the input data and put it on L1 as calldata).

True, but you’re emphasizing a rather peculiar property (we should care more about challenging incorrect history). Interactive optimistic rollup is pleasant without this property: if the histroy is correct but it gets challenged, then the dishonest challenger just loses money under the assumption that there exists at least one honest challenger (if there aren’t any honest challengers now but an honest challenger joins soon after this dishonest reversal occured, then the honest challenger will still be rewarded via the deposit of the dishonest challenger).

7

Maybe a good way to explain how I think about this is that I would like security to hold as much as possible against malicious adversaries, as opposed to rational adversaries.

  • In the full SNARK solution, there we get full security against malicious adversaries — no PPT adversary can generate a bad proof, regardless of how much money they have to burn. Honest miners have to verify one SNARK proof per layer (or per batch, if that’s larger) and that’s it.

  • In the interactive fraud-proof solution, a malicious adversary can DoS the system by repeatedly challenging ancient history. This can happen even if our honest majority assumptions hold, and can cause consensus detays while the challenges are resolved (again, due to the interactive nature of the proofs, we have to allow long periods for users to respond, and the adversarial challengers can force the maximum wait for each phase).
    Of course this costs the adversary a lot, but that’s only protection against rational adversaries.

  • In the non-interactive fraud-proof solution, a malicious adversary can cause honest miners to verify one SNARK proof per layer (or per batch). which is similar to the full SNARK solution, except that it also causes a consensus delay until the challenge SNARK can be generated. However, since it’s non-interactive, the delay doesn’t have to take into account a “human-in-the-loop”, so can be much shorter than the interactive version.

    Note that ancient history can’t be challenged in this setting, unless there was a very long dishonest majority period, in which case there could be a re-org to ancient history, and the entire state from the reorg must be recomputed.

    Even in this case (which is already extremely unlikely), the non-interactive proof won’t require many SNARK verifications, as long as there is at least one honest challenger in each challenge phase. Here’s how a challenge to 1000-layer history would work, assuming we elect say 20 challengers at most for each layer:

    • At layer i, there are at least 2 executors with different state commitments, and state chains that diverge at layer i-1000.
    • 20 phase 1 challengers for layer i publish a SNARK proof for layer i-1000, and a state commitment for layer i. Of these, 1 is honest, and the rest are malicious (so they give incorrect state chains).
    • Some number (up to 20) phase 2 challengers for layer i publish SNARK proofs that refute all of the 19 malicious challengers. This requires at most one SNARK proof for each malicious challenger, and they can be computed in parallel (a valid phase 2 challenge must refute every challenge, leaving at most one).
    • Since no one can refute the honest phase 1 challenger, all valid challenges must agree on the correct state — there can be no phase 3.

In the interactive version they do need extra computation, since they need to commit to the computation transcript. In the non-interactive case, the commitment is only to the final (good) state, so there’s 0 overhead for the computation itself.

It does need to be synced, but it actually shouldn’t be in the blocks (this is also true for interactive fraud proofs). The reason is that our blocks don’t form a chain, so the state-chain is conditioned on the layer hash.

In terms of who to trust, you download the state chains from your neighbors, then if there is an inconsistency you wait a layer to see if any of them are challenged.

8

If there’s a magical entity that indeed computed all these SNARKs then we’re secure against malicious adversaries (though this can be false in practice in case the SNARK uses non-conservative algebraic assumptions and/or non-conservative security parameters to push down the concrete complexity). Since the magical entity doesn’t exist, we need rational entities to be incentivized to perform this highly demanding work (the cost is supposed to be covered in a way that makes sense over the long term), so we end up with an incentive-incompatible protocol, whereas the interactive alternative is easily incentive-compatible.

There’s no DoS, the rollup state and the liveness remain uninterrupted unless a fraud proof succeeds. The only effect of the repeated challenges is that the adversary is losing money per challenge.

It’s longer and much more costly.

I looked now at the previous forum thread and your only complaint re the interactive proof was about the way it handles “very long dishonest majority period” (it handles it pleasantly, though you came up with a reserve pool of money that’s in fact unworkable). Now when you came up with non-interactive optimistic rollup, you neglect the “very long ishonest majority” reversal issue (this issue is far worse with non-interactive optimistic rollup compared to either non-interactive validity rollup or interactive optimistic rollup).

Curious, now it became 20 challengers, who’s paying for all of this? Why did you say “at most” and not “at least” ? Unlike the hare where this number is 40, here uou suggested 20, presumably because you were concerned that 40 is too costly and not worth the extra “security” (it’s only secure if rational actors want to do it, which is unconvincing to say the least), but your statement “there can be no phase 3” depends on this “security”. As mentioned, the most reasonable variant is to allow a single challenger.

Please re-read, the interactive version doesn’t need executors to perform any extra computation, jexactly like the non-interactive optimistic rollup. I remind you that as we discussed a while ago (and you may have forgotten), the interactive version can be better with an extra round (layer) for commit-reveal in order tp protect the reward scheme against freeloading, and exactly the same is true for non-interactive optimistic rollup.

I don’t see your point, there’s full ordering of the history in the content blocks.
If you want to rely on tortoise beacon and epoch-wide sampling then that’s really bad here because the sampled challengers are supposed to act only if there’s fraud in the current timeframe (it’s a huge systemic risk, the security would rely on actors who aren’t supposed to do anything whatsoever in the happy flow, so it’s very likely that they will opt to freeload and do nothing whatsoever always).

The simple problem is that there’s nothing to challenge, you’re just a newcomer and you have one bad neighbor. If the security that you propose now relies on honest majority among your immedaite neighbors, then that’s a far cry from “security against malicious adversaries” that you proclaimed above.