Topic: A Non-Outsourceable Puzzle to Prevent Hosted Mining (and Mining Pools) - page 2. (Read 25633 times)

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

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.

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

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.

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

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. 

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

This statement has never been proved to be true.

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

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. 

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

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.)

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.

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

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. 

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.

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.

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

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)

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