原文標題：Binius: highly efficient proofs over binary fields

原文作者：Vitalik Buterin

原文編譯：Kate，MarsBit

這篇文章主要針對大致熟悉2019 年時代密碼學的讀者，特別是SNARK 和STARK。如果你不是，我建議你先閱讀這些文章。特別感謝 Justin Drake, Jim Posen, Benjamin Diamond 和 Radi Cojbasic 的回饋和評論。

在過去的兩年中，STARK 已經成為一種關鍵且不可替代的技術，可以有效地對非常複雜的語句進行易於驗證的加密證明（例如，證明以太坊區塊是有效的）。其中一個關鍵原因是欄位大小小：基於橢圓曲線的SNARK 要求您在256 位元整數上工作才能足夠安全，而STARK 允許您使用更小的欄位大小，效率更高：首先是Goldilocks 欄位（64 位元整數） ，然後是Mersenne31 和BabyBear（都是31 位）。由於這些效率的提高，使用 Goldilocks 的 Plonky2 在證明多種計算方面比其前輩快數百倍。

一個自然而然的問題是：我們能否將這一趨勢引向合乎邏輯的結論，透過直接在零和一上操作來建立運行速度更快的證明系統？這正是 Binius 試圖做的事情，使用了許多數學技巧，使其與三年前的 SNARK 和 STARK 截然不同。這篇文章介紹了為什麼小字段使證明生成更有效率，為什麼二進位字段具有獨特的強大功能，以及 Binius 用來使二進製字段上的證明如此有效的技巧。

Binius。在這篇文章的最後，你應該可以理解此圖的每個部分。

回顧：有限領域（finite fields）

加密證明系統的關鍵任務之一是對大量資料進行操作，同時保持數字較小。如果你可以將一個關於大型程式的語句壓縮成一個包含幾個數字的數學方程，但是這些數字與原始程式一樣大，那麼你將一無所獲。

為了在保持數字較小的情況下進行複雜的算術，密碼學家通常使用模運算 (modular arithmetic)。我們選擇一個質數“模數”p。 % 運算子的意思是「取餘數」：15%7=1，53%10=3，等等。 （請注意，答案總是非負數的，所以例如-1%10=9）

你可能已經在時間的加減上下文中見過模運算( 例如，9 點過4 小時是幾點？但在這裡，我們不只是對某個數進行加、減模，我們還可以進行乘、除和取指數。>

以上規則都是自洽的。 )

1-3=5（因為-2%7=5）

2*5=3

3/5=2

這種結構的更通用術語是有限域。值都可以用固定的大小表示。 。 12i+4i+8=16i+2。 Binius 使用) 完全依賴擴展以具有實際效用。 SNARK 和STARK 證明電腦程式的方法是透過算術：你把一個關於你想證明的程式的陳述，轉換成一個包含多項式的數學方程式。>

舉個簡單的例子，假設我計算了第100 個斐波那契數，我想向你證明它是什麼。多項式F：所以F(0)=F(1)=1、F(2)=2、F(3)=3、F(4)=5 依此類推，共100 步。 F(x+2)=F(x)+F(x+1) 在整個範圍內x={0,1…98}。

其中Z(x) = (x-0) * (x-1) * … (x-98)。 . 如果我能提供有 F 且 H 滿足此等式，則 F 必須在該範圍內滿足 F(x+2)-F(x+1)-F(x)。如果我另外驗證滿足 F，F(0)=F(1)=1，那麼 F(100) 其實必須是第 100 個斐波那契數。

如果你想證明一些更複雜的東西，那麼你用一個更複雜的方程式來取代「簡單」關係F(x+2) = F(x ) + F(x+1)，它基本上是說「F(x+1) 是初始化一個虛擬機器的輸出，狀態是F(x)”，並且運行一個計算步驟。你也可以用一個更大的數字來代替數字 100，例如，100000000，以容納更多的步驟。

所有SNARK 和STARK 都基於這個想法，即使用多項式( 有時是向量和矩陣) 上的簡單方程式來表示單一值之間的大量關係。並非所有的演算法都像上面那樣檢查相鄰計算步驟之間的等價性：例如，PLONK 沒有，R1CS 也沒有。但是許多最有效的檢查都是這樣做的，因為多次執行相同的檢查 ( 或相同的少數檢查 ) 可以更輕鬆地將開銷降至最低。

