distributed-lab / distributed-lab/op_rand
Soundness bug: `ScalarField::from_bignum` returns unconstrained brillig wNAF decomposition (slices not bound to input scalar)
- Dominant language
- Noir
- Stars
- 15
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Description
## The bug
The circuit takes a secret number `x` and breaks it into a digit-like representation (a wNAF **decomposition**, a list of `slices`) by asking an **unconstrained hint** (`get_wnaf_slices2`). The function `ScalarField::from_bignum` then uses those slices directly, **without ever checking that the slices add back up to `x`**.
**The bug: the decomposition is never bound to the input.** Because the slices come from an unconstrained (prover-controlled) hint and nothing asserts `reconstruct(slices) == x`, as a result, a malicious prover can hand in the decomposition of a **completely different number**, and the circuit happily does its elliptic-curve math on *that* number instead of `x`. The committed value and the value the proof actually uses come apart.
## Example
Think of the `slices` as the **digits** of the committed number. Suppose a player commits to `x = 53`. Run honestly, the hint hands back its digits, `5` and `3`, and the circuit reads them as `5×10 + 3 = 53` and does its curve math on 53.
But nothing makes the circuit add those digits back up. So a cheating player hands back the digits `7` and `1` instead. The circuit never computes `7×10 + 1 = 71` to compare against the committed `53`, it just takes the digits and multiplies as if they were valid, doing its math on **71** while the proof still claims to be about `53`. Both runs produce a valid proof for the same committed input, because the one check that would separate `53`'s digits from `71`'s, *"do these digits actually add up to `x`?"*, is the missing constraint. And a potentially malicious prover can decide which number is really used.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.