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

[1715482346]

1715482346

[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?

[TierNolan]

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?

They are the same as normal blocks.

Each block header has a merkle root in it.  This can be scrambled by changing an ignored field in the coinbase transaction.

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.  So, if there were 4 normal blocks, then the chain would look like this:

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

A miner would then 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.

He then tries to solve the block as normal, by submitting it whatever hashing power he has available.

If he solves the block to normal difficulty, then the block becomes block E and he broadcasts it to the network, as normal.

If he solves it to 1/64 of the difficulty, then he broadcasts just the header as a sub-chain block.

This is a valid sub-chain link, since it points at D and the LSBs of the merkle root match D's.  It is now block D1, instead of E.

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

He then has to update his header.  He keeps it pointing at D, but now he has to get the LSBs of the merkle root to match D1's instead.  The main previous is still to D, but the 10-bit reference points to D1.  This is still a candidate E block but also a candidate D2 block.  It is a valid E block according to the standard chain link rules too.

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 header if other miners broadcast their headers.  That would happen about once every 10 seconds.  If he doesn't then his blocks would lose orphan tie breaks.

[organofcorti]

Thanks for taking the time to explain that in a way I could follow. One other question - how do you suggest the block reward be distributed? Every block, or only in blocks with tx fees?

[TierNolan]

One other question - how do you suggest the block reward be distributed? Every block, or only in blocks with tx fees?

To keep it backward compatible, it has to be main blocks only.

However, a rule like p2pool could be used to pay for the sub-links.  A main block which doesn't pay to the sublinks would not count.

As I said, I think the fee isn't required.  The incentive not to broadcast is pretty low.

[jl2012]

What's the implication for mining pools? Do they need to communicate with miner much frequently?

[TierNolan]

What's the implication for mining pools? Do they need to communicate with miner much frequently?

The header target would update around once every 10 seconds.  However, other than that, there is almost no change.  Pools already tell their clients that the difficulty is much lower than it really is.

If they set it to 1/1024, then clients would send in all block headers that are better than 1/1024 difficulty and then the pool would select the ones that are better than 1/64 for the sub-chain.

Smart miners would have to be told what the merkle root rule is, so they can generate valid headers.  This is a 10-bit number that they would need to be told about every 10 seconds.  Normal clients would be told an 80 byte header target every 10 seconds.

If the main chain block reward is 16 points, then not participating the sub-chain could get their blocks orphaned with high probability, even if they distribute their block to 100% of the network first.

[kjj]

I'm pretty sure this would lead to more forks, not less.  The time between sub-blocks is short relative to network latency, so the sub-chain would be wildly more divergent than the current blockchain.  Essentially, pockets of miners would be working on their own sub-chains, with no way to reconcile with the broad network until a real block hit.  At best, it would be pointless, at worst, it would lead to chaos.

[Deafboy]

This does not make any sense.
Faster (lower difficulty) blocks = less secure blocks.

[TierNolan]

This does not make any sense.
Faster (lower difficulty) blocks = less secure blocks.

There are 3 security problems

1) Random reversal

This is the where a fork manages to overtake the main chain due to luck.  If the fork has 10% of the hashing power and is 5 blocks behind, then the odds of it ever overtaking the main block is 0.1%.

This is where the 6 confirms rule comes into things.  After 6 confirms, the transaction is assumed mostly safe from reversal.

2) Brute forcing the new fork

This is where someone throws lots of hashing power at the problem.  The value of 50% of the hashing power of the network would be related to the minting and tx fees being paid.

If you have a 1000 BTC transaction, then you should wait at least 1000 / 25 blocks before considering it confirmed.  If you don't, in theory, someone could pay 1000 BTC for an alt chain. 

That assumes that there is enough non-bitcoin hashing power available to win the race.  I don't think the current client does this calculation.

3) Latency

If block propagation latency is high relative to the block time, then it is in the best interests on a miner not to propagate their block.  The only reason to propagate is to get other miners to start building on your block.  If it is to slow, then you should hold it back.  That way you get to build on a longer chain than everyone else.  The end result is all miners hold back their chains and thus the most powerful single miner ends up with the longest chain.  This is why the block rate is 10 minutes.

----------------------------

If your transaction is low value, say < 1 BTC, then problem 2 is not a problem.  Even after 1 confirmation, it wouldn't be worth it to reverse your transaction.

Therefore, problems 1 and 3 are the most important for fast-confirmation applications. 

