多項式コミットメントの１つであるKZG commitmentについて↓
techmedia-think.hatenablog.com
より詳しく理解するためにRubyで実装してみた↓
https://github.com/azuchi/kzg/
セットアップ
KZG commitmentはまず最初に公開パラメーターを生成する。これは基本的に、多項式の最大次数が変わらない限り、最初に１回すればいい計算。
計算自体は単純で、シークレット値（sとする）を生成して、BLS曲線のPointG1のジェネレーターポイントに対して（Gとする）、を計算する。同様にPointG2のジェネレーターポイントに対して（Hとする）も。
このシークレット値は知られるといけない値なので、基本的にTrusted Setupになる。最近EthereumでもPROTO-DANKSHARDINGで使用するためのパラメーターを生成するセレモニーやってる。
今回は、調査目的なので適当なシークレット生成してセットアップする（※ 運用用途では使わないように）。
require 'kzg' secret = xxx # secret number n = 10 setting = KZG.setup_params(secret, n)
↑で9次の多項式まで表現できるパラメーターを生成。※ Pure Rubyで書いてるので、ちょっと遅い。
コミットメントの作成
続いて任意の多項式に対するコミットメントを作成は↓
coefficients = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] commitment = KZG::Commitment.from_coeffs(setting, coefficients) commitment.value # コミットメント値
↑はへのコミットメントになる。
コミットメントの計算の結果得られるのは、多項式の各係数をBLS曲線の有限体の要素として対応する各公開パラメーター（PointG1の点）に乗算して、それらを加算したPointG1の点。
プルーフの作成
続いて、コミットした多項式の評価値（あるxの値におけるf(x)の値）を多項式を開示することなく証明する。たとえば↑の多項式で、x = 35とした場合、f(35) = 808951170278371であることを証明するプルーフを作成する。
proof = commitment.compute_proof(35)
この計算の中身は、
- 多項式
において
を計算する
のようなq(x)が成立するのは、f(35) = 808951170278371の場合のみ。
このプルーフもPointG1の点となる。
検証
コミット値と↑の証明を提供することで、(x, f(x)) = (35, 808951170278371)がコミットされた多項式の評価結果であることを検証することができる。
x = 35 y = 808951170278371 setting.valid_proof?(commitment.value, proof, x, y)
ここでは、BLSのペアリング特性を利用して、 が成立するか検証する。つまりBLSを使って、(x, f(x))のペアに対して、↑のq(x)が成立することを検証している。
↑のペアリングの計算から分かるけど、KZG commitmentの単一のプルーフにおいては、PointG2側の公開パラメータ（）は、最初のsHのみで済む。
Vector commitmentとしての利用
↑のKZG commitmentをVector commitmentとして利用する場合は、多項式の評価値がコミットする値になる多項式を構成する。たとえば、[3, 2, 9]という３つの値にコミットする場合、(x, f(x))が(1, 3), (2, 2), (3, 9)となる点を通過する多項式を構成する。多項式補間を利用すればこのような多項式を計算することができる。
x = [1, 2, 3] y = [3, 2, 9] # x, y座標から多項式を構成 polynomial = KZG::Polynomial.lagrange_interpolate(x, y) # 計算した多項式のコミットメントを作成 commitment = KZG::Commitment.from_coeffs(setting, polynomial.coeffs) # x = 3の場合のプルーフを計算 proof = commitment.compute_proof(3) # f(3) = 9であることを検証 setting.valid_proof?(commitment.value, proof, 3, 9)
今回は、ラグランジュ補間を使って実装してみたけど、go-kzgとかではFFT使ってる。
ということで、実際に実装してみるとふんわり理解してたところが、少し明確になった。次はマルチプルーフとか作ってみるかな。
