# Trustless Uniswap Oracles via ZK (Axiom)

We propose to build general ZK oracles on top of Uniswap v2 or v3 pools which allow for **arbitrary** time weighting, median or volatility oracles, or outlier filtering. These oracles are trustless and **checkpoint-free** and are made possible by using Axiom's ZK proof technology to read and process historical state from Ethereum. We believe that using oracles of this form can reduce the risk of TWAP oracle manipulation and increase usage of trustless Uniswap-based oracles in downstream DeFi applications.

We propose to build trustless oracles of two types:
* **Checkpoint-free Uniswap v2 and v3 TWAP:** Atomic computation of the Uniswap v2 or v3 TWAP between _arbitrary_ historical blocks. Our implementation of this removes checkpointing for v2 and the caching overhead in v3.
* **Arbitrary Uniswap oracles:** Computation of richer oracles based on historic Uniswap prices. Example oracles include:
* Time-weighted median or windsor-ized oracles between any two historical blocks.
* Exponentially weighted moving average price between any two historical blocks.
* Realized volatility between any two historical blocks.

**About Axiom:** Axiom is a ZK coprocessor for Ethereum which provides smart contracts trustless access to on-chain data and expressive compute over it. Axiom augments the capabilities of the EVM, just like GPUs do for CPUs today. Smart contract applications can use Axiom to trustlessly import historical data and verifiably evaluate functions on top of it. With this new capability, we hope to enable richer and more expressive trust-minimized decentralized applications.

## Scope of Work, Milestones, and Grant Allocation

We have divided the grant into three phases, corresponding to complexity of oracle. We are asking for a grant allocation of $20K for Phase 1 at present. If Phase 1 is completed to Uniswap's satisfaction, we would like to discuss further exploration and going to production in Phases 2 and 3.

#### Phase 1 (Present - March 15)

The goal of Phase 1 will be to technically derisk the use of Axiom to build ZK oracles on top of Uniswap v2 and v3 by producing prototypes of the checkpoint-free v2 and v3 TWAP above. These smart contracts and circuits will be a combination of standard Axiom contracts/circuits and custom integrations built for Uniswap. In particular, Axiom will deliver prototypes of:
* SNARK circuits for TWAP computation.
* Smart contract to verify SNARKs and access TWAPs.
* Coordinator node to generate and submit proofs.

Axiom will also assist in marketing and explaining the integration, including:
* Public blog post and co-marketing.
* Detailed technical explanation of circuit architecture.
* Detailed analysis of security guarantees.

We are asking for $20K for this proof-of-concept milestone, to be paid upon grant approval.

#### Phase 2 (March 15 - May 15)

In Phase 2, Axiom will derisk general ZK oracles on top of Uniswap. This includes prototypes of:
* SNARK circuits for median, EMA, and volatility oracles between arbitrary blocks.
* Smart contracts to verify SNARKs and access oracle values.
* Coordinator node to generate and submit proofs.

These prototypes will give precise latencies and gas costs which can be expected to hold in production. Axiom will also produce:
* A technical blogpost explaining these protoypes.
* Documentation to explain this integration.

#### Phase 3 (May 15 - July 15)

In Phase 3, Axiom will deliver polished versions of selected oracles in a public-facing way which are ready for mainnet audit. This includes:
* Deployment of system on Ethereum testnet.
* Public and clearly documented open-source repos for smart contracts and SNARK circuits.
* Axiom-provided coordinator running live on Ethereum testnet.

Axiom will also assist in preparing the system for mainnet deployment, including:
* Coordination with Uniswap for ZK circuit and smart contract audits
* Operating provers to fulfill on-chain queries
* Providing an open-source implementation of a prover for backup proof generation.

Depending on demand, Axiom is open to maintaining SLAs on latency and uptime for proving services.

## Team

The Axiom team consists of the two co-founders, and this grant proposal will be built on top of Axiom. This includes ZK circuits written by Axiom for:
* Ethereum storage proofs
* Trustlessly reading from the account and storage trie in ZK.
* Ethereum block header proofs
* Decommitting the chain of block header hashes in ZK to trustlessly prove past block headers from knowledge of a recent block hash.
* Recursive verification and aggregation of ZK proofs
* Verifying multiple ZK proofs within a new ZK proof to make them viable to verify on-chain

