感谢作者白菜[1]指出问题和对社区技术分享的支持
Thanks
感谢SecbitLabs @郭宇 前两个月分享的Spartan Overview (尽管当时也没太理解)， 以及@even 在研究方向上的指引(据说Hyrax 不太好啃)，不至于走太多弯路。
Motivation
缘于folding，缘于NOVA，缘于Setty，了解到了Spartan，但并不认识它，所以才有了本篇及接下来的关于它的一切(预备知识)......
关于Spartan，在ZK领域可能时间上相对也有点儿远了，暂且不考虑它在某些方面的争议，它的一些思想其实已经影响到其它比较热门的方向了，比如当下的热点Lasso & Jolt，所以它的研究意义仍然很大。
Overview
本篇文章主要参考Hyrax 论文后半部分5-6节，即Hyrax 基于GKR with ZK Argument的contribution。
主要分为两部分，前半部分Reduced Sumcheck Verification主要针对GKR with ZK Argument的Step Two做的优化，对应Hyrax 论文中的Part 5。
后半部分Reduced Witness Evaluation 主要针对GKR with ZK Argument的Final Step做的优化，对应Hyrax 论文中的Part 6。
为了方便对照原始论文理解，本文中的notion尽量与Hyrax 原始论文对齐。
Reduced Sumcheck Verification
仍然以这个图为例，，则 ；第0层，，则 ；第1层，，则 ；第2层，，则 。
Number of Sumcheck Commitments
为了简单起见，上一篇GKR with ZK Argument 中Sumcheck 协议每次round prover 发送给verifier 的多项式系数的commitment的个数我们固定都是4，也就是说多项式的degree全为3。其实prover 需要commit的多项式的degree是有变化的。
Sumcheck Verifications
我们试图把verifier sumcheck 协议中所有round的校验等式且一个矩阵点乘运算表示：
其中每个round verifier 需要验证时用的参数：
备注：其中， 是第1个round 需要校验的sumcheck 值，是verifier 随机采样的第0层电路编码的evaluation值，也是prover 第1个round要证明的值。
汇总一下就是：
矩阵 需要verifier 自行计算，用红色标记的向量 和 向量 都是需要prover 进行commit。 如果说仍然是一个field对应一个commitment,那么commit之后的校验就变成了:
有没有觉得向量 size太大了(19个commitment)？是的，它直接影响着协议过程中的communication cost，所以需要进行压缩处理。
Reducing Sumcheck Commitments
一个field 对应一个commitment:
每次commit的时候还需要一个blind factor .
这样的话Sumcheck 协议中的commitment个数就会与要commit的多项式的degree成线性关系。如果把一个多项式所有参数的commitment压缩成一个commitment：
这样的话就需要多个generator 了，但blind factor 变成了一个 。
我们用矩阵第一行的校验为例：
如果把commitment 压缩成一个commitment ，verifier 就无法直接通过上面的等式来进行校验。这其实就转换成了大家所熟知的IPA 证明，即Inner Product Argument verification。 接下来简单描述一下IPA协议的执行过程
IPA Protocol Overview
prover 要证明query 向量 满足:
Step Three
verifier 发送一个challenge factor 给prover，prover 计算
Reducing Sumcheck into IPA
最后我们看看Hyrax 中Sumcheck 协议被reduced成IPA 协议后的执行过程：
Step One
把多个verification fold成一个：
Step Two
prover 随机生成一个与 等长的向量 ，同 一样计算它的commitment，及 的commitment：
Step Three
verifier 发送一个challenge factor 给prover，prover 计算：
Step Four
verifier 验证：
到此为止多个round 的Sumcheck verification就被转换成了一个IPA verification，proof size(commitments) 也被进一步压缩。
Reduced Witness Evaluation
本节是Hyrax 基于GKR with ZK Argument的Final Step做的优化，对应Hyrax 论文中的Part 6。
Recall
GKR with ZK Argument协议的Final Step是要对最下面一层(input + witness) 的某个evaluation 进行证明，我们仍然用GKR with ZK Argument中的例子：
Compressed Lagrange Basis
基于MLE 多项式：
通过两组 的子向量来represent 长度为 的整个向量，这里应该是一种很常见的succinct 做法。比如protostar 论文中3.5 节compressed verification也是采用了这种技巧，细节可以参考 https://learnblockchain.cn/article/6503
References
【1】Hyrax 论文：https://eprint.iacr.org/2017/1132.pdf
【2】PAZK by Thaler：https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
【3】protostar compressed verification: https://learnblockchain.cn/article/6503
参考资料
[1]白菜: https://learnblockchain.cn/people/15677
来源：登链社区，本站：/zixun/743.html
0 条评论