Explore nesting STARK proofs inside SNARK proofs

[vimwitch]

For the build ordered tree circuit we need to scale to (ideally) hundreds of thousands of inputs. Right now we do this in a SNARK. This requires a long proving time because the proving time scales roughly linearly with number of operations. The advantage is a constant size proof/verification time suitable for onchain verification.

A STARK can make the same proof as a SNARK, but ~10x faster.

1

So we can generate a cheap STARK proof building the tree, then generate a SNARK proof using the STARK. The SNARK proof is then verified onchain.

--

This might be a viable approach for all our proofs. We can use a pattern where the user makes STARK proofs in browser and gives those proofs to a relay that wraps them in SNARKS before putting them onchain. The browser proving time would be reduced by ~10x at the cost of the relay having to do more computation. STARK proofs don't require a trusted setup or proving keys, so the user won't have to download large files.

STARK proofs are slightly larger than SNARK proofs, but small enough that moving proofs over http should be instant. We can use FFLONK SNARK proofs to wrap the STARK proofs. By doing so the system doesn't need a phase 2 trusted setup.

2

If the user is making STARK proofs we could potentially run a system configured like:

{
  EPOCH_TREE_ARITY: 2
  EPOCH_TREE_DEPTH: 32
  STATE_TREE_DEPTH: 32

  FIELD_COUNT: 200

  EPK_NONCE_PER_EPOCH: 10
}

This would store 5 kb of data for each user, and give each user 10 identities per epoch. As we expand the data storage we will eventually be able to build a ZK database for each user (abstracting the uint[] away).

--

I think we can yoink the engine out of this and build a recursive prover for generic STARK circuits. This would solidify the user/relay separation by shifting the cost of gas and compute to the relay. They're also looking for input on selecting a license.