零知識證明（Zero-Knowledge Proof）是一種創新型的密碼學協定，可以讓證明方在不泄露隱私資訊的前提下，證明自己擁有這項資訊。零知識證明系統中有證明者（Prover）和驗證者（Verifier）兩個角色，證明者擁有一個秘密資訊，想要讓驗證者相信自己擁有這個資訊，而不洩露實際資訊。證明者根據秘密資訊生成一個證明，該證明不包含實際的秘密資訊。這個證明通常經過數學運算構造，可以證明證明者確實擁有這個秘密資訊。驗證者收到證明后，通過預設的驗證演算法來檢查證明的正確性，但驗證者並不能從證明中獲取實際秘密資訊。證明者能通過驗證，就可以說驗證者相信了證明者擁有秘密資訊，而沒有獲得任何有關秘密的實際資訊，這就是證明的“零知識性”。

隨著區塊鏈交易所加密貨幣交易量的增長，使用者需要確認交易所擁有足夠的儲備金來支援交易。但是使用者資產詳細數據、儲備金的具體數額是交易所不希望公開的敏感資訊，零知識證明可以做到在不暴露具體數額的情況下證明交易所擁有足夠的儲備金和具有相應的償付能力，經過嚴格約束設計的證明電路可以確保最終的證明是由嚴謹的計算過程得出，杜絕證明造假的情況發生。採用這種先進的密碼學技術可以大大增強使用者對交易所的信任，同時增強交易所資金透明度，起到防範金融風險的作用。與傳統的外部審計相比，零知識證明不需要將全部儲備資產移交第三方審計，大大降低了操作成本和資金風險。這使得儲備金證明成為一種常規化的進程，可以頻繁進行，定期披露。

zksnark及Groth16原理簡介

引言：

什麼是zksnark？

首字母縮略詞 zk-SNARK 代表“零知識簡潔非互動式知識論證”，指的是一種證明結構，在這種結構中，人們可以證明擁有某些資訊，例如秘密密鑰，而無需透露該資訊，並且兩者之間沒有任何交互。

“零知識”證明允許一方（證明者）向另一方（驗證者）證明一個陳述是真實的，而不會透露任何超出陳述本身有效性的資訊。例如，給定一個隨機數的散列，證明者可以讓驗證者相信確實存在一個具有該散列值的數位，而無需透露它是什麼。

在零知識「知識證明」中，證明者不僅可以說服驗證者該數位存在，而且他們實際上知道這樣一個數位——同樣，無需透露有關該數位的任何資訊。 “證明”和“論證”之間的區別是相當技術性的，我們在這裡不深入探討。

“簡潔”的零知識證明可以在幾毫秒內得到驗證，即使對於非常大的程序的陳述，證明長度也只有幾百位元組。在第一個零知識協定中，證明者和驗證者必須來回通信多輪，但在“非互動式”結構中，證明由證明者發送給驗證者的單個消息組成。

以下是現存的zk-snark簡介：

Groth16：Groth16是目前最快、數據量最小的zk-SNARK，被用於Zcash等。 Groth16不是通用的，其設置需要綁定到一個特定的電路。由於其速度和證明的小數據量，因此常常被新的zk-SNARK拿來比較性能。 Groth16論文連結：https://eprint.iacr.org/2016/260

Sonic：Sonic是一個早期的通用zk-SNARK協定。論文發表於2019年1月。 Sonic支援通用、可升級的參考字串。 Sonic的證明大小固定，但是驗證成本高。理論上可以將多個證明分批驗證以獲得更好的性能。下面列舉的許多新的zk-SNARK都是基於Sonic。 Sonic論文連結：https://eprint.iacr.org/2019/099

Fractal：Fractal 是一種允許遞歸的zk-SNARK。通過對電路的預處理實現了透明設置。證明最大250KB，這筆其他構建生成的證明都要大的多。 Fractal論文連結： https://eprint.iacr.org/2019/1076

Halo：Halo支援遞歸證據組織，無需可信設置。與其他新的zk-SNARK構建不同，Halo的驗證時間是線性的。 Halo論文連結： https://eprint.iacr.org/2019/1021

SuperSonic：SuperSonic 是Sonic的改進版，是第一個在驗證時間和證明數據量方面實用化的透明zk-SNARK。 SuperSonic論文連結： https://eprint.iacr.org/2019/1229

Marlin：Marlin 是Sonic的改進版，證明時間縮短10倍，驗證時間縮短4倍。 Marlin論文連結： https://eprint.iacr.org/2019/1047

Plonk：Plonk也是Sonic的改進，證明時間縮短5倍。 Plonk論文連結： https://eprint.iacr.org/2019/953

