Trace sorting: Take advantage of sorted trace in sumcheck #870
Assignees
Milestone
Comments
ledwards2225
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Apr 23, 2024
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 ```
AztecBot
pushed a commit
that referenced
this issue
Apr 24, 2024
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 ```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We can take advantage of a sorted execution trace in sumcheck by only evaluating relations that are active at each row. This will involve logic for determining active relations in the first round and subsequent rounds as appropriate.
Note: This is not directly tied to the Noir-Honk integration but needs to be done at some point and seems like a nice bonus to have at the time of integration since it will dramatically improve proving speeds.
Edit: The simplest approach here is the one taken by Kesha in his "skippety" work. For each round of sumcheck, simply check if the selector for a given relation is zero at both points on the edge being collapsed. If so, the contribution from that edge is zero and the computation can be skipped. The effectiveness of this method is improved by the sorting since it will in general be the case that if a relation is off at one point on the edge, it will be off at the other, and vice versa. Another approach is to condition relation execution based on the simple range where the relation is active (based on the block size/sorting). It seems plausible that this could lead to better branch prediction and therefore lower overhead for the conditionals. Worth considering but seems unlikely to provide much benefit.
The text was updated successfully, but these errors were encountered: