Hiding KZG10 是 KZG10 协议的变种，其产生的多项式承诺带有随机的盲化因子（Blinding Factor），从而具备 Perfect Hiding 的性质。即假设攻击者的计算能力无限，并且攻击者不能通过承诺来逆向计算出多项式的任何信息。Hiding KZG10 并不常见，但它是构造具有 Zero-knowledge 性质的 zkSNARK 或者其它安全协议的重要组件。
本文介绍两种不同的 Hiding KZG10，第一种方案出自 [KT23]，其主要的技术是多元多项式承诺一个简化版本 [PST13]，[ZGKPP17]，与 [XZZPS19]。第二种方案出自 [CHMMVW19]，其主要的技术是对原始 KZG10 协议论文 [KZG10] 的改进。
None-hiding KZG10 ¶ 先回忆一下基本的 KZG10 协议。首先 KZG10 基于一个事先经过预设置（Universal Trusted Setup）的 SRS：
S R S = ( [ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 , [ 1 ] 2 , [ τ ] 2 ) SRS = ([1]_1, [\tau]_1, [\tau^2]_1, [\tau^3]_1, \ldots, [\tau^D]_1, [1]_2, [\tau]_2) SRS = ([ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 , [ 1 ] 2 , [ τ ] 2 ) 其中 τ 是秘密值，需要在 Setup 阶段后被遗忘，否则任何知道 τ 的一方都可以发起攻击。我们用中括号记号 [ a ] 1 [a]_1 [ a ] 1 a ⋅ G a\cdot G a ⋅ G G ∈ G 1 G\in\mathbb{G}_1 G ∈ G 1 G 1 \mathbb{G}_1 G 1 G 2 \mathbb{G}_2 G 2
由于椭圆曲线群上的元素的除法运算是一个困难问题，所以如果我们的算力有限，那么就无法通过 [ a ] 1 [a]_1 [ a ] 1 a a a a ∈ F r a\in\mathbb{F}_r a ∈ F r a a a
KZG10 需要一个双线性配对运算友好的曲线，即存在另一个椭圆曲线群 G 2 \mathbb{G}_2 G 2 G ′ G' G ′ [ b ] 2 [b]_2 [ b ] 2 b ⋅ G ′ b\cdot G' b ⋅ G ′
e ( a ⋅ G , b ⋅ G ′ ) = ( a b ) ⋅ e ( G , G ′ ) e(a\cdot G, b\cdot G') = (ab)\cdot e(G, G') e ( a ⋅ G , b ⋅ G ′ ) = ( ab ) ⋅ e ( G , G ′ ) 现在假设有一个一元多项式 f ( X ) ∈ F r [ X ] f(X)\in\mathbb{F}_r[X] f ( X ) ∈ F r [ X ]
f ( X ) = f 0 + f 1 X + f 2 X 2 + ⋯ + f d X d f(X) = f_0 + f_1 X + f_2 X^2 + \cdots + f_d X^d f ( X ) = f 0 + f 1 X + f 2 X 2 + ⋯ + f d X d 这里多项式的 Degree d d d d < D d< D d < D C f C_f C f
C f = C o m m i t ( f ( X ) ) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + f 2 ⋅ [ τ 2 ] 1 + ⋯ + f d ⋅ [ τ d ] 1 C_f = \mathsf{Commit}(f(X)) = f_0 \cdot [1]_1 + f_1 \cdot [\tau]_1 + f_2 \cdot [\tau^2]_1 + \cdots + f_d \cdot [\tau^d]_1 C f = Commit ( f ( X )) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + f 2 ⋅ [ τ 2 ] 1 + ⋯ + f d ⋅ [ τ d ] 1 经过推导，不难发现下面的等式成立
C f = [ f ( τ ) ] C_f = [f(\tau)] C f = [ f ( τ )] Evaluation 证明 ¶ 对于我们任意取的多项式 f ( X ) f(X) f ( X ) F r [ X ] \mathbb{F}_r[X] F r [ X ]
f ( X ) = q ( X ) ⋅ g ( X ) + r ( X ) f(X) = q(X) \cdot g(X) + r(X) f ( X ) = q ( X ) ⋅ g ( X ) + r ( X ) 其中 g ( X ) g(X) g ( X ) r ( X ) r(X) r ( X ) deg ( r ) < deg ( g ) \deg(r)<\deg(g) deg ( r ) < deg ( g )
如果我们令 g ( X ) = X − z g(X) = X-z g ( X ) = X − z r ( X ) r(X) r ( X )
f ( X ) = q ( X ) ⋅ ( X − z ) + r f(X) = q(X) \cdot (X-z) + r f ( X ) = q ( X ) ⋅ ( X − z ) + r 进一步，将 X = z X=z X = z f ( z ) = r f(z)=r f ( z ) = r
f ( X ) = q ( X ) ⋅ ( X − z ) + f ( z ) f(X) = q(X) \cdot (X-z) + f(z) f ( X ) = q ( X ) ⋅ ( X − z ) + f ( z ) 这个公式正是 KZG10 协议的核心公式。即如果我们要证明 f ( z ) = r f(z)=r f ( z ) = r f ( X ) − f ( z ) f(X)-f(z) f ( X ) − f ( z ) ( X − z ) (X-z) ( X − z ) q ( X ) q(X) q ( X )
q ( X ) = f ( X ) − f ( z ) X − z q(X) = \frac{f(X)-f(z)}{X-z} q ( X ) = X − z f ( X ) − f ( z ) 如果 f ( X ) f(X) f ( X ) X = z X=z X = z r r r q ( X ) q(X) q ( X )
因此，Prover 只要发送 q ( X ) q(X) q ( X ) q ( X ) q(X) q ( X ) f ( X ) f(X) f ( X )
π e v a l = q 0 ⋅ [ 1 ] 1 + q 1 ⋅ [ τ ] 1 + ⋯ + q d − 1 ⋅ [ τ d − 1 ] 1 = [ q ( τ ) ] 1 \pi_{eval} = q_0 \cdot [1]_1 + q_1 \cdot [\tau]_1 + \cdots + q_{d-1} \cdot [\tau^{d-1}]_1 = [q(\tau)]_1 π e v a l = q 0 ⋅ [ 1 ] 1 + q 1 ⋅ [ τ ] 1 + ⋯ + q d − 1 ⋅ [ τ d − 1 ] 1 = [ q ( τ ) ] 1 然后 Verifier 利用 SRS 提供的 Base 元素来检查分解公式的正确性。对于 Verifier， f ( z ) f(z) f ( z ) z z z
e ( [ f ( τ ) ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) e\Big({\color{red}[f(\tau)]_1} - {\color{blue}f(z)}\cdot[1]_1,\ [1]_2\Big) = e\Big({\color{red}[q(\tau)]_1},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) e ( [ f ( τ ) ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) 上面公式中红色的部分由 Prover 提供，并且不暴露 [ ⋅ ] 1 [\cdot]_1 [ ⋅ ] 1
KZG10 协议的 Polynomial Evaluation 证明仅仅包含一个 G 1 \mathbb{G}_1 G 1 [ q ( τ ) ] 1 [q(\tau)]_1 [ q ( τ ) ] 1 O ( 1 ) O(1) O ( 1 ) O ( 1 ) O(1) O ( 1 ) O ( 1 ) O(1) O ( 1 )
Degree Bound 证明 ¶ KZG10 还支持证明一个多项式 f ( X ) ∈ F r [ X ] f(X)\in\mathbb{F}_r[X] f ( X ) ∈ F r [ X ] d d d
Prover 证明的方式非常直接，即构造一个新的多项式 f ^ ( X ) \hat{f}(X) f ^ ( X )
f ^ ( X ) = X D − d ⋅ f ( X ) \hat{f}(X) = X^{D-d}\cdot f(X) f ^ ( X ) = X D − d ⋅ f ( X ) 显然 f ^ ( X ) \hat{f}(X) f ^ ( X ) D D D [ τ D ] 1 [\tau^D]_1 [ τ D ] 1 D D D
因此，Prover 可以构造 Degree Bound 证明 π 为：
π d e g = f 0 ⋅ [ τ D − d ] 1 + f 1 ⋅ [ τ D − d + 1 ] 1 + ⋯ + f d ⋅ [ τ D ] 1 = [ τ D − d ⋅ f ( τ ) ] 1 \pi_{deg} = f_0\cdot [\tau^{D-d}]_1 + f_1\cdot [\tau^{D-d+1}]_1 + \cdots + f_{d}\cdot [\tau^D]_1 = [\tau^{D-d}\cdot f(\tau)]_1 π d e g = f 0 ⋅ [ τ D − d ] 1 + f 1 ⋅ [ τ D − d + 1 ] 1 + ⋯ + f d ⋅ [ τ D ] 1 = [ τ D − d ⋅ f ( τ ) ] 1 而 Verifier 的验证方法也比较直接，检查 f ^ ( X ) \hat{f}(X) f ^ ( X ) f ( X ) f(X) f ( X ) X D − d X^{D-d} X D − d
e ( [ τ D − d ⋅ f ( τ ) ] 1 , [ 1 ] 2 ) = e ( [ f ( τ ) ] 1 , [ τ D − d ] 2 ) e\Big({\color{red}[\tau^{D-d}\cdot f(\tau)]_1},\ [1]_2\Big) = e\Big({\color{red}[f(\tau)]_1},\ [{\color{blue}\tau^{D-d}}]_2\Big) e ( [ τ D − d ⋅ f ( τ ) ] 1 , [ 1 ] 2 ) = e ( [ f ( τ ) ] 1 , [ τ D − d ] 2 ) 其中 [ τ D − d ] 2 [\tau^{D-d}]_2 [ τ D − d ] 2 G 2 \mathbb{G}_2 G 2
S R S = ( [ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 [ 1 ] 2 , [ τ ] 2 , [ τ 2 ] 2 , [ τ 3 ] 2 , … , [ τ D ] 2 ) SRS = \left(\begin{array}{ccccccc}[1]_1, &[\tau]_1, &[\tau^2]_1, &[\tau^3]_1, &\ldots, &[\tau^D]_1\\[1ex]
[1]_2, &[\tau]_2, &[\tau^2]_2, &[\tau^3]_2, &\ldots, &[\tau^D]_2\\
\end{array}\right) SRS = ( [ 1 ] 1 , [ 1 ] 2 , [ τ ] 1 , [ τ ] 2 , [ τ 2 ] 1 , [ τ 2 ] 2 , [ τ 3 ] 1 , [ τ 3 ] 2 , … , … , [ τ D ] 1 [ τ D ] 2 ) 继续思考，如果 Prover 要同时证明 f ( X ) f(X) f ( X ) f ( X ) f(X) f ( X ) G 1 \mathbb{G}_1 G 1 ( [ f ^ ( τ ) ] 1 , [ τ D − d f ^ ( τ ) ] 1 ) ([\hat{f}(\tau)]_1, [\tau^{D-d}\hat{f}(\tau)]_1) ([ f ^ ( τ ) ] 1 , [ τ D − d f ^ ( τ ) ] 1 )
Perfect Hiding ¶ 如果我们比较在意协议交互过程中的隐私保护问题，那么 KZG10 需要增强对 f ( X ) f(X) f ( X ) [ f ( τ ) ] 1 [f(\tau)]_1 [ f ( τ ) ] 1 f ( X ) f(X) f ( X )
相比之下，传统的 Pedersen Commitment 则具备 Perfect Hiding 的性质，因为它的承诺带有一个随机数作为盲化因子（Blinding Factor），所以即使攻击者有无限的算力，也不能通过 [ f ( τ ) ] 1 [f(\tau)]_1 [ f ( τ ) ] 1 f ( X ) f(X) f ( X )
P e d e r s e n . C o m m i t ( f ( X ) , r ) = f 0 ⋅ G 0 + f 1 ⋅ G 1 + ⋯ + f d ⋅ G d + r ⋅ G ′ \mathsf{Pedersen.Commit}(f(X), r) = f_0 \cdot G_0 + f_1 \cdot G_1 + \cdots + f_d \cdot G_d + {\color{red}r} \cdot G' Pedersen.Commit ( f ( X ) , r ) = f 0 ⋅ G 0 + f 1 ⋅ G 1 + ⋯ + f d ⋅ G d + r ⋅ G ′ 其中 { G i } i = 0 d ∈ G 1 d + 1 \{G_i\}_{i=0}^d\in\mathbb{G}^{d+1}_1 { G i } i = 0 d ∈ G 1 d + 1 G ′ ∈ G 1 G'\in\mathbb{G}_1 G ′ ∈ G 1 r ∈ F r r\in\mathbb{F}_r r ∈ F r
我们接下来解释如何将 KZG10 协议转换为 Perfect Hiding 的协议。这个方案出自[KT23]，其基本思想来自[ZGKP17] 与 [PST13]。
首先，我们可以「尝试」考虑让 KZG10 在承诺 f ( X ) f(X) f ( X )
K Z G . C o m m i t ( f ( X ) , r ) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + ⋯ + f d ⋅ [ τ d ] 1 + r ⋅ [ 1 ] 1 \mathsf{KZG.Commit}(f(X), r) = f_0 \cdot [1]_1 + f_1 \cdot [\tau]_1 + \cdots + f_d \cdot [\tau^d]_1 + {\color{red}r} \cdot [1]_1 KZG.Commit ( f ( X ) , r ) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + ⋯ + f d ⋅ [ τ d ] 1 + r ⋅ [ 1 ] 1 但是这样承诺会有安全问题。因为在 Pedersen Commitment 中，用来承诺 r r r G ′ G' G ′ G i G_i G i r r r f ( X ) f(X) f ( X ) f 0 f_0 f 0
因此我们需要扩充 SRS，并引入一个额外的预设置随机值 γ，专门用以承诺盲化因子 r r r
S R S = ( [ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 , [ γ ] 1 , [ 1 ] 2 , [ τ ] 2 , [ γ ] 2 ) SRS = ([1]_1, [\tau]_1, [\tau^2]_1, [\tau^3]_1, \ldots, [\tau^D]_1, {\color{red}[\gamma]_1}, [1]_2, [\tau]_2, {\color{red}[\gamma]_2}) SRS = ([ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 , [ γ ] 1 , [ 1 ] 2 , [ τ ] 2 , [ γ ] 2 ) 那么 f ( X ) f(X) f ( X )
K Z G . C o m m i t ( f ( X ) , r ) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + ⋯ + f d ⋅ [ τ d ] 1 + r ⋅ [ γ ] 1 \mathsf{KZG.Commit}(f(X), r) = f_0 \cdot [1]_1 + f_1 \cdot [\tau]_1 + \cdots + f_d \cdot [\tau^d]_1 + r \cdot {\color{red}[\gamma]_1} KZG.Commit ( f ( X ) , r ) = f 0 ⋅ [ 1 ] 1 + f 1 ⋅ [ τ ] 1 + ⋯ + f d ⋅ [ τ d ] 1 + r ⋅ [ γ ] 1 我们下面用一个更短的符号 c m ( f ) \mathsf{cm}(f) cm ( f ) f ( X ) f(X) f ( X )
Hiding-KZG10 的 Evaluation 证明 ¶ 虽然我们在 Commitment 加上 Blinding Factor，但是 f ( X ) f(X) f ( X ) f ( X ) f(X) f ( X )
设想如果 Prover 要向 Verifier 证明 f ( z ) = v f(z)=v f ( z ) = v q ( X ) q(X) q ( X ) [ q ( τ ) ] 1 [q(\tau)]_1 [ q ( τ ) ] 1 [ q ( τ ) ] 1 [q(\tau)]_1 [ q ( τ ) ] 1 [ q ( τ ) ] 1 [q(\tau)]_1 [ q ( τ ) ] 1 q ( X ) q(X) q ( X ) f ( X ) f(X) f ( X )
因此，我们也需要为 [ q ( τ ) ] 1 [q(\tau)]_1 [ q ( τ ) ] 1 s \color{green}s s
K Z G . C o m m i t ( q ( X ) , s ) = q 0 ⋅ [ 1 ] 1 + q 1 ⋅ [ τ ] 1 + ⋯ + q d ⋅ [ τ d − 1 ] 1 + s ⋅ [ γ ] 1 = [ q ( τ ) + s ⋅ γ ] 1 \begin{aligned}
\mathsf{KZG.Commit}(q(X), {\color{green}s}) & = q_0 \cdot [1]_1 + q_1 \cdot [\tau]_1 + \cdots + q_d \cdot [\tau^{d-1}]_1 + {\color{green}s} \cdot {\color{red}[\gamma]_1} \\
& = [q(\tau) + {\color{green}s}\cdot{\color{red}\gamma}]_1
\end{aligned} KZG.Commit ( q ( X ) , s ) = q 0 ⋅ [ 1 ] 1 + q 1 ⋅ [ τ ] 1 + ⋯ + q d ⋅ [ τ d − 1 ] 1 + s ⋅ [ γ ] 1 = [ q ( τ ) + s ⋅ γ ] 1 我们把加上盲化因子的 q ( X ) q(X) q ( X ) c m ( q ) \mathsf{cm}(q) cm ( q )
继续回忆下，Non-hiding KZG10 的 Verifier 需要检查下面的等式来验证 q ( X ) q(X) q ( X )
e ( [ f ( τ ) ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) e\Big({\color{red}[f(\tau)]_1} - {\color{blue}f(z)}\cdot[1]_1,\ [1]_2\Big) = e\Big({\color{red}[q(\tau)]_1},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) e ( [ f ( τ ) ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) 不过在 Hiding-KZG10 中，由于多项式承诺 c m ( f ) \mathsf{cm}(f) cm ( f ) c m ( q ) \mathsf{cm}(q) cm ( q )
e ( [ f ( τ ) + r ⋅ γ ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) ≠ e ( [ q ( τ ) + s ⋅ γ ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) e\Big([f(\tau) + {\color{red}r\cdot\gamma}]_1 - {\color{blue}f(z)}\cdot[1]_1,\ [1]_2\Big) \neq e\Big([q(\tau)+{\color{red}s\cdot\gamma}]_1,\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) e ( [ f ( τ ) + r ⋅ γ ] 1 − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) + s ⋅ γ ] 1 , [ τ ] − z ⋅ [ 1 ] 2 ) 我们来推理下为什么上面的等式不成立。先看看等式左边相当于在计算
l h s = f ( τ ) + r ⋅ γ − f ( z ) = f ( τ ) − f ( z ) + r ⋅ γ \begin{aligned}
lhs & = f(\tau) + r\cdot\gamma - f(z) \\
& = f(\tau) - f(z) + r\cdot\gamma
\end{aligned} l h s = f ( τ ) + r ⋅ γ − f ( z ) = f ( τ ) − f ( z ) + r ⋅ γ 等式右边相当于在计算
r h s = ( q ( τ ) + s ⋅ γ ) ⋅ ( τ − z ) = q ( τ ) ⋅ ( τ − z ) + s ⋅ ( τ − z ) ⋅ γ = f ( τ ) − f ( z ) + s ⋅ ( τ − z ) ⋅ γ \begin{aligned}
rhs & = (q(\tau) + s\cdot\gamma) \cdot (\tau - z) \\
& = q(\tau)\cdot(\tau - z) + s\cdot(\tau - z)\cdot\gamma\\
& = f(\tau) - f(z) + s\cdot(\tau - z)\cdot\gamma\\
\end{aligned} r h s = ( q ( τ ) + s ⋅ γ ) ⋅ ( τ − z ) = q ( τ ) ⋅ ( τ − z ) + s ⋅ ( τ − z ) ⋅ γ = f ( τ ) − f ( z ) + s ⋅ ( τ − z ) ⋅ γ 左右两边相差的项为
l h s − r h s = r ⋅ γ − s ⋅ ( τ − z ) ⋅ γ = ( r − s ⋅ ( τ − z ) ) ⋅ γ \begin{aligned}
lhs - rhs & = r\cdot\gamma - s\cdot(\tau - z)\cdot\gamma \\
& = (r - s\cdot(\tau - z)) \cdot \gamma \\
\end{aligned} l h s − r h s = r ⋅ γ − s ⋅ ( τ − z ) ⋅ γ = ( r − s ⋅ ( τ − z )) ⋅ γ 为了让 Verifier 能够验证，我们需要引入一个额外的「群元素」来配平 Pairing 验证公式：
E = r ⋅ [ 1 ] 1 − s ⋅ [ τ ] 1 + ( s ⋅ z ) ⋅ [ 1 ] 1 E = r \cdot [1]_1 - s \cdot [\tau]_1 + (s\cdot z)\cdot [1]_1 E = r ⋅ [ 1 ] 1 − s ⋅ [ τ ] 1 + ( s ⋅ z ) ⋅ [ 1 ] 1 于是，Verifier 可以通过下面的公式来验证：
e ( [ f ( τ ) + r ⋅ γ ] − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) + s ⋅ γ ] , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) e\Big([f(\tau) + r\cdot\gamma] - f(z)\cdot[1]_1,\ [1]_2\Big) = e\Big([q(\tau)+s\cdot\gamma],\ [\tau] - z\cdot[1]_2\Big) + e\Big(E,\ [\gamma]_2\Big) e ( [ f ( τ ) + r ⋅ γ ] − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( [ q ( τ ) + s ⋅ γ ] , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) 或者写为：
e ( c m ( f ) − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( c m ( q ) , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) e\Big({\color{red}\mathsf{cm}(f)} - {\color{blue}f(z)}\cdot[1]_1,\ [1]_2\Big) = e\Big({\color{red}\mathsf{cm}(q)},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) + e\Big({\color{red}E},\ [\gamma]_2\Big) e ( cm ( f ) − f ( z ) ⋅ [ 1 ] 1 , [ 1 ] 2 ) = e ( cm ( q ) , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) 其中红色部分由 Prover 提供，蓝色的部分是公开值。
Hiding-KZG10 的 Degree Bound 证明 ¶ 为了证明 f ( X ) f(X) f ( X ) f ^ ( X ) \hat{f}(X) f ^ ( X ) f ( X ) f(X) f ( X )
c m ( f ^ ) = [ τ D − d ⋅ f ( τ ) ] 1 + η ⋅ [ γ ] 1 \mathsf{cm}(\hat{f}) = [\tau^{D-d}\cdot f(\tau)]_1 + {\color{red}\eta}\cdot[\gamma]_1 cm ( f ^ ) = [ τ D − d ⋅ f ( τ ) ] 1 + η ⋅ [ γ ] 1 同时还要附加上一个用来配平的元素 E ∈ G 1 E\in\mathbb{G}_1 E ∈ G 1
E = ρ ⋅ [ τ D − d ] 1 − η ⋅ [ 1 ] 1 E = \rho\cdot[\tau^{D-d}]_1 - {\color{red}\eta}\cdot[1]_1 E = ρ ⋅ [ τ D − d ] 1 − η ⋅ [ 1 ] 1 这样 Verifier 可以用过下面的等式来验证 f ( X ) f(X) f ( X )
e ( c m ( f ) , [ τ D − d ] 2 ) = e ( c m ( f ^ ) , [ 1 ] 2 ) + e ( E , [ γ ] 2 ) e\Big({\color{red}\mathsf{cm}(f)},\ [\tau^{D-d}]_2\Big) = e\Big({\color{red}\mathsf{cm}(\hat{f})},\ [1]_2\Big) + e\Big({\color{red}E},\ [\gamma]_2\Big) e ( cm ( f ) , [ τ D − d ] 2 ) = e ( cm ( f ^ ) , [ 1 ] 2 ) + e ( E , [ γ ] 2 ) 读者可以自行验证下，上面等式为何成立。
Hiding KZG10 的 Evaluation-and-degree-bound 证明 ¶ 假如对于同一个 Polynomial f ( X ) f(X) f ( X ) f ( X ) f(X) f ( X ) G 1 \mathbb{G}_1 G 1 G 1 \mathbb{G}_1 G 1
Prover 需要构造两个 G 1 \mathbb{G}_1 G 1
c m ( q ) = [ τ D − d ⋅ q ( τ ) ] 1 + η ⋅ [ γ ] 1 \mathsf{cm}(q) = [\tau^{D-d}\cdot q(\tau)]_1 + \eta\cdot[\gamma]_1 cm ( q ) = [ τ D − d ⋅ q ( τ ) ] 1 + η ⋅ [ γ ] 1 另一个元素 E E E
E = ρ ⋅ [ τ D − d ] 1 − η ⋅ [ τ ] 1 + ( η ⋅ z ) ⋅ [ 1 ] 1 E = \rho\cdot[\tau^{D-d}]_1 - \eta\cdot[\tau]_1 + (\eta\cdot z)\cdot[1]_1 E = ρ ⋅ [ τ D − d ] 1 − η ⋅ [ τ ] 1 + ( η ⋅ z ) ⋅ [ 1 ] 1 Prover 发送证明
π = ( c m ( q ) , E ) \pi = (\mathsf{cm}(q), E) π = ( cm ( q ) , E ) 而 Verifier 需要验证下面的等式：
e ( c m ( f ) − f ( z ) ⋅ [ 1 ] 1 , [ τ D − d ] 2 ) = e ( c m ( q ) , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) e\Big({\color{red}\mathsf{cm}(f)} - {\color{blue}f(z)}\cdot[1]_1,\ [\tau^{D-d}]_2\Big) = e\Big({\color{red}\mathsf{cm}(q)},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) + e\Big({\color{red}E},\ [\gamma]_2\Big) e ( cm ( f ) − f ( z ) ⋅ [ 1 ] 1 , [ τ D − d ] 2 ) = e ( cm ( q ) , [ τ ] − z ⋅ [ 1 ] 2 ) + e ( E , [ γ ] 2 ) 另一种 Hiding KZG10 的构造 ¶ 在原始的 [KZG10] 论文中，也提供了实现 Perfect Hiding 的构造方案。我们可以对比下两种不同风格的 Hiding KZG10 变种。
这种方案的想法是在 Commit f ( X ) f(X) f ( X ) r ( X ) r(X) r ( X ) f ( X ) f(X) f ( X ) r ( X ) r(X) r ( X )
f ( X ) = ∑ i = 0 d f i ⋅ X i r ( X ) = ∑ i = 0 d r i ⋅ X i f(X)=\sum_{i=0}^{d}f_i\cdot X^i\qquad r(X)=\sum_{i=0}^{d}r_i\cdot X^i f ( X ) = i = 0 ∑ d f i ⋅ X i r ( X ) = i = 0 ∑ d r i ⋅ X i 注意这里，盲化多项式 r ( X ) r(X) r ( X ) f ( X ) f(X) f ( X )
S R S = ( [ 1 ] 1 , [ τ ] 1 , [ τ 2 ] 1 , [ τ 3 ] 1 , … , [ τ D ] 1 [ γ ] 1 , [ γ τ ] 1 , [ γ τ 2 ] 1 , [ γ τ 3 ] 1 , … , [ γ τ D ] 1 [ 1 ] 2 , [ τ ] 2 , [ τ 2 ] 2 , [ τ 3 ] 2 , … , [ τ D ] 2 ) SRS = \left(
\begin{array}{ccccccc}
[1]_1, &[\tau]_1, &[\tau^2]_1, &[\tau^3]_1, &\ldots, &[\tau^D]_1\\[1ex]
[{\color{red}\gamma}]_1, &[{\color{red}\gamma}\tau]_1, &[{\color{red}\gamma}\tau^2]_1, &[{\color{red}\gamma}\tau^3]_1, &\ldots, &[{\color{red}\gamma}\tau^D]_1\\[1ex]
[1]_2, &[\tau]_2, &[\tau^2]_2, &[\tau^3]_2, &\ldots, &[\tau^D]_2\\
\end{array}\right) SRS = ⎝ ⎛ [ 1 ] 1 , [ γ ] 1 , [ 1 ] 2 , [ τ ] 1 , [ γ τ ] 1 , [ τ ] 2 , [ τ 2 ] 1 , [ γ τ 2 ] 1 , [ τ 2 ] 2 , [ τ 3 ] 1 , [ γ τ 3 ] 1 , [ τ 3 ] 2 , … , … , … , [ τ D ] 1 [ γ τ D ] 1 [ τ D ] 2 ⎠ ⎞ 下面我们定义下 c m ( f ) \mathsf{cm}(f) cm ( f )
K Z G 10. C o m m i t ( f ( X ) , r ( X ) ) = ∑ i = 0 d f i ⋅ [ τ i ] 1 + ∑ i = 0 d r i ⋅ [ γ τ i ] 1 = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 \begin{split}
\mathsf{KZG10.Commit}(f(X), r(X)) & = \sum_{i=0}^{d}f_i\cdot[\tau^i]_1 + \sum_{i=0}^{d}r_i\cdot[{\color{red}\gamma}\tau^i]_1 \\
& = [f(\tau) + {\color{red}\gamma}\cdot r(\tau)]_1
\end{split} KZG10.Commit ( f ( X ) , r ( X )) = i = 0 ∑ d f i ⋅ [ τ i ] 1 + i = 0 ∑ d r i ⋅ [ γ τ i ] 1 = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 本质上，对 f ( X ) f(X) f ( X ) f ˉ ( X ) = f ( X ) + γ ⋅ r ( X ) \bar{f}(X) = f(X) + {\color{red}\gamma}\cdot r(X) f ˉ ( X ) = f ( X ) + γ ⋅ r ( X )
c m ( f ) = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 = [ f ˉ ( τ ) ] 1 \mathsf{cm}(f) = [f(\tau) + {\color{red}\gamma}\cdot r(\tau)]_1 = [\bar{f}(\tau)]_1 cm ( f ) = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 = [ f ˉ ( τ ) ] 1 当 Prover 要证明 f ( z ) = v f(z)=v f ( z ) = v q ( X ) q(X) q ( X ) r ( X ) r(X) r ( X ) X = z X=z X = z
π = ( c m ( q ) , r ( z ) ) \pi = (\mathsf{cm}(q), r(z)) π = ( cm ( q ) , r ( z )) 其中多项式 q ˉ ( X ) \bar{q}(X) q ˉ ( X ) f ˉ ( X ) \bar{f}(X) f ˉ ( X ) ( X − z ) (X-z) ( X − z )
q ˉ ( X ) = q ( X ) + γ ⋅ q ′ ( X ) = f ( X ) − f ( z ) X − z + γ ⋅ r ( X ) − r ( z ) X − z \bar{q}(X) = q(X) + \gamma\cdot q'(X) = \frac{f(X)-f(z)}{X-z} + \gamma\cdot \frac{r(X)-r(z)}{X-z} q ˉ ( X ) = q ( X ) + γ ⋅ q ′ ( X ) = X − z f ( X ) − f ( z ) + γ ⋅ X − z r ( X ) − r ( z ) 当 Verifier 接收到 π e v a l = ( c m ( q ˉ ) , r ( z ) ) \pi_{eval}=(\mathsf{cm}(\bar{q}), r(z)) π e v a l = ( cm ( q ˉ ) , r ( z ))
e ( c m ( f ˉ ) − f ( z ) ⋅ [ 1 ] 1 − r ( z ) ⋅ [ γ ] 1 , [ 1 ] 2 ) = e ( c m ( q ˉ ) , [ τ ] − z ⋅ [ 1 ] 2 ) e\Big({\color{red}\mathsf{cm}(\bar{f})} - {\color{blue}f(z)}\cdot[1]_1 - {\color{red}r(z)}\cdot[\gamma]_1,\ [1]_2\Big) = e\Big({\color{red}\mathsf{cm}(\bar{q})},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) e ( cm ( f ˉ ) − f ( z ) ⋅ [ 1 ] 1 − r ( z ) ⋅ [ γ ] 1 , [ 1 ] 2 ) = e ( cm ( q ˉ ) , [ τ ] − z ⋅ [ 1 ] 2 ) 直觉上，虽然 Prover 发送了 r ( X ) r(X) r ( X ) r ( z ) r(z) r ( z ) r ( X ) r(X) r ( X ) r ( z ) r(z) r ( z ) r ( X ) r(X) r ( X ) f ( X ) f(X) f ( X )
实际上如果我们知道 f ( X ) f(X) f ( X ) k < d k<d k < d r ( X ) r(X) r ( X ) k k k k k k k + 1 k+1 k + 1 r ( X ) r(X) r ( X ) k k k f ( X ) f(X) f ( X )
举一个极端的例子 r ( X ) r(X) r ( X ) f ( z ′ ) = v ′ f(z')=v' f ( z ′ ) = v ′ r ( X ) r(X) r ( X ) f ( X ) f(X) f ( X )
Evaluation-with-degree-bound 证明 ¶ 接下来的问题是，在这个 Hiding-KZG10 方案中，能否像第一种方案一样同时证明 f ( z ) = v f(z)=v f ( z ) = v deg f ≤ d \deg{f}\leq d deg f ≤ d
Commit ¶ 假设 f ( X ) f(X) f ( X ) e e e r ( X ) r(X) r ( X ) e e e
C f = C o m m i t ( f ( X ) , r ( X ) ) = ( ∑ i = 0 d f i ⋅ [ τ i ] 1 ) + ( ∑ i = 0 e r i ⋅ [ γ τ i ] 1 ) = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 \begin{aligned}
C_{f}=\mathsf{Commit}(f(X),r(X)) & = \Big(\sum_{i=0}^{d}f_i\cdot[\tau^i]_1\Big) + \Big(\sum_{i=0}^{e}r_i\cdot[{\color{red}\gamma}\tau^i]_1\Big) \\
& = [f(\tau) + {\color{red}\gamma}\cdot r(\tau)]_1
\end{aligned} C f = Commit ( f ( X ) , r ( X )) = ( i = 0 ∑ d f i ⋅ [ τ i ] 1 ) + ( i = 0 ∑ e r i ⋅ [ γ τ i ] 1 ) = [ f ( τ ) + γ ⋅ r ( τ ) ] 1 为了证明 Degree Bound, 我们还需要承诺 X D − d ⋅ f ( X ) X^{D-d}\cdot f(X) X D − d ⋅ f ( X )
C x f = C o m m i t ( X D − d ⋅ f ( X ) , s ( X ) ) = ( ∑ i = 0 d f i ⋅ [ τ D − d + i ] 1 ) + ( ∑ i = 0 d s i ⋅ [ γ ⋅ τ i ] 1 ) = [ τ D − d ⋅ f ( τ ) + γ ⋅ s ( τ ) ] 1 \begin{aligned}
C_{xf}=\mathsf{Commit}(X^{D-d}\cdot f(X),s(X)) & = \Big(\sum_{i=0}^{d}f_i\cdot[\tau^{D-d+i}]_1\Big) + \Big(\sum_{i=0}^{d}s_i\cdot[{\color{red}\gamma}\cdot \tau^{i}]_1\Big) \\
& = [\tau^{D-d}\cdot f(\tau) + {\color{red}\gamma}\cdot s(\tau)]_1
\end{aligned} C x f = Commit ( X D − d ⋅ f ( X ) , s ( X )) = ( i = 0 ∑ d f i ⋅ [ τ D − d + i ] 1 ) + ( i = 0 ∑ d s i ⋅ [ γ ⋅ τ i ] 1 ) = [ τ D − d ⋅ f ( τ ) + γ ⋅ s ( τ ) ] 1 所以整体上，f ( X ) f(X) f ( X ) c m ( f ) \mathsf{cm}(f) cm ( f )
c m ( f ) = ( C f , C x f ) \mathsf{cm}(f) = (C_{f}, C_{xf}) cm ( f ) = ( C f , C x f ) Evaluation with degree bound 协议 ¶ 公共输入 ：
多项式 f ( X ) f(X) f ( X ) C f C_f C f 多项式 X D − d ⋅ f ( X ) X^{D-d}\cdot f(X) X D − d ⋅ f ( X ) C x f C_{xf} C x f 多项式 f ( X ) f(X) f ( X ) X = z X=z X = z 多项式求值结果：f ( z ) = v f(z)=v f ( z ) = v Witness ：
多项式 f ( X ) f(X) f ( X ) r ( X ) r(X) r ( X ) 多项式 X D − d ⋅ f ( X ) X^{D-d}\cdot f(X) X D − d ⋅ f ( X ) s ( X ) s(X) s ( X ) 第一步 ：Verifier 发送随机数 α ← F r \alpha\leftarrow\mathbb{F}_r α ← F r
第二步 ：Prover 按照下面的步骤
Prover 计算商多项式 q ( X ) q(X) q ( X ) q ( X ) = f ( X ) − f ( z ) X − z q(X) = \frac{f(X) - f(z)}{X-z} q ( X ) = X − z f ( X ) − f ( z ) Prover 计算聚合的盲化多项式 t ( X ) t(X) t ( X ) deg ( t ) ≤ d \deg(t)\leq d deg ( t ) ≤ d t ( X ) = r ( X ) + α ⋅ s ( X ) t(X) = r(X) + \alpha\cdot s(X) t ( X ) = r ( X ) + α ⋅ s ( X ) Prover 计算商多项式 q t ( X ) q_t(X) q t ( X ) q t ( X ) = t ( X ) − t ( z ) X − z q_t(X) = \frac{t(X) - t(z)}{X-z} q t ( X ) = X − z t ( X ) − t ( z ) Prover 引入一个辅助多项式 f ∗ ( X ) f^*(X) f ∗ ( X ) X = z X=z X = z f ∗ ( z ) = 0 f^*(z)=0 f ∗ ( z ) = 0 f ∗ ( X ) = X D − d ⋅ f ( X ) − X D − d ⋅ f ( z ) f^*(X)=X^{D-d}\cdot f(X)-X^{D-d}\cdot f(z) f ∗ ( X ) = X D − d ⋅ f ( X ) − X D − d ⋅ f ( z ) Prover 计算 f ∗ ( X ) f^*(X) f ∗ ( X ) ( X − z ) (X-z) ( X − z ) q ∗ ( X ) q^*(X) q ∗ ( X ) q ∗ ( X ) = f ∗ ( X ) − f ∗ ( z ) X − z = ( X D − d ⋅ f ( X ) − X D − d ⋅ f ( z ) ) − 0 X − z = X D − d ⋅ q ( X ) \begin{aligned}
q^*(X) & = \frac{f^*(X) - f^*(z)}{X-z} \\
& = \frac{\big(X^{D-d}\cdot f(X) - X^{D-d}\cdot f(z)\big) - 0}{X-z} \\
& = X^{D-d}\cdot q(X)
\end{aligned} q ∗ ( X ) = X − z f ∗ ( X ) − f ∗ ( z ) = X − z ( X D − d ⋅ f ( X ) − X D − d ⋅ f ( z ) ) − 0 = X D − d ⋅ q ( X ) Prover 承诺商多项式 q ( X ) q(X) q ( X ) Q = ∑ i = 0 d − 1 q i ⋅ [ τ i ] 1 = [ q ( τ ) ] 1 Q = \sum_{i=0}^{d-1}q_i\cdot[\tau^{i}]_1 = [q(\tau)]_1 Q = i = 0 ∑ d − 1 q i ⋅ [ τ i ] 1 = [ q ( τ ) ] 1 Prover 承诺商多项式 q ∗ ( X ) q^*(X) q ∗ ( X ) Q ∗ = ∑ i = 0 d − 1 q i ⋅ [ τ D − d + i ] 1 = [ q ∗ ( τ ) ] 1 Q^* = \sum_{i=0}^{d-1}q_i\cdot[\tau^{D-d+i}]_1 = [q^*(\tau)]_1 Q ∗ = i = 0 ∑ d − 1 q i ⋅ [ τ D − d + i ] 1 = [ q ∗ ( τ ) ] 1 Prover 承诺盲化多项式的商多项式 q t ( X ) q_t(X) q t ( X ) Q t = ∑ i = 0 d − 1 q t , i ⋅ [ γ τ i ] 1 = [ γ ⋅ q t ( τ ) ] 1 \begin{aligned}
Q_{t} & = \sum_{i=0}^{d-1}q_{t,i}\cdot[{\color{red}\gamma}\tau^{i}]_1 \\
& = [{\color{red}\gamma}\cdot q_t(\tau)]_1
\end{aligned} Q t = i = 0 ∑ d − 1 q t , i ⋅ [ γ τ i ] 1 = [ γ ⋅ q t ( τ ) ] 1 Prover 计算合并的承诺 Q Q Q Q = Q + α ⋅ Q ∗ + Q t = [ q ( τ ) ] 1 + α ⋅ [ q ∗ ( τ ) ] 1 + [ γ ⋅ q t ( τ ) ] 1 \begin{aligned}
Q & = Q + \alpha\cdot {Q^*} + Q_{t} \\
& = [q(\tau)]_1 + \alpha\cdot [q^*(\tau)]_1 + [{\color{red}\gamma}\cdot q_t(\tau)]_1
\end{aligned} Q = Q + α ⋅ Q ∗ + Q t = [ q ( τ ) ] 1 + α ⋅ [ q ∗ ( τ ) ] 1 + [ γ ⋅ q t ( τ ) ] 1 Prover 输出证明 π = ( Q , t ( z ) ) \pi = \big(Q, t(z)\big) π = ( Q , t ( z ) ) 实际上这个协议原理可以换个角度来理解。构造过程可以分解为：两个多项式在同一个点的求值的 Batch（利用 α 随机数）。其中一个是证明多项式 f ( X ) f(X) f ( X ) X = z X=z X = z f ( z ) f(z) f ( z ) f ∗ ( X ) f^*(X) f ∗ ( X ) X = z X=z X = z g ( X ) g(X) g ( X )
g ( X ) = f ( X ) + α ⋅ ( X D − d ⋅ f ( X ) − X D − d ⋅ f ( z ) ) g(X) = f(X) + \alpha\cdot (X^{D-d}\cdot f(X) - X^{D-d}\cdot f(z)) g ( X ) = f ( X ) + α ⋅ ( X D − d ⋅ f ( X ) − X D − d ⋅ f ( z )) 而这个聚合后的多项式 g ( X ) g(X) g ( X ) ( X − z ) (X-z) ( X − z ) q g ( X ) q_g(X) q g ( X )
q g ( X ) = g ( X ) − g ( z ) X − z = q ( X ) + α ⋅ q ∗ ( X ) q_g(X) = \frac{g(X) - g(z)}{X-z} = q(X) + \alpha\cdot q^*(X) q g ( X ) = X − z g ( X ) − g ( z ) = q ( X ) + α ⋅ q ∗ ( X ) 最后 Prover 计算的承诺 Q Q Q [ q g ( τ ) ] [q_g(\tau)] [ q g ( τ )] [ γ ⋅ q t ( τ ) ] [{\color{red}\gamma}\cdot q_t(\tau)] [ γ ⋅ q t ( τ )]
因此这个证明思路其实和 Evaluation 的证明思路基本一致。
Verification
Verifier 接收到的证明为 π = ( Q , t ( z ) ) \pi = \big(Q, t(z)\big) π = ( Q , t ( z ) )
计算 g ( X ) + t ( X ) g(X)+t(X) g ( X ) + t ( X ) C g + t C_{g+t} C g + t C g + t = C f + α ⋅ ( C x f − f ( z ) ⋅ [ τ D − d ] 1 ) C_{g+t} = {\color{red}C_{f}} + \alpha\cdot ({\color{red}C_{xf}} - {\color{blue}f(z)}\cdot[\tau^{D-d}]_1) C g + t = C f + α ⋅ ( C x f − f ( z ) ⋅ [ τ D − d ] 1 ) 计算 g ( X ) + t ( X ) g(X)+t(X) g ( X ) + t ( X ) X = z X=z X = z V g + t V_{g+t} V g + t V g + t = f ( z ) ⋅ [ 1 ] 1 + t ( z ) ⋅ [ γ ] 1 V_{g+t} = f(z)\cdot[1]_1 + {\color{red}t(z)}\cdot[\gamma]_1 V g + t = f ( z ) ⋅ [ 1 ] 1 + t ( z ) ⋅ [ γ ] 1 验证 C g + t C_{g+t} C g + t e ( C g + t − V g + t , [ 1 ] 2 ) = e ( Q , [ τ ] − z ⋅ [ 1 ] 2 ) e\Big(C_{g+t} - V_{g+t},\ [1]_2\Big) = e\Big({\color{red}Q},\ [\tau] - {\color{blue}z}\cdot[1]_2\Big) e ( C g + t − V g + t , [ 1 ] 2 ) = e ( Q , [ τ ] − z ⋅ [ 1 ] 2 ) 第一种方案 Prover 在 Commit 的时候无需关心多项式以后会被打开几次，而只需要加一个随机因子即可实现 Perfect Hiding。而第二种方案则要求 Prover 一次性地加上足够的随机因子（以随机多项式的形式），并且保证多项式以后被打开的次数不会超过这个随机因子。
第二种方案因此带来的一个优势时，在每次证明 Evalutation 时，证明只包含一个 G 1 \mathbb{G}_1 G 1 F r \mathbb{F}_r F r G 1 \mathbb{G}_1 G 1
进一步，第二种方案带来的第一个优势是 Verifier 只需要计算两个 Pairing，而第一种方案则需要计算三个 Pairing。
References ¶ [KZG10] Kate, Aniket, Gregory M. Zaverucha, and Ian Goldberg. “Constant-size commitments to polynomials and their applications.” Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. Springer Berlin Heidelberg, 2010. [KT23] Kohrita, Tohru, and Patrick Towa. “Zeromorph: Zero-knowledge multilinear-evaluation proofs from homomorphic univariate commitments.” Cryptology ePrint Archive (2023). https:// [PST13] Papamanthou, Charalampos, Elaine Shi, and Roberto Tamassia. “Signatures of correct computation.” Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. https:// [ZGKPP17] “A Zero-Knowledge Version of vSQL.” Cryptology ePrint Archive (2023). https:// [XZZPS19] Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. “Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation.” https:// [CHMMVW19] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas Ward. “Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS.” https://