# 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)***