Plonky2：從256 位元SNARK 和STARK 到64 位元...... 只有STARK

五年前，不同類型的零知識證明的合理總結如下。有兩種類型的證明：( 基於橢圓曲線的 )SNARK 和 ( 基於哈希的 )STARK。從技術上講，STARK 是 SNARK 的一種，但在實踐中，通常使用“SNARK”來指基於橢圓曲線的變體，而使用“STARK”來指基於哈希的結構。 SNARK 很小，因此你可以非常快速地驗證它們並輕鬆地將它們安裝在鏈上。 STARK 很大，但它們不需要可信的設置，而且它們是抗量子的。

STARK 的工作原理是將資料視為多項式，計算該多項式的計算，並使用擴展數據的梅克爾根作為“多項式承諾”。

這裡的一個關鍵歷史是，基於橢圓曲線的SNARK 首先得到了廣泛的使用：直到2018 年左右，STARK 才變得足夠高效，這要歸功於FRI，而那時Zcash 已經運行了一年多。基於橢圓曲線的 SNARK 有一個關鍵的限制：如果你想使用基於橢圓曲線的 SNARK，那麼這些方程中的算術必須使用橢圓曲線上的點數模數來完成。這是一個很大的數字，通常接近 2 的 256 次方：例如，bn128 曲線為 2188824287183927522224640574525727508854836440041603434369250886但實際的計算使用的是小數字：如果你用你最喜歡的語言來考慮一個“真正的”程序，它使用的大部分東西是計數器，for 循環中的索引，程序中的位置，代表True 或False 的單一位，以及其他幾乎總是只有幾位數長的東西。

即使你的「原始」資料由「小」數字組成，證明過程也需要計算商數、擴展、隨機線性組合和其他資料轉換，這將導致相等或更大數量的對象，這些對象的平均大小與你的字段的全部大小一樣大。這造成了一個關鍵的低效率：為了證明對 n 個小值的計算，你必須對 n 個大得多的值進行更多的計算。起初，STARK 繼承了 SNARK 使用 256 位元欄位的習慣，因此也遭受了同樣的低效率。

一些多項式求值的 Reed-Solomon 擴充。儘管原始值很小，但額外的值都將擴展到字段的完整大小( 在本例中是2 的31 次方-1)

2022年，Plonky2 發布。 Plonky2 的主要創新是對一個較小的質數進行算術取模：2 的 64 次方 – 2 的 32 次方 + 1 = 18446744067414584321。現在，每次加法或乘法總是可以在 CPU 上的幾個指令中完成，並且將所有資料哈希在一起的速度比以前快 4 倍。但這有一個問題：這種方法只適用於 STARK。如果你嘗試使用 SNARK，對於如此小的橢圓曲線，橢圓曲線將變得不安全。

為了確保安全，Plonky2 還需要引入擴充欄位。檢查算術方程式的一個關鍵技術是「隨機點抽樣」：如果你想檢查的H(x) * Z(x) 是否等於F(x+2)-F(x+1)-F(x)，你可以隨機選擇一個座標r，提供多項式承諾開證明證明H(r)、Z(r) 、F(r)，F(r+1) 和F(r+2)，然後驗證H(r) * Z(r) 是否等於F(r+2)-F(r+1)- F(r)。如果攻擊者可以提前猜出座標，那麼攻擊者就可以欺騙證明系統——這就是為什麼證明系統必須是隨機的。但這也意味著座標必須從一個足夠大的集合中採樣，以使攻擊者無法隨機猜測。如果模數接近 2 的 256 次方，這顯然是事實。但是，對於模數是 2 的 64 次方 -2 的 32 次方 +1，我們還沒到那一步，如果我們降到 2 的 31 次方 -1，情況肯定不是這樣。試圖偽造證明 20 億次，直到一個人幸運，這絕對在攻擊者的能力範圍內。

為了阻止這種情況，我們從擴展字段中採樣r，例如，你可以定義y，其中y 的3 次方=5，並採用1、y、y的2 次方的組合。這將使座標的總數增加到大約 2 的 93 次方。證明者計算的多項式的大部分不進入這個擴展域；只是用整數取模 2 的 31 次方 -1，因此，你仍然可以從使用小域中獲得所有的效率。但是隨機點檢查和 FRI 計算確實深入到這個更大的領域，以獲得所需的安全性。

從小質數到二進制數

