path: root/a5/a2269c9d464d8524a5c07481f34d3142c1bfcd

Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <mh.in.england@gmail.com>) id 1USl9D-0002HY-GT
	for bitcoin-development@lists.sourceforge.net;
	Thu, 18 Apr 2013 09:28:55 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.219.54 as permitted sender)
	client-ip=209.85.219.54; envelope-from=mh.in.england@gmail.com;
	helo=mail-oa0-f54.google.com; 
Received: from mail-oa0-f54.google.com ([209.85.219.54])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1USl9C-0003v8-Ch
	for bitcoin-development@lists.sourceforge.net;
	Thu, 18 Apr 2013 09:28:55 +0000
Received: by mail-oa0-f54.google.com with SMTP id l20so2506747oag.41
	for <bitcoin-development@lists.sourceforge.net>;
	Thu, 18 Apr 2013 02:28:49 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.60.56.36 with SMTP id x4mr4925849oep.25.1366277329007; Thu,
	18 Apr 2013 02:28:49 -0700 (PDT)
Sender: mh.in.england@gmail.com
Received: by 10.76.167.169 with HTTP; Thu, 18 Apr 2013 02:28:48 -0700 (PDT)
In-Reply-To: <20130418090444.GA30995@savin>
References: <CANEZrP1yKeQMayFHsEUWtA3=q+v5rPAutjzEFVVHopPGNZ4jGQ@mail.gmail.com>
	<453bfc69-b2ab-4992-9807-55270fbda0db@email.android.com>
	<CANEZrP0z6W0ZDsytQ7Rcqb5L6rswn1wv8cbR7c383Dmpzu+gyg@mail.gmail.com>
	<CAPaL=UVJd3mdd0bs6Oo9vFHnv_6RbFowjmp0tD-ZbOzZxJEJ3g@mail.gmail.com>
	<CANEZrP3ocAJNoQ3xJqRTL8Gz3_T8xsCPPAvSfEOYpPo76wgbig@mail.gmail.com>
	<20130418090444.GA30995@savin>
Date: Thu, 18 Apr 2013 11:28:48 +0200
X-Google-Sender-Auth: -pysRLkyKvIMSsBZUPvozLAeBK8
Message-ID: <CANEZrP0AYaWnVhrAbMXP0BGhb=CZMg_-PYVzwKbcCoRKC9V2rw@mail.gmail.com>
From: Mike Hearn <mike@plan99.net>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a11c249f6dc3cd504da9f3a86
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
	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: 1USl9C-0003v8-Ch
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Anti DoS for tx replacement
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Thu, 18 Apr 2013 09:28:55 -0000

--001a11c249f6dc3cd504da9f3a86
Content-Type: text/plain; charset=UTF-8

> An attack still shuts down useful tx replacement though. For instance in
> the adjusting payments example an attacker sets up a legit adjusting
> payment channel, does a bunch of adjustments, and then launches their
> attack. They broadcast enough adjustments that their adjustment session
> looks like part of an attack, and then don't have to pay for the full
> adjusted amount.
>

It's possible, but let's do some back of the envelope calculations to look
at how quickly such an attack can exhaust itself.

Consider a contract that has a time window of 12 hours and is adjusted once
per second for that duration. That's 43,200 adjustments. It sounds sort of
ballpark-ish for micropayments. If you end up losing 1 seconds worth of
service, well, probably that's no big deal. As the contract reaches its
nLockTime, the attacker starts broadcasting all of the adjustments in
sequence in the hope that an earlier version will be being processed as the
lock time expires and a block is solved, so the latest version (the one
that gives him the least money) ends up not being included in the chain.

The input is a multi-signature transaction, so to process every single
adjustment created would take 86,400 signature verifications. With the
sipaspeed patches it seems ECDSA can be processed on modern cores at
something like 20,000 signatures per second. So it'd take a bit over 4
seconds to process all of them (cpu time).

That gives the attacker a less than 4 second window in which to try and
roll back the contract to an earlier time before he reaches the last
version and things are as they should be. Given that a block is solved on
average every 10 minutes, you'd have to get very lucky indeed to succeed
with such an attack. It's probably easier to try and find a corrupt miner
who is willing to bend the rules for you.

Let's include bandwidth. Say the contract (multi-sig input + the outputs)
is about 700 bytes. 43,200 transactions is then about 29 megabytes of data.
On a fairly normal 10mbit connection that would take about 23 seconds to
transfer. Of course the real number is a bit higher because of latency
introduced by the inv/tx round-tripping. So the time window of the attack
is dominated by bandwidth but it's still quite small compared to the block
solving window.

It's *easily* DoSable, not trivially.
>

What I meant is - find some open DNS resolvers, start firing packets at
testnet nodes, done. You don't have to do protocol level attacks to just
render nodes useless.


> You would need some way of determining which input was responsible for a
> replacement though - I can't think of an obvious way to within the
> current transaction format, but I haven't thought hard about it yet.
>

Ah, I think it actually is possible and this is an intriguing idea. Each
input has its own sequence number. Look at the definition of IsNewerThan()
- to make a newer version you increment your inputs sequence number in a
particular manner whilst leaving the others alone.

Having a single multi-sig input means you can't do that because both
parties co-operate to update the single input, but schemes that use
multiple inputs do seem posible.


> How exactly do you envision replacement working with non-final ==
> non-standard anyway?
>

As I said at the bottom of my second mail, it means making non-final
transactions relayable again, but only to nodes that advertise a high
enough version number. Those nodes are expected to do something intelligent
with them, like just not put them in the wallet (unless the user has opted
in and ticked the "i know what i'm doing" box, perhaps).


