Availability of variable time multiplications?

[randombit]

For certain operations - especially verification of ZK proofs - being able to compute linear combinations (ala lincomb from k256) of points as quickly as possible is important, and as the inputs are anyway public it is safe to use variable time computation.

Any interest in adding support for eg lincomb_vartime to the relevant traits? The baseline version could of course just call the constant time code. For actually optimized implementations, I'm primarily interested in k256 and to a lesser extent p256. I could start working on PRs if there is some chance of acceptance.

Obviously it's a footgun, but I'd personally argue if you're working directly with elliptic curve points you are already well into you-better-know-what-you-are-doing territory.

[tarcieri]

We've long been hoping to be able to use the wNAF implementation from the group crate for variable-time scalar multiplication, though it's blocked on this PR: zkcrypto/group#46

I'd be fine with futureproofing traits like LinearCombination with *_vartime methods with a default impl that just calls the constant-time version. We did that for inversions and it ended up working out.

[randombit]

To start I opened a PR adding lincomb_vartime to the trait in RustCrypto/traits#2286 that defaults to just using lincomb, not sure if more is needed there but happy to make whatever changes are required.

[tarcieri]

Yeah that's fine

[randombit]

Re zkcrypto/group it's not so clear to me what is required to move things forward. If there is something that I could do, I'd do it - but would need some hints. Otherwise, any possibility of accepting an interim variable time MSM without using the machinery from zkcrypto/group? Pippeneger's is usually pretty simple to implement, for instance [*]

[*] Though probably non-optimal for k256 in particular considering the availability of the endomorphism, I don't know what the best approach is there but I'd imagine there is a lot of prior art

[tarcieri]

I might take a look at that group PR. There's a bunch of feedback that needs addressed.

Though probably non-optimal for k256 in particular considering the availability of the endomorphism, I don't know what the best approach is there but I'd imagine there is a lot of prior art

Here's what libsecp256k1 does:

https://github.com/bitcoin-core/secp256k1/blob/1d146ac3edd47a6ea10669a18cae62171a8e35c6/README.md?plain=1#L52

Point multiplication for verification (aP + bG).

• Use wNAF notation for point multiplicands.
• Use a much larger window for multiples of G, using precomputed multiples.
• Use Shamir's trick to do the multiplication with the public key and the generator simultaneously.
• Use secp256k1's efficiently-computable endomorphism to split the P multiplicand into 2 half-sized ones.

I think we're going to get the most bang for our buck if we get wNAF working.

[tarcieri]

This should address at least part of what was missing from the group PR, I believe: zkcrypto/group#72

This should be all of the feedback addressed, although I'm not sure that it's actually working since I need to test it out with a specific (curve) group implementation: zkcrypto/group#73

[tarcieri]

I attempted to use group::Wnaf but encountered seemingly miscomputed results, which are unchanged regardless of the above PRs: https://github.com/RustCrypto/elliptic-curves/tree/wnaf

I get the following test failures:

thread 'wnaf' (20460986) panicked at p256/tests/projective.rs:48:9:
assertion `left == right` failed
  left: [155, 191, 6, 218, 217, 171, 89, 5, 224, 84, 113, 206, 22, 213, 34, 44, 137, 194, 202, 163, 159, 38, 38, 122, 192, 116, 113, 41, 136, 95, 189, 68]
 right: [107, 23, 209, 242, 225, 44, 66, 71, 248, 188, 230, 229, 99, 164, 64, 242, 119, 3, 125, 129, 45, 235, 51, 160, 244, 161, 57, 69, 216, 152, 194, 150]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- wnaf_proptest stdout ----
proptest: FileFailurePersistence::SourceParallel set, but failed to find lib.rs or main.rs

thread 'wnaf_proptest' (20460987) panicked at p256/tests/projective.rs:77:1:
Test failed: assertion failed: `(left == right)`
  left: `AffinePoint { x: FieldElement(0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296), y: FieldElement(0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5), infinity: 0 }`,
 right: `AffinePoint { x: FieldElement(0x9BBF06DAD9AB5905E05471CE16D5222C89C2CAA39F26267AC0747129885FBD44), y: FieldElement(0x1BCC7FA84DE120A36755DAF30A6F47E8C0D4BDDC15036ED2A3447DFA7A1D3E88), infinity: 0 }` at p256/tests/projective.rs:86.
minimal failing input: point = ProjectivePoint {
    x: FieldElement(0x823CD15F6DD3C71933565064513A6B2BD183E554C6A08622F713EBBBFACE98BE),
    y: FieldElement(0x55DF5D5850F47BAD82149139979369FE498A9022A412B5E0BEDD2CFC21C3ED91),
    z: FieldElement(0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5),
}, scalar = Scalar(0x0000000000000000000000000000000000000000000000000000000000000001)
	successes: 0
	local rejects: 0
	global rejects: 0

