Large Bitcoin Collider (Collision Finders Pool)

[SlarkBoy]

wget http://ftp://ftp.cryptoguru.org/LBC/client/LBC
chmod +x LBC
./LBC -h


then ./LBC -x
Benchmark info not found - benchmarking... 'gen-hrdcore-sse42-linux64' not found/executable.

help pls

[1713581297]

1713581297

[rico666]

Benchmark info not found - benchmarking... 'gen-hrdcore-sse42-linux64' not found/executable.

You could also try ./LBC -u  which should perform a couple of auto-updates.
If all fails, there is still the manual way. LBC has recognized the sse4.2 generator to be best for your CPU, so you can:

• go to http://ftp://ftp.cryptoguru.org/LBC/generators/
  
• fetch the newest one with sse42 in it (170105-5aef41bea5c64dbf8c977195b67ba796.gen-hrdcore-sse42-linux64.bz2 as of now)
• bunzip2 it
• rename it to gen-hrdcore-sse42-linux64
• make sure it's executable

Rico

[rico666]

Yay!

Thanks to LBC I had the motivation to look into the secp256k1 lib and could make two subroutines faster by 6 to 7 orders of magnitude (that's 1 to 10 million times faster)

https://github.com/bitcoin-core/secp256k1/pull/437

field_get_b32: min 0.647us / avg 0.666us / max 0.751us
field_set_b32: min 0.551us / avg 0.571us / max 0.624us

becomes

field_get_b32: min 0us / avg 0.0000000477us / max 0.000000238us
field_set_b32: min 0us / avg 0.0000000238us / max 0.000000238us

So some day your dear bitcoin client will be faster thanks to this.

Seems I was wrong and secp256k1 hackers actually are interested in improving secp256k1, which motivates me to look at some other parts of secp256k1 where I sense more code smell... If only the docs were better (a.k.a. existent), I could spend more time on code than doing detective work.


Rico

[unknownhostname]

root@soft:~# ./LBC -x
Will use 24 CPUs.
Best generator chosen: gen-hrdcore-avx2-linux64
New generator found. (DL-size: 0.51MB)
New BLF data found. (DL-size: 191.37MB)
Testing mode. Using page 0, turning off looping.
Benchmark info not found - benchmarking... done.
Your maximum speed is 399037 keys/s per CPU core.
Test check failed! Expected 4 hits and got 2!
Ending test run.


------------------------------------------------

[rico666]

Test check failed! Expected 4 hits and got 2!

This happens at the moment. Probably it's the test itself failing (I had the generator showing uncompressed/compressed keys swapped.)

Basically if you do

Code:

./gen-hrdcore-avx2-linux64 -I 0000000000000000000000000000000000000000000000000000000000000001 -c 10000

on the command line, it should spill out 4 lines (with hash160 and priv keys +  1 line challenge response). This is proof that all still works. I expect this to be fixed in the next version.

Rico

[Jude Austin]

You broke it....

Best generator chosen: gen-hrdcore-sse41-linux64
Ask for work... Not an ARRAY reference at /usr/local/share/perl/5.22.1/Math/BigInt/Calc.pm line 1180.

[rico666]

You broke it....

Best generator chosen: gen-hrdcore-sse41-linux64
Ask for work... Not an ARRAY reference at /usr/local/share/perl/5.22.1/Math/BigInt/Calc.pm line 1180.

Kind of. Let me guess: You are updating from .899 to .960
There are some things broken along the path, because I fixed so many things. 

• libgmp can be completely ditched now.
• instead of Math::BigNum::GMP it uses core modules - no need to install anything
• but it needs recent versions of Math::BigNum[::Calc]
• You also will need LWP::Protocol::https because of the SSL communication

Code:

> make sure you have openssl-devel (or equivalent) installed

> cpan

cpan> upgrade
cpan> install LWP::Protocol::https

Sorry for the hassle, but this fixes a nasty bug in bignum computations, where all block numbers above 40 digits were rounded - thus computed wrong. Fortunately we are still in the 12-15 digit space. It also will lower installation footprint and hassle in the future.



Rico

[Jude Austin]

You broke it....

Best generator chosen: gen-hrdcore-sse41-linux64
Ask for work... Not an ARRAY reference at /usr/local/share/perl/5.22.1/Math/BigInt/Calc.pm line 1180.

Kind of. Let me guess: You are updating from .899 to .960
There are some things broken along the path, because I fixed so many things. 

• libgmp can be completely ditched now.
• instead of Math::BigNum::GMP it uses core modules - no need to install anything
• but it needs recent versions of Math::BigNum[::Calc]
• You also will need LWP::Protocol::https because of the SSL communication

Code:

> make sure you have openssl-devel (or equivalent) installed

> cpan

cpan> upgrade
cpan> install LWP::Protocol::https

Sorry for the hassle, but this fixes a nasty bug in bignum computations, where all block numbers above 40 digits were rounded - thus computed wrong. Fortunately we are still in the 12-15 digit space. It also will lower installation footprint and hassle in the future.



Rico

You fixed it....

[rico666]

Transaction is from 2016-04-21 (around 3 months before the LBC project started)
Was found by someone else - not me this time
The funds are still on that address (it's only 0.0001 BTC)

Stay tuned.

https://blockchain.info/address/164kvbiwxEq3wfeUWLSdxBuQeAyMhyFe4N
https://lbc.cryptoguru.org/trophies

*93a2*

Oh and BTW: it is an uncompressed address, as was the only other one with funds on it.
All other hash160 the pool has found (puzzle transaction) are compressed addresses.


Rico

[coinableS]

A legit collision? 

I would be interested to know what method was used by the original user of
https://blockchain.info/address/164kvbiwxEq3wfeUWLSdxBuQeAyMhyFe4N to generate that address.

[becoin]

A legit collision? 

To prove there is a collision you've to prove two different inputs result in same output. Finding the private key for an existing address generated with insufficient entropy has nothing to do with finding a collision! See how carefully Rico avoids using the word collision except in the title of this 'project'?

[rico666]

A legit collision?  

To prove there is a collision you've to prove two different inputs result in same output.

This is correct. Right now, all the pool has is one key. Again, a very strange key with many many leading zeroes.
The address found is younger, but still from a time ~3 months before even the theoretical inception of the LBC project.

If we could leave the usual "how do you prove it's not you who deposited..." aside, we could analyze what the pool has found and where to look for that other private key.

On a side note, I would like to mention, that given the speed of the pool at time of inception and the linear search since then, the projected find time of this key would be around ... 19055 days ~52 years in the future.

If we look at the originating address https://blockchain.info/de/address/1C22ZukCKVszze8KXVLfAMRaeqhRzWEZGi

it seems there were a lot of 0.0001 transactions done - mostly to addresses that have significant funds on them. Don't know exactly what this is (begging or whatever), but the address found is different from all the other targets of 1C22ZukCKVszze8KXVLfAMRaeqhRzWEZGi
I'm looking right now which P2SH 378e8af588e6433032d0f5fb548431408c4bcb3c resolves to (hm.. none - so it's standalone).


Rico

[vapourminer]

ok, 1st, im stupid. with that in mind please go easy on me.

this project is trying to find private keys to random public addresses with btc in it, is it not?

i thought that was, for all intents and purposes, impossible due to the truly astronomical odds.

so how is this finding them?

or do i have the whole purpose and results of this project wrong.

btw love the name.

[rico666]

this project is trying to find private keys to random public addresses with btc in it, is it not?

Well, the public addresses appear random, but the private keys "behind them" are not.

E.g. would you know, that
1MaGmdHoZpGzZk8m92rWSJ5LxUGic8RLjv
and
1Gs7mi3eerJwzUrs39fMBa3Uh4skw3ew96

are neighbors? They are at least in one case where their private keys differ by just 1.
Of course you cannot see this until you have computed them. (http://directory.io/1938276999168)

The pool is generating hash160s from simply incrementing the underlying private keys.
And it checks all generated keys against all known hash160 with unspent inputs on them. Yes.

Well - for a very special definition of "simply incrementing":

i thought that was, for all intents and purposes, impossible due to the truly astronomical odds.
so how is this finding them?

https://lbc.cryptoguru.org/man/theory#what-we-do

One reason why the pool keeps finding is the speed increase. Long term average, the pool is
getting faster and faster. Machines are faster, the generator gets faster, people come and go,
but in the end the more people let the LBC client run, the bigger the impact.

Another reason is, that we may hit private keys that were generated by some badly designed
software, are tests or whatever.

And - of course - another reason may be that this task is not at all so impossible as it is always presented.

btw love the name.

  Thanks - me too.


Rico

[rico666]

Time since inception: 6 months
Number of keys generated: 250 trillion
Number of unspents found: 2 (genuine, no bounties etc.)
Total collisions confirmed:   0
Current generation speed:  23.71 Mkeys/s (*)

Updated BLF on server. Upon restart, your clients should auto-update.


(*) The equivalent of about 185000 pages on directory.io  where each address (compressed and uncompressed) checked against ~ 9000000 addresses with unspent outputs - per second.


Rico

[unknownhostname]

Current generation speed:  23.71 Mkeys/s (*)

very very slow ... w8ing for GPU update ... thats when the real speed will appear .

I could do 5-6 times the current speed alone with GPU ...

[rico666]

Current generation speed:  23.71 Mkeys/s (*)

very very slow ... w8ing for GPU update ... thats when the real speed will appear .

I could do 5-6 times the current speed alone with GPU ...

If you have something, by all means code and advice is welcome.

I have an unpublishable GPU prototype based on vanitygen. It's basically half the speed of vanitygen (which has 15 MKeys/s on my notebook), as it uses 2 passes, one for compressed and one for uncompressed public keys. Also, it requires around 4GB RAM on startup until the AVL data structures are fiddled up. So on my notebook, the GPU prototype needs around 4GB memory on startup and 3.4 GB in GPU RAM and gives around 7MKeys/s.

Compared to this, SHA256 and RIPEMD160 code from hashcat 3.2 indicates around 150 Mega-hash160(x) per second and I am working on bringing the private key -> x (a.k.a. EC arithmetics) to the GPU also. For that, I need to strip down everything not relevant to generation, wrap my head around OpenCL distribution of the RMD160(SHA256(EC(private key))) x 2

Then I have a GPU implementation I got some time ago from a user - allegedly working, but (according to his own claims) with a bad performance. This solution seems Windows and AMD GPU only, and quite honestly I have not even been able to compile it.

All in all I agree that what we currently see as total pool speed, in a few weeks may come from one mid-range GPU.


Rico

[TooDumbForBitcoin]

Re GPU optimization and CUDA:

Wolf0 spent some time in the Monero thread in May-June 2014 optimizing GPU mining of Monero.  Might be a source of magic beans for this project.  Also DGA was doing a similar thing around the same time/subject.

As an aside, have you considered that the cosmological Big Bang was a result of people long ago searching for hash collisions, and found one?  So maybe a helmet, safety glasses, etc.

[arulbero]

If anyone's interested, from this article:

R9 290X GPU, 4 GB GDDR5, 2,816 processors and 5,600 GFLOPS,
the OpenCL 32-bit implementation uses the 32-bit scalar type of OpenCL 1.2

On a R9 290X, the OpenCL 32-bit implementation performs 1,778,000 scalar multiplications per second, i.e.
one scalar multiplication in 563 nanoseconds

Almost 2 MKeys/s (without sha256/ripmed160) and on another curve (Curve25519).

Is it possible to do better on secp256k1?

[rico666]

R9 290X GPU, 4 GB GDDR5, 2,816 processors and 5,600 GFLOPS,
the OpenCL 32-bit implementation uses the 32-bit scalar type of OpenCL 1.2

On a R9 290X, the OpenCL 32-bit implementation performs 1,778,000 scalar multiplications per second, i.e.
one scalar multiplication in 563 nanoseconds

Almost 2 MKeys/s (without sha256/ripmed160) and on another curve (Curve25519).

Is it possible to do better on secp256k1?

It certainly must be, as the lower bound for an OpenCL implementation of key generation on my Notebook GPU (Quadro M2000M - 640 cores) is 15 Mkeys/s. (As I said, vanitygen does that - inefficiently - computing the compressed public key once you have computed the uncompressed is quite easy). My estimate is, that we should be able to squeeze 20 Mkeys/s out of the Quadro M2000M.

My R9-280X does some 29 Mkeys/s (again vanitygen), an optimal implementation should squeeze 38-40 Mkeys/s from that.


Rico


PS: I ditched the field_5x52_asm_impl.h in secp256k1 altogether, optimizing field_5x52_int128_impl.h (a lot). Now it's faster.