BIP327: reduce nonces robustly to avoid failure condition #1508

1. 
   conduition commented at 8:29 pm on October 25, 2023: none

   Affects the draft BIP 0327.

   This is not ready for merging yet; we would still need to update the reference implementation and test vectors to match. I’m opening this PR as a suggestion to get consensus before going to such effort.

   The secret nonces $k_1$ and $k_2$ are currently generated by reducing $H(…) \mod n$ and failing if the result is zero.

   We could instead reduce them to a non-zero scalar in $[1, n)$ every time by reducing mod $n-1$ and incrementing.

2. reduce nonces robustly to avoid failure condition a33d513ba5
3. conduition renamed this:
   reduce nonces robustly to avoid failure condition
   BIP327: reduce nonces robustly to avoid failure condition
   on Oct 25, 2023
4. 
   jonasnick commented at 2:56 pm on October 26, 2023: contributor

   I think this idea can make sense in theory. But at most it’s a tiny improvement and I don’t think it’s worth changing the BIP for that.

   Also, I don’t think this change makes sense in practice. Many secp256k1 implementations have specialized scalar arithmetic mod n and not mod n-1. Adding this would introduce more complexity than checking whether the ks are 0.

5. 
   real-or-random commented at 4:51 pm on October 26, 2023: contributor

   @conduition Is the only goal to avoid the failure case? That one here can only be reached with negligible probability, so it’s not a problem. I agree that such failure cases are somewhat annoying in practice, e.g., for testing and code coverage.

   But in this case, I agree with what @jonasnick said:

   Also, I don’t think this change makes sense in practice. Many secp256k1 implementations have specialized scalar arithmetic mod n and not mod n-1. Adding this would introduce more complexity than checking whether the ks are 0.

   If you really need to avoid the failure case in practice, there are simpler ways than reducing mod n-1, e.g., if k_i = 0 then k_i = 1 will avoid zeros.

6. 
   conduition commented at 1:02 am on October 27, 2023: none

   Many secp256k1 implementations have specialized scalar arithmetic mod n and not mod n-1.

   Fair point, I hadn’t considered that.

   Is the only goal to avoid the failure case?

   Yup exactly right. It’d be nice if nonce generation didn’t require any potential failure paths. Since it’s practically impossible already, I figure we might want to remove it completely.

   Sounds like this concept isn’t worth changing the BIP for so I’ll close :+1:

7. conduition closed this on Oct 27, 2023

   ---

8. conduition deleted the branch on Oct 27, 2023

Contributors
conduition jonasnick real-or-random