bulletproofs.cpp raw
1 // Copyright (c) 2025 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #include <crypto/bulletproofs.h>
6 #include <crypto/bignum.h>
7 #include <crypto/sha256.h>
8 #include <secp256k1.h>
9 #include <secp256k1_extrakeys.h>
10 #include <secp256k1_schnorrsig.h>
11
12 #include <cstring>
13 #include <mutex>
14 #include <string>
15
16 // ---------------------------------------------------------------------------
17 // Curve constants
18 // ---------------------------------------------------------------------------
19
20 // secp256k1 group order.
21 static BigNum CurveOrder()
22 {
23 static const uint8_t n_bytes[32] = {
24 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
25 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE,
26 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,
27 0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41,
28 };
29 static BigNum n(std::vector<uint8_t>(n_bytes, n_bytes + 32), true);
30 return n;
31 }
32
33 // secp256k1 base point G, compressed.
34 static const std::vector<uint8_t>& BasePointG()
35 {
36 static const std::vector<uint8_t> g = {
37 0x02, 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0,
38 0x62, 0x95, 0xCE, 0x87, 0x0B, 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D,
39 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98,
40 };
41 return g;
42 }
43
44 // ---------------------------------------------------------------------------
45 // Scalar arithmetic mod the curve order, using BigNum.
46 // ---------------------------------------------------------------------------
47
48 static BigNum SMod(const BigNum& x) { return x % CurveOrder(); }
49
50 static BigNum SAdd(const BigNum& a, const BigNum& b) { return (a + b) % CurveOrder(); }
51
52 static BigNum SMul(const BigNum& a, const BigNum& b) { return (a * b) % CurveOrder(); }
53
54 static BigNum SNeg(const BigNum& a)
55 {
56 return a.is_zero() ? BigNum(0u) : CurveOrder() - a;
57 }
58
59 static BigNum SInv(const BigNum& a)
60 {
61 // Fermat: a^(n-2) mod n.
62 return BigNum::mod_pow(a, CurveOrder() - BigNum(2u), CurveOrder());
63 }
64
65 // 32-byte big-endian scalar.
66 static std::vector<uint8_t> ScalarToBytes(const BigNum& x)
67 {
68 auto le = x.to_bytes(BP_SCALAR_SIZE);
69 std::vector<uint8_t> be(BP_SCALAR_SIZE);
70 for (size_t i = 0; i < BP_SCALAR_SIZE; i++) be[i] = le[BP_SCALAR_SIZE - 1 - i];
71 return be;
72 }
73
74 static BigNum ScalarFromBytes(const std::vector<uint8_t>& be)
75 {
76 return SMod(BigNum(be, true));
77 }
78
79 // Domain-separated hash to a scalar in [0, n).
80 static BigNum HashToScalar(const char* label, const std::vector<uint8_t>& data)
81 {
82 CSHA256 sha;
83 sha.Write(reinterpret_cast<const uint8_t*>(label), std::strlen(label));
84 sha.Write(data.data(), data.size());
85 uint8_t hash[CSHA256::OUTPUT_SIZE];
86 sha.Finalize(hash);
87 return SMod(BigNum(std::vector<uint8_t>(hash, hash + CSHA256::OUTPUT_SIZE), false));
88 }
89
90 // ---------------------------------------------------------------------------
91 // Point operations via secp256k1
92 // ---------------------------------------------------------------------------
93
94 static secp256k1_context* GetContext()
95 {
96 static secp256k1_context* ctx = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY);
97 return ctx;
98 }
99
100 static bool ParsePoint(const std::vector<uint8_t>& in, secp256k1_pubkey& out)
101 {
102 return secp256k1_ec_pubkey_parse(GetContext(), &out, in.data(), in.size()) == 1;
103 }
104
105 static std::vector<uint8_t> SerializePoint(const secp256k1_pubkey& pub)
106 {
107 std::vector<uint8_t> out(BP_POINT_SIZE);
108 size_t len = BP_POINT_SIZE;
109 secp256k1_ec_pubkey_serialize(GetContext(), out.data(), &len, &pub, SECP256K1_EC_COMPRESSED);
110 out.resize(len);
111 return out;
112 }
113
114 // Try-and-increment hash-to-curve, returning a NUMS point with even y.
115 static bool HashToCurve(const std::string& label, std::vector<uint8_t>& out)
116 {
117 for (uint32_t counter = 0; counter < 0x100000; counter++) {
118 CSHA256 sha;
119 sha.Write(reinterpret_cast<const uint8_t*>(label.data()), label.size());
120 uint8_t cb[4] = {uint8_t(counter >> 24), uint8_t(counter >> 16),
121 uint8_t(counter >> 8), uint8_t(counter)};
122 sha.Write(cb, 4);
123 uint8_t hash[CSHA256::OUTPUT_SIZE];
124 sha.Finalize(hash);
125
126 secp256k1_xonly_pubkey xonly;
127 if (!secp256k1_xonly_pubkey_parse(GetContext(), &xonly, hash)) continue;
128
129 // Convert to a full point (even y) with a zero tweak.
130 secp256k1_pubkey pub;
131 static const uint8_t zero[32] = {0};
132 if (!secp256k1_xonly_pubkey_tweak_add(GetContext(), &pub, &xonly, zero)) continue;
133
134 out = SerializePoint(pub);
135 return true;
136 }
137 return false;
138 }
139
140 // ---------------------------------------------------------------------------
141 // Generators
142 // ---------------------------------------------------------------------------
143
144 static std::vector<uint8_t> g_value;
145 static std::vector<std::vector<uint8_t>> g_G_vec;
146 static std::vector<std::vector<uint8_t>> g_H_vec;
147 static std::once_flag g_generators_init;
148
149 void InitBulletproofGenerators()
150 {
151 std::call_once(g_generators_init, []() {
152 HashToCurve("bulletproofs v1 H", g_value);
153 g_G_vec.resize(BP_BITS);
154 g_H_vec.resize(BP_BITS);
155 for (size_t i = 0; i < BP_BITS; i++) {
156 HashToCurve("bulletproofs v1 G" + std::to_string(i), g_G_vec[i]);
157 HashToCurve("bulletproofs v1 H" + std::to_string(i), g_H_vec[i]);
158 }
159 });
160 }
161
162 bool VerifyBulletproofGenerators()
163 {
164 InitBulletproofGenerators();
165 std::vector<std::vector<uint8_t>> all;
166 all.push_back(g_value);
167 all.insert(all.end(), g_G_vec.begin(), g_G_vec.end());
168 all.insert(all.end(), g_H_vec.begin(), g_H_vec.end());
169 all.push_back(BasePointG());
170
171 for (size_t i = 0; i < all.size(); i++) {
172 if (all[i].size() != BP_POINT_SIZE) return false;
173 secp256k1_pubkey tmp;
174 if (!secp256k1_ec_pubkey_parse(GetContext(), &tmp, all[i].data(), all[i].size()))
175 return false;
176 for (size_t j = i + 1; j < all.size(); j++) {
177 if (all[i] == all[j]) return false;
178 }
179 }
180 return true;
181 }
182
183 // ---------------------------------------------------------------------------
184 // Commitment
185 // ---------------------------------------------------------------------------
186
187 bool CommitAmount(__int128 amount, const BPScalar& blinding, BPCommitment& out)
188 {
189 if (blinding.size() != BP_SCALAR_SIZE) return false;
190 InitBulletproofGenerators();
191
192 // C = r*G + v*H (blinding r in base point G, value v in NUMS H).
193 // amount as a full 128-bit BigNum (little-endian bytes).
194 std::vector<uint8_t> amount_bytes(16);
195 for (int i = 0; i < 16; i++) amount_bytes[i] = uint8_t(static_cast<uint64_t>(static_cast<__uint128_t>(amount) >> (8 * i)));
196 BigNum v = SMod(BigNum(amount_bytes, false));
197 BigNum r = ScalarFromBytes(blinding);
198
199 // Skip zero scalars (identity points). Require at least one non-zero
200 // term so the commitment is never the point at infinity.
201 std::vector<secp256k1_pubkey> pubs;
202 std::vector<const secp256k1_pubkey*> ptrs;
203 if (!v.is_zero()) {
204 secp256k1_pubkey vH;
205 if (!ParsePoint(g_value, vH)) return false;
206 auto vs = ScalarToBytes(v);
207 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &vH, vs.data())) return false;
208 pubs.push_back(vH);
209 }
210 if (!r.is_zero()) {
211 secp256k1_pubkey rG;
212 if (!ParsePoint(BasePointG(), rG)) return false;
213 auto rs = ScalarToBytes(r);
214 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &rG, rs.data())) return false;
215 pubs.push_back(rG);
216 }
217 if (pubs.empty()) return false;
218
219 for (auto& p : pubs) ptrs.push_back(&p);
220 secp256k1_pubkey sum;
221 if (!secp256k1_ec_pubkey_combine(GetContext(), &sum, ptrs.data(), ptrs.size())) return false;
222
223 out = SerializePoint(sum);
224 return true;
225 }
226
227 // ---------------------------------------------------------------------------
228 // Multiscalar check: sum of scalar*point == identity.
229 // ---------------------------------------------------------------------------
230
231 static bool MultiscalarEqualsIdentity(
232 const std::vector<std::pair<BigNum, std::vector<uint8_t>>>& terms)
233 {
234 // Add a fixed offset point so the result is never the identity; the sum
235 // is the identity iff result == offset.
236 std::vector<uint8_t> offset;
237 if (!HashToCurve("bulletproofs v1 offset", offset)) return false;
238
239 std::vector<secp256k1_pubkey> pubs;
240 pubs.reserve(terms.size() + 1);
241 std::vector<const secp256k1_pubkey*> ptrs;
242
243 secp256k1_pubkey off;
244 if (!ParsePoint(offset, off)) return false;
245 pubs.push_back(off);
246
247 for (const auto& [scalar, point] : terms) {
248 BigNum s = SMod(scalar);
249 if (s.is_zero()) continue;
250 secp256k1_pubkey pub;
251 if (!ParsePoint(point, pub)) return false;
252 auto sb = ScalarToBytes(s);
253 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &pub, sb.data())) return false;
254 pubs.push_back(pub);
255 }
256
257 for (auto& p : pubs) ptrs.push_back(&p);
258
259 secp256k1_pubkey result;
260 if (!secp256k1_ec_pubkey_combine(GetContext(), &result, ptrs.data(), ptrs.size()))
261 return false;
262
263 return SerializePoint(result) == offset;
264 }
265
266 // ---------------------------------------------------------------------------
267 // Inner product: compute the folding challenges u_j and the s vector.
268 // ---------------------------------------------------------------------------
269
270 static bool ComputeIPAScalars(
271 const Bulletproof& proof,
272 const BigNum& w,
273 std::vector<BigNum>& u_sq,
274 std::vector<BigNum>& u_inv_sq,
275 std::vector<BigNum>& s)
276 {
277 // Challenges u_6..u_1, each bound to the range proof via w.
278 // proof.L[i] corresponds to round (6 - i), so L[0]=L_6 ... L[5]=L_1.
279 std::vector<BigNum> u(BP_ROUNDS);
280 {
281 std::vector<uint8_t> acc = ScalarToBytes(w);
282 for (size_t j = 0; j < BP_ROUNDS; j++) {
283 std::vector<uint8_t> data = acc;
284 data.insert(data.end(), proof.L[j].begin(), proof.L[j].end());
285 data.insert(data.end(), proof.R[j].begin(), proof.R[j].end());
286 BigNum uj = HashToScalar("bp-u", data);
287 if (uj.is_zero()) uj = BigNum(1u);
288 u[j] = uj;
289 acc = ScalarToBytes(uj);
290 }
291 }
292
293 u_sq.resize(BP_ROUNDS);
294 u_inv_sq.resize(BP_ROUNDS);
295 BigNum allinv(1u);
296 for (size_t j = 0; j < BP_ROUNDS; j++) {
297 BigNum inv = SInv(u[j]);
298 u_sq[j] = SMul(u[j], u[j]);
299 u_inv_sq[j] = SMul(inv, inv);
300 allinv = SMul(allinv, inv);
301 }
302
303 // s[i] = s[i - 2^lg] * u_{lg+1}^2, s[0] = allinv.
304 // u vector is stored as u[0..5] = u_6..u_1.
305 s.resize(BP_BITS);
306 s[0] = allinv;
307 for (size_t i = 1; i < BP_BITS; i++) {
308 size_t lg = 63 - __builtin_clzll((unsigned long long)i);
309 size_t k = size_t(1) << lg;
310 // u_{lg+1} corresponds to index (BP_ROUNDS - 1 - lg).
311 size_t idx = (BP_ROUNDS - 1) - lg;
312 s[i] = SMul(s[i - k], u_sq[idx]);
313 }
314 return true;
315 }
316
317 // ---------------------------------------------------------------------------
318 // Range proof verification.
319 // ---------------------------------------------------------------------------
320
321 bool VerifyBulletproof(const BPCommitment& commitment, const Bulletproof& proof)
322 {
323 if (commitment.size() != BP_POINT_SIZE) return false;
324 if (proof.A.size() != BP_POINT_SIZE || proof.S.size() != BP_POINT_SIZE) return false;
325 if (proof.T1.size() != BP_POINT_SIZE || proof.T2.size() != BP_POINT_SIZE) return false;
326 if (proof.t_hat.size() != BP_SCALAR_SIZE || proof.taux.size() != BP_SCALAR_SIZE) return false;
327 if (proof.mu.size() != BP_SCALAR_SIZE) return false;
328 if (proof.a.size() != BP_SCALAR_SIZE || proof.b.size() != BP_SCALAR_SIZE) return false;
329 for (size_t i = 0; i < BP_ROUNDS; i++) {
330 if (proof.L[i].size() != BP_POINT_SIZE || proof.R[i].size() != BP_POINT_SIZE)
331 return false;
332 }
333 InitBulletproofGenerators();
334
335 // Validate that all points parse (and are not the identity).
336 secp256k1_pubkey tmp;
337 auto valid_point = [&](const std::vector<uint8_t>& p) {
338 return ParsePoint(p, tmp);
339 };
340 if (!valid_point(commitment) || !valid_point(proof.A) || !valid_point(proof.S) ||
341 !valid_point(proof.T1) || !valid_point(proof.T2)) return false;
342 for (size_t i = 0; i < BP_ROUNDS; i++) {
343 if (!valid_point(proof.L[i]) || !valid_point(proof.R[i])) return false;
344 }
345
346 // Challenges.
347 BigNum y, z, x, w, c;
348 {
349 std::vector<uint8_t> data = commitment;
350 data.insert(data.end(), proof.A.begin(), proof.A.end());
351 data.insert(data.end(), proof.S.begin(), proof.S.end());
352 y = HashToScalar("bp-y", data);
353 if (y.is_zero()) y = BigNum(1u);
354 {
355 auto yb = ScalarToBytes(y);
356 data.insert(data.end(), yb.begin(), yb.end());
357 }
358 z = HashToScalar("bp-z", data);
359 if (z.is_zero()) z = BigNum(1u);
360
361 std::vector<uint8_t> tx = proof.T1;
362 tx.insert(tx.end(), proof.T2.begin(), proof.T2.end());
363 x = HashToScalar("bp-x", tx);
364 if (x.is_zero()) x = BigNum(1u);
365
366 std::vector<uint8_t> td = proof.t_hat;
367 td.insert(td.end(), proof.taux.begin(), proof.taux.end());
368 td.insert(td.end(), proof.mu.begin(), proof.mu.end());
369 w = HashToScalar("bp-w", td);
370 if (w.is_zero()) w = BigNum(1u);
371
372 c = HashToScalar("bp-c", ScalarToBytes(w));
373 if (c.is_zero()) c = BigNum(1u);
374 }
375
376 BigNum t_hat = ScalarFromBytes(proof.t_hat);
377 BigNum taux = ScalarFromBytes(proof.taux);
378 BigNum mu = ScalarFromBytes(proof.mu);
379 BigNum a_scalar = ScalarFromBytes(proof.a);
380 BigNum b_scalar = ScalarFromBytes(proof.b);
381
382 // y^{-i} for i = 0..n-1, and y^i.
383 std::vector<BigNum> y_pow(BP_BITS); // y^i
384 std::vector<BigNum> y_inv_pow(BP_BITS); // y^{-i}
385 {
386 BigNum yp(1u), yip(1u), yinv = SInv(y);
387 for (size_t i = 0; i < BP_BITS; i++) {
388 y_pow[i] = yp;
389 y_inv_pow[i] = yip;
390 yp = SMul(yp, y);
391 yip = SMul(yip, yinv);
392 }
393 }
394
395 // delta(y,z) = (z - z^2) * <1, y^n> - z^3 * <1, 2^n>
396 BigNum z2 = SMul(z, z);
397 BigNum z3 = SMul(z2, z);
398 BigNum sum_y(0u), sum_2(0u);
399 {
400 BigNum two(2u), twopow(1u);
401 for (size_t i = 0; i < BP_BITS; i++) {
402 sum_y = SAdd(sum_y, y_pow[i]);
403 sum_2 = SAdd(sum_2, twopow);
404 twopow = SMul(twopow, two);
405 }
406 }
407 BigNum delta = SAdd(SMul(SAdd(z, SNeg(z2)), sum_y), SNeg(SMul(z3, sum_2)));
408
409 // IPA folding scalars.
410 std::vector<BigNum> u_sq, u_inv_sq, s_vec;
411 if (!ComputeIPAScalars(proof, w, u_sq, u_inv_sq, s_vec)) return false;
412
413 // Build the multiscalar terms: sum must equal identity.
414 std::vector<std::pair<BigNum, std::vector<uint8_t>>> terms;
415
416 // A, S, V, T1, T2
417 terms.emplace_back(BigNum(1u), proof.A);
418 terms.emplace_back(x, proof.S);
419 terms.emplace_back(SMul(c, z2), commitment);
420 terms.emplace_back(SMul(c, x), proof.T1);
421 terms.emplace_back(SMul(c, SMul(x, x)), proof.T2);
422
423 // Value generator H (NUMS): w*(t_hat - a*b) + c*(delta - t_hat)
424 {
425 BigNum ab = SMul(a_scalar, b_scalar);
426 BigNum gcoef = SAdd(SMul(w, SAdd(t_hat, SNeg(ab))), SMul(c, SAdd(delta, SNeg(t_hat))));
427 terms.emplace_back(gcoef, g_value);
428 }
429 // Blinding generator G (base): -mu - c*taux
430 terms.emplace_back(SAdd(SNeg(mu), SNeg(SMul(c, taux))), BasePointG());
431
432 // G_vec: -z - a*s_i
433 for (size_t i = 0; i < BP_BITS; i++) {
434 BigNum coef = SAdd(SNeg(z), SNeg(SMul(a_scalar, s_vec[i])));
435 terms.emplace_back(coef, g_G_vec[i]);
436 }
437 // H_vec: z + y^{-i} * (z^2 * 2^i - b / s_i), where 1/s_i = s_{n-1-i}.
438 {
439 BigNum two(2u), twopow(1u);
440 for (size_t i = 0; i < BP_BITS; i++) {
441 BigNum binv = s_vec[BP_BITS - 1 - i]; // 1/s_i
442 BigNum inner = SAdd(SMul(z2, twopow), SNeg(SMul(b_scalar, binv)));
443 BigNum coef = SAdd(z, SMul(y_inv_pow[i], inner));
444 terms.emplace_back(coef, g_H_vec[i]);
445 twopow = SMul(twopow, two);
446 }
447 }
448 // L_j * u_j^2 and R_j * u_j^{-2}
449 for (size_t j = 0; j < BP_ROUNDS; j++) {
450 terms.emplace_back(u_sq[j], proof.L[j]);
451 terms.emplace_back(u_inv_sq[j], proof.R[j]);
452 }
453
454 return MultiscalarEqualsIdentity(terms);
455 }
456
457 // ---------------------------------------------------------------------------
458 // Parsing
459 // ---------------------------------------------------------------------------
460
461 bool VerifyCTBalance(const std::vector<std::vector<uint8_t>>& input_commitments,
462 const std::vector<std::vector<uint8_t>>& output_commitments,
463 __int128 fee,
464 const std::vector<uint8_t>& kernel_msg,
465 const std::vector<uint8_t>& kernel_sig,
466 const std::vector<__int128>& transparent_inputs)
467 {
468 if (kernel_msg.size() != BP_SCALAR_SIZE || kernel_sig.size() != 64) return false;
469 InitBulletproofGenerators();
470
471 // kernel K = sum(C_in) - sum(C_out) - fee*H + sum(v_transparent_in)*H.
472 // No offset terms: the balance equation is a plain Pedersen sum, so a
473 // committed excess must equal the signer's key exactly.
474 // Transparent mint inputs contribute their visible value with zero
475 // blinding; their script signatures authorize the spend separately.
476 std::vector<std::pair<BigNum, std::vector<uint8_t>>> terms;
477 for (const auto& c : input_commitments) {
478 if (c.size() != BP_POINT_SIZE) return false;
479 terms.emplace_back(BigNum(1u), c);
480 }
481 for (const auto& c : output_commitments) {
482 if (c.size() != BP_POINT_SIZE) return false;
483 terms.emplace_back(SNeg(BigNum(1u)), c);
484 }
485 for (const __int128 v : transparent_inputs) {
486 if (v < 0) return false;
487 std::vector<uint8_t> vb(16);
488 for (int i = 0; i < 16; i++) vb[i] = uint8_t(static_cast<uint64_t>(static_cast<__uint128_t>(v) >> (8 * i)));
489 terms.emplace_back(SMod(BigNum(vb, false)), g_value);
490 }
491 {
492 std::vector<uint8_t> fb(16);
493 for (int i = 0; i < 16; i++) fb[i] = uint8_t(static_cast<uint64_t>(static_cast<__uint128_t>(fee) >> (8 * i)));
494 terms.emplace_back(SNeg(SMod(BigNum(fb, false))), g_value);
495 }
496
497 // Compute K. It must be a valid, non-identity point (the excess key).
498 std::vector<secp256k1_pubkey> pubs;
499 std::vector<const secp256k1_pubkey*> ptrs;
500 for (const auto& [scalar, point] : terms) {
501 BigNum s = SMod(scalar);
502 if (s.is_zero()) continue;
503 secp256k1_pubkey pub;
504 if (!ParsePoint(point, pub)) return false;
505 auto sb = ScalarToBytes(s);
506 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &pub, sb.data())) return false;
507 pubs.push_back(pub);
508 }
509 if (pubs.empty()) return false;
510 for (auto& p : pubs) ptrs.push_back(&p);
511 secp256k1_pubkey K;
512 if (!secp256k1_ec_pubkey_combine(GetContext(), &K, ptrs.data(), ptrs.size()))
513 return false;
514
515 // Convert K to an x-only pubkey (even y) and verify the Schnorr signature.
516 secp256k1_xonly_pubkey Kx;
517 if (!secp256k1_xonly_pubkey_from_pubkey(GetContext(), &Kx, nullptr, &K))
518 return false;
519
520 return secp256k1_schnorrsig_verify(GetContext(), kernel_sig.data(),
521 kernel_msg.data(), BP_SCALAR_SIZE, &Kx) == 1;
522 }
523
524 bool CreateCTKernelSig(const BPScalar& excess, const std::vector<uint8_t>& kernel_msg,
525 std::vector<uint8_t>& sig)
526 {
527 if (excess.size() != BP_SCALAR_SIZE || kernel_msg.size() != BP_SCALAR_SIZE)
528 return false;
529
530 // The excess is the private key; must be in [1, n-1].
531 BigNum e = ScalarFromBytes(excess);
532 if (e.is_zero()) return false;
533
534 secp256k1_keypair keypair;
535 auto seckey = ScalarToBytes(e);
536 if (!secp256k1_keypair_create(GetContext(), &keypair, seckey.data()))
537 return false;
538
539 sig.resize(64);
540 static const uint8_t aux[32] = {0};
541 return secp256k1_schnorrsig_sign32(GetContext(), sig.data(), kernel_msg.data(),
542 &keypair, aux) == 1;
543 }
544
545 std::vector<uint8_t> SerializeBulletproof(const Bulletproof& proof)
546 {
547 std::vector<uint8_t> out;
548 auto append = [&](const std::vector<uint8_t>& v) { out.insert(out.end(), v.begin(), v.end()); };
549 append(proof.A); append(proof.S); append(proof.T1); append(proof.T2);
550 append(proof.t_hat); append(proof.taux); append(proof.mu);
551 for (size_t i = 0; i < BP_ROUNDS; i++) { append(proof.L[i]); append(proof.R[i]); }
552 append(proof.a); append(proof.b);
553 return out;
554 }
555
556 bool ParseBulletproof(std::span<const uint8_t> data, Bulletproof& proof)
557 {
558 size_t offset = 0;
559 auto read_vec = [&](size_t n, std::vector<uint8_t>& out) {
560 if (offset + n > data.size()) return false;
561 out.assign(data.begin() + offset, data.begin() + offset + n);
562 offset += n;
563 return true;
564 };
565
566 if (!read_vec(BP_POINT_SIZE, proof.A)) return false;
567 if (!read_vec(BP_POINT_SIZE, proof.S)) return false;
568 if (!read_vec(BP_POINT_SIZE, proof.T1)) return false;
569 if (!read_vec(BP_POINT_SIZE, proof.T2)) return false;
570 if (!read_vec(BP_SCALAR_SIZE, proof.t_hat)) return false;
571 if (!read_vec(BP_SCALAR_SIZE, proof.taux)) return false;
572 if (!read_vec(BP_SCALAR_SIZE, proof.mu)) return false;
573 for (size_t i = 0; i < BP_ROUNDS; i++) {
574 if (!read_vec(BP_POINT_SIZE, proof.L[i])) return false;
575 if (!read_vec(BP_POINT_SIZE, proof.R[i])) return false;
576 }
577 if (!read_vec(BP_SCALAR_SIZE, proof.a)) return false;
578 if (!read_vec(BP_SCALAR_SIZE, proof.b)) return false;
579 return offset == data.size();
580 }
581
582 // ---------------------------------------------------------------------------
583 // Prover (wallet-side, not consensus)
584 // ---------------------------------------------------------------------------
585
586 static BigNum SeedScalar(const std::vector<uint8_t>& seed, const char* label, uint32_t counter)
587 {
588 CSHA256 sha;
589 sha.Write(seed.data(), seed.size());
590 sha.Write(reinterpret_cast<const uint8_t*>(label), std::strlen(label));
591 uint8_t cb[4] = {uint8_t(counter >> 24), uint8_t(counter >> 16),
592 uint8_t(counter >> 8), uint8_t(counter)};
593 sha.Write(cb, 4);
594 uint8_t hash[CSHA256::OUTPUT_SIZE];
595 sha.Finalize(hash);
596 return SMod(BigNum(std::vector<uint8_t>(hash, hash + CSHA256::OUTPUT_SIZE), false));
597 }
598
599 // Sum of scalar*point, skipping zero scalars. Returns false on malformed point.
600 static bool MultiscalarMul(const std::vector<std::pair<BigNum, std::vector<uint8_t>>>& terms,
601 std::vector<uint8_t>& out)
602 {
603 std::vector<secp256k1_pubkey> pubs;
604 std::vector<const secp256k1_pubkey*> ptrs;
605 for (const auto& [scalar, point] : terms) {
606 BigNum s = SMod(scalar);
607 if (s.is_zero()) continue;
608 secp256k1_pubkey pub;
609 if (!ParsePoint(point, pub)) return false;
610 auto sb = ScalarToBytes(s);
611 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &pub, sb.data())) return false;
612 pubs.push_back(pub);
613 }
614 if (pubs.empty()) { out.clear(); return true; }
615 for (auto& p : pubs) ptrs.push_back(&p);
616 secp256k1_pubkey result;
617 if (!secp256k1_ec_pubkey_combine(GetContext(), &result, ptrs.data(), ptrs.size()))
618 return false;
619 out = SerializePoint(result);
620 return true;
621 }
622
623 bool ProveBulletproof(__int128 amount, const BPScalar& blinding, const BPScalar& seed,
624 BPCommitment& commitment, Bulletproof& proof)
625 {
626 if (blinding.size() != BP_SCALAR_SIZE || seed.size() != BP_SCALAR_SIZE) return false;
627 InitBulletproofGenerators();
628
629 BigNum gamma = ScalarFromBytes(blinding);
630
631 // a_L = bits of v, a_R = a_L - 1.
632 std::vector<BigNum> aL(BP_BITS), aR(BP_BITS);
633 for (size_t i = 0; i < BP_BITS; i++) {
634 BigNum b(uint32_t((static_cast<uint64_t>(amount >> i)) & 1));
635 aL[i] = b;
636 aR[i] = SAdd(b, SNeg(BigNum(1u)));
637 }
638
639 // Random scalars.
640 BigNum alpha = SeedScalar(seed, "alpha", 0);
641 BigNum rho = SeedScalar(seed, "rho", 0);
642 BigNum tau1 = SeedScalar(seed, "tau1", 0);
643 BigNum tau2 = SeedScalar(seed, "tau2", 0);
644 std::vector<BigNum> sL(BP_BITS), sR(BP_BITS);
645 for (size_t i = 0; i < BP_BITS; i++) {
646 sL[i] = SeedScalar(seed, "sL", (uint32_t)i);
647 sR[i] = SeedScalar(seed, "sR", (uint32_t)i);
648 }
649
650 // A = alpha*G + <aL, G_vec> + <aR, H_vec>; S = rho*G + <sL, G_vec> + <sR, H_vec>.
651 // (alpha, rho are blinding scalars, so they sit in the base point G.)
652 std::vector<std::pair<BigNum, std::vector<uint8_t>>> A_terms, S_terms;
653 A_terms.emplace_back(alpha, BasePointG());
654 S_terms.emplace_back(rho, BasePointG());
655 for (size_t i = 0; i < BP_BITS; i++) {
656 A_terms.emplace_back(aL[i], g_G_vec[i]);
657 A_terms.emplace_back(aR[i], g_H_vec[i]);
658 S_terms.emplace_back(sL[i], g_G_vec[i]);
659 S_terms.emplace_back(sR[i], g_H_vec[i]);
660 }
661 if (!MultiscalarMul(A_terms, proof.A)) return false;
662 if (!MultiscalarMul(S_terms, proof.S)) return false;
663
664 // Commitment C = v*G + gamma*H.
665 if (!CommitAmount(amount, blinding, commitment)) return false;
666
667 // Challenges y, z.
668 BigNum y, z;
669 {
670 std::vector<uint8_t> data = commitment;
671 data.insert(data.end(), proof.A.begin(), proof.A.end());
672 data.insert(data.end(), proof.S.begin(), proof.S.end());
673 y = HashToScalar("bp-y", data);
674 if (y.is_zero()) y = BigNum(1u);
675 {
676 auto yb = ScalarToBytes(y);
677 data.insert(data.end(), yb.begin(), yb.end());
678 }
679 z = HashToScalar("bp-z", data);
680 if (z.is_zero()) z = BigNum(1u);
681 }
682
683 // y^i and y^{-i}.
684 std::vector<BigNum> y_pow(BP_BITS), y_inv_pow(BP_BITS);
685 {
686 BigNum yp(1u), yip(1u), yinv = SInv(y);
687 for (size_t i = 0; i < BP_BITS; i++) {
688 y_pow[i] = yp;
689 y_inv_pow[i] = yip;
690 yp = SMul(yp, y);
691 yip = SMul(yip, yinv);
692 }
693 }
694
695 // l0 = aL - z, l1 = sL.
696 // r0 = y^n o (aR + z) + z^2 * 2^n, r1 = y^n o sR.
697 std::vector<BigNum> l0(BP_BITS), l1(BP_BITS), r0(BP_BITS), r1(BP_BITS);
698 BigNum z2 = SMul(z, z);
699 {
700 BigNum two(2u), twopow(1u);
701 for (size_t i = 0; i < BP_BITS; i++) {
702 l0[i] = SAdd(aL[i], SNeg(z));
703 l1[i] = sL[i];
704 r0[i] = SAdd(SMul(y_pow[i], SAdd(aR[i], z)), SMul(z2, twopow));
705 r1[i] = SMul(y_pow[i], sR[i]);
706 twopow = SMul(twopow, two);
707 }
708 }
709
710 // t0 = <l0,r0>, t2 = <l1,r1>, t1 = <l0+l1,r0+r1> - t0 - t2.
711 BigNum t0(0u), t2(0u), t1(0u);
712 {
713 BigNum t01(0u);
714 for (size_t i = 0; i < BP_BITS; i++) {
715 t0 = SAdd(t0, SMul(l0[i], r0[i]));
716 t2 = SAdd(t2, SMul(l1[i], r1[i]));
717 t01 = SAdd(t01, SMul(SAdd(l0[i], l1[i]), SAdd(r0[i], r1[i])));
718 }
719 t1 = SAdd(SAdd(t01, SNeg(t0)), SNeg(t2));
720 }
721
722 // T1 = t1*H + tau1*G, T2 = t2*H + tau2*G (t in value gen H, tau in base G).
723 {
724 std::vector<std::pair<BigNum, std::vector<uint8_t>>> t1t, t2t;
725 t1t.emplace_back(t1, g_value);
726 t1t.emplace_back(tau1, BasePointG());
727 t2t.emplace_back(t2, g_value);
728 t2t.emplace_back(tau2, BasePointG());
729 if (!MultiscalarMul(t1t, proof.T1)) return false;
730 if (!MultiscalarMul(t2t, proof.T2)) return false;
731 }
732
733 // x = H(T1, T2).
734 BigNum x;
735 {
736 std::vector<uint8_t> tx = proof.T1;
737 tx.insert(tx.end(), proof.T2.begin(), proof.T2.end());
738 x = HashToScalar("bp-x", tx);
739 if (x.is_zero()) x = BigNum(1u);
740 }
741
742 // l = l0 + l1*x, r = r0 + r1*x, t_hat = <l, r>.
743 std::vector<BigNum> l(BP_BITS), r(BP_BITS);
744 BigNum t_hat(0u);
745 for (size_t i = 0; i < BP_BITS; i++) {
746 l[i] = SAdd(l0[i], SMul(l1[i], x));
747 r[i] = SAdd(r0[i], SMul(r1[i], x));
748 t_hat = SAdd(t_hat, SMul(l[i], r[i]));
749 }
750
751 // tau_x = tau2*x^2 + tau1*x + z^2*gamma; mu = alpha + rho*x.
752 BigNum x2 = SMul(x, x);
753 BigNum tau_x = SAdd(SAdd(SMul(tau2, x2), SMul(tau1, x)), SMul(z2, gamma));
754 BigNum mu = SAdd(alpha, SMul(rho, x));
755
756 proof.t_hat = ScalarToBytes(t_hat);
757 proof.taux = ScalarToBytes(tau_x);
758 proof.mu = ScalarToBytes(mu);
759
760 // w = H("bp-w", t_hat || tau_x || mu); Q = w * G.
761 BigNum w;
762 {
763 std::vector<uint8_t> td = proof.t_hat;
764 td.insert(td.end(), proof.taux.begin(), proof.taux.end());
765 td.insert(td.end(), proof.mu.begin(), proof.mu.end());
766 w = HashToScalar("bp-w", td);
767 if (w.is_zero()) w = BigNum(1u);
768 }
769 std::vector<uint8_t> Q;
770 {
771 secp256k1_pubkey q;
772 if (!ParsePoint(g_value, q)) return false;
773 auto wb = ScalarToBytes(w);
774 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &q, wb.data())) return false;
775 Q = SerializePoint(q);
776 }
777
778 // IPA over (G, y^{-n} o H) with vectors (l, r), Q, proving <l, r> = t_hat.
779 std::vector<std::vector<uint8_t>> Gc = g_G_vec;
780 std::vector<std::vector<uint8_t>> Hc(BP_BITS);
781 for (size_t i = 0; i < BP_BITS; i++) {
782 secp256k1_pubkey h;
783 if (!ParsePoint(g_H_vec[i], h)) return false;
784 auto yib = ScalarToBytes(y_inv_pow[i]);
785 if (!secp256k1_ec_pubkey_tweak_mul(GetContext(), &h, yib.data())) return false;
786 Hc[i] = SerializePoint(h);
787 }
788
789 std::vector<BigNum> al = l, ar = r;
790 std::vector<uint8_t> acc = ScalarToBytes(w);
791 size_t n = BP_BITS;
792 for (size_t round = 0; round < BP_ROUNDS; round++) {
793 size_t half = n / 2;
794 BigNum cL(0u), cR(0u);
795 for (size_t i = 0; i < half; i++) {
796 cL = SAdd(cL, SMul(al[i], ar[i + half]));
797 cR = SAdd(cR, SMul(al[i + half], ar[i]));
798 }
799 std::vector<std::pair<BigNum, std::vector<uint8_t>>> Lt, Rt;
800 for (size_t i = 0; i < half; i++) {
801 Lt.emplace_back(al[i], Gc[i + half]);
802 Lt.emplace_back(ar[i + half], Hc[i]);
803 Rt.emplace_back(al[i + half], Gc[i]);
804 Rt.emplace_back(ar[i], Hc[i + half]);
805 }
806 Lt.emplace_back(cL, Q);
807 Rt.emplace_back(cR, Q);
808 if (!MultiscalarMul(Lt, proof.L[round])) return false;
809 if (!MultiscalarMul(Rt, proof.R[round])) return false;
810
811 std::vector<uint8_t> data = acc;
812 data.insert(data.end(), proof.L[round].begin(), proof.L[round].end());
813 data.insert(data.end(), proof.R[round].begin(), proof.R[round].end());
814 BigNum u = HashToScalar("bp-u", data);
815 if (u.is_zero()) u = BigNum(1u);
816 BigNum uinv = SInv(u);
817 acc = ScalarToBytes(u);
818
819 std::vector<BigNum> na(half), nb(half);
820 std::vector<std::vector<uint8_t>> nG(half), nH(half);
821 for (size_t i = 0; i < half; i++) {
822 na[i] = SAdd(SMul(al[i], u), SMul(al[i + half], uinv));
823 nb[i] = SAdd(SMul(ar[i], uinv), SMul(ar[i + half], u));
824 }
825 for (size_t i = 0; i < half; i++) {
826 std::vector<std::pair<BigNum, std::vector<uint8_t>>> gt, ht;
827 gt.emplace_back(uinv, Gc[i]);
828 gt.emplace_back(u, Gc[i + half]);
829 ht.emplace_back(u, Hc[i]);
830 ht.emplace_back(uinv, Hc[i + half]);
831 if (!MultiscalarMul(gt, nG[i])) return false;
832 if (!MultiscalarMul(ht, nH[i])) return false;
833 }
834 al = std::move(na);
835 ar = std::move(nb);
836 Gc = std::move(nG);
837 Hc = std::move(nH);
838 n = half;
839 }
840
841 proof.a = ScalarToBytes(al[0]);
842 proof.b = ScalarToBytes(ar[0]);
843 return true;
844 }
845