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

phelix

legendary

Activity: 1708

Merit: 1020

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.

misterbigg

legendary

Activity: 1064

Merit: 1001

Quote from: Peter Todd on February 28, 2013, 12:39:44 PM

...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!

Peter Todd

legendary

Activity: 1120

Merit: 1160

Quote from: misterbigg on February 28, 2013, 11:11:27 AM

Quote from: Sergio_Demian_Lerner on February 28, 2013, 08:42:38 AM

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)

Sergio_Demian_Lerner

hero member

Activity: 555

Merit: 654

Quote from: misterbigg on February 28, 2013, 11:11:27 AM

Quote from: Sergio_Demian_Lerner on February 28, 2013, 08:42:38 AM

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.

misterbigg

legendary

Activity: 1064

Merit: 1001

Quote from: Sergio_Demian_Lerner on February 28, 2013, 08:42:38 AM

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?

phelix

legendary

Activity: 1708

Merit: 1020

Quote from: Sukrim on February 28, 2013, 08:20:23 AM

Quote from: phelix on February 28, 2013, 03:19:47 AM

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%

Quote from: Sergio_Demian_Lerner on February 28, 2013, 08:42:38 AM

Quote from: phelix on February 28, 2013, 03:19:47 AM

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

Quote

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.

Sergio_Demian_Lerner

hero member

Activity: 555

Merit: 654

Quote from: phelix on February 28, 2013, 03:19:47 AM

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.

Sukrim

legendary

Activity: 2618

Merit: 1007

Quote from: phelix on February 28, 2013, 03:19:47 AM

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.

phelix

legendary

Activity: 1708

Merit: 1020

Quote from: Sergio_Demian_Lerner on February 27, 2013, 09:32:17 AM

Quote from: phelix on February 27, 2013, 03:58:12 AM

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalksearch.org/topic/m.804916

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.

conv3rsion

sr. member

Activity: 310

Merit: 250

Quote from: misterbigg on February 26, 2013, 02:01:01 PM

Quote from: Sukrim on February 26, 2013, 01:53:29 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!

Yea this is good stuff right here.

blueadept

full member

Activity: 225

Merit: 101

Quote from: Timo Y on February 27, 2013, 08:16:30 AM

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.

phelix

legendary

Activity: 1708

Merit: 1020

Quote from: Sergio_Demian_Lerner on February 27, 2013, 09:32:17 AM

Quote from: phelix on February 27, 2013, 03:58:12 AM

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalksearch.org/topic/m.804916

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

Sergio_Demian_Lerner

hero member

Activity: 555

Merit: 654

Quote from: phelix on February 27, 2013, 03:58:12 AM

A while ago I suggested a maximum spread for transaction fees which is somewhat similar: https://bitcointalksearch.org/topic/m.804916

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.

Sergio_Demian_Lerner

hero member

Activity: 555

Merit: 654

Quote from: Atruk on February 27, 2013, 02:52:25 AM

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.

Timo Y

legendary

Activity: 938

Merit: 1001

bitcoin - the aerogel of money

Quote from: blueadept on February 26, 2013, 01: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(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.

phelix

legendary

Activity: 1708

Merit: 1020

Quote from: Sergio_Demian_Lerner on February 26, 2013, 11:22:57 PM

Quote from: Peter Todd on February 26, 2013, 03:04:05 PM

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:

Quote from: Sergio_Demian_Lerner on February 26, 2013, 11:41:46 PM

[...]
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://bitcointalksearch.org/topic/m.804916

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.

Atruk

hero member

Activity: 700

Merit: 500

Quote from: Maged on February 27, 2013, 02:09:01 AM

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 Wink

) 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.

Maged

legendary

Activity: 1204

Merit: 1015

Quote from: Sergio_Demian_Lerner on February 26, 2013, 11:19:16 PM

Zeilap: This is getting really interesting...

Quote from: Zeilap on February 26, 2013, 05:24:35 PM

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.

farlack

legendary

Activity: 1310

Merit: 1000

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.

Zeilap

full member

Activity: 154

Merit: 100

Quote from: Sergio_Demian_Lerner on February 26, 2013, 11:19:16 PM

Zeilap: This is getting really interesting...

Quote from: Zeilap on February 26, 2013, 05:24:35 PM

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

Topic: A clean solution to ALL Bitcoin problems: SatoshiDice, Block size, future fees. (Read 4370 times)