You are going to send 500 personal messages with entry numbers and you are not going to charge anything for your time?  That sounds like is a lot of work.
 
http://bitlotto.com  has a fully automated, totally transparent lottery system in place.  The winning ticket is picked automatically from all the entries using the transaction id for the entry ticket number.  The winning ticket number is based on the winning numbers from a public lottery so it is fair and easy to verify that the choice was random and the correct person gets paid.  Also all ticket entries are public and the number of entries sold is publicly available in the block explorer.

If you are going to start a lottery system you should really check it out

Not 100% sure on this because I have not tried it yet but can't you just create a single transaction to move the BTC from the coin/bar into any public address of your choice using the on line transaction creator here:  https://bitcointalk.org/index.php?topic=51254.0

Is that what you are looking for?

Since nodes will come and go, workload lists will vary from node to node, and workload subnets will develop I think we need to add the following to the claim message:

Let's assume a node finds the desired public key and it broadcasts a message "I found public key 1xxxx... and I am claiming the prize".  In this message it includes the following:

• Its own private key (maybe encrypted by the requestor's public key - see below).
• The private key that found the desired public key (maybe/maybe not encrypted to the requestor's public key).
• Its new public key to be used for subsequent searching.
• The payment address for the claim.
• The list of all public keys used to make the desired vanity key.
• The entire message signed by the sending node

I forgot to include the signature in my last post.  So if we sign using the OLD private key then we must encypt the private key in the message because it is the key used to sign the message.  If we sign with the NEW private key then I guess the private key in the message can be clear text.  Still thinking on that one.

Then only the nodes on the list need respond with the private key/new public key messages.  And the same thing goes for these messages the private key can be clear if it is not the key used to sign the messages.

I have redeemed several coins on Mt. Gox.  After I enter a private key there it moves the BTC from the coin into my Mt. Gox account.   Then since it is in sweep mode if anyone were to (foolishly) put any BTC on that same keypair anytime in the future the BTC get automatically swept into my Mt. Gox account.  I guess I do not understand the trust issue you are talking about (above and beyond the obvious trust we place in Mike when he makes the coins).  Since the account associated with the coin is now drained there is really no reason to ever use it again.  So the service has no way of getting any future coins from it - unless you use it again.

O, I see now, you are talking about a "fly by night" operation that builds trust in the community and then at some point runs away with some coins.  Well that is what "fly by night" operations do.

I just wanted to describe my current understanding of the basic claim algorithm here to make sure I am on the same page:

At the time a desired public key is found the node that has just found the desired public key has two pieces to the puzzle: the very "last" piece and their own private key that corresponds to their published key.

Every other node has one additional piece of the puzzle and the requestor has the "first" piece of the puzzle.

Every node has the public keys from every other node and the private key corresponding to their published key.

So the problem is to collect all the pieces together to complete the puzzle.  It makes sense to me to have all the nodes send their pieces to the requesting node.

Let's assume a node finds the desired public key and it broadcasts a message "I found public key 1xxxx... and I am claiming the prize".  In this message it includes the following:

• Its own private key, encrypted by the requestor's public key.
• The private key that found the desired public key, encrypted to the requestor's public key.
• Its new public key to be used for subsequent searching.
• The payment address for the claim.

Every node can then encrypt their current private key with the requestors public key, create a new public key and broadcast a message containing the encrypted private key and the new public key out to the network.

Every node then accepts the new public keys from everyone else, calculates the new starting point, and begins searching for the remaining patterns.

Meanwhile the requestor can assemble all the keys together, verify the claim and then pay the finder.

Is that close to what we are talking about?

Yes, I realized that after I published the post.  At any rate this is much easier "now days" since you can import mini private keys directly into a Mt. Gox or StrongCoin account.
Question:  besides Mt. Gox and StrongCoin does anyone know of any other places that accept the mini private key format for import?

First, I like the "adding keys" solution better than my "muliplying keys" solution so I suggest we go that route.

It seems to me there is a workable solution here all we need to do is solve a few logistical issues!  Fun.  Going off line is kind of a nasty issue in that from the time one participant goes off line to the time this is detected and the common starting point is recalculated the efforts of the entire network of participants is wasted.  I think there are two separate "going off line" use cases.

1) a participant decides to shut down for whatever reason - in this case an "I am going to stop participating" message could be broadcast.
2) a participant goes offline without a message (power failure, etc.) - in this case we want a mechanism to detect this as soon as possible and get back on track

In a peer-to-peer implementation could't we have each node monitor just it's connected nodes and then broadcast a "node X went offline" to the entire network as soon as it detects one of it's peers has gone offline?

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.

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.

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.

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?

I also have noticed that the balance in not correct.  It is way too high.  I have not downloaded the very latest so I am hoping the issue may be fixed when I download the pending version.

I was quite sad when I found out that http://firstbits.com/1bitcoin had been wasted on a dead end account.  I have created quite a few vanity addresses and I think my favorite so far is http://firstbits.com/1zaphod  Also, and this might date me, I own http://firstbits.com/1xyzzy (the magic word in one of the first computer games called Adventure)

Sounds great and given the high quality of all your other products I am sure they will be beautiful.  I will buy some for sure.

TyGrrTech is pretty long, but other, shorter versions (for example http://firstbits.com/1TGTech) are still available.

This whole idea of finding accounts for others would be pretty cool except for one thing:  security of the private key.

For example if I did find 1TyGrrTech (or more likely 1TGTech) I would now know the private key.  If I give/sell the keypair to you then there is really no way you can be sure I don't keep a copy of it so I can go in and steal all your coins once I see you have a bunch on the account.

The best option I can think of is that if you were to get/buy one of these keys where you are unsure of the security of the private key then import the private key into Mt. Gox and set it to immediately sweep any coins sent to the account off the account into another account.

Even doing that you still would have to "race" with anyone else who had the same private key and see who could sweep the coins out first.

You can buy physical Bitcoins with Paypal and have them shipped to you here http://www.memorydealers.com

Currently 1 BTC coins are $5.86 each, 25 BTC coins are $96 and 100 BTC bars are $353.39

Don't know if that help you since I do not know what you are going to do with your 20 BTC.  If you are planning on keeping them "forever" this is a pretty good way to do it.

My fiinal post on this point, I hope I am being helpful and educational here - that is my intent.

Just as an example the 0.10 BTC you sent to me can be seen here:

http://blockexplorer.com/address/1Kuktw1ebnL3ySLx3AJK5kEA3xbkibH535

Notice they were sent from and address you probably didn't even know you had