search

a16z / jolt

The simplest and most extensible zkVM. Fast and fully open source from a16z crypto and friends. ⚡
https://jolt.a16zcrypto.com
MIT License
580 stars 105 forks source link

feat: R1CS Refactor #368

Closed sragss closed 3 weeks ago

sragss commented 1 month ago

R1CS refactor for declarative R1CS programming. Supports appending constraints by any implementations of R1CSConstraintBuilder which will be important with the RISC-V extensions and Binius custom SNARKs.

Example:

struct TestConstraints();
impl<F: JoltField> R1CSConstraintBuilder<F> for TestConstraints {
    type Inputs = TestInputs;
    fn build_constraints(&self, builder: &mut R1CSBuilder<F, Self::Inputs>) {
        builder.constrain_prod(TestInputs::OpFlags0, TestInputs::OpFlags1, TestInputs::BytecodeA);
        let _aux = builder.allocate_prod(TestInputs::OpFlags2, TestInputs::OpFlags3);
    }
}

Each aux variable that is appended to the builder is appended along with a lambda to compute the aux from inputs.

Auxiliary variables are computed directly from linear combinations (LC) and (Az, Bz, Cz) are computed directly from linear combinations of the corresponding constraints. This appears to be slightly less efficient than before costing 1-2% end-to-end.

Devex: R1CSBuilder.assert_valid will describe the exact constraint and step which failed.

PR introduces a massive number of tests for each and every part of R1CS and Spartan. Ignoring these tests the PR is diff neutral.

sragss commented 3 weeks ago

On further thought – this PR adds several constraints and input variables (merged upstream virtual instructions, mul instructions) so these algorithims are a significant speedup.