# 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)***
Last changed by  
 
0xMonia
223

Read more

Hardware Review: GPUs , FPGAs and Zero Knowledge Proofs

Zero Knowledge Proofs (ZKPs) are of growing importance for decentralized systems. Initially gaining popularity with projects such as ZCash, they are most widely known today as a scaling solution for Ethereum.

9/1/2023
Urbit Resources

developer docs detailed curriculm sigilante youtube channel with many amazing videos Content the network age podcast Projects uqbar uqbar - zk

4/13/2023
Nightly Paper

Every night I will read a short (max 20 page) and interesting paper. I will choose papers that are from other domains out side my daily work. list of papers I have read so far: https://arxiv.org/pdf/2302.02083.pdf

2/13/2023
An opinion on what it takes to build a remote team

My realationship with remote work I spent my whole childhood making friends online, learning online, and even working online at the age of 14. I'm used to hours of isolation, communicating with a friend I never saw face to face. There are many like me. However when I joined my first startup, I joined a tight knit team we worked every day for 8-12 hours in the office an hour drive from my home. This experience granted me long lasting friendships and valuable learning experiences. I started working remotely again two years ago during the start of COVID. During these two years I switched time zones alot, started new jobs and traveled around the globe. But most importantly remote work gives me a sense of freedom, to live my own life as I wish. However along the way I have learned a lot of hard lessons regarding remote work. I will share some of my observations with you. Building a remote team

1/19/2023
Read more from 0xMonia
Published on HackMD