Deterministic r value in transaction signatures

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: vjudeu on October 01, 2021, 02:33:06 AM

Quote

if k is not random (is known)

Why k is known if it is calculated as a combination of known and unknown value?

If k is correctly computed using a good algorithm and at least one strong source of entropy then it will be random hence unknown.
Keep in mind that r value is simply k multiplied by the curve generator (R=k*G & r=R_x).

Quote from: vjudeu on October 01, 2021, 02:33:06 AM

So if we can derive keys in HD wallets, why not derive r values in a similar way with different derivation path?

Because the key may not have been derived from a BIP-32 seed and the signer may not even have BIP-32 implemented. Also it is not wise to use the key that can be generated by the wallet at a different derivation path as k.
With that said, the algorithm for BIP-32 and RFC-6979 are somewhat similar, they both use an initial entropy and use HMAC-SHA2 internally.

Quote from: vjudeu on October 01, 2021, 02:33:06 AM

Then, for backward compatibility r values could be present in all transactions, but could be skipped and calculated on-the-fly by all new nodes in all cases where deterministic r matches r-value used in signature.

R values are present in all transactions that have a signature and the nodes don't compute it and don't know or care how it was generated (whether using an RNG or deterministic doesn't matter).

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: vjudeu on October 01, 2021, 01:04:28 AM

Private keys "k" have to remain hidden

I think we should start adopting a vocabulary specified for these things to avoid any confusion. The k value isn't the private key, but d which are uncorrelated. Unless you mean that it's another private key and r another public key.

So, I repeat; d is your private key and dG your public key, while k another random number (not a private key in which you can unlock outputs!) and r another public key (kG).

Quote from: vjudeu on October 01, 2021, 01:04:28 AM

Why random "r" values are needed in signatures?

Each signature has to have a different r value each time to avoid being one equation away of finding k. Specifically, you're that far if you reuse k and hence, r:

Code:

k = (z_1 - z_2) * (s_1 - s_2)^-1 mod n

Quote from: vjudeu on October 01, 2021, 02:33:06 AM

Why k is known if it is calculated as a combination of known and unknown value?

He probably meant if it's generated with a flawed RNG. With RFC-6979 it's generated as you say, but if each time you had to use your RNG to generate another k, it'd be a matter of your RNG's strength.

Quote from: vjudeu on October 01, 2021, 02:33:06 AM

So if we can derive keys in HD wallets, why not derive r values in a similar way with different derivation path?

Isn't RFC-6979 for this? Each time you sign a new transaction, the k value is a hash of d plus the transaction data unless I'm missing something. The r value isn't supposed to be generated at all; as said, it's a point on the curve calculated from k times G.

vjudeu

copper member

Activity: 906

Merit: 2258

Quote

if k is not random (is known)

Why k is known if it is calculated as a combination of known and unknown value?

Quote

That's not how deterministic key derivation works.

Good point, I forgot about key derivation. So if we can derive keys in HD wallets, why not derive r values in a similar way with different derivation path? Then, for backward compatibility r values could be present in all transactions, but could be skipped and calculated on-the-fly by all new nodes in all cases where deterministic r matches r-value used in signature.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: vjudeu on October 01, 2021, 01:04:28 AM

Why random "r" values are needed in signatures?

Because r is computed from k and if k is not random (is known) the ECDSA math ensures that private key can be computed (s = k⁻¹(e + rd_U) mod n becomes 1 equation with 1 unknown variable d_U).

Quote from: vjudeu on October 01, 2021, 01:04:28 AM

for example by adding transaction hash to the public key,

That's not how deterministic key derivation works. If you want to derive a random key you still have to use a random entropy that is why the private key is used in the KDF (such as RFC-6979) with other things to derive k not public key.

Also key derivation is not a simple reversible operation such as "addition", it always involves an irreversible operation such as hashing.
For example RFC-6979 used in bitcoin computes at least 5 HMAC-SHA256 hashes to return k, or the new one used in Schnorr signatures uses Tagged-SHA256 hashes.

vjudeu

copper member

Activity: 906

Merit: 2258

Why random "r" values are needed in signatures? Private keys "k" have to remain hidden, but it can be done with deterministic "r" as well, for example by adding transaction hash to the public key, in this way we could have "s=(z+((z+d)*G.x)d)/k", where "r=(z*G)+(d*G)", so it can be computed by anyone.

Topic: Deterministic r value in transaction signatures (Read 122 times)