Vanity address mining - How to pool work?

[fizzisist]

I've been working on a project to create a vanity address mining pool, mostly as a side project to gain some experience developing a web app, but also because I felt the need to improve on vanitypool.appspot.com.

It is currently close to being ready to announce, but only as a simple "market place" for vanity address generation. That is, the concept of pooled work is not really implemented (it's not implemented in vanitypool, either).

I'm hoping to tap on the bitcointalk hive-mind to come up with good ideas for how to create proof-of-work and reward miners for partial matches. At this point, I don't see how to do this in a fair and reasonable way.

My first idea is to allow miners to submit partial matches, and those serve as a proof-of-work. After the vanity address is found (full match), the miners that submitted partial matches should receive some percentage of the total bounty. But, how to divide it up?

Bonus points for ideas that minimize risk for the pool operator, protect against miners from withholding full matches, and are simple to implement without user registration.

Thanks in advance for any input!

[fpgaminer]

Buyer (person who wants the vanity address generated) submits the following information to the pool:  prefix, Q_b, bounty
Where Q_b is the Base Public Key.

Miners request work from the pool.  The pool returns: prefix, Q_b'
Where:

Code:

r = random 256-bit integer
Q_b' = Q_b + r * G
if Q_b' is infinity, select a new r and repeat

Miners can now do the usual vanity mining. i.e.

Code:

public_key = Q_b'
for i in range (forever):
    public_key += 1
    hash = hash (public_key)
    if hash is partial or full match:
        submit i to pool (along with some job identifier)

Miners should return partial or full matches, returning only the offset from the Q_b' that they found.  Miners should listen to the pool, in case the job they are working on expires (someone else found a full match).

When a full match is found, the pool can payout using any of the existing reward schemes (proportional, PPS, DGM, etc).  The pool can then return the winning offset and r to the Buyer.  The buyer can use these to reconstruct the final private key:

Code:

private_key = base_private_key + r + i

Having the pool give out Q_b' instead of Q_b allows the miners to all work on "unique" jobs.  The pool can easily verify that any offsets returned by the miners are real (by adding and hashing them), and are not duplicates.  I can't think of any way for a miner to fake results, so each share returned is a proof-of-work.

As for preventing withholding, I'm not sure if this is solvable, or if it's already solved in some existing payout scheme.  Regardless, it's the same problem any other mining pool would face, so there should be plenty of existing literature on it.

The only real caveat here is that Buyers would need to give the bounty to the pool when they submit the job.  If the Buyer were to hold on to the bounty until the full match was found, it would be possible for a Buyer to back out of the deal and stiff all of the miners.  So the pool needs to hold on to the Bounty until a solution is found ... which may be never! (Buyer beware)

NOTE: This is all off the top of my head.  I didn't spent any significant time checking this system for vulnerabilities.
NOTE2: The pool will need to be a mighty bit beefier than a Bitcoin mining pool, since ECDSA is a more expensive algorithm.

[Kontakt]

I believe a pool should hook all of the already available boards; vanitypool.appspot and all the spinoffs.

As for preventing withholding and  proof of work, I've been working on learning the base of the algorithm for generating addresses. I've actually written a program over the last 2 days that converts a public key to a 25 bit standard key. Nothing new or special, just a research project.

I need to examine the double key method for the split key mining to see if this is feasible, but if a third key were added to the mix with the private key being held by the pool, you could ensure generated addresses were presented to the pool.

Since mining for addresses only requires SHA256 of RIPEMD-160 of <public key>, you can just make proof of work compatible hashes with a set amount of prefix zeroes, just as the bitcoin miners use.

As for the payment up front, I believe the best solution is to have a timeframe element associated with the job request. You pay a flat registration fee and place the bounty as a deposit. If the address is not found within the specified timeframe, the bounty deposit is returned to your account. The fee can be kept by the operator or shared among the miners. Or a little of both.

[fizzisist]

Thanks, fpgaminer, for the great ideas! Generating a Q_b' is certainly an interesting idea, and yes, it does seem like I can simply use one of the already established methods for dividing up the bounty. An important point, though, we need to remember that miners can search for all the patterns simultaneously that belong to the same base public key. Just means passing a list of patterns back to the miner, though, and checking the returned Q_b' and offset against the entire list when they submit.

As for the bounty issue, my site allows submitters to click a "cancel bounty" button to have the bounty they submitted returned back to the address they sent from. This button is only accessible from a special link they receive after submitting the work, so anyone can't just go in and click cancel and wreak havoc.

To kontakt, yes, I have considered proxying work from other pools to allow miners to work on the best available work on any website at once. The drawback to this idea is that it requires a level of trust from the miner with my pool, because I could simply replace the payout address in the "solved work" with my own before sending the solution to the "proxied" pool, effectively stealing the bounty. Of course I wouldn't do this, but in cases of problems with the proxied pool, the miners would come knocking on my door. Not sure if it's worth the trouble to open that can of worms.

That said, replacing the payout address with my own could be the way to proxy the work AND turn it into an actual pooled implementation. That is, I want the entire bounty to be sent to my pool, then I will send out proportional bounty fractions to the miners that submitted proof-of-work. In that case, though, I would be left out in the cold if someone found the solution and submitted it directly to the proxied pool bypassing me. The Q_b' idea mostly avoids this, so still something to consider.

Thanks to both of you!

[gmaxwell]

Just a minor plea: Please don't build more address generators that don't use compressed keys.  Compressed keys are faster to generate and uncompressed ones bloat the network.

[Blowfeld]

... As for the bounty issue, my site allows submitters to click a "cancel bounty" button to have the bounty they submitted returned back to the address they sent from. This button is only accessible from a special link they receive after submitting the work, so anyone can't just go in and click cancel and wreak havoc. ...

A client asks for an 8-character vanity address, knowing the cost is too high.  After one (or more) 7-character partial matches have been found, the client cancels their request.  Now what?

Maybe the client wanted a 7-character address in the first place.  Depending what information is public, the client may have their 7-character address for free, and neither you nor the miners get anything.

Maybe the client wanted a 7-character address in the first place.  Even if partial matches are secret, a miner who found a 7-character partial match may negotiate with the original client for the 7-character match.  Neither you nor the other miners get anything.

I would suggest that a refund should deduct *something* related to the value of work done so far.  The deduction to be paid to the miners for work already performed.

If you choose a sophisticated pool payout method, like those used by some Bitcoin mining pools, where payouts may carry over from one block to the next, then the algorithms must be adapted (significantly) for this project.  Unlike Bitcoin mining, where every block reward is the same and difficulty changes modestly every couple of weeks, each and every Vanity job payout is different and the difficulty may vary by orders of magnitude from one job to the next.  Further complication is that two (or more) Vanity jobs may be in progress at the same time.

You may have to develop your own payout scheme that will lure vanity miners whether a job is new or old, even if "luck" (as used by some Bitcoin mining pools) is bad.  The fluctuations you can withstand (PPS) and fees you charge will have a big say in choosing payout schemes that are mutually beneficial to both you and the miners.

Also, I don't see any need for the server to generate the random starting point in the ECDSA keyspace.  The mining client chooses their own starting point, and the probability of overlap (with a fair client) is negligible.  To avoid cheating, you should keep the partial matches and don't award credit for duplicate matches.

It sounds like an interesting project!

[fizzisist]

Just a minor plea: Please don't build more address generators that don't use compressed keys.  Compressed keys are faster to generate and uncompressed ones bloat the network.

I will happily use compressed keys, but hopefully someone else will help with implementing this in vanitygen. I think someone already did, actually, just not in the main repo. Obviously, it will also need changes in the pool protocol and partial match handling, so that's a bit of work as it is. Samr7 has been afk for a few months, so hopefully he pops up again and can at least provide some advice as I make these changes.

[fizzisist]

... As for the bounty issue, my site allows submitters to click a "cancel bounty" button to have the bounty they submitted returned back to the address they sent from. This button is only accessible from a special link they receive after submitting the work, so anyone can't just go in and click cancel and wreak havoc. ...

A client asks for an 8-character vanity address, knowing the cost is too high.  After one (or more) 7-character partial matches have been found, the client cancels their request.  Now what?

Maybe the client wanted a 7-character address in the first place.  Depending what information is public, the client may have their 7-character address for free, and neither you nor the miners get anything.

Maybe the client wanted a 7-character address in the first place.  Even if partial matches are secret, a miner who found a 7-character partial match may negotiate with the original client for the 7-character match.  Neither you nor the other miners get anything.

I would suggest that a refund should deduct *something* related to the value of work done so far.  The deduction to be paid to the miners for work already performed.

If you choose a sophisticated pool payout method, like those used by some Bitcoin mining pools, where payouts may carry over from one block to the next, then the algorithms must be adapted (significantly) for this project.  Unlike Bitcoin mining, where every block reward is the same and difficulty changes modestly every couple of weeks, each and every Vanity job payout is different and the difficulty may vary by orders of magnitude from one job to the next.  Further complication is that two (or more) Vanity jobs may be in progress at the same time.

You may have to develop your own payout scheme that will lure vanity miners whether a job is new or old, even if "luck" (as used by some Bitcoin mining pools) is bad.  The fluctuations you can withstand (PPS) and fees you charge will have a big say in choosing payout schemes that are mutually beneficial to both you and the miners.

Also, I don't see any need for the server to generate the random starting point in the ECDSA keyspace.  The mining client chooses their own starting point, and the probability of overlap (with a fair client) is negligible.  To avoid cheating, you should keep the partial matches and don't award credit for duplicate matches.

It sounds like an interesting project!

Very good points about the refunding. Duly noted. And definitely crucial to check for duplicates! I hadn't actually thought of that yet...

The point about requestors going straight to the miners to receive a partial match is avoided with fpgaminer's idea to add a second key to the original one, as long as those keys is kept secret from the other parties. Not totally sure if that's possible, though.

As I see it, PPS makes the most sense because old, unlucky work will essentially be getting less and less valuable to work on as partial matches rack up. This will turn into "pattern hopping," although I think I could partially avoid that server side (not allow miners to submit matches for just any pattern...). That doesn't really jive with my idea of this as a free market place though. The point is that requestors can set any price they want, and miners only have to work on it if they think the reward/difficulty is high enough.

With PPS, we can have the requestor lose N*PPS if they cancel after N shares have been submitted.

Thanks for the ideas!

[Remember remember the 5th of November]

Since vanity pools work by either adding or multiplying two public keys, the person who wants an address will submit some random public key of his to the website and his desired pattern. Then you send this public key and the miners will generate other random public/private keypairs and multiply/add the two public keys to see if it creates an address that matches the desired one.

No doubt during this process there will be partial matches like:
1MyADDY
1MyAdDy
1myaddy

This will be your proof-of-work. And all will be valid, because there is no way to cheat here when you add the two public keys.

[Blowfeld]

... As I see it, PPS makes the most sense because old, unlucky work will essentially be getting less and less valuable to work on as partial matches rack up. This will turn into "pattern hopping," although I think I could partially avoid that server side (not allow miners to submit matches for just any pattern...). That doesn't really jive with my idea of this as a free market place though. The point is that requestors can set any price they want, and miners only have to work on it if they think the reward/difficulty is high enough.

With PPS, we can have the requestor lose N*PPS if they cancel after N shares have been submitted. ...

With the existing vanity pool, neither the customer nor the pool operator bear much risk.  The risk belongs to the vanity pool miners who may toil for no reward or who may get a lucky break and a big reward.  The goal of your project, as I understand it, is to reduce the risk to the vanity pool miners.  You've done enough math on the forums and on your own Web Site I'm sure you understand the risks that a Poison Distribution brings to a PPS pool operator.  If you can handle the risks, I agree that PPS does make the most sense.

Another option is to shift the risk to the customer requesting the vanity address.  When the customer's funding is exhausted, miners won't work on the customer's vanity address until more funding arrives.  If a miner finds the solution early, you would refund the unused funding to the customer.  Other variants might be to allow your customer to specify both the total funding and a fixed PPS or to specify total funding and PPS as a fraction of remaining funding.

I hope you *do* allow pattern-hopping.  My version of the vanity mining client is customized in several ways.  One customization is that I will not submit work that I consider to be too cheap.  Even if one customer with a common public partial key has a collection of work that can be performed simultaneously, if the value of certain vanity addresses within the collection is *too* cheap, I won't submit those.  (I'd rather pour out my milk than sell it at a price that's too low.)  In turn, I evaluate the value of the collection of work differently than the standard miner evaluates the collection of work.  Thus, my preferred pattern is often not the same as the standard miner's preferred pattern.

If you implement PPS and pay as shares are discovered, you could probably implement your project with no changes to the existing vanity mining protocol.  Just make sure your site offers shares (5- or 6-character shares, perhaps) to any oclvanityminer who comes knocking.  For transparency, your Web Site should show the true (7- or 8-character) vanity address being requested along with total funding, and PPS formula.  But the mining client only *needs* to know what it will be paid for.

[Kontakt]

PPS sounds fine to me, as well, since this is a work-until-found job rather than a competitive time sensitive problem. Honestly, a proportional payout would put less risk on the pool, but would be prone to hoppers mining for the first little while on an address.

You can ensure that work is delivered to the pool if found by running a second mod add or multiply on the public key before passing it to the miners. This makes the private key found useless unless first doctored by the pool server.

Using the same second hash for every identical public hash submitted would allow for parallel mining of any addresses submitted by the same person.

Instead of feeding the private key generator random data, you could pass it a incrementing position along the sequence of possible inputs. This would allow you to space miners apart to prevent any possible overlap in mining. Having the client return a current point every time it checks for updated work would allow a database of all searched values. This would aid in calculating odds of finding and general statistic keeping.

I've been dissecting vanitygen over the last week to understand it. I believe most of these things can be added without much trouble.

[fizzisist]

Thanks for everyone's thoughts on this. I really appreciate your help! It looks to me like PPS is the way to go, and I'm starting to figure out how to implement it. It will take some time.

If anyone's curious, the alpha version of the site is up. This is without PPS, so it's not too exciting for now. I'd appreciate any feedback, though. Thanks!

http://vanityamp.com

[Kontakt]

I mined on it for a short bit the last few minutes, and it received the work alright.

Were you planning on pulling work from the other pools?

[fizzisist]

I mined on it for a short bit the last few minutes, and it received the work alright.

Were you planning on pulling work from the other pools?

Thanks for testing!

I worry that proxying work from other pools could potentially get me in trouble. If the work is proxied, I will be receiving the full solution and, in theory, could swap the payout address for my own. The reason I worry about this is that the other pool operator could essentially frame me by doing this themselves if they see the solution came from my end. I would have no way to prove to the miner that I didn't do this. If there was some way to protect from this, I'd gladly do it but I don't see a solution at this point.

Anyway, the real goal is to get PPS working so that this is the first truly pooled vanity address site. Another thing on my wishlist is some client side javascript for the user to generate ECDSA keypairs and combine private key solutions.

I'm hoping to get all that worked out in the next few weeks. If anyone would like to contribute to the javascript part, I'd love to work out a partnership!

[Kontakt]

I mined on it for a short bit the last few minutes, and it received the work alright.

Were you planning on pulling work from the other pools?

Thanks for testing!

I worry that proxying work from other pools could potentially get me in trouble. If the work is proxied, I will be receiving the full solution and, in theory, could swap the payout address for my own. The reason I worry about this is that the other pool operator could essentially frame me by doing this themselves if they see the solution came from my end. I would have no way to prove to the miner that I didn't do this. If there was some way to protect from this, I'd gladly do it but I don't see a solution at this point.

Anyway, the real goal is to get PPS working so that this is the first truly pooled vanity address site. Another thing on my wishlist is some client side javascript for the user to generate ECDSA keypairs and combine private key solutions.

I'm hoping to get all that worked out in the next few weeks. If anyone would like to contribute to the javascript part, I'd love to work out a partnership!

You would have to swap the payout address for your own, to distribute the PPS. Basically, your site would submit a getwork to the workboard, take those results and perform the modular multiplication on the provided Public addresses. Your miners see the work in their pull and get the tier 2 public key. Then, when they get a result, they send it to you. You recombine the tier 2 private key with the submitted key, verify the work, and pass that public/private key back to the original board with your address. That address gets payment, 0.5% is shunted out for the server and the rest distributed by the share scheme. Just post solved work on the site and be transparent. Easy as pie.

[fizzisist]

I mined on it for a short bit the last few minutes, and it received the work alright.

Were you planning on pulling work from the other pools?

Thanks for testing!

I worry that proxying work from other pools could potentially get me in trouble. If the work is proxied, I will be receiving the full solution and, in theory, could swap the payout address for my own. The reason I worry about this is that the other pool operator could essentially frame me by doing this themselves if they see the solution came from my end. I would have no way to prove to the miner that I didn't do this. If there was some way to protect from this, I'd gladly do it but I don't see a solution at this point.

Anyway, the real goal is to get PPS working so that this is the first truly pooled vanity address site. Another thing on my wishlist is some client side javascript for the user to generate ECDSA keypairs and combine private key solutions.

I'm hoping to get all that worked out in the next few weeks. If anyone would like to contribute to the javascript part, I'd love to work out a partnership!

You would have to swap the payout address for your own, to distribute the PPS. Basically, your site would submit a getwork to the workboard, take those results and perform the modular multiplication on the provided Public addresses. Your miners see the work in their pull and get the tier 2 public key. Then, when they get a result, they send it to you. You recombine the tier 2 private key with the submitted key, verify the work, and pass that public/private key back to the original board with your address. That address gets payment, 0.5% is shunted out for the server and the rest distributed by the share scheme. Just post solved work on the site and be transparent. Easy as pie.

Ah, you're talking about proxying the work and turning it into PPS. This is an interesting idea, but would be extremely risky for me. I would have to pay for each share submitted, but could potentially never get paid myself. I could remove the risk by logging shares, then paying out proportionally instead of PPS. Either way, I think I'll save these ideas to possibly be implemented further down the line.

[Kontakt]

I still think proportional is fine for proxied work. Not a huge risk.

You're going to be mining for compressed addresses, right?
Uncompressed are outdated.

[TierNolan]

Since vanity pools work by either adding or multiplying two public keys, the person who wants an address will submit some random public key of his to the website and his desired pattern. Then you send this public key and the miners will generate other random public/private keypairs and multiply/add the two public keys to see if it creates an address that matches the desired one.

No doubt during this process there will be partial matches like:
1MyADDY
1MyAdDy
1myaddy

This will be your proof-of-work. And all will be valid, because there is no way to cheat here when you add the two public keys.

The easiest is just shorter matches.  The "difficulty target" is effectively <number of characters>, next character.

So,

{1MyAD, 9} would mean that you need to get MyAD as the first 4 characters and the 5th has to be less than 9. 

That gives you reasonable steps in share target.

Btw, what is the calculation for difficulty of the solution?  I assumed (58)^(character), but that doesn't seem to give the right answer.

You definitely should include an extra private key for the pool.  That way the address only has value if you have all 3 pieces (and only the owner will have all 3), but the miner cannot bypass the pool.

[jackjack]

Just a minor plea: Please don't build more address generators that don't use compressed keys.  Compressed keys are faster to generate and uncompressed ones bloat the network.

Why would it be faster to generate?

[fizzisist]

Just a minor plea: Please don't build more address generators that don't use compressed keys.  Compressed keys are faster to generate and uncompressed ones bloat the network.

Why would it be faster to generate?

... generating compressed vanity addresses is a bit faster since there is less data to hash each time you try one.

A side note, I am still working on this project, albeit slowly. If there is anyone that would like to collaborate on it, please let me know!