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

[ArticMine]

I see a problem with this. Would not one dominant source of transactions effectively set the transaction fees? For example S.Dice would be able to set the transaction fee effectively at will in today’s market. http://blockchain.info/

[1713938712]

1713938712

[1713938712]

1713938712

[Zeilap]

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

At the moment, to increase your transaction priority, you increase the transaction fee. Pretty simple.

With this system, it is no longer true. Instead the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions. Your goal is to set your fee so that it is similar in value to as many other transactions as possible, so a large group with small variance is formed, becoming most profitable to mine.
But, if you set it to the same fee of a large group of other transactions, the group may get too large (to fit in a block) and so only a subgroup of that group will be used (or another group in a different range of fees), so you might want to set your fee to be slightly larger within the group, to increase your chances of placing in the subgroup. Too large however and it may be more profitable for the miner to include several smaller paying transactions than your slightly larger one etc.

To pick your fee you need to know what the most profitable group of transactions *will be*, i.e. you need to know what transactions other people are going to send before they send them.

[Technomage]

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

At the moment, to increase your transaction priority, you increase the transaction fee. Pretty simple.

With this system, it is no longer true. Instead the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions. Your goal is to set your fee so that it is similar in value to as many other transactions as possible, so a large group with small variance is formed, becoming most profitable to mine.
But, if you set it to the same fee of a large group of other transactions, the group may get too large (to fit in a block) and so only a subgroup of that group will be used (or another group in a different range of fees), so you might want to set your fee to be slightly larger within the group, to increase your chances of placing in the subgroup. Too large however and it may be more profitable for the miner to include several smaller paying transactions than your slightly larger one etc.

To pick your fee you need to know what the most profitable group of transactions *will be*, i.e. you need to know what transactions other people are going to send before they send them.

I don't see it as that problematic. Fees would have variance from block to block but that isn't such a big deal. Only the first ones announcing their tx are blind to what is going on and don't really know the optimal fee, but on the other hand they have the most power in defining the fee that's most useful for that block. The ones coming later would simply react to what kind of transactions are in the block already and choose the fee automatically.

The user can simply set an upper bound to how much he is willing to pay. If the next set of transactions is not looking good the client would postpone the tx to be sent once that block clears, or the client could just send it right away but it wouldn't be accepted into the next block because it has a fee that doesn't fit. Not sure if I'm way over the place with this but I think it can work.

[solex]

Sergio's idea sounds great, therefore I went away and examined two blocks.

SatoshiDice launched on April 24, 2012 so I randomly chose a large block two weeks earlier:

April 9, 2012      
block 174997 (Tx = 154)
Fee            Count   
0                 116   
0.0005           35   
0.001              4   
0.00677853     1   
0.01                1   
CoVar = 4.00      

Then I chose a similar sized block which went through in the last hour:
      
Feb 26, 2013      
block 223287 (Tx = 151)
Fee         Count   
0              13   
0.0005      61   
0.001        70   
0.0015        1   
0.002          2   
0.005          4   
CoVar = 0.93      

First, a wider analysis is warranted as this is a very narrow test. However, in the meantime I am not sure if there is a problem to be solved!  In the April 2012 example most transactions did not have fees, in the block today they do. SD is paying a lot in fees. It seems bitcoin is improving its economic "health" organically, or at least through current incentives for fees. All it needs is more time to see whether the fees climb or level off.

I am wondering whether fees are tangential and the real issue about the max block limit is block propagation/verification time as Gavin indicated at the start!

[twolifeinexile]

I am wondering if fees are tangental and the real issue about the max block limit is block propagation/verification time as Gavin indicated at the start!

max block limit is the real question in my opinion, since that determines how much free ride could pontentially be and then the block proopagation/verification has long term effect on miner competition.

[solex]

I am wondering if fees are tangental and the real issue about the max block limit is block propagation/verification time as Gavin indicated at the start!

max block limit is the real question in my opinion, since that determines how much free ride could pontentially be and then the block proopagation/verification has long term effect on miner competition.

Yes, but the 1Mb limit is nothing more than a psychological constraint at present, yet fees are rising anyway. The concern is about when it becomes a physical  constraint (due to transaction volumes).

[streblo]

Nash equilibrium at 1 satoshi txn fee ruins this idea. There is no incentive to ever submit a transaction with a non-1 satoshi fee.

[misterbigg]

the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions.

This is true even in today's Bitcoin implementation.

[misterbigg]

Nash equilibrium at 1 satoshi txn fee ruins this idea. There is no incentive to ever submit a transaction with a non-1 satoshi fee.

