Decreasing the variance of block interval w/o decreasing the mean of interval

[jl2012]

The block interval follows exponential distribution of lambda=1/10, with mean = 1/lambda = 10 and variance = square of the mean = 100.

It is not uncommon to see block intervals of >1 hour and that could be really annoying. Having two blocks too close to each other is also a waste of block space.

As the variance is the square of the mean, we may decrease the variance by decreasing the mean but that would have other side effects.

It is possible to decrease the variance to 50 while keeping the mean as 10:

1. A miner will first mine the following message

Code:

 |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a| 

until it is below the target. The difficulty is determined to archive an average successful rate of 5 minutes. hashCoinbase is the 256-bit hash of the desired reward transaction. The miner won't broadcast the message

2. When a valid hash is found in the step 2, the miner will start to hash the following message:

Code:

 |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a|hashMerkleRoot|Time|Nonce-b| 

until it is below the target. The average successful rate is also 5 minutes. This is the valid block to broadcast to the network

3. A block is valid if it satisfies all the following requirements:

• Hash of |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a| is below the 5-minutes target
• Hash of |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a|hashMerkleRoot|Time|Nonce-b| is below the same 5-minutes target
• Hash of the reward transaction is same as hashCoinbase
• All other existing rules, e.g. all transactions are valid, timestamp requirements