> If he's reasonable about the scope, IE just a initial implementation for
> further evaluation, I figure it's about two days work.


Well, it depends on your use case - you need to cast the (fixed) algorithm
into a network protocol, manage the interactions between the parties,
monitor the network for malicious broadcasts so you can replace them, fix
the code so the wallets don't accept non-final transactions except when
taking part in your contract, etc. If you do it all with Bitcoin-Qt it's
easier but then your app can't easily run in places that can't afford a few
hundred megs of ram (like wifi hotspots). The devil is in the details.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><div class=3D"gmail_quote">=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
An attack still shuts down useful tx replacement though. For instance in<br=
>
the adjusting payments example an attacker sets up a legit adjusting<br>
payment channel, does a bunch of adjustments, and then launches their<br>
attack. They broadcast enough adjustments that their adjustment session<br>
looks like part of an attack, and then don&#39;t have to pay for the full<b=
r>
adjusted amount.<br></blockquote><div><br></div><div style>It&#39;s possibl=
e, but let&#39;s do some back of the envelope calculations to look at how q=
uickly such an attack can exhaust itself.</div><div style><br></div><div st=
yle>
Consider a contract that has a time window of 12 hours and is adjusted once=
 per second for that duration. That&#39;s 43,200 adjustments. It sounds sor=
t of ballpark-ish for micropayments. If you end up losing 1 seconds worth o=
f service, well, probably that&#39;s no big deal. As the contract reaches i=
ts nLockTime, the attacker starts broadcasting all of the adjustments in se=
quence in the hope that an earlier version will be being processed as the l=
ock time expires and a block is solved, so the latest version (the one that=
 gives him the least money) ends up not being included in the chain.</div>
<div style><br></div><div style>The input is a multi-signature transaction,=
 so to process every single adjustment created would take 86,400 signature =
verifications. With the sipaspeed patches it seems ECDSA can be processed o=
n modern cores at something like 20,000 signatures per second. So it&#39;d =
take a bit over 4 seconds to process all of them (cpu time).</div>
<div style><br></div><div style>That gives the attacker a less than 4 secon=
d window in which to try and roll back the contract to an earlier time befo=
re he reaches the last version and things are as they should be. Given that=
 a block is solved on average every 10 minutes, you&#39;d have to get very =
lucky indeed to succeed with such an attack. It&#39;s probably easier to tr=
y and find a corrupt miner who is willing to bend the rules for you.</div>
<div style><br></div><div style>Let&#39;s include bandwidth. Say the contra=
ct (multi-sig input + the outputs) is about 700 bytes. 43,200 transactions =
is then about 29 megabytes of data. On a fairly normal 10mbit connection th=
at would take about 23 seconds to transfer. Of course the real number is a =
bit higher because of latency introduced by the inv/tx round-tripping. So t=
he time window of the attack is dominated by bandwidth but it&#39;s still q=
uite small compared to the block solving window.</div>
<div style><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 =
0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"im"><span=
 style=3D"color:rgb(34,34,34)">It&#39;s *easily* DoSable, not trivially.</s=
pan></div>
</blockquote><div style><br></div><div style>What I meant is - find some op=
en DNS resolvers, start firing packets at testnet nodes, done. You don&#39;=
t have to do protocol level attacks to just render nodes useless.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex">
<div class=3D"im"><span style=3D"color:rgb(34,34,34)">You would need some w=
ay of determining which input was responsible for a</span><br></div>
replacement though - I can&#39;t think of an obvious way to within the<br>
current transaction format, but I haven&#39;t thought hard about it yet.<br=
></blockquote><div><br></div><div style>Ah, I think it actually is possible=
 and this is an intriguing idea. Each input has its own sequence number. Lo=
ok at the definition of IsNewerThan() - to make a newer version you increme=
nt your inputs sequence number in a particular manner whilst leaving the ot=
hers alone.</div>
<div style><br></div><div style>Having a single multi-sig input means you c=
an&#39;t do that because both parties co-operate to update the single input=
, but schemes that use multiple inputs do seem posible.</div><div>=C2=A0</d=
iv>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">How exactly do you envision replacement work=
ing with non-final =3D=3D<br>
non-standard anyway?<br></blockquote><div><br></div><div style>As I said at=
 the bottom of my second mail, it means making non-final transactions relay=
able again, but only to nodes that advertise a high enough version number. =
Those nodes are expected to do something intelligent with them, like just n=
ot put them in the wallet (unless the user has opted in and ticked the &quo=
t;i know what i&#39;m doing&quot; box, perhaps).</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex">
<div class=3D"im"><span style=3D"color:rgb(34,34,34)">If he&#39;s reasonabl=
e about the scope, IE just a initial implementation for</span><br></div>
further evaluation, I figure it&#39;s about two days work.</blockquote><div=
><br></div><div style>Well, it depends on your use case - you need to cast =
the (fixed) algorithm into a network protocol, manage the interactions betw=
een the parties, monitor the network for malicious broadcasts so you can re=
place them, fix the code so the wallets don&#39;t accept non-final transact=
ions except when taking part in your contract, etc. If you do it all with B=
itcoin-Qt it&#39;s easier but then your app can&#39;t easily run in places =
that can&#39;t afford a few hundred megs of ram (like wifi hotspots). The d=
evil is in the details.</div>
</div></div></div>

--001a11c249f6dc3cd504da9f3a86--