Author

Topic: Simple mining demo & educational tool (Read 1138 times)

full member
Activity: 219
Merit: 100
March 31, 2013, 08:23:44 PM
#3
The interesting thing about this last example is that we requested 4 leading '0's in the hash and out of 200k samples we got 7 positive results, however expectation was to get only 2^(4 * 4)/200k~=3, so we were lucky. If we make just one small change in the string we are hashing by adding _ in the sent_to we get only 4 positive results in 200k tries, but we do also get one 5 '0' result:

Search for a sha256 of "Abe_sent_to_Bob_1.0BTC_noonce="+noonce where noonce=1..200000 with 4 leading zeros (0000) over 8 threads.
worker 1 0 24999
worker 2 25000 49999
worker 3 50000 74999
worker 4 75000 99999
worker 5 100000 124999
worker 6 125000 149999
worker 7 150000 174999
worker 8 175000 199999
4428 4912 2900 9016 8896 5892 7968 9116
35987:00008be2fad58980ccb07770cb6fdcd5738ea8e01001c3d2dd3f5aebcc952051
168822:00004854a5ea7532713f69d7e5cb1052277f3e47e86886710a4abe748a86525f
170766:000002b6c8dcbc65b363de776bd856a77f113652b0e209e402ad2135d7724296
145679:0000563da0da65d1c6559e176e3e8a5022f8d37fba483b95af54bb714ed629ce
Done.
real    26m 42.37s
user    22m 7.97s
sys     46m 40.64s


