ZKP: Zero Knowledge Proofs, ZK-SNARK
- MOOC: Zero Knowledge Proofs
- KZG10
- Groth16
- BCCGP16
- Bulletproofs
- Scalable Zero Knowledge via Cycles of Elliptic Curves
- Nova
MOOC: Zero Knowledge Proofs
Lecture 2 Dan Boneh: Introduction to Modern SNARKs
zk-SNARK: Zero-knowledge a Succinct ARgument of Knowledge
setup for circuit C:
- trusted setup per circuit:
S(C; r) -> (pp, vp), secret r - trusted but universal setup:
Sinit(λ; r) -> gp, secret r 仅初始化一次; Sindex(gp, C) -> (pp, vp), per circuit - transparent setup:
S(C) -> (pp, vp)
SNARK (S, P, V)
S(C) -> (pp, vp), public parametersP(pp, x, w) -> π, proofV(vp, x, π) -> accept/reject
functional commitment
setup(1^λ) -> gpcommit(gp, f, r) -> comf, r为random, f为function- polinomial
- multilinear
- vector
- inner product arguments (IPA)
- eval(P, V):
P(gp, f, x, y, r) -> π, V(gp, comf, x, y, π) -> accept/reject
interactive oracle proof (IOP)
Lecture 5 Dan Boneh: The Plonk SNARK
Poly-IOP: Zero Test, Sum Check, Prod Check, Permutation Check
PLONK: a poly-IOP for a general circuit 𝐶(𝑥, 𝑤)，构造input, gate, wiring, output的check，使用lagrange & FFT
Lecture 6 Yupeng Zhang: Polynomial Commitments based on Pairing and Discrete Logarithm
Univariate KZG, Multivariate KZG, …
Bulletproofs
KZG10
KZG10: Constant-Size Commitments to Polynomials and Their Applications
Pairing
universal polynomial φ(x)的取值作为g的幂次，同等变换为，polynomial φ(x)的coffients做为PK里的g^(α^i)的幂次
再结合pairing求解
Trusted Setup:
bilinear pairing group GG = 〈e, G, Gt〉
SK = Random α, PK =〈GG, g, g^α, . . . , g^(α^t) 〉
polynomial φ(x) ∈ Zp[x]
φ(x) = ∑ φj * x^j, 0<= j <=deg(φ), deg(φ) <= t
Commit(PK, φ(x)):
commit C = g^φ(α)
= g^(∑ φj * x^j)
= ∏ g^(φj * α^j)
= ∏ (g^(a^j))^φj
Open(PK, C, φ(x)): φ(x)
VerifyPoly(PK, C, φ(x)):
verify C == ∏ (g^(a^j))^φj
CreateWitness(PK, φ(x), i):
ψi(x) = (φ(x)−φ(i))/(x−i),
proof wi = g^ψi(α)
output 〈i, φ(i), wi〉
VerifyEval(PK, C, i, φ(i), wi):
verify e(C, g) == e(wi, g^α/g^i) * e(g, g)^φ(i)
e(wi, g^α/g^i) * e(g, g)^φ(i)
= e(g^ψi(α) , g^(α-i)) * e(g^φ(i), g)
= e(g^(ψi(α) * (α-i)), g) * e(g^φ(i), g)
= e(g^(φ(α)−φ(i)), g) * e(g^φ(i), g)
= e(g^φ(α), g)
= e(C, g)
Batch Opening 针对多个i聚合运算
CreateWitnessBatch(PK, φ(x), B): 〈B, r(x), wB 〉
B ⊂ Zp
r(x) = φ(x) % ∏ (x-i), i∈B
ψB(x) = (φ(x)−r(x))/ ∏ (x-i), i∈B
wB = g^ψB(α)
VerifyEvalBatch(PK, C, B, r(x), wB ): i∈B
verify e(C, g) == e(g^∏ (α−i), wB ) * e(g, g^r(α))
verify r(i) == φ(i)
Groth16
Groth16: On the Size of Pairing-based Non-interactive Arguments
Groth16 zkSNARK: R1CS and QAP - From Zero to Hero with Finite Fields & sagemath
The Mathematical Mechanics Behind the Groth16 Zero-knowledge Proving Protocol
R1CS: rank-1 constraint system
- 假设共m个Gate。
- 将Gate运算的variable按顺序排列，S中的每一列对应每个variable在某个输入的取值statement x。
- 将Gate运算公式转换为约束matrix：A中的每一行为left input，B中的每一行为right input，C中的每一行为output。
QAP
- 对A/B/C的每一列，以
(row_i, value)为point计算lagrange多项式，获得转置后的lagrange系数多项式matrix，对应ui(x), vi(x), wi(x)。 -
S 与 上述lagrange matrix点乘，获得A/B/C对应的多项式A(x), B(x), C(x)，计算
T(x) = A(x) * B(x) - C(x) Z(x) = (x - 1) * … * (x - m) H(x) = T(x) / Z(x)
显然，T(x) = H(x) * Z(x)
NIZK
见 3.2 NIZK arguments for quadratic arithmetic programs
pairing-friendly elliptic curves
a0 = 1
public statements (a1, ..., al)
secret witnesses (al+1, ..., am)
∑ ai*ui(x) · ∑ ai*vi(x) = ∑ ai*wi(X) + h(X)t(X), i = 0, ..., m
Setup(R):
τ = (α, β, γ, δ, x)
σ1 = ( α, β, δ,
{x^i} 0<=i<=n−1,
{ (β*ui(x)+α*vi(x)+wi(x))/γ } 0<=i<=l,
{ (β*ui(x)+α*vi(x)+wi(x))/δ } l+1<=i<=m,
{ (x^i * t(x))/δ } 0<=i<=n-2
)
σ2 = ( β, γ, δ,
{x^i} 0<=i<=n-1
)
σ = ([σ1]1, [σ2]2)
Prove:
π ← Prove(R, σ, a1, . . . , am)
r, s ← Zp
A = α + ∑ ai*ui(x) + rδ, 0<=i<=m
B = β + ∑ ai*vi(x) + sδ, 0<=i<=m
C = ( ∑ ai*( β*ui(x) + α*vi(x) + wi(x)) + h(x)t(x) )/δ + As + Br − rsδ
π = ([A]1, [C]1, [B]2)
Verify:
Vfy(R, σ, a1, . . . , al, π)
[A]1 · [B]2 = [α]1 · [β]2 + ∑ ai*( (β*ui(x) + α*vi(x) + wi(x))/γ ) · [γ]2 + [C]1 · [δ]2, 0<=i<=l
Sim:
π ← Sim(R, τ, a1, . . . , al)
C = ( AB − αβ − ∑ ai*(β*ui(x) + α*vi(x) + wi(x)) )/δ, i= 0, ..., l
精简的σV，只需l+2个G1 element, 3个G2 element，1个GT element
σV = ( p, G1, G2, GT , e, [1]1, { [( β*ui(x) + α*vi(x) + wi(x))/γ ]1 } 0<=i<=l, [1]2, [γ]2, [δ]2, [αβ]T )
security
显然容易继承pairing curve的malleable问题，基本参考校验原文，或者防重放等。
如果关联identity，同时涉及identity的trust。
BCCGP16
BCCGP16: Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
homomorphic commitment
Comck(m0; r0) · Comck(m1; r1) = Comck(m0 + m1; r0 + r1)
Pedersen commitment
g, h are group elements
(m, r) ∈ Zp x Zp
c = g^r * h^m
Recursive Argument for Inner Product Evaluation
假设g vector size 为 n
n = ∏ m_i , 1 <= i <= µ
按因子顺序做reduce, 例如
取首个m = m_µ，拆分g = (g_1, ..., g_m), 相当于拆分成 m 个 vector size 为 n/m 的vectors g_i。h, a, b 的拆分与g类似。
计算
A_k = ∏ g_i^a_(i+k), min(m,m−k) <=i<=max(1,1−k), k = 1 − m, . . . , m − 1
A = g^a = ∏ g_i^a_i, 1<=i<=m
g_i^a_j的matrix斜线元素相乘，即为A_(j-i)，显然，A = A_0。B与A类似。
(G, p, g, A, h, B, z, m_µ = m, m_µ−1 = m', . . . , m_1)
计算
random challenge x
g' = ∏ (g_i)^(x^−i), 1<=i<=m
A' = ∏ (A_k)^(x^k), 1-m<=k<=m-1
a' = ∑ a_i*(x^i), 1<=i<=m
A' = g'^a'
random challenge x^-1
h' = ∏ (h_i)^(x^i), 1<=i<=m
B' = ∏ (B_k)^(x^-k), 1-m<=k<=m-1
b' = ∑ b_i*(x^-i), 1<=i<=m
B' = h'^b'
z_k = ∑ a_i · b_(i+k), min(m,m−k) <= i <= max(1,1−k), 1-m<=k<=m-1
z_0 = z = ∑ a_i · b_i, 1 <= i <= m
z' = ∑ z_k * x^(-k), 1-m<=k<=m-1
a' · b' = ∑ a_i*(x^i) · ∑ b_j*(x^-j)
= ∑ a_i*(x^i) · b_j*(x^-j)
= ∑ (a_i · b_j)*(x^(i-j))
= ∑ (a_i · b_(i+k))*(x^(-k)) , permutation, let j = i+k
= ∑ z_k * x^(-k)
= z'
获得(G, p, g', A', h', B', z', m_µ−1, . . . , m_1)，显然，g’ vector size为n/m，可进一步拆分为m' = m_µ−1个子vector size。
Recursive Argument, 直至m_1。
Bulletproofs
Bulletproofs: Short Proofs for Confidential Transactions and More
Improved Inner-Product Argument
与BCCGP思路类似，优化为每次折半，Recursive ARgument log(n) 次
g, h ∈ G^n
u, P ∈ G
a, b ∈ Zp^n
n=1:
P->V: a, b
c = a · b
V check P == g^a · h^b · u^c
n>1:
n' = n/2
(a1, a2) = a, (b1, b2) = b, (g1, g2) = g, (h1, h2) = h
c = a · b = a1 · b1 + a2 · b2
CL = a1 · b2 ∈ Zp
CR = a2 · b1 ∈ Zp
L = g2^a1 · h1^b2 · u^CL ∈ G
R = g1^a2 · h2^b1 · u^CR ∈ G
P->V: L, R
V->P: x ∈ Zp*
g' = g1^(x^(-1)) · g2^x ∈ G^n'
h' = h1^x · h2^(x^(-1)) ∈ G^n'
P' = L^(x^2) · P · R^(x^(-2)) ∈ G
a' = a1*x + a2*x^(-1) ∈ Zp^n'
b' = b1*x^(-1) + b2*x ∈ Zp^n'
c' = a' · b'
= a1 · b1 + (a1 · b2)*x^2 + (a2 · b1)*x^(-2) + a2 · b2
P' = L^(x^2) · P · R^(x^(-2))
= (g2^(a1*x^2) · h1^(b2*x^2) · u^(CL*x^2))
· ((g1^a1 · g2^a2) · (h1^b1 · h2^b2) · u^(a · b))
· ((g1^(a2*x^(-2)) · h2^(b1*x^(-2)) · u^(CR*x^(-2))
= (g1^(a1+a2*x^(-2)) · g2^(a2+a1*x^2))
· (h1^(b2*x^2+b1) · h2^(b2+b1*x^(-2)))
· u^(CL*x^2+a · b+CR*x^(-2))
= (g1^(x^(-1)))^(a1*x+a2*x^(-1)) · (g2^x)^(a2*x^(-1)+a1*x)
· (h1^x)^(b2*x+b1*x^(-1)) · (h2^(x^(-1)))^(b2*x+b1*x^(-1))
· u^((a1 · b2)*x^2+a1 · b1 + a2 · b2+(a2 · b1)*x^(-2))
= g'^a' · h'^b · u^c'
get (g', h', u, P', a', b')
显然，g’/h’/a’/b’ 的vector size折半
Inner-Product Range Proof
< aL - z * 1^n, y^n · (aR + z * 1^n) + z^2 * 2^n >
= < aL, y^n · (aR + z * 1^n) >
+ < aL, z^2 * 2^n >
+ < - z * 1^n, y^n · (aR + z * 1^n) >
- z^3 * <1^n, 2^n>
= <aL · aR, y^n> + <aL, y^n · z * 1^n>
+ z^2 * <aL, 2^n>
- z * <1^n, y^n · aR>
- z^2 * <1^n, y^n>
- z^3 * <1^n, 2^n>
= 0 + z * <aL, y^n>
+ z^2 * v
- z * <aR, y^n>
- z^2 * <1^n, y^n>
- z^3 * <1^n, 2^n>
= z * <aL -aR, y^n>
+ z^2 * v
- z^2 * <1^n, y^n>
- z^3 * <1^n, 2^n>
= z^2 *v
+ (z - z^2) * <1^n, y^n>
- z^3 * <1^n, 2^n>
= z^2 * v
+ δ(y, z)
隐藏aL，引入sL、sR
A为aL/aR的commitment, S为sL/sR的commitment
结合Inner-Product, aL/aR/sL/sR 构造 linear vector polynomials
l(X) = (aL - z * 1^n) + sL · X
r(X) = y^n · (aR + z * 1^n + sR · X) + z^2 * 2^n
t(X) = <l(X), r(X)> = t0 + t1 · X + t2 · X^2
显然，t0 = z^2 * v + δ(y, z)
再构造检查
- t1,t2的commitments: T1, T2
- l(x), r(x)的commitment: P
- t与
<l, r>相等
Logarithmic Range Proof
结合Inner-Product Argument, Inner-Product Range Proof，节省 l, r的传输，可优化为2log2(n) + 2 elements
达到n的Logarithmic
Aggregating Logarithmic Proofs
把m个indivual proof 拼成n*msize的vector，同样经过Inner-Product优化，以及Logarithmic的约减，优化为log2(n*m)+4element
达到m的additive
Non-Interactive Proof through Fiat-Shamir
把 Inner-Product Range Proof 中的 y, z 生成方式改一下
mpc
看dealer
Inner-Product Proof for Arithmetic Circuits
注意t2可直接计算，因此仅构造t1, t3, t4, t5, t6的commitment，用于校验t(x)
h' = h^(y^(-n)), 注意此处h’, h为G^n element
再基于P校验l(x), r(x)
Scalable Zero Knowledge via Cycles of Elliptic Curves
Scalable Zero Knowledge via Cycles of Elliptic Curves
Nova
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
通过incrementally verifiable computation (IVC)构造recursive zk ARgument, 实现folding
Relaxed R1CS 将W, E均构造为witness；folding时，二者对应的commitment W’, E’也进行对应的变换
Relaxed R1CS: A, B, C ∈ F^(m x m)
public scalar u ∈ F
public x ∈ F^l
witness W ∈ F^(m−l−1)
Z = (W, x, u)
Folding:
E ← E1 + r · (AZ1 ◦ BZ2 + AZ2 ◦ BZ1 − u1CZ2 − u2CZ1) + r2 · E2
E ∈ F^m
AZ ◦ BZ = (u1 + r · u2) · C(Z1 + rZ2) + E
= uCZ + E
T = AZ1 ◦ BZ2 + AZ2 ◦ BZ1 − u1CZ2 − u2CZ1
...
Construction 1: E’ = Com(ppE , E, rE ) W’ = Com(ppW , W, rW ) T’ = Com(ppE , T, rT ) 将2个Relaxed R1CS instance/witness进行folding，得到新的instance/witness instance (E’, u, W’, x) witness (E, rE , W, rW )
