3. Feather Forking - 25 points In class we learned about feather forking: a coalition of miners controlling a fraction of the total mining power attempts to censor transactions by announcing: "if we see a block containing a transaction from our blacklist, we will attempt to fork until we are 3 blocks behind the main chain." This strategy can be shown in a probabilistic state machine: a. What is the probability that the censorship attack will succeed in terms of a? Hint: Express the probability of the fork succeeding from each active state in the state machine above as po, pi, and pz. You can now express each probability in terms of the others and solve a system of three equations for pi, the probability of the attack succeeding from the start state "1 behind," in terms of a. b. On expectation, for how long (expressed as a number of blocks found) will the systenm be in a forked state after the attack is launched before it either succeeds or fails? Hint You can solve this problem using a similar system of equations as above, noting that every time a transition is taken, the fork lasts one additional block. Make sure that, as a sanity check, the attack is expected to resolve in 2 blocks for both a-0 and a1 (extra credit) Validate your analytical results above using Monte Carlo methods. The following pseudocode can be used as a guide: c. Monte Carlo Method to determine p,assuming a 0.2 Perform the following 20,000 rounds i. Start in state 1 ii. Run the Markov chain (assuming a 0.2) until one of the absorbing states "attacker wins" or "attacker aborts" is reached. Keep track of the total number of state transitions for this round as well. The fraction of rounds that the round ends in the "attacker wins" state is an estimate for pi when a 0.2. Does this match your analytical result from part (a)? The average number of state transitions over all rounds is an estimate for how long (expressed as a number of blocks found) the system is in a forked state after the attack is launched before it either succeeds or fails (when a 0.2). Does this match your analytical result from part (b)? Perform the same analysis for a range of values of a. 3. Feather Forking - 25 points In class we learned about feather forking: a coalition of miners controlling a fraction of the total mining power attempts to censor transactions by announcing: "if we see a block containing a transaction from our blacklist, we will attempt to fork until we are 3 blocks behind the main chain." This strategy can be shown in a probabilistic state machine: a. What is the probability that the censorship attack will succeed in terms of a? Hint: Express the probability of the fork succeeding from each active state in the state machine above as po, pi, and pz. You can now express each probability in terms of the others and solve a system of three equations for pi, the probability of the attack succeeding from the start state "1 behind," in terms of a. b. On expectation, for how long (expressed as a number of blocks found) will the systenm be in a forked state after the attack is launched before it either succeeds or fails? Hint You can solve this problem using a similar system of equations as above, noting that every time a transition is taken, the fork lasts one additional block. Make sure that, as a sanity check, the attack is expected to resolve in 2 blocks for both a-0 and a1 (extra credit) Validate your analytical results above using Monte Carlo methods. The following pseudocode can be used as a guide: c. Monte Carlo Method to determine p,assuming a 0.2 Perform the following 20,000 rounds i. Start in state 1 ii. Run the Markov chain (assuming a 0.2) until one of the absorbing states "attacker wins" or "attacker aborts" is reached. Keep track of the total number of state transitions for this round as well. The fraction of rounds that the round ends in the "attacker wins" state is an estimate for pi when a 0.2. Does this match your analytical result from part (a)? The average number of state transitions over all rounds is an estimate for how long (expressed as a number of blocks found) the system is in a forked state after the attack is launched before it either succeeds or fails (when a 0.2). Does this match your analytical result from part (b)? Perform the same analysis for a range of values of a
