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

[phelix]

How does this prevent a miner from creating their own transactions to game the coefficients? [...]

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.

As long as there is room in the block he can influence the coefficient by sending coins back to himself. See below.

Code:

						Miner:	5,00
						Miner:	5,00
						Miner:	5,00
						Miner:	5,00
						Miner:	5,00
							
	0,00		1,00	1,00			1,00
	0,00		1,00	1,00			1,00
	0,00		1,00	1,00			1,00
	0,00		1,00	1,00			1,00
	5,00		1,00	1,00			1,00
	5,00		1,00	1,00			1,00
	6,00		1,00	1,00			1,00
	7,00		1,00	1,00			1,00
	8,00		1,00	1,00			1,00
	7,00		1,00	1,00			1,00
			1,00	1,00			1,00
			1,00	1,00	1,00		1,00
			2,00	2,00	2,00		2,00
			10,00		10,00		10,00
							
							-25,00
Sum	38,00		24,00	14,00	13,00		24,00
Mean	3,80		1,71	1,08	4,33		2,58
Var	11,51		5,76	0,08	24,33		6,37
StdDev	3,39		2,40	0,28	4,93		2,52
Coeff	0,89		1,40	0,26	1,14		0,98

(my openoffice seems to come to slightly different values than you)

Edit: Data is based on Sergio's example:

[...]
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.

[...]

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalk.org/index.php?topic=67900.msg804916#msg804916


One problem of both solutions is that with a couple of high fee transactions you can stall the whole network.


Still, there might lay a solution in this direction up ahead.

[Timo Y]

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.

Even better:

CoVar(txfee*priority)

Priority is already used by the protocol. It's defined as:

priority = sum(input_value_in_base_units * input_age)/size_in_bytes


Giving a higher priority transaction a bigger weight makes sense intuitively, since we already use priority as a criterion for excluding certain transactions.

[Sergio_Demian_Lerner]

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.

You are completely right. I can't promise I'll do it in the near future, but I'll start writing it down in a formal way. Also I will take into consideration block-chain statistics and the excellent critics the idea have received.

But if anyone is interested in writing this paper instead of me, be my guest.
Maybe a game-theoretic thesis can come out from this analysis.

[Sergio_Demian_Lerner]

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalk.org/index.php?topic=67900.msg804916#msg804916


One problem of both solutions is that with a couple of high fee transactions you can stall the whole network.


Still, there might lay a solution in this direction up ahead.

Yes, the same idea. And it's a pity it passed unnoticed. I would prefer everybody writes their ideas in the Bitcoin wiki, so the common knowledge is increased.

My idea of discarding the transactions in the 10% of the highest fees before computing CoVar is sound. Obviously miners can manipulate everything, but the point is that they always act rationally, so why would they insert transactions to change the CoVar? And how much time will they invest finding the correct transactions to insert? That problem is, probably, very hard.

[phelix]

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalk.org/index.php?topic=67900.msg804916#msg804916


One problem of both solutions is that with a couple of high fee transactions you can stall the whole network.


Still, there might lay a solution in this direction up ahead.

Yes, the same idea. And it's a pity it passed unnoticed. I would prefer everybody writes their ideas in the Bitcoin wiki, so the common knowledge is increased.

My idea of discarding the transactions in the 10% of the highest fees before computing CoVar is sound. Obviously miners can manipulate everything, but the point is that they always act rationally, so why would they insert transactions to change the CoVar? And how much time will they invest finding the correct transactions to insert? That problem is, probably, very hard.

Should it not be easy to just add a couple of tx with fees at the mean of the normal fees?

Maybe I am missing something but it worked in the example

[blueadept]

Even better:

CoVar(txfee*priority)

Priority is already used by the protocol. It's defined as:

priority = sum(input_value_in_base_units * input_age)/size_in_bytes


Giving a higher priority transaction a bigger weight makes sense intuitively, since we already use priority as a criterion for excluding certain transactions.

This is, at first glance, almost certainly better than my original modification. Makes it more expensive to game the system with low priority coins. And miners can't pay too much to themselves in fees for fear of competitors intentionally orphaning their block to take the fee even despite retep's idea of nLockTime in every transaction, when the disparity between fees and difficulty is too large.

[conv3rsion]

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!

Yea this is good stuff right here.

[phelix]

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalk.org/index.php?topic=67900.msg804916#msg804916


One problem of both solutions is that with a couple of high fee transactions you can stall the whole network.


Still, there might lay a solution in this direction up ahead.

Yes, the same idea. And it's a pity it passed unnoticed. I would prefer everybody writes their ideas in the Bitcoin wiki, so the common knowledge is increased.

My idea of discarding the transactions in the 10% of the highest fees before computing CoVar is sound. Obviously miners can manipulate everything, but the point is that they always act rationally, so why would they insert transactions to change the CoVar? And how much time will they invest finding the correct transactions to insert? That problem is, probably, very hard.

Disregarding the 10% highest fees can easily be skirted by the miners. they just add a couple high fee tx.

The concept will not work like this because with a couple of bitcoins the whole network will stall. say, 100 tx with a fee of 1btc every ten minutes. so at 600btc per hour I can bring everything to a grinding halt or at least slow it down until there are enough low fee tx (should enough fit into a block).

maybe there is a more robust formula. what about this: fees must be higher than half the median of all fees.

naah, I can not think of anything temper proof.


The miners have to dictate / compete for the fees.

[Sukrim]

Disregarding the 10% highest fees can easily be skirted by the miners. they just add a couple high fee tx.

The concept will not work like this because with a couple of bitcoins the whole network will stall. say, 100 tx with a fee of 1btc every ten minutes. so at 600btc per hour I can bring everything to a grinding halt or at least slow it down until there are enough low fee tx (should enough fit into a block).

The reason against miners mining their own money as fees is that if a block gets orphaned, some other miner can claim the money from these transactions.

High fees to drive out lower transactions would work in probably any limitation scenario. If you invest 600 BTC per hour in the current network, you're also probably able to drive out a LOT of transactions.

[Sergio_Demian_Lerner]

maybe there is a more robust formula. what about this: fees must be higher than half the median of all fees.

That formula does not work, it just keeps rising fees.

What about this alternative:

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

2. fees lower than the average are passed through the CoVar test (including the highest part)
(this reduces the changes of spamming txs with almost zero fees)

The key difference is that the average is not taken for the last block, but for a number of past blocks.
I will this method Restricted-CoVar for reference.

This method looks self-healing: 
- if the 50b-average fees goes down, many more transactions with higher fees are included, then the average goes up.
- if the 50b-average goes up too much, then everybody will send lower transaction fees, and the average goes down, but not too fast, since the CoVar limits it.

[phelix]

Disregarding the 10% highest fees can easily be skirted by the miners. they just add a couple high fee tx.

The concept will not work like this because with a couple of bitcoins the whole network will stall. say, 100 tx with a fee of 1btc every ten minutes. so at 600btc per hour I can bring everything to a grinding halt or at least slow it down until there are enough low fee tx (should enough fit into a block).

The reason against miners mining their own money as fees is that if a block gets orphaned, some other miner can claim the money from these transactions.

[...]

Thanks for bringing that up. I had not thought of it and missed it in the discussion above. I assume a typical orphan rate is 1.5%

maybe there is a more robust formula. what about this: fees must be higher than half the median of all fees.

That formula does not work, it just keeps rising fees.

yup  

What about this alternative:

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

2. fees lower than the average are passed through the CoVar test (including the highest part)
(this reduces the changes of spamming txs with almost zero fees)

The key difference is that the average is not taken for the last block, but for a number of past blocks.
I will this method Restricted-CoVar for reference.

This method looks self-healing:  
- if the 50b-average fees goes down, many more transactions with higher fees are included, then the average goes up.
- if the 50b-average goes up too much, then everybody will send lower transaction fees, and the average goes down, but not too fast, since the CoVar limits it.

My gut says this will mostly slow things down but not much more. Miners can still drive up the minimum fees (as long as they don't loose too much because of orphaned blocks).

What about this:
1.) In each block miners vote for a minimum tx fee by the lowest tx fee included. this txFeeMin is averaged over 50 blocks.

Of course miners have an incentive to drive it as high as possible. So to keep up the competition:

2.) txs with fees up to half txFeeMinAvg are valid.

[misterbigg]

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

Do we also allow the block size to exceed the 1 megabyte limit, by not counting the size of these transactions with above-average fees towards the total block size?

[Sergio_Demian_Lerner]

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

Do we also allow the block size to exceed the 1 megabyte limit, by not counting the size of these transactions with above-average fees towards the total block size?

Good, a new idea. Nevertheless there must be a hard limit (say 10 Mbytes) for DoS protection reasons.

[Peter Todd]

1. fees equal or greater than the average fees of the last 50 blocks are always accepted.
(This allows any used to put whatever high fee he may want, and it's predictable)

Do we also allow the block size to exceed the 1 megabyte limit, by not counting the size of these transactions with above-average fees towards the total block size?

...which means large miners can offer "direct-submission" contracts where they accept transactions with above average fees, then refund the fees after they get them mined, minus the orphan rate and some small cut of profit. It'd be a great way for satoshidice to operate for example, and you could submit the same transaction with multiple miners at once if the miners agree to sign their coinbases. (you'll have to audit that the orphans are real, but to do so the miner just has to keep track of every block they produce, orphaned or not)

[misterbigg]

...which means large miners can offer "direct-submission" contracts where they accept transactions with above average fees, then refund the fees after they get them mined, minus the orphan rate and some small cut of profit.

Damnit, I didn't think of that. You're devious!

[phelix]

Let me repost this as I think it might be a way to balance a single miners short time interest with all miners long time interest to hold up transaction fees. It allows for something like a limited extend miners union.

1.) In each block miners vote for a minimum tx fee by the lowest tx fee included. this txFeeMin is averaged over 50 blocks or more (2016?).
2.) txs with fees up to above 0.5 * txFeeMinAvg are valid.


The averaging could be done via a moving average (or even together with difficulty changes).

Of course the factor does not have to be 0.5 - it's choice is critical.