concrete benchmarks

[rahulghangas]

Now that Sonobe is going towards audits, is it possible to get some concrete benchmarks against other Nova implementations?

Related to #148

[winderica]

Yes we do plan to compare the performance of Sonobe with other folding libraries.

Currently I only have some preliminary benchmark results for our revamped version of Nova IVC (not Nova FS) vs Microsoft/Nova. This is not an apple to apple comparison but I am sharing it anyway for your information:

• Setup:
  • Environment: A Linux PC with Intel Core i9-12900K and 64GB of RAM.
  • Circuit used for benchmarks: The "bitwise and" example in Microsoft/Nova, which was ported to arkworks when testing Sonobe.
  • Configuration: 32 steps of IVC prover, each of which performs 1024 bitwise and operations for two 64-bit integers. No proof compression (I haven't adapted our decider to the new API yet).
• Results:
  • Nova IVC in PSE/Sonobe:
    • Primary circuit size: 242697
    • Secondary circuit size: 1349
    • IVC prover time for 32 steps: 2.449777616s
    • IVC prover RAM for 32 steps: 450088 KB
  • Nova IVC in Microsoft/Nova:
    • Primary circuit size: 212737
    • Secondary circuit size: 10538
    • IVC prover time for 32 steps: 4.861617317s
    • IVC prover RAM for 32 steps: 395376 KB

We were quite surprised to see that our IVC prover is about 2x faster than the original implementation. Later I looked a bit into their codebase and found that their IVC prover additionally applies rerandomization to witness-instance pairs, while ours only performs proof accumulation, which is why I mentioned earlier that the comparison is not very fair.

After the audits, I will try to benchmark the Nova FS instead. Since folding is a primitive for a single purpose (while IVC is kind of a composed protocol that may have additional functionalities), we should be able to provide more accurate comparisons under the same (or highly similar) setting for Nova FS. I estimate that our performance should be on par with Microsoft/Nova's, but it's also possible that ours is a bit faster (because I avoided quite some memory copies in the revamped version) or slower (because IIRC bellman, used by Microsoft/Nova, is a bit faster than arkworks, used by Sonobe).