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.

Sign up for GitHub

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

Optimize ecrecover ASM #840

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
Fix
  • Loading branch information
@wborgeaud
wborgeaud committed Nov 10, 2022
commit 5219bab0519eaaa3ad1d8aa014b79163d97b26e3
17 changes: 11 additions & 6 deletions evm/src/cpu/kernel/asm/curve/secp256k1/curve_add.asm
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -198,16 +198,21 @@ ec_add_equal_points:
%jump(ec_add_valid_points_with_lambda)

// Secp256k1 elliptic curve doubling.
// Assumption: (x0,y0) is a valid point.
// Assumption: (x,y) is a valid point.
// Standard doubling formula.
global ec_double_secp:
wborgeaud marked this conversation as resolved.
Show resolved Hide resolved
// stack: x0, y0, retdest
DUP2
// stack: y0, x0, y0, retdest
DUP2
// stack: x0, y0, x0, y0, retdest
// stack: x, y, retdest
DUP2 DUP2 %ec_isidentity
// stack: (x,y)==(0,0), x, y, retdest
wborgeaud marked this conversation as resolved.
Show resolved Hide resolved
%jumpi(retpoint)
DUP2 DUP2
// stack: x, y, x, y, retdest
%jump(ec_add_equal_points)
wborgeaud marked this conversation as resolved.
Show resolved Hide resolved

retpoint:
%stack (x, y, retdest) -> (retdest, x, y)
JUMP

// Push the order of the Secp256k1 scalar field.
%macro secp_base
PUSH 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
Expand Down
122 changes: 61 additions & 61 deletions evm/src/cpu/kernel/tests/curve_ops.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -174,73 +174,73 @@ mod secp {
);

// Standard addition #1
// let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0, point1.1, point1.0])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point2.1, point2.0])?);
// // Standard addition #2
// let initial_stack = u256ify(["0xdeadbeef", point1.1, point1.0, point0.1, point0.0])?;
// let stack = run(&kernel.code, ec_add, initial_stack, &kernel.prover_inputs)?
// .stack()
// .to_vec();
// assert_eq!(stack, u256ify([point2.1, point2.0])?);
//
let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0, point1.1, point1.0])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point2.1, point2.0])?);
// Standard addition #2
let initial_stack = u256ify(["0xdeadbeef", point1.1, point1.0, point0.1, point0.0])?;
let stack = run(&kernel.code, ec_add, initial_stack, &kernel.prover_inputs)?
.stack()
.to_vec();
assert_eq!(stack, u256ify([point2.1, point2.0])?);

// Standard doubling #1
// let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0, point0.1, point0.0])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point3.1, point3.0])?);
// // Standard doubling #2
// let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0])?;
// let stack = run_interpreter(ec_double, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point3.1, point3.0])?);
// // Standard doubling #3
// let initial_stack = u256ify(["0xdeadbeef", "0x2", point0.1, point0.0])?;
// let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point3.1, point3.0])?);
//
// // Addition with identity #1
// let initial_stack = u256ify(["0xdeadbeef", identity.1, identity.0, point1.1, point1.0])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point1.1, point1.0])?);
// // Addition with identity #2
// let initial_stack = u256ify(["0xdeadbeef", point1.1, point1.0, identity.1, identity.0])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point1.1, point1.0])?);
// // Addition with identity #3
// let initial_stack =
// u256ify(["0xdeadbeef", identity.1, identity.0, identity.1, identity.0])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([identity.1, identity.0])?);
let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0, point0.1, point0.0])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point3.1, point3.0])?);
// Standard doubling #2
let initial_stack = u256ify(["0xdeadbeef", point0.1, point0.0])?;
let stack = run_interpreter(ec_double, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point3.1, point3.0])?);
// Standard doubling #3
let initial_stack = u256ify(["0xdeadbeef", "0x2", point0.1, point0.0])?;
let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point3.1, point3.0])?);

// Addition with identity #1
let initial_stack = u256ify(["0xdeadbeef", identity.1, identity.0, point1.1, point1.0])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point1.1, point1.0])?);
// Addition with identity #2
let initial_stack = u256ify(["0xdeadbeef", point1.1, point1.0, identity.1, identity.0])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point1.1, point1.0])?);
// Addition with identity #3
let initial_stack =
u256ify(["0xdeadbeef", identity.1, identity.0, identity.1, identity.0])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([identity.1, identity.0])?);

// Scalar multiplication #1
let initial_stack = u256ify(["0xdeadbeef", s, point0.1, point0.0])?;
let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point4.1, point4.0])?);
// // Scalar multiplication #2
// let initial_stack = u256ify(["0xdeadbeef", "0x0", point0.1, point0.0])?;
// let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([identity.1, identity.0])?);
// // Scalar multiplication #3
// let initial_stack = u256ify(["0xdeadbeef", "0x1", point0.1, point0.0])?;
// let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point0.1, point0.0])?);
// // Scalar multiplication #4
// let initial_stack = u256ify(["0xdeadbeef", s, identity.1, identity.0])?;
// let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([identity.1, identity.0])?);
//
// // Multiple calls
// let ec_mul_hex = format!("0x{ec_mul:x}");
// let initial_stack = u256ify([
// "0xdeadbeef",
// s,
// &ec_mul_hex,
// identity.1,
// identity.0,
// point0.1,
// point0.0,
// ])?;
// let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
// assert_eq!(stack, u256ify([point4.1, point4.0])?);
// Scalar multiplication #2
let initial_stack = u256ify(["0xdeadbeef", "0x0", point0.1, point0.0])?;
let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([identity.1, identity.0])?);
// Scalar multiplication #3
let initial_stack = u256ify(["0xdeadbeef", "0x1", point0.1, point0.0])?;
let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point0.1, point0.0])?);
// Scalar multiplication #4
let initial_stack = u256ify(["0xdeadbeef", s, identity.1, identity.0])?;
let stack = run_interpreter(ec_mul, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([identity.1, identity.0])?);

// Multiple calls
let ec_mul_hex = format!("0x{ec_mul:x}");
let initial_stack = u256ify([
"0xdeadbeef",
s,
&ec_mul_hex,
identity.1,
identity.0,
point0.1,
point0.0,
])?;
let stack = run_interpreter(ec_add, initial_stack)?.stack().to_vec();
assert_eq!(stack, u256ify([point4.1, point4.0])?);

Ok(())
}
Expand Down