計算機透過將較大的數字表示為0 和1 的序列來進行算術運算，並在這些bit 之上建構「電路」來計算加法和乘法等運算。計算機特別針對 16 位元、32 位元和 64 位元整數進行了最佳化。例如，2 的64 次方-2 的32 次方+1 和2 的31 次方-1，選擇它們不僅是因為它們符合這些界限，還因為它們與這些界限很吻合：可以透過執行常規的32 位乘法來執行乘法取模2 的64 次方-2 的32 次方+1，並在幾個地方按位移位和複製輸出；這個文章很好地解釋了一些技巧。

然而，更好的方法是直接用二進制進行計算。如果加法可以「只是」異或，而無需擔心「攜帶」從一個位元添加 1 + 1 到下一個位的溢出？如果乘法可以以同樣的方式更加並行化呢？這些優點都是基於能夠用一個 bit 表示真 / 假值。

取得直接進行二進位計算的這些優點正是 Binius 試圖要做的。 Binius 團隊在zkSummit 的演講中展示了效率提升：

儘管「大小」大致相同，但32 位元二進位字段操作比31 位元Mersenne 字段操作所需的計算資源少5 倍。

從一元多項式到超立方體

假設我們相信這個推理，並且想要用bit(0 和1) 來做所有的事情。我們如何用一個多項式來表示十億 bit 呢？

在這裡，我們面臨兩個實際問題：

1. 對於一個表示大量值的多項式，這些值需要在多項式的求值時可以存取：在上面的斐波那契例子中，F(0)，F(1) … F(100)，在一個更大的計算中，指數會達到數百萬。我們使用的欄位需要包含到這個大小的數字。

2. 證明我們在Merkle 樹中提交的任何值( 就像所有STARK 一樣) 都需要Reed-Solomon 對其進行編碼：例如，將值從n 擴展到8n，使用冗餘來防止惡意證明者在計算過程中偽造一個值來作弊。這也需要有一個足夠大的字段：要將一百萬個值擴展到 800 萬個，你需要 800 萬個不同的點來計算多項式。

Binius 的一個關鍵思想是分別解決這兩個問題，並透過以兩種不同的方式表示相同的數據來實現。首先，多項式本身。基於橢圓曲線的 SNARK、2019 時代的 STARK、Plonky2 等系統通常處理一個變數上的多項式：F(x)。另一方面，Binius 從 Spartan 協議中獲得靈感，並使用多元多項式：F(x1,x2,… xk)。實際上，我們在計算的「超立方體」上表示整個計算軌跡，其中每個 xi 不是 0 就是 1。例如，如果我們想要表示一個斐波那契數列，並且我們仍然使用一個足夠大的字段來表示它們，我們可以將它們的前16 個數列想像成這樣：

也就是說，F(0,0,0,0) 應該是1，F(1,0,0 ,0) 也是1，F(0,1,0,0) 是2，以此類推，一直到F(1,1,1,1)=987。給定這樣一個計算的超立方體，就會有一個產生這些計算的多元線性 ( 每個變數的度數為 1) 多項式。所以我們可以把這組值看成是多項式的代表；我們不需要計算係數。

這個例子當然只是為了說明：在實踐中，進入超立方體的全部意義是讓我們處理單一 bit。計算斐波那契數的「Binius 原生」方法是使用一個高維的立方體，使用每組例如 16 位元儲存一個數字。這需要一些聰明才智來在 bit 的基礎上實現整數相加，但對於 Binius 來說，這並不太難。

現在，我們來看看糾刪碼。 STARK 的工作方式是：你取n 值，Reed-Solomon 將它們擴展到更多的值( 通常8n，通常在2n 和32n 之間)，然後從擴展中隨機選擇一些Merkle 分支，並對它們執行某種檢查。超立方體在每個維度上的長度為 2。因此，直接擴展它是不實際的：沒有足夠的“空間”從 16 個值中採樣 Merkle 分支。那我們該怎麼做呢？我們假設超立方體是一個正方形！

簡單的Binius - 一個例子

請參考此處查看該協定的python 實作。

讓我們看一個範例，為了方便起見，使用正規整數作為我們的欄位 ( 在實際實作中，將使用二進位欄位元素 )。首先，我們將想要提交的超立方體，編碼為正方形：

現在，我們用Reed-Solomon 擴展正方形。也就是說，我們將每一行視為在x ={0,1,2,3} 處求值的3 次多項式，並在x ={4,5,6,7} 處求值相同的多項式：

