# Why is $\operatorname{Hash}(x \oplus y)$ not a secure proof-of-work algorithm?

$$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$$

1. $$x ,y = \{ 0, 1 \}^{512}$$
2. $$\operatorname{H}(x,y) = \operatorname{SHA-256}(x \oplus y)$$
3. 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:

1. the precomputation attack is related to xor operation. for example $$1101 \oplus 1111 =0101, 0000 \oplus 0101 = 0101$$.
2. 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)

• How is x and y calculated and what details are sent as a "proof-of-work"? What "work" is being proven? Is x the "block" (to give a blockchain-specific example) and y the "nonce" that the user chooses to prove that "work" has been done? Oct 29, 2022 at 10:03
• I think you are right. Use blockchain as an example, x is the block message itself, (I guess it is the the header of the last/current block), it is a certain string provided by one block. y is the calculated "nounce". @James Oct 29, 2022 at 12:17

The alleged prover can pre-compute a $$u$$ such that $$H(u)$$ satisfies the condition of the proof of work.
Given a challenge $$x$$, the prover can output $$x \text{XOR} u$$ as the proof thus cheating the game.
• Thank you very much. It really helps me a lot. It reminds me of the introduction of a magic property of xor operation. If $x XOR u = y$, there is $x XOR y = u$. Thank you for your help. Oct 29, 2022 at 12:03