Feat: unified ECADD #631

yelhousni · 2023-04-07T23:26:34Z

Fixes #630.

→ Suggested solution:

Select λ to be either (y1-p.y2)/(x1-x2) or 3x1²/2y1 based on x1==x1 && y1==y2. The problem is that division by x1-x2 will trigger an error as it uses big.Int ModInverse https://github.com/ConsenSys/gnark/blob/c02da5f61944d13c557d2b390ca56d5a26c597a1/std/math/emulated/hints.go#L251
~~So we implement a special method DivSpecial() that returns 0 when denominator is 0. We use it to compute (y1-p.y2)/(x1-x2) and proceed further, and then select 3x1²/2y1 if applicable.~~

Actually we can use Brier-Joye unified addition formulas, which compute a slope that works for both addition and doubling in affine coordinates — and also save half the constraints of the previous solution.

yelhousni · 2023-04-12T16:01:08Z

We use zero=(0,0) as the affine "representation" of the infinity point.

UnifiedAdd(P, zero) should output P
UnifiedAdd(zero, P) should output P
UnifiedAdd(zero, zero) should output zero
UnifiedAdd(P, -P) should output zero
ScalarMul(0, P) should output zero
ScalarMul(s, zero) should output zero
ScalarMulBase(0) should output zero

These methods are used in the EVM precompiles, so they should follow the (0,0) convention.
For double(), triple(), add() and doubleAndAdd() (now private) we don't handle the edge cases (used when these should not happen).
For Pair() the zkEVM arithmetization would filter the (0,0) points @OlivierBBB.

yelhousni · 2023-04-13T12:26:30Z

fixes #634

ivokub · 2023-04-17T07:44:01Z

Suggested edit:

