Topic: Large Bitcoin Collider (Collision Finders Pool) - page 42. (Read 193404 times)

 

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

Pool in perfect working condition again.


Rico

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 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.


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:


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


or


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):


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:


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

whats this mean...  ELI5 please

bitcoin is ded?

Hey Ryan,

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

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.


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.


Donald Trump is paying for that - with Mexican money.


Rico

Of course, you do!

The main purpose is not:


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?

Hi,


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

Great job, keep on working !  


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

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?

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

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.

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://bitcointalksearch.org/topic/m.45565

--> 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.

I have no clue ... I'm not a programmer .

But I'm sure you are and you will find a way

I gave my nose a blow, unfortunately no GPU client appeared in my handkerchief.
Any other suggestions how I should "try"?


Rico

Intel Xeon Phi 7290 are very rare.

GPU's arent ... you should try GPU ... I'm sure you can delivered great speed with GPU

even with 1 server I think I can triple the pool speed.

root@soft:~# lshw -C video | grep product:
       product: ASPEED Graphics Family
       product: GK210GL [Tesla K80]
       product: GK210GL [Tesla K80]
       product: GK210GL [Tesla K80]
       product: GK210GL [Tesla K80]

If you have access to a Knights Landing CPU (http://ark.intel.com/products/codename/48999/Knights-Landing), please ping me if you would like to try a generator, I have AVX-512 binaries available.

A single Intel Xeon Phi 7290 can give you 50 MKeys/s! That's right - about as much as the total pool speed right now.


Rico

1: Your maximum speed is 493068 keys/s per CPU core.
2: Your maximum speed is 482198 keys/s per CPU core.
3: Your maximum speed is 484588 keys/s per CPU core.
4: Your maximum speed is 484546 keys/s per CPU core.
5: Will use 24 CPUs. Best generator chosen: gen-hrdcore-avx2-linux64 (w8ing to finish , than I will check the speed )

Pool looks to be picking up speed, I like it.

Anyone with an AVX2 capable CPU (haswell, broadwell), might want to restart LBC for a generator auto-update.

Your keyrate will go up by ~20%.


Rico

I gave SHA256 quite some attention and there is a puzzling fact to SHA256:

I ended up using most of the code from OpenSSL 1.1.0c as it proved to be faster than supervanitygen code, which in turn uses
The Intel reference implementation from 2012: https://github.com/klynastor/supervanitygen/tree/master/sha256

What puzzles me most is that I should get in between 320MB/s and 560MB/s with the Intel reference implementation on my CPU. It's padded to 64bytes, so this would mean something between 5Mhash/s and 8MHash/s for compressed keys. Should be at worst 3.3 seconds for the 2^24 compressed keys. Still, the 4.5s I get from OpenSSL is better than what I could get from the 2012 Intel code.

So either I am not using the optimized code from Intel well, or there is meanwhile better optimized code (I haven't inspected the OpenSSL implementation, as reading thr OpenSSL code is ... let's say even worse than libsecp256k1 code), or I cannot simply transfer the 320MB/s to 320MB/s / 64bytes or....
Intel had 2015 a writeup about improving openssl: https://software.intel.com/en-us/articles/improving-openssl-performance

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.


Rico