他山之石 | 技術解讀實現無狀態版以太坊的「Kate 多項式承諾」_KAT

技術的突破是推動區塊鏈行業前進的引擎，幣安中國區塊鏈研究院與鏈聞ChainNews同為密切關注區塊鏈與密碼學等領域技術發展前沿的組織，故而聯合推出「他山之石」專欄，向中文世界讀者介紹全球范圍最值得關注的區塊鏈技術進展，以及在金融等產業最新的應用分析與動態，以期為中國的區塊鏈行業「攻玉」提供借鑒和思考。

本文從技術視角介紹一種「Kate多項式承諾」的密碼學方案，此方案正用于研究實現無狀態以太坊。

原文標題：《Kate多項式承諾》撰文：DankradFeist，以太坊基金會研究員編譯：幣安中國區塊鏈研究院

本文已取得作者授權，并由鏈聞和幣安中國區塊鏈研究院獲得中文地區翻譯首發權

在本文擬介紹Kate、Zaverucha和Goldberg所提出的承諾方案1。但作為一篇介紹性文章，本文無意做嚴謹、完整的數學或密碼學論述。

該方案通常被稱作「Kate多項式承諾方案」，是多項式承諾方案的一種。它支持驗證人計算對多項式的承諾，可通過其屬性在任意后續位置開啟此承諾：驗證人需要證明多項式在某位置上的值均等于聲明值。

驗證人一旦將承諾值發給了校驗人，便無法再更改相應的多項式，因此得名「承諾」。校驗人只能提供多項式的有效證明；若嘗試作弊，要么無法得出證明，要么證明會被校驗人拒絕。

預備知識

強烈推薦不熟悉有限域、橢圓曲線與配對的讀者提前閱讀VitalikButerin有關橢圓曲線配對的文章。

與默克爾樹的對比

若讀者熟悉默克爾樹，本人希望可以更直觀地呈現默克爾樹與Kate承諾之間的差別。用密碼學家的話來說，默克爾樹是一種向量承諾：你可以使用一個深度為d的默克爾樹，計算出對向量

的承諾。你也可以運用默克爾證明，借助d散列，證明位于i處的元素ai是該向量的一部分。

律師：SEC主席或成為SBF案件的證人:金色財經報道，美國律師MetaLawMan在其推文中表示，美國司法部針對SBF的新起訴書稱，SBF游說國會議員和其他高級政府官員促進加密貨幣監管，這有利于他的商業和個人利益，這或許會讓SEC主席Gary Gensler成為該案的證人，這意味著SBF的律師將能夠在審判時對Gensler進行盤問。[2023/8/15 21:23:47]

實際上，我們可以通過默克爾樹得出多項式承諾：次數為n的多項式p(X)只是一個函數

其中pi是多項式的系數。

通過設置ai=pi并計算其系數的默克爾根，可以很容易地得出次數為n=2d-1時的多項式。證明求值指的是驗證人想要告訴校驗人：對于某個z，p(z)=y。對此，驗證人可以把所有的pi值都發給校驗人，然后校驗人計算得出p(z)確實等于y。

當然，這是一個非常低級的多項式承諾，但能幫助我們理解其具有哪些優勢。觀察下面這些屬性：

1.承諾大小是一個單散列。一個足夠安全的加密散列通常需要256個位元，即32個字節。2.要想證明一個求值，驗證人需要把所有的pi發出去，以此證明大小與多項式的次數呈線性關系，校驗人需要進行線性運算（通過計算

求出多項式在位置z處的值）。

3.此方案未對多項式進行隱藏——驗證人以非隱藏方式發送完整的多項式，及其每一個系數。

下面，我們探討一下Kate方案以此類指標可以實現怎樣的效果。

承諾大小是一個橢圓群的群元素，該群支持配對。例如，BLS12_381有48個字節。證明大小不受多項式大小的影響，也是一個群元素。校驗多項式次數和大小的影響，始終需要一次兩群相乘和兩輛配對。該方案基本實現了對多項式隱藏——實際上，將會出現無數多項式Kate承諾完全相同的情況。但是，完全隱藏仍未實現：如能猜出多項式，就能找出承諾多項式。另外，也可以把任意求值的證明合并到一個群元素中。正是這些屬性使Kate方案通行于PLONK、SONIC等零知識證明系統，也使之可以作為向量承諾適用于一般情況。下文將予以詳述。