注意，數字會快速膨脹！這就是為什麼在實際實作中，我們總是使用有限域，而不是正規整數：如果我們使用整數模 11，例如，第一行的擴展將只是 [3,10,0,6]。

如果你想嘗試擴展並親自驗證這裡的數字，可以在這裡使用我的簡單 Reed-Solomon 擴充程式碼。

接下來，我們將此擴充視為列，並建立列的 Merkle 樹。梅克爾樹的根是我們的承諾。

現在，讓我們假設證明者想要在某個時候證明這個多項式的計算r={r0,r1,r2,r3}。在Binius 中有一個細微的差別，使它比其他多項式承諾方案更弱：證明者在提交到Merkle 根之前不應該知道或能夠猜測s ( 換句話說，r 應該是一個依賴於默克爾根的偽隨機值)。這使得該方案對「資料庫查找」無用 ( 例如，「好吧，你給了我默克爾根，現在證明給我看 P(0,0,1,0)！」)。但是我們實際使用的零知識證明協議通常不需要「資料庫查找」；他們只需要在一個隨機的求值點檢查多項式。因此，這個限制符合我們的目的。

假設我們選擇r={1,2,3,4} ( 此時多項式的計算結果為-137；你可以使用此程式碼進行確認) 。現在，我們進入了證明的過程。我們分為 r 兩部分：第一部分 {1,2} 表示行內列的線性組合，第二部分 {3,4} 表示行的線性組合。我們計算一個「張量積」，對於列部分：

對於行部分：

這意味著：每個集合中一個值的所有可能乘積的列表。在行情況下，我們得到：

[(1-r2)*(1-r3), (1-r3), (1-r2)* r3, r2*r3]

用r={1,2,3,4} ( 所以r2=3 和r3=4)：

[(1-3)*(1-4), 3*(1-4),(1-3)*4,3*4] = [6, -9 -8 -12]

現在，我們透過採用現有行的線性組合來計算一個新的「行」t。也就是說，我們取：

你可以把這裡發生的看作是部分求值。如果我們把全張量乘積乘以所有值的全向量，你將得到計算 P(1,2,3,4) = -137。在這裡，我們將只使用一半評估座標的偏張量乘積相乘，並將 N 值網格簡化為一行根 N 的值。如果你把此行提供給其他人，他們可以用另一半的求值座標的張量積來完成剩下的計算。

證明者向驗證者提供以下新行：t 以及一些隨機抽樣列的Merkle 證明。在我們的說明性範例中，我們將讓證明程式只提供最後一列；在現實生活中，證明者需要提供數十列來實現足夠的安全性。

現在，我們利用 Reed-Solomon 程式碼的線性。我們使用的關鍵屬性是：取一個 Reed-Solomon 擴充的線性組合得到與線性組合的 Reed-Solomon 擴充相同的結果。這種「順序獨立性」通常發生在兩個操作都是線性的情況下。

驗證者正是這樣做的。他們計算了 t，並且計算與證明者之前計算的相同的列的線性組合 ( 但只計算證明者提供的列 )，並驗證這兩個過程是否給出相同的答案。

在本例中，是擴充t，計算相同的線性組合( [6,-9,-8,12]，兩者給了相同的答案：-10746 這證明默克爾的根是「善意」建構的( 或至少「夠接近」)，而且它是匹配t 的：至少絕大多數列是相容的。

但是驗證者還需要檢查另一件事：檢查多項式 {r0…r3} 的求值。到目前為止，驗證者的所有步驟實際上都沒有依賴證明者聲稱的值。我們是這樣檢查的。我們取我們標記為計算點的「列部分」的張量積：

在我們的例子中，其中r={1,2,3,4} 所以選擇列的那一半是{1,2})，這等於：

現在我們取這個線性組合t：

這和直接求多項式的結果是一樣的。

以上內容非常接近「簡單」Binius 協定的完整描述。這已經有了一些有趣的優點：例如，由於資料被分成行和列，因此你只需要一個大小減半的欄位。但是，這並不能實現用二進制進行計算的全部好處。為此，我們需要完整的 Binius 協定。但首先，讓我們更深入地了解二進位字段。

二進位字段

最小的可能域是算術模2，它非常小，我們可以寫出它的加法和乘法表：

