Large Bitcoin Collider (Collision Finders Pool)

[Janu$$]

@rico666
"....Because we assume the private keys to addresses with funds on them are also uniformly distributed in the search space, this means that the effective search space until any collision for these is found is 160bit - log2(9000000)bit = ~137bit."

I might be wrong, but because of this (wolfram alpha expression):

1-(((2^21)! * (2^160 über  2^21))/((2^160)^(2^21))) 

I'm not sure I follow this. (mathematically I do, but semantically I don't)

Where do you get the 2²¹ from? Thats 2M.

I assume the possibilty of hitting one of your approximately 2,5 mil target addresses is:
1.5*10^-36  or  1/(2^119)

We have 14 mil target addresses at the moment.

If you agree with the things written above, I would recommend to expand the target address space to 2^23 (8.x mil pub keys)
and gain a 4 times higher possibility to hit one of your targets:
2.4*10^-35 or or  1/(2^115)

It's still 160 - log₂(14000000) = ~ 136.26bit search space


Rico

Hello Rico,

what I wanted to submit was that in terms of prohability you should consider to expand your public address list for comparision from about 2.x million to 8.y million pub keys. I have read somewhere, maybe in some older postings, that your address list covers only 2.5 million addresses. As you know the birthday paradox (https://en.wikipedia.org/wiki/Birthday_problem) says with an increasing number of persons (in our example: public addresses) the prohability to find 2 with the same birthdays (in our example: RIPEMD-160 hash number) increases exponentially.

2 million addesses give us a prohability of:
1-(((2^21)! * (2^160 über  2^21))/((2^160)^(2^21))) = 1.504 × 10^-36
or differently:
1-e^((-2^21*(2^21-1))/(2*2^160)) = 1.504 × 10^-36

8 million addesses give us a prohability of:
1-e^((-2^23*(2^23-1))/(2*2^160)) =2.407 × 10^-35

4 times more public addresses give a 16 times higher prohability to hit one target. That´s why I suggested to expand the public key address space. Want I did not know at the time of writing that you already expand your list to 14 million addresses.

So your prohability with 14 million addresses for each key you are generating at the moment is about:
1-e^((-2^23.7389*(2^23.7389-1))/(2*2^160)) = 6.70521 × 10^-35
or simpler as we have big numbers:
(2^23.7389)^2/(2*2^160) = 6.70521 × 10^-35


Besides that, I came across an interessting article about increasing the prohability of collision through interating hash functions:
https://security.stackexchange.com/questions/61756/wont-all-hashes-collide-after-enough-iterations-with-a-static-salt
and
http://crypto.stackexchange.com/questions/15068/entropy-when-iterating-cryptographic-hash-functions

N(hash1)>N(hash2)>N(hash3)>N(hash4)....>N(hashx)
due to collisions and the lacking to use the full 256 rsp. 160 bit space.
4 hashes have to be done to create a bitcoin address. This is surely reducing the number of different pub addresses further.
The collisions and mapping errors of each hash level causing an exponential effect in reducing the output.
That is giving you a better prohability than 6.70521 × 10^-35.

Reagrds,
Janu$$

[1714914527]

1714914527

[1714914527]

1714914527

[1714914527]

1714914527

[rico666]

So your prohability with 14 million addresses for each key you are generating at the moment is about:
1-e^((-2^23.7389*(2^23.7389-1))/(2*2^160)) = 6.70521 × 10^-35
or simpler as we have big numbers:
(2^23.7389)^2/(2*2^160) = 6.70521 × 10^-35

Interesting. I thought the probability is 1/2^{(160-23.7389)} = ~ 9.52 x 10^-42

Now I am at the moment in the middle of the rollout of the new client, so I cannot dig deeper into this, but I will certainly have a look for the explanation of this 7 orders of magnitude discrepancy.

Thanks!


Rico

[icanscript]

I see the client is created in perl, will there be support for windows? strawberry perl or such.

An ISO Live Image may be good for people who have a GPU and are not running linux.

Cuda and OCL?

[rico666]

I see the client is created in perl, will there be support for windows? strawberry perl or such.

An ISO Live Image may be good for people who have a GPU and are not running linux.

Cuda and OCL?

At the moment an easy-to-use ISO for windows users would be the best option (in any case for the GPU client, but also welcome for the CPU client).

The generator is written in C/OpenCL. As for a native windows client: The Perl client (LBC) is not the problem (it does run on Strawberry and we had a windows version already - the source still has rudimentary support for it in it's DNA), the problem is the generator using some libc memory management intrinsics.

=> I would happily give GPUauth=1 to anybody who would do a decent easy-to-use robust GPU (Nvidia and AMD) and CPU support LBC image ISO.  

Of course it would still have to go through a rigorous review process for trojans/viruses etc. but I believe it would be a very welcome addition for the Win-users with nifty GPUs.

Ideally, it would be a minimal Linux which would boot from USB stick. As for "live-image" - LBC does auto-update itself (BLF, generator and the LBC itself), so there should be a writable partition on the USB stick else people would have to load a new version of the ISO over and over again. (and I wouldn't have the time to review the images that often - thus not authorize them)


Rico


edit: I see you all left the #666 post for me - how nice of you.

[icanscript]

I see the client is created in perl, will there be support for windows? strawberry perl or such.

An ISO Live Image may be good for people who have a GPU and are not running linux.

Cuda and OCL?

At the moment an easy-to-use ISO for windows users would be the best option (in any case for the GPU client, but also welcome for the CPU client).

The generator is written in C/OpenCL. As for a native windows client: The Perl client (LBC) is not the problem (it does run on Strawberry and we had a windows version already - the source still has rudimentary support for it in it's DNA), the problem is the generator using some libc memory management intrinsics.

=> I would happily give GPUauth=1 to anybody who would do a decent easy-to-use robust GPU (Nvidia and AMD) and CPU support LBC image ISO.  

Of course it would still have to go through a rigorous review process for trojans/viruses etc. but I believe it would be a very welcome addition for the Win-users with nifty GPUs.

Ideally, it would be a minimal Linux which would boot from USB stick. As for "live-image" - LBC does auto-update itself (BLF, generator and the LBC itself), so there should be a writable partition on the USB stick else people would have to load a new version of the ISO over and over again. (and I wouldn't have the time to review the images that often - thus not authorize them)


Rico

I can have a look at this as I have a fair bit of experience with linux and arch seems a good use for this. dont worry about the gpuauth=1 yet, il see if I can get an iso up and running with the client and right dependencies installed first and then I can get back to you on that. Also being arch and minimal it will be easier to go over for the review process.

I also have a fair bit of time on my hands at the moment, so it may do me some good

[TooDumbForBitcoin]

So your prohability with 14 million addresses for each key you are generating at the moment is about:
1-e^((-2^23.7389*(2^23.7389-1))/(2*2^160)) = 6.70521 × 10^-35
or simpler as we have big numbers:
(2^23.7389)^2/(2*2^160) = 6.70521 × 10^-35

Interesting. I thought the probability is 1/2^{(160-23.7389)} = ~ 9.52 x 10^-42

Now I am at the moment in the middle of the rollout of the new client, so I cannot dig deeper into this, but I will certainly have a look for the explanation of this 7 orders of magnitude discrepancy.

Thanks!


Rico

This revelation is of equal, if not greater, significance to Alan Guth's discovery in 1979 of the exponential expansion of the universe, doubling in size 100 times for 10^-35 seconds right after the Big Bang.

An instant 7-magnitude increase in the Bitcoin Big Banger, in one post!  This should win the Nobel Cryptocurrency Prize.

[rico666]

Hi colliders!

New versions of the SSE42, AVX2 and Skylake  hrd-core generators are now available. These use the arulbero-ECC library instead of the libsecp256k1 and give a nice keyrate bump. It's not as big as for the GPU-accelerated versions (soon to come), but still pretty decent. It seems the sse42 version profits most.

SSE42: +79%
AVX2: +29%
Skylake: +6%

There will be no SSE41 or 32bit-generic versions available. If you run one of these, put a "no_update": 1, line in your lbc.json.
edit: but there will be a 64bit generic binary available!


How to update?

1) End your LBC by pressing "e" and wait until you see the shell prompt.

2) type in ./LBC -u, it will update the generator (and may even the BLF)

Code:

# LBC -u
New generator found. (DL-size: 0.54MB)
BLF patch found. (DL-size: 206.96MB)
Finished update run - system up to date.

3) type in ./LBC -x to test and benchmark the new generator. You should see a better maximum keyrate.

4) Ready to go!


Rico

[unknownhostname]

ubuntu@instance-5:~/collider$ ./LBC -u
Finished update run - system up to date.

ubuntu@instance-5:~/collider$ ./LBC -x
Testing mode. Using page 0, turning off looping.
Benchmark info not found - benchmarking... done.
Your maximum speed is 511909 keys/s per CPU core.


Nothing happens


But ...

Ask for work... got blocks [1466349440-1466357631] (8589 Mkeys)

went to

Ask for work... got blocks [1466443152-1466452879] (10200 Mkeys)


I think it did update somehow.

tried with sudo ./LBC -u nothing happens.

[rico666]

ubuntu@instance-5:~/collider$ ./LBC -u
Finished update run - system up to date.

ubuntu@instance-5:~/collider$ ./LBC -x
Testing mode. Using page 0, turning off looping.
Benchmark info not found - benchmarking... done.
Your maximum speed is 511909 keys/s per CPU core.

Nothing happens


But ...

Ask for work... got blocks [1466349440-1466357631] (8589 Mkeys)

went to

Ask for work... got blocks [1466443152-1466452879] (10200 Mkeys)


I think it did update somehow.
[/quote]

If there was an output after LBC -u (new generator found) yes. Else: no

LBC -u must fetch a new generator. If it doesn't (for whatever reasons), you must fetch it manually (unpack, rename, chmod a+x, yadda yadda)

then LBC -x, then profit




Rico

[rico666]

It's official, the on-GPU bloom filter code is not working on Nvidia Tesla K80.  

To be more precise, it's the simple single "printf" that's crashing the app.
The one single printf which shows - on rare occasions - a find. e.g.

Code:

2d17543d32448acc7a1c43c5f72cd5be459ab302:u:priv:0000000000000000000000000000000000000000000000000000000000000001 + 0x5e
02e62151191a931d51cdc513a86d4bf5694f4e51:c:priv:0000000000000000000000000000000000000000000000000000000000000001 + 0x65
9d74ffdb31068ca2a1feb8e34830635c0647d714:u:priv:00000000000000000000000000000000000000000000000000000000000f9001 + 0xf8c
3d6871076780446bd46fc564b0c443e1fd415beb:c:priv:00000000000000000000000000000000000000000000000000000000000f9001 + 0xf8c

I will probably make the on-GPU bloom selectable by command line option to navigate around this problem. Until then, if you have a K80 (which unfortunately is true for most of the cloud machines), the old GPU gnerator is working...
If you have newer machines like Maxwell or Pascal architectures and a Nvidia 375 or newer driver, chances are very good it will work for you. On the other hand, its quite probable if you have a Kepler GPU (or older), that the new code will bite you.


Rico

[unknownhostname]

It's official, the on-GPU bloom filter code is not working on Nvidia Tesla K80.  

So what do u want me to put on those GPU k80 servers ?

[rico666]

It's official, the on-GPU bloom filter code is not working on Nvidia Tesla K80.  

So what do u want me to put on those GPU k80 servers ?

The new version I will write especially for these servers. It's PITA, but it would be a shame to not have a keyrate doubling.
So wait for it (1-2 days). I believe these 4 x K80 machines could still deliver more than 70 Mkeys/s each (machine).

Rico

[unknownhostname]

I believe these 4 x K80 machines could still deliver more than 70 Mkeys/s each (machine).

What about 32 vCPU , 8 x K80 machines ?

[rico666]

I believe these 4 x K80 machines could still deliver more than 70 Mkeys/s each (machine).

What about 32 vCPU , 8 x K80 machines ?

I believe the 8 x K80 machines do have 64 vCPU? else even the new generator cannot saturate 8 K80 with "only" 32 vCPUs.
Still, the speedup and GPU usage is way better with the new GPU generators. Speedup between 2.5x and 3.1x is to be expected.
With the 4 x K80 32vCPU machines one can expect the CPUs to almost saturate the GPUs. (Now less than 50%)

All in all - with the new generators we should be able to significantly lower the time until #51. Even worst case it should be 10 days less than what the stats show now. (edit: I see we have almost 40% of the #51 search space covered)


Rico

[GoldTiger69]

I just updated my  LBC and now I'm getting this: Server doesn't like us. Answer: too fast.
I'm using and AMD FX 4300 with ./LBC -c 2 (I even tried -c 1, same result).
Thanks in advance.

[Jude Austin]

I just updated my  LBC and now I'm getting this: Server doesn't like us. Answer: too fast.
I'm using and AMD FX 4300 with ./LBC -c 2 (I even tried -c 1, same result).
Thanks in advance.

What generator is LBC trying to use?

[palawan]

.....

Code:

2d17543d32448acc7a1c43c5f72cd5be459ab302:u:priv:0000000000000000000000000000000000000000000000000000000000000001 + 0x5e
02e62151191a931d51cdc513a86d4bf5694f4e51:c:priv:0000000000000000000000000000000000000000000000000000000000000001 + 0x65
9d74ffdb31068ca2a1feb8e34830635c0647d714:u:priv:00000000000000000000000000000000000000000000000000000000000f9001 + 0xf8c
3d6871076780446bd46fc564b0c443e1fd415beb:c:priv:00000000000000000000000000000000000000000000000000000000000f9001 + 0xf8c

...
Rico

Hello, how is the private key converted to normal format?

[GoldTiger69]

I just updated my  LBC and now I'm getting this: Server doesn't like us. Answer: too fast.
I'm using and AMD FX 4300 with ./LBC -c 2 (I even tried -c 1, same result).
Thanks in advance.

What generator is LBC trying to use?

I see this file there: gen-hrdcore-sse42-linux64

[Jude Austin]

I just updated my  LBC and now I'm getting this: Server doesn't like us. Answer: too fast.
I'm using and AMD FX 4300 with ./LBC -c 2 (I even tried -c 1, same result).
Thanks in advance.

What generator is LBC trying to use?

I see this file there: gen-hrdcore-sse42-linux64

Did you try a benchmark test? Append -x and see what happens.

[GoldTiger69]

I just updated my  LBC and now I'm getting this: Server doesn't like us. Answer: too fast.
I'm using and AMD FX 4300 with ./LBC -c 2 (I even tried -c 1, same result).
Thanks in advance.

What generator is LBC trying to use?

I see this file there: gen-hrdcore-sse42-linux64

Did you try a benchmark test? Append -x and see what happens.

This is the result:

./LBC -x
Will use 2 CPUs.
Testing mode. Using page 0, turning off looping.
Benchmark info not found - benchmarking... done.
Your maximum speed is 3720003547 keys/s per CPU core.