Soundness bug: `ScalarField::from_bignum` returns unconstrained brillig wNAF decomposition (slices not bound to input scalar)

[anon-researchers-123]

Explanation of the bug

ScalarField::from_bignum in distributed-lab/op_rand (circuits/crates/common/src/secp256k1/scalar_field.nr) takes a BigNum, calls a brillig hint get_wnaf_slices2 to decompose it into wNAF form (slices, skew), and returns the decomposition without any constraint that the decomposition reconstructs to the input.

A malicious prover can supply arbitrary (slices, skew) for ANY input scalar, and the function accepts them. Downstream secp256k1 scalar multiplication (G.mul(scalar) in challenger_circuit, which derives the commitment points and the Bitcoin address checked against public inputs) consumes the unverified decomposition directly, allowing an attacker to substitute a different scalar than the one nominally being multiplied.

Caller propagation in op_rand

The from_bignum function is used by the production binary at four sites in challenger_circuit/src/main.nr (lines 47, 48, 56, 57). Each result feeds G.mul(scalar) (secp256k1 scalar multiplication implemented in secp256k1/curve_jac.nr / mod.nr). The relevant flow:

let a1: Secp256k1Fq = BigNum::from_be_bytes(a1);          // a1, a2 are PRIVATE witnesses
let a1_scalar: ScalarField<65> = ScalarField::from_bignum(a1);  // <-- unconstrained slices
let A1 = G.mul(a1_scalar);                                // point uses prover-controlled scalar
let A1_H: Secp256k1Fq = BigNum::from_be_bytes(sha256(point_to_bytes(A1)));
let A1_H_scalar: ScalarField<65> = ScalarField::from_bignum(A1_H);  // <-- unconstrained again
let A1_H_G = G.mul(A1_H_scalar);
assert(A1_H_G == H1);                                     // H1, H2, PK, ADDR are PUBLIC
...
assert(addr_a1 == ADDR | addr_a2 == ADDR);

Every scalar that flows through from_bignum is bound to its input only by the (missing) constraint, so the ScalarField value that G.mul actually consumes is a free, prover-chosen witness rather than a function of the input bignum.

Exploitability. OP_RAND settles a winner-takes-all bet on real Bitcoin: each side locks in a hidden commitment up front, and the protocol opens those commitments later to decide who wins. The whole thing is only fair if a player is truly stuck with the one value they committed, they must not be able to change it after seeing how the round is going. This bug removes that lock: the circuit never checks that the value a player committed to is the value their proof actually uses. And this isn't just theoretical, we got the real verifier to accept a perfectly valid proof for a commitment setup that an honest player could never have produced, one the legitimate process can't even generate. So a passing proof no longer means a player is honestly pinned to a single commitment, exactly the foothold a cheater needs to wriggle out of their commitment instead of being bound by it. Where that leads, keeping your options open and steering the round to take the other player's Bitcoin, is the very thing a money-settling protocol must prevent; we show the lock is broken, and stop short of carrying out the full theft.

Fix. In from_bignum, after getting the slices from the brillig hint, reconstruct the scalar from those slices and assert it equals the input x, this is the binding the function currently omits, so any incorrect decomposition is rejected. Do the reconstruction with this file's own Into digit-sum (not into_bignum, which is a broken inverse at this width) and range-check each slice to 4 bits so the digits are well-formed. With that check in place the substituted decomposition no longer reconstructs to x, and witness generation fails.

PoC

The PoC packaged is provided in the attachment.

poc.zip

A reproduction that links the actual op_rand library, verbatim is attached under poc/. The harness mirrors challenger_circuit/main.nr: it builds a real secp256k1 field element, calls the real ScalarField::<65>::from_bignum (the production width), and returns the wNAF slices the function produced, the exact quantity the production consumer G.mul(scalar) uses.

Steps to reproduce:

bash poc/attack/run.sh
# [1] HONEST   : honest verify: OK (exit 0)
# [2] MALICIOUS: prove(HONEST circuit, MALICIOUS witness): OK
#                verify(HONEST vk, MALICIOUS proof): OK (exit 0)   <== SOUNDNESS BREAK
# [3] FIX      : fixed + HONEST brillig   : witness produced (assert passes)  OK
#                fixed + MALICIOUS brillig: rejected at witness-gen (assert fires)  GOOD

For the same public input x = 5, the honest brillig hint emits the wNAF slices of 5 ([8,0,…,0,2]); a one-line malicious patch to the (unconstrained) hint makes it emit the slices of 7 ([8,0,…,0,3]). Both witnesses are proved against the one honest circuit (compiled from the pristine library) and both verify under the one honest verification key. Two distinct accepted (input, output) pairs share the same public input ⇒ the prover, not x, controls the scalar.

Why both pass: from_bignum never constrains the brillig output against x. The slices are unconstrained witness values; the verification key does not depend on the brillig hint, so the honest verifier accepts the substituted slices. (Independent corroboration: beta.1's own under-constrained-brillig checker prints bug: Brillig function call isn't properly covered by a manual constraint at scalar_field.nr:210 during nargo execute.)