Optimize ecrecover ASM
#840
Merged
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
# Conflicts: # evm/src/cpu/kernel/interpreter.rs # evm/src/memory/segments.rs
# Conflicts: # evm/src/cpu/kernel/interpreter.rs
unzvfu
approved these changes
Jan 27, 2023
There was a problem hiding this comment.
Nice work! Good to go, modulo a few minor things.
Some notes on things that aren't part of the pull request:
- nit: You can remove most of the
SWAPs inecrecoverby changing the order ofDUPs andPUSHs; something like%ecrecover_input_check; PUSH 27; SWAP3; SUB; DUP4; %secp_liftxshould suffice. ecrecover_input_checkverifies that bothrandsare less thansecp256k1n. This is what appears in, for example, some documents, however the Yellow paper says thatsshould be less thansecp256k1n / 2 + 1. I suggest we work out which one it is and document the choice in the code.- Line 60 of
ecrecover.asm, looks like it should beSWAP6notSWAP5?! - Comment on line 18 of
curve_add.asmshould say 'second' instead of 'first' (but note review comments about how those checks might not be necessary)
wborgeaud
commented
Jan 31, 2023
There was a problem hiding this comment.
- nit: You can remove most of the
SWAPs inecrecoverby changing the order ofDUPs andPUSHs; something like%ecrecover_input_check; PUSH 27; SWAP3; SUB; DUP4; %secp_liftxshould suffice.
Good catch. This code predates the introduction of %stack, so I've just changed it to use it.
ecrecover_input_checkverifies that bothrandsare less thansecp256k1n. This is what appears in, for example, some documents, however the Yellow paper says thatsshould be less thansecp256k1n / 2 + 1. I suggest we work out which one it is and document the choice in the code.
So the s < secp256k1n / 2 + 1 is for signature verification on the network. For ecrecover, the condition is indeed s < secp256k1n (see equation (210) in the Yellow Paper). Don't ask me why they are different...
- Line 60 of
ecrecover.asm, looks like it should beSWAP6notSWAP5?!
Hm why? SWAPi swaps the 1st and i+1th element of the stack. Here we want to swap the 1st and 6th (s) element of the stack.
// stack: r^(-1), r^(-1), y, hash, x, s, retdest
SWAP5
// stack: s, r^(-1), y, hash, x, r^(-1), retdest
- Comment on line 18 of
curve_add.asmshould say 'second' instead of 'first' (but note review comments about how those checks might not be necessary)
👍
Oops, you're right, ignore that comment. |
Nashtare
pushed a commit
to topos-protocol/plonky2
that referenced
this pull request
Feb 2, 2023
* windowed mul * Working * Window of 4 bits * Fix * Comments * Unroll loop * Unroll loop * remove global * Minor * Minor * Implement `CALLVALUE, CALLDATALOAD, CALLDATASIZE, CALLDATACOPY` in interpreter * Minor * Doesn't work * Minor * Minor * wnaf msm * Working hardcoded values: 28657 opcodes * Working wnaf * Small wnaf optim * Precompute works * Working together * Bump to 129 bits * Working glv decomposition * Working MSM with GLV * Almost working * Working * ECC test folder * Working with real sig data * Fix tests + Clippy * Minor * Cleaning * Comments * Cleaning * Smaller glv test file * Print opcode count at the end of interpreter run * More constants * Add z3 proof that the GLV scalars are 129-bit or less * Minor change to z3 proof * Minor * Hamish's suggestion * Working * Cleaning * Clippy * PR feedback * Minor PR feedback
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.
Optimize ECDSA verification assembly by using GLV + wNAF + MSM.
An average ETH (valid) tx signature takes 37678 cycles to verify (currently 90089).