VanitySearch (Yet another address prefix finder) - page 59.

Lolo54

member

Activity: 131

Merit: 32

Quote from: Lolo54 on March 11, 2019, 07:59:11 AM

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!

Quote from: Lolo54 on March 06, 2019, 10:02:25 AM

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

Good Job Jean_Luc
but this time I don’t get a raise on my equipment it’s the same

Start Fri Mar 15 12:03:33 2019
Difficulty: 15318045009Search: 1testr
Base Key:EABBFA78AB6FB34A0D274DF6A909167A0CC8A231DE815525743C84097A632B86
Number of CPU thread: 4
4.290 MK/s (GPU 0.000 MK/s) (2^25.94) [P 0.42%][50.00% in 00:44:45][0]

Jean_Luc

sr. member

Activity: 462

Merit: 701

Hello,

I ended the implementation of endomorphisms and their symmetrics (CPU only).
The code is committed to GitHub for those who want to test.
On my hardware, I observe a ~20% speed increase (compressed addresses), the hash functions (SSE) takes now 76% of the CPU.
GPU implementation is coming...

Many thanks again to arulbero for these precious tips concerning symmetries and to all for you for helping to make this software better Wink

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on March 13, 2019, 04:23:46 PM

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?

May be there is a confusion between IntGroup::ModInv(256*3 ModMulK1) and Int::ModInv (The true ModInv).
Look only a the column on the right (Self CPU).

ModInv is taking ~2% (using compressed address) so if I multiply by 2 the group size I can expect a ~1% speed increase for the CPU release. I did the test on 1 core and as expected, the key rate goes from 3.4MKey/s to 3.44MKey/s. Of course for other applications where you do not need to hash, you can expect a more significant speed increase.
I attach a new CPU profile with SSE disabled (-nosse option) and using compressed address, this profile should be close enough to the GPU profile, there is no SIMD instruction on GPU to speed up hash functions.

Here the ModInv fall to 1%.

For VanitySearch, having a smaller group size is better (This is a reason why I worked a lot on this DRS62 ModInv implementation). I can double the size of the group (I will definitely do it) but not more. The GPU kernel performs one group per thread and send back hash160 to the CPU. If the group size is too large, memory transfer and allocation become a problem. Divide and rule Wink

Quote from: OgNasty on March 13, 2019, 07:54:49 PM

It's amazing how much progress is being made on this software so quickly. Great work!

Thanks

OgNasty

donator

Activity: 4760

Merit: 4323

Leading Crypto Sports Betting & Casino Platform

It's amazing how much progress is being made on this software so quickly. Great work!

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on March 13, 2019, 08:16:25 AM

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.

Quote from: Jean_Luc on March 13, 2019, 08:16:25 AM

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?

Lolo54

member

Activity: 131

Merit: 32

Quote from: arulbero on March 13, 2019, 05:13:47 AM

to 2160/m, the probabilty -> probability

the probabilty of finding -> probability

Quote from: Jean_Luc on March 13, 2019, 04:37:59 AM

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/

pairgen as cubitrack are totally different from vanitysearch or vanytigen they have absolutely not the same goal!
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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on March 13, 2019, 07:47:17 AM

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:

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.

arulbero

legendary

Activity: 1948

Merit: 2097

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:

Quote

02000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92

Without sha256 + ripemd160 + base58 encode, I guess I could achieve a very impressive key rate.

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks again for the typo, the automatic corrector doesn't work when editing the README.md Cheesy

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.

arulbero

legendary

Activity: 1948

Merit: 2097

to 2160/m, the probabilty -> probability

the probabilty of finding -> probability

Quote from: Jean_Luc on March 13, 2019, 04:37:59 AM

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/

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks

Hope I will be less disturbed by dreamers !

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on March 13, 2019, 03:30:12 AM

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

propability -> probability

perfrom -> perform

Lotery -> Lottery

precission -> precision

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks

LoyceV

legendary

Activity: 3290

Merit: 16489

Thick-Skinned Gang Leader and Golden Feather 2021

Quote from: Jean_Luc on March 13, 2019, 03:30:12 AM

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

Just typos:

Quote

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

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

arulbero

legendary

Activity: 1948

Merit: 2097

Quote from: Jean_Luc on March 12, 2019, 12:37:29 PM

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

)

LoyceV

legendary

Activity: 3290

Merit: 16489

Thick-Skinned Gang Leader and Golden Feather 2021

Quote from: Jean_Luc on March 12, 2019, 11:41:12 AM

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on March 12, 2019, 12:36:54 PM

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: arulbero on March 12, 2019, 12:19:20 PM

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.

Topic: VanitySearch (Yet another address prefix finder) - page 59. (Read 32966 times)