A clean solution to ALL Bitcoin problems: SatoshiDice, Block size, future fees.

[Sergio_Demian_Lerner]

The idea is simple, butrequires a hardfork, but is has minimum impact in the code and in the economics.

Solution: Require that the set of fees collected in a block has a maximum dispersion. Use, for example, the Coefficient of Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If the CoVar is higher than a fixed constant, the block is invalid.

The Coefficient of variation is computed as the standard deviation over the mean value, so it's very easy to compute. (if the mean is zero, we assume CoVar=0). Note that the CoVar function does not depend of the scale, so is just what a coin with floating value requires.

This means that if there are many transactions containing high fees in a block, then free transactions cannot be included.
The core devs should tweak the transaction selection algorithm to take into account this maximum bound.

Example

If the transaction fee set is: 0,0,0,0,5,5,6,7,8,7
The CoVar is 0.85
Suppose we limit the CoVar to a maximum of 1.

Suppose the transaction fee set is: 0,0,0,0,0,0,0,0,0,10
Then the CoVar is 3.0

In this case the miner should have to either drop the "10" from the fee set or drop the zeros. Obviously the miner will drop some zeros, and choose the set: 0,10, that has a CoVar of 1.

Why it solves SD Problem?

Using this little modification, users of SatoshiDice would require to use higher fees, only if the remaining users in the community rises their fees. And miners won't be able to include an enormous amounts of spamming txs.

Why it solves the futue fee problem? (and the tragedy-of-the-commons "problem")

Because as miners are forced to keep the CoVar low, if people rises the fees to confirm faster than spamming txs, automatically smamming txs become less likely to appear in blocks.

Why it solves the block size problem?

Because if we increase the block size, miners acting irrationally won't be able to fill the block with spamming txs. Edit: This is not a solution against an attacker-miner.

Best regard,
  Sergio.

Edit: PLEASE don't confuse the acronym CoVar I used here with co-variance.

[1714883234]

1714883234

[1714883234]

1714883234

[misterbigg]

NICE!!!! A brand new idea!!!

[Technomage]

Good job Sergio. That is an interesting idea. Right now I have nothing else to say but maybe later as I think about it more.

[Sergio_Demian_Lerner]

Note that a miner could also drop transaction with very high fees in order to collect many transactions with lower fees, but I find it very rare in practice, since transactions consume block space.

I also think that even if the high-to-low fee selection algorithm is fast and greedy O(n), an optimum algorithm that maximizes fees with the dispersion restriction would be O(n^2), where n is the number of transactions to test.


 

[justusranvier]

Why do miners need to be forced to adopt a fee policy? If it's a good idea there's nothing stopping them from implementing it right now.

How do you decide on the optimum value for the magic constant that you want to embed into the block validation rules?

[misterbigg]

Why do miners need to be forced to adopt a fee policy? If it's a good idea there's nothing stopping them from implementing it right now.

Because the network would need to reject blocks if the covariance is too high.

[markm]

The same crowd who argue for inifinite (no limit) max block size will use the the same arguments against this.

To them it is just another arbitrary restriction preventing all out class-warfare from playing itself out to its natural conclusion of "the biggest bullies win".

-MarkM-

[AsymmetricInformation]

Sergio provided an example where the policy caused a low-fee transaction to be dropped.

Can anything think of a counterexample where the policy caused something dramatic and horrible to happen?

I personally think I might have one involving miners who themselves create transactions to perfectly meet the CoVar, ensuring they recapture the fees and the block, but I haven't worked it out. It might be impractical. (Also I'm not sure I understand my own intuition so if anyone sees where Im going with this please write it down and save me the trouble.)

Why do miners need to be forced to adopt a fee policy? If it's a good idea there's nothing stopping them from implementing it right now.

How do you decide on the optimum value for the magic constant that you want to embed into the block validation rules?

Does anyone know the historical value of the CoVar? Ideally a graph of CoVar(Fees in block t) against Blocks (ie Time)? By some miracle it could be very stable, and only increase in association with the rise of 'unwanted' things (SatoshiDice).


It is a cool new idea though. Looking forward to the discussion.

[blueadept]

One issue might be transactions that spam by means of their size. Perhaps a modification taking into account transaction size, too? Something like CoVar(txfee_i/txsize_i)?

I haven't had enough time yet to try thinking of other ways of gaming this.

[Sergio_Demian_Lerner]

How do you decide on the optimum value for the magic constant that you want to embed into the block validation rules?

A historical analysis of the block chain must be done, but I don't have the right tools to do it. (a ready to run development environment).
If would choose the maximum historical CoVar as the fixed constant (maybe probably removing the 5% highest percentile).

But this value will be clearer when you have the historical data.

Maybe someone who develops BitcoinJ or the Satoshi Client can provide us with a graph CoVar/Time ?

Maybe there is some hidden information related to SD and spamming txs there that we have overlooked.

[Sergio_Demian_Lerner]

One issue might be transactions that spam by means of their size. Perhaps a modification taking into account transaction size, too? Something like CoVar(txfee_i/txsize_i)?

I haven't had enough time yet to try thinking of other ways of gaming this.

Rational miners choose smaller transactions because:

1. Gives extra space to put more transactions in the block
2. Reduces the propagation time.

So there is enough incentives to include smaller txs.

