Taiga post-ordering execution and verification

Protocol Design
1

Taiga shielded state transitions are computed prior to ordering (typically client-side or offline) and then verified (via SNARKs) post-ordering. This is primarily because shielded state is not publicly visible, but also this state transition model can provide some scalability and security benefits since the state transition only needs to be verified and not re-computed.

However, at least sometimes it is not possible to compute the state transition before ordering. Some example applications might include AMMs or bridges. The primary problems happen when:

  1. The state transition depends on the result of ordering, and/or
  2. The state transition updates globally addressable shared state

For example, if we have a public global counter which shielded state updates can increment or decrement, then each shielded execution cannot individually update this state because the prior state (from a previous block or previous transaction within the same block) would not have been available at execution time (pre-ordering).

So the orderer must be able to compute a post-ordering execution with input state determined only once ordering is finalized, and apply the final state once computed. The input and output state and the computation must be public, since it is not known in advance who the orderer might be. The requirement to update globally addressable shared state is also different than the shielded execution’s state model. Finally, the last requirement is rollup efficiency, requiring that the post-ordering execution be circuit friendly.

There are several potential options for the post-ordering execution model, where the orderer runs a computation and:

  1. replicates across other {validators, full nodes} in a transparent execution model that can read/write addressable state
  2. proves its validity, in a transparent (circuit) execution model that can read/write addressable state
  3. proves its validity in exactly the shielded execution model, but with special shielded state representation of global addresses

I think (1) is undesirable because of the complexity of adding an entire VM (or similar execution environment) solely to compute post-ordering execution.

In some ways (3) is theoretically ideal, since it would depart the least from the existing shielded execution model and thus require the fewest modifications and additions. However, it may have some practical problems: shielded predicates take 2 inputs (which may be insufficient) and also the latency of proving in the shielded environment may be more than acceptable for an orderer.

The best option might be (2), where a slightly modified execution model (but still substantially similar) can be used. Predicates would have a different API signature (perhaps more inputs) and the Action circuit can be drastically simplified (no merkle tree, no VP commitments, etc) which should help latency substantially.

2 Likes
2

Can you go into more details as to why these to application types would be problematic? Specifically, If you have consensus rounds on demand, why is this an issue?

The way these are described reads like higher order commitments, requiring ordering and verification of the underlying transitions before a state transition containing the higher order commitment dependent on the outcome of an AMM or bridge update can be computed.

3

Yeah, fundamentally, the problem seems to be that if you have some globally addressable (and shared) state like a pool balance or escrow balance, you don’t want this to be held in regular Taiga shielded state (even if it’s made transparent by key reveal, etc) because then you have to deal with the fact that many tx within a block can be updating this state simultaneously, and if you try to distribute/shard this state into more places, then you have a global addressing problem because it’s not as simple to look up the current state. (At least this is my understanding)

There might be more direct examples where the input state simply doesn’t exist until after ordering (for example, something depends on the exact ordering of tx) but I’m not sure I know any natural examples of this.

1 Like
4

Insight from the transparent VM implementation track:

We assume to the VM, shielded Resources and (P)TXs are ByteString with limited amounts of introspection (like looking at the commitment and hints).
In addition to this, the VM can call Taiga, e.g. to generate commitments and nullifiers for shielded and transparent TXs.

Note: I’m not sure if we can (or need to) generate zk-proofs via Taiga from transparent TXs without shielding the Resources first, but maybe it doesn’t matter if we can just include 1k-proofs into a zk-chain.

Using the above and a plaintext executable of type tx -> tx + access to state of e.g. the consensus provider KVS, we can unify the transparent and shielded post ordering execution models.

This would be compatible with 1. or 2. since the state update could be performed by the VM in a replicated setting, or just have the proofs provided. Once we figure out how to do 3. we can add that as a special case.