Bitcoin Forum
September 28, 2023, 01:36:57 AM
 News: Latest Bitcoin Core release: 25.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1] 2 3  All
 Author Topic: A clean solution to ALL Bitcoin problems: SatoshiDice, Block size, future fees.  (Read 4247 times)
Sergio_Demian_Lerner (OP)
Hero Member

Offline

Activity: 549
Merit: 603

 February 26, 2013, 05:27:05 PMLast edit: February 26, 2013, 06:29:16 PM by 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.

1695865017
Hero Member

Offline

Posts: 1695865017

Ignore
 1695865017

1695865017
 Report to moderator
1695865017
Hero Member

Offline

Posts: 1695865017

Ignore
 1695865017

1695865017
 Report to moderator
1695865017
Hero Member

Offline

Posts: 1695865017

Ignore
 1695865017

1695865017
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
misterbigg
Legendary

Offline

Activity: 1064
Merit: 1001

 February 26, 2013, 05:30:12 PM

NICE!!!! A brand new idea!!!
Technomage
Legendary

Offline

Activity: 2184
Merit: 1056

Affordable Physical Bitcoins - Denarium.com

 February 26, 2013, 05:37:18 PM

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.

Denarium closing sale discounts now up to 43%! Check out our products from here!
Sergio_Demian_Lerner (OP)
Hero Member

Offline

Activity: 549
Merit: 603

 February 26, 2013, 05:38:21 PM

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
Legendary

Offline

Activity: 1400
Merit: 1006

 February 26, 2013, 05:41:16 PM

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
Legendary

Offline

Activity: 1064
Merit: 1001

 February 26, 2013, 05:41:53 PM

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
Legendary

Offline

Activity: 2940
Merit: 1090

 February 26, 2013, 05:52:09 PMLast edit: February 26, 2013, 06:12:44 PM by 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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
AsymmetricInformation
Member

Offline

Activity: 115
Merit: 10

 February 26, 2013, 06:06:06 PM

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.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
Full Member

Offline

Activity: 225
Merit: 101

 February 26, 2013, 06:24:02 PM

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

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

Like my posts?  Connect with me on LinkedIn and endorse my "Bitcoin" skill.
Decentralized, instant off-chain payments.
Sergio_Demian_Lerner (OP)
Hero Member

Offline

Activity: 549
Merit: 603

 February 26, 2013, 06:25:51 PM

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 (OP)
Hero Member

Offline

Activity: 549
Merit: 603

 February 26, 2013, 06:27:19 PM

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

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
Full Member

Offline

Activity: 154
Merit: 100

 February 26, 2013, 06:45:25 PM

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
Legendary

Offline

Activity: 2618
Merit: 1006

 February 26, 2013, 06:53:29 PM

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?

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
AsymmetricInformation
Member

Offline

Activity: 115
Merit: 10

 February 26, 2013, 07:00:21 PM

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.

Support Decentralized Bitcoin Prediction Markets: 1M5tVTtynuqiS7Goq8hbh5UBcxLaa5XQb8
https://github.com/psztorc/Truthcoin
misterbigg
Legendary

Offline

Activity: 1064
Merit: 1001

 February 26, 2013, 07:01:01 PM

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
Legendary

Offline

Activity: 1064
Merit: 1001

 February 26, 2013, 07:03:23 PM

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
Full Member

Offline

Activity: 154
Merit: 100

 February 26, 2013, 07:19:29 PM

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 (OP)
Hero Member

Offline

Activity: 549
Merit: 603

 February 26, 2013, 07:34:34 PM

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
Legendary

Offline

Activity: 1120
Merit: 1134

 February 26, 2013, 08:04:05 PM

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
Moderator
Legendary

Offline

Activity: 4018
Merit: 7844

 February 26, 2013, 08:16:11 PM

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.
 Pages: [1] 2 3  All