Zhuang's Diary

CS251_Final_Exam_2021-stanford.edu-2

Posted on 2022-03-11 Edited on 2022-03-31

Problem 2. [20 points]: Byzantine broadcast.

Consider n parties, where n ≥ 3, and where one of the parties is designated as a sender. The sender has a bit b ∈ {0, 1}. A broadcast protocol is a protocol where the parties send messages to one another, and eventually every party outputs a bit bi , for i = 1, . . . , n, or outputs nothing.

We say that the protocol has consistency if for every two honest parties, if one party outputs b and the other outputs b’ , then b = b’ .
We say that the protocol has validity if when the sender is honest, the output of all honest parties is equal to the sender’s input bit b.
We say that the protocol has totality if whenever some honest party outputs a bit, then eventually all honest parties output a bit.

A reliable broadcast protocol (RBC) is a broadcast protocol that satisfies all three properties. Let us assume that there is a public key infrastructure (PKI), meaning that every party has a secret signing key, and every party knows the correct public signature verification key for every other party.

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 its bit b and terminates.
step 1: Every non-sender party i echoes what it heard from the sender to all the other non-sender parties (with i’s signature added). If the party heard nothing from the sender, it does nothing in this step. Similarly, the party does nothing in this step if the sender’s message is malformed: for example, if the sender’s signature is invalid, or the message is not a single bit.
step 2: Every non-sender party collects all the messages it received (up to n−1 messages, with at most one from the sender in step 0 and at most one from each non-sender party in step 1). If some two of the received messages contain a valid signature by the sender, but for opposite bits (i.e., in one signed message the bit is 0 and in the other signed message the bit is 1) then the sender is dishonest and the party outputs 0 and terminates. Otherwise, all the properly signed bits from the sender are the same, and the party outputs that bit. If the non-sender received no messages, it outputs nothing.

For each of the following questions, describe an attack or explain why there is no attack.

A) If there is at most one dishonest party, does the protocol have consistency?

answer - a dishonest party have options as below in step 1 & 2 to cheat a honest part:

don’t answer / response;
broke sender’s signature but cannot make a fake/wrong bit b, because broken signature cannot verify correct.
broke node’s signature itself.

If the sender is a dishonest party, in step 0, dishonest part can send b to some parties, and send a different b’ to other parties. Then it don’t have consistency. If the sender is a honest part, the dishonest party don’t response, so other nodes can’t accumulate “all the properly signed bits from the sender are the same, and the party outputs that bit”, then other nodes have no response. Then it still don’t have consistency.

B) If there is at most one dishonest party, does the protocol have validity?

answer - dishonest party don’t response any message , and make other nodes cannot reach “all the properly signed bits from the sender are the same, and the party outputs that bit.” So this protocol don’t have validity.

C) If there are at most two dishonest parties, show that the protocol does not have consistency.

answer - As answer A)

D) If there are at most two dishonest parties, does the protocol have validity?

answer - two dishonest parties can send out the same dishonest message or they don’t response, and make other nodes cannot reach “all the properly signed bits from the sender are the same, and the party outputs that bit.” So this protocol don’t have validity.

E) Does the protocol have totality (for any number of dishonest parties)?

answer - It assume that this protocol run in a reliable broadcast protocol (RBC). But the dishonest party can send a (or some) correct response to one (or some other) party, but don’t response any message to one (or some other) party in step 1. Dishonest party also can do the same in step 0. So these honest party cannot have the same result. Then this protocol don’t have totality.

CS251_Final_Exam_2021-stanford.edu-1

Posted on 2022-03-10 Edited on 2022-03-31

Problem 1. [18 points]: Questions from all over.

A) Briefly explain why a Rollup system stores all transaction data on chain? What would go wrong if transaction data were discarded and not stored anywhere?

answer - The main goal of Rollup is to increase transaction speed (faster finality), and transaction throughput (high transactions per second), without sacrificing decentralization or security.

Some Rollup solutions are optimistic rollups, zero-knowledge rollups or state channels. Transactions are rolled up into a single transaction to Mainnet Ethereum, reducing gas fees for users making Ethereum more inclusive and accessible for people everywhere. Rollups perform transaction execution outside layer 1 and then the data is posted to layer 1 where consensus is reached. As transaction data is included in layer 1 blocks, this allows rollups to be secured by native Ethereum security. That is why Rollup system stores all transaction data.

So If Rollup system has only one single data storage and its transaction data were discarded, the transaction data before rollup will lose and can not get back. Usually, Rollup system is a blockchain and data saved in decentralized nodes, so original transaction data will not lose when one of blockchain nodes is down or broken.

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: a contract at address X and a contract at address Y . Which of the following can read the state of _balances in contract X? Circle the correct answer(s).

A Code in the _transfer() function in contract ERC20 at address X
B Code in the _transfer() function in contract ERC20 at address Y
C An enduser using etherscan.io

answer C is correct.

C) Continuing with part (B),

which of the following can read the log entry Transfer emitted when the function _transfer() is called? Circle the correct answer(s).

A Code in the function getBalance() defined in contract ERC20 at address X
B Code in the function getBalance() defined in contract ERC20 at address Y
C An enduser using etherscan.io

answer C is correct.

D) Two Ethereum transactions, tx1 and tx2, are submitted to the network at the same time. Transaction tx1 has maxPriorityFee set to y and transaction tx2 has maxPriorityFee set to 2y. Will tx2 necessarily be executed on chain before tx1? Justify your answer. You can assume that maxFee for both tx1 and tx2 is greater than baseFee + maxPriorityFee.

answer - Assume that maxFee (tx1 and tx2) is greater than baseFee + maxPriorityFee, tx1 and tx2 will mine by miner both, they will execute in the same block, that is the most possibility, because usually miner nodes are working for tx order base on gasFee from high to low. But still has other possibilities - 1) send tx1 in node 1, send tx2 in node2, the network of node 1 is bad, and all txs in txpool of node 1 maybe blocked , so the speed and status of network of node is very important for transaction success; 2) the other transactions’ maxPriorityFee, if they all very high than 2y, the block is full and cannot take tx2 in, then tx1 and tx2 will not execute, and their executed order will depends on the next block. Or they all very high than y, the block is full and cannot take tx1 in, but the block take tx2 in, so tx1 will not execute, tx2 will execute.

Catch up high Miner extractable value (MEV) may cause a miner to take priority of a lower fee transaction because it benefits them in some way, it is good for DeFi and application boom, but bad for UX, blockchain network congestion, even make blockchain block order re-organization and consensus instability.

E) Alice wants to buy a car from dealer Bob. She sends 1 BTC to Bob’s Bitcoin address. Bob waits for a transaction where (i) the input is from Alice’s address, and (ii) one of the outputs is a UTXO bound to Bob’s address with a value of 1 BTC. As soon as Bob sees this transaction on the Bitcoin blockchain, he gives Alice the keys, and she drives away. Is this safe? Could Alice get the car for free? If so, explain why. If not, explain what Bob should do to ensure that he gets paid.

answer - In bitcoin with PoW consensus protocol, the tx finality need to wait 6 blocks. so Bob should to wait 6 blocks after the block of tx.

F) Alice owns a brand new Tesla Model Y. Can she currently use her car as collateral for a loan in the Compound system? (without selling the car) If yes, explain how. If no, explain why not.

answer - no, physical car cannot come into digital Compound system yet, because the car maybe bad, maybe broken, maybe stole from somewhere illegally, the car loan needs many kinds of service to confirm its value and price. Compound now only provide cryptocurrencies as collateral for a loan.