Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize ecrecover ASM #840

Merged
merged 48 commits into from
Jan 31, 2023
Merged
Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
48 commits
Select commit Hold shift + click to select a range
3fefe66
windowed mul
wborgeaud Nov 9, 2022
9f05bc3
Working
wborgeaud Nov 10, 2022
a040ff8
Window of 4 bits
wborgeaud Nov 10, 2022
5219bab
Fix
wborgeaud Nov 10, 2022
5d7c9f9
Comments
wborgeaud Nov 14, 2022
41555a9
Unroll loop
wborgeaud Nov 16, 2022
3461f75
Unroll loop
wborgeaud Nov 16, 2022
0840911
remove global
wborgeaud Nov 16, 2022
41bf153
Minor
wborgeaud Nov 18, 2022
a28c217
Minor
wborgeaud Nov 18, 2022
a7f7568
Implement `CALLVALUE, CALLDATALOAD, CALLDATASIZE, CALLDATACOPY` in in…
wborgeaud Nov 18, 2022
bbc13dc
Merge branch 'calldata_opcodes' into evm_secp_glv
wborgeaud Nov 18, 2022
1d87530
Minor
wborgeaud Nov 19, 2022
a96af5c
Doesn't work
wborgeaud Nov 21, 2022
4c97518
Minor
wborgeaud Dec 5, 2022
d2edaa3
Minor
wborgeaud Dec 5, 2022
be68c6b
wnaf msm
wborgeaud Dec 6, 2022
dff7593
Working hardcoded values: 28657 opcodes
wborgeaud Dec 6, 2022
99cc05a
Working wnaf
wborgeaud Dec 7, 2022
138c1df
Small wnaf optim
wborgeaud Dec 7, 2022
5a8783b
Precompute works
wborgeaud Dec 7, 2022
d39e9c9
Working together
wborgeaud Dec 7, 2022
33ede19
Bump to 129 bits
wborgeaud Dec 8, 2022
1204b4a
Working glv decomposition
wborgeaud Dec 8, 2022
2121790
Working MSM with GLV
wborgeaud Dec 8, 2022
2ddf4e3
Almost working
wborgeaud Dec 8, 2022
83157c3
Working
wborgeaud Dec 8, 2022
041c98c
ECC test folder
wborgeaud Dec 8, 2022
93285df
Working with real sig data
wborgeaud Dec 8, 2022
00da66e
Fix tests + Clippy
wborgeaud Dec 8, 2022
835ee56
Minor
wborgeaud Dec 8, 2022
0564144
Cleaning
wborgeaud Dec 9, 2022
b86001b
Comments
wborgeaud Dec 9, 2022
ebf5df0
Merge branch 'main' into evm_secp_glv
wborgeaud Dec 9, 2022
a55b9aa
Cleaning
wborgeaud Dec 9, 2022
bafe340
Smaller glv test file
wborgeaud Dec 9, 2022
269eb12
Print opcode count at the end of interpreter run
wborgeaud Dec 9, 2022
cb001d8
More constants
wborgeaud Dec 9, 2022
e9293d6
Add z3 proof that the GLV scalars are 129-bit or less
wborgeaud Dec 9, 2022
84c1683
Minor change to z3 proof
wborgeaud Dec 9, 2022
69e1290
Merge branch 'main' into evm_secp_glv
wborgeaud Dec 13, 2022
c45e9c3
Minor
wborgeaud Dec 15, 2022
d413b05
Hamish's suggestion
wborgeaud Jan 13, 2023
ccc225a
Working
wborgeaud Jan 13, 2023
c01b0e3
Cleaning
wborgeaud Jan 13, 2023
3e3e722
Clippy
wborgeaud Jan 13, 2023
5da15fa
PR feedback
wborgeaud Jan 31, 2023
0fe940f
Minor PR feedback
wborgeaud Jan 31, 2023
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Cleaning
  • Loading branch information
wborgeaud committed Dec 9, 2022
commit 05641440e7fbb3eb72f646b0fbd9ade444461000
25 changes: 5 additions & 20 deletions evm/src/cpu/kernel/asm/curve/secp256k1/curve_add.asm
Original file line number Diff line number Diff line change
Expand Up @@ -215,30 +215,15 @@ retself:

// Push the order of the Secp256k1 scalar field.
%macro secp_base
PUSH 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
PUSH @SECP_BASE
%endmacro

// Modular subtraction. Subtraction x-y underflows iff x<x-y, so can be computed as N*(x<x-y) + x-y.
// Modular subtraction.
// TODO: Use SUBMOD when it's ready
%macro submod_secp_base
// stack: x, y
SWAP1
// stack: y, x
DUP2
// stack: x, y, x
SUB
// stack: x - y, x
DUP1
// stack: x - y, x - y, x
SWAP2
// stack: x, x - y, x - y
LT
// stack: x < x - y, x - y
%secp_base
// stack: N, x < x - y, x - y
MUL
// stack: N * (x < x - y), x - y
ADD
// (x-y) % N
%stack (x, y) -> (@SECP_BASE, y, x, @SECP_BASE)
SUB ADDMOD
%endmacro
wborgeaud marked this conversation as resolved.
Show resolved Hide resolved

// Check if (x,y) is a valid curve point.
Expand Down
2 changes: 1 addition & 1 deletion evm/src/cpu/kernel/asm/curve/secp256k1/ecrecover.asm
Original file line number Diff line number Diff line change
Expand Up @@ -187,7 +187,7 @@ pubkey_to_addr:
%endmacro

%macro secp_scalar
PUSH 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
PUSH @SECP_SCALAR
%endmacro

// Return u256::MAX which is used to indicate the input was invalid.
Expand Down
6 changes: 3 additions & 3 deletions evm/src/cpu/kernel/asm/curve/secp256k1/glv.asm
Original file line number Diff line number Diff line change
Expand Up @@ -9,7 +9,7 @@ global glv:
// -(q1+q2) = -(k.b1.a1-k.b2.a2) = k2
// k1 - k2\lambda = k
// push group modulus n onto stack
PUSH 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 dup1 dup1
PUSH @SECP_SCALAR dup1 dup1
// we need to calculate k*b1. We require a full-width 512 bit multiplication,
// see https://medium.com/wicketh/mathemagic-full-multiply-27650fec525d
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff // -1 n n n k
Expand All @@ -23,7 +23,7 @@ global glv:
sub sub // top = (mm - bottom - (m < bottom)) n n n k
PUSH 0x3086d221a7d46bcde86c90e49284eb15 mulmod // q2 n n k

PUSH 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
PUSH @SECP_SCALAR
PUSH 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff // -1 n q2 n n k
PUSH 0x3086d221a7d46bcde86c90e49284eb15 dup7 mulmod // mm n q2 n n k
PUSH 0x3086d221a7d46bcde86c90e49284eb15 dup7 mul // bottom mm n q2 n n k
Expand All @@ -32,7 +32,7 @@ global glv:
PUSH 0xfffffffffffffffffffffffffffffffdd66b5e10ae3a1813507ddee3c5765c7e mulmod // q1 q2 n n k
add %sub_check_underflow // k2 underflow n k
swap3 // k underflow n k2
PUSH 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 // n k underflow n k2
PUSH @SECP_SCALAR // n k underflow n k2
dup5 PUSH 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72 // s k2 n k underflow n k2
mulmod // (s*k2)%n k underflow n k2
SWAP2 DUP1 %jumpi(underflowed)
Expand Down