diff --git a/std/algebra/emulated/sw_emulated/point.go b/std/algebra/emulated/sw_emulated/point.go
index 69e32594..46bdd8d5 100644
--- a/std/algebra/emulated/sw_emulated/point.go
+++ b/std/algebra/emulated/sw_emulated/point.go
@@ -77,6 +77,9 @@ func (c *Curve[B, S]) GeneratorMultiples() []AffinePoint[B] {
 
 // AffinePoint represents a point on the elliptic curve. We do not check that
 // the point is actually on the curve.
+//
+// Point (0,0) represents point at the infinity. This representation is
+// compatible with the EVM representations of points at infinity.
 type AffinePoint[Base emulated.FieldParams] struct {
 	X, Y emulated.Element[Base]
 }

ivokub · 2023-04-17T07:45:52Z

Suggested edit:

diff --git a/std/algebra/emulated/sw_emulated/point.go b/std/algebra/emulated/sw_emulated/point.go
index 69e32594..0ef6cd01 100644
--- a/std/algebra/emulated/sw_emulated/point.go
+++ b/std/algebra/emulated/sw_emulated/point.go
@@ -126,12 +126,12 @@ func (c *Curve[B, S]) add(p, q *AffinePoint[B]) *AffinePoint[B] {
 //
 // ✅ p can be equal to q, and either or both can be (0,0).
 // (0,0) is not on the curve but we conventionally take it as the
-// neutral/infinity point as per the EVM [EYP].
+// neutral/infinity point as per the [EVM].
 //
-// It uses the unified formulas of Brier and Joye [BriJoy02] (Corollary 1).
+// It uses the unified formulas of Brier and Joye ([[BriJoy02]] (Corollary 1)).
 //
 // [BriJoy02]: https://link.springer.com/content/pdf/10.1007/3-540-45664-3_24.pdf
-// [EYP]: https://ethereum.github.io/yellowpaper/paper.pdf
+// [EVM]: https://ethereum.github.io/yellowpaper/paper.pdf
 func (c *Curve[B, S]) AddUnified(p, q *AffinePoint[B]) *AffinePoint[B] {
 
 	// selector1 = 1 when p is (0,0) and 0 otherwise
@@ -338,7 +338,7 @@ func (c *Curve[B, S]) Lookup2(b0, b1 frontend.Variable, i0, i1, i2, i3 *AffinePo
 //
 // ✅ p can can be (0,0) and s can be 0.
 // (0,0) is not on the curve but we conventionally take it as the
-// neutral/infinity point as per the EVM [EYP].
+// neutral/infinity point as per the [EVM].
 //
 // It computes the standard little-endian variable-base double-and-add algorithm
 // [HMV04] (Algorithm 3.26).
@@ -352,7 +352,7 @@ func (c *Curve[B, S]) Lookup2(b0, b1 frontend.Variable, i0, i1, i2, i3 *AffinePo
 //
 // [ELM03]: https://arxiv.org/pdf/math/0208038.pdf
 // [HMV04]: https://link.springer.com/book/10.1007/b97644
-// [EYP]: https://ethereum.github.io/yellowpaper/paper.pdf
+// [EVM]: https://ethereum.github.io/yellowpaper/paper.pdf
 func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *AffinePoint[B] {
 
 	// if p=(0,0) we assign a dummy (0,1) to p and continue
@@ -402,7 +402,7 @@ func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *Affi
 //
 // ✅ When s=0, it retruns (0,0).
 // (0,0) is not on the curve but we conventionally take it as the
-// neutral/infinity point as per the EVM [EYP].
+// neutral/infinity point as per the [EVM].
 //
 // It computes the standard little-endian fixed-base double-and-add algorithm
 // [HMV04] (Algorithm 3.26).
@@ -413,7 +413,7 @@ func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *Affi
 // [3]g, [5]g and [7]g points.
 //
 // [HMV04]: https://link.springer.com/book/10.1007/b97644
-// [EYP]: https://ethereum.github.io/yellowpaper/paper.pdf
+// [EVM]: https://ethereum.github.io/yellowpaper/paper.pdf
 func (c *Curve[B, S]) ScalarMulBase(s *emulated.Element[S]) *AffinePoint[B] {
 	g := c.Generator()
 	gm := c.GeneratorMultiples()

ivokub · 2023-04-17T07:46:27Z

Suggested edit:

diff --git a/std/algebra/emulated/sw_emulated/point.go b/std/algebra/emulated/sw_emulated/point.go
index 69e32594..78b05b99 100644
--- a/std/algebra/emulated/sw_emulated/point.go
+++ b/std/algebra/emulated/sw_emulated/point.go
@@ -400,7 +400,7 @@ func (c *Curve[B, S]) ScalarMul(p *AffinePoint[B], s *emulated.Element[S]) *Affi
 // ScalarMulBase computes s * g and returns it, where g is the fixed generator.
 // It doesn't modify s.
 //
-// ✅ When s=0, it retruns (0,0).
+// ✅ When s=0, it returns (0,0).
 // (0,0) is not on the curve but we conventionally take it as the
 // neutral/infinity point as per the EVM [EYP].
 //

ivokub

A few stylistic change suggest: for paper use "academic"-style links and for EVM just use it.
An idea about renaming the methods.
One potential optimisation.

Other than that I think it looks good.

std/algebra/emulated/sw_emulated/point.go

ivokub · 2023-04-17T23:08:06Z

Applied the changes. If looks good then go for merge.

feat(sw_emulated): AddSafe for input points equal or not

c2bb362

yelhousni added type: bug Something isn't working dep: linea Issues affecting Linea downstream labels Apr 7, 2023

yelhousni added this to the v0.9.0 milestone Apr 7, 2023

yelhousni requested review from OlivierBBB, gbotrel and ivokub April 7, 2023 23:26

yelhousni self-assigned this Apr 7, 2023

yelhousni added 8 commits April 9, 2023 14:06

feat: use Brier-Joye unified add for evm ecadd

cce13ba

refactor: remove DivSpecial

73661f0

fix(ecadd): add y1+y2=0 edge case

35b2a7a

feat(sw_emulated): infinity as (0,0) edge-cases in UnifiedAdd

19a8962

feat(sw_emulated): infinity as (0,0) edge-cases in ScalarMul

44fe9af

test(sw_emulated): infinity as (0,0) edge-cases in ScalarMul

fa0592a

docs: add comments to sw_emulated

855ef61

refactor: make double, add, triple and doubleAndAdd private

460c1c9

fix: use AddUnified in ECRecover

3b6747b

ivokub approved these changes Apr 17, 2023

View reviewed changes

std/algebra/emulated/sw_emulated/point.go Outdated Show resolved Hide resolved

std/algebra/emulated/sw_emulated/point.go Show resolved Hide resolved

ivokub added 5 commits April 18, 2023 00:44

docs: point at infinity

6f3bf1f

docs: godoc linking

c262b0b

docs: typo

44f60fc

docs: comment about AddUnified

4ba43d3

perf: optimise one sub

259043e

yelhousni merged commit 66b8db3 into develop Apr 18, 2023

yelhousni deleted the feat/AddSafe branch April 18, 2023 06:44

yelhousni mentioned this pull request Apr 18, 2023

ECADD precompile: input points can be equal #630

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Feat: unified ECADD #631

Feat: unified ECADD #631

Uh oh!

yelhousni commented Apr 7, 2023 •

edited

Loading

Uh oh!

yelhousni commented Apr 12, 2023

Uh oh!

yelhousni commented Apr 13, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub left a comment

Uh oh!

Uh oh!

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Feat: unified ECADD #631

Feat: unified ECADD #631

Uh oh!

Conversation

yelhousni commented Apr 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

yelhousni commented Apr 12, 2023

Uh oh!

yelhousni commented Apr 13, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

ivokub left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

ivokub commented Apr 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

yelhousni commented Apr 7, 2023 •

edited

Loading