Bitwise申請將其比特幣期貨ETF修改為比特幣+以太坊等權重策略ETF:金色財經報道，彭博分析師James Seyffart發布推文稱，Bitwise剛剛提交了更新的招股說明書，將其BITC從比特幣期貨ETF更改為“Bitwise 比特幣和以太坊等權重策略 ETF”，生效日期為2023年10月9日。

金色財經此前報道，Valkyrie也將以太坊期貨納入其比特幣期貨ETF。[2023/8/11 16:19:08]

橢圓曲線與配對

如上所述，本人強烈推薦VitalikButerin有關橢圓曲線配對的文章，其中介紹了理解本文所需的所有預備知識，尤其是有限域、橢圓曲線與配對等方面。

假設G1和G2為帶有配對e的兩條橢圓曲線：G1×G2→GT。G1和G2的階數均為p，生成元分別為G和H。用簡化符號分別記作

1=xG∈G1和2=xH∈G2

任意x∈Fp。

可信設置

假設完成了可信設置，則在某個秘密點s上，驗證人和校驗人均能獲得i=0、……n-1時的1和2元素。

你可以這樣理解這種秘密設置：用一臺氣隙計算機計算隨機數s，計算所有的群元素x，然后用有線方式只把這些元素發出去，最后把這臺計算機銷毀。當然，這種方案不夠完美，因為你必須信任計算機操作員不會通過秘密通信通道獲取到秘密點s的值。

在實踐中，這通常是通過安全的多方計算來實現的，此方法允許由一組計算機創建此類群元素，從而杜絕任何計算機獲取秘密點s的值，而要想獲取到s，需要所有的計算機聯手才能做到。

注意，不會出現以下情況：即僅通過選擇某個隨機群元素1，計算出其他的群元素，最后得出s。在s未知的情況下，無法計算出1。

現在，橢圓曲線加密基本上說明了不可能通過可信設置的群元素得出s的實際值。s是Fp中的一個數，但是驗證人不可能找出這個數的實際值。驗證人只能根據提供給他們的元素執行特定的計算。因此，驗證人可以通過橢圓曲線乘法運算，很容易地計算出c1=csiG=1等，且由于可以加上橢圓曲線點，還可以計算出c1d1=(csidsj)G=1等。實際上，如果

幣安將上線GAS/USDT、GLM/USDT等多個交易對:金色財經報道，幣安將于2023年03月17日16:00（東八區時間）上線GAS/USDT、GLM/USDT、PROM/USDT、QKC/USDT、UFT/USDT交易對。[2023/3/16 13:07:28]

是多項式，驗證人可以計算出：

有趣的是，幾乎每個人都能使用這種可信設置在s未知的情況下，求出多項式在秘密點s處的值。除非他們沒有得到自然數輸出，而是只得到橢圓曲線點1=p(s)G，但是這就已經非常強大了。

Kate承諾

在Kate承諾方案中，元素C=1是對多項式p(X)的承諾。

或許你會問：驗證人能否找到另一個具有相同承諾的多項式q(X)≠p(X)，即1=1？假設存在這種情況。那將意味著1=1，說明p(s)-q(s)=0。

現在，r(X)=p(X)-q(X)本身就是一個多項式。我們知道因為p(X)≠q(X)，所以其并非常數。眾所周知，任何次數為n的非常數多項式最多可以有n個零：因為如果r(z)=0，則r(X)可被線性因子X-z整除；因為我們可以將每個零除以一個線性因子，并且每除一次會使次數減一，所以次數不會超過n。^2

由于驗證人不知道s，因此實現p(s)-q(s)=0的唯一方法是在盡可能多的位置上實現p(X)-q(X)=0。但是，正如以上證明，由于驗證人最多可以選n個位置，所以成功的可能性不高：由于n值遠小于曲線p的次數，因此他們不太可能選擇s點來使p(X)=q(X)。為了感受此概率，假設采用當前可實現的最大可信設置，其中n=228，并將其與曲線階數p≈2^256進行比較：即便攻擊者通過精心設計，使多項式q(X)在最多n=228個點上等于p(X)，使這個多項式得出相同承諾的概率也只有228/2256=2^28-2^56≈2·10-69。概率極低。這其實就意味著攻擊者無法實現其意圖。

