零知识证明 一

发表于 分类于 阅读次数： Waline： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

介绍

零知识证明的目标是让验证者相信证明者拥有某个秘密(withness)，满足某种关系，而无需向验证者或其他任何人透露秘密本身。

我们可以更具体地认为这是一个程序，表示为C，接受两个输入：C(x, w)。输入x是公共输入，w是秘密见证输入(区块链内一般指交易本身)。该程序的输出是布尔值，即true或false。随后的目标是给出了具体的公共投入x，证明了证明方知道秘密输入w这样C(x,w) == true。

示例程序

假设Bob知道一个散列值H，并且他希望有一个证明，证明Alice知道s的散列的值是H。通常 Alice会通过把s给Bob来证明这一点，之后Bob会重新计算哈希并检查它是否等于H。

但是，假设Alice不想把s透露给Bob，而只是想证明她知道该值。她可以为此使用zk-SNARK。

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

其中w就代表了秘密s，x代表公开值H，C(x, w)就代表了证明(proofs)。Bob只需要验证C(x, w)是否为true即可相信Alice，而无须知道s本身。

zk-SNARK 的定义

一个zk-SNARK由三个算法组成，G, P, V定义如下：

密钥生成器G接受一个秘密参数lambda和一个程序电路C，并生成两个公开可用的密钥，一个证明密钥pk和一个验证密钥vk。这些密钥是公共参数，只需要为给定程序C生成一次。

证明者将P证明密钥pk、公共输入x和隐私见证作输入w。该算法生成证明prf = P(pk, x, w)。

验证者V计算证明prf，如果正确则V(vk, x, prf)返回true，否则返回false。因此，如果证明者知道w，则此函数C(x,w) == true

请注意此处生成器中使用的秘密参数lambda。这个参数有时会让在实际应用中使zk-SNARK变得很棘手。这样做的原因是任何知道这个参数的人都可以生成假证明。具体来说，给定任何程序C和公共输入x，知道lambda的人可以生成一个证明fake_prf，以便在不知道秘密w的情况下使V(vk, x, fake_prf)等于true。

因此，实际运行生成器需要一个非常安全的过程，以确保没有人知道并将参数保存在任何地方。这就是Zcash团队为了生成证明密钥和验证密钥而进行了极其精心的仪式的原因，确保lambda在此过程中被销毁。

给我们的示例使用zk-SNARK

Alice和Bob在实践中如何使用zk-SNARK来证明Alice知道上面例子中的秘密值？

首先，如上所述，我们将使用一个由以下函数定义的程序:

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

Bob的第一步是运行生成器g，以创建验证密钥pk和验证密钥vk。首先随机生成 lambda并使用它作为输入:

(pk, vk) = G(C, lambda)

正如上面所讨论的，必须小心处理lambda参数，因为如果Alice知道lambda的值，她将能够创建伪证明。Bob将与Alice分享pk和vk。

Alice现在将扮演证明者的角色。她需要证明她知道散列到已知hash H的值s。她运行证明算法 P，输入pk,H和s来生成证明prf:

prf = P(pk, H, s)

接下来，Alice把证明文件交给Bob，Bob运行验证函数v(vk,H,prf) ，在这种情况下返回 true，因为Alice完全知道这个秘密。Bob可以确信Alice知道这个秘密，但Alice不需要向Bob透露这个秘密。

可重用的证明和验证密钥

在我们上面的示例中，如果Bob想向Alice证明他知道一个s'，就不能使用上面的过程了。这是因为Alice不知道Bob有没有保存lambda参数。如果保存了，Bob有能力伪造证明。

如果一个程序对许多人有用(比如 Zcash 的例子) ，一个独立于Alice和Bob的可信任的第三方可以运行生成器并创建证明密钥pk和验证密钥vk，这样就没有人知道lambda了。

任何信任这个第三方的人都可以在未来的交互中使用这些密钥。

Ethereum 中的 zk-snark

开发者已经开始将zk-snark集成到Ethereum中。这看起来像什么？具体而言，验证算法（verify）的构建模块以预编译合同的形式添加到Ethereum。用法如下: 生成器链下运行，生成验证密钥和验证密钥。然后，任何证明者都可以使用proving key来创建证明，也是链下运行的。通用验证算法可以在一个智能合约中运行，使用pk、vk和公共输入作为输入参数。验证算法的结果可以用于触发其他链上活动。

这里有一个简单的例子来说明zk-snark如何帮助保护Ethereum上的隐私。假设我们有一个简单Token合约。一般来说，常规的合同（ERC20）是从地址到余额的映射：

mapping (address => uint256) balances;

我们将用余额的散列替换余额，bytes32代替uint256。

mapping (address => bytes32) balanceHashes;

我们不会隐藏交易的发送者或接收者，但是我们可以隐藏余额和发送量。这种财产有时被称为机密交易。

两个zk-snark用于将令牌从一个帐户发送到另一个帐户，一个由发送者创建，一个由接收者创建。（发送者生成发送的proof，接收者生成接收的proof）

通常在一个Token合约中，如果一个交易金额是有效的，我们需要验证以下内容:

balances[fromAddress] >= value

因此，我们也需要在zk-snark证明更新后的哈希值与更新后的余额相匹配。

其主要思想是，发送者将使用他们的startBalance和交易value作为隐私输入，将startBalance、afterBalance和value的哈希作为公共输入。类似地，接收者将startBalance和value作为秘密输入，将startBalance、afterBalance和value的哈希作为公共输入。

下面是我们将用于发送方zk-SNARK的程序，其中与前面一样，x表示公共输入，w表示私有输入。

function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value &&
    sha256(w.value) == x.hashValue &&
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
  )
}

接收方使用的程序如下:

function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  )
}

程序检查发送余额是否大于正在发送的值，并检查所有散列是否匹配。一组可信的人员将为我们的 zk-snark生成证明和验证密钥，我们称之为confTxSenderPk、confTxSenderVk、conftxreceivpk和confTxReceiverPk。

使用zk-snark的Token合约看起来像这样:

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];
  
  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

因此，区块链上唯一的更新是balance的hash，而不是balance本身。然而，我们可以知道所有的balance是正确的更新，因为我们可以检查自己的证明已经验证。

上述机密事务方案主要是给出了一个如何在 Ethereum 上使用 zk-snark 的实例。为了在此基础上创建一个健壮的机密事务方案，我们需要解决一些问题:

  • 用户将需要跟踪他们的余额客户端，如果您失去了余额，这些令牌是不可恢复的。也许可以使用从签名密钥派生的密钥对余额进行链式加密存储。注： 要用户记录自己的w，或存储在链上。
  • 余额需要使用32字节的数据和编码熵的平衡的一部分，以防止能够扭转哈希算出余额。注： 对balanceHash加salt避免字典攻击。
  • 需要处理发送到未使用地址的边缘情况。
  • 为了发送，发送者需要与接收者互动。一个可能有一个系统，其中发送者使用他们的证据来启动交易，和接收者可以看到在块环链上，他们有一个“未决的传入交易”，并可以完成它。注： 必须要有个链下的撮合系统收集发送者和接收者的proof。

参考

https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b