Proof size increase after migration to P3

[Al-Kindi-0]

... it seems like our proof sizes have exploded with this migration. Specifically, what previously was 100KB now become 300KB. There are probably multiple factors for this:

• We are now using Blake3_256 instead of Blake3_192 hash function.
• We are using FRI folding factor 2 instead of 8.
• We are using bincode instead of handcrafted serialization.
• Maybe anything else?

Originally posted by @bobbinth in #2472 (comment)

[bobbinth]

Documenting my benchmarks here for running the BLAKE3 example for 1M cycles (done on current main):

Proof sizes with:

• 192-bit hash + FRI folding factor 8: 100 KB.
• 256-bit hash + FRI folding factor 4: 138 KB.
• 256-bit hash + FRI folding factor 2: 195 KB.

This compares to our current next at 300 KB for 256-bit hash + FRI folding factor 2.

[Al-Kindi-0]

Looking at the P3 implementation, it seems that batching of Merkle authentication paths is not done. After some experiments, we have the following numbers

  Parameters:
    Trace size: 2^20 = 1048576
    Folding factor: 2
    Final poly degree: 1
    Number of FRI queries: 27
    Number of FRI layers: 20

  Standard STARK Proof:
     FRI proof: 238068 bytes (232.49 KB)
  Batched FRI Proof:
    FRI proof size: 166136 bytes (162.24 KB)

This is just for the FRI proof part as integrating batching in the whole proving/verifying will require a bit of work. However, if we extrapolate the above 30% reduction in FRI proof size to the whole STARK proof, then we will be able to account for the 100KB increase in the proof size after migration. Of course, this is a crude approximation but it shouldn't be far off.

[bobbinth]

This should get at least partially resolved by migration to Lifted STARK.

[Al-Kindi-0]

Given the recent work by @adr1anh in #2798 , the proof size are now:

• 256-bit hash + FRI folding factor 4: 138 KB.
• 256-bit hash + FRI folding factor 2: 195 KB.

This matches exactly the numbers reported above by @bobbinth (and yes, I double checked that it is lifted STARK and not Winterfell as the numbers were suspiciously similar :) )

[Al-Kindi-0]

This is now fixed in the current VM release