# Sigma protocols and Fiat–Shamir heuristic
## Sigma Protocols
```sequence
Prover->Verifier: generate commitment t
Verifier->Prover: generate challenge c
Prover->Verifier: generate response z
Note right of Verifier: accept or reject
```
tldr;
Sigma Protocols are interactive protcols, that contain 3 stages and 2 actors (Prover, Verifier). Sigma protocls allow a Prover to display knolwage of a secret witness. While allowing a Verifier to challane the Prover and to be almost certain (read Soundness section) that the Prover isnt lying.
A properly constructed Sigma Protocol will provide "Completeness" making sure a honest Prover will always be responded to with ACCEPT from the Verifier. As well as "soundness" giving the Verifier confidance that a dishonest Prover can attempt to deceive no more then once.
## Definitions
***Effective relation***
An effective relation is a [binary relation](https://en.wikipedia.org/wiki/Binary_relation) `R ⊆ X × Y`,
where `X` , `Y` and R are efficiently recognizable finite sets.
- Elements of `Y` are called **statements**.
- If `(x, y) ∈ R`, then `x` is called a **witness** for `y`.
***Sigma protocol***
Let `R ⊆ X × Y` be an *effective relation*. A Sigma protocol
for `R` is a pair `(P, V)`.
- `(P, V)` are both interactive protocol algorithms. `P` takes an input a witness statment pair `(x,y) ∈ R`. `V` takes as input a statment, this stament may be **rejected or accepted** by `V`.
- `P` and `V` are constructed to awlays work in the following way:
- To start the protocol, `P` computes a **message `t`, called the commitment**, and sends `t` to `V` ;
- Upon receiving `P`’s commitment `t`, `V` chooses a **challenge `c` at random from a finite challenge space `C`**, and sends `c` to `P`;
- Upon receiving `V` ’s challenge `c`, `P` computes a response `z`, and sends `z` to `V` ;
- Upon receiving P’s response `z`, `V` outputs either `ACCEPT` or `REJECT`, which must be computed strictly as a function of the statement `y` and the **conversation** ``(t, c, z)``. In particular, `V` does not make any random choices other than the selection of the challenge — all other computations are completely deterministic.
- `∀(x, y) ∈ R`, when `P(x, y)` and `V (y)` interact with each other, `V (y)` always outputs `ACCEPT`.
Sigma protocols uphold 3 important prporties:
***Completness***
If (P,V) fullfils the Sigma protocol. Where `(x, y) ∈ R` is input to `P`. Then V must always return `ACCEPT`.
What this means is that a Prover can rest assure that an honest answer will be accepeted.
***Soundness***
Special soundness. Is the ability to compute a witness efficiently from two accepting transcripts. Where the transcripts share the same commitment but diferent challange.
What this means is that a cheating `P` can only answer correctly once at best.
*Special soundness (formally defined)* - Let `(P, V)` be a Sigma protocol for `R ⊆ X × Y`. We say that `(P, V)` provides special soundness if there is an efficient deterministic algorithm `Ext` , called a witness extractor, with the following property: whenever `Ext` is given as input a statement `y ∈ Y`, and two accepting conversations ``(t, c, z)`` and `(t, c', z')`, with `c != c'`, algorithm `Ext` always outputs `x ∈ X` such that `(x, y) ∈ R` (i.e., x is a witness for y).
***Special honest verifier zero knowledge (HVZK)***

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up