Bitcoin Forum
January 22, 2020, 09:29:16 AM *
News: Latest Bitcoin Core release: 0.19.0.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 »
  Print  
Author Topic: VanitySearch (Yet another address prefix finder)  (Read 8980 times)
WhyFhy
Full Member
***
Offline Offline

Activity: 532
Merit: 105


View Profile
December 06, 2019, 09:50:51 PM
 #441

Any other ECDSA properties are used?

Endomorphism. It is a elliptic curve property, not a ECDSA property.

If kG = (x,y)  then  (λ*k)G = (β*x, y)  and  (λ*λ*k)G = (β*β*x, y)

where

Code:
λ = 5363ad4c c05c30e0 a5261c02 8812645a 122e22ea 20816678 df02967c 1b23bd72
β = 7ae96a2b 657c0710 6e64479e ac3434e9 9cf04975 12f58995 c1396c28 719501ee

λ*k is mod n,  β*x is mod p

where

Code:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

In this way, you get 6 points with only 1 "operation" kG:

(x,y) (β*x, y)  (β*β*x, y)
(x,p-y) (β*x, p-y)  (β*β*x, p-y)

this explains why 1 of 6 will be valid if split gen right?

1579685356
Hero Member
*
Offline Offline

Posts: 1579685356

View Profile Personal Message (Offline)

Ignore
1579685356
Reply with quote  #2

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

Posts: 1579685356

View Profile Personal Message (Offline)

Ignore
1579685356
Reply with quote  #2

1579685356
Report to moderator
1579685356
Hero Member
*
Offline Offline

Posts: 1579685356

View Profile Personal Message (Offline)

Ignore
1579685356
Reply with quote  #2

1579685356
Report to moderator
arulbero
Legendary
*
Offline Offline

Activity: 1363
Merit: 1468


View Profile
December 07, 2019, 07:57:07 AM
Last edit: December 07, 2019, 11:31:01 AM by arulbero
 #442


this explains why 1 of 6 will be valid if split gen right?


Yes. But this is due only to the way the programs we use to reassemble the pieces for the final private key work.

Let s (Q = sG) be the secret private key (the public key). Only one person knows 's'.

Then he sends only Q to another person, who run a "split gen" program.

Usually "split gen" works like this:

it computes only (s+1)G = Q + G, (s+2)G = Q + 2G, …, (s+k)G = Q + kG = P

until it gets a public key P with a particular address.

The program knows only k (the partial private key).

Then you need to compute k' (k' G = P):

k' = (s + k)  mod n.


Now suppose you get P in this way: - (Q + kG) = P

then in order to get from the partial private key k the correct final private key k' = (-s -k) mod n
you need to know how k was obtained (exploiting the symmetry).


If you get P in this way: λ(Q + kG) = P

(exploiting the endomorphism) the correct final private k' will be: λ*(s + k) mod n   and so on.
MrFreeDragon
Full Member
***
Offline Offline

Activity: 168
Merit: 107


View Profile
December 08, 2019, 02:56:50 PM
Last edit: December 08, 2019, 10:07:13 PM by MrFreeDragon
 #443

Any other ECDSA properties are used?

Endomorphism. It is a elliptic curve property, not a ECDSA property.

If kG = (x,y)  then  (λ*k)G = (β*x, y)  and  (λ*λ*k)G = (β*β*x, y)
-snip-

Thank you! I have looked at the code and also found just these properties:
1) Endomorphism (for λ and λ*λ) -  2 additional addresses for kG
2) Curve symmetry (if (x,y) = k*G, then (x, -y) is -k*G) - 1 additional address

So, it is clear why 6 addresses are found: (1+2) * 2 = 6

Are these properties all known elliptic curve properties, or there are some other known properties but not used in vanitysearch?

I also made some tests with vanitysearch and it is interesting for me why it is faster than bitcrack. For example, for 1 compressed address on GTX 1080ti bitcrack has 340-350MKey/sec, but vanitysearch has 950-1000MKey/sec (3 times more). Was it caused by endomorphism used?
Jean_Luc
Full Member
***
Offline Offline

Activity: 218
Merit: 222


View Profile
December 08, 2019, 07:43:16 PM
Last edit: December 09, 2019, 07:42:27 AM by Jean_Luc
Merited by OgNasty (1)
 #444

Are these properties all known elliptic curve properties, or there are some other known properties but not used in vanitysearch?

