Mining protocol for a blockchain
A new cooperative blockchain EBLOCKS produces blocks using the following protocol, which works in phases. We assume that the number of members n is fixed. At the beginning of each phase all n members become active. In each step within a phase, each active member flips a fair coin and with probability p = 1/2, the member remains active, and with the remaining probability it becomes inactive. The phase ends when the number of active members becomes either 0 or 1. When the phase ends with a single active member, this member produces a block, otherwise the phase terminates without a block.
(a) Show that the probability that a block is produced in a phase is at least 2/3.
(b) Show that the expected number of steps in a phase is 9(logn), giving both a lower and an upper bound, and conclude that this blockchain protocol produces a block every O(long) steps in expectation.
(c) The above protocol produces one block per 9(logn) steps in expectation. By changing only the probability p that each member remains active in each step, can we get a protocol so that a block is produced in expected O(1) steps?
By purchasing this solution you'll be able to access the following files: