e2e cycle reduction

[yczhangsjtu]

Breakdown of ZKVM verifier (after #54)

Total cycles: 1883948 (Fibonacci e2e with n=$2^{20}$)

• Read ZKVM proof variable from input: 482501 (25.6%)
• Before BaseFold verifier: 657479 (34.9%)
  • Tower proofs: 532010 (26.6%)
• BaseFold verifier: 743835 (39.5%)
  • Batching and first FRI round: 2047 * 100 (10.9%)
  • FRI rounds: 3740 * 100 (16.2%)
• After BaseFold verifier: 133 (0%)

Breakdown of BaseFold verifier

Using the test case generated by Fibonacci e2e.

Total cycles: 880000

• Read from witness stream data: 135231
• Before the query phase: 62161
• Query phase: approximately 684140
  • Beginning 817
  • Build round context (precompute values independent of query) 3065
  • Opening proofs 652305
    • Approximately 6530 * 100 loops, where for each loop
      • 514 Preparation
      • 2059 MMCS verify (Two input rounds)
        • Round 1 1601
          • Compute batching and reordering 1560
            • Approximately 36 * 40 loops
        • Round 2 440
      • 206 First Round Folding
      • 3734 FRI rounds (including MMCS ext verify)
      • 18 Finalizing
  • Sumcheck 16959
  • Final evals 10952

[yczhangsjtu]

Update (as done in #56):

FRI rounds reduced to 1709 * 100

This leads to the new breakdown:

Total cycles: 1682981 (Fibonacci e2e with $n=2^{20}$ )

• Read ZKVM proof variable from input: 482501 (28.6%)
• Before BaseFold verifier: 657479 (39%)
  • Tower proofs: 532010 (29.8%)
• BaseFold verifier: 542868 (32.2%)
  • Batching and first FRI round: 2047 * 100 (12.2%)
  • FRI rounds: 1709 * 100 (10.1%)
• After BaseFold verifier: 133 (0%)

[yczhangsjtu]

Breakdown of input variable reading:

• Read chip proofs: 361396 (21.5%)
• Read pcs proof: 120535 (7.1%)

[yczhangsjtu]

Update (handled in #55):

After flattening Vec<IOPProverMessage> and Vec<Vec<Vec<E>>>, read input cycles is reduced from 482501 to 362747.

As a bonus, the cycle of the "Before BaseFold verifier" is also slightly reduced from 657479 to 642016 (perhaps because some builder.get calls are replaced with slice operations).

New breakdown:

• Total cycles: 1547764 (Fibonacci e2e with $n=2^{20}$)
  • Read ZKVM proof variable from input: 362747 (23.4%)
    • Read chip proofs: 241622 (15.6%)
    • Read PCS proof: 120535 (7.8%)
  • Before BaseFold verifier: 642016 (41.5%)
    • Tower proofs: 518421 (33.5%)
  • BaseFold verifier: 542868 (35.1%)
    • Batching and first FRI round: 2047 * 100 (13.2%)
    • FRI rounds: 1709 * 100 (11.0%)
  • After BaseFold verifier: 133 (0%)

[yczhangsjtu]

Found that the ratio between cycle count and number of base field elements is 3. That means reading each base field element costs three cycles.

Possible reason: each DslIr::StoreHintWord instruction brings three ASM instructions. (But it should be following the IndexTriple::Const branch. No idea.)

https://github.com/openvm-org/openvm/blob/ca36de3803213da664b03d111801ab903d55e360/extensions/native/compiler/src/asm/compiler.rs#L529-L537

                DslIr::StoreHintWord(ptr, index) => match index.fp() {
                    IndexTriple::Const(index, offset, size) => self.push(
                        AsmInstruction::StoreHintWordI(ptr.fp(), size * index + offset),
                        debug_info.clone(),
                    ),
                    IndexTriple::Var(index, offset, size) => {
                        self.add_scaled(A0, ptr.fp(), index, size, debug_info.clone());
                        self.push(AsmInstruction::StoreHintWordI(A0, offset), debug_info)
                    }
                },

https://github.com/openvm-org/openvm/blob/ca36de3803213da664b03d111801ab903d55e360/extensions/native/compiler/src/asm/compiler.rs#L745-L752

    fn add_scaled(&mut self, dst: i32, src: i32, val: i32, c: F, debug_info: Option<DebugInfo>) {
        if c == F::ONE {
            self.push(AsmInstruction::AddF(dst, src, val), debug_info);
        } else {
            self.push(AsmInstruction::MulFI(dst, val, c), debug_info.clone());
            self.push(AsmInstruction::AddF(dst, dst, src), debug_info);
        }
    }

[kunxian-xia]

@kunxian-xia report cycle count of OpenVM's recursion program for keccak.

[darth-cy]

Total cycles: 3424397 (Keccak), detailed table breakdown:

Detailed sub-chip breakdown:

Overall Chart:

Detailed Breakdown Chart: