Extends BUSS with random evaluation points hidden behind a one-way function. Corrupt guardians can be identified and their guilt proven; honest guardians cannot be falsely accused — any valid accusation requires producing an OWF preimage.
Traceable BUSS extends BUSS with two structural changes. First, each guardian's
evaluation point xⱼ is a random field element rather than the integer index j.
Second, the trace key stores H(xⱼ) — a one-way hash image — rather than xⱼ
directly, so trace key and verification key coincide:
tk = vk = (H(x₁), …, H(xₙ₋₁)). Together these give
non-imputability: to accuse guardian j, the tracer must produce xⱼ as
a witness, and the verifier checks H(witness) = vk[j]. Forging a false accusation
requires inverting the hash.
The tracing mechanism mirrors Traceable Shamir, generalised to the bottom-up setting:
given the leaked shares of up to f ≤ t corrupt guardians, trace()
reconstructs against synthesized fresh shares plus one perturbed probe point per query,
collecting noisy evaluations of a degree-f "traitor polynomial". Guruswami-Sudan list
decoding recovers that polynomial — and hence the corrupt xⱼ as its roots — even when
some queries disagree, so tracing works from an imperfect reconstruction box, not
only the all-t-corrupted "perfect box" case.
hash_fr(label, x) = H(label ‖ x_bytes)
reduced to a field element via FromUniformBytes<64> (SHA-512 or
BLAKE2b-512). Domain separation (a distinct label per scheme) prevents
cross-protocol attacks — the same helper is shared with Traceable Shamir.
Same as BUSS: each guardian j computes σⱼ = H(owner_id ‖ skⱼ).
They additionally choose a random evaluation point
xⱼ ←$ 𝔽*, distinct from every other guardian's.
The owner interpolates q through
(0, s), (x₁, σ₁), …, (xₙ₋₁, σₙ₋₁), then evaluates it at
n−t−1 fresh points (derived by hashing q's coefficients, since split has no RNG
input) to produce φ. compute_tracing_keys
derives vk = (H(x₁), …, H(xₙ₋₁)) — published as the
verification key.
Any t+1 guardians combine their (xⱼ, σⱼ) with φ — exactly
n points of the degree-(n−1) polynomial q — to recover s = q(0) via Lagrange
interpolation.
Given the f leaked guardian shares, trace() issues N
reconstruction queries — each combining the leaked shares, t−f fresh synthetic
shares, and one δ-shifted probe point — to collect noisy evaluations of the traitor
polynomial h*(X) = Πj corrupt(xⱼ − X)/xⱼ. Guruswami-Sudan list decoding
recovers h*; its roots are matched to guardians by re-hashing and comparing against
vk. verify_trace checks
H(witness[k]) == vk[accused[k]] for each accusation.
use arc_pleiades::TraceableBuss;
use arc_pleiades::bottom_up::buss::Share;
use arc_pleiades::bottom_up::{BottumUpSS, TraceableBSS};
use midnight_curves::Fq as Scalar;
use sha2::Sha512;
use rand::thread_rng;
let mut rng = thread_rng();
// t=3, n=6: threshold=4, 5 guardian shares, |φ|=2, traces up to f=1 leaker
let tbuss = TraceableBuss::<Sha512>::new(3, 6, 1, 4)?;
let secret = Scalar::random(&mut rng);
// Each guardian independently picks a random eval point and derives σ from their key
let shares: Vec<Share<Scalar>> = (0..5)
.map(|_| Share { x: Scalar::random(&mut rng), y: Scalar::random(&mut rng) })
.collect();
// Owner interpolates q through (0,s) and the guardian shares; publishes φ
let phi = tbuss.split(secret, &shares)?;
let (tk, vk) = tbuss.compute_tracing_keys(&shares)?;
// Recovery: any 4 guardian shares + φ = n evaluations of q
let recovered = tbuss.reconstruct(&phi, &shares[..4])?;
assert_eq!(secret, recovered);
// ── Tracing: guardian at index 2 leaked their share ──
let corrupted = [Share { x: shares[2].x, y: shares[2].y }];
let (accused, witness) = tbuss.trace(&tk, &phi, &corrupted, &mut rng)?
.expect("should find the corrupt guardian");
assert_eq!(accused, vec![2]);
tbuss.verify_trace(&accused, &witness, &vk)?;