### Mathematics in blockchain (74) -- sigma protocol and Fiat Shamir transformation

blocksight 2021-05-06 23:21:38 阅读数:641

mathematics blockchain sigma protocol fiat

## 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) R.V It's an interactive protocol called verification , The input is a statement,y 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 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)^{-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.

## Summary

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 ！！

## Write it at the front

In the last introduction RSA Accumulator Non member proof and application in blockchain , Some of the details didn't unfold , For example, why use prime factors ？ Because their product will uniquely represent the set . otherwise , There will be confusion 【 The same product , There will be different combinations of factors , Such as 18 = 2 9 = 3 6】 wait .

Up to now , There's a signature , Cryptography promises , Homomorphic computation , Elliptic curve and so on , Next, we can see the specific content of zero knowledge proof . This article belongs to popular science , Compared with the previous , Happy reading does not burn the brain ！

## What is zero knowledge proof

Generally speaking, zero knowledge proof makes the verifier believe by some means （ confirm ） The witness's statement is correct （ For example, knowing some key information ）, Without exposing the information itself . There are many examples on the Internet to help understand , Here's a scene ： If V Found a lost bank card ,P Come and say that the bank card is his , And said he knew the bank card number and password , Because the bank card is V In the hands of ,V It's easy to judge P Is the card number correct , however V I still don't believe it P It's the owner of the card , therefore P He also said that he knew the withdrawal code of the bank card , But I can't tell you directly V Otherwise, it will be leaked . So they agreed , Come to the nearby ATM By the machine ,V leave ATM Keep a certain distance from the plane , To make visible P Perform the withdrawal operation , But not so close as to see P The withdrawal code you entered .P It's just ATM Wait by the side V Operation instructions of .

When they're in place ,V Let's take it out 100 element ,P Insert the card , Enter the password and take it out 100 element （ Suppose that Cary is rich ）,V Let's take it out again 300 element ,P Do it and take it out again 300 element , After a few repetitions ,V Make sure the bank card is P Of .

P I got my bank card in this way , Didn't let V Know the withdrawal code , This simulation scenario is the application scenario of zero knowledge proof .

### purpose

Zero knowledge proof is often used in the following scenarios ：(1） Proof of privacy data ： A person's bank account is more than X; last year , A bank is not associated with an entity Y Make a deal ; A person's credit score is higher than Z; Without exposing the whole DNA Matching on the premise of data DNA

(2） Anonymous Authentication ： Without revealing identity （ Like the login password ）, Prove that the requester R Have access to restricted areas of the site ; Prove that a person comes from a group of allowed countries / A country in the region list / region , But it doesn't reveal which one ; Prove that a person is a member of an organization but not who .（3） Anonymous payment / Tokens, ： In the blockchain （ Untraceable ） Privacy coin ; Payment is completely separated from any kind of display identity ; Paying taxes without disclosing income ;

（4） Outsourcing computing outsources expensive computing tasks , And verify whether the calculation results are correct without re execution ; It opens up a category of zero Trust Computing ; Improve the blockchain model , Do the same calculation from all nodes , To only need one side to calculate and then other nodes to verify and so on ,zk rollup layer2 Plan, etc .

## ZK-SNARK

since 1985 year , The concept of zero knowledge proof is in “ Knowledge complexity of interactive proof system ” In this paper, we introduce , Later included non interactive research , In recent years, the research and application of blockchain has developed rapidly . The zero knowledge proof system should satisfy the following properties .

1. integrity : Just state (statement) That's right. ,prover You can make verifier Conviction ;
2. reliability : If you state (statement) It's wrong. , So cheating prover There's no way to verifier Believe in
3. Zero knowledge : The interaction of protocols only exposes statements (statement) Whether it is correct without disclosing any other information

At present, the mature application is zk-SNARK Technical solution . This term means ：

ZK-SNARK Full name :zero-knowledge succinct non-interactive arguments of knowledge

Succint ( Conciseness ) : Compared with the actual calculated length , The generated zero knowledge evidence message is very small .

Non-interactive ( Non interactivity ) : about zk-SNARK Algorithm , There is usually a build phase , After the build phase is complete , Certifier (prover) Just report to the verifier (verifier) Just send a message . and ,SNARK There's usually another one called " Public verifier " Characteristics of , It means that anyone can verify zero knowledge evidence without any interaction , This is crucial to blockchain .

Arguments ( Controversial ) : The verifier can only resist the attack of the verifier with limited computing power . The prover with enough computing power can create forged zero knowledge evidence to deceive the verifier . This is also often called " Computational completeness (computational soundness)", instead of " Perfect integrity (perfect soundness) ".

of Knowledge : For a certifier , Without knowing the specific proof (witness) Under the premise of , It is impossible to construct an effective zero knowledge evidence .

## Summary

In any zero knowledge proof system , There is one. prover Let... Without divulging any additional information verifier Be sure of certain statements （Statement） That's right. .

ZK-SNARK At present, it is widely used , There are many mature Libraries , Such as libsnark,bellman etc. . Some don't need to setup Of zk-stark The plan , Let's talk about it later .

Okay , Next, we'll go on to zero knowledge proof ！.

Link to the original text ：https://mp.weixin.qq.com/s/LHuRAA1RPzbccKHZ1wdU6g Welcome to the official account ：blocksight

### 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 proof and blockchain applications

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 ）