Is it possible to mine bitcoins faster on CPUs with this strategy?

Question

This guy on bitcointalk.org suggested a potentially faster method for mining bitcoins using CPUs: https://bitcointalk.org/index.php?topic=265759.0

To quote from the author:

"Rather than computationally solving for SHA256(SHA256(block_header)), the approach is to solve it symbolically. What I mean by this is, rather than treating the block header input bits as 0 or 1, treat each input bit as an individual symbolic variable (640 in total). Next, perform the double SHA256, and produce a set of equations that represents each bit in the final hash. These will obviously be huge, but you can PolynomialReduce after each step of the hashing to reduce the equation size.

The SHA256 output is 32 bytes, so what you end up with is a system of 256 equations, consisting of 640 variables each (which include all the logical operators applied from the double hash.) For the purposes of mining at difficulty 1, you can discard all but the first 32 equations.

Now to mine using this method: You have to collapse the equations and simplify. Take the current, real block_header in question, and fill in actual values in your 32 equations for every bit except for the 32-bit nonce (608 in total.) Reduce.

Now you have a system of 32 equations, and 32 unknowns. Set all 32 equations equal to one another, and solve the system of equations.

What you end up with are 3 possible solutions: A nonce that produces 32 "0" bits (what we want), a nonce that produces all "1" bits (discard) or no solution (increment extraNonce.)

Note to make reduction and solving the system of equations simpler, convert the logical operators (xor, or, and) into arithmetic operations and do the reduction and solving in the modulo 2 number ring, for example:

a^b == (a+b)%2
(a | b) == ( (a*b)%2 + a%2 + b%2 );
(a & b) == (a * b) % 2 "

Now, I'm not a math guy, but from what I can gather, this strategy takes up a lot of computing memory. Therefore, my question is - is this strategy theoretically feasible? Can it be as efficient as ASIC mining?

Answer 1

It's not clear what the strategy is. It just says "and solve the system of equations".

The entire structure of cryptographic hashes like SHA256 is carefully designed to make doing this as difficult as possible, and there's not even a hint of how to solve that system of equations.

This is precisely what ordinary miners do, except they try to solve the system of equations by guessing possible solutions and seeing if they solve the equations. If there is a simpler way to solve them, what is it?

Answer 2

Now, I'm not a math guy, but from what I can gather, this strategy takes up a lot of computing memory. Therefore, my question is - is this strategy theoretically feasible?

If it is feasible, SHA256 is broken and we should switch to something else.

The whole point of proof-of-work is to find a function for which partial preimages can practically only be found by iterating candidate solutions (or at least using work proportional to the number of candidate solutions tried).

If an algebraic way to solve these equations exists, it means SHA256 is not sufficiently distinguishable from a random function, as the relation between input and output obeys some tractable algebraic formulas. It wouldn't just be a break for its use in Bitcoin, but to SHA256 in general.

Can it be as efficient as ASIC mining?

If it works and is feasible, it'd likely be faster as it would permit solvers that scale better with increasing difficulty.

Thankfully, this approach is infeasible.