Topic: Vanitygen: Vanity bitcoin address generator/miner [v0.22] - page 173. (Read 1153620 times)

As far as I can tell, the only thing the transaction script would have to do is convert the actual public key (Pub2) into a Bitcoin address.
The transaction script can do that using OP_HASH160 as far as I can tell.
Assuming the vanity address only needs to match a certain prefix, ie. the start of the address matches "xxx", then a simple binary AND operation should be able to tell if the first x bits in the address matches the pattern that is specified in the original vanity address generation request transaction.
If we want to be able to find vanity addresses that match patterns in any position in the address, it would be a bit more complex, but still doable I think. Matching multiple patterns, or even a Regular Expression is a lot harder, but since using a reg ex slows down oclvanitygen considerably anyway, this probably isn't a going to be fulfilled, unless it's very simple. And if it is very simple, multiple, simpler transactions could be made instead.

Yes the reward that would go to whomever finds the valid address is locked until someone finds it. I haven't been able to find out whether it's possible to create a transaction that "times out" after a certain period, so that the reward is not lost in case no one can or wants to find the vanity pattern specified in the transaction.

Regarding telling people that I have a vanity address that they should search for; the Bitcoin network will propagate the vanity address generation transaction (VAGT from now on) to all nodes (like it will with all other transactions), and a special Bitcoin client will need to be run that can detect these special transactions and present them to a user who wishes to use compute power to try to find vanity addresses in exchange for Bitcoins. This client would leverage the technology of the original Bitcoin client (connecting to peers to get transactions, downloading the block chain etc.) but would only look for VAGTs and present them to the user:
This special client would then run oclvanitygen, oclvanitygen would run until the pattern is found and report the Priv2,Pub2 key-pair to the client, which would then create a transaction in the network that spends the reward by providing the Pub2 that, when converted into a Bitcoin address, matches the pre-defined pattern that was in the VAGT.
A website could easily be made where the back-end is this special client, and any user can go to the website, type in her desired vanity address pattern, deposit x Bitcoins and the website back-end creates the aforementioned transaction on the network and returns the result to the website user, when or if it receives one.

Regarding ByteCoin's proposal: why would we need to coordinate anything? Can't each worker just start at a random point, and the probability that two will work on the same keys will be extremely small?

As soon as someone stops participating, the common public key is recalculated without theirs. To detect this each participant needs to send everyone else some sort of keep-alive signal signed with their private key every minute or so. This is an obvious solution.

ByteCoin

Yeah, that's roughly what I meant, however, when one of the "everyone" is suddenly disconnected, then point 5 can't be done anymore. So, as soon as there's a disconnection, all users need to generate the new common public key. But then you need to detect someone disconnecting, somehow.

Solution:
1) Each party publishes their pattern list.
2) Each party generates a keypair and publishes the public key.
3) Everyone adds all the public key points together to get a common public key.
4) Everone searches from that point in some suitable fashion to avoid duplicating work until one of the patterns is matched.
5) The matching offset and all the other private keys are sent to the lucky "owner" of that pattern.
6) Cross off that pattern and go to 2.

A suitable searching strategy for n people would be as follows:
Agree on a numbering x of participants from 0 to n-1 inclusive.
Agree on a batch size m.
Each participant calculates m affine curve points (x+i*n)G where i runs from 0 to m-1 inclusive.
Each participant adds the common public key to each of the above m points, does a bulk inverse, hashes and checks for pattern matches.
If no match is found then the common public key is incremented by mnG and then the last step is repeated.

ByteCoin

Yup, your edit for the process (between two people) is correct now.

One small addition: An alternative to multiplying the two private keys, you could also make a scheme where you would add the two private keys. In my imagination, adding of bignums is easier than multiplying. In practice, you're using a bignum library (or python) anyway, so it doesn't really matter.

For completeness, here's the script with adding of private keys, instead of multiplying:
So yeah

Anyway
Well, there's the trivial solution of just having N people, and then when person x's address is found, asking the other N-x people for their private keys.* Ideally you don't want to contact the other N-x people at all, but this seems impossible.

Imagine this was possible. Then, when a vanity address was found, I (as a host, or the person searching for addresses) would give all the information I have to the relevant customer. The customer would then calculate the vanity's privkey.
If this is possible, then I (as a malicious host (remember, we want a scheme where no one has to trust me)) can also act as a customer to my own service, I can duplicate the information I send to the vanity customer, send it to myself as a (fake) customer, and also calculate the private address.

The only way this could be made to work, is if somehow the vanityness of the address was involved, meaning the resulting private key could only be calculated by the person who actually submitted the vanity request. I wouldn't quite know how to do this. But then still, I could pretend to submit a shorter vanity address for every vanity address my customers submit.

