From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 822478D4 for ; 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 ; Sat, 7 Nov 2015 01:26:13 +0000 (UTC) Received: by igbxm8 with SMTP id xm8so22518764igb.1 for ; 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 Date: Fri, 6 Nov 2015 17:25:53 -0800 Message-ID: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
(My apol= ogies for a 'drive-by' posting. I'm not subscribed to this mail= ing list but this post may be of interest here. If you'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=A0https://medium.com/@bramcohen/how-wallets-can-handle-tran= saction-fees-ff5d020d14fb=C2=A0)

Since transaction f= ees are a good thing (see=C2=A0https://medium.com/@br= amcohen/bitcoin-s-ironic-crisis-32226a85e39f=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=A0https://w= ww.youtube.com/watch?v=3DiKDC2DpzNbw&t=3D13m17s=C2=A0and=C2=A0https://scalingbitcoin.org/montreal2015/pr= esentations/Day1/11-bram_wallet_fees.pdf=C2=A0).

Ground Rules

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 (seehttps://medium.com/@bra= mcohen/the-inevitable-demise-of-unconfirmed-bitcoin-transactions-8b5f66a44a= 35=C2=A0) because the best solution uses that fairly aggressively.

What should transaction fees be?

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

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.

What should th= e wallet user interface be?

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.

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.

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.

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

What information to use

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

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.

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.

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

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

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

Let B =3D max number of blo= cks 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=8A=E2=80=94=E2=80=8Alg(S)) * H= /B)

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

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.
<= br>
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.

Sidebar: Handling ut= xo combining

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.

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.

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.

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.

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. --047d7b3a9bc0e095f10523e93e89--