Module 0x1::sigma_protocol_homomorphism

This module can be used to build $\Sigma$-protocols for proving knowledge of a pre-image on a homomorphism $\psi$.

Let $\mathbb{G}^{n_1} \times \mathbb{F}^{n_2}$ denote the set of public statements.

This module helps you convince a verifier with $X\in S$ that you know a secret $w\in \mathbb{F}^k$ such that $\psi(w) = f(X)$, where:

$\psi : \mathbb{F}^k \rightarrow \mathbb{G}^m$ is a homomorphism, and $f : \mathbb{G}^{n_1} \times \mathbb{F}^{n_2} \rightarrow \mathbb{G}^m$ is a transformation function.

Many useful statements can be proved in ZK by framing them as proving knowledge of a pre-image on a homomorphism:

e.g., a Schnorr signature is just proving knowledge of $x$ such that $\psi(x) = x G$, where the PK is $x G$.

e.g., a proof that $C_1, C_2$ both Pedersen-commit to the same $m$ is proving knowledge of $(m, r_1, r_2)$ s.t. $\psi(m, r_1, r_2) = (m G + r_1 H, m G + r_2 H)$

The sigma protocol is very simple:

• —————— + + ———————————————— + | Prover has $(X, w)$ | | Verifier has |
• —————— + | $X \in \mathbb{G}^{n_1} \times \mathbb{F}^{n_2}$ |
• ———————————————— +

1. Sample $\alpha \in \mathbb{F}^k

2. Compute commitment $A \gets \psi(\alpha)$

3. send commitment $A$ —————————––>

4. Assert $A \in \mathbb{G}^m$

5. Pick random challenge $e$ (via Fiat-Shamir on: $(X, A)$ a protocol identifier and a session identifier)

6. send challenge $e$ <—————————––

7. Compute response $\sigma = \alpha + e \cdot w$

8. send response $\sigma$ —————————––>

9. Check $\psi(\sigma) = A + e f(X)$

• Struct TransformationFunction
• Struct Homomorphism

use 0x1::sigma_protocol_representation_vec;
use 0x1::sigma_protocol_statement;
use 0x1::sigma_protocol_witness;

Struct TransformationFunction

The transformation function $f : \mathbb{G}^{n_1} \times \mathbb{F}^{n_2} \rightarrow \mathbb{G}^m$

struct TransformationFunction<P>

Struct Homomorphism

The homomorphism $\psi : \mathbb{F}^k \rightarrow \mathbb{G}^m$

struct Homomorphism<P>