The block time interval will follow Erlang distribution (http://en.wikipedia.org/wiki/Erlang_distribution) with lambda=1/5 and k=2. The mean is k/lambda=10, and variance=k/(lambda^2)=50

The block header size will be expanded from 80bytes to 116bytes.

We can further decrease the variance by decreasing the difficulty while requesting more nonce. For example, we can decrease the difficulty to 1/3, then:

First step:

Code:

 |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a| 

Second step:

Code:

 |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a|Nonce-b| 

Final step:

Code:

 |Version|hashPrevBlcok|hashCoinbase|Bits|Nonce-a|Nonce-b|hashMerkleRoot|Time|Nonce-c| 

The mean block time interval is still 10, but the variance decreases further to 33.33

For each additional nonce requested, 4 bytes additional bytes are needed

Why need a hashCoinbase? We need to make sure people can't steal the partially completed block of other miner

It may make some types of one-confirmation double spend attack easier. I'm not very sure.

Any comments?

[maaku]

And mining is no longer progress-free. Now the fastest miner finds all the blocks.

[jl2012]

And mining is no longer progress-free. Now the fastest miner finds all the blocks.

You are right, if we indefinitely increase the k (number of nonce requested)

Although I can't show the maths but it could be shown with the following mental experiment.

Let say I own 10 pieces of ASICs.

Currently, no matter they are mining the same block or different blocks, my expected return is exactly the same.

In my scheme, for the first step, the 10 ASICs may still mine independently. When a valid hash is found by one of the ASIC, the rest will stop first step mining and move to the second step immediately to increase the chance of getting a full block. This implies that efficiency of a fast miner is higher.

It would be nice if someone could show the maths. Let say we have 2 miners controlling 1/3 and 2/3 of total hashing power. What is the long-term block proportion in a 2-step mining?


EDIT: As the exponential distribution is the only memoryless continuous probability distribution, we have no choice but sticking to it?

[TierNolan]

It would be nice if someone could show the maths. Let say we have 2 miners controlling 1/3 and 2/3 of total hashing power. What is the long-term block proportion in a 2-step mining?

2/3 of hashing power means all the blocks, no matter what.

I ran a quick simulation with 100k blocks.

hash_power = [0.3000    0.2000    0.1500    0.1000    0.1000    0.1000    0.0500]
block_share = [0.4144    0.2250    0.1345    0.0685    0.0679    0.0698    0.0199]

[jl2012]

It would be nice if someone could show the maths. Let say we have 2 miners controlling 1/3 and 2/3 of total hashing power. What is the long-term block proportion in a 2-step mining?

2/3 of hashing power means all the blocks, no matter what.

I ran a quick simulation with 100k blocks.

hash_power = [0.3000    0.2000    0.1500    0.1000    0.1000    0.1000    0.0500]
block_share = [0.4144    0.2250    0.1345    0.0685    0.0679    0.0698    0.0199]

It could not be "all" because it is still random process, right?

Anyway, it seems exponential distribution is the only choice

[TierNolan]

It could not be "all" because it is still random process, right?

Well, I meant 2/3 is a 51% attack, the miner can just orphan all the other miner's blocks.

Anyway, it seems exponential distribution is the only choice

The key is that miners must be able to work together to build up the block.

For example, you could update the header so that

H(nonce1) < diff
H(nonce1 | nonce2) < diff
H(nonce1 | nonce2 | nonce3) < diff

and so on.

Once a miner finds a nonce1, they can broadcast it and then all the other miners can work on nonce2.

You would need a way to reward the miners who find nonce2 though.

An even easier way would be to increase the block rate to 1 block a minute, but only allow every tenth block to have transactions in it.  Each block would still be allowed to have a coinbase though but it would be 10X times smaller.

This gets the same effective block rate as now, but still means that miners can be rewarded for finding the (near) empty blocks.

You could do this with a soft fork but you would need at least 91% of the network to make it work.  A poll with only 10% of the hashing power would be able to create a fork that would be followed by older clients.

Each would have to embed in the coinbase a reference to a chain containing 9 mini-blocks.  Each mini block would have the same difficulty as the main chain block, but would be a header and a simple coinbase.

When a new block is found, miners would switch to trying to build 9 mini-blocks on top of it.  Once the nine have been found, they could build the next block.

90% of the tx + minting fees would have to be paid out to the mini-block's coinbases in order to keep things fair.

This reduces the incentive to add transactions though.  If you add a 1BTC fee transaction, you only get 0.1BTC.  This may result in some pools not bothering with full blocks.

[jl2012]

It could not be "all" because it is still random process, right?

Well, I meant 2/3 is a 51% attack, the miner can just orphan all the other miner's blocks.

Just assume all miners are honest

Anyway, it seems exponential distribution is the only choice

The key is that miners must be able to work together to build up the block.

For example, you could update the header so that

H(nonce1) < diff
H(nonce1 | nonce2) < diff
H(nonce1 | nonce2 | nonce3) < diff

and so on.

Once a miner finds a nonce1, they can broadcast it and then all the other miners can work on nonce2.

You would need a way to reward the miners who find nonce2 though.

An even easier way would be to increase the block rate to 1 block a minute, but only allow every tenth block to have transactions in it.  Each block would still be allowed to have a coinbase though but it would be 10X times smaller.

This gets the same effective block rate as now, but still means that miners can be rewarded for finding the (near) empty blocks.

You could do this with a soft fork but you would need at least 91% of the network to make it work.  A poll with only 10% of the hashing power would be able to create a fork that would be followed by older clients.

Each would have to embed in the coinbase a reference to a chain containing 9 mini-blocks.  Each mini block would have the same difficulty as the main chain block, but would be a header and a simple coinbase.

When a new block is found, miners would switch to trying to build 9 mini-blocks on top of it.  Once the nine have been found, they could build the next block.

90% of the tx + minting fees would have to be paid out to the mini-block's coinbases in order to keep things fair.

This reduces the incentive to add transactions though.  If you add a 1BTC fee transaction, you only get 0.1BTC.  This may result in some pools not bothering with full blocks.

System like this may work if the block reward is constant. People discovering miniblocks will get 1/10 of the reward. People discovering a main block will get 1/10 of the reward + transaction fee

[TierNolan]

System like this may work if the block reward is constant. People discovering miniblocks will get 1/10 of the reward. People discovering a main block will get 1/10 of the reward + transaction fee

That would work too.  The system breaks down when minting fees are less important.

With a soft-fork, the new block could have any rules for paying out to the mini-blocks.

Any share is possible, but the payout per hash should be around the same for both.

[gmaxwell]

As Maaku hints to, the a big reason Bitcoin has 10 minute blocks is because the variance is desirable. We need the variation in order to increase the allowed network radius/block processing time, the latency permitted for miners, and to control the incidence of long forks.  The only advantage to having lower variance without increasing the number of blocks would be reducing header traversal costs to link a block, but we know how to do secure header traversal now in logarithmic time in any case.

Progress freeness is also very important. You do not want to reward people super-linearly with their hashrate.