Symmetry (x,y) (x,-y) is a common property of all elliptic curve.
Secpk1 admit a primitive cubic root of unity so an endomorphism can be constructed using β and λ (β^3 = 1 mod p and λ^3 = 1 mod n)
If β^3 = 1 and λ^3 = 1 we have also (β^-1)^3 = 1,(λ^-1)^3 = 1 so we can construct a second endomorphism using β^-1 and λ^-1.
Note:  β^3 = 1 mod p =>   β^3.(β^-1) = 1.(β^-1) mod p => β^2 =  β^-1 mod p (same for λ^3 mod n)

Code:
β = 7ae96a2b 657c0710 6e64479e ac3434e9 9cf04975 12f58995 c1396c28 719501ee
λ = 5363ad4c c05c30e0 a5261c02 8812645a 122e22ea 20816678 df02967c 1b23bd72

To find primitive roots of unity you need to factorize p-1 and n-1 and find common prime factors. We have always a primitive square root of unity but it is 1 and it does not bring an improvement, speck1 admit only a cubic primitive root of unity which can be exploited.

Code:
Factorization of p-1 and n-1, only 3 can be exploited.

p-1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2E
2
3
7
3481
1DB8260E5E3B460A46A0088FCCF6A3A5936D75D89A776D4C0DA4F338AAFB

n-1 = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
2^6
3
95
277
17D6CFB8EE30C51
978C6F353C3889A79
10DBFF26EAB8198050172EE03275


I also made some tests with vanitysearch and it is interesting for me why it is faster than bitcrack. For example, for 1 compressed address on GTX 1080ti bitcrack has 340-350MKey/sec, but vanitysearch has 950-1000MKey/sec (3 times more). Was it caused by endomorphism used?

Symmetry and endomorphisms bring significant speedup. I'm not sure, but it seems to me that bitcrak use 32 bits arithmetic which is slower...


Edit: Added factorisation of p-1 and n-1
MrFreeDragon
Full Member
***
Offline Offline

Activity: 168
Merit: 107


View Profile
December 09, 2019, 09:25:59 AM
 #445

Jean_Luc, thank you for the detailed explanation.

Do you know, are there any other elliptic curve properties exist besides symmetry and endomorphism?

Symmetry and endomorphism were used by you in the code to spead up the process. However may be you know some other properties or features which could be used for additional speedup?
Jean_Luc
Full Member
***
Offline Offline

Activity: 218
Merit: 222


View Profile
December 09, 2019, 10:24:26 AM
Merited by MrFreeDragon (1)
 #446

Jean_Luc, thank you for the detailed explanation.

Do you know, are there any other elliptic curve properties exist besides symmetry and endomorphism?

Symmetry and endomorphism were used by you in the code to spead up the process. However may be you know some other properties or features which could be used for additional speedup?

To my knowledge, no other speedup using other ec properties can be added to VanitySearch, but my knowledge is not infinite Wink
In any case the time required for ECC calculation is now low compare to hashing (~80% of CPU usage is taken by SHA256 and RIPEMD160). By using symmetry and endomorphism, we are near of ~1 modular multiplication per point. Even if we double the speed of ECC, it will only result in a ~10% speed increase.
To my point of view, the only significant speedup can be bring by partial reversing of the hashing function in order to reduce hashing time consumption.
blockblock1
Newbie
*
Offline Offline

Activity: 2
Merit: 0


View Profile
December 12, 2019, 01:09:14 PM
Last edit: December 12, 2019, 01:19:32 PM by blockblock1
 #447

How to configure VanitySearch to work with bitfury bf1

https://imgur.com/8bwVYG8
https://imgur.com/iqpi94c
https://imgur.com/226O3t7

GPU: GPU #0 GeForce GTX 770 (8x192 cores) Grid(64x128)
Seed: 1576154843
167.716 MegaKey/sec
ComputeKeys() found 1494 items , CPU check...
GPU/CPU check OK