我們的零知識證明採用的是groth16，下面是對該方案的詳細介紹：

實現路線：

我們通過：如下六個流程來完成我們的證明。

這篇文檔用一個現實的簡單的例子來做說明説明大家更好理解：

例子：如何證明我們知道方程x^3+x+5=35的解。

實現過程及簡單原理：

因為我們的問題本身就是證明我們知道一個方程的解，那麼我們直接從第二步：滿足的計算方程組->r1cs電路開始進行說明。

2.1 滿足的計算方程組->r1cs電路：

首先，將上面的計算方程組拆分成一次只做一次加減乘除中的一種運算的方程組。

E.g.：計算x^3+x+5=35 可以拆分為：

(1) X0 = x*x

(2) Y0 = X0*x

(3) Y1 = Y0+x

(4) Out = Y1+5

於是把x^3+x+5=35拆分成了四個約束（constraints），換句話說，當我們能夠證明我們同時滿足上面的四個約束的時候，我們也就能夠證明我們知道x^3+x+5=35的解。

之後我們需要使用一個向量組（a,b,c）與解向量s滿足如下條件<s,a>*<s,b> = <s,c>。其中<*，*>表示向量內積。

為了滿足上面所說的解向量s與向量組（a，b，c）所滿足的關係，我們首先構造解向量s=（1，Out，x，X0，Y0，Y1）=（1,35,3,9,27,30）

由此我們可以根據解向量s 構造我們所需要的向量a1=（0,0,1,0,0,0），b1=（0,0,1,0,0,0）， c1=（0,0,0,1,0,0）。當我們分別把a1 b1 c1 帶入<s，a>*<s，b> = <s，c>，並把s用（1，Out，x，X0，Y0，Y1）進行表示，我們可以很容易的得到式子（1） X0 = x*x，那麼我們就得到了式子（1）的向量表達方式。同理，我們也可以通過構造如下的向量分別得到式子（2）（3）（4）所對應的向量表達方式。

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

所以當我們的解向量s輸入正確的時候，就代表我們能夠有這個方程組正確的解。

由此我們得到了方程組轉r1cs電路的過程。（拆分+構造向量）也就是說，我們把給出方程解的問題變成了求r1cs電路相等的問題。上面介紹的內容：電路定義對應在我們公開項目裡面的：circuit/group_user_circuit.go裡面的Define（）函數;電路編譯成r1cs對應在我們公開的項目裡面的src/keygen/main.go 裡面的frontend. Compile（）函數。

如果想具體瞭解r1cs電路的問題，我們推薦閱讀文獻【1】。

1. r1cs電路—>QAP問題：

但是通過這四個向量組解決這個問題顯得過於複雜，我們希望使用更加簡單的辦法

進行解決，由此我們需要把r1cs電路轉化為QAP問題。

我們先將剛才得到的四個向量組在下方列出來：

a1=(0,0,1,0,0,0)，b1=(0,0,1,0,0,0), c1=(0,0,0,1,0,0)

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

從向量a1，a2，a3，a4分別選擇第一個點：0,0,0,5構成y0，y1，y2，y3，選擇1,2,3,4構成x0，x1，x2，x3。

通過拉格朗日插值可以構造多項式fa_0（x）使得fa_0（1）=0，fa_0（2）=0，fa_0（3）=0，fa_0（4）=5

同理可以構造fa_1（x）...，fc_6（x）共18個多項式。

將這18個多項式按照如下方式排列：

向量a=（fa_0（x），fa_1（x），fa_2（x），fa_3（x）,...,fa_6(x))

向量b以及向量c按照a的方式構造出來，由此我們得到三個6維向量（元素為多項式）分別取x=1,2,3,4即可帶入到我們的向量a，b，c就可以還原我們的每一個向量組（a1，b1，c1）,...,（a4，b4，c4）。

這個時候當我們需要驗證r1cs中的等式<s，a>*<s，b> = <s，c>的時候，只需要分別帶入x=1，x=2,... ，x=4進行驗證都成立即可。 （此時向量（fa_0（x），fa_1（x），fa_2（x），fa_3（x）,...,fa_6（x））又變回了數位向量）。

但是分別帶入太麻煩了，如何一次驗證呢？

我們這裡令Z（x）=（x-1）（x-2）（x-3）（x-4）. 這裡是對上面選擇的x0，x1，x2，x3進行插值

當x為1,2,3,4的時候，我們的<s，a>*<s，b> = <s，c>成立也就是A（x）*B（x）-C（x）=0=H（x）Z（x）

