litevm: "Stateless" Token Transfers on a HyperVM

[patrick-ogrady]

Context: https://twitter.com/_patrickogrady/status/1672354822568419328
TODOs: #225

[furkan-ux]

"proofs required per tx can be quite large (on the order of KBs in large trees). You trade network bandwidth for less validator state management."

I think if the appropriate (zk-friendly) hashing algorithms are used for the merkle tree, instead of providing the full merkle proof, it can be possible to provide the zero-knowledge proof of knowing the appropiate path, which would result in a significant decrase in the size. Also this might enable batching just like a rollup. As an idea I am leaving this here.

[furkan-ux]

Surely! I just wrote this to test this idea. It is written in circom2 and uses Poseidon hashing (faster than MiMC7 and more secure).

You can find the circuit, input, and the proof files here:
https://github.com/furkan-ux/zkmt/tree/main

It turns out that for a tree with a depth of 32, proof size decreases from 3.03KB -> 993B. Depending on the tree size, the efficiency will increase as well.

A very similar setup is used in Tornado Cash with the MiMC7 in fiestel:
https://berkeley-defi.github.io/assets/material/Tornado%20Cash%20Whitepaper.pdf
More info about Poseidon:
https://eprint.iacr.org/2019/458.pdf

[furkan-ux]

By the way, we are currently building this same methodology on HyperSDK (it was built as a contract in evm before) in EtraPay (ofc with tons of other primitives for privacy), as I wrote in this tweet: https://twitter.com/furkanrypt/status/1671442489775882241 and we are happy to discuss this further.

[patrick-ogrady]

Thanks for sharing! Will dig into this over the next few days...

Would be very curious to do some benchmarking as well (both on proving and verifying). Neither would be done in the verification loop of a block, so we could tolerate some delay on either...especially proof gen.

The extension to your example (what we are digging into next) would be to prove multiple values at once so that a tx would just provide a single proof for all values it will touch (which should dedup overlapping nodes). If your link already does that, nvm lol (haven't looked to close yet).

[patrick-ogrady]

Very very happy to review any ZK packages you propose for general use on the HyperSDK.

One thing I'd like to see much more of in this repo for sure.

[StephenButtolph]

Hmmm I'm not sure I really understand the idea yet. What would the ZK proof be proving?

Currently the proofs don't just provide the inclusion / exclusion proofs for the key -> value pair. They provide the information needed to perform state modifications to the keys.

The difference here enables us to actually construct the new merkle trie at the end of validating the block. Constructing the merkle trie during verification is needed to enable concurrent proof submissions.

If we were to remove the concurrent proof submission support, I think we'd probably need to move the inclusion / exclusion proofs into the block builder (which quickly results in just becoming a ZK rollup imo)... I.e. if the block builder is able to provide the inclusion / exclusion proofs as they build the block, they should probably just produce a single proof that Execution(parent merkle root, txs) -> new merkle root and skip the inclusion / exclusion proofs.

Not sure if I missed some nuance tho...