Skip to main content

binius_verifier/
signature.rs

1// Copyright 2026 The Binius Developers
2
3//! Signature of knowledge support.
4//!
5//! A Binius64 proof is a non-interactive proof of knowledge: an interactive protocol made
6//! non-interactive with the Fiat-Shamir transform. Such a proof can be converted into a
7//! *signature of knowledge* (SoK) over a message `m` by binding `m` into the Fiat-Shamir
8//! transcript before any other data is observed. The verifier then needs the message in order
9//! to recompute the same transcript and check the proof; a proof produced for one message does
10//! not verify against any other message.
11//!
12//! Rather than observing the message bytes directly, we observe the *hash* of the message,
13//! computed with the same hash function the Merkle commitment scheme uses for its leaves
14//! ([`HashSuite::LeafHash`]). This keeps the amount of data fed into the challenger fixed-size
15//! and independent of the message length, and insulates the construction from future changes to
16//! the transcript API.
17//!
18//! The message (and its hash) are *observed* into the transcript, not written to the proof tape:
19//! they affect the Fiat-Shamir challenges but are not part of the serialized proof. The verifier
20//! must supply the message out of band, exactly as a signature verifier supplies the signed
21//! message.
22//!
23//! Signing is only exposed on the zero-knowledge prover and verifier (`ZKProver::prove_sig` and
24//! [`ZKVerifier::verify_sig`](crate::zk_config::ZKVerifier::verify_sig)): a signature of knowledge
25//! should not reveal the witness it is signed under, and only the ZK configuration hides the
26//! witness. The [`observe_message`] helper below is generic over the hash suite and is shared by
27//! both.
28//!
29//! # Security analysis
30//!
31//! - **Binding / non-malleability.** The message hash is observed *first*, before the public input
32//!   and before the prover's witness commitment. Every subsequent Fiat-Shamir challenge therefore
33//!   depends on the message. An adversary who is given a valid proof for message `m` cannot maul it
34//!   into a valid proof for a different message `m'`: changing the message changes the first
35//!   challenger absorption and hence every sampled challenge, so the rest of the (replayed) proof
36//!   no longer satisfies the verifier's checks. This is the standard "strong Fiat-Shamir"
37//!   requirement that the full statement — here extended with the message — be bound into the
38//!   transcript.
39//!
40//! - **Reduction to collision resistance.** Because we bind `H(m)` rather than `m`, the binding is
41//!   only as strong as the collision resistance of `H = HashSuite::LeafHash`. If an adversary finds
42//!   `m != m'` with `H(m) = H(m')`, a signature on `m` also verifies for `m'`. The leaf hashes used
43//!   by the shipped suites (SHA-256) are collision resistant, so this is not a practical concern;
44//!   it is the same assumption the Merkle commitment already relies on.
45//!
46//! - **Knowledge soundness is preserved.** Observing extra public data at the start of the
47//!   transcript does not weaken the soundness of the underlying argument: it is equivalent to
48//!   running the original protocol on a statement augmented with a public message-hash that does
49//!   not participate in any constraint. A forger who cannot satisfy the constraint system still
50//!   cannot, for any message.
51//!
52//! - **Zero knowledge is preserved.** The message hash is public input to the Fiat-Shamir transform
53//!   and never touches the witness, so binding it leaks nothing about the witness in the ZK
54//!   configuration.
55//!
56//! - **Prover/verifier must agree on the mode.** Whether a message is bound, and what it is, is not
57//!   encoded in the proof. A verifier that checks a SoK proof without the message (or with the
58//!   wrong message) samples different challenges and rejects. Callers must therefore agree out of
59//!   band on whether a proof is a plain proof of knowledge or a signature of knowledge. Note that
60//!   an empty message (`Some(&[])`, which binds `H("")`) is distinct from no message at all
61//!   (`None`, which binds nothing).
62
63use binius_hash::HashSuite;
64use binius_transcript::{BufMut, TranscriptWriter};
65use digest::Digest;
66
67/// Observes the hash of a signed message into a transcript, turning a proof of knowledge into a
68/// signature of knowledge.
69///
70/// The message is hashed with `H::LeafHash` (the Merkle scheme's leaf hash) and the resulting
71/// digest is observed into the transcript via the provided observing writer. Both the prover and
72/// the verifier must call this with the same message *before any other transcript interaction*.
73///
74/// The `writer` must be an *observing* writer (obtained from `transcript.observe()`), so the
75/// digest is mixed into the Fiat-Shamir state without being written to the proof tape.
76pub fn observe_message<H, B>(writer: &mut TranscriptWriter<'_, B>, message: &[u8])
77where
78	H: HashSuite,
79	B: BufMut,
80{
81	let digest = <H::LeafHash as Digest>::digest(message);
82	writer.write_bytes(digest.as_ref());
83}