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.