# Verkle Trees 検証コスト

参考文献

- [Gas and circuit constraint benchmarks of binary and quinary incremental Merkle trees using the Poseidon hash function (Koh Wei Jie)](https://ethresear.ch/t/gas-and-circuit-constraint-benchmarks-of-binary-and-quinary-incremental-merkle-trees-using-the-poseidon-hash-function/7446)
- [Inner Product Arguments (Dankrad Feist)](https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html)
- [PCS multiproofs using random evaluation (Dankrad Feist)](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html)
- [Verkle Trees (John Kuszmaul)](https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf)

Verkle tree がどのようなものであるかをざっくり把握したいのであれば, [図解](https://hackmd.io/@totorozk/S1L-b-YOF)を参照してください.

## Hash Function

$32$ bytes の値 $2$ つを $32$ bytes の値にハッシュする関数の特徴.

| Method | Gas cost in Solidity | Constraints of PlonK circuit | Wires of PlonK circuit |
|-|-:|-:|-:|
| Poseidon(t=3) | 49,858 | 234 | 237 |
| MiMC sponge | 59,840 | 1,320 | 1,324 |
| SHA256 | 23,179 | 30,134 | 29,823 |

参考実装

- [MiMC.sol](https://github.com/appliedzkp/semaphore/blob/1e34d21f989550bb10c1a356e045770dfd4b0a6d/contracts/sol/MiMC.sol)
- [buildPoseidon.ts](https://github.com/appliedzkp/maci/blob/36387984f15a448152f5bb4227db978c75082e59/contracts/ts/buildPoseidon.ts) で生成した Solidity
- [mimcsponge.circom](https://github.com/iden3/circomlib/blob/v0.2.4/circuits/mimcsponge.circom) の `MiMCSponge(2, 220, 1)`
- [poseidon3_test.circom](https://github.com/iden3/circomlib/blob/v0.2.4/test/circuits/poseidon3_test.circom)
- [sha256_2_test.circom](https://github.com/iden3/circomlib/blob/v0.2.4/test/circuits/sha256_2_test.circom)

## Vector commitment

$\mathbb{G}_{1}$, $\mathbb{G}_{2}$, $\mathbb{G}_{T}$ を楕円曲線, $\mathbb{F}_{r}$ を有限体とする. 計算量を表現するために, 次の記号を用いる.

- $P$ は有限体 $\mathbb{F}_{r}$ 上の $1$ 点や楕円曲線 $\mathbb{G}_{i}$ 上の $1$ 点を表現するために必要な bytes 数. ここでは, $P = 32$ bytes とする.
- $\mathsf{add}$ は有限体 $\mathbb{F}_{r}$ 上の加算 $\mathbb{F}_{r} \times \mathbb{F}_{r} \to \mathbb{F}_{r}$ の計算コスト.
- $\mathsf{mult}$ は有限体 $\mathbb{F}_{r}$ 上の乗算 $\mathbb{F}_{r} \times \mathbb{F}_{r} \to \mathbb{F}_{r}$ の計算コスト.
- $\mathsf{hash}$ は二値ハッシュ関数 $h: \mathbb{F}_{r} \times \mathbb{F}_{r} \to \mathbb{F}_{r}$ の計算コスト.
- $\mathsf{Add}_i$ は楕円曲線 $\mathbb{G}_{i}$ 上の加算 $\mathbb{G}_{i} \times \mathbb{G}_{i} \to \mathbb{G}_{i}$ の計算コスト.
- $\mathsf{Mult}_i$ は楕円曲線 $\mathbb{G}_{i}$ 上のスカラー倍 $\mathbb{F}_{r} \times \mathbb{G}_{i} \to \mathbb{G}_{i}$ の計算コスト.
- $\mathsf{Pairing}$ はペアリング $e: \mathbb{G}_{1} \times \mathbb{G}_{2} \to \mathbb{G}_{T}$ の計算コスト.
- $\mathsf{op}$ は有限体上の加算や乗算, ハッシュの計算コスト.
- $\mathsf{Op}$ は楕円曲線上の加算やスカラー倍の計算コスト.

各要素が $\mathbb{F}_{r}$ の元で大きさが $k$ の配列の inclusion proof を行う各手法の特徴は下記のようになっている.

| Method | Trusted setup | Commitment size | Proof size | Verification cost |
|-|-|-|-|-|
| KZG | Yes | $P$ | $P$ | $1 \cdot \mathsf{Pairing}$ |
| Pedersen | No | $P$ | $2 \log_2 k \cdot P$ | $k \cdot \mathsf{Add}_1 + {}$ $(k-1) \cdot \mathsf{Mult}_1$|

実際に検証を行う際には, commitment, proof の他に inclusion proof したい index とそこに格納された値を提出する必要がある.

## Zero Knowledge Inclusion Proof of Merkle Tree

各要素が $\mathbb{F}_{r}$ の元で大きさが $n$ の配列の inclusion proof を行う各手法の特徴は下記のようになっている.

| Method | Setup cost | Update cost | Proof size | Verification cost |
|-|-|-|-|-|
| $k$-ary Merkle Tree | $O(n \cdot \mathsf{op})$ | $O(k \log_k n \cdot \mathsf{op})$ | $(k-1) \log_k n \cdot P$ | $O(\log_k n \cdot \mathsf{hash})$ |
| $k$-ary KZG Verkle Tree (注1) | $O(kn \cdot \mathsf{Op})$ | $O(k \log_k n \cdot \mathsf{Op})$ | $\log_k n \cdot P$ (?) | $O(\log_k n \cdot \mathsf{hash}) + {}$ $O(\log_k n \cdot \mathsf{Pairing})$ |
| $k$-ary Pedersen Verkle Tree | $O(kn \cdot \mathsf{Op})$ | $O(k \log_k n \cdot \mathsf{Op})$ | $(\log_k n + 2 \log_2 (\log_k n) + 2) \cdot P$ | $O(\log_k n \cdot \mathsf{hash}) + {}$ $O(\log_k n \cdot \mathsf{Op})$ |

注1. 現状, PlonK 上でペアリングは実装されていない. matter-labs 実装で recursive PlonK を実装するときには, 個々の証明のペアリングを回路内では計算せず, 集約した証明と合わせて検証者側で確認しているように見える. ([L2 - Deep into PLONK Aggregation Circuit](https://starli.medium.com/l2-deep-into-plonk-aggregation-circuit-d9928ccd0749)).

KZG Verkle Tree の leaf の数が n の完全 k 分木の場合, 大きさ k のベクトルに対する KZG commitment の構築に必要な計算量が $O(k^2)$ なので, Verkle tree 全体の構築には $O(kn)$ を要する. なぜなら, 木の深さを $d = \lceil \log_{k}(n) \rceil$とおけば, internal node の個数は $\sum_{l = 0}^{d-1} k^l$ なので,

$$O \left( k^2 \cdot \mathsf{Op} \cdot \sum_{l = 0}^{d-1} k^l \right) = O \left(k^2 \cdot \frac{1-k^d}{1-k} \cdot \mathsf{Op} \right) = O \left(k^{d+1} \cdot \mathsf{Op} \right) = O(kn \cdot \mathsf{Op})$$

であることによる.

更新時の計算量は, 大きさ $k$ の Kate commitment の更新に必要な計算量が $O(k)$ なので, Verkle tree 全体の構築には path の長さが $d$ であることから $O(kd) = O(k \cdot \log_{k}(n))$ を要する.

ここで, Verkle tree の更新コストに現れる値 $f(k) = k \log_k(n)$ が分岐の数 $k$ によってどのように変化するかが気になるが, $f(k)$ は $k = e \approx 2.718$ のときに最小値を取り, $k \geq e$ の範囲で単調増加である. 整数の範囲では $f(3) < f(2) = f(4) < f(5) < \cdots$ となる.

proof size は, $\log_k n$ 個の KZG proof を IPA で $1$ つの proof にまとめ, path に沿った各枝の commitment を root を除いて提出すると考えて算出した.

Verkle Tree の verification cost に $\mathsf{hash}$ の項を含めたのは, 楕円曲線 $\mathbb{G}_{1}$ 上の任意の点を有限体 $\mathbb{F}$ 上の点に変換する衝突耐性のある方法が必要だからである. その他のデータ整形などはコストに含めていない.

実装できる見込みのある $k$-ary Pedersen Verkle Tree を, 今までのbinary (=$2$-ary) Merkle Tree と比較すると, proof size のオーダーは変わらず, verification cost はハッシュの回数が減る代わりに楕円曲線上の加算, 乗算を行う必要がある.

## Proof size

$\mathbb{G}$, $\mathbb{F}_r$ の元は, ともに $P = 32$ bytes で表現できるとする.
$\mathtt{multiProof}$ の大きさは $(2 \log_2 d + 2) \cdot P$ bytes, $\mathtt{commitments}$ の大きさは $d \cdot P$ bytes である. $k = 256, d = 256$ の場合は, $\mathtt{multiProof}$ が $576$ bytes, $\mathtt{commitments}$ が $8192$ bytes である. $k = 256, $d = 32$ ならば, それぞれ $384$ bytes, $1024$ bytes になる.
あるいは代わりに, $576$ bytes の $\mathtt{multiProof}$ の中に $8$ つ分の inclusion proof をまとめることも可能なはずである.

## 検証コスト

[gballet/go-verkle](https://github.com/gballet/go-verkle) の実装における計算コストを調査した. [実装詳細](https://hackmd.io/@totorozk/HyUg8OnFt)については別でまとめてある.

leaf の数が $n = 2^{256}$ のとき, pedersen Verkle proof の検証に用いられる楕円曲線やハッシュの演算回数を調べたところ,
$$75 \cdot \mathsf{Mul} + 80 \cdot \mathsf{Add} + 111 \cdot \mathsf{hash} + 3 \cdot \mathsf{inv} + 360 \cdot \mathsf{mul} + 160 \cdot \mathsf{add}$$ となった.

一方, 通常の Merkle proof の検証では楕円曲線の計算がないので, $256 \cdot \mathsf{hash}$ となる. $\mathsf{hash}$ として Poseidon (t = 3) を用いるとすれば, $59904$ constraints である.

一般の $n$ では, $d = \frac{1}{8} \log_2 n$ とおいたとき, pedersen Verkle proof の検証は $$(2d + 2 \log_2 d + 1) \cdot \mathsf{Mul} + (2d + 3 \log_2 d + 1) \cdot \mathsf{Add} + (3d + 2 \log_2 d + 5) \cdot \mathsf{hash} \\ + 3 \cdot \mathsf{inv} + (11d + 2 \log_2 d - 2) \cdot \mathsf{mul} + 5d \cdot \mathsf{add}$$ であるのに対して, Merkle proof は $8d \cdot \mathsf{hash}$ である.

## 各演算と PlonK の constraints 数

以下, 断りがなければ R1CS (Groth16) の constraints 数について言及する. 回路として実装する楕円曲線の位数は 254 bits とする.

有限体上の加算 $\mathsf{add}$ ・乗算 $\mathsf{mul}$ はそれぞれ $1$ constraint である.

有限体上の逆数を求める演算 $\mathsf{inv}$ は, 逆数をあらかじめ計算したあとで, もとの数と乗算して $1$ になることだけ確認する制約をかければ良いので $1$ constraints である.

<!-- affine form で表された楕円曲線の加算 $\mathsf{Add}$ は, 愚直にやれば $1 \cdot \mathsf{inv} + 3 \cdot \mathsf{mul} + 6 \cdot \mathsf{add} = 10$ constraints 程度だろうか. -->

`AltBabyJubjubBn256` の実装によれば, R1CS constraints 数は, 楕円曲線上の点が $a = -1$ の twisted edwards form $a x^2 + y^2 = 1 + dx^2 y^2$ で表されているときに, 加算 $\mathsf{Add}$ が $6$, 二倍算 $\mathsf{Double}$ が $5$, スカラーが bit 列で与えられた時のスカラー倍 $\mathsf{Mul}$ が $3291$ であった. ここで $n$ bits $(n \leq 254)$ のスカラー倍は
$$\mathsf{Mul} = 1 \cdot \mathsf{select} + (n - 1) \cdot (\mathsf{Add} + \mathsf{Double} + \mathsf{select})$$ であり, 条件分岐 $\mathsf{select}$ は x, y 座標のそれぞれについて行うので $2$ constraints であることによる.

[この issue](https://github.com/zcash/zcash/issues/3924) によれば, Montogomery form $b y^2 = x^3 + a x^2 + x$ で表された楕円曲線上の点の加算 $\mathsf{Add}$ は $4$ constraints で実装できる. また, 楕円曲線上の点の乗算 $\mathsf{Mul}$ は 1 bit あたり約 $6$ constraints で実装できるとのこと. 254 bits のスカラー倍 $\mathsf{Mul}$ は $1530$ constraints になる.

twisted edwards form から Montogomery form への変換は 3 constraints, Montogomery form から twisted edwards form への変換は 2 constraints で行える.

[この issue](https://github.com/zcash/zcash/issues/4254) によれば, **PLONK / Halo 2 custom gates** を用いた場合, Montogomery form で表された楕円曲線上の点の乗算 $\mathsf{Mul}$ は 1 bit あたり約 <s>3 constraints</s> $3.5$ constraints で実装できるとのこと. これが正しければ, $\mathsf{Mul}$ は <s>759 constraints</s> $889$ constraints ということになる (が, なぜこの方法でできるのか理解できていない).

$\mathsf{hash}$ として Poseidon (t = 3) を用いるとすれば, leaf の数が $n = 2^{256}$ ($d = 32$) のときに当てはめると, 1 回の inclusion proof は,
<!-- $$75 \cdot 759 + 80 \cdot 4 + 111 \cdot 234 + 3 \cdot 1 + 360 \cdot 1 + 160 \cdot 1 = 83742
$$ constraints となる. -->
$$75 \cdot 1530 + 80 \cdot 4 + 111 \cdot 234 + 3 \cdot 1 + 360 \cdot 1 + 160 \cdot 1 = 143008
$$ constraints となる.

また, 8 つ分まとめた inclusion proof ($d = 256$ の場合) は
<!-- $$529 \cdot 759 + 537 \cdot 4 + 789 \cdot 234 + 3 \cdot 1 + 2830 \cdot 1 + 1280 \cdot 1 = 592378
$$ constraints である. -->
$$529 \cdot 1530 + 537 \cdot 4 + 789 \cdot 234 + 3 \cdot 1 + 2830 \cdot 1 + 1280 \cdot 1 = 1000257
$$ constraints である.

一方, Merkle proof の場合は 8 つ分の inclusion proof を順に処理していくと, $64d \cdot \mathsf{hash}$ である.

$\mathsf{hash}$ として他の方式を用いたときの比較を下に記す (constraints 数は "PlonK/Halo2" と書いていないものについては Groth16 で作成した時の値).

| | Hash | Merkle | Pedersen Verkle | Pedersen Verkle with PlonK/Halo2 |
|-|-:|-:|-:|-:|
| $d = 32$, Poseidon(t=3) | 234 | 59,904 | 143,008 | 83,742 |
| $d = 32$, MiMC sponge | 1,320 | 337,920 | 263,554 | 204,288 |
| $d = 32$, SHA256 | 30,134 | 7,714,304 | 3,461,908 | 3,402,642 |
| $d = 256$, Poseidon(t=3) | 234 | 479,232 | 1,000,257 | 592,378 |
<!-- | $d = 4096$, Poseidon(t=3) | 234 | 7,667,712 | | >9,000,000 | -->