Moneyfellows宣布完成3100萬美元B輪融資:金色財經報道，埃及金融科技初創公司Moneyfellows宣布已從由Commerz Ventures、中東風險投資伙伴 (MEVP) 和 Arzan Venture Capital 牽頭的 B 輪融資中籌集了 3100 萬美元。參與這輪融資的還有這家初創公司的現有投資者，如Partech、Sawari Ventures、4DX Ventures 和 P1 Ventures。[2022/11/10 12:44:05]

多項式相乘

到現在，我們已經證明了能夠求出多項式在秘密點s處的值，這使得我們能夠對一個唯一的多項式做出承諾——在某種意義上，盡管具有相同承諾C=1的多項式不止一個，但在實際中是無法計算出來的）。

不過，在不將多項式完整地發送給校驗人的情況下，我們仍無法「開啟」承諾。而要「開啟」承諾，我們需要用到配對。如上所述，我們可以用秘密元素進行某些線性運算；例如，我們可以把1計算為對p(X)的承諾，也可以把p(X)和q(X)的兩個承諾相加，得出合并承諾p(X)q(X)：11=1。

現在我們無法將兩個多項式相乘。否則，就能使用多項式的某些屬性實現目標。盡管橢圓曲線本身做不到，但所幸，我們可以通過配對來實現：我們知道：

其中引入了新符號T=e(G,H)x。因此，雖然我們不能把橢圓曲線里的兩個域元素簡單地相乘，然后將其乘積當作一個橢圓曲線元素的屬性之一；而橢圓形曲線僅是加法同態的），但是，如果在兩個不同的曲線中對它們進行承諾，并且輸出是一個G元素的話，我們就能把兩個域元素相乘。

這時就觸及到了Kate證明的核心：還記得我們之前提到了線性因子么：如果多項式在z處為零，則多項式可被X-z整除。顯然，反過來也是如此——如果多項式可被X-z整除，那么多項式在z處顯然為零：被Xz整除意味著：我們可以得出某些多項式q(X)的p(X)=(X-z)-q(X)，且多項式在X=z處顯然為零。

KKR沒有計劃牽頭競購東芝 可能會成為投資人:7月19日消息，據外媒報道，KKR＆Co不打算在這個時候牽頭競購東芝。據兩位知情人士稱，KKR仍可能作為股權合作伙伴參與一項交易。此前消息，Dragonfly Capital宣布已為旗下第三支加密基金籌集6.5億美元，KKR為投資人。（財聯社）[2022/7/19 2:23:25]

現在要證明p(z)=y。我們接著使用多項式p(X)-y——由于該多項式在z處顯然為零，因此我們可以運用線性因子的相關知識。使q(X)等于多項式p(X)-y，被線性因子X-z整除，即

即等同于q(X)(X-z)=p(X)-y。

Kate證明

現在，將p(z)=y求值的Kate證明定義為π=1。對多項式p(X)的承諾被定義為C=1。

校驗人使用以下公式檢查此證明：

注意，校驗人可以計算出2，因為2只是來自可信設置的元素2與z的組合，且z是多項式的求值點。同樣，把y當作聲明值p(z)，便可以計算出1。那么，為什么此檢查能使校驗人相信p(z)=y；更準確地說，是使校驗人相信由C所承諾的多項式在z處求出的值為y？

我們需要評估兩個屬性：正確性和可靠性。正確性指驗證人執行我們定義的步驟，可以得出能通過核驗的證明。這一點一般不難。可靠性指校驗人無法得出「不正確」的證明，即無法使校驗人相信當y'≠y時，p(z)=y′。

首先，寫出配對群中的方程式：

其正確性現在應該很明顯了，即在未知隨機點s上需要求值的方程q(X)(X-z)=p(X)-y。

那么，我們怎么證明其可靠性以及驗證人無法創建假證明呢？我們要用多項式思路來思考這個問題。如果驗證人按我們的方法來構造證明，就必須以某種方式使p(X)-y′被X-z整除。但是p(z)-y′不為零，因此無法進行多項式除法運算，因為總會有余數。所以，這種方法顯然行不通。

至此，就要嘗試橢圓群：如果能計算出某些承諾C的橢圓群元素，結果又會怎樣？

很顯然，如果做到了這一點，就能證明一切。憑直覺來看，這一點很難實現，因為必須將與s相關的某些值指數化，但是s是未知的。出于證明的周密性考慮，需要提出配對的密碼學假設，即所謂的q-SDH假設3。

