The fact that GHash.io has reached twice 51% of the Bitcoin hashing power this year has pushed scientist an
d alt-coin creators to find for other proof-of-work puzzles that discourage mining coalitions. Several months ago I read the foundations of Nonoutsourceable Puzzles as proposed by Andrew Miller, and now his paper (working with Elaine Shi, Jonathan Katz, and Ahmed Kosba) is almost ready to be published. A pre-print can be reached here. Also practical example (but many practical and theoretical details still need to be analyzed to prove usefulness)
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, the cartel can stop mining on top of the blocks the others solve or the cartel can blacklist the solo miner’s 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 by joining a pool they re-enforce the blacklisting pressure.
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
For weakly Nonoutsourceable Puzzles (which do not prevent 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. For strongly Nonoutsourceable Puzzles this is not true, and 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) .
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.
BitcoinBlockPow
The basic BlockPoW is incompatible with Bitcoin ASICs as is but it can be made partially compatible with some tweaks: The value b is replaced by a a a subset or an integrity check of the block.
Using a subset:
First the hashMerkleRoot and hashPrevBlock fields are replaced by the fields: ChildBlock (32 bytes) and ScatteredBlockBytes (32 bytes). ChildBlock is the hash of a message with stores the old hashMerkleRoot and hashPrevBlock. ScatteredBlockBytes is a pseudo-random subset of bytes taken from the block template being mined. The seed for the pseudo-random function that selects the subset is the hashMerkleRoot plus the block time. When a miner scans all the 32bit nonce space, then a new hashMerkleRoot must be created to increase the extra-nonce field or the time must be updated. When this happens, a new subset of pseudo-random 32 block bytes must be collected. If the miner only stores 10% of the block template (e.g. 100 Kbytes instead of 1 Mbyte), then the probability he can build the ScatteredBlockBytes by brute-forcing the seed is 10^-32. If the miner performs 100 GH/sec, then the 32-bit nonce will overflow every 20 msec and the miner could request the ScatteredBlockBytes from the pool admin using a bandwidth of 1 Kbyte/s. A pool hosting 6 PH/sec (such as Eligious, which has 8%) would need to stream more than 60 Mb/s of ScatteredBlockBytes fields. A mining pool having 50% would need to stream 500 Mb/s, which is quite challenging. So miners will download the block normally, and become active part of the network.
Using an integrity check:
ScatteredBlockBytes is replaced by a field BlockHash defined as H( full-block-with-zero-nonce ). Obviously the header must be at the beginning of the block to force the re-hash.
Bitslog 