Why Knowledge soundness is not a meaningful notion for the sumcheck protocol?

[dajuguan]

更深层的问题是什么snark协议需要Knowledge sound，哪些只需要sound就够了？

[kurtpan666]

• 直观上说是因为sumcheck要证的statement里没有(多项式长度的）witness，要证的就是一个evaluation 的 summation = a value，verifier有本事自己也能自己算一遍（可惜一般他没有这种计算能力）。
  往深了说KS抽取一个witness这件事有一个前提，就是要「存在」一个多项式长度的witness，这正是 $\mathcal{NP}$ 的定义，所以一般KS性质都是针对NP语言内的讨论。而sumcheck可以证的语言比如 UNSAT/#SAT/TQBF ，这三个语言都不是 $\mathcal{NP}$ 的（分别属于 coNP/#P/PSPACE )。
• 证明a statement is true和我「知道」「为什么」this statement is true中间是有gap的；反过来后者KS蕴含soundness，我「证明statement is true+证明知道为什么statement is true」蕴含「证明statement is true」。
• 去证明一个「数学定理」is true的时候，验证者其实不太关心一定要知识抽取的，只要让我相信定理is true就够了，上面sumcheck证的语言都是这种。
• 而对于KS必需的情况举一个例子：对一个地址，我用SNARK证明了对应的私钥（比如离散对数或哈希原像）是「存在」的。这完全不能用！我得去证明我「知道」这个地址相对应的私钥（而不仅仅是私钥存在），我才能去发起交易。
• 此外还有的情况下，KS性质都是不够的！比如可以对不包括在约束中的instance更改以进行malleability attack。如果还要在这种攻击存在下依然安全，那要满足simulation extractability (SE性质)。（UC-secure imply SE)。SE最新相关内容有一篇欧密23的文章 Spartan and Bulletproofs are Simulation-Extractable (for Free!)

[dajuguan]

by kurtpan666:
仔细想。
满足zero knowledge 性质是保护了谁的利益，是prover，malicious verifier不能获取任何额外信息。
满足knowledge soundness性质是保护谁的利益，是verifier，malicious prover不能伪造任何假statement。
你的误解在于没有理解ideal world的概念，没有区分开real world里的adversary和ideal world里的adversary。simulator不能帮助prover造假，extractor也不能帮助verifier偷秘密，相反，simulator只是verifier心中的幻像，extractor只是prover心中的幻像（正式点说是oracle access）。幻像只存在于ideal world中，那个世界里时间是不存在的。simulator只是扮演prover的角色，不一定按照prover的算法来执行，只要输出分布一致即可。extractor也只是在扮演verifier的角色，不一定按照verifier的算法来执行，二者目标根本都不同，extractor的目标是抽取witness。
还有，再说一遍，rewinding 不是只有extractor才用到，simulator一样会用到，例子很多，比如上面提到的QR/G3C协议的simulation里都会用到。
其实如果对simulation paradigm有更深的理解后，你会发现ZKP里KS和ZK两个性质的模拟只是非常简单特殊情况，明显有更一般的情况，在那种情况下verifier的输出也是要抽取的而不是一个比特，那种情况的名字就叫作「安全两方计算2PC」，那个时候就不区分extractor/simulator这些名字了，都是adversary in ideal world。“无量义者，从一法生。其一法者，即无相也。” 阿弥陀佛🙏

[dajuguan]

必读 by 郭宇老师: 理解模拟和提取器 Extractor