我們可以透過擴展得到更大的二進位字段：如果我們從F2( 整數模2) 然後定義x 在哪裡x 的平方=x+1，我們得到以下的加法和乘法表：

事實證明，我們可以透過重複這個構造將二進位字段擴展到任意大的大小。與實數上的複數不同，在實數上，你可以加一個新元素，但不能再添加任何元素I（四元數確實存在，但它們在數學上很奇怪，例如：ab 不等於ba)，使用有限的字段，你可以永遠添加新的擴充。具體來說，我們對元素的定義如下：

等等.. ....。這通常被稱為塔式結構，因為每一個連續的擴展都可以被視為為塔增加了一個新的層。這並不是構造任意大小二進位字段的唯一方法，但它有一些獨特的優點，Binius 利用了這些優點。

我們可以把這些數字表示成 bit 的清單。例如，1100101010001111。第一位表示 1 的倍數，第二位表示 x0 的倍數，然後後續位元表示以下 x1 數的倍數： x1, x1*x0, x2, x2*x0, 依此類推。這種編碼很好，因為你可以分解它：

這是一種相對不常見的表示法，但我喜歡將二進位字段元素表示為整數，採用更有效bit 在右側的位元表示。也就是說，1=1，x0=01=2，1+x0=11=3，1+x0+x2=11001000 =19, 等等。在這個表達式中，是 61779。

二進位字段中的加法只是異或 ( 順便說一句，減法也是如此 )；注意，這意味著 x+x=0 對於任何 x。將兩個元素x*y 相乘，有一個非常簡單的遞歸演算法：把每個數字分成兩半：

然後，將乘法分割：

最後一部分是唯一有點棘手的，因為你必須應用簡化規則。有更有效的方法來做乘法，類似於 Karatsuba 演算法和快速傅立葉變換，但我將把它作為一個練習留給有興趣的讀者去弄清楚。

二進位欄位中的除法是透過結合乘法和反轉來完成的。 「簡單但緩慢」的反轉方法是廣義費馬小定理的應用。還有一個更複雜但更有效的反演演算法，你可以在這裡找到。你可以使用這裡的程式碼來玩二進位字段的加法，乘法和除法。

左圖：四位二進位字段元素（即僅由1、x0 、x1、x0x1）的加法表。右圖：四位二進位字段元素的乘法表。

這種類型的二進位字段的美妙之處在於，它結合了“正則”整數和模運算的一些最好的部分。與正規整數一樣，二進位字段元素是無界的：你可以隨意擴展。但就像模運算一樣，如果你在一定的大小限制內對值進行運算，你所有的結果也會保持在相同的範圍內。例如，如果取42 連續冪，則得到：

255 步驟之後，你就回到42 的255 次方=1，就像正整數和模運算一樣，它們遵循通常的數學定律：a*b=b*a、a*(b+c)=a*b+a* c，甚至還有一些奇怪的新法律。

最後，二進位欄位可以方便地處理bit：如果你用適合2 的k 次方的數字做數學運算，那麼你所有的輸出也將適合2 的k 次方bit。這避免了尷尬。在以太坊的EIP-4844 中，一個blob 的各個「區塊」必須是數位模5243587517512619047944774050818596583769055250052763782260365837690552500527637822603658696938691931378226036檢查，以確保每個元素儲存的值小於2 的248 次方。這也意味著二進位字段運算在電腦上是超級快速的——無論是 CPU，還是理論上最優的 FPGA 和 ASIC 設計。

這一切都意味著我們可以像上面所做的Reed-Solomon 編碼那樣做，以一種完全避免整數「爆炸」的方式，就像我們在我們的例子中所看到的那樣，並且以一種非常“原生”的方式，計算機擅長的那種計算。二進位欄位的「拆分」屬性－我們是如何做到的 1100101010001111=11001010+10001111*x3，然後根據我們的需求進行拆分，這對於實現很大的靈活性也是至關重要的。

完整的Binius

請參閱此處查看該協定的python 實作。

現在，我們可以進入「完整的Binius」，它將「簡單的Binius」調整為(i) 在二進位欄位上工作，(ii) 讓我們提交單一bit。這個協議很難理解，因為它在查看比特矩陣的不同方式之間來回切換；當然，我花了更長的時間來理解它，這比我通常理解加密協議所花的時間要長。但是一旦你理解了二進位字段，好消息是 Binius 所依賴的「更難的數學」就不存在了。這不是橢圓曲線配對，在橢圓曲線配對中有越來越深的代數幾何兔子洞要鑽；在這裡，你只需要二進位字段。

讓我們再看完整的圖表：

到目前為止，你應該熟悉了大多數元件。將超立方體「扁平化」成網格的思想，將行組合和列組合計算為評價點的張量積的思想，以及檢驗“Reed-Solomon 擴展再計算行組合”和“計算行組合再Reed- Solomon 擴展」之間的等價性的思想，都是在簡單的Binius 中實現的。

「完整的 Binius」有什麼新內容？基本上有三件事：

· 超立方體和正方形中的單一值必須是 bit(0 或 1)。

· 擴充過程透過將bit 分組為列並暫時假定它們是較大的欄位元素，將bit 擴展為更多的bit

· 在行組合步驟之後，有一個元素方面的「分解為bit」步驟，該步驟將擴充轉換回bit

我們將依序討論這兩種情況。首先，新的延期程序。 Reed-Solomon 程式碼有一個基本的限制，如果你要擴展 n 到 k*n，則需要在具有 k*n 不同值的欄位中工作，這些值可以用作座標。使用 F2（又稱 bit），你無法做到這一點。因此，我們所做的是，將相鄰 F2 的元素「打包」在一起形成更大的值。在這裡的範例中，我們一次將兩個 bit 打包到 {0，1，2，3} 元素中，因為我們的擴充只有四個計算點，所以這對我們來說已經足夠了。在“真實”證明中，我們可能一次返回 16 位。然後，我們對這些打包值執行 Reed-Solomon 程式碼，並再次將它們解壓縮為 bit。

現在，行組合。為了讓「在隨機點求值」檢查加密安全，我們需要從一個相當大的空間 ( 比超立方體本身大得多 ) 中對該點進行採樣。因此，雖然超立方體內的點是位，但超立方體外的計算值將會大得多。在上面的例子中，「行組合」最終是 [11,4,6,1]。

這就出現了一個問題：我們知道如何將bit 組合成一個更大的值，然後在此基礎上進行Reed-Solomon 擴展，但是如何對更大的值對做同樣的事情呢？

Binius 的技巧是按bit 處理：我們查看每個值的單一bit ( 例如：對於我們標為「11」的東西，即[1, 1,0,1] )，然後按行擴展。物件上執行擴充過程。也就是說，我們對每個元素的1 行執行擴展過程，然後在x0 行上，然後在“x1”行上，然後在x0x1 行上，依此類推（好吧，在我們的玩具示例中，我們停在那裡，但在實際實現中，我們將達到128 行（最後一個是x6*…*x0））

回顧：

· 我們把超立方體中的bit，轉換成一個網格

· 然後，我們將每行上的相鄰bit 群組視為更大的字段元素，並對它們進行算術運算以Reed-Solomon 擴展行

· 然後，我們取每列bit 的行組合，並獲得每一行的bit 列作為輸出( 對於大於4x4 的正方形，要小得多)

· 然後，我們把輸出看成一個矩陣，再把它的bit 當作行

為什麼會這樣呢？在「普通」數學中，如果你開始將一個數字按 bit 切片，( 通常 ) 以任意順序進行線性運算並得到相同結果的能力就會失效。例如，如果我從數字 345 開始，我把它乘以 8，然後乘以 3，我得到 8280，如果把這兩個運算反過來，我也得到 8280。但如果我在兩個步驟之間插入一個「按bit 分割」操作，它就會崩潰：如果你做8 倍，然後做3 倍，你會得到：

但是，如果你做3 倍，然後做8 倍，你會得到：

但在用塔結構建構的二進位場中，這種方法確實有效。原因在於它們的可分離性：如果你用一個大的值乘以一個小的值，在每個線段上發生的事情，會留在每個線段上。如果我們1100101010001111 乘以11，這和第一次分解1100101010001111 是一樣的，為

然後將每個分量分別乘以11 相同。

把它們放在一起

一般來說，零知識證明系統的工作原理是對多項式進行陳述，同時表示對底層評估的陳述：就像我們在斐波那契的例子中看到的那樣，F(X+2)-F(X+1)-F(X) = Z (X)*H(X) 同時檢查斐波那契計算的所有步驟。我們透過在隨機點證明求值來檢查關於多項式的陳述。這種隨機點的檢查代表整個多項式的檢查：如果多項式方程式不匹配，則它在特定隨機座標處匹配的可能性很小。

