Magic of ZKP

2023/7/16 Solidity Coding Zkp Cryptography

零知识证明：如何证明你知道一个秘密，而不透露任何信息？

零知识证明是一种神奇的密码学技术，它可以让你向别人证明你知道一个秘密，而不需要透露任何关于秘密的信息。这样，你就可以保护你的隐私和安全，同时让别人相信你的说法。

首先，让我来介绍一下零知识证明的基本原理。零知识证明的过程通常涉及两个参与者：证明者（Prover）和验证者（Verifier）。证明者想要向验证者证明一个陈述是真实的，比如“我知道一个满足某个方程的解”或“我拥有某个加密货币的私钥”。但是，证明者不想透露任何关于这个解或私钥的信息给验证者，也不想让验证者能够重复或复制他的证明。为了做到这一点，证明者和验证者需要遵循一个预先定义好的协议，通过一系列的交互步骤，最终让验证者相信证明者的陈述是正确的，而不泄露任何多余的信息。

想象一下，如果你想向我证明你有一张银行卡，但又不想告诉我卡号和密码，怎么办？你可以用以下方法来做一个零知识证明：

你把银行卡放在一个盒子里，然后把盒子锁上，给我看。
我随机选择一个数字，比如 1234，然后告诉你。
你用你的密码加上我给你的数字，得到一个新的数字，比如 5678，然后用手机登录银行网站，输入这个数字作为验证码，显示登录成功。
你把手机屏幕给我看，让我看到登录成功的提示。
我就相信了你有一张银行卡，而不知道你的卡号和密码。

这个过程就是一个零知识证明，因为我只知道你有一张银行卡，而不知道任何关于卡号和密码的信息。而且，如果你没有一张银行卡，你也无法通过这个过程骗我。

当然，这个例子只是为了说明零知识证明的概念，并不是一个安全的实现。在实际应用中，零知识证明通常涉及更复杂的数学问题和密码学算法。当然，这个例子只是为了说明零知识证明的概念，并不是一个安全的实现。在实际应用中，零知识证明通常涉及更复杂的数学问题和密码学算法。

那么，零知识证明有什么用呢？它可以帮助我们解决很多难题，比如：

隐私交易：通过零知识证明，我们可以在区块链上进行匿名的转账或支付，而不需要公开我们的身份或交易细节。这样，我们就可以享受更高的隐私和安全性。比如混币器和 Tornado Cash 就是利用零知识证明来实现隐私交易的工具。
身份认证：通过零知识证明，我们可以向第三方机构或平台证明我们拥有某些身份属性或资格，而不需要提供具体的证件或信息。这样，我们就可以避免泄露我们的敏感数据或隐私。比如我们可以向银行证明我们年龄超过 18 岁，而不需要提供身份证。
智能合约：通过零知识证明，我们可以让智能合约执行一些复杂的逻辑或计算，而不需要公开所有的输入或输出数据。这样，我们就可以保护我们的商业秘密或隐私数据。比如我们可以向智能合约证明我们满足某些条件或规则，而不需要把条件或规则本身公开。

在数学上如何表示和实现零知识证明呢？我们可以用以下公式来描述：

首先，零知识证明通常使用交互式证明系统，其中一种常见的证明系统是Schwartz-Zippel lemma。这是一个多项式的零知识证明的例子，其中证明者P（Prover）知道一个多项式 (f(x)) 的所有系数，并希望向验证者V（Verifier）证明 (f(a) = b)，而不透露关于多项式 (f(x)) 的任何其他信息。这可以表示为以下的证明过程：

[
$：其中是从一定范围内随机选择的数：其中是从一定范围内随机选择的数：其中是证明者计算的值$
]

然后，验证者通过检查 (s = h + c f(a)) 来验证证明。如果等式成立，则证明被接受。否则，证明被拒绝。这个过程可以重复多次来减小错误的可能性。这个证明过程的零知识性质来自于证明者的承诺对于验证者来说是不可预测的，并且在没有知道 (r) 的情况下，验证者不能从 (s) 中获取任何有关 (f(x)) 的信息。

