StarkWare-用於提高區塊鏈的可拓展性和隱私性的堆棧

最新 05-29

項目概要

【StarkWare】（A預評級）V神參與的以色列已完成600萬USD種子輪，暫未眾籌 ; 項目概念：用於提高區塊鏈的可拓展性和隱私性的堆棧; 項目分類：基礎設施（零知識證明）;

官網：starkware.co

Stark是一種新密碼證明系統，可能服務於構建更安全和更具擴展性的區塊鏈。

StarkWare將使用STACK技術提高區塊鏈的可擴展性和隱私，提供零知識、簡潔、透明(不需要可信設置)和後量子安全的密碼證明。StarkWare將開發一個完整的驗證堆棧：軟體和硬體，以支持快速可靠地生成和驗證通用計算的計算完整性證明。已完成600萬USD種子輪，暫無眾籌計劃。

項目介紹

StarkWare將使用STARK技術提高區塊鏈的可擴展性和隱私性，提供零知識，簡潔，透明（不需要可信任安裝）和後量子安全的密碼證明。

StarkWare將開發一個完整的驗證堆棧：軟體和硬體，以支持用於一般計算的計算完整性證明的快速和可靠的生成和驗證。

STARKs，第一部分：多項式證明

特別感謝Eli Ben-Sasson提供的正在進行的幫助，解釋和評論，提出了本文中使用的一些示例，最重要的是發明了很多這樣的東西; 感謝王曉偉的回顧

希望很多人現在都聽說過ZK-SNARKs，它是通用簡潔的零知識證明技術，可用於從可驗證計算到隱私保護加密貨幣等各種用途的應用。你可能不知道的是ZK-SNARKs有一個更新，更閃亮的堂兄：ZK-STARKs。由於T代表「透明」，ZK-STARK解決了ZK-SNARKs的一個主要弱點，即它依賴於「可信賴的設置」。它們還帶有更簡單的密碼假設，避免了對橢圓曲線，配對和指數知識假設的需求，而是純粹依賴散列和信息理論; 這也意味著即使對量子計算機的攻擊者也是如此。

但是，這需要付出代價：證明的大小從288個位元組增加到幾百個千位元組。有時候成本並不值得，但在其他時候，特別是在對信任最小化的需求很高的公共區塊鏈應用環境中，它可能是這樣。如果橢圓曲線斷裂或量子計算機確實會出現，那肯定會是。

那麼這種其他類型的零知識證明是如何工作的呢？首先，讓我們回顧一下通用簡潔ZKP的功能。假設你有一個（公共）函數f，一個（私有）輸入x和一個（公共）輸出y。你想證明你知道x這樣一個事實f(x) = y，而不會透露什麼x是。此外，為使證明簡潔，您希望它比計算f本身更快得到驗證。

我們來看幾個例子：

f是一項計算，需要兩周才能在普通計算機上運行，但在數據中心上需要兩個小時。您向數據中心發送計算（即要運行的代碼f），數據中心運行它，並y通過證據給出答案。您在幾毫秒內驗證證明，並確信y實際上是答案。

你有一個加密交易，形式為「X1是我的舊平衡。X2是你的舊平衡。X3是我的新餘額。X4是你的新平衡「。你想創建一個證明這筆交易是有效的證據（具體地說，新舊餘額非負數，我的餘額減少抵消了餘額的增加）。x可以是一對加密密鑰，並且f可以是包含作為內置公共輸入事務的函數，以密鑰作為輸入，解密事務，執行檢查，如果它通過則返回1，如果它通過則返回0不。y當然是1。

你有像以太坊這樣的區塊鏈，你可以下載最新的區塊。你想證明這個塊是有效的，並且這個塊位於鏈中每個塊有效的鏈的末端。您要求現有的完整節點提供這樣的證明。x是整個區塊鏈（是的，全部是千兆位元組），f是一個逐塊處理它的函數，驗證有效性並輸出最後一個塊y的散列，並且是你剛剛下載的塊的散列。

那麼這一切都很難？事實證明，零知識（即隱私）保證是（相對）容易提供的; 有很多方法可以將任何計算轉換為類似三色圖問題的實例，其中圖的三色對應於原始問題的解，然後使用傳統的零知識證明協議來證明你有一個有效的圖形著色而不會透露它是什麼。馬修·格林2014年的這篇出色的文章詳細描述了這一點。

