A broken proof of work hash function. In class we discussed using a hash function H : X Y {0, 1, . . . , 2

n 1} for a proof of work scheme. Once an x X and a difficulty level D are published, it should take an expected D evaluations of the hash function to find a y Y such that H(x, y) < 2

n/D. Suppose that X = Y = {0, 1} m for

some m (say m = 512), and consider the hash function H : X Y {0, 1, . . . , 2

256 1} defined as H(x, y) := SHA256(x y). Here denotes a bit-wise xor. Show that this H is insecure as a proof of work hash. In particular, suppose D is fixed ahead of time. Show that a clever attacker can find a solution y Y with minimal effort once x X is published. Hint: the attacker will do most of the work before x is published.