A Non-Outsourceable Puzzle to Prevent Hosted Mining (and Mining Pools)

[socrates1024]

“Hosted mining” poses a systemic threat to Bitcoin’s decentralization. Due to economies of scale, it can be more cost effective to hire someone to mine for you than it is to operate a miner yourself. An example of hosted mining is alydian.co.

The design of Bitcoin currently *encourages* hosted mining. This is a design flaw. It makes it easy to run a secure hosted mining protocol, where a Server proves it’s performing work that only benefits the Client. It does so by transmitting “shares”, where a share is a “near-miss” that commits to a coinbase transaction rewarding the Client. (This is exactly the opposite of a mining pool, where the Client does work for the Server (pool operator), but the protocol is the same.) The underlying problem is that the entity doing the work (guessing nonces and checking the hash) doesn’t necessarily get to spend the reward.

What I propose is modifying the proof-of-work protocol so that if the Server does the work, the Server can *steal* the reward for itself, in such a way that it is *undetectable* to the Client. If such a puzzle were used, then no reasonable Client would hire a hosted miner, since the hosted miner would take rewards as necessary and the Client would just seem unlucky.

There’s a way to do this that doesn’t require changing how existing mining works. It would require, however, a hard-fork that supports an additional zero-knowledge form of valid block. Ordinarily, a valid block reveals the nonce and merkleroot such that

Code:

H(prev, nonce, merkleroot) < target.

For the zero-knowledge option, the same nonce would be a solution, but you would not reveal the nonce, or the original merkleroot, to claim the block. Instead you would prove in zero-knowledge that you know a valid solution, and at the same time commit to a possibly different merkleroot’.

Code:

   Reveal prev, merkleroot’.
   Prove in Zero-Knowledge that you know a nonce, merkleroot, and value m, such that 
        H(prev, nonce, merkleroot) < target, and m = merkleroot ^ merkleroot’

Then the block would consist of this proof, and the transactions underlying merkleroot’. This does not reveal nonce or merkleroot. However, this acts as a non-malleable signature on merkleroot’ in the sense that someone who does not know merkleroot (or m) cannot create use the proof to take their reward.

General purpose ZK proofs like this could be done using Pinocchio or SCIP. I estimate that it would take around 20 seconds for an ordinary computer to construct such a proof. Verification would take as little as 15ms, according to the Pinocchio paper (they implemented SHA1, SHA2 is marginally slower). Note that it is not necessary for every miner to construct this zero knowledge proof - in ordinary use you can still just publish the nonce and merkleroot, like normal. But the point of this proposal is to additionally support an alternate zero-knowledge verification method, so that there is a clear temptation for hosted miners to steal the reward.

There is not currently a complete open source implementation of Pinocchio, but one could probably be made from the paper using the Pairing Based Crypto library.

This relies on an assumption that there is no effective way to 'obfuscate' SHA2, in the sense that the only way for a Server to efficiently mine is to actually know the nonce, which would let it steal the reward.

It seems like discouraging outsourcing this way would *also* discourage pooled mining. This is perhaps an unintended casualty, since pooled mining is not necessarily a systemic threat to decentralization, at least not in the same way. But maybe there's a way to support lower-variance mining while still preventing outsourcing.

Since the merkleroot' is not committed to while mining, it makes it trivial to create hundreds of 1-block forks. This doesn't affect consensus overall, since the blockhash (used as prev in the next block) *will* contain a commitment to a single merkleroot'.


***Update***: I've published a preprint of a research paper which presents improved versions of this scheme in more detail: Nonoutsourceable Scratch-off Puzzles to Discourage Bitcoin Mining Coalitions

[gmaxwell]

Arguably the reduction in 1 block commitment security might have useful benefits in security practices.

I've wondered before if some kind of chameleon hash couldn't be used for anti-censorship.  E.g. miner thinks he's mining transaction A but no no no there really exists a transaction B that he equally mined... but I've never found a way to make it work. Maybe I should think about using a proof of knoweldge.

I guess the biggest problems I can see with your idea are that:

(1) No one currently cares.  Pools, for example, can rob their miners undetectably... they _could_ do things to prove that they were not cheating, but none do.  Miners could use P2Pool which can't rob miners, but most do not. I imagine the story will be the same for cloud mining services, and they'll be able to use even more arguments about reputation and such to claim their honesty.

(2) The standard Mike Hearn argument: Part of the reason that Bitcoin is viable is that its very comprehensible (at least in broad strokes, if not for the subtle details) to basically any technically minded person, invoking some kind of zero knoweldge thing to _enable_ a specific kind of cheating is far more complex than anything currently in Bitcoin, even if it is a neat idea.

I guess the counter argument to (2) is that a lot of people initially believe its possible for miners (e.g. mining in a pool) to steal work, and it takes some effort to convince them that they can't.  Your idea would, in some ways, make mining more intuitive. I suspect its not possible to avoid breaking pooling, even in its most harmless forms, since anything that preserved pooling for payment would by definition be proving that the right parties were getting paid.

[btc4ever]

I care.  I use p2pool and avoid central mining pools.  just sayin.

(1) No one currently cares.  Pools, for example, can rob their miners undetectably... they _could_ do things to prove that they were not cheating, but none do.  Miners could use P2Pool which can't rob miners, but most do not. I imagine the story will be the same for cloud mining services, and they'll be able to use even more arguments about reputation and such to claim their honesty.

[socrates1024]

(1) No one currently cares.  Pools, for example, can rob their miners undetectably... they _could_ do things to prove that they were not cheating, but none do.  Miners could use P2Pool which can't rob miners, but most do not. I imagine the story will be the same for cloud mining services, and they'll be able to use even more arguments about reputation and such to claim their honesty.

(2) The standard Mike Hearn argument: Part of the reason that Bitcoin is viable is that its very comprehensible (at least in broad strokes, if not for the subtle details) to basically any technically minded person, invoking some kind of zero knoweldge thing to _enable_ a specific kind of cheating is far more complex than anything currently in Bitcoin, even if it is a neat idea.

Both of these are reasonable points, at least for the time being. But think of this as a long term idea. It's hard to project how people will behave in the future, as Bitcoin becomes more widespread and familiar. I'm pointing out a potential concern, and if it eventually becomes the case that hosted mining catches on, and clients demand proof-of-honesty from these services, then here's a solution ready to go.

“We are part of a transformation of Bitcoin mining,” said Hans Olsen, CEO of Alydian.
http://alydian.co/news/CoinLab-Announces-First-Incubator-Company

[gmaxwell]

I care.  I use p2pool and avoid central mining pools.  just sayin.

So do I.  But only 1.5% of the hashpower does, this leaves me pretty comfortable saying that no one cares.

[Carlton Banks]

(2) The standard Mike Hearn argument: Part of the reason that Bitcoin is viable is that its very comprehensible (at least in broad strokes, if not for the subtle details) to basically any technically minded person, invoking some kind of zero knoweldge thing to _enable_ a specific kind of cheating is far more complex than anything currently in Bitcoin, even if it is a neat idea.

Not thoroughly convinced by this one. You'd be disincluding the mirror neuron ("monkey-see monkey-do") miners; the only aspect they understand to begin with is electricity in -> money out. Maybe that's too crass a simplification, but they may not comprehend a great deal more than that to be tempted. It's so "tempting" that possibly >75% of those purchasing hardware in the past 4 months will never ROI.

I would consider supporting the disallowing of centrally pooled mining in the future, certainly when we get to a stage where the diversity of chain-complete nodes increases along with a block size limit increase/removal. I once read a dev suggesting incorporating the p2pool code into the standard client, I hope that's not been shelved.

Centralised pools were good to to attract miners with deep pockets and shallow motives, they make the uninitiated feel comfortable that they can pick a "winning team", but the manifest effects of that psychology are right now playing out at a new level of ugliness. Maybe the DOS attacks will make people latch on to p2pool more, but the evidence suggests that people are just setting a public p2pool node as a failover instead, and that dynamic is unlikely to win too many converts.

Miners are currently lazy and a very strange type of conservative (they only want to conserve the perceived assuredness of their own income, strengthening the network either doesn't matter or isn't contemplated)

[Cryddit]

I consider pooled mining to be a serious risk to Bitcoin's protocol.

Right now if the three biggest pool operators were to collude, it would be easy for them to simply agree never to mine on chains whose most recent block was not from one of them.  They'd immediately (roughly) double their profits by cutting out all other miners.  (AKA, a 51% attack).

But Bitcoin's design encourages this.  There is only one block reward every ten minutes, and the odds of a user getting one in his lifetime are rapidly approaching nil.  The only way to see a reasonably steady trickle of income is to join a mining pool.  So people do.  So we are all at risk on the decisions made by approximately any four out of six, or any three of the four biggest. 

And it gets worse when bitcoin's block reward  decreases.  At that point you see major hashing power simply turning off and waiting for the next time the difficulty comes down far enough to make mining into a profitable use of electricity again, then jumping back in again.  With mining pools, that can happen in huge chunks, making a 51% attack even more likely.

It's a design flaw that needs to be addressed at some point.  I don't know how, but we should definitely try to make it better to mine individually than in a pool. Or at least, as good in the long run.

Cryddit

[gmaxwell]

The only way to see a reasonably steady trickle of income is to join a mining pool.  So people do.  So we are all at risk on the decisions made by approximately any four out of six, or any three of the four biggest.

This isn't true, it's just how it is today. It's perfectly possible to pool for payment without pooling for consensus.

E.g. Pool gives you a coinbase transaction. You attempt to mine blocks including that coinbase, according to whatever policy you think is correct. You return shares to the pool and are credited according to what you submit.  The pool doesn't strictly need to even check the validity of your solutions, excepting that they include the right coinbase payments, since at worse mining invalid blocks is equal to a withholding attack which cannot be prevented in Bitcoin today... though checking might help guard against misconfiguration.

P2Pool is a somewhat extreme version of this, where the coinbase source is itself a distributed system which uses a kind of genesisless blockchain to track payouts... but coinbase mining would work just fine in the model and payment schemes of today's centralized pools without undermining the security of Bitcoin.  That just isn't what people built, ... for some reason no one thought of it this way three years ago. If they had the world might be a very different place today.

Taking this back on-topic, the idea here would break all forms of pooling, including the consensus-harmless "pool for income". Arguably that solves all the ills resulting from pooling but perhaps its a heavy hammer.  There is an argument that excessive variance also rewards consolation: the variance of mining substantially goes away if you personally own 2% of all the hashpower.

[socrates1024]

I think the best solution is to effectively build a 'mining pool' into the ordinary blockchain rules, basically allowing low difficulty blocks so miners can claim a smaller portion of reward somehow. I have no idea how to do this though without introducing a big DoS vulnerability. But IMO something like this would have to be solved before my non-outsourceable puzzle could work. Destroying pooled mining, without figuring out how else to serve the 'low-variance mining market' that currently uses pools, would have a big negative economic blowback, like a loss of mining participation.

I do think that hosted mining will eventually become a problem and we should work this out before then. Even if it doesn't seem like anyone cares right now.

[Cryddit]

Rather than having low-difficulty blocks, it might suit security purposes to reward users for near-miss hashes.

That means that in the coinbase transaction, the person who actually hit the difficulty target gets (say) 9 coins instead of 25, and the protocol also awards everybody who misses the target by less than 4 bits (there will be approximately 16 such hashes per block) with one coin. 

