Zk-SNARKs：引擎蓋下_ARKS

作者：VitalikButerin

原標題：《Zk-SNARKs:UndertheHood》

發表時間：2017年2月1日

這是解釋zk-SNARKs背后的技術如何工作的系列文章的第三部分；以前關于二次算術程序和橢圓曲線配對的文章是必讀的，本文將假設這兩個概念的知識。還假設了zk-SNARK是什么以及它們做什么的基本知識。另請參閱此處的ChristianReitwiessner的文章以獲得另一篇技術介紹。

在之前的文章中，我們介紹了二次算術程序，這是一種用多項式方程表示任何計算問題的方法，它更適合各種形式的數學技巧。我們還介紹了橢圓曲線配對，它允許一種非常有限的單向同態加密形式，可以讓你進行相等性檢查。現在，我們將從上次中斷的地方開始，使用橢圓曲線配對以及其他一些數學技巧，以允許證明者證明他們知道特定QAP的解決方案，而無需透露任何關于實際解決方案。

本文將重點介紹Parno、Gentry、Howell和Raykova從2013年開始的Pinocchio協議；基本機制有一些變化，因此在實踐中實施的zk-SNARK方案可能會略有不同，但基本原理通常保持不變。

首先，讓我們進入我們將要使用的機制的安全性背后的關鍵密碼假設：指數知識假設。

Layer2 ZK-ZKVM 項目 Ola 發布第二版技術白皮書:4月9日消息，可編程性隱私和擴容方案 Ola 發布第二版技術白皮書，致力于構建一個集隱私、高性能、可編程性為一體的 Layer2 ZK-ZKVM 平臺，讓用戶真正掌控個人數據所有權與使用權。第二版白皮書強調了如何設計和構建 Ola 中最重要的基礎模塊，高性能的 ZKVM，OlaVM；ZK 友好的智能合約語言，Ola-lang；以及隱私的設計架構。

另外，Ola 已于近期開啟品牌升級計劃，將于 2023 年年內上線測試網，2024 年年初上線主網。據悉，Ola 由 Sin7y Labs 團隊研發，專注于 Layer2 的 ZK- ZKVM 方案。[2023/4/9 13:53:28]

基本上，如果你得到一對點P和Q，其中P*k=Q，并且你得到一個點C，那么除非C以某種方式從P“派生”出來，否則不可能得出C*k你知道的。這可能看起來很直觀，但是這個假設實際上不能從我們通常在證明基于橢圓曲線的協議的安全性時使用的任何其他假設推導出來，因此zk-SNARK實際上確實依賴于比橢圓曲線密碼學更普遍的基礎更不穩定——盡管它仍然足夠堅固，大多數密碼學家都可以接受。

現在，讓我們來看看如何使用它。假設有一對點(P,Q)從天上掉下來，其中P*k=Q，但沒有人知道k的值是多少。現在，假設我提出了一對點(R,S)，其中R*k=S。那么，KoE假設意味著我可以得出這對點的唯一方法是取P和Q，并且將兩者乘以我個人知道的某個因子r。還要注意，由于橢圓曲線配對的魔力，檢查R=k*S實際上并不需要知道k-相反，你可以簡單地檢查e(R,Q)=e(P,S)。

V神：以太坊不需要為Layer 1使用單一的ZK-EVM實現進行標準化:金色財經報道，以太坊創始人Vitalik Buterin發文解釋了“不同類型的ZK-EVM和類似ZK-EVM的項目，以及它們之間的權衡”。V神例舉了描述了多個EVM等價的不同“類型”的分類，以及嘗試實現每種類型的好處和成本。

V神總結稱，就我個人而言，我希望隨著時間的推移，通過ZK-EVM的改進和以太坊本身的改進相結合，使其對ZK-SNARK更加友好，一切都將成為Type1。在這樣的未來，我們將有多個ZK-EVM實現，它們既可以用于ZK匯總，也可以用于驗證以太坊鏈本身。

從理論上講，以太坊不需要為Layer1使用單一的ZK-EVM實現進行標準化；不同的客戶可以使用不同的證明，因此我們繼續從代碼冗余中受益。但是，要實現這樣的未來，還需要相當長的時間。與此同時，我們將在擴展以太坊和基于以太坊的ZK-rollup的不同路徑中看到許多創新。[2022/8/4 12:02:16]

讓我們做一些更有趣的事情。假設我們有十對點從天而降：(P_1,Q_1),(P_2,Q_2)…(P_10,Q_10)。在所有情況下，P_i*k=Q_i。假設我隨后為你提供一對點(R,S)，其中R*k=S。你現在知道什么？你知道R是一些線性組合P_1*i_1+P_2*i_2+…+P_10*i_10，其中我知道系數i_1,i_2…i_10。也就是說，要得到這樣的一對點，唯一的方法就是取P_1，P_2…P_10的一些倍數并將它們相加，然后用Q_1，Q_2…Q_10進行相同的計算。

