### Phase 2: Circuit Compilation and Setup (Bash)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Performs circuit compilation, Groth16 setup, and generates the Verifier.sol contract. Requires circom and snarkjs.

```bash
# Phase 2: 回路コンパイル + Groth16 セットアップ + Verifier.sol 生成
make phase2
# circom circuits/tornado-cats/withdraw.circom --r1cs --wasm --sym -o build
# snarkjs groth16 setup build/withdraw.r1cs build/pot15_final.ptau build/withdraw_0000.zkey
# snarkjs zkey export verificationkey build/withdraw_0001.zkey build/verification_key.json
```

--------------------------------

### Build and Run Docker Container for Tornado Cats

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/intro/introduction.md

Use these Docker commands to build the Tornado Cats image, create a container that mounts the current directory, and start the container. This setup allows for development within a consistent environment.

```bash
docker build . -t tornado-cats
```

```bash
docker create --name tornado-cats -v $(pwd):/home/cat/tornado-cats -it tornado-cats
```

```bash
docker start -ai tornado-cats
```

--------------------------------

### Generate Trusted Setup Parameters with zkUtil

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/appendix/tornado-cash-classic-ceremony.md

Generate the trusted setup parameters for the circuit using zkUtil. These parameters are essential for creating proving and verification keys.

```bash
zkutil setup -c build/circuits/withdraw.json -p build/circuits/withdraw.params
```

```bash
$ zkutil setup -c build/circuits/withdraw.json -p build/circuits/withdraw.params
Loading circuit from build/circuits/withdraw.json...
Generating trusted setup parameters...
Has generated 28300 points
Writing to file...
Saved parameters to build/circuits/withdraw.params
```

--------------------------------

### Initialize Project Dependencies (Bash)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Installs project dependencies using npm and pip. Run this before other make commands.

```bash
# 初回セットアップ（依存パッケージのインストール）
make init
# npm install && pip install -r requirements.txt
```

--------------------------------

### Groth16 Setup Algorithm (Mathematical Representation)

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/groth16.md

Mathematical representation of the Setup algorithm for Groth16, which generates the common reference string (CRS) and simulation trapdoor from a given relation R.

```mathematica
(\sigma, \tau) \leftarrow \operatorname{Setup}(R)
```

--------------------------------

### Example Pairing Check

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/appendix/tornado-cash-classic-contracts.md

Demonstrates how to use the pairing function to check the equality of two aggregated pairings. The example checks if e(P1, P2) * e(P1.negate(), P2) equals 1.

```solidity
pairing([P1(), P1().negate()], [P2(), P2()])
```

--------------------------------

### Groth16 Setup: Common Reference String (CRS) Components

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/groth16.md

Defines the components \sigma_1 and \sigma_2 that form the common reference string \sigma for the Groth16 protocol.

```mathematica
\sigma \coloneqq ([oldsymbol{\sigma}_1]_1,[oldsymbol{\sigma}_2]_2)
```

```mathematica
\boldsymbol{\sigma}_1\coloneqq\left(\begin{array}{c} \alpha, \beta, \delta,\left\lbrace x^i
ight\rbrace_{i=0}^{n-1},\left\lbrace \frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}
ight\rbrace_{i=0}^{\ell} , \left\lbrace\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}
ight\rbrace_{i=\ell+1}^m,\left\lbrace\frac{x^i t(x)}{\delta}
ight\rbrace_{i=0}^{n=2} \end{array}\right)
```

```mathematica
\boldsymbol{\sigma}_2\coloneqq\left(\beta, \gamma, \delta,\left\lbrace x^i
ight\rbrace_{i=0}^{n-1}\right)
```

--------------------------------

### Export Proving and Verification Keys with zkUtil

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/appendix/tornado-cash-classic-ceremony.md

Export the proving key and verification key from the circuit and setup parameters using zkUtil. These keys are used for generating and verifying zero-knowledge proofs.

```bash
zkutil export-keys -c build/circuits/withdraw.json -p build/circuits/withdraw.params -r build/circuits/withdraw_proving_key.json -v build/circuits/withdraw_verification_key.json
```

```bash
$ zkutil export-keys -c build/circuits/withdraw.json -p build/circuits/withdraw.params -r build/circuits/withdraw_proving_key.json -v build/circuits/withdraw_verification_key.json
Exporting build/circuits/withdraw.params...
Created build/circuits/withdraw_proving_key.json and build/circuits/withdraw_verification_key.json.
```

--------------------------------

### Compile Circuit with Circom

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/appendix/tornado-cash-classic-ceremony.md

Use Circom to compile the withdrawal circuit definition into a JSON file. This step is necessary before generating setup parameters.

```bash
npx circom circuits/withdraw.circom -o build/circuits/withdraw.json
```

```bash
$ npx circom circuits/withdraw.circom -o build/circuits/withdraw.json
Constraints: 10000
Constraints: 20000
Constraints: 30000
Constraints: 40000
Constraints: 50000
```

--------------------------------

### Groth16 Setup: Trapdoor Generation

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/groth16.md

Generates the simulation trapdoor \tau by selecting random elements \alpha, \beta, \gamma, \delta, x from the finite field Z_p^*.

```mathematica
 \alpha, \beta, \gamma, \delta, x \leftarrow \mathbb Z_p^* 
```

```mathematica
\tau\coloneqq(\alpha, \beta, \gamma, \delta, x)
```

--------------------------------

### Generate Witness using Node.js

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/witness-computation.md

Use this command to generate a witness file (`.wtns`) from a WebAssembly circuit, input JSON, and an output file name. Ensure you are using string representations for large integers.

```bash
node multiplier2_js/generate_witness.js multiplier2_js/multiplier2.wasm input.json witness.wtns
```

--------------------------------

### Get R1CS Info with snarkjs

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/r1cs.md

Use `snarkjs r1cs info` to display metadata about an R1CS file, such as the number of wires, constraints, and inputs.

```bash
$ snarkjs r1cs info
 multiplier2.r1cs
[INFO]  snarkJS: Curve: bn-128
[INFO]  snarkJS: # of Wires: 4
[INFO]  snarkJS: # of Constraints: 1
[INFO]  snarkJS: # of Private Inputs: 2
[INFO]  snarkJS: # of Public Inputs: 0
[INFO]  snarkJS: # of Labels: 4
[INFO]  snarkJS: # of Outputs: 1
```

--------------------------------

### Create Deposit Data (JavaScript)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Generates deposit data including nullifier, secret, preimage, commitment, and nullifier hash. Requires crypto and circomlib.

```javascript
// cli/cli.js — createDeposit の実装
const rbigint = nbytes => snarkjs.bigInt.leBuff2int(crypto.randomBytes(nbytes))
const pedersenHash = data => circomlib.babyJub.unpackPoint(
    circomlib.pedersenHash.hash(data)
)[0]

function createDeposit({ nullifier, secret }) {
    const deposit = { nullifier, secret }
    deposit.preimage      = Buffer.concat([
        deposit.nullifier.leInt2Buff(31),
        deposit.secret.leInt2Buff(31)
    ])
    deposit.commitment    = pedersenHash(deposit.preimage)
    deposit.commitmentHex = toHex(deposit.commitment)
    deposit.nullifierHash = pedersenHash(deposit.nullifier.leInt2Buff(31))
    deposit.nullifierHex  = toHex(deposit.nullifierHash)
    return deposit
}

// 呼び出し例
const deposit = createDeposit({ nullifier: rbigint(31), secret: rbigint(31) })
```

--------------------------------

### Generate Merkle Proof Input (JavaScript)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Generates input JSON for Circom circuits by calculating Merkle proofs from deposit events. Requires fs and merkleTree.

```javascript
// cli/cli.js — generateMerkleProof と generateInput の実装
function generateMerkleProof(depositEventsJsonPath, leafIndex) {
    const depositEventsJson = JSON.parse(
        fs.readFileSync(__dirname + "/../" + depositEventsJsonPath)
    )
    const leaves = depositEventsJson.commitments.map(
        commitment => bigInt(commitment).toString()
    )
    const tree = new merkleTree(MERKLE_TREE_HEIGHT, leaves)  // 高さ20
    const { pathElements, pathIndices } = tree.path(leafIndex)
    return { pathElements, pathIndices, root: tree.root() }
}

async function generateInput({
    depositEventsJsonPath, nullifier, nullifierHash,
    secret, leafIndex, recipient, relayerAddress = 0, fee = 0
}) {
    const { root, pathElements, pathIndices } = 
        generateMerkleProof(depositEventsJsonPath, leafIndex)

    return {
        root,
        nullifierHash: bigInt(nullifierHash).toString(),
        recipient:     bigInt(recipient).toString(),
        relayer:       bigInt(relayerAddress).toString(),
        fee:           bigInt(fee).toString(),
        nullifier:     bigInt(nullifier).toString(),
        secret:        bigInt(secret).toString(),
        pathElements,
        pathIndices,
    }
}
```

--------------------------------

### Generate ZK Proof with Snarkjs

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/generation-and-verification.md

Use this command to generate a zero-knowledge proof. Ensure you have the necessary key and witness files.

```bash
snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json
```

--------------------------------

### Groth16 Sim Algorithm (Mathematical Representation)

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/groth16.md

Mathematical representation of the Sim (Simulator) algorithm, which generates a proof \pi for a given relation R, trapdoor \tau, and statement a_1,...,a_l without needing the full witness.

```mathematica
\pi \leftarrow \operatorname{Sim}(R, \tau, a_1, \ldots, a_{\ell})
```

--------------------------------

### End-to-End Test: Deposit and Withdraw

Source: https://context7.com/minaminao/tornado-cats/llms.txt

This test orchestrates a full deposit-to-withdrawal cycle within a Solidity test environment using `vm.ffi` to call external scripts. It covers deposit generation, on-chain deposit, proof input generation, witness calculation, Groth16 proof generation, and on-chain withdrawal verification.

```Solidity
// contracts/test/TornadoCats.t.sol
// 実行: forge test -vvv --match-test testDepositAndWithdraw

function testDepositAndWithdraw() public {
    // 1. デポジットオブジェクトの生成（Node.js CLI）
    string[] memory cmds = new string[](3);
    cmds[0] = "node"; cmds[1] = "cli/cli.js"; cmds[2] = "gen-deposit";
    string memory depositJson = string(vm.ffi(cmds));

    bytes32 commitment = depositJson.readBytes32(".commitment");
    uint256 nullifier  = depositJson.readUint(".nullifier");
    uint256 nullifierHash = depositJson.readUint(".nullifierHash");
    uint256 secret     = depositJson.readUint(".secret");

    // 2. コントラクトにデポジット（1 ETH）
    vm.recordLogs();
    tornadoCats.deposit{value: 1 ether}(commitment);
    Vm.Log[] memory logs = vm.getRecordedLogs();
    (uint32 leafIndex,) = abi.decode(logs[0].data, (uint32, uint256));

    // 3. Merkleプルーフを含む証明インプットを生成（Node.js CLI）
    cmds = new string[](9);
    cmds[0] = "node"; cmds[1] = "cli/cli.js"; cmds[2] = "gen-input";
    cmds[3] = "tmp/deposit_events.json";
    cmds[4] = Strings.toHexString(nullifier);
    cmds[5] = Strings.toHexString(nullifierHash);
    cmds[6] = Strings.toHexString(secret);
    cmds[7] = Strings.toHexString(leafIndex);
    cmds[8] = Strings.toHexString(address(0xdeadbeaf));
    string memory inputJson = string(vm.ffi(cmds));
    vm.writeFile("tmp/input.json", inputJson);

    // 4. Wasmウィットネス計算
    cmds = new string[](5);
    cmds[0] = "node";
    cmds[1] = "build/withdraw_js/generate_witness.js";
    cmds[2] = "build/withdraw_js/withdraw.wasm";
    cmds[3] = "tmp/input.json"; cmds[4] = "build/witness.wtns";
    vm.ffi(cmds);

    // 5. snarkjs でGroth16証明を生成
    cmds = new string[](7);
    cmds[0] = "snarkjs"; cmds[1] = "groth16"; cmds[2] = "prove";
    cmds[3] = "build/withdraw_0001.zkey"; cmds[4] = "build/witness.wtns";
    cmds[5] = "build/proof.json"; cmds[6] = "build/public.json";
    vm.ffi(cmds);

    // 6. Pythonで証明をABIエンコード変換
    cmds = new string[](2);
    cmds[0] = "python"; cmds[1] = "cli/gen_proof_calldata.py";
    vm.ffi(cmds);

    // 7. 出金実行と残高確認
    bytes memory proof = vm.readFile("tmp/proof_calldata.json")
        .readBytes(".proof");
    uint256 root = stringToUint(inputJson.readString(".root"));
    address recipient = address(0xdeadbeaf);

    assertEq(recipient.balance, 0);
    tornadoCats.withdraw(
        proof, bytes32(root), bytes32(nullifierHash),
        payable(recipient), payable(address(0)), 0
    );
    assertEq(recipient.balance, 1 ether);  // 出金後に1 ETHが受け取られていること
}

```

--------------------------------