In general we need 2^(4 * #_of_lead_0s) tries to get one positive result. so for:

#_of_lead_0sNoonce_hash_triesTime 1 GH/s miner would take
11616 ns
22560.3 us
34'0964 us
465'53665 us
51'048'5761 ms
616'777'21616 ms
7268'435'4560.3 s
84'294'967'2964 s
968'719'476'7361 min
101'099'511'627'77618 min
1117'592'186'044'4165 h
12281'474'976'710'6563 days
134'503'599'627'370'4961.7 months

note that real life hash example from previous post had 13 '0's in it. Now "target" below which hash must fall in order to be considered as a valid signature for a block in Bitcoin network is set much more granularly than in the case above where we just count '0's, but the concept is the same.

Cheers!
19USHJYiFCZvX5mpFSNHPKh3yvJN4yuGN
full member
Activity: 219
Merit: 100
March 31, 2013, 07:43:58 PM
#2
Slightly modified shamine.sh is a bit faster as I have removed an old piece of code used to debug:

Code:
#!bash

# num of 0
L=4

# num of hashes
N=200000

# num of threads
TH=8

# hash string
hstr="Abe_sentto_Bob_1.0BTC_noonce="

# init ZeroS
ZS=""
for i in `eval echo {1..$L}`
do
  ZS=$ZS"0"
done

# usage worker Nfrom Nto
function worker
{
  {
    for i in `eval echo {$1..$2}`
    do
      r=$(./sha256 $hstr$i)
      if [ ${r:0:L} = $ZS ]
      then
        echo $i":"$r
      fi
    done
  } &
}

# main loop
echo "Search for a sha256 of \""$hstr"\"+noonce where noonce=1.."$N" with "$L" leading zeros ("$ZS") over "$TH" threads."
PIDS=""
for i in `eval echo {1..$TH}`
do
  echo "worker" $i $[ ( $i - 1 ) * $N / $TH ] $[ $i * $N / $TH - 1]
  worker $[ ( $i - 1 ) * $N / $TH ] $[ $i * $N / $TH - 1]
  PIDS="$PIDS $!"
done
echo $PIDS
wait
echo "Done."

It produces the following result:


[Arijan.tosh] → time ./shamine.sh
Search for a sha256 of "Abe_sentto_Bob_1.0BTC_noonce="+noonce where noonce=1..200000 with 4 leading zeros (0000) over 8 threads.
worker 1 0 24999
worker 2 25000 49999
worker 3 50000 74999
worker 4 75000 99999
worker 5 100000 124999
worker 6 125000 149999
worker 7 150000 174999
worker 8 175000 199999
3484 7968 5776 6452 984 5332 8024 8148
75127:0000825ea95a41c68a7fc3e4aa43e34377cb51644496eb6ec33ff7a9a1d6b446
150156:000015c122346ed9c1bf7971ea74e867d4fe8e8df85da2b228b7980192e404f8
53569:0000d125978869aef0b6eceddb9b8a0c774fdca45343fba0e3d6936d79b85e2c
10492:0000cb6a6cb6df5d3abe045d4c454b1a0aa5ab3361a946bb10dabea97a6ec46a
40296:0000f60757fa9b3b8921751eb889c409483511cc3173f7e1ca5e8b473b5b2b0b
169376:00001efa1eb0fa593c2fbf2c0a21447a40bfb8b0c4f6da2a090595e6652edea5
199332:0000310918747d3ee431e4c2e68b89f7883695d6f1c21e0252fb0ea3d19c5bc9
Done.
real    26m 3.19s
user    21m 38.69s
sys     44m 59.68s


we can verify result with:


[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC_noonce=150156
000015c122346ed9c1bf7971ea74e867d4fe8e8df85da2b228b7980192e404f8
full member
Activity: 219
Merit: 100
March 31, 2013, 06:43:31 PM
#1
Hi All,

I had some spare time this afternoon and I came up with one bash shell script and one .c source which will generate hashes and finds ones with some '0' in them at the front.

The point of this exercise is not to excel in speed & efficiency but rather to show someone how mining works and perhaps to see how difficult mining really is.

To start I used sha256 implemented in C by Brad Conte (http://bradconte.com/sha256_c). Any Linux/BSD system will compile the sha256.c file by issuing "cc sha256.c -o sha256", you can use "cc -O3 sha256.c -o sha256" if you feel that extra optimisation is needed Smiley
If you are using Windows I suggest downloading Cygwin (http://www.cygwin.com/) or MobaXterm, which is what I used (http://mobaxterm.mobatek.net/) in the later case please be sure to download gcc & development tools plugin which can be found on the plugins page. Both these tools will allow you to comfortably use cc commands as if you were on linux.

once compiles sha256 will produce a hash on any input say:

[Arijan.tosh] → ./sha256 abc
ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad


or a more realistic example geared towards mining:

[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC
37ee5903b981270f19bdc2a47d5a9a69467d139fe04d0b226240e9b0ff0f1a43


or a bit further:

[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC_noonce=1
72a7e10d7dcd9354de9c3f3d86b9e130be92121bf26c370e598880242a557ed5

[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC_noonce=2
abe9b13d11e818f7d1fca70d3d6132a6ef74e59e1b1baeb71cab6f0ee3d18832

[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC_noonce=3
470c5e62f576d9412c98260013df8399d2c76482d83282297d026aa8e437e8af

[Arijan.tosh] → ./sha256 Abe_sentto_Bob_1.0BTC_noonce=300
104068881ee8610653c75d04f785af807c371d7fc776ecf344e2f2e4ebc782b5


please use any public sha256 generator as a reference that these hashes are indeed correct. Google will help you...

as you can see changing an arbitrary number at the end of simplified transaction changes the hash completely. If we were to make those changes long enough we would find a hash which has some special arbitrary defined characteristics. In the case of Bitcoin that would be a has that is low enough, i.e. that has lot's of '0' in front. This is where "shamine.sh" comes into play as it does just that automatically for you. You can tweak it by editing a few lines at the beginning:

# num of 0, it is specifying how many 0s hash needs to have in front in order to be printed
L=3

# num of hashes, that is how many hashes we try from 1 to 100'000
N=100000

# num of threads, most modern computers have more than 1 core so why not putting number of cores here just so speed things a little
TH=4

# hash string, what is the "transaction string" that we are hashing, a more realistic example would be: "A_sent_to_B_1BTC_noonce="
hstr="aaa"


sample run on my laptop with these parameters will run for about 30min and will produce following output:

[Arijan.tosh] → time ./shamine.sh
Search for a sha256 of "aaa"+noonce where noonce=1..100000 with 3 leading zeros (000) over 4 threads.
worker 1 0 24999
worker 2 25000 49999
worker 3 50000 74999
worker 4 75000 99999
5992 6664 5248 8420    <------ these are process IDs
75076:00022ca5b45eb72a059c05ceac286c9e4f531820e587bcd0781c1fc17389200e   <--- shows "noonce" and resulting sha256 hash
50651:0005376009f975e98adcbc1a103b169ed2d5f1c20765c3332d9399a5e1a4dfbb
50998:000af580951c7ee4083f59ee8203aab62e4368d3b2a224acb790e7e9a9043d83
53334:0008f75a23614a0b69032efbbd35198f77e2dcdb18f9101ed4296bc17e319f50
4628:000c4c1ff5dd5c692fdf60f4939e9643c836d80e6d602e233484bfcf61465ae5
29799:0005a24dea70a97d05e5c581a674f11d5aec4dc3f941e86e4b668d453a092b45
80610:000cb6eae48517c72b5f933716a15438f5ccfd5a6906355c25f7d57fb9f4cf20
30753:000135418479ba81f84a0a22d0d57e7620abed881f17f5b1f4a2f85a67aa9561
33108:000662a7f13f2de4eb937bed8180200c45c11d36ac3ee3d20f4640bd27aa8215
34427:00098f593bdc7aeecfb6418ccbb73627534e11cbe51739607e8b7df47bcaeb04
85445:000dddbbbf8e2c57f4e92d85b5b08fe8b1671aa4bf408d5dd83e32fd42013fd1
35492:000244997febcb7e5c50d900ea83b1b4699d8085610bad9ef9422e66e714b501
36118:00010173d288439c2ab4f02bfae3d41e20e89aea6e0e9e95d98bb03f39c11e9a
36689:000602971f51906acb842c1f348ad6788394c959bdb12b51bf9bf4efcdb93546
87391:0007afcb4e3cf9bbda2c208119ad8e1986530e1ac8be066965474834e0f4020d
64651:00055c0c37d14ea475a3ab699f8e756d7f13da1fa917b31c4ff0be3b6ba569c6
15766:0005f99b4f0fc9a94380d18051575cbe557ae96f481a230e859a5733e950fc9c
91226:000eb2bf26ae2010bfe0c0535ad53a16b1d2d4ffbcff8d933047a02f883754f5
42372:00016a862ddd1ad5f00a8c744e759c4d6fac7180c1cc5bbfa9767f9fd85578ca
93293:0003a676aef623b768a3f2b96a54b1c676ad6185cae96476909e15b7a57ef471
93651:000cbf3fecf2555093149a4aa0d8c8710a3253a01c12b17016dcdbcd23043713
96708:0007bb61cf5a0aa70d67a939296b7d2a1e043195cd84ed10f2faaecc2fa006f8
97698:00093644960f08f67fcdc325f732c03e5ea6d0558a8942e6066530fd0fa239c2
74474:00081786785796b4081fdf51bb9de8f447452a8550f0ef8626ac0b4987570d94
49862:000ef69f74fba11a4d1fab2f84b43f064f9b5ff16012fc08861310db770187fb
24925:0004783e8000e5651a930a2c1813da29795e00574daf16f7ceabd2641f4d3cab
Done.
real    21m 16.41s
user    17m 12.94s
sys     36m 0.22s


Again this examples will work in linux/BSD and windows (via MobaXterm or similar), so it si quite useful as a demonstration tool. Please note that no four '0' hash was found in the first 100'000 hashes. This goes to show how difficult is to find a real world bitcoin hash like this one: 0000000000000274facba8aec660aa8f1cb609017084882f6f0ad861cb17d8ad. Also please note that due to 4 concurrent processes running in parallel, first trying hashes with noonces from 1..24999, second from 25000 to 49999, etc., resulting hashes are not sorted, which again mimics real world Bitcoin hashing.

I plan to develop this a little further if I find the time, my ideas are along these lines and of course your ideas are welcome:
- implement double hashing same way Bitcoin protocol does, just to show the difficulty in computing
- possibly get "real" block data just to show that noonces in solved blocks really yield low hashes with lot's of '0's.
- using pseudo random noonces instead of linear ones to simulate multiple miners more realistically.
- ...

Sources are below, if you find this useful and worthy of donation do not hesitate to send some to 19USHJYiFCZvX5mpFSNHPKh3yvJN4yuGN.

Cheers!

Code:
#!bash
#
# shamine.sh

# num of 0
L=3

# num of hashes
N=100000

# num of threads
TH=4

# hash string
hstr="aaa"

# init ZeroS
ZS=""
for i in `eval echo {1..$L}`
do
  ZS=$ZS"0"
done

# usage worker Nfrom Nto
function worker
{
  {
    for i in `eval echo {$1..$2}`
    do
      r=$(./sha256 `echo $hstr$i`)
      if [ ${r:0:L} = $ZS ]
      then
        echo $i":"$r
      fi
    done
  } &
}

# main loop
echo "Search for a sha256 of \""$hstr"\"+noonce where noonce=1.."$N" with "$L" leading zeros ("$ZS") over "$TH" threads."
PIDS=""
for i in `eval echo {1..$TH}`
do
  echo "worker" $i $[ ( $i - 1 ) * $N / $TH ] $[ $i * $N / $TH - 1]
  worker $[ ( $i - 1 ) * $N / $TH ] $[ $i * $N / $TH - 1]
  PIDS="$PIDS $!"
done
echo $PIDS
wait
echo "Done."

Code:
# sha256.c, original at http://bradconte.com/sha256_c

#include
#include
#include

// Signed variables are for wimps
#define uchar unsigned char // 8-bit byte
#define uint unsigned long // 32-bit word

// DBL_INT_ADD treats two unsigned ints a and b as one 64-bit integer and adds c to it
#define DBL_INT_ADD(a,b,c) if (a > 0xffffffff - (c)) ++b; a += c;
#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))
#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

typedef struct {
   uchar data[64];
   uint datalen;
   uint bitlen[2];
   uint state[8];
} SHA256_CTX;

uint k[64] = {
   0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
   0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
   0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
   0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
   0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
   0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
   0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
   0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
};


void sha256_transform(SHA256_CTX *ctx, uchar data[])

   uint a,b,c,d,e,f,g,h,i,j,t1,t2,m[64];
     
   for (i=0,j=0; i < 16; ++i, j += 4)
      m[i] = (data[j] << 24) | (data[j+1] << 16) | (data[j+2] << 8) | (data[j+3]);
   for ( ; i < 64; ++i)
      m[i] = SIG1(m[i-2]) + m[i-7] + SIG0(m[i-15]) + m[i-16];

   a = ctx->state[0];
   b = ctx->state[1];
   c = ctx->state[2];
   d = ctx->state[3];
   e = ctx->state[4];
   f = ctx->state[5];
   g = ctx->state[6];
   h = ctx->state[7];
   
   for (i = 0; i < 64; ++i) {
      t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
      t2 = EP0(a) + MAJ(a,b,c);
      h = g;
      g = f;
      f = e;
      e = d + t1;
      d = c;
      c = b;
      b = a;
      a = t1 + t2;
   }
   
   ctx->state[0] += a;
   ctx->state[1] += b;
   ctx->state[2] += c;
   ctx->state[3] += d;
   ctx->state[4] += e;
   ctx->state[5] += f;
   ctx->state[6] += g;
   ctx->state[7] += h;


void sha256_init(SHA256_CTX *ctx)

   ctx->datalen = 0;
   ctx->bitlen[0] = 0;
   ctx->bitlen[1] = 0;
   ctx->state[0] = 0x6a09e667;
   ctx->state[1] = 0xbb67ae85;
   ctx->state[2] = 0x3c6ef372;
   ctx->state[3] = 0xa54ff53a;
   ctx->state[4] = 0x510e527f;
   ctx->state[5] = 0x9b05688c;
   ctx->state[6] = 0x1f83d9ab;
   ctx->state[7] = 0x5be0cd19;
}

void sha256_update(SHA256_CTX *ctx, uchar data[], uint len)

   uint t,i;
   
   for (i=0; i < len; ++i) {
      ctx->data[ctx->datalen] = data[i];
      ctx->datalen++;
      if (ctx->datalen == 64) {
         sha256_transform(ctx,ctx->data);
         DBL_INT_ADD(ctx->bitlen[0],ctx->bitlen[1],512);
         ctx->datalen = 0;
      } 
   } 


void sha256_final(SHA256_CTX *ctx, uchar hash[])

   uint i;
   
   i = ctx->datalen;
   
   // Pad whatever data is left in the buffer.
   if (ctx->datalen < 56) {
      ctx->data[i++] = 0x80;
      while (i < 56)
         ctx->data[i++] = 0x00;
   } 
   else {
      ctx->data[i++] = 0x80;
      while (i < 64)
         ctx->data[i++] = 0x00;
      sha256_transform(ctx,ctx->data);
      memset(ctx->data,0,56);
   } 
   
   // Append to the padding the total message's length in bits and transform.
   DBL_INT_ADD(ctx->bitlen[0],ctx->bitlen[1],ctx->datalen * 8);
   ctx->data[63] = ctx->bitlen[0];
   ctx->data[62] = ctx->bitlen[0] >> 8;
   ctx->data[61] = ctx->bitlen[0] >> 16;
   ctx->data[60] = ctx->bitlen[0] >> 24;
   ctx->data[59] = ctx->bitlen[1];
   ctx->data[58] = ctx->bitlen[1] >> 8;
   ctx->data[57] = ctx->bitlen[1] >> 16; 
   ctx->data[56] = ctx->bitlen[1] >> 24;
   sha256_transform(ctx,ctx->data);
   
   // Since this implementation uses little endian byte ordering and SHA uses big endian,
   // reverse all the bytes when copying the final state to the output hash.
   for (i=0; i < 4; ++i) {
      hash[i]    = (ctx->state[0] >> (24-i*8)) & 0x000000ff;
      hash[i+4]  = (ctx->state[1] >> (24-i*8)) & 0x000000ff;
      hash[i+8]  = (ctx->state[2] >> (24-i*8)) & 0x000000ff;
      hash[i+12] = (ctx->state[3] >> (24-i*8)) & 0x000000ff;
      hash[i+16] = (ctx->state[4] >> (24-i*8)) & 0x000000ff;
      hash[i+20] = (ctx->state[5] >> (24-i*8)) & 0x000000ff;
      hash[i+24] = (ctx->state[6] >> (24-i*8)) & 0x000000ff;
      hash[i+28] = (ctx->state[7] >> (24-i*8)) & 0x000000ff;
   } 


int main(int argc, char **argv) {
    if (argc > 1) {
//     printf("sizeof(uint)=%d\n", sizeof(uint));
//     printf("argv[1]=\"%s\"=", argv[1]);
       SHA256_CTX ctx;
       sha256_init(&ctx);
       uint i;
       for (i = 0; argv[1][i]; i++);
//         printf("%.2x", (uint) argv[1][i]);
//     printf("\n");
       sha256_update(&ctx, argv[1], i);
       uchar hash[32];
       sha256_final(&ctx, (uchar *) hash);
       for (i = 0; i < 32; i++)
           printf("%02x", hash[i]);
       printf("\n");
    }
   
    return(0);
}
Jump to: