Large Bitcoin Collider (Collision Finders Pool)

[cz3kit]

Hey Your project is great. I follow it already some time and it's nice to follow it and see how it evolves and how people add math to it to make it even better. I wanted to run your program on a pine64. Had no time to try it out yet. Hope to do it over the weekend.
I was thinking about doing something like you, just to be able to learn more about bitcoins/blockchain and the math Keep on going with this project.

[Jude Austin]

Basically the LBC generator is now about twice as fast as supervanitygen, as it does 730 000 keys/s (supervanitygen 767 000), but contrary to supervanitygen HRD-core does both uncompressed and compressed (supervanitygen only compressed).

Your suggestion about doubling the key rate by using the complement private keys is as of now the only thing that could significantly raise keygen rate. Maybe I could hit 1Mkeys/s on one core on my CPU, but I believe this is really it what can be done with CPU - unless someone can come up with something really surprising.

Looking at the equation y^2 = x^3 +7

1) my first suggestion was exploiting the symmetry with respect to the X-Axis, in that case I took care of the first term y^2 --> (X,Y), (X-Y)

2) now another suggestion (to generate other public keys almost free, but unfortunately not in your range) concerns the term x^3;

you could exploit endomorphism for your specific task (not to perform faster a single multiplication k*G).

Endomorphism:

-->  https://bitcointalk.org/index.php?topic=3238.msg45565#msg45565

--> http://crypto.stackexchange.com/questions/22738/how-do-you-derive-the-lambda-and-beta-values-for-endomorphism-on-the-secp256k1-c




lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72   (lambda^3 = 1 mod n)

beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee    (beta^3 = 1 mod p)

private key                       --> public key

      k                               --> k*G = (X,Y)    

 (lambda*k) mod n        --> (lambda*k)*G = (beta*X, Y)    only 2 field multiplications (lambda*k   beta*X)

 (lambda^2*k) mod n    --> (lambda^2*k)*G = (beta^2*X, Y) only 2 field multiplications (lambda^2*k  beta^2*X)
      
                                
(beta*X and beta^2*X are mod p)

In this way you can perform 3 private keys and 3 public keys, all with the same Y.


 
3) If you implement 1) + 2) you'll have:

6 public keys (+ 6 compressed)

(X,Y)          ,    (X,-Y)
(beta*X,Y)  ,    (beta*X, -Y)                           <-- these points are out of the range 1-2^160
(beta^2*X,Y),  (beta^2*X, -Y)                       <-- these points are out of the range 1-2^160

and 6 private keys (+ 6 compressed):

k,                   n-k,
lambda*k        n-lambda*k                             <-- these keys are out of the range 1-2^160
lambda^2*k    n-lambda^2*k                         <-- these keys are out of the range 1-2^160

then 12 addresses at a very low computational cost.

[rico666]

Thanks to all for the ongoing support and interest in the project. I'm being asked about my current work on the project (mostly GPU  ), so I decided to keep some info about the pending work and development on the LBC here.

Basically, LBC consists of 3 main components: The server, the client and the generator.

The server is what drives the web pages at https://lbc.cryptoguru.org, takes work from clients, issues new work, keeps track of what has been done already, computes stats and is the top-level instance to check PoW to make sure clients do not cheat about work done. It has some mechanisms to protect the server against DoS and blacklists misbehaving clients.

The client is the "local intelligence" on your machine. It talks to the server when asking for work or when delivering PoW of work done. It fires up the generator(s) according to the amount of work promised to do, which depends on the time committed and the capabilities of the local machine. The client also tries to make deployment of itself as easy as possible and handles updates of itself, the generator and the blf-file.

The generator is the low-level workhorse. Its sole purpose is to generate hash160s from private keys of a given range and to compare the generated hash160s against those in the BLF file (a bloom filter) containing all known hash160 with funds on them. The generator (or generators if you have a multi-CPU system) is fired up by the LBC client with the correct partitioning of search space, it is given a challenge parameter and has to answer with the correct response to be evaluated by the LBC client.

So the TODO will mention work TBD on these 3 components. Depending on time available, urgency, personal preferences and mood (hey - I'm doing it for fun) I'll shift my attention between these 3. E.g. I've been working for the past - at least - month on the generator workhorse optimizing it. And while there are some very promising things that could be done (EC arithmetics as pointed out by arulbero), there are some equally pressing things regarding the "intelligence" part i.e. the LBC client. So expect the next big thing(tm) to come from that component.

I should mention, that I got quite some motivation to look at the GPU generator again and managed to complete a nice and swift GPU-hashing prototype. That is, on my M2000M (640 cores) hashing h160 with almost 100Mhash/s which is not optimized yet. I was wondering if I did a hybrid CPU/GPU generator where I'd do the EC on the CPU(s) and offload the hashing to the GPU, I could have that pretty quick and maybe get again a nice speedup (my notebook does atm ~2.8Mkeys/s and I guess with GPU offloading the hashing that should be at least 6.7 Mkeys/s)


Rico

[arulbero]

Depending on time available, urgency, personal preferences and mood (hey - I'm doing it for fun) I'll shift my attention between these 3.

Great job, keep on working !  


I have a (probably stupid) question about the main purpose:

This is a collision finders pool, because its main purpose is to find a hash160 collision

You could generate 10 millions of random private keys (public keys / addresses). You should only check that all keys are greater than 2^160.  Then you can make a new *.blf file with your addresses. Obviously you have to save the private keys somewhere.

If the pool finds a collision, then it is automatically a real collision. And you have two keys and two curve points as proof, without problems with btc holders.

Furthermore if you double the 10 millions, you'll find a collision in half time (like to speedup x2 your program, but more simple).

Am I missing something?

[rico666]

Hi,

I have a (probably stupid) question about the main purpose:

This is a collision finders pool, because its main purpose is to find a hash160 collision

You could generate 10 millions of random private keys (public keys / addresses). You should only check that all keys are greater than 2^160.  Then you can make a new *.blf file with your addresses. Obviously you have to save the private keys somewhere.

If the pool finds a collision, then it is automatically a real collision. And you have two keys and two curve points as proof, without problems with btc holders.

Furthermore if you double the 10 millions, you'll find a collision in half time (like to speedup x2 your program, but more simple).

the question is not stupid at all. Ever since the pool has found it's 1st "real private key" i.e. of an address with unspent input and the following discussions which can be seen in this thread, I thought about whether/how to take the "BTC holders" as you name them out of the equation.

The approach as you suggest has a technical and a motivational problem:

The search space is 2¹⁶⁰ bits, which is roughly 10^48.1. Even if we take the 2^137.5 into account until something is found, that's still about 10^41.4. The bloom filter currently used has 2^32 bits, 20 hash functions and holds around 9 M entries - resulting in a false positive probability of 10^-27. This means, that on average, during our search of the search space until something is found, we will hit about 10^14.4 false positives.

While you can raise the probability (I'd not speak of speed) of a find by adding more "targets" into the bloom filter, you inevitably also raise the number of false positives. Current parameters given, we will have a false positive every thousand trillion trillion generated keys, potentionally we will - as is - see over one hundred trillion of these. Raising the number of hash functions would hurt speed, raising the size of the bloom filter is additional memory requirement. I can imagine the pool to become a million times faster than it is now and then the current false positive rate starts to fail us.
While the 512MB are currently not a problem for main memory, uploading the bloom filter as global memory to a GPU and leaving enough for a couple thousand kernels, is only viable with GPUs that have 3GB or more.

I know that all this is only because we're at the moment taking the constraints from the brainflayer bloom filter implementation as given and that a specific redesign of the BLF allowing maybe dozens of millions of "control addresses" would give us a way bigger fishing net than we have now. However, we have searched almost 3 x 10¹⁴ keys now and had already two or so false positives (plus the 7033bd97579b0105561056fcfc1ddcaa8a04abf0 -> 40000031337 find which I'm still not sure what that was about), so jeopardizing the BLF false positive probability is not some path I'd like to follow.

Then there is the motivational part as mentioned: Myself, I can mobilize around 2-3Mkeys/s intermittently - if I was to average that down to continuous operation, not much more than 1Mkey/s would be left. If I read old articles in the thread and see how I had around 150Kkeys/s before the pool went online (and it had about 300Kkeys/s then), I'm not sure the pool would be today churning nearly 60 Mkeys/s if people weren't motivated to participate.

Now I certainly don't want that motivation to be to "steal other peoples funds" and to the best of my knowledge no such thing has happened with the pool (although a prominent core-dev shouts otherwise). I know that RyanC has announced a bounty of around 5 BTC / min $3000 for the find of a collision, maybe there are other bounties too. Not sure if a reward/bounty-only system would mobilize sufficient computational power.

I still do believe, that the pool can fulfill it's main task of finding a collision without stealing from people. If - of course - such a thing did happen, the option to fold the pool altogether is still open. While I haven't released all parts of the source that would allow someone else to immediately set up a similar thing, it's not impossible. I did it, any other fairly competent hacker with enough time on his hands can too. In fact, we can never be sure if there is not already one or more clandestine projects doing a similar thing - but with different purpose.

Also, there are other aspects to this pool and the addresses with funds we are checking against. How many lost bitcoins are there? Is it stealing if we find these and if - say - within a year the owner does not appear distribute them among the pool participants, charity or if the finder keeps them then? If I was to find the hard drive with the private key(s) to 7500 BTC on some landfill (https://www.theguardian.com/technology/2013/nov/27/hard-drive-bitcoin-landfill-site) and if I kept it - would that be stealing them? If I did not find the drive, but just the keys - would that be stealing them?

I know everybody has his opinion about this. My opinion - after lots of discussions - is that whatever will happen, right now the LBC pool is a unique project walking in uncharted territory. The engineer in me thinks this is fun. The bitcoin enthusiast in me (฿ → ∞) honestly believes  this project is as designed a constructive contribution to the bitcoin ecosystem.


Rico

[becoin]

Am I missing something?

Of course, you do!

The main purpose is not:

This is a collision finders pool, because its main purpose is to find a hash160 collision

And don't ask again because the answer will always change the angle depending on how question is asked.

Whatever the key generation speed is there is always much bigger constraint. The number of public keys in the database that newly generated keys are checked against. That is why the number of keys on the list must be kept really optimal to key generation speed. The list consists of the early Satoshi bitcoin addresses. If a private key from that list is ever found it can be sold out to someone that will move some early bitcoins and prove they are Satoshi.

It is really amusing to watch how this guy is wasting his time. It will be a good lesson to all treasure hunters. The only interesting question is who is paying for that effort?

[rico666]

The number of public keys in the database that newly generated keys are checked against. That is why the number of keys on the list must be kept really optimal to key generation speed.

eh... no. The false positive rate should not become a problem and for that the number of the addresses with funds on them is about right. If the number of P2PKH addresses with funds on them should suddenly double or triple, we'd probably use only the 10M most funded, but it's not about speed, it's about false positive rate.

The list consists of the early Satoshi bitcoin addresses. If a private key from that list is ever found it can be sold out to someone that will move some early bitcoins and prove they are Satoshi.

Oh that conspiracy theory.  Drink much?

We're looking at all Common P2PKH, not just "early Satoshi bitcoin addresses". Of course - if this project could help so that Satoshi can move his coins and not be bothered ("I'm not Satoshi, I just happened to find/buy the keys") - then I'm happy to provide this plausible deniability for him.

It is really amusing to watch how this guy is wasting his time. It will be a good lesson to all treasure hunters. The only interesting question is who is paying for that effort?

Donald Trump is paying for that - with Mexican money.


Rico

[shifty252]

If someone posts in this thread a different private key that also works out to 1PVwqUXrD5phy6gWrqJUrhpsPiBkTnftGg, I'll pay them 5BTC.

Now that's an incentive. I wonder if there would be a better place to announce that than here.
As nrg1zer wrote here: https://bitcointalk.org/index.php?topic=1573035.msg16523769#msg16523769
even if the owner of 1PVwqUXrD5phy6gWrqJUrhpsPiBkTnftGg sees (and cares about) that drain, how should he know where to look?


Rico

Actually, let's make that 5BTC or $3000 worth of BTC based on CoinDesk's bitcoin price index at the time of claim, whichever is more. I'm sure otherwise, someone will claim I'm assuming that me having to pay would crash the price.

If blockchain.info still has the feature that allows a "public message" to be added to a transaction, that would be a good option for signaling. A message could also be encoded in a series of vanity addresses.

For the fellow who figured "how much wood could a woodchuck chuck if a woodchuck could chuck wood" would make for a good brainwallet password, I was able to track him down via his transactions, but luck was a major factor in my ability to do that.

This problem was actually discussed somewhat by a fellow who went by "btcrobinhood" on reddit, see here: https://github.com/btcrobinhood/bips/blob/master/bip-1337.mediawiki (note that I have no opinion on that proposal at this time).

Hey Ryan,

Here's a collision for 1PVwqUXrD5phy6gWrqJUrhpsPiBkTnftGg:
http://prnt.sc/e0nsqp

[throwawayme3434534554]

whats this mean...  ELI5 please

bitcoin is ded?

[rico666]

LBC client update announcement

LBC client will auto-update itself to a new version >= 0.990 soon. This version has some long awaited features, so you might want to give them a try:

1. Set own id

You will be able to set your own id with the -id <string> command line parameter. String may be any of the 63 "word characters" (a-zA-Z0-9_) - no space - and must be between 8 and 32 (inclusive) characters in length.

Code:

valid ids:
__rico666__
Colliders_Inc
Elliptic_Epilepsy
etc.

invalid ids:
hello
.-=1337=-.
something_really_long_more_than32
etc.

With this, you will be able to start your LBC clients on different machines under the same id and therefore contribute "as one" to the stats.
If you PM me with the MD5 ids you had so far and you'd like to aggregate, I will move their contributed GKeys to your desired id in the DB.

Of course, the automatic issued md5-id will continue to work, so if you do not want to set an id, just don't. You can - of course - set some arbitrary md5 id  

I hope, you are aware this feature gives you some freedom that could be abused, so should there be some profanities appearing in the stats or anything shady I have not taken into account yet, I reserve the right to modify the ids and in severe (recurring) cases to ditch them. If you have to have an own id, try to be unique, try to be funny or just keep some inconspicuous md5 and impress by the #Gkeys next to it.

2. Set a secret/passwort

By setting an id you could assume an arbitrary identity and with such obtain information that's not meant for you (e.g. now with -q "query"). Soon, there also will be a possibility to attach a BTC address to your id for payments of bounties, incentives, grants and unclaimed found bitcoins. *crowd moans*

So it makes sense to protect your id by a password, which is done by the --secret [oldpwd:]pwd  command line parameter. It certainly makes sense to set a password right when setting an id. e.g. like this:

Code:

$ LBC -id Hoolakawoola -s x:somesecret -c 4 -t 20
Server message: secret set.
Best generator chosen: gen-hrdcore-skylake-linux64
...And from here on you know it...

From then on, you use LBC as you did so far, only you have to use the -id and -s parameters in addition, else

Code:

$ LBC -id Hoolakawoola -s wrongsecret -q
Server answer to 'query' is:
{
"nil" : "wrong secret"
}

or

Code:

$ LBC -id Hoolakawoola -s wrongsecret -c 1 -t 1
Best generator chosen: gen-hrdcore-skylake-linux64
Ask for work... Server doesn't like us. Answer: wrong secret.

Yes, the password is stored salted + SHA256 hashed on the server. Should you forget it, all I can do is to remove it or set another one, I can't bring it back (yet :-)).

3. Current Speed

When LBC measures the speed of the generator, it does so on one core. The result serves as bootstrap information when asking the server for a certain amount of work. Depending on the system load, the number of cores working, temperature etc., the key generation rate may differ significantly. Therefore, the new LBC client will perform measures of the current performance and show you after each "round":
This is how it looks like on my system (shortened):

Code:

$ LBC -c 1 -t 1
Ask for work... got blocks [266052633-266052680] (50 Mkeys)
ooo (0.73 Mkeys/s)

$ LBC -c 2 -t 1
Ask for work... got blocks [266054297-266054392] (100 Mkeys)
oooooo (1.34 Mkeys/s)

$ LBC -c 3 -t 1
Ask for work... got blocks [266055257-266055400] (150 Mkeys)
ooooooooo (1.79 Mkeys/s)

$ LBC -c 4 -t 1
Ask for work... got blocks [266057321-266057512] (201 Mkeys)
oooooooooooo (2.39 Mkeys/s)
Ask for work... got blocks [266057993-266058184] (201 Mkeys)
oooooooooooo (2.45 Mkeys/s)

$ LBC -c 8 -t 1
Ask for work... got blocks [266204457-266204840] (402 Mkeys)
oooooooooooooooooooooooo (3.02 Mkeys/s)

You can see how the 1-core performance (of ~730000 keys/s) drops to around 600000 keys/s when all 4 physical cores are active and the 4 logical cores themself bring only about 150000 keys/s each.

4. Local config file

Entering command line parameters can become tedious. Also, giving the secret on command line may expose this information to other users on the computer. LBC now supports configuration by a config file in JSON-format. If a file lbc.json is found, it is taken as the default config file for LBC. It can look e.g. like this:

Code:

{
    "cpus":   4,
    "id":     "Hoolakawoola",
    "secret": "somesecret",
    "time":   20
}

Of course, the command line parameters still work and have higher precedence. So if you start LBC without any command line parameters and this file is present, it will use 4 CPUs, send the id and secret to the server and ask for 20-minute chunks of work. If you start LBC with -c 2, this will take precedence and despite the information in the config file, it will use only 2 CPU cores.


5. Other

Feature: no_update flag. If you feel uncomfortable with LBC auto-updating, you can use this flag to  prevent this behavior
Bugfix: The failing test with LBC -x (expected 4, found 0) has been fixed.


Questions?


Other Updates:

Server:

- mostly manual updates
- what happens when something is found https://lbc.cryptoguru.org/man/user#found-
- how to use pulsed operation to fire up LBC only at nighttime https://lbc.cryptoguru.org/man/user#pulsed-operation
- elaborated on maximum keyrate and physical/logical CPU performance https://lbc.cryptoguru.org/man/admin#generator-speed

Generator:

Again a tiny performance gain of 1.5% for the avx2 generator, by compiling it with gcc 6.3.0 instead of 5.4.0


Rico

[rico666]

 

update in progress. Please wait with the shitstorm until it's over.

Pool in perfect working condition again.


Rico

[Haze]

I never set an ID or password previously and when I try to set something like this, I get the "server doesn't like us. Answer:wrong secret.". How can I get up and running? Sorry for the noob question.

Code:

$ LBC -id haze -s mypassword -c 1 -t 1
Best generator chosen: gen-hrdcore-skylake-linux64
Ask for work... Server doesn't like us. Answer: wrong secret.

[rico666]

I never set an ID or password previously and when I try to set something like this, I get the "server doesn't like us. Answer:wrong secret.". How can I get up and running? Sorry for the noob question.

Code:

$ LBC -id haze -s mypassword -c 1 -t 1
Best generator chosen: gen-hrdcore-skylake-linux64
Ask for work... Server doesn't like us. Answer: wrong secret.

I expected some hiccups - that's why I posted the docs in advance

* Id is too short (8-32 chars)
* You need to set a password, so you have to provide some old password.

As you had none before, you can take an arbitrary one

so if you do

Code:

LBC -id haze_the_great -s x:mypassword -c 1 -t 1

it should work. You should see a message "Password set". From then on -s mypassword is enough.
If you would like to change it, you need to do -s mypassword:newsecretpass




Rico

[Jude Austin]

Ask for work... Server doesn't like us. Answer: wrong secret.

Duh, didn't notice had to add -s x:mypassis12345

[rico666]

Ask for work... Server doesn't like us. Answer: wrong secret.

See above

Code:

LBC -s x:judesnewpass

and later then (a.k.a. on subsequent invocations)

Code:

LBC -s judesnewpass

or use the config file (also see above) if you do not want to type it over and over again nor if you want it to be seen on command line.


Rico

[rico666]

Also my offer to consolidate everybody's delivered Gkeys to a new id is still on the table.

I consolidated my old 1ff... and the Pleiades prototype also under __rico666__

Just tell me your old id and the new one and I move the gkeys from the old to the new (old id will be deleted from the DB).


Rico

[Jude Austin]

Ask for work... Server doesn't like us. Answer: wrong secret.

See above

Code:

LBC -s x:judesnewpass

and later then (a.k.a. on subsequent invocations)

Code:

LBC -s judesnewpass

or use the config file (also see above) if you do not want to type it over and over again nor if you want it to be seen on command line.


Rico

Thanks Rico!

I figured it out after I RTFM...

It's been a long day.

Jude

[Jude Austin]

Also my offer to consolidate everybody's delivered Gkeys to a new id is still on the table.

I consolidated my old 1ff... and the Pleiades prototype also under __rico666__

Just tell me your old id and the new one and I move the gkeys from the old to the new (old id will be deleted from the DB).


Rico

You can put these on JudeAustin:

ba6c903275906f7367f83e52e393648e
14ec34f45a80e99744e75b5e313a3d29
117a66a89de5393b34b7e37e8a00b2b6

There might be a couple more, for some reason on my "dedicated" every so often the client ID would change.

I will PM you the IP if you want to check if there are any others.

Thanks,
Jude

[rico666]

You can put these on JudeAustin:

ba6c903275906f7367f83e52e393648e
14ec34f45a80e99744e75b5e313a3d29
117a66a89de5393b34b7e37e8a00b2b6

There might be a couple more, for some reason on my "dedicated" every so often the client ID would change.

I will PM you the IP if you want to check if there are any others.

Thanks,
Jude

15078b42893011a9e1d13c0d53c8774f - also merged

Congrats, you're #5

Rico

[Jude Austin]

You can put these on JudeAustin:

ba6c903275906f7367f83e52e393648e
14ec34f45a80e99744e75b5e313a3d29
117a66a89de5393b34b7e37e8a00b2b6

There might be a couple more, for some reason on my "dedicated" every so often the client ID would change.

I will PM you the IP if you want to check if there are any others.

Thanks,
Jude

15078b42893011a9e1d13c0d53c8774f - also merged

Congrats, you're #5

Rico

Only number 5....

TO THE BATCAVE!