Reducing proof size

[wborgeaud]

• Compress Merkle paths. Done in Simpler Merkle paths compression #255.
• Remove the element that can be inferred in the FRI reduction step. We already did that before f2c423e, but it was removed when we replaced the InsertionGate with the RandomAccessGate. We can add it back to save some field elements. Done in Remove inferred element in compressed proof #298.
• Replace Merkle caps with Merkle roots in the compressed proofs. In Replace Merkle roots with Merkle caps #170 we replace Merkle roots with Merkle caps to save some gates in the recursive verifier. However this is a bit wasteful in compressed proofs, so replacing the caps with the roots would save some space there.
• The FRI verifier queries the oracle at many indices that are not necessarily distinct. We could check for duplicates and remove the duplicate query proofs in the compressed proofs. Done in Remove duplicate query indices in FRI proofs  #279.
• We could implement our own proof serialization. Right now serde_cbor wastes quite a bit of space. For example a vector of 100 CrandallField elements is serialized with 902 bytes, whereas a simple byte array would take 800 bytes. Done in Custom serializer for proofs #280.
• Reduce num_query_rounds. The proof size is currently given by 12.4 + 6.7*num_query_rounds KB, so simply reducing num_query_round can save quite a bit of memory. Note that we'd need to increase proof_of_work_bits or rate_bits to maintain security, which would in turn increase the proving time.

[dlubarov]

I think the 3rd item can be considered done/wontfix based on the points you raised yesterday. I.e. if there are Merkle cap elements that aren't "seen", we can't recover the cap, unless we include the unseen elements, but that would negate the space savings. cap_height: 0 works for bridge proofs at least.

I think the last point can be considered done, since the size_optimized test uses fewer rounds along with more PoW bits and rate bits.

[wborgeaud]

All of the 6 original tasks have been completed.
Here are the current recursive proof sizes:

• Recursive proof optimized for gate count and prover time, using rate_bits=3, num_query_rounds=28, reduction_arity_bits=[3,3,3], pow_bits=16, cap_height=3: Average proof size: 137KB, σ=1.5KB.
• Recursive proof optimized for proof size, using rate_bits=7, num_query_rounds=11, reduction_arity_bits=[3,3], pow_bits=23, cap_height=0: Average proof size: 71KB, σ=0.6KB.