Qtum創始人：Qtum正在為GameFi等開發zk-rollup layer2解決方案:1月3日消息，Qtum創始人Patrick Dai表示，Qtum正在為GameFi和SocialFi以及元宇宙區塊鏈基礎設施開發zk-rollup layer2解決方案。零知識證明是實現Web3去信任的最佳擴容解決方案之一。 Qtum TPS 可以達到1萬，交易費用可以是1-2美分。[2022/1/3 8:21:32]

請注意，給定任何你可能想要檢查線性組合的特定P_1…P_10點集，你實際上無法在不知道k是什么的情況下創建隨附的Q_1…Q_10點，如果你確實知道k是什么，那么你可以創建一對(R,S)，其中R*k=S為你想要的任何R，而無需創建線性組合。因此，要使其發揮作用，絕對必須確保創建這些點的人是值得信賴的，并且在創建十個點后實際上刪除k。這就是“可信設置”概念的來源。

請記住，QAP的解是一組多項式(A,B,C)，使得A(x)*B(x)-C(x)=H(x)*Z(x)，其中：

A是一組多項式{A_1…A_m}的線性組合

B是具有相同系數的{B_1…B_m}的線性組合

C是具有相同系數的{C_1…C_m}的線性組合

集合{A_1…A_m}、{B_1…B_m}和{C_1…C_m}以及多項式Z是問題陳述的一部分。

基于zk-Rollup的Layer 2隱私協議Zecrey獲得Polygon基金會的資助:10月24日消息，基于zk-Rollup的Layer 2隱私協議Zecrey宣布獲得Polygon基金會的資助。[2021/10/24 6:10:24]

但是，在大多數實際情況下，A、B和C都非常大；對于像散列函數這樣具有數千個電路門的東西，多項式可能有數千個項。因此，我們不是讓證明者直接提供線性組合，而是使用我們上面介紹的技巧讓證明者證明他們提供的東西是線性組合，但不透露其他任何東西。

你可能已經注意到，上面的技巧適用于橢圓曲線點，而不是多項式。因此，實際發生的是我們將以下值添加到可信設置中：

G*A_1(t),G*A_1(t)*k_aG*A_2(t),G*A_2(t)*k_a…G*B_1(t),G*B_1(t)*k_bG*B_2(t),G*B_2(t)*k_b…G*C_1(t),G*C_1(t)*k_cG*C_2(t),G*C_2(t)*k_c…你可以將t視為計算多項式的“秘密點”。G是一個“生成器”，t、k_a、k_b和k_c是“有廢物”，絕對必須不惜一切代價刪除的數字，或者擁有它們的人將能夠制作假證明。現在，如果有人給你一對點P,Q使得P*k_a=Q，那么你知道他們給了什么你是在t處求值的A_i多項式的線性組合。

以色列理工學院所研究的區塊鏈隱私解決方案 ZK-Starks正在變成現實:5月26日，據Coindesk報道，以色列理工學院發明的區塊鏈隱私解決方案ZK-Starks受到許多開發者稱贊。所謂的zk-starks提供了一種有希望將大量信息壓縮成小樣本的方式，命名為starks，并可以使用零知識證明來保護該信息的隱私。Starks對于量子計算也是高效，透明和安全的，Starks團隊稱之為“令牌技術模型”.創始人Eli Ben-Sasson和Alessandro Chiesa正在走企業路線，希望將他們的新技術提供給實際區塊鏈以換取其原生資產。許多社區的倡導者對這項技術發表了積極的評論，其中包括以太坊創始人Vitalik，他曾暗示這種系統可以部署在“以太坊3.0”之上。Ben-Sasson稱：“我們的技術是獨一無二的，因為它是目前唯一一個允許真正指數級加速驗證的計算系統，無需設置假設，也無需事先分配任何密鑰。”[2018/5/27]

因此，到目前為止，證明者必須給出：

π_a=G*A(t),π'_a=G*A(t)*k_aπ_b=G*B(t),π'_b=G*B(t)*k_bπ_c=G*C(t),π'_c=G*C(t)*k_c

請注意，證明者實際上不需要知道t、k_a、k_b或k_c來計算這些值；相反，證明者應該能夠僅根據我們添加到可信設置的點來計算這些值。

下一步是確保所有三個線性組合具有相同的系數。我們可以通過向可信設置添加另一組值來做到這一點：G*(A_i(t)+B_i(t)+C_i(t))*b，其中b是另一個應該被視為“有廢物”的數字，并且受信任的設置完成后立即丟棄。然后，我們可以讓證明者使用具有相同系數的這些值創建一個線性組合，并使用與上述相同的配對技巧來驗證該值是否與提供的A+B+C匹配。

最后，我們需要證明A*B-C=H*Z。我們通過配對檢查再次執行此操作：

e(π_a,π_b)/e(π_c,G)?=e(π_h,G*Z(t))

其中π_h=G*H(t)。如果這個方程和A*B-C=H*Z之間的聯系對你來說沒有意義，請返回閱讀有關配對的文章。

我們在上面看到了如何將A、B和C轉換為橢圓曲線點；G只是生成器。我們可以將G*Z(t)添加到可信設置中。H更硬；H只是一個多項式，我們很少提前預測每個單獨QAP解決方案的系數。因此，我們需要向可信設置添加更多數據；具體順序：

G,G*t,G*t2,G*t3,G*t?...。

在Zcash可信設置中，這里的序列高達200萬左右；這是你需要多少次冪才能確保始終能夠計算H(t)，至少對于他們關心的特定QAP實例而言。這樣，證明者就可以為驗證者提供所有信息以進行最終檢查。

還有一個細節需要我們討論。大多數時候，我們不只是想抽象地證明某些特定問題的解決方案存在；相反，我們想證明某個特定解決方案的正確性，或者如果你限制解決方案存在一些參數。例如，在交易金額和賬戶余額被加密的加密貨幣實例中，你想證明你知道一些解密密鑰k，這樣：

加密的old_balance、tx_value和new_balance應該公開指定，因為這些是我們希望在特定時間驗證的特定值；只有解密密鑰應該被隱藏。需要對協議進行一些細微的修改，以創建與輸入的某些特定限制相對應的“自定義驗證密鑰”。

現在，讓我們退后一步。首先，這里是完整的驗證算法，由benSasson、Tromer、Virza和Chiesa提供：

第一行處理參數化；本質上，你可以將其功能視為為指定了某些參數的問題的特定實例創建“自定義驗證密鑰”。第二行是A、B、C的線性組合檢查；第三行是檢查線性組合是否具有相同的系數，第四行是乘積檢查A*B-C=H*Z。

總之，驗證過程是幾個橢圓曲線乘法和五次配對檢查，其中一次包括額外的配對乘法。證明包含八個橢圓曲線點：A(t)、B(t)和C(t)各有一對點，b*(A(t)+B(t)+C(t)有一個點π_k))，以及H(t)的點π_h。其中七個點在F_p曲線上，在Zcash實現中，一個點(π_b)在F_p2的扭曲曲線上，所以證明的總大小約為288字節。

創建證明的兩個計算上最難的部分是：

將(A*B-C)/Z除以得到H進行橢圓曲線乘法和加法運算以創建A(t)、B(t)、C(t)和H(t)值及其對應的對創建證明如此困難的基本原因是，如果我們要從中制作零知識證明，原始計算中的單個二進制邏輯門變成了必須通過橢圓曲線操作進行加密處理的操作.這一事實，加上快速傅立葉變換的超線性，意味著Zcash交易的證明創建需要大約20-40秒。

另一個非常重要的問題是：我們是否可以嘗試使受信任的設置稍微……不那么需要信任？不幸的是，我們不能讓它完全不信任；KoE假設本身排除了在不知道k是什么的情況下制作獨立對(P_i,P_i*k)。但是，我們可以通過使用N-of-N多方計算來大大提高安全性——也就是說，在N方之間構建可信設置，只要至少有一個參與者刪除他們的有廢物，那么你就可以了.

為了稍微了解如何執行此操作，這里有一個簡單的算法，用于獲取現有集合，并“添加”你自己的秘密，以便你需要你的秘密和以前的秘密來作弊。

輸出集很簡單：

G,(G*t)*s,(G*t2)*s2,(G*t3)*s3…

請注意，你可以只知道原始集合和s來生成此集合，并且新集合的功能與舊集合相同，只是現在使用t*s作為“有廢物”而不是t。只要你和創建前一組的人都沒有刪除你的有廢物并隨后串通，那么該組是“安全的”。

為完整的受信任設置執行此操作要困難得多，因為涉及多個值，并且必須在各方之間分幾輪完成算法。這是一個積極研究的領域，看看是否可以進一步簡化多方計算算法并使其需要更少的輪次或更可并行化，因為你可以做的越多，參與可信設置過程的參與方就越多.有理由看到為什么六個相互認識并一起工作的參與者之間的信任設置可能會讓一些人感到不舒服，但是一個擁有數千名參與者的信任設置與完全不信任幾乎沒有區別——而且如果你真的很偏執，你可以自己進入并參與設置過程，并確保你親自刪除了你的值。

另一個活躍的研究領域是使用不使用配對的其他方法和相同的可信設置范例來實現相同的目標。請參閱ElibenSasson最近的演示文稿以了解另一種選擇

特別感謝ArielGabizon和ChristianReitwiessner的審閱。

Tags：ARK以太坊LAYERARKSark幣和木頭姐有什么關系以太坊硬幣layer幣的價值ARKS價格

SHIB