零知识证明 - Zkopru Layer2隐私协议介绍

  • Star Li
  • 更新于 2020-09-17 15:38
  • 阅读 2527

Zkopru利用零知识证明在以太坊上实现layer2隐私交易的新方案

最近翻到一篇利用零知识证明在以太坊上实现隐私交易的新方案。Zkopru采用的还是UTXO模型,交易隐私实现的思路和ZCash类似。Zkopru的这篇介绍比较详细的介绍交易的类型,layer1/layer2的交互等等。翻译了一下,方便其他小伙伴查看。对layer2隐私协议感兴趣的小伙伴可以看看。

https://ethresear.ch/t/zkopru-zk-optimistic-rollup-for-private-transactions/7717

很高兴能给大家分享Ethereum的一个隐私层 - Zkopru的实现。去年十一月开始,我和@barryWhiteHat 就开始撰写这个教程,现在终于呈现给大家我们的成果。

特别感谢帮助我们修改,支持这个项目的V, W, K, J, JP, L, and A 等人。

Zkopru是什么?

  • 隐私交易中的一个layer 2解决方案

  • 使用 optimistic rollup来管理区块

  • 使用 zk SNARK 来建立隐私交易

性能

  • Ethereum上每个隐私交易消耗 8800 gas

  • 当gas limit为11.95M,block time为13.2s时,最大TPS是105

功能强大

  • 支持 ETH, ERC20, 甚至是 ERC721

  • 支持 private atomic swap,可用于私人的对盘系统

  • Subtree rollup缩减了更新merkle tree大概20倍的成本

  • 区块结束前即时提取资产

  • 通过使用大量存款和大规模迁移,我们可以构建一个inter-layer-2的网络.

重中之重,来这里试试我们的测试版 https://zkopru.network

简介

Zkopru 使用zk-SNARK和optimistic rollup,是实现隐私交易的layer-2扩展解决方案。Zkopru在layer-2网络中支持ETH, ERC20, ERC721间隐私交易和原子互换,并且成本很低。同时,它的提前支付功能使用户可以在layer-2上状态确定前提取资产。

交易

zk交易接受几种UTXO输入并且创建新的UTXO输出,所以验证UTXO的输入输出是非常重要的步骤。

注:交易采用的是UTXO模型。支持三种交易:一般交易,图的最左边。提取交易,图的最右边,链上交易,layer1和layer2之间。

UTXO输入验证

Zkopru通过使用信息提交-作废协议(commitment-nullifer)实现隐私性。这意味着zk交易在不揭示使用的是哪一个交易(note)的同时使用UTXO。与此相对的,通过生成nullifer,“断开“和UTXO交易的连接。

使用UTXO需要满足以下几个条件:

UTXO 存在性证明

通过提交每一个UTXO的Merkle证明来证明其存在。为了提升SNARK计算的性能,UTXO树使用Poseidon来作为它的hash function。

所有权证明

只有所有者拥有使用UTXO的权限。为达成这个条件,每一个note都有一个公钥(Babyjubjub点)。通过使用对应的密钥,所有者可以创建EdDSA签名来证明他/她的所有权。

Commitment证明

电路需要输入UTXO交易的具体信息来计算输入交易的总和。并且,交易的Poseidon hash值应当与Merkle证明和所有权证明的叶子结点hash值相等。

Nullifier证明

提供的Nullifer应当从输入UTXO中正确计算获取。

UTXO输出验证

zk交易可以产生三种不同的输出:一般UTXO交易(layer2的普通交易),提取交易(layer2中的特殊交易),迁移交易(layer1和layer2交互交易)。如果zk交易产生UTXO交易,将它们加到 UTXO树上。当产生提取交易输出时,Zkopru将它们加到withdrawal 树上。最后,迁移交易,也就是layer-2区块的一部分, 包含了区块中每一个zk交易的迁移输出。

输出交易需要满足以下几点:

  1. 当输出是UTXO交易时,输出的hash值等于SNARK电路上的计算值。

  2. 当输出是withdrawal或迁移,它应该将正确数量的资产移出layer2。

Zero-sum证明

最后,zk交易应当保证UTXO输入和UTXO输出金额相等,包括手续费。

区块结构

区块头信息

区块头372个字节,包含了以下信息:

Property type
Proposer’s address address
Parent block hash bytes32
Metadata uint256
Fee uint256
Latest UTXO tree’s root uint256
Latest UTXO tree’s leaf index uint256
Nullifier tree’s root bytes32
Latest withdrawal tree’s root uint256
Latest withdrawal tree’s leaf index uint256
Transactions’ root bytes32
Deposits’ root bytes32
Migrations’ root bytes32

