Related eBooks
Q. For a hash function H: {0,1} * → {1,...,2 256 }, consider the following alternate proof-of-
work: given a challenge c and a difficulty d, find nonces n 1 ≠ n 2 such that:

H(c,n 1 ) = H(c,n 2 ) (mod d)

That is, the miner must find two nonces that collide under H modulo d. Clearly, puzzle
solutions are easy to verify and the difficulty can be adjusted granularly.

A. A simple algorithm to solve this problem is to repeatedly choose a random nonce n, and
add (n, H(c,n)) to a set L stored to allow efficient search by n (such as a hash map). The
algorithm terminates when the last hash value added to L collides with some hash value
already in L. For given values of d, approximately how many invocations of H are required in
expectation to generate a solution n1 ,n2? How much memory does this use? Hint: it will be
helpful to familiarize yourself with the birthday paradox.

B. Consider an algorithm with limited memory that chooses one random nonce n 1 and then
repeatedly chooses a random nonce n 2 until it finds an n 2 that collides with n 1 . How many
invocations of H will this algorithm use in expectation? We note that there is a clever
algorithm that finds a solution in the same asymptotic time as part (A), but using only
constant memory.

C. Recall that a proof-of-work is progress-free if for all h,k (where h·k< B for some large
bound B) the probability of finding a solution after generating h·k hashes is k times higher
than the probability of finding a solution after just h hashes. Is this puzzle progress-free?


By pplny

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Translate »