在實務中，效率低下的一個主要原因是在實際程式中，我們處理的大多數數字都很小：for 迴圈中的索引、True /False 值、計數器和類似的東西。但是，當我們使用 Reed-Solomon 編碼「擴展」資料以使基於 Merkle 證明的檢查安全所需的冗餘時，大多數「額外」值最終會佔用欄位的整個大小，即使原始值很小。

為了解決這個問題，我們想讓這個場越小越好。 Plonky2 將我們從 256 位數字降至 64 位數字，然後 Plonky3 進一步降至 31 位。但即使這樣也不是最優的。使用二進位字段，我們可以處理單一 bit。這使得編碼「密集」：如果你的實際底層資料有 n 位，那麼你的編碼將有 n 位，擴展將有 8 * n 位，沒有額外的開銷。

現在，讓我們第三次看這張圖表：

在Binius 中，我們致力於一個多線性多項式：一個超立方體P(x0,x1,…xk)，其中單一評估P(0,0,0,0)，P( 0,0,0,1) 直到P(1,1,1,1), 保存我們關心的資料。為了證明某一點上的計算，我們將相同的數據「重新解釋」為一個平方。然後，我們擴展每一行，使用 Reed-Solomon 編碼，為隨機默克爾分支查詢提供安全所需的資料冗餘。然後我們計算行的隨機線性組合，設計係數，使新的組合行實際上包含我們關心的計算值。這個新建立的行 ( 被重新解釋為 128 行 bit) 和一些隨機選擇的帶有 Merkle 分支的列都被傳遞給驗證者。

然後，驗證器執行「擴展的行組合」( 或者更確切地說，是擴展的幾列) 和「行組合的擴展」，並驗證兩者是否匹配。然後計算一個列組合，並檢查它是否傳回證明者所聲明的值。這就是我們的證明系統 ( 或者更確切地說，多項式承諾方案，它是證明系統的關鍵組成部分 )。

我們還沒講到什麼？

· 有效的演算法來擴展行，這是實際提高驗證器計算效率所必需的。我們在二進位欄位上使用快速傅立葉變換，在這裡描述 ( 儘管確切的實現將有所不同，因為這篇文章使用了一個不基於遞歸擴展的效率較低的結構 )。

· 算術化。一元多項式很方便，因為您可以做一些事情，例如F(X+2)-F(X+1)-F(X) = Z(X)*H(X) 將計算中相鄰的步驟連結起來。在超立方體中，「下一步」的解釋遠不如「X+1」。你可以做 X+k，k 的冪，但是這種跳躍行為會犧牲 Binius 的許多關鍵優勢。 Binius 論文介紹了解決方案。參見第 4.3 節 )，但這本身就是一個「深兔子洞」。

· 如何安全地進行特定值檢查。斐波那契範例需要檢查關鍵邊界條件：F(0)=F(1)=1 和 F(100) 的值。但是對於「原始的」Binius，在已知的計算點進行檢查是不安全的。有一些相當簡單的方法可以將已知計算檢查轉換為未知計算檢查，使用所謂的和檢查協議；但是我們這裡沒有講到這些。

· 查找協議，這是另一項最近被廣泛使用的技術，它被用來製作超高效的證明系統。 Binius 可以與許多應用程式的查找協定結合使用。

· 超越平方根驗證時間。平方根是昂貴的：bit 的 Binius 證明 2 的 32 次方大約 11MB 長。你可以使用其他證明系統來彌補這個問題，以製作「Binius 證明的證明」，從而獲得 Binius 證明的效率和較小的證明大小。另一種選擇是更複雜的 FRI- binius 協議，它創建了一個多對數大小的證明 ( 就像普通的 FRI)。

· Binius 是如何影響「SNARK 友善」的。基本的總結是，如果你使用Binius，你不再需要關心如何使計算“算術友好”：“常規”哈希不再比傳統的算術哈希更有效率，乘法模2 的32 次方或模2的256 次方與乘法模相比不再是一件令人頭痛的事情，等等。但這是一個複雜的話題。當一切都以二進制形式完成時，很多事情都會改變。

我希望在未來的幾個月裡，基於二進位欄位的證明技術會有更多的改進。

原文連結

欢迎加入律动 BlockBeats 官方社群：

Telegram 订阅群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方账号：https://twitter.com/BlockBeatsAsia