The latency problem is helped because the sub-chain is only 80 bytes to propagate per block, so can be very fast.  Also, propagation is helped because it is fast to confirm (you don't have to check the transactions referred to by the merkle root are valid).

The main problem is therefore random reversals.  This has nothing to do with the total POW.  The more blocks the better, as long as latency is kept low.  The subchain achieves that, though not quite as well as a very fast chain would, but it suffers less from latency,

[doobadoo]

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.

Bitcoin txns are based on proof not trust, or reputation.

Substituting trust for proof will give bad results.

Why exactly would you mine a bunch of non tx blocks?  is this designed to create more block reward events so that coins can be distributed to solo miners? 

Or are you trying to create more movements of nature so that the tx window happens closer to 10 minutes.

You know i often wondered if the Poisson distribution of block generation time could be fixed by expanding the degrees of freedom of the hash algo.  The hash algo looks for 1 none (one movement of nature).  If it were to look for many nonces (say 32), we'd get much closer to 10 minutes.  We certainly wouldn't have 1% of blocks being found in less than 10 sec.

Not to hijack the thread, but would simply changing the algo to:

1)  A sha256 hash below the difficulty target
2) A sha256(sha256) below 50%, iterated 31

Thus a correct hash would have an initial hash less than the target, and then a (1/2)^31 chance of having successive hashes being values less than the median of the potential output range of sha256.

Could this "successive" hash requirement accomplish the same thing?  Getting the hash window closer to a 10 minute average?

[TierNolan]

Bitcoin txns are based on proof not trust, or reputation.

Substituting trust for proof will give bad results.

The validator thing isn't part of the updated proposal.

If someone pays some BTC to become a validator and they lose their status if they lie, then that creates an incentive not to lie.

The validators were just to get fast answers.  It would be coupled with a way to prove that they are wrong.  If someone submits proof, then it would cancel the validator's status.

1)  A sha256 hash below the difficulty target
2) A sha256(sha256) below 50%, iterated 31

The reason for the proposal was to have faster sub-blocks.  This is because you need at least 6 blocks, no matter what their difficulty to protect against random double spends.  It wasn't to help pools have lower variance.

However, your proposal is interesting.  Maybe it could be used by pool. 

I was thinking of something much more complex for the problem.

[organofcorti]

Or are you trying to create more movements of nature so that the tx window happens closer to 10 minutes.

You know i often wondered if the Poisson distribution of block generation time could be fixed by expanding the degrees of freedom of the hash algo.  The hash algo looks for 1 none (one movement of nature).  If it were to look for many nonces (say 32), we'd get much closer to 10 minutes.  We certainly wouldn't have 1% of blocks being found in less than 10 sec.

Not to hijack the thread, but would simply changing the algo to:

1)  A sha256 hash below the difficulty target
2) A sha256(sha256) below 50%, iterated 31

Thus a correct hash would have an initial hash less than the target, and then a (1/2)^31 chance of having successive hashes being values less than the median of the potential output range of sha256.

Could this "successive" hash requirement accomplish the same thing?  Getting the hash window closer to a 10 minute average?

Are you suggesting that the current method of block finding be replaced by the above? So in order to solve a block you need to have a sha256 below target and then 31 x sha256(sha256()) below median.

Unless I misunderstand you, that's still a single probability for any given target. This means that solving a block is still bernoulli trial, so the times between block solves will be exponentially distributed (with a varying lambda for hashrate changes) and the number of blocks solved in any given time period will still be a non-homogenous poisson process.

If you want the distribution of the non-homogenous Poisson process to be less widely distributed you have to increase lambda - more blocks in a given time period.

Unless I misunderstand what you mean, in which I'd really like to understand what you mean.

[TierNolan]

Unless I misunderstand you, that's still a single probability for any given target. This means that solving a block is still bernoulli trial, so the times between block solves will be exponentially distributed (with a varying lambda for hashrate changes) and the number of blocks solved in any given time period will still be a non-homogenous poisson process.

He suggested extra nonces.  I think he meant the process to be:

h[0] = hash(header)
h[1] = hash(h[0];n[1])
h[2] = hash(h[1];n[2])
....
h[31] = hash(h[30];n[2])

You send the block and also n[1] to n[31].

You can solve the block by solving h[0] < difficulty and then h[1] < difficulty.

The nonces would have to be made larger though.  Maybe variable length byte arrays could be used.

[organofcorti]

