{"content":{"title":"Mina Learning - Polynomial commitment","body":"多项式承诺是一种方案, 它允许你对一个多项式(即对其系数)做出承诺. 之后, 有人可以要求你在某个点上对多项式进行求值并给出结果, 你可以做到这一点, 同时还能提供正确求值的证明. \r\n\r\n承诺应具有 hiding 和 binding 属性. 同时具有一定的同态属性(如基于 pairing 的承诺具有乘法同态属性; 基于 DLG 的承诺具有加法同态属性).\r\n\r\nBinding: 不存在 $m' \\not = m$, 使得 $\\text{Commit}(m, r) = \\text{Commit}(m', r')$.\r\n\r\nHiding: 对于随机数集合 $\\mathbb{R}$, $\\text{Commit}(m, \\mathbb{R}) \\equiv \\text{Commit}(m', \\mathbb{R})$. 即承诺 $\\text{Commit}(m, r)$ 也不会泄露 $m$ 的任何信息.\r\n\r\n多项式承诺中包含的3个主要算法为: \r\n\r\n1. Commit\r\n2. Open\r\n3. Verify\r\n\r\n![polycom.png](https://img.learnblockchain.cn/attachments/2024/12/5Xv4SeqC674d7b08a70e2.png)\r\n\r\n\r\n### Pedersen hashing and commitments\r\n\r\n简单的非隐藏承诺: Pedersen hash. 要对单个值 $x$ 进行承诺, 只需计算 $xG$, 其中 $G$ 的离散对数是未知的. 要打开承诺, 只需揭示值 x. \r\n\r\n使用 Pedersen hash 可以进行多重承诺. 对于一个值的向量 $(x_{1}, \\cdots, x_{k})$, 可以通过计算 $x_{1}G_{1} + \\cdots + x_{k}G_{k}$ 来实现多重承诺. 其中每个 $G_{i}$ 都是不同的, 并且也具有未知的离散对数. 通常会将最后这个公式简化表示为内积 $<\\vec{x}, \\vec{G}>$, 这里 $\\vec{x} = (x_{1}, \\cdots, x_{k})$, $\\vec{G} = (G_{1}, \\cdots, G_{k})$. 要揭示这个承诺, 只需揭示出值 $x_{i}$.\r\n\r\nPedersen hash 承诺是非隐藏但具有绑定性的, 因为你不能将它们打开为与最初承诺不同的值. 同时将 $x$ 和 $y$ 的承诺相加会得到 $x + y$ 的承诺: $xG + yG = (x + y)G$, 这在我们的 IPA 协议中会很有用. \r\n\r\n### [Inner product argument](https://o1-labs.github.io/proof-systems/plonk/inner_product.html) \r\n\r\n给定域 $F$ 上的两个长度为 $n$ 的向量, 证明它们的内积 $< \\vec{a}, \\vec{b}> = z$.\r\n\r\n对于多项式 $f$ 的系数向量 $\\vec{f}={a_{0}, \\cdots, a_{n}}$, 有 $f(x) = a_{0} + a_{1}x + \\cdots + a_{n}x^{n}$.\r\n\r\n注意 $f(s) = <\\vec{f}, (1, s, \\cdots, s^{n})> $即是内积表示. \r\n\r\n#### Setup\r\n\r\n仅证明者知道的秘密向量是 $\\vec{a} = (a_1,a_2,a_3,a_4)$. \r\n\r\n所有参与者都知道的有:\r\n- $\\vec{G} = (G_1, G_2, G_3, G_4)$, Pedersen hash 的一个基\r\n- $A = \\langle \\vec{a}, \\vec{G} \\rangle$, $\\vec{a}$ 的承诺\r\n- $\\vec{b} = (b_1, b_2, b_3, b_4)$, 某个值 $s$ 的幂, 使得$\\vec{b} = (1, s, s^2, s^3)$\r\n- 内积的结果 $z = \\langle \\vec{a}, \\vec{b} \\rangle$\r\n\r\n![inner1.png](https://img.learnblockchain.cn/attachments/2024/12/TvbGMPBJ674d8c0643d51.png)\r\n\r\n\r\n### Reduced problem\r\n\r\n首先, 证明者将所有内容一分为二. 然后, 他们使用$x$来构造这些分割的线性组合：\r\n\r\n* $\\vec{a'} = x^{-1} \\begin{pmatrix}a_1 \\\\ a_2\\end{pmatrix} + x \\begin{pmatrix}a_3 \\\\ a_4\\end{pmatrix}$\r\n* $\\vec{b'} = x \\begin{pmatrix}b_1 \\\\ b_2\\end{pmatrix} + x^{-1} \\begin{pmatrix}b_3 \\\\ b_4\\end{pmatrix}$\r\n* $\\vec{G'} = x \\begin{pmatrix}G_1 \\\\ G_2\\end{pmatrix} + x^{-1} \\begin{pmatrix}G_3 \\\\ G_4\\end{pmatrix}$\r\n\r\n问题被简化为 $\\langle \\vec{a'}, \\vec{b'} \\rangle = z'$. \r\n\r\n\r\n\r\n#### The actual proof\r\n\r\n$$\r\n\\begin{align*}\r\n\\vec{A'} =& \\langle \\vec{a'}, \\vec{G'} \\rangle \\\\\r\n=& (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) \\\\\r\n=& A + x^{-2} (a_1 G_3 + a_2 G_4) + x^2 (a_3 G_1 + a_4 G_2) \\\\\r\n=& A + x^{-2} L_a + x^{2} R_a\r\n\\end{align*}\r\n$$\r\n\r\n\r\n$$\r\n\\begin{align*}\r\n\\vec{z'} =& \\langle \\vec{a'}, \\vec{b'} \\rangle \\\\\r\n=& \\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 \\\\\r\n=& (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) \\\\\r\n=& z + x^{-2} (L_z) + x^2 (R_z)\r\n\\end{align*}\r\n$$\r\n\r\n验证者可以从先前的值 $z$ 以及证明者需要提供的两个标量值 $L_z$ 和 $R_z$ 重新计算 $z'$. \r\n\r\n所以最后, 证明变成了： \r\n* 向量 $\\vec{a'}$, 其大小是 $\\vec{a}$ 的一半; \r\n* $L_a, R_a$ 曲线点(如果压缩, 则围绕两个域元素); \r\n*  $L_z, R_z$ 标量值. \r\n\r\n我们可以更新我们之前的图表: \r\n\r\n![inner2.png](https://img.learnblockchain.cn/attachments/2024/12/VilTcfS4674d9146cfbed.png)\r\n\r\n\r\n#### The HALO optimization\r\n\r\nHalo 优化类似于 bulletproofs 优化, 可进一步较少 proof size.\r\nHalo 优化中, 问题转换成 $C = A + z U = \\langle \\vec{a}, \\vec{G} \\rangle + \\langle \\vec{a}, \\vec{b} \\rangle U$.\r\n可将其 half reduce 为 \r\n$$ \r\n\\begin{align*}\r\nC' &= A' + z' U \\\\\r\n   &= \\langle \\vec{a'}, \\vec{G'} \\rangle + \\langle \\vec{a'}, \\vec{b'} \\rangle U  \\\\\r\n   &= [A + x^{-2}L_{a} + x^{2}R_{a}] + [z + x^{-2}L_{z} + x^{2}R_{z}] U  \\\\\r\n   &= C + x^{-2}(L_{a} + L_{z}U) + x^{2}(R_{a} + R_{z}U) \\\\\r\n   &= C + x^{-2}L + x^{2}R,\r\n\\end{align*}\r\n$$\r\n这里 $ L= L_{a} + L_{z}U $, $ R = R_{a} + R_{z}U $.\r\n\r\nHalo 优化将 4 个 域元素(压缩后)优化成 2 个域元素.\r\n\r\n下面来添加零知识(给 pedersen commitment 添加 hiding), 有\r\n$$ \r\n\\begin{align*}\r\nC &= A + zU + rH \\\\ \r\n  &= \\langle \\vec{a}, \\vec{G} \\rangle  + \\langle \\vec{a}, \\vec{b} \\rangle U + rH \\\\\r\n  &= C + x^{-2}L + x^{2}R ,\r\n\\end{align*}\r\n$$\r\n这里 $ L= L_{a} + L_{z}U + r_{L}H $, $ R = R_{a} + R_{z}U + r_{R}H $.\r\n\r\n\r\n最后, 下图是协议在经过 $\\log_{2}(n)$ 轮归约后再进行承诺打开的结果:\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/12/CacF4iPE674fce76dd2a7.png)\r\n\r\n#### Aggregation\r\n\r\n1. Aggregating opening proofs for several polynomials\r\n\r\n    Insight:\r\n\r\n    $$\r\n    \\langle \\vec{f} + v \\cdot \\vec{g}, \\vec{x}\\rangle = f(x) + v \\cdot g(x)\r\n    $$\r\n\r\n2. Aggregating opening proofs for several evaluations\r\n\r\n    Insight:\r\n\r\n    $$\r\n    \\langle \\vec{f}, \\vec{x_1} + u \\cdot \\vec{x_2}\\rangle = f(x_1) + u \\cdot f(x_2)\r\n    $$\r\n\r\n3. Double aggregation\r\n\r\n    Insight:\r\n\r\n    $$\r\n    \\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))\r\n    $$\r\n\r\n    Note that this kind of aggregation forces us to provide all combinations of evaluations, some of which might not be needed (for example, $f(x_2)$).\r\n\r\n4. Splitting a polynomial\r\n\r\n    If a polynomial is too large to fit in one SRS, you can split it in chuncks of size at most $n$\r\n\r\n\r\n#### [U(S)RS](https://github.com/o1-labs/proof-systems/blob/403763e2c824b030b3de5c25950c116984311d9b/poly-commitment/src/ipa.rs#L668C1-L694C6)\r\n\r\n\r\nURS 由以下部分组成: \r\n\r\n* `Gs`: 一个任意顺序的曲线点列表, 可用于以非隐藏方式承诺一个多项式. \r\n* `H`: 一个盲化曲线点, 可用于为多项式承诺方案添加隐藏性. \r\n\r\nURS 是确定生成的, 可以由下面的代码生成: \r\n\r\n```rust\r\n    fn create(depth: usize) -> Self {\r\n        let m = G::Map::setup();\r\n\r\n        let g: Vec<_> = (0..depth)\r\n            .map(|i| {\r\n                let mut h = Blake2b512::new();\r\n                h.update((i as u32).to_be_bytes());\r\n                point_of_random_bytes(&m, &h.finalize())\r\n            })\r\n            .collect();\r\n\r\n        // Compute a blinder\r\n        let h = {\r\n            let mut h = Blake2b512::new();\r\n            h.update(\"srs_misc\".as_bytes());\r\n            // FIXME: This is for retrocompatibility with a previous version\r\n            // that was using a list initialisation. It is not necessary.\r\n            h.update(0_u32.to_be_bytes());\r\n            point_of_random_bytes(&m, &h.finalize())\r\n        };\r\n\r\n        Self {\r\n            g,\r\n            h,\r\n            lagrange_bases: HashMapCache::new(),\r\n        }\r\n    }\r\n ```\r\n生成算法, 见 [hash-to-curve](https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html#simple-swu).\r\n\r\n\r\n### KZG10\r\n\r\n$\\textbf{Setup}(1^\\kappa, t)$ 计算两个素数阶 $p$(提供 $\\kappa$ 位安全性)的群 $\\mathbb{G}$ 和 $\\mathbb{G}_{T}$, 使得存在一个对称双线性配对 $e:\\mathbb{G}×\\mathbb{G} \\rightarrow \\mathbb{G}_{T}$ 且 $t$-$\\text{SDH}$ 假设成立. 我们将生成的双线性配对群记为 $\\mathcal{G}=\\langle e,\\mathbb{G},\\mathbb{G}_{T} \\rangle$. 选择一个生成元 $g \\in_{R} \\mathbb{G}$. 令 $\\alpha \\in_{R} \\mathbb{Z}_{p}^{*}$ 为 $\\text{SK}$, 由一个(可能是分布式的)可信权威机构生成. $\\text{Setup}$ 还生成一个 $(t + 1)$ 元组 $\\langle g,g^\\alpha,\\cdots,g^{\\alpha^t}\\rangle\\in\\mathbb{G}^{t + 1}$ 并输出 $\\text{PK}=\\langle\\mathbb{G},g,g^\\alpha,\\cdots,g^{\\alpha^t}\\rangle$. 在构造的其余部分不需要 $\\text{SK}$. \r\n\r\n$\\textbf{Commit}(\\textbf{PK},\\phi(x))$ 计算对次数为 $t$ 或更低的多项式 $\\phi(x)\\in \\mathbb{Z}_{p}[X]$ 的承诺 $\\mathcal{C} = g^{\\phi(\\alpha)} \\in \\mathbb{G}$. 对于$\\phi(x)=\\sum_{j = 0}^{deg(\\phi)}\\phi_{j}x^{j}$, 它输出 $\\mathcal{C} = \\prod_{j = 0}^{deg(\\phi)}(g^{ \\alpha^{j} })^{\\phi_{j} }$ 作为对 $\\phi(x)$ 的承诺.  \r\n\r\n$\\textbf{Open}(\\textbf{PK},\\mathcal{C},\\phi(x))$ 输出所承诺的多项式 $\\phi(x)$.  \r\n\r\n$\\textbf{VerifyPoly}(\\textbf{PK},\\mathcal{C},\\phi(x))$ 验证 $\\mathcal{C} \\stackrel{?} {=} g^{\\phi(\\alpha)}$. 如果对于 $\\phi(x)=\\sum_{j = 0}^{deg(\\phi)}\\phi_{j}x^{j}$ 有 $\\mathcal{C}=\\prod_{j = 0}^{deg(\\phi)}(g^{\\alpha^j})^{\\phi_j}$, 该算法输出 $1$, 否则输出 $0$. 注意, 这仅在 $deg(\\phi)\\leq t$ 时有效.  \r\n\r\n$\\textbf{CreateWitness}(\\textbf{PK},\\phi(x),i)$ 计算 $\\psi_i(x)=\\frac{\\phi(x)-\\phi(i)}{x - i}$ 并输出 $\\langle i,\\phi(i),w_i\\rangle$, 其中见证 $w_i = g^{\\psi_{i}(\\alpha)}$ 的计算方式与上述 $\\mathcal{C}$ 类似.  \r\n\r\n$\\textbf{VerifyEval}(\\textbf{PK},\\mathcal{C},i,\\phi(i),w_i)$ 验证 $\\phi(i)$ 是否是由 $C$ 所承诺的多项式在索引 $i$ 处的求值. 如果 $e(\\mathcal{C},g) \\stackrel{?}{=} e(w_{i},g^{\\alpha}/g^i)e(g,g)^{\\phi(i)}$, 该算法输出 $1$, 否则输出 $0$. $VerifyEval$是正确的, 因为 \r\n$$\r\n\\begin{align*} \r\ne(w_i,g^{\\alpha}/g^i)e(g,g)^{\\phi(i)} \r\n&= e(g^{\\psi_i(\\alpha)},g^{(\\alpha - i)})e(g,g)^{\\phi(i)} \\\\ &=e(g,g)^{\\psi_i(\\alpha)(\\alpha - i)+\\phi(i)} \\\\ \r\n&=e(g,g)^{\\phi(\\alpha)} \\\\ \r\n&=e(C,g) \r\n\\end{align*} \r\n$$\r\n因为$\\phi(x)=\\psi_i(x)(x - i)+\\phi(i)$. \r\n\r\n\r\n> **注意**: $\\alpha$ 是有毒的废物, 必须丢弃, 因为它可以用来破坏绑定性. \r\n\r\n\r\n### Trusted setup\r\n\r\n更多内容, 见 [How do trusted setups work?](https://vitalik.eth.limo/general/2022/03/14/trustedsetup.html)\r\n\r\n\r\n![image.png](https://img.learnblockchain.cn/attachments/2024/12/3QGkKk5R674eadac2bd0e.png)\r\n\r\n最后生成 SRS $\\langle g, g^{\\prod_{i=0}^{k} s_{i}}, \\cdots, g^{\\prod_{i=0}^{k} s_{i}^{n}}    \\rangle$.\r\n\r\n\r\n### 更新 SRS \r\n\r\n对于 SRS $<g, g^{s}, \\cdots, g^{s^{n}} >$, 随机生成 $t$, 更新 SRS 为\r\n$<g, g^{st}, \\cdots, g^{(st)^{n}} >$.\r\n\r\n\r\n### FRI \r\ntodo"},"author":{"user":"https://learnblockchain.cn/people/24251","address":null},"history":null,"timestamp":1733284278,"version":1}