So I think this scheme is impossible.

*The "trivial solution" is very possible, and may not be a bad idea. It just requires some coordination, and it requires people to leave their tool running. The tool could either be a program that does nothing, except respond to a getPrivateKey request from the rest, every now and then, or it could be an active searcher, helping in the search for the vanity addresses^¶. A proof of work principle could be employed, similar to coin mining°, to give these active searchers a share of the fees for the vanity address.
Ideally this could be done nearly identical to p2pool, but I know nothing of p2pool, so screw that, and just put in a "host", through which all communication is conducted. One problem is offline node detection though: When someone exits their program, everyone needs to start calculating from a new sum-public-point, which does not include that offline node's private key anymore.

°Imagine sending in every time you find an address that starts with 1111111, and its corresponding private key. The host would have to keep a list of seen 1111111 addresses though, to prevent cheating. Not ideal… may require more consideration. Alternatively, just pay the full fee to the person who found the vanity address. This is easier, but makes the payout more lottery-like. When there's lots of vanity requests, this doesn't matter.

^¶If these searchers have no requests, then they don't need to add their public point to the sum-public-point. This helps, because you also don't need to detect it going offline, he can stop whenever he wants.

Final post from me for tonight (promise).  As BTCurious pointed out if I could do what I need to do in order to get my idea for the solution to the "multiple customer problem" to work then I could also simply calculate any private key from the knowledge of the public key (and the base point).  So, I am actually wondering if my idea could in fact be used as the basis for some sort of proof that the "multiple customer problem" cannot be solved.  Well, at least we know for sure it cannot be solved by my approach so I am giving up trying to solve it for now and going to bed.

You are correct in that my post was totally incorrect and that my idea will not work.  But, in my defense, as a side note, point addition and point subtraction are defined for the elliptical curve group.  Unfortunately it turns out that I actually need point multiplication/division to be able to get the idea to work and those operations are not defined.

I made my two posts and then went to play hockey.  We lost in OT (darn).  On the drive home I realized that I had made several very embarrassing basic algebra mistakes.  But hey, it is not very often that I get to dust off my math skills and actually use them – so I am a bit rusty.  I am fixing the mistakes I know of in my two previous posts.

This is impossible. The public keys aren't neatly ordered in line, so you can't calculate the private key difference between any two public keys. The problem is that it's impossible to know anything about the private key, given that there's only the public key…

Edit: If this was possible, I would just generate a private P_M, get the public key M, and then get person 1's private key by calculating P_M - m1 = P1

I have also updated this post and fixed all the glaring/embarrassing mistakes I made.  Please let me know if you see any others.  Keeping in mind this is all finite field mathematics on an elliptical curve - which is "hard” - I think the algebra is pretty simple and may now even be correct.  Also note that this idea will not work (even with the stupid mistakes corrected).  I decided to leave it here instead of just deleting it because possibly kicking around this idea with everyone here may lead to an actual solution.

The "vanity address miners" get multiple customer requests which are a public key and a list of desired patterns:

Customer 0:  P0, pattern list 0
Customer 1:  P1, pattern list 1
Customer 2:  P2, pattern list 2
etc.

Then the miners each generate their own random public key, let’s call it M.

Then for each public key in the customer list calculate the following.  [This is where the idea breaks down because upon further more careful reading of the specification I found that even though the EC system used is based on a prime finite field the points on the elliptical curve form a group, not a field.  This means that multiplication (and division) of points on the curve is not defined – which is what I really needed to get the idea to work.]

m0 = M / P0
m1 = M / P1
m2 = M / P2
etc.

Then run ALL the customer requests at the same time from the starting public key point M. If one of the vanity patterns matches, let's assume it was one of the patterns from customer 1, then transmit the public key t times m1 [mini proof: V = tM, M = (m1)P1, V = t(m1)P1] back to customer 1.  Customer 1 can then calculate the vanity private key from their private key p1 as v1 = p1 times t times m1 and the vanity public key is V1 = (p1)t(m1)G

So, I did not solve the problem but I did make a stab at it

Burt Wagner (donations for trying to 1BurtWEejbnKeBRsvcydJvsNztB1bXV5iQ)

I have updated this post and fixed all the glaring/embarrassing mistakes I made.  Please let me know if you see any others.  Keeping in mind this is all finite field mathematics on an elliptical curve - which is "hard” - I think the algebra is pretty simple and may now even be correct:

Using G as the base point on the curve and p as the private key then the public key P is defined as simply P = pG.  Therefore, the algorithm is as simple as BTCurious says:

Person 1 hands out a public key and a vanity request (or list of vanity requests) to the "vanity address miners"

The vanity address miners do the following:

1) Generate a random test private key from the finite field, let’s call it t.
2) Calculate the corresponding public key but instead of calculating it from the base point G calculate it from Person 1's public key, simple:  T = tP
3) Hash and check the generated public key T against the vanity criteria, if it does not match any of them then go to step 1) if it matches one then continue to step 4)
4) Transmit the private key found (t) back to person 1 [t could be easily encrypted using P]
5) Person 1 can then calculate the vanity private key from the private key sent by the miner (t) and the private key they originally generated (p) as follows:  P = pG, V = tP so V = t(pG) and V = (tp)G so the vanity private key is t times p.
6) Then the corresponding key V = (tp)G = vG is the vanity public key!
7) Person 1 can simply hash and double check the public key found (V) and then pay person 2 for their help.

This is VERY COOL, very simple and will work as far as I can tell.

Nope, it's a bit different.

An EC private key is any random integer smaller than the field size*. This can be used to calculate a public key, which is a point in the field (2 coordinates). The reverse calculation, finding the private key given the point in the field, is unfeasible, just like factoring pq into p and q in SSL is unfeasible. This is what makes both SSL and EC secure.

*If you add your random integer to the other person's, you can just do mod fieldsize, and get an integer anyway.

I don't know the exact details of the encryption and signing. I just know you need the private key for that.

Anyway, if I were to define the keys in parameters, it would be significantly simpler than in SSL:

(F = the field, with predefined parameters. Basically you can do the same thing on different fields, but all of bitcoin uses secp256k1, so we don't need to communicate these parameters to peers at all.)
p = any random number, smaller than Fp (Fp = the field size, basically the amount of distinct private keys that exist)
[x,y] = a coordinate in the field, which can be calculated from p. (There exist Fp [x,y] pairs, so every private key corresponds to exactly one unique [x,y] pair, I believe.)

p is the private key
[x,y] is the public key.

If you want to learn more about it: I learned most from this paper: http://www.secg.org/collateral/sec1_final.pdf
It's actually very readable, just make sure you ignore the stuff that's not relevant to you. The bitcoin curve used is a prime finite field (Fp), not a characteristic 2 finite field (F2m), so just ignore paragraphs about F2m.
The specific parameters on secp256k1 can be found in: http://www.secg.org/collateral/sec2_final.pdf

And a site that helps with visualisation is http://www.certicom.com/index.php/ecc-tutorial
They have some interactive applets, 's nice

My first assumption is that Bitcoin uses the standard public/private key infrastructure (PKI) - the same one used for SSL - because that is what I am familiar with.  However, since I have never actually read up on it this is just an assumption on my part.  Given that Bitcoin uses the same public/private keypair infrastructure as SSL then the paramters are all defined as follows:

p  = first very large random prime number
q  = second very large random prime number
n  = pq (also a very large number)
m = lcm {p−1, q−1} (lcm is the least common multiple)
r  = is a selected coprime with m (r>1 and r and m have no factors in common), most commonly set to 0x10001 = 65537
s  = the unique s such that rs ≡ 1 (mod m)

The public key is made up of n and r

The private key is made up of n, r, p, q and s (m and n can be calculated from p and q - see above, and all you really need is n and s to decrypt - see below)

Encryption of message M is defined as Encrypt(M) = Mc = (M ^ r) (mod n)

Decryption of the encrypted message Mc is defined as Decrypt(Mc) = M = (Mc ^ s) (mod n)

I thought this was pretty standard terminology but I found that http://en.wikipedia.org/wiki/RSA_(algorithm) has it slightly different:

p, q, n are the same.  They have φ(n) where I have m, e where I have r, and d where I have s.

Interesting idea! I'm not sure if the transaction script is powerful enough to do this; it would have to be able to do conversions from private to public key, and (bit)string editing and matching and such. Apart from that, the funding would be locked until something is found. And you would still have to somehow tell people that you've got an open request. If a site is made that could search for multiple people at the same time, it should be no problem to make an address request and only actually pay upon delivery. I'll ask some people working on multiple key signing if it may be possible.

Regarding the wish to be able to do distributed vanity address generation, the thought came to me that this might already be possible, if your method, BTCurious, of securely generating another person's private key is functional.

Now I'm no expert on the Bitcoin script format used in transactions, so I can only say it seems to me that this is possible in theory. Someone with more knowledge in this area will be able to confirm or deny whether this is actually possible.

Say I want a fresh, new-and-shiny vanity address and I am willing to pay for it. I create a custom transaction that contains Pub1 (using the terminology in BTCurious's post) and the desired vanity pattern, and broadcast it to the network. To redeem this transaction, someone must provide a Priv2 and Pub2 where the left-most x bits (determined from the desired vanity pattern specified in the transaction) in the hash of Pub2 matches the vanity-pattern specified in the transaction.
If the prize for successfully finding a Pub2 and Priv2 that allows the transaction-creator to get his desired vanity address is big enough (probably meaning that the prize is greater than if someone had spent the time mining instead), someone will go for it, eventually find this key pair and broadcast a transaction containing them to the network, thus spending the prize included in the initial transaction, and making public the Priv2 key so the transaction-generator can get his much-wanted pretty address.
The user desiring a vanity address might include a time-out on his vanity address generation request (not sure if this is possible either), such that if no one successfully spends the transaction in y days, the transaction becomes invalid and the Bitcoins are not lost.

Hmm, I'm on my phone right now, so I can't really check what your variables meant exactly. I'll however explain it in the terms I usually reason in, maybe that will help.

Bitcoin uses a field with some standard, predefined settings. A point in this field is given by two coordinates. A public key is actually just 0x04, and then the two coordinates. You can generate a random point in this field by taking a random number R (smaller than the field size), and adding the field source point to itself R times. The source point (or zero point or something, I'm not sure) is one of the predefined field settings. The random number R is more commonly known as the private key.

So we have a random int as a private key, and this gives a point in the field as a public key.
Now, Person 1 creates Priv1, and subsequently Pub1, and gives Pub1 to Person 2. Person 2 generates a random Priv2, and adds the source point Priv2 times to Pub1. This creates a new point in the field, which is actually the public key associated with the random number (Priv1+Priv2). So that would make it Pub(1+2).

Now, Person 2 can find the address for Pub12, but he'll never be able to claim any bitcoins on the address, because he'd have to sign his transactions with Priv(1+2), but he doesn't have Priv1.


Anyway, the loop here starts after Person 1 sends Pub1 to Person 2. Person 2 can keep generating a new Priv2 to check for niceness, and only has to report back to Person 1 after he has actually found a nice address.

Now, I haven't found a way to generate addresses for a lot of people at the same time though, since everyone gives you a different public key. But it might be possible. The problems involved sound a bit like multiple key authentication, which is being worked on right now. But yeah, for now at least, having one person generating a vanity address for someone else securely is not impossible.

I am no expert but I have done a fair amount of work creating and debugging standard PKI code.  I am very curious about your post and need a bit more help in understanding it.  Given a bit more understanding I think I could write the code and then maybe we could eventually get it included into the vanitygen project.


Person1 creates the Pub1(n1, r1) Priv1(n1, r1, p1, q1, s1) keypair.


I assume this it the search loop of the program:
1) Create a new keypair PubN(nN, rN) PrivN(nN, rN, pN, qN, sN) [I assume we can make rN=r1, are there any other restrictions to this keypair generation?]
2) Create the public key to test PubT where PubT is a function of Pub1 and the new keypair:  PubT(nT, rT) = F1(n1, r1, nN, rN, pN, qN, sN)
3) Hash and test PubT for the vanity criteria, if it does not match then go to step 1), if it does match then continue


