Generator mismatch with bandersnatch implementation and the published paper

[kevaundray]

Summary

The generator point being used is inconsistent with the generator in the bandersnatch paper. This can lead to mismatch with future implementations of bandersnatch that follow the paper.

Version

0.3

Description

The paper https://eprint.iacr.org/2021/1152.pdf on page 6, states that the generator in affine co-ordinates for the Twisted Edwards variant is:

xTE=29c132cc2c0b34c5743711777bbe42f32b79c022ad998465e1e71866a252ae18 yTE=2a6c669eda123e0f157d8b50badcd586358cad81eee464605e3167b6cc974166

In decimal:

xTE=18886178867200960497001835917649091219057080094937609519140440539760939937304 yTE=19188667384257783945677642223292697773471335439753913231509108946878080696678

This differs from the generator being used currently in arkworks: https://github.com/arkworks-rs/curves/blob/master/ed_on_bls12_381_bandersnatch/src/curves/mod.rs#L92

Cause

It was previously the point being used in the reference implementation (not sure how it was generated): https://github.com/asanso/Bandersnatch/blob/a4b844082575e576ab9278edf6ec2dc8719b8507/python-ref-impl/bench.py#L58

However, as stated in the paper, all generators are now deterministically computed by finding the lexicographically smallest valid x-coordinate of a point of the curve, and scaling it by the cofactor 4 such that the result is not the point at infinity

Solution

Change:

#[rustfmt::skip]
const GENERATOR_X: Fq = field_new!(Fq, "29627151942733444043031429156003786749302466371339015363120350521834195802525");
#[rustfmt::skip]
const GENERATOR_Y: Fq = field_new!(Fq, "27488387519748396681411951718153463804682561779047093991696427532072116857978");

To:

#[rustfmt::skip]
const GENERATOR_X: Fq = field_new!(Fq, "18886178867200960497001835917649091219057080094937609519140440539760939937304");
#[rustfmt::skip]
const GENERATOR_Y: Fq = field_new!(Fq, "19188667384257783945677642223292697773471335439753913231509108946878080696678");

Note

This is a breaking change for libraries using bandersnatch in arkworks. However, GitHub searching for "ark-ed-on-bls12-381" returns one crate which is also not in production, so I believe the surface of affected crates will be negligible.

[Pratyush]

@zhenfeizhang is the relevant person to ask, I think

[zhenfeizhang]

This was fixed in https://github.com/arkworks-rs/curves/pull/67/files#diff-b7b37837cb97673dfadb21460e7d8483bf28fc23a3753070af28f32315625afbR108

would love to get more reviews and merged

[Pratyush]

Left a review, looks good modulo the comments. Thanks for the PR!

[Pratyush]

Fixed by #67