Blockpad: Improved Proof-of-work function with decentralization incentives

A few posts ago I presented BlockPow, an example of a proof of work function that practically reduces the incentives for users to join mining pools. The shorter the block interval, the best it works. Let’s first summarize the idea behind BlockPow:  if a miner tries to join a pool, then he incur in overhead and earn less than working alone. This is done by requiring that miners have access to the full contents of the block in order to begin hashing. Receiving the full block contents requires no less resources than having a full network node, so they should choose collecting their own transaction set instead of delegating the selection to the pool administrator, without incurring in relevant costs. The key security property is that the function prevents the use of a compressed or “midstate” description of the full block. But BlockPow has a drawback: even if it tries to even the cost of mining small and large blocks, it cannot truly guarantee that for a certain computing architecture the incentive is slightly bias towards one of the sides. If the function encourages small blocks, then miners won’t contribute to the network processing transactions. If the function encourages large blocks, then miners will fill the block until reaching its maximum capacity with bogus transactions, forcing the network to waste storage.

BlockPad is a new proof-of-work function that attempts to correct this by first expanding the current block into a fixed size pad whose size is not lower than the maximum block size. The expansion uses a pseudo-random generation function but with the property that on average pad chunks cannot be regenerated without the knowledge of the full block contents. Then this pad is hashed for every nonce. For extreme protection the block is first passed through an expensive transformation to prevent any shortcut based on transaction compression, although I can’t find an realistic example for such incentive. The transformation chosen is the exactly building block of SeqMemoHash, a strict-memory-hard function I proposed in this paper.

Let “block” be the full block. 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.  Let M be the the number of chunks of the pad. The chunk size could be anything above 64 bits. It can be half of the hash digest size or it can be equal to the internal block size of the hashing function. Let N be the number of iterations to transform the pad first in order to reduce any practical chance of block compression to be useful: N=1 should be enough. size(x) returns the size of x in chunks, and x[i] returns the chuck at chunk index i.

Def: BlockPad

Setup:

1. Compute pad :=ExpandAndTransform(block)

Mine:

1. For each r in the nonce-range:
2. If H ( H( r || pad ) || h || r) ) < 2^-d return r
3. else return null

ExpandAndTransform(block):

1. Create the pad t of size M (in chunks) and fill t with zeros
2. Mix(t,block,1)
3. Mix(t,t,N)
4. return t

Mix(dst,src,count):

1. repeat count times
2. For i :=0 to size(dst)-1 do
3. dst[i] :=H ( src[i mod size(src)] || dst[(i-1+size(dst)) mod size(dst) ] )

Note that we’re not trying to discourage ASICs with BlockPad, but ASICs could be discouraged by hashing the pad in chunks  in a pseudo-random order where includes every chunk has a high probability of having been selected, and where the index of the next chunk in the pad to hash is derived from the previous pad chunk contents using the RandMemoHash function proposed in my paper. The ASIC-unfriendly version is defined as :

Mine:

1. For each r in the nonce-range:
2. If H ( RandMemoHash( r || block ) || h || r) ) < 2^-d return r
3. else return null

In my previous post I explain how SPV nodes can use BlockPad without problem.

Verification time should not be a problem size the size of the data to hash would be approximately 4*MaxBlockSize, where currently in Bitcoin the amount is approximately 1*MaxBlockSize because of the hashing of each transaction to build the Merkle tree (assuming blocks are near full).

As explained in the previous post, Bitcoin can implement a variation of BlockPad that still provides the same properties and maintains compatibility with current mining ASICs. The idea is that every time the time field or the MerkleRoot field change (generally after the 32-bit nonce has been fully scanned), a the pad must be re-hashed and the pad hash is referenced by the block header. I’ll make this a BIP. My aim is not to remove the incentive from miners joining pools to reduce the variability in payoffs, but to force miners to choose their own transactions to include. BlockPad miners can still join pools by publishing shares where they pay to the previous miners in the pool, such in p2pool.