You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
4. A KZG setup for committing polynomials in the coefficient representation can't be repurposed to commit polynomials in the point-value representation。
9. The claim that sets F = {f(a)}{a \in \Omega} and G = {g(a)}{a \in \Omega} are permutations of each other can be reduced to the following product-check claim: $\prod_{a \in \Omega} f(a)/g(a) = 1$
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
1. KZG prover must not know tau to preserve soundness of the polynomial commitment scheme.
正确。$\tau$ , 并产生gp。
KZG trust setup 阶段,需要随机产生一个秘密
Verifier根据gp 和 Prover提供的承诺和证明来验证多项式计算的正确性。$\tau$ ,它可以伪造的一个多项式 $f'(x)$ , 让 $f'(x)$ 和原多项式 $f(x)$ 有相同的承诺。
如果Prover知道
假设$\tau = 5$ 这个秘密被prover 知道了, 对于 $f(x) = 2x^3+x +4$ , 它的commitment是
prover 可以伪造出另外一个多项式,$f'(x) = x^3 + 4x^2 + 4x + 9$ , 它的commitment是
因此$\tau$ 又被称为有毒废料,在setup 之后应当被丢弃。
2. The complexity of KZG verifier is independent of polynomial degree d。
正确。参考 p6 ~ p8
最基本的KZG承诺方案如下:
发送q(x)的commitment$[q(x)]_1$ 和 $v$ 给verifier.
verifier 的复杂度是2次乘法($\zeta[q(x)]_1$ , $[v]_1$ ), 两次加法($[f(x)]_1-[v]_1+\zeta[q(x)]_1$ ) 和一次paring 运算。
3. KZG commitment scheme can't be used to commit to rational functions。
正确。
KZG承诺方案是用于承诺多项式的值,不能用于承诺有理函数(rational functions)
多项式(Polynomials) 是由常数和变量的有限个非负整数次幂组成的。例如,2x^3 + 5x^2 - 3x + 7 就是一个多项式。
有理函数(Rational Functions) 是两个多项式的比值,其中分母的多项式不能为零。有理函数可以表示为 P(x) / Q(x),其中 P(x) 和 Q(x) 都是多项式,而且 Q(x) 不等于零。例如,(2x^2 + 3x) / (x^2 - 5x + 6) 就是一个有理函数。
对于有理函数$\frac{1}{1-x} ,|x|<1$ , 它的泰勒级数展开为无限次,而KZG承诺方案中setup参数为有限次,因此KZG 承诺不能用于有理函数。
4. A KZG setup for committing polynomials in the coefficient representation can't be repurposed to commit polynomials in the point-value representation。
错误。参考p10 ~ p11
这个问题是: 为多项式系数形式生成的KZG setup参数是否能用于产生该多项式的点值形式的承诺?
一个系数形式多项式KZG参数无法直接用于在多项式的点值形式,但是可以将这些KZG 参数转换为点值形式后再用于承诺多项式的点值形式
具体实现可以参考:
https://github.com/qizhou/research/blob/385f4eb5a852ec6b2c7925c51fb75a2af8d1a60f/basic_crypto/poly_commit.py#L35
5. Unlike vector commitments, polynomial commitments support batch evaluation proofs。
错误。参考p14$m\cdot\log{k}, k= merkle,depth$ .
vector commitments 和 polynomial 都支持支持多点打开。
如果 vector commitments 是经典的merkle tree,它的m点打开的proof size 是
KZG 在多点打开的时候,proof size 仍然是一个group element.
6. In ZeroTest, the degree bound on quotient polynomial q(X) ensures that it is not a rational function
正确, 参考问题3 和 p24.
在实际使用时,要限制q(x) 的阶数<<p, 以便使用Schwartz-Zippel引理。
7. ProductCheck protocol incurs quasilinear prover complexity because the polynomial t(X) is defined in the point-value representation。
正确。参考p27~p29
$t(X)$ 是点值形式的(p27), prover 计复杂度是 $O(k\cdot log{k})$ (p29) 。
这句话翻译为:因为多项式t(X)是点值形式表示的, 所以ProductCheck协议prover 的复杂度是准线性的。
8. The set Omega is required to be a multiplicative subgroup in the ProductCheck protocol
正确。参考p26-p29
在ProductCheck协议中,集合Ω(Omega)必须是一个乘法子群(multiplicative subgroup)。
9. The claim that sets F = {f(a)}{a \in \Omega} and G = {g(a)}{a \in \Omega} are permutations of each other can be reduced to the following product-check claim:$\prod_{a \in \Omega} f(a)/g(a) = 1$
错误。
比如{2,3,6,7} 和{2,3,3,14} 这两个集合算满足上述Product-Check,但是这两个集合显然不等。
正确的做法见郭宇老师plonk讲义(https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-constraints.md)
10. Unlike the sumcheck-based polynomial IOP discussed in lecture 4, the plonk IOP has verifier complexity independent of circuit size
错误。$Z_h(\zeta)$ 与电路的size 有关。1:09:59
Plonk IOP 中拷贝约束的中的
11. Unlike the sumcheck-based polynomial IOP discussed in lecture 4, the plonk IOP has constant number of rounds
正确。
Plonk IOP的轮次是固定的 。在郭老师的讲义中是6轮,在plonkathon的代码实现中是5轮。 https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-constraints.md.
12. The custom gates beyond addition and multiplication in plonkish arithmetization help reduce prover time。
正确。参考p56。
在Plonkish算术化中,自定义门允许将更复杂的计算步骤合并成单个门操作,从而减少了在零知识证明中所需的计算量和通信成本。从而节省时间并加快证明的生成过程。
Beta Was this translation helpful? Give feedback.
All reactions