Re: [Bitcoin-development] Anti DoS for tx replacement

[Mike Hearn <mike@plan99.net>]

[-- 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 --]