其中A（x）=<s，a>，其中a是上面的向量a=（fa_0（x），fa_1（x），fa_2（x），fa_3（x）,...,fa_6（x）），B（x），C（x）同理。

也就是說當我們驗證了A（x）*B（x）-C（x）能夠被Z（x）整除的時候，我們的電路r1cs就被驗證了。由此我們完成了r1cs到QAP問題的轉化。當我們完成了QAP問題的驗證之後，也就代表我們完成了r1cs電路的驗證，也就代表我們證明瞭我們知道原方程x^3+x+5=35的解。

上面是一個QAP問題的實例。

我們對上面的符號以及現實問題做一個一一對應。裡面的A，B，C分別代表我們上面所講的A（x），B（x）和C（x）。 D代表的是我們上面展示的插值空間即D={1,2,3,4}。 Z_D（x）即Z（x）=（x-1）（x-2）（x-3）（x-4）。其中小的zi代表的是我們的秘密向量s=（1， Out，x，X0，Y0，Y1）每一個點的值，即zi=si。 hi代表上方所講的H（x）的係數。通過把我們的秘密向量s按照上面的拆分方式進行拆分，secret witness向量w= （x，X0，Y0，Y1），public witness向量x=（1，Out）。

上述過程通過使用開源專案中src/keygen/main.go（）裡面的函數groth16. SetupLazyWithDump（）之中的部分功能實現。

如果想更加具體地瞭解QAP問題我們推薦閱讀文獻【2】。

1. QAP問題->生成證明：

在介紹該流程之前，我們首先對使用的符號進行說明：

我們通過QAP問題按照如下的方法使用prover生成我們需要的證明：

我們根據上面的方法使用prover生成我們需要的證明檔proof（prover做的只是隨機選擇數域F裡面的元素，並對他們按照我們定義好的映射方式進行計算），將其保存在資料庫中。

1. 生成證明->驗證：

當我們的使用者需要驗證的時候，只需要從資料庫中調取我們的proof以及用戶驗證需要的vk，以及input x對上方verifier裡面的等式進行驗證，其中x就是上面所說的public witness（1，Out）=（1,35）。如果等式成立，就說明我們的QAP問題驗證成立，也就說明我們知道上方所提到的x^3+x+5=35的解。因為我們的多項式裡面的元素都是使用的橢圓曲線群（group）裡面的點，所以並不會洩漏任何其他的資訊，由此保證了我們和使用者的安全。

2.3生成證明的內容對應開源專案中src/keygen/main.go()裡面的函數groth16.SetupLazyWithDump()進行實現。 2.4證明內容通過開源專案中src/verifier/main.go進行實現。

如果想要瞭解具體的證明和驗證正確性和安全性問題，我們推薦閱讀文獻【3】。

以上就是我們的zksnark groth16的整個證明思路。具體的zkpor內容，我們只需要將現實的問題抽象成方程組，按照上面的流程一步一步向下即可。對於我們的zkpor的具體方程（約束設計）我們推薦閱讀：《基於零知識證明的PoR原理與實現》。

參考文獻：

【1】Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. DIZK: a distributed zero knowledge proof system. In Proceedings of the 27th USENIX Conference on Security Symposium (SEC'18). USENIX Association, USA, 675–692.

https://eprint.iacr.org/2018/691.pdf

【2】Gennaro, Rosario et al. “Quadratic Span Programs and Succinct NIZKs without PCPs.” IACR Cryptology ePrint Archive (2013).

https://eprint.iacr.org/2012/215.pdf

【3】Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666. Springer-Verlag, Berlin, Heidelberg, 305–326.

https://eprint.iacr.org/2016/260

在APP內開啟

為什麼要使用零知識證明來做儲備金證明？

2023/09/14 08:27

資產審計

zksnark及Groth16原理簡介

引言：

什麼是zksnark？

以下是現存的zk-snark簡介：

Halo：Halo支援遞歸證據組織，無需可信設置。與其他新的zk-SNARK構建不同，Halo的驗證時間是線性的。 Halo論文連結： https://eprint.iacr.org/2019/1021

SuperSonic：SuperSonic 是Sonic的改進版，是第一個在驗證時間和證明數據量方面實用化的透明zk-SNARK。 SuperSonic論文連結： https://eprint.iacr.org/2019/1229

Marlin：Marlin 是Sonic的改進版，證明時間縮短10倍，驗證時間縮短4倍。 Marlin論文連結： https://eprint.iacr.org/2019/1047

Plonk：Plonk也是Sonic的改進，證明時間縮短5倍。 Plonk論文連結： https://eprint.iacr.org/2019/953

我們的零知識證明採用的是groth16，下面是對該方案的詳細介紹：

實現路線：

我們通過：如下六個流程來完成我們的證明。

這篇文檔用一個現實的簡單的例子來做說明説明大家更好理解：

例子：如何證明我們知道方程x^3+x+5=35的解。

實現過程及簡單原理：

因為我們的問題本身就是證明我們知道一個方程的解，那麼我們直接從第二步：滿足的計算方程組->r1cs電路開始進行說明。

2.1 滿足的計算方程組->r1cs電路：

首先，將上面的計算方程組拆分成一次只做一次加減乘除中的一種運算的方程組。

E.g.：計算x^3+x+5=35 可以拆分為：

(1) X0 = x*x

(2) Y0 = X0*x

(3) Y1 = Y0+x

(4) Out = Y1+5

之後我們需要使用一個向量組（a,b,c）與解向量s滿足如下條件<s,a>*<s,b> = <s,c>。其中<*，*>表示向量內積。

為了滿足上面所說的解向量s與向量組（a，b，c）所滿足的關係，我們首先構造解向量s=（1，Out，x，X0，Y0，Y1）=（1,35,3,9,27,30）

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

所以當我們的解向量s輸入正確的時候，就代表我們能夠有這個方程組正確的解。

如果想具體瞭解r1cs電路的問題，我們推薦閱讀文獻【1】。

1. r1cs電路—>QAP問題：

但是通過這四個向量組解決這個問題顯得過於複雜，我們希望使用更加簡單的辦法

進行解決，由此我們需要把r1cs電路轉化為QAP問題。

我們先將剛才得到的四個向量組在下方列出來：

a1=(0,0,1,0,0,0)，b1=(0,0,1,0,0,0), c1=(0,0,0,1,0,0)

a2=(0,0,0,1,0,0)，b2=(0,0,1,0,0,0), c2=(0,0,0,0,1,0)

a3=(0,0,1,0,1,0)，b3=(1,0,0,0,0,0), c3=(0,0,0,0,0,1)

a4=(5,0,0,0,0,1)，b4=(1,0,0,0,0,0), c4=(0,1,0,0,0,0)

從向量a1，a2，a3，a4分別選擇第一個點：0,0,0,5構成y0，y1，y2，y3，選擇1,2,3,4構成x0，x1，x2，x3。

通過拉格朗日插值可以構造多項式fa_0（x）使得fa_0（1）=0，fa_0（2）=0，fa_0（3）=0，fa_0（4）=5

同理可以構造fa_1（x）...，fc_6（x）共18個多項式。

將這18個多項式按照如下方式排列：

向量a=（fa_0（x），fa_1（x），fa_2（x），fa_3（x）,...,fa_6(x))

但是分別帶入太麻煩了，如何一次驗證呢？

我們這裡令Z（x）=（x-1）（x-2）（x-3）（x-4）. 這裡是對上面選擇的x0，x1，x2，x3進行插值

當x為1,2,3,4的時候，我們的<s，a>*<s，b> = <s，c>成立也就是A（x）*B（x）-C（x）=0=H（x）Z（x）

其中A（x）=<s，a>，其中a是上面的向量a=（fa_0（x），fa_1（x），fa_2（x），fa_3（x）,...,fa_6（x）），B（x），C（x）同理。

上面是一個QAP問題的實例。

上述過程通過使用開源專案中src/keygen/main.go（）裡面的函數groth16. SetupLazyWithDump（）之中的部分功能實現。

如果想更加具體地瞭解QAP問題我們推薦閱讀文獻【2】。

1. QAP問題->生成證明：

在介紹該流程之前，我們首先對使用的符號進行說明：

我們通過QAP問題按照如下的方法使用prover生成我們需要的證明：

1. 生成證明->驗證：

2.3生成證明的內容對應開源專案中src/keygen/main.go()裡面的函數groth16.SetupLazyWithDump()進行實現。 2.4證明內容通過開源專案中src/verifier/main.go進行實現。

如果想要瞭解具體的證明和驗證正確性和安全性問題，我們推薦閱讀文獻【3】。

參考文獻：

https://eprint.iacr.org/2018/691.pdf

【2】Gennaro, Rosario et al. “Quadratic Span Programs and Succinct NIZKs without PCPs.” IACR Cryptology ePrint Archive (2013).

https://eprint.iacr.org/2012/215.pdf

https://eprint.iacr.org/2016/260

2023/09/14 09:52

2023/09/14 09:51

2023/02/22 06:09

2023/02/22 06:08

2023/02/22 06:08

公告

搜尋

為什麼要使用零知識證明來做儲備金證明？

zksnark及Groth16原理簡介

zksnark及Groth16原理簡介