Code duplication between `reddsa` and `redjubjub`

[mpguerra]

Details

The redjubjub crate implements the RedDSA signature scheme over the Jubjub curve. The reddsa crate mostly subsumes that task and provides RedDSA support for both the Jubjub and Pallas curves; the migration of the code from redjubjub to reddsa, and its generalization to unify support over distinct elliptic curves, are currently in an incomplete state, resulting in some code duplication. Thus, there are currently (at least) three mostly identical implementations of the multiplication of a curve point by a scalar with the w-NAF method, in redjubjub/src/scalar_mul.rs, reddsa/src/scalar_mul.rs, and reddsa/src/orchard.rs. In all three cases, the input scalar is converted to a w-NAF representation over exactly 256 digits:

https://github.com/ZcashFoundation/redjubjub/blob/e19279f70f3999627b4076386848d1956b18560e/src/scalar_mul.rs#L66-L70

https://github.com/ZcashFoundation/reddsa/blob/507dcdf695bbc7eccd5d6b8e3c0d62625a45e4e9/src/scalar_mul.rs#L73-L77

https://github.com/ZcashFoundation/reddsa/blob/507dcdf695bbc7eccd5d6b8e3c0d62625a45e4e9/src/orchard.rs#L90-L94

The w-NAF representation converts an input value x into signed digits, using a window width w (expressed in bits), with the following characteristics:

• Each digit is either zero, or an odd signed integer between -2^w-1 and +2^w-1.
• Between any two non-zero digits, there are at least w digits of value zero.
• n+1 output digits are sufficient to represent all possible x such that 0 ≤ x < 2ⁿ + 2^n-w.

The non_adjacent_form() function requires that the window width w lies between 2 and 8. The use of 256 digits is then slightly wasteful for the Jubjub and Pallas curves, where scalars are lower than the prime (sub)group order of interest:

• Jubjub order is about 2^251.85, and thus needs only 253 digits at most for w-NAF.
• Pallas order is slightly below 2²⁵⁴ + 2^125.1, leading to a maximum w-NAF scalar size of 255 digits.

Since the number of iterations in the multiplication loop is exactly equal to the number of digits, and each iteration includes at least a curve point doubling, then some of these doublings are wasted (they will repeatedly double the initial value of the accumulator point, i.e. the curve identity point). On the other hand, if the non_adjacent_form() and optional_multiscalar_mul() functions are turned into generic functions that handle arbitrary curves whose scalars fit on 32 bytes, then 256 digits are not enough: a curve whose order is greater than 2²⁵⁵ +2²⁴⁷ (e.g. secp256k1, or NIST’s P-256) may need up to 257 digits for its scalars in w-NAF representation.

[teor2345]

Is this resolved by the latest versions of each of these crates?

[teor2345]

Thus, there are currently (at least) three mostly identical implementations of the multiplication of a curve point by a scalar with the w-NAF method, in redjubjub/src/scalar_mul.rs,

As of redjubjub 0.7, the first duplicate implementation has been removed. The duplicates within reddsa still remain.

[upbqdn]

As of redjubjub 0.7, the first duplicate implementation has been removed.

Nitpick: the duplicate implementation was removed in 0.6.

[upbqdn]

The description of the issue says:

Between any two non-zero digits, there are at least w digits of value zero.

I think this statement contains an off-by-one error. The correct number of zero digits should be w-1 since in a w-NAF, at most one of any w consecutive digits is nonzero.

[conradoplg]

The description of the issue says:

Between any two non-zero digits, there are at least w digits of value zero.

I think this statement contains an off-by-one error. The correct number of zero digits should be w-1 since in a w-NAF, at most one of any w consecutive digits is nonzero.

digs out Guide to ECC

You're correct!

[upbqdn]

Sorry, I should have added the full definition right away so others don't have to search for it. I only realized that now.

[mpguerra]

@upbqdn can you please add a size for this issue?

[upbqdn]

Done.