Unless I misunderstand you, that's still a single probability for any given target. This means that solving a block is still bernoulli trial, so the times between block solves will be exponentially distributed (with a varying lambda for hashrate changes) and the number of blocks solved in any given time period will still be a non-homogenous poisson process.

He suggested extra nonces.  I think he meant the process to be:

h[0] = hash(header)
h[1] = hash(h[0];n[1])
h[2] = hash(h[1];n[2])
....
h[31] = hash(h[30];n[2])

You send the block and also n[1] to n[31].

You can solve the block by solving h[0] < difficulty and then h[1] < difficulty.

The nonces would have to be made larger though.  Maybe variable length byte arrays could be used.

In your notation, what I thought he means:

if
h[0] < target & h[31] < median of possible sha256 hashes
then
block solved

This still only has one probability, which will only vary with the target and not with each block. This means the process will have no effect on the distribution of block solve times.

[TierNolan]

This still only has one probability, which will only vary with the target and not with each block. This means the process will have no effect on the distribution of block solve times.

Yeah, inherently, new nonces are needed so you can do it one step at a time.

[TierNolan]

An even larger extension to this would be to have the sub-chain made up of single transactions.

You get your transaction into that sub-chain and it is locked down.

The sub-chain links would only check that there is no double spending.  This still requires RAM, but at least no elliptic curve crypt or script checks.

The next full block would include all valid transactions, in the order that they appear in the sub-chain.  The 2nd double spent transaction and any transaction without valid crypt or script would be skipped.

The chain would effectively be

F = full block
E = easy header
T = transaction

F <- T <- T ... <- T <- E <- T <- T <- ... T <- F

The reputation system could be used to prevent transaction spam.  A merchant could create an id that is cancelled if any invalid transactions are submitted.

A simple (low security) way to do it would be to find a random number that hashes to some difficulty and publish the result.

A transaction link would then include
- merchant id
- random number that hashes to the target
- hash(new random number)

This would count as submitting the transaction and also redirecting the "token" to the new random number.

A dishonest node could change the merchant id and target.  However, assuming most of the network are honest, the honest tx will be the one to make it into the sub-sub chain.

The key is to keep verification as simple as possible.

[doobadoo]

Are you suggesting that the current method of block finding be replaced by the above? So in order to solve a block you need to have a sha256 below target and then 31 x sha256(sha256()) below median.

Yes, and admittedly, i'm not sure it accomplishes what i want.  I just dont want to expand the size of the block header by say 600 bytes  (32 nonces ~ 20 bytes each)

Unless I misunderstand you, that's still a single probability for any given target. This means that solving a block is still bernoulli trial, so the times between block solves will be exponentially distributed (with a varying lambda for hashrate changes) and the number of blocks solved in any given time period will still be a non-homogenous poisson process.

your probably right, the nonce is where the entropy comes from, without an increase in entropy inside the system, nothing has actually happened (corollary to 2nd thermodynamic law).

We need more probability trials to take place during the block generation to move the mean closer to 10 minutes.  I just figured that by finding a correct initial hash (target within limited intereval), then feeding that into sha256 as if it were a nonce, i would be creating a second trial.  But if trial 2 is not independent of the outcome of trial 1 then we are in the same event.

If you want the distribution of the non-homogenous Poisson process to be less widely distributed you have to increase lambda - more blocks in a given time period.

Unless I misunderstand what you mean, in which I'd really like to understand what you mean.

No, thats what i mean, but you wouldn't have to publish the result hashes in the header, just the nonces and maybe the last hash.

Sha256 (prev-block-hash + N0) < target = H1
sha256(H1 + N1) < target = H 2
...
Sha256 (H31 + Tx Merkle Root + Time Stamp ... + N31) < target

my only concern is that you might have to publish N0-N31, which would add like hundreds of bytes to headers...unless that's trivial with broadband.  

Heck, just increasing the trials to 10 would do half the job. Is it worth 100-200 bytes extra header weight?

[organofcorti]

We need more probability trials to take place during the block generation to move the mean closer to 10 minutes.  I just figured that by finding a correct initial hash (target within limited intereval), then feeding that into sha256 as if it were a nonce, i would be creating a second trial.  But if trial 2 is not independent of the outcome of trial 1 then we are in the same event.

The mean is already 10 minutes - you mean reduce the standard deviation? Then, yes, you need multiple independent trials. But you really don't want to make the block arrival time more predictable for reasons I outline below.

