SHA-256: (Probabilistic?) partial preimage possible?

Question

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:

$$\mathit{success} := \operatorname{SHA256}( \operatorname{SHA256}( \mathit{IV} \mathbin\Vert \mathit{nonce} ) ) < \mathit{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 $\mathit{target}$ number a valid nonce is found. (The $\mathit{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:

$$\mathit{success} := \operatorname{SHA256}( X ) < \mathit{target}$$

I am not aware of the correct term (if there is one), so I would say this is a "partial preimage" 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 preimage 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 \leq 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.)

Edit:

To maybe illustrate the rationale behind my thougts, lets look at the (differentials of) basic operations in a statistical way:

a) XOR

For the XOR operation on single bits $A$ and $B$

$$\mathit{result} := A \oplus B$$

the case is simple: Without actually doing the calculation we can tell beforehand that the result will be the inverse of $B$ iff $A = 1$ and $B$ iff $A = 0$ with probability 1. This equally holds for arbitraty length binary numbers $A$ and $B$.

b) Addition

This one is more interesting because we have probabilites of 1 or less.

Again, for the single-bit operation $A + B$ the result is the same as in the XOR case, with equal probability of 1.

However, when $A$ and $B$ are binary numbers of length $n > 1$ the result is different. Basically it turns out that the probability that one/all bit(s) in the result is inverted from $B$ is higher for a bigger $A$;

extrema: $$A = 0 \implies p = 0, \quad A = 1111\dots111 \implies p = 1$$

Plus: $$0 < A < 1111\dots111 \implies 0 < p < 1$$

XOR and addition are commutative so that $A$ and $B$ may be exchanged freely, maybe even in parts.

I was thinking that obervations like these could be leveraged to make statements like:

"If at some point $t$ in the calculation we obtain a value for some state variable $A$ that is greater than some threshold $X$ and [some statement about $B$] the probability $p$ of a positive outcome of the complete hashing function is greater/lower than $p$ and we continue/abort abort the current calculation."

Answer 1

The Bitcoin mining algorithm can not be simplified by exploiting any weakness in the SHA-2 hashing algorithm with the current state of the art.

The problem is manyfold. From the SHA-256 point of view, there is no (partial) preimage search algorithm that applies to the full hash function. Even worse, the attacks that penetrate a fewer number of rounds have huge complexity. In fact, no practical (partial) preimage attacks on any version of SHA-256 with more than 20 (out of 64) rounds have been ever constructed.

From the Bitcoin point of view, the situation is even worse. Recall that SHA-256 splits its input to 512-bit blocks and feeds them iteratively to the internal compression function, whose inverse is the core problem of preimage attacks. What is hashed in Bitcoin is the block header of 640 bits long, which requires two calls of the compression function (it consumes 512 bits per call), plus extra one in the outer call of SHA-256. The second call of the compression function gives little freedom to the attacker, who controls less than 128 bits of the 512-bit message block. As a result, even if SHA-256 was reduced threefold, it would likely to withstand attacks in the Bitcoin setting, not speaking of the full version.

Bitcoin miners still do some optimization by precomputing the 512 bits of the block header and hence the first call of the compression function, but the next steps can not be optimized much.

Answer 2

"If this would work for SHA-256 (in the current best published attack the initial structure is limited to four rounds), we would just be a few rounds away from a full preimage attack on the hash standard." "We derive a system of functional equations linking internal states several rounds apart. Then we show that it is equivalent to a system of differentials, so the full structure of states can be built out of a structure of trails. These structures are two sets of internal states with each state having a relation with all states in another set." from Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family paper.

The bounty for finding this kind of probabilistic preimage attack is very high : 12.5 BTC = 125000 USD every 10 min

You would think there are people exploiting partial pre-image attacks with ASICs mining with an advantage over the rest of the network