注意，这里的 "commit" 函数是一个承诺函数，它可以是任何一个安全的哈希函数或者加密函数，它的目的是隐藏其输入的具体内容。在实际的应用中，可能会使用更复杂的承诺方案来实现这个函数。

这个公式表示了零知识证明的三个基本步骤：

Commitment：证明者向验证者发送一个承诺（Commitment），这是一个关于他想要证明的陈述的加密信息，比如一个哈希值或一个加密的证据。这个承诺不能被验证者篡改或伪造，也不能被验证者用来推断出证明者的秘密。
Challenge：验证者向证明者发送一个挑战（Challenge），这是一个随机生成的问题，比如一个数字或一个位串。这个挑战不能被证明者预测或控制，也不能被验证者用来获得证明者的秘密。
Response：证明者根据他的承诺和验证者的挑战，计算出一个响应（Response），并发送给验证者。这个响应是一个关于他想要证明的陈述的有效性的证据，比如一个签名或一个解答。这个响应不能被验证者伪造或重用，也不能被验证者用来获取证明者的秘密。

如果证明者能够正确地回答验证者的挑战，那么验证者就会接受他的证明，并相信他的陈述是真实的。如果证明者不能正确地回答验证者的挑战，那么验证者就会拒绝他的证明，并怀疑他的陈述是假的。这个过程可以重复多次，以提高验证者对证明者的信任度。

为了保证零知识证明的安全性和有效性，它必须满足以下三个性质：

完备性（Completeness）：如果证明者知道秘密，并且遵循协议，那么验证者总是能够接受他的证明。
声明性（Soundness）：如果证明者不知道秘密，或者不遵循协议，那么验证者总是能够拒绝他的证明。
零知识性（Zero-Knowledge）：如果验证者遵循协议，那么他从证明者那里得到的信息，除了证明者知道秘密之外，没有任何其他有用的信息。

零知识性是零知识证明最核心也最难以理解和实现的性质。它要求在协议中，验证者不能从证明者那里学到任何关于秘密或陈述本身的信息，也不能利用交互过程中得到的信息来构造出新的有效的证明。换句话说，验证者在协议结束后，对于秘密或陈述本身，仍然一无所知。

为了形式化地定义零知识性，我们需要引入一个概念叫做模拟器（Simulator）。模拟器是一个算法，它可以在不知道秘密或与真正的证明者交互的情况下，生成与真实交互过程中一样分布的假承诺、假挑战和假响应。如果存在这样一个模拟器，并且它可以在多项式时间内运行，那么我们就说这个协议具有零知识性。

为了说明模拟器是如何工作的，我们可以回到前面提到的银行卡的故事。在这个故事中，你用银行卡、盒子和手机来构造了一个零知识证明。但是我们可以想象有一个模拟器，它可以在不知道你的卡号和密码的情况下，生成一张假银行卡、一个假盒子和一个假手机，然后用这些东西来模拟和我的交互过程。比如，模拟器可以先生成一个随机的卡号和密码，然后用它们来登录银行网站，得到一个真实的验证码。然后，模拟器可以把这个验证码减去我给出的数字，得到一个假密码。最后，模拟器可以把这个假密码和随机的卡号放在盒子里，锁上，给我看。这样，模拟器就生成了一个看起来和真实交互过程一样的假承诺、假挑战和假响应。如果我不能区分出这些是真的还是假的，那么就说明你的证明具有零知识性。

当然，这个例子也只是为了说明模拟器的概念，并不是一个严格的定义。在数学上，我们需要用更精确的方式来描述模拟器的行为和效果。比如，我们可以用以下公式来定义零知识性：

我们通常表示模拟器的存在和行为为：

[
V^* S, (x, w): _{V^*}[P(x, w) V^*(x)] _{V^*}[S(x) V^*(x)]
]

这个公式的意思是，对于任意的验证者 (V^*)，都存在一个模拟器 (S)，使得对于任意的陈述 (x) 和相应的秘密 (w)，验证者在与真实证明者 (P) 的交互中获得的视图（即他看到的所有信息）的分布，与他在与模拟器的交互中获得的视图的分布，是无法区分的。这里的 "视图" 包括了所有的承诺、挑战和响应，以及可能的其他信息。

