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

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

原文標題:《【他山之石】Kate 多項式承諾(polynomial commitments)
撰文:Dankrad Feist,以太坊基金會研究員
編譯:幣安中國區塊鏈研究院

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

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

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

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

預備知識

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

與默克爾樹(Merkle tree)的對比

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

(即一系列固定長度的元素)的承諾。你也可以運用默克爾證明,藉助 d 散列,證明位於 i 處的元素 ai 是該向量的一部分。

實際上,我們可以通過默克爾樹得出多項式承諾:次數爲 n 的多項式 p(X) 只是一個函數
他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

其中 pi 是多項式的係數。

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

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

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

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

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

  1. 承諾大小是一個橢圓羣的羣元素,該羣支持配對。例如,BLS12_381 有 48 個字節。
  2. 證明大小不受多項式大小的影響,也是一個羣元素。校驗多項式次數和大小的影響,始終需要一次兩羣相乘和兩輛配對。
  3. 該方案基本實現了對多項式隱藏——實際上,將會出現無數多項式 Kate 承諾完全相同的情況。但是,完全隱藏仍未實現:如能猜出多項式(例如,當多項式很簡單或只有幾組可能的多項式時),就能找出承諾多項式。

另外,也可以把任意求值的證明合併到一個羣元素中。正是這些屬性使 Kate 方案通行於 PLONK、SONIC 等零知識證明系統,也使之可以作爲向量承諾適用於一般情況。下文將予以詳述。

橢圓曲線與配對

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

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

[x]1=xG∈G1 和 [x]2=xH∈G2

任意 x∈Fp。

可信設置(Trusted setup)

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

你可以這樣理解這種祕密設置:用一臺氣隙計算機(airgapped computer)計算隨機數 s,計算所有的羣元素 [si]x,然後用有線方式只把這些元素髮出去(不發送 s),最後把這臺計算機銷燬。當然,這種方案不夠完美,因爲你必須信任計算機操作員不會通過祕密通信通道獲取到祕密點 s 的值。

在實踐中,這通常是通過安全的多方計算(MPC)來實現的,此方法允許由一組計算機創建此類羣元素,從而杜絕任何計算機獲取祕密點 s 的值,而要想獲取到 s,需要所有的計算機聯手(或同時被攻破)才能做到。

注意,不會出現以下情況:即僅通過選擇某個隨機羣元素 [s]1 (其 s 未知),計算出其他的羣元素,最後得出 s。在 s 未知的情況下,無法計算出 [s2]1。

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

Kate 承諾

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

或許你會問:(在 s 未知的情況下)驗證人能否找到另一個具有相同承諾的多項式 q(X) ≠ p(X),即 [p(s)]1=[q(s)]1?假設存在這種情況。那將意味着 [p(s)-q(s)]1=[0]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),使這個多項式得出相同承諾(p(s) = q(s))的概率也只有 228/2256 = 2^28-2^56 ≈ 2·10-69。概率極低。這其實就意味着攻擊者無法實現其意圖。

多項式相乘

到現在,我們已經證明了能夠求出多項式在祕密點 s 處的值,這使得我們能夠對一個唯一的多項式做出承諾——在某種意義上,儘管具有相同承諾 C=[p(s)]1 的多項式不止一個,但在實際中是無法計算出來的(密碼學家稱之爲計算綁定(computationally binding))。

不過,在不將多項式完整地發送給校驗人的情況下,我們仍無法「開啓」承諾。而要「開啓」承諾,我們需要用到配對。如上所述,我們可以用祕密元素進行某些線性運算;例如,我們可以把 [p(s)]1 計算爲對 p(X) 的承諾,也可以把 p(X) 和 q(X) 的兩個承諾相加,得出合併承諾 p(X)+q(X):[p(s)]1+[q(s)]1=[p(s)+q(s)]1。

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

其中引入了新符號 [x]T=e(G, H)x。因此,雖然我們不能把橢圓曲線裏的兩個域元素簡單地相乘,然後將其乘積當作一個橢圓曲線元素(這是所謂的全同態加密(FHE)的屬性之一;而橢圓形曲線僅是加法同態的),但是,如果在兩個不同的曲線中對它們(一個在 G1 中,一個在 G2 中)進行承諾,並且輸出是一個 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 整除,即

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

Kate 證明

現在,將 p(z)= y 求值的 Kate 證明定義爲π = [q(s)]1。對多項式 p(X) 的承諾被定義爲 C = [p(s)]1。

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

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

首先,寫出配對羣中的方程式:

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

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

至此,就要嘗試橢圓羣:如果能計算出某些承諾 C 的橢圓羣元素,結果又會怎樣?

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

多值證明(Multiproofs)

現在,我們已經演示瞭如何證明多項式在一個點上的求值。注意,這已經非常了不起了:通過僅發送一個單羣元素(例如,BLS12_381 中有 48 個字節),就能證明某個具有任意個次數(假設 228 個)的多項式在某個點上包含了某個值。在將默克爾樹當作多項式承諾的小例子中,需要發送 228 個元素——多項式的所有係數。

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

就可以計算商數了

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

我們現在可以給求值 (z0, y0)、(z1, y1)……(zk-1, yk-1):π=[q(s)]1 定義 Kate 多值證明——注意,這裏仍然只有一個羣元素。

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

通過寫出配對羣中的方程,可以輕鬆地校驗其能否以與單點 Kate 證明相同的方式進行驗證:

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

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

用作向量承諾的 Kate 承諾

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

他山之石 | 技術解讀 Kate 多項式承諾,與默克爾樹有何不同?

利用這個多項式,我們可以僅使用一個羣元素就能證明向量中任意數量的元素!(僅就證明大小而言)這種方法的效率要比默克爾樹高得多:僅證明一個元素,一次默克爾證明會消耗 log n 個散列!

延伸閱讀

我們目前正在研究如何利用 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