ethereum / ethereum/sonobe

Nova decider possibly accepts proofs for arbitrary statements

Open
#280 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
285
Forks
97
PR merge metrics
No merged PRs in 30d

Description

There is a possible soundness concern where the implementation deviates from the Nova paper. Any feedback would be appreciated.

The Nova on-chain decider splits the check `NIFS.V(r, U_n, u_n, T̄) = U_{n+1}` into an in-circuit
half (step 6.1, the field elements `u` and `x`) and a native half (step 6.2, the commitments).
Neither half is joined to the other:

1. **The fold challenge `r` is unconstrained.** `DeciderNovaGadget::fold_field_elements_gadget`
receives it as `_randomness` and ignores it, and `proof.r` is not among the Groth16 public
inputs. The circuit derives its own Fiat-Shamir challenge and uses it for the field elements;
the verifier folds the commitments with whatever `r` the prover sent.
2. **The commitments folded natively are unauthenticated.** `Decider::verify` receives
`running_commitments` and `incoming_commitments` from the caller (in the Solidity verifier,
straight from calldata) and folds them, but nothing — in-circuit or natively — ties them to the
`U_i` / `u_i` that the circuit's hash check (step 3) binds to the IVC chain. Both are private
witnesses in the circuit.

Because the relaxed-R1CS check (step 1) uses a **private, unconstrained error vector** `W_{i+1}.E`,
gap 2 alone makes the entire statement forgeable: a prover picks any `W`, *solves* step 1 for
`E := Az∘Bz − u'·Cz`, commits to both with the public KZG SRS, and submits those commitments as the
"running instance" commitments. Every remaining check then passes honestly.

As a result **`Decider::verify` accepts a proof for an arbitrary `(i, z_0, z_i)`**, using only public
artifacts — no witness, no IVC step, no interaction. Verified end-to-end (see PoC below).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with Decider::verify and DeciderNovaGadget::fold_field_elements_gadget, then compare their handling of r, commitments, and the relaxed-R1CS check with the Nova paper. Reproduce the reported end-to-end proof acceptance and identify the relevant verification tests; done means arbitrary statements can no longer pass and the missing bindings are covered by regression tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
blockchain, cryptography, security
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
28/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.