前言
您準備好探索 zk-SNARK 更復雜的一面了嗎?在上一節中,我們瞭解了一些更高級的概念,例如算術電路和二次算術程序。在本部分中,我們將通過深入研究另一個強大的概念來擴展我們的知識:橢圓曲線配對。
注意:對於許多人來說,深入理解橢圓曲線配對等主題有時可能具有挑戰性。然而,這就是我們寫這篇文章的原因——幫助您至少對此有一個基本的瞭解。
我的目標不僅是徹底解釋橢圓曲線配對,而且使該主題更有趣且更容易理解。希望通過本文,您將瞭解橢圓曲線對在數學和密碼學中的強大功能,以及它們在 zk-SNARK 中的具體應用。
橢圓曲線
橢圓曲線是橢圓曲線密碼學領域的一部分。這是一個複雜的課題,不是每個人都能輕易理解的。爲了更好地理解它們,請查看我之前關於 ECC 的文章。
橢圓曲線密碼學涉及二維空間中的“點”,每個“點”由一對座標 (x, y) 表徵。
執行點之間的加法和減法等數學運算有特定的規則,允許在已知其他點的情況下計算新點的座標。
示例:計算座標 R = P + Q
您還可以將點與整數相乘,方法是重複將點與自身相加,次數與該整數相同。
例如:P * n = P + P + … + P
這提供了一種在橢圓曲線加密中執行數學運算的有效方法
在橢圓曲線上,有一個特殊的點,稱爲“無窮遠點”(O),相當於點微積分中的零,P + O = P 始終成立。
曲線也有“階”;存在一個數字 n,對於所有 P,P * n = O(P * (n+1) = P、P * (7*n + 5) = P * 5,依此類推)。
還有一個“生成點”(G),可以理解爲以某種方式代表數字 1。理論上,曲線上的任何點(O 除外)都可以是 G。
搭配
配對可以對橢圓曲線點進行更復雜的方程測試。
例如:
您可以僅根據 P、Q 和 R 檢查 p * q 是否等於 r。
儘管有關 p 的信息可能會從 P 泄漏,但這種泄漏會受到仔細控制。
配對允許測試二次約束。
例如:測試 e(P, Q) * e(G, G * 5) = 1 實際上是測試 p * q + 5 = 0。
是一種稱爲配對的數學運算。數學家也稱其爲雙線性映射。 這裏的“雙線性”將遵守以下規則:
請注意,您可以以任何方式使用運算符 + 和 *,只要它們符合以下規則:
和
如果 P、Q、R 和 S 是簡單的數字,則使用以下表達式可以輕鬆創建簡單的配對操作:
結果如下:
這就是並行性!
然而,這種簡單的配對操作並不適合密碼學,因爲它們對簡單的整數進行操作並且太容易分析。
一旦您在執行配對操作時知道了一個號碼及其結果,您就可以輕鬆計算並找到剩餘的號碼。
我們使用像“黑匣子”這樣的數學運算,只能執行基本運算,而無需進一步分析或理解。這就是爲什麼橢圓曲線和橢圓曲線上的配對操作在密碼學中變得重要。
素數域和擴展域
可以在橢圓曲線點上創建雙線性映射(Bilinear Maps)——即創建一個函數
其中 P 和 Q 是橢圓曲線點,結果是稱爲 F_p^2 的元素類型
首先,我們來了解一下素域和擴展域。
上圖中的橢圓曲線之所以如此美麗,是因爲該曲線的方程是使用普通實數定義的。
然而,在密碼學中,使用普通實數可能會導致使用對數“倒退”,並把事情搞砸,因爲存儲和表示數字所需的空間量可以任意增加。因此,我們在素數字段中使用數字。
素數字段由數字 0、1、2…p-1 的集合組成,其中 p 是素數,各種運算定義如下:
所有運算均以 p 爲模進行
除法是一種特殊情況;通常,3/2 不是整數,現在我只想處理整數,所以我嘗試找到數字 x,這樣
x * 2 = 3。
這可以使用擴展歐幾里得算法來完成。例如,如果 p = 7,則:
接下來,我們將討論擴展字段。
您在數學書籍中經常遇到的一個常見示例是複數字段,其中實數字段通過附加元素 sqrt(-1) = i 進行“擴展”。
擴展字段的工作原理是採用現有字段,然後“添加”新元素並定義該新元素與原始字段中已有元素之間的關係(例如 i² + 1 = 0)。
重要的是這個方程對於原域中的任何數字都不成立,然後考慮原域中的元素和剛剛創建的新元素的所有線性組合。
我們還可以擴展素數字段
例如,用 i 擴展我們上面描述的素數域 mod 7,我們可以執行以下操作:
如果您想查看代碼中完成的所有數學運算,則可在此處完成主字段和字段擴展
橢圓曲線配對
橢圓曲線配對是一種從兩條橢圓曲線中獲取兩個點並將這些點映射爲單個數字的機制。
您可以將此映射視爲等效於橢圓曲線上的點相乘。
從數學上講,橢圓曲線配對定義爲將橢圓曲線上的兩個點映射到另一個組中的元素作爲有限域:
這裏 e 是配對,E1 和 E2 是橢圓曲線,𝐹 是有限域。
請注意,橢圓曲線 E1 和 E2 不需要不同。
一旦發生串聯,結果是另一個組中的元素無法在下一次串聯中重用。
橢圓曲線配對具有某些稱爲雙線性映射的屬性:
這裏 P、Q 和 R 是橢圓曲線上的點,𝑎ε𝑍、𝑏ε𝑍
使用這些“雙線性映射”,我們可以在這兩條曲線上“移動”係數 𝑎 和 𝑏,同時保持相同的映射:
來源:https://muens.io/elliptic-curve-pairing
我們可以將橢圓曲線配對想象爲 G2 x G1 -> Gt 的映射,其中:
G1 是一條橢圓曲線,其中點滿足形式方程
兩個座標都是 F_p 的元素(它們是簡單的數字,但運算是對特定素數取模)
G2 也是一條橢圓曲線,其中的點滿足與 G1 相同的方程,但它們的座標屬於域 F_p^2(我們定義一個新的“幻數”w,由 12 次多項式定義,如下所示:
Gt 是橢圓曲線結果所涉及的對象類型。在我們考慮的曲線中,Gt 是 F_p^2(與 G2 中使用的強複數相同)
這裏它必須滿足雙線性:
還有另外兩個重要標準:
高效的可計算性:高效的可計算性意味着能夠快速計算複合運算,而不會太複雜。例如,如果我們只取點的離散對數並將它們相乘以創建串聯,那麼這在計算上就會變得太困難,就像破解原始橢圓曲線密碼一樣。因此,如果可以有效地計算複合運算而不施加太多的計算負擔,則該複合運算被認爲是計算高效的。
非簡併性:非簡併性確保串聯不是無用的串聯,即它不僅僅返回獨立於輸入點的固定值,例如:如果我們想要複合含義爲 e(P, Q) = 1。對於所有 P 和 Q,它沒有提供有關橢圓曲線上點之間關係的任何有用信息。因此,如果串聯提供了有關輸入點之間關係的有用信息,則該串聯被視爲非退化。
那麼如何做到這一點呢?
首先,我們需要了解除數的概念,這是表示橢圓曲線上點函數的另一種方式。
函數的除數本質上是計算函數的零數和無窮數。爲了理解這意味着什麼,讓我們看一些例子。讓我們修復一些點 P = (P_x, P_y),並考慮以下函數:
除數爲 [P] + [-P] – 2 * [O]
[P] + [Q] 與 [P + Q] 不同。 原因如下:
該函數在 P 處爲零,因爲當 x 爲 P_x 時,因此 x – P_x = 0。
該函數在 -P 處爲 0,因爲 -P 和 P 具有相同的 x 座標。
當 x 趨向無窮大時,函數趨向無窮大,因此我們稱函數在 O 處無限。
原因在於橢圓曲線的方程:
y 增長到無窮大大約比 x 快“1.5 倍”,以便能夠跟上 x^3。因此,如果線性函數只有 x,它將被表示爲重數爲 2 的無窮大,但如果它有 y,它將被表示爲重數爲 3 的無窮大。
現在,考慮一個“線函數”:
其中 a、b 和 c 是經過精心選擇的,以便直線穿過橢圓曲線上的 P 點和 Q 點。
由於橢圓曲線上的加法運算方式,這也意味着它會經過點 -P-Q。該函數也會根據 x 和 y 趨於無窮大,從而劃分可能性
每個“有理函數”(在點座標上僅使用有限數量的 +、-、*、/ 運算定義的函數)唯一對應於一個除數,但須遵守乘以常數的條件(即,如果兩個函數F 和 G 具有相同的除數,則 F = G * k,其中 k 是常數)。
兩個函數的乘積除法等於每個函數的除法之和,因此
然後
文章來源:Team Tech/Research Alphatrue
參考來源:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627