VanitySearch (Yet another address prefix finder)

[Jean_Luc]

Hello,

Yes , the SLarkBoy's config is impressive. As for stivensons , I would suggest to free some CPU cores to see if the performance are better using the -t option.

Some news:

I will probably publish a new release today or tomorrow with a slight performance increase and the possibility to search several prefixes in one go. It was difficult to find a solution to not alter the performance due to the overhead of lookup tables but I manage to find good compromises.

However, I'm facing an issue with the Linux release and I don't really know at the moment from where it comes. It seems that it is related to my old hardware or to the old SKD (I'm not sure). The same code works perfectly on windows (CUDA SDK 10) but not on my Linux config (CUDA SDK 8.0). It compiles without errors or warnings in both cases, but the generated seems wrong and returns wrong results on Linux. If I remove some part of it, it works again, it seems that I reached a limit somewhere. I have to figure out where...

@arulbero:
I see that you make a test with a Quadra M2200, it was on Linux ? If yes, would it possible that you try to compile from the last source and execute VanitySearch -check to see if it works on your config. Thanks

EDIT:
Concerning the issue, I'm speaking of the GPU code, the CPU code works great in both cases.

[Jean_Luc]

The new release (1.7) is ready.
I had to revue the inline decision of the compiler (Linux) to make the old hardware work but still not very clear.
I hope that it won't alter the performance for recent GPU. On my hardware, the reviewing on inline decision has improved a bit performance.
Thanks to test it

[Lolo54]

versions 1.2 to 1.3 looked on my old CPU 1.8 MK / s
For version 1.6 it was already a nice increase in speed, a nice optimization Jean_Luc nice!

Tested Jean_Luc nice, on my old gear the improvement is 65% CPU .... for the GPU I can not enjoy it for the moment CUDA 8.0
Start Wed Mar  6 15:55:46 2019
Search: 1testr
Difficulty: 15318045009
Base Key:5D48B5A686EF3CCD828F2B23DBD365564D4193F3DC5EA98EB696641F8C8CFC17
Number of CPU thread: 4
3.016 MK/s (GPU 0.000 MK/s) (2^28.15) [P 1.92%][50.00% in 00:57:02][0]

With this version 1.7 the increase of the speed on my old material is still impressive + 30%
result version 1.7

Start Mon Mar 11 13:38:57 2019
Difficulty: 15318045009Search: 1testr
Base Key:EF61AC731BD4EAA239646EC88F3F3538D39BBA9B2A8C580276CB9AFAE849ECFE
Number of CPU thread: 4
4.395 MK/s (GPU 0.000 MK/s) (2^26.09) [P 0.47%][50.00% in 00:45:09][0]

The i option works very well at home ... I dream of compatibility with CUDA 8.0 to enjoy my old GPU GT520M  

Start Mon Mar 11 13:53:03 2019
Ignoring prefix "1CPuID" (0, I, O and l not allowed)
Search: 3 prefixes (Lookup size 3)
Base Key:C24307039526A5A5EA9DA60EB6C67A3E9F60BC32BA44E8337171A53751AA3A12
Number of CPU thread: 4
4.192 MK/s (GPU 0.000 MK/s) (2^26.91) [P 37.96%][50.00% in 00:00:14][0]

on the other hand I do not know what I'm doing wrong it only records the results of the first pattern
good job Jean_Luc  

[Jean_Luc]

The i option works very well at home ... I dream of compatibility with CUDA 8.0 to enjoy my old GPU GT520M  

I'll work on this ASAP.

on the other hand I do not know what I'm doing wrong it only records the results of the first pattern

May be because you didn't use the -stop option. In that case all matching addresses are recorded and if one is much more probable than others, then you will have a lot of them in the output.
By using the -stop option, only one record per prefix entry are saved and the program ends when all prefixes have been found.

good job Jean_Luc  

Thanks

[Jean_Luc]

I reached the performance of the good old oclvanitygen on my GeForce GTX 645 (3x192 cores) with my Core i7-4770@3.4GHz alone

Code:

C:\C++\VanitySearch\x64\Release>VanitySearch.exe -u 1Happy
Start Mon Mar 11 14:47:44 2019
Difficulty: 264104224Search: 1Happy
Base Key:4F3C51AA76D9FFDD605B50174A0F2E54A79B58434DD5A0FBED72DCB9EBA69855
Number of CPU thread: 8
9.489 MK/s (GPU 0.000 MK/s) (2^25.77) [P 19.46%][50.00% in 00:00:13][0]

Code:

C:\C++\VanityGen>oclvanitygen.exe 1Happy
Difficulty: 259627881
[9.28 Mkey/s][total 56623104][Prob 19.6%][50% in 13.3s]

C:\C++\VanityGen>vanitygen64.exe 1Happy
Difficulty: 259627881
[1.31 Mkey/s][total 3227136][Prob 1.2%][50% in 2.3min]

[arulbero]

@arulbero:
I see that you make a test with a Quadro M2200, it was on Linux ? If yes, would it possible that you try to compile from the last source and execute VanitySearch -check to see if it works on your config. Thanks

It works on Linux with CUDA 8.0.

Amazing improvements :

./VanitySearch -stop -t 6 -gpu  1Happgggy
130 MKeys/s  


./VanitySearch -stop -t 8  1Happgggy
13.7 MKeys/s

Code:

----:~/VanitySearch$ ./VanitySearch -check
GetBase10() Results OK
Add() Results OK : 121.951 MegaAdd/sec
Mult() Results OK : 24.213 MegaMult/sec
Div() Results OK : 4.132 MegaDiv/sec
ModInv()/ModExp() Results OK
ModInv() : 342.810 KiloInv/sec
IntGroup.ModInv() : 8.944 MegaInv/sec
ModMulK1() : 12.643 MegaMult/sec
ModSqrt() OK !
Check Generator :OK
Check Double :OK
Check Add :OK
Check GenKey :OK
Adress : 15t3Nt1zyMETkHbjJTTshxLnqPzQvAtdCe OK!
Adress : 1BoatSLRHtKNngkdXEeobR76b53LETtpyT OK!
Adress : 1JeanLucgidKHxfY5gkqGmoVjo1yaU4EDt OK(comp)!
Adress : 1Test6BNjSJC5qwYXsjwKVLvz7DpfLehy OK!
Adress : 1BitcoinP7vnLpsUHWbzDALyJKnNo16Qms OK(comp)!
Check Calc PubKey (full) 1ViViGLEawN27xRzGrEhhYPQrZiTKvKLo :OK
Check Calc PubKey (even) 1Gp7rQ4GdooysEAEJAS2o4Ktjvf1tZCihp:OK
Check Calc PubKey (odd) 18aPiLmTow7Xgu96msrDYvSSWweCvB9oBA:OK
GPU: GPU #0 Quadro M2200 (8x128 cores) Grid(64x128)
Seed: 591012
82.215 MegaKey/sec
ComputeKeys() found 530 items , CPU check...
GPU/CPU check OK

[Jean_Luc]

Thank you very much to all of you for testing this software and helping me to make it better

[stivensons]

Code:

G:\vanitysearch>vanitysearch -stop -t 0 -gpu -gpuId 0,1,2,3,4,5,6 1Testtttt
Start Tue Mar 12 20:03:18 2019
Difficulty: 2988734397852221Search: 1Testtttt
Base Key:E04D2ABC020297FCE97546517F7F2B190EFE4A6055B293615B326B03F1857ACB
Number of CPU thread: 0
GPU: GPU #6 GeForce GTX 1060 3GB (9x128 cores) Grid(72x128)
GPU: GPU #0 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)y][0]
GPU: GPU #5 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)
GPU: GPU #3 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)
GPU: GPU #2 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)
GPU: GPU #1 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)
GPU: GPU #4 GeForce GTX 1060 6GB (10x128 cores) Grid(80x128)
1571.848 MK/s (GPU 1571.848 MK/s) (2^34.87) [P 0.00%][50.00% in 15.3d][0]

 

[arulbero]

Next Step:
- Optimize CPU/GPU exchange
- Add missing ECC optimizations (some symmetries and endomorphism)
- Add support for GPU funnel shift that should speed up SHA (but I need to find a board with compute capability >3.5, mine is 3.0).

Did you implement already all the steps 1, 2, 3 or there is still space to further improvements?

[Jean_Luc]

Next Step:
- Optimize CPU/GPU exchange
- Add missing ECC optimizations (some symmetries and endomorphism)
- Add support for GPU funnel shift that should speed up SHA (but I need to find a board with compute capability >3.5, mine is 3.0).

Did you implement already all the steps 1, 2, 3 or there is still space to further improvements?

- Support for funnel shift no yet done.
- p-iG/p+iG done.
- k.(x,y)/-k.(x,-y) done.
- Endomorphism is in progress.
- CPU/GPU exchange done but still need improvement (difficult to find good compromises with multi prefixes search)

[Jean_Luc]

Hello,
 
I added a note in the readme about attacking full address. It may be not clear. I would like a simple and understandable text about his.
Thanks to help me to make it clear.

Please don't use VanitySearch to attack a list of complete addresses. It is very unlikely that you find a collision. The time displayed indicates the time needed to reach the displayed probability of the most probable prefix in the list. In case of having n complete addresses in the input file, simply divide this time by the number of entries to get an aproximative idea of the time needed to reach the displayed probability (in fact it is longer). Even with a file containing 1 billion of addresses, using a very competitive hardware, the time needed to reach a probability of 50% will be much longer than the age of the universe. Note that the birthday paradox cannot be applied here as we look for fixed addresses and there is no trick possible (as for Pollard rho method on points coordinates) to simulate random walks because addresses are hashed.

[arulbero]

Hello,
 
I added a note in the readme about attacking full address. It may be not clear. I would like a simple and understandable text about his.
Thanks to help me to make it clear.

Please don't use VanitySearch to attack a list of complete addresses. It is very unlikely that you find a collision. The time displayed indicates the time needed to reach the displayed probability of the most probable prefix in the list. In case of having n complete addresses in the input file, simply divide this time by the number of entries to get an aproximative idea of the time needed to reach the displayed probability (in fact it is longer). Even with a file containing 1 billion of addresses, using a very competitive hardware, the time needed to reach a probability of 50% will be much longer than the age of the universe. Note that the birthday paradox cannot be applied here as we look for fixed addresses and there is no trick possible (as for Pollard rho method on points coordinates) to simulate random walks because addresses are hashed.

You compute the probability this way?

I  use the concept of the target set T of the addresses we want to find. The target set of the addresses with prefix 1A has many (1/22* 2^160) elements, the target set of the addresses with prefix 1A11XxW8qtLWXoxJrjkHuvKDgjnJ1Kfjss has instead only 1 element.

Your example (1 billion of addresses) is like to find a collision with an address with a very long prefix. Just so you know, the target set of LBC has size of 2^24 addresses (about 16 million).

How does vanitygen compute the probability?

Let's do an example with 1A prefix. Let T be the target set of the addresses 1Axxxxx. To get on average 1 match we have to generate 22 addresses.

Smaller is the target, bigger is the difficulty to hitting it and viceversa.

Let me rephrase this: difficulty * size of target = search space, in our case a small difficulty and therefore a big target ( it's easy to hit this target!):

Code:

22 * 63703009616853067642911677093369144589991624155  = 2^160

number of keys we have to use (= numbers of addresses we have to generate to get on average 1 match) * number of addresses in T = 2^160 possible addresses.

Every time we try a new private key, we have 1 chance over 22 to hit our target set T (the probability is 1/22). At every roll then we don't hit the set T with probability 1 - 1/22. If we use k private keys, we don't hit T with probability (21/22)^k.
The probability of hitting T in k trials is then:

P = 1 - (21/22)^k

https://en.wikipedia.org/wiki/Geometric_distribution

The geometric distribution gives the probability that the first occurrence of success requires k independent trials, each with success probability p. If the probability of success on each trial is p, then the probability that the kth trial (out of k trials) is the first success is

P(X=k) = p(1-p)^(k-1)  for k = 1, 2, 3, ....

The cumulative distribution function is P(X<=k) = 1 - (1-p)^k  (it is the probability that X will take a value less than or equal to k ).

If we want to have :

a 50% chance, 1 - (21/22)^k = 0.50 --> k = log(0.50)/log(21/22) = 14.9 tries (not 11!)

a 64% chance, 1 - (21/22)^k = 0.64  --> k = log(0.36)/log(21/22) = 22.0 tries

a 75% chance, 1 - (21/22)^k = 0.75  --> k = log(0.25)/log(21/22) = 29.8 tries (not 11!)

a 90% chance, 1 - (21/22)^k = 0.90  --> k = log(0.10)/log(21/22) = 49.5 tries

a 95.5% chance, 1 - (21/22)^k = 0.955  --> k = log(0.045)/log(21/22) = 66.7 tries (3 times 22!!)

a 99% chance,  1 - (21/22)^k = 0.99  --> k = log(0.01)/log(21/22) = 99 tries

and so on (100% only for k -> infinity).


On average it takes 22 tries to get 1 match, but if you do 22 tries only once you will have only a 64% chance to get a match!

And vanitygen computes right the probability to find a match in the particular sequence you are running, vanitygen doesn't compute anything "on average".

[arulbero]

About difficulty, your program shows slightly (negligible) different results respect of vanitygen:

Code:

./vanitygen 1Bit
Difficulty: 77178


./VanitySearch -stop -u -t 7 -gpu  1Bit
Start Tue Mar 12 18:36:06 2019
Difficulty: 78509Search: 1Bit


./vanitygen 1Bitcoin
Difficulty: 873388193410

./VanitySearch -stop -u -t 7 -gpu  1Bitcoin
Start Tue Mar 12 18:35:46 2019
Difficulty: 888446610539Search: 1Bitcoin

For the output, a space between Difficulty and Search would be better 

[Jean_Luc]

You compute the probability this way?

I compute the difficulty as vanitygen (number are not exactly equal because I use double calculation but you can see they are very near) then simply a Bernoulli trial as vanitygen also.
Attacking 1 billion of addresses (I know there is much less with funds) is like having a key rate 1 billion time faster.
I just would like a simple text to explain that birthday paradox cannot be used here and that having a big input file does not improve enough the odds to find a collision and it is still infeasible.

[Jean_Luc]

For the output, a space between Difficulty and Search would be better 

lol, i see that, I'll correct it in the next release

[LoyceV]

I added a note in the readme about attacking full address. It may be not clear. I would like a simple and understandable text about his.
Thanks to help me to make it clear.

Please don't use VanitySearch to attack a list of complete addresses. It is very unlikely that you find a collision. The time displayed indicates the time needed to reach the displayed probability of the most probable prefix in the list. In case of having n complete addresses in the input file, simply divide this time by the number of entries to get an aproximative idea of the time needed to reach the displayed probability (in fact it is longer). Even with a file containing 1 billion of addresses, using a very competitive hardware, the time needed to reach a probability of 50% will be much longer than the age of the universe. Note that the birthday paradox cannot be applied here as we look for fixed addresses and there is no trick possible (as for Pollard rho method on points coordinates) to simulate random walks because addresses are hashed.

I would suggest to rewrite it into something like:
"Feel free to use VanitySearch to attack a list of complete addresses. You won't find a matching private key, but it might help convince yourself that Bitcoin is secure."

Ever so often someone pops up in the vanitygen-thread, with the idea to brute-force existing addresses. It's useless, but if takes a few years of processing time to convince them, let them try

[arulbero]

Attacking 1 billion of addresses (I know there is much less with funds) is like having a key rate 1 billion time faster.
I just would like a simple text to explain that birthday paradox cannot be used here and that having a big input file does not improve enough the odds to find a collision and it is still infeasible.

Find a single exact address like 1WantFindBitcoinVanitySearch --> difficulty 2^160

Find 1 address (any) in a list of 10^9 = 2**30 addresses:  difficulty 2^160 /  2^30 = 2^130

Find 1 address with prefix : 1WantFindBitcoinVanityS  --> difficulty 2^133

Then the chances to find a private key for a single address in a list of 10^9 addresses is like to remove only 5 characters from an address. Too difficult.


Birthday paradox doesn't apply in this context, it works only if we know already the public key (not the address, the hash of the public key) we want to find.  This program doesn't look for collisions between public keys. It searchs only for collisions with addresses with a certain prefix (short prefix -> many addresses with that prefix -> low difficulty -> high chanches to find a collision, long prefix -> few addresses with that prefix --> high difficulty --> low chanches to find a collision)

Using a list of particular addresses is (from the point of view of the probability) like searching for a single very very long prefix (because the number of addresses of your list will be always negligible in a space search of 2^160 addresses), then has no sense trying to find any exact address.

 (Don't look at the English ...   )

[Jean_Luc]

OK Thanks arulbero , it is clear and rather simple, I will try to write something better. tomorow.
see you

[Jean_Luc]

I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me

[LoyceV]

I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me

Just typos:

the following table shows the probabilty of findindg a collision after a certain amount of time: