Topic: VanitySearch (Yet another address prefix finder) - page 58. (Read 32072 times)
It's amazing how much progress is being made on this software so quickly. Great work!
Yes and there is also a CUDA intrinsic that search for the number of starting zero __ffsll which could be used to speed up the checking of public key.
Thanks for the information.
CPU profiles of the last release:
...
...
A note:
ModInv <-> ModMulK1
6% <-> 13% (uncompressed)
10,3% <-> 18,9% (compressed)
it seems to me that ModInv should be much lower than 50% of ModMulk1, are you sure you don't take significative advantage from using more than 256 elements for each batch? Why don't try with 1024 or 4096?
to 2160/m, the probabilty -> probability
the probabilty of finding -> probability
It would be nice (but requires a completely different program --> https://github.com/basil00/pairgen) to exploit the birthday paradox to find 2 addresses with the same very long prefix.
To find 2 private keys (and then 2 public keys) related to the same address, it takes about 2^80 steps. But you can't pick wich address will be.
To find 2 private keys that generate 2 public keys with the same first 100 bits, it takes 2^50 steps.
https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/
pairgen as cubitrack are totally different from vanitysearch or vanytigen they have absolutely not the same goal!the probabilty of finding -> probability
Thanks 
Hope I will be less disturbed by dreamers !
Hope I will be less disturbed by dreamers !
It would be nice (but requires a completely different program --> https://github.com/basil00/pairgen) to exploit the birthday paradox to find 2 addresses with the same very long prefix.
To find 2 private keys (and then 2 public keys) related to the same address, it takes about 2^80 steps. But you can't pick wich address will be.
To find 2 private keys that generate 2 public keys with the same first 100 bits, it takes 2^50 steps.
https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/
Pairgen would actually be the fastest and most efficient program (faster than cubitrack). Using the Birthday Paradox is very effective but it should be optimized much more because currently it only works on CPUs even if it is very fast, make it usable on GPU would give amazing results and optimize its functions like being able to choose an input file -i (several prefixes which one could choose) and a file of exit -o (for each collision found since -i ) and a -continue function or -stop .....
In the current state it is possible to find a prefix of 12 characters without problem see 14 but actually it is not possible to choose the address
With some mod of your code, I could try another project, a vanity pubkey instead of an address pubkey:
https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys
The "best" pubkey I have found with my onw cpu code so far is:
Without sha256 + ripemd160 + base58 encode, I guess I could achieve a very impressive key rate.
https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys
The "best" pubkey I have found with my onw cpu code so far is:
Quote
02000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92
Without sha256 + ripemd160 + base58 encode, I guess I could achieve a very impressive key rate.
Yes and there is also a CUDA intrinsic that search for the number of starting zero __ffsll which could be used to speed up the checking of public key.
CPU profiles of the last release:
(using compressed address)
(using uncompressed address)
EDIT: FindKey include, mainly, lookup table, ecc arithmetic (ModAdd and ModSub)
ModMulK1 is the SecpK1 modular mult, there are 2 ModMulK1 signatures for this method.
Added the 2 profiles for compressed and uncompressed.
With some mod of your code, I could try another project, a vanity pubkey instead of an address pubkey:
https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys
The "best" pubkey I have found with my onw cpu code so far is:
Without sha256 + ripemd160 + base58 encode, I guess I could achieve a very impressive key rate.
https://crypto.stackexchange.com/questions/60239/elliptic-curve-and-vanity-public-keys
The "best" pubkey I have found with my onw cpu code so far is:
Quote
02000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92
Without sha256 + ripemd160 + base58 encode, I guess I could achieve a very impressive key rate.
Thanks again for the typo, the automatic corrector doesn't work when editing the README.md 
Yes it can be fun, with GPU optimization we can win few base58 caracter, but 2^80 is still high to find a complete collision.
Yes it can be fun, with GPU optimization we can win few base58 caracter, but 2^80 is still high to find a complete collision.
to 2160/m, the probabilty -> probability
the probabilty of finding -> probability
It would be nice (but requires a completely different program --> https://github.com/basil00/pairgen) to exploit the birthday paradox to find 2 addresses with the same very long prefix.
To find 2 private keys (and then 2 public keys) related to the same address, it takes about 2^80 steps. But you can't pick wich address will be.
To find 2 private keys that generate 2 public keys with the same first 100 bits, it takes 2^50 steps.
https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/
the probabilty of finding -> probability
Thanks
Hope I will be less disturbed by dreamers !
Hope I will be less disturbed by dreamers !
It would be nice (but requires a completely different program --> https://github.com/basil00/pairgen) to exploit the birthday paradox to find 2 addresses with the same very long prefix.
To find 2 private keys (and then 2 public keys) related to the same address, it takes about 2^80 steps. But you can't pick wich address will be.
To find 2 private keys that generate 2 public keys with the same first 100 bits, it takes 2^50 steps.
https://www.reddit.com/r/Bitcoin/comments/34hjph/generating_partial_address_collisions_using_the/
Thanks
Hope I will be less disturbed by dreamers !
Hope I will be less disturbed by dreamers !
I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me
Thanks to correct me
propability -> probability
perfrom -> perform
Lotery -> Lottery
precission -> precision
Thanks
I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me
Just typos:Thanks to correct me
Quote
the following table shows the probabilty of findindg a collision after a certain amount of time:
I wrote this: https://github.com/JeanLucPons/VanitySearch#trying-to-attack-a-list-of-addresses
Thanks to correct me
Thanks to correct me
OK Thanks arulbero , it is clear and rather simple, I will try to write something better. tomorow.
see you
see you
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.
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 ...
)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.
I would suggest to rewrite it into something like: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.
"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
For the output, a space between Difficulty and Search would be better
lol, i see that, I'll correct it in the next release
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.
About difficulty, your program shows slightly (negligible) different results respect of vanitygen:
For the output, a space between Difficulty and Search would be better
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
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
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.
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!):
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
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".
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 ).
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".
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.
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.
Jump to: