Zenn
⛓️

NFTを用いたCTFを開催したので問題作成者が解説してみる

2021/12/16に公開
ブロックチェーン
Solidity
Ethereum
Bitcoin
#
merkletree
tech

はじめに

この記事は Ethereum Advent Calendar 2021 の 16日目の記事です！

「no plan inc. からの挑戦状」 という記事というか企画を出して、そこそこにバズりそこそこの方に参加いただいたので、どうやって解けるのかという解説記事です。

執筆: @_serinuntius

参加状況

  • q1~q4で記事を執筆してる現在(12/13 15:20)だと、256txが投げられています！
  • q1正解者は88アドレス
  • q2正解者は46アドレス
  • q3正解者は8アドレス(バグがあったのであえて正解できないようにしてq4に移行していただきました)
  • q4正解者は10アドレス
  • 正答率(txを投げた方がfailしてない)で言うと約59%

q1解説

q1はどんな参加者でも直コンしたことがある人であれば解けるぐらいのレベル感にしたいなと思いこのレベルにしています。

解説するまでもないかもしれませんが require(_year == 2021, "This year is 2021"); が肝で_yearという引数に2021を入れれば正解する問題でした。

    function q1(uint _year) external {
        require(_year == 2021, "This year is 2021");
        require(!q1Minted[msg.sender], "Your account has already minted.");

        q1Minted[msg.sender] = true;
        q1NFT.mint(msg.sender);
    }

q2解説

q2はkeccak256の計算と簡単なコントラクトが読みとけるかという問題です。ずっと同じ引数で回答できても面白くないので、mintの回数ごとに変わるようにしています。

    function q2(bytes32 hash) external {
        require(hash == keccak256(abi.encodePacked(q2Hint, q2MintCount)), "Do you know a hash called keccak256?");
        require(!q2Minted[msg.sender], "Your account already minted.");

        q2Minted[msg.sender] = true;
        q2NFT.mint(msg.sender);
        q2MintCount += 1;
    }

模範解答は下記です。もちろん色々な解き方があります！

import { ethers } from "hardhat";
import { utils } from "ethers";
import { defaultAbiCoder } from "ethers/lib/utils";

const HackMe = await ethers.getContractFactory("HackMe");
const hackMe = HackMe.attach("0x....");

const hint = await hackMe.q2Hint();
const q2mintCount = 0;
const encodedSecret = defaultAbiCoder.encode(
  ["bytes32", "uint256"],
  [hint, q2mintCount]
);
const hashedSecret = utils.keccak256(encodedSecret);
console.log(hashedSecret);

q3解説

q3が本当は一番難しい問題で、これでレベルを測ろうと企んでいました。BitcoinのtxをMerkle Rootの中に含まれているということを証明する問題です。

ただこちらの不手際でバグがあり、正攻法じゃない解き方で解かれてしまいました・・・😇

function q3(uint256 blockNumber, uint256 index, bytes32 txid, bytes memory proof) external {
        require(!q3Minted[msg.sender], "Your account already minted.");

        bytes32 root = merkleRoots[blockNumber];
        require(root != NULL, "The root is not registered.");
        require(!usedMerkleRoots[root], "This root has already used.");
        require(ValidateSPV.prove(txid, root, proof, index), "We need to prove that the block contains Tx.");

        q3Minted[msg.sender] = true;
        usedMerkleRoots[root] = true;
        q3NFT.mint(msg.sender);
    }

Merkle TreeはleafがRootの中に含まれているかどうかを証明するのに便利なデータ構造です。

ですが、そのMerkle Rootだけを提出し、leafを空にし0番目のデータであるということことにされて検証が通ってしまいました。。。

        // Shortcut the empty-block case
        if (
            _txid == _merkleRoot &&
            _index == 0 &&
            _intermediateNodes.length == 0
        ) {
            return true;
        }

1時間足らずでq3をゲットされた方がいたので、「そんな早く問題解ける人いるのか」と思って、世の中すごいや〜と思ってたのですが、バグを利用してハックされてると気づくのに時間がかかりましたw

ちゃんとinput dataを見て、「やらかした😇」とすぐにわかりました。

q4解説

q3がバグってたので急いで修正をして追加したのがq4です。q3で本来試したかった知識を問う問題になります。

requireで色々バリデーションがされてますが、最後の方に ValidateSPV.prove というメソッドが呼び出されています。

    function q4(uint256 blockNumber, uint256 index, bytes32 txid, bytes memory proof) external {
        require(!q4Minted[msg.sender], "Your account already minted.");

        bytes32 root = merkleRoots[blockNumber];
        require(root != NULL, "The root is not registered.");
        require(!usedMerkleRoots[root], "This root has already used.");
        require(index > 0, "index gt 0");
        require(proof.length > 0, "Proof is not zero");
        require(ValidateSPV.prove(txid, root, proof, index), "We need to prove that the block contains Tx.");

        q4Minted[msg.sender] = true;
        usedMerkleRoots[root] = true;
        q4NFT.mint(msg.sender);
    }

SPV(Simplified Payment Verification)って聞いたことありますか？簡単にいうとBitcoin等の全部のデータを持たずに、txの検証ができる仕組みです。

つまりq4は、Ethereum(EVM)の上でBitcoinの全ての情報を持つことなく、blockヘッダーの情報のみでtxが有効であるかどうかの検証がしたいという問題です。

そして、既に問題では何かブロックチェーンのMerkle Rootがセットされています。

例えば blockNumber 700000, merkleRoot 659cecf4a06ed500031b741384e87d40ce5c16c3ec8c09b09ffe4b863c218d1f になっています。

おそらくBitcoinの700000blockを見にいく方が多いのではないでしょうか？

どこのエクスプローラーでもいいですが、覗いてみましょう！
https://btc.com/ja/btc/block/700000

https://blockchair.com/bitcoin/block/700000

どちらも 1f8d213c864bfe9fb0098cecc3165cce407de88413741b0300d56ea0f4ec9c65 というMerkle Rootになっています。このブロック高のMerkle Rootと一致していれば問題でセットされているのはBitcoinだと言えるでしょう。

例えば blockNumber 700000, merkleRoot 659cecf4a06ed500031b741384e87d40ce5c16c3ec8c09b09ffe4b863c218d1f になっています。

先程のセットされてるルートと見比べてみましょう。

1f8d213c864bfe9fb0098cecc3165cce407de88413741b0300d56ea0f4ec9c65
659cecf4a06ed500031b741384e87d40ce5c16c3ec8c09b09ffe4b863c218d1f

🤔🤔🤔🤔🤔

どうやら違うようです。

？？？「な〜んだ、Bitcoinと思わせながら、Bitcoinじゃないじゃん！！」

本当にそうですか？

よくよく見てみると、２文字ずつのセットでreverseされてるのがわかります。

上のRootは 1f と 8d と続きますが、下のルートの下の方の桁をみると、確かにreverseされています。

はい、これが今回の罠の1つです。

リトルエンディアンという通常と逆の並びのbytesでコンピューターは計算しています。

例えば適当な16進数の番号があったとします。

12345678

これをlittle-endianで表すと

78563412

になります。

詳しくはこちらに載っています。

https://learnmeabitcoin.com/technical/little-endian

Bitcoinが使われてるとわかれば、あとはMerkle Proofと適当なtxを用意すればいいので、簡単です。

700000ブロックに入っている適当なtxと、Merkle Proofを用意しましょう。

Merkle Proofを用意する

例えば 700000 BlockのMerkle Proofは次のようなAPIで取得することができます。blockstreamが無料でAPIを提供しているようです。もちろんノードを立ててそちらから取得しても構いません。

https://blockstream.info/api/tx/<TX HASH>/merkle-proof

curl https://blockstream.info/api/tx/46951cfd631ff75140c8ec38af1927909dd2e5ed4192500982b591902d7e4fbb/merkle-proof

{
    "block_height": 700000,
    "merkle": [
        "bcf84712500459da1670546601ef7373946fbca624f2e9957a53f5205102a224",
        "45842be09a25fea0391da31dc5ac2ef7e027dd83da10ed3851d430675d4f645d",
        "2e5f8d3ae61d4b18ca4a324a3e48a221a6b51132d6c688ddf314a525e52c1a20",
        "2eb53f93c23a7e8b4ef1b85b15f6954f0a748841fd1d0c462a9e10d177730c95",
        "988629e0a61f25615b91c8e4d1a12d1e0ce138725871d8fb6d0df3b20b808d77",
        "912f6f9fb9869c6dded8f36b618d4c643e7e5fef71543dc85b5ee9a93e0d191a",
        "2bb950e819c228449121bb7645a974c343d595444844bf564d8da3a8ff928a7f",
        "c7aff03f86413b875883a6a973c6406b22717a7f4caf3afc80cd2b91e5a65db1",
        "bad3fc4c8d071cec73c6a7878559e74df4bdd357d93224a0b094bbbb981b876a",
        "ccdff982359d3bfc1334493acad8f1dcb0fd0209c97d27b8b3927b497c178308",
        "53d1e6d928e6ff27e4c2000ae2613515e9087a423c4a446bfb5ac4a13cb5eaf7"
    ],
    "pos": 8
}

このMerkle Proofも例の如くリトルエンディアンにしないといけないので次のようなスクリプトを書くことで反転できます。txhashも反転する必要があるので反転しています。

const node = [
  "bcf84712500459da1670546601ef7373946fbca624f2e9957a53f5205102a224",
  "45842be09a25fea0391da31dc5ac2ef7e027dd83da10ed3851d430675d4f645d",
  "2e5f8d3ae61d4b18ca4a324a3e48a221a6b51132d6c688ddf314a525e52c1a20",
  "2eb53f93c23a7e8b4ef1b85b15f6954f0a748841fd1d0c462a9e10d177730c95",
  "988629e0a61f25615b91c8e4d1a12d1e0ce138725871d8fb6d0df3b20b808d77",
  "912f6f9fb9869c6dded8f36b618d4c643e7e5fef71543dc85b5ee9a93e0d191a",
  "2bb950e819c228449121bb7645a974c343d595444844bf564d8da3a8ff928a7f",
  "c7aff03f86413b875883a6a973c6406b22717a7f4caf3afc80cd2b91e5a65db1",
  "bad3fc4c8d071cec73c6a7878559e74df4bdd357d93224a0b094bbbb981b876a",
  "ccdff982359d3bfc1334493acad8f1dcb0fd0209c97d27b8b3927b497c178308",
  "53d1e6d928e6ff27e4c2000ae2613515e9087a423c4a446bfb5ac4a13cb5eaf7",
];

// reverse
const proof = node
  .map((value) => Buffer.from(value, "hex").reverse().toString("hex"))
  .join("");

const txid = Buffer.from("46951cfd631ff75140c8ec38af1927909dd2e5ed4192500982b591902d7e4fbb", "hex")
	.reverse()
	.toString("hex");
	
await hackMe.q4(700000, 8, "0x" + txid, "0x" + proof);

仕組みや罠に気付ければそんなに難しくないですね！やってること自体はシンプルです。

元ネタ

極度妄想さんのスカウティングICOです。2019年に行われた超難問を解ける人のみが貰える会員証みたいなものでしょうか！

目標調達金額： 0円
目標人数： 100人
トークン利用方法： 後述
時期・場所： 今ここで
対象者：通常解けない問題を解ける人
目的：分散台帳やセキュリティに興味を持つ人の多様性を高める
方法： 以下の問題のどれかを解くと、答えがパスワードになっています。一番先に後述のリンク先でパスワードを入力し、自分だけのパスワードに変更して下さい。すると他の人はもうパスワードを変更できなくなります。
https://leonahioki.medium.com/スカウティングico開催のお知らせ-c702559457cb より引用

当時何問か解こうと思ってチャレンジしてたのですが、全くだめでした😇僕の頭がいかに平凡であるかがわかりましたw

問題も残っているのでチャレンジしてみてください！メンサの方とかが活躍されてたように記憶しています。

仕組み自体はすごく面白くてここからエッセンスを得ています。問題自体もブロックチェーンに載せて、NFTもフルオンチェーンのNFTになってるのが斬新なぐらいでしょうか！

フルオンチェーンNFT

こんな感じでno plan inc.のロゴをフルオンチェーンNFTにしてます。元々ロゴはSVGなので、特に手間をかけることなくフルオンチェーンNFTを作ることができました。