如果我们回到之前多项式的零知识证明的例子，模拟器可能会这样工作：首先，模拟器会随机选择一个值 (h) 作为承诺，然后，当收到验证者的挑战 (c) 后，模拟器会随机选择一个值 (s) 作为响应。然后，模拟器会计算 (b = s - c h)，并把 (b) 当作 (f(a)) 的值返回给验证者。在这个过程中，模拟器没有使用到多项式 (f(x)) 的任何信息，而是完全随机地生成了所有的承诺和响应。而对于验证者来说，他无法区分这个过程和真实证明者的交互过程，因为在两个过程中，他看到的所有信息的分布是一样的。这就是模拟器的工作原理，也是零知识证明的核心概念。

这个公式表示了对于任意一个验证者（Verifier），都存在一个模拟器（Simulator），使得对于任意一个陈述（x）和秘密（w），以及任意一个承诺（Commitment）、挑战（Challenge）和响应（Response），验证者接受证明者（Prover）的证明的概率，等于验证者接受模拟器生成的假证明的概率。这就意味着验证者无法区分出真实证明和假证明，也就无法从证明者那里获得任何有用的信息。

现在我们已经了解了零知识证明的基本原理和性质，那么我们如何在实际中构造和使用零知识证明呢？事实上，有很多种不同的零知识证明协议，它们各有各的优缺点和适用场景。在这里，我为您介绍三种比较流行和重要的零知识证明协议：SNARKs、STARKs和Bulletproofs。

SNARKs：SNARKs是一种基于非交互式零知识证明（Non-Interactive Zero-Knowledge Proof, NIZK）的协议，它可以让证明者在不与验证者交互的情况下，生成一个短小而高效的证明。SNARKs是一种基于椭圆曲线密码学（Elliptic Curve Cryptography, ECC）和二次剩余问题（Quadratic Residuosity Problem, QRP）的协议，它可以把任意一个可计算问题转化为一个二次方程组（Quadratic Arithmetic Program, QAP），然后用一个椭圆曲线上的点来表示这个方程组的解。SNARKs的优点是它可以生成非常小的证明（通常只有几十个字节），并且验证的速度非常快（通常只需要几毫秒）。SNARKs的缺点是它需要一个可信的设置（Trusted Setup），也就是说，证明者和验证者需要事先生成一些公共参数，并且保证这些参数是安全和随机的。如果这些参数被泄露或篡改，那么就会导致证明的安全性被破坏。SNARKs的一个典型的应用是Zcash，这是一种基于零知识证明的隐私加密货币，它可以让用户在不透露交易双方和金额的情况下，进行匿名的转账或支付。
STARKs：STARKs是一种基于交互式零知识证明（Interactive Zero-Knowledge Proof, IZK）的协议，它可以让证明者和验证者通过多轮的交互，生成一个相对较小而高效的证明。STARKs是一种基于哈希函数（Hash Function）和低度测试（Low-Degree Test, LDT）的协议，它可以把任意一个可计算问题转化为一个多项式（Polynomial），然后用一个哈希值来表示这个多项式的值。STARKs的优点是它不需要一个可信的设置，也就是说，证明者和验证者不需要事先生成任何公共参数，而是可以根据问题本身来动态地生成参数。这样就可以避免可信设置带来的安全风险和成本。STARKs的缺点是它生成的证明相对较大（通常有几百个字节），并且验证的速度相对较慢（通常需要几秒钟）。STARKs的一个典型的应用是StarkWare，这是一种基于零知识证明的可扩展性解决方案，它可以让用户在不牺牲隐私和安全性的情况下，提高区块链上的交易吞吐量和效率。
Bulletproofs：Bulletproofs是一种基于非交互式零知识证明（Non-Interactive Zero-Knowledge Proof, NIZK）的协议，它可以让证明者在不与验证者交互的情况下，生成一个中等大小而高效的证明。Bulletproofs是一种基于椭圆曲线密码学（Elliptic Curve Cryptography, ECC）和内积论证（Inner Product Argument, IPA）的协议，它可以把任意一个可计算问题转化为一个向量（Vector），然后用一个椭圆曲线上的点来表示这个向量的内积（Inner Product）。Bulletproofs的优点是它不需要一个可信的设置，也就是说，证明者和验证者不需要事先生成任何公共参数，而是可以根据问题本身来动态地生成参数。这样就可以避免可信设置带来的安全风险和成本。Bulletproofs的缺点是它生成的证明相对较大（通常有几千个字节），并且验证的速度相对较慢（通常需要几十毫秒）。Bulletproofs的一个典型的应用是Monero，这是一种基于零知识证明的隐私加密货币，它可以让用户在不透露交易双方和金额的情况下，进行匿名的转账或支付。

