Skip to content

Conversation

@yelhousni
Copy link
Contributor

@yelhousni yelhousni commented Jun 16, 2023

I was trying to have a ScalarMul() circuit with only additions and no doublings. Ultimately, I could make the circuit work with less constraints than the previous right-to-left double-and-add circuit. So I looked in the literature to check if it was previously known and I found that Marc Joye of course did it in 2007 😅
So this PR corresponds actually to Alg.2 of [CHES:Joye07] with some tweaks to make it work efficiently in-circuit:

  • select-logic with an additional register;
  • isolate first iteration and use [ELM02] triple() method;
  • isolate last iteration and discard R1 and R2 computations.

Now when we use this new method in precompiles it saves:

  • ECRECOVER:
    • 17 609 r1cs
    • 111 590 scs
  • ECMUL:
    • 22 997 r1cs
    • 124 945 scs

P.S.: We can ditch the old ScalarMul() and replace it with the new ScalarMulAddOnly() once the PR is reviewed.

@yelhousni yelhousni added type: perf dep: linea Issues affecting Linea downstream labels Jun 16, 2023
@yelhousni yelhousni added this to the v0.9.0 milestone Jun 16, 2023
@yelhousni yelhousni requested a review from ivokub June 16, 2023 15:42
Copy link
Collaborator

@ivokub ivokub left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The table-free windowubg in JointScalarMulBase was difficult to follow but seems correct (two selects in a row thing...).

I'm not sure about name ScalarMulAddOnly, but really cannot suggest anything more succincit (maybe ScalarMulWithAdds, but it still is very long).

@ivokub
Copy link
Collaborator

ivokub commented Jun 23, 2023

The table-free windowubg in JointScalarMulBase was difficult to follow but seems correct (two selects in a row thing...).

I'm not sure about name ScalarMulAddOnly, but really cannot suggest anything more succincit (maybe ScalarMulWithAdds, but it still is very long).

Oh, we can ditch old ScalarMul and replace with it. Yup, makes also sense. But leave it in comments just in case, maybe is useful in the future, so is good to have close :)

@yelhousni yelhousni merged commit 5f2979f into develop Jul 4, 2023
@yelhousni yelhousni deleted the emulated/scalarMul branch July 4, 2023 11:08
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

dep: linea Issues affecting Linea downstream type: perf

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants