This is the first commit from PR 17977 that uses the new functionality and interfaces
in libsecp256k1. You may need to make clean && ./configure && make for the build to
succeed.
Schnorr signatures are a
digital signature scheme that can be constructed over any group where the
discrete log problem is hard. It’s a different signature scheme from ECDSA,
which is used in Bitcoin today, but there are certain similarities between the
two schemes.
We won’t go into the construction of Schnorr signatures or the motivation for
adding them to Bitcoin, but it’d be useful to have a high-level understanding of
those things to motivate why we’re making these changes. BIP
340 explains
both the motivation and the construction of these signatures.
We also won’t go into the implementation of signing and verifying the
signatures themselves. That’s all hidden away inside the libsecp library. The
firsttwo
commits from PR 17977 pull in the required changes to libsecp. If you want to
dig deeper into the implementation, lipsecp PR
558 is where the new
cryptographic code is implemented.
Instead, we’re going to look at the new interface provided by libsecp for
verifying Schnorr signatures, and how it’s integrated into Bitcoin Core.
The first thing to note about the Schnorr signature interface is that
pubkeys in
BIP340
are 32 bytes. That’s unlike pubkeys in our ECDSA implementation,
which are 33 or 65 bytes (depending on whether they’re compressed or
uncompressed). BIP 340 public keys can be 32 bytes because the y-value
or the point is implicit. See the Implicit Y coordinates and Public Key
Generation sections of BIP
340 for full
details.
The new XOnlyPubKey object is the lowest-level object we’ll use for signature
validation. It’s constructed with a uint256, and then the function
VerifySchnorr() is called with the 32 bytes hash of the message that was
signed (this hash can sometimes just be called the ‘message’, or in the case of
signing a Bitcoin transaction the ‘sighash’), and the 64 byte signature.
The XOnlyPubKey object is used within a hierarchy of signature checker classes,
which are used by the higher-level code to check signatures:
At the base is
BaseSignatureChecker,
which provides three (virtual) public methods: CheckSig(),
CheckLockTime() and CheckSequence(). This PR adds CheckSchnorrSig().
Above that is
GenericTransactionSignatureChecker
(which is actually a template that’s instantiated as
TransactionSignatureChecker or MutableTransactionSignatureChecker depending
on whether it’s being used with a CTransaction or CMutableTransaction).
GenericTransactionSignatureChecker overrides the virtual CheckSig() and
CheckSchnorrSig() methods with implementations of signature verification.
And above TransactionSignatureChecker is a
CachingTransactionSignatureChecker,
which uses the signature cache (calling
CachingTransactionSignatureChecker::Verify____Signature() more than once on
the same transaction won’t result in the same signatures being validated
multiple times).
<fjahr> The "Implicit Y coordinates" section in BIP340 explains it: Every X coordinate has 2 two Y coordinates. There are different options on how to determine which Y to use but the Y which is a quadratic residue was chosen.
<jnewbery> a public key in elliptic curve cryptography is a point, but because the curve is mirrored in the x-axis, as long as we all agree a scheme to determine which of the 2 possible y values to choose, then we don't actually need to explicitly state which y value we're using
<sipa> i guess this is as good a time to mention this as any: i believe our original reasoning for picking quadratic residue for R was flawed, and we should consider making both use even
<jnewbery> sipa: thanks. Let's focus on Bitcoin Core's use of the signature verification in this meeting, and maybe circle back to the cryptography at the end if we have time
<michaelfolkson> TransactionSignatureChecker, MutableTransacstionSignatureChecker, CacheTransactionSignatureChecker too.... were they derived from Base? (just checking)
<fjahr> 65 bytes includes a different sighash type (not SIGHASH_DEFAULT) in the last byte. It gets stripped and the 64 bytes are used to check sig. If its 64 bytes the default is used automatically. 65 bytes with SIGHASH_DEFAULT is not allowed to protect against malleability.
<willcl_ark> <sipa> pinheadmz: you can do either; have a 64-byte one with implicit sighash 0, or explicitly make a 65-byte sig with hashtype 1; their semantics are the same... but the signature will still differ because the hash commits to the actual hashtype value
<jnewbery> if there's no sighash byte (and the sig is therefore 64 bytes), then the sighash is SIGHASH_DEFAULT, which hashes the same transaction data as SIGHASH_ALL
<jnewbery> you can have SIGHASH_ALL, which is the same transaction data (but the hash also includes the sighash to avoid malleability between SIGHASH_DEFAULT and SIGHASH_ALL)
<fjahr> tx sigs can be evaluated multiple times by a node for example at entry of mempool and when included in a block. with the cache it doesn't have to which si saving computation resources.
<sipa> if there somehow is a collision in the cache's hashing, it would be on an isolated machine, rather than consistently on every node in the network
<thomasb06> for real numbers, the equivalent of quadratic residue is "is the number positive, or negative". If the number is positive, it has a square root. If it's negative, it hasn't. In F_p, half numbers are square roots and half are not. The Legendre symbole says if it does or not.
<gzhao408> script in atmp, we use more flags (e.g. standardness) than when we are validating a block. but what i mean to say is... i feel like it doesn't need to be the exact verify flags?
<michaelfolkson> "The benchmark was repeatedly testing the same constant input, which apparently was around 2.5x faster than the average speed. It is a variable-time algorithm, so a good variation of inputs matters."
<jnewbery> sipa: lots to digest there. My very rudimentary understanding was that to lift an x co-ordinate onto a point, the last step was squaring, so you'd always end with a quadratic residue. Is that relevant here?
<michaelfolkson> For what it is worth I don't think an improvement like this shouldn't be made because it is late in the day. It doesn't have knock on impacts right?
<jnewbery> gzhao408: the flags used for validating are hashed into the cache entry, so it'd be quite a big redesign to make the change you're suggesting