以太坊價格 以太坊價格
Ctrl+D 以太坊價格
ads
首頁 > 火幣APP > Info

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

Author:

Time:1900/1/1 0:00:00

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

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

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

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

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

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

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

預備知識

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

與默克爾樹的對比

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

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

安全監測:@Popcorn_DAO Discord 服務器遭攻擊:金色財經報道,據SharkTeam鏈上分析平臺 ChainAegis 安全監測顯示,@Popcorn_DAO Discord 服務器遭攻擊,正在發布虛假釣魚網站,請勿點擊發布的任何鏈接直至團隊修復以免造成損失。[2023/6/21 21:52:20]

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

加密交易所Bullish取消了90億美元的SPAC計劃:金色財經報道,Peter Thiel支持的加密貨幣交易所Bullish和特殊目的收購公司 (SPAC) Far Peak Acquisition Corporation 已共同同意取消他們計劃中的合并。?2021 年 7 月,Far Peak 和 Bullish同意合并,該加密貨幣交易所將在紐約證券交易所 (NYSE) 公開交易。[2022/12/23 22:04:00]

橢圓曲線與配對

如上所述,本人強烈推薦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等。實際上,如果

加拿大國有電力供應商BC Hydro將暫停向還未接入的比特幣礦場供電:12月23日消息,加拿大不列顛哥倫比亞省國有電力供應商BC Hydro將暫停向還未接入以及處于接入早期的比特幣礦場供電18個月的時間。BC Hydro表示,加密貨幣挖礦會消耗大量的電力但并未創造很多的就業機會。[2022/12/23 22:03:17]

是多項式,驗證人可以計算出:

有趣的是,幾乎每個人都能使用這種可信設置在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。概率極低。這其實就意味著攻擊者無法實現其意圖。

ENS DAO正在投票以選出三個工作小組的管理員:金色財經報道,ENS DAO目前正在投票以選出明年將領導meta治理、ENS生態系統和公共產品三個工作組的管理員。meta治理工作組負責監督DAO治理事務;ENS生態系統工作組側重于支持與項目相關的用戶和組織;公共產品工作組專門資助ENS和更廣泛的web3生態系統中的項目。(The Block)[2022/12/13 21:40:11]

多項式相乘

到現在,我們已經證明了能夠求出多項式在秘密點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處顯然為零。

Optimism社區發起向Curve流動池分配100萬枚OP代幣的提案:7月25日消息,以太坊二層擴容網絡Optimism社區成員發起提案,計劃向Curve的sUSD、sETH、sBTC池按比例分配100萬枚OP代幣,其中每周5萬枚,共分發20周。據悉,在每周分配的5萬枚OP中,25,000OP用于sUSD池,15,000OP用于sETH池,10,000OP用于sBTC池。[2022/7/25 2:35:28]

現在要證明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:KATbinanceBINNANKATANA幣binance-coinY2B Finance

火幣APP
EFI:鏈上無抵押借貸協議 TrueFi 完成首筆借貸還款,SBF 為首位借款人

鏈聞消息,鏈上無抵押借貸協議TrueFi上首個借款人已在14天內完成還款,借出的500萬美元共產生約1.9萬美元利息收入,FTX創始人SamBankman-Fried為首位借款人.

1900/1/1 0:00:00
NOS:ETC 硬分叉引發礦工熱潮的價值邏輯

導語: 11月29日,ETC主網達到區塊高度11700000,正式激活Thanos硬分叉升級。此次升級通過Thanos協議部署,恢復3GB和4GBGPU礦工挖礦權限.

1900/1/1 0:00:00
NCE:分析師:明年看好的項目包括Black Hole Swap和Perpetual Protocol

加密分析師TylerSwope表示,一些自動做市商將于2021年在DeFi領域取得成功。Swope稱,盡管比特幣經歷了回調,他正在跟蹤在過去30天里蓬勃發展的兩個DeFi平臺.

1900/1/1 0:00:00
DEF:DeFi流動性挖礦項目大盤點,CellETF有哪些核心優勢?

從今年6月中旬Compound點燃“流動性挖礦”火焰開始,sushiswap、yearnfinance接力,DeFi板塊持續火爆。現在三天一個新項目已經是DeFi的常態了.

1900/1/1 0:00:00
DEC:談喻凱:比特幣強勢反抽劍指2萬關口 門羅幣以太坊多頭紛紛跟隨

投資千萬條,風險第一條;策略千百種,哪個適合我;思路沒跟上,踏空兩行淚。關注談喻凱公眾號幣圈散戶聯盟,精選全球最準行情分析,消息面,技術面為你指引解讀,帶你把握行情,瞄準良機,穩健交易.

1900/1/1 0:00:00
UNI:用三國殺講分布式算法 太舒適了吧?

前言 《三國殺》是一款熱門的卡牌游戲,結合中國三國時期背景,以身份為線索,以卡牌為形式,益智休閑,老少皆宜。在講解之前,我們先聊下分布式協議和算法整體脈絡.

1900/1/1 0:00:00
ads