Instead of just crunching numbers to solve SHA256(SHA256(block_header)), there's a different angle to tackle it. The idea is to look at each bit in the block header not as just 0 or 1, but as its own symbolic variable (there’s a total of 640). Then you run the double SHA256 and create a whole bunch of equations that represent each bit in the resulting hash. Sure, they’ll be massive, but you can keep shrinking those equations with PolynomialReduction after each hashing step.
With SHA256 giving us 32 bytes, you end up with 256 equations, each having 640 variables, which cover all the logical operations from the double hashing. If you’re mining at difficulty 1, you can ignore all but the first 32 equations.
To actually mine this way, you’ve got to simplify and collapse those equations. Start with your current block_header, plug in real values for all the bits in your 32 equations except for the 32-bit nonce (that leaves you with 608 bits). Then reduce everything.
At this point, you’re dealing with a set of 32 equations and 32 unknowns. You just need to make all 32 equations equal and solve them.
In the end, you’ll find 3 possible outcomes: a nonce that gives you 32 leading zeroes (which is what we want), a nonce that results in all ones (which you can toss out), or you get no valid solution (so you just bump up the extraNonce).
Pro tip to keep things easy when reducing and solving: change the logical operators (like xor, or, and) into arithmetic ones and do your reductions and solutions in modulo 2 arithmetic, for instance:
a^b == (a+b)%2
(a | ...
This is different than a SAT solver approach in my view,
What I'm proposing is coming up with equations that represent doing the double SHA256 symbolically. Each equation will have no more logical operations than the double hash itself (sans the symbolic carry bits from addition) and no more than 640 input variables corresponding to the input bits of the block header.
All of this can be computed offline. Then it's about solving a system of 32 equations with 32 unknowns to derive the correct nonce. I propose this can be done faster than trying to hash the full nonce range on the CPU, maybe faster than doing it on a GPU; Wolfram Mathematica for example can do it in a few seconds depending on the equation complexity.
Wouldn't the stateful 32-bit operations (ROTR, + mod 32) radically complicate creating a reduceable linear polynomial? ROTR I can see since its just assignment in your model, but where do all the carry flags go in + mod 32?
BTW, this topic is a great match for your nickname.
Here is what my symbolic carry bit code looks like for + (note, TUInt32 is my class which acts as an UInt32 but symbolically tracks all operations applied to it.)
public static TUInt32 operator +(TUInt32 b1, TUInt32 b2)
{
var r = new TUInt32((uint)0);
TBit carryBit = new TBit("0");
for (int i = 0; i < 32; i++)
{
var tmp = new TBit(b1._bits, "^", b2._bits);
r._bits = new TBit(tmp, "^", carryBit);
var op1 = new TBit(b2._bits, "|", carryBit);
var op2 = new TBit(b1._bits, "&", op1);
var op3 = new TBit(b2._bits, "&", carryBit);
carryBit = new TBit(op2, "|", op3);
}
r._value = (uint)(b1._value + b2._value);
return r;
}
The equations do get quite complicated, but as I mentioned previously, you can PolynomialReduce after each step of the procedure;
For symbolic unsigned integers "a" and "b", having symbolic bits a0-a31 and b0-b31, here is the result for each bit of "c" in the operation "c = (a + b)" after PolynomialReduce:
bit0: (a0^b0)
bit1: (a1^a0&b0^b1)
bit2: (a2^a0&b0&b1^b2)
bit3: (a3^a0&b0&b1&b2^b3)
bit4: (a4^a0&b0&b1&b2&b3^b4)
bit5: (a5^a0&b0&b1&b2&b3&b4^b5)
bit6: (a6^a0&b0&b1&b2&b3&b4&b5^b6)
bit7: (a7^a0&b0&b1&b2&b3&b4&b5&b6^b7)
bit8: (a8^a0&b0&b1&b2&b3&b4&b5&b6&b7^b8)
bit9: (a9^a0&b0&b1&b2&b3&b4&b5&b6&b7&b8^b9)
bit10: (a10^b10^a0&b0&b1&b2&b3&b4&b5&b6&b7&b8&b9)
bit11: (a11^b11^a0&b0&b1&b10&b2&b3&b4&b5&b6&b7&b8&b9)
bit12: (a12^b12^a0&b0&b1&b10&b11&b2&b3&b4&b5&b6&b7&b8&b9)
bit13: (a13^b13^a0&b0&b1&b10&b11&b12&b2&b3&b4&b5&b6&b7&b8&b9)
bit14: (a14^b14^a0&b0&b1&b10&b11&b12&b13&b2&b3&b4&b5&b6&b7&b8&b9)
bit15: (a15^b15^a0&b0&b1&b10&b11&b12&b13&b14&b2&b3&b4&b5&b6&b7&b8&b9)
bit16: (a16^b16^a0&b0&b1&b10&b11&b12&b13&b14&b15&b2&b3&b4&b5&b6&b7&b8&b9)
bit17: (a17^b17^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b2&b3&b4&b5&b6&b7&b8&b9)
bit18: (a18^b18^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b2&b3&b4&b5&b6&b7&b8&b9)
bit19: (a19^b19^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b2&b3&b4&b5&b6&b7&b8&b9)
bit20: (a20^b20^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b3&b4&b5&b6&b7&b8&b9)
bit21: (a21^b21^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b3&b4&b5&b6&b7&b8&b9)
bit22: (a22^b22^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b3&b4&b5&b6&b7&b8&b9)
bit23: (a23^b23^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b3&b4&b5&b6&b7&b8&b9)
bit24: (a24^b24^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b3&b4&b5&b6&b7&b8&b9)
bit25: (a25^b25^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b3&b4&b5&b6&b7&b8&b9)
bit26: (a26^b26^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b3&b4&b5&b6&b7&b8&b9)
bit27: (a27^b27^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b26&b3&b4&b5&b6&b7&b8&b9)
bit28: (a28^b28^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b26&b27&b3&b4&b5&b6&b7&b8&b9)
bit29: (a29^b29^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b26&b27&b28&b3&b4&b5&b6&b7&b8&b9)
bit30: (a30^b30^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b26&b27&b28&b29&b3&b4&b5&b6&b7&b8&b9)
bit31: (a31^b31^a0&b0&b1&b10&b11&b12&b13&b14&b15&b16&b17&b18&b19&b2&b20&b21&b22&b23&b24&b25&b26&b27&b28&b29&b3&b30&b4&b5&b6&b7&b8&b9)
Clever implementation. Lends itself well to complete regression testing / provability.
On first inspection, I'm not convinced that the reduced form is correct. By definition, doesn't c31 depend on a30 if b30 = 1?
Looking at it another way, the third term of c31 will be zero in all but 2 out of 2^32 cases for all possible values of b and in all cases if a0 = 0.
As you've shown it becomes monstrously complex very quickly and so the only viable solution is a brute force. The only hope is that you manage to cancel some terms out so that you effectively find a short cut but crypto-analysts spend an awful lot of time studying all the common crypto and hashing algorithms and I don't believe they've found anything that indicates a weakness with SHA256 yet - so I wouldn't hold your breath on this one.
Probably a better hope would be to have an analog circuit that operates backwards so that for a given hash it could indicate a list of possible inputs but, I suspect, that having built this it won't indicate any weakness - these things have been thoroughly studied using a range of techniques already.
Good luck, though.
Thank you dentldir, it turns out there was a bug in the module feeding stuff to wolfram,
new bits for (c = a + b) are looking like this:
c0: (a0^b0)
c1: (a1^a0&b0^b1)
c2: (a2^a1&b1^a0&b0&(a1^b1)^b2)
c3: (a3^a2&b2^a1&b1&(a2^b2)^a0&b0&(a1^b1)&(a2^b2)^b3)
c4: (a4^a2&a3&b2^a3&b3^a2&b2&b3^a1&b1&(a2^b2)&(a3^b3)^a0&b0&(a1^b1)&(a2^b2)&(a3^b3)^b4)
c5: (a5^a4&(a3&b3^a2&b2&(a3^b3))^(a4^a3&b3^a2&b2&(a3^b3))&b4^a1&b1&(a2^b2)&(a3^b3)&(a4^b4)^a0&b0&(a1^b1)&(a2^b2)&(a3^b3)&(a4^b4)^b5)
c6: (a6^a4&a5&(a3&b3^a2&b2&(a3^b3))^a5&(a4^a3&b3^a2&b2&(a3^b3))&b4^(a5^a4&b4^a3&b3&(a4^b4)^a2&b2&(a3^b3)&(a4^b4))&b5^a1&b1&(a2^b2)&(a3^b3)&(a4^b4)&(a5^b5)^a0&b0&(a1^b1)&(a2^b2)&(a3^b3)&(a4^b4)&(a5^b5)^b6)
at first glance they verified in an excel sheet, other bits are still simplifying.
Right. A 32-bit x86 add operation takes 1 cycle.
Your currently 7-bit symbolic add operation has (roughly - don't trust my counting skills) 66 XOR ops and 67 AND ops. You could have calculated the 133rd fibonacci number by the time you had added 7 bits together.
Another advantage brute-force has is parallelism. Because of the varying brackets, you can't even execute most of your instructions in parallel.
Matthew:out
@botnet
What do you mean with the word PolynomialReduce? Do you mean polynomial reduction?
I did not take the tour to understand your thoughts fully because it looks like some sort of ILP problem to me (at least there seems to be a polynomial reduction from your problem to the ILP).
Generally speaking: If there would be a known feasible solution for something like:
sha256^(-1)(sha256^(-1)(result)) = (nonce, previous_block)
then it would be silly to call sha2 an one way function.
SAT and ILP have feasible solutions only under the assumption that P=NP.
In my case I literally mean the PolynomialReduce function in Wolfram Mathematica: http://reference.wolfram.com/mathematica/ref/PolynomialReduce.html
So my TUInt32 class creates a symbolic representation of every mathematical or logical operator that is applied to it, and after each operation, it feeds that equation through Wolfram Mathematica to reduce and simplify the equation, for example: FullSimplify[PolynomialReduce[a*b, a0^2 - a0, b0^2 - b0, Modulus -> 2]]
(recall that logical operations are being transformed to numeric operations in the modulo 2 number ring)
1.21 Gigawatts!
I thank you. My tip address is below.
Really, what level of course material are you guys talking here? I only had the first level of CS classes and I'm having a tough time following. Looks cool though.
@botnet
Now I understand your idea better. But you are possibly wrong: The main complexity of your approach is not because of the degree of the polynomials but because of the referencing of the literals (you called them 'variables') to each other.
At this point you have just two choices:
1. Try random input (you know this solution under the (wrong) name 'brute force')
2. Try to approximate to a good solution (but then your result would only be partly correct: Who is interested in a 90% correct nonce to the given block and targeted result?) and it is not proven in this case that an approximation exists.
@c789
YMMD!
In my case: Halting problem, P, NP, some other part of the complexity zoo and SAT were basic stuff. Second year.
ILP came in higher classes.
Are you trying to get a degree in computer science?
@cheater123
Welcome to the forum!
A very short introduction to mining
To find a new block the network gives every miner a challenge (i.e. a target value). The higher the difficulty the lower the desired value. Now every miner reads the last block and tries to guess a nonce for it. If the computed result is lower than the target value then a new block has been found and the next challenge uses the newly found block.
Maybe one could try addition as basic algorithm for mining:
lastblock + nonce = result
But that would be pointless: Subtraction would find the nonce by simple computation.
result - lastblock = nonce
That is because of the fact that addition and subtraction are each fast to compute.
So the chosen basic algorithm is SHA256 which is known for a speciality: computing a result by
sha256(original_input)=result
is fast to compute.
But computing the original_input by using only the result is really time consuming.
These algorithms are known as one way function (with trap door).
For reversing to the nonce in a feasible time one would need a theoretical machine which guesses the right value in the first step. Unfortunately there is no known way to produce such a machine in reality.
So every miner uses a random value as nonce and computes:
sha256(sha256(nonce, last_block))=result
and evaluates whether result < target_value.
If so then a new block was found. Otherwise the miner tries another random value as nonce and evaluates again.