原文标題：Binius： highly efficient proofs over binary fields
原文作者：Vitalik
原文來源：vitalik.eth.limo
編譯：Kate, 火星财經
這篇文章主要針對大緻熟悉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小時是幾點？但在這裡，我們不隻是對某個數進行加、減模，我們還可以進行乘、除和取指數。
我們重新定義：
以上規則都是自洽的。例如，如果p=7，那麼：
5+3=1（因為8%7=1）
1-3=5（因為-2%7=5）
2*5=3
3/5=2
這種結構的更通用術語是有限域。有限域是一種數學結構，它遵循通常的算術法則，但其中可能的值數量有限，是以每個值都可以用固定的大小表示。
模運算(或質數域)是有限域最常見的類型，但也有另一種類型：擴充域。你可能已經見過一個擴充字段：複數。我們“想象”一個新元素，并給它貼上标簽i，并用它進行數學運算：（3i+2）*（2i+4）=6i*i+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曲線為21888242871839275222246405745257275088548364400416034343698204186575808495617。但實際的計算使用的是小數字：如果你用你最喜歡的語言來考慮一個“真正的”程式，它使用的大部分東西是計數器，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的各個“塊”必須是數字模52435875175126190479447740508185965837690552500527637822603658699938581184513，是以編碼二進制資料需要扔掉一些空間，并在應用層進行額外的檢查，以確定每個元素存儲的值小于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次方 與乘法模相比不再是一件令人頭疼的事情，等等。但這是一個複雜的話題。當一切都以二進制形式完成時，很多事情都會發生變化。
我希望在未來的幾個月裡，基于二進制字段的證明技術會有更多的改進。