LootのNFTのtokenURIメソッドを参考にさせていただいてます！普通にSVG入れてるだけなので難しいことはしてないですね！

    function tokenURI(uint256 tokenId) public view override(ERC721) returns (string memory) {
        string memory json = Base64.encode(bytes(string(abi.encodePacked('{"name": "Flag #', Strings.toString(tokenId), '", "description": "With this flag, you can prove that you are a Lv', Strings.toString(engineerLevel) ,' blockchain engineer; with Lv1, Lv2, and Lv3 flags, you can skip the job interview at no plan inc. until the final interview.", "image": "data:image/svg+xml;base64,', Base64.encode(bytes(flagSvg)), '"}'))));
        string memory output = string(abi.encodePacked('data:application/json;base64,', json));
        return output;
    }

参加した人の声

https://twitter.com/GaNZnO/status/1464459502447517697?s=20

わざわざblocknumber指定してるということは総当りで計算しろとかtxidが0,1,2,3とかではないんだろうけど、探しても見つからなかったのでふて寝します

https://twitter.com/WakiyamaP/status/1464443120276230148?s=20

https://twitter.com/ocrybit/status/1464434610192986121?s=20

https://twitter.com/arandoros/status/1464426339620900864?s=20

https://twitter.com/IsekaiTaiku/status/1464420576781430784?s=20

https://twitter.com/fujiwaraizuho/status/1464418123881205764?s=20

https://twitter.com/oishun1112_ja/status/1464416827207868420?s=20

https://twitter.com/oishun1112_ja/status/1464415707802714114?s=20

https://twitter.com/mi2valley/status/1464495104882712579?s=20

polygonscanが落ちてしまうというトラブルもw
https://twitter.com/crysis44k/status/1464463260460093440?s=20

https://twitter.com/BCryptomato/status/1464927996880379904?s=20

インタビューしたいって言ってくれた方も！
https://twitter.com/yutakandori/status/1464417335855312902?s=20

https://twitter.com/NowAndNawoo/status/1464924210560520193?s=20

https://twitter.com/arandoros/status/1464917882702159880?s=20

https://twitter.com/0xbakuchii/status/1465656179569295360?s=21

難易度について

https://twitter.com/_serinuntius/status/1465485709293219843?s=20

アンケートとってみましたが、難しかったようです！まあこれぐらいがいいと思ってますw

正直難しすぎて解ける人がいないんじゃないかと危惧してましたが、杞憂でした！ただのMerkle TreeのInclusion Proofなので問題自体はシンプルなのですが、リトルエンディアンで普通は詰むと思うんですよねw

気をつけたほうがよかったかもしれない点

  • フロントランニング耐性(?)
    • これがもっと高級でガチな問題でEthereumなら考えた方がいいかもしれません
    • Polygonならブロックタイムの関係でそんなに問題にならないと考えます
  • q3のバグに気づけたらよかった
    • サクッとレビューも無しに、芹川が作った問題だったのでその辺気をつけたらよかった
    • テストは書いてましたが、攻撃ベクトルのテストが甘かったです・・・

まとめ

想像より盛り上がるイベントになってくれてよかったです！q4は解かれないだろうと思ってリリースしたので防衛してる時はずっとヒヤヒヤしてましたw解かれてからは悔しい気持ちと、解いてくれる人がいるという嬉しい気持ちの狭間でうろうろしてました！解いてくださった方ありがとうございました！

これを解かれた方とTwitterで少し絡ませていただいたのですが、勝手に仲間なんじゃないかという気持ちが湧いてきてました！ これはNFTを作ったりしたクリエイターや、NFTを所有したことがあるコレクターにしか味わうことができない感覚だと個人的には思っています。

no plan inc.ではブロックチェーンを使ったアプリケーションを研究、開発しています！ブロックチェーンに強い興味関心があるエンジニアの方を募集しています！

「Web業界にいてエンジニアの基礎はあるけど、ブロックチェーンは全くわからない！！」

そんな方でも大丈夫です！社内の学習カリキュラムに沿って学習していけば今のところ100%わかるようになっています！

興味ある方は https://twitter.com/_serinuntius　までDMお待ちしております！

Discussion