Alternatively, you could have special transactions allowing users to join (or leave) groups that split all block awards according to the number of acknowledged near-miss hashes turned in for that block.  With group membership encoded in the blockchain, the protocol could award shares of earnings to all members in the coinbase protocol.  So, it would marginally bloat the blockchain with group membership info and "near miss" tallies for members, but avoid additional transactions in which mining pools distribute block awards to miners.  So that would implement pooling for profit without pooling for consensus. 

But at this point we're seriously getting into AltCoin territory.  This would be fundamental rearchitecture in Bitcoin and I'd anticipate the devs flatly refusing to attempt anything like it unless an AltCoin had done it first and found it a good thing. 

[adam3us]

I think the best solution is to effectively build a 'mining pool' into the ordinary blockchain rules, basically allowing low difficulty blocks so miners can claim a smaller portion of reward somehow. I have no idea how to do this though without introducing a big DoS vulnerability. But IMO something like this would have to be solved before my non-outsourceable puzzle could work. Destroying pooled mining, without figuring out how else to serve the 'low-variance mining market' that currently uses pools, would have a big negative economic blowback, like a loss of mining participation.

I do think that hosted mining will eventually become a problem and we should work this out before then. Even if it doesn't seem like anyone cares right now.

I agree these objectives are important.  I explored this a bit in the past and it seemed to me it could work to have multiple smaller rewards, and multiple parallel winners, where the coinbase for each new block mined referred to the set of previous parallel blocks that are non-conflicting with it.  (There's not actually any need to orphan something just because its different so long as you dont disagree with it and bitcoin doesnt do that, just adopting new mined blocks as the new starting point unless there is conflict).  Then some heuristics for how reward is paid out, how fees are shared out.  I was kind of gratified that it seemed plausible that it should work, as it appears difficult to change anything much about bitcoin without making it worse in some way.  However its clearly less bandwidth efficient and more complicated rules have to be used for reward and fees.

Also its relatively easy to reduce variance of hashcash (or other proof of work functions), by the generic approach of using multiple sub-puzzles, however the problem is bitcoin is structured as a first-past-the-post race to find a solution (or first-n past the post with the multiple parallel chain) for the block reward, and if you reduce the variance the faster miner will win disproportionately to its power (eg win 75% of time with 50% of power or that kind of effect) which is bad. (You can see it more clearly with the thought experiment what if the variance is 0, ie the proof of work is deterministic, then clearly the fastest node will win every time.

Adam

[Cryddit]

Multiple rewards do not necessarily imply reducing the variance in an unfair way.

For example, you could simply maintain two different targets; one is good enough to get a reward, and another good enough to end the round and start a new block.  It would be simple enough to have a rule that the reward target is always ten times the block target, thus on average you'd have ten rewards (including the one that hit the block target) per block.  Same logic applies if you have a hundred rewards instead of ten.

The bigger miners enjoy rewards (at a lower variance) still exactly proportional to the number of hashes they turn in, not greater.  The round ending target is completely unaffected, and someone else still has the same chance of getting it even if the bigger miners turn in all of the other reward blocks that round.

[Meni Rosenfeld]

I consider pooled mining to be a serious risk to Bitcoin's protocol.

Right now if the three biggest pool operators were to collude, it would be easy for them to simply agree never to mine on chains whose most recent block was not from one of them.  They'd immediately (roughly) double their profits by cutting out all other miners.  (AKA, a 51% attack).

But Bitcoin's design encourages this.  There is only one block reward every ten minutes, and the odds of a user getting one in his lifetime are rapidly approaching nil.  The only way to see a reasonably steady trickle of income is to join a mining pool.  So people do.  So we are all at risk on the decisions made by approximately any four out of six, or any three of the four biggest. 

And it gets worse when bitcoin's block reward  decreases.  At that point you see major hashing power simply turning off and waiting for the next time the difficulty comes down far enough to make mining into a profitable use of electricity again, then jumping back in again.  With mining pools, that can happen in huge chunks, making a 51% attack even more likely.

It's a design flaw that needs to be addressed at some point.  I don't know how, but we should definitely try to make it better to mine individually than in a pool. Or at least, as good in the long run.

Cryddit

Multi-PPS solves this problem. (It's based on the smart miners already mentioned in this thread, and offers a way to decentralized the reward pooling agents.)

[adam3us]

Multiple rewards do not necessarily imply reducing the variance in an unfair way.

Thats true as they are independent progress free works then.  But they do need to be time-stamped, which means some coordination (broadcast?) and incentive structure to ensure later miners do not disregard or throw away earlier wins.

Were you thinking that the block needs to include the reward proofs as a means to time-stamp?

Adam

[Cryddit]

It's far simpler, if you want to motivate whomever finds the block to acknowledge the rewards due earlier miners, to simply award tx processing fees on all the 'mining reward' transactions in the block.   I mean, on the same basis as any other transaction, the 'mining reward' transactions would occupy space in the blockchain, and therefore should require tx fees proportional to the space they occupy.  Seriously, as I described it, their reward for finding the 'block' isn't in any way diminished by the rewards due people for finding 'near-misses', so why wouldn't they?

The thing that becomes probabilistic is the number of coins awarded per block.  But this is regulated, as always, by adjusting difficulty targets as needed. 

[oakpacific]

To my best knowledge all ZK technologies have to depend on asymmetric cryptography, anyone care to enlighten me?

[Trongersoll]

“Hosted mining” poses a systemic threat to Bitcoin’s decentralization.

This statement has never been proved to be true.

[fellowtraveler]

To my best knowledge all ZK technologies have to depend on asymmetric cryptography, anyone care to enlighten me?

No, you can prove something (without showing it) using a hash algorithm, without having to use any asymmetric algorithms.

[Cryddit]

Actually, you can perform a zero-knowledge proof of a whole lot of things without any recourse to cryptography at all.

Harry Houdini provided a whole lot of zero-knowledge proofs that various makes and models of locks and handcuffs and shackles were insecure.  Nobody saw exactly how he got out, but the fact remains that when the curtains were lifted he had them all off. 

Let's say I claim that I'm able to teleport.  But I won't actually allow anyone to *see* me teleporting.  I can perform a zero-knowledge proof for you by climbing into one box and out of another. 

Let's say I claim to be able to swim ten miles in deep rough water.  Maybe I don't want to let anyone see me doing it, but I can perform a zero knowledge proof by delivering your letter to the lighthouse keeper on his doorstep in the middle of a storm, while you're elsewhere, on the only boat in the area.

Remember that kid in the 'Mystery Men' who could turn invisible, but only if nobody was looking?  His zero-knowledge proof involved walking past security cameras.

Let's say Mike claims to be able to predict the price of bitcoin a week in advance.  He doesn't have to let you know what the prediction is, but he can make a prediction, stick it into a safe, and let you guard it.  At the end of a week, he gives you the key to the safe and you can see what his prediction was. 

[oakpacific]

Actually, you can perform a zero-knowledge proof of a whole lot of things without any recourse to cryptography at all.

Harry Houdini provided a whole lot of zero-knowledge proofs that various makes and models of locks and handcuffs and shackles were insecure.  Nobody saw exactly how he got out, but the fact remains that when the curtains were lifted he had them all off. 

Let's say I claim that I'm able to teleport.  But I won't actually allow anyone to *see* me teleporting.  I can perform a zero-knowledge proof for you by climbing into one box and out of another. 

Let's say I claim to be able to swim ten miles in deep rough water.  Maybe I don't want to let anyone see me doing it, but I can perform a zero knowledge proof by delivering your letter to the lighthouse keeper on his doorstep in the middle of a storm, while you're elsewhere, on the only boat in the area.

Remember that kid in the 'Mystery Men' who could turn invisible, but only if nobody was looking?  His zero-knowledge proof involved walking past security cameras.

Let's say Mike claims to be able to predict the price of bitcoin a week in advance.  He doesn't have to let you know what the prediction is, but he can make a prediction, stick it into a safe, and let you guard it.  At the end of a week, he gives you the key to the safe and you can see what his prediction was. 

Security through obscurity is out of the question for an open source project.

[Cryddit]

It isn't "security through obscurity".  It's "zero knowledge proof".  There's a difference in concept.

In a zero-knowledge proof you know in advance that there is only *ONE* way for someone to do something (or to reliably do something), and that is with knowledge of a certain secret.  You observe someone does that thing (or is able to do that thing reliably), and you accept it as proof that a person knows that secret.  And you can accept this proof even though it provides no way at all for you to learn that secret.

In "security through obscurity" you know that because no one else has a particular secret known to you, no one else can do a particular thing which you can do.  First it isn't as useful.  You learn nothing by noting that no one else is doing something.  You cannot prove that the secret is unknown to them; only that they haven't used it while you've been watching.  And if you can't perform a zero-knowledge proof of your secret, you can't demonstrate to anyone else that you have the secret yourself without running the risk that they learn the secret. 

I can cheerfully post my wallet.dat file, confident that no one else has my password to decrypt it, and that's security by obscurity.  Nobody else can prove that I have the keys, and nobody can prove that I'm the only person with the keys.  Nobody learns a thing.  Now if someone sends that wallet a new coin, and I demonstrate my ability to access the new coin's private key from the wallet, that can be accepted as a ZK proof that I know the wallet passphrase.  It still can't be accepted as any kind of proof that no one else does.

[peaty]

This sounds great, but a hard fork requires critical mass to succeed. What's to stop large pool operators from not upgrading?

[socrates1024]

Update: my advisors at University of Maryland and I have recently written a research paper about an improved version of this basic scheme, including a proof-of-concept implementation. The paper is currently undergoing peer review, but we will announce a preprint of the paper in the next week.

[gmaxwell]

Update: my advisors at University of Maryland and I have recently written a research paper about an improved version of this basic scheme, including a proof-of-concept implementation. The paper is currently undergoing peer review, but we will announce a preprint of the paper in the next week.

Just in time to redo it using libsnark: https://github.com/scipr-lab/libsnark 

[ABISprotocol]

Update: my advisors at University of Maryland and I have recently written a research paper about an improved version of this basic scheme, including a proof-of-concept implementation. The paper is currently undergoing peer review, but we will announce a preprint of the paper in the next week.

Just in time to redo it using libsnark: https://github.com/scipr-lab/libsnark 

That libsnark / zero knowledge stuff is interesting to be sure. Note:  I've amended my open issue to include a possible remedy and have tagged you (@gmaxwell) in it.

https://github.com/bitcoin/bitcoin/issues/4079

Cheers

[JaSK]

Peaty the pools/miners don't control the network, clients do.
Miners won't mine a coin nobody uses.

[sugarpuff]

Both of these are reasonable points, at least for the time being. But think of this as a long term idea. It's hard to project how people will behave in the future, as Bitcoin becomes more widespread and familiar. I'm pointing out a potential concern, and if it eventually becomes the case that hosted mining catches on, and clients demand proof-of-honesty from these services, then here's a solution ready to go.

That "if clients demand proof-of-honesty" is a very big IF that seems to go against the spirit of the original bitcoin paper (demanding an algorithmic answer, not a human one).

A related concern is that full nodes are disappearing as the cost of both running, and *especially* bringing online a new node, increases.

I made a proposal to address this issue that I called a rolling root, but even though nobody found a flaw in it, it was unpopular because it would require changing the protocol in some significant ways. I still think it should be done FTW.

[DeathAndTaxes]

I made a proposal to address this issue that I called a rolling root, but even though nobody found a flaw in it, it was unpopular because it would require changing the protocol in some significant ways. I still think it should be done FTW.

It was "unpopular" because it was unworkable.  Of course you ignored all criticism and failed to even do basic research on HOW transactions are verified.  Even basic concepts like addresses don't have balances and the input of all txs are the unspent outputs of prior txs were foreign to you.   

[sugarpuff]

It was "unpopular" because it was unworkable.  Of course you ignored all criticism and failed to even do basic research on HOW transactions are verified.

That is complete nonsense. I replied to every single unique point that I saw you (and others) make.

That you say I "ignored all criticism" can be verified to be a lie by anyone who reads the thread.

Even basic concepts like addresses don't have balances and the input of all txs are the unspent outputs of prior txs were foreign to you.  

This mantra of yours too, received a reply from me in that thread.

[socrates1024]

Wait, I'm confused, if hosted mining catches on, this doesn't provide a proof-of-honesty, it provides the opposite. That "if clients demand proof-of-honesty" is a very big IF that seems to go against the spirit of the original bitcoin paper (demanding an algorithmic answer, not a human one).

Yes, the way to read this is: if hosted mining catches on, but users are suspicious that the service may be cheating them unless the host provides proof to the contrary, then this puzzle may be effective since it's designed to *prevent* such proofs.

Imagine a user that says "I'll hire a hosted mining service, but only if they can prove to me they aren't ripping me off; otherwise I'll solo mine." Then this user would hire the hosted mining service in the current Bitcoin puzzle, but would solo mine given this modification.

My interpretation of the "spirit of Bitcoin" is that it is about *trust in a population's predictable response to incentive structures,* rather than *trust in the benevolence of oligarchs* or *trust in the responsiveness of vigilantes* etc. The point is that the behaviors we see now and will see in the future are largely a result of the incentive mechanism we implement. Altruism exists, and campaigns appealing to miners' long term stake in the stability of Bitcoin may be effective, etc. -- but correctly designing the incentive mechanism is an essential concern. I don't think we've fully tuned it yet, and the large mining pools are an example of this. Accurately predicting how people will react to the wide array of possible incentive designs is still an open research question.

This proposal is counterintuitive in that it involves engineering distrust between self-interested parties (pool members), as a way of encouraging safe behavior (solo mining) overall.

Also, in the interest of being self-contained, I repeat that this proposal is a useful technique but not a panacea on it's own. Several other non-trivial changes would need to be adopted at the same time as this puzzle, in order to provide the same low-variance option to solo miners, who otherwise would switch to Dogecoin or quit altogether.

[socrates1024]

A preprint of my paper can be found here:
http://cs.umd.edu/~amiller/nonoutsourceable_full.pdf

The major features include:
- Formal definitions of Scratch-off puzzles (a generalization of Bitcoin's proof of work)
- Formal definitions of Outsource schemes (a generalization of the "shares" system used by mining pools)
- Formal definitions of Non-outsourceable puzzles (a weak version, which lets pool members "steal" the reward from a pool, and a strong version, which lets them evade detection!)
- A simple construction (no moon math, just hashes and Merkle trees) for the weak-case
- An upgraded scheme (using SNARKs and other moon math) for the stronger-case
- Proofs
- Benchmark implementation results using Pinocchio (though these would likely improve by orders of magnitude if we use libsnark instead)

I'm working on a series of future posts explaining some of the concepts in better detail and summarizing the implementation issues that petertodd, gmaxwell, and others have raised.

[CoinHeavy]

"On the other hand, mining pools serve a desirable purpose of reducing the payoff variance for individual participants in the coin minting process. With our nonoutsourceable puzzles, we must seek a separate mechanism to achieve lower variance in mining. This can potentially be achieved by designing and incorporating a more flexible lottery mechanism into Bitcoin. Specifically, the lottery mechanism should allow players to choose different puzzle difficulties, and the higher the difficulty, the higher the promised reward. How to design such a lottery mechanism and understanding its economic implications is part of our future work."
--Section 8 (discussion), paragraph: mining pools.

This is certainly the crux of the tradeoff.  Vitalik also raised this point at the bitcoin NYC developers meetup yesterday.  Is anyone aware of active work in this domain?  With lower difficulty puzzles, high-hashrate actors could dominate the low end of the puzzle-difficulty spectrum, presumably trading off marginally higher gains from higher difficulty puzzles for reduced variance in reward amounts.

Very compelling work.  Staying tuned and chewing on some interesting food for thought in the meantime.  Thanks for sharing.

[Sergio_Demian_Lerner]

Here is my post I published today about this topic.. I hope it adds some new issues to be discussed...
(http://bitslog.wordpress.com/2014/06/19/theoretical-and-practical-nonoutsourceable-puzzles/)

Theoretical and Practical Nonoutsourceable Puzzles

The idea of a theoretical non-outsourceable puzzle is very tempting, and I encourage anyone to read the paper and try their constructions. Nevertheless I see four problems with this approach. Two are theoretical, one is legal and the last is practical. The core idea of the paper is that if if a miner can steal a block from the pool admin, and the pool admin has no way to catch the stealer, then there is no incentive to become a pool admin, since no solved blocks will be shared with the other pool members.

Problem 1: Mining cartels

If at any time 51% of the miners decide to prevent the others from mining solo, they can stop mining on top of the blocks they solve or they can blacklist their coinbase addresses.  Then all miners would be forced to join pools and include in each block (as a transaction or in any other part) an identification of the mining pool they belong. Then a Nash equilibrium arises: miners cannot mine solo (unregistered) because pools won’t mine on top of unregistered blocks so they will join pools, which re-enforces the disincentive to do solo mining because of they blacklist solo blocks.

Problem 2: Finding a cheater can be easy, even with ZNPs

Suppose a miner (called a “server” in the paper) wants to steal a block from the pool admin (called a “client” in the paper). First we must make clear that both the miner and the pool admin want to collaborate in a pool. They will do whatever is necessary to achieve collaboration. So the pool admin can set rules to catch a stealer that miners agree to obey. With punishment rules, the miner admin can always punish a miner that tries to steal a block even with a  non-outsourceable puzzle. Suppose the pool admin forces each miner to scan a certain nonce space (so nonce is watermarked by as 128-bit secret key and must be incremented sequentially) while mining. Suppose also that the pool admin asks each miner to send the best share found every second to the pool admin (to be paid in accordance) along with the nonce used for that share, and checks that the nonce is in the expected range, according to the miner declared computing power. Since every miner obey, so far the pool works. But the pool admin can track which is the nonce being scanned by any miner at any time. Then, whenever the pool admin sees a stolen block being published, he just need to scan the nonce space of at most 1-second of each miner member of the pool to detect if the cheater is a miner from the pool (or a random number of seconds between 1 and 30).

Let’s see an example: Suppose that the pool hashing power is 10% of the total hashing power. Suppose that stolen blocks are unusual (say 1% of the time). Suppose that miners must send shares every second to the pool admin. Then the pool admin would only need to spend 1/600000 = 0,0016% of the pool hashing power in finding a cheater. The hardware used to find a cheater could be owned by the pool admin, or even the search could be conducted by the pool itself, giving a reward to the miner who finds the cheater. This will obviously take to the pool about 1 second of processing, if the cheater is part of the pool. So there is a trade-off between using the pool resources to find the cheater or using the pool resources to mine more blocks. Note that the pool admin does not need to look at the content of the block, not try check the presence of any watermark in the block. He just need to re-do the last 1 second work of the pool to check if the cheater was in the pool.

I suppose that there is a Nash equilibrium: if the stolen block rate is low, pool admins can detect cheaters and so nobody will be willing to try to steal, so the stolen block rate will be low. It needs all miner to rebel against the pool operators and steal all block in order to prevent the detection of cheaters.

Problem 3: Nonce Watermarks

Mining pool admins and members of the pool can agree to have their own block watermarked. A watermark can be embedded into a nonce like, for example, nonce(i) = HMAC(k,i) || i , where k is a unique secret symmetric key shared between each miner and the pool admin. Even if the nonce is hidden by a Zero-knowledge-proof, the pool admin can re-scan the nonce space and detect the watermark. The probability that the watermark is present by chance can be made arbitrarily low, such as 2^-128. So the watermark is a proof of the violation of tacit (but 100% legal) agreement between both the miner and the pool admin which states that the block reward belongs to the pool, and not to the miner. So the pool admin can go legally against the cheater. Nevertheless, going legally is only a good option if information regarding the identity of each pool member is collected by the pool admin.

Problem 4: Complexity

The constructions proposed by Miller are far more complex than the well-known Bitcoin SHA-2 PoW. More “esoteric” cryptography  (as Schneier used to call it) must be carefully analyzed and implemented without bugs.

 
A Practical and Simple Proposal: BlockPow

I will propose a kind of PoW puzzle that only practically prevents mining pools for certain cryptocurrency settings. The idea is that if miners try to join a pool, then they incur in overhead and earn less than working solo. Let b (the payload) contain a full block. b must contain all the transactions and the header, and not only the transaction hashes. b should not hide anything. Let h be the block header (which contains the previous block hash and the Merkle tree root of the transactions). Let d be the difficulty. hash-block-length(b) returns the number of blocks processed by the hash function when fed with the block b. The target is divided by hash-block-length(b) so that the difficulty does not depend on the length of the block. Some other function can be used to encourage nodes to add more or less transactions.

Def: BlockPoW

For each r in the nonce-range: if H ( H( r || b ) || h || r) ) < 2^-d/ hash-block-length(b) then return r

return null

The header (h) is appended to the hashed message to allow SPV clients to verify the PoW without requiring the full block to be downloaded. Peers can send only (x,r,h) to SPV nodes, where x = H( r || b ), so they can verify the PoW. The verification procedure is obvious, and is skipped here. r is inserted at the beginning of the message to prevent pool administrators from keeping a secret mid-state of the hash function secret in order to prevent block stealing and also to force the miner to know b in the inner mining loop.

So now mining requires the knowledge of the block b to be mined, and b must be received at each block-chain epoch. This could create an incentive not to include any transaction and use an almost empty b, because that way the bandwidth requirements is decreased. But this incentive should not exists normally, since by including transactions the solo miner gets an additional revenue from fees, which is lost if the block is empty. Anyway, to prevent this possible incentive we can append to b a subset of previous blocks (e.g 100 blocks). The block subset to include could be derived from a peudo-random function seeded by the previous block hash. Then a node would still need to download part or all the block-chain in order to mine.

Now if the miner wants to be a dumb node and take part of a pool, then the current working unsolved block (the template) must be sent each time from the pool admin to each miner. If the pool admin hosts 1000 miners, then to serve them with fresh block templates he needs 1000 times more bandwidth that the miners, making this much more expensive. If miners create another network topology to distribute templates, they are incurring in the same overhead as being actively part of the cryptocurrency network, so they gain nothing.

For example, in a block-chain with a 5 seconds block-rate, such as in NimbleCoin, each block can be as large as 200 Kbytes (100 tps are allowed). A miner will require the block template to be ready as fast as possible, say before 3 seconds, so as not to loose more than 60% of the times the transaction fees present in the block template. This means that a pool admin serving 1000 clients must have a upload bandwidth of at least 60 Mbytes/sec, and load balance servers, because all miners will demand the block template at the same time and will compete for it.

The same miner, working solo, will not loose the 60% of block fees. If block fees are 10% of block reward, then solo miners earn 6% more than pool miners. Also, having a block rate of 5 seconds allows solo miners to receive payments more often and so it reduces the payment variance.

This method to discourage mining pools only work as long as time is takes to transmit a block is comparable to the block interval time, e.g. 20%. This seems not to be a problem since if the cryptocurrency becomes popular, then we can expect blocks to be near full, while if is is not, then nobody will care about mining pools.

For this method to work for Bitcoin, Bitcoin should reduce the block rate to at least 1 minute, and keep blocks of at least 10 Mbytes. Or go the NimbleCoin way, and reduce the block interval to 5 seconds. The sole reduction of the block rate from 10 minutes to 5 seconds would reduce notably the mining reward variance, which is the main reason miners don’t mine solo.

[socrates1024]

Problem 3: Nonce Watermarks
Mining pool admins and members of the pool can agree to have their own block watermarked.

This is not the case. Suppose a pool member finds a nonce, and publishes a ZK block solution. Even if the pool also finds this nonce by rescanning, it cannot associate the ZK block solution with it. This is because the ZK NIZK proofs (the GGPR scheme) are information-theoretically hiding.

Problem 2: Finding a cheater can be easy, even with ZNPs

This is only partially true. Any detection scheme like this is susceptible to false positives. Someone else who finds a ZK block at roughly the same time as a pool member is effectively framing them. Again, our definition says that a stolen ZK puzzle is indistinguishable from one created independently.

[Sergio_Demian_Lerner]

Problem 3: Nonce Watermarks
Mining pool admins and members of the pool can agree to have their own block watermarked.

This is not the case. Suppose a pool member finds a nonce, and publishes a ZK block solution. Even if the pool also finds this nonce by rescanning, it cannot associate the ZK block solution with it. This is because the ZK NIZK proofs (the GGPR scheme) are information-theoretically hiding.

Yes, it was my mistake. Thank you Andrew for clarifying this to me.

For weakly Nonoutsourceable Puzzles was true but for strongly Nonoutsourceable Puzzles the pool admin can only get a clue of who might be a cheater but no real evidence.
Nevertheless the clue may be strong (for example, if the supposedly cheating miner that is member of the pool has 0.1% of the total hashing power, the probability that this miner has not cheated is 1/600000) .

[socrates1024]

In case anyone has missed it, Eyal&Sirer have posted about an enhancement to my puzzle scheme that makes it possible to reuse existing Bitcoin miners. It's too bad I missed this! Compatibility with existing Bitcoin miners is a major win for the plausibility of implementing this as a practical fix.
http://hackingdistributed.com/2014/06/18/how-to-disincentivize-large-bitcoin-mining-pools/

The 2-Phase puzzle they propose is a "weakly nonoutsourceable" puzzle according to my definition. The main idea is that instead of *each* attempt requiring knowledge of a private key, only some constant fraction (1/Y) of attempts need to. First you, configure an existing Bitcoin miner to mine blocks at a very low difficulty (1/X chance of winning), where your coinbase contains a commitment to some public key. Every time your mining rig outputs a partial solution, you perform a second check, which essentially involves signing the solution with the corresponding private key.

In total, 1/(XY) attempts must be made to find a solution, so XY should be set equal to the current difficulty. The tradeoff between X and Y should be chosen so that Y is small enough that an ordinary GPU or CPU can "keep pace" with the partial solutions generated by a typical Bitcoin mining rig, but Y is large enough that it would be infeasible for a miner to *interact* with the pool operator without learning the private key on its own. This is actually the same sort of analysis we did in Permacoin.

This scheme is compatible with most of the work of my existing puzzle schemes:
1. A good candidate for the signature scheme is the Merkle tree-based signature scheme used in this paper and in Permacoin. ECDSA, however, is out. It's essential that the signature scheme is deterministic - there should be exactly one valid signature for a given message and keypair.
2. Since this is a "weakly nonoutsourceable" puzzle, it can be *upgraded* to a "strongly nonoutsourceable" puzzle using the generic scheme described in our paper.... basically you can take any weak-NO puzzle and make it strong-NO by adding a zkSNARK option.

[Crowex]

 What if your scheme was implemented and as a result the hosted mining schemes decided to publish the ROI as a way of measuring their honesty. So each week/month they would say that they were paying out a certain percentage according to how much a client had invested.
 This would easily be verifiable by the investors by looking at what payout they receive.
 Over time we could see who had better returns and a result people would end up moving from the dishonest hosted mining schemes that weren't declaring mined blocks and investing to the schemes that had the consistently better returns.

 Mining pools would fail because the miners would cheat the pool so everybody would end up investing in hosted mining and specifically in the top performing hosted miner who would eventually control all of the mining. 

[socrates1024]

What if your scheme was implemented and as a result the hosted mining schemes decided to publish the ROI as a way of measuring their honesty. So each week/month they would say that they were paying out a certain percentage according to how much a client had invested.
 This would easily be verifiable by the investors by looking at what payout they receive.
 Over time we could see who had better returns and a result people would end up moving from the dishonest hosted mining schemes that weren't declaring mined blocks and investing to the schemes that had the consistently better returns.

 Mining pools would fail because the miners would cheat the pool so everybody would end up investing in hosted mining and specifically in the top performing hosted miner who would eventually control all of the mining.  

This is a really insightful point, and my response to it so far is, at best, sketchy and speculative. This point has been brought up by others including gmaxwell, SDLerner, and zooko.

First of all, suppose that we solve the low-variance problem, and solo individual miners are able to choose whatever sort of risk profile they want, without having to join a pool. Now lower-variance isn't a reason to join a pool or hire a cloud miner.

However, there are still reasons to hire a cloud miner... cloud miners enjoy some economies of scale, and may benefit from vertical integration and custom mining rigs. It may be the case, given this, that cloud mining is inevitable and decentralized proof-of-work is doomed.

I think there's a plausible(ish?) alternate outcome. It's outlined in this post https://bitcointalk.org/index.php?topic=305781.0 but I'll repeat a bit of it here.
- Bitcoin mining is unprofitable, on average. It's so unprofitable, that even vertically-integrated cloud miners are unprofitable or unsustainable.
- Even though it's unprofitable, people are still systematically incentivized to mine, for the same reason that State Lotteries are a big business: in some cases, people actually PREFER a high variance prospect, if there's the *chance* of winning a large jackpot. Bitcoin mining is an occasionally lucky gamble, rather than a reliable profit.

In other words, this is based on a premise that potential miners -- in the future, if not now -- actually have some appetite for variance and luck. Right now there's only one game - the 25btc jackpot. But imagine you can choose a puzzle that has some chance of giving you 0.1 btc, some chance of giving you 1btc, some chance of giving you 10 btc, and so on. Go to any gas station (in the US) and look at the variety of lotto games you can play for inspiration.

If miners choose something with a high-enough-variance component, then they'll be suspicious of a cloud provider that can get away with stealing their "lucky" jackpots, if not their every-day 0.01 btc consolation prizes.

I don't have the tools to really evaluate or justify this hypothesis. For sure it's outside the scope of this present paper. An ASIC resistant puzzle, if there truly is one, may diminish the effectiveness of cloud mining. It's also possible that a nonoutsourceable puzzle is the best we can do, and this gap just has to be tolerated.

[Crowex]

It’s easier to come up with problems and reasons why decentralisation won’t happen than it is to come up with solutions and I wish I could offer more constructive ideas. It does seem that everything tends towards centralisation and you have to actively guard against it.

The variance problem is related to the fact that is so much easier for everyone to verify the work done by one big lottery winner than to verify the work done by lots of people winning minor prizes for their effort - which is why the mining reward system has to be so probabilistic. Any system that reduces variance will probably require more computing power spent on verification.

[TPTB_need_war]

I guess the counter argument to (2) is that a lot of people initially believe its possible for miners (e.g. mining in a pool) to steal work, and it takes some effort to convince them that they can't.

Except they can. It is called a Share Withholding Attack which I learned from reading Meni Rosenfeld's 2011 white paper, where the miner withholds the shares which are winning blocks, thus stealing the work of the other honest miners in the pool. And his proposed solution oblivious shares was apparently never adopted by Bitcoin.

Given the high variance afaik this sort of cheating can't be detected statistically very well.

The motivation for doing this could be for the purposes of monopolizing pooling to drive up transaction fees, when debasement ends, because transactions fees are a Tragedy of the Commons.

[TransaDox]

It’s easier to come up with problems and reasons why decentralisation won’t happen than it is to come up with solutions and I wish I could offer more constructive ideas. It does seem that everything tends towards centralisation and you have to actively guard against it.

I've got to agree here. It is a hard problem that we all thought Bitcoin had conquered. Turns out; not so much.

I think the issue is profit. It's very hard to monetise a distributed system. It is why we have the internet we have to day and why Apple, Google and now Windows are walled gardens behind controlled access-ways. The target end-game of all for-profit ventures is a monopoly as that guarantees income, guarantees market share and guarantees a price.

Targeting and crippling pools I don't think is a real solution. It just removes the only real competition to commercial miners - so I question the motives. Pools were the natural progression once hobbyists were overtaken by the costs of hardware needed to claim a steady income. I see pools as more of a community enterprise to pool resources in times of hardship. Unfortunately, that always provides the way through for the rentier business to offer coordination services very much the way Amazon, Ebay or Uber do. Eventually, they will be forced out or bought out by the commercial miners who will disincentivise hard-core hobbyist to give up on mining or exploit them with unfair terms. It's the town market verses the supermarket scenario and we know who wins that.

So I suggest we don't target pools. We target mining, period. If un-outsourcable POW can decentralise away from commercial farms as well as pools, then I'm in. If it only targets my next door neigbour who bought a single Ant Miner with his Xmas cheque, then I am firmly against. Most non-outsourcable POW systems I've seen so far, however, only target the latter since a commercial miner is the admin and participants and therefor always gets the reward however you want to cut it.

[r0ach]

Targeting and crippling pools I don't think is a real solution. It just removes the only real competition to commercial miners

It's a no win situation for Bitcoin with either move.  I think I made a pretty good case for implementing the non-outsourceable puzzle in the following thread.  The only problem is, PoW and the non-outsourceable puzzle can probably never win in the free market vs other consensus mechanisms.  On the other hand, it seems doomed anyway if you don't address the issue.  It's a Kobayashi Maru:

https://bitcointalk.org/index.php?topic=1176835.0;all

A Reply in thread to clarify more:

https://bitcointalk.org/index.php?topic=1176835.msg12395590#msg12395590

[TransaDox]

Targeting and crippling pools I don't think is a real solution. It just removes the only real competition to commercial miners

It's a no win situation for Bitcoin with either move.  I think I made a pretty good case for implementing the non-outsourceable puzzle in the following thread.  The only problem is, PoW and the non-outsourceable puzzle can probably never win in the free market vs other consensus mechanisms.  On the other hand, it seems doomed anyway if you don't address the issue.  It's a Kobayashi Maru:

https://bitcointalk.org/index.php?topic=1176835.0;all

A Reply in thread to clarify more:

https://bitcointalk.org/index.php?topic=1176835.msg12395590#msg12395590

I'm not as pessimistic as that.......yet. My stance is that network integrity needs to be reliant on numbers (of clients) rather than resources and that is the key to preventing the coalescing of power structures. The unfortunate situation we currently find ourselves in is because we give too much credence to game theory and commercial interest instead of nullifying their corruptions with technology and maths.

I too think that non-outsourceable puzzles have a desirable aspect but just haven't seen any proposals that prevent the inevitable mining co-location centers. I find them uninteresting unless they can address both. I think I see where we will end up if things continue as is; just not sure what or how to change the software to prevent it right now.Most energy seems to be with this block size nonsense which I tend to view as how many fingers do we want broken rather than how do we de-claw the miners (pools and commercial) and re-claw the users. The answer to my quest also answers the mining pools and hosted mining, I believe and my intuition tells me that if there is an answer, it probably lies in non-outsourceable puzzles.

[r0ach]

I just randomly stumbled onto this.  Some altcoin that nobody has ever heard of actually attempted it: