Mina Learning - Polynomial commitment

  • longerd
  • 发布于 2024-12-03 15:34
  • 阅读 606

介绍常见的多项式承诺

多项式承诺是一种方案, 它允许你对一个多项式(即对其系数)做出承诺. 之后, 有人可以要求你在某个点上对多项式进行求值并给出结果, 你可以做到这一点, 同时还能提供正确求值的证明.

承诺应具有 hiding 和 binding 属性. 同时具有一定的同态属性(如基于 pairing 的承诺具有乘法同态属性; 基于 DLG 的承诺具有加法同态属性).

Binding: 不存在 mmm' \not = m, 使得 Commit(m,r)=Commit(m,r)\text{Commit}(m, r) = \text{Commit}(m', r').

Hiding: 对于随机数集合 R\mathbb{R}, Commit(m,R)Commit(m,R)\text{Commit}(m, \mathbb{R}) \equiv \text{Commit}(m', \mathbb{R}). 即承诺 Commit(m,r)\text{Commit}(m, r) 也不会泄露 mm 的任何信息.

多项式承诺中包含的3个主要算法为:

  1. Commit
  2. Open
  3. Verify

polycom.png

Pedersen hashing and commitments

简单的非隐藏承诺: Pedersen hash. 要对单个值 xx 进行承诺, 只需计算 xGxG, 其中 GG 的离散对数是未知的. 要打开承诺, 只需揭示值 x.

使用 Pedersen hash 可以进行多重承诺. 对于一个值的向量 (x1,,xk)(x_{1}, \cdots, x_{k}), 可以通过计算 x1G1++xkGkx_{1}G_{1} + \cdots + x_{k}G_{k} 来实现多重承诺. 其中每个 GiG_{i} 都是不同的, 并且也具有未知的离散对数. 通常会将最后这个公式简化表示为内积 <x,G><\vec{x}, \vec{G}>, 这里 x=(x1,,xk)\vec{x} = (x_{1}, \cdots, x_{k}), G=(G1,,Gk)\vec{G} = (G_{1}, \cdots, G_{k}). 要揭示这个承诺, 只需揭示出值 xix_{i}.

Pedersen hash 承诺是非隐藏但具有绑定性的, 因为你不能将它们打开为与最初承诺不同的值. 同时将 xxyy 的承诺相加会得到 x+yx + y 的承诺: xG+yG=(x+y)GxG + yG = (x + y)G, 这在我们的 IPA 协议中会很有用.

Inner product argument

给定域 FF 上的两个长度为 nn 的向量, 证明它们的内积 <a,b>=z< \vec{a}, \vec{b}> = z.

对于多项式 ff 的系数向量 f=a0,,an\vec{f}={a_{0}, \cdots, a_{n}}, 有 f(x)=a0+a1x++anxnf(x) = a_{0} + a_{1}x + \cdots + a_{n}x^{n}.

注意 f(s)=<f,(1,s,,sn)>f(s) = <\vec{f}, (1, s, \cdots, s^{n})> 即是内积表示.

Setup

仅证明者知道的秘密向量是 a=(a1,a2,a3,a4)\vec{a} = (a_1,a_2,a_3,a_4).

所有参与者都知道的有:

  • G=(G1,G2,G3,G4)\vec{G} = (G_1, G_2, G_3, G_4), Pedersen hash 的一个基
  • A=a,GA = \langle \vec{a}, \vec{G} \rangle, a\vec{a} 的承诺
  • b=(b1,b2,b3,b4)\vec{b} = (b_1, b_2, b_3, b_4), 某个值 ss 的幂, 使得b=(1,s,s2,s3)\vec{b} = (1, s, s^2, s^3)
  • 内积的结果 z=a,bz = \langle \vec{a}, \vec{b} \rangle

inner1.png

Reduced problem

首先, 证明者将所有内容一分为二. 然后, 他们使用xx来构造这些分割的线性组合:

  • a=x1(a1a2)+x(a3a4)\vec{a'} = x^{-1} \begin{pmatrix}a_1 \\ a_2\end{pmatrix} + x \begin{pmatrix}a_3 \\ a_4\end{pmatrix}
  • b=x(b1b2)+x1(b3b4)\vec{b'} = x \begin{pmatrix}b_1 \\ b_2\end{pmatrix} + x^{-1} \begin{pmatrix}b_3 \\ b_4\end{pmatrix}
  • G=x(G1G2)+x1(G3G4)\vec{G'} = x \begin{pmatrix}G_1 \\ G_2\end{pmatrix} + x^{-1} \begin{pmatrix}G_3 \\ G_4\end{pmatrix}

问题被简化为 a,b=z\langle \vec{a'}, \vec{b'} \rangle = z'.

The actual proof

A=a,G=(x1a1+xa3)(xG1+x1G3)+(x1a2+xa4)(xG2+x1G4)=A+x2(a1G3+a2G4)+x2(a3G1+a4G2)=A+x2La+x2Ra\begin{align*} \vec{A'} =& \langle \vec{a'}, \vec{G'} \rangle \\ =& (x^{-1} a_1 + x a_3)(x G_1 + x^{-1} G_3) + (x^{-1} a_2 + x a_4)(x G_2 + x^{-1}G_4) \\ =& A + x^{-2} (a_1 G_3 + a_2 G_4) + x^2 (a_3 G_1 + a_4 G_2) \\ =& A + x^{-2} L_a + x^{2} R_a \end{align*}
z=a,b=(x1a1+xa3x1a2+xa4),(xb1+x1b3xb2+x1b4)=(a1b1+a2b2+a3b3+a4b4)+x2(a1b3+a2b4)+x2(a3b1+a4b2)=z+x2(Lz)+x2(Rz)\begin{align*} \vec{z'} =& \langle \vec{a'}, \vec{b'} \rangle \\ =& \langle \begin{pmatrix}x^{-1} a_1 + x a_3 \\ x^{-1} a_2 + x a_4 \end{pmatrix}, \begin{pmatrix}x b_1 + x^{-1} b_3 \\ x b_2 + x^{-1} b_4 \end{pmatrix} \rangle \\ =& (a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4) + x^{-2} (a_1b_3 + a_2b_4) + x^2 (a_3b_1 + a_4b_2) \\ =& z + x^{-2} (L_z) + x^2 (R_z) \end{align*}

验证者可以从先前的值 zz 以及证明者需要提供的两个标量值 LzL_zRzR_z 重新计算 zz'.

所以最后, 证明变成了:

  • 向量 a\vec{a'}, 其大小是 a\vec{a} 的一半;
  • La,RaL_a, R_a 曲线点(如果压缩, 则围绕两个域元素);
  • Lz,RzL_z, R_z 标量值.

我们可以更新我们之前的图表:

inner2.png

The HALO optimization

Halo 优化类似于 bulletproofs 优化, 可进一步较少 proof size.
Halo 优化中, 问题转换成 C=A+zU=a,G+a,bUC = A + z U = \langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b} \rangle U.
可将其 half reduce 为

C=A+zU=a,G+a,bU=[A+x2La+x2Ra]+[z+x2Lz+x2Rz]U=C+x2(La+LzU)+x2(Ra+RzU)=C+x2L+x2R,\begin{align*} C' &= A' + z' U \\ &= \langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'} \rangle U \\ &= [A + x^{-2}L_{a} + x^{2}R_{a}] + [z + x^{-2}L_{z} + x^{2}R_{z}] U \\ &= C + x^{-2}(L_{a} + L_{z}U) + x^{2}(R_{a} + R_{z}U) \\ &= C + x^{-2}L + x^{2}R, \end{align*}

这里 L=La+LzUL= L_{a} + L_{z}U, R=Ra+RzUR = R_{a} + R_{z}U.

Halo 优化将 4 个 域元素(压缩后)优化成 2 个域元素.

下面来添加零知识(给 pedersen commitment 添加 hiding), 有

C=A+zU+rH=a,G+a,bU+rH=C+x2L+x2R,\begin{align*} C &= A + zU + rH \\ &= \langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b} \rangle U + rH \\ &= C + x^{-2}L + x^{2}R , \end{align*}

这里 L=La+LzU+rLHL= L_{a} + L_{z}U + r_{L}H, R=Ra+RzU+rRHR = R_{a} + R_{z}U + r_{R}H.

最后, 下图是协议在经过 log2(n)\log_{2}(n) 轮归约后再进行承诺打开的结果:

image.png

Aggregation

  1. Aggregating opening proofs for several polynomials

    Insight:

    f+vg,x=f(x)+vg(x)\langle \vec{f} + v \cdot \vec{g}, \vec{x}\rangle = f(x) + v \cdot g(x)
  2. Aggregating opening proofs for several evaluations

    Insight:

    f,x1+ux2=f(x1)+uf(x2)\langle \vec{f}, \vec{x_1} + u \cdot \vec{x_2}\rangle = f(x_1) + u \cdot f(x_2)
  3. Double aggregation

    Insight:

    f+vg,x1+ux2=f(x1)+vg(x1)+u(f(x2)+vg(x2))\langle \vec{f} + v \cdot \vec{g}, \vec{x_1} + u \cdot \vec{x_2} \rangle = f(x_1) + v \cdot g(x_1) + u \cdot (f(x_2) + v \cdot g(x_2))

    Note that this kind of aggregation forces us to provide all combinations of evaluations, some of which might not be needed (for example, f(x2)f(x_2)).

  4. Splitting a polynomial

    If a polynomial is too large to fit in one SRS, you can split it in chuncks of size at most nn

U(S)RS

URS 由以下部分组成:

  • Gs: 一个任意顺序的曲线点列表, 可用于以非隐藏方式承诺一个多项式.
  • H: 一个盲化曲线点, 可用于为多项式承诺方案添加隐藏性.

URS 是确定生成的, 可以由下面的代码生成:

    fn create(depth: usize) -> Self {
        let m = G::Map::setup();

        let g: Vec<_> = (0..depth)
            .map(|i| {
                let mut h = Blake2b512::new();
                h.update((i as u32).to_be_bytes());
                point_of_random_bytes(&m, &h.finalize())
            })
            .collect();

        // Compute a blinder
        let h = {
            let mut h = Blake2b512::new();
            h.update("srs_misc".as_bytes());
            // FIXME: This is for retrocompatibility with a previous version
            // that was using a list initialisation. It is not necessary.
            h.update(0_u32.to_be_bytes());
            point_of_random_bytes(&m, &h.finalize())
        };

        Self {
            g,
            h,
            lagrange_bases: HashMapCache::new(),
        }
    }

生成算法, 见 hash-to-curve.

KZG10

Setup(1κ,t)\textbf{Setup}(1^\kappa, t) 计算两个素数阶 pp(提供 κ\kappa 位安全性)的群 G\mathbb{G}GT\mathbb{G}_{T}, 使得存在一个对称双线性配对 e:G×GGTe:\mathbb{G}×\mathbb{G} \rightarrow \mathbb{G}_{T}tt-SDH\text{SDH} 假设成立. 我们将生成的双线性配对群记为 G=e,G,GT\mathcal{G}=\langle e,\mathbb{G},\mathbb{G}_{T} \rangle. 选择一个生成元 gRGg \in_{R} \mathbb{G}. 令 αRZp\alpha \in_{R} \mathbb{Z}_{p}^{*}SK\text{SK}, 由一个(可能是分布式的)可信权威机构生成. Setup\text{Setup} 还生成一个 (t+1)(t + 1) 元组 g,gα,,gαtGt+1\langle g,g^\alpha,\cdots,g^{\alpha^t}\rangle\in\mathbb{G}^{t + 1} 并输出 PK=G,g,gα,,gαt\text{PK}=\langle\mathbb{G},g,g^\alpha,\cdots,g^{\alpha^t}\rangle. 在构造的其余部分不需要 SK\text{SK}.

Commit(PK,ϕ(x))\textbf{Commit}(\textbf{PK},\phi(x)) 计算对次数为 tt 或更低的多项式 ϕ(x)Zp[X]\phi(x)\in \mathbb{Z}_{p}[X] 的承诺 C=gϕ(α)G\mathcal{C} = g^{\phi(\alpha)} \in \mathbb{G}. 对于ϕ(x)=j=0deg(ϕ)ϕjxj\phi(x)=\sum_{j = 0}^{deg(\phi)}\phi_{j}x^{j}, 它输出 C=j=0deg(ϕ)(gαj)ϕj\mathcal{C} = \prod_{j = 0}^{deg(\phi)}(g^{ \alpha^{j} })^{\phi_{j} } 作为对 ϕ(x)\phi(x) 的承诺.

Open(PK,C,ϕ(x))\textbf{Open}(\textbf{PK},\mathcal{C},\phi(x)) 输出所承诺的多项式 ϕ(x)\phi(x).

VerifyPoly(PK,C,ϕ(x))\textbf{VerifyPoly}(\textbf{PK},\mathcal{C},\phi(x)) 验证 C=?gϕ(α)\mathcal{C} \stackrel{?} {=} g^{\phi(\alpha)}. 如果对于 ϕ(x)=j=0deg(ϕ)ϕjxj\phi(x)=\sum_{j = 0}^{deg(\phi)}\phi_{j}x^{j}C=j=0deg(ϕ)(gαj)ϕj\mathcal{C}=\prod_{j = 0}^{deg(\phi)}(g^{\alpha^j})^{\phi_j}, 该算法输出 11, 否则输出 00. 注意, 这仅在 deg(ϕ)tdeg(\phi)\leq t 时有效.

CreateWitness(PK,ϕ(x),i)\textbf{CreateWitness}(\textbf{PK},\phi(x),i) 计算 ψi(x)=ϕ(x)ϕ(i)xi\psi_i(x)=\frac{\phi(x)-\phi(i)}{x - i} 并输出 i,ϕ(i),wi\langle i,\phi(i),w_i\rangle, 其中见证 wi=gψi(α)w_i = g^{\psi_{i}(\alpha)} 的计算方式与上述 C\mathcal{C} 类似.

VerifyEval(PK,C,i,ϕ(i),wi)\textbf{VerifyEval}(\textbf{PK},\mathcal{C},i,\phi(i),w_i) 验证 ϕ(i)\phi(i) 是否是由 CC 所承诺的多项式在索引 ii 处的求值. 如果 e(C,g)=?e(wi,gα/gi)e(g,g)ϕ(i)e(\mathcal{C},g) \stackrel{?}{=} e(w_{i},g^{\alpha}/g^i)e(g,g)^{\phi(i)}, 该算法输出 11, 否则输出 00. VerifyEvalVerifyEval是正确的, 因为

e(wi,gα/gi)e(g,g)ϕ(i)=e(gψi(α),g(αi))e(g,g)ϕ(i)=e(g,g)ψi(α)(αi)+ϕ(i)=e(g,g)ϕ(α)=e(C,g)\begin{align*} e(w_i,g^{\alpha}/g^i)e(g,g)^{\phi(i)} &= e(g^{\psi_i(\alpha)},g^{(\alpha - i)})e(g,g)^{\phi(i)} \\ &=e(g,g)^{\psi_i(\alpha)(\alpha - i)+\phi(i)} \\ &=e(g,g)^{\phi(\alpha)} \\ &=e(C,g) \end{align*}

因为ϕ(x)=ψi(x)(xi)+ϕ(i)\phi(x)=\psi_i(x)(x - i)+\phi(i).

注意: α\alpha 是有毒的废物, 必须丢弃, 因为它可以用来破坏绑定性.

Trusted setup

更多内容, 见 How do trusted setups work?

image.png

最后生成 SRS g,gi=0ksi,,gi=0ksin\langle g, g^{\prod_{i=0}^{k} s_{i}}, \cdots, g^{\prod_{i=0}^{k} s_{i}^{n}} \rangle.

更新 SRS

对于 SRS <g,gs,,gsn><g, g^{s}, \cdots, g^{s^{n}} >, 随机生成 tt, 更新 SRS 为
<g,gst,,g(st)n><g, g^{st}, \cdots, g^{(st)^{n}} >.

FRI

todo

点赞 3
收藏 2
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论