Scalable trust-minimized order book based on recursive ZkVM rollup

[Oleg Andreev]

Hello,

I'd like to present an early draft of an idea how we could use ZkVM stateless validation as a feature to enable trust-minimized verification of centralized ledgers and implement non-custodial matching engines that give us both performance, security and confidentiality.

TL;DR: Instead of implementing custom centralized "trade chain" both in normal software and in an expensive L1 smart contract, we reuse the same ZkVM format that permits stateless verification and invoke "recursive" verification from within outer ZkVM chain, reusing conventional implementation in Rust and having none of virtualization overhead. The cost is that of verifying one more regular transaction + a checking a few hashes along some merkle trees such as utreexo snapshots.

Same article in the repo: https://github.com/stellar/slingshot/issues/495

# ZkVM Rollup

## Motivation

Blockchains are great at trust-minimization at a cost of performance, while centralized trading systems are more scalable and performant. For instance, offers in the order book need to be updated rapidly and always ready to be consumed by any of many players involved.

Several Ethereum projects explored schemes known as **rollups**, where a central party organizes the marketplace and commits to its rules. Users' funds are locked up with an on-chain contract that knows the rules and can check violation of them. In case of a violation, any user can submit a proof of it and begin the process of returning their deposit.

The transcript of the game, or **trade chain**, is very similar to a blockchain: individually signed transactions that modify shared state. Except the consensus is operated by centralized signer and their actions can be disputed on a higher-order blockchain (**main chain**).

## Kinds of violations

There are three kinds of violations to deal with in a rollup system: 

1. censorship,

2. invalid transition,

3. fork of the state.

**Censorship** is mitigated by the ability to withdraw funds directly from the smart contract at the latest state of the trade chain. In such case, the withdrawal is timelocked to ensure that the funds were not consumed from that account.

**Invalid transaction attack** is mitigated by being able to "bisect" to the point in the trade chain history where violation took place. When such location is proven, all further transactions are ignored (rolled back). This should not hurt traders who validate trade chain directly and halt trading when violation is detected.

**Fork attack** occurs when the operator signs two incompatible, but independently valid histories and it's impossible to objectively prove which one is the correct one. One mitigation is to commit the state of the history early and often, as frequent as every block of the host chain. This reduces the window of profit opportunity: when an operator could make a risky bet, lose, and attempt to roll back the chain by forking it to the point before the bet was placed. 

To make such attacks expensive, operator places a bond on host chain that gets destroyed in case operator forks the chain. The size of the bond is bounded from below by the trade volume between the commits and above by the cost of capital vis-a-vis the transaction fees collected by the operator. Also, the attack scope is limited to a one-time event, after which everyone stops trusting the operator and looks for recourse in the legal framework outside the blockchain.

## Kinds of rollups

**Optimistic Rollup:** snapshots of the trade chain state are optimistically committed to the main chain and can be challenged within certain timeframe. All funds are controlled by a smart contract on main chain that is capable of checking the above violations. In case of Ethereum, a EVM bytecode needs to implement all rules of the trade chain so it can execute the minimal state transition and check whether it's valid (no need to verify the entire chain).

**ZK Rollup:** snapshots of the trade chain state are committed to the main chain with the zkSNARK proof of correct or incorrect evaluation. In Ethereum, a EVM smart contract must implement SNARK verification logic. Important difference is that SNARK could pack up verification of all transactions between the checkpoints and apply updates unconditionally, without timeouts to watch for violations. However, contest mechanism is still required to be able to prove fork.

## ZkVM rollup

In both cases above, the rules of the trade chain must be encoded using the smart contract language: either directly (optimistic rollup), or indirectly through SNARK circuit (zkrollup).

ZkVM offers a third opportunity: ZkVM may implement one or two instructions for recursive validation of embedded ZkVM transactions. Instead of re-implementing ZkVM in its own language, we could simply instantiate another VM instance and run a trade chain transaction through it. This is possible because ZkVM has a well-defined compact state, stateless tx validation that is sufficiently lightweight for a wide range of "trade chain" applications. 

The cost of contesting a violation of a ZkVM trade chain is simply a cost of one more ZkVM transaction: it is easy to account for, it does not require new tooling for the language and allows keeping the smart contract language non-generic and high-level, unlike EVM.

EVM permits implementation of arbitrary trade chain state machines, while ZkVM would only be able to validate the ZkVM rules. How do we implement custom trade chain logic then? The answer is: we can do it using both the mainchain and trade chain contracts. All the individual or bilateral rules could be specified in the trade chain contracts, while global rules (such as "offers must be fullfilled in correct order") could be verified for violation in the outer, main chain contract.

