Perf: variant of the Karabina cyclotomic squaring #933
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
ivokub
approved these changes
Nov 23, 2023
ivokub
added a commit
that referenced
this pull request
Nov 28, 2023
commit 6c05ea4 Author: Ivo Kubjas <[email protected]> Date: Tue Nov 28 16:24:47 2023 +0100 perf: use G2 precomputed lines for Miller loop (#930) * feat: add lazy line eval for Miller loop * chore: go mod * fix: DoublePairFixed order * refactor: remove fixed Q specialized methods * chore: serialize lines for KZG key * chore: go generate * docs: add init docs * feat: add fixed KZG verification key init * test: add constant and fixed VK test cases * test: use fixed init * feat: add fixed Groth16 verification * fix: unused import * refactor: merge last manual iteration commit a99d198 Author: Ivo Kubjas <[email protected]> Date: Tue Nov 28 16:20:44 2023 +0100 feat: add PLONK in-circuit verifier (#880) * test: add recursion hash tests * fix: accumulate MSM result * refactor: take emulated element for additional data * fix: handled infinity point in native multi scalar exp * fix: use only nbBits when creating scalar * feat: add PLONK verifier * feat: PlaceholderVerifyingKey takes the vk as argument * feat: f -> scalarApi * feat: addition of computeIthLagrangeAtZeta * feat: bsb commitments are added to pi * refactor: PlaceholderProof takes the proof as argument * fix: compute ith lagrange ok, hashToField failing * fix: native short hash output size * feat: add bw6 * docs: add package documentation * refactor: describe error in panic * refactor: init curve and pairing implicitly * refactor: remove comments * docs: add package examples * feat: add all supported witness assignments * test: add MSM test * fix: remove todo panic * feat: add option shortcuts * fix: include hash to field in shortcut option * feat: use only CCS for placeholder proof and verifyingkey * chore: typos and cleanup * docs: add KZG package documentation --------- Co-authored-by: Thomas Piellard <[email protected]> commit 62b52ea Merge: ec07217 97156f3 Author: Youssef El Housni <[email protected]> Date: Fri Nov 24 10:44:33 2023 -0500 Merge pull request #933 from Consensys/perf/karabina-cycloSq Perf: variant of the Karabina cyclotomic squaring commit 97156f3 Author: Youssef El Housni <[email protected]> Date: Fri Nov 24 10:27:00 2023 -0500 refactor: apply PR review suggestions commit f52c4cb Author: Youssef El Housni <[email protected]> Date: Thu Nov 23 01:50:41 2023 -0500 perf(bls12-377): implement a variant of Karabina cyclo square commit d7e8d78 Author: Youssef El Housni <[email protected]> Date: Wed Nov 22 23:28:26 2023 -0500 perf(bw6): implement a variant of Karabina cyclo square commit ec07217 Merge: 3aa2559 5479586 Author: Youssef El Housni <[email protected]> Date: Wed Nov 22 18:16:46 2023 -0500 Merge pull request #931 from Consensys/perf/bw6-finalExp Perf: optimize addition chains in BW6-761 final exponentiation commit 5479586 Author: Youssef El Housni <[email protected]> Date: Wed Nov 22 13:07:50 2023 -0500 perf(bw6/finalExp): replace Add(x,x) by MulConst(x,2) commit 65cd6ee Author: Youssef El Housni <[email protected]> Date: Tue Nov 21 21:39:55 2023 -0500 fix(linter): ineffectual assignment commit d948c7c Author: Youssef El Housni <[email protected]> Date: Tue Nov 21 21:27:02 2023 -0500 perf(bw6/finalExp): optimize addition chains commit 3aa2559 Author: Gautam Botrel <[email protected]> Date: Mon Nov 20 14:03:52 2023 -0600 feat: if we don't compress we don't need the dict (#929)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Description
Currently we implement Theorem 3.2 from https://eprint.iacr.org/2010/542.pdf whenever we have 3 repeated squaring or more in the final exponentiation. It is the fastest variant of cyclotomic squaring but in-circuit the selector logic to handle branching cases when denominators are zero makes it not always the best in some cases. This PR compares different variants in Sec. 5 and proposes a tradeoff:
For the native case, when repeated squaring size is:
So nothing changes concretely for BLS12-377 since we do not encouter the case of size 3.
For emulated case, it difficult to theoretically set a threshold due to emulated arithmetic but empirically for BW6-761:
Type of change
How has this been tested?
TestExptFp6andTestFinalExponentiationTestSolveare used here to test the new Karabina variants. Otherwise we need to implement the go version of these in gnark-crypto.How has this been benchmarked?
For BW6-761, this saves 290826 SCS in the Final exp.
Checklist:
golangci-lintdoes not output errors locally