EIP-4844: KZG verification acceleration via proof of equivalence

[mratsim]

Describe the feature request

KZG verification is too slow to use without accelerator/coprocessor/precompile/circuit if we just compile https://github.com/ethereum/c-kzg-4844 in a zkVM.

One way to solve this is by using the "proof-of-equivalence" technique mentioned in:

• https://notes.ethereum.org/@vbuterin/proto_danksharding_faq#Moderate-approach-works-with-any-ZK-SNARK
• https://notes.ethereum.org/@dankrad/kzg_commitments_in_proofs
• https://ethresear.ch/t/easy-proof-of-equivalence-between-multiple-polynomial-commitment-schemes-to-the-same-data/8188

For zkVMs, we should like use Poseidon2 on top of BabyBear (assuming its the prover field) as the hash function for efficiency.

This is accelerated:

• for Risc0
  • https://github.com/risc0/risc0/blob/2deb83a/risc0/zkp/src/core/hash/poseidon2/mod.rs#L41-L62
  • https://github.com/risc0/risc0/blob/2deb83a/risc0/sys/kernels/zkp/cuda/poseidon2.cu
  • https://github.com/risc0/risc0/blob/2deb83a/risc0/sys/kernels/zkp/metal/poseidon.metal
• for SP1 & Plonky3
  • https://github.com/succinctlabs/sp1/blob/ef6887b/core/src/utils/prove.rs#L237-L261
  • Poseidon2 speedups Plonky3/Plonky3#257
• Powdr / Polygon PIL
  • Goldilocks-only, missing BabyBear: https://github.com/powdr-labs/powdr/blob/f66d7a9/std/hash/poseidon_gl.asm

zkEVM

In the ZK-EVM, the equivalent circuit is: taikoxyz/zkevm-circuits#106

[mratsim]

Another quick-win we might be able to do is hardcoding the proof for loading the trusted setup since it will never ever change.

See @smtmfft perf report for

    let mut input = [0; 4096*32];
    // env::read_slice(&mut input);
    let (g1, g2) = parse_kzg_trusted_setup(&KZG_TRUST_SETUP).unwrap();
    // TODO: do something with the input

    // uncomment any of following line, you will see the error message
    // undefined symbol: malloc
    let kzg_settings = KzgSettings::load_trusted_setup(&g1.0, &g2.0).unwrap();
    let kzg_commit = KzgCommitment::blob_to_kzg_commitment(&input.into(), &kzg_settings).unwrap();
    let versioned_hash = kzg_to_versioned_hash(