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 MSM for Bandersnatch/wagon and Verkle Tries #415

Open
mratsim opened this issue Jun 29, 2024 · 0 comments
Open

Optimize MSM for Bandersnatch/wagon and Verkle Tries #415

mratsim opened this issue Jun 29, 2024 · 0 comments

Comments

@mratsim
Copy link
Owner

mratsim commented Jun 29, 2024

Followup to #414

There are 3 ways to optimize MSM for the Bander curves

  1. MSM for Bandersnatch and Banderwagon does not use endomorphism acceleration. This is because their endomorphism requires to switch to projective coordinates.
    func computeEndoBander[F](r {.noalias.}: var EC_TwEdw_Prj[F], P: EC_TwEdw_Prj[F]) =
    static: doAssert F.Name in {Bandersnatch, Banderwagon}
    var xy {.noInit.}, yy {.noInit.}, zz {.noInit.}: F
    xy.prod(P.x, P.y)
    yy.square(P.y)
    zz.square(P.z)
    const b = F.fromHex("0x52c9f28b828426a561f00d3a63511a882ea712770d9af4d6ee0f014d172510b4")
    const c = F.fromHex("0x6cc624cf865457c3a97c6efd6c17d1078456abcfff36f4e9515c806cdf650b3d")
    r.x.diff(zz, yy)
    r.x *= c
    zz *= b
    r.y.sum(yy, zz)
    r.y *= b
    r.z.diff(yy, zz)
    r.x *= r.z
    r.y *= xy
    r.z *= xy
  2. We use Projective coordinates but Twisted Extended (X, Y, Z, T) might be noticeably faster (22% according to paper): https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
  3. Implement precomputed tables for fixed CRS for Verkle Tries / IPA:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant