[Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Sergio Lerner]

[-- Attachment #1: Type: text/plain, Size: 3867 bytes --]

Two years ago I presented a new way to create a fee market that does not
depend on the block chain limit.

This proposal has not been formally analyzed in any paper since then,
but I think it holds a good promise to untangle the current problem
regarding increasing the tps and creating the fee market. BTW, think the
maximum tps should be increased, but not by increasing the block size,
but by increasing the block rate (I'll expose why in my next e-mail).

The original post is here (I was overly optimistic back then):
https://bitcointalk.org/index.php?topic=147124.msg1561612#msg1561612

I'll summarize it here again, with a little editing and a few more
questions at the end:

The idea is simple, but requires 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
dispersion below a threshold. Use, for example, the Coefficient of
Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If
the CoVar is higher than a fixed threshold, the block is considered 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 on the
scale*, so is just what a coin with a floating price 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 reduces the Tx spamming Problem?*

Using this little modification, spamming users 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 helps solving **the tragedy-of-the-commons fee "problem"?*

As miners are forced to keep the CoVar below the threshold, if people
rises the fees to confirm faster than spamming txs, automatically
smamming txs become less likely to appear in blocks, and fee-estimators
will automatically increase future fees, creating a the desired feedback
loop.

*Why it helps solving the block size problem?*

Because if we increase the block size, miners that do not care about the
fee market won't be able to fill the block with spamming txs and destroy
the market that is being created. This is not a solution against an
attacker-miner, which can always fill the block with transactions.

*Can the system by gamed? Can it be attacked?*

I don't think so. An attacker would need to spend a high amount in fees
to prevent transactions with low fees to be included in a block.
However, a formal analysis would be required. Miller, Gun Sirer, Eyal..
Want to give it a try?
*
Can create a positive feedback to a rise the fees to the top or push
fess to the bottom?

*Again, I don't think so. This depends on the dynamics between the each
node's fee estimator and the transaction backlog. MIT guys?

*Doesn't it force miners to run more complex algorithms (such as linear
programming) to find the optimum tx subset ?

*Yes, but I don't see it as a drawback, but as a positive stimulus for
researchers to develop better tx selection algorithms. Anyway, the
greedy algorithm of picking the transactions with highest fees fees
would be good enough.

*
PLEASE don't confuse the acronym CoVar I used here with co-variance.*

Best regard,
  Sergio.




[-- Attachment #2: Type: text/html, Size: 4985 bytes --]

Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1239 bytes --]

On Sun, May 10, 2015 at 05:45:32PM -0300, Sergio Lerner wrote:
> Two years ago I presented a new way to create a fee market that does not
> depend on the block chain limit.

<snip>

> Solution: Require that the set of fees collected in a block has a
> dispersion below a threshold. Use, for example, the Coefficient of
> Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If
> the CoVar is higher than a fixed threshold, the block is considered invalid.

It's not possible to create consensus rules enforcing anything about
fees because it's trivial to pay miners out of band.

For instance, you can pay transaction fees by including anyone-can-spend
outputs in your transactions. The miner creating the block then simply
adds a transaction at the end of their block collecting all the
anyone-can-spend outputs. Equally, if you try to prohibit that - e.g. by
preventing respending of funds in the same block - they can simply
publish fee addresses and have people put individual outputs for those
addresses in their transactions. (IIRC Eligius gave people the option to
pay fees that way for awhile)

-- 
'peter'[:-1]@petertodd.org
00000000000000000fa57b40dc86a61d35aaf9241c86f047ef6f4bab8f13dfb7

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Gregory Maxwell]

On Sun, May 10, 2015 at 8:45 PM, Sergio Lerner
<sergiolerner@certimix.com> wrote:
> Can the system by gamed?

Users can pay fees or a portion of fees out of band to miner(s); this
is undetectable to the network.

