distributed-lab / distributed-lab/op_rand

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

Open
#9 0 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.