path: root/02/3a3963386d87d4480ab17b001ea366bc52c249

Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 822478D4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat,  7 Nov 2015 01:26:15 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f169.google.com (mail-ig0-f169.google.com
	[209.85.213.169])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 78C23EC
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat,  7 Nov 2015 01:26:13 +0000 (UTC)
Received: by igbxm8 with SMTP id xm8so22518764igb.1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 06 Nov 2015 17:26:13 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=bittorrent_com.20150623.gappssmtp.com; s=20150623;
	h=mime-version:from:date:message-id:subject:to:content-type;
	bh=B6UG4kW087fA+/fezsHLAeyrBkdAooP7NzegLXujm7A=;
	b=C+4dVdTNtK4KgDWfh24cLi1RCqjhAE1zsQCSwyd9KAHqMwe5Anip0IuxIYpoo7WU/e
	To0RhGE6pb7Ru2DAjBegmuvowEiNvPTB6BcrkfwBJkouPLVuTry+6EJiutwWVui/ImO1
	tq43VrHg3VKi4lhszMc11CBVON1j/OqwW6XFCnjZPHicwzue5DJCFA26xlGIHMRrMZS+
	q1Ni6lrl+dFNJft6/Ql9+VMPUAmKMUTcJzdVumPpPsd2Mpb8P/3FUWo9nunWbypBUIBK
	ofOsVBJDg43URgYidNBkMSBeMGI+b7RVU7tIh7u8pr6gej1lX92fvMeIPGwZzBEQ7Rod
	kFXA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:from:date:message-id:subject:to
	:content-type;
	bh=B6UG4kW087fA+/fezsHLAeyrBkdAooP7NzegLXujm7A=;
	b=WBz3FvdAit3CEmCeM25ZspCQztxynSofhYpHKkp63ZVRFVvAli15BWoNRJPf/LXR17
	v6czySb6fW0JbH1kwJWtINAQv7ns4cW4t7Ys9oAxKBCIpLXFz23gr8oEOGc/pJpmKRZO
	vGBjs9D4phfw3kd0O6LhvMvKdgi2Nv/HexbeDU5KEYECwRjMFnRmrdxLlTqGhB5CpO5S
	vZ2jN9/+O4U84BQ3dRihTHhYBj/POd/FzXRW1VAv3bMcC1WXGzd8YZlX/2mEs6NgW8D1
	9HKoa18j8gfk8YJAVqipzkO/TW1ohRd6buFAPpWlxsuVGZ998EjiKrXBiUc6bzjXHt7u
	nyZw==
X-Gm-Message-State: ALoCoQnaMf4u6YU4Hs/+CRM7HzsH2CJMCa52WbOrd5N7SuOt9XPAsm7xcd3iS1+mvKi+rBArg9lf
X-Received: by 10.50.131.229 with SMTP id op5mr12146418igb.83.1446859572803;
	Fri, 06 Nov 2015 17:26:12 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.5.82 with HTTP; Fri, 6 Nov 2015 17:25:53 -0800 (PST)
From: Bram Cohen <bram@bittorrent.com>
Date: Fri, 6 Nov 2015 17:25:53 -0800
Message-ID: <CA+KqGkq7L_gfaCRobSdaL4paEbhYcGO-j_Gmh_q_=P7CKPVPwQ@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=047d7b3a9bc0e095f10523e93e89
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Sat, 07 Nov 2015 01:36:58 +0000
Subject: [bitcoin-dev] How wallets can handle real transaction fees
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 07 Nov 2015 01:26:15 -0000

--047d7b3a9bc0e095f10523e93e89
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

(My apologies for a 'drive-by' posting. I'm not subscribed to this mailing
list but this post may be of interest here. If you'd like to make sure I
see a response send it to me directly. This post was originally posted to
the web at
https://medium.com/@bramcohen/how-wallets-can-handle-transaction-fees-ff5d0=
20d14fb
 )

