0xAlpha 投稿 DODO research:讓我們一起深入解析了 zk-SNARK 技術,探討它在加密和區塊鏈中實現隱私保護的原理和應用
作者:0xAlpha Co-founder @DeriProtocol
歡迎關注推特:@0x_Alpha
![](https://web3caff.com/wp-content/uploads/2023/11/image-33.png)
0xAlpha 投稿 DODO research。 這篇文章將用數學解碼這項技術,揭示它如何在不透露任何資訊的情況下證明知識的真實性。 準備好,讓我們一起揭開 zk-SNARK 的神秘面紗。
介紹
zk-SNARK,即「零知識簡潔非互動式知識論證」,使得一名驗證者 能夠確認一名證明者 擁有某些特定知識,這些知識被稱為 witness,滿足特定的關係,而無需透露關於見證本身的任何資訊。
為特定問題生成 zk-SNARK 包括以下四個階段:
- 將問題(或函數)轉換成算術門電路。
- 然後將這個電路翻譯成矩陣公式。
- 这个矩阵公式进一步转换成一个多项式,这个多项式应该能被一个特定的最小多项式整除。
- 最后,这种可整除性在有限域的椭圆曲线点中表示出来,证明就在这里进行。
前三个步骤仅仅是转换了原始陈述的表示方式。最后一个步骤使用同态加密将第三步的陈述投影到加密空间中,使得证明者能够证实其中的镜像陈述。鉴于这种投影利用了非对称加密,从第三步的陈述回溯到原始陈述是不可行的,确保了零知识的暴露。
阅读本文所需的数学背景相当于 STEM 专业学生的大一级代数水平。唯一可能具有挑战性的概念可能是椭圆曲线加密。对于不熟悉这一点的人来说,可以将其视为具有特殊基数的指数函数,同时要记住其逆函数仍然未解。
![](https://web3caff.com/wp-content/uploads/2023/11/image-32.png)
在本文中,我们将继续使用方程式 (1) 作为讨论的基础。
第 1 步:算术门电路
方程式 (1) 可以分解为以下基本算术运算:
![](https://web3caff.com/wp-content/uploads/2023/11/image-31.png)
这对应于以下算术门电路:
![](https://web3caff.com/wp-content/uploads/2023/11/image-30.png)
我们还将方程式 (2) 称为一组 4 个 “一级约束”,每个约束描述了电路中一个算术门的关系。通常,一组 n 个一级约束可以概括为一个二次算术程序(QAP),接下来将进行解释。
第 2 步:矩阵
![](https://web3caff.com/wp-content/uploads/2023/11/image-28.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-29.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-27.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-34.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-35.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-26.png)
第 3 步:多项式
![](https://web3caff.com/wp-content/uploads/2023/11/image-25.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-36.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-37.png)
如果提取出每一行单独观察,不难发现这四行对应于在四个点分别求值的相同表达式。因此,上述矩阵方程等价于:
![](https://web3caff.com/wp-content/uploads/2023/11/image-24.png)
一种直接但不保密的方式来证明这一点是提供方程式 (4) 的左边并展示因式分解。然而,zk-SNARK 的主要目的是保持隐秘(不透露任何知识)。因此,我们不会直接证明这个方程,而是在椭圆曲线点的空间中证明它的加密版本。
第 4 步:椭圆曲线点
将方程式 (4) 重写为:
![](https://web3caff.com/wp-content/uploads/2023/11/image-23.png)
接下來,我們將更詳細地闡述實際的操作步驟。
橢圓曲線加密
![](https://web3caff.com/wp-content/uploads/2023/11/image-22.png)
另一方面,兩個橢圓曲線點的加法定義如下圖所示:
![](https://web3caff.com/wp-content/uploads/2023/11/image-21.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-20.png)
![](https://web3caff.com/wp-content/uploads/2023/11/image-19.png)
然而,Alice 想要證明的方程式(5)是二次形式的,所以線性不夠。 為了處理二次項,我們需要在加密空間中定義乘法。 這被稱為配對函數,或雙線性映射,接下來將進行解釋。
雙線性映射
![](https://web3caff.com/wp-content/uploads/2023/11/image-18.png)
這是我們都熟悉的東西——加法和乘法操作的分配律。
有了這樣的雙線性映射,我們就可以將方程式(5)的兩邊映射到加密空間。
公共參考字串
![](https://web3caff.com/wp-content/uploads/2023/11/image-17.png)
整個過程被稱作「驗證鑰」,簡稱 VK。 這裡只涉及 7 個橢圓曲線點(ECPs),需要提供給驗證方。 要注意的是,不管問題裡面涉及多少輸入和一級約束,VK 始終是由 7 個 ECPs 構成的。
另外,值得一提的是,「可信設置」以及生成 PK 和 VK 的過程,對於一個特定的問題來說,只需操作一次即可。
證明與驗證
現在擁有公鑰(PK),愛麗絲將計算以下橢圓曲線點(ECPs):
![](https://web3caff.com/wp-content/uploads/2023/11/image-16.png)
這 9 個橢圓曲線點就是零知識簡潔非互動式證明(zk-SNARK)的關鍵!
注意,愛麗絲其實只是對公鑰里的橢圓曲線點做了些線性組合運算。 這點特別關鍵,驗證時會重點檢查。
現在,愛麗絲交出了 zk-SNARK 證明,咱們終於進入驗證環節,分三步走。
![](https://web3caff.com/wp-content/uploads/2023/11/image-15.png)
參考文獻
- “Zk-SNARKs: Under the Hood” (Vitalik Buterin)
- “A Review of Zero Knowledge Proofs” (Thomas Chen, Abby Lu, Jern Kunpittaya, and Alan Luo)
- “Why and How zk-SNARK Works: Definitive Explanation” (Maksym Petkus)
- Website: Zero-Knowledge Proofs
- Wikipedia: Elliptic curve
- Wikipedia: Finite field
- Wikipedia: Pairing-based cryptography
免責聲明
本研究報告內的資訊均來自公開披露資料,且本文中的觀點僅作為研究目的,並不代表任何投資意見。 報告中出具的觀點和預測僅為出具日的分析和判斷,不具備永久有效性。