CS 582 STB, Midterm - Iniyan Joseph
0) Academic integrity acknowledgement I certify that I have followed the policies above, have not discussed this midterm with others or used AI tools, and have written all submitted solutions solely myself.
Signature: Iniyan Joseph Date: 11/03/2026
1) Safety and Liveness
1a) Trivial Safety
A trivial protocol which guarantees safety but not liveness is to never append any transaction to the chain. Every validator will agree on the chain, so safety is guaranteed.
1b) Trivial Liveness
A trivial protocol which guarantees liveness but not safety is to append every transaction to the chain. Every transaction will be added to every chain, but there may be forks and conflicts.
1c) Trivial Safety + Liveness assuming honest validators
Assuming honest validators, consensus need not happen for safety. Thus appending every transaction to the chain will be both safe and live.
2) Proof of Work
2a) The honest miners can compute hashes per second in total, and an attacker can compute hashes per second. What is the probability that finds the next block?
Their probability of finding the next block is their share of the total hash, . This is the same reason why selection in proof of stake can directly replace proof of work.
2b) Suppose that the attacker now creates 100 identities and divides its hardware among them. Its total hash power is still hashes per second. What is the probability that finds the next block? How does this compare to “The honest miners can compute hashes per second in total, and an attacker can compute hashes per second. What is the probability that finds the next block?”, and why?
The probability that the attacker finds the next block is the same, since their total hash power is the same (they are not more likely to find the next block). In other words, the probability of computing the next hash is independent of the number of identities.
2c) Suppose that initially, a block is found by some miner every 10 minutes on average.All miners replace their hardware that is twice as fast. What is the expected time between blocks immediately after this change? How would the Bitcoin protocol respond?
The Bitcoin protocol would respond by halving the threshold for mining a block. Since it (in expectation) is twice as difficult to find the valid number needed to mine the next block, the block rate remains 10 minutes.
2d) What is a fork in PoW consensus? Can it occur even when all miners are honest? Explain.
A fork in PoW consensus is when two longest chains are committed. It can happen when all miners are honest, for example, due to network issues (i.e. a partition) that prevent two parts of the network from communicating. Since both are able to make progress independently in longest-change PoW, a fork may occur as the blocks are committed, or when two honest miners mine the same block in a block race.
2e) Give an example of what could go wrong with a chain with a very low block time.
In a chain with very low block time, you are more likely to have another validator mine the same block before the block reaches the whole network, which can create a fork (i.e. a block race). By having a higher block time (and thus harder to mine blocks), you are more likely to be able to communicate the next block to the network before another validator is able to mine the next block.
2f) Suppose that an attacker control 80% of the total hash rate. Explain one way that it can profit.
If an attacker controls 80% of the total hash rate, it can censor all honest transactions and create all blocks. Thus, it can earn all of the block rewards and profit.
2g) Suppose that an attacker has 99% of the hash power. Can it spend coins belonging to an honest user? Explain your answer.
No. Any transaction transferring coins from the honest user’s wallet must be signed by the user’s private key. An attacker will thus not be able to make a valid transaction which will be accepted by the rest of the chain to be committed.
3) Execution
3a) In Bitcoin, who decides which transactions are included in a particular block? How does that party typically choose transactions?
The validator who has mined that block can choose what transactions are included. That validator chooses transactions by doing a greedy knapsack based on the transaction reward and the amount of effort to execute the transaction.
3b) In Ethereum, what does “gas” measure? What happens when a transaction runs out of its gas during execution?
Gas is the unit for paying fees on transactions. When a transaction runs out of gas during execution, it is not added to the block.
3c) Define one property that we would want a transaction fee mechanism (TFM) to satisfy. Give an example of a TFM that satisfies this property and one that does not.
We would want a transaction fee mechanism which satisfies user individual rationality. One example of a TFM that satisfies this property is where . One that does not is where , for example where it charges more than the amount of money transferred.
3d) Consider a mechanism exactly like EIP-1559, except that the base fee is paid to the block producer instead of being burned. What TFM property does it no longer satisfy. Explain.
It no longer follows off-chain-agreement proofness. If the base fee is paid to the block producer instead of being burned, then the block producer can agree to refund the value of the bid off-chain.
4) Rollups
4a) Rollups still post data (e.g., a batch/sequence of transactions) to L1. Why can processing transactions through a rollup be cheaper than executing those transactions directly on L1?
Processing transactions through a rollup can be cheaper than executing transactions directly on L1 since some of the transactions may happen off-chain.
4b) A malicious sequencer submits a state update that gives itself 100 ETH without any valid transaction authorizing it. Compare how a ZK rollup and an optimistic rollup prevent this update from becoming final. What assumptions does each design make?
In an optimistic rollup, this state may not become final if it is disputed by another user. This design assumes that there are watchdogs who catch incorrect state commits and submit proofs of incorrectness. In a ZK rollup, it assumes that there is computing power dedicated to verifying proof of correctness (which only became practical recently).
4c) Describe a mechanism that lets Alice get her transaction included in a rollup even if the sequencer is malicious and wants to censor her transaction.
An optimistic rollup allows for censorship resistance. In this rollup, Alice can get her transaction included in a rollup by challenging the sequencer once the batch L has been executed. Since she can prove that her transaction was added to the batch initially by showing the state after executing the batch.
5) Privacy
5a) What is the difference between pseudonymity and anonymity.
Pseudonymity is being unable to distinguish who owns what account by looking at addresses, since addresses are not tied to identity. Anonymity is being unable to distinguish any information about either agent from a transaction. For example, physical cash is anonymous, since the knowledge of the transaction doesn’t require information from either party.
5b) Describe one heuristic on the Bitcoin transaction graph for breaking privacy.
When tracing UTXOs through a public graph, looking for round numbers can inform who paid any transaction fee, which in turn may indicate who spent the money.
5c) Briefly explain what mixers achieve. How does the design of CoinJoin on Bitcoin differ from that of Tornado Cash on Ethereum?
Mixers achieve privacy by creating a “black box” through which transactions are performed, where many accounts pool their transactions into one and sign together. It is simply a privacy-preserving transaction. In contrast, Tornado Cash is a smart contract, where the sender promises money to the smart contract, and the Zero Knowledge proof is used by the recipient to prove that they are meant to receive the money.
6) Consider an ETH-USDC pool on a constant-product AMM that has no fees. Suppose that it holds and .
6a) What is the marginal price for ETH in this pool?
The marginal price of ETH in this pool is
6b) Suppose a user wanted to sell to the pool. What is the amount of USDC the user will receive in exchange? Ignore fees and gas costs.
If the user wants to sell in the pool, then the new quantity of ETH in the pool is , so the mechanism wants to maintain . The new amount of USD held in the pool is , so they earn .
6c) In what direction should an arbitrageur trade in the AMM?
The arbitrageur should buy ETH, since amount of USDC returned by the AMM in the other direction is less than the value of the initial ETH. In the previous example, the user paid 10 ETH and received the equivalent of 9.09 ETH in USDC.
6d) Find the pool reserves after the optimal arbitrage executes
Assuming ETH is worth 2000 USDC / ETH, the optimal arbitrage ends when , so . And the pool’s reserves are thus
6e) How much profit did the arbitrageur make?
The arbitrageur bought in profit.
7) Liquidations and Leverage
Consider a loan contract where a user can deposit x ETH as collateral and borrow a total of y USDC, up to half the current value of the collateral. If the debt reaches or exceeds two-thirds of the collateral’s value, the position is immediately liquidated: all collateral is sold at the current price, the debt is repaid, and any remaining USDC is returned to the user.
For the numerical calculations, assume liquidation occurs exactly at the price where the debt first equals two-thirds of the collateral’s value.
ETH prices are quoted in USDC per ETH. All portfolio values are measured in USDC. Ignore fees, interest, and price impact.
A user’s net portfolio value is the value of all their assets, including collateral and assets held outside the contract, minus outstanding debt. For parts (a) and (b), ETH initially costs 2,000 USDC. A user deposits 10 ETH, borrows the maximum allowed amount, and keeps all borrowed USDC without spending it or repaying the loan.
7a) At or below what ETH price will liquidation occur? What is the user’s net portfolio value immediately after liquidation? Include the USDC the user kept from borrowing.
If the user deposits ETH as collateral, it can borrow USDC The liquedation will occur when the debt price is above the value of the collateral, i.e. when . This occurs when the value of ETH is .
After the liquidation, since the entire collateral is sold, the net portfolio value is the value of the sold collateral - the debt value. sells for , and the debt is , so the portfolio value is .
7b) After liquidation, ETH rises back to 2,000 USDC. The user makes no further trades. What is their portfolio value now? Explain why the price recovery does or does not restore their initial portfolio value.
Their portfolio value is now . Price recovery does not restore their initial portfolio value, since the value of the debt was much higher relatively when deducted from the collateral.
7c) How can the loan contract obtain the ETH price needed to value its collateral? Describe two different techniques and compare them.
The loan contract can obtain the ETH price needed to value its collateral by forcing the dissolution of the loan or by exchanging its collateral.
Return to the initial setting: the user starts with 10 ETH and ETH costs 2,000 USDC. This time, the user borrows the maximum allowed USDC, uses all of it to buy ETH, and deposits the purchased ETH as additional collateral. They then borrow the maximum additional amount allowed and keep this USDC without spending it or repaying the loan. ETH stays at 2,000 USDC throughout these steps. The user then stops borrowing and trading.
7ci) Find the total ETH collateral and the amount of USDC the user owns outside the lending contract.
Initially, the user owns . The user is able to use this as collateral to borrow USDC. They can use this to buy . They then deposit this as collateral, and borrow . In their wallet at this point, there is , and they have staked .
7cii) If ETH rises to 3,000 USDC, what is the user’s net portfolio value?
If ETH rises to 3000 USDC, then the user’s net portfolio value is .
7ciii) In a separate scenario, ETH falls from 2,000 USDC until the position is liquidated. At what price does liquidation occur, and what is the user’s net portfolio value immediately afterward? Compare this with part (a).
Liquidation occurs when the debt is of the collateral’s value. In this case before the price drop, the collateral is and the debt is . After the price drop, the new total value of the collateral is , and this is triggered when the value of one ETH is . Thus, the user’s net portfolio value is . This is lower than part (a) since they had more of their value staked on the value of ETH being high relative to the dollar.
8) Rate the difficulty of each problem from 1 to 10 and give the approximate time you spent on it in minutes
| # | H | T |
|----|----|----|
| 1 | 1 | 5 |
| 2 | 4 | 20 |
| 3 | 2 | 10 |
| 4 | 2 | 10 |
| 5 | 2 | 10 |
| 6 | 7 | 30 |
| 7 | 6 | 20 |