## Trading engine example

### Terminology

Parties to the protocol are: one **operator** and variable number of **traders**. Operator could be secured with a multi-signature / multi-party setup, but from the perspective of the traders it is still a single logical entity.

Protocol is executed over a **main chain** and a **trade chain**. Trade chain is timestamped by the **operator** on the **main chain**, where all the deposited funds and a trade chain state are secured in a contract. Contract implements the key part of the protocol: enabling transition from one state to another and dispute of the invalid or conflicting transitions.

### Roles

Operator coordinates deposit of traders' funds in a global smart contract on main chain.

Traders can deposit and withdraw funds.

Traders place orders and pay required fee to the operator. Operator includes transactions that pay agreed-upon fees.

It is possible to have different confidential fee agreements for different traders, depending on volume/load/liquidity.

Operator matches orders in correct order (better price first) and makes regular checkpoints.

Traders watch for correctness and submit dispute proofs on main chain in case a fork or invalid tx is detected.

Traders also halt immediately when violation is detected.

Note: some of the following actions, in their entirety, or portions of them, could be implemented once and for all as a ZkVM facility. Other parts are specific to the rules of trade chain and must be specified as custom ZkVM contract clauses.

### Action 1: deposit

Operator merges the existing contract with the deposited funds, making them available on the trade chain. We need an instruction to "import" asset to an embedded chain.

### Action 2: withdrawal

Trader may request a withdrawal of funds from the trade chain. This request necessarily must be delayed to make sure there was not uncommitted transaction that spends the same funds. At the same time, the request must 

### Action 3: forced withdrawal

Trader may withdraw funds w/o cooperation of the operator. This is a slower process, but a necessary insurance against censorship. 

1. The withdrawal request is done against the global contract that holds all the deposits of the tradechain. 

2. The request is delayed to make sure there was not uncommitted transaction that spends the same funds. 

3. At the same time, the request forces the operator to mark the utxo as unspendable: if they were to allow transaction spending it, they'd be violating the rules.

### Action 3: order placement

Within the trade chain, a passive asset can be locked in an "order contract" that has a cleartext price and provision to automatically match against counter-offer with compatible price.

### Action 4: order matching

Operator keeps track of the non-matched orders sorted by price. As new orders overlapping with the order book come in, they are immediately matched and new transaction is recorded on trade chain.

Every matched trade commits to a structure of the order book which is used in the main chain contract to check for violations such as skipping over an order (see below).

### Action 5: checkpoint

Operator periodically bundles transactions in a block that's committed into the "checkpoint" on main chain: transition of the main contract to a new state. Checkpoint transition also includes newly deposited funds that get reflected in the utxo set of the trade chain.

### Action 6: withdrawal dispute

When the trader initiates force-withdrawal, they may incorrectly claim a utxo that they have already spent. In such case, within a timeout (several main chain blocks), a spending trade chain transaction could be presented that consumes that utxo. 

It does not matter whether it is spent in a correct trade chain because only the owner of the utxo could claim the withdrawal, and if they do so twice, they are clearly at fault and the higher-order request can be cancelled.

Note: this requires careful domain-separation of signatures and contract IDs in order to work correctly across arbitrary depth of inception.

### Action 7: invalid checkpoint dispute

Every checkpoint update by the operator is an opportunity to bring an invalid state:

1. invalid utreexo updates

2. invalid transactions

3. allowing spending utxos already destroyed during withdrawal

4. violating custom rules, e.g. regarding correct ordering of bids/asks.

When a proof of violation is presented, the contract enters the locked mode at a specified state, which can only be backtracked to an even earlier invalid state, but not further.

### Action 8: forked state dispute

Similar to the invalid state, this is a presentation of the forked state in-between checkpoints that advances the checkpoint to the block before the fork. 

## Required modifications to ZkVM

The above protocol requires additions to the ZkVM instruction set and VM semantics to support nested chain validation and fraud proofs.

* Generic merkle proof computation support

* Nested tx, block and utreexo verification

* Block signer support for flexible transactions (for resolving commutative multiuser accesses to shared contracts)

* Correct domain-separation of the tx IDs, contract IDs, tx signatures between chains. We probably need to keep asset IDs the same, but issuances domain-separated between chain IDs.

[Leigh McCulloch]

Hi Oleg,

I have a few questions, please bear with me if some are naive.

Are the three chains discussed the Stellar network (main on-chain L1), trade chain, then embedded chain? Is the main chain the Stellar network or ZkVM?

Would the operator take custody of the assets when deposited to the trade chain?

What would prevent disputes from negatively impacting other participants?

What's missing from Stellar to support this?

Leigh