Dynamic block frequency

[nybble41]

As someone that knows a little bit about CPUs and digital logic, I can promise you that the right shift operation is not done by divide-and-round, it is done in dedicated hardware called a shifter that literally shifts bits.  It might be harder for laymen to understand, but programmers (and CPUs) understand shift very literally.

Look, we're not going to get anywhere if you keep misinterpreting what I say. Of course how a CPU physically does a bit shift is completely different from how it does integer division. That's why I said it's faster.

Actually, they're not implemented all that differently. True, shifts are not implemented via division; it's the other way around. Division can be implemented in hardware as a series of right-shift and subtract operations (a naive binary version of long division), and division by two reduces to a simple right-shift, though there may be some wasted cycles. For that reason, any decent optimizing compiler will generate the opcode for a right-shift operation rather than integer division when the code specifies integer division by a fixed power of two. As you said, it's exactly the same mathematical operation. The compiler is just unrolling the loop implied by the division algorithm.

Your proposal is interesting, and I agree the confirmation time is definitely a point of some friction. I like litecoin's 2.5 minute target, but even that could get unrealistically large for things like high frequency trading.

The system isn't going to do any magic. Too frequent blocks will cause excessive forking, so some things will just have to be done with layers on top of Bitcoin.

Would it be possible to re-integrate the forks instead, provided there are no conflicting transactions? It should be rare to have forks which cannot be reconciled. Example:

Chain 1: A(t1, t2) -> B(t3, t4)
Chain 2: A(t1, t2) -> C(t3, t5, t6)
Next: A(t1, t2) -> {B(t3, t4), C(t3, t5, t6)} -> D(t7)

Instead of a single parent, Block D would list the heads of all the chains its compatible with. The height would be the maximum along any path from the genesis block (i.e. height(D) = height(A) + max(difficulty(B, C))). In the event of conflicting transactions, it would be up to the miner of block D to choose a non-conflicting subset of the available chains.

[Meni Rosenfeld]

Your proposal is interesting, and I agree the confirmation time is definitely a point of some friction. I like litecoin's 2.5 minute target, but even that could get unrealistically large for things like high frequency trading.

The system isn't going to do any magic. Too frequent blocks will cause excessive forking, so some things will just have to be done with layers on top of Bitcoin.

Would it be possible to re-integrate the forks instead, provided there are no conflicting transactions? It should be rare to have forks which cannot be reconciled. Example:

Chain 1: A(t1, t2) -> B(t3, t4)
Chain 2: A(t1, t2) -> C(t3, t5, t6)
Next: A(t1, t2) -> {B(t3, t4), C(t3, t5, t6)} -> D(t7)

Instead of a single parent, Block D would list the heads of all the chains its compatible with. The height would be the maximum along any path from the genesis block (i.e. height(D) = height(A) + max(difficulty(B, C))). In the event of conflicting transactions, it would be up to the miner of block D to choose a non-conflicting subset of the available chains.

There has been talk here about doing pretty much this. Maged has a few ideas how it would work. It would be interesting to see how to combine the ideas of dynamic block times and a different graph structure for the blockchain.

[nybble41]

Your proposal is interesting, and I agree the confirmation time is definitely a point of some friction. I like litecoin's 2.5 minute target, but even that could get unrealistically large for things like high frequency trading.

The system isn't going to do any magic. Too frequent blocks will cause excessive forking, so some things will just have to be done with layers on top of Bitcoin.

Would it be possible to re-integrate the forks instead, provided there are no conflicting transactions? It should be rare to have forks which cannot be reconciled. Example:

Chain 1: A(t1, t2) -> B(t3, t4)
Chain 2: A(t1, t2) -> C(t3, t5, t6)
Next: A(t1, t2) -> {B(t3, t4), C(t3, t5, t6)} -> D(t7)

