search

0xPolygonZero / zk_evm

Apache License 2.0
85 stars 37 forks source link

Enables optional verification of Keccak tables #657

Closed sai-deng closed 1 month ago

sai-deng commented 1 month ago

Enables optional verification of Keccak tables in root circuits, saving unnecessary recursion time for empty Keccak tables. In my tests below, it reduces proving time by around 3 seconds when a segment contains no Keccak operations. #620 

RUST_LOG=info /Users/sdeng/.cargo/bin/cargo test --color=always -r --lib fixed_recursive_verifier::tests::test_segment_proof_generation_without_keccak --no-fail-fast --manifest-path /Users/sdeng/Project/0xPolygonZero/zk_evm/evm_arithmetization/Cargo.toml -- --ignored
[2024-09-25T04:47:30Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:47:30Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 100, byte_packing_len: 3, cpu_len: 512, keccak_len: 24, keccak_sponge_len: 1, logic_len: 8, memory_len: 67556 }, mem_before_len: 66049, mem_after_len: 66113
[2024-09-25T04:47:46Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:47:46Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 102, byte_packing_len: 7, cpu_len: 512, keccak_len: 96, keccak_sponge_len: 4, logic_len: 23, memory_len: 67773 }, mem_before_len: 66113, mem_after_len: 66126
[2024-09-25T04:48:01Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:48:01Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 83, byte_packing_len: 5, cpu_len: 512, keccak_len: 48, keccak_sponge_len: 2, logic_len: 14, memory_len: 67631 }, mem_before_len: 66126, mem_after_len: 66136
test fixed_recursive_verifier::tests::test_segment_proof_generation_without_keccak has been running for over 60 seconds
[2024-09-25T04:48:16Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:48:16Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 121, byte_packing_len: 2, cpu_len: 512, keccak_len: 0, keccak_sponge_len: 0, logic_len: 4, memory_len: 67684 }, mem_before_len: 66136, mem_after_len: 66173
[2024-09-25T04:48:28Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:48:28Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 98, byte_packing_len: 7, cpu_len: 512, keccak_len: 24, keccak_sponge_len: 1, logic_len: 8, memory_len: 67759 }, mem_before_len: 66173, mem_after_len: 66244
[2024-09-25T04:48:44Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:48:44Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 89, byte_packing_len: 2, cpu_len: 512, keccak_len: 24, keccak_sponge_len: 1, logic_len: 8, memory_len: 67871 }, mem_before_len: 66244, mem_after_len: 66251
[2024-09-25T04:49:00Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:49:00Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 115, byte_packing_len: 2, cpu_len: 512, keccak_len: 0, keccak_sponge_len: 0, logic_len: 4, memory_len: 67796 }, mem_before_len: 66251, mem_after_len: 66251
[2024-09-25T04:49:12Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:49:12Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 121, byte_packing_len: 4, cpu_len: 512, keccak_len: 0, keccak_sponge_len: 0, logic_len: 4, memory_len: 67807 }, mem_before_len: 66251, mem_after_len: 66257
[2024-09-25T04:49:23Z INFO  evm_arithmetization::generation] CPU trace padded to 512 cycles
[2024-09-25T04:49:23Z INFO  evm_arithmetization::witness::traces] Trace lengths (before padding): TraceCheckpoint { arithmetic_len: 90, byte_packing_len: 4, cpu_len: 512, keccak_len: 48, keccak_sponge_len: 2, logic_len: 13, memory_len: 67831 }, mem_before_len: 66257, mem_after_len: 0
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] 150.4260s to Segment Proof Generation
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 22.9381s to Create all recursive circuits
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 0.0000s to Generate dummy payload
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 15.6231s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 15.1803s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 15.4374s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 11.6834s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 16.2813s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 15.7072s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 11.7241s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 11.6348s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 14.2030s to Prove segment
[2024-09-25T04:49:37Z INFO  plonky2::util::timing] | 0.0034s to Verify segment proof
test fixed_recursive_verifier::tests::test_segment_proof_generation_without_keccak ... ok
sai-deng commented 1 month ago

@LindaGuiga Thanks for reviewing! I have synced the zkVM verifier with the prover.

In the next PR #690 , I will make the proofs optional in the proof table, but this requires changes on the Plonky2 side. This is also why I’m sending this PR for review before updating Plonky2.