スタンフォード大学 CS251（暗号通貨とブロックチェーン技術）2021年度 期末試験問題
TechFlow厳選深潮セレクト
スタンフォード大学 CS251（暗号通貨とブロックチェーン技術）2021年度 期末試験問題
スタンフォード大学 CS251（暗号通貨とブロックチェーン技術）2021年度 学年末試験問題
Web3業界の深掘り報道に専念し潮流を洞察編集：TechFlow intern
スタンフォードの名誉規約の明文化された規定および精神に従い、私は今回の試験において、いかなる助けも受けず、また他の者にいかなる助けも提供しませんでした。
署名：_________________________
• 本試験は6問からなり、合計100点満点です。
• 規定時間内に試験を完了する必要があります。
• Gradescope (D5GKRX) 上で解答を行ってください。
• 問題への回答は簡潔にしてください。
問題1.（18点）マクロ的問題。
A)→Rollupシステムがすべてのトランザクションをオンチェーンに保存する理由を簡単に説明してください。もしトランザクションデータが失われて、他にバックアップがない場合、どうなるでしょうか？
B)→以下のSolidityコードを見てください：
pragma solidity ^0.8.0;
contract ERC20 is IERC20 {
mapping(address => uint256) private _balances;
event Transfer(address indexed from, address indexed to, uint256 value); function _transfer(address sender, address recipient, uint256 amount) { emit Transfer(sender, recipient, amount);
}}
このコードが2つのコントラクトにデプロイされていると仮定します。1つはアドレスX、もう1つはアドレスYです。次の選択肢の中で、コントラクトXにおいて_balancesの状態を読み取ることができるものはどれですか？正しい答えを（1つ以上）囲んでください。
A コントラクトERC20のアドレスXにおける_transfer()関数内のコード
B コントラクトERC20のアドレスYにおける_transfer()関数内のコード
C etherscan.ioを使用するエンドユーザー
C)→前問に続き、関数_transfer()が呼び出された際に、Transferイベントログを読み取れるのは次のうちどの選択肢ですか？正しい答えを囲んでください。
A ERC20コントラクト内で定義され、アドレスXにあるgetBalance()関数内のコード
B ERC20コントラクト内で定義され、アドレスYにあるgetBalance()関数内のコード
C etherscan.ioを使用するエンドユーザー
D)→2つのイーサリアムトランザクションtx1とtx2が同時に送信されるとき、tx1のmaxPriorityFeeをy、tx2のmaxPriorityFeeを2yに設定すると、tx2は必ずtx1より前にチェーン上で実行されるのでしょうか？答えとその根拠を示してください。tx1およびtx2のmaxFeeは、baseFee + maxPriorityFeeより大きいと仮定してよいものとします。
E)→Aliceは販売業者Bobから車を買いたいと考えています。彼女は1ビットコインをBobのビットコインアドレスに送金します。Bobは、1つ目の入力がAliceのアドレスから来ており、出力の1つがBobのアドレスに紐づく1BTC相当のUTXOであるようなトランザクションを待っています。Bobがビットコインブロックチェーン上にそのトランザクションを見たら、彼は鍵をAliceに渡し、Aliceはその車を運転して帰ります。これは安全でしょうか？Aliceは無料でその車を得ることはできますか？可能であれば、その理由を説明してください。不可能であれば、Bobが支払いを受け取ることを保証するためにどうすべきかを説明してください。
F)→Aliceは新型Yのテスラを1台所有しています。彼女はこれを担保にしてCompoundシステムでローンを組むことは可能でしょうか（売却しないまま）？可能であれば、その方法を説明し、不可能であればその理由を説明してください。
問題2.（20点）Byzantine broadcast.
n人の参加者がおり、n>3とします。そのうち1人が送信者（sender）として指定されています。送信者はビットb∈{0,1}を持っています。broadcastプロトコルとは、各参加者が相互にメッセージを送信し、最終的に各参加者がビットbiを出力するプロトコルであり、iは1,...,nまたは0です。
• プロトコルが一貫性（consistency）を持つとは、任意の2つの正直な参加者について、一方が出力b、他方がb'を出力したとき、b = b'となることを意味します。
• プロトコルが有効性（validity）を持つとは、送信者が正直であれば、すべての正直な参加者の出力が送信者の入力ビットbと一致することを意味します。
• プロトコルが普遍性（universality）を持つとは、ある正直な参加者がビットを出力したならば、最終的にすべての正直な参加者がビットを出力することを意味します。
信頼できるブロードキャストプロトコル（RBC）とは、上記3つの特性を満たすブロードキャストプロトコルです。公開鍵基盤（PKI）が存在すると仮定しており、つまり各参加者は秘密の署名鍵を持っており、他の参加者の正しい公開鍵検証鍵を知っているとします。
同期ネットワークにおいて、以下のブロードキャストプロトコルを考えます：
• ステップ0：送信者は自身の入力ビットbを（署名とともに）他のすべての参加者に送信します。その後、送信者はビットbを出力し、終了します。
• ステップ1：各非送信者iは、送信者から受信した情報を（自身の署名を付けて）他の非送信者に中継します。もし送信者からのメッセージを受信しなかった場合、あるいはメッセージが不正（送信者の署名が無効、またはメッセージが単一のビットではないなど）であった場合は、何も行いません。
• ステップ2：各非送信者は、最大n-1個のメッセージを集約します。これにはステップ0で送信者から直接得たメッセージ1つと、ステップ1で各非送信者から得たメッセージ最大1つずつが含まれます。送信者からの2つの有効署名付きメッセージがあり、それらのビット値が異なる場合（例：一方は0、他方は1）、送信者は不正と判断され、非送信者は0を出力して終了します。逆に、送信者から受信したすべての正当な署名付きビットが同じであれば、非送信者はそのビットを出力します。メッセージを全く受信しなかった場合は、何も出力しません。
以下の問いに対して、攻撃の例を提示するか、攻撃が成立しない理由を説明してください。
A) 不正参加者が最大1人であると仮定した場合、プロトコルは依然として一貫性を持ちますか？
B) 不正参加者が最大1人であると仮定した場合、プロトコルは依然として有効性を持ちますか？
C) 不正参加者が最大2人であると仮定した場合、プロトコルが一貫性を持たないことを示してください。
D) 不正参加者が最大2人であると仮定した場合、プロトコルは有効性を持ちますか？
E) 不正参加者の数が任意であっても、プロトコルは普遍性を持ちますか？
問題3（20点）：オートメーテッド・マーケットメーカー（AMM）。
あなたはUniswap V2の流動性提供者として、DAI/ETHプールに5ETHおよび5000DAIを供給しました。1DAI＝1ドルと仮定すると、あなたの出資金額は合計1万ドルです。
A) 数ヶ月後、1ETHの価格が2000DAIに上昇しました。DAI/ETHプールがこの新たな為替レートに適応し安定した後、流動性提供者としての自分の持分を全額引き出すことにしました。システム手数料はゼロ（φ=1）と仮定すると、あなたはいくらのETHとDAIを受け取ることになりますか？
B) もしあなたが5ETHと5000DAIをそのまま保有していた場合、現在の資産価値は15,000DAIとなり、5000DAIの利益を得ていたことになります。この数ヶ月間、Uniswap V2の流動性提供者として活動した結果、「自分で保有する」戦略と比べてどのような損失を被りましたか？その損失をドル建ての絶対値で表してください（1DAI = 1USDと仮定）。これは「暫定的損失（impermanent loss）」と呼ばれます。ただし、このケースでは損失はかなり永続的です。
C) Uniswap V2の流動性提供者としてxドルの損失を被った場合、そのxドルはどこへ行ったのでしょうか？具体的に、この過程で誰がxドルを得たのでしょうか？
D) 次に、Uniswap V2での取引について考えます。BobがDAI/ETHプールを使って大規模なDAIからETHへの交換を行ったとします。取引後、DAI/ETHプールのDAI残高は以前よりやや多く、ETH残高はやや少なくなりました。そのため、プール内の資産比率が均衡点から少しズレています。
裁定機会（アービトラージチャンス）を発見したAliceは、逆方向の取引を行いプールを再均衡させたいと考えています。彼女はこの取引から利益を得たいので、自分の取引がBobの取引直後に即座に実行されることを確実にしたいと考えています。この戦略は「トレーリング（尾行）」と呼ばれます。
Aliceはどのようにしてこのトレーリング計画を実行できるでしょうか？Aliceの取引がBobの後に即座に実行される可能性が高くなる方法を提案してください。
E) Bobの取引によって生じた裁定機会を捕らえようとする10人の異なる裁定者が、同時に同じトレーリング戦略を実行したとします。彼らはみな、(D)部で説明したのと同じメカニズムを使用しているとしたら、この10人のうち誰が成功するでしょうか？
問題4. [16点]：Hashmasks 再入脆弱性
第8講第3節では、Solidityの再入脆弱性について学びました。本問では、現実世界の興味深い事例を扱います。以下は16,384個のNFTで使用されているSolidityコードの断片です。mintNFT()関数を呼び出すことで、ユーザーは一度に最大20個のNFTを取得できます。すべての内部変数はコンストラクタによって正しく初期化されているものとします（表示されていません）。
function mintNFT(uint256 numberOfNfts) public payable {
require(totalSupply() < 16384, "Sale has already ended");
require(numberOfNfts > 0, "numberOfNfts cannot be 0");
require(numberOfNfts <= 20, "You may not buy more than 20 NFTs at once"); require(totalSupply().add(numberOfNfts) <= 16384, "Exceeds NFT supply"); require(getNFTPrice().mul(numberOfNfts) == msg.value, "Value sent is not correct");
for (uint i = 0; i < numberOfNfts; i++) {
uint mintIndex = totalSupply(); // 発行済みNFT数を取得
_safeMint(msg.sender, mintIndex); // 次のNFTを発行
} }
function _safeMint(address to, uint256 tokenId) internal virtual {
// 1つのNFTを発行し、アドレスtoに割り当てる
require(!_exists(tokenId), "ERC721: token already minted");
_data = _mint(to, tokenId); // NFTを発行し、アドレスtoに割り当てる
_totalSupply ++; // totalSupply() を1増加
if (to.isContract()) {
// アドレスtoにあるonERC721Received()関数を呼び出し、
// NFTの登録が正しく行われたことを確認する
// 引数の詳細はここでは重要ではない
// onERC721Receivedが正しく実装されていれば
// 全て正常なら _ERC721_RECEIVED を返す
bytes4 memory retval=
IERC721Receiver(to).onERC721Received(to, address(0), tokenId, _data);
require(retval == _ERC721_RECEIVED, "NFT Rejected by receiver");
} }
_safeMint関数はその名前とは裏腹にまったく安全でないことを証明しましょう。
A) すでに16,370個のNFTが発行されており、totalSupply() = 16,370であると仮定します。悪意のあるコントラクトがどのようにして16,384個を超えるNFTを偽造できるかを説明してください。攻撃者は最大で何個のNFTを発行できますか？
ヒント：onERC721Receivedの呼び先が悪意を持っている場合、どうなるでしょうか？発行ループを注意深く確認し、再入脆弱性を検討してください。
B) 現在のtotalSupplyの値が16,370であると仮定し、(a)の攻撃を実行する悪意のあるSolidityコントラクトコードを書いてください。
C) この攻撃を防ぐために、前のページのコードのどの行を追加または変更すればよいですか？ただし、1回のトランザクションで20個を超えるNFTが発行されないよう注意してください。
問題5. （15点）ビットコインに関する問題。
A) Lightning Networkプロトコルの利点は、ビットコインネットワークにトランザクションを投稿せずに支払いを実行できることです。Lightning Networkの支払いは最終的にすべてのビットコイン取引を完全に置き換え、ブロックチェーンを不要にするでしょうか？
B) ビットコイントランザクションは一連の入力アドレスと出力アドレスから構成されます。通常、各入力アドレスの鍵は、（署名を除く）トランザクション全体の支払いを承認できます。この署名タイプはSIGHASH_ALLと呼ばれます。
一方、各入力アドレスの鍵を使って、署名を除くTxin（トランザクションの入力部分）のみを署名し、その他は何も署名しないと仮定します。つまり、Txout（出力部分）は署名されません（この署名タイプはSIGHASH_NONEと呼ばれます）。
トランザクションがビットコインネットワークに提出された後、SIGHASH_NONE方式を使用したトランザクションについて、マイナーはその入力アドレスから資金を盗むことができますか？可能であれば、その方法を説明してください。不可能であれば、その理由を説明してください。
C) ECDSA公開鍵のみから、任意のメッセージに対するECDSA署名を偽造する方法が発見された場合、ビットコインにどのような影響がありますか？1つの署名の偽造に30分かかり、高速化できないと仮定します。
問題6.（11点）：Tornado Cash
第14講では、Tornado Cashミキサーについて学びました。Tornado Cashコントラクトは大きなnullifierリストを保存する必要があり、引き出し時にツリーからnullifierを取り出します。引き出し処理中、コントラクトは、引き出されたノートのnullifierが既に引き出されたnullifierリストに含まれていないことを確認する必要があります。含まれていなければ、コントラクトはそのnullifierをセットに追加します。Tornado Cashコントラクトでは、これを次のようにマッピングで実装しています：
mapping(bytes32 => bool) public nullifierHashes;
引き出し処理中、コントラクトは提供されたzk-SNARK証明を検証し、有効であれば以下を実行します：
bytes32 _nullifierHash; // 引き出し中のノートのnullifier require(!nullifierHashes[_nullifierHash], "The note has been spent"); nullifierHashes[_nullifierHash] = true;
A) ツリーからk回の引き出しが成功したと仮定します。イーサリアムトランザクションを検証するマイナーにとって、nullifierHashesマッピングを保存するために必要なストレージ容量は、kの関数としていくらですか？このnullifierHashesマッピング以外に、Tornadoコントラクトが長期ストレージを必要としないと仮定できます。
B) 引き出されたnullifier集合Skをクラウドなどのオンチェーン外に保存できれば理想的です。Tornadoコントラクトは、現在のnullifier集合Skに対する短いコミットメントだけを保存します。withdraw関数呼び出し時、ユーザーは通常のパラメータに加えて、以下を提供します：
• 引き出し対象のコインのnullifier nf がコミットメントされた集合Skに含まれていないこと（nf ∉ Sk）を示す証明π、および
• Tornadoコントラクトが更新されたnullifier集合Sk+1 := Sk U {nf}のコミットメントを計算できる十分な情報
コントラクトはπを検証し（nf ∉ Sk）、Sk+1のコミットメントを計算し、現在のSkのコミットメントを更新されたSk+1のコミットメントで置き換えます。
このような機能を提供するデータ構造はいくつかあります。例えば、Skのコミットメントは32バイトのハッシュ値であり、証明πは2[log₂k]個の32バイトハッシュ値のみを含みます。さらに、この短い証明によりTornadoコントラクトはSk+1の短いコミットメントを計算できます。第7講で紹介したMerkle Patriciaツリーを改変することで実現できますが、ここではその詳細は省略します。
この手法はコントラクトのストレージサイズを大幅に削減しますが、withdraw関数のガスコストを削減できる場合に限り実装価値があります。以下のガスコストを考慮してください：
• ストレージ配列のゼロ項目への書き込み：20,000ガス
• ストレージ配列の非ゼロ項目への書き込み：5,000ガス
• calldata（関数引数のバイト配列）：1バイトあたり16ガス
上記の3項目にかかるガスのみを計算対象とします。現在の実装と比較して、この変更によりkの関数としていくらのガスが節約されるでしょうか？証明πは32 × 2[log₂k]バイトであり、withdraw関数のcalldataの一部として提供されなければならないことを思い出してください。
C) Tornado Cashは、ユーザーが自分のコインを匿名解除できるコンプライアンスツールを提供しています。このツールは、ユーザーの預け入れと特定の引き出しを結びつけるファイルを生成します。中央集権型取引所（Coinbaseなど）がこの資金を受け入れる前に、この文書を提出する必要があるかもしれません。
n人がコインをTornadoプールに預け入れたと仮定し、匿名セットのサイズはn（n=1000と仮定）となります。その後、n人全員がそれぞれ新しいイーサリアムアドレスにコインを引き出します（各アドレスに1コイン）。観察者はどの新しいアドレスがn人のうち誰に対応するか判別できません。したがって、匿名セットのサイズはnです。
しかし、n-1人がコンプライアンスツールを使い、その結果の文書をCoinbaseに送信したと仮定します。これは、最後の一人がプライベートアドレスを保持したい場合、その人物のプライバシーにとってどのような意味を持ちますか？
コースリンク：https://cs251.stanford.edu/
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
