Module 0x1::sigma_protocol
Constants
One of our internal invariants was broken. There is likely a logical error in the code.
const E_INTERNAL_INVARIANT_FAILED: u64 = 2;
The length of the A field in Proof did NOT match the homomorphism’s output length
const E_PROOF_COMMITMENT_WRONG_LEN: u64 = 1;
Function verify
Verifies a ZK proof that the prover knows a witness $w$ such that $f(X) = \psi(w)$ where $X$ is the
statement in stmt.
Optimized to perform a faster batched verification: A + e f(X) - \psi(\sigma) = zero() <=> \forall i \in[m], A[i] + e f(X)[i] - \psi(\sigma)[i] = 0 <=> \sum_{i \in [m]} \beta[i] A[i] + \beta[i] ( e f(X)[i] ) - \beta[i] ( \psi(\sigma)[i] ) = 0, for random \beta[i]’s (picked via Fiat-Shamir)
Note: I don’t think picking $\beta_i$’s via on-chain randomness will save that much gas. Plus, we do not want to premise the security of confidential assets on the unpredictability of on-chain randomness.
@param dst application-specific domain separator (e.g., “Aptos confidential assets protocol v2025.06 :: public withdrawal NP relation”)
@param psi a homomorphism mapping a vector of scalars to a vector of $m$ group elements, except each group
element is returned as a Representation so that, later on, the main $\psi(\sigma) = A + e f(X)$
can be done efficiently in one MSM.
@param f transformation function takes takes in the public statement and outputs $m$ group elements, also
returned as a RepresentationVec.
@param stmt the public statement $X$ that satisfies $f(X) = \psi(w)$ for some secret witness $w$
@param proof the ZKP proving that the prover knows a $w$ s.t. $f(X) = \psi(w)$
Returns true if it succeeds and false otherwise.
public(friend) fun verify<P>(dst: sigma_protocol_fiat_shamir::DomainSeparator, psi: sigma_protocol_homomorphism::Homomorphism<P>, f: sigma_protocol_homomorphism::TransformationFunction<P>, stmt: &sigma_protocol_statement::Statement<P>, proof: &sigma_protocol_proof::Proof): bool
Implementation
public(friend) inline fun verify<P>(
dst: DomainSeparator,
psi: Homomorphism<P>,
f: TransformationFunction<P>,
stmt: &Statement<P>,
proof: &Proof,
): bool {
// Step 1: Fiat-Shamir transform on `(dst, (psi, f), stmt)` to derive the random challenge `e`
let _A = proof.get_commitment();
let m = _A.length();
let (e, betas) = fiat_shamir(dst, stmt, proof.get_compressed_commitment(), proof.get_response_length());
// Step 2:
let psi_sigma = psi(stmt, &proof.response_to_witness());
let efx = f(stmt);
assert!(m == psi_sigma.length(), error::invalid_argument(E_PROOF_COMMITMENT_WRONG_LEN));
assert!(m == efx.length(), error::invalid_argument(E_PROOF_COMMITMENT_WRONG_LEN));
// "Scale" all the representations in `f(stmt)` by `e`. (Implicit assumption here is that `f` is homomorphic:
// i.e., `e f(X) = f(eX)`, which holds because our `f`'s are a `RepresentationVec`.)
efx.scale_all(&e);
// "Scale" the `i`th reprentation in `efx` by `\beta[i]`
efx.scale_each(&betas);
// "Scale" the `i`th reprentation in `\psi` by `-\beta[i]`
// TODO(Perf): I think this could be sub-optimal: we will redo the same \beta[i] \sigma[j] multiplication several times
// when a `RepresentationVec`'s row reuses \sigma[j].
psi_sigma.scale_each(&neg_scalars(&betas));
// We start with an empty MSM: \sum_{i \in m} 0
// ...and extend it to: \sum_{i \in [m]} A[i]^{\beta[i]}
// ^^^^^^^^^^^^^^^
let bases = points_clone(_A);
let scalars = betas;
// These asserts will only fail when we have mis-implemented the cloning of `A` above
assert!(bases.length() == m, error::internal(E_INTERNAL_INVARIANT_FAILED));
assert!(scalars.length() == m, error::internal(E_INTERNAL_INVARIANT_FAILED));
// Extend MSM to: be \sum_{i \in [m]} A[i]^\beta[i] + \beta[i] ( e f(stmt)[i] )
// ^^^^^^^^^^^^^^^^^^^^^^^^^
efx.for_each_ref(|repr| {
bases.append(repr.to_points(stmt));
scalars.append(*repr.get_scalars());
});
// Extend MSM to: be \sum_{i \in [m]} A[i]^\beta[i] + \beta[i] ( e f(stmt)[i] ) - \beta[i] (\psi(\sigma)[i])
// ^^^^^^^^^^^^^^^^^^^^^^^^^^
psi_sigma.for_each_ref(|repr| {
bases.append(repr.to_points(stmt));
scalars.append(*repr.get_scalars());
});
// TODO(Perf): Could combine exponents for shared bases more aggresively? Or does the MSM code do it implicitly?
// Do the MSM and check it equals the (zero) identity
multi_scalar_mul(&bases, &scalars).point_equals(&point_identity())
}