要提供更難的是簡潔。直觀地說，簡潔地證明計算的事情很難，因為計算非常脆弱。如果你有一個長而複雜的計算，並且你作為一個邪惡的精靈有能力在計算中間的任何地方翻轉0到1，那麼在很多情況下，即使是一個翻轉的位也足以使計算得到完全不同的結果。因此，很難看到你如何做一些事情，比如隨機抽取一個計算軌跡來衡量它的正確性，因為它很容易錯過這個「一個壞點」。然而，用一些奇特的數學，事實證明，你可以。

一般來說，非常高層次的直覺是完成這個的協議使用與擦除編碼中使用的數據類似的數學，擦除編碼經常用於製作數據容錯。如果你有一段數據，並且你將數據編碼為一行，那麼你可以在線上選出四個點。這四點中的任何兩點都足以重建原始線，因此也給你另外兩點。此外，如果您對數據進行了細微的更改，那麼至少可以保證這四個點中的三個。您也可以將數據編碼為一個1,000,000多項式，並在多項式上選出2,000,000個點; 任何1,000,001點將恢復原始數據，因此其他點，原始數據的任何偏差將改變至少1,000,000點。這裡顯示的演算法將大量使用多項式來進行誤差放大。

即使改變原始數據中的一個點，也會導致多項式軌跡發生較大變化

一個簡單的例子

假設你要證明你有一個多項式P，從而P(x)為一個整數0

證明這一點的「傳統」方法是僅顯示所有1,000,000點，並通過檢查值驗證它。但是，我們想看看我們是否能夠做出可以在少於1,000,000步驟中驗證的證明。簡單地隨機檢查評估P不會做; 一個惡意的證明者總有可能提出一個P滿足999,999個地方的約束條件但在最後一個地方不滿足約束條件的地方，而隨機抽樣只有幾個值幾乎總是會錯過該值。那麼我們可以做什麼？

讓我們在數學上對這個問題進行一些改變。我們C(x)是一個約束檢查多項式 ; C(x) = 0如果0

現在，問題就變成了：證明你知道P這樣C(P(x)) = 0對所有x從1到100萬。讓Z(x) = (x-1) * (x-2) * ... (x-1000000)。這是一個已知的數學事實，任何等於零的多項式x從1到1,000,000是倍數Z(x)。因此，這個問題現在可以再次轉變：證明你知道P，並D使得C(P(x)) = Z(x) * D(x)所有的x（注意，如果你知道一個合適的C(P(x))，然後通過將其Z(x)以計算D(x)不是太困難，你可以使用長多項式除法或者更現實地更快的演算法基於FFT）。現在，我們已經將原來的陳述轉換成看起來數學上乾淨並且可能相當可證的東西。

那麼如何證明這一說法呢？我們可以將證明過程想像為證明者和驗證者之間的三步通信：證明者發送一些信息，然後驗證者發送一些請求，然後證明者發送更多信息。首先，證明方承諾（即作出了Merkle樹，並發送驗證的根hash）的各種評價P(x)，並D(x)為所有x從1到1十億（是的，十億）。這包括100萬分0

我們假設驗證者已經知道Z(x)所有這些點的評估; 該Z(x)就像是一個「公開驗證密鑰」這項計劃，每個人都必須預先知道（沒有存儲空間的客戶Z(x)的全部可以簡單地存儲的梅克爾根Z(x)，並要求證明者還為每個提供分支Z(x)值驗證者需要查詢;可選地，也有一些數量的欄位在其Z(x)對某些x非常容易計算）。在接收到承諾（即Merkle根）之後，驗證者隨後選擇一個x在1到10億之間的隨機16 值，並要求證明者提供Merkle分支P(x)和D(x)那裡。證明者提供這些值，並且驗證者檢查（i）分支匹配之前提供的Merkle根，並且（ii）在所有16個案例中C(P(x))實際上相等Z(x) * D(x)。

