search

sipa / bips

Bitcoin Improvement Proposals
bitcoin.org
145 stars 43 forks source link

bip-taproot: Publick key tweak resulting in point-at-infinity #168

Closed dr-orlovsky closed 4 years ago

dr-orlovsky commented 4 years ago

It is known, that with a very small chances, a public key tweaking may fail due to the fact that addition of some tweaking factor multiplied by generator to an existing public key may result in the special elliptic curve point "infinity". This is already covered by the possibility for libsecp256k1 to return a failure (non-1 value) from theecp256k1_ec_pubkey_tweak_add function: https://github.com/bitcoin-core/secp256k1/blob/e541a90ef6461007d9c6a74b9f9a7fb8aa34aaa8/src/secp256k1.c#L596. Also, the function theoretically may fail b/c the tweaking factor exceeds the elliptic curve field order, however this fact is, according to https://github.com/bitcoin-core/secp256k1/blob/137d304a6bf419bbbafd70d1dbdb2162354d71b7/src/scalar_low_impl.h#L58, always ignored.

Anyway, if the function may deterministicaly fail for a given tweak (i.e. resulting hash from some input data, added *G to the intermediate public key) the specification should encounter for the possible reaction to the case. If you ok, I can work on the PR covering this.

elichai commented 4 years ago

Not sure about documenting, but unlike tweak_add which you can easily pass the inversion of the point. Here to commitment includes the point you're adding to, so you can't manufacture an inversion. And assuming SHA256 is random then the probability of that happening is 1 over the group order

dr-orlovsky commented 4 years ago

I do not see that this tweak function does it. It usually happens inside the function that utilizes this one for the actual commitment procedure.

elichai commented 4 years ago

As you can see there's an if, it can definitely fail.

https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c#L596

https://github.com/bitcoin-core/secp256k1/blob/master/src/eckey_impl.h#L63

dr-orlovsky commented 4 years ago

My comment was related to this:

Here to commitment includes the point you're adding to, so you can't manufacture an inversion.

meaning that the ecp256k1_ec_pubkey_tweak_add does not commit to the original untweaked value of the public key (which, as far as I have understood, is what you meant in your comment).

Thanks for the links, I have figured out that also b/c of Sipa comment here: https://github.com/bitcoin-core/secp256k1/issues/697

sipa commented 4 years ago

Is this resolved?