Bitcoin Forum
September 19, 2019, 09:38:34 AM *
News: Latest Bitcoin Core release: 0.18.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 [4] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 »  All
  Print  
Author Topic: VanitySearch (Yet another address prefix finder)  (Read 6077 times)
Lolo54
Member
**
Offline Offline

Activity: 70
Merit: 25


View Profile
March 11, 2019, 01:04:41 AM
 #61

Nice speed  Grin

Code:
C:\VanitySearch>VanitySearch.exe -stop -gpu -gpuId 0,1,2,3 1SLarkBoyKEK
Start Sun Mar 10 22:26:19 2019
Difficulty: 583137945833742401536Search: 1SLarkBoyKEK
Base Key:7098934A348028B578A730116289AC3A6BB56AFF8664117F5CE69920A360A4E9
Number of CPU thread: 31
GPU: GPU #0 Tesla V100-SXM2-16GB (80x64 cores) Grid(640x128)
GPU: GPU #3 Tesla V100-SXM2-16GB (80x64 cores) Grid(640x128)
GPU: GPU #2 Tesla V100-SXM2-16GB (80x64 cores) Grid(640x128)
GPU: GPU #1 Tesla V100-SXM2-16GB (80x64 cores) Grid(640x128)
7260.449 MK/s (GPU 7212.931 MK/s) (2^36.56) [P 0.00%][50.00% in 1765.33y][0]


C:\VanitySearch>VanitySearch.exe -stop -gpu -gpuId 0,1 1SLarkBoyKEK
Start Mon Mar 11 02:56:57 2019
Difficulty: 583137945833742401536Search: 1SLarkBoyKEK
Base Key:B97C76053D7951498A9122DEBC2951EB803A51C309326D1C321DF35DF5FB79EE
Number of CPU thread: 19
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(224x128)
GPU: GPU #1 GeForce GTX 1080 Ti (28x128 cores) Grid(224x128)
1293.435 MK/s (GPU 1255.415 MK/s) (2^32.96) [P 0.00%][50.00% in 9909.36y][0]
ah yes impressive speed but the tesla config is crazy  Shocked ! it also allows to see that despite a software optimizes and the top of the technology it is still not possible to obtain a vanity address of 12 patterns or more in a reasonable delay alas  Undecided
it can already have good fun to create beautiful addresses of vanity if you do not climb so high in the number of pattern remaining within a reasonable time ...
1568885914
Hero Member
*
Offline Offline

Posts: 1568885914

View Profile Personal Message (Offline)

Ignore
1568885914
Reply with quote  #2

1568885914
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 11, 2019, 04:39:37 AM
Last edit: March 11, 2019, 05:00:20 AM by Jean_Luc
 #62

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 Wink

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

Activity: 154
Merit: 193


View Profile
March 11, 2019, 08:56:57 AM
Merited by OgNasty (1), TryNinja (1)
 #63

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 Wink
Lolo54
Member
**
Offline Offline

Activity: 70
Merit: 25


View Profile
March 11, 2019, 12:59:11 PM
 #64

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  Grin

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  Smiley

Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 11, 2019, 01:15:49 PM
 #65

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

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  Smiley

Thanks Wink


Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 11, 2019, 01:55:47 PM
 #66

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

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
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
March 11, 2019, 06:40:40 PM
Last edit: March 11, 2019, 07:21:59 PM by arulbero
Merited by LoyceV (1)
 #67

@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 Wink

It works on Linux with CUDA 8.0.

Amazing improvements :

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


./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
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 04:51:12 AM
 #68

Thank you very much to all of you for testing this software and helping me to make it better Smiley
stivensons
Jr. Member
*
Offline Offline

Activity: 83
Merit: 1


View Profile
March 12, 2019, 01:08:05 PM
 #69

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]

 Smiley
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
March 12, 2019, 01:29:48 PM
 #70

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
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 01:49:49 PM
 #71

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
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 04:41:12 PM
 #72

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.

Quote
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
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
March 12, 2019, 05:19:20 PM
Last edit: March 12, 2019, 05:31:21 PM by arulbero
 #73

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.

Quote
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
Quote
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
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
March 12, 2019, 05:36:54 PM
 #74

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  Cheesy
Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 05:37:29 PM
 #75

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
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 05:40:15 PM
 #76


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

lol, i see that, I'll correct it in the next release Smiley
LoyceV
Legendary
*
Offline Offline

Activity: 1610
Merit: 4625


Largest Merit Circle on BPIP!


View Profile WWW
March 12, 2019, 05:51:37 PM
 #77

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.

Quote
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 Cheesy

arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
March 12, 2019, 05:59:08 PM
Last edit: March 12, 2019, 06:13:35 PM by arulbero
 #78

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

Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 12, 2019, 06:09:57 PM
 #79

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

Jean_Luc
Full Member
***
Offline Offline

Activity: 154
Merit: 193


View Profile
March 13, 2019, 08:30:12 AM
 #80

I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me Wink
Pages: « 1 2 3 [4] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!