ゼロ知識セットメンバーシップ証明を可能にするCurve Treesの仕組み

最近、Moneroが計画しているメンバーシップ証明のアップグレードや、BitcoinのUTXOの所有をUTXOの情報を明らかにせずに証明する新しいスキームで見かけるようになったCurve Treesというスキームについて。

https://eprint.iacr.org/2022/756.pdf

Curve Treesは、要素が集合に含まれていることを、要素やマークルパスを明かさずに証明できるよう設計されたデータ構造および証明スキームである。通常のマークルツリーは証明時にマークルパスを公開する必要があるが、Curve Treesでは各ノードをPedersen Commitmentとして構成することで、パス全体をゼロ知識で証明できる。

Curve Treesの仕組み

Curve Treesでは、Shallow Merkle Treeと呼ばれる深さの浅いマークルツリーを使用する。l分木のツリー（l ≧ 2）で、lを大きく取って深さDを浅くする。これは各階層についてゼロ知識証明を行うため、深さDが小さいほど証明サイズや証明時間を抑えられるから。例えば、 ${N = 2^{32}, l = 256, D = 4}$ 。ツリーのリーフはセットの要素で、コミットされた値を表す楕円曲線上の点になる。

リーフの親ノードは、l個の子ノードを束ねたこれも１つの楕円曲線上の点になる。具体的には、

l個の子について、子の（x, y）座標に対して、2l個の独立した生成元 ${G_{x, j}, G_{y, j}}$ を割り当て、各座標値を対応する生成元に乗算した2l個の点と
ランダムなブラインドファクターrと点Hを使って求めたrH

を合算した点が親ノードを表すコミットメントになる。子ノード ${\hat{C}_j}$ の座標を ${\hat {C}_j = (x_j, y_j)}$ とすると、l = 256の場合、親ノードCは

${C = x_1 \cdot G_{x, 1} + x_2 \cdot G_{x, 2} + ... + x_{256} \cdot G_{x, 256} + y_1 \cdot G_{y, 1} + y_2 \cdot G_{y, 2} + ... + y_{256} \cdot G_{y, 256} + r\cdot H}$

となる。

2-cycle曲線

このリーフノードからツリーのルートまで親ノードを計算する際に、2-cycle曲線というものを採用している。

楕円曲線暗号では、

曲線そのものを定義する基礎体（base field）：曲線 ${E: y^{2} = x^{3} + ax + b (a, b \in \mathbb F_q)}$ の係数a, bおよび曲線上の点の座標(x, y)が存在する体 ${\mathbb F_q}$ と
スカラー体（scalar field）： ${k \cdot P}$ のように点をk倍する際のスカラー値kが存在する体。

という2つの異なる体が存在する。

先程リーフの親ノードCを計算した例では、

各 ${x_{j}, y_{j}}$ は基礎体の元だが、それらをPedersen Commitmentではスカラー値（スカラー体の元）として使用する
結果は曲線上の点なのでCの座標は基礎体の元

となる。

ここで、2つの楕円曲線 ${E_1, E_2}$ があり、

${E_1}$ は有限体 ${\mathbb F_p}$ 上に定義され、
${E_2}$ は有限体 ${\mathbb F_q}$ 上に定義され

さらに、

${E_1}$ の群の群位数がq（スカラー体が ${\mathbb F_q}$ ）
${E_2}$ の群の群位数がp（スカラー体が ${\mathbb F_p}$ ）

となる場合、この2つの曲線は2-cycleを形成する。ここでpとqはともに素数。

先程のリーフの計算に用いた各 ${x_{j}, y_{j}}$ を ${\mathbb F_q}$ とした場合、2l個の生成元は ${E_1}$ 上の点で、Pedersen Commitmentの結果Cも ${E_1}$ 上の点となる。しかし、Cを子としたさらにその親を計算する場合、Cのスカラー値(x, y)はpの元であり、 ${E_1}$ のスカラー体は ${\mathbb F_q}$ なので、 ${\mathbb F_p}$ の座標値をそのままスカラーとして利用できない。そのため、親の層では異なる2l個の生成元が必要になる。これに対応するために、2つの楕円曲線の2つの体が切り替わる2-cycle曲線を利用する。 ${\mathbb F_p}$ の元で、Cを計算したときとは異なる ${E_2}$ 上の2l個の生成元を使って同様の計算を行う。つまり、ツリーの階層毎に、ノードの楕円曲線 ${E_1, E_2}$ が入れ替わるような構造になる。このため、各層で得られたノードの座標を、そのまま親層のPedersen Commitmentの係数として利用できる。

Permissible Pointによる最適化

ツリー全体では、上記の2-cycle曲線により2l個×2の生成元を必要とするが、y座標を省略してx座標のみで処理するよう最適化するのがPermissible Pointのアプローチ。基本的に点P = (x, y)において、同じx座標を持つ点はもう1点-P = (x, -y)となる点。

Bitcoinなどでよく見られる点の圧縮では、

x座標とy座標が偶奇どちらを示すかを表す符号bitを付与することで点のエンコードサイズを約半分に圧縮表現や
Taprootのx-only公開鍵ではルールとしてyは偶数であることを強制することでx座標のみをエンコードする（一方の秘密鍵を持っていれば、もう一方の秘密鍵も計算可能なので）

といった手法が用いられている。

Permissible Pointは、少しx-only公開鍵と似ていて、ある述語を満たす点として定義し、その結果を満たすのが (x, y)および (x, -y)のいずれかになる。x座標のみを使用するため、コミットメント値は

${C = \sum\ x_{j} \cdot G_{x, j} + r \cdot H}$

となるが、このとき、x座標に対応するPedersen部分は固定されるため、述語を満たすようにブラインド値rのみを調整する。

述語はペアのちょうど一方だけが満たす判定式である必要がある。ただ、yが偶数とか数値的に小さい方といった整数ベースの判定は、有限体上で算術回路に落とすとビット分解が必要で高コストになるため、論文では平方剰余性に基づく判定を採用している。

メンバーシップ証明とゼロ知識性

任意の値にコミットしたリーフ（要素）を用いて上記の浅いツリーを代数的ハッシュ（Pedersen Commitment）で構築したら、そのツリー内に要素があるかどうかメンバーシップ証明を提供する。なお、以降は、Permissible Pointにより各ノードをx座標のみで表す。

一般的なマークルツリーでは、リーフとツリーのルートまでの兄弟ノードのリストをパスとして提供することでメンバーシップの証明が可能だが、これだとリーフの情報とルートまでのパスが明らかになってしまう。

Curve Treesは、リーフもそのメンバーシップ証明であるマークルパスも隠した状態でメンバーシップを証明するための仕組み。秘匿されないのはツリーのルートだけ。

まず、パス上の各ノードのコミットメント ${C_i}$ について、同じコミットメントをそのまま公開するとパス上のノードが特定されるため、層ごとに独立した新しい乱数 ${\rho'_i}$ を使って再ランダム化したコミットメント ${\hat{C}_i = C_i + \rho'_i \cdot H}$ を計算する。ここで各子 ${V_j}$ は層の曲線上の点で、そのx座標を ${x_j}$ とする。そしてツリーの各層iについて、以下の2つの関係をゼロ知識で証明する。

コミットメントの関係：親が子全体をコミットしていることを証明する。 ${\hat{C}_{i-1}}$ が子 ${V_1, ..., V_l}$ の再ランダム化したコミットメントであること。つまり、 ${\hat{C}_{i-1} = \sum x_j \cdot G_{x, j} + (r_{i-1} + \rho'_{i-1}) \cdot H}$ 。
選択の関係：自分が1の子の1つであることを証明する。ある隠れたインデックスjが存在し、 ${\hat{C}_i = V_j + \rho'_i \cdot H}$ を満たすこと。つまり、層iでパスが通るノードは、層i-1のノードが束ねるl個の子のうちj番目の子である（ ${C_i = V_j}$ である）。

この2つをルートから層Dまで繋ぐとルートからリーフへの一本のパスが、どのノードを通ったかを一切明かさずに証明される。これらの2つの関係は算術回路として表現し、Bulletproofsで証明する。実装によっては、回路内でPedersen Commitmentを直接扱えるよう拡張したGeneralized Bulletproofsが用いられる(Monero FCMP++など)模様。

1については、

再ランダム化された親のコミットメント ${\hat{C_{i-1}}}$ と公開パラメーターである生成元を公開入力とし、
l個の子のx座標と合算ブラインド値 ${r_{i-1} + \rho'_{i-1}}$ をwitnessとして

上記の等式が成立することを回路でチェックする。つまりl個の項からなるマルチスカラー倍算の検算処理。

2については、

層iの再ランダム化コミットメント ${\hat{C_{i}}}$ と公開パラメーターである生成元を公開入力とし、
インデックスj（j番めだけが1で他はすべて0のベクトル ${b_k \in \lbrace 0, 1 \rbrace}$ ）と選ばれた子のx座標と再ランダム化の乱数 ${\rho'_i}$ をwitnessとして

witnessのベクトルが1つだけ1で他はすべて0であることを強制し（ ${b_k(b_k - 1) = 0}$ かつ ${\sum b_k = 1}$ ）、選ばれたx座標を1のwitnessから取り出す（ ${x_j = \sum_{k=1}^{l} b_k \cdot x_k}$ ）。これで ${x_j}$ は確かに親が束ねた子の1つであることが回路内で保証される。選ばれた ${x_j}$ に対応する層iの曲線上の点を ${C_i}$ とすると、公開入力 ${\hat{C_{i}}}$ について ${\hat{C}_i = C_i + \rho'_i \cdot H}$ が成立するかチェックする。これは ${C_i}$ と ${\hat{C_{i}}}$ の差がHの ${\rho'_i}$ 倍であること、すなわち再ランダム化の整合の証明で、単一のスカラー倍算で済む。