Upgrade to Pro — share decks privately, control downloads, hide ads and more …

KZG Commitment

KZG Commitment

GBECの解説動画の資料です。
https://goblockchain.network/2023/04/kzg-commitment/

shigeyuki azuchi

April 17, 2023
Tweet

More Decks by shigeyuki azuchi

Other Decks in Technology

Transcript

  1. 1 KZG Commitment
 https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf 
 多項式を利用したコミットメント方式
 
 • コミットメントは固定サイズ
 →楕円曲線上の1つの点


    • 要素の包含証明も固定サイズ
 →楕円曲線上の1つの点
 • 複数の包含証明も集約して固定サイズに
 →楕円曲線上の1つの点
 
 構成要素:
 
 • ペアリングに適した楕円曲線(BLS12-381など)
 • Trusted Setup
 EthreumでもPROTO-DANKSHARDINGに向けて
 セレモニーを実施
 https://ceremony.ethereum.org/
 

  2. 2 多項式を利用したコミットメント
 要素のリストにコミットする多項式の作成: 
 各要素の値が多項式の評価結果になるように多項式を構築する。 
 
 (例)35, 92, 111という値のリストにコミットする場合

    
 1. (1, 35)、(2, 92)、(3, 111)が(x, p(x))となるように多項式補間で多項式を計算する。 
 
 
 p(x) = -19x2 + 114x - 60
 各要素にコミットした多項式ができる 
 2. 多項式を楕円曲線上の点としてエンコードする。 
 P = -19 S 2 + 114 S 1 - 60G
 ※ S 1 とS 2 は誰も値を知らない数値 sを利用し手計算された楕円曲線上の点 S 1 = sG, S 2 = s2G
 Pは上記p(x)にコミットした楕円曲線上の点になる 

  3. 3 Trusted Setup
 KZG CommitmentにおけるTrusted Setupは、コミットメントをエンコードする際に必要な 
 公開パラメーター(S 1 ,

    S 2 , …)を生成する処理 
 
 • n:コミットする要素の数 
 • 多項式の次数= n - 1 = 必要な公開パラメーターの数 
 • ペアリング適した楕円曲線 e: G 1 ✕G 2 → G T とした場合
 ◦ G = G 1 のベースポイント
 ◦ H = G 2 のベースポイント
 として、同じs値を使用して、以下を計算する
 sG, s2G, s3G, …, sn-1G
 sH, s2H, s3H, …, sn-1H
 計算結果を公開パラメーターとする 
 多項式の各次数項の点を 導出するためのTrusted Setup
  4. 4 コミットした値の証明
 マークルツリーを使ったコミットメント方式の場合、 
 
 
 
 
 
 


    
 
 
 log 2 (要素の数)分のデータがプルーフとして必要になる 
 A
 B
 C
 D
 P1
 P2
 commitment
 Bがコミットされていることを証明するには、 
 ツリーの兄弟ブランチの値( AとP2)を提供し、
 それらの値を使ってルートハッシュを計算し、 
 コミットメントと一致するか検証する。 

  5. 5 多項式の性質を利用した包含証明
 【剰余の定理】
 • 多項式p(x)を(x - a)で除算した場合:
 p(x) = q(x)(x

    - a) + r 
 を満たすq(x)とrが一意に存在し(r = p(a))、
 q(x) = (p(x) - r) / (x - a) が成立する。
 
 この特性を利用して 
 1. 証明したい値について( a, p(a))、商多項式q(x)を計算する。
 2. 商多項式q(x)を楕円曲線にエンコードした点 Qを値(a, p(a))のプルーフとして提供する。 
 3. PとQと値について上記の関係が成立するか検証する。 
 ※ この関係の証明にペアリング暗号を使用する 
 

  6. 6 多項式の性質を利用した包含証明
 (例)(1, 35)、(2, 92)、(3, 111)のコミットメント
 
 p(x) = -19x2

    + 114x - 60 P = -19 S 2 + 114 S 1 - 60G
 
 について、(2, 92)が含まれていることを証明する場合、 
 
 q(x) = (p(x) - 92) / (x - 2) を計算し、楕円曲線の点 Qとしてエンコードする 
 
 剰余の定理より、Q・ (S 1 - 2G) == P - 92G が成立すれば、
 Pに(2, 92)がコミットされていることの証明になる 
 
 どうやって検証する? 
 

  7. 7 ペアリング暗号を利用した検証
 • ペアリング関数:加法巡回群G 1 , G 2 と乗法巡回群 G

    T について、
 e: G 1 ✕G 2 → G T
 という関係が成立する一方向写像。 
 つまりG 1 , G 2 の2つの群要素を入力としてG T の群要素を出力することができる。 
 • 双線形性:任意の整数a, bについて以下が成立
 e(aG, bH) = e(G, H)ab
 
  ※ この特性を利用したデジタル署名方式がBLS署名 
 参考:https://goblockchain.network/2022/09/bls/ 

  8. 8 ペアリング暗号を利用した検証
 e(aG, bH) = e(G, H)ab
 
 (例)(1, 35)、(2,

    92)、(3, 111)のコミットメントの
 p(x) = -19x2 + 114x - 60 P = -19 S 2 + 114 S 1 - 60G
 (2, 92)のプルーフ、q(x) = (p(x) - 92) / (x - 2)       Q
 について、剰余の定理の証明 Q・ (S 1 - 2G) == P - 92G 
 
 
 e(Q, sH - 2H) = e(P - 92G, H)
 e(q(s)G, (s - 2)H) = e((p(s) - 92)G, H) 
 e(G, H)(q(s)・(s - 2)) = e(G, H)(p(s) -92)
 q(s)・(s - 2) = p(s) -92
 ペアリング関数を利用して、 剰余の定理の関係を検証
  9. 9 まとめ
 • KZG Commitmentは
 ◦ コミットメントが固定サイズ
 ◦ 包含証明のプルーフも固定サイズ 


    ◦ Commitmentの作成のため、Trusted Setupで作られる公開パラメータを必要とする 
 ◦ ペアリング関数を利用して、多項式の剰余の定理を検証 
 ◦ 複数の要素の包含証明も単一のプルーフで証明可能 
 https://techmedia-think.hatenablog.com/entry/2021/12/21/221009