An even larger extension to this would be to have the sub-chain made up of single transactions.

The subchain is really just the main chain with only one tx instead of many, right?

If you assign every nth block to be a full block, you have the problem that the standard deviation of the expected arrival time of the full block is now much lower.

There are two cases which are of interest.


1. When the generated bitcoin value of the full tx block is approximately that of the 1 tx blocks (as would be the case currently), then there is little disincentive for miners to mine the 1 tx blocks. However you have the problem that since all blocks are part of the main chain, the solving full tx block is still more likely to be an orphan race, which will encourage fewer tx to be included in the block.

Solution: Mandate a minimum block size. However, then each tx block is more likely to be an orphan than a 1tx block. If electricity costs are high, then it may be the case that some hashes will have a negative expected value, so you're discentivising (is that a word?) tx block creation.

2. When the value of full tx block is much greater than that of the 1 tx blocks then there is incentive not to mine the 1tx blocks. If the standard deviation of the arrival time of the full tx block is reduced and electricity costs are appreciable then it's possible to act to increase the expected value of each hash by not working on 1tx blocks.

Solutions:
a. Make the probability of any block to be a full tx block be p.
If p does not vary, then there is no disincentive to mine the 1tx blocks but the time between full tx blocks is back to being exponentially distributed.
If p varies, then you have a trade off between the variation of the expected value of a hash and the distribution of the times between blocks. However any variation in the expected value of a hash will invite abuse.

b. Make every nth block a full tx block, but distribute the tx fees in some fashion so that the creator of tx block and the creators of the next n-1 blocks have some share of the fees. This has been covered elsewhere, and there are a number of ways this can be achieved.


I think a good summary is:
1. If that if you make the expected value of a block vary (either by reward or the likelihood of it being orphaned), and
2. Electricity costs are significant so that shutting down your mining device is more rewarding than mining, then
3. The expected value of each hash varies and some blocks are more likely to be mined than others. So,
4. If t = the critical time at which the expected value of a hash worth either more or less, and
5. You make t more predictable, then
6. You provide a way to allow miners to maximise their earnings by shutting down their mining devices until the expected value of a share is positive again.

So you need to make each block equal in size and reward to each other block. This means that if you want a simple and provably fair system, you can't have sub chains - each block in the chain must be equal in value and similar in size to every other block in the chain or hashes will not have equal expected values of generated bitcoin.

I might still not be fully understanding what you meant, but if I have then I'm pretty sure my conclusions are solid.

 

[TierNolan]

An even larger extension to this would be to have the sub-chain made up of single transactions.

The subchain is really just the main chain with only one tx instead of many, right?

I was thinking that transactions would specify the hash of the previous transaction or an easy header.

In this case the sub-chain is made up of full blocks, easy blocks (otherwise valid full block headers that have lower POW) and transactions.

If you assign every nth block to be a full block, you have the problem that the standard deviation of the expected arrival time of the full block is now much lower.

It isn't every nth block, it is every nth block on average.  Effectively, the sub-chain is merge mined.

1. When the generated bitcoin value of the full tx block is approximately that of the 1 tx blocks (as would be the case currently), then there is little disincentive for miners to mine the 1 tx blocks. However you have the problem that since all blocks are part of the main chain, the solving full tx block is still more likely to be an orphan race, which will encourage fewer tx to be included in the block.

There is no bitcoin generated by anything other than full blocks.  Otherwise, it is a change that isn't backwards compatible.

The transactions will have a tx fee though.  The higher your fee the more likely others will build on your tx.

Solution: Mandate a minimum block size. However, then each tx block is more likely to be an orphan than a 1tx block. If electricity costs are high, then it may be the case that some hashes will have a negative expected value, so you're discentivising (is that a word?) tx block creation.

Miners don't mine the tx chain.  That would effectively be paid for by tx fees.

It is in the best interests of merchants/customers to add their tx to the longest chain, since that will inherently have the highest fees.  Some merchants might decide not to build on zero fee transactions.

As I said there is a trade-off.  You can make full blocks worth more than easy headers.  Similarly, easy headers would be worth more than transactions.

2. When the value of full tx block is much greater than that of the 1 tx blocks then there is incentive not to mine the 1tx blocks.

Right, but they are paid by the tx fee.

Solutions:
a. Make the probability of any block to be a full tx block be p.

The easy blocks work that way.

If p does not vary, then there is no disincentive to mine the 1tx blocks but the time between full tx blocks is back to being exponentially distributed.