Instead of a single parent, Block D would list the heads of all the chains its compatible with. The height would be the maximum along any path from the genesis block (i.e. height(D) = height(A) + max(difficulty(B, C))). In the event of conflicting transactions, it would be up to the miner of block D to choose a non-conflicting subset of the available chains.

There has been talk here about doing pretty much this. Maged has a few ideas how it would work. It would be interesting to see how to combine the ideas of dynamic block times and a different graph structure for the blockchain.

There is a serious problem with reintegration which I didn't consider before: the fees and block rewards will inevitably conflict between the different chains. Assuming B and C were discovered by different miners, the fee for transaction t3 in block B would conflict with the fee for the same transaction in block C, and the {B,C} set, while still representing only a single link in the chain, would have double the combined block reward.

[Meni Rosenfeld]

Your proposal is interesting, and I agree the confirmation time is definitely a point of some friction. I like litecoin's 2.5 minute target, but even that could get unrealistically large for things like high frequency trading.

The system isn't going to do any magic. Too frequent blocks will cause excessive forking, so some things will just have to be done with layers on top of Bitcoin.

Would it be possible to re-integrate the forks instead, provided there are no conflicting transactions? It should be rare to have forks which cannot be reconciled. Example:

Chain 1: A(t1, t2) -> B(t3, t4)
Chain 2: A(t1, t2) -> C(t3, t5, t6)
Next: A(t1, t2) -> {B(t3, t4), C(t3, t5, t6)} -> D(t7)

Instead of a single parent, Block D would list the heads of all the chains its compatible with. The height would be the maximum along any path from the genesis block (i.e. height(D) = height(A) + max(difficulty(B, C))). In the event of conflicting transactions, it would be up to the miner of block D to choose a non-conflicting subset of the available chains.

There has been talk here about doing pretty much this. Maged has a few ideas how it would work. It would be interesting to see how to combine the ideas of dynamic block times and a different graph structure for the blockchain.

There is a serious problem with reintegration which I didn't consider before: the fees and block rewards will inevitably conflict between the different chains. Assuming B and C were discovered by different miners, the fee for transaction t3 in block B would conflict with the fee for the same transaction in block C, and the {B,C} set, while still representing only a single link in the chain, would have double the combined block reward.

I think the rewards can be split between the referenced blocks one way or another.

[nybble41]

There is a serious problem with reintegration which I didn't consider before: the fees and block rewards will inevitably conflict between the different chains. Assuming B and C were discovered by different miners, the fee for transaction t3 in block B would conflict with the fee for the same transaction in block C, and the {B,C} set, while still representing only a single link in the chain, would have double the combined block reward.

I think the rewards can be split between the referenced blocks one way or another.

I considered that, but any such split would necessarily be after the fact; there are any number of ways blocks B and C, and possibly other blocks, could be recombined into block D, and then into block E, and so on. Reducing the reward after a valid block has been discovered doesn't seem very fair to the miners. Similarly, splitting transaction fees ex post facto would introduce chaos into the miners' transaction selection process. It also seems like a much more involved protocol change than simply adding multiple parent blocks and merging their transactions.

[Meni Rosenfeld]

There is a serious problem with reintegration which I didn't consider before: the fees and block rewards will inevitably conflict between the different chains. Assuming B and C were discovered by different miners, the fee for transaction t3 in block B would conflict with the fee for the same transaction in block C, and the {B,C} set, while still representing only a single link in the chain, would have double the combined block reward.

I think the rewards can be split between the referenced blocks one way or another.

I considered that, but any such split would necessarily be after the fact; there are any number of ways blocks B and C, and possibly other blocks, could be recombined into block D, and then into block E, and so on. Reducing the reward after a valid block has been discovered doesn't seem very fair to the miners. Similarly, splitting transaction fees ex post facto would introduce chaos into the miners' transaction selection process. It also seems like a much more involved protocol change than simply adding multiple parent blocks and merging their transactions.

Mining rewards mature after 120 blocks, and it seems reasonable if they change during that time. Though how to do this technically might be a challenge.

