比特幣價格 比特幣價格
Ctrl+D 比特幣價格
ads
首頁 > 酷幣 > Info

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

Author:

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

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

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

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

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

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

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

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

預備知識

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

與默克爾樹的對比

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

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

數據:StarkNet橋接TVL突破20萬枚ETH:金色財經報道,據 Dune Analytics 最新數據顯示,以太坊 Layer 2 擴容解決方案 StarkNet 橋接存儲總價值 TVL 已突破 20 萬枚 ETH,本文撰寫時達到 201,318 ETH,按照當前價格計算約合 3.7 億美元。[2023/8/11 16:19:58]

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

Zcash推出V5.5.0版本,引入按比例收費機制:4月28日消息,據官方博客。加密隱私貨幣協議Zcash推出V5.5.0版本,該版本進行了多個漏洞修復,并引入按比例收費機制,可能有助于解決未來區塊鏈上高交易負載的問題。此外,該版本為下一版本的資金可用性功能奠定了基礎。[2023/4/28 14:32:16]

橢圓曲線與配對

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

Starknet生態衍生品協議ZKX新測試網Polaris:4月25日消息,基于 Starknet 的去中心化衍生品交易協議 ZKX 宣布發布新版測試網 Polaris,該版本添加了一個做市機器人來加快訂單執行,并添加資金費率功能來維護平臺穩定性。[2023/4/25 14:25:45]

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

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

Chiliz創始人發推稱Chiliz將獲新生,或暗示Chiliz 2.0即將推出:2月7日,體育和娛樂公鏈Chiliz創始人Alexandre Dreyful在社交平臺上發表推文,明天將是你余生的第一天@Chiliz,社區認為此條推文或暗示CHZ 2.0智能鏈即將推出。[2023/2/7 11:52:55]

多項式相乘

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

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

Robinhood和Coinbase盤前分別跌3.31%和8.85%。:金色財經消息,美股經紀商Robinhood和加密貨幣交易所Coinbase盤前分別跌3.31%和8.85%。[2022/6/22 1:24:34]

即等同于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:KATBINNANANCKATANA幣UBIN價格NanjcoinPera Finance

酷幣
DOT:波卡生態專區重磅上線,參與交易享雙重好禮_OCEANS

親愛的用戶: DigiFinex將于2020年12月12日18:00(GMT8)上線波卡生態專區,并上線DOT、KSM、CELR、DOCK、OCEAN及ANKR首批波卡生態代幣.

1900/1/1 0:00:00
比特幣:財哥談幣:此時不多更待何時 六百點利潤等你拿_DEFI

市場雖然繼續下探,但是遇到資金大量買入,下跌幅度不會太大,今天早上,主流幣開始試探性止跌反彈。市場依然是那個市場,比特幣還是那個比特幣,無論他怎么走都沒有改變基礎.

1900/1/1 0:00:00
GAT:Gate.io 已發充值TRU領超級空投福利活動獎勵公告_gate.io怎么下載

Gate.io充值TRU領超級空投福利活動已圓滿結束,根據活動規則,我們已為符合規則的用戶發放了活動獎勵。用戶可進入“賬戶管理—我的資金—賬單明細”查詢獎勵發放情況.

1900/1/1 0:00:00
比特幣:現在用3.8萬元就可以獲得一枚價值12萬的比特幣_LibraFace

1、直接購買當然可以,就算20000美金的價格也可以,但首先你得拿得住,俗話說守幣如守寡。在比特幣大漲大跌面前面不改色心如止水的人恐怕不多.

1900/1/1 0:00:00
比特幣:分析:機構投資者的興趣增加,比特幣價格一度逼近1.9萬美元_DOS

比特幣價格今天一度逼近1.9萬美元,而此時機構投資者對比特幣的興趣越來越大。比特幣在過去幾周的大部分時間里都在1.8萬美元至2萬美元之間波動,最近一次反彈發生在比特幣昨日跌破1.76萬美元之后,

1900/1/1 0:00:00
BTC:人氣紅人!紅包邀請好友,參與瓜分10000枚USDHK!_SIG

尊敬的用戶: 為歡迎更多用戶加入HKEx.one大家庭,“人氣紅人!紅包邀請好友”將火熱展開!詳情如下:活動時間:2020年12月10日24:00-2020年12月16日24:00分析 | BT.

1900/1/1 0:00:00
ads