# 8.3 Preparation

The Sigma protocol is a special type of three-stage (3-move) interactive zero-knowledge proof protocol. The so-called "interactive" means that the prover (Prover) and the verifier (Verifier) ​​need to communicate back and forth multiple times to complete the proof. Its name "Σ" comes from the shape of its communication process, which is similar to the Greek letter Sigma (Σ) and contains three core steps:

Commitment: sent by the prover to the verifier.

Challenge: Sent by the verifier to the prover.

Response: Sent by the prover to the verifier, and the verifier verifies accordingly.

Suppose the prover (P) wants to prove to the verifier (V) that he knows some secret information (such as the solution of a discrete logarithm) without revealing the information itself. A typical sigma protocol runs as follows:

Step One: Commitment

Prover (P) -> Verifier (V)

The prover generates a random nonce and uses this nonce to compute a commitment (a). The promise often appears random, hiding nonce values ​​and secret information but being mathematically related to them.

The prover sends the promise a to the verifier.

Step 2: Challenge

Verifier (V) -> Prover (P)

After the verifier receives the commitment, it randomly selects a challenge value (e) and sends it to the prover.

This challenge value is randomized, ensuring that the prover cannot prepare the answer in advance.

Step 3: Response

Prover (P) -> Verifier (V)

After the prover receives the challenge value, it calculates a response (z) using the secret information it possesses, the temporary value generated in the first step, and the challenge value received.

The prover sends response z to the verifier.

Verification

After the verifier receives the response, it uses the previously received commitment a, the challenge e issued by itself, and the response z to perform calculations through a specific verification equation.

If the equation holds, the verifier accepts the proof (i.e., believes that the prover does know the secret); otherwise, it rejects.

The Sigma protocol is powerful because it simultaneously satisfies the following three core security properties:

Completeness:

If the prover does have the correct secret information, and both parties are honest in executing the agreement, the verifier will always accept the proof.

Simply put: Honest people always prove themselves.

Special Honest-Verifier Zero-Knowledge (SHVZK):

"Zero-knowledge" means that all the verifier learns from the protocol is the fact that the prover knows the secret, without any information about the secret itself.

"Specially honest validator" means that this property holds when the validator randomly chooses the challenge value honestly. This means that for a pre-fixed challenge value, anyone can simulate

Produce a transcript of the conversation (commitment, challenge, response) that looks completely real, and this simulated transcript does not require any secret information to generate. This proves that the response does not contain any additional secret information.

Special Soundness:

This is a very strong attribute. It states:

If a prover can generate two valid responses (z and z') that can both be verified for two different challenge values ​​(e and e') for the same commitment a, then the prover's secret information must be extracted from them.

To put it simply: If a cheater has no secret but successfully deceives a validator, he can only succeed at most once (for a specific challenge). It is almost impossible for him to respond effectively to the same commitment to every possible challenge. If he could meet both challenges, he essentially had the secret. This ensures that "a person who does not know the secret cannot prove that he knows the secret."

The most famous sigma protocol is the Schnorr authentication protocol, which is used to prove knowledge of discrete logarithms.

Setting: The system parameter has a generator g (in a cyclic group). The prover's public key is h = g^w mod p and the private key is w.

Goal: The prover proves to the verifier that he knows the private key w without revealing w.

Commitment: The prover randomly selects a number r, calculates a = g^r mod p, and sends a to the verifier.

Challenge: The verifier randomly selects a challenge number e and sends it to the prover.

Response: The prover computes z = r + e \* w and sends z to the verifier.

Verification: The verifier checks whether g^z ≡ a \* h^e mod p holds.

Left side: g^z = g^(r + e\*w)

Right side: a \* h^e = g^r \* (g^w)^e = g^(r + e\*w)

If equal, the verification passes.