From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1US9r7-0002V2-Pt for bitcoin-development@lists.sourceforge.net; Tue, 16 Apr 2013 17:39:45 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.214.170 as permitted sender) client-ip=209.85.214.170; envelope-from=mh.in.england@gmail.com; helo=mail-ob0-f170.google.com; Received: from mail-ob0-f170.google.com ([209.85.214.170]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1US9r6-00015R-Aa for bitcoin-development@lists.sourceforge.net; Tue, 16 Apr 2013 17:39:45 +0000 Received: by mail-ob0-f170.google.com with SMTP id x4so687765obh.15 for ; Tue, 16 Apr 2013 10:39:39 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.28.37 with SMTP id y5mr1248280oeg.134.1366133978880; Tue, 16 Apr 2013 10:39:38 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.167.169 with HTTP; Tue, 16 Apr 2013 10:39:38 -0700 (PDT) Date: Tue, 16 Apr 2013 19:39:38 +0200 X-Google-Sender-Auth: xadArydFDu0Yyr8E8-tQnCjKk8c Message-ID: From: Mike Hearn To: Bitcoin Dev Content-Type: multipart/alternative; boundary=e89a8fb1f7f086e71004da7dda76 X-Spam-Score: -0.5 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (mh.in.england[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.0 T_FRT_PROFILE2 BODY: ReplaceTags: Profile (2) 0.0 T_FRT_PROFILE1 BODY: ReplaceTags: Profile (1) 1.0 HTML_MESSAGE BODY: HTML included in message 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1US9r6-00015R-Aa Subject: [Bitcoin-development] Anti DoS for tx replacement X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Apr 2013 17:39:46 -0000 --e89a8fb1f7f086e71004da7dda76 Content-Type: text/plain; charset=UTF-8 This was previously discussed on the forums a bunch of times, but in particular here: https://bitcointalk.org/index.php?topic=91732.0 BTW, I don't think all this has to be solved to re-activate replacement on testnet. It's useful for people to be able to develop apps that use this feature, indeed, it helps build the case for re-activating it on the main network after the necessary work is done. Otherwise there'll inevitably be people who say "why re-activate something even though we think it's safe when there are no use cases for it". Letting people develop and deploy interesting prototypes in parallel solves that catch-22. --- Refresher: since the first release Bitcoin has had the ability to replace transactions that sit in the memory pool if the transaction is non-final, the inputs are the same and the replacement is newer than the replacee. Being non-final means not having reached the nLockTime threshold, and having at least one input with a sequence number < UINT_MAX. Around the time of the bugs in various opcodes being found, Satoshi disabled the feature because nothing was using it - it was something he'd planned for the future, it had no utility in the Bitcoin of 2010. The purpose of tx replacement is to implement high frequency trading, according to material Satoshi sent me when I asked him what it was all for (I wanted to know why sequence numbers were a property of inputs not the transaction). It's very important to understand that this does *NOT* mean high-frequency from the networks perspective. In normal operation, tx replacement is not actually intended to be used at all. Sort of like double-spending protection, it's a code path that's only meant to be triggered when one or the other party is maliciously trying to roll back a negotiated contract. And when a party is trying to do that, you don't need lots of replacements. A single replacement is enough. To see why this is the case please review the micropayment channel protocol here: https://en.bitcoin.it/wiki/Contracts#Example_7:_Rapidly-adjusted_.28micro.29payments_to_a_pre-determined_party This isn't the only use of contractual HFT in Bitcoin, it's a deliberately simplified and stripped down example (eg, that only uses two parties). The example Satoshi gave me was more abstract and actually had N parties in it - it left me puzzled for a while and struggling to see practical application. The "billing for a metered resource" use case is easier to understand. Now the obvious problem is that even though the feature is only intended to be used occasionally or never, nothing in the existing code stops you using it as fast as possible and exhausting nodes CPU time and bandwidth. What's more, solving this is not as easy as it looks. Most proposed solutions will not work: 1) Requiring higher fees for each replacement means that a channel/contract has to be torn down and rebuilt much, much faster than before because otherwise the amount of money lost to fees quickly becomes the entire size of the channel (or you can't update it very often). Remember, you'd have to increase the fee for each replacement regardless of whether it's presented to the network or not. As the whole point of the setup is to avoid putting lots of transactions on the network, anything that pushes you back towards doing that undermines the entire utility of the system. 2) Refusing to update the transaction after certain thresholds are reached, having cooldown periods, etc also won't work because the replacement mechanism is there to protect each counter-party in the HFT contract. Simply converting a DoS on the network to a DoS on the participants means one malicious party can break the mechanism that protects all the others by broadcasting the initial set of updates all at once and deliberately tripping the thresholds. OK, let's take a step back. What is the purpose of abusing this feature? It's to mount a denial of service attack - either against the entire Bitcoin network, or against the other participants in the contract. But someone, somewhere has to be denied service, otherwise the attack is pointless. We can exploit this fact by realising that typically anti-DoS is a prioritisation problem. It doesn't usually matter if you serve some abusive traffic if all legitimate traffic gets served first because it removes the denial of service from the attack, and usually there are lots of ways to attack someone with methods that don't work - real world experience indicates that people don't pointlessly mount attacks over and over again if there's nothing to be gained by doing so. So we can do the following - multi-thread verification of transactions that are trying to enter the memory pool, and order them such that high priority transactions are verified first, low priority next, and then replacements of transactions sorted by age of last replacement. Same thing for relaying - faced with getdatas, service the new transactions first, replacements with whatever is left over. Drop whatever doesn't make it into the nodes available resources. Handling DoS as a prioritisation problem has a number of advantages, most obviously not introducing new hard coded magic numbers that may or may not stay up to date with changing conditions. This setup means someone can force CPU/bandwidth usage to whatever the node operators have configured as their max allowed across the network for a while, but doing so won't actually disrupt normal transactions. It'll just result in the replacements getting dropped. It slightly increases the risk of a malicious counter-party in an HFT contract trying to take advantage of the saturation to themselves execute an attack on the contract, but I doubt it'd be a problem in practice - you'd need to write your software to be able to perform such an attack, most of the time it wouldn't work, and if people saturate the network with low priority easily dropped transactions so that it would work then nodes/apps could just warn users not to take advantage of the feature whilst the flood is in progress. I know that some people will object to such a design on principle, but I think this is a good balance - the only attacks that exist aren't profitable and the worst case outcome in the face of continual profitless abuse is we switch the feature off and end up no worse off than today. I haven't touched on the topic of cartels of malicious miners or other topics, just DoS. This email is long enough already and handling malicious miners (if necessary) can be done at the application protocol level, it doesn't need any changes to the core tx replacement / locktime mechanism. --e89a8fb1f7f086e71004da7dda76 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
This was previously discussed on the forums a b= unch of times, but in particular here:


BTW, I don't think all this has to be solved to re-= activate replacement on testnet. It's useful for people to be able to d= evelop apps that use this feature, indeed, it helps build the case for re-a= ctivating it on the main network after the necessary work is done. Otherwis= e there'll inevitably be people who say "why re-activate something= even though we think it's safe when there are no use cases for it"= ;. Letting people develop and deploy interesting prototypes in parallel sol= ves that catch-22.

=C2=A0 ---

Refreshe= r: since the first release Bitcoin has had the ability to replace transacti= ons that sit in the memory pool if the transaction is non-final, the inputs= are the same and the replacement is newer than the replacee. Being non-fin= al means not having reached the nLockTime threshold, and having at least on= e input with a sequence number < UINT_MAX. Around the time of the bugs i= n various opcodes being found, Satoshi disabled the feature because nothing= was using it - it was something he'd planned for the future, it had no= utility in the Bitcoin of 2010.

The purpose of tx replacement is to impleme= nt high frequency trading, according to material Satoshi sent me when I ask= ed him what it was all for (I wanted to know why sequence numbers were a pr= operty of inputs not the transaction).

It's very important to understand that = this does NOT mean high-frequency from the networks perspective. In = normal operation, tx replacement is not actually intended to be used at all= . Sort of like double-spending protection, it's a code path that's = only meant to be triggered when one or the other party is maliciously tryin= g to roll back a negotiated contract. And when a party is trying to do that= , you don't need lots of replacements. A single replacement is enough.<= /div>

To see why this is the case please review t= he micropayment channel protocol here:


This isn't the only use of contra= ctual HFT in Bitcoin, it's a deliberately simplified and stripped down = example (eg, that only uses two parties). The example Satoshi gave me was m= ore abstract and actually had N parties in it - it left me puzzled for a wh= ile and struggling to see practical application. The "billing for a me= tered resource" use case is easier to understand.

Now the obvious problem is that even though= the feature is only intended to be used occasionally or never, nothing in = the existing code stops you using it as fast as possible and exhausting nod= es CPU time and bandwidth.

What's more, solving this is not as eas= y as it looks. Most proposed solutions will not work:

<= /div>
1) Requiring higher fees for each replacement means that a = channel/contract has to be torn down and rebuilt much, much faster than bef= ore because otherwise the amount of money lost to fees quickly becomes the = entire size of the channel (or you can't update it very often). Remembe= r, you'd have to increase the fee for each replacement regardless of wh= ether it's presented to the network or not. As the whole point of the s= etup is to avoid putting lots of transactions on the network, anything that= pushes you back towards doing that undermines the entire utility of the sy= stem.

2) Refusing to update the transaction after= certain thresholds are reached, having cooldown periods, etc also won'= t work because the replacement mechanism is there to protect each counter-p= arty in the HFT contract. Simply converting a DoS on the network to a DoS o= n the participants means one malicious party can break the mechanism that p= rotects all the others by broadcasting the initial set of updates all at on= ce and deliberately tripping the thresholds.

OK, let's take a step back. What is the= purpose of abusing this feature? It's to mount a denial of service att= ack - either against the entire Bitcoin network, or against the other parti= cipants in the contract. But someone, somewhere has to be denied service, o= therwise the attack is pointless.

We can exploit this fact by realising that = typically anti-DoS is a prioritisation problem. It doesn't usually matt= er if you serve some abusive traffic if all legitimate traffic gets served = first because it removes the denial of service from the attack, and usually= there are lots of ways to attack someone with methods that don't work = - real world experience indicates that people don't pointlessly mount a= ttacks over and over again if there's nothing to be gained by doing so.=

So we can do the following - multi-thread v= erification of transactions that are trying to enter the memory pool, and o= rder them such that high priority transactions are verified first, low prio= rity next, and then replacements of transactions sorted by age of last repl= acement. Same thing for relaying - faced with getdatas, service the new tra= nsactions first, replacements with whatever is left over. Drop whatever doe= sn't make it into the nodes available resources.

Handling DoS as a prioritisation prob= lem has a number of advantages, most obviously not introducing new hard cod= ed magic numbers that may or may not stay up to date with changing conditio= ns.

This setup means someone can force CPU/band= width usage to whatever the node operators have configured as their max all= owed across the network for a while, but doing so won't actually disrup= t normal transactions. It'll just result in the replacements getting dr= opped. It slightly increases the risk of a malicious counter-party in an HF= T contract trying to take advantage of the saturation to themselves execute= an attack on the contract, but I doubt it'd be a problem in practice -= =C2=A0you'd need to write your software to be able to perform such an = attack, most of the time it wouldn't work, and if people saturate the n= etwork with low priority easily dropped transactions so that it would work = then nodes/apps could just warn users not to take advantage of the feature = whilst the flood is in progress.

I know that some people will object to such= a design on principle, but I think this is a good balance - the only attac= ks that exist aren't profitable and the worst case outcome in the face = of continual profitless abuse is we switch the feature off and end up no wo= rse off than today.

I haven't touched on the topic of carte= ls of malicious miners or other topics, just DoS. This email is long enough= already and handling malicious miners (if necessary) can be done at the ap= plication protocol level, it doesn't need any changes to the core tx re= placement / locktime mechanism.
--e89a8fb1f7f086e71004da7dda76--