[twolifeinexile]

The idea is simple, butrequires a hardfork, but is has minimum impact in the code and in the economics.

Solution: Require that the set of fees collected in a block has a maximum dispersion. Use, for example, the Coefficient of Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If the CoVar is higher than a fixed constant, the block is invalid.

The Coefficient of variation is computed as the standard deviation over the mean value, so it's very easy to compute. (if the mean is zero, we assume CoVar=0). Note that the CoVar function does not depend of the scale, so is just what a coin with floating value requires.

This means that if there are many transactions containing high fees in a block, then free transactions cannot be included.
The core devs should tweak the transaction selection algorithm to take into account this maximum bound.

Example

If the transaction fee set is: 0,0,0,0,5,5,6,7,8,7
The CoVar is 0.85
Suppose we limit the CoVar to a maximum of 1.

Suppose the transaction fee set is: 0,0,0,0,0,0,0,0,0,10
Then the CoVar is 3.0

In this case the miner should have to either drop the "10" from the fee set or drop the zeros. Obviously the miner will drop some zeros, and choose the set: 0,10, that has a CoVar of 1.

Why it solves SD Problem?

Using this little modification, users of SatoshiDice would require to use higher fees, only if the remaining users in the community rises their fees. And miners won't be able to include an enormous amounts of spamming txs.

Why it solves the futue fee problem? (and the tragedy-of-the-commons "problem")

Because as miners are forced to keep the CoVar low, if people rises the fees to confirm faster than spamming txs, automatically smamming txs become less likely to appear in blocks.

Why it solves the block size problem?

Because if we increase the block size, miners acting irrationally won't be able to fill the block with spamming txs. Edit: This is not a solution against an attacker-miner.

Best regard,
  Sergio.

Edit: PLEASE don't confuse the acronym CoVar I used here with co-variance.

great thought, I will vote up this to let more people to think about that.
Just is it possible at some point in time no coVar threshold compliant block that can be found? Then the whole chain will just wait more transactions?
Also, given this coVar requirement, what algorithm a miner would like to run to select transactions?
Maybe the logic could be if the block is smaller than certain size, then coVar check is not needed.
All in all, sounds like a very elegant solution.

[Sukrim]

Can a miner be forced to include free transactions or to drop certain transactions by publishing "better" transactions with this approach?

Also I like it because it leaves the issue of block size aside. On the other hand maybe that might be a problem?

[AsymmetricInformation]

How do you decide on the optimum value for the magic constant that you want to embed into the block validation rules?

A historical analysis of the block chain must be done, but I don't have the right tools to do it. (a ready to run development environment).
If would choose the maximum historical CoVar as the fixed constant (maybe probably removing the 5% highest percentile).

But this value will be clearer when you have the historical data.

Maybe someone who develops BitcoinJ or the Satoshi Client can provide us with a graph CoVar/Time ?

Maybe there is some hidden information related to SD and spamming txs there that we have overlooked.

What about merging this suggestion with Hazek's suggestion in a different post, which suggested increasing the block size limit if (subsidy + fees) > 50 BTC, and decreasing it (subsidy + fees) < 25. Instead of changing the block size directly you could just change the CoVar.

[misterbigg]

Also I like it because it leaves the issue of block size aside. On the other hand maybe that might be a problem?

If the maximum block size is increased, then this proposal will prevent fees from dropping to nothing. I like it!

[misterbigg]

is it possible at some point in time no coVar threshold compliant block that can be found?

No, because a block with 1 or more transactions that all have the same fee always has a coefficient of variation of zero.

[twolifeinexile]

Why it solves the block size problem?
Because if we increase the block size, miners acting irrationally won't be able to fill the block with spamming txs. Edit: This is not a solution against an attacker-miner.

Trying to understand this further... If a miner mean to force out other miners out of network by flooding large block, and make many many many low fee trasactions, how it is affected?
If the block has many low fee transactions, no higher fee txs, then the coVaR may still low and pass the test, no?

[Sergio_Demian_Lerner]

Why it solves the block size problem?
Because if we increase the block size, miners acting irrationally won't be able to fill the block with spamming txs. Edit: This is not a solution against an attacker-miner.

Trying to understand this further... If a miner mean to force out other miners out of network by flooding large block, and make many many many low fee trasactions, how it is affected?
If the block has many low fee transactions, no higher fee txs, then the coVaR may still low and pass the test, no?

Yes, as I added to the original post: it's not a solution against malicious miners. Only against selfish (and irrational)  miners that do not think about the future of Bitcoin.

[Peter Todd]

How does this prevent a miner from creating their own transactions to game the coefficients? The only cost is the orphan rate, which can be kept well under 1% for a miner with sufficient infrastructure.

[gmaxwell]

If the maximum block size is increased, then this proposal will prevent fees from dropping to nothing. I like it!

that isn't obvious to me, say you mine a small block with some big fee txn. Great. The moment after that there are no big fee txn— but there is 10gb of low fee txn. So of course everyone mines those next.  Alternatively if the sum of low fee transactions is greater than a high fee one that would blow the covar, you'd drop the high fee txn and take the gigabyte of dust— so instead of keeping fees high, in some cases it would encourage people to lower their fees.

I think it would exaggerate priority effects, I'll have to think more about it.