Score:1

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

na flag

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

James avatar
br flag
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?
user2383960 avatar
na flag
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
Score:3
vu flag

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.

user2383960 avatar
na flag
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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.