多值證明

現在，我們已經演示了如何證明多項式在一個點上的求值。注意，這已經非常了不起了：通過僅發送一個單群元素，就能證明某個具有任意個次數的多項式在某個點上包含了某個值。在將默克爾樹當作多項式承諾的小例子中，需要發送228個元素——多項式的所有系數。

現在，我們要更進一步，證明可以在任意數量的點上求出多項式的值，且仍然只使用一個群元素即可。為此，我們需要引入另一個概念：插值多項式。假設有一系列的k值(z0,y0)、(z1,y1)……(zk-1,yk-1)：然后，總是能找到一個次數小于k的多項式能通過所有這些點。實現方法之一是使用拉格朗日插值法，此方法為該多項式I(X)提供了一個明確的公式：

現在，假設已知p(X)通過了所有點。則多項式p(X)-I(X)在z0、z1……、zk-1處均明顯為零。這意味著它可以被所有線性因子、……整除。我們把所有因子都合并到所謂的零多項式中

就可以計算商數了

注意，這是可行的，因為p(X)-I(X)可被Z(X)中的所有線性因子整除，因此它可被整個Z(X)整除。

我們現在可以給求值(z0,y0)、(z1,y1)……(zk-1,yk-1)：π=1定義Kate多值證明——注意，這里仍然只有一個群元素。

現在，要進行檢查，校驗人還必須計算插值多項式I(X)和零多項式Z(X)。借此，他們可以計算2和1，從而校驗配對方程式

通過寫出配對群中的方程，可以輕松地校驗其能否以與單點Kate證明相同的方式進行驗證：

其效果驚人：只需提供一個群元素，就可以證明任何數量的求值達一百萬次！僅48字節即可證明所有求值！

用作向量承諾的Kate承諾

雖然Kate承諾方案被設計成了一種多項式承諾，但實際上也能成為非常好的向量承諾。向量承諾對向量a0……an-1進行承諾，為證明自己對某個i承諾了ai提供了方法。可以使用Kate承諾方案來進行重現：使p(X)為所有i均取為p(i)=ai的多項式。我們現在得到了這樣一個多項式，可以用拉格朗日插值法來計算它：

利用這個多項式，我們可以僅使用一個群元素就能證明向量中任意數量的元素！這種方法的效率要比默克爾樹高得多：僅證明一個元素，一次默克爾證明會消耗logn個散列！

延伸閱讀

我們目前正在研究如何利用Kate承諾打造出無狀態版的以太坊。因此，本人強烈建議在ethresearch論壇中搜索Kate，查找與當前研究相關的話題。

除本文外，Vitalik對PLONK的介紹也非常精彩，其中大量使用了多項式承諾，并采用了Kate方案作為主要示例。

1.https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

2.此結果常被錯誤地引用做代數基本定理。而代數基本定理剛好相反，在復雜的數值中，每一個次數為n的多項式都有n個線性因子。但是，盡管此處簡化結果對于代數學有重要意義，但還缺少一個簡潔、朗朗上口的名稱。

3.https://www.cs.cmu.edu/~goyal/ibe.pdf

來源鏈接：dankradfeist.de

免責聲明：作為區塊鏈信息平臺，本站所發布文章僅代表作者個人觀點，與鏈聞ChainNews立場無關。文章內的信息、意見等均僅供參考，并非作為或被視為實際投資建議。

幣安

幣安

幣安Binance區塊鏈數字資產交易平臺，引領幣幣交易創新模式，為用戶提供更加安全、便捷的數字貨幣兌換服務，聚合全球優質數字貨幣，致力于打造世界級的區塊鏈資產交易平臺。提供比特幣、以太坊、萊特幣、幣安幣等主流加密數字貨幣交易。公司幾乎所有的資產，包括對于交易收取的費用及拿到的融資，都以加密數字貨幣形式保存。幣安BinanceBNBBinanceChainBinanceLabsBinanceLabs幣安慈善幣安慈善基金會幣安孵化器BinanceDEX幣安寶幣安研報幣安研究院BinanceResearch幣安美國BinanceFuturesBinanceLaunchpad幣安云BinanceCloudBinanceCardBinance.US幣安Launchpad幣安LaunchpoolBinancePay查看更多以太坊

Tags：KATANCbinanceNANKATSGravis FinanceBinancedoglafifinance

ETH