I know VanitySearch is just check first few bits of the address but that could be useful trade off for example checking 70% of the address to increase the speed of keyhunt and if there are a hit then do 100% checking.
I will check it thanks.
Regards
Topic: Some doubts about rmd160 and address for vanity search (Read 276 times)
I will check it thanks.
Regards
Well yes it is some offtopic but i going to reply to you here
Okay, I didn't get your idea at first glance, but after rereading it for the second time, I now understand what you're trying to do.
There are many substractions in BSGS not only ONE example:
Current Implementation:
Code:
Key 99
known range 75-100
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,25,20}
First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24
New Target Key 24
Giant step 0
24 - 0 = 24 is on Baby Table? NO
Giant step 1
24 - 5 = 19 is on Baby Table? NO
Giant step 2
24 - 10 = 14 is on Baby Table? NO
Giant step 3
24 - 15 = 9 is on Baby Table? NO
Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)
Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99
known range 75-100
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,25,20}
First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24
New Target Key 24
Giant step 0
24 - 0 = 24 is on Baby Table? NO
Giant step 1
24 - 5 = 19 is on Baby Table? NO
Giant step 2
24 - 10 = 14 is on Baby Table? NO
Giant step 3
24 - 15 = 9 is on Baby Table? NO
Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)
Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99
Your proposed Implementation:
Code:
Key 99
known range 75-100
Baby step 5 = {75,76,77,78,79}
Giant step 5 = {0,5,10,25,20}
Target Key 99
Giant step 0
99 - 0 = 99 is on Baby Table? NO
Giant step 1
99 - 5 = 94 is on Baby Table? NO
Giant step 2
99 - 10 = 89 is on Baby Table? NO
Giant step 3
99 - 15 = 84 is on Baby Table? NO
Giant step 4
99 - 20 = 79 is on Baby Table? YES (HIT)
Calcualted KEY is the HIT key
I don't know if that is your idea or not, please correctme if im wrong But in this example We only avoid one substraction, all the Giant Step subtractions remain... There will be some more varians of this (only make stride known range 75-100
Baby step 5 = {75,76,77,78,79}
Giant step 5 = {0,5,10,25,20}
Target Key 99
Giant step 0
99 - 0 = 99 is on Baby Table? NO
Giant step 1
99 - 5 = 94 is on Baby Table? NO
Giant step 2
99 - 10 = 89 is on Baby Table? NO
Giant step 3
99 - 15 = 84 is on Baby Table? NO
Giant step 4
99 - 20 = 79 is on Baby Table? YES (HIT)
Calcualted KEY is the HIT key
with the Giant step, etc...) but almost all keep the Giant Step subtractions.
BTW another important thing to Generate a lis from 1 to X is that we can use that SAME list for ANOTHER targets BUt if you do the list from Target to ( Target + X), then that list only is going to be useful againts that specific target.
Mora about BSGS: https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/
You are right, I was wrong. I just think of it in my head and I'm aware of trade off, creating new list with every target but when you put it with example I see it clearly useless.
There something I found odd that could be useful for this topic, I test both KeyHunt-Cuda & VanitySearch, there result is too big different in the speed.
KeyHunt-Cuda(I test on around 20M keys, so with one key it should be 2200-2400Mk/s)
[00:00:04] [CPU+GPU: 2151.32 Mk/s] [GPU: 2151.32 Mk/s] [C: 0.000000 %] [R: 0] [T: 8,606,711,808 (34 bit)] [F: 0]
VanitySearch
[5258.87 Mkey/s][GPU 5258.87 Mkey/s][Total 2^36.89][Prob 0.0%][50% in 42.0213y][Found 0]
I know VanitySearch is just check first few bits of the address but that could be useful trade off for example checking 70% of the address to increase the speed of keyhunt and if there are a hit then do 100% checking.
This could be out of topic but I have suggestion for BSGS.
Instead of create list from 1bit -> Xbit, create it from target -> Xbit (or reverse) so you can just directly check the hash table without doing any subtract to the private key.
Instead of create list from 1bit -> Xbit, create it from target -> Xbit (or reverse) so you can just directly check the hash table without doing any subtract to the private key.
Well yes it is some offtopic but i going to reply to you here
Okay, I didn't get your idea at first glance, but after rereading it for the second time, I now understand what you're trying to do.
There are many substractions in BSGS not only ONE example:
Current Implementation:
Code:
Key 99
known range 75-100
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,15,20}
First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24
New Target Key 24
Giant step 0
24 - 0 = 24 is on Baby Table? NO
Giant step 1
24 - 5 = 19 is on Baby Table? NO
Giant step 2
24 - 10 = 14 is on Baby Table? NO
Giant step 3
24 - 15 = 9 is on Baby Table? NO
Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)
Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99
known range 75-100
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,15,20}
First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24
New Target Key 24
Giant step 0
24 - 0 = 24 is on Baby Table? NO
Giant step 1
24 - 5 = 19 is on Baby Table? NO
Giant step 2
24 - 10 = 14 is on Baby Table? NO
Giant step 3
24 - 15 = 9 is on Baby Table? NO
Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)
Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99
Your proposed Implementation:
Code:
Key 99
known range 75-100
Baby step 5 = {75,76,77,78,79}
Giant step 5 = {0,5,10,15,20}
Target Key 99
Giant step 0
99 - 0 = 99 is on Baby Table? NO
Giant step 1
99 - 5 = 94 is on Baby Table? NO
Giant step 2
99 - 10 = 89 is on Baby Table? NO
Giant step 3
99 - 15 = 84 is on Baby Table? NO
Giant step 4
99 - 20 = 79 is on Baby Table? YES (HIT)
Calcualted KEY is the HIT key
I don't know if that is your idea or not, please correctme if im wrong But in this example We only avoid one substraction, all the Giant Step subtractions remain... There will be some more varians of this (only make stride known range 75-100
Baby step 5 = {75,76,77,78,79}
Giant step 5 = {0,5,10,15,20}
Target Key 99
Giant step 0
99 - 0 = 99 is on Baby Table? NO
Giant step 1
99 - 5 = 94 is on Baby Table? NO
Giant step 2
99 - 10 = 89 is on Baby Table? NO
Giant step 3
99 - 15 = 84 is on Baby Table? NO
Giant step 4
99 - 20 = 79 is on Baby Table? YES (HIT)
Calcualted KEY is the HIT key
with the Giant step, etc...) but almost all keep the Giant Step subtractions.
BTW another important thing to Generate a list from 1 to X is that we can use that SAME list for ANOTHER targets BUt if you do the list from Target to ( Target + X), then that list only is going to be useful againts that specific target.
Mora about BSGS: https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/
This could be out of topic but I have suggestion for BSGS.
Instead of create list from 1bit -> Xbit, create it from target -> Xbit (or reverse) so you can just directly check the hash table without doing any subtract to the private key.
Instead of create list from 1bit -> Xbit, create it from target -> Xbit (or reverse) so you can just directly check the hash table without doing any subtract to the private key.
Yes actually is what my program do it search those base 58 strings that decodes into 25 bytes. Theninuse those values as limits
The thing about base58 encoded addresses is that they don't have a fixed length, they can have between 25 and 34 characters (for mainnet P2PKH). This means you should set your "Lower Limit" value to "1Bitcoin11111111111111111" (25 characters in total) and your "Higher Limit" should be "1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz" (34 characters in total).
But now there is another problem. These limits (25 and 34 chars) happen on very special occasions and can not happen with every combination of characters. But there is an easy fix, you just decode the initial limits I mentioned above and if the result was less than the RIPEMD160 size (20+1+4 byte) you pad the shorter values and remove characters from longer ones.
Keep ind mind that because of how Base58 encoding works there is not a 1:1 relationship between bytes and number of characters. In other words if for example your result is missing 3 bytes you can't just add 3 characters. You have to do it step by step to find the correct value like this (added 8 chars to get the missing 6 bytes):
Now you have to choose the lower (hex) value from the lower limit that gives 25 bytes and the higher (hex) value from the upper limit that gives 25 bytes.
As you can see here we had 2 variation of lower limit with 25 bytes and the lower hex value is the first one but we only got one valid result for upper limit so the actual search space is:
But now there is another problem. These limits (25 and 34 chars) happen on very special occasions and can not happen with every combination of characters. But there is an easy fix, you just decode the initial limits I mentioned above and if the result was less than the RIPEMD160 size (20+1+4 byte) you pad the shorter values and remove characters from longer ones.
Keep ind mind that because of how Base58 encoding works there is not a 1:1 relationship between bytes and number of characters. In other words if for example your result is missing 3 bytes you can't just add 3 characters. You have to do it step by step to find the correct value like this (added 8 chars to get the missing 6 bytes):
Code:
1Bitcoin11111111111111111 > 00047502e626c837fa53ff2bca12b84cf60000 (19 bytes)
pad:
1Bitcoin111111111111111111 > 00010282a824c95caeb707cfebc83dc16fbc0000 (20 bytes)
1Bitcoin1111111111111111111 > 003a919a18559eff9577c51b6b5dfdd350980000 (20 bytes)
1Bitcoin11111111111111111111 > 000d44fce9836605e7dd22a836534b81e042700000 (21 bytes)
[...]
1Bitcoin111111111111111111111111 > 0008f352601de4f02026a2374257306a7e294e29d7000000 (24 bytes)
1Bitcoin1111111111111111111111111 > 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000 (25 bytes)
1Bitcoin11111111111111111111111111 > 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000 (25 bytes)
1Bitcoin111111111111111111111111111 > 001aa5a936f8001e853804e1d419e3bc8c2aa91cc07f98000000 (26 bytes)
pad:
1Bitcoin111111111111111111 > 00010282a824c95caeb707cfebc83dc16fbc0000 (20 bytes)
1Bitcoin1111111111111111111 > 003a919a18559eff9577c51b6b5dfdd350980000 (20 bytes)
1Bitcoin11111111111111111111 > 000d44fce9836605e7dd22a836534b81e042700000 (21 bytes)
[...]
1Bitcoin111111111111111111111111 > 0008f352601de4f02026a2374257306a7e294e29d7000000 (24 bytes)
1Bitcoin1111111111111111111111111 > 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000 (25 bytes)
1Bitcoin11111111111111111111111111 > 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000 (25 bytes)
1Bitcoin111111111111111111111111111 > 001aa5a936f8001e853804e1d419e3bc8c2aa91cc07f98000000 (26 bytes)
Code:
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz > 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff (25 bytes)
The initial value is correct but lets add and remove one char:
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz > 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff (24 bytes)
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzzz > 001aa5a936f847e5e7d0ddf3783fb57fc9ec79678674bfffffff (26 bytes)
The initial value is correct but lets add and remove one char:
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz > 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff (24 bytes)
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzzz > 001aa5a936f847e5e7d0ddf3783fb57fc9ec79678674bfffffff (26 bytes)
Now you have to choose the lower (hex) value from the lower limit that gives 25 bytes and the higher (hex) value from the upper limit that gives 25 bytes.
As you can see here we had 2 variation of lower limit with 25 bytes and the lower hex value is the first one but we only got one valid result for upper limit so the actual search space is:
Code:
1Bitcoin1111111111111111111111111 > 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000 (25 bytes)
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz > 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff (25 bytes)
1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz > 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff (25 bytes)
I don't have your C module, but shouldn't you check for the lowest and highest valid address? Replacing the remaining base58 characters with ones and z's doesn't make the address valid, because of the checksum.
Guys this is an example, the Checkcum or validity doesn't is important for the lowest and highes addresses
I only use those values as limits, when i compare if the current hash I omit the prefix 00 byte and the postfix checksum bytes.
Example:
Code:
Target base58: 1Bitcoin
Lower limit base 58: 1Bitcoin11111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Higher limit rmd160: 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
Current Address: 1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo
current hashrmd: 00759d667708fb31996328d15f3056d190278a1bb57dc660b2
Lower limit base 58: 1Bitcoin11111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Higher limit rmd160: 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
Current Address: 1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo
current hashrmd: 00759d667708fb31996328d15f3056d190278a1bb57dc660b2
Code:
(Lower Limit) <= (Current HASH) <= (Higher Limit)
For this case will be:
Code:
759d667708d463667bab9e23c1b83761d6c71dcd<= 759d667708fb31996328d15f3056d190278a1bb5 <= 759d66770a11348c6dc1fda8d293dbc1dec867d5
memcmp stop at the first byte with some difference so the comparation will be only like:
759d667708d4<= 759d667708fb <= 759d66770a11
So if the Current hash value is between the given limits that means the function base58_encode_checksum(00 byte +current hash) will have the Same expected Prefix for this case will be "1Bitcoin"
Have you considered how permutations work on rmd160 hashes?
...
How exactly skipping a simple base58 encoding could double the speed? Is base58 encoding heavier than hashing? If that's the case then it could change a lot of other things, I just need to think what those things could be.
...
How exactly skipping a simple base58 encoding could double the speed? Is base58 encoding heavier than hashing? If that's the case then it could change a lot of other things, I just need to think what those things could be.
About the speed that its what in practice i get when i run keyhunt for addresses and keyhunt for hashes rmd160. rmd160 search get almost the double of the speed of address search
Aboute the permutations i will check it.
I already tested and for each prefix that we search for vanity ["1Fortune", "1Prosper", "1Winner", etc...] and almost always there are two RMD ranges that generate the same Base58 prefix, so I think that i will add all those ranges to the search, it will be enough.
The next example compare one address againts some prefixes. but it can also be the other way around Many address to one or more vanity prefixes
Output:
Code:
Address 1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo encode to 759d667708fb31996328d15f3056d190278a1bb5
Raw size: 25, Encoded size: 33 : expected string 1Fortune, base string 1Fortune1111111111111111111111111 => hex 0002ccf0c09d38ef18ac118453594f3bf77af9d90366000000
Raw size: 25, Encoded size: 34 : expected string 1Fortune, base string 1Fortune11111111111111111111111111 => hex 00a26e8ba39ee62b96fbf7fae23bf39611dc9b2ac51c000000
Raw size: 25, Encoded size: 33 : expected string 1Fortune, base string 1Fortunezzzzzzzzzzzzzzzzzzzzzzzzz => hex 0002ccf0c09d3e6576041abaf0203889d5d363cd0c5fffffff
Raw size: 25, Encoded size: 34 : expected string 1Fortune, base string 1Fortunezzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00a26e8ba3a022fcbcee0e5a674ccf3a71e49c74cdbfffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (02ccf0c09d38ef18ac118453594f3bf77af9d903 and 02ccf0c09d3e6576041abaf0203889d5d363cd0c)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (a26e8ba39ee62b96fbf7fae23bf39611dc9b2ac5 and a26e8ba3a022fcbcee0e5a674ccf3a71e49c74cd)
Raw size: 25, Encoded size: 33 : expected string 1Prosper, base string 1Prosper1111111111111111111111111 => hex 000452ba9d1f9147e608975a8067caddeb99dbb63f06000000
Raw size: 25, Encoded size: 34 : expected string 1Prosper, base string 1Prosper11111111111111111111111111 => hex 00fabe479926ea4a1df24a811783f64760dbc74a475c000000
Raw size: 25, Encoded size: 33 : expected string 1Prosper, base string 1Prosperzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000452ba9d1f96be4360a0911d2eb42bc9f245aa47ffffffff
Raw size: 25, Encoded size: 34 : expected string 1Prosper, base string 1Prosperzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00fabe479928271b43e460e09c94d1ebc0e3c8944fffffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (0452ba9d1f9147e608975a8067caddeb99dbb63f and 0452ba9d1f96be4360a0911d2eb42bc9f245aa47)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (fabe479926ea4a1df24a811783f64760dbc74a47 and fabe479928271b43e460e09c94d1ebc0e3c8944f)
Raw size: 25, Encoded size: 33 : expected string 1Winner, base string 1Winner11111111111111111111111111 => hex 00059ef26b901a66d6bda68342507cdb76d44268a9dc000000
Raw size: 25, Encoded size: 33 : expected string 1Winner, base string 1Winnerzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00059ef26b915737fcafbce2c761587fd6dc43b2b27fffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (059ef26b901a66d6bda68342507cdb76d44268a9 and 059ef26b915737fcafbce2c761587fd6dc43b2b2)
Raw size: 25, Encoded size: 33 : expected string 1Bitcoin, base string 1Bitcoin1111111111111111111111111 => hex 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000
Raw size: 25, Encoded size: 34 : expected string 1Bitcoin, base string 1Bitcoin11111111111111111111111111 => hex 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Raw size: 25, Encoded size: 33 : expected string 1Bitcoin, base string 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff
Raw size: 25, Encoded size: 34 : expected string 1Bitcoin, base string 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (020720a9c6c5de6748c0c08507c0f820955bb57a and 020720a9c6cb54c4a0c9f721ceaa45feedc5a983)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 match bewteen the start and end range (759d667708d463667bab9e23c1b83761d6c71dcd and 759d66770a11348c6dc1fda8d293dbc1dec867d5)
Raw size: 25, Encoded size: 33 : expected string 1Satoshi, base string 1Satoshi1111111111111111111111111 => hex 0004d6b1134630fc8c8a8caf92ab9153c6e5569b77fa000000
Raw size: 25, Encoded size: 33 : expected string 1Satoshi, base string 1Satoshizzzzzzzzzzzzzzzzzzzzzzzzz => hex 0004d6b113463672e9e295e62f727aa1a53dc08f80f3ffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (04d6b1134630fc8c8a8caf92ab9153c6e5569b77 and 04d6b113463672e9e295e62f727aa1a53dc08f80)
Raw size: 25, Encoded size: 33 : expected string 1P, base string 1P1111111111111111111111111111111 => hex 00042926b2614c8a210db0867df56b3274219a39c700000000
Raw size: 25, Encoded size: 34 : expected string 1P, base string 1P11111111111111111111111111111111 => hex 00f152c46a0b574b7d19fe78899a496e4f9cf1171600000000
Raw size: 25, Encoded size: 33 : expected string 1P, base string 1Pzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000459912eda15d639d42146c98092fa90aec425217fffffff
Raw size: 25, Encoded size: 34 : expected string 1P, base string 1Pzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00fc4ae49d68f2891a0f8a09a7214cc4c798706996ffffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (042926b2614c8a210db0867df56b3274219a39c7 and 0459912eda15d639d42146c98092fa90aec42521)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (f152c46a0b574b7d19fe78899a496e4f9cf11716 and fc4ae49d68f2891a0f8a09a7214cc4c798706996)
Raw size: 25, Encoded size: 33 : expected string 1Q, base string 1Q1111111111111111111111111111111 => hex 000459912eda15d639d42146c98092fa90aec4252180000000
Raw size: 25, Encoded size: 34 : expected string 1Q, base string 1Q11111111111111111111111111111111 => hex 00fc4ae49d68f2891a0f8a09a7214cc4c79870699700000000
Raw size: 25, Encoded size: 33 : expected string 1Q, base string 1Qzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000489fbab52df22529a9207150bbac2ad3bee107bffffffff
Something is wrong please check this case "1Q"
Raw size: 25, Encoded size: 33 : expected string 1Fortune, base string 1Fortune1111111111111111111111111 => hex 0002ccf0c09d38ef18ac118453594f3bf77af9d90366000000
Raw size: 25, Encoded size: 34 : expected string 1Fortune, base string 1Fortune11111111111111111111111111 => hex 00a26e8ba39ee62b96fbf7fae23bf39611dc9b2ac51c000000
Raw size: 25, Encoded size: 33 : expected string 1Fortune, base string 1Fortunezzzzzzzzzzzzzzzzzzzzzzzzz => hex 0002ccf0c09d3e6576041abaf0203889d5d363cd0c5fffffff
Raw size: 25, Encoded size: 34 : expected string 1Fortune, base string 1Fortunezzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00a26e8ba3a022fcbcee0e5a674ccf3a71e49c74cdbfffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (02ccf0c09d38ef18ac118453594f3bf77af9d903 and 02ccf0c09d3e6576041abaf0203889d5d363cd0c)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (a26e8ba39ee62b96fbf7fae23bf39611dc9b2ac5 and a26e8ba3a022fcbcee0e5a674ccf3a71e49c74cd)
Raw size: 25, Encoded size: 33 : expected string 1Prosper, base string 1Prosper1111111111111111111111111 => hex 000452ba9d1f9147e608975a8067caddeb99dbb63f06000000
Raw size: 25, Encoded size: 34 : expected string 1Prosper, base string 1Prosper11111111111111111111111111 => hex 00fabe479926ea4a1df24a811783f64760dbc74a475c000000
Raw size: 25, Encoded size: 33 : expected string 1Prosper, base string 1Prosperzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000452ba9d1f96be4360a0911d2eb42bc9f245aa47ffffffff
Raw size: 25, Encoded size: 34 : expected string 1Prosper, base string 1Prosperzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00fabe479928271b43e460e09c94d1ebc0e3c8944fffffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (0452ba9d1f9147e608975a8067caddeb99dbb63f and 0452ba9d1f96be4360a0911d2eb42bc9f245aa47)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (fabe479926ea4a1df24a811783f64760dbc74a47 and fabe479928271b43e460e09c94d1ebc0e3c8944f)
Raw size: 25, Encoded size: 33 : expected string 1Winner, base string 1Winner11111111111111111111111111 => hex 00059ef26b901a66d6bda68342507cdb76d44268a9dc000000
Raw size: 25, Encoded size: 33 : expected string 1Winner, base string 1Winnerzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00059ef26b915737fcafbce2c761587fd6dc43b2b27fffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (059ef26b901a66d6bda68342507cdb76d44268a9 and 059ef26b915737fcafbce2c761587fd6dc43b2b2)
Raw size: 25, Encoded size: 33 : expected string 1Bitcoin, base string 1Bitcoin1111111111111111111111111 => hex 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000
Raw size: 25, Encoded size: 34 : expected string 1Bitcoin, base string 1Bitcoin11111111111111111111111111 => hex 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Raw size: 25, Encoded size: 33 : expected string 1Bitcoin, base string 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff
Raw size: 25, Encoded size: 34 : expected string 1Bitcoin, base string 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (020720a9c6c5de6748c0c08507c0f820955bb57a and 020720a9c6cb54c4a0c9f721ceaa45feedc5a983)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 match bewteen the start and end range (759d667708d463667bab9e23c1b83761d6c71dcd and 759d66770a11348c6dc1fda8d293dbc1dec867d5)
Raw size: 25, Encoded size: 33 : expected string 1Satoshi, base string 1Satoshi1111111111111111111111111 => hex 0004d6b1134630fc8c8a8caf92ab9153c6e5569b77fa000000
Raw size: 25, Encoded size: 33 : expected string 1Satoshi, base string 1Satoshizzzzzzzzzzzzzzzzzzzzzzzzz => hex 0004d6b113463672e9e295e62f727aa1a53dc08f80f3ffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (04d6b1134630fc8c8a8caf92ab9153c6e5569b77 and 04d6b113463672e9e295e62f727aa1a53dc08f80)
Raw size: 25, Encoded size: 33 : expected string 1P, base string 1P1111111111111111111111111111111 => hex 00042926b2614c8a210db0867df56b3274219a39c700000000
Raw size: 25, Encoded size: 34 : expected string 1P, base string 1P11111111111111111111111111111111 => hex 00f152c46a0b574b7d19fe78899a496e4f9cf1171600000000
Raw size: 25, Encoded size: 33 : expected string 1P, base string 1Pzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000459912eda15d639d42146c98092fa90aec425217fffffff
Raw size: 25, Encoded size: 34 : expected string 1P, base string 1Pzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 00fc4ae49d68f2891a0f8a09a7214cc4c798706996ffffffff
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (042926b2614c8a210db0867df56b3274219a39c7 and 0459912eda15d639d42146c98092fa90aec42521)
The target Address 759d667708fb31996328d15f3056d190278a1bb5 NOT match bewteen the start and end range (f152c46a0b574b7d19fe78899a496e4f9cf11716 and fc4ae49d68f2891a0f8a09a7214cc4c798706996)
Raw size: 25, Encoded size: 33 : expected string 1Q, base string 1Q1111111111111111111111111111111 => hex 000459912eda15d639d42146c98092fa90aec4252180000000
Raw size: 25, Encoded size: 34 : expected string 1Q, base string 1Q11111111111111111111111111111111 => hex 00fc4ae49d68f2891a0f8a09a7214cc4c79870699700000000
Raw size: 25, Encoded size: 33 : expected string 1Q, base string 1Qzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz => hex 000489fbab52df22529a9207150bbac2ad3bee107bffffffff
Something is wrong please check this case "1Q"
Code:
Code:
/*
Compile in the keyhunt directory
gcc -o examplermdvanity examplermdvanity.c base58.o util.o
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "util.h"
#include "base58/libbase58.h"
#define LIST_SIZE 8
int main() {
char *targetaddress = "1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo";
unsigned char raw_value_target[50];
char *hexaddress;
char *hextemp,*hextempA,*hextempB;
char *list_targets[LIST_SIZE] = {"1Fortune", "1Prosper", "1Winner", "1Bitcoin","1Satoshi","1P","1Q","1R"};
char target[50];
int i,j,cmpA,cmpB;
int raw_values_A_size,raw_values_B_size;
unsigned char **raw_values_A,**raw_values_B;
unsigned char raw_value_A[50],raw_value_B[50];
size_t stringsize,raw_value_length;
stringsize = strlen(targetaddress);
raw_value_length = 50;
b58tobin(raw_value_target,&raw_value_length,targetaddress,stringsize);
b58tobin(raw_value_target,&raw_value_length,targetaddress,stringsize);
hexaddress = tohex(raw_value_target+1,20);
printf("Address %s encode to %s\n",targetaddress,hexaddress);
raw_values_A = NULL;
raw_values_B = NULL;
for(i = 0; i < LIST_SIZE; i++) {
raw_value_length = 50;
stringsize = strlen(list_targets[i]);
memset(raw_value_A,0,50);
memset(raw_value_B,0,50);
memset(target,0,50);
strncpy(target,list_targets[i],stringsize);
j = 0;
do {
raw_value_length = 50;
b58tobin(raw_value_A,&raw_value_length,target,stringsize);
if(raw_value_length < 25) {
target[stringsize] = '1';
stringsize++;
}
if(raw_value_length == 25){
b58tobin(raw_value_A,&raw_value_length,target,stringsize);
raw_values_A = realloc(raw_values_A,(j+1) * sizeof(unsigned char *));
raw_values_A[j] = calloc(25,1);
memcpy(raw_values_A[j],raw_value_A,25);
hextemp = tohex(raw_values_A[j],raw_value_length);
printf("Raw size: %li, Encoded size: %li : expected string %s, base string %s => hex %s\n", raw_value_length,stringsize,list_targets[i],target,hextemp);
free(hextemp);
j++;
raw_values_A_size = j;
target[stringsize] = '1';
stringsize++;
}
}while(raw_value_length <= 25);
stringsize = strlen(list_targets[i]);
memset(raw_value_B,0,50);
memset(target,0,50);
strncpy(target,list_targets[i],stringsize);
j = 0;
do {
raw_value_length = 50;
b58tobin(raw_value_B,&raw_value_length,target,stringsize);
if(raw_value_length < 25) {
target[stringsize] = 'z';
stringsize++;
}
if(raw_value_length == 25) {
b58tobin(raw_value_B,&raw_value_length,target,stringsize);
raw_values_B = realloc(raw_values_B,(j+1) * sizeof(unsigned char *));
raw_values_B[j] = calloc(25,1);
memcpy(raw_values_B[j],raw_value_B,25);
hextemp = tohex(raw_values_B[j],raw_value_length);
printf("Raw size: %li, Encoded size: %li : expected string %s, base string %s => hex %s\n", raw_value_length,stringsize,list_targets[i],target,hextemp);
free(hextemp);
j++;
raw_values_B_size = j;
target[stringsize] = 'z';
stringsize++;
}
}while(raw_value_length <= 25);
if(raw_values_A_size != raw_values_B_size) {
printf("Something is wrong please check this case \"%s\"\n",list_targets[i]);
exit(0);
}
for(j = 0; j < raw_values_A_size; j++) {
hextempA = tohex(raw_values_A[j]+1,20);
hextempB = tohex(raw_values_B[j]+1,20);
cmpA = memcmp(raw_values_A[j]+1,raw_value_target+1,20);
cmpB = memcmp(raw_values_B[j]+1,raw_value_target+1,20);
if(cmpA <= 0 && cmpB >= 0) {
printf("The target Address %s match bewteen the start and end range (%s and %s)\n",hexaddress,hextempA,hextempB);
}
else {
printf("The target Address %s NOT match bewteen the start and end range (%s and %s)\n",hexaddress,hextempA,hextempB);
}
free(hextempA);
free(hextempB);
}
if(raw_values_A_size > 0){
for(j = 0; j < raw_values_A_size; j++) {
free(raw_values_A[j]);
free(raw_values_B[j]);
}
free(raw_values_A);
free(raw_values_B);
raw_values_A =NULL;
raw_values_B =NULL;
}
}
}
Compile in the keyhunt directory
gcc -o examplermdvanity examplermdvanity.c base58.o util.o
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "util.h"
#include "base58/libbase58.h"
#define LIST_SIZE 8
int main() {
char *targetaddress = "1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo";
unsigned char raw_value_target[50];
char *hexaddress;
char *hextemp,*hextempA,*hextempB;
char *list_targets[LIST_SIZE] = {"1Fortune", "1Prosper", "1Winner", "1Bitcoin","1Satoshi","1P","1Q","1R"};
char target[50];
int i,j,cmpA,cmpB;
int raw_values_A_size,raw_values_B_size;
unsigned char **raw_values_A,**raw_values_B;
unsigned char raw_value_A[50],raw_value_B[50];
size_t stringsize,raw_value_length;
stringsize = strlen(targetaddress);
raw_value_length = 50;
b58tobin(raw_value_target,&raw_value_length,targetaddress,stringsize);
b58tobin(raw_value_target,&raw_value_length,targetaddress,stringsize);
hexaddress = tohex(raw_value_target+1,20);
printf("Address %s encode to %s\n",targetaddress,hexaddress);
raw_values_A = NULL;
raw_values_B = NULL;
for(i = 0; i < LIST_SIZE; i++) {
raw_value_length = 50;
stringsize = strlen(list_targets[i]);
memset(raw_value_A,0,50);
memset(raw_value_B,0,50);
memset(target,0,50);
strncpy(target,list_targets[i],stringsize);
j = 0;
do {
raw_value_length = 50;
b58tobin(raw_value_A,&raw_value_length,target,stringsize);
if(raw_value_length < 25) {
target[stringsize] = '1';
stringsize++;
}
if(raw_value_length == 25){
b58tobin(raw_value_A,&raw_value_length,target,stringsize);
raw_values_A = realloc(raw_values_A,(j+1) * sizeof(unsigned char *));
raw_values_A[j] = calloc(25,1);
memcpy(raw_values_A[j],raw_value_A,25);
hextemp = tohex(raw_values_A[j],raw_value_length);
printf("Raw size: %li, Encoded size: %li : expected string %s, base string %s => hex %s\n", raw_value_length,stringsize,list_targets[i],target,hextemp);
free(hextemp);
j++;
raw_values_A_size = j;
target[stringsize] = '1';
stringsize++;
}
}while(raw_value_length <= 25);
stringsize = strlen(list_targets[i]);
memset(raw_value_B,0,50);
memset(target,0,50);
strncpy(target,list_targets[i],stringsize);
j = 0;
do {
raw_value_length = 50;
b58tobin(raw_value_B,&raw_value_length,target,stringsize);
if(raw_value_length < 25) {
target[stringsize] = 'z';
stringsize++;
}
if(raw_value_length == 25) {
b58tobin(raw_value_B,&raw_value_length,target,stringsize);
raw_values_B = realloc(raw_values_B,(j+1) * sizeof(unsigned char *));
raw_values_B[j] = calloc(25,1);
memcpy(raw_values_B[j],raw_value_B,25);
hextemp = tohex(raw_values_B[j],raw_value_length);
printf("Raw size: %li, Encoded size: %li : expected string %s, base string %s => hex %s\n", raw_value_length,stringsize,list_targets[i],target,hextemp);
free(hextemp);
j++;
raw_values_B_size = j;
target[stringsize] = 'z';
stringsize++;
}
}while(raw_value_length <= 25);
if(raw_values_A_size != raw_values_B_size) {
printf("Something is wrong please check this case \"%s\"\n",list_targets[i]);
exit(0);
}
for(j = 0; j < raw_values_A_size; j++) {
hextempA = tohex(raw_values_A[j]+1,20);
hextempB = tohex(raw_values_B[j]+1,20);
cmpA = memcmp(raw_values_A[j]+1,raw_value_target+1,20);
cmpB = memcmp(raw_values_B[j]+1,raw_value_target+1,20);
if(cmpA <= 0 && cmpB >= 0) {
printf("The target Address %s match bewteen the start and end range (%s and %s)\n",hexaddress,hextempA,hextempB);
}
else {
printf("The target Address %s NOT match bewteen the start and end range (%s and %s)\n",hexaddress,hextempA,hextempB);
}
free(hextempA);
free(hextempB);
}
if(raw_values_A_size > 0){
for(j = 0; j < raw_values_A_size; j++) {
free(raw_values_A[j]);
free(raw_values_B[j]);
}
free(raw_values_A);
free(raw_values_B);
raw_values_A =NULL;
raw_values_B =NULL;
}
}
}
Have you considered how permutations work on rmd160 hashes?
Now what you need to do is to calculate permutations correctly and the tool should skip invalid ranges by itself.
How exactly skipping a simple base58 encoding could double the speed? Is base58 encoding heavier than hashing? If that's the case then it could change a lot of other things, I just need to think what those things could be.
Code:
1Bitcoin1111111111111111111qzESSG
1Bitcoinzzzzzzzzzzzzzzzzzzzyf4ZS9
1Bitcoinzzzzzzzzzzzzzzzzzzzyf4ZS9
Code:
1BitcoimzzzzzzzzzzzzzzzzzzzvQRFio
1Bitcoinzzzzzzzzzzzzzzzzzzzyf4ZS9
Changing the 6th character from right end of checksum changed the address entirely, it even forced 1Bitcoin into 1Bitcoim.1Bitcoinzzzzzzzzzzzzzzzzzzzyf4ZS9
Now what you need to do is to calculate permutations correctly and the tool should skip invalid ranges by itself.
How exactly skipping a simple base58 encoding could double the speed? Is base58 encoding heavier than hashing? If that's the case then it could change a lot of other things, I just need to think what those things could be.
What's the problem with decoding the wanted address, and only comparing RIPEMD-160 hashes? (with all the necessary protocol changes and additions of course)
I don't have your C module, but shouldn't you check for the lowest and highest valid address? Replacing the remaining base58 characters with ones and z's doesn't make the address valid, because of the checksum.
Quote
Code:
Lower limit base 58: 1Bitcoin1111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz
Edit.
TL;TR
Almost all the address before the prefix "1Q" have two valid RMD ranges.
I want to improve some feature of the tool that i develop keyhunt
Actually keyhunt can do some vanity search but it is slow because it do the search by string comparation something like:
example:
To improve the speed of the vanity search, So my idea was to do some vanity search but only comparing the hash rmd160 (i mean the binary or raw data not the hexadecimal string representation of it).
This avoid the Base58 encode, to do this we need to calcualte the lower and higher limit of the target hash and check if the current hash is bewteen them
example
Although this approach works well, I discovered that there are other valid lower and higher limit values for the hash rmd160 that may generate the same base58 prefix, as shown below:
In this case, my previous address would not match if compared based on its rmd value.
I wanted to use rmd because it avoids the base58 encoding process and makes the program almost twice as fast.
However, I now realize that there may be multiple valid rmd ranges that can generate the same base58 prefix.
I have not yet checked how other applications handle this comparison against vanity targets but i want to know your thoughts.
What is the most efficient method to search for vanity collisions without performing Base58 encoding, while ensuring that no hits are missed?
TL;TR
Almost all the address before the prefix "1Q" have two valid RMD ranges.
I want to improve some feature of the tool that i develop keyhunt
Actually keyhunt can do some vanity search but it is slow because it do the search by string comparation something like:
Code:
strncmp(current_addrres,vanity_target,len_vanity_target);
example:
Code:
strncmp("1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo","1Bitcoin",8);
To improve the speed of the vanity search, So my idea was to do some vanity search but only comparing the hash rmd160 (i mean the binary or raw data not the hexadecimal string representation of it).
This avoid the Base58 encode, to do this we need to calcualte the lower and higher limit of the target hash and check if the current hash is bewteen them
Code:
if(memcmp(rmd_lower_limit,rmd_current,20) >= 0 && memcmp(rmd_current,rmd_higher_limit,20) <= 0 ){
//match
}
//match
}
example
Code:
/*
Target base58: 1Bitcoin
Lower limit base 58: 1Bitcoin11111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Higher limit rmd160: 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
Current Address: 1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo
current hashrmd: 00759d667708fb31996328d15f3056d190278a1bb57dc660b2
So for this case the code evalute the next values:
*/
if(memcmp(759d667708d463667bab9e23c1b83761d6c71dcd,759d667708fb31996328d15f3056d190278a1bb5,20) >= 0 && memcmp(759d667708fb31996328d15f3056d190278a1bb5,759d66770a11348c6dc1fda8d293dbc1dec867d5,20) <= 0 ){
//match
}
Target base58: 1Bitcoin
Lower limit base 58: 1Bitcoin11111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00759d667708d463667bab9e23c1b83761d6c71dcd3c000000
Higher limit rmd160: 00759d66770a11348c6dc1fda8d293dbc1dec867d5dfffffff
Current Address: 1Bitcoin873Ns4mSAVnUn1eD43RBq89vqo
current hashrmd: 00759d667708fb31996328d15f3056d190278a1bb57dc660b2
So for this case the code evalute the next values:
*/
if(memcmp(759d667708d463667bab9e23c1b83761d6c71dcd,759d667708fb31996328d15f3056d190278a1bb5,20) >= 0 && memcmp(759d667708fb31996328d15f3056d190278a1bb5,759d66770a11348c6dc1fda8d293dbc1dec867d5,20) <= 0 ){
//match
}
Although this approach works well, I discovered that there are other valid lower and higher limit values for the hash rmd160 that may generate the same base58 prefix, as shown below:
Code:
/*
Target base58: 1Bitcoin
Lower limit base 58: 1Bitcoin1111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000
Higher limit rmd160: 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff
*/
Target base58: 1Bitcoin
Lower limit base 58: 1Bitcoin1111111111111111111111111
Higher limit base 58: 1Bitcoinzzzzzzzzzzzzzzzzzzzzzzzzz
Lower limit rmd160: 00020720a9c6c5de6748c0c08507c0f820955bb57ab6000000
Higher limit rmd160: 00020720a9c6cb54c4a0c9f721ceaa45feedc5a983afffffff
*/
In this case, my previous address would not match if compared based on its rmd value.
I wanted to use rmd because it avoids the base58 encoding process and makes the program almost twice as fast.
However, I now realize that there may be multiple valid rmd ranges that can generate the same base58 prefix.
I have not yet checked how other applications handle this comparison against vanity targets but i want to know your thoughts.
What is the most efficient method to search for vanity collisions without performing Base58 encoding, while ensuring that no hits are missed?
Jump to: