在简单情况下(拥有散列为x的字符串)证明/验证零知识证明(zkSNARK)的键

Question

我正在研究一些简单的例子，以了解ZK是如何工作的。

在这个伟大的导言之后，我试图详细介绍一个生成器函数，给出一个验证器和验证键：

pk, vk = G (C, lambda)

这将适用于简单的案件

C (x, w) { return (sha256 (w) == x); }

例如，如何为简单用例构建零知识证明方案：

我认识s的一个字符串，他的哈希是x。我可以证明给你看，而不用透露S。

如何为这个简单的用例实际构建一个zk证明算法？(在这篇文章的注释之后，如何获得证明/验证密钥和函数的方法，给出了在生成后将被丢弃的lambda“浪费”？)

Answer 1

论文von体系结构的简洁非交互零知识中的这一部分就是您想要的。请看下面的图片。

下面我将描述一个非常高层次的想法。使用libsnark和ZCash的ZKSNARK是基于指数假设的。基本上，椭圆曲线密码学中使用的指数就是你提到的“有毒废物”。将G表示为所使用的曲线的组生成器，G*t, G*t^2, \ldots (t是所谓的私有硬币的一部分)，这个系列将一直延续到某些多项式(如H(t)) )的计算被覆盖为止。你可能会想知道H(t)是什么。一个简单的回答是，我们将NP语句(由于单向函数的性质，SHA256的前象是NP语句的见证)转化为由加法门和乘法门组成的算术电路(假设这里不作布尔比较)，然后是多项式A(t)*B(t)-C(t)=H(t)*Z(t)。该多项式方程成立(特别是H(t)存在) iff，证明过程是正确的。简单地说，如果电路包含N门(约束)，那么我们需要阶N的多项式表示。再说一遍为什么这个奇怪的等式？假设底层计算采用T步骤，由于多项式和\text{Fast Fourier Transformation (FFT)}之间的深度联系，这给出了证明时间的下界T\log(T)。在此方法之前，证明时间至少为T^2 (内积和外积，即平方)。另一方面，我们可以将多项式方程进一步简化为\text{ECC}双线性配对问题。我们需要最后一次转换，因为它允许验证步骤非常有效。证明始终是128字节(3对)，验证始终在3-5毫秒左右。所以现在我们也可以回答这个“可信设置”的概念来自哪里。它是重要的，没有人有设置程序的陷阱，即没有人可以接触到“有毒废物”。通常，应用多方计算，以便如果至少有一方是诚实的，则设置是可信的。您提到的另一件事是pk和vk。如您所见，pk是一个证明模板，它使用同态加密对验证器检查多项式A(x)、B(x)和C(x)的知识承诺，以及它们是否使用相同的系数。vk只是在配对中使用。

如果你想知道更多的细节，一个伟大的开端将是解释由Vitalik。不难理解这件事。这是另一种更正式的解释，由基督教Reitwie。此外，对于更多的学术教学资源，本讲座系列涵盖了可验证计算、交互式参数系统、ZKSNARK与预处理、ZK系统前端转换等主题。

Answer 2

在libsnark中，验证器和验证器的密钥由

r1cs_ppzksnark_generator< proof_system >(约束)。

https://github.com/vadym-f/Sudoku_可解性_证明/

要生成密钥，必须首先定义电路。对于sha256，只需选择合适的“小工具”即可。

完整的“算法”是生成密钥，产生一个证明，验证它。你需要学习一些数学和行话，所以2013/879年度如果你能遵循它，那就太棒了。