Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_crypto/src/linkring.rs

36.2 KiB, 3 runs

created by r1870400018:61079, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A scoped linkable ring signature, `linkring/1`, whose proof grows with the
2//! logarithm of the ring.
3//!
4//! A signer holding one secret key of a ring of public keys proves that fact
5//! without saying which key is theirs, and publishes a *tag* `τ = k·H_p(scope)`
6//! that is fixed by the pair (key, scope) alone. The same key signing twice
7//! under one scope gives one tag, so a verifier can count signers, while tags
8//! under two scopes cannot be linked without the key (decisional
9//! Diffie-Hellman). The proof also binds the tag to the key, so no signer can
10//! produce the tag of another ring member.
11//!
12//! # Construction
13//!
14//! A Groth-Kohlweiss one-out-of-many proof in the radix-`n` form of Bootle et
15//! al. (ESORICS 2015), with `n = 16`, over ristretto255, plus a second relation
16//! on the base `U = H_p(scope)` that reuses the same response `z`:
17//!
18//! ```text
19//! Σ_i p_i(x)·P_i − Σ_k x^k·G_k = z·G (ring)
20//! x^m·τ − Σ_k x^k·Y_k = z·U (tag, Y_k = ρ_k·U)
21//! ```
22//!
23//! The ring is padded to `16^m` entries by repeating its last key, which costs
24//! nothing: since `Σ_i p_i(x) = x^m`, the padded entries fold into one
25//! coefficient on that key. The prover computes the `G_k` by expanding each
26//! `p_i` over the digit positions where `i` agrees with the signer's index, so
27//! signing costs about `(1 + 1/16)^m` ring multi-scalar multiplications rather
28//! than `m` of them.
29//!
30//! `H_p` is RFC 9380's `hash_to_ristretto255` (expand_message_xmd with SHA-512,
31//! then the RFC 9496 one-way map). The ring digest is SHA-256 over the
32//! concatenated 32-byte keys, in ring order. The Hematite User Guide gives the
33//! sizes and costs at 10^5 to 10^7 keys.
34//!
35//! # Encoding
36//!
37//! The body is `m ‖ A ‖ B ‖ C ‖ D ‖ G_0..G_{m-1} ‖ Y_0..Y_{m-1} ‖ f ‖ z_A ‖ z_C ‖ z`,
38//! with `f` the `m·15` responses `f_{j,1..15}`, every point a compressed
39//! ristretto255 encoding and every scalar canonical little-endian. Its first
40//! byte fixes its length, `1 + 32·(7 + 17m)`. It carries no key and no index.
41//! The tag travels beside it. A change to any of this is a new algorithm name.
42//!
43//! # What a false means
44//!
45//! As in `p256`, a malformed body or tag is a verification failure,
46//! `Ok(false)`, not an error. Only a malformed ring is an error, because the
47//! ring is the verifier's own input.
48//!
49//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
50//! Anthropic Claude
51
52use oxedyne_fe2o3_core::prelude::*;
53use oxedyne_fe2o3_hash::sha256;
54
55use std::sync::Mutex;
56
57use curve25519_dalek::{
58 constants::RISTRETTO_BASEPOINT_POINT,
59 ristretto::{
60 CompressedRistretto,
61 RistrettoPoint,
62 },
63 scalar::Scalar,
64 traits::{
65 Identity,
66 IsIdentity,
67 MultiscalarMul,
68 VartimeMultiscalarMul,
69 },
70};
71use rand_core::{
72 OsRng,
73 RngCore,
74};
75use sha2::{
76 Digest,
77 Sha512,
78};
79use zeroize::Zeroize;
80
81pub const ALG: &str = "linkring/1";
82pub const RADIX: usize = 16;
83pub const KEY_LEN: usize = 32;
84pub const TAG_LEN: usize = 32;
85pub const MAX_DIGITS: usize = 8; // rings up to 16^8 = 2^32 keys
86
87// Domain separation
88const DST_SCOPE: &[u8] = b"linkring/1:scope";
89const DST_GEN: &[u8] = b"linkring/1:gen";
90const DST_SECRET: &[u8] = b"linkring/1:secret";
91const DST_NONCE: &[u8] = b"linkring/1:nonce";
92
93const CHUNK: usize = 1 << 16; // points per multi-scalar multiplication
94
95/// The number of radix-16 digits `m` a ring of `n` keys uses.
96pub fn digits(n: usize) -> usize {
97 let mut m = 1;
98 let mut cap = RADIX;
99 while cap < n {
100 m += 1;
101 cap = cap.saturating_mul(RADIX);
102 }
103 m
104}
105
106/// The body length for `m` digits.
107pub fn body_len(m: usize) -> usize {
108 1 + 32 * (7 + 17 * m)
109}
110
111/// SHA-256 over the concatenated 32-byte keys, in ring order.
112pub fn ring_digest(list: &[u8]) -> [u8; 32] {
113 sha256::digest(list)
114}
115
116/// RFC 9380 `hash_to_ristretto255`: expand_message_xmd with SHA-512 to 64
117/// bytes, then the RFC 9496 one-way map.
118pub fn hash_to_group(dst: &[u8], msg: &[u8]) -> Outcome<RistrettoPoint> {
119 if dst.is_empty() || dst.len() > 255 {
120 return Err(err!("hash_to_group: domain tag length {} is outside 1..=255.",
121 dst.len(); Invalid, Input));
122 }
123 let dst_len = [dst.len() as u8];
124 let mut h = Sha512::new();
125 h.update([0u8; 128]); // Z_pad, the SHA-512 block size
126 h.update(msg);
127 h.update([0u8, 64u8]); // l_i_b_str, 64 bytes wanted
128 h.update([0u8]);
129 h.update(dst);
130 h.update(dst_len);
131 let b0 = h.finalize();
132 let mut h = Sha512::new();
133 h.update(b0);
134 h.update([1u8]);
135 h.update(dst);
136 h.update(dst_len);
137 let b1 = h.finalize();
138 let mut uniform = [0u8; 64];
139 uniform.copy_from_slice(&b1);
140 Ok(RistrettoPoint::from_uniform_bytes(&uniform))
141}
142
143/// The tag base for a scope, `U = H_p(scope)`.
144fn scope_base(scope: &[u8]) -> Outcome<RistrettoPoint> {
145 hash_to_group(DST_SCOPE, scope)
146}
147
148/// The vector commitment generators `H_{j,i}`, at `j·16 + i`.
149fn generators(m: usize) -> Outcome<Vec<RistrettoPoint>> {
150 let mut gens = Vec::with_capacity(m * RADIX);
151 for idx in 0..(m * RADIX) as u32 {
152 gens.push(res!(hash_to_group(DST_GEN, &idx.to_le_bytes())));
153 }
154 Ok(gens)
155}
156
157fn wide(bytes: &[u8]) -> Scalar {
158 let mut w = [0u8; 64];
159 w.copy_from_slice(bytes);
160 let s = Scalar::from_bytes_mod_order_wide(&w);
161 w.zeroize();
162 s
163}
164
165// ── Keys ────────────────────────────────────────────────────────────────────
166
167/// A ring secret key, a non-zero ristretto255 scalar. Zeroed on drop.
168#[derive(Clone)]
169pub struct SecretKey(Scalar);
170
171impl Drop for SecretKey {
172 fn drop(&mut self) { self.0.zeroize(); }
173}
174
175impl std::fmt::Debug for SecretKey {
176 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
177 write!(f, "SecretKey(..)")
178 }
179}
180
181impl SecretKey {
182 /// Derives a key from seed material as the scalar `SHA-512(DST ‖ seed)`
183 /// reduced modulo the group order, so a key can be restored from the same
184 /// seed on any device.
185 pub fn from_seed(seed: &[u8]) -> Outcome<Self> {
186 let mut h = Sha512::new();
187 h.update(DST_SECRET);
188 h.update(seed);
189 let s = wide(&h.finalize());
190 if s == Scalar::ZERO {
191 return Err(err!("linkring: the seed reduces to the zero scalar."; Invalid, Input));
192 }
193 Ok(Self(s))
194 }
195
196 /// Reads a canonical, non-zero scalar.
197 pub fn from_bytes(bytes: &[u8; 32]) -> Outcome<Self> {
198 let s: Option<Scalar> = Scalar::from_canonical_bytes(*bytes).into();
199 match s {
200 Some(s) if s != Scalar::ZERO => Ok(Self(s)),
201 _ => Err(err!("linkring: the secret key is not a canonical non-zero scalar.";
202 Invalid, Input)),
203 }
204 }
205
206 pub fn random() -> Outcome<Self> {
207 let mut seed = [0u8; 64];
208 OsRng.fill_bytes(&mut seed);
209 let key = Self::from_seed(&seed);
210 seed.zeroize();
211 key
212 }
213
214 pub fn to_bytes(&self) -> [u8; 32] { self.0.to_bytes() }
215
216 pub fn public_key(&self) -> [u8; KEY_LEN] {
217 RistrettoPoint::mul_base(&self.0).compress().to_bytes()
218 }
219}
220
221/// The tag of `key` under `scope`, `k·H_p(scope)`.
222pub fn tag(key: &SecretKey, scope: &[u8]) -> Outcome<[u8; TAG_LEN]> {
223 let u = res!(scope_base(scope));
224 Ok((u * key.0).compress().to_bytes())
225}
226
227// ── Ring ────────────────────────────────────────────────────────────────────
228
229/// A decoded ring with its digest, built once and reused for every signature
230/// over it. Holds about 200 bytes per key.
231pub struct Ring {
232 keys: Vec<[u8; KEY_LEN]>,
233 points: Vec<RistrettoPoint>,
234 digest: [u8; 32],
235}
236
237impl Ring {
238 /// Decodes a ring list, the concatenation of 32-byte keys.
239 pub fn from_list(list: &[u8]) -> Outcome<Self> {
240 Self::from_list_par(list, 1)
241 }
242
243 /// As `from_list`, decoding on `threads` threads.
244 pub fn from_list_par(list: &[u8], threads: usize) -> Outcome<Self> {
245 if list.is_empty() || list.len() % KEY_LEN != 0 {
246 return Err(err!("linkring: a ring list of {} bytes is not a non-empty \
247 multiple of {}.", list.len(), KEY_LEN; Invalid, Input, Size));
248 }
249 let n = list.len() / KEY_LEN;
250 // Compared as u64: `1usize << 32` overflows where usize is 32 bits, and
251 // that is a compile error on wasm32, which this crate builds for.
252 if n as u64 > 1u64 << 32 {
253 return Err(err!("linkring: a ring of {} keys exceeds 2^32.", n; Invalid, Input, Size));
254 }
255 let mut keys = Vec::with_capacity(n);
256 for c in list.chunks_exact(KEY_LEN) {
257 let mut k = [0u8; KEY_LEN];
258 k.copy_from_slice(c);
259 keys.push(k);
260 }
261 let points = res!(decode_all(&keys, threads.max(1)));
262 Ok(Self { keys, points, digest: ring_digest(list) })
263 }
264
265 pub fn from_keys(keys: &[[u8; KEY_LEN]]) -> Outcome<Self> {
266 let mut list = Vec::with_capacity(keys.len() * KEY_LEN);
267 for k in keys {
268 list.extend_from_slice(k);
269 }
270 Self::from_list(&list)
271 }
272
273 pub fn len(&self) -> usize { self.keys.len() }
274 pub fn is_empty(&self) -> bool { self.keys.is_empty() }
275 pub fn digest(&self) -> &[u8; 32] { &self.digest }
276 pub fn keys(&self) -> &[[u8; KEY_LEN]] { &self.keys }
277
278 /// The first position of `key` in the ring.
279 pub fn position(&self, key: &[u8; KEY_LEN]) -> Option<usize> {
280 self.keys.iter().position(|k| k == key)
281 }
282}
283
284fn decode_one(pos: usize, k: &[u8; KEY_LEN]) -> Outcome<RistrettoPoint> {
285 match CompressedRistretto(*k).decompress() {
286 Some(p) if !p.is_identity() => Ok(p),
287 Some(_) => Err(err!("linkring: ring key {} is the identity, whose secret is zero.",
288 pos; Invalid, Input)),
289 None => Err(err!("linkring: ring key {} is not a ristretto255 encoding.",
290 pos; Invalid, Input, Decode)),
291 }
292}
293
294fn decode_all(keys: &[[u8; KEY_LEN]], threads: usize) -> Outcome<Vec<RistrettoPoint>> {
295 if threads <= 1 || keys.len() < threads * 256 {
296 let mut pts = Vec::with_capacity(keys.len());
297 for (pos, k) in keys.iter().enumerate() {
298 pts.push(res!(decode_one(pos, k)));
299 }
300 return Ok(pts);
301 }
302 let per = (keys.len() + threads - 1) / threads;
303 let failed: Mutex<Option<Error<ErrTag>>> = Mutex::new(None);
304 let mut parts: Vec<Vec<RistrettoPoint>> = Vec::new();
305 std::thread::scope(|s| {
306 let mut handles = Vec::new();
307 for (t, part) in keys.chunks(per).enumerate() {
308 let failed = &failed;
309 handles.push(s.spawn(move || {
310 let mut pts = Vec::with_capacity(part.len());
311 for (i, k) in part.iter().enumerate() {
312 match decode_one(t * per + i, k) {
313 Ok(p) => pts.push(p),
314 Err(e) => {
315 if let Ok(mut f) = failed.lock() {
316 if f.is_none() { *f = Some(e); }
317 }
318 break;
319 }
320 }
321 }
322 pts
323 }));
324 }
325 for h in handles {
326 parts.push(h.join().unwrap_or_default());
327 }
328 });
329 let failed = res!(failed.into_inner().map_err(|_| err!(
330 "linkring: a ring decode thread poisoned its lock."; Thread, Poisoned)));
331 if let Some(e) = failed {
332 return Err(e);
333 }
334 let mut pts = Vec::with_capacity(keys.len());
335 for p in parts {
336 pts.extend(p);
337 }
338 if pts.len() != keys.len() {
339 return Err(err!("linkring: {} of {} ring keys decoded; a decode thread died.",
340 pts.len(), keys.len(); Thread));
341 }
342 Ok(pts)
343}
344
345// ── Guards ──────────────────────────────────────────────────────────────────
346
347// Each check in `verify` has a bit here. The unit tests switch one off, on
348// their own thread only, to prove the attack it stops then succeeds.
349const G_MSG: u32 = 1; // message in the transcript
350const G_DIGEST: u32 = 2; // ring digest in the transcript
351const G_DIGITS_AB: u32 = 4; // A + x·B = Com(f; z_A)
352const G_DIGITS_CD: u32 = 8; // x·C + D = Com(f(x − f); z_C)
353const G_TAG: u32 = 16; // tag relation
354const G_RING: u32 = 32; // ring relation
355
356#[cfg(test)]
357thread_local! {
358 static SKIP: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
359}
360
361#[cfg(test)]
362fn on(g: u32) -> bool { SKIP.with(|s| s.get() & g == 0) }
363
364#[cfg(not(test))]
365#[inline(always)]
366fn on(_g: u32) -> bool { true }
367
368// ── Transcript ──────────────────────────────────────────────────────────────
369
370struct Commit {
371 a: RistrettoPoint,
372 b: RistrettoPoint,
373 c: RistrettoPoint,
374 d: RistrettoPoint,
375 g: Vec<RistrettoPoint>, // G_k
376 y: Vec<RistrettoPoint>, // Y_k
377}
378
379fn challenge(
380 ring: &Ring,
381 m: usize,
382 scope: &[u8],
383 tau: &[u8; TAG_LEN],
384 msg: &[u8],
385 com: &Commit,
386)
387 -> Scalar
388{
389 let mut h = Sha512::new();
390 h.update(ALG.as_bytes());
391 h.update((RADIX as u32).to_le_bytes());
392 h.update((m as u32).to_le_bytes());
393 h.update((ring.len() as u64).to_le_bytes());
394 if on(G_DIGEST) {
395 h.update(ring.digest);
396 }
397 h.update((scope.len() as u64).to_le_bytes());
398 h.update(scope);
399 h.update(tau);
400 if on(G_MSG) {
401 h.update((msg.len() as u64).to_le_bytes());
402 h.update(msg);
403 }
404 for p in [&com.a, &com.b, &com.c, &com.d].into_iter().chain(com.g.iter()).chain(com.y.iter()) {
405 h.update(p.compress().as_bytes());
406 }
407 wide(&h.finalize())
408}
409
410// ── Sign ────────────────────────────────────────────────────────────────────
411
412/// Signs `msg` under `scope` as a hidden member of `ring`, returning the tag
413/// and the body. The key must be in the ring.
414pub fn sign(
415 ring: &Ring,
416 key: &SecretKey,
417 scope: &[u8],
418 msg: &[u8],
419)
420 -> Outcome<([u8; TAG_LEN], Vec<u8>)>
421{
422 let mut aux = [0u8; 32];
423 OsRng.fill_bytes(&mut aux);
424 sign_with_aux(ring, key, scope, msg, &aux)
425}
426
427/// As `sign`, with the prover's randomness derived from the key, the inputs
428/// and `aux` alone, so equal inputs give an equal body. `aux` hedges against
429/// a fault; empty is safe, since the nonces still depend on everything signed.
430pub fn sign_with_aux(
431 ring: &Ring,
432 key: &SecretKey,
433 scope: &[u8],
434 msg: &[u8],
435 aux: &[u8],
436)
437 -> Outcome<([u8; TAG_LEN], Vec<u8>)>
438{
439 let pk = key.public_key();
440 let l = match ring.position(&pk) {
441 Some(l) => l,
442 None => return Err(err!("linkring: the signing key is not in the ring of {} keys.",
443 ring.len(); Missing, Input)),
444 };
445 let u = res!(scope_base(scope));
446 let tau = u * key.0;
447 let body = res!(prove(ring, l, &key.0, &tau, &u, scope, msg, aux));
448 Ok((tau.compress().to_bytes(), body))
449}
450
451struct Nonces {
452 seed: [u8; 64],
453 ctr: u32,
454}
455
456impl Nonces {
457 fn next(&mut self) -> Scalar {
458 let mut h = Sha512::new();
459 h.update(self.seed);
460 h.update(self.ctr.to_le_bytes());
461 self.ctr += 1;
462 wide(&h.finalize())
463 }
464}
465
466impl Drop for Nonces {
467 fn drop(&mut self) { self.seed.zeroize(); }
468}
469
470#[allow(clippy::too_many_arguments)]
471fn prove(
472 ring: &Ring,
473 l: usize,
474 k: &Scalar,
475 tau: &RistrettoPoint,
476 u: &RistrettoPoint,
477 scope: &[u8],
478 msg: &[u8],
479 aux: &[u8],
480)
481 -> Outcome<Vec<u8>>
482{
483 let n_ring = ring.len();
484 let m = digits(n_ring);
485 if m > MAX_DIGITS {
486 return Err(err!("linkring: a ring of {} keys needs {} digits, over {}.",
487 n_ring, m, MAX_DIGITS; Invalid, Input, Size));
488 }
489 let g = RISTRETTO_BASEPOINT_POINT;
490 let gens = res!(generators(m));
491 let tau_bytes = tau.compress().to_bytes();
492
493 let mut nonces = {
494 let mut h = Sha512::new();
495 h.update(DST_NONCE);
496 h.update(k.as_bytes());
497 h.update(ring.digest);
498 h.update((n_ring as u64).to_le_bytes());
499 h.update((l as u64).to_le_bytes());
500 h.update((scope.len() as u64).to_le_bytes());
501 h.update(scope);
502 h.update((msg.len() as u64).to_le_bytes());
503 h.update(msg);
504 h.update((aux.len() as u64).to_le_bytes());
505 h.update(aux);
506 let mut seed = [0u8; 64];
507 seed.copy_from_slice(&h.finalize());
508 Nonces { seed, ctr: 0 }
509 };
510
511 // Signer's digits, least significant first.
512 let ld: Vec<usize> = (0..m).map(|j| (l >> (4 * j)) & (RADIX - 1)).collect();
513
514 // a_{j,i}: random for i ≥ 1, a_{j,0} makes each row sum to zero.
515 let mut a = vec![Scalar::ZERO; m * RADIX];
516 for j in 0..m {
517 let mut sum = Scalar::ZERO;
518 for i in 1..RADIX {
519 let s = nonces.next();
520 a[j * RADIX + i] = s;
521 sum += s;
522 }
523 a[j * RADIX] = -sum;
524 }
525 let r_a = nonces.next();
526 let r_b = nonces.next();
527 let r_c = nonces.next();
528 let r_d = nonces.next();
529 let rho: Vec<Scalar> = (0..m).map(|_| nonces.next()).collect();
530
531 // Digit commitments, constant time since they hold secrets.
532 let sigma = |j: usize, i: usize| if ld[j] == i { Scalar::ONE } else { Scalar::ZERO };
533 let mut s_a = Vec::with_capacity(m * RADIX + 1);
534 let mut s_b = Vec::with_capacity(m * RADIX + 1);
535 let mut s_c = Vec::with_capacity(m * RADIX + 1);
536 let mut s_d = Vec::with_capacity(m * RADIX + 1);
537 s_a.push(r_a);
538 s_b.push(r_b);
539 s_c.push(r_c);
540 s_d.push(r_d);
541 for j in 0..m {
542 for i in 0..RADIX {
543 let aji = a[j * RADIX + i];
544 let sji = sigma(j, i);
545 s_a.push(aji);
546 s_b.push(sji);
547 s_c.push(aji * (Scalar::ONE - sji - sji));
548 s_d.push(-(aji * aji));
549 }
550 }
551 let bases: Vec<RistrettoPoint> = std::iter::once(g).chain(gens.iter().copied()).collect();
552 let com_a = RistrettoPoint::multiscalar_mul(&s_a, &bases);
553 let com_b = RistrettoPoint::multiscalar_mul(&s_b, &bases);
554 let com_c = RistrettoPoint::multiscalar_mul(&s_c, &bases);
555 let com_d = RistrettoPoint::multiscalar_mul(&s_d, &bases);
556 for v in [&mut s_a, &mut s_b, &mut s_c, &mut s_d] {
557 v.zeroize();
558 }
559
560 // G_k = Σ_i p_{i,k}·P_i, gathered by the subsets T of digit positions that
561 // contribute a constant; positions outside T are fixed to the signer's.
562 let mut gk = vec![RistrettoPoint::identity(); m];
563 let mut coef_sum = vec![Scalar::ZERO; m];
564 let mut idx_buf: Vec<u32> = Vec::new();
565 let mut sc_buf: Vec<Scalar> = Vec::new();
566 for mask in 1usize..(1 << m) {
567 let pos: Vec<usize> = (0..m).filter(|j| mask & (1 << j) != 0).collect();
568 let t = pos.len();
569 let deg = m - t;
570 let mut base = 0usize;
571 for j in 0..m {
572 if mask & (1 << j) == 0 {
573 base += ld[j] << (4 * j);
574 }
575 }
576 // Mixed-radix counter over T, least significant position fastest, so
577 // the index only rises and the enumeration stops at the ring's end.
578 let mut d = vec![0usize; t];
579 let mut prod = vec![Scalar::ONE; t + 1]; // prod[q] = Π_{q' ≥ q} a
580 for q in (0..t).rev() {
581 prod[q] = prod[q + 1] * a[pos[q] * RADIX];
582 }
583 idx_buf.clear();
584 sc_buf.clear();
585 loop {
586 let mut idx = base;
587 for q in 0..t {
588 idx += d[q] << (4 * pos[q]);
589 }
590 if idx >= n_ring {
591 break;
592 }
593 idx_buf.push(idx as u32);
594 sc_buf.push(prod[0]);
595 coef_sum[deg] += prod[0];
596 if idx_buf.len() == CHUNK {
597 gk[deg] += msm_indexed(&sc_buf, &idx_buf, &ring.points);
598 idx_buf.clear();
599 sc_buf.clear();
600 }
601 // Increment.
602 let mut q = 0;
603 while q < t {
604 d[q] += 1;
605 if d[q] < RADIX {
606 break;
607 }
608 d[q] = 0;
609 q += 1;
610 }
611 if q == t {
612 break;
613 }
614 for q2 in (0..=q).rev() {
615 prod[q2] = prod[q2 + 1] * a[pos[q2] * RADIX + d[q2]];
616 }
617 }
618 if !idx_buf.is_empty() {
619 gk[deg] += msm_indexed(&sc_buf, &idx_buf, &ring.points);
620 }
621 }
622 sc_buf.zeroize();
623 // Padded entries repeat the last key; since every coefficient below x^m
624 // sums to zero over all 16^m entries, theirs is minus the sum seen.
625 let last = ring.points[n_ring - 1];
626 let mut ym = Vec::with_capacity(m);
627 for kk in 0..m {
628 gk[kk] += RistrettoPoint::multiscalar_mul(
629 [-coef_sum[kk], rho[kk]],
630 [last, g],
631 );
632 ym.push(u * rho[kk]);
633 }
634 coef_sum.zeroize();
635
636 let com = Commit { a: com_a, b: com_b, c: com_c, d: com_d, g: gk, y: ym };
637 let x = challenge(ring, m, scope, &tau_bytes, msg, &com);
638 if x == Scalar::ZERO {
639 return Err(err!("linkring: the challenge is zero."; Invalid));
640 }
641
642 // Responses.
643 let mut body = Vec::with_capacity(body_len(m));
644 body.push(m as u8);
645 for p in [&com.a, &com.b, &com.c, &com.d].into_iter().chain(com.g.iter()).chain(com.y.iter()) {
646 body.extend_from_slice(p.compress().as_bytes());
647 }
648 for j in 0..m {
649 for i in 1..RADIX {
650 let f = sigma(j, i) * x + a[j * RADIX + i];
651 body.extend_from_slice(f.as_bytes());
652 }
653 }
654 let z_a = r_b * x + r_a;
655 let z_c = r_c * x + r_d;
656 let mut xp = Scalar::ONE;
657 let mut z = Scalar::ZERO;
658 for kk in 0..m {
659 z -= rho[kk] * xp;
660 xp *= x;
661 }
662 z += k * xp;
663 body.extend_from_slice(z_a.as_bytes());
664 body.extend_from_slice(z_c.as_bytes());
665 body.extend_from_slice(z.as_bytes());
666 a.zeroize();
667 Ok(body)
668}
669
670fn msm_indexed(scalars: &[Scalar], idx: &[u32], points: &[RistrettoPoint]) -> RistrettoPoint {
671 RistrettoPoint::vartime_multiscalar_mul(
672 scalars.iter(),
673 idx.iter().map(|&i| &points[i as usize]),
674 )
675}
676
677// ── Verify ──────────────────────────────────────────────────────────────────
678
679/// Does `body` prove that a member of `ring` signed `msg` under `scope` with
680/// tag `tau`?
681pub fn verify(
682 ring: &Ring,
683 scope: &[u8],
684 msg: &[u8],
685 tau: &[u8],
686 body: &[u8],
687)
688 -> Outcome<bool>
689{
690 verify_par(ring, scope, msg, tau, body, 1)
691}
692
693/// As `verify`, spreading the ring sum over `threads` threads. Use 1 on
694/// wasm32, which has no threads.
695pub fn verify_par(
696 ring: &Ring,
697 scope: &[u8],
698 msg: &[u8],
699 tau: &[u8],
700 body: &[u8],
701 threads: usize,
702)
703 -> Outcome<bool>
704{
705 let m = digits(ring.len());
706 if m > MAX_DIGITS || body.len() != body_len(m) || body[0] as usize != m {
707 return Ok(false);
708 }
709 if tau.len() != TAG_LEN {
710 return Ok(false);
711 }
712 let mut tau_bytes = [0u8; TAG_LEN];
713 tau_bytes.copy_from_slice(tau);
714 let tau_pt = match CompressedRistretto(tau_bytes).decompress() {
715 Some(p) if !p.is_identity() => p,
716 _ => return Ok(false),
717 };
718
719 // Parse.
720 let mut off = 1;
721 let mut pts = Vec::with_capacity(4 + 2 * m);
722 for _ in 0..(4 + 2 * m) {
723 match CompressedRistretto::from_slice(&body[off..off + 32]).ok().and_then(|c| c.decompress()) {
724 Some(p) => pts.push(p),
725 None => return Ok(false),
726 }
727 off += 32;
728 }
729 let mut scs = Vec::with_capacity(m * (RADIX - 1) + 3);
730 for _ in 0..(m * (RADIX - 1) + 3) {
731 let mut b = [0u8; 32];
732 b.copy_from_slice(&body[off..off + 32]);
733 let s: Option<Scalar> = Scalar::from_canonical_bytes(b).into();
734 match s {
735 Some(s) => scs.push(s),
736 None => return Ok(false),
737 }
738 off += 32;
739 }
740 let com = Commit {
741 a: pts[0],
742 b: pts[1],
743 c: pts[2],
744 d: pts[3],
745 g: pts[4..4 + m].to_vec(),
746 y: pts[4 + m..4 + 2 * m].to_vec(),
747 };
748 let z_a = scs[m * (RADIX - 1)];
749 let z_c = scs[m * (RADIX - 1) + 1];
750 let z = scs[m * (RADIX - 1) + 2];
751
752 let x = challenge(ring, m, scope, &tau_bytes, msg, &com);
753 if x == Scalar::ZERO {
754 return Ok(false);
755 }
756
757 // Full response matrix, f_{j,0} = x − Σ_{i≥1} f_{j,i}.
758 let mut f = vec![Scalar::ZERO; m * RADIX];
759 for j in 0..m {
760 let mut sum = Scalar::ZERO;
761 for i in 1..RADIX {
762 let v = scs[j * (RADIX - 1) + i - 1];
763 f[j * RADIX + i] = v;
764 sum += v;
765 }
766 f[j * RADIX] = x - sum;
767 }
768
769 // Digit checks: A + x·B = Com(f; z_A) and x·C + D = Com(f(x − f); z_C).
770 let g = RISTRETTO_BASEPOINT_POINT;
771 let gens = res!(generators(m));
772 let mut s1 = Vec::with_capacity(m * RADIX + 3);
773 let mut s2 = Vec::with_capacity(m * RADIX + 3);
774 s1.push(z_a);
775 s2.push(z_c);
776 for v in &f {
777 s1.push(*v);
778 s2.push(v * (x - v));
779 }
780 s1.push(-Scalar::ONE);
781 s1.push(-x);
782 s2.push(-x);
783 s2.push(-Scalar::ONE);
784 let p1 = std::iter::once(&g).chain(gens.iter()).chain([&com.a, &com.b]);
785 let p2 = std::iter::once(&g).chain(gens.iter()).chain([&com.c, &com.d]);
786 if on(G_DIGITS_AB) && !RistrettoPoint::vartime_multiscalar_mul(&s1, p1).is_identity() {
787 return Ok(false);
788 }
789 if on(G_DIGITS_CD) && !RistrettoPoint::vartime_multiscalar_mul(&s2, p2).is_identity() {
790 return Ok(false);
791 }
792
793 // Tag check: x^m·τ − Σ x^k·Y_k − z·U = 0.
794 let u = res!(scope_base(scope));
795 let mut xpow = Vec::with_capacity(m + 1);
796 let mut xp = Scalar::ONE;
797 for _ in 0..=m {
798 xpow.push(xp);
799 xp *= x;
800 }
801 let mut st = Vec::with_capacity(m + 2);
802 st.push(xpow[m]);
803 for kk in 0..m {
804 st.push(-xpow[kk]);
805 }
806 st.push(-z);
807 let pt = std::iter::once(&tau_pt).chain(com.y.iter()).chain(std::iter::once(&u));
808 if on(G_TAG) && !RistrettoPoint::vartime_multiscalar_mul(&st, pt).is_identity() {
809 return Ok(false);
810 }
811
812 // Ring check: Σ p_i(x)·P_i + pad·P_{N−1} − Σ x^k·G_k − z·G = 0.
813 if !on(G_RING) {
814 return Ok(true);
815 }
816 let (sum_pt, sum_p) = res!(ring_sum(ring, &f, m, threads.max(1)));
817 let mut sr = Vec::with_capacity(m + 2);
818 sr.push(xpow[m] - sum_p);
819 for kk in 0..m {
820 sr.push(-xpow[kk]);
821 }
822 sr.push(-z);
823 let last = &ring.points[ring.len() - 1];
824 let pr = std::iter::once(last).chain(com.g.iter()).chain(std::iter::once(&g));
825 Ok((sum_pt + RistrettoPoint::vartime_multiscalar_mul(&sr, pr)).is_identity())
826}
827
828/// `Σ_{i<N} p_i(x)·P_i` and `Σ_{i<N} p_i(x)`, where `p_i(x) = Π_j f_{j,i_j}`.
829fn ring_sum(
830 ring: &Ring,
831 f: &[Scalar],
832 m: usize,
833 threads: usize,
834)
835 -> Outcome<(RistrettoPoint, Scalar)>
836{
837 let n = ring.len();
838 if threads <= 1 || n < threads * 256 {
839 return Ok(ring_sum_range(ring, f, m, 0, n));
840 }
841 let per = ((n + threads - 1) / threads).max(1);
842 let mut out = Vec::new();
843 std::thread::scope(|s| {
844 let mut handles = Vec::new();
845 let mut lo = 0;
846 while lo < n {
847 let hi = (lo + per).min(n);
848 handles.push(s.spawn(move || ring_sum_range(ring, f, m, lo, hi)));
849 lo = hi;
850 }
851 for h in handles {
852 out.push(h.join());
853 }
854 });
855 let mut pt = RistrettoPoint::identity();
856 let mut sc = Scalar::ZERO;
857 for r in out {
858 match r {
859 Ok((p, s)) => {
860 pt += p;
861 sc += s;
862 }
863 Err(_) => return Err(err!("linkring: a ring sum thread panicked."; Thread)),
864 }
865 }
866 Ok((pt, sc))
867}
868
869fn ring_sum_range(
870 ring: &Ring,
871 f: &[Scalar],
872 m: usize,
873 lo: usize,
874 hi: usize,
875)
876 -> (RistrettoPoint, Scalar)
877{
878 let mut d: Vec<usize> = (0..m).map(|j| (lo >> (4 * j)) & (RADIX - 1)).collect();
879 let mut prod = vec![Scalar::ONE; m + 1]; // prod[j] = Π_{j' ≥ j} f_{j', d_j'}
880 for j in (0..m).rev() {
881 prod[j] = prod[j + 1] * f[j * RADIX + d[j]];
882 }
883 let mut pt = RistrettoPoint::identity();
884 let mut total = Scalar::ZERO;
885 let mut buf = Vec::with_capacity(CHUNK.min(hi - lo));
886 let mut start = lo;
887 for i in lo..hi {
888 buf.push(prod[0]);
889 total += prod[0];
890 if buf.len() == CHUNK {
891 pt += RistrettoPoint::vartime_multiscalar_mul(buf.iter(), ring.points[start..=i].iter());
892 buf.clear();
893 start = i + 1;
894 }
895 // Next index.
896 let mut j = 0;
897 while j < m {
898 d[j] += 1;
899 if d[j] < RADIX {
900 break;
901 }
902 d[j] = 0;
903 j += 1;
904 }
905 let top = j.min(m - 1);
906 for j2 in (0..=top).rev() {
907 prod[j2] = prod[j2 + 1] * f[j2 * RADIX + d[j2]];
908 }
909 }
910 if !buf.is_empty() {
911 pt += RistrettoPoint::vartime_multiscalar_mul(buf.iter(), ring.points[start..hi].iter());
912 }
913 (pt, total)
914}
915
916#[cfg(test)]
917mod tests {
918 use super::*;
919
920 fn ring_of(n: usize) -> Outcome<(Vec<SecretKey>, Ring)> {
921 let mut keys = Vec::with_capacity(n);
922 for i in 0..n {
923 keys.push(res!(SecretKey::from_seed(fmt!("k{}", i).as_bytes())));
924 }
925 let pubs: Vec<[u8; 32]> = keys.iter().map(|k| k.public_key()).collect();
926 let ring = res!(Ring::from_keys(&pubs));
927 Ok((keys, ring))
928 }
929
930 fn with_skip<T>(g: u32, f: impl FnOnce() -> T) -> T {
931 SKIP.with(|s| s.set(g));
932 let out = f();
933 SKIP.with(|s| s.set(0));
934 out
935 }
936
937 fn scalar_at(body: &[u8], off: usize) -> Scalar {
938 let mut b = [0u8; 32];
939 b.copy_from_slice(&body[off..off + 32]);
940 Scalar::from_bytes_mod_order(b)
941 }
942
943 fn put_scalar(body: &mut [u8], off: usize, s: Scalar) {
944 body[off..off + 32].copy_from_slice(s.as_bytes());
945 }
946
947 // Offsets of z_A, z_C and z in a body of m digits.
948 fn z_offsets(m: usize) -> (usize, usize, usize) {
949 let base = 1 + 32 * (4 + 2 * m + 15 * m);
950 (base, base + 32, base + 64)
951 }
952
953 // Guard G_MSG: the message is bound only by the transcript.
954 #[test]
955 fn test_guard_message() -> Outcome<()> {
956 let (keys, ring) = res!(ring_of(5));
957 let (t, b) = res!(with_skip(G_MSG, || sign_with_aux(&ring, &keys[2], b"s", b"m1", b"")));
958 req!(res!(with_skip(G_MSG, || verify(&ring, b"s", b"m2", &t, &b))), true, "guard off");
959 let (t, b) = res!(sign_with_aux(&ring, &keys[2], b"s", b"m1", b""));
960 req!(res!(verify(&ring, b"s", b"m2", &t, &b)), false, "guard on");
961 Ok(())
962 }
963
964 // Guards G_DIGITS_AB and G_DIGITS_CD: z_A and z_C sit in no other check.
965 #[test]
966 fn test_guard_digit_checks() -> Outcome<()> {
967 let (keys, ring) = res!(ring_of(5));
968 let (t, b) = res!(sign_with_aux(&ring, &keys[1], b"s", b"m", b""));
969 let (oa, oc, _) = z_offsets(1);
970 for (g, off) in [(G_DIGITS_AB, oa), (G_DIGITS_CD, oc)] {
971 let mut bad = b.clone();
972 put_scalar(&mut bad, off, scalar_at(&b, off) + Scalar::ONE);
973 req!(res!(with_skip(g, || verify(&ring, b"s", b"m", &t, &bad))), true, "guard {} off", g);
974 req!(res!(verify(&ring, b"s", b"m", &t, &bad)), false, "guard {} on", g);
975 }
976 Ok(())
977 }
978
979 // Guard G_TAG, and the no-frame property: a member cannot carry another
980 // member's tag, even one it has seen, because the tag relation extracts
981 // the signer's own key.
982 #[test]
983 fn test_guard_tag_no_frame() -> Outcome<()> {
984 let (keys, ring) = res!(ring_of(20));
985 let scope = b"present/1:https://app.example";
986 let msg = b"m";
987 let u = res!(scope_base(scope));
988 let tau_b = u * keys[7].0;
989 let tb = tau_b.compress().to_bytes();
990 let body = res!(prove(&ring, 3, &keys[3].0, &tau_b, &u, scope, msg, b""));
991 req!(res!(with_skip(G_TAG, || verify(&ring, scope, msg, &tb, &body))), true, "guard off");
992 req!(res!(verify(&ring, scope, msg, &tb, &body)), false, "guard on");
993 // The tag's own key proves it.
994 let body = res!(prove(&ring, 7, &keys[7].0, &tau_b, &u, scope, msg, b""));
995 req!(res!(verify(&ring, scope, msg, &tb, &body)), true, "honest");
996 Ok(())
997 }
998
999 // Guard G_RING: without the ring relation anyone signs with no key at
1000 // all, by proving a made-up secret against the tag base alone.
1001 #[test]
1002 fn test_guard_ring_keyless_forgery() -> Outcome<()> {
1003 let (_, ring) = res!(ring_of(20));
1004 let fake = res!(SecretKey::from_seed(b"not in the ring"));
1005 let u = res!(scope_base(b"s"));
1006 let tau = u * fake.0;
1007 let tb = tau.compress().to_bytes();
1008 let body = res!(prove(&ring, 4, &fake.0, &tau, &u, b"s", b"m", b""));
1009 req!(res!(with_skip(G_RING, || verify(&ring, b"s", b"m", &tb, &body))), true, "guard off");
1010 req!(res!(verify(&ring, b"s", b"m", &tb, &body)), false, "guard on");
1011 Ok(())
1012 }
1013
1014 // Guard G_DIGEST: without the ring in the transcript a forger fixes the
1015 // proof first and then solves for a ring key that satisfies it.
1016 #[test]
1017 fn test_guard_digest_ring_after_challenge() -> Outcome<()> {
1018 let (keys, _) = res!(ring_of(2));
1019 let p0 = keys[0].public_key();
1020 let q = res!(SecretKey::from_seed(b"placeholder")).public_key();
1021 let fake = res!(SecretKey::from_seed(b"forger"));
1022 let u = res!(scope_base(b"s"));
1023 let tau = u * fake.0;
1024 let tb = tau.compress().to_bytes();
1025 let forge = |guard_off: bool| -> Outcome<bool> {
1026 let skip = if guard_off { G_DIGEST } else { 0 };
1027 with_skip(skip, || {
1028 let placeholder = res!(Ring::from_keys(&[p0, q]));
1029 let body = res!(prove(&placeholder, 1, &fake.0, &tau, &u, b"s", b"m", b""));
1030 // Recompute x as the verifier will, then solve for P_1 in
1031 // f_0·P_0 + (Σ_{i≥1} f_i)·P_1 − G_0 = z·G.
1032 let mut pts = Vec::new();
1033 for i in 0..6 {
1034 let c = res!(CompressedRistretto::from_slice(&body[1 + 32 * i..33 + 32 * i])
1035 .map_err(|_| err!("slice"; Test)));
1036 pts.push(res!(c.decompress().ok_or_else(|| err!("point"; Test))));
1037 }
1038 let com = Commit { a: pts[0], b: pts[1], c: pts[2], d: pts[3],
1039 g: vec![pts[4]], y: vec![pts[5]] };
1040 let x = challenge(&placeholder, 1, b"s", &tb, b"m", &com);
1041 let mut rest = Scalar::ZERO;
1042 for i in 0..15 {
1043 rest += scalar_at(&body, 1 + 32 * 6 + 32 * i);
1044 }
1045 let f0 = x - rest;
1046 let (_, _, oz) = z_offsets(1);
1047 let z = scalar_at(&body, oz);
1048 let p0_pt = placeholder.points[0];
1049 let p1 = (RISTRETTO_BASEPOINT_POINT * z + com.g[0] - p0_pt * f0) * rest.invert();
1050 let ring = res!(Ring::from_keys(&[p0, p1.compress().to_bytes()]));
1051 verify(&ring, b"s", b"m", &tb, &body)
1052 })
1053 };
1054 req!(res!(forge(true)), true, "guard off");
1055 req!(res!(forge(false)), false, "guard on");
1056 Ok(())
1057 }
1058
1059 // The prover's subset expansion must equal the plain coefficient sum, at
1060 // every index and every ring size across a digit boundary.
1061 #[test]
1062 fn test_sizes_across_digit_boundaries() -> Outcome<()> {
1063 for n in [1usize, 2, 15, 16, 17, 255, 256, 257, 300] {
1064 let (keys, ring) = res!(ring_of(n));
1065 for l in [0, n / 2, n - 1] {
1066 let (t, b) = res!(sign_with_aux(&ring, &keys[l], b"s", b"m", b""));
1067 req!(b.len(), body_len(digits(n)));
1068 req!(res!(verify(&ring, b"s", b"m", &t, &b)), true, "n={} l={}", n, l);
1069 }
1070 }
1071 Ok(())
1072 }
1073}