pubkey.cpp raw
1 // Copyright (c) 2009-present The Bitcoin Core developers
2 // Copyright (c) 2017 The Zcash developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6 #include <pubkey.h>
7
8 #include <hash.h>
9 #include <secp256k1.h>
10 #include <secp256k1_ellswift.h>
11 #include <secp256k1_extrakeys.h>
12 #include <secp256k1_recovery.h>
13 #include <secp256k1_schnorrsig.h>
14 #include <span.h>
15 #include <uint256.h>
16 #include <util/strencodings.h>
17
18 #include <algorithm>
19 #include <cassert>
20
21 using namespace util::hex_literals;
22
23 namespace {
24
25 struct Secp256k1SelfTester
26 {
27 Secp256k1SelfTester() {
28 /* Run libsecp256k1 self-test before using the secp256k1_context_static. */
29 secp256k1_selftest();
30 }
31 } SECP256K1_SELFTESTER;
32
33 } // namespace
34
35 /** This function is taken from the libsecp256k1 distribution and implements
36 * DER parsing for ECDSA signatures, while supporting an arbitrary subset of
37 * format violations.
38 *
39 * Supported violations include negative integers, excessive padding, garbage
40 * at the end, and overly long length descriptors. This is safe to use in
41 * Bitcoin because since the activation of BIP66, signatures are verified to be
42 * strict DER before being passed to this module, and we know it supports all
43 * violations present in the blockchain before that point.
44 */
45 int ecdsa_signature_parse_der_lax(secp256k1_ecdsa_signature* sig, const unsigned char *input, size_t inputlen) {
46 size_t rpos, rlen, spos, slen;
47 size_t pos = 0;
48 size_t lenbyte;
49 unsigned char tmpsig[64] = {0};
50 int overflow = 0;
51
52 /* Hack to initialize sig with a correctly-parsed but invalid signature. */
53 secp256k1_ecdsa_signature_parse_compact(secp256k1_context_static, sig, tmpsig);
54
55 /* Sequence tag byte */
56 if (pos == inputlen || input[pos] != 0x30) {
57 return 0;
58 }
59 pos++;
60
61 /* Sequence length bytes */
62 if (pos == inputlen) {
63 return 0;
64 }
65 lenbyte = input[pos++];
66 if (lenbyte & 0x80) {
67 lenbyte -= 0x80;
68 if (lenbyte > inputlen - pos) {
69 return 0;
70 }
71 pos += lenbyte;
72 }
73
74 /* Integer tag byte for R */
75 if (pos == inputlen || input[pos] != 0x02) {
76 return 0;
77 }
78 pos++;
79
80 /* Integer length for R */
81 if (pos == inputlen) {
82 return 0;
83 }
84 lenbyte = input[pos++];
85 if (lenbyte & 0x80) {
86 lenbyte -= 0x80;
87 if (lenbyte > inputlen - pos) {
88 return 0;
89 }
90 while (lenbyte > 0 && input[pos] == 0) {
91 pos++;
92 lenbyte--;
93 }
94 static_assert(sizeof(size_t) >= 4, "size_t too small");
95 if (lenbyte >= 4) {
96 return 0;
97 }
98 rlen = 0;
99 while (lenbyte > 0) {
100 rlen = (rlen << 8) + input[pos];
101 pos++;
102 lenbyte--;
103 }
104 } else {
105 rlen = lenbyte;
106 }
107 if (rlen > inputlen - pos) {
108 return 0;
109 }
110 rpos = pos;
111 pos += rlen;
112
113 /* Integer tag byte for S */
114 if (pos == inputlen || input[pos] != 0x02) {
115 return 0;
116 }
117 pos++;
118
119 /* Integer length for S */
120 if (pos == inputlen) {
121 return 0;
122 }
123 lenbyte = input[pos++];
124 if (lenbyte & 0x80) {
125 lenbyte -= 0x80;
126 if (lenbyte > inputlen - pos) {
127 return 0;
128 }
129 while (lenbyte > 0 && input[pos] == 0) {
130 pos++;
131 lenbyte--;
132 }
133 static_assert(sizeof(size_t) >= 4, "size_t too small");
134 if (lenbyte >= 4) {
135 return 0;
136 }
137 slen = 0;
138 while (lenbyte > 0) {
139 slen = (slen << 8) + input[pos];
140 pos++;
141 lenbyte--;
142 }
143 } else {
144 slen = lenbyte;
145 }
146 if (slen > inputlen - pos) {
147 return 0;
148 }
149 spos = pos;
150
151 /* Ignore leading zeroes in R */
152 while (rlen > 0 && input[rpos] == 0) {
153 rlen--;
154 rpos++;
155 }
156 /* Copy R value */
157 if (rlen > 32) {
158 overflow = 1;
159 } else {
160 memcpy(tmpsig + 32 - rlen, input + rpos, rlen);
161 }
162
163 /* Ignore leading zeroes in S */
164 while (slen > 0 && input[spos] == 0) {
165 slen--;
166 spos++;
167 }
168 /* Copy S value */
169 if (slen > 32) {
170 overflow = 1;
171 } else {
172 memcpy(tmpsig + 64 - slen, input + spos, slen);
173 }
174
175 if (!overflow) {
176 overflow = !secp256k1_ecdsa_signature_parse_compact(secp256k1_context_static, sig, tmpsig);
177 }
178 if (overflow) {
179 /* Overwrite the result again with a correctly-parsed but invalid
180 signature if parsing failed. */
181 memset(tmpsig, 0, 64);
182 secp256k1_ecdsa_signature_parse_compact(secp256k1_context_static, sig, tmpsig);
183 }
184 return 1;
185 }
186
187 /** Nothing Up My Sleeve (NUMS) point
188 *
189 * NUMS_H is a point with an unknown discrete logarithm, constructed by taking the sha256 of 'g'
190 * (uncompressed encoding), which happens to be a point on the curve.
191 *
192 * For an example script for calculating H, refer to the unit tests in
193 * ./test/functional/test_framework/crypto/secp256k1.py
194 */
195 constexpr XOnlyPubKey XOnlyPubKey::NUMS_H{
196 // Use immediate lambda to work around GCC-14 bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=117966
197 []() consteval { return XOnlyPubKey{"50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0"_hex_u8}; }(),
198 };
199
200 std::vector<CPubKey> XOnlyPubKey::GetCPubKeys() const
201 {
202 std::vector<CPubKey> out;
203 unsigned char b[33] = {0x02};
204 std::copy(m_keydata.begin(), m_keydata.end(), b + 1);
205 CPubKey fullpubkey;
206 fullpubkey.Set(b, b + 33);
207 out.push_back(fullpubkey);
208 b[0] = 0x03;
209 fullpubkey.Set(b, b + 33);
210 out.push_back(fullpubkey);
211 return out;
212 }
213
214 std::vector<CKeyID> XOnlyPubKey::GetKeyIDs() const
215 {
216 std::vector<CKeyID> out;
217 for (const CPubKey& pk : GetCPubKeys()) {
218 out.push_back(pk.GetID());
219 }
220 return out;
221 }
222
223 CPubKey XOnlyPubKey::GetEvenCorrespondingCPubKey() const
224 {
225 unsigned char full_key[CPubKey::COMPRESSED_SIZE] = {0x02};
226 std::copy(begin(), end(), full_key + 1);
227 return CPubKey{full_key};
228 }
229
230 bool XOnlyPubKey::IsFullyValid() const
231 {
232 secp256k1_xonly_pubkey pubkey;
233 return secp256k1_xonly_pubkey_parse(secp256k1_context_static, &pubkey, m_keydata.data());
234 }
235
236 bool XOnlyPubKey::VerifySchnorr(const uint256& msg, std::span<const unsigned char> sigbytes) const
237 {
238 assert(sigbytes.size() == 64);
239 secp256k1_xonly_pubkey pubkey;
240 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_static, &pubkey, m_keydata.data())) return false;
241 return secp256k1_schnorrsig_verify(secp256k1_context_static, sigbytes.data(), msg.begin(), 32, &pubkey);
242 }
243
244 static const HashWriter HASHER_TAPTWEAK{TaggedHash("TapTweak")};
245
246 uint256 XOnlyPubKey::ComputeTapTweakHash(const uint256* merkle_root) const
247 {
248 if (merkle_root == nullptr) {
249 // We have no scripts. The actual tweak does not matter, but follow BIP341 here to
250 // allow for reproducible tweaking.
251 return (HashWriter{HASHER_TAPTWEAK} << m_keydata).GetSHA256();
252 } else {
253 return (HashWriter{HASHER_TAPTWEAK} << m_keydata << *merkle_root).GetSHA256();
254 }
255 }
256
257 bool XOnlyPubKey::CheckTapTweak(const XOnlyPubKey& internal, const uint256& merkle_root, bool parity) const
258 {
259 secp256k1_xonly_pubkey internal_key;
260 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_static, &internal_key, internal.data())) return false;
261 uint256 tweak = internal.ComputeTapTweakHash(&merkle_root);
262 return secp256k1_xonly_pubkey_tweak_add_check(secp256k1_context_static, m_keydata.begin(), parity, &internal_key, tweak.begin());
263 }
264
265 std::optional<std::pair<XOnlyPubKey, bool>> XOnlyPubKey::CreateTapTweak(const uint256* merkle_root) const
266 {
267 secp256k1_xonly_pubkey base_point;
268 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_static, &base_point, data())) return std::nullopt;
269 secp256k1_pubkey out;
270 uint256 tweak = ComputeTapTweakHash(merkle_root);
271 if (!secp256k1_xonly_pubkey_tweak_add(secp256k1_context_static, &out, &base_point, tweak.data())) return std::nullopt;
272 int parity = -1;
273 std::pair<XOnlyPubKey, bool> ret;
274 secp256k1_xonly_pubkey out_xonly;
275 if (!secp256k1_xonly_pubkey_from_pubkey(secp256k1_context_static, &out_xonly, &parity, &out)) return std::nullopt;
276 secp256k1_xonly_pubkey_serialize(secp256k1_context_static, ret.first.begin(), &out_xonly);
277 assert(parity == 0 || parity == 1);
278 ret.second = parity;
279 return ret;
280 }
281
282
283 bool CPubKey::Verify(const uint256 &hash, const std::vector<unsigned char>& vchSig) const {
284 if (!IsValid())
285 return false;
286 secp256k1_pubkey pubkey;
287 secp256k1_ecdsa_signature sig;
288 if (!secp256k1_ec_pubkey_parse(secp256k1_context_static, &pubkey, vch, size())) {
289 return false;
290 }
291 if (!ecdsa_signature_parse_der_lax(&sig, vchSig.data(), vchSig.size())) {
292 return false;
293 }
294 /* libsecp256k1's ECDSA verification requires lower-S signatures, which have
295 * not historically been enforced in Bitcoin, so normalize them first. */
296 secp256k1_ecdsa_signature_normalize(secp256k1_context_static, &sig, &sig);
297 return secp256k1_ecdsa_verify(secp256k1_context_static, &sig, hash.begin(), &pubkey);
298 }
299
300 bool CPubKey::RecoverCompact(const uint256 &hash, const std::vector<unsigned char>& vchSig) {
301 if (vchSig.size() != COMPACT_SIGNATURE_SIZE)
302 return false;
303 int recid = (vchSig[0] - 27) & 3;
304 bool fComp = ((vchSig[0] - 27) & 4) != 0;
305 secp256k1_pubkey pubkey;
306 secp256k1_ecdsa_recoverable_signature sig;
307 if (!secp256k1_ecdsa_recoverable_signature_parse_compact(secp256k1_context_static, &sig, &vchSig[1], recid)) {
308 return false;
309 }
310 if (!secp256k1_ecdsa_recover(secp256k1_context_static, &pubkey, &sig, hash.begin())) {
311 return false;
312 }
313 unsigned char pub[SIZE];
314 size_t publen = SIZE;
315 secp256k1_ec_pubkey_serialize(secp256k1_context_static, pub, &publen, &pubkey, fComp ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED);
316 Set(pub, pub + publen);
317 return true;
318 }
319
320 bool CPubKey::IsFullyValid() const {
321 if (!IsValid())
322 return false;
323 secp256k1_pubkey pubkey;
324 return secp256k1_ec_pubkey_parse(secp256k1_context_static, &pubkey, vch, size());
325 }
326
327 bool CPubKey::Decompress() {
328 if (!IsValid())
329 return false;
330 secp256k1_pubkey pubkey;
331 if (!secp256k1_ec_pubkey_parse(secp256k1_context_static, &pubkey, vch, size())) {
332 return false;
333 }
334 unsigned char pub[SIZE];
335 size_t publen = SIZE;
336 secp256k1_ec_pubkey_serialize(secp256k1_context_static, pub, &publen, &pubkey, SECP256K1_EC_UNCOMPRESSED);
337 Set(pub, pub + publen);
338 return true;
339 }
340
341 bool CPubKey::Derive(CPubKey& pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode& cc, uint256* bip32_tweak_out) const {
342 assert(IsValid());
343 assert((nChild >> 31) == 0);
344 assert(size() == COMPRESSED_SIZE);
345 unsigned char out[64];
346 BIP32Hash(cc, nChild, *begin(), begin()+1, out);
347 memcpy(ccChild.begin(), out+32, 32);
348 if (bip32_tweak_out) {
349 memcpy(bip32_tweak_out->begin(), out, 32);
350 }
351 secp256k1_pubkey pubkey;
352 if (!secp256k1_ec_pubkey_parse(secp256k1_context_static, &pubkey, vch, size())) {
353 return false;
354 }
355 if (!secp256k1_ec_pubkey_tweak_add(secp256k1_context_static, &pubkey, out)) {
356 return false;
357 }
358 unsigned char pub[COMPRESSED_SIZE];
359 size_t publen = COMPRESSED_SIZE;
360 secp256k1_ec_pubkey_serialize(secp256k1_context_static, pub, &publen, &pubkey, SECP256K1_EC_COMPRESSED);
361 pubkeyChild.Set(pub, pub + publen);
362 return true;
363 }
364
365 EllSwiftPubKey::EllSwiftPubKey(std::span<const std::byte> ellswift) noexcept
366 {
367 assert(ellswift.size() == SIZE);
368 std::copy(ellswift.begin(), ellswift.end(), m_pubkey.begin());
369 }
370
371 CPubKey EllSwiftPubKey::Decode() const
372 {
373 secp256k1_pubkey pubkey;
374 secp256k1_ellswift_decode(secp256k1_context_static, &pubkey, UCharCast(m_pubkey.data()));
375
376 size_t sz = CPubKey::COMPRESSED_SIZE;
377 std::array<uint8_t, CPubKey::COMPRESSED_SIZE> vch_bytes;
378
379 secp256k1_ec_pubkey_serialize(secp256k1_context_static, vch_bytes.data(), &sz, &pubkey, SECP256K1_EC_COMPRESSED);
380 assert(sz == vch_bytes.size());
381
382 return CPubKey{vch_bytes.begin(), vch_bytes.end()};
383 }
384
385 void CExtPubKey::Encode(unsigned char code[BIP32_EXTKEY_SIZE]) const {
386 code[0] = nDepth;
387 memcpy(code+1, vchFingerprint, 4);
388 WriteBE32(code+5, nChild);
389 memcpy(code+9, chaincode.begin(), 32);
390 assert(pubkey.size() == CPubKey::COMPRESSED_SIZE);
391 memcpy(code+41, pubkey.begin(), CPubKey::COMPRESSED_SIZE);
392 }
393
394 void CExtPubKey::Decode(const unsigned char code[BIP32_EXTKEY_SIZE]) {
395 nDepth = code[0];
396 memcpy(vchFingerprint, code+1, 4);
397 nChild = ReadBE32(code+5);
398 memcpy(chaincode.begin(), code+9, 32);
399 pubkey.Set(code+41, code+BIP32_EXTKEY_SIZE);
400 if ((nDepth == 0 && (nChild != 0 || ReadLE32(vchFingerprint) != 0)) || !pubkey.IsFullyValid()) pubkey = CPubKey();
401 }
402
403 void CExtPubKey::EncodeWithVersion(unsigned char code[BIP32_EXTKEY_WITH_VERSION_SIZE]) const
404 {
405 memcpy(code, version, 4);
406 Encode(&code[4]);
407 }
408
409 void CExtPubKey::DecodeWithVersion(const unsigned char code[BIP32_EXTKEY_WITH_VERSION_SIZE])
410 {
411 memcpy(version, code, 4);
412 Decode(&code[4]);
413 }
414
415 bool CExtPubKey::Derive(CExtPubKey &out, unsigned int _nChild, uint256* bip32_tweak_out) const {
416 if (nDepth == std::numeric_limits<unsigned char>::max()) return false;
417 out.nDepth = nDepth + 1;
418 CKeyID id = pubkey.GetID();
419 memcpy(out.vchFingerprint, &id, 4);
420 out.nChild = _nChild;
421 return pubkey.Derive(out.pubkey, out.chaincode, _nChild, chaincode, bip32_tweak_out);
422 }
423
424 /* static */ bool CPubKey::CheckLowS(const std::vector<unsigned char>& vchSig) {
425 secp256k1_ecdsa_signature sig;
426 if (!ecdsa_signature_parse_der_lax(&sig, vchSig.data(), vchSig.size())) {
427 return false;
428 }
429 return (!secp256k1_ecdsa_signature_normalize(secp256k1_context_static, nullptr, &sig));
430 }
431