-- First, lets assume that outputs of the hash function are indistinguishible from what is called a Random Oracle. That is, on input x (a bit string), the output value SHA256(x) is uniformly chosen from all bits strings of length 256, which is the same as if you flipped 256 fair independent coins and recorded the output. Further, if you hash the same x, you get the same value both times. Hence, it behaves like an oracle that on a request randomly chooses an output, and then remembers it for future requests.

-- Second, assume that each miner randomly chooses a value for the nonce r_j, hashes it along with B_j and B_j1, and checks if the output has leading zeros. If it doesn't, it chooses a fresh random r_j and tries again.

-- Third, lets assume that the required number of leading zeros is denoted . Note that in real life, this parameter is chosen by the Bitcoin community based on the number of active miners and the total computing power available to the miners in order to curb the introduction of new blocks.

Under these assumptions, we can model a single attempt at mining as a random variable X ~ Bern(p), with two outcomes: success in mining a Bitcoin (with probability p) or failure.

As mentioned earlier, the parameter which is the number of leading zeroes is NOT always the same. For a given {0,1,2,...,256}, we want to be able to find the probability of generating a nonce which starts with zeros, in other words, the probability of flipping a coin 256 times and having all tails for the first flips.

For example, if =0, this means we don't care how many leading zeroes there are, and the probability of success is 1.

****Question****

We assume SHA-256 is indistinguishable from a random oracle. Under this assumption, let p be the probability that a rondomly chosen nonce r_j confirms that some block B_j comes after block B_j-1. Give a formula for p in terms of p.

Hint: recall that when a random oracle is queried on a new input, its response is uniformly chosen from bit strings of length 256 and becomes fixed for that input. In other words, let X be a Bernouli random variable that is 1 if a block is confirmed by a nonce, and 0 otherwise. Then X ~ Bern( f (p) ). Find f.