Mathematical sigma protocol and Fiat Shamir transformation in blockchain

blocksight 2021-05-07 18:09:15 阅读数:73

mathematical sigma protocol fiat shamir

Write it at the front

In the last introduction The concept and properties of zero knowledge proof , There is no common Sudoku , An example of map coloring , These can be self searched to understand ,

This article continues with sigma agreement , A protocol with certain zero knowledge nature !

Sigma agreement 9

Set up a relationship $R\subseteq X * Y$, that <P, V> Builds on the R On the one Sigma Agreement for :

P It's an interactive protocol called proof , The input is a witness-statement Yes $(x,y)\in R$.V It's an interactive protocol called verification , The input is a statement,$y \in R$.

P and V The interaction process is :

  1. First ,P Calculate a commitment (commitment) t , Send it to V;
  2. On receiving from P After the news ,V In the limited challenge space C Randomly select one of the challenge elements (challenge) c, And send it to P ;
  3. On receiving from V After the challenge , P Calculate a feedback (response) z , Send it to V
  4. After receiving from P After the feedback , V Output accept perhaps reject.


Abstract definitions are often confusing , Illustrate with examples !

Illustrate with examples

Take exponential operation as an example , p As a prime number ,q by p − 1, The largest prime factor of ,g by $Z^*_p$ in order by q The elements of , some x yes P The secret of , Detailed process :1)P Calculation $h =g^x\ mod\ p$, As a promise to V

2)P Choose random numbers $r ∈ z_q $, Calculation $a = g^r\ mod\ p$, P take a Value sent to V

3) V Choose random numbers challenge e,V take e Value sent to P;

4) P Calculation $z = r + ex\ mod\ q$, take z Value sent to V,

5) V Judge $g^z=? =ah^e\ mod\ p$ Is it true , If it is true , be V Accept that P Do know what's right x.

sigma The protocol is also called the honest verifier's ( special ) Proof of zero knowledge . It assumes that the verifier is honest . This example is similar to Schnorr Authentication Protocol , It's just that the latter is usually non interactive .

correctness (completeness)

In the agreement above , Correctness means that if everyone follows the agreement , Then the agreement will be executed normally . stay Sigma In the middle of the agreement , It means P and V Do it ,V Finally, we should accept the State .

Fairness (special soundness)

Fairness means P Can't prove a wrong statement statement. Sigma The agreement achieves Fair . To be exact , Special fairness ! Special fairness means , If P Can let V Find two of the challenges , So the two challenges are (e,z) and (e′,z′). By algebraic calculation 【 Power division 】 You can get $𝑑 =(e-e')^1 $, namely $ x = 𝑑⋅(𝑠 − 𝑠^′)$. So we calculate x Then only one of the equations can be satisfied .

Zero knowledge (special honest verifier zk)

V Neither can we know from the agreement that x Value , And not to a third party , prove V Know the secret ( namely V You can't pretend to be P). That is to say V Nothing was learned from the agreement ( except P know x outside ).

Fiat-Shamir Transformation

Interactive mode has its limitations , For example, two or more parties have to be online at the same time .Fiat-Shamir Transformation , Also called Fiat-Shamir Heurisitc( heuristic ), perhaps Fiat-Shamir Paradigm( normal form ), yes Fiat and Shamir stay 1986 A change proposed in , Its characteristic is that it can transform interactive zero knowledge proof into non interactive zero knowledge proof . In this way, the communication efficiency is improved by reducing the communication steps !

The algorithm allows the random challenge in the interactive step to be replaced by a non interactive random number oracle (Random oracle). Random number prediction machine , That's the random number function , It is a kind of function with independent tangent uniform distribution between the outputs for any input . The ideal random number predictor doesn't exist , Pseudo random numbers are usually used (PRNG) In engineering code , Cryptographic hash functions are often used as random number predictors .

Take a look at non interactive sigma agreement :1)P Calculation $h =g^x\ mod\ p$, As a secret

2)P Choose random numbers $r ∈z_q$ , Calculation $a = g^r\ mod\ p$, P take a Value sent to V

3)P Calculation $e = Hash(h, a)$;

4) P Calculation $z = r + ex\ mod\ q$, take z Value sent to V,

5) V Judge $g^z=? = ah^e\ mod\ p$ Is it true , At the same time e Whether the hash result of is correct , After they all passed , be V Accept that P Do know what's right x.


In this paper, Sigma The interactive and non interactive nature of the protocol , Simple and clear , This paper introduces the common zero knowledge proof Fiat-Shamir Transformation ,Sigma There are also variations and uses of the agreement , Let's talk about it next time !

If you don't think it's simple enough , It shows that the foundation is still lacking , Take a look at the previous article patiently , Cuddle wood , Born in the end , The platform of a hundred feet rises from the earth !!

Reference resources :

Link to the original text : Welcome to the official account :blocksight

Related reading

Mathematics in blockchain - What is zero knowledge proof ? The concept and properties of zero knowledge proof

Mathematics in blockchain - RSA Non member proof of accumulator RSA Accumulator Non member certification

Mathematics in blockchain - Accumulator( accumulator ) Accumulator and RSA Accumulator

Mathematics in blockchain - Kate promise batch opening Kate Promise volume Certification

Mathematics in blockchain - I promise Knowledge and commitment

Mathematics in blockchain - Pedersen Key sharing Pedersen Key sharing

Mathematics in blockchain - Pedersen promise Cryptography promises --Pedersen promise

Mathematics in blockchain - Inadvertently transmit Oblivious transport protocol

Mathematics in blockchain - RSA Algorithm encryption and decryption process and principle RSA Encryption and decryption algorithm

Mathematics in blockchain - BLS Threshold signature BLS m of n Threshold signature

Mathematics in blockchain - BLS Key aggregation BLS Key aggregation

Schorr Signature and elliptic curve Schorr Signature and elliptic curve

Mathematics in blockchain -Uniwap Automated market maker core algorithm analysis Uniwap Core algorithm analysis ( in )