[galambo]

Optimal block frequency is determined by the conditions of the network, not the market.

You are making an economic mistake that many bitcoiners do.

As far as the field of economics is concerned, coinbase transactions contain zero information. Its what you do with it, not what it is.

The economic value of bitcoin is the non-coinbase transactions.

[Meni Rosenfeld]

Optimal block frequency is determined by the conditions of the network, not the market.

You are making an economic mistake that many bitcoiners do.

As far as the field of economics is concerned, coinbase transactions contain zero information. Its what you do with it, not what it is.

The economic value of bitcoin is the non-coinbase transactions.

I think you've missed the point. Block frequency has the effects that I described on Bitcoin users, nodes and miners.

[gmaxwell]

I think you've missed the point. Block frequency has the effects that I described on Bitcoin users, nodes and miners.

On the contrary, you missed his.  The most important element of the inter-block time is the network convergence radius, if the interblock time is too small relative to the block validating and forwarding delay and the network is likely to never converge. Somewhat larger, but still small— a concentrated attacker gains an unusual advantage against distributed honest defenders, because the defenders lose hash power extending multiple separate forks due to slow convergence.  If you set the time just high enough to avoid the most fatal effects you still greatly increase the computational burden on full validating nodes, increase the storage burden on simplified nodes, and damage decentralization by discouraging validating or semi-validating nodes and driving people to centralized services.

It's not really an market parameter at all— and to the extent that it is one, it would be one highly prone to a race to the bottom which devalues the system for everyone.   Even if you set it to stupidly-low-will-break-for-sure levels there will intermittently be very long blocks. If you're engaging in activity where you need fast evidence of irreversibility it's almost always the case that you need consistently fast evidence of irreversibility— often fast, sometimes not isn't good.  So making the block times different doesn't really solve anything here.  Fortunately there are other ways to get evidence of irreversibility, lower variance for mining, etc. that don't require breaking the system.

[allten]

There's a strong atmosphere in the Bitcoin community that "if its not broken then don't fix it". May not be optimal or flexible, but it works. until we reach a scenario where it becomes obvious to all that varied block timing will be beneficial, it will be very hard to influence the change.

Anyways, thanks for proposal. It's definitely good food for thought.

[Meni Rosenfeld]

@gmaxwell - I've already addressed most of these points. I think the problem is a too narrow definition of market - everything can be a market if there's an appropriate incentive scheme. I guess your point is that there's currently no good incentive scheme - which is a challenge, but I don't think an insurmountable one.

The most important element of the inter-block time is the network convergence radius, if the interblock time is too small relative to the block validating and forwarding delay and the network is likely to never converge.

More frequent blocks will make forks longer, but I don't think there's a sense in which they can not converge.

Somewhat larger, but still small— a concentrated attacker gains an unusual advantage against distributed honest defenders, because the defenders lose hash power extending multiple separate forks due to slow convergence.

That's the market of miners who don't wish their hashes to be wasted, and the market of users who prefer to minimize the probability of their transactions being double-spent. It is still an open problem how to have a way for users to act on this preference.

If you set the time just high enough to avoid the most fatal effects you still greatly increase the computational burden on full validating nodes,

The market of nodes who wish to cut costs.

increase the storage burden on simplified nodes,

The market of users. Though this is a small enough problem that it can be solved by agreement rather than direct action.

and damage decentralization by discouraging validating or semi-validating nodes and driving people to centralized services.

The users have a preference for more decentralization. Again there's some work to find the incentive scheme that's best for letting them act on it.

So making the block times different doesn't really solve anything here.

There's a tradeoff with regards to block frequency. Where there's a tradeoff there's an optimal value, and I see no reason to believe 10 minutes is it.

What I'm trying to say is that the weight placed on arbitrary decrees should be minimized. "10 minutes is the block frequency and there's nothing you can do about it" may solve the incentive issues but it leads to a result far from optimum. With a dynamic block frequency you'll still need some decree to keep the incentives in line, but most of the heavylifting of finding the best value will be done by the actions of those who are affected by the decision. Think of it as a sort of amplification.

