Topic: A Non-Outsourceable Puzzle to Prevent Hosted Mining (and Mining Pools) (Read 25696 times)

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

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.

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://bitcointalksearch.org/topic/m.12395590

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.

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.

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.

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://bitcointalksearch.org/topic/bitcoin-as-lottery-prospect-theory-and-unprofitable-mining-305781 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.

 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. 

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.

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

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.


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.

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.

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

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.

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.

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.


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

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.   

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.

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

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