这下面是一个使用zk-SNARKs实现的简单混币器的Solidity合约示例。

混币器的目的是让用户能够在不公开他们的身份的情况下发送和接收以太币。在这个示例中，我们假设用户会在链下生成一个zk-SNARKs证明，然后把这个证明提交到合约来验证。

pragma solidity ^0.5.0;

// 导入Pairing库，它包含了zk-SNARKs需要的配对函数
import "./Pairing.sol";

contract Mixer {
    using Pairing for *;
    
    // 验证zk-SNARKs证明需要的配对参数
    struct VerifyingKey {
        Pairing.G1Point alpha;
        Pairing.G2Point beta;
        Pairing.G2Point gamma;
        Pairing.G2Point delta;
        Pairing.G1Point[] gammaABC;
    }

    // zk-SNARKs证明
    struct Proof {
        Pairing.G1Point A;
        Pairing.G2Point B;
        Pairing.G1Point C;
    }
    
    VerifyingKey public vk;
    
    mapping(bytes32 => bool) public nullifiers;

    event Deposit(address to, uint amount, bytes32 commitment);
    event Withdrawal(address to, uint amount, bytes32 nullifier);

    constructor(VerifyingKey memory _vk) public {
        vk = _vk;
    }

    function deposit(bytes32 commitment) public payable {
        emit Deposit(msg.sender, msg.value, commitment);
    }
    
    function withdraw(
        uint[] memory input,
        Proof memory proof,
        bytes32 nullifier
    ) public {
        require(!nullifiers[nullifier], "Nullifier has been used");
        // 验证证明，省略了具体的实现
        bool valid = verify(input, proof, vk);
        require(valid, "Invalid proof");
        
        nullifiers[nullifier] = true;
        msg.sender.transfer(input[0]);
        
        emit Withdrawal(msg.sender, input[0], nullifier);
    }
    
    function verify(
        uint[] memory input,
        Proof memory proof,
        VerifyingKey memory vk
    ) public returns (bool) {
        // 验证证明的代码
        // 这部分代码通常会使用Pairing预编译合约提供的函数，以及zk-SNARKs证明的数学原理来实现。
        // 在实际的应用中，这部分代码会根据具体的zk-SNARKs证明系统和应用场景来编写。
        // 这里省略了具体的实现，因为它通常会非常复杂，需要深入理解配对密码学和zk-SNARKs的原理才能编写。
    }
}

在这个混币器合约中：

用户首先在deposit函数中存入一定数量的以太币，并提交一个承诺（commitment）。这个承诺是用户的秘密信息的哈希，它可以用来证明用户有权取回他存入的以太币，但不能用来确定用户的身份。
然后，当用户想取回他的以太币时，他会生成一个zk-SNARKs证明，这个证明可以证明他知道一个承诺的秘密信息，而不需要公开这个信息。然后他在withdraw函数中提交这个证明和一个零知识值（nullifier）。这个零知识值是用户的秘密信息的另一个哈希，它用来防止用户重复取回他的以太币。
合约在withdraw函数中验证用户提交的证明，如果证明有效，合约就把相应的以太币转给用户，并把用户的零知识值记录下来，以防止用户以后再次使用这个值。

当然，这只是一个基本的示例，实际的混币器可能会有更多的功能和细节，比如更复杂的证明系统、多个用户的混合交易、匿名投票等。而且，实现这个合约需要一些高级的密码学知识，包括配对密码学、哈希函数、零知识证明等。

LOADING

Magic of ZKP