Skip condition for lookup relation #952

ledwards2225 · 2024-04-17T19:34:26Z

The following skip condition applies for the lookup relation:

// From the definition of the lookup grand product, if the inputs are trivial,
// Z_lookup is updated as Z_lookup_{i+1} = Z_lookup_i * \gamma * (1 + \beta). If this condition holds, the
// contribution of the given inputs will be the zero polynomial.
auto gamma_by_one_plus_beta = params.gamma * (params.beta + 1);
bool is_active = !(in.z_lookup_shift.value_at(0) == in.z_lookup.value_at(0) * gamma_by_one_plus_beta &&
                           in.z_lookup_shift.value_at(1) == in.z_lookup.value_at(1) * gamma_by_one_plus_beta);

Applying this for sumcheck (proof construction, decider) passes all tests (and skips many trivial contributions if the circuit does not have a large number of lookups/tables). However, there are sporadic failures in bb acir tests. The error is repeatable on CI, but not between CI and local. Any test seems to pass when run individually. All tests pass when built in debug, eve if all run sequentially.

Adds Kesha's relation skipping approach for Sumcheck only (i.e. full proof construction / decider), not for folding. My only addition is a condition for skipping the permutation relation. (I added a condition for skipping the lookup relation but it leads to erratic failures in acir tests that I couldn't explain. Details written into an [issue](AztecProtocol/barretenberg#952)). Closes: AztecProtocol/barretenberg#870 (Taking advantage of sorted trace in sumcheck) Master bench: ``` --------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------- construct_proof_ultrahonk/sha256 426 ms 397 ms 2 construct_proof_ultrahonk/keccak 1627 ms 1517 ms 1 construct_proof_ultrahonk/ecdsa_verification 2974 ms 2754 ms 1 construct_proof_ultrahonk/merkle_membership 237 ms 219 ms 3 construct_proof_ultrahonk_power_of_2/15 249 ms 231 ms 3 construct_proof_ultrahonk_power_of_2/16 455 ms 427 ms 2 construct_proof_ultrahonk_power_of_2/17 886 ms 831 ms 1 construct_proof_ultrahonk_power_of_2/18 1762 ms 1657 ms 1 construct_proof_ultrahonk_power_of_2/19 3428 ms 3211 ms 1 construct_proof_ultrahonk_power_of_2/20 6752 ms 6344 ms 1 ``` Branch: ``` --------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------- construct_proof_ultrahonk/sha256 330 ms 262 ms 3 construct_proof_ultrahonk/keccak 1212 ms 1036 ms 1 construct_proof_ultrahonk/ecdsa_verification 2311 ms 1980 ms 1 construct_proof_ultrahonk/merkle_membership 191 ms 158 ms 4 construct_proof_ultrahonk_power_of_2/15 191 ms 176 ms 4 construct_proof_ultrahonk_power_of_2/16 342 ms 316 ms 2 construct_proof_ultrahonk_power_of_2/17 664 ms 614 ms 1 construct_proof_ultrahonk_power_of_2/18 1271 ms 1174 ms 1 construct_proof_ultrahonk_power_of_2/19 2542 ms 2332 ms 1 construct_proof_ultrahonk_power_of_2/20 4944 ms 4540 ms 1 ```

Adds Kesha's relation skipping approach for Sumcheck only (i.e. full proof construction / decider), not for folding. My only addition is a condition for skipping the permutation relation. (I added a condition for skipping the lookup relation but it leads to erratic failures in acir tests that I couldn't explain. Details written into an [issue](#952)). Closes: #870 (Taking advantage of sorted trace in sumcheck) Master bench: ``` --------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------- construct_proof_ultrahonk/sha256 426 ms 397 ms 2 construct_proof_ultrahonk/keccak 1627 ms 1517 ms 1 construct_proof_ultrahonk/ecdsa_verification 2974 ms 2754 ms 1 construct_proof_ultrahonk/merkle_membership 237 ms 219 ms 3 construct_proof_ultrahonk_power_of_2/15 249 ms 231 ms 3 construct_proof_ultrahonk_power_of_2/16 455 ms 427 ms 2 construct_proof_ultrahonk_power_of_2/17 886 ms 831 ms 1 construct_proof_ultrahonk_power_of_2/18 1762 ms 1657 ms 1 construct_proof_ultrahonk_power_of_2/19 3428 ms 3211 ms 1 construct_proof_ultrahonk_power_of_2/20 6752 ms 6344 ms 1 ``` Branch: ``` --------------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------------- construct_proof_ultrahonk/sha256 330 ms 262 ms 3 construct_proof_ultrahonk/keccak 1212 ms 1036 ms 1 construct_proof_ultrahonk/ecdsa_verification 2311 ms 1980 ms 1 construct_proof_ultrahonk/merkle_membership 191 ms 158 ms 4 construct_proof_ultrahonk_power_of_2/15 191 ms 176 ms 4 construct_proof_ultrahonk_power_of_2/16 342 ms 316 ms 2 construct_proof_ultrahonk_power_of_2/17 664 ms 614 ms 1 construct_proof_ultrahonk_power_of_2/18 1271 ms 1174 ms 1 construct_proof_ultrahonk_power_of_2/19 2542 ms 2332 ms 1 construct_proof_ultrahonk_power_of_2/20 4944 ms 4540 ms 1 ```

ledwards2225 · 2024-08-02T07:50:38Z

Plookup was replaced with log-derivative lookups, for which the skip condition has been implemented.

ledwards2225 mentioned this issue Apr 18, 2024

feat: Keshas skipping plus conditions for grand prod relations AztecProtocol/aztec-packages#5766

Merged

ledwards2225 self-assigned this Aug 2, 2024

ledwards2225 closed this as completed Aug 2, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Skip condition for lookup relation #952

Skip condition for lookup relation #952

ledwards2225 commented Apr 17, 2024 •

edited

Loading

ledwards2225 commented Aug 2, 2024

Skip condition for lookup relation #952

Skip condition for lookup relation #952

Comments

ledwards2225 commented Apr 17, 2024 • edited Loading

ledwards2225 commented Aug 2, 2024

ledwards2225 commented Apr 17, 2024 •

edited

Loading