Decoupling transactions and POW

[TierNolan]

[edit]This is the latest suggestion, rather than the OP[/edit]

This is a soft fork that creates a sub-chain.  The benefit is that it allows the effective block rate to be reduced.  Full blocks would still occur every 10 minutes.

The process of finding the hash for a block inherently creates lots of lower POW headers for every actual block created.  These could be used to create a sub-chain to more quickly break ties and so allow faster confirms.

Current System

Normal blocks have a pointer to the previous (main chain) block in their header and all transactions included must be valid according to the rules.  If there were 4 normal blocks, then the chain would look like this:

Root <- A <- B <- C <- D

Miners create a new block E, which points to D as its previous block.  When they hit the target, they broadcast the block.

Updated System

Miners would create a valid (unsolved) "E" block and look at the merkle root.  If the 10 least significant bits of the merkle root are the same as the 10 least significant bits of D's hash, then the miner has a valid block (ignoring the POW requirement).  Otherwise, he scrambles the merkle root by updating the coinbase and checks again.  It would take on average 1024 attempts to get that to work.  This would be pretty fast even on a CPU.

This block can be mined as normal and it is broadcast if it meets the standard POW.

However, if he finds a solution that has at least 1/64 of the required POW, then he just broadcasts the header as a sub-chain block.  The header becomes block D1 instead of E.

Root <- A <- B <- C <- D <- D1

This requires updating the block so that it points to D1.  The previous block hash field would still point to D, but the lower 10 bits of the merkle root would point to D1.

On average there will be 64 sub-chain blocks per main chain block, so the chain would be something like

Root <- A <- B <- C <- D <- D1 <- D2 .... <- D71 <- E

The miner would also need to update his blocks when he receives new sub-chain broadcasts and when he finds sub-chain blocks.

POW Rules

The POW rules would be that a full block is worth 16 points and sub-chain blocks are worth 1 point.  The POW value of a point would be scaled according to the difficulty.

Rewards

The reward system is unchanged.  Only full blocks pay out minting and transaction fees.

Incentives

Miners have an incentive to build against the longest sub-chain.  On average there are 64 sub-chain blocks and that has a value of 4 full blocks.  However, as long as a miner is within 15 sub-chain blocks of the longest sub-chain, if they find a full block, they will still be the longest chain.  Mining pools might decide not to bother updating workers, as long as the workers are within 4-5 of the longest sub-chain.

Miners have little incentive to actually broadcast sub-chain links.  Only the miner who found the previous block (block D above) would have an incentive as it adds extra POW to his block.  However, the cost is very low.  They just have to broadcast 80 bytes. 

This is probably well within the level of altruism miners can be expected to have.  They are unlikely to update software to remove the feature, since it costs almost nothing and hardens the network.

Security

There are 3 security problems

Random Reversal

If a miner has 10% of the mining power and is 5 blocks behind, then the probability of a reversal is less than 1%.  Safety here is purely determined by the number of blocks. 

6 sub-chain confirms won't give the same level of confidence as 6 full blocks do now, but it would be reasonably secure.  The more miners try to ensure that they are building on the longest chain the better.

Brute Force Reversal

There is where someone buys/rents a large amount of hashing power in order to reverse a transaction.  If someone wants to reverse a 1000 BTC transaction, then they may be willing to pay up to 1000 BTC to do it.

The price of hashing is roughly 25 BTC for a block's worth of hashing.  This means that a merchant should wait 1000 / 25 = 40 full blocks for a 1000 BTC transaction, rather than the 6 blocks that is normally recommended.

Attackers who collectively have 1000 BTC at stake might be willing to pool their resources to brute force a reversal.

This attack is not affected by this proposal.  It would work just as well with or without a sub-chain.

Latency Triggered Collapse

This is where the block time is much lower than the network latency.

The incentives for miners are to broadcast their blocks as fast as possible.  Once you have broadcast your block, all other miners will then build on your block. 

However, it network latency is high, then that incentive is removed.  By the time you have broadcast your block, the network will have produced a new block anyway.  This prevents the majority of the hashing power working together to build a chain faster than a single miner who has a large single amount of hashing power.

If 90 miners had 1% each and one miner had 10%, then he can produce a chain faster than the 90%, since he doesn't have to worry about latency.

This is not an issue for the sub-chain, since the sub-chain blocks are only 80 bytes and the target rate is once every 10 seconds.  Even if the block rate went up to 10 per second, that is still only 800 bytes per second (and it would drop back down at the next difficulty re-targeting).

[jl2012]

This would be a hark fork or alt chain.

The idea would be to ban transaction except for every Nth block.  Almost all blocks are empty.

