II. PROBLEM 2. QUICKEST VIOLATION (50 POINTS) In this problem, you will delve into the security aspects of the longest-chain-fork-choice rule. The question is: Suppose the adversary begins to attack the system from time 0 immediately after the genesis block is mined, what is the minimum expected time or number of blocks mined to create the first safety violation. Your approach can be theoretical, involving formulas, or you can carry out computer simulations to obtain numerical results, or both. A. Basic Model The proof-of-work Nakamoto consensus protocol builds a growing sequence of transaction-carrying blocks where every block is chained to its predecessor block by a solution to a computational puzzle. At any point in time, every honest node attempts to \"mine\" a new block that extends the longest chain of blocks (blockchain) to its knowledge; once a new longest blockchain is mined or received, an honest node sends it to other nodes through a gossip network. Definition 1 (block depth). The height-h block in a chain of length h + k 1 is said to be k-deep. For example, the fourth block of a chain of length six is 3-deep. A block is always 1-deep upon its mining. It can become 2-deep, 3-deep, and so on as more blocks confirm it. Definition 2 (k-confirmation commit rule). A node commits a block when it is at least k-deep in a longest chain known to that node. Throughout, we think of & as a given natural number. Let a and h (in blocks per second) denote the total block mining rates of the adversarial miners and the honest miners, respectively. Let A denote the maximum block propagation delay in seconds. The basic version of the problem assumes zero propagation delays, i.e., A = 0 and proof-of-work mining. Under proof-of-work mining, we also assume 1.1 2 ,t (1) Recall that (1) describes the fundamental fault tolerance for the proof-of-work longest-chain-win protocol. As long as (1) holds, a transaction is safe if it remains on the longest chain after a sufficient number of block confirmations (i.e., it is k-deep with a sufficiently large ). B. The Simple Private-Mining Attack A very simple attack is the following private-mining attack we discussed many times in class. Definition 3 (Private-mining attack on height 1). From time 0, the adversary mines a private chain on top of the genesis block. Evidently, the honest miners grow a separate chain, which we shall call the public chain. A safety violation occurs or is guaranteed to occur as soon as both of the following conditions are met: 1) The private chain's height is at least k; and 2) the private chain is at least as long as the public chain. We have spent time in class analyzing the probability of a safety violation on height 1. Under assumption (1), the probability of safety violation is strictly less than 1. This means that, with some positive probablity, the safety of height 1 will never be violated this is the safety guarantee, a highly desirable property. C. Private-Mining with Reset Being fixated on attacking height 1 does not guarantee a violation. In order to guarantee a successful violation, the attacker needs to consider causing a violation on some other heights. For example, if the public chain becomes much longer than the private chain, the adversary should target a different height. In the basic version of the problem, we define a specific attack as follows: Definition 4 (private mining with reset). At time 0, the adversary sets its base block (or simply base) to the genesis block and begins to mine a private chain. (A private chain is not published until the moment the attack succeeds.) At any point in time, the adversary may reset its base to the highest honest block and begin to mine a new private chain on the new base; the target of the attack is always the first honest child of the base. If the base becomes k +1 deep in a private chain before it is k +1 deep in a public chain, the adversary joins the honest miners to extend the public chain. The adversary publishes all blocks to violate the target's safety as soon as both of the following conditions are met: 1) The target is at least k deep; and 2) the private chain which includes the current base is a longest chain. The only degree of freedom in the attack is the reset strategy, i.e., when to reset the base to the highest honest block. Given a reset strategy, the time to violation is a function of the block mining times. Do the following: 1) Provide a clear and concise formulation of the basic problem. (10 points) 2) Design a reset policy (i.e., when to reset) to guarantee violation. Analyze or simulate (e.g., by running 100 instances) the expected minimum time to first violation. (20 points) 3) Study and discuss how to design a reset policy that make the expected time to a first violation as small as possible. Explain your design/ideas. If it is challenging to chieve the minimum, discuss what challenges you have. (20 points) Evidently, no one can exhaust all possible parameters in a simulation. If you use simulations, you may assume reasonable values of a, h, and & to obtain results that are practically relevant and/or interesting, and computationally feasible. A recommendation is a = 0.3, h = 0.7, and k = 5. D. Bonus Points You may extend your study in a non-trivial manner to earn up to 10 bonus points. The following questions are suggested for you to consider, but you may define your own extension: 1) When the adversary reset its base (this is where to mine), is it always the best to reset it to the highest honest node? If so, justify; if not, propose a better alternative and justify. 2) Characterize the minimum time to violation under the relaxed assumption of A > 0? One way the adversary may benefit from is to delay the propagation of all honest blocks maximally (i.e., by A). Finally, if you estimate the expected minimum time to the first violation accurately, you will receive an additional 20 points. Reference [1] or a good textbook on reinforcement learning might be useful to this study