einar/pr/extended.jacobian.coordinates #1

einar-taiko · 2023-08-21T10:01:23Z

This resolves taikoxyz/zkevm-circuits#121

To measure the performance impact:

cd /tmp
git clone https://github.com/einar-taiko/halo2curves.git
cd halo2curves
git checkout b09144e
cargo bench multiexp
git checkout einar/pr/extended.jacobian.coordinates
cargo bench multiexp

mratsim · 2023-08-22T15:48:29Z

I get even less improvement than previously reported which is quite strange

git clone https://github.com/taikoxyz/halo2curves taiko-halo2curves
cd taiko-halo2curves/
git fetch origin pull/1/head
git checkout 9692b29
cargo bench multiexp
git checkout -b review-pr1 FETCH_HEAD
cargo bench multiexp

mratsim · 2023-08-22T15:51:00Z

src/multiexp.rs

+            });
+            sum
+        })
+}


Is the plan to remove this after the review? This duplicates halo2_proofs https://github.com/privacy-scaling-explorations/halo2/blob/f3487575f00e627705fcb7778d7d1049eed79601/halo2_proofs/src/arithmetic.rs#L28-L174

mratsim

The EC implementation is correct with a small issue on inline usage that will lead to code explosion.

The multiexp implementation should be done by just modifying the buckets accumulation scheme in https://github.com/privacy-scaling-explorations/halo2/blob/f3487575f00e627705fcb7778d7d1049eed79601/halo2_proofs/src/arithmetic.rs#L67-L71

Also, there are 2 passes over the coeffs+base instead of 1 in this PR which should explain most of the slowness compared to theoretical (15%) and conservative estimate (10% speedup).

Cargo.toml

mratsim · 2023-08-23T05:41:31Z

src/derive/curve.rs


        // Jacobian implementations

+        // From affine to homogeneous


Is it from affine to homogeneous or from affine to Jacobian?

This seems to contradict the comment above

Agreed. I added the comment because I found it confusing too, since $name refers to homogeneous coordinates and $name_affine to affine coordinates. Alternatively, I can remove the first comment, since non-extended Jacobian coordinates should be gone anyway.

mratsim · 2023-08-23T05:45:46Z

src/derive/curve.rs

+                let zzz1 = p.zzz;
+
+                // curve constants
+                let a = Self::curve_constant_a();


a is always equal to 0 for pairing curves (those needed for Snarks) and it's also equal to 0 for secp256k1.

If Rust provides compile time evaluation, it would be extremely useful to specialize for a == 0

At the very least a comment is needed to point out an future easy optimization opportunity

a is always equal to 0 for pairing curves (those needed for Snarks) and it's also equal to 0 for secp256k1.

If Rust provides compile time evaluation, it would be extremely useful to specialize for a == 0

I have changed it to:

// curve constants const A: $base = $name_jac_ext::curve_constant_a();

This should enforce compile time evaluation and hopefully imply that

let m = (x1_sqr.double()+x1_sqr) + A*zz1.square();

gets optimized to

let m = (x1_sqr.double()+x1_sqr)

for the curves where $a=0$. But I am currently not sure how to verify this.

You should use if A == 0 and if A != 0.

The multiplication and addition operations are pure assembly and will not be optimized away.

We can make it that way, no problem, but I politely remain skeptical of the argument. When the value is known to be 0 at compile time, like in our case, the assembly will indeed be optimized away. I tested it with -opt-level=2 here https://godbolt.org/z/4Gr41o8Kr

We can make it that way, no problem, but I politely remain skeptical of the argument. When the value is known to be 0 at compile time, like in our case, the assembly will indeed be optimized away. I tested it with -opt-level=2 here https://godbolt.org/z/4Gr41o8Kr

I realise that * is overloaded for field arithmetic, so my argument may or may not be applicable.

mratsim · 2023-08-23T05:47:15Z

src/derive/curve.rs

+                let w = u*v;
+                let s = x1 * v;
+                let x1_sqr = x1.square();
+                let m = (x1_sqr.double()+x1_sqr) + a*zz1.square();


with a = 0, a*zz1.square() can be skipped

I tried commenting out the last term and then ran cargo test. All tests pass.

I put in a debug_assert_eq!(a, 0);, so if we can catch future curves where a != 0.

mratsim · 2023-08-23T05:51:15Z

src/derive/curve.rs

+            }
+
+            /// <http://www.hyperelliptic.org/EFD/g1p/auto-shortw-xyzz.html#doubling-dbl-2008-s-1>
+            #[inline]


#[inline] is likely not worth it here. Especially because the underlying field operations are already inline so it will lead to code size explosion:

