文章目錄

• ZK簡介
• • 例子
  • 承諾協議
  • 如何證明零知識性質
  • 如何證明任意的statement
  • 證明和證明某個知識
  • 由Schnorr身份認證協議來看看ZK的性質，以及如何轉為非交互式證明
  • • completeness
    • Soundness
    • Zero-knowledgeness
    • 從交互式證明到非交互式
• 三種基礎ZK：SNARKS，STARKs，Bulletproofs
• • BulletProofs
  • SNARKs
• 區塊鏈擴容
• • 區塊鏈擴容包括了兩層
  • ZKP如何做擴容？

ZK簡介

最初在1980年提出，由Shafi Goldwasser, Silvio Micali和Charles Rackoff。剛開始叫做交互式證明系統(Interactive proof system)。

Prover和Verifier之間交換信息，讓Verifier相信某種statement是真的。

Completeness：誠實的Prover最后會讓Verifier相信這個statement。

Soundness：只有statement是真的時候，才能讓Verifier相信。

zero knowledge：Prover除了證明這個statement是真的之外，不暴露其他信息。

• Completeness: If the Prover is honest, then she will eventually convince the Verifier.
• Soundness: The Prover can only convince the Verifier if the statement is true.
• Zero-knowledge(ness): The Verifier learns no information beyond the fact that the statement is true.

例子

服務器上面存儲了密碼的哈希值，用戶相當于Prover，服務器是Verifier，用戶傳輸哈希值來證明自己擁有對應的密碼，但是服務器不知道哈希值的原像是什么。

三色圖問題，可以Prover給圖一個解，Verifier隨機打開一條邊，Prover再打亂這個解。多次交互。可以動手試試

承諾協議

在三色圖問題里面，用灰色的點蓋住了答案，所以Verifier無法看到答案，但Prover也不可以對答案進行更改了。

在實際中，這樣的“灰點”是一個承諾協議：里面加密了一個信息，但同時綁定了這個信息。

承諾方案允許一方 "承諾 "一個給定的信息，同時對其進行保密，然后再 "打開 "所產生的承諾，以揭示里面的內容。承諾協議可以直接由加密的哈希函數構造。可以理解成一個信封?，我將一個信息放進了信封里面，發送給別人，但之后我可以將信封撕掉，顯示出里面的信息。在這個過程中其他人無法看到里面的信息，這是信息的保密性，同時我在證明過程中也無法對信封內的東西進行替換，這是綁定性。

如何證明零知識性質

最終我們得到的是以下定理。如果存在任何Verifier計算機程序，通過與一些Prover交互式地運行該協議，成功地提取某些信息，那么我們可以簡單地在該程序上使用倒帶技巧，重新提交一個隨機的解決方案，一旦不能正確回答其挑戰，就通過倒帶執行來 "欺騙 "Verifier。與我們上面給出的邏輯相同：如果這樣的Verifier在運行真實協議后成功地提取了信息，那么它應該能夠從模擬的、基于倒帶的協議中提取相同數量的信息。但是，由于沒有信息進入模擬協議，所以沒有信息可以提取。因此，驗證人能夠提取的信息必須總是零。

如果對于每一個可能的Verifier，你都能證明存在一種叫做 "Simulator "的算法，并證明這種算法對于verifier來說與現實統計上不可區分，那么一個協議就可以被證明為零知識。

從純粹的機械角度來看，模擬器就像一種特殊的驗證者。然而，與真正的驗證者不同的是–它從一些特殊的知識開始，使它能夠證明一個語句的真實性–模擬器根本沒有得到任何特殊的知識。* 盡管如此，模擬器（或模擬器）必須能夠 "欺騙 "每個驗證者，使其相信該語句是真實的，同時產生一個在統計上與真正的驗證者的輸出相同（或不可區分）的記錄。

如何證明任意的statement

Goldreich, Micali and Wigderson (GMW)協議允許我們證明一個圖的三著色問題。首先三著色問題是一個NP完全問題。所以可以將任意的NP問題規約為三著色問題。

如果存在任何決策問題（即具有是/否答案的問題），其見證（解決方案）可以在多項式時間內得到驗證，那么。

我們可以通過以下方式證明上述解決方案的存在：（1）將問題轉化為圖三色問題的實例，以及（2）運行GMW協議。

證明和證明某個知識

Statements about “facts”. For example, I might wish to prove that “a specific graph has a three coloring” or “some number N is in the set of composite numbers*“.* Each of these is a statement about some intrinsic property of the universe.

Statements about my personal knowledge. Alternatively, I might wish to prove that I know some piece information. Examples of this kind of statement include: “I know a three coloring for this graph”, or “I know the factorization of N”. These go beyond merely proving that a fact is true, and actually rely on what the Prover knows.