Fortunately there are other ways to get evidence of irreversibility, lower variance for mining, etc. that don't require breaking the system.

That's probably true. P2Pool emulates frequent blocks for variance purposes, and these days I have a different idea on how to make fast payments, so having a dynamic block frequency isn't critical.

[gmaxwell]

More frequent blocks will make forks longer, but I don't think there's a sense in which they can not converge.

A toy example: The block rate is infinitely fast, the communication delay between miners is 0+ε.  All miners are on their own forks and will never converge onto a single chain.   This was even demonstrated in practice on a altcoin.

That's the market of miners who don't wish their hashes to be wasted, and the market of users who prefer to minimize the probability of their transactions being double-spent.

The miners hases aren't "wasted", since eveyone takes the losses from orphaning. There is only the loss of security of blocks which are frequently below the communications horizon and the race to the bottom to include more transactions regardless of the overall security implications.

The market of users. Though this is a small enough problem that it can be solved by agreement rather than direct action.

There are many problems which are basically unsolvable in a dynamic system but are trivial when the parties can pre-commit. Bitcoin is defined by it's rules, its a pre-commitment that we've all signed up for. Changes that favor some over others would rightfully undermine any trust people put in it...

That's probably true. P2Pool emulates frequent blocks for variance purposes, and these days I have a different idea on how to make fast payments, so having a dynamic block frequency isn't critical.

... especially when there are alternatives.

[Meni Rosenfeld]

More frequent blocks will make forks longer, but I don't think there's a sense in which they can not converge.

A toy example: The block rate is infinitely fast, the communication delay between miners is 0+ε.  All miners are on their own forks and will never converge onto a single chain.   This was even demonstrated in practice on a altcoin.

Of course if the block frequency is infinite, so will the forks be. Interestingly, I think the length of forks grows very rapidly with diminishing time between blocks, exp(1/T).

That's the market of miners who don't wish their hashes to be wasted, and the market of users who prefer to minimize the probability of their transactions being double-spent.

The miners hases aren't "wasted", since eveyone takes the losses from orphaning. There is only the loss of security of blocks which are frequently below the communications horizon and the race to the bottom to include more transactions regardless of the overall security implications.

If block time decreases for everyone then yes, miners aren't worse off. In the context of my proposal, a miner deciding to personally go for a shorter time will have his hashes wasted since his block has a higher chance to be rejected. That's one of the market forces restoring equilibrium.

[jl2012]

Miners will decide the "optimal" block frequency only based on their interest (e.g. reducing mining variance), not for network security / efficiency

[Meni Rosenfeld]

Miners will decide the "optimal" block frequency only based on their interest (e.g. reducing mining variance), not for network security / efficiency

Exactly.

[jl2012]

Miners will decide the "optimal" block frequency only based on their interest (e.g. reducing mining variance), not for network security / efficiency

Exactly.

Therefore, your proposal may actually have harmful effect on network security / efficiency. For example, if miners find out that 20-minute block is optimal for for mining, all transactions will wait much longer before getting confirmed.

[Meni Rosenfeld]

Miners will decide the "optimal" block frequency only based on their interest (e.g. reducing mining variance), not for network security / efficiency

Exactly.

Therefore, your proposal may actually have harmful effect on network security / efficiency. For example, if miners find out that 20-minute block is optimal for for mining, all transactions will wait much longer before getting confirmed.

Not if there is an incentive system in place which allows users who want fast confirmations to pay the miners who deliver a quick block.

[ripper234]

Nice thread. Might be worthwhile for Bitcoin 2.0.

Added to the Hardfork wishlist.

Keep up the good work & innovation Meni!

[Meni Rosenfeld]

Keep up the good work & innovation Meni!

Thanks. I think I've had this idea since Nov 2011, too bad it took me until May to write about it.