# How to formalize a partial preimage task?

Part of the bitcoin mining proof of work is associated with solving a partial preimage problem. For example, output a preimage message $M′$ which computes to a hash value $Y$ with $|Y| = n$ bits where half of the output bits are fixed to 0, $Y =0^{n/2} ∥ Z$ for any $Z$ with $|Z| = n/2$ bits.

$Adv(A) = Pr(z \leftarrow Z,\ |Z|=n/2,\ Y=0^{n/2} || Z,\ H(M') = Y)$
• The adversary $A$ does not appear in your probability. I'd more likely write this as $\mathsf{Adv}(A) = \mathsf{Pr}[y \gets A(H): \exists z \in \{0,1\}^{n/2}, H(y) = 0^{n/2}||z]$, where $H$ is the hash function, which is given as input to the adversary $A$ in this experiment. – Geoffroy Couteau Nov 22 '16 at 18:00