第一種和第二種是不一樣的：第一種不需要特定的知識也能證明，比如需要證明一個數$n$是合數，并不一定說要知道他的因子是什么；但是第二種證明需要特定的知識，比如$n$的具體的因子有哪些，

由Schnorr身份認證協議來看看ZK的性質，以及如何轉為非交互式證明

假設Alice公布了她的公鑰$p{k}_A=g^a\mathrm{m}\mathrm{o}\mathrm{d}p$，其中$a\in [1,q]$是私鑰，$g$是$q$的生成元，$p,q$是兩個素數。

如果Alice要向Bob證明她擁有這個公鑰所對應的私鑰。那他們運行如下的交互協議。
$$\begin{array}{rlrl}& \mathbf{A}\mathbf{l}\mathbf{i}\mathbf{c}\mathbf{e}& & \mathbf{B}\mathbf{o}\mathbf{b}\\ & \text{Pick?random?}k\in [1,q]& \stackrel{h=g^k(\mathrm{m}\mathrm{o}\mathrm{d}p)}{}& \text{Pick?random?}c\in [1,q]\\ & & \stackrel{c}{}& \\ & & \stackrel{s=ac+k(\mathrm{m}\mathrm{o}\mathrm{d}q)}{}& \text{Check?}{g}^s\equiv p{k}_A^c?h\mathrm{m}\mathrm{o}\mathrm{d}p\end{array}$$

completeness

If the Prover is honest, then she will eventually convince the Verifier.

首先，我們應該問自己，該協議是否完備。這通常是最容易驗證的屬性：如果Alice誠實地執行協議，Bob在協議結束時應該感到滿意？在這種情況下，只要做一點替換，完整性就很容易看到。
$$\begin{array}{rlr}{g}^s& \equiv p{k}_A^c?h& \mathrm{m}\mathrm{o}\mathrm{d}p\\ g^{ac+k}& \equiv (g^a{)}^c?g^k& \mathrm{m}\mathrm{o}\mathrm{d}p\\ g^{ac+k}& \equiv g^{ac+k}& \mathrm{m}\mathrm{o}\mathrm{d}p\end{array}$$

Soundness

The Prover can only convince the Verifier if the statement is true.

說到證明知識證明的合理性，我們有一個非常好的形式化方法。就像我們上面討論的模擬器一樣，我們需要證明一種特殊算法的存在。這種算法被稱為知識提取器，它所做的正是它所聲稱的。知識提取器（Extractor）是一種特殊的驗證器，它與Prover進行交互，如果Prover成功地完成了證明，提取器應該能夠提取Prover的原始秘密。
$$\begin{array}{rlrl}& \mathbf{A}\mathbf{l}\mathbf{i}\mathbf{c}\mathbf{e}& & \mathbf{E}\mathbf{x}\mathbf{t}\mathbf{r}\mathbf{a}\mathbf{c}\mathbf{t}\mathbf{o}\mathbf{r}\\ & \text{Pick?random?}k\in [1,q]& \stackrel{h=g^k(\mathrm{m}\mathrm{o}\mathrm{d}p)}{}& \text{Pick?random?}{c}_1\in [1,q]\\ & & \stackrel{c_1}{}& \\ & & \stackrel{s_1=a{c}_1+k(\mathrm{m}\mathrm{o}\mathrm{d}q)}{}& \\ & & & \text{Extractor?rewinds?Alice?to?Step?2}\\ & & \stackrel{c_2}{}& \\ & & \stackrel{s_2=a{c}_2+k(\mathrm{m}\mathrm{o}\mathrm{d}q)}{}& \end{array}$$
Extractor可以重置Prover的狀態，就比如這里，讓Prover給出了兩個相同的k。

通過得到了$c_1,c_2,s_1,s_2$，Extractor可以用如下方式恢復Prover的原始秘密。
$$\begin{array}{rl}(s_1?s_2)/(c_1?c_2)\mathrm{m}\mathrm{o}\mathrm{d}q& \\ =((a{c}_1+k)?(a{c}_2+k))/(c_1?c_2)\mathrm{m}\mathrm{o}\mathrm{d}q& \\ =a(c_1?c_2)/(c_1?c_2)\mathrm{m}\mathrm{o}\mathrm{d}q& \\ =a& \end{array}$$

Zero-knowledgeness

The Verifier learns no information beyond the fact that the statement is true.

證明零知識性需要用到模擬器（SImulator），模擬器與Verifier交互，擁有rewind verifier的能力。標準的Schnorr協議是沒有這種模擬器的。要證明零知識性，我們要基于一個假設，那就是Verifier是誠實的，也就是他的輸入不會隨著我們的輸入而改變，也就是他會用隨機發生器來生成$c$，而不是更具我們發送的值來選。只要有這個假設，就可以構造一個Simulator。

Simulator做如下事情：

首先，輸出隨便$g^{k_1}$作為第一個消息。然后得到Verifier發送的$c$。

重置Verifier的狀態，選一個隨機數$z\in [1,q]$。

計算$g^{k_2}=g^z?p{k}_A^{?c}$，并輸出$g^{k_2}$作為Prover的初始消息。

當Verifier輸出$c$作為挑戰時，輸出$z$。

總結來說，這里Simulator輸出的$g^k,c,z$與原始的Prover和Verifier交互是統計上不可區分的。Simulator在不知道$a$的情況下，使得Verifier相信了他的證明，因此Verifier無法從這個證明中提取出$a$的信息。

從交互式證明到非交互式

Fiat和Shamir在1980年發現，只要用一個有效的哈希函數，就可以把一個交互式的證明變為一個非交互式的。

特別地，非交互式證明看起來如下：

Prover隨機選取$g^k\mathrm{m}\mathrm{o}\mathrm{d}p$。

Prover計算一個挑戰$c=H(g^k||M)$，其中$H()$是一個哈希函數，$M$是任意消息串。

計算$ac+k\mathrm{m}\mathrm{o}\mathrm{d}q$。

這里一個有意思的點在于，如果$M$是作為一個消息傳入的，那么這個方案就可以作為一個Signature方案使用。

三種基礎ZK：SNARKS，STARKs，Bulletproofs

三種協議的開銷如上，

從技術上來說：SNARKs¹和STARKs²都是對某種計算的證明，$f(x)=y$，不暴露$x$的情況下證明$y$是由$x$計算出來的。而BulletProof是一種范圍證明，用于證明某個數字在$[0,2^n)$中。

在應用中來說：SNARKs是用在Zcash之中的技術，STARKs用在0x上。bulletproof用在門羅幣當中，但不是用于保護隱私，門羅幣中使用RingCT來保護隱私。

BulletProofs

BulletProofs的思想是一個數字可以表示成二進制形式，如果一個數字的二進制形式有$n$位，那么就可以證明這個數字在$[0,2^n)$中。

在實際使用過程中，令這個數字為$v$，二進制表示為$\mathbf{a}$，則$v=?\mathbf{a},2^i?$。

要證明的是：

$\mathbf{a}$的大小是正確的。

證明我們知道這個值，可以用pedersen承諾加Fiat-Shamir類似的技術來證明。

SNARKs

SNARKs¹有非常多的變種(50+)，SNARKs的基本思路是Computation$\to$Arithmetic Circuit$\to$R1CS³$\to$QAP⁴$\to$SNARKs

由一個算式，比如$x?y+4=10$，要不暴露$x,y$的情況下證明這個算式是成立的。

---

先把他轉換為算數電路：

---

再由算數電路變為R1CS：

R1CS³是一種描述電路的語言。具體來說，一條R1CS由四個向量組成，分別為三個描述向量$\left(L,R,O\right)$，以及一個解向量$v$，要滿足
$$?L,v???R,v?=?O,v?$$

首先這個算數電路中的Constraint有3個，分別是：

${\text{output}}_1=x?y$

${\text{output}}_1+4=10$

將其轉換為R1CS，則令$v=[1,x,y,outpu{t}_1]$，對于兩個Constraint，分別取:

$L=[0,1,0,0],R=[0,0,1,0],O=[0,0,0,1]$

$?L,v?=x,?R,v?=y,?O,v?=outpu{t}_1$

$?L,v???R,v?=?O,v??x?y=outpu{t}_1$

$L=[4,0,0,1],R=[1,0,0,0],O=[10,0,0,0]$

$?L,v?=outpu{t}_1+4,?R,v?=1,?O,v?=10$

$?L,v???R,v?=?O,v??(outpu{t}_1+4)?1=10$

---

從算數電路得到QAP⁴:

QAP的構造方式如下，L,R,O都是長度為4的向量，我們構造3*4個多項式$L_i(X),R_i(X),O_i(X),i\in [1,4]$。

拿$L_i(X)$舉例，他代表著$L$向量的第$i$個元素，在不同的Constraint下的多項式，也就是說$L_1(1)=0,L_1(2)=4$，通過多項式插值可以得到$L_1(X)=4X?4$