Right, I don't really see how you could get it to work otherwise.

If p varies, then you have a trade off between the variation of the expected value of a hash and the distribution of the times between blocks. However any variation in the expected value of a hash will invite abuse.

If the easy headers are valid main blocks, except with lower difficulty, then the variance can't be fixed anyway.

I think a good summary is:
1. If that if you make the expected value of a block vary (either by reward or the likelihood of it being orphaned), and

Probably the orphaned thing would be the only option that is backward compatible.

2. Electricity costs are significant so that shutting down your mining device is more rewarding than mining, then

Another option would be cooling.  For example, the server room could be cooled at a constant rate, so on average a certain amount of electricity is used.  However, you can burst a lot of extra heating.

So you need to make each block equal in size and reward to each other block. This means that if you want a simple and provably fair system, you can't have sub chains - each block in the chain must be equal in value and similar in size to every other block in the chain or hashes will not have equal expected values of generated bitcoin.

I might still not be fully understanding what you meant, but if I have then I'm pretty sure my conclusions are solid.

I think the problem is that the thread is discussing different objectives.  I don't think main block variance is that important.

The sub-chain was mainly to allow transaction ordering to be guaranteed, even before the next easy block, in order to protect against double spends.

Having a transaction chain locks that down pretty quickly.  A transaction could optionally specify a previous transactions and is only valid if all transactions in the transaction chain back to the previous main block are included, except those that are invalid for some reason.  No checking would be performed except hashes.

In fact, with that system, easy blocks could almost be dropped entirely.  Your client keeps track of the transaction chain and keeps trying to submit the transactions with a different previous link until it wins.  That still requires large bandwidth per client though, as the tx rate increases.

Maybe the merchant submits to a provider that keeps up with the block chain.  The provider doesn't have to check chain authenticity, they just need to check hash links.

[organofcorti]

I think I really haven't understood what your goal is or how you're achieving it. Sorry about that. And I thought the idea of making the tx blocks appear more regularly was a goal? Never mind, must have had my wires crossed.

[TierNolan]

I think I really haven't understood what your goal is or how you're achieving it. Sorry about that. And I thought the idea of making the tx blocks appear more regularly was a goal? Never mind, must have had my wires crossed.

The goal is to allow faster confirmations.

You inherently need 6 blocks after a transaction to consider it confirmed.

The main proposal is that when miners find a a block that is 1/64 th of the required difficulty, they publish that header.

A tweak to merkle root rules allows a miner to specify a previous sub-chain header.  This is done before they start mining it.

If they hit the main difficulty, then it is a standard compliant main chain header.

This gives a sub-chain with a 64X block rate, so it takes 1 minute for 6 confirms.

There is a tradeoff in how you do rewards.  If the sub-chain blocks count as the same POW as the main chain blocks, then publishing sub-chain headers is poor strategy.  If you keep them to yourself, you can publish them and your final block as a single unit, and it massively strengthens your block's effective POW.  If you publish a main block + 7 sub-blocks, your block jumps forward 8 steps.  The miner with the most total power would win nearly every main block.

However, if you make the sub-chain links to cheap, then it doesn't have any strength to maintain ordering.

I think 16 points of POW for a main chain block and 1 point of POW for a sub-chain block seems reasonable.  That gives only a weak incentive to withhold sub-chain blocks.  As long as a miner with within 16 sub-chain links of the head of the chain, their main block will jump to the front of the queue.  Miners who have to be able to mine 16 sub-blocks before the others can mine 16 before they can win by withholding blocks.

It actually means that you need 16 (+6?) sub-chain blocks to be sure of a confirmation, so 2.5 minutes.

Maybe 4 points for a main chain block would be better, in that case.  Withholding is only worth it if you can generate 4 sub-chain blocks before the rest of the network can generate 4. 

However, there is a danger.  If most miners withhold their sub-chain blocks, then honest miners are harmed.

Since miners tend to be mining most blocks, another reason to publish sub-chain blocks is to lock in your block reward.  If a miner won a block 10 blocks back, they would want to keep it locked in, so they don't lose their coinbase transaction.

The second proposal/extension is to have transactions also form a chain.  You can only incorporate a transaction into a block if there is a chain from the previous main block through the transaction to the new block.

Giving it more thought, maybe only certain transactions would be marked with the fast flag.  If you are willing to wait for 6 confirmations, then don't bother flooding the fast transaction chain.