It's also behavior that miners have engaged in since at least 2011 (in
two forms;  treating transactions that paid them directly via outputs
as having that much more in fees;  and taking contracts for fast
processing for identified transactions (e.g. address matching or via
an API) e.g. "I'll pay you x at the end of the month for each of my
transactions you process, you can poll this API". I'm aware of at
least two companies having had this arrangement with miners).

I think what you suggested then just further rewards this behavior as
it allows bypassing your controls.-- I suspect generally any scheme
the looks at the fee values has this property.

Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Stephen]

[-- Attachment #1: Type: text/plain, Size: 5616 bytes --]

Why do so many tie the block size debate to creating "a fee market", as if one didn't already exist? Yes, today we frequently see many low priority transactions included into the next block, but that does not mean there is not a marketplace for block space. It just means miners are not being sufficiently tough to create a *competitive* marketplace. 

But who are we to say that the marketplace should be more competitive, and to go further and try to force it by altering consensus rules like the block size limit? If miners want to see more competitive fees, then they need only to alter their block creation protocol. 

There are many arguments for and against changing the consensus limit on block size. I'm simply saying that "to force a marketplace for fees/block space" should not be one of them. Let the market develop on it's own. 

- Stephen



> On May 10, 2015, at 4:45 PM, Sergio Lerner <sergiolerner@certimix.com> wrote:
> 
> Two years ago I presented a new way to create a fee market that does not depend on the block chain limit.
> 
> This proposal has not been formally analyzed in any paper since then, but I think it holds a good promise to untangle the current problem regarding increasing the tps and creating the fee market. BTW, think the maximum tps should be increased, but not by increasing the block size, but by increasing the block rate (I'll     expose why in my next e-mail).
> 
> The original post is here (I was overly optimistic back then): https://bitcointalk.org/index.php?topic=147124.msg1561612#msg1561612
> 
> I'll summarize it here again, with a little editing and a few more questions at the end:
> 
> The idea is simple, but requires 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 dispersion below a threshold. Use, for example, the Coefficient of Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If the CoVar is higher than a fixed threshold, the block is considered 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 on the scale, so is just what a coin with a floating price 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 reduces the Tx spamming Problem?
> 
> Using this little modification, spamming users 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 helps solving the tragedy-of-the-commons fee "problem"?
> 
> As miners are forced to keep the CoVar below the threshold, if people rises the fees to confirm faster than spamming txs, automatically smamming txs become less likely to appear in blocks, and fee-estimators will automatically increase future fees, creating a the desired feedback loop.
> 
> Why it helps solving the block size problem?
> 
> Because if we increase the block size, miners that do not care about the fee market won't be able to fill the block with spamming txs and destroy the market that is being created. This is not a solution against an attacker-miner, which can always fill the block with transactions.
> 
> Can the system by gamed? Can it be attacked?
> 
> I don't think so. An attacker would need to spend a high amount in fees to prevent transactions with low fees to be included in a block. 
> However, a formal analysis would be required. Miller, Gun Sirer, Eyal.. Want to give it a try?
> 
> Can create a positive feedback to a rise the fees to the top or push fess to the bottom?
> 
> Again, I don't think so. This depends on the dynamics between the each node's fee estimator and the transaction backlog. MIT guys? 
> 
> Doesn't it force miners to run more complex algorithms (such as linear programming) to find the optimum tx subset ?
> 
> Yes, but I don't see it as a drawback, but as a positive stimulus for researchers to develop better tx selection algorithms. Anyway, the greedy algorithm of picking the transactions with highest fees fees would be good enough. 
> 
> 
> PLEASE don't confuse the acronym CoVar I used here with co-variance.
> 
> Best regard,
>   Sergio.
> 
> 
> 
> ------------------------------------------------------------------------------
> One dashboard for servers and applications across Physical-Virtual-Cloud 
> Widest out-of-the-box monitoring support with 50+ applications
> Performance metrics, stats and reports that give you Actionable Insights
> Deep dive visibility with transaction tracing using APM Insight.
> http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[-- Attachment #2: Type: text/html, Size: 7494 bytes --]

Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Sergio Lerner]

El 10/05/2015 06:07 p.m., Gregory Maxwell escribió:
> On Sun, May 10, 2015 at 8:45 PM, Sergio Lerner
> <sergiolerner@certimix.com> wrote:
>> Can the system by gamed?
> Users can pay fees or a portion of fees out of band to miner(s); this
> is undetectable to the network.
Then this is exactly what is needed. Let me explain.

I know of 5 methods for a user to pay fees to a miner. I will explain
each method and why these methods do not prevent the fee market from
being created:

1) By transaction fees

This is the standard, which would be limited by the CoVar algorithm, and
would create the fee market, if it were the only way to pay fees.

2) By creating multiple transactions, each adding an output that pays to
each miner (to a known miner address) the fees. User does not
pre-negotiate anything with miners.

