# The state of client side zk research Feb 15th, 2023

## Epistemic status

- _Likely to contain errors in descriptions of schemes_
- _Pls think of this doc only as my view of the client proving research_

## The objective of this research

Build/Find a zero-knowledge proving system that has the following three properties

1. Can provide right-field arithmetic for any cryptosystem
2. Ease of proof accumulation
- Calling a smart contract method for every proof generated likely isn’t scalable. We can achieve verification scalability by batching multiple proofs into a single smart contract invocation.
3. Compute and bandwidth efficient proving
- We want the proving key size to be small and the proving itself to be fast

## Motivation to add ZK with non-elliptic-curve means

- There are mainly two reasons to favor proving systems that do not use elliptic curves
- Ease of right-field arithmetic
- Works with any cryptosystem regardless of the finite field
- Ease of recursion
- Proving and verification are done in the same field, making “proof verification inside another proof” relatively simpler. Whereas in a proving system using elliptic curves, a *cycle* of scalar and base fields is required for efficient recursion.

## Motivation to avoid FFTs

- FFTs require a certain structure to the field, and not every finite field of major cryptosystems (K256 ECDSA, P256 ECDSA) has such a structure.

- A counterargument can be made to embrace the need for FFTs by employing ECFFTs. However, the need for a sub-system is undesirable.

## SumCheck and ZK SumCheck

**SumCheck**

- Most proving systems that don’t require FFTs interpolate the polynomials over the boolean hypercube, and make claims using the sum-check protocol.

e.g. Spartan, Hyperplonk.

**ZK SumCheck**

- Most techniques to add zero knowledge to the sum-check protocol **require an oracle to the polynomial (i.e. a polynomial commitment scheme)** that is being summed.

- In [the Hyperplnok paper](https://eprint.iacr.org/2022/1355.pdf), there are various mentions of polynomial commitment schemes that can be used with the proving system. (Modified versions of FRI and KZG which work with multilinear polynomials, and a polynomial commitment scheme from [Orion](https://eprint.iacr.org/2022/1010).)

- Spartan uses a bulletproof-like polynomial commitment scheme to make sum check zk.

**Variants of ZK SumChecks that don’t require elliptic curves**

- FRI
- Orion PC

**Variants of ZK SumChecks that don’t require FFTs**

- TBD

## Possible constructions to obtain three properties

### HyperPlonk instantiated with FRI/Orion PC/etc

- HyperPlonk comes with custom gates and lookup tables, which allows efficient arithmetization. Elliptic curve operations are more efficient when expressed with custom gates than in R1CS ([TurboPlonk](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf)). And lookup tables are important to bring down circuit size and proving-time of Keccak.
- HyperPlonk has the possibility of having all three properties (universal right-field, ease of proof accumulation, and fast proving).
- Though we have never benchmarked Keccak w/ lookups so it’s still unknown if we can get fast enough proving.

### Spartan with Orion PC/FRI/etc
- A variant of Spartan using non-elliptic-curve means to obtain ZK.
This is easier to implement compared to the above construction since it’s an incremental improvement from spartan-ecdsa. Although since it’s based on R1CS, it’s unlikely that we can achieve fast Keccak proving in a *straightforward* manner.

## Possible pathways

Although Hyperplonk seems more forward-compatible than Spartan, we all need to consider the **speed of iteration** when deciding what to do next.

Also, it’s valuable to enumerate the known unknowns.

We have some sense of the nature of the following two properties we aim to achieve.

- Compute and bandwidth efficiency of proving (e.g. when the circuit size is 1~2MB and proving doesn’t require any large CRS, we can get <5s in-browser proving)
- Universal right-field (we better not rely on elliptic curves!)

**When it comes to accumulatability of proofs, we can only imagine what it could be like since we’ve never tried it.** Moreover, there are likely learnings from on-chain verification that is implied from developing proof accumulation.

**Therefore, developing the accumulation of Spartan proofs and at the same time shipping on-chain verification will likely give us good learnings in a relatively short time period.**

## A little bit on membership management

Zooming out a little, there is a need for a consensus on which _set_ to refer to for each membership proving instance. In Semaphore. the set is managed in a smart contract. However, for example in a set of NFT owners, we can refer **to the blockchain state itself**.

In order to prove your NFT ownership, you can provide a Merkle path of the smart contract storage slot in which your ETH address is stored, and prove knowledge of the private key which corresponds to the ETH address. The advantage of such construction is that it doesn’t require a set management smart contract, which leads to the simplification of the overall architecture. However, since the Ethereum state trie uses Keccak to hash nodes, such proving is only efficient if we have fast Keccak proving; another reason to favor that rich arithmetization for Hyperplonk.