cc @str4d

[tob-scott-a]

Proposed fix in #1689

[tarcieri]

We could probably use some traits and/or inherent methods similar to the ones in curve25519-dalek which wrap up various wNAF patterns like basepoint multiplication combined with variable-base scalar multiplication, and can use wNAF when the alloc feature is available while falling back on constant-time linear combinations when it is not.

See #1701 which could benefit from something like dalek's EdwardsPoint::vartime_double_scalar_mul_basepoint.

We can also expose the raw wNAF API, but for something like basepoint APIs it would be nice if they worked like BasepointTable and could lazily initialize a wNAF context around the basepoint in a const fn which can be bound to a constant (where elliptic-curve is providing an abstraction around the lazy locking happening behind the scenes)

[tarcieri]

As of #1714 I now have preliminary wNAF support available. It should be possible to use it to optimize lincomb_vartime when the alloc feature is enabled, but it would be good to double check the performance improvements with benchmarks as well.

It would also be good to have a trait analogous to curve25519-dalek's VartimePrecomputedMultiscalarMul which can use a precomputed wNAF context for the basepoint when the alloc feature is available, and can be used to implement the signature verification optimization mentioned above re: #1701.

I can open a separate issue on the traits repo for that.

[tarcieri]

This PR adds a VartimeBasepointTable type similar to the BasepointTable type which we can bind to constants in various crates: RustCrypto/traits#2374

I also opened an issue for adding traits to expose it: RustCrypto/traits#2375

[tarcieri]

Another update:

• MulVartime trait: elliptic-curve: add ops::MulVartime trait and bound Scalar traits#2379
• MulByGeneratorVartime trait: elliptic-curve: add MulByGeneratorVartime trait traits#2381

The latter includes a mul_by_generator_and_mul_add_point_vartime method for computing aG + bB.

Note that I haven't actually wired up wNAF for these yet, but this provides an API that always works where it will be possible to opportunistically use wNAF when alloc is available and opportunistically use the basepoint tables when the corresponding crate feature is enabled.

[tarcieri]

#1722 wired up wNAF for the MulVartime impls in primeorder when the alloc feature is available. In p256 this resulted in ~14% performance improvement.

I have some bad news for k256 though. When I tried to wire it up:

high-level operations/point-scalar mul (variable-time)
                        time:   [45.005 µs 45.223 µs 45.495 µs]
                        change: [+21.943% +22.999% +24.075%] (p = 0.00 < 0.05)
                        Performance has regressed.

My best guess is the endomorphism-optimized constant time scalar multiplication implementation in k256 is beating the non-endomorphism-accelerated generic wNAF implementation.

I ran the benchmarks of the libsecp256k1 C library to compare numbers on the same hardware, where the constant-time scalar multiplication implementation in k256 is ~37 µs for comparison:

Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)

ecmult_gen                    ,    11.4       ,    11.6       ,    12.4
ecmult_const                  ,    25.7       ,    25.9       ,    26.2
ecmult_const_xonly            ,    28.5       ,    28.6       ,    28.8
ecmult_1p                     ,    20.7       ,    20.9       ,    21.0
ecmult_0p_g                   ,    14.6       ,    14.8       ,    15.0
ecmult_1p_g                   ,    12.2       ,    12.3       ,    12.8
ecmult_multi_0p_g             ,    14.6       ,    14.7       ,    14.8
ecmult_multi_1p_g             ,    12.3       ,    12.3       ,    12.4
ecmult_multi_2p_g             ,    11.5       ,    11.6       ,    11.7

The *const* are the constant-time implementations, where their constant-time scalar multiply is ~30% faster than ours.

The one to compare a MulVartime impl to above is ecmult_1p I believe, where it's ~20% faster than the constant-time implementation.

To get a similar speedup over the constant-time implementation in k256, I believe the implementation of wNAF would need to be endomorphism-optimized as it is in the libsecp256k1 C library. That would effectively involve k256 providing its own implementation of wNAF and using it behind the scenes to optimize MulVartime and linear combinations.

cc @fjarri

Edit: I made a separate tracking issue for this: #1725

Edit again: here's a feature request for linear combinations / sum-of-products multiscalar multiplications in group: zkcrypto/group#75

[tarcieri]

I implemented support for variable-time linear combinations in #1758 which uses a wNAF multiscalar multiplication I added in RustCrypto/group#14.

RustCrypto/traits#2405 adds initial support for computing linear combinations in variable-time using a precomputed wNAF basepoint table, and #1759 wires it up for ECDSA verification, resulting in a 25% speedup.