Stanford University CS251 (Cryptocurrencies and Blockchain Technologies) 2021 Final Exam
TechFlow Selected TechFlow Selected
Stanford University CS251 (Cryptocurrencies and Blockchain Technologies) 2021 Final Exam
Stanford University CS251 (Cryptocurrencies and Blockchain Technologies) 2021 Final Exam
Navigating Web3 tides with focused insightsCompiled by: TechFlow intern
In accordance with the letter and spirit of Stanford's Honor Code, I have neither given nor received any assistance during this exam.
Signature: _________________________
• This exam contains 6 questions, totaling 100 points.
• You must complete the exam within the allotted time.
• Please answer on Gradescope (D5GKRX).
• Be concise in your answers.
Question 1. (18 points) Macro Questions.
A) → Briefly explain why Rollup systems store all transactions on-chain? What would happen if transaction data were lost and there was no backup elsewhere?
B) → Consider the following Solidity code:
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);
}}
Suppose this code is deployed in two contracts: one at address X and another at address Y. Which of the following options can read the state of _balances in contract X? Circle the correct answer(s) (one or more).
A Code inside the _transfer() function in contract ERC20 at address X
B Code inside the _transfer() function in contract ERC20 at address Y
C An end user using etherscan.io
C) → Continuing from the previous question, which of the following options can read the emitted log entry Transfer when the function _transfer() is invoked? Please circle the correct answer.
A Code in a getBalance() function defined in the ERC20 contract at address X
B Code in a getBalance() function defined in the ERC20 contract at address Y
C An end user using etherscan.io
D) → When two Ethereum transactions tx1 and tx2 are submitted simultaneously, setting the maxPriorityFee of tx1 to y and that of tx2 to 2y, must tx2 be executed before tx1 on-chain? Provide your answer and reasoning. You may assume that both tx1 and tx2 have maxFee greater than baseFee + maxPriorityFee.
E) → Alice wants to buy a car from dealer Bob. She sends 1 Bitcoin to Bob’s Bitcoin address. Bob waits for a transaction where: 1) an input comes from Alice’s address, and 2) one of the outputs is a UTXO bound to Bob’s address worth 1 BTC. As soon as Bob sees this transaction on the Bitcoin blockchain, he gives Alice the keys, and Alice drives away with the car. Is this safe? Can Alice get the car for free? If so, explain how. If not, explain what Bob should do to ensure he gets paid.
F) → Alice owns a brand-new Tesla model Y. Can she currently use it as collateral to take out a loan on the Compound system (without selling it)? If yes, explain how. If not, explain why not.
Question 2. (20 points) Byzantine broadcast.
Suppose there are n parties, with n > 3, and one party is designated as the sender. The sender has a bit b ∈ {0,1}. A broadcast protocol involves parties sending messages to each other, and eventually every party outputs some bit bi, where i can be 1,...,n or 0.
• We say the protocol satisfies consistency if for any two honest parties, if one outputs b and the other outputs b', then b = b'.
• We say the protocol is valid if when the sender is honest, all honest parties output the sender’s input bit b.
• We say the protocol is universal if whenever one honest party outputs a bit, then eventually all honest parties output a bit.
A reliable broadcast protocol (RBC) is a broadcast protocol satisfying these three properties. We assume a public key infrastructure (PKI) exists, meaning each party has a secret signing key and all parties know each other's correct public verification keys.
In a synchronous network, consider the following broadcast protocol:
• Step 0: The sender sends its input bit b (along with its signature) to all other parties. The sender then outputs bit b and terminates.
• Step 1: Each non-sender i forwards to all other non-senders the message it heard from the sender, appending its own signature. If it heard nothing from the sender, it does nothing in this step. Similarly, if the sender’s message is malformed—e.g., the sender’s signature is invalid, or the message is not a single bit—the non-sender does nothing in this step.
• Step 2: Each non-sender collects all messages received, up to n - 1 messages—one possibly from the sender in step 0, and at most one from each non-sender in step 1. If two messages from the sender contain valid signatures but opposite bits (i.e., one signed message has bit 0, another has bit 1), then the sender is dishonest, and the non-sender outputs 0 and terminates. Otherwise, if all correctly signed bits sent by the sender are the same, the non-sender outputs that bit. If the non-sender received no messages, it outputs nothing.
For the following questions, describe an attack or explain why no attack is possible.
A) Assuming at most one dishonest party, does the protocol still satisfy consistency?
B) Assuming at most one dishonest party, does the protocol still satisfy validity?
C) Assume at most two dishonest parties, and show that the protocol fails to achieve consistency.
D) Assuming at most two dishonest parties, does the protocol satisfy validity?
E) For any number of dishonest parties, does the protocol satisfy universality?
Question 3 (20 points): Automated market maker (AMM).
You are a liquidity provider on Uniswap V2, contributing 5 ETH and 5000 DAI to the DAI/ETH pool. Assuming 1 DAI = 1 USD, your total contribution is $10,000.
A) Several months later, the price of 1 ETH rises to 2000 DAI. After the DAI/ETH pool adjusts to this new exchange rate and stabilizes, you decide to withdraw your entire liquidity share. Assuming no fees (∅ = 1), how much ETH and DAI will you receive?
B) If instead you had simply held your 5 ETH and 5000 DAI, your assets would now be worth 15,000 DAI, gaining 5000 DAI in profit. Over these months, compared to the “holding” strategy, what loss did you experience as a Uniswap V2 liquidity provider? Express the loss in absolute dollar terms, assuming 1 DAI = 1 USD. This is known as impermanent loss, although in this case, the loss becomes effectively permanent.
C) If you lost x dollars by being a Uniswap V2 liquidity provider, where did those funds go? Specifically, who gained the x dollars during this process?
D) Now let’s turn to trading on Uniswap V2. Suppose Bob executes a large trade swapping DAI for ETH using the DAI/ETH pool. After the trade, the amount of DAI in the DAI/ETH pool is slightly higher, and the amount of ETH is slightly lower. Thus, the asset ratio in the DAI/ETH pool is somewhat unbalanced from equilibrium.
Arbitrageur Alice spots this opportunity and wishes to execute a trade in the reverse direction to rebalance the pool. She aims to profit from this trade and wants to ensure her transaction is executed immediately after Bob’s. This strategy is called “tailgating.”
How can Alice implement this tailgating plan? Propose a method that gives Alice a reasonable chance of having her transaction executed immediately after Bob’s.
E) Suppose 10 different arbitrageurs, aiming to capture the arbitrage opportunity created by Bob’s trade, simultaneously execute the same tailgating strategy. They all use the same mechanism described in part (D). Which one among the 10 will succeed?
Question 4. [16 points]: Hashmasks Reentrancy Vulnerability
In Lecture 8, Section 3, we discussed Solidity reentrancy vulnerabilities. In this question, we examine an interesting real-world example. Consider the following Solidity code snippet used by 16,384 NFTs. By calling the mintNFT() function on this NFT contract, users can claim up to 20 NFTs at once. You may assume all internal variables are properly initialized by the constructor (not shown).
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(); // get number of NFTs issued so far
_safeMint(msg.sender, mintIndex); // mint the next one
} }
function _safeMint(address to, uint256 tokenId) internal virtual {
// Mint one NFT and assign it to address(to).
require(!_exists(tokenId), "ERC721: token already minted");
_data = _mint(to, tokenId); // mint NFT and assign it to address to
_totalSupply ++; // increment totalSupply() by one
if (to.isContract()) {
// Confirm that NFT was recorded properly by calling
// the function onERC721Received() at address(to).
// The arguments to the function are not important here.
// If onERC721Received is implemented correctly at address(to) then
// the function returns _ERC721_RECEIVED if all is well.
bytes4 memory retval=
IERC721Receiver(to).onERC721Received(to, address(0), tokenId, _data);
require(retval == _ERC721_RECEIVED, "NFT Rejected by receiver");
} }
Let us prove that _safeMint is fundamentally unsafe (despite its name suggesting otherwise).
A) Suppose 16,370 NFTs have already been minted, so totalSupply() = 16,370. Explain how a malicious contract could cause more than 16,384 NFTs to be minted. What is the maximum number of NFTs an attacker could mint?
Hint: What happens if the onERC721Received call at the receiving address is malicious? Carefully examine the minting loop and consider reentrancy vulnerabilities.
B) Assuming the current total supply is 16,370, write Solidity code for a malicious contract that carries out the attack described in part (a).
C) Which line of Solidity code in the above code would you add or modify to prevent your attack? Note that no single transaction should mint more than 20 NFTs.
Question 5. (15 points) Bitcoin Questions.
A) The benefit of the Lightning Network protocol is that payments can be executed without publishing transactions to the Bitcoin network. Will Lightning Network payments eventually replace all Bitcoin transactions entirely, making the blockchain unnecessary?
B) Recall that a Bitcoin transaction has a set of input addresses and a set of output addresses. Typically, each input address signs the entire transaction (excluding the signature itself), authorizing payment. This signature type is called SIGHASH_ALL.
Instead, suppose each input address signs only the Txin (the input portion of the transaction, excluding the signature), and nothing else. That is, the Txout (output portion) is not signed. (This signature type is called SIGHASH_NONE).
After such a transaction is submitted to the Bitcoin network, can miners steal funds from its input addresses using the SIGHASH_NONE method? If yes, explain how. If not, explain why not.
C) If someone discovered a way to forge ECDSA signatures for arbitrary messages given only the ECDSA public key, how would Bitcoin be affected? Assume forging one signature takes 30 minutes and cannot be accelerated.
Question 6. (11 points): Tornado Cash
In Lecture 14, we discussed the Tornado Cash mixer. Recall that the Tornado Cash contract needs to store a large list of nullifiers, adding one each time a note is withdrawn. During withdrawal, the contract must ensure that the note’s nullifier is not already in the list of spent nullifiers. If not, the contract adds this nullifier to the set. Tornado Cash implements this as a mapping:
mapping(bytes32 => bool) public nullifierHashes;
During withdrawal, the contract should verify the provided zk-SNARK proof, and if valid, should:
bytes32 _nullifierHash; // nullifier of note being withdrawn require(!nullifierHashes[_nullifierHash], "The note has been spent"); nullifierHashes[_nullifierHash] = true;
A) Suppose k withdrawals have successfully occurred from the tree. Consider a miner validating an Ethereum transaction. As a function of k, how much storage space must this miner allocate to store the nullifierHashes mapping? You may assume the Tornado contract requires no other long-term storage besides this mapping.
B) It would be better if we could store the set of spent nullifiers Sk off-chain, e.g., in the cloud. The Tornado contract would store only a short commitment to the current set Sk. When calling the withdraw function, the user would provide all current parameters, plus:
• A proof π that the nullifier nf of the coin being withdrawn is not in the committed set Sk, i.e., nf ∉ Sk, and
• Enough information for the Tornado contract to compute an updated commitment to Sk+1 := Sk ∪ {nf}
The contract would verify the proof π that nf ∉ Sk, compute the commitment to Sk+1, and replace the current commitment to Sk with the updated one for Sk+1.
Several data structures offer these features—for example, the commitment to Sk could be a 32-byte hash, and the proof π might consist of only 2[log₂k] 32-byte hashes. This short proof allows the Tornado contract to compute the short commitment to Sk+1. A Merkle Patricia tree, adapted from Lecture 7, provides one such example, though we leave constructing it for later.
While this approach would greatly reduce the contract’s storage footprint, it is only worthwhile if it reduces the gas cost of the withdraw function. Consider the following gas costs:
• Writing a zero entry into storage: 20K gas
• Writing a non-zero entry into storage: 5K gas
• calldata (byte array of function arguments): 16 gas per byte
Assume we only account for gas consumed by the three items listed above. For what values of k does this change save gas when executing a withdrawal? Recall that the proof π is 32 × 2[log₂k] bytes and must be included as part of the calldata for the withdraw function call.
C) Recall that Tornado Cash provides a compliance tool allowing users to de-anonymize their coins: the tool generates a file linking a user’s deposit to a specific withdrawal. This document may need to be submitted to centralized exchanges (like Coinbase) before accepting the funds.
Suppose n people deposit one coin each into a Tornado pool, giving the pool an anonymity set of size n (assume n = 1000). Afterwards, all n individuals withdraw their coins to n new Ethereum addresses (one coin per new address). An observer cannot determine which new Ethereum address corresponds to which of the n individuals, so the anonymity set size remains n.
However, suppose n−1 of them use the compliance tool and send the resulting documents to Coinbase. What does this mean for the privacy of the last person who wishes to keep their address private?
Course link: https://cs251.stanford.edu/
Join TechFlow official community to stay tuned
Telegram:https://t.me/TechFlowDaily
X (Twitter):https://x.com/TechFlowPost
X (Twitter) EN:https://x.com/BlockFlow_News