Assuming PubT matches the vanity criteria then send the keypair PubN(nN, rN) PrivN(nN, rN, pN, qN, sN) from Person2 to Person1 [this could be encrypted using Pub1]


PrivNice(nNice, rNice, pNice, qNice, sNice) = F2(n1, r1, p1, q1, s1, nN, rN, pN, qN, sN)

So my question is can you give me the details for the two functions:

PubT(nT, rT) = F1(n1, r1, nN, rN, pN, qN, sN) and
PrivNice(nNice, rNice, pNice, qNice, sNice) = F2(n1, r1, p1, q1, s1, nN, rN, pN, qN, sN)

or point me to a site or paper that can give me these details?

^ Cool! I'm glad you proved me wrong . I don't know anything about EC cryptography but I'll take your word for it.
It means that we could begin building websites where users can buy vanity addresses securely for Bitcoins.

Wrong.

(The explanation assumes you know something about EC cryptography)
Person 1 makes a private key Priv1, and calculates the public key Pub1. Person 2 gets Pub1, creates a new private key Priv2, and adds (EC source point) * Priv2 to it, creating Pub2. Now, if Pub2 hashes to a nice vanity address Vnice, then Person 2 sends Priv2 to Person 1. Person 1 then adds Priv1 to Priv2, getting Privnice.

This is a way for Person 2 to help generating an address for Person 1. At the same time, Person 2 can search for his own stuff, and if he finds one of his own vanity targets first, he will instead request Priv1 from Person 1. Now Person 1 doesn't know Privnice. For further search, both Persons generate a new random private key, and they start over.

^ Me neither. Unless we invent a homomorphic encryption scheme to accompany this distributed vanity address generator. But maybe that'd be just a liiitle too much work for cool Bitcoin addresses .