This allows speeding up the block generation rate, without needing lots of extra validation.

For example, if the block rate was 10 seconds but only every 60th block contained transactions, then the effective block rate would still only be one block every 10 minutes.

The merkle root in the other blocks could encode an address for fees to be paid.  These blocks would be 80 bytes forever.

The other blocks would be 80 bytes always.  No matter how many transactions the system is handling, most blocks would be tiny.  As time passes, network latency should become insignificant.

This means that random block chain reversions would be less like.  6 blocks would happen in 1 minute instead of 1 hour.

The payout would have to be split in some way.  A validator could submit a block and assign some of the fees to any miners who build on it.  There would be a trade-off.  Miners would build on the block with the most fees.

Validators could have something like reputation, which grows with time if they submit valid blocks.  Proof that they have submitted bad blocks would set their reputation back to zero.

Now the max block size is 1000KB. So why don't simply increase the generation rate by 60x to 10 seconds, and reduce the block size by 60x to 16.67KB? It sounds the same (except that some big transactions may not be included)

[scatha]

So why don't simply increase the generation rate by 60x to 10 seconds, and reduce the block size by 60x to 16.67KB? It sounds the same (except that some big transactions may not be included)

Wasn't that tested already with GeistGeld ? .. does anyone still experiment with that chain ?

[TierNolan]

Actually, this could be implemented as a soft fork.  

Part of the timestamp could be re-purposed as as extended previous field.  If a 256 range of seconds are assigned for this purpose, then that gives 8 bits for a prev field.  

Can ASIC miners modify the step size for their counters?  If so, then the nonce could be used directly.

The previous field of a block becomes

<hash of previous main chain block>:<Least significant byte of the hash of the aux chain header>

Only the headers matter.  There is no transaction verification on the parallel chain.  It is just to show processing is happening.

Alt chain headers are valid if they have at least 1/64th of the PoW of the main chain blocks and point to a previous block on the alt chain.

The process would be something like

Main Block A: Prev Z, LSB of hash = 62
- Header A-1: Prev A, LSB of hash = 31, LSB of timestamp = 62
- Header A-2-a: Prev A, LSB of hash = 191, LSB of timestamp = 31
- Header A-2-b: Prev A, LSB of hash = 101, LSB of timestamp = 31 (orphan, both valid though)
- Header A-3: Prev A, LSB of hash = 88, LSB of timestamp = 101
...
...
- Header A-26: Prev A, LSB of hash = 176, LSB of timestamp = 4


Main Block B, Prev A, LSB of hash 99, LSB of timestamp = 176

The sub-chain can never have more than 256 sub-blocks.  However, if the chain is that long it proves that at least 256 links were found.  Orphans are interchangeable, they just show that that step was reached, so as a length of 256 is reached, most alt-blocks would collide with other early steps.

Miners should not broadcast those ones.

Also, ties should be broken based on the length of the alt chain.

If a miners receives A->B->C and then gets C*, it should switch mining to C*, if C* has a longer alt chain lead in.

[TierNolan]

So why don't simply increase the generation rate by 60x to 10 seconds, and reduce the block size by 60x to 16.67KB? It sounds the same (except that some big transactions may not be included)

It means that most blocks are kept fixed size and don't require validation (other than verifying the sha hash).  Transactions can be aggregated in a 10 minute period.

[jl2012]

So why don't simply increase the generation rate by 60x to 10 seconds, and reduce the block size by 60x to 16.67KB? It sounds the same (except that some big transactions may not be included)

It means that most blocks are kept fixed size and don't require validation (other than verifying the sha hash).  Transactions can be aggregated in a 10 minute period.

I think the total bandwidth and CPU usage are just exactly the same

[TierNolan]

I think the total bandwidth and CPU usage are just exactly the same

Yes, but latency matters less.  Latency seems to be what causes the big objections to faster blocks.

However, latency is mostly bandwidth anyway.

[🏰 TradeFortress 🏰]

Validators could have something like reputation, which grows with time if they submit valid blocks.  Proof that they have submitted bad blocks would set their reputation back to zero.

And how are you going to do this with a decentralized system?

[TierNolan]

And how are you going to do this with a decentralized system?

Perhaps an alt chain or something.  A validator can create initial reputation by submitting proof of work to the alt chain.

Validators can then "stamp" blocks as valid.  However, if another node then proves the block is wrong, then the validator's reputation goes to zero.

The updated proposal doesn't decouple things though, it works as now, just there are extra block headers being published.

[TierNolan]

I think the rule should be that main blocks didn't count anything extra for proof of work.  Any block with better than 1/64th of the standard POW requirement would count.

