1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – James
    Oct 29, 2022 at 10:03
  • $\begingroup$ 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 $\endgroup$ Oct 29, 2022 at 12:17

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 29, 2022 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.