区块内容

区块内容由交易,充值和迁移组成。而且区块头应该包含了区块的正确信息。如果区块头不正确,区块视为无效。

交易

充值

迁移

账户系统

新的公钥结构正在起草,注意这部分说明会被更新。

Zkopru账户系统同时管理layer-1和layer-2的钥匙串。首先,账户里必须有一个随机生成私钥的Ethereum账户,用来在layer-1上进行操作。其次,Zkopru钱包从Ethereum账户的私钥中创建一个Babyjubjub私钥和公钥对。这个Babyjubjub 钥匙对会被用于EdDSA和layer-2上的加密备忘录字段。

Key 大小 如何得到 在哪使用
Master seed 32 byte 随机生成 恢复钥匙
Ethereum private key 32 byte Master seed通过BIP39派生 Layer1 ECDSA
Ethereum public address 20 byte 私钥派生 Layer 1 操作
Babyjubjub private key 254 bit Ethereum私钥派生 创建EdDSA来使用UTXO
Babyjubjub public key (254 bit, 254 bit) Babyjubjub私钥派生 证明UTXO所有权

UTXO

新的UTXO说明近期将更新

性质 描述
Ether ETH数量
Public Key note所有者的一个Babyjubjub点
Salt 随机salt. Zkopru 使用这个salt生成 UTXO hash
Token Address (Optional) 当包含ERC20或者ERC721代币合同的地址。默认值为0
ERC20 Amount (Optional) 当包含ERC20时ERC20代币的数量,默认值为0
NFT Id (Optional) 当包含ERC721时ERC721代币的ID,默认值为0

然后Zkopru通过Poseidon hash计算Commitment:

var intermediate_hash = poseidon(ether, pub_key.x, pub_key.y, salt)
var result_hash = poseidon(intemediate_hash, token_address, erc20, nft)

接收者如何知道?

一笔zk交易可以包含81字节给接收者的加密备忘录字段。因为零知识的特性,即使是接收者也无法在没有一定操作的情况下了解到这些信息,因此当我们想保持操作的简便性,我们可以在备忘录字段上为接收者添加一些保密信息。

加密

使用Diffie-Hellman密钥交换协议生成共享的钥匙,对于发信者生成共享钥匙的具体步骤如下:

  1. 创建一个临时密钥和其同态计算值
ehemeral = e
public_ephemeral = g^e
  1. 用临时密钥乘以接收者的公钥
recipient_pubkey = g^a
shared_key = (g^a)^e
  1. 准备用于加密的压缩数据
data = {
  salt // 16 byte
  tokenId, // 1 byte
  value, // 32 byte
}
  1. 使用chacha20算法加密数据,并用临时公钥来创建备忘录数据
ephemeral = random.new()
public_ephemeral = generator.multiply(ephemeral)
shared_key = recipient_jubjub.multiply(ephemeral)
ciphertext = chacha20.encrypt(data, shared_key)
memo = public_ephemeral + ciphertext

解密

使用Diffie-Hellman密钥交换协议,接收者同样通过临时公钥和密钥创建共享钥匙。

  1. 解析备忘录,利用私钥获取共享钥匙
public_ephemeral, ciphertext = parse(memo)
shared_key = public_ephemeral.multiply(private_key)
  1. 使用共享钥匙解密密文
decrypted = ciphertext.decrypt(shared_key)
  1. 加密数据仅有49字节以尽量减小数据大小,接收者用解密结果验证多个UTXO的输出。

压缩数据

为了尽量减小数据大小,Zkopru将原始数据压缩成49个字节。首先,公钥不包括在加密信息中,接收者可以用自己的公钥来推断。Zkopru采用代币ID来映射被支持的代币地址,指标范围0~255。value可以是ether,erc20Amount或者nftId。最后,如果推断出的UTXO存在于交易输出的列表中,接收者便能成功收到UTXO。

限制

Zkopru并没有采用电路证明加密协议。因此,如若发交易者没有使用恰当的共享钥匙或数据,接收者将不会收到该货币。

原子交换

Zkopru支持原子交换的方式非常直接。如果A和B想交换他们的资产,他们创建各自的note,并在交易信息中透露适当的数据。然后打包者应当将相对的交易配对或删除。

