zk-SNARK：关于私钥、环签名、ZKKSP
私钥
理论上，对于任何数学问题都可以构造一个零知识证明(ZKP)，而无需公开其解决方案。在实践中，为一个问题开发 ZKP 通常需要发明一种全新的密码算法。它没有标准的“配方”，需要的是广泛且深入的密码学知识。例如，ZK 的谜题涉及∑-protocol 和 ZK key-statement proof Pedersen 承诺和 Fiat-Shamir 启发式。
zk-SNARK 对任意问题的 ZKP 生成进行标准化。只需用 ZK 格式表达要证明的原始问题，例如利用特定语言 Circom 或 Zokrates。其余的都由通用的 zk-SNARK 框架处理，它隐藏了底层密码学的所有复杂性。
在 zk-SNARK 之前，为新问题构建 ZKP 就类似于在需要设计新的 ZKP 应用程序时构建新的 ASIC。zk-SNARK 允许通过简单地对通用“ZK CPU”进行编程来构建新的 ZKP。前者需要一个密码学家，而后者只需要一个程序员，极大地降低了 ZKP 的进入门槛。
为了展示这种范式转换的威力，我们使用它构建一个最流行的 ZKP：给定公钥(也就是离散对数)的私钥知识。
私钥知识的 ZKP
要将比特币锁定到公钥 / 地址，所有者必须表明他知道相应的私钥。但他不能公开，否则比特币可能被窃取。这是通过数字签名完成的，它是 ZKP²的一种形式。我们将展示使用 zk-SNARK 实现相同目标的另一种方法。
在比特币中，公钥 Q 就是私钥 d 乘以生成器 G。
下面的 Circom 代码实现了比特币椭圆曲线 secp256k1 上的标量乘法。我们可以很容易地用它证明 Q 是 d 的公钥：
将第 3 行的输入标量设置为 d：注意，它是私有的，因此仍然是需要保密的。
将第 4 行的输入点设为 G。
将第 6 行的输出设置为 Q。
// encoded with k registers of n bits eachtemplate Secp256k1ScalarMult(n, k) {signal private input scalar[k];signal public input point[2][k];signal output out[2][k];component n2b[k];for (var i = 0; i < k; i++) {n2b[i] = Num2Bits(n);n2b[i].in <== scalar[i];}// has_prev_non_zero[n * i + j] == 1 if there is a nonzero bit in location [i][j] or higher order bitcomponent has_prev_non_zero[k * n];for (var i = k - 1; i >= 0; i--) {for (var j = n - 1; j >= 0; j--) {has_prev_non_zero[n * i + j] = OR();if (i == k - 1 && j == n - 1) {has_prev_non_zero[n * i + j].a <== 0;has_prev_non_zero[n * i + j].b <== n2b[i].out[j];} else {has_prev_non_zero[n * i + j].a <== has_prev_non_zero[n * i + j + 1].out;has_prev_non_zero[n * i + j].b <== n2b[i].out[j];}}}signal partial[n * k][2][k];signal intermed[n * k - 1][2][k];component adders[n * k - 1];component doublers[n * k - 1];for (var i = k - 1; i >= 0; i--) {for (var j = n - 1; j >= 0; j--) {if (i == k - 1 && j == n - 1) {for (var idx = 0; idx < k; idx++) {partial[n * i + j][0][idx] <== point[0][idx];partial[n * i + j][1][idx] <== point[1][idx];}}if (i < k - 1 || j < n - 1) {adders[n * i + j] = Secp256k1AddUnequal(n, k);doublers[n * i + j] = Secp256k1Double(n, k);for (var idx = 0; idx < k; idx++) {doublers[n * i + j].in[0][idx] <== partial[n * i + j + 1][0][idx];doublers[n * i + j].in[1][idx] <== partial[n * i + j + 1][1][idx];}for (var idx = 0; idx < k; idx++) {adders[n * i + j].a[0][idx] <== doublers[n * i + j].out[0][idx];adders[n * i + j].a[1][idx] <== doublers[n * i + j].out[1][idx];adders[n * i + j].b[0][idx] <== point[0][idx];adders[n * i + j].b[1][idx] <== point[1][idx];}// partial[n * i + j]// = has_prev_non_zero[n * i + j + 1] * ((1 - n2b[i].out[j]) * doublers[n * i + j] + n2b[i].out[j] * adders[n * i + j])// + (1 - has_prev_non_zero[n * i + j + 1]) * pointfor (var idx = 0; idx < k; idx++) {intermed[n * i + j][0][idx] <== n2b[i].out[j] * (adders[n * i + j].out[0][idx] - doublers[n * i + j].out[0][idx]) + doublers[n * i + j].out[0][idx];intermed[n * i + j][1][idx] <== n2b[i].out[j] * (adders[n * i + j].out[1][idx] - doublers[n * i + j].out[1][idx]) + doublers[n * i + j].out[1][idx];partial[n * i + j][0][idx] <== has_prev_non_zero[n * i + j + 1].out * (intermed[n * i + j][0][idx] - point[0][idx]) + point[0][idx];partial[n * i + j][1][idx] <== has_prev_non_zero[n * i + j + 1].out * (intermed[n * i + j][1][idx] - point[1][idx]) + point[1][idx];}}}}for (var idx = 0; idx < k; idx++) {out[0][idx] <== partial[0][0][idx];out[1][idx] <== partial[0][1][idx];}}
为了便于解释，我们使用标准的双加算法。主循环发生在第 33 行到第 65 行。我们在第 42 行使用Secp256k1AddUnequal进行点相加；在 43 行使用Secp256k1Double进行点加倍。在每次迭代中，我们都在第 355-358 行处加倍。如果设置了当前位，我们还会添加。
一旦我们有了 Circom 代码，我们就可以使用通用的 zk-SNARK 库来证明对私钥的知识，同时保持它的机密性。我们已经演示了没有数字签名的方法。
证明组织成员身份
下面，我们将展示如何通过简单地用零知识语言 Circom“编程”实现另一个复杂的密码原语：环签名。
使用 zk-SNARK 的环签名
在环签名中，组 / 环的任何成员都可以签名来证明他们的成员身份，而不需要透露他们的具体身份。基于签名，验证者可以确定组中的一个成员签名，但他不知道是哪个成员签的名。
由于 zk-SNARK 的可编程性和可组合性，我们可以在前面的点乘法库的基础上简单地“编码”环签名，如下所示。
// `n`: chunk length in bits for a private key// `k`: chunk count for a private key// `m`: group member counttemplate Main(n, k, m) {signal private input privkey[k];signal public input pubKeyGroup[m][2][k];signal output existInGroup;// get pubkey from privkeycomponent privToPub = ECDSAPrivToPub(n, k);for (var i = 0; i < k; i++) {privToPub.privkey[i] <== privkey[i];}signal pubkey[2][k];// assign pubkey to intermediate varfor (var i = 0; i < k; i++) {pubkey[0][i] <== privToPub.pubkey[0][i];pubkey[1][i] <== privToPub.pubkey[1][i];}// check whether pubkey exists in groupvar exist = 0;component eq[2*m];var compareResult[m];for (var i = 0; i < m; i++) {// pubkey `x` comparereq[i] = BigIsEqual(k);// pubkey `y` comparereq[i+m] = BigIsEqual(k);for(var j = 0; j < k; j++) {// compare `x`eq[i].in[0][j] <== pubkey[0][j];eq[i].in[1][j] <== pubKeyGroup[i][0][j];// compare `y`eq[i+m].in[0][j] <== pubkey[1][j];eq[i+m].in[1][j] <== pubKeyGroup[i][1][j];}compareResult[i] = eq[i].out * eq[i+m].out;}component checker = InGroupChecker(m);for(var i = 0; i < m; i++) {checker.in[i] <== compareResult[i];}existInGroup <== checker.out;}
从第 11 行到第 22 行，我们使用私钥部分中介绍的 ECDSAPrivToPub 从第 5 行中的私钥派生出第 16 行中的公钥。然后，我们将得到的公钥与第 7 行中定义的组中的每个公钥进行比较。当且仅当它匹配组中第 54 行中的任何一个时，我们返回 true。
由于私钥输入是私有的并且保持隐藏状态，因此验证者不能使用它来识别是哪个成员创建了证明。我们已经创建了一个 ZKP 的成员在组 / 环的环签名，而无需了解任何底层密码学。
ZKKSP
在上面，我们已经展示了如何使用称为 ZK Key-Statement proof (ZKKSP)的技术为以下语句构建零知识证明 (ZKP)。
虽然 ZKKSP 奏效，但它有一个很大的局限性：它只适用于一种特定形式的语句，即 secret 是给定公钥的私钥，而且它也是给定哈希的原映像。目前还不清楚如何将其扩展到一个稍加修改的语句，例如，除了是私钥和原映像之外，secret 也是一个偶数。此外，提出它需要密码学的专利级知识，如∑-protocol 和承诺方案。
ZKKSP 使用 zk-SNARK
我们通过利用 zk-SNARK 的可编程性来重新实现 ZKKSP。我们将证明组织成员身份部分中使用的椭圆曲线点乘法与散列库简单地结合起来。生成的 Circom 代码如下所示：
// library circuits from https://github.com/0xPARC/circom-ecdsainclude "lib-circom-ecdsa/ecdsa.circom";include "../node_modules/circomlib/circuits/sha256/sha256.circom";include "../node_modules/circomlib/circuits/bitify.circom";// `n`: chunk length in bits for a private key// `k`: chunk count for a private keytemplate Main(n, k) {// n * k == 256assert(n * k >= 256);assert(n * (k-1) < 256);// little-endiansignal private input privkey[k];signal public input pubkey[2][k];signal public output privkeyHash[k];// get pubkey from privkeycomponent privToPub = ECDSAPrivToPub(n, k);for (var i = 0; i < k; i++) {privToPub.privkey[i] <== privkey[i];}// verify input pubkeysignal pub_x_diff[k];signal pub_y_diff[k];for (var i = 0; i < k; i++) {pub_x_diff[i] <-- privToPub.pubkey[0][i] - pubkey[0][i];pub_x_diff[i] === 0;pub_y_diff[i] <-- privToPub.pubkey[1][i] - pubkey[1][i];pub_y_diff[i] === 0;}// calculate sha256 of privkeycomponent sha256 = Sha256(256);for (var i = 0; i < k; i++) {for (var j =0; j < n; j++) {// change privkey to big-endian as sha256 inputsha256.in[i * n + j] <-- (privkey[k-1-i] >> (n-1-j)) & 1;}}// set outputcomponent b2n[k];for (var i = 0; i < k; i++) {b2n[i] = Bits2Num(n);for(var j = 0; j < n; j++) {// `b2n` input is little-endian in bits, `sha256` out is big-endian in bitsb2n[i].in[n-1-j] <== sha256.out[i * n + j];}privkeyHash[i] <== b2n[i].out;}}component main {public [pubkey]} = Main(64, 4);
与前面一样，我们在第 15 行使用 ECDSAPrivToPub 从第 14 行的私钥派生出一个公钥。然后我们使用第 3 行导入的 sha256 库中的 Sha256 对相同的私钥进行哈希处理，以确保结果与第 17 行的给定哈希匹配。我们只是“编程”了 ZKKSP，不需要事先了解高级密码学。此外，由于 zk-SNARK 的可组合性，我们可以轻松地对其进行扩展以添加对 secret 的约束。
Source：
https://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-1-9599deb1db47
https://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-2-890869249291
https://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-3-d707dbfa2b28
关于
ChinaDeFi - ChinaDeFi.com 是一个研究驱动的 DeFi 创新组织，同时我们也是区块链开发团队。每天从全球超过 500 个优质信息源的近 900 篇内容中，寻找思考更具深度、梳理更为系统的内容，以最快的速度同步到中国市场提供决策辅助材料。
Layer 2 道友 - 欢迎对 Layer 2 感兴趣的区块链技术爱好者、研究分析人与 Gavin（微信: chinadefi）联系，共同探讨 Layer 2 带来的落地机遇。敬请关注我们的微信公众号 “去中心化金融社区”。
【免责声明】市场有风险，投资需谨慎。本文不构成投资建议，用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
来源链接