Our team has extensive background in ZK and blockchain infrastructure:
* Yi Sun
* Co-author of ZK circuits for ECDSA ([circom-ecdsa](https://github.com/0xPARC/circom-ecdsa)), elliptic curve pairings ([circom-pairing](https://github.com/yi-sun/circom-pairing)), and Ethereum on-chain data ([zk-attestor](https://github.com/yi-sun/zk-attestor)). Advisor to Gauntlet and Scroll and Assistant Professor in Statistics at UChicago.
* Jonathan Wang
* Co-author of ZK circuits for elliptic curve pairings ([circom-pairing](https://github.com/yi-sun/circom-pairing)). PhD in number theory from UChicago and elliptic curve math specialist.

## Appendix: Protocol Spec

### Uniswap v2 TWAP

Uniswap v2 maintains variables in `UniswapV2Pair`. For `X` in `{0, 1}`, the variable `priceXCumulativeLast` after event `n + 1` is the cumulative sum of

(reserveY_n / reserveX_n) * timeElapsed_n

Here `(reserveY / reserveX)` is the price of `X` in units of terms of `Y`, and:
* `reserveY_n` is the reserve of asset `Y != X` after event `n`
* `reserveX_n` is the reserve of asset `X` after event `n`
* `timeElapsed_n` is the block timestamp difference between events `n` and `n + 1`

To compute TWAP of `X` between block numbers `k1 < k2`, we compute

(currentCumulativePrice(k2) - currentCumulativePrice(k1)) / (blockTimestamp(k2) - blockTimestamp(k1))

where

def currentCumulativePrice(k):
    increment = uint(reserveX(k) / reserveY(k)) * (blockTimestamp(k) - blockTimestampLast(k))
    return priceXCumulativeLast(k) + increment

To prove this in Axiom, we must fetch the following slots from `UniswapV2Pair`:
* `reserve0(k1)`, `reserve0(k2)`
* `reserve1(k1)`, `reserve1(k2)`
* `blockTimestampLast(k1)`, `blockTimestampLast(k2)`
* `priceXCumulativeLast(k1)`, `priceXCumulativeLast(k2)`

and the following header fields
* `blockTimestamp(k1)`, `blockTimestamp(k2)`

### Uniswap v3 TWAP

We can do a similar operation to Uniswap v2 TWAP to compute Uniswap v3 TWAP for cases where checkpoints have expired from the cache. In this case we offer computations of two quantities. Define the tick to be
$$
t = \lfloor \log_{\sqrt{1.0001}}(\sqrt{P}) \rfloor
$$ and define the inverse liquidity to be $1/L$. Uniswap v3 stores the time weighted accumulators of `tick * time` and `(1/L) * time`. The tick TWAP gives a geometric mean TWAP of discretized prices, and we may also compute the TWAP of seconds weighted inverse liquidity.

### Uniswap v2 and v3: Arbitrary weighted-time oracles (EMA, etc.)

To compute oracles not supported by explicit accumulators in the Uniswap v2 or v3 protocols, we apply an **accumulation** function to a per-block function within Axiom. To compute this between blocks `k1 < k2`, we use Axiom to read:
* For block number `k in [k1, k2)`, read the price of Token 0, called `p_k`
* in `UniswapV2Pair`: `reserve1(k) / reserve0(k)`
* in `UniswapV3Pool`: `slot0(k).sqrtPriceX96 ** 2` (adjusted for fixed point)
* Compute an arbitrary oracle function of `p_k`:
* for median, compute:
* `median over k in [k1, k2) of p_k`
* for EMA with parameter `alpha`, compute:
* `sum over k in [k1, k2) of p_k alpha^{k2 - k - 1}`
* This requires fixed point arithmetic
* for arbitrary weighted-time average with weights `alpha_k`, compute:
* `sum over k in [k1, k2) of alpha_k * p_k`
* for sample volatility, compute:
* `n/(n-1) * (\sum_k p_k^2 - (\sum_k p_k)^2 / n^2)`

This requires:
* storage proofs for slots for either `reserve0(k)` and `reserve1(k)` or `slot0(k)`
* fixed point arithmetic for median, EMA, or average computations