### Verify ZK Proof with Snarkjs

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/generation-and-verification.md

Use this command to verify a generated zero-knowledge proof. This requires the verification key, public inputs, and the proof itself.

```bash
snarkjs groth16 verify verification_key.json public.json proof.json
```

--------------------------------

### Compile Circom Circuit

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/compile.md

Use this command to compile a .circom file. The flags generate necessary files for R1CS, WebAssembly witness generation, debugging symbols, and C++ code.

```bash
circom multiplier2.circom --r1cs --wasm --sym --c
```

--------------------------------

### Implement Deposit Function

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/mixer/mixer-contract.md

Implement the deposit function logic. This includes checking for duplicate commitments, verifying the deposit amount against the denomination, inserting the commitment into the Merkle tree, registering the commitment, and emitting a Deposit event.

```solidity
function deposit(bytes32 commitment) external payable {
        require(!isCommitmentKnown(commitment), "Commitment already exists");
        require(msg.value == denomination, "Invalid deposit amount");

        merkleTree.insert(commitment);
        knownCommitments[commitment] = true;

        emit Deposit(commitment, msg.sender, denomination);
    }
```

--------------------------------

### Generate Input JSON Command (Bash)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Command-line usage for generating input JSON for Circom circuits. Takes deposit events, nullifier, secret, and other parameters.

```bash
# 使用例
node cli/cli.js gen-input \
  tmp/deposit_events.json \
  0x1a2b3c... \   # nullifier
  0xaabbcc... \   # nullifierHash
  0xdeadbe... \   # secret
  0x0 \           # leafIndex (16進数)
  0xdeadbeaf      # recipient アドレス
```

--------------------------------

### Encode Proof Data for Solidity (Python)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Converts Groth16 proof and public inputs into ABI-encoded bytes for Solidity contracts. Uses subprocess and json.

```python
# cli/gen_proof_calldata.py
import subprocess, json

# snarkjs generatecall で proof と public input を結合文字列として取得
call = subprocess.run(
    'snarkjs generatecall build/public.json build/proof.json'.split(),
    capture_output=True, text=True
).stdout

# タプル (a, b, c, input) としてパース
a, b, c, _input = eval(call)

# a[0], a[1], b[0][0], b[0][1], b[1][0], b[1][1], c[0], c[1] を結合して packed bytes に変換
proof = (
    a[0][2:] + a[1][2:]
    + b[0][0][2:] + b[0][1][2:] + b[1][0][2:] + b[1][1][2:]
    + c[0][2:] + c[1][2:]
)

# tmp/proof_calldata.json に保存
json.dump({"proof": "0x" + proof}, open("tmp/proof_calldata.json", "w"))

# 使用例（Foundryテスト内）:
# python cli/gen_proof_calldata.py
# string memory proofJson = vm.readFile("tmp/proof_calldata.json");
# bytes memory proof = proofJson.readBytes(".proof");
# tornadoCats.withdraw(proof, bytes32(root), bytes32(nullifierHash), payable(recipient), ...);
```

--------------------------------

### Phase 1: Powers of Tau Ceremony (Bash)

Source: https://context7.com/minaminao/tornado-cats/llms.txt

Executes the first phase of the Powers of Tau ceremony for generating cryptographic constants. Supports up to 2^15 constraints.

```bash
# Phase 1: Powers of Tau セレモニー（2^15 制約まで対応）
make phase1
# snarkjs powersoftau new bn128 15 build/pot15_0000.ptau -v
# openssl rand -hex 10 | snarkjs powersoftau contribute build/pot15_0000.ptau build/pot15_0001.ptau
# snarkjs powersoftau prepare phase2 build/pot15_0001.ptau build/pot15_final.ptau -v
```

--------------------------------

### Proof Generation Algorithm (Groth16)

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/mixer/design.md

The prover generates a proof $\pi$ using the Prove algorithm. This algorithm requires knowledge of the nullifier, secret, Merkle opening, and index, along with other parameters like the recipient and relayer addresses and fees.

```plaintext
$\pi \leftarrow \operatorname{Prove}(\sigma, R,\mathrm{nullifierHash},A_{\mathrm{recipient}},A_{\mathrm{relayer}},f,\mathrm{nullifier},\mathrm{secret},O_l,l)$
```

--------------------------------

### Withdraw Circuit for Groth16 Proof Generation

Source: https://context7.com/minaminao/tornado-cats/llms.txt

This Circom circuit generates Groth16 proofs for withdrawals. It verifies the existence of a deposit and the validity of the nullifier by taking public inputs like root, nullifierHash, recipient, relayer, fee, and private inputs such as nullifier, secret, and Merkle path elements.

```circom
// circuits/tornado-cats/withdraw.circom
// 使用方法: circom circuits/tornado-cats/withdraw.circom --r1cs --wasm --sym -o build

template Withdraw(levels) {
    // ---- パブリック入力 ----
    signal input root;           // Merkleルート
    signal input nullifierHash;  // Pedersen(nullifier)
    signal input recipient;      // 出金先アドレス
    signal input relayer;        // リレイヤーアドレス
    signal input fee;            // リレイヤー手数料

    // ---- プライベート入力 ----
    signal input nullifier;              // 248ビット秘密乱数
    signal input secret;                 // 248ビット秘密乱数
    signal input pathElements[levels];   // Merkleパス要素
    signal input pathIndices[levels];    // Merkleパスインデックス

    // コミットメントとヌリファイアハッシュの計算・検証
    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret    <== secret;
    hasher.nullifierHash === nullifierHash;  // ヌリファイアハッシュの制約

    // Merkleプルーフの検証
    component tree = MerkleTreeChecker(levels);
    tree.leaf <== hasher.commitment;
    tree.root <== root;
    for (var i = 0; i < levels; i++) {
        tree.pathElements[i] <== pathElements[i];
        tree.pathIndices[i]  <== pathIndices[i];
    }

    // recipient / fee / relayer を回路に結びつける（フロントランニング対策）
    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    recipientSquare <== recipient * recipient;
    feeSquare       <== fee * fee;
    relayerSquare   <== relayer * relayer;
}

component main {public [root, nullifierHash, recipient, relayer, fee]} = Withdraw(20);

```

--------------------------------

### Verification Algorithm (Groth16)

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/mixer/design.md

The Verify algorithm checks if a given proof $\pi$ is valid. It returns 1 for acceptance and 0 for rejection, ensuring that the prover knows the necessary secrets and that all parameters match the expected values.

```plaintext
$0/1 \leftarrow \operatorname{Verify}(\sigma,R, \mathrm{nullifierHash},A_{\mathrm{recipient}},A_{\mathrm{relayer}},f,\pi)$
```

--------------------------------

### Checking QAP Properties with Polynomial Division

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/qap.md

Verifies if a QAP is valid by checking if the polynomial (w*a')*(w*b') - w*c' is divisible by the product of (x-i) for all constraint indices. This confirms the integrity of the witness.

```python
z = (x-1)*(x-2)*(x-3)*(x-4)
w = vector([1, 3, 35, 9, 27, 30])
f = w.dot_product(ap) * w.dot_product(bp) - w.dot_product(cp)
f.quo_rem(z)
```

--------------------------------

### Successful ZK Proof Verification Output

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/circuit/generation-and-verification.md

This output indicates that the zero-knowledge proof has been successfully verified. It confirms the validity of the proof and the underlying statement.

```bash
$ snarkjs groth16 verify verification_key.json public.json proof.json
[INFO]  snarkJS: OK!
```

--------------------------------

### Run Contract Tests

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/mixer/mixer-contract.md

Execute this command to run all tests for the TornadoCats contract. Ensure all tests pass to confirm correct implementation.

```bash
forge test -vvv
```

--------------------------------

### Groth16 Prove Algorithm (Mathematical Representation)

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/zkp-theory/groth16.md

Mathematical representation of the Prove algorithm, which takes the relation R, CRS \sigma, and witness values a_1,...,a_m to output a proof \pi.

```mathematica
\pi \leftarrow \operatorname{Prove}(R, \sigma, a_1, \ldots, a_m)
```

--------------------------------

### Helper Functions for Points P1 and P2

Source: https://github.com/minaminao/tornado-cats/blob/main/book-src/appendix/tornado-cash-classic-contracts.md

Provides specific point coordinates for G1 and G2 groups used in pairing operations. P1 is a point in G1, and P2 is a point in G2.

```solidity
function P1() internal returns (G1Point) {
        return G1Point(1, 2);
    }
    function P2() internal returns (G2Point) {
        return G2Point(
            [11559732032986387107991004021392285783925812861821192530917403151452391805634,
             10857046999023057135944570762232829481370756359578518086990519993285655852781],
            [4082367875863433681332203403145435568316851327593401208105741076214120093531,
             8495653923123431417604973247489272438418190587263600148770280649306958101930]
        );
    }
```