Not true, if everyone included only 1 satoshi as the fee the confirmation time would grow without bound.

[Zeilap]

I don't see it as that problematic. Fees would have variance from block to block but that isn't such a big deal.

Let's consider the analogous situation in real life:
[Customer   ] Hi, I'd like to buy this item, would you deliver it to this address
[Shop owner] No problem
[Customer   ] When can I expect delivery?
[Shop owner] I don't know, possibly immediately, possibly never.
[Customer   ] WTF!? Can I pay you a little extra to guarantee I get it by tomorrow?
[Shop owner] Sorry, that's not how the system works.
[Customer   ] So how does it work then?
[Shop owner] Well, I'm thinking of a number between 1 and 100, give me some money between $1 and $100 and if the amount you choose is closer than the other customers, you'll get it delivered tomorrow.

Only the first ones announcing their tx are blind to what is going on and don't really know the optimal fee, but on the other hand they have the most power in defining the fee that's most useful for that block. The ones coming later would simply react to what kind of transactions are in the block already and choose the fee automatically.

No, what will happen is that multiple transactions will appear all at different values early on, and only one of them will end up being in the winning group. The result is that announcing early gives you least control over getting your transaction processed. The incentive now is to announce your transaction as late as possible, but not too late to miss getting into the block.


If this were to come into force, people would end up realizing that it is in their interest to send their transaction multiple times with different fees. Only one can be processed due to double spends, but if they have transactions at all different fees, they are more likely to get one of them processed.

Further, I could easily set up a service to game the system for people who actually care about getting their transactions processed. How it would work is that they send me multiple versions of the transaction they would like to broadcast, each version with a different fee. I would hold the transactions until I got enough transactions to game the system, then I dump them all at once on the network, creating the best group of transactions or joining the current best group if I can't beat it.

[Sergio_Demian_Lerner]

Zeilap: This is getting really interesting...

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

...

With this system, it is no longer true. Instead the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions. Your goal is to set your fee so that it is similar in value to as many other transactions as possible, so a large group with small variance is formed, becoming most profitable to mine.

This can be very easily avoided. Before calculating the CoVar, sort them by fees, and remove from the CoVar computation the transactions that in the 10% percentile that pay most.

Then you'll always be able to get the transaction into the next block: send the fee high enough to be in that percentile.

But I'm unsure if a high fee transaction would be ever discarded. I will simulate this.

[Sergio_Demian_Lerner]

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.

It just goes against his own interests. Why would he do that? There is no memory between blocks, so a block cannot influence the next.

[bpd]

Couldn't someone DoS the network for a period by submitting 1 high-fee transaction at a time? So high that including any other normal-fee transactions would violate the CoVar max, and high enough that it is greater than the sum of all the rest of the transactions in the pool?

Yes, it would cost bitcoin to do this, but an entity with deep pockets could just keep buying BTC on the open market to do this as long as they wanted.

[Sergio_Demian_Lerner]

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

At the mome

Here is an example of what Zeilap  sais:

Suppose the set of transaction fees available is:
1,1,1,1,1,1,1,1,1,1,1,1,2,10

Suppose the maximum CoVar is 1.

We compare two possible sets to choose, one containing 10 and another without it:

(A) 1,1,1,1,1,1,1,1,1,1,1,1,2
(B) 1,2,10


Results for A:

Sum=14.00
Mean= 1.08
Variance= 0.07
StdDev= 0.27
CoVar= 0.25

Results for B:

Sum=13.00
Mean= 4.33
Variance=16.25
StdDev= 4.03
CoVar= 0.93

So the set A pays more fees, and so it will be chosen.

I would discard the 10% percentile, as I said.

[Sergio_Demian_Lerner]

Couldn't someone DoS the network for a period by submitting 1 high-fee transaction at a time? So high that including any other normal-fee transactions would violate the CoVar max, and high enough that it is greater than the sum of all the rest of the transactions in the pool?

Yes, it would cost bitcoin to do this, but an entity with deep pockets could just keep buying BTC on the open market to do this as long as they wanted.

Yes.
One solution would be to use Robust statistics, like the median instead of the mean to divide the Standard deviation. Or the Median absolute deviation divided by the median. Let's call it CoVar*. So CoVar* will work as CoVar, but won't be affected by outliers.

[Maged]

Be very careful with this. There are valid use cases where free transactions can be completely acceptable because they are paid for some other way. For example, chaining transactions so that the recipient pays the fee instead of the sender. This can be worked around by making sure that the algorithm is aware of that and considers the chain as a single unit. However, my point is that these cases need to all be known at the time of writing the algorithm because it would take a hard fork to change it later.

