Inner-Product Verification with Multiexponentiation | Inner-Product Protocol for Non-powers of 2 #20
Conversation
This file contains 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
…dded range-proof benches to assess faster verification.
suyash67
changed the title
|
looks fantastic ! |
omershlo
reviewed
Jun 7, 2020
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.
Faster inner product proof verification using a single multi-exponentiation as described in Section 3.1 of the Bulletproofs paper. Improves the inner product verification by ~30%
Protocols similar in spirit to Bulletproofs require support for inner product protocol with secret vector sizes a non-power of 2. I have added a test demonstrating the same. The idea is simple:
2.1 Append secret vectors with 0's to make them the next power of 2
2.2 Extend the original base vectors to make them too the next power of 2
2.3 Compute vector exponentiations with a condition to check any 0's. This ensures minimum overhead computational cost due to modification of vector sizes to the next power of 2.