第 5 课练习

$K Z G$ 多项式承诺方案在 $S e t u p$ 阶段涉及到计算对秘密评估点 $τ$ 的幂的承诺，这被称为“可信设置”，通常在被称为“Powers of Tau”的仪式中利用多方计算生成。假如说有一天，你在一张纸条上找到了 $τ$ 的值。你怎么能用它来制作一个假的 $K Z G$ 证明呢？
从 $K Z G$ 多项式承诺方案构造一个向量承诺方案。（提示：对于向量 $m = (m_{1}, \dots, m_{q})$ ，是否存在一个“插值多项式” $I (X)$ 使得 $I (x_{i}) = y_{i}$ ？）

有趣的事实

Verkle 树 [1] 是一种使用向量承诺而不是哈希函数的 Merkle 树。使用 KZG 向量承诺方案，您能看出为什么 Verkle 树更高效吗？

$K Z G$ 多项式承诺方案对关系 $p (x) =$ $y$ 进行披露证明 $π$ 。你能扩展这个方案来产生一个多重证明 $π$ ，让我们相信 $p (x_{i}) = y_{i}$ 对于点列表和评估 $(x_{i}, y_{i})$ ？（提示：假设您有一个插值多项式 $I (X)$ 使得 $I (x_{i}) = y_{i}$ ）。

英文原文

The $S e t u p$ phase of the $K Z G$ polynomial commitment scheme involves computing commitments to powers of a secret evaluation point $τ$ . This is called the "trusted setup" and is often generated in a multi-party computation known as the "Powers of Tau" ceremony. One day, you find the value of $τ$ on a slip of paper. How can you use it to make a fake $K Z G$ opening proof?
Construct a vector commitment scheme from the $K Z G$ polynomial commitment scheme. (Hint: For a vector $m = (m_{1}, \dots, m_{q})$ , is there an "interpolation polynomial" $I (X)$ such that $I (i) = m [i]$ ?)

Fun fact

The Verkle tree [1] is a Merkle tree that uses a vector commitment instead of a hash function. Using the KZG vector commitment scheme, can you see why a Verkle tree is more efficient?

The $K Z G$ polynomial commitment scheme makes an opening proof $π$ for the relation $p (x) =$ $y$ . Can you extend the scheme to produce a multiproof $π$ , that convinces us of $p (x_{i}) = y_{i}$ for a list of points and evaluations $(x_{i}, y_{i})$ ? (Hint: assume that you have an interpolation polynomial $I (X)$ such that $I (x_{i}) = y_{i}$ ).

参考文献

[1] J. Kuszmaul. Verkle trees. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf, 2019.

第 5 课 练习 ​

参考文献 ​

第 5 课练习

参考文献