Bitcoin Forum
May 26, 2019, 08:42:10 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: A clean solution to ALL Bitcoin problems: SatoshiDice, Block size, future fees.  (Read 4071 times)
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 541
Merit: 514


View Profile WWW
February 26, 2013, 05:27:05 PM
Last edit: February 26, 2013, 06:29:16 PM by Sergio_Demian_Lerner
 #1

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.





GET 25 FREE SPINS AT REGISTRATION
GET 100% BONUS ON FIRST DEPOSIT
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
misterbigg
Legendary
*
Offline Offline

Activity: 1064
Merit: 1001



View Profile
February 26, 2013, 05:30:12 PM
 #2

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

Activity: 1974
Merit: 1028


Affordable Physical Bitcoins - Denarium.com


View Profile WWW
February 26, 2013, 05:37:18 PM
 #3

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 Christmas Competition & Giveaway is live! - Check it out from here!
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 541
Merit: 514


View Profile WWW
February 26, 2013, 05:38:21 PM
 #4

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 Offline

Activity: 1400
Merit: 1006



View Profile WWW
February 26, 2013, 05:41:16 PM
 #5

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 Offline

Activity: 1064
Merit: 1001



View Profile
February 26, 2013, 05:41:53 PM
 #6

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 Offline

Activity: 2282
Merit: 1005



View Profile WWW
February 26, 2013, 05:52:09 PM
Last edit: February 26, 2013, 06:12:44 PM by markm
 #7

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 Offline

Activity: 115
Merit: 10


View Profile WWW
February 26, 2013, 06:06:06 PM
 #8

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
blueadept
Full Member
***
Offline Offline

Activity: 225
Merit: 100


View Profile
February 26, 2013, 06:24:02 PM
 #9

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
Hero Member
*****
expert
Offline Offline

Activity: 541
Merit: 514


View Profile WWW
February 26, 2013, 06:25:51 PM
 #10


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
Hero Member
*****
expert
Offline Offline

Activity: 541
Merit: 514


View Profile WWW
February 26, 2013, 06:27:19 PM
 #11

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 Offline

Activity: 154
Merit: 100



View Profile
February 26, 2013, 06:45:25 PM
 #12

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 Offline

Activity: 2478
Merit: 1002


View Profile
February 26, 2013, 06:53:29 PM
 #13

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. No fees(!).
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
AsymmetricInformation
Member
**
Offline Offline

Activity: 115
Merit: 10


View Profile WWW
February 26, 2013, 07:00:21 PM
 #14


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 Offline

Activity: 1064
Merit: 1001



View Profile
February 26, 2013, 07:01:01 PM
 #15

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 Offline

Activity: 1064
Merit: 1001



View Profile
February 26, 2013, 07:03:23 PM
 #16

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 Offline

Activity: 154
Merit: 100



View Profile
February 26, 2013, 07:19:29 PM
 #17

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
Hero Member
*****
expert
Offline Offline

Activity: 541
Merit: 514


View Profile WWW
February 26, 2013, 07:34:34 PM
 #18

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
*
expert
Offline Offline

Activity: 1106
Merit: 1013


View Profile
February 26, 2013, 08:04:05 PM
 #19

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
*
qt
Offline Offline

Activity: 2744
Merit: 2268



View Profile
February 26, 2013, 08:16:11 PM
 #20

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
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!