羅列一下所有$L_i(X)$的可得：
$$\begin{gathered} Constraint1:L^{(1)}=[0,1,0,0] \\ Constraint2:L^{(2)}=[4,0,0,1] \\ \begin{array}{rlrlrl}{L}_1(1)& =0,& & L_1(2)=4,& & L_1(X)=4X?4\\ L_2(1)& =1,& & L_2(2)=0,& & L_2(X)=?X+2\\ L_3(1)& =0,& & L_3(2)=0,& & L_3(X)=0\\ L_3(1)& =0,& & L_3(2)=1,& & L_4(X)=X?1\end{array} \end{gathered}$$
可以看出$L_i(n)=L^{(n)}[i]$。

令

$L(X)=(L_1(X),L_2(X),L_3(X),L_4(X))$

$R(X)=(R_1(X),R_2(X),R_3(X),R_4(X))$

$O(X)=(O_1(X),O_2(X),O_3(X),O_4(X))$

很容易驗證$L(1)=L^{(1)},L(2)=L^{(2)}$

令

$L(X)=?L(X),v?$

$R(X)=?R(X),v?$

$O(X)=?O(X),v?$

由此可以得到$L(X)?R(X)?O(X)=0forX\in \{1,2\}$

令$P(X)=L(X)?R(X)?O(X)$，將$P(X)$拆為兩個因子多項式$P(X)=T(X)?H(X)$。

其中$T(X)$公開。

這樣的$T(X)$其實很容易找，因為$X=1,X=2$是$P(X)=0$的兩個根，所以可以令$T(X)=(X?1)(X?2)$，用多項式的除法得到$H(X)$即可。

---

現在要向外部證明的其實是：

$P(X)=L(X)?R(X)?O(X)=T(X)?H(X)$這樣一個式子在所有$X$上成立。

但是公開的多項式只有$T(X)$，也就是說，如果取一個數$X=s$，那么其他人最多能知道$T(s)$的值。那如何在不暴露$L(s),R(s),O(s),H(s)$的情況下證明$L(s)?R(s)?O(s)=T(s)?H(s)$成了現在要考慮的問題。

那這里就用到了基于橢圓曲線的一種加密：

令$E(s)=sG$，其中$G$是橢圓曲線的一個生成元。

這樣的加密如下性質：

單項性：給定$x$，很容易計算$y=E(x)$，但給定$y$，很難找到一個$x$滿足$y=E(x)$。

線性：$E(\alpha x+\beta y)=\alpha E(x)+\beta E(y)$

單射：$x=y?E(x)=E(y)$

所以Prover可以直接計算出$P(E(s))=E(P(s))$的值。

SNARKs的協議如下：

1. Setup: 將$E(s)$公開，$T(s)$公開，$s$本身丟棄 2. Prover自己有$L,R,O,H$四個多項式 3. Prover發送$E(L(s)),E(R(s)),E(O(s)),E(H(s))$ 4. 任何人都可以驗證： $E(L(s))?E(R(s))?E(O(s))=E(H(s))?E(T(s))$

小結：

這里省略了很多的細節，只講了大概的框框，包括SNARKs是否滿足ZK的三個性質是沒證明的，所以看到這里應該還沒被說服，為啥只要給出了這個證明就得相信這個計算是正確的？其實就是Completeness和Soundness沒有證明嘛。
省略的細節包括橢圓曲線，$s$其實還要做盲化，要不然不是Zero-knowledge，以及一些配對相關的東西。

區塊鏈擴容

區塊鏈擴容包括了兩層

對區塊鏈本身進行擴容，讓他能存更多的交易。這類擴容的例子有Ethereum,Eth2x,DFinity, Polkadot,Cosmos，用到的技術有Sharding, Pruning, State rent, WASM, PoS, Casper, Light clients, ZKPs.

在分布式應用中盡量少的依賴區塊鏈。比如Dapps，代表性的有Plasma Cash, Ignis，Rollup。

ZKP如何做擴容？

ZKP是解決了這樣一個問題：$F(X,Y)=Z$，其中$F$是任意函數，$X$是公開的輸入，$Y$是私有的輸入，$Z$是公開的輸出。

這里$Y$除了可以當做一個隱私信息，還可以作為一個批量的信息源，比如$X$和$Z$都是幾十byte，而$Y$是幾MB的消息。比如在區塊鏈中，$F$可以是驗證交易以及更新賬本，$X$是先前值的Merkle root，$Z$是當前值的Merkle root，$Y$是一整個Merkle tree。

目前ZKP的技術可以一次操作處理500個交易。Prover的時間是25分鐘，目標是降到10分鐘（2019年的演講）。

---

Succinct Non-interactive ARguments of Knowledge ?? ??

Succinct (Scalable) Transparent ARguments of Knowledge ??

Rank-1 Constraint Satisfaction ?? ??

Quadratic arithmetic program ?? ??

總結

以上是生活随笔為你收集整理的零知识证明从0到1，ZK简介的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。