Use modified divsteps with initial delta=1/2 for constant-time #906

sipa commented at 3:32 AM on March 19, 2021: contributor

This updates the divsteps-based modular inverse code to use the modified version which starts with delta=1/2. For variable time, the delta=1 variant is still used as it appears to be faster.

See https://github.com/sipa/safegcd-bounds/tree/master/coq and https://medium.com/blockstream/a-formal-proof-of-safegcd-bounds-695e1735a348 for a proof of correctness of this variant.

TODO:

Update unit tests to include edge cases specific to this variant

I'm still running the Coq proof verification for the 590 bound in non-native mode. It's unclear how long this will take.

real-or-random commented at 8:43 AM on March 19, 2021: contributor

Concept ACK

There's still this comment and the corresponding code: /* Bounds on eta that follow from the bounds on iteration count (max 12*62 divsteps). */

The docs and the code might be more readable without eta having two different meanings. Maybe try another name for the new eta?

sipa force-pushed on Mar 19, 2021

sipa commented at 6:59 PM on March 19, 2021: contributor

There's still this comment and the corresponding code: /* Bounds on eta that follow from the bounds on iteration count (max 12*62 divsteps). */

Fixed. There was an equivalent in modinv32 as well.

The docs and the code might be more readable without eta having two different meanings. Maybe try another name for the new eta?

Renamed to zeta.

roconnor-blockstream commented at 3:34 PM on March 24, 2021: contributor

FWIW I don't believe that it is necessary to wait for the Coq proof checked in "paranoid mode" to complete. OTOH, I estimate the check will probably be completed before this gets merged anyways, so it doesn't really matter.

Edit: (23 days later) I no longer believe the check will be completed before this gets merged.

real-or-random commented at 8:23 AM on March 26, 2021: contributor

@sipa Is this ready for review?

sipa commented at 8:28 AM on March 26, 2021: contributor

@real-or-random I plan to add some more unit tests, but otherwise yes.

sipa force-pushed on Mar 29, 2021

sipa commented at 4:42 AM on March 29, 2021: contributor

This PR is ready, I think.

coqc is still running:

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND                                                                                 
25511 pw        20   0   10.6g  10.4g    204 R 100.0  88.6  59500:51 coqc

sipa force-pushed on Mar 29, 2021

sipa force-pushed on Apr 1, 2021

sipa commented at 8:33 PM on April 1, 2021: contributor

Added a selection of randomly generated inputs (with generic modulus, and for field/scalar) as tests that trigger the largest/smallest d and e values at various points during the execution over a few billion runs.

sipa cross-referenced this on Apr 2, 2021 from issue Update libsecp256k1 subtree to latest master by sipa

sipa commented at 10:30 PM on April 12, 2021: contributor

Update: coqc has been running for 8 weeks.

real-or-random commented at 10:02 AM on April 13, 2021: contributor

Hm, I think I'm in favor of not waiting any longer for Coq... We have the bounds analysis plus the Coq proof in native mode. This should be more than enough to be confident in the algorithm.

I'll try to review this soon.

in doc/safegcd_implementation.md:553 in 0ca692f553 outdated

 548 | @@ -535,7 +549,8 @@ other cases, it slows down calculations unnecessarily. In this section, we will
 549 |  faster non-constant time `divsteps_n_matrix` function.
 550 |  
 551 |  To do so, first consider yet another way of writing the inner loop of divstep operations in
 552 | -`gcd` from section 1. This decomposition is also explained in the paper in section 8.2.
 553 | +`gcd` from section 1. This decomposition is also explained in the paper in section 8.2. We use
 554 | +the original version with initial *&delta;=1* and *&eta;=-&delta;*here.

real-or-random commented at 11:25 AM on April 13, 2021:

the original version with initial *&delta;=1* and *&eta;=-&delta;* here.

sipa commented at 7:00 PM on April 13, 2021:

Done.

real-or-random commented at 11:26 AM on April 13, 2021: contributor

ACK mod nit

Fix typo in explanation 376ca366db

Use modified divsteps with initial delta=1/2 for constant-time

Instead of using eta=-delta, use zeta=-(delta+1/2) to represent
delta. This variant only needs at most 590 iterations for 256-bit
inputs rather than 724 (by convex hull bounds analysis).

277b224b6a

Optimization: only do 59 hddivsteps per iteration instead of 62 cd393ce228

Add unit tests for edge cases with delta=1/2 variant of divsteps be0609fd54

sipa force-pushed on Apr 13, 2021

real-or-random approved

real-or-random commented at 2:04 PM on April 15, 2021: contributor

ACK be0609fd54af95a15b76cea150e6907d581318dd careful code review and some testing

roconnor-blockstream commented at 5:59 PM on April 15, 2021: contributor

I'm not really planning to review this PR myself at this time. But I do ACK the 590 constant. I have actually very carefully reviewed those three digits.

gmaxwell commented at 6:30 PM on April 15, 2021: contributor

ACK be0609fd54af95a15b76cea150e6907d581318dd

sanket1729 commented at 1:21 AM on April 22, 2021: none

crACK be0609fd54af95a15b76cea150e6907d581318dd

real-or-random merged this on Apr 22, 2021

real-or-random closed this on Apr 22, 2021

sipa commented at 7:21 PM on April 23, 2021: contributor

Posthumous update: the paranoid-mode Coq proof finished succesfully 3 hours before this got merged.

roconnor-blockstream commented at 7:24 PM on April 23, 2021: contributor

For the record, the Coq runtime in paranoid-mode ended up being approximately 66 days.

jonasnick cross-referenced this on Jun 14, 2021 from issue Upstream PRs 831, 907, 903, 889, 918, 906, 928, 922, 933, Merge bitcoin-core/secp256k1#936: Fix gen_context/ASM build on ARM, 925, 937, 926, Merge bitcoin-core/secp256k1#940: contrib: Explain explicit header guards, 850, 930, 941, 846, 947, 662, 950 by jonasnick