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

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

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

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

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

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

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

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

預備知識

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

與默克爾樹的對比

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

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

微軟與Aptos達成合作，將探索數字支付和代幣化:8月9日消息，Aptos Labs宣布與科技巨頭微軟建立新的合作伙伴關系。除了雙方探索與資產代幣化、數字支付和央行數字貨幣相關的“創新解決方案”外，Aptos還將利用微軟的Azure OpenAI服務。

兩家公司在一份聲明中表示，在一開始，雙方的合作似乎主要集中在利用微軟的人工智能能力來簡化用戶登錄Web3的過程，并幫助“開發人員構建智能合約和去中心化應用程序”。[2023/8/9 21:34:42]

實際上，我們可以通過默克爾樹得出多項式承諾：次數為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等零知識證明系統，也使之可以作為向量承諾適用于一般情況。下文將予以詳述。

TradFi：比特幣和恒生指數出現漲勢停滯可能意味著更大范圍的避險情緒:金色財經報道，TradFi公司表示，比特幣一個月前開始的上漲在本周遇到了瓶頸，上漲勢頭在關鍵技術阻力位附近失去了動力。香港基準股指恒生指數也出現了類似的情況。Spectra Markets的交易員兼總裁Brent Donnelly在周一晚些時候發給客戶的一份報告中說，比特幣和恒生指數的失敗是技術警告，表明2023年初的寧靜可能不會持續一整年。

Donnelly的言論證明，比特幣在經驗豐富的交易員中作為風險情緒先期指標的信譽正在增強。過去，比特幣在主要頂部和底部領先了標普500指數幾周。

比特幣周一跌幅接近4%，從2.4萬美元開始下跌。去年8月在24000美元上方也出現過類似的沖擊失敗。恒生指數也從阻力位轉低，阻力位可以追溯到2022年6月。[2023/2/1 11:41:20]

橢圓曲線與配對

如上所述，本人強烈推薦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，需要所有的計算機聯手才能做到。

Genesis提交第11章破產申請文件，資產和負債估計在10億至100億美元之間:1月20日消息，Genesis向紐約南區美國破產法院提交Chapter 11破產申請文件，Genesis列出的資產和負債估計在10億至100億美元之間。Genesis表示，將由委員會監督重組的所有方面，現有手頭現金超過1.5億美元。貸款業務的新貸款發放仍處于停滯狀態。[2023/1/20 11:22:42]

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

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

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

有趣的是，幾乎每個人都能使用這種可信設置在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

數據：超過10年未活躍的比特幣供應量創歷史新高:金色財經報道，Glassnode數據顯示，超過10年未活躍的比特幣供應量達到2,520,888.300枚，創歷史新高。[2022/9/25 7:19:41]

由于驗證人不知道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。概率極低。這其實就意味著攻擊者無法實現其意圖。

多項式相乘

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

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

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

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

韓國廣播電視臺MBC與The Sandbox達成合作伙伴關系:金色財經報道，近日，韓國廣播電視臺MBC（Munhwa Broadcasting Corporation）已與元宇宙游戲平臺The Sandbox達成業務合作伙伴關系。據悉，MBC將在虛擬空間上創建其Sangam辦公樓和制作工作室，并為The Sandbox用戶提供其他元宇宙原創內容。（Forkast）[2022/9/5 13:09:20]

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

現在要證明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：KATBINbinanceNCEkat幣行情RobinHoodProtocolBinance Multi-Chain CapitalKohima Finance

LTC