does not see the device bitfury bf1 ((


I want to set up a mining farm to work with VanitySearch.
USB hub 49 ports.
Dabs
Legendary
*
Offline Offline

Activity: 2576
Merit: 1350


The Concierge of Crypto


View Profile
December 12, 2019, 03:08:31 PM
 #448

I don't think you can get any ASICs meant for mining to work on VanitySearch.

blockblock1
Newbie
*
Offline Offline

Activity: 2
Merit: 0


View Profile
December 12, 2019, 06:42:34 PM
 #449

I don't think you can get any ASICs meant for mining to work on VanitySearch.

why?
Are there alternative programs?
OgNasty
Donator
Legendary
*
Offline Offline

Activity: 3164
Merit: 1758


I 💚 Bitcoin


View Profile
December 12, 2019, 07:11:16 PM
Merited by gmaxwell (1)
 #450

I don't think you can get any ASICs meant for mining to work on VanitySearch.

why?
Are there alternative programs?

None I've ever heard of.  More surprisingly, I'm not even aware of any FPGA vanity searching tools.

imjustagirl
Jr. Member
*
Offline Offline

Activity: 117
Merit: 6


View Profile
December 20, 2019, 01:29:30 PM
Merited by MrFreeDragon (1)
 #451

It would be nice if you could search for not just a specific Vanity address, but also a specific pubkey address.
For example if I wanted to search for an address with a public key that begins with 0400000000 or 02123456  or 03333333 etc.
Is it very hard to implement something like this to the VanitySearch?

1JPnqMd1Q43L3KbZ7SoTSdRCD2aLj2sikF Tip Me!
MrFreeDragon
Full Member
***
Offline Offline

Activity: 168
Merit: 107


View Profile
December 21, 2019, 10:03:57 AM
 #452

It would be nice if you could search for not just a specific Vanity address, but also a specific pubkey address.
For example if I wanted to search for an address with a public key that begins with 0400000000 or 02123456  or 03333333 etc.
Is it very hard to implement something like this to the VanitySearch?

Interesting idea ) Something like vanity public key  Grin
Actually this could be applied to ETH addresses as well (in ETH 256bit public keys are the addresses).

I also suppose that vanity search for BTC public key should be faster (as there is no need to perform RIPEMD 160 and SHA256 hash fuctions)
A-Bolt
Legendary
*
Online Online

Activity: 1480
Merit: 1348

CryptoTalk.Org - Get Paid for every Post!


View Profile
December 22, 2019, 10:31:00 AM
 #453

in ETH 256bit public keys are the addresses

Ethereum address is the lower 20 bytes of the keccack256 hash of the public key.

 
                                . ██████████.
                              .████████████████.
                           .██████████████████████.
                        -█████████████████████████████
                     .██████████████████████████████████.
                  -█████████████████████████████████████████
               -███████████████████████████████████████████████
           .-█████████████████████████████████████████████████████.
        .████████████████████████████████████████████████████████████
       .██████████████████████████████████████████████████████████████.
       .██████████████████████████████████████████████████████████████.
       ..████████████████████████████████████████████████████████████..
       .   .██████████████████████████████████████████████████████.
       .      .████████████████████████████████████████████████.

       .       .██████████████████████████████████████████████
       .    ██████████████████████████████████████████████████████
       .█████████████████████████████████████████████████████████████.
        .███████████████████████████████████████████████████████████
           .█████████████████████████████████████████████████████
              .████████████████████████████████████████████████
                   ████████████████████████████████████████
                      ██████████████████████████████████
                          ██████████████████████████
                             ████████████████████
                               ████████████████
                                   █████████
.YoBit AirDrop $.|.Get 700 YoDollars for Free!.🏆
MrFreeDragon
Full Member
***
Offline Offline

Activity: 168
Merit: 107


View Profile
December 22, 2019, 03:17:58 PM
 #454

in ETH 256bit public keys are the addresses

Ethereum address is the lower 20 bytes of the keccack256 hash of the public key.

Yeah, right. ETH addresses are 160bit (20x8). I made a mistake. Thank you.
zielar
Member
**
Offline Offline

Activity: 142
Merit: 35


View Profile
December 25, 2019, 12:06:04 PM
 #455

Hello,
I have a question to dispel doubts about the diff index in VanitySearch.
Suppose I am looking for the prefix "1RoseCross".
VanitySearch reports difficulty 173346595075428800 for the indicated prefix.

1. Is this value simply speaking - a group that creates 100% addresses where one of them will start with a given search (1RoseCross)?
2. If YES, is "173346595075428800" a decimal value which in hex is "0x0267d9cf4e7e91c0"?
3. If YES, are there any cases or exceptions in which it will be possible not to find the prefix after scanning the range 173346595075428800 despite the fact that VanitySearch has given such difficulty value?

Thank you in advance for your response!
Jean_Luc
Full Member
***
Offline Offline

Activity: 218
Merit: 222


View Profile
December 26, 2019, 10:09:52 AM
 #456

Hi,
The difficulty is the search space size.
A difficulty of 173346595075428800 means that you have a probability of 1/173346595075428800 to find the result after 1 try.
After n tries, you can compute the probability to reach the desired address by using Bernoulli.
P(n) = 1-(1-1/173346595075428800)^n
arulbero
Legendary
*
Offline Offline

Activity: 1363
Merit: 1468


View Profile
December 26, 2019, 11:18:37 AM
Last edit: December 26, 2019, 04:38:25 PM by arulbero
Merited by MrFreeDragon (1)
 #457

Hello,
I have a question to dispel doubts about the diff index in VanitySearch.
Suppose I am looking for the prefix "1RoseCross".
VanitySearch reports difficulty 173346595075428800 for the indicated prefix.

1. Is this value simply speaking - a group that creates 100% addresses where one of them will start with a given search (1RoseCross)?


The difficulty is the search space size.
A difficulty of 173346595075428800 means that you have a probability of 1/173346595075428800 to find the result after 1 try.
After n tries, you can compute the probability to reach the desired address by using Bernoulli.
P(n) = 1-(1-1/173346595075428800)^n


To be more precise:

difficulty = 173346595075428800 means that:
--> there is a correct address each 173346595075428800  addresses
--> you have a probability of 1/173346595075428800 to find the result each 1 try
--> on average it takes 173346595075428800 tries to get 1 match (on average means: if you try many times 173346595075428800 tries), but if you do 173346595075428800 tries only once you will have only a 63% chance to get a match! No 100%!

Any vanitygen-like program computes right the probability to find a match in the particular sequence you are running, it doesn't compute anything "on average".

Search space size is not 173346595075428800, sometimes you have to generate more than 173346595075428800 addresses to get a match.
A group that creates 100% addresses where one of them will start with a given prefix has size 2^160 - 173346595075428800 + 1 (and I'm not considering the fact that there are 2^96 different private keys - means tries - for the same address).

Here more details:
https://bitcointalk.org/index.php?topic=5068417.msg48056010#msg48056010
arulbero
Legendary
*
Offline Offline

Activity: 1363
Merit: 1468


View Profile
December 26, 2019, 11:35:38 AM
 #458

@Jean-Luc

Could you implement the possibility to import a different generator point G as parameter?

To run your program on unsafe machine:

https://bitcointalk.org/index.php?topic=5211545.msg53429180#msg53429180
zielar
Member
**
Offline Offline

Activity: 142
Merit: 35


View Profile
December 26, 2019, 02:42:38 PM
 #459

Hi,
The difficulty is the search space size.
A difficulty of 173346595075428800 means that you have a probability of 1/173346595075428800 to find the result after 1 try.
After n tries, you can compute the probability to reach the desired address by using Bernoulli.
P(n) = 1-(1-1/173346595075428800)^n


I am asking because I have scanned the range of keys being the number given by Diff, but I have not found a solution.

1. What is the remainder of the range that I should scan to find the answer?
2. The fact that I did not find the correct key despite this is not the reason for the error in the code?
arulbero
Legendary
*
Offline Offline

Activity: 1363
Merit: 1468


View Profile
December 26, 2019, 04:33:04 PM
 #460

Hi,
The difficulty is the search space size.
A difficulty of 173346595075428800 means that you have a probability of 1/173346595075428800 to find the result after 1 try.
After n tries, you can compute the probability to reach the desired address by using Bernoulli.
P(n) = 1-(1-1/173346595075428800)^n


I am asking because I have scanned the range of keys being the number given by Diff, but I have not found a solution.

1. What is the remainder of the range that I should scan to find the answer?
2. The fact that I did not find the correct key despite this is not the reason for the error in the code?

I already answered to you: difficulty is not the range you should scan to find the solution at 100% : you have in the above example  

P(173346595075428800) =  1-(1-1/173346595075428800)^173346595075428800 = 0.63 --> 63% ( = 1-1/e),  not 100%!

That means that only 2 times each 3 you will find the solution in a range = difficulty.
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [23] 24 25 26 »
  Print  
 
Jump to:  

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