# SHA-256: (Probabilistic?) partial pre-image possible?

Currently busying myself with the Bitcoin "mining" algorithm, I am wondering if the process really cannot be simplified.

For reference, the algorithm is basically SHA-256d:

$success := SHA256( SHA256( IV || nonce ) ) < target$

The resulting hash of 256 bits is then interpreted as a single number of 256 digits (base 2). If this number is lower than the given $target$ number a valid nonce is found. (The $IV$ can be considered to be constant.)

At the moment, brute-forcing through all possible $nonce$s is deemed to be the only viable way of finding values that satisfy the above equation, and, considering the double-application of the hash function, this seems to be a reasonable assumption.

However, one may simplify the problem by (first) only looking at the second application of the hash function:

$success := SHA256( X ) < target$

I am not aware of the correct term (if there is one), so I would say this is a "partial pre-image" problem. The constraint on the output is not that it equals a given value, but that it is lower than a given value. In other words, and again simplified: The constraint is that the first n digits (bits) of the output are 0, where n may be comparably low, 32 for example, as opposed to the full pre-image attack where n = 256.

"SAT solving - An alternative to brute force bitcoin mining" seems to describe a logical approach to the problem: Transform the hash function to a boolean function and then, given the (relatively weak) constraint on the output of the hash function and (a part of) the known input $X$, perform backtracking to deduce a constraint on the input from the constraint on the output.

In papers about higher-order differential cryptanalysis of a reduced version of SHA-256 it is demonstrated that one may be able to predict a part of the internal state of the function which is reached after round $r$ from the internal state after round $r-d$ (for $d \in {[2, r[}$) with certain probabilities $p <= 1$ without actually computing rounds $r-d+1$ through $r$.

Now, considering the above constraint about the leading 0s of the output I have been trying to find out during the past days if there may be a probabilistic approach which could yield an estimate of the probability of a certain partial state after round $r$ from the outcome of round $r-d$.

Of course, for this Bitcoin case the hash function does not need to be considered a black box or an oracle, because the complete input is known and so is the complete internal state at any point of the calculation.

If such an estimate would exist for $r=64$ and $d \gg 1$ and this could be computed more efficiently than $d$ rounds of the hash function it would possibly allow a shortcut through the second application of the hash function.

Note that the estimation does not have to be very accurate, nor does the probability have to be very high to be of use. It is also not required that the estimate is safe in either direction; it is well acceptable to not find all solutions (nonces) this way.

Is anyone aware of such a probabilistic approach for forward-estimation for some of the rounds of SHA256?

Can there actually be one of significance? (An estimate yielding, for example, $p=0.501$ for one bit of output is probably not significant in the sense that it may reduce computational complexity.)

-