Topic: Potentially faster method for mining on the CPU - page 4. (Read 14431 times)
This will be many, many orders of magnitude harder than brute force.
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.
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.
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.
Thoughts? Make sure you have 32GB of RAM installed 
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.
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.
I am sooooo confused
Mathematical Minning could return to normal people, minning.
Watching.
Go foward!!!
Watching.
Go foward!!!
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.
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.
Quote
Next, perform the double SHA256, and produce a set of equations that represents each bit in the final hash.
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?
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)
Thoughts?
I'll get back to you when you can show a working implementation that is faster than the current SSE2 one. Quote
Next, perform the double SHA256, and produce a set of equations that represents each bit in the final hash.
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.
It wont be faster than brute force method. read this for more details: http://jheusser.github.io/2013/02/03/satcoin.html
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.
https://bitcointalksearch.org/topic/sha-256-as-a-boolean-function-55888
It wont be faster than brute force method. read this for more details: http://jheusser.github.io/2013/02/03/satcoin.html
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.
It wont be faster than brute force method. read this for more details: http://jheusser.github.io/2013/02/03/satcoin.html
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
Thoughts?
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
Thoughts?
Jump to: