to 2160/m, the probabilty -> probability the probabilty of finding -> probability Thanks  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/ |
|
|
|
propability -> probability perfrom -> perform Lotery -> Lottery precission -> precision |
|
|
|
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 ...  ) |
|
|
|
About difficulty, your program shows slightly (negligible) different results respect of vanitygen: ./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  |
|
|
|
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!): 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)^khttps://en.wikipedia.org/wiki/Geometric_distributionThe 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". |
|
|
|
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? |
|
|
|
@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----:~/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
|
|
|
|
I published a new release (1.6). No new feature, just performance increase (16% GPU, 50% CPU on my hardware). The performance increase are mainly due to a best ECC calculations ( many thanks to arulbero ) It affects less the GPU because the GPU has no SIMD instructions to speed up the SHA, so the resource goes mainly to it and much less to ECC calculations. On my pc:
VanitySearch -stop -u -t 1 1tryme --> 1,2 MKeys/s
my ecc library --> 2,0 MKeys/s (17 M Public keys/s)
Now (Intel(R) Xeon(R) CPU E3-1505M v6 @ 3.00GHz): VanitySearch -stop -u -t 1 1tryme --> 2,078 MKeys/s VanitySearch -stop -t 1 1tryme --> 2,771 MKeys/s VanitySearch -stop -t 8 1tryme --> 10,758 MKeys/s EDIT: Search: 1Happpppy Difficulty: 51529903411245 Base Key:89D6DCD4B58447BB26F7FAFC99C12612B4ADB97E8A0CC5133253E3CB74B6734E Number of CPU thread: 6 GPU: GPU #0 Quadro M2200 (8x128 cores) Grid(64x128) 98.840 MK/s (GPU 88.068 MK/s) (2^31.39) [P 0.01%][50.00% in 4.3d] For a comparison with Bitcrack: ./cuBitCrack -b 128 -t 256 -p 256 1FshYsUh3mqgsG29XpZ23eLjWV8Ur3VwH Quadro M2200 568/4038MB | 1 target 61.75 MKey/s (807,927,808 total) [00:00:21] |
|
|
|
Compressed G:\bit\cuBitCrack.exe -c -d 0 1CF1o6DRBpyGXqQXVJHTGiHNVVu54npgHo
[2019-03-04.21:54:29] [Info] Compression: compressed
GeForce GTX 1060 1083/6144MB | 1 target 58.56 MKey/s (1,473,773,568 total) [00:00:23]
Uncompressed G:\bit\cuBitCrack.exe -u -d 0 1CF1o6DRBpyGXqQXVJHTGiHNVVu54npgHo
[2019-03-04.21:53:35] [Info] Compression: uncompressed
GeForce GTX 1060 1083/6144MB | 1 target 51.94 MKey/s (1,238,368,256 total) [00:00:21]
Both G:\bit\cuBitCrack.exe -c -u -d 0 1CF1o6DRBpyGXqQXVJHTGiHNVVu54npgHo
[2019-03-04.21:52:18] [Info] Compression: both
GeForce GTX 1060 1083/6144MB | 1 target 46.99 MKey/s (1,696,071,680 total) [00:00:34]
Then with GeForce GTX 1060: bitcrack: 58.5 MKeys/s VanitySearch: 580/7 = 82 MKeys/s |
|
|
|
To do a comparison with another software, bitcrack (that has a different goal, instead of having a set of same prefix addresses it has as target a set of addresses with funds, but more or less both programs do the same calculations): https://bitcointalk.org/index.php?topic=4453897.msg49793258#msg49793258in particular: GeForce GTX 1060 3GB = compressed = 60.61 MKeys/s
GeForce GTX 1060 3GB = both = 46.93 MKeys/s
|
|
|
|
Hello, I would like to thanks arulbero who gave me by MP a great tip to improve speed by MP using some symmetries I missed this, shame on me. It will save few modular mult. But however, ~40% of cpu is used for modular mult, other 60% mainly go to SHA,RIPE,Base58,ModInv and byteswapping, so I don't know if I can reach the 2.0MKey/s (x 1.66) For linux (cpu side), I have to work on code generation optimization but assembly using AT&T syntax makes me crazy. As reference for SHA and RIPE, you could look here: https://github.com/klynastor/supervanitygenI don't use Base58 in my code, because I need only address in hex format, not Base58. When an OpenCL implementation? EDIT: on cpu 40% is used for ecc arithmetic; on gpu? I'm curious. |
|
|
|
Linux or windows ?
Is it open source ? Can i try it ?
Linux. You have a PM |
|
|
|
A group size of 512 does not bring significant improvement (less than 1%). The DRS62 ModInv is fast and almost negligible with a group size of 256.
If you have a modular mult faster than the digit serial Montgomery mult on a 256bit field, I'm obviously fully open. A folding does not improve thing on 256 bit when working with 64bit digits. I'm not sure if Barrett could be faster, I must say I didn't try and for "medium size field", there can be traps.
On my pc: VanitySearch -stop -u -t 1 1tryme --> 1,2 MKeys/s my ecc library --> 2,0 MKeys/s (17 M Public keys/s) EDIT: I use: a) group of 4096 points b) a * b = c mod p a*b --> 8 * 64 bit, then first 4 limbs * (2**256 - p) + lower 4 limbs. c) exploit some properties of secp256k1 curve |
|
|
|
Hello,
Affine coordinates for search (faster):
Each group perform p = startP + i*G, i in [1..group_size] where i*G is a pre-computed table containing G,2G,3G,.... in affine coordinates. The inversion of deltax (dx1-dx2) is done once per group (1 ModInv and 256*3 mult). group_size is 256 key long.
Protective coordinates for EC multiplication (computation of starting keys). Normalization of the key is done after the multiplication for starting key.
Edit:
You also may have noticed that I have an innovative implementation of modular inversion (DRS62) which is almost 2 times faster than the Montgomery one. Some benchmark and comments are available in IntMop.cpp.
Ok. two questions: 1) why only 256 for the group size? There is a memory problem? Less inversions are better 2) the field multiplication a*b = c mod p ; why do you use Montgomery, are you sure it is worth it? |
|
|
|
Hello,
I would like to present a new bitcoin prefix address finder called VanitySearch. It is very similar to Vanitygen.
The main differences with Vanitygen are that VanitySearch is not using the heavy OpenSSL for CPU calculation and that the kernel is written in Cuda in order to take full advantage of inline PTX assembly.
On my Intel Core i7-4770, VanitySearch runs ~4 times faster than vanitygen64. (1.32 Mkey/s -> 5.27 MK/s)
On my GeForce GTX 645, VanitySearch runs ~1.5 times faster than oclvanitygen. (9.26 Mkey/s -> 14.548 MK/s)
If you want to compare VanitySearch and Vanitygen result, use the -u option for searching uncompressed address.
There is still lots of improvement to do.
Feel free to test it and to submit issue.
Are you using affine or jacobian coordinates for the points? |
|
|
|
arulbero, online ?
Yes. What's the problem? |
|
|
|
I have read thru a lot of the pages and I have said it before and will say it again - I am confused as to what the goal is here? Is it just to find the addresses? or is the actual attempt here to find a way to take btc from a wallet?
The goal depends on the one who use it. For example OP/the creator create this software to solve Bitcoin puzzle. There's 2^256 combination of private key, so take/steal from an address is very unlikely goal unless people don't know this fact. Not completely true. It would be enough to try "only" 2^160 combinations (for example from key = 1 to key = 2^160) to be able to move the funds from all addresses (P2PKH utxo). With about 2^135 combinations you should get access at one address with funds. (1 random) |
|
|
|
https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89In practice, you will not compile an executable script for this task (where you also need to change #define GSTEP (1 << 25)) to #define GSTEP (1UL << 60) In the original version of the script it looks like this: 2 ^ 25 * 2 * 8/1024/1024 = 512 MB #Required RAM memory
* 2 * 8/1024/1024 = 17592186044416 MB (seventeen trillion five hundred ninety-two billion one hundred eighty-six million forty-four thousand four hundred sixteen megabytes) #Required RAMSo ... if you do not have this amount of RAM - you will not use this method. Look at the original code: https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89/* giant steps are 2^25 */
#define GSTEP (1<<25)
#define NUMPUBKEYS 51
unsigned char rawpubkeys[NUMPUBKEYS][33] ...
As you can see, to search the key #51 (from 2^50 to 2^51) you need a number of giant steps (and baby steps) equal to 2^25 (not to 2^51!) if you look at the hash table: typedef struct hashtable_entry {
uint32_t x;
uint32_t exponent;
} hashtable_entry;
#define HASH_SIZE (2*GSTEP)
hashtable_entry table[HASH_SIZE];
each entry size is 32 bit + 32 bit = 64 bit = 8 byte. The size of the hash table is 2*GSTEP, 2^26 entries. So for the original script: 8 byte * 2^26 = 2^29 bytes, 512 MB. If you change GSTEP from 2^25 to 2^26, you can find the keys #51 and #52 too (if you have more than 1 GB). It is not correct at all saying that at the current level we need 2^60 giant steps / 2^60 baby steps!I did many other modifications to the code. I can have a max number of giant steps (for my RAM) equal to 2^30, if I need to search in a bigger space than 2^60 I have to split then the baby step lists ( I generate first a hash table with a part of the list, then I delete it and I create another one, and so on). This way the program becomes very slow, I can retrieve a key in a 2^60 space in a very short time, but not over the 2^70 (unless I accept to wait days to have the result). |
|
|
|
@zielar: it is possible, I used the baby step giant step algorithm to retrieve the key #60 in about 80 seconds. And I have 32 GB ram. space search for each key of the puzzle transaction: key #1 : from 1 to 1 (2^0 -> 2^1 - 1) key #2 : from 2 to 3 (2^1 -> 2^2 - 1) key #3 : from 4 to 7 (2^2 -> 2^3 - 1) key #4 : from 8 to 15 (2^3 -> 2^4 - 1) .... key #60: from 2^59 to 2^60 - 1 Let's say for semplicity that our space search in this case is 2^60 (actually is only half, 2^59). P is the public key, we want to find the private key k. If G is the generator of the curve, the private key k is the number : k*G = P baby-step-giant-step (--> http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/): you create two lists, the first one (the baby steps list) in a hash table stored in the Ram and the second one (the giant steps list) dynamic: a) ( baby steps list): each baby step is equal to 1 (the distance between 2 consecutive elements is 1*G) and we store all these public keys: (0G), 1*G, 2*G, 3*G, 4*G, 5*G, ..., 2^30*G (because sqrt(2^60) = 2^30) in a hash table b) ( giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(2^60) = 2^30, namely the distance between 2 elements is 2^30*G . We generate on fly this list: P, P - 2^30*G, P - 2*2^30*G, P - 3*2^30*G, P - 4*2^30*G, P - 5*2^30*G, ....., P - (2^30 - 1)*2^30*G and we check if there is a element in the giant-steps list equal to an element in the baby-steps list. If for example P - 5*2^30*G = 1000*G, then P = 5*2^30*G + 1000*G --> P = (5*2^30 + 1000) * G --> private key k = (5*2^30 + 1000)2 lists, 2^30 elements * 2^30 elements = 2^60 comparisons without doing 2^60 operations, this is the trick. Hash table: 2^30 entries, each entry has the coordinate x of the public key (256 bit) + the number of the private key (max 32 bit). I'm using only the first 32 bits of the x instead of 256 bits (there are only few false collisions looking at the first 32 bits and I check these collisions), then I need to store (32 + 32) * 2^30 bit, 2^36 bit, 8 GByte. The hash table actually has to have the double of the number of the keys in the baby steps list (to avoid collisions between two different "x" that share the same 32 bits), so I need at least 16 GByte. With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256k1 curve), I can run the program. When the search space is greater than 60 bit, let's say 62 bit, I can't store all the 2^31 public keys of the baby steps list at once in the Ram, then I split 2^31 in 2 lists of 2^30 elements, A e B, then first I check the entire giant steps list against the list A, and if there is no match, I generate the list B and I generate again the giant steps list. |
|
|
|
and address 60 has been solved today ! who can give the private key ?
Private key : 0000000000000000000000000000000000000000000000000fc07a1825367bbe
Public key :
x: 48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
y: d094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f
PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYkzijLsc5qE43yZ5eLV
Address c. : cdf8e5c7503a9d22642e3ecfc87817672787b9c5
Address c. : 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su
|
|
|
|
|
Show Posts
