Large Bitcoin Collider (Collision Finders Pool)

[rico666]

Why client wrote

Server doesn't like us. Answer: wrong secret

Look at #371 - #374
https://bitcointalk.org/index.php?topic=1573035.msg17644236#msg17644236


Rico

[1713575837]

1713575837

[1713575837]

1713575837

[1713575837]

1713575837

[1713575837]

1713575837

[arulbero]

New version of symmetric function, only 2M + 1S

Code:

def symmetric(x1,y1,x2,y2,z3inv):
	
	a=((y2+y1)*z3inv)      % p   #1M
	b=a**2		       % p   #1S	
	x4 = (b - x1 - x2)     % p   
	y4 = (a*(x4-x1) - y1)  % p   #1M       
	   
        return x4,y4

then we pass from 7M + 1,5S for each point to 6M + 2S.

[rico666]

For the next week, I'll be having fun in the Alps and will be trying to not break my legs - or neck.
I leave you with the LBC ... unattended, so I hope the pool will not be completely dead when I return. 


Managed to push out a stats update with a graph showing the 24h pool speed average
(if you look at the X-axis right to left, thats like 0 = [now, -24h] -1 = [-24h, -48h] etc.)

So if you will not hear anything from me for the next 168hours, do not worry, I probably haven't been murdered yet. 


Rico

[TooDumbForBitcoin]

For the next week, I'll be having fun in the Alps and will be trying to not break my legs - or neck.
I leave you with the LBC ... unattended, so I hope the pool will not be completely dead when I return. 


Managed to push out a stats update with a graph showing the 24h pool speed average
(if you look at the X-axis right to left, thats like 0 = [now, -24h] -1 = [-24h, -48h] etc.)

So if you will not hear anything from me for the next 168hours, do not worry, I probably haven't been murdered yet. 


Rico

How is this luxury trip being financed?  Perhaps a sudden windfall of BTC?  Whose BTC?  How obtained? 

[Jude Austin]

wow HeavenlyCreatures use gpu maybe  

I think that is privatenode.

[arulbero]

Good news, from 6M + 2S to  4,5M +2S for each point!

Considering that your current code performs 6M + 1S only for the transition from jacobian to affine coordinates for each point and that you are using J+J --> J to perform each addition (12M + 4S), your current cost should be 18M + 5S each point.

Let's say 1S = 0,8M, then my code should be about 3,5 faster than yours.

If you are now using instead  J+A --> J to perform addition (8M + 3S), then my code should be 2,8 faster than yours.

If you implement:

1)  (X,Y) , (X,-Y)   --> 2x

2)  endomorphism  --> 3x (but non free, 1M for each point)

3) 4,5M + 2S generation --> 2,8x / 3,5x

you could speedup your points generation about x 15 (at least). Maybe less if your field multiplication is so optimized that it makes field additions/negations not negligible.

Enjoy your holiday!

[becoin]

Enjoy your holiday!

What holiday? He isn't entitled to go on a holiday! He hasn't found even a single collision.

[unknownhostname]

#49 anyone ?

[rico666]

I'm back.

How is this luxury trip being financed?  Perhaps a sudden windfall of BTC?  Whose BTC?  How obtained?  

No BTC involved whatsoever. I just made a deal with a European top model to be at her service and she
promised to pay for the trip. Life's hard.


~160 Mkeys/s while I was away. Wow! Seems #49 has not been found yet, at least I have no info about it.
But I see quite some janitoring has to be done (promised undelivered blocks) - please people end your sessions
with "e" + return (and wait), instead of Ctrl-C

It'd be quite some irony if #49 was in one of the blocks to be re-issued.


I managed to hack some things after fulfilling my duties with aforementioned model, so expect some news
and releases this weekend. Spoiler alert: You may want to make sure OpenCL is installed correctly on your
machine.  


Rico

[SlarkBoy]

I'm back.

How is this luxury trip being financed?  Perhaps a sudden windfall of BTC?  Whose BTC?  How obtained?  

No BTC involved whatsoever. I just made a deal with a European top model to be at her service and she
promised to pay for the trip. Life's hard.


~160 Mkeys/s while I was away. Wow! Seems #49 has not been found yet, at least I have no info about it.
But I see quite some janitoring has to be done (promised undelivered blocks) - please people end your sessions
with "e" + return (and wait), instead of Ctrl-C

It'd be quite some irony if #49 was in one of the blocks to be re-issued.


I managed to hack some things after fulfilling my duties with aforementioned model, so expect some news
and releases this weekend. Spoiler alert: You may want to make sure OpenCL is installed correctly on your
machine.  


Rico

wow!
tell me if you need to test on GTX 1080 and TESLA K80 

[Jude Austin]

I'm back.

How is this luxury trip being financed?  Perhaps a sudden windfall of BTC?  Whose BTC?  How obtained?  

No BTC involved whatsoever. I just made a deal with a European top model to be at her service and she
promised to pay for the trip. Life's hard.


~160 Mkeys/s while I was away. Wow! Seems #49 has not been found yet, at least I have no info about it.
But I see quite some janitoring has to be done (promised undelivered blocks) - please people end your sessions
with "e" + return (and wait), instead of Ctrl-C

It'd be quite some irony if #49 was in one of the blocks to be re-issued.


I managed to hack some things after fulfilling my duties with aforementioned model, so expect some news
and releases this weekend. Spoiler alert: You may want to make sure OpenCL is installed correctly on your
machine.  


Rico

Eeeeeeeeee

[rico666]

When showing the help via ./LBC -h the 1st option you saw was

Code:

     --address <BTC P2PK address>
      Give a BTC address for rewards to this client. NYI

The NYI (not yet implemented) will be gone with the next version of the LBC client and also the type of the BTC address is not constrained anymore (you can give a P2SH as well). I intend to release the next LBC client this weekend and yours will most probably auto-update - so leave the download section alone for now  .

Code:

$ ./LBC -h

         LBC - Large Bitcoin Collider v. 1.005
    client fingerprint: 8eb48dd9fd0a77b8b4110be83baf04c2

 Usage:
    LBC [options]

 Options:
    --address <BTC address>
      Give a BTC address for rewards to this client.

(remark: The to-be-released-client will probably have a bigger version number than 1.005)

So how does setting a BTC address look like and what will it do?

You can set a BTC address for the id you own any time/as often as you want, but only the last value is valid. You can check the BTC address set via query (-q). And you can do both in one step:

Code:

$ LBC -q -a 1DoofusZqKv2wDhUAvKRjUPVQsyZw3NKCw
Server answer to 'query' is:
{
"done" : 18075470,
"btcadr" : "1DoofusZqKv2wDhUAvKRjUPVQsyZw3NKCw",
"ips" : {
...
},
"lastsee" : ...
}
'done' means we have delivered  18953.504 valid Gkeys.

From then on, the given BTC address is attached to your id and whatever reward - relevant to your client - the pool will issue, will be paid to this BTC address (or whichever is active at time of payout - as you can change them as often as you want).

Wait - what reward?!

 

When the pool started, i planted some small bounties in the search space for any client to find. Some may remember 1AKKm1J8hZ9HjNqjknSCAfkLR4GgvCAPjq and 1TinnSyfYkFG8KC3gZ72KpYxBXsxSadD8.

While this is some fun and I plan doing so again, it's more of a "the winner takes it all" game and that's not what pools are about - is it?
So there will be another incentive, but this time - with a BTC address attached to an id - the pool can reward clients proportionately.

Let's say - and this is just a thought experiment / example - I put out a 1 BTC reward to be distributed among all ids in the top30 (except __rico666__ - of course) proportionately to their delivered GKeys, with this in place I can do so.

Or let's say the pool does find something and no one claims ownership - we can use this for distribution of the find.

Or let's say the pool does find something, the rightful owner does claim (and prove) ownership and we can distribute a finders fee among the clients... or ... or ...


Some time ago, I promised to make sure people who supported the pool early on will have favors. The 1st such favor will be, that any id in the top30 will get a GPU client for free (i.e. as many GPU client instances as you want/need - for your id), everyone else wanting the GPU client will fork out 0.1 BTC 
I reserve the right to give out GPU freebies to special supporters - like arulbero - should they be interested. Also, the price for becoin is 0.5 BTC.

The 0.1BTC for any GPU client will not be paid to yours truly (aka me), but - see above - proportionately to all pool members except myself. Specs of the GPU client will follow soon.

So maybe it is time to have a look at the cost-benefit evaluation of being in the top30 of the LBC:

The cheapest price/performance AWS compute nodes will allow you to compute/check 65 Gkeys for 40 us cent. If I look at some examples of the current top 30:

Code:

Rank	Client Id           #GKeys	Activity
1	Unknownhostname	                       101313	3m 6s
2	a01f54a6df31b6d9075a99507b7c4a27	48206	5m 25s
3	Brother_of_Castor	                44736	3m 54s
4	HeavenlyCreatures	                37771	1m 16s
...
7	JudeAustin	                        17611	4m 15s
...
13	John_Snow	                         6238	2h 15m 12s
...
30	a14f027942e6f0507083a3d4f2ae376f	 1866	13d 21h 14m 56s

based on the AWS price, #30 is worth some $11, John_Snow delivered keys worth about $38, Unknownhostname about $623(!) etc.
So right now, if you are not in the top30 and want a GPU client, it's way cheaper to deliver some Gkeys than 0.1BTC
Once you are in top30 and you have a GPU client, you will be part of the LBC establishment for quite some time to come.

If you are not in the top30, but have delivered quite some Gkeys under different ids (different computers, hardware changed, etc.), I repeat my offer to merge your contributions to one id.

Right now, the vast majority of the pool performance comes from Unknownhostname and HeavenlyCreatures. That is two guys (or groups - but I believe guys), delivering over 80% of the pool performance. Most of the ids in the top30 are dormant as you can see. The entry barrier is f*ing low, so carpe diem.


Rico

[rico666]

I modified the stats slightly:

• The pool performance shown is a 24 average and as such is equivalent to the last point (0 on x-axis) shown in the pool performance graph.
• For #51 you can now see a "from to" estimate. The previous value was just the (pessimistic) "max" value assuming #51 would be a private key 2⁵¹-1

Based on the 2nd you can see the time - at most - it will take to hit #50. (currently 51 days)
Estimate for #49 is left as an exercise to the reader.


Rico

[arulbero]

2. Outside the Box

2. Outside the Box

IMO, for any substantial optimizations, it is required to think outside the box. The box here being the libsecp256k1 library. This library provides us with an API - a set of functions - which is functionally complete, but may sometimes be obstructive for certain tasks. If you look at the use case from above, it would certainly be nice if we had a function that could efficiently sum up affine points into jacobian.

Thinking outside the box, why do we need a function A + A -> J ?

We have to add only affine points, and we have never to add the result of an addition with other points.

So we can get rid of the jacobian coordinates. In this way we achieve only 3,5M + 1S for each point, if we use the classical (simple and more efficient) A+A-> A formula!

Here is my script:
  
https://www.dropbox.com/s/kr10oil2idlhd80/ecc_for_collider02.zip?dl=0  it works with python3 too  

1) kG
2) all the inverse of the batch (3M for couple, 1,5M for each point)
3) 2048 couples (2M + 1S with A+A->A for each point)

total 3,5M + 1S for each point. Very very fast.


EDIT:
with this script   https://www.dropbox.com/s/4q3i0mqvdfgd258/ecc_for_collider03.zip?dl=0
I can generate about 4.1 millions of keys in 51 s,  about 80000 keys/s