我們知道這個證明是完全完備的 - 如果你確實知道一個合適的P(x)，那麼如果你D(x)正確地計算和構造證明，它將總是通過所有16次檢查。但是，健全性 - 也就是說，如果惡意證明者提供了不好的結果P(x)，他們將被捕獲的最小概率是多少？我們可以分析如下。由於C(P(x))是一個度數為10的多項式，其度為-1000000多項式，因此其度數至多為10,000,000。一般而言，我們知道兩個不同的N次多項式至多在N個點上一致; 因此，度數為10,000,000的多項式不等於總是等於Z(x) * D(x)某些的多項式x將至少在990,000,000點上與他們全然不同意。因此，P(x)即使在一輪中發生壞事的可能性已經達到99％。經過16次檢查，被抓到的概率高達1 - 10 - 32 ; 也就是說，該方案與計算散列衝突一樣難以欺騙。

那麼......我們剛剛做了什麼？我們使用多項式來「增強」任何錯誤解決方案中的錯誤，以便對原始問題的任何不正確的解決方案（這將需要直接查找百萬個檢查）轉變為驗證協議的解決方案，該解決方案可能會被標記為錯誤的99％的時間，甚至一次檢查。

我們可以將這個三步機制轉換為非互動式證明，可以由一個證明者進行一次廣播，然後由任何人驗證，使用菲亞特 - 沙米爾啟發式。證明者首先建立一個Merkle樹P(x)和D(x)值，並計算樹的根散列。根本身然後被用作熵的來源，這決定了證明者需要提供的樹的哪些分支。然後證明者將Merkle根和分支一起作為證明。計算全部在證明方完成; 從數據中計算Merkle根的過程，然後使用它來選擇需要審計的分支，從而有效地替代對交互驗證者的需求。

沒有有效的惡意證明者唯一P(x)能做的就是一遍又一遍地做一個有效的證明，直到最終他們對他們計算出的Merkle根所選擇的分支感到非常幸運，但它的完整性為1 - 10 -32（即一個給定的假冒偽造證明不能通過該檢查的概率至少為1 - 10 - 32），那麼證明數十億年的惡意證據就會證明其可靠性。

走得更遠

為了說明這種技術的強大功能，讓我們用它來做一些簡單的事情：證明你知道第100個斐波那契數。為了達到這個目的，我們將證明你有一個表示計算帶的多項式的知識，P(x)表示第x個Fibonacci數。約束檢查多項式現在在三個x坐標跳：C(x1, x2, x3) = x3-x2-x1（注意，如果是如何C(P(x), P(x+1), P(x+2)) = 0為所有x然後P(x)表示斐波納契數列）。

翻譯的問題變成：證明你知道P並且D這樣C(P(x), P(x+1), P(x+2)) = Z(x) * D(x)。對於每個16個指數的證明審計，證明者需要為提供了Merkle分支P(x)，P(x+1)，P(x+2)和D(x)。證明者還需要提供Merkle分支來證明這一點P(0) = P(1) = 1。否則，整個過程是相同的。

事實證明，這種可能性可以有效地防範，雖然這樣做的工具相當複雜，所以你可以合理地說它們構成了STARK中的大部分數學創新。此外，該解決方案還有一個局限性：您可以清除對距離任意度-1000000多項式很遠的數據的承諾（例如，您需要更改所有值的20％以使其成為-1000000多項式），但是您不能刪除對僅與一個或兩個坐標中的多項式不同的數據的承諾。因此，這些工具將提供的是接近證明 - 證明P和D上的大多數點對應於正確的多項式。

事實證明，這足以作出證明，雖然有兩個「捕獲」。首先，驗證者需要檢查幾個指數來彌補這個限制引入的額外錯誤空間。其次，如果我們正在進行「邊界約束檢查」（P(0) = P(1) = 1例如上面斐波納契示例中的驗證），那麼我們需要擴展鄰近證明，不僅證明大多數點在同一個多項式上，而且還證明這兩個特定點（或任何其他數量的特定點要檢查）都在該多項式上。

在本系列的下一部分中，我將更詳細地描述接近檢查的解決方案，並且在第三部分中，我將描述如何構造更複雜的約束函數來檢查斐波那契數字和範圍，還可以進行任意計算。

項目應用