Effectively, what this does is break ties much more quickly than currently.  If there are 2 blocks found at around the same time, after 1/64th of the block time, most of the hashing power would know which one to switch to, rather than having to wait.

The maximum POW between two main chain blocks would be limited to 256 links on the parallel chain.  Assuming the parallel chain has 64 times lower POW, the odds of 256 links being added is (63 / 64) ^ 256 = 1.8%, so it wouldn't happen very often.  If it did happen that block would probably be locked in anyway.

Alt headers more than a few hundred blocks old wouldn't have to be stored.  This is just to quickly lock the mining horsepower onto a particular block.  New miners can just download the block chain as normal and can scan the parallel chain once the next full block arrives.

An even less complex version would be just for miners to count the number reduced POW headers found for all equal height blocks, and mine against the one with the most hits.

[Maged]

Not too bad. This would even allow us to quickly resolve attacks by minority attackers, such as a 49% attack.

[jl2012]

Actually, this could be implemented as a soft fork.  

Part of the timestamp could be re-purposed as as extended previous field.  If a 256 range of seconds are assigned for this purpose, then that gives 8 bits for a prev field.  

Can ASIC miners modify the step size for their counters?  If so, then the nonce could be used directly.

The previous field of a block becomes

<hash of previous main chain block>:<Least significant byte of the hash of the aux chain header>

Only the headers matter.  There is no transaction verification on the parallel chain.  It is just to show processing is happening.

Alt chain headers are valid if they have at least 1/64th of the PoW of the main chain blocks and point to a previous block on the alt chain.

The process would be something like

Main Block A: Prev Z, LSB of hash = 62
- Header A-1: Prev A, LSB of hash = 31, LSB of timestamp = 62
- Header A-2-a: Prev A, LSB of hash = 191, LSB of timestamp = 31
- Header A-2-b: Prev A, LSB of hash = 101, LSB of timestamp = 31 (orphan, both valid though)
- Header A-3: Prev A, LSB of hash = 88, LSB of timestamp = 101
...
...
- Header A-26: Prev A, LSB of hash = 176, LSB of timestamp = 4


Main Block B, Prev A, LSB of hash 99, LSB of timestamp = 176

The sub-chain can never have more than 256 sub-blocks.  However, if the chain is that long it proves that at least 256 links were found.  Orphans are interchangeable, they just show that that step was reached, so as a length of 256 is reached, most alt-blocks would collide with other early steps.

Miners should not broadcast those ones.

Also, ties should be broken based on the length of the alt chain.

If a miners receives A->B->C and then gets C*, it should switch mining to C*, if C* has a longer alt chain lead in.

How could you distribute reward if 2 sub-blocks with the same LSBs for hash and timestamp were found?

[TierNolan]

How could you distribute reward if 2 sub-blocks with the same LSBs for hash and timestamp were found?

There's no reward.  The idea is that miners would broadcast hits.  The cost is tiny, it is just 80 more bytes to send.

Collisions aren't really that big a deal, if there are 2 hits, then that link has 2 possible paths, but it doesn't matter which you follow.

[jl2012]

How could you distribute reward if 2 sub-blocks with the same LSBs for hash and timestamp were found?

There's no reward.  The idea is that miners would broadcast hits.  The cost is tiny, it is just 80 more bytes to send.

Collisions aren't really that big a deal, if there are 2 hits, then that link has 2 possible paths, but it doesn't matter which you follow.

Does it mean the miners will mine as normal? If the Hash < Target, it'll be a main block. If the Target < Hash < Target*64, it'll be a sub block. Am I correct?

[TierNolan]

Does it mean the miners will mine as normal? If the Hash < Target, it'll be a main block. If the Target < Hash < Target*64, it'll be a sub block. Am I correct?

Right, a pool could just check all returned shares.  If the share target is less than 1/64 of the main chain difficulty, then they don't even need to change that.

I was thinking than an improvement would be to use the merkle root as part of the reverse link.

Header A builds on Header B if
- they both have the same previous full block or B has A as its previous block
- The N LSBs of B's merkle root match the hash of A

By using the extra nonce, the pool can set the least significant bytes of the merkle root to anything they want.  If N = 16 bits was used, this would require on average 64k hashes * merkle depth attempts by the pool.  This could probably be done in software, but is maybe a little heavy.

This would keep collisions to a minimum.  They don't really cause that much of a problem.  Once a new block is found, they are mostly a tie breaking rule.

Sub-chain length probabilities

<= 64: 63.5%
<= 256: 98.23%
<= 512: 99.97%
<= 1024: 99.99999%

So, 1024 would mean that the sub-chain would almost never saturate the previous link field.  Using a single byte would mean around every 50 - 100 blocks, the sub-chain would be saturated.

Full difficulty blocks would be worth 256 points and 1/64 difficulty headers would be worth 1 point.  Miners should build against the longest chain.

This means that the sub-chain is only really used to break ties.  To reverse a full block would require 256 links on the sub-chain.  This requires 4X as much hashing as just creating an alternative block.

Blocks more than 1024 full blocks from the end of the chain are 128 points and 1/64 difficulty headers are worth nothing.  This allows old low difficulty headers to be discarded after a while.  A split more than 1024 blocks deep is already a major fork anyway.

Since there is no reward for broadcasting, the incentives to broadcast are different than for main chain blocks.  Keeping a header back, means you can publish both that header and your new block at once.  This instantly breaks any orphan tie in your favor.  However, that is only useful if your block would have been orphaned otherwise.

Assuming a 1% orphan rate for main blocks, then holding back the header will increase revenue by at most 1%.  In addition, the header is only worth something if nobody else finds a sub-chain header in the meantime, since if that happens, the public sub-chain has the same POW as your secret one.  The odds of the next block happening before the next sub-chain header is 1 in 64.  This means net benefit of holding back is 1/64 of 1%.

Given that mining pools can't be bothered to update the transaction inclusion rules by much, it is likely that a significant fraction wouldn't bother changing their code to hold back the sub-chain headers.

[jl2012]

Really interesting. In this case 2 confirmations in main chain would be more than enough.

Is it a soft-fork? I think it is also transparent to users if they are not mining.

[TierNolan]

Really interesting. In this case 2 confirmations in main chain would be more than enough.

6 sub-chain confirmations would be strong evidence that the block is locked down.

Is it a soft-fork? I think it is also transparent to users if they are not mining.

Yes.  However, it would have to get into a portion of client software so that miners have to stick to it.

One problem is that the larger the reward for a full block, the less valuable the sub-chain confirms are. 

If main blocks are less valuable, then there is strong encouragement to build on the longest sub-chain, but greater incentive to not publish the sub-chain links.

256 goes on the side of encouraging publishing header.  This means 75% of the POW is the main chain blocks.  If the main blocks were worth 16 points, then 75% of the POW would be on the sub-chain.  This creates an incentive to hold back blocks, but more of an incentive to build on the longest sub-chain.

With 16 points, a longer sub-chain could outweigh a chain with more main chain blocks.  On average, there would be 64 sub-chain links per main chain link.

Having said that, assuming the orphan rate is reasonably low, there is pretty low incentives to hold back.

[organofcorti]

Can you explain what problem you're trying to solve? I'm not following (this is not your fault, it's just an area in which I need some education )

[TierNolan]

If you have a transaction that is 100 blocks deep in the chain, it is very unlikely that it will be reversed.

If someone wants to reverse the transaction, they have to fork the chain before the transaction and then catch up and pass out the main chain.  If they have 10% of the hashing power, the main chain will get around 10 blocks for every block they add to their alt chain, on average.  The most likely outcome is that their alt chain just falls further and further behind and all the hashing goes to waste.

They could get extremely lucky and find 150 blocks before the main chain finds 50 blocks, so they pull ahead, but it is very unlikely.

The more blocks added after your transaction, the harder it is for the chain to be reversed by someone with less than 50% of the hashing power.  It turns out that it doesn't matter how fast the blocks are for this effect to happen.

As long as network latency is low relative to the block rate, the block rate should be as fast as possible.  If there is a block once every 10 seconds, then you only need to wait 1 minute to get the same protection as you currently get in 1 hour.

The proposal is to have sub-chain links.  This is a backward compatible change.  Increasing the block rate of the main chain is a major change that would not be accepted by old clients. 

The sub-chain has very simple verification and you only have to send the header.  This keep latency low, which compensates for the faster chain rate.

The disadvantage is that only every 64th fast block (on average) can actually include transactions.  You get the 10 second per block rate, but it takes 5 minutes on average until the next main block and then 50 seconds for 5 sub-chain blocks.  This gives 11 minutes on average instead of 60.

For even faster confirms, you could verify that your transaction is included in the sub-chain.  If you contact a pool, they could tell you which sub-chain blocks they own and prove that they included your transaction.  This would allow you verify that at least some miners are adding your transaction into the next block. 

[organofcorti]

Thanks for the explanation. I think I mostly understand what you propose, but I don't understand some of the mechanics of how the tx free blocks are generated - what's the proof of work? Also, how is does a block become a tx block?