public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* Re: [Bitcoin-development] Anti DoS for tx replacement
@ 2013-04-20  1:48 Jeremy Spilman
  2013-07-18 11:13 ` Peter Todd
  0 siblings, 1 reply; 26+ messages in thread
From: Jeremy Spilman @ 2013-04-20  1:48 UTC (permalink / raw)
  To: bitcoin-development

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

 I’m not sure I followed John’s proposal fully, why would a user sign TX1
committing funds to the MULTISIG they may never get back? I also don’t see
the problem with getting a signed TX2 back from the AP before releasing
TX1... see the sequence below. But more importantly, we only need exactly
one replacement, so for starters we could anti-DoS by allowing only
nSequence of 0 or MAX.

 If this was enabled on test-net, I would be including a link to
transactions that implement the following proposal. At the moment, the best
I can do is unit test and generate the rawtransaction output at each step –
you can find source code and test output here:
https://gist.github.com/jspilman/5424310

 The initial funding transaction and time-locked refund is pretty annoying
to setup, if you want to support the general case of coins from arbitrarily
sized inputs. You will have:
 - 1 or more inputs from the user, 0 or 1 change outputs
 - 0 or more inputs from the AP, 0 or 1 change outputs
 - 1 output to ‘2 PK1 PK2 2 CHECKMULTISIG’

 This precludes using SIGHASH_SINGLE except for the special cases where
inputs are perfectly sized (i.e. they are created in a prior step).

 0. User and AP negotiate how much to escrow, who pays the fees, and how
far in the future nLockTime will be set (how long user’s funds will be tied
if AP doesn’t close the channel)

 1. User creates an unsigned TX1 with 1 or more inputs from user’s
‘listunspent’, change going back to user (if any), and a single output of
‘FundAmount’ with scriptPubKey of ‘2 PK1 OP_0 CHECKMULTISIG’, and sends to
the AP

 2. AP adds to TX1; their inputs (if any), their change (if any), replaces
OP_0 in the scriptPubKey with a PK they control, and signs SIGHASH_ALL, and
returns TX1 to User.

 3. User verifies TX1 is as agreed, and signs it SIGHASH_ALL, but keeps it
to himself. User, having completed TX1, knows its TxID and can now create
TX2-Locked spending TX1 back to themselves. User sets nLockTime to the
agreed point, signs SIGHASH_ALL, and sends TX2-Locked to AP.

 4. AP verifies TX2-Locked and adds their signature, and returns TX2-Locked
to User. User can now broadcast TX1 and TX2-Locked.

 5. At each payment milestone, user creates TX2-Final; TX1 as input, final
nSequence, no lock time, with a single output going back to to the user,
and an amount equal to the remaining balance of the channel. User signs
with SIGHASH_SINGLE and sends to the AP.

 6. AP can add an output to TX2-Final sending their portion of the coins
where ever they want, sign it SIGHASH_ALL, and broadcast it at any point,
closing the channel. AP must broadcast TX2-Final before nLockTime, but has
no guarantee the user hasn’t offered a bribe for miners by spending
TX2-Locked with a large fee, e.g. a pissed off user spends TX2-Locked
entirely to fees just to see if they can convince miners to wait for it.

 The alternative to the TX2-Locked is a 3rd party in the MULTISIG who is
trusted to close the channel at the request of either party, based on the
latest TX2-Final which was sent by the user. In this case there is no
TX2-Locked, only a single boardcast version of TX2-Final, and you do not
need transaction replacement at all.

 Thanks,
--Jeremy

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

^ permalink raw reply	[flat|nested] 26+ messages in thread
* Re: [Bitcoin-development] Anti DoS for tx replacement
@ 2013-04-20 20:51 Jeremy Spilman
  2013-04-22 11:07 ` Mike Hearn
  2013-04-23 12:40 ` John Dillon
  0 siblings, 2 replies; 26+ messages in thread
From: Jeremy Spilman @ 2013-04-20 20:51 UTC (permalink / raw)
  To: bitcoin-development

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

I was discussing this with petertodd a couple days ago and we were thinking
the sequence I sent yesterday was usable today.  I tried getting it to work
on test-net but the final transaction closing the channel was not being
accepted into the mempool beacause "ERROR: CTxMemPool::accept() : inputs
already spent"

But I was talking with sipa and gmaxwell on IRC about it, and sipa reminded
me; Test-Net implements IsStandard() to allow the non-final "refund" TX
into the mempool, but then doesn't allow it to be replaced, Main-Net
implements IsStandard() to *reject* non-final transactions in the first
place.

Therefore, this actually will work on Main-Net today, since the refund TX
won't even be allowed into the mempool until it's final, the AP is free to
sign and broadcast its final TX without any replacement. Of course, if the
AP waits too long, the user can get their Refund into the mempool and the
AP's [higher seq] version will be locked out.

This may be a case where Test-Net is in a "bad" state, by allowing
non-final TXs into the pool, but not allowing replacement, you get an
intermediate state which neither matches Main-Net behavior, nor implements
behavior which would ever be deployed to Main-Net as-is.

The current Main-Net behavior is actually very well suited for this
application. Any application that can be reduced to two instances of a Tx,
namely one non-final, and one final which is updated internally between the
parties, works very well under the current Main-Net rules.

If you set the nLockTime of the refund to be several days after the
scheduled closing time of the channel, it would be quite challenging to get
the Refund TX into the blockchain *despite* a final broadcast TX from the
AP. Since the vast majority of Main-Net won't even accept it, the attacker
would have to distribute the TX to any miner who could include the AP's
transaction in a block between now and when the refund becomes final, and
convince them all to not include the perfectly valid, fees paid, final,
nSeq=MAX, nLockTime=0 transaction from the AP. Demonstrating that level of
coordination would act substantially against the best interests of the
miners, to say the least.

This proposal still suffers from any malleability weakness, where the
user's refund could be invalidated by a miner changing the TxID of TX1.

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

^ permalink raw reply	[flat|nested] 26+ messages in thread
* [Bitcoin-development] Anti DoS for tx replacement
@ 2013-04-16 17:39 Mike Hearn
  2013-04-16 18:43 ` Peter Todd
       [not found] ` <CAD0SH_WOG8jQvzsNzwud3fYjaxqTJo0CS7yP6XZeKvap_yqtqg@mail.gmail.com>
  0 siblings, 2 replies; 26+ messages in thread
From: Mike Hearn @ 2013-04-16 17:39 UTC (permalink / raw)
  To: Bitcoin Dev

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

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.

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

^ permalink raw reply	[flat|nested] 26+ messages in thread
end of thread, other threads:[~2013-07-18 16:10 UTC | newest]

Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-04-20  1:48 [Bitcoin-development] Anti DoS for tx replacement 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
  -- strict thread matches above, loose matches on Subject: below --
2013-04-20 20:51 Jeremy Spilman
2013-04-22 11:07 ` Mike Hearn
2013-04-23 12:40 ` John Dillon
2013-04-16 17:39 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
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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox