零知识证明
大约 3 分钟
零知识证明
零知识证明(Zero-Knowledge Proof,简称 ZKP)
保密性: 证明过程中不泄露关键信息,证明者仅向验证者展示所需的证据,而非详细信息。
有效性: 验证者可以使用证明验证断言的真实性,确保证明者提供的证据是有效的。
不可伪造性: 除非证明者拥有相关的真实信息,否则无法伪造出有效的零知识证明。
抽象代数
抽象代数 是数学的一个分支,研究代数结构(如群、环、域等)的性质和运算。它为理解代数对象提供了一个统一的框架,并在计算机科学和密码学中得到了广泛应用。
主要代数结构
群:一个集合及其上的一个运算,满足结合律、单位元和逆元的性质。
- 示例:整数加法群(( \mathbb{Z}, + ))。
环:一个集合及其上的两个运算(加法和乘法),满足特定的性质。
- 示例:整数环(( \mathbb{Z} ))。
域:一个环的特例,其中每个非零元素都有乘法逆元。
- 示例:有理数域(( \mathbb{Q} ))。
ZKP 与抽象代数的关系
零知识证明的设计通常依赖于一些抽象代数的概念,例如:
群论:许多 ZKP 方案使用群的性质,如离散对数问题,这在许多密码学协议中是基础。
同态加密:利用代数结构的性质,在不解密的情况下对加密数据进行计算。
承诺方案:在 ZKP 中,承诺方案允许证明者在不透露信息的情况下承诺某个值,并在后续的步骤中证明这一承诺。
类型
- zk-SNARKs
特点:证明简洁、验证快速、适合实际应用,但通常需要可信设置。
原理:基于算术电路和多项式承诺,通过生成和验证一系列多项式约束来实现零知识证明。
- zk-STARKs
特点:无需可信设置、透明且可扩展,但证明大小和验证时间通常较大。
原理:基于多项式交互证明,通过使用随机化和多项式约束来确保零知识性和可靠性。
使用场景
- 隐私保护的加密货币如 Zcash 利用了 zk-SNARKs 来隐藏交易的发送方、接收方和交易金额。通过零知识证明,用户可以证明他们拥有一定数量的资金并进行交易,而无需公开具体的交易细节。
- ZKP 可以用于去中心化身份验证系统,用户可以证明他们拥有某种属性或资格(如年龄超过18岁、拥有某个证书等),而无需透露更多的个人信息。
- ZKP 可以用于验证数据的完整性和正确性,而不需要暴露数据本身。这在跨链数据共享和数据市场中非常有用。
简单例子
const crypto = require('crypto');
// 生成随机数
function getRandomInt(max) {
return crypto.randomInt(max);
}
// 计算 (base ^ exp) % mod
function modPow(base, exp, mod) {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}
// 零知识证明协议
class ZeroKnowledgeProof {
constructor(p, g, x) {
this.p = p; // 大素数
this.g = g; // 生成元
this.x = x; // 私钥
this.y = modPow(g, x, p); // 公钥
}
// 生成承诺
generateCommitment() {
this.r = getRandomInt(this.p - 1); // 随机数
this.C = modPow(this.g, this.r, this.p); // 承诺
return this.C;
}
// 提出挑战
generateChallenge() {
return getRandomInt(2); // 返回 0 或 1 的随机挑战
}
// 生成响应
generateResponse(challenge) {
if (challenge === 0) {
return (this.x + this.r) % (this.p - 1);
} else {
return this.r;
}
}
// 验证证明
verifyProof(C, challenge, response) {
if (challenge === 0) {
const lhs = (C * this.y) % this.p;
const rhs = modPow(this.g, response, this.p);
return lhs === rhs;
} else {
const lhs = C;
const rhs = modPow(this.g, response, this.p);
return lhs === rhs;
}
}
}
// 使用示例
const p = 23; // 素数
const g = 5; // 生成元
const x = 6; // 私钥
const zkProof = new ZeroKnowledgeProof(p, g, x);
// 生成承诺
const C = zkProof.generateCommitment();
console.log('Commitment:', C);
// 提出挑战
const challenge = zkProof.generateChallenge();
console.log('Challenge:', challenge);
// 生成响应
const response = zkProof.generateResponse(challenge);
console.log('Response:', response);
// 验证证明
const isValid = zkProof.verifyProof(C, challenge, response);
console.log('Proof is valid:', isValid);