This requires a transaction to have an additional output and requires
sending through the p2p network one different transaction to each miner,
each having an output with a "known" address of that miner. But the
network does not propagates double-spends, so those transaction would
need to be sent directly to the top miners, and to all at the same time.
The IP addresses of the top miners are not generally publicly available,
and then may not accept new incoming connections. Also having an
additional output means the transactions would be larger, so they will
score lower by any metric the miner uses to choose transactions. Last,
miners must be programmed to automatically interpret payments to their
addresses as fees. The resulting protocol is very difficult to do
reliably, expensive, as any delay would make one miner receive the
transaction from other miner and reject the double-spend that is being
send directly to it, increasing the average confirmation time.

3) By adding an anyone-can-spend output for fees, so the miner can spend
that output in the same block.  User does not pre-negotiate anything
with miners.

We can hard-fork not to allow spending outputs created in the same
block. This is a drawback, unless we reduce the block rate, which is my
proposal. However, spending in the same block also requires an storing
in the block an additional input, which consumes at least 40 bytes more,
and the transaction containing the input cannot be relayed to the
network in advance. Then the block that uses this method to collect fees
from many transactions will propagate slower, and the miner may end
loosing money. The any-one-can-spend output would take approximately 10
bytes. So if transmitting 10+40=50 bytes, cost more than the fees
earned, then miners do not have an incentive to game the system. It's
has been studied that "each kilobyte costs an additional 80ms delay
until a majority knows about the block." (Information propagation in the
Bitcoin network). So 50 bytes costs 3.9 ms in propagation time, which
having a a 25 BTC subsidy is roughly equivalent to 0.2 mBTC. Currently
this is more than what transactions do pay in fees (about 0.1 mBTC), so
this should not be a problem for at least 5 years. And again, we could
just prevent spending outputs in the same block they are created.

4) Using a transaction having a single input having exactly the desired
output amount plus fees and signing the input with SIGHASH_SINGLE |
SIGHASH_ANYONECANPAY and adding to the transaction a single output with
the desired amount. The miner will be able to join many of these
transactions and finally add an output to collect all fees together,
without using standard transaction fees.

This is unreliable and cannot be systematically repeated without
creating a pre-transaction just to prepare the single input having the
amount plus fees exactly. The pre-transaction would need to pay fees, so
the problem is not avoided, just moved around.

5) By negotiating out of band with the miner previously. Anything could
be agreed by the user and the miner.

This actually creates a parallel out-of-band market for fees, which is
exactly what we want. If a user-to-miner pre-negotiation will take
place, then the miner can establish whatever price policy he wants to
compete and stay in business, as block data propagation costs money. So
there will be two fee markets, the "out-of-band" market, and the
"in-band" market, and both should converge.

My conclusion is that fee markets will be created, and any alternate
fee-paying methods (without a pre-negotiation) are not reliable nor
cost-saving options. The full proposal would be to use the CoVar method,
reduce the block rate to 1 minute, and do not allow spending outputs in
the same block they are created.

Best regards,
 Sergio.