$x$ is challenging string, $y$ is proof string. $\operatorname{H}$ is the proof-of-work (pow) function, to find a $y$ such that $H(x,y)<2^{256}/D$
- $x ,y = \{ 0, 1 \}^{512}$
- $\operatorname{H}(x,y) = \operatorname{SHA-256}(x \oplus y)$
- find a $y$ such that $\operatorname{H}(x,y)<2^{256}/D$
the question is to prove:
If difficulty $D$ is fixed ahead of time, attacker can find $y$ with minimum of time once $x$ is published.
(the attacker can do most of the work before x is publish)
my intuition is that:
- the precomputation attack is related to xor operation. for example $1101 \oplus 1111 =0101, 0000 \oplus 0101 = 0101$.
- there is some collision before the hash funciton. $x \oplus y = x' \oplus y'$, $\operatorname{H}(x \oplus y )=\operatorname{H}(x' \oplus y')$.
I tried my best to learn some precomputation attack or preimage attack for a full day , but finally no progress. I would be very grateful if you could give some clues.
The link of the origin question:
https://cs251.stanford.edu/hw/hw1.pdf
(This is from Stanford course cs251 homework, but I am not an enrolled student and I learned it by myself. I tried to finish the homework and projects to make sure I understand the topic details. Besides, the work is overdue, so I think it not violate some school rules. If it is inappropriate to ask, please let me know)
