search

a16z / jolt

The simplest and most extensible zkVM. Fast and fully open source from a16z crypto and friends. ⚡
https://jolt.a16zcrypto.com
MIT License
578 stars 105 forks source link

EVM Friendly Transcript #328

Open sragss opened 2 months ago

sragss commented 2 months ago

One of the quickest routes to on-chain verification is to switch the commitment scheme to Zeromorph then verify those proofs directly on-chain. Currently our Fiat-shamir transcript uses the Merlin library which depends on the Strobe RNG. We'll want to swap this to Keccak to support cheaper EVM verification using the Keccak precompiles.

The Honk on-chain verifier has an example of the transcript written in solidity.

Steps: 1) Make the transcript generic over the hash function 2) Support keccak and poseidon2 3) Reduce count and size of domain separators (in Merlin these are referred to as 'labels') 4) Integration test for parity with EVM version

MatteoMer commented 2 months ago

I'd be happy to work on that!

To make sure I understand correctly the idea is to completely remove merlin and write jolt own implementation of the transcript?

Also, I'm not sure I understand exactly the 3rd step, do you mean removing the number of append_message in the code?

I think I'll just work to be 1/1 with the EVM version 😄

Maddiaa0 commented 2 months ago

Looking into Merlin it appears that it is already using keccak as its hash function? (based on https://github.com/dalek-cryptography/merlin/blob/53535f32e6d6de421372d67f56176af0c0f55fd7/src/strobe.rs#L97)

sragss commented 2 months ago

That would be great @MatteoMer!

Good point @Maddiaa0 – new step 1 would be to determine if RustCrypto/sponges keccak::f1600(...) (used by Merlin) is the same as the EVM's Keccak256 and determine the additional augmentations done by Merlin.

We'd like to append the same values to transcript in Rust and EVM and then sample the same bytes of randomness.

If we can do this and keep Merlin, great. If not, let's write our own.

MatteoMer commented 1 month ago

Haven't took time to dive into determine if both keccak implementations are the same yet (will do soon)

But came across this recently: https://github.com/arkworks-rs/nimue (an hash-agnostic fiat-shamir library), and while I don't think it's ready for use yet, I think it's interesting to put it here, since in the original ticket, you were talking about being generic

PatStiles commented 3 weeks ago

@moodlezoup Interested in taking this on!

aleph-v commented 1 week ago

I just added changes relevant to this in https://github.com/a16z/jolt/pull/402 and will be following up with the onchain transcript with integration tests.

PatStiles commented 1 week ago

Hey @aleph-v Is your plan to finish the on chain verifier?