Shard Proofs

Code: crates/hypercube/src/verifier/shard.rs::verify_shard.

Each shard proof consists mainly of:

• Generating the computation trace.
• Generating auxiliary data required toward the proof, this is referred to as the witness.
• Proving that the witness satisfies a set of constraints, that ensure consistency with the RISC V spec and with the global memory.

The computation trace is logically set in tables, where each table corresponds to one of the RISC V instructions (e.g., ADDI, MUL, LSHIFT, etc). The columns of the table consist of all the operands of the relevant instruction, that are needed in order to verify it that was executed correctly.

The Hypercube proof-system is a (multilinear) polynomial based interactive oracle proof (IOP). The proof-system starts by committing to a polynomial that encodes the computation trace. In previous versions of SP1, this was done by committing separately to each column of each table. The separate commitments carry a significant overhead in recursion (basically linear in the number of columns). This is avoided in SP1 by committing to a single polynomial that contains the entire trace (as a concatenation of the columns), and then using an adapter, called the Jagged Polynomial Commitment Scheme (PCS), which converts claim about individual columns to a trace about the multilinear extension of the entire trace.