举个例子,Alice想用她的50ETH换取Bob的1000DAI:

  1. Alice 消费60 ETH币,创建10 ETH币给她自己,50 ETH币给Bob。

  2. Alice 同时为她将收到的1000DAI币计算hash值,并将该数值记录在她交易的swap中。

  3. Bob 消费3000 DAI 币,创建2000 DAI给他自己,1000 DAI币给Alice。

  4. Bob 同时为他将收到的 50 ETH计算hash值,并将该数值记录在他交易的swap中。

  5. 当打包者将交易池中的这两笔交易配对,将交易对打包进一个区块里。

  6. 如果区块只有配对交易的其中一个交易,打包者将被惩罚。

Zkopru采用的是简单版的原子交换。如果你想查看一个MPC的zk原子交换模型,你可以在 这里 读到更多细节。

Merkle树结构

注意Zkopru从下一版本开始将使用深度64的UTXO树和withdrawal树,以替代原本的深度32。

Zkopru森林由UTXO树,nullifier树和withdrawal树组成。

UTXO树是由UTXO组成的仅允许追加的Merkle树。用户可以通过提交包含Merkle证明,使用UTXO作为交易的流入,交易的结果将被加入UTXO树。

同理,如果zk交易创建的是withdrawal输出,Zkopru将它们加入withdrawal树。一旦树的根被标记为确定状态,所有者在证明所有权之后可以提取资产。

随后,依据承诺-无效符方案,被使用的UTXO的无效符会在nullifier树中被标记成已使用, nullifier树是一个唯一稀疏merkle树。如果一笔交易试图使用一个已经废除的叶子,这笔交易将被作废,同时区块提交者将被惩罚。

Merkle树说明

UTXO 树 Nullifier 树 Withdrawal 树
种类 稀疏Merkle树 稀疏Merkle树 稀疏Merkle树
深度 31 256 31
Hash Poseidon Keccak256 Keccak256
How to update 仅许追加,5层深度树rollup SMT rollup 仅许追加,5层深度树rollup
成本(gas/leaf) 180k 351k 5.2k

UTXO 树和 withdrawal 树在Burrito 版本中将有64层深度. https://github.com/zkopru-network/zkopru/issues/35 3

如何管理UTXO树

一个单一的UTXO是为了存在性证明的稀疏Merkle树。它采用的是Poseidon hash,SNARK中最便宜的hash函数之一,来生成zk-SNARK证明以隐藏哈希和它的路径。

协调者采用以下步骤来给UTXO树添加新叶子:1. 准备一个数组;2. 协调者选择添加的MassDeposits并将MassDeposits中每一笔存款加入数组;3. L2交易生成新的UTXO,将新生成的UTXO加入到数组;4. 将准备好的数组打散成chunk size 32;5. 构建子树并执行子树rollup

假定UTXO树由(2^31)项填满,系统封存被填满的树并开始一个新树。被封存的树允许被用作交易存在证明的参考。

Zkopru 积极地更新树的根并仅当挑战存在时进行确认。对于挑战,Zkopru运用子树rollup方法生成链上防欺诈。子树rollup不是一个一个加入,而是将固定大小的子树一次性加入。当子树深度为5时,它将一次加入32个。如果子树仅包含18个,剩下的14个将会永远设置成0值。这个子树rollup的方法相比较于rollup,极大地减小了gas成本——大约20倍。请到 contracts/controllers/challenges/RollUpChallenge.sol查看源代码,想知道子树的运作原理请查看packages/contracts/contracts/libraries/Tree.sol。

无效符树

每一次转账,提取,和迁移交易都使用了包含证明的UTXO,并从树上将派生的nullifier标志成已使用。因此,nullifier树是一个巨大的稀疏Merkle树,在254层深的稀疏Merkle树中记录了使用的UTXO。所以Zkopru 使用了最廉价的keccak256作为 nullifier树的哈希函数。

协调者通过下列步骤来更新nullifier树:

  1. 选择交易(转账,提取,迁移)并收集交易中所有的nullifier。

  2. 确认不存在已被使用的nullifier。

  3. 将所有nullifier标记成已使用。在更新过程中,如果树根没有被任何nullifier改变,废弃这笔交易因为该交易试图尝试双花。

同UTXO树一样,Zkopru积极更新nullifier树根。如果过程存在任何问题,我们可以通过生成一个链上反欺诈来证明nullifier被多次使用,想知道这是如何运作的请查看RollUpChallenge.sol 和 SMT.sol。

Withdrawal树