Code:

antonio@ubuntu:~/src/python$ time python3 ./gen_batch_points03.py 

real	0m52.423s
user	0m51.992s
sys	0m0.040s

With your code my old pc generates about 530000 keys/s (200000 keys/s --> 200000 * 22/6 = 530000), my script then is only 6,5x slower than your code! No assembly, no C!

[rico666]

Also in the next LBC release, there will be a tiny small inconspicuous parameter

Code:

    --gpu
      Enable GPU acceleration if available.

When given, LBC will check your OpenCL installation and print out some debug information about your GPU hardware. This will show you if your hardware is capable to use GPU acceleration in principle. If you want to make sure your hardware is supported well/in the optimum way, please send the output of this to bots@cryptoguru.org for further examination.

Also it will check if the id of the LBC client is eligible to run GPU acceleration and print the result of the check.

The output will look like this:

Code:

$VAR1 = {
          'Intel(R) OpenCL' => [
                                 {
                                   'vector_width' => {
                                                       'preferred' => {
                                                                        'long' => 1,
                                                                        'half' => 8,
                                                                        'char' => 16,
...
                                   'max' => {
                                              'clock_frequency' => 1050,
                                              'work' => {
                                                          'item_dimensions' => 3,
                                                          'item_sizes' => [
                                                                            256,
                                                                            256,
                                                                            256
                                                                          ],
                                                          'group_size' => 256
                                                        },
                                              'compute_units' => 24,
...
                                   'mem' => {
                                              'global' => {
                                                            'cache_type' => 2,
                                                            'cacheline_size' => 64,
                                                            'size' => '13344676250',
                                                            'cache_size' => 524288
                                                          },
                                              'max_alloc_size' => 6672338125,
                                              'host_unified' => 1
                                            },
                                   'device' => {
                                                 'name' => 'Intel(R) HD Graphics',
                                                 'driver_version' => 'r2.0.54425',
                                                 'version' => 'OpenCL 2.0 ',
                                                 'vendor' => 'Intel(R) Corporation',
...
                                   'device' => {
                                                 'name' => 'Intel(R) Xeon(R) CPU E3-1505M v5 @ 2.80GHz',
                                                 'driver_version' => '1.2.0.10264',
                                                 'version' => 'OpenCL 2.0 (Build 10264)',
                                                 'vendor' => 'Intel(R) Corporation',
                                                 'profile' => 'FULL_PROFILE',
                                                 'available' => 1,
                                                 'endian_little' => 1,
                                                 'compiler_available' => 1,
                                                 'local_mem' => 32768,
                                                 'type' => 2,
                                                 'address_bits' => 64,
                                                 'extensions' => 'cl_khr_icd cl_khr_global_int32_base_atomics cl_khr_global_int32_extended_atomics cl_khr_local_int32_base_atomics cl_khr_local_int32_extended_atomics cl_khr_byte_addressable_store cl_khr_depth_images cl_khr_3d_image_writes cl_intel_exec_by_local_thread cl_khr_spir cl_khr_fp64 cl_khr_image2d_from_buffer '
                                               },
                                   'mem' => {
                                              'global' => {
                                                            'cache_type' => 2,
                                                            'size' => '16691331072',
                                                            'cacheline_size' => 64,
                                                            'cache_size' => 262144
                                                          },
                                              'host_unified' => 1,
                                              'max_alloc_size' => 4172832768
...
          'NVIDIA CUDA' => [
                             {
                               'mem' => {
                                          'host_unified' => '',
                                          'max_alloc_size' => 1059487744,
                                          'global' => {
                                                        'cache_type' => 2,
                                                        'cacheline_size' => 128,
                                                        'size' => 4237950976,
                                                        'cache_size' => 81920
                                                      }
                                        },
                               'device' => {
                                             'name' => 'Quadro M2000M',
                                             'version' => 'OpenCL 1.2 CUDA',
                                             'driver_version' => '375.26',
                                             'compiler_available' => 1,
....

etc. etc. - above example is very shortened. See ftp://ftp.cryptoguru.org/LBC/source/opencl.txt to get an idea of the full output. This is what my notebook looks like. There are 2 OpenCL platforms found (Intel & Nvidia), Intel has 2 devices, the built-in GPU "Intel HD Graphics" and the Xeon CPU, and Nvidia has 1 device: The Quadro M2000M.

We have been talking about "GPU client" in the past, but it's really an OpenCL client we meant.



Rico

[TooDumbForBitcoin]

Also, the price for becoin is 0.5 BTC.

I had a boss pull this on me 30 years ago in front of a crowd of people.  It was very effective in shutting my smartass mouth.

[Syarina]

1GmjDxtKXF59MZiqmGR3YjLyUyttbC3WmJ

[rico666]

EDIT:
with this script   https://www.dropbox.com/s/4q3i0mqvdfgd258/ecc_for_collider03.zip?dl=0
I can generate about 4.1 millions of keys in 51 s,  about 80000 keys/s

Code:

antonio@ubuntu:~/src/python$ time python3 ./gen_batch_points03.py 

real	0m52.423s
user	0m51.992s
sys	0m0.040s

With your code my old pc generates about 530000 keys/s (200000 keys/s --> 200000 * 22/6 = 530000), my script then is only 6,5x slower than your code! No assembly, no C!

I tried it. On my notebook it takes

Code:

real    0m26.493s
user    0m26.490s
sys     0m0.000s

for the ~4.1mio keys (1000 * 4096). And

Code:

real    1m47.661s
user    1m47.657s
sys     0m0.003s

for 16M keys. So around ~160 000 keys/s

However, the HRD core also does the hash160 of the uncompressed and also hash160 of the compressed public keys.
The public key generation part takes around 6 seconds for the 16M keys. If I understand your code correctly, it also does only the ECC computation part. Then we are at around 6 seconds versus 107 seconds. Not sure how much slower Python vs. C is

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=python3&lang2=gcc

suggests it can be anything between a factor of 3 and 100 
Factor 100 would be cool, then your code should be somewhere ~1s in C ... we'll see. It certainly seems more lightweight than what we have now.


Rico

[arulbero]

I tried it. On my notebook it takes

Code:

real    0m26.493s
user    0m26.490s
sys     0m0.000s

for the ~4.1mio keys (1000 * 4096). And

Code:

real    1m47.661s
user    1m47.657s
sys     0m0.003s

for 16M keys. So around ~160 000 keys/s

However, the HRD core also does the hash160 of the uncompressed and also hash160 of the compressed public keys.
The public key generation part takes around 6 seconds for the 16M keys. If I understand your code correctly, it also does only the ECC computation part. Then we are at around 6 seconds versus 107 seconds. Not sure how much slower Python vs. C is

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=python3&lang2=gcc

suggests it can be anything between a factor of 3 and 100 
Factor 100 would be cool, then your code should be somewhere ~1s in C ... we'll see. It certainly seems more lightweight than what we have now.

So in your case 107 / 6 means about 18x slower, I think it is not bad at all.

I'm sure that your optimizations with field_5x52_int128_impl.h can make a huge difference. The field operations make the difference. We'll see.

[rico666]

Good morning!

HeavenlyCreatures found #49

Code:

From	XXX
To	bots@cryptoguru.org
Date	Today 08:02
Hi,

I found #49

0d2f533966c6578e1111978ca698f8add7fffdf3:c:priv:000000000000000000000000000000000000000000000000000174176b015001
+ 0xf4c

Looking at the PK, the pool must have found it GMT: Sat, 11 Feb 2017 04:32:26 GMT

edit: trophies update.

cheers!

Rico