Mathematical sigma protocol or proof & signature in blockchain

blocksight 2021-05-11 20:20:20 阅读数:834

mathematical sigma protocol proof signature

Write it at the front

In the last introduction sigma Protocol and non interactive paradigm , You can see that non interactive sigma The protocol is very similar to the previous signature mechanism , If you pay attention to the chronological order in which they appear , You will know that the latter appeared later than sigma Years after the agreement was put forward , We believe it is on this basis .

Actually , Any technology ( even to the extent that “ thought ”) It's the same , They are all moving forward on the basis of their predecessors , Standing on the shoulders of giants , To stand high and look far !

Shut oneself up in a room making a cart , I've always had to do it ! So understanding the history and current situation of the target is the premise of development . Otherwise, when you don't know why something appeared and where it was at that time in history , There will be a lot of doubts .

“ The west wind withered the trees last night , Alone on tall buildings , Looking at the end of the earth ”, It's about the first stage of learning , That is to know the past , The present .

This article continues with sigma Protocol related extensions and applications !

OR prove (OR-proof)

Take exponential operation as an example ( Parameters are the same as above ), hypothesis P know $y_1=g_1^{x_1}$ , $y_2=g_2^{x_2}$(mod p Omitted ) Any exponential secret in the equation ,$x_1$ or $x_2$ person , P How to talk to V Prove that he knows one of them but doesn't disclose which one ?

Premise :$g_1,g_2,g_3$ It has been made public

hypothesis P What we know is $x_1$,P technological process :1) Random selection $v_1,v_2.w$, Calculation $t_1=g_1^{x_1}$,$t_2=y_2^wg_2^{v_2}$,

2) Make c = Hash($g_1,g_2,y_1,y_2,t_1,t_2$)

3) Make $c_1=w,c_2=c-c_1 (mod\ q)$

4)$r_1=v_1-c_1x_1,r_2=v_2 (mod\ q)$

V technological process :5) V Calculation $t_1'=y_1^{c_1}g_1^{r_1}$ , $t_2'=y_2^{c_1}g_2^{r_2}$ test $t_1'=?=t_1$,$t_2'=t_2$

6) Calculation $c_1+c_2=?= Hash(g_1,g_2,y_1,y_2,t_1',t_2') (mod\ q)$

The inspection process can be deduced by itself !

be based on Sigma Protocol authentication and signature

By imitation Schnorr Construction , You can take whatever you want Sigma The protocol is transformed into identity authentication scheme and signature scheme . hypothesis (P,V) It's built on relationships $R\subset (X*Y) $ Upper Sigma agreement . Need to add :

  1. A probability ( Randomness ) And it has one-way characteristic , Generate pk,sk, And $(sk,pk)\in R$
  2. Safe hash function , As random Oracle, yes Fiat-Shamir The core of transformation

Okay , Fully built Fiat-Shamir The flow of signature scheme is as follows :

  1. Key generation algorithm G Generate public key (x,y)$\in R$
  2. P(Prover part ) Generate commitment t, t$\in T$
  3. P Computing challenges c = H(m, t),m It's a message to be signed
  4. P What makes the challenge response z$\in Z$
  5. P According to the challenge z Generate signature :s = (t,z)$\in T*Z$
  6. V(Verifier part ) Use public key y, verification (t,z)$\in T*Z$ , And c = H(m, t), Otherwise, refuse !


It's fun to be here , Let's look back at the signature mechanism described earlier (RSA,ECDSA,Schnorr,EdDSA etc. ), It can be found that this article is almost an abstract version of these signature mechanisms , They are all concrete examples !

So here the signature mechanism has formed a small closed loop , Know what it is, know what it is ! We always thought Fragmented knowledge has no power , Only a systematic system can be stable and far-reaching !

In addition, based on sigma There are other examples of agreements Such as Okamoto’s protocol,And proof I won't introduce !

Reference resources :

Link to the original text :

Welcome to the official account :blocksight

Related reading

Mathematics in blockchain -sigma Deal with the Fiat-Shamir Transformation sigma Deal with the Fiat-Shamir Transformation

Mathematics in blockchain - What is zero knowledge proof ? What is 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 Basics Schorr Signature and elliptic curve

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