From b6b0715c2864abcfb9bdda81593f29c35dd1473f Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Wed, 26 Aug 2020 15:56:23 -0700 Subject: Clarify that Jacobian coordinates are the optimization, not the Legendre symbol --- bip-0340.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'bip-0340.mediawiki') diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index afd71b0..9502a69 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -80,7 +80,7 @@ Using the first option would be slightly more efficient for verification (around # Implicitly choosing the Y coordinate that is evenSince ''p'' is odd, negation modulo ''p'' will map even numbers to odd numbers and the other way around. This means that for a valid X coordinate, one of the corresponding Y coordinates will be even, and the other will be odd.. # Implicitly choosing the Y coordinate that is a quadratic residue (i.e. has a square root modulo ''p''). -The second option offers the greatest compatibility with existing key generation systems, where the standard 33-byte compressed public key format consists of a byte indicating the oddness of the Y coordinate, plus the full X coordinate. To avoid gratuitous incompatibilities, we pick that option for ''P'', and thus our X-only public keys become equivalent to a compressed public key that is the X-only key prefixed by the byte 0x02. For consistency, the same is done for ''R''An earlier version of this draft used the third option instead, based on a belief that this would in general trade signing efficiency for verification efficiency. Determining if a Y coordinate is a quadratic residue can be done by computing the Legendre symbol directly in Jacobian coordinates (a common optimization), while determining oddness needs a conversion to affine coordinates first, which needs a modular inversion. As modular inverses and Legendre symbols have similar [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-August/018081.html performance] in practice, this trade-off is not worth it.. +The second option offers the greatest compatibility with existing key generation systems, where the standard 33-byte compressed public key format consists of a byte indicating the oddness of the Y coordinate, plus the full X coordinate. To avoid gratuitous incompatibilities, we pick that option for ''P'', and thus our X-only public keys become equivalent to a compressed public key that is the X-only key prefixed by the byte 0x02. For consistency, the same is done for ''R''An earlier version of this draft used the third option instead, based on a belief that this would in general trade signing efficiency for verification efficiency. When using Jacobian coordinates, a common optimization in ECC implementations, it is possible to determine if a Y coordinate is a quadratic residue by computing the Legendre symbol, without converting to affine coordinates first (which needs a modular inversion). As modular inverses and Legendre symbols have similar [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-August/018081.html performance] in practice, this trade-off is not worth it.. Despite halving the size of the set of valid public keys, implicit Y coordinates are not a reduction in security. Informally, if a fast algorithm existed to compute the discrete logarithm of an X-only public key, then it could also be used to compute the discrete logarithm of a full public key: apply it to the X coordinate, and then optionally negate the result. This shows that breaking an X-only public key can be at most a small constant term faster than breaking a full one.This can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is odd. A proof sketch can be found [https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 here].. -- cgit v1.2.3