Search content
Sort by
Showing 20 of 35 results by botnet
The latest version of cgminer detects my K16s, but I have the same slow hashrate issue. What's odd is they seem to perform better running solo than when combined on the same machine.
Do I special version of cgminer for windows built with klondike support, or does the latest version have that built in already?
Do I special version of cgminer for windows built with klondike support, or does the latest version have that built in already?
1) logred_set_scanf(a, "a00 + a00");
logred_set_reduce(a);
logred_set_printf(a);
Shouldn't that always produce 0? for me it outputs a00
Nope. A or A == A. A or !A == 1 and A!A = 0logred_set_reduce(a);
logred_set_printf(a);
Shouldn't that always produce 0? for me it outputs a00
Ahh, there was misunderstanding about the + operator.
I've been thinking about arithmetic operations mod 2, where "(a+b) mod 2" is equivalent to XOR
0+0 = 0, 0 mod 2 = 0
0+1 = 1, 1 mod 2 = 1
1+0 = 1, 1 mod 2 = 1
1+1 = 2, 2 mod 2 = 0
= XOR
Playing a bit here, turns out the A=A+AB and A+B=A+!AB reductions have no effect in 32bit add. Guess that's what makes it a nice 32bit bijection.
Download logred_v4.zip which will be faster for your application.
You can disable those reduction algorithms by commenting out logred_set_reduce_2_A_AB() and logred_set_reduce_4_A_nAB_n() inside logred_set_reduce()
Download logred_v4.zip which will be faster for your application.
You can disable those reduction algorithms by commenting out logred_set_reduce_2_A_AB() and logred_set_reduce_4_A_nAB_n() inside logred_set_reduce()
Been trying this out, so many questions...
1) logred_set_scanf(a, "a00 + a00");
logred_set_reduce(a);
logred_set_printf(a);
Shouldn't that always produce 0? for me it outputs a00
2) Similarly I would expect (a + !a) = 1
logred_set_scanf(a, "a00");
logred_set_not(b, a);
logred_set_xor(c, a, b);
= crash
3) Haven't debugged enough, but part 2 could be related to this?:
logred_set_scanf(a, "!a00!b00"); = works
logred_set_scanf(a, "!a00"); = crash
4) Actually, is there support for numeric literals (0, 1)? c = a+b is purely symbolic, but during SHA256 you add in those K-Constants which can sometimes help reduce things further.
4) x64 only? This is giving me heap problems:
#define VAR_T size_t
#define VAR_T_SIZE_BITS ( 8 * sizeof(VAR_T) )
#define VAR_A_BITS 256
#define VAR_A_LEN 4L
(worked around setting VAR_A_BITS = 128... maybe this is the source of all my problems?
)I'll PM you a link to my C code for logic reduction in a few mins. You can compile C right? And know how to code? It should be quite a bit faster than Mathmatica or Maple.
It uses de Morgan's rules and some basic reduction rules to optimize the circuit.
It uses de Morgan's rules and some basic reduction rules to optimize the circuit.
This is excellent by the way
I will start integrating with my code. Right now my stuff is all C#, so I will have to compile your code into a lib and do marshaling - though at first glance of your API I don't think marshaling will have too bad of a perf impact. I'll try with c=a+b to test the runtime and validate the results match yours. Do you know how your de Morgan approach compares to this Quine McCluskey one I keep reading about? http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
Cool. How are you generating the formulas? Iterating through each input possibility?
The 8th bit "explosion" is probably due to triggering the use of a 2nd path of 32bit addition.
The formulas for 32bit add (64 in, 32 out) get very large very quickly (http://jlcooke.ca/btc/sha256_logred_formulas.html) due to carry bits. Result r_31 depends on a_31 .. a_0 and b_31 .. b_0.
The 8th bit "explosion" is probably due to triggering the use of a 2nd path of 32bit addition.
The formulas for 32bit add (64 in, 32 out) get very large very quickly (http://jlcooke.ca/btc/sha256_logred_formulas.html) due to carry bits. Result r_31 depends on a_31 .. a_0 and b_31 .. b_0.
To generate formulas, I do an in-order walk of the tree, and simplify at each level going up... although I'm not sure I fully understand your quesiton.
Quick update, I've been trying out Maple as a potential replacement for Mathematica. BooleanSimplify chokes on even 8 bits, but doing simplify( (arithmetic expression mod 2, {a*a-a, b*b-b, c*c-c, ....}) does way better. Maple seems to evaluate these expressions an order of magnitude faster than mathematica, although the resulting equations aren't as compact. It also consumed a modest 300 megs of memory for 8 bits. Still learning the maple syntax so things might improve.
Any updates?
Memory is the big issue right now, trying to run simulations to determine how much ram will be needed.
I did runs with 4, 6, 7, and 8 symbolic input bits to see the peak working set of the mathematica kernel. I picked bits from nonce to be symbolic, and the fixed bits came from a previously solved blockheader.
4 bits: 79,312 K
6 bits: 84,720 K
7 bits: 89,372 K
8 bits: 850,800 K
What's odd is it looked very linear until 8 bits were reached; It's running now with 9 bits across 4 cores, I'll have those results in about 30 hours.
I also computed the equation length after PolynomialReduce at each node in the tree; I trust all the data except for '7 bits' where I maybe have recorded it wrong:
4 bits: median: 25, max: 62
6 bits: median: 170, max:222
7 bits: median: 379, max:495
8 bits: median: 919, max:1218
There the growth does appear linear.
For 8 bits I also computed the number of nodes that contained two leaf node children. This is essentially the number of equations that can be simplified in parallel (before any potential adjustments to the tree.) Is there a word for this type of node?
median: 17, max:96
I can post the output equations if anyone is interested.
Lastly, I would be open to try any other symbolic computation engines that support modulus->2 to compare speed and memory consumption. Any suggestions?
Thoughts? Make sure you have 32GB of RAM installed 
Do you guys know how often 'Version' changes in the block header? Or more specifically, can any bits in the block header can be treated as constant for some extended period of time, for the purposes of mining?
I am running into some memory concerns, mostly due to all the parallelization. The fewer variables in these equations the better
Hehe. I like encouraging people to explore this. Good learning "exorcize" (pun). 32 bit addition logic for botnet: http://jlcooke.ca/btc/sha256_logred.html
Just do that about 768 times and reduce!
Just do that about 768 times and reduce!
your c1...c31 bits can be reduced by one instruction
c1 == a1b1 + a1c0 + b1c0
== a1(b1+c0) + b1c0
Let's let the OP try to write up the logic formula for SHA256's first 32 bits of input and 1 bit of output.
Thanks for the links.
I rewrote the code so that it performs the double SHA256 first, constructing an in-memory tree of all the operations and variables (without actually evaluating them, arithmetically or symbolically.) So basically for each bit in the final hash, I have a tree representing all the operations that have to occur (using an in-order walk) to compute that bit.
What this allows me to do is simplify different branches of the trees independently, and in parallel on different threads. The other thing it gives me is the ability to see the current depth of the tree I'm trying to simplify, which will give me some "order of magnitude" guess of how large the final equation will be.
There's thousands of these branches to simplify and they do take a very long time, but watching them in the debugger, things are reducing and it's not ballooning out of control (yet.)
If everything looks good, the longer term plan is to assign branch simplification to different datacenter machines, so that I can have a few thousand of them simplifying in parallel instead of 8 on my desktop.
a colleague of mine noted the symbolic addition follows a recurrence relation pattern and hence might be simplified by these means: http://en.wikipedia.org/wiki/Recurrence_relation
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.
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.
I think there is some misunderstanding of the technique that I will try and clear up with an example. It should in fact give an exact solution, not an approximate one.
As mentioned, traditional bitcoin mining performs target=SHA256(SHA256(header+nonce)), looking for a very specific solution (top 4 bytes of 'target' are 0.) Mining today uses a brute force approach, iterating through every possible nonce value in the 32 bit address space, performing the double SHA256, and looking at the result to check if those top 4 bytes are 0.
In my example here, rather than the function target=SHA256(SHA256(header+nonce)), let's start with a very simple function:
target = (nonce + 0xAD) ^ 0x6E;
(Assume we're working with 8 bit numbers for this example.)
Just like mining, let's try to find a value for 'nonce' such that target = 0; Mining today would try and brute force try all possible values for 'nonce' until that condition is satisfied, e.g:
for(nonce = 0; nonce <= 255; nonce++)
{
target = (nonce + 0xAD) ^ 0x6E;
if(target == 0)
return nonce;
}
In my proposed approach, this is done symbolically. First, symbolically do the addition and Xor operations to produce a set of equations that represents each of the 8 bits of 'target' in terms of the 8 bits of 'nonce'
t0: (!n0)
t1: (Xor[1, n0, n1])
t2: (Xor[n2, n1 && n0])
t3: (Xor[1, !n3, n2 || (n1 && n0)])
t4: (Xor[n4, n3 || n2 || (n1 && n0)])
t5: (Xor[1, n4 && (n3 || n2 || (n1 && n0)), !n5])
t6: (Xor[1, n6, n5 || (n4 && (n3 || n2 || (n1 && n0)))])
t7: (Xor[n6 && (n5 || (n4 && (n3 || n2 || (n1 && n0)))), !n7])
Now we can solve the system of equations, which will give us values for n0...n7 which satisfy the condition that t0...t7 == 0; This will not be an approximation, we will get exact values for each bit.
As mentioned earlier, we convert the logical operations to arithmetic operations, modulo 2:
t0: (1+n0)
t1: (1+n0+n1)
t2: (n0*n1+n2)
t3: (n2+n0*n1*(1+n2)+n3)
t4: (n2+n3+n2*n3+n0*n1*(1+n2)*(1+n3)+n4)
t5: ((n2+n3+n2*n3+n0*n1*(1+n2)*(1+n3))*n4+n5)
t6: (1+n5+(n2+n3+n2*n3+n0*n1*(1+n2)*(1+n3))*n4*(1+n5)+n6)
t7: (1+(n5+(n2+n3+n2*n3+n0*n1*(1+n2)*(1+n3))*n4*(1+n5))*n6+n7)
And now we can solve (done using wolfram mathematica):
In[1] := Solve[(1 + n0) == 0 && (1 + n0 + n1) == 0 && (n0*n1 + n2) == 0 && (n2 + n0*n1*(1 + n2) + n3) == 0 && (n2 + n3 + n2*n3 + n0*n1*(1 + n2)*(1 + n3) + n4) == 0 && ((n2 + n3 + n2*n3 + n0*n1*(1 + n2)*(1 + n3))*n4 + n5) == 0 && (1 + n5 + (n2 + n3 + n2*n3 + n0*n1*(1 + n2)*(1 + n3))*n4*(1 + n5) + n6) == 0 && (1 + (n5 + (n2 + n3 + n2*n3 + n0*n1*(1 + n2)*(1 + n3))*n4*(1 + n5))*n6 + n7) == 0 && n0*n0 - n0 == 0 && n1*n1 - n1 == 0 && n2*n2 - n2 == 0 && n3*n3 - n3 == 0 && n4*n4 - n4 == 0 && n5*n5 - n5 == 0 && n6*n6 - n6 == 0 && n7*n7 - n7 == 0, {n0, n1, n2, n3, n4, n5, n6, n7}, Modulus -> 2]
Out[1] = {{n0 -> 1, n1 -> 0, n2 -> 0, n3 -> 0, n4 -> 0, n5 -> 0, n6 -> 1, n7 -> 1}}
You can see this produced the exact solution: 11000001 == 0xC1 == 193, which does in fact validate:
(0xC1 + 0xAD) ^ 0x6E == 0
Now we just expand this for bitcoin mining. Do everything I did above, but with the symbolic version of SHA256(SHA256(block_header)) rather than my simple example. Take the first 32 equations from this result set (corresponding to the 4 bytes we want to be 0), and fill in literal values from the block header for everything except for the 32 bits of nonce we want to solve for. Now solve the system of equations; we get the exact bits for nonce that produces a target with the first 4 bytes zeroed.
Again, the symbolic SHA256 stuff can all be computed offline and saved - the computation part of mining now will just be solving that system of 32 equations, which mathematica (or another symbolic math module) can do incredibly fast. Much faster than my GPU can brute-force every possible nonce combination.
What do you mean with the word PolynomialReduce? Do you mean polynomial reduction?
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)
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.
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)
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.
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?
I barrowed from your design and made some improvements
http://www.youtube.com/watch?v=j8ru5Mz9Xqw
http://www.youtube.com/watch?v=j8ru5Mz9Xqw