Since transaction fees are a good thing (see
https://medium.com/@bramcohen/bitcoin-s-ironic-crisis-32226a85e39f ), that
brings up the question: How should wallets handle them? This essay is an
expansion of my talk at the bitcoin scaling conference (see
https://www.youtube.com/watch?v=3DiKDC2DpzNbw&t=3D13m17s and
https://scalingbitcoin.org/montreal2015/presentations/Day1/11-bram_wallet_f=
ees.pdf
 ).

Ground Rules

To answer this question we first need to lay down some ground rules of what
we=E2=80=99re trying to solve. We=E2=80=99ll focus on trying to solve the p=
roblem for
consumer wallets only. We=E2=80=99ll be ignoring microchannels, which drama=
tically
reduce the number of transactions used but still have to put some on the
blockchain. We=E2=80=99ll also be assuming that full replace by fee is in e=
ffect
(see
https://medium.com/@bramcohen/the-inevitable-demise-of-unconfirmed-bitcoin-=
transactions-8b5f66a44a35
)
because the best solution uses that fairly aggressively.

What should transaction fees be?

Before figuring out how wallets should calculate transaction fees, we first
need to know what transaction fees should be. The obvious solution to that
question is straightforward: It should be determined by supply and demand.
The price is set at the point where the supply and demand curves meet. But
supply and demand curves, while mostly accurate, are a little too simple of
a model to use, because they don=E2=80=99t take into account time. In the r=
eal
world, the supply of space for transactions is extremely noisy, because
more becomes available (and has to be immediately consumed or it=E2=80=99s =
lost
forever) every time a block is minted, and block minting is an
intentionally random process, that randomness being essential for
consensus. Demand is random and cyclical. Random because each transaction
is generated individually so the total amount is noisy (although that
averages out to be somewhat smooth at scale) and has both daily and weekly
cycles, with more transactions done during the day than at night.

What all these result in is that there should be a reward for patience. If
you want or need to get your transaction in quicker you should have to pay
on average a higher fee, and if you=E2=80=99re willing to wait longer it sh=
ould on
average cost less. Inevitably this will result in transactions taking on
average longer than one block to go through, but it doesn=E2=80=99t require=
 it of
everyone. Those who wish to offer high fees to be sure of getting into the
very next block are free to do so, but if everyone were to do that the
system would fall apart.

What should the wallet user interface be?

Ideally transaction fees would be handled in a way which didn=E2=80=99t req=
uire
changes to a wallet=E2=80=99s user interface at all. Unfortunately that isn=
=E2=80=99t
possible. At a minimum it=E2=80=99s necessary to have a maximum fee which t=
he user
is willing to spend in order to make a transaction go through, which of
course means that some transactions will fail because they aren=E2=80=99t w=
illing
to pay enough, which is the whole point of having transaction fees in the
first place.

Because transaction fees should be lower for people willing to wait longer,
there should be some kind of patience parameter as well. The simplest form
of this is an amount of time which the wallet will spend trying to make the
transaction go through before giving up (Technically it may make sense to
specify block height instead of wall clock time, but that=E2=80=99s close e=
nough to
not change anything meaningful). This results in fairly understandable
concepts of a transaction being =E2=80=98pending=E2=80=99 and =E2=80=98fail=
ed=E2=80=99 which happen at
predictable times.

Transactions eventually getting into a =E2=80=98failed=E2=80=99 state inste=
ad of going into
permanent limbo is an important part of the wallet fee user experience.
Unfortunately right now the only way to make sure that a transaction is
permanently failed is to spend its input on something else, but that
requires spending a transaction fee on the canceling transaction, which of
course would be just as big as the fee you weren=E2=80=99t willing to spend=
 to make
the real transaction go through in the first place.

What=E2=80=99s needed is a protocol extension so a transaction can make it
impossible for it to be committed once a certain block height has been
reached. The current lack of such an extension is somewhat intentional
because there are significant potential problems with transactions going
bad because a block reorganization happened and some previously accepted
transactions can=E2=80=99t ever be recommitted because their max block heig=
ht got
surpassed. To combat this, when a transaction with a max block height gets
committed near its cutoff it=E2=80=99s necessary to wait a longer than usua=
l number
of blocks to be sure that it=E2=80=99s safe (I=E2=80=99m intentionally not =
giving specific
numbers here, some developers have suggested extremely conservative
values). This waiting is annoying but should only apply in the edge case of
failed transactions and is straightforward to implement. The really big
problem is that given the way Bitcoin works today it=E2=80=99s very hard to=
 add
this sort of extension. If any backwards-incompatible change to Bitcoin is
done, it would be a very good idea to use that opportunity to improve
Bitcoin=E2=80=99s extension mechanisms in general and this one in particula=
r.

What information to use

The most obvious piece of information to use for setting transaction fees
is past transaction fees from the last few blocks. This has a number of
problems. If the fee rate goes high, it can get stuck there and take a
while to come down, if ever, even though the equilibrium price should be
lower. A telltale sign of this is high fee blocks which aren=E2=80=99t full=
, but
it=E2=80=99s trivial for miners to get around that by padding their blocks =
with
self-paying transactions. To some extent this sort of monopoly pricing is
inherent, but normally it would require a cabal of most miners to pull it
off, because any one miner can make more money in the short term by
accepting every transaction they can instead of restricting the supply of
available transaction space. If transaction fees are sticky, a large but
still minority miner can make money for themselves even in the short term
by artificially pumping fees in one of their blocks because fees will
probably still be high by the time of their next block.

Past fees also create problems for SPV clients, who have to trust the full
nodes they connect to to report past fees accurately. That could be
mitigated by making an extension to the block format to, for example,
report what the minimum fee per bytes paid in this block is in the headers.
It isn=E2=80=99t clear exactly what that extension should do though. Maybe =
you want
to know the minimum, or the median, or the 25th percentile, or all of the
above. It=E2=80=99s also possible for miners to game the system by making a=
 bunch
of full nodes which only report blocks which are a few back when fees have
recently dropped. There are already some incentives to do that sort of bad
behavior, and it can be mitigated by having SPV clients connect to more
full nodes than they currently do and always go with the max work, but SPV
clients don=E2=80=99t currently do that properly, and it=E2=80=99s unfortun=
ate to create
more incentives for bad behavior.

Another potential source of information for transaction fees is currently
pending transactions in the network. This has a whole lot of problems. It=
=E2=80=99s
extremely noisy, much more so than regular transaction fees, because (a)
sometimes a backlog of transactions builds up if no blocks happen to have
happened in a while (b) sometimes there aren=E2=80=99t many transactions if=
 a bunch
of blocks went through quickly, and (c) in the future full nodes can and
should have a policy of only forwarding transactions which are likely to
get accepted sometime soon given the other transactions in their pools.
Mempool is also trivially gameable, in exactly the same way as the last few
blocks are gameable, but worse: A miner who wishes to increase fees can run
a whole lot of full nodes and report much higher fees than are really
happening. Unlike with fee reporting in blocks, there=E2=80=99s no way for =
SPV
clients to audit this properly, even with a protocol extension, and it=E2=
=80=99s
possible for full nodes to lie in a much more precise and targetted manner.
Creating such a strong incentive for such a trivial and potentially
lucrative attack seems like a very bad idea.

A wallet=E2=80=99s best information to use when setting price are the thing=
s which
can be absolutely verified locally: The amount it=E2=80=99s hand to pay in =
the
past, the current time, how much it=E2=80=99s willing to pay by when. All o=
f these
have unambiguous meanings, precise mathematical values, and no way for
anybody else to game them. A wallet can start at a minimum value, and every
time a new block is minted which doesn=E2=80=99t accept its transaction inc=
rease
its fee a little, until finally reaching its maximum value at the very end.
Full nodes can then follow the behavior of storing and forwarding along
several blocks=E2=80=99s worth of transactions, ten times sounds reasonable=
,
ignoring transactions which pay less per byte than the ones they have
stored, and further requiring that a new block be minted between times when
a single transaction gets replaced by fee. That policy both has the
property of being extremely denial-of-service resistant and minimizing the
damage to zeroconf. (Zeroconf is a bad idea, but if something is a good
idea to do for other reasons reducing the pain to those stuck with zeroconf
is a nice bonus.)

An actual formula

At long last, here is the formula I advocate using:

Pick a starting point which is de minimis for your first transaction or 1/2
(or less, configurable) your last fee paid if you=E2=80=99ve sent coin befo=
re

Let B =3D max number of blocks from start before giving up, S =3D starting =
fee,
M =3D max fee

For each new block at height H from the start, post a new transaction with
fee e^(lg(S) + (lg(M) =E2=80=94 lg(S)) * H/B)

To avoid artifacts when multiple wallets use the same magic numbers, do
this before the first block: pick V uniformly in [0, 1], let S =3D e^(lg(S)=
 +
(lg(M) =E2=80=94 lg(S)) * (V/(V+B)))

The very first time you send coin it makes sense to give it a longer time
to do the transaction because it=E2=80=99s starting from a very low value a=
nd you
don=E2=80=99t want to way overshoot the amount necessary. But if you start =
from the
standard absolute minimum fee in Bitcoin and put the maximum time at
several hours it will increase by less than 10% per block, so exponential
growth is on your side.

It might be reasonable to, for example, start at a value which is a
discount to the minimum paid in the last block if that value is less than
what you would start with otherwise and if there=E2=80=99s a protocol exten=
sion to
put that information in the block headers. Such possibilities should be
studied and discussed more, but the formula I gave above should be the
default starting point if you simply want something which works and is
conservative and reliable.

Sidebar: Handling utxo combining

Whenever a wallet makes a payment, it needs to decide how to structure the
inputs and outputs of the new transaction. Generally the output consists of
two utxos, one of them going to the recipient and one of them going back
into the original wallet. Which input or inputs to use is less clear.
Usually an attempt is made to optimize for anonymity, or at least leaking
as little information as possible, and there=E2=80=99s usually a comment in=
 the
code saying what amounts to =E2=80=98I can=E2=80=99t clearly justify any pa=
rticular
strategy here but this is what I=E2=80=99m doing=E2=80=99.

When there are real transaction fees, one might consider trying to optimize
utxo combining for fees. The strategy used turns out to matter surprisingly
little for fees in the long run. For every separate utxo in your wallet,
you=E2=80=99ll eventually have to pay the fee to combine it with something =
else,
and the amount of increase in fee will be the same regardless of whether
you do it in the current transaction or a later transaction. It does make
sense to include more inputs in earlier versions of a payment though,
because the fees at that time are lower, and drop them in later versions
once the fees have gone up, in the hopes that the utxo consolidation can be
done for cheaper in some later transaction. It may also make sense to do
completely separate purely consolidation transactions with no external
output during off-peak times. That puts more bytes on the blockchain
because of the unnecessary intermediary value it generates though, so there
needs to be a significant difference in fees between peak and off-peak
times for it to make sense. Both of those techniques have significant and
unclear privacy implications and should be studied more.

There are also signing tricks which could potentially save significant
amounts of bytes on the blockchain, thus lowering fees. The most elegant
would be to create a new extension so that when there are multiple inputs
to a transaction which all use Schnorr the signature can be a single
combination signature instead of separate signatures for each of them. This
has very little downside and I=E2=80=99m strongly in favor of it being done=
.

A simpler, less elegant trick which saves more bytes would be to allow
multiple inputs to the same transaction which use the same key to only
result in a single signature. This lowers privacy, because it gives away
the association between utxos before they=E2=80=99re consolidated, but if u=
sed
properly would only push back that reveal a little bit. The danger is that
wallets would instead use it improperly and use the same key all the time,
which would always save as many bytes as possible but be a privacy disaster=
.

A trick which is a just plain bad idea, although it would save even more
bytes, would be not count the bytes of the reveal of a p2sh script to count
if that exact same script has ever been used before. This is clearly a bad
idea, because it directly encourages extremely privacy-averse behavior, and
because it necessitates a data structure of all p2sh scripts which have
ever been done before for validation, which is quite large and costly to
maintain.

--047d7b3a9bc0e095f10523e93e89
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><span style=3D"color:rgb(0,0,0);font-size:12.8px">(My apol=
ogies for a &#39;drive-by&#39; posting. I&#39;m not subscribed to this mail=
ing list but this post may be of interest here. If you&#39;d like to make s=
ure I see a response send it to me directly. This post was originally poste=
d to the web at=C2=A0</span><a href=3D"https://medium.com/@bramcohen/how-wa=
llets-can-handle-transaction-fees-ff5d020d14fb" target=3D"_blank" style=3D"=
font-size:12.8px">https://medium.com/@bramcohen/how-wallets-can-handle-tran=
saction-fees-ff5d020d14fb</a><span style=3D"color:rgb(0,0,0);font-size:12.8=
px">=C2=A0)</span><div style=3D"color:rgb(0,0,0);font-size:12.8px"><br></di=
v><div style=3D"color:rgb(0,0,0);font-size:12.8px"><div>Since transaction f=
ees are a good thing (see=C2=A0<a href=3D"https://medium.com/@bramcohen/bit=
coin-s-ironic-crisis-32226a85e39f" target=3D"_blank">https://medium.com/@br=
amcohen/bitcoin-s-ironic-crisis-32226a85e39f</a>=C2=A0), that brings up the=
 question: How should wallets handle them? This essay is an expansion of my=
 talk at the bitcoin scaling conference (see=C2=A0<a href=3D"https://www.yo=
utube.com/watch?v=3DiKDC2DpzNbw&amp;t=3D13m17s" target=3D"_blank">https://w=
ww.youtube.com/watch?v=3DiKDC2DpzNbw&amp;t=3D13m17s</a>=C2=A0and=C2=A0<a hr=
ef=3D"https://scalingbitcoin.org/montreal2015/presentations/Day1/11-bram_wa=
llet_fees.pdf" target=3D"_blank">https://scalingbitcoin.org/montreal2015/pr=
esentations/Day1/11-bram_wallet_fees.pdf</a>=C2=A0).</div><div><br></div><d=
iv>Ground Rules</div><div><br></div><div>To answer this question we first n=
eed to lay down some ground rules of what we=E2=80=99re trying to solve. We=
=E2=80=99ll focus on trying to solve the problem for consumer wallets only.=
 We=E2=80=99ll be ignoring microchannels, which dramatically reduce the num=
ber of transactions used but still have to put some on the blockchain. We=
=E2=80=99ll also be assuming that full replace by fee is in effect (see<a h=
ref=3D"https://medium.com/@bramcohen/the-inevitable-demise-of-unconfirmed-b=
itcoin-transactions-8b5f66a44a35" target=3D"_blank">https://medium.com/@bra=
mcohen/the-inevitable-demise-of-unconfirmed-bitcoin-transactions-8b5f66a44a=
35</a>=C2=A0) because the best solution uses that fairly aggressively.</div=
><div><br></div><div>What should transaction fees be?</div><div><br></div><=
div>Before figuring out how wallets should calculate transaction fees, we f=
irst need to know what transaction fees should be. The obvious solution to =
that question is straightforward: It should be determined by supply and dem=
and. The price is set at the point where the supply and demand curves meet.=
 But supply and demand curves, while mostly accurate, are a little too simp=
le of a model to use, because they don=E2=80=99t take into account time. In=
 the real world, the supply of space for transactions is extremely noisy, b=
ecause more becomes available (and has to be immediately consumed or it=E2=
=80=99s lost forever) every time a block is minted, and block minting is an=
 intentionally random process, that randomness being essential for consensu=
s. Demand is random and cyclical. Random because each transaction is genera=
ted individually so the total amount is noisy (although that averages out t=
o be somewhat smooth at scale) and has both daily and weekly cycles, with m=
ore transactions done during the day than at night.</div><div><br></div><di=
v>What all these result in is that there should be a reward for patience. I=
f you want or need to get your transaction in quicker you should have to pa=
y on average a higher fee, and if you=E2=80=99re willing to wait longer it =
should on average cost less. Inevitably this will result in transactions ta=
king on average longer than one block to go through, but it doesn=E2=80=99t=
 require it of everyone. Those who wish to offer high fees to be sure of ge=
tting into the very next block are free to do so, but if everyone were to d=
o that the system would fall apart.</div><div><br></div><div>What should th=
e wallet user interface be?</div><div><br></div><div>Ideally transaction fe=
es would be handled in a way which didn=E2=80=99t require changes to a wall=
et=E2=80=99s user interface at all. Unfortunately that isn=E2=80=99t possib=
le. At a minimum it=E2=80=99s necessary to have a maximum fee which the use=
r is willing to spend in order to make a transaction go through, which of c=
ourse means that some transactions will fail because they aren=E2=80=99t wi=
lling to pay enough, which is the whole point of having transaction fees in=
 the first place.</div><div><br></div><div>Because transaction fees should =
be lower for people willing to wait longer, there should be some kind of pa=
tience parameter as well. The simplest form of this is an amount of time wh=
ich the wallet will spend trying to make the transaction go through before =
giving up (Technically it may make sense to specify block height instead of=
 wall clock time, but that=E2=80=99s close enough to not change anything me=
aningful). This results in fairly understandable concepts of a transaction =
being =E2=80=98pending=E2=80=99 and =E2=80=98failed=E2=80=99 which happen a=
t predictable times.</div><div><br></div><div>Transactions eventually getti=
ng into a =E2=80=98failed=E2=80=99 state instead of going into permanent li=
mbo is an important part of the wallet fee user experience. Unfortunately r=
ight now the only way to make sure that a transaction is permanently failed=
 is to spend its input on something else, but that requires spending a tran=
saction fee on the canceling transaction, which of course would be just as =
big as the fee you weren=E2=80=99t willing to spend to make the real transa=
ction go through in the first place.</div><div><br></div><div>What=E2=80=99=
s needed is a protocol extension so a transaction can make it impossible fo=
r it to be committed once a certain block height has been reached. The curr=
ent lack of such an extension is somewhat intentional because there are sig=
nificant potential problems with transactions going bad because a block reo=
rganization happened and some previously accepted transactions can=E2=80=99=
t ever be recommitted because their max block height got surpassed. To comb=
at this, when a transaction with a max block height gets committed near its=
 cutoff it=E2=80=99s necessary to wait a longer than usual number of blocks=
 to be sure that it=E2=80=99s safe (I=E2=80=99m intentionally not giving sp=
ecific numbers here, some developers have suggested extremely conservative =
values). This waiting is annoying but should only apply in the edge case of=
 failed transactions and is straightforward to implement. The really big pr=
oblem is that given the way Bitcoin works today it=E2=80=99s very hard to a=
dd this sort of extension. If any backwards-incompatible change to Bitcoin =
is done, it would be a very good idea to use that opportunity to improve Bi=
tcoin=E2=80=99s extension mechanisms in general and this one in particular.=
</div><div><br></div><div>What information to use</div><div><br></div><div>=
The most obvious piece of information to use for setting transaction fees i=
s past transaction fees from the last few blocks. This has a number of prob=
lems. If the fee rate goes high, it can get stuck there and take a while to=
 come down, if ever, even though the equilibrium price should be lower. A t=
elltale sign of this is high fee blocks which aren=E2=80=99t full, but it=
=E2=80=99s trivial for miners to get around that by padding their blocks wi=
th self-paying transactions. To some extent this sort of monopoly pricing i=
s inherent, but normally it would require a cabal of most miners to pull it=
 off, because any one miner can make more money in the short term by accept=
ing every transaction they can instead of restricting the supply of availab=
le transaction space. If transaction fees are sticky, a large but still min=
ority miner can make money for themselves even in the short term by artific=
ially pumping fees in one of their blocks because fees will probably still =
be high by the time of their next block.</div><div><br></div><div>Past fees=
 also create problems for SPV clients, who have to trust the full nodes the=
y connect to to report past fees accurately. That could be mitigated by mak=
ing an extension to the block format to, for example, report what the minim=
um fee per bytes paid in this block is in the headers. It isn=E2=80=99t cle=
ar exactly what that extension should do though. Maybe you want to know the=
 minimum, or the median, or the 25th percentile, or all of the above. It=E2=
=80=99s also possible for miners to game the system by making a bunch of fu=
ll nodes which only report blocks which are a few back when fees have recen=
tly dropped. There are already some incentives to do that sort of bad behav=
ior, and it can be mitigated by having SPV clients connect to more full nod=
es than they currently do and always go with the max work, but SPV clients =
don=E2=80=99t currently do that properly, and it=E2=80=99s unfortunate to c=
reate more incentives for bad behavior.</div><div><br></div><div>Another po=
tential source of information for transaction fees is currently pending tra=
nsactions in the network. This has a whole lot of problems. It=E2=80=99s ex=
tremely noisy, much more so than regular transaction fees, because (a) some=
times a backlog of transactions builds up if no blocks happen to have happe=
ned in a while (b) sometimes there aren=E2=80=99t many transactions if a bu=
nch of blocks went through quickly, and (c) in the future full nodes can an=
d should have a policy of only forwarding transactions which are likely to =
get accepted sometime soon given the other transactions in their pools. Mem=
pool is also trivially gameable, in exactly the same way as the last few bl=
ocks are gameable, but worse: A miner who wishes to increase fees can run a=
 whole lot of full nodes and report much higher fees than are really happen=
ing. Unlike with fee reporting in blocks, there=E2=80=99s no way for SPV cl=
ients to audit this properly, even with a protocol extension, and it=E2=80=
=99s possible for full nodes to lie in a much more precise and targetted ma=
nner. Creating such a strong incentive for such a trivial and potentially l=
ucrative attack seems like a very bad idea.</div><div><br></div><div>A wall=
et=E2=80=99s best information to use when setting price are the things whic=
h can be absolutely verified locally: The amount it=E2=80=99s hand to pay i=
n the past, the current time, how much it=E2=80=99s willing to pay by when.=
 All of these have unambiguous meanings, precise mathematical values, and n=
o way for anybody else to game them. A wallet can start at a minimum value,=
 and every time a new block is minted which doesn=E2=80=99t accept its tran=
saction increase its fee a little, until finally reaching its maximum value=
 at the very end. Full nodes can then follow the behavior of storing and fo=
rwarding along several blocks=E2=80=99s worth of transactions, ten times so=
unds reasonable, ignoring transactions which pay less per byte than the one=
s they have stored, and further requiring that a new block be minted betwee=
n times when a single transaction gets replaced by fee. That policy both ha=
s the property of being extremely denial-of-service resistant and minimizin=
g the damage to zeroconf. (Zeroconf is a bad idea, but if something is a go=
od idea to do for other reasons reducing the pain to those stuck with zeroc=
onf is a nice bonus.)</div><div><br></div><div>An actual formula</div><div>=
<br></div><div>At long last, here is the formula I advocate using:</div><di=
v><br></div><div>Pick a starting point which is de minimis for your first t=
ransaction or 1/2 (or less, configurable) your last fee paid if you=E2=80=
=99ve sent coin before</div><div><br></div><div>Let B =3D max number of blo=
cks from start before giving up, S =3D starting fee, M =3D max fee</div><di=
v><br></div><div>For each new block at height H from the start, post a new =
transaction with fee e^(lg(S) + (lg(M)=E2=80=8A=E2=80=94=E2=80=8Alg(S)) * H=
/B)</div><div><br></div><div>To avoid artifacts when multiple wallets use t=
he same magic numbers, do this before the first block: pick V uniformly in =
[0, 1], let S =3D e^(lg(S) + (lg(M)=E2=80=8A=E2=80=94=E2=80=8Alg(S)) * (V/(=
V+B)))</div><div><br></div><div>The very first time you send coin it makes =
sense to give it a longer time to do the transaction because it=E2=80=99s s=
tarting from a very low value and you don=E2=80=99t want to way overshoot t=
he amount necessary. But if you start from the standard absolute minimum fe=
e in Bitcoin and put the maximum time at several hours it will increase by =
less than 10% per block, so exponential growth is on your side.</div><div><=
br></div><div>It might be reasonable to, for example, start at a value whic=
h is a discount to the minimum paid in the last block if that value is less=
 than what you would start with otherwise and if there=E2=80=99s a protocol=
 extension to put that information in the block headers. Such possibilities=
 should be studied and discussed more, but the formula I gave above should =
be the default starting point if you simply want something which works and =
is conservative and reliable.</div><div><br></div><div>Sidebar: Handling ut=
xo combining</div><div><br></div><div>Whenever a wallet makes a payment, it=
 needs to decide how to structure the inputs and outputs of the new transac=
tion. Generally the output consists of two utxos, one of them going to the =
recipient and one of them going back into the original wallet. Which input =
or inputs to use is less clear. Usually an attempt is made to optimize for =
anonymity, or at least leaking as little information as possible, and there=
=E2=80=99s usually a comment in the code saying what amounts to =E2=80=98I =
can=E2=80=99t clearly justify any particular strategy here but this is what=
 I=E2=80=99m doing=E2=80=99.</div><div><br></div><div>When there are real t=
ransaction fees, one might consider trying to optimize utxo combining for f=
ees. The strategy used turns out to matter surprisingly little for fees in =
the long run. For every separate utxo in your wallet, you=E2=80=99ll eventu=
ally have to pay the fee to combine it with something else, and the amount =
of increase in fee will be the same regardless of whether you do it in the =
current transaction or a later transaction. It does make sense to include m=
ore inputs in earlier versions of a payment though, because the fees at tha=
t time are lower, and drop them in later versions once the fees have gone u=
p, in the hopes that the utxo consolidation can be done for cheaper in some=
 later transaction. It may also make sense to do completely separate purely=
 consolidation transactions with no external output during off-peak times. =
That puts more bytes on the blockchain because of the unnecessary intermedi=
ary value it generates though, so there needs to be a significant differenc=
e in fees between peak and off-peak times for it to make sense. Both of tho=
se techniques have significant and unclear privacy implications and should =
be studied more.</div><div><br></div><div>There are also signing tricks whi=
ch could potentially save significant amounts of bytes on the blockchain, t=
hus lowering fees. The most elegant would be to create a new extension so t=
hat when there are multiple inputs to a transaction which all use Schnorr t=
he signature can be a single combination signature instead of separate sign=
atures for each of them. This has very little downside and I=E2=80=99m stro=
ngly in favor of it being done.</div><div><br></div><div>A simpler, less el=
egant trick which saves more bytes would be to allow multiple inputs to the=
 same transaction which use the same key to only result in a single signatu=
re. This lowers privacy, because it gives away the association between utxo=
s before they=E2=80=99re consolidated, but if used properly would only push=
 back that reveal a little bit. The danger is that wallets would instead us=
e it improperly and use the same key all the time, which would always save =
as many bytes as possible but be a privacy disaster.</div><div><br></div><d=
iv>A trick which is a just plain bad idea, although it would save even more=
 bytes, would be not count the bytes of the reveal of a p2sh script to coun=
t if that exact same script has ever been used before. This is clearly a ba=
d idea, because it directly encourages extremely privacy-averse behavior, a=
nd because it necessitates a data structure of all p2sh scripts which have =
ever been done before for validation, which is quite large and costly to ma=
intain.</div></div></div>

--047d7b3a9bc0e095f10523e93e89--