zk-SNARK:关于私钥、环签名、ZKKSP

语言: CN / TW / HK

私钥

理论上,对于任何数学问题都可以构造一个零知识证明(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 each
template 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 bit
component 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]) * point
for (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 count
template Main(n, k, m) {
signal private input privkey[k];

signal public input pubKeyGroup[m][2][k];
signal output existInGroup;


// get pubkey from privkey
component privToPub = ECDSAPrivToPub(n, k);
for (var i = 0; i < k; i++) {
privToPub.privkey[i] <== privkey[i];
}


signal pubkey[2][k];


// assign pubkey to intermediate var
for (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 group
var exist = 0;
component eq[2*m];
var compareResult[m];


for (var i = 0; i < m; i++) {
// pubkey `x` comparer
eq[i] = BigIsEqual(k);


// pubkey `y` comparer
eq[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-ecdsa
include "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 key
template Main(n, k) {
// n * k == 256
assert(n * k >= 256);
assert(n * (k-1) < 256);


// little-endian
signal private input privkey[k];
signal public input pubkey[2][k];


signal public output privkeyHash[k];


// get pubkey from privkey
component privToPub = ECDSAPrivToPub(n, k);
for (var i = 0; i < k; i++) {
privToPub.privkey[i] <== privkey[i];
}


// verify input pubkey
signal 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 privkey
component sha256 = Sha256(256);
for (var i = 0; i < k; i++) {
for (var j =0; j < n; j++) {
// change privkey to big-endian as sha256 input
sha256.in[i * n + j] <-- (privkey[k-1-i] >> (n-1-j)) & 1;
}
}


// set output
component 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 bits
b2n[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带来的落地机遇。敬请关注我们的微信公众号   “去中心化金融社区”