halo2curves/src/bn256/assembly.rs

Lines 11 to 12 in 2264867

#[inline]

pub fn double(&self) -> $field {

Okay. I will remove it from the add as well then.

mratsim · 2023-08-23T06:00:43Z

src/multiexp.rs

+    let num_threads = num_cpus::get();
+    if n > num_threads && n > 32 {
+        let chunk = n / num_threads;
+        let results: Vec<C::ExtendedJacobianCoordinates> = coeffs


Only the inner buckets result should be collected in Extended Jacobian.

Extended Jacobian mixed addition is faster than projective, but for plain addition, projective is faster.

So the signature of best_multiexp should stay with projective coordinates

mratsim · 2023-08-23T06:01:55Z

benches/multiexp.rs

+            })
+            .sample_size(30);
+    }
+}


To measure perf of this PR without multithreading interference, a serial benchmark is needed as well.

mratsim · 2023-08-23T06:03:23Z

src/multiexp.rs

+    }
+}
+
+pub(crate) fn multiexp_serial<C: CurveJacExt>(coeffs: &[C::Scalar], bases: &[C]) -> C::ExtendedJacobianCoordinates {


similarly, the signature of multiexp_serial should stay homogeneous projective

mratsim · 2023-08-23T06:11:16Z

src/multiexp.rs

+        .enumerate()
+        .rev()
+        .map(|(i, bucket)| {
+            for (coeff, base) in coeffs.iter().zip(bases.iter()) {


The map and for are inefficient, you loop twice over the data.

You should loop over the coeff+base and directly mutate/add_assign in the matching bucket

mratsim · 2023-08-23T06:14:16Z

src/multiexp.rs

+            }
+            bucket
+        })
+        .fold(C::jac_ext_identity(), |mut sum, bucket| {


The final reduction should use projective coordinates (and explicitly convert the bucket sum to projective)

mratsim · 2023-08-29T06:55:17Z

Note on our discussion on constant_a, some more changes upstream privacy-scaling-explorations#82.

…_curve()` is implemented

einar-taiko requested a review from mratsim August 21, 2023 10:01

mratsim reviewed Aug 22, 2023

View reviewed changes

mratsim requested changes Aug 23, 2023

View reviewed changes

einar-taiko self-assigned this Aug 23, 2023

einar-taiko added 2 commits August 28, 2023 14:50

Add multiexp benchmark

21ccac6

Add Extended Jacobian Coordinates

6455fe2

einar-taiko added 7 commits August 30, 2023 15:15

fix: remove mistakes from rebase

2d8f029

fix: compile, hash_to_curve not implemented

66bb47f

fix: make benchmark independent of crate halo2

8982d11

fix: Ignore all proptests until function `src/derive/curve.rs:hash_to…

95ce8c3

…_curve()` is implemented

refactor: Implement partial review suggestions

93ef06b

fix: remove curve_constant_a

8ab6cc8

experiment: patch to use local halo2 path

747c6e2

einar-taiko force-pushed the einar/pr/extended.jacobian.coordinates branch from d52078b to 747c6e2 Compare August 30, 2023 08:13

WIP: refactor

c6612e1

mratsim force-pushed the main branch from ba112ff to 5b0e99e Compare September 6, 2023 12:18

mratsim force-pushed the taiko/unstable branch from 2239b6a to 81a0782 Compare November 2, 2023 16:22

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

einar/pr/extended.jacobian.coordinates #1

einar/pr/extended.jacobian.coordinates #1

einar-taiko commented Aug 21, 2023

mratsim commented Aug 22, 2023

mratsim Aug 22, 2023

mratsim left a comment

mratsim Aug 23, 2023 •

edited

Loading

einar-taiko Aug 24, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

einar-taiko Aug 23, 2023

mratsim Aug 30, 2023

einar-taiko Aug 30, 2023

einar-taiko Aug 31, 2023

mratsim Aug 23, 2023

einar-taiko Aug 24, 2023

mratsim Aug 23, 2023

einar-taiko Aug 23, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

mratsim Aug 23, 2023

mratsim commented Aug 29, 2023

einar/pr/extended.jacobian.coordinates #1

Are you sure you want to change the base?

einar/pr/extended.jacobian.coordinates #1

Conversation

einar-taiko commented Aug 21, 2023

mratsim commented Aug 22, 2023

Choose a reason for hiding this comment

mratsim left a comment

Choose a reason for hiding this comment

mratsim Aug 23, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

mratsim commented Aug 29, 2023

mratsim Aug 23, 2023 •

edited

Loading