Also, I'm assuming that every reference to "transaction fee" really means transaction fee per KB, otherwise that opens up the potential for people to use mega-transactions to split single the fee between multiple parties (transactions larger than 500KB make sense now, don't they  ) instead of mega-transactions just receiving a marginally lower fee over using normal transactions.

Finally, does this really require a hard fork? It might be used with one, sure, but could this be done at a later point via a soft fork? I'm trying to figure out if I'm missing anything about your proposal...

[Zeilap]

Zeilap: This is getting really interesting...

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

...

With this system, it is no longer true. Instead the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions. Your goal is to set your fee so that it is similar in value to as many other transactions as possible, so a large group with small variance is formed, becoming most profitable to mine.

This can be very easily avoided. Before calculating the CoVar, sort them by fees, and remove from the CoVar computation the transactions that in the 10% percentile that pay most.

Then you'll always be able to get the transaction into the next block: send the fee high enough to be in that percentile.

But I'm unsure if a high fee transaction would be ever discarded. I will simulate this.

I'm not sure what you mean here (in bold), or maybe I do but don't understand how it solves the problem.
Also, I get the impression that you're assuming that the distribution of fees will still be unimodal. By changing the way that the system works like you propose, you change the way people are going to set their fees and you will likely end up with many clusters of transactions at different fees.
Note that it isn't enough to simply join the most profitable cluster - blocksize limits mean that there will be competition within the largest clusters. Thus the centres of these clusters will move over the course of one block as people fight for position, and may merge or split - fuck knows.
You can only know what the optimal fee is at the moment you send your transaction, which would be fine if you are the last player to make his move - but you won't be, so the next person will find a slightly different optimal fee (because your transaction has changed the optimal value), and so on until one minute later, your transaction is far enough away from optimal that it won't be processed this block.

I applaud you for thinking outside the box on this (and a lot of things actually), but I think you've just come up with an interesting topic for game theorists

[farlack]

No one puts into consideration that there will be a large bank backed person to come in pour a ton of money into hardware and mine fees for profit powered off solar panels.
Google, the US government, paypal banks, etc.


Wouldn't that speed things along?
Granted it would have a huge startup and a long term profit ratio, but the big banks will always be around even if the USD collapses, and bitcoin are the new currency.

[Maged]

Zeilap: This is getting really interesting...

This is just going to cause the transaction fees to bounce around wildly, and users will no longer have any real control over transaction priority.

...

With this system, it is no longer true. Instead the optimal fee to increase your transaction priority is dependent on the other transaction fees in the set of unprocessed transactions. Your goal is to set your fee so that it is similar in value to as many other transactions as possible, so a large group with small variance is formed, becoming most profitable to mine.

This can be very easily avoided. Before calculating the CoVar, sort them by fees, and remove from the CoVar computation the transactions that in the 10% percentile that pay most.

Then you'll always be able to get the transaction into the next block: send the fee high enough to be in that percentile.

But doesn't that break the whole system because even honest miners would be encouraged to add spam transactions (possibly generated locally) in order to make the 10% percentile bigger? In theory, they could artificially expand the set of transactions so that all "real" transactions fit within the 10% percentile.

[Atruk]

Be very careful with this. There are valid use cases where free transactions can be completely acceptable because they are paid for some other way. For example, chaining transactions so that the recipient pays the fee instead of the sender. This can be worked around by making sure that the algorithm is aware of that and considers the chain as a single unit. However, my point is that these cases need to all be known at the time of writing the algorithm because it would take a hard fork to change it later.

Also, I'm assuming that every reference to "transaction fee" really means transaction fee per KB, otherwise that opens up the potential for people to use mega-transactions to split single the fee between multiple parties (transactions larger than 500KB make sense now, don't they  ) instead of mega-transactions just receiving a marginally lower fee over using normal transactions.

Finally, does this really require a hard fork? It might be used with one, sure, but could this be done at a later point via a soft fork? I'm trying to figure out if I'm missing anything about your proposal...

In my transaction experience it is very easy to just start paying proportional fees like this on one's own. It has been a while since my transactions haven't made it into the next block.

What I would really like to see out of the OP's proposal is a formal whitepaper. There's a lot of mathematical language in the original post, and I think a more formal proposal would be very useful. I may be hoping for a bit too much because SDL usually only makes abbreviated posts, but more than in any other post he has made I want to see the white paper from this one.