public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Mike Hearn <mike@plan99.net>
To: Peter Todd <pete@petertodd.org>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Anti DoS for tx replacement
Date: Thu, 18 Apr 2013 11:28:48 +0200	[thread overview]
Message-ID: <CANEZrP0AYaWnVhrAbMXP0BGhb=CZMg_-PYVzwKbcCoRKC9V2rw@mail.gmail.com> (raw)
In-Reply-To: <20130418090444.GA30995@savin>

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

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

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

  parent reply	other threads:[~2013-04-18  9:28 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-04-16 17:39 [Bitcoin-development] Anti DoS for tx replacement Mike Hearn
2013-04-16 18:43 ` Peter Todd
2013-04-17  9:48   ` Mike Hearn
2013-04-17 19:44     ` Alan Reiner
2013-04-18  6:07     ` John Dillon
2013-04-18  8:14       ` Peter Todd
2013-04-19  4:38         ` John Dillon
2013-04-19  4:55           ` Jeff Garzik
2013-04-18  8:32       ` Mike Hearn
2013-04-18  9:04         ` Peter Todd
2013-04-18  9:28           ` Peter Todd
2013-04-18  9:32             ` Mike Hearn
2013-04-18  9:28           ` Mike Hearn [this message]
2013-04-18  9:34             ` Mike Hearn
2013-04-18 10:08             ` Peter Todd
2013-04-18 10:19               ` Mike Hearn
2013-04-18 13:37                 ` Gavin Andresen
     [not found] ` <CAD0SH_WOG8jQvzsNzwud3fYjaxqTJo0CS7yP6XZeKvap_yqtqg@mail.gmail.com>
2013-04-17  9:19   ` Mike Hearn
2013-04-20  1:48 Jeremy Spilman
2013-07-18 11:13 ` Peter Todd
2013-07-18 12:53   ` Jeff Garzik
2013-07-18 13:43     ` Peter Todd
2013-07-18 16:09   ` Peter Todd
2013-04-20 20:51 Jeremy Spilman
2013-04-22 11:07 ` Mike Hearn
2013-04-23 12:40 ` John Dillon

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CANEZrP0AYaWnVhrAbMXP0BGhb=CZMg_-PYVzwKbcCoRKC9V2rw@mail.gmail.com' \
    --to=mike@plan99.net \
    --cc=bitcoin-development@lists.sourceforge.net \
    --cc=pete@petertodd.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox