[bitcoin-dev] 32-byte public keys in Schnorr and Taproot

From: Pieter Wuille <pieter.wuille@gmail•com>
To: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] 32-byte public keys in Schnorr and Taproot
Date: Fri, 9 Aug 2019 11:16:29 -0700	[thread overview]
Message-ID: <CAPg+sBhDQ5yS-BemRWqSxV7TJaWNFs7d-zD6p5HtquFwUjDdsg@mail.gmail.com> (raw)

Hello all,

It has been suggested [1] to drop the Y oddness bit in the witness
program for Taproot outputs. This seems like a worthwhile change, as:
* The bit doesn't actually contribute to security.
* It avoids Taproot outputs from being more expensive to create than v0 P2WSH.
* It doesn't preclude future changes that would still need the
additional byte anyway.

In exploring that option, Jonas Nick found that it seems cleanest [2]
to actually introduce a type of 32-byte public keys (which implicitly
have an even Y coordinate) in bip-schnorr, with associated signing and
verification logic that are distinct from the 33-byte variant.

This makes me wonder if we need 33-byte public keys at all.

So I'd like to hear opinions about modifying bip-schnorr to only
define 32-byte public keys. The implications of that would be:
* bip-schnorr public keys wouldn't be exactly the same as ECDSA public
keys, however all derivation logic would still apply (BIP32,
mnemonics, xpubs, ... would still exist and be compatible - just the
first pubkey byte would be dropped at the end).
* The Q point in bip-taproot (the one going in the scriptPubKey) would
just follow the 32-byte pubkey encoding, rather than needing a 33rd
byte.
* The P point in bip-taproot (the internal key revealed during script
path) would become just a 32-byte public key (and we can drop the one
bit in the control block to transmit the oddness of the Y coordinate
of P).
* In order to permit batch verification of the P to Q tweaking for
script-path spending, another control block bit is now needed, namely
one that indicates whether a negation was needed to make P+H(P||m)*G's
Y coordinate even.
* All public keys inside bip-tapscript would also become 32-bytes. If
desired, the "upgradable public key" construction in bip-tapscript can
be kept, by triggering based on the length of public keys (rather than
based on their first byte).

One question is whether it's worth such a change to bip-schnorr at
this point. We've purposefully never progressed it past draft since
publishing [3], but it has been a while. If necessary, it's possible
to keep verification compatible by still hashing the implied "even"
byte inside the scheme (which commits to the pubkey), but if we're
going to change things, it's perhaps best to do it as cleanly as
possible and also drop that byte.

Opinions?

  [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016943.html
  [2] https://github.com/sipa/bips/pull/52
  [3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html

Cheers,

-- 
Pieter