Open CeciliaZ030 opened 1 week ago
I still think x=hash(C1,C2)
, which is used in the formula's of both dankrad and vitalik (and what we also did for the PSE circuits: https://github.com/taikoxyz/zkevm-circuits/issues/37#issuecomment-1335969679 and checked by Aleksei/Mario for correctness).
His method predates the actual presence of ZkVM, so it's operating directly with Plonk's public input commitment. However in ZkVM we don't have access to the public input commitment but we we can achieve the same purpose with simplification:
Looking at evaluate_polynomial_in_evaluation_form
: https://github.com/grandinetech/rust-kzg/blob/1c9f4435a32f5ad7ffb73e299a33b212340fe86b/mcl/kzg/src/eip_4844.rs#L243. It does seem to use the barycentric formula, so I think this is the most efficient we can get it and also the one we did for the PSE circuits, so should be good!
(note that the point evaluation precompile will still be disable in L2 due to high cost)
Do you know the number of cycles of the point precompile for c-kzg vs rust-kzg? We only have to do point precompile calculations on the revm side.
We may also want to use sha256 instead of keccak for the hashing of the data, if it saves some cycles (sha256 should be a bit more efficient, but we'll have to see about that I guess).
I still think
x=hash(C1,C2)
, which is used in the formula's of both dankrad and vitalik (and what we also did for the PSE circuits: taikoxyz/zkevm-circuits#37 (comment) and checked by Aleksei/Mario for correctness).
It's hard to obtain C1 tho, in the ZkVM case C1 is the implicit commit that the proof system is using to commit ALL memory. It's not like in Halo2 u can init a column and force it to be zero in all unused rows. The ZkVM guest code literally init blob: Vec<u8>
, and this memory allocation is written somewhere of the STARK circuit along with other memory traces, how do u get the C1 which commit all these?
Do you know the number of cycles of the point precompile for c-kzg vs rust-kzg? We only have to do point precompile calculations on the revm side.
Well @smtmfft says 200-300M for c-kzg in Risc0 but i can't get it compiled in Sp1 so idk.
We may also want to use sha256 instead of keccak for the hashing of the data, if it saves some cycles (sha256 should be a bit more efficient, but we'll have to see about that I guess).
We should use which ever that's the fastest, sp1 has both sha256 and keccak so we have see cycles and the actually time of those syscall.
I still think
x=hash(C1,C2)
, which is used in the formula's of both dankrad and vitalik (and what we also did for the PSE circuits: taikoxyz/zkevm-circuits#37 (comment) and checked by Aleksei/Mario for correctness).It's hard to obtain C1 tho, in the ZkVM case C1 is the implicit commit that the proof system is using to commit ALL memory. It's not like in Halo2 u can init a column and force it to be zero in all unused rows. The ZkVM guest code literally init
blob: Vec<u8>
, and this memory allocation is written somewhere of the STARK circuit along with other memory traces, how do u get the C1 which commit all these?
C1 = keccak/sha256 hash of the blobdata C2 = kzg commitment of the blobdata (free from ethereum)
No need to use any built in commitment of the blobdata inside the zkVM circuit itself, the hash is also a commitment we can just calculate inside the VM.
Do you know the number of cycles of the point precompile for c-kzg vs rust-kzg? We only have to do point precompile calculations on the revm side.
Well @smtmfft says 200-300M for c-kzg in Risc0 but i can't get it compiled in Sp1 so idk.
That's for the calculation of the kzg commitment as far as I know, not the point precompile.
We may also want to use sha256 instead of keccak for the hashing of the data, if it saves some cycles (sha256 should be a bit more efficient, but we'll have to see about that I guess).
We should use which ever that's the fastest, sp1 has both sha256 and keccak so we have see cycles and the actually time of those syscall.
sha256 you would expect to be faster, but do indeed need to measure it to make sure.
👌
C1 = keccak/sha256 hash of the blobdata
Yes, you can do this if it's cheap enough to evaluate keccak/sha256 inside your proof system.
It's not safe to leave out C1: it's possible to find another polynomial f'(x) that evaluates to f'(x)=f(x)=y and that would pass the check.
Yes, you can do this if it's cheap enough to evaluate keccak/sha256 inside your proof system.
It's not safe to leave out C1: it's possible to find another polynomial f'(x) that evaluates to f'(x)=f(x)=y and that would pass the check.
Thanks for replying @dankrad ! In this case, i guess we're replacing a poly commitment of blob (i.e. f(x)) with a hash commitment, so the security assumption comes from the hash function, then the malleability of f(x) is out of picture
Background
We have to prove that Rollup's data availability is from a given blob with KZG commitment
This means that the ZkVM guest has to go through the computation that generates the
BlobHash
:However this function
blob_to_kzg_commitment_rust
whichThe group operation is too costly, and even compiling kzg libraries into RiscV is challenging due to C bindings.
Data
It's impractical to run any of the KZG library with ZkVM, even when it compiles it takes millions of cycles. c-kzg in Risc0 spends 200-300M, while rust-kzg benchmarks as following with
zkcrypto
backend in Sp1:Solution: Simpilified Proof of Equivalence with Fiat Input
Aligned Version
https://notes.ethereum.org/@dankrad/kzg_commitments_in_proofs
Non-aligned Version with Fiat Input
While our situation falls into the case of non-aligned fields, because there's no way to prove the same y = f(x) in ZkVM's runtime trace and underlying commitment scheme. Instead we can use a simplified variant of the "Fiat Input Method" proposed by @dankrad. In short, his method assumes a ZkVM field >> Bls381 filed, and he encodes the blob elements in the ZkVM commitment polynomial g(x) with g(x0) = b0, g(x1) = b1, ..., g(x4096) = b4096 (note that there are 4096 field elements per blob). Then use the ZkVM proof to show that g(x) is valid with [b1, ..., b4096] and the commitment E as public input. With some tweaks, The scheme let the verifier compute that g(x) evaluates to 0 everywhere else than the first 4096 roots of unity.
Non-aligned Simplification with ZkVM
His method predates the actual presence of ZkVM, so it's operating directly with Plonk's public input commitment. However in ZkVM we don't have access to the public input commitment but we we can achieve the same purpose with simplification:
We argue that it's a variation of the Fiat Input method because it has similar cost evaluation: 1) non-aligned field operations 2) one single hash. The benchmark is the following:
Implimentation
Spam policy