withdrawal树和UTXO树唯一不同点在于withdrawal tree使用keccak256作为哈希函数,使用keccak256的原因在于Zkopru在智能合约上需要withdrawal树的Merkle证明,同时需要UTXO树的Merkle证明。withdrawal树在layer-1智能合约上树根确定后,可以提取相应的资产。

协调者需要通过下列步骤来更新withdrawal树:

  1. 收集被选出的交易中所有的提取交易

  2. 以32的块大小来打散收集好的交易

  3. 构建子树,进行子树rollup

大额存款

当用户在Zkropu存入资产时会发生什么

  1. Zkopru合约将给定数目的资产从用户账户转移到自己的账户

  2. 确认note具有合法哈希值

  3. 把note合并入MassDeposit[] 清单上最后一项

MassDeposit是什么?

MassDeposit是用于rollup证明的mergedLeaves(bytes32)。如果协调者提出了一个含有 MassDeposits的区块,区块将MassDeposit中所有Note加入它的UTXO Merkle树。

协调者如何处理MassDeposits?

协调器可以只包含确定的不会再改变的MassDeposits。协调者通过监控Deposit 事件来添加MassDeposit。

MassDeposit什么时候变成“承诺的”?

存款需要尽快被推送到layer-2。协调者提出每个新区块时,冻结最新一笔 MassDeposit 。

协调者可以包含多于一个MassDeposit吗?

是的,在最大成本的区间里同时包含多笔MassDeposits是可能的。

大规模迁移

大规模迁移的基本思想很简单。当layer-1合约上的 deposit交易建立一个 MassDeposit对象, “迁移” 类别的交易输出可以创建一个 MassMigration,为目标网络创建 MassDeposit 。

一笔交易可以有UTXO, 迁移, 或提取 类型的输出。

在Zkopru里,针对迁移有源网络和目的网络两个概念。一旦源网络的大规模迁移完成(代码在 这里),源网络上的 migrateTo函数 被执行。这个函数移动包含Ether, ERC20, 和ERC721在内的资产,并在目的网络建立一个MassDeposit对象。

因此,目的网络应当调用 acceptMigration 函数。详情见 这里

rollup间的迁移标准将通过EIP确立。

即时提款

在Zkopru中,取款者可以通过为每个即时提款支付费用完成及时提款。所有人都可以为尚未确定的取款提前支付并得到手续费。

为了申请即时提款,持有人为她的note生成一个ECDSA签名并进行广播。任何持有足够资产的人可以通过使用该签名为此次提款提前支付。一旦Zkopru完成这笔交易,智能合约将所提取note的拥有权转让给支付方。最后,预付方在确定状态后获得支付。

我们可以为即时提款建立一个分散的公开市场。对这个话题有兴趣的话请关注这个github issue https://github.com/zkopru-network/zkopru/issues/33 9](https://github.com/zkopru-network/zkopru/issues/33)

总结

我们就成功地通过Circom, Solidity, Typescript等搭建了测试网:

https://github.com/zkopru-network/zkopru

首先,每笔zk交易的gas费用都是可以我们承担的,平均在8800 gas。当gas limit是11,950,000,block time是13.2秒时,理论TPS最大值为105。在Zkopru中,交易数据仅占534字节。因为证明数据是256字节,在未来我们可以通过证明聚合来减少两倍的交易成本。除此以外,每个区块提出和确定的存储费用分别是168k和55k。当完成350次交易时,这个成本大概是区块生成成本的6.7 %。

此外,运用Optimistic Rollup的灵活性我们可以实现很多功能。第一,Zkopru支持多种交易类型。你甚至可以进行一个输入,四个输出或者四个输入,一个输出的交易。因为Optimistic Rollup灵活性,多种类型的交易是很容易支持。第二,Zkopru实现了pin-point的挑战方式,这意味着如果区块中第n个交易出了问题,挑战会仅仅针对这个交易进行检查。

另一个需要重视的点是Zkopru让你在自己的机器上运行节点。因此SNARK效率和轻节点成为软件开发中需要考虑的很重要的一个环节。相应地,项目是由Typescript和NodeJS实现的,支持未来在react-native架构下移动应用的使用。轻节点期望仅消耗50~100 MB的存储空间。

简而言之,我们希望Zkopru可以在Ethereum的隐私交易层中被采用。它具有快捷,廉价,并且可迁移到更新的版本的特性。

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
Star Li
Star Li
Trapdoor Tech创始人,前猎豹移动技术总监,香港中文大学访问学者。