[Bitcoin-development] Anti DoS for tx replacement

[Bitcoin-development] Anti DoS for tx replacement

[Mike Hearn]

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

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

[Peter Todd]

Post tge malicious miners and other bits so we can evaluate the system as a whole. 

Mike Hearn <mike@plan99.net> wrote:

>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.
>
>
>------------------------------------------------------------------------
>
>------------------------------------------------------------------------------
>Precog is a next-generation analytics platform capable of advanced
>analytics on semi-structured data. The platform includes APIs for
>building
>apps and a phenomenal toolset for data science. Developers can use
>our toolset for easy data analysis & visualization. Get a free account!
>http://www2.precog.com/precogplatform/slashdotnewsletter
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Bitcoin-development mailing list
>Bitcoin-development@lists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/bitcoin-development

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

[Mike Hearn]

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

When this system was first being discussed, Gavin was concerned that miner
incentives were to ignore replacements because it meant extra work and the
replacement might have equal or lower fees than before (or indeed, no
fees). He proposed two solutions: one is to progressively raise the fee on
each replacement. The other is to specify lock time in terms of blocks and
then step it backwards once for each replacement, thus ensuring that by
replacing the transaction you get to claim any attached fee earlier.

It should be apparent that both solutions can be implemented by whichever
application is running the contract - the core Bitcoin network and software
is agnostic either way.

Now, Gavin and I disagreed on whether this would actually be necessary. As
I already pointed out, both solutions seriously reduce the utility of HFT
because they limit how often you can update the contract. Instead of an
online game billing you per second, maybe it can only do it per minute or
per 10 minutes with the lock time solution because otherwise you run out of
blocks, and with ever-increasing fees perhaps the contract becomes too
expensive to justify after a while.

So it'd be nice if this ended up not being necessary. Experience indicates
that rational miners typically don't pursue a short-termist
profit-at-any-cost agenda - free transactions have always been included in
blocks, miners include transactions even though you could avoid a lot of
complexity by just not including any at all, etc. Some miners like BTC
Guild have actually sacrificed significant amounts of money for the good of
the system. You can see this in terms of rational self interest - miners
earn Bitcoins thus it's in their interest for Bitcoins to be as useful as
possible, as that is what gives them value. Or you can see it in terms of
ideologically-driven altruism. Or both.

If I were to implement an application that used tx replacement, I would
probably start with replacements that don't change the fees and don't count
down the lock time field. We can then observe whether miners bother
changing their software to behave differently, or whether the inherent
utility of the application is enough to convince them to play by the
default rules. Ideally at least one application made possible by this
feature is a "killer app" - something so useful / unique / compelling that
people want to obtain Bitcoin just to use it. If someone can find such an
app, then rational miners should want tx replacement to work as reliably as
possible because it boosts the value of their earnings.

There are some other misc details - reactivation requires that we bump the
protocol version and start relaying non-final transactions to new nodes
again. Those nodes should relay replacements but not let them enter wallets
unless/until the wallet software itself can handle them better, for
instance, by communicating via APIs anticipated confirmation times. This is
something for individual wallet APIs to handle on their own, and just
ignoring non-final transactions is a perfectly workable approach for
Bitcoin-Qt.

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

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

[Alan Reiner]

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

One of the big topics of recent past on IRC is "malleability" of
transactions:  to what extent can someone /else /change your signed
transaction without affecting its validity?  In the past I used to
consider this just annoying, but not so malicious.  But in terms of HFT,
it sounds like malicious behavior is possible:

To recap the procedure:

(1)  Alice creates a transaction, Tx1, for 10 BTC to a 2-of-2-{Alice,
Bob} address.  It has a locktime of 30 days in the future.
(2)  Before signing the transaction, she gets Bob to sign a transaction,
Tx2, from 2-of-2-{Alice, Bob} back to herself.   That transaction
references the Tx1 by hash.
(3)  Any time in the next 30 days, Alice can sign an alternate Tx2
transactions reducing the amount returned to self and increasing amount
to Bob, as a method of paying Bob more.  Bob doesn't need to broadcast
anything except for the last one, 29 days later.

It was originally conceived that Bob couldn't do anything malicious,
because Alice gets Bob to sign Tx2-spending-Tx1 before she gives him
Tx1.  The problem is that Bob can follow her process, then
broadcast/mine Tx1' (Tx1-prime), which has a different number of 0x00
pad bytes in the signatures, or "flips the sign" of one of the s-values
in the signature, thus changing the hash of Tx1.

By doing this, Bob has now created a transaction, Tx1', that Tx2 no
longer returns to Alice.  It's not flat-out theft, because Tx1 still
sends to a 2-of-2 address requiring both of their signatures.  But Bob
didn't risk anything to do this, besides his reputation/trust.  He now
has Alice's money locked and can hold it for ransom, since she needs his
signature to do move it.  He could offer his signature for half of it.

Of course, these types of HFT contracts will usually be between parties
that have some mutual respect/history.  Thus, they are not usually
zero-trust.   But we should find a way to try to close that, if
possible.  For instance, if the malleability was reduced to one bit, you
could just have Bob sign two different transactions before Alice
broadcasts Tx1.  The two tx would be from either variant.  But I know
there's too many bits of malleability in the transaction serialization
for that to work.  Is there any way to avoid this?

-Alan



On 04/17/2013 05:48 AM, Mike Hearn wrote:
> When this system was first being discussed, Gavin was concerned that
> miner incentives were to ignore replacements because it meant extra
> work and the replacement might have equal or lower fees than before
> (or indeed, no fees). He proposed two solutions: one is to
> progressively raise the fee on each replacement. The other is to
> specify lock time in terms of blocks and then step it backwards once
> for each replacement, thus ensuring that by replacing the transaction
> you get to claim any attached fee earlier.
>
> It should be apparent that both solutions can be implemented by
> whichever application is running the contract - the core Bitcoin
> network and software is agnostic either way.
>
> Now, Gavin and I disagreed on whether this would actually be
> necessary. As I already pointed out, both solutions seriously reduce
> the utility of HFT because they limit how often you can update the
> contract. Instead of an online game billing you per second, maybe it
> can only do it per minute or per 10 minutes with the lock time
> solution because otherwise you run out of blocks, and with
> ever-increasing fees perhaps the contract becomes too expensive to
> justify after a while.
>
> So it'd be nice if this ended up not being necessary. Experience
> indicates that rational miners typically don't pursue a short-termist
> profit-at-any-cost agenda - free transactions have always been
> included in blocks, miners include transactions even though you could
> avoid a lot of complexity by just not including any at all, etc. Some
> miners like BTC Guild have actually sacrificed significant amounts of
> money for the good of the system. You can see this in terms of
> rational self interest - miners earn Bitcoins thus it's in their
> interest for Bitcoins to be as useful as possible, as that is what
> gives them value. Or you can see it in terms of ideologically-driven
> altruism. Or both.
>
> If I were to implement an application that used tx replacement, I
> would probably start with replacements that don't change the fees and
> don't count down the lock time field. We can then observe whether
> miners bother changing their software to behave differently, or
> whether the inherent utility of the application is enough to convince
> them to play by the default rules. Ideally at least one application
> made possible by this feature is a "killer app" - something so useful
> / unique / compelling that people want to obtain Bitcoin just to use
> it. If someone can find such an app, then rational miners should want
> tx replacement to work as reliably as possible because it boosts the
> value of their earnings.
>
> There are some other misc details - reactivation requires that we bump
> the protocol version and start relaying non-final transactions to new
> nodes again. Those nodes should relay replacements but not let them
> enter wallets unless/until the wallet software itself can handle them
> better, for instance, by communicating via APIs anticipated
> confirmation times. This is something for individual wallet APIs to
> handle on their own, and just ignoring non-final transactions is a
> perfectly workable approach for Bitcoin-Qt.
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


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

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

[John Dillon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, Apr 17, 2013 at 9:48 AM, Mike Hearn <mike@plan99.net> wrote:
> So it'd be nice if this ended up not being necessary. Experience indicates that rational miners typically don't pursue a short-termist profit-at-any-cost agenda - free transactions have always been included in blocks, miners include transactions even though you could avoid a lot of complexity by just not including any at all, etc. Some miners like BTC Guild have actually sacrificed significant amounts of money for the good of the system. You can see this in terms of rational self interest - miners earn Bitcoins thus it's in their interest for Bitcoins to be as useful as possible, as that is what gives them value. Or you can see it in terms of ideologically-driven altruism. Or both.

Please don't say Gavin agrees with you. This reminds me of discussing
security in the early days of the internet when the general assumption
that everyone played nice was still correct.

We're seeing huge, expensive, DoS attacks against mining pools,
exchanges, information sites, stores etc. Bitcoin has enemies. Peter
Todd is 100% correct, tx replacement is another form of zero
confirmation transaction and all that has to happen is some subset of
mining power start doing replace by tx fee for it to have no security
while with your proposed implementation opening up a DoS attack
vector.

You also see the DoS attack vector as unimportant and suggest to
handle it as a prioritization problem. "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." <- of course there
is something to be gained, shutting down a service dependent on tx
replacement, as seen by all the DoS attacks we are seeing. If I were
deciding if my service should use tx replacement and I understood that
it could be trivially shut down, I sure wouldn't be happy I could
"just warn users not to take advantage of the feature whilst the flood
is in progress"

Gavin do you actually agree with Mike on this stuff like he implies?
Because if you do, I think people should know. Myself I wouldn't want
to be contributing to your salary as a foundation member if you don't
take Bitcoin security seriously.


The rapidly-adjusted payments stuff on the Contracts page of the wiki
is broken in multiple ways:

1. (known) Requires DoS vulnerable infrastructure.
2. (known) TX mutability
3. (unknown?) Just doesn't work. Step 5 is to check that T2 is signed
correctly by the access point, and if so, sign T1 and T2. But the
signature of T2 includes the txid of T1 and that isn't known until T1
is fully signed.

That #3 has not been noticed before shows that for all this hot air
no-one has ever bothered making an implementation of the idea. So
Mike, why are you happy to make testnet vulnerable to an unusually
easy DoS attack for an idea you haven't even tried on your own private
testnet with replacement enabled?


Anyway, with Peter Todd's much saner tx-replacement-by-fee the
following can be done:

1. Create a new public key PK1

2. Request a public key PK2 from the access point.

2. Create TX1 with two inputs and two outputs. Both parties sign it
and broadcast it.

access point input -> 2 PK1 PK2 checkmultisig, value = input #1 - fee
you input -> 2 PK1 PK2 checkmultisig, value == input #2 - fee

3. Create TX2.

TX1 #1 -> pay to access point PK2
TX1 #2 -> pay to yourself PK1 (change)

Set TX2 nLockTime to some time in the future.

4. Set the initial value's of TX2 out #1 and out #2 to the value the
access point and you committed in TX1. Both parties sign with
SIGHASH_SINGLE. (which means both parties are signing for both inputs)

5. Update TX2 as required and sign both inputs. The access point
doesn't need to sign TX2 or give the updated copy of TX2 to the other
party. The TX is not broadcast when updated (like the earlier contract
proposal) although doing so harms no-one.

When the session ends with both parties online, do the following:

1. You sign a version of TX2 with the final output values and nLockTime=0

2. If the final output values are acceptable to the access point, they
sign the other half of the 2-of-2 inputs and broadcast. (with whatever
fees required)

If the buyer quits the session abruptly:

1. Access point signs the last (most funds) version of TX2 given to
them, waits until the nLockTime expires, and broadcasts. This also
gets their TX1 input back.

If the access point quits abruptly they can do the above when they go
back online. The buyer has the first, signed, version of TX2 and at
worst can broadcast it eventually to get their deposit back.

Attacks:

After TX1 is signed and broadcast both parties are in on the contract
together, so the funds can't move without the consent of the other.
Both parties can block the movement of the other's deposit, but they
lose their deposit too. With tx mutability there is a small window of
time for a technical mistake, but that should be very, very rare.

You can broadcast an earlier version of the transaction where you pay
less than you were supposed too. However if you do this, the access
point can broadcast a new version of the transaction, splicing
together your signature on the correct output value, with your
signature on an earlier version of the access point's output, thus
paying miners a higher fee than the transaction you broadcast.
Rational miners will chose the latter version rather than your one.
This bidding process can continue until you are out the full amount
you were supposed to pay, with the whole payment going to fees, so why
bother? With nLockTime you don't have a better chance of mining the
transaction than any other miner.

I apologize if the above has already been discussed. I only looked at
the wiki and source code and don't waste too much time reading the
endless bitcointalk forums. The wiki should be updated with these
ideas as they are developed by people and vetted.


Strict replacement by fee should be written so it can be tested
properly and people in the Bitcoin ecosystem use proper security
practices with regard to unconfirmed transactions. I'm willing to
pledge $500USD to anyone who implements it. That is write the core
functionality that does replacement by fee, and a simple 'undo' RPC
command. I would do it myself but my programming is rusty.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBAgAGBQJRb4vZAAoJEEWCsU4mNhiPRNoH/jGcGw2NBUcIh0/HT70nnwU+
deaXcdYp9RhDlSf0VGvPwwEAnjWBFc+pYVC+vtL4XEvWR+5PC7FcOrRrv/+sTDPs
YwPkCIwvXJizFe5pAhXOde4EdibXU0WXTLonMNUeZkwhxUfrczURm2tgmJlNE7nA
3PBun4c4r7EcdRHuh9SiK0C4RgB5w63t/qyFVUfqwhyKYiS55K/2t2mVLLxcPWkY
8nxlYlese5eZZJBTfiePtPOqTd43DHOkN+4Iu5XXQIH7v2QHf50DMqgI3iVLVe08
c2i9GutwX+2MevSMe/S57952BCjBq4zF0nBpaAfIFCVHDDZ6bDbgA7fUjDtLVds=
=1Tc0
-----END PGP SIGNATURE-----

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

[Peter Todd]

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

On Thu, Apr 18, 2013 at 06:07:23AM +0000, John Dillon wrote:
> Gavin do you actually agree with Mike on this stuff like he implies?
> Because if you do, I think people should know. Myself I wouldn't want
> to be contributing to your salary as a foundation member if you don't
> take Bitcoin security seriously.

FWIW Gavin has spent quite a bit of time and effort ensuring that
Bitcoin is resistent to DoS attacks, as well as spearheading a move
towards better testing. The latter in particular is helpful against
chain-forking bugs, so better testing is very much a security issue. He
also spearheaded P2SH, and the current efforts to get a payment protocol
implemented. I'm less convinced about his stance against attackers that
pose a threat to the system as a whole, but it's not fair to accuse him
of not taking security seriously.

> Strict replacement by fee should be written so it can be tested
> properly and people in the Bitcoin ecosystem use proper security
> practices with regard to unconfirmed transactions. I'm willing to
> pledge $500USD to anyone who implements it. That is write the core
> functionality that does replacement by fee, and a simple 'undo' RPC
> command. I would do it myself but my programming is rusty.

You should clarify if you want this patch to compute fees recursively or
not, IE, should the patch include fees paid by child transactions in how
it computes the total fee the transaction pays. Doing this is
non-trivial, although Luke-Jr has written a patch to do this without
replacement: https://github.com/bitcoin/bitcoin/pull/1647

Also, clarify if you want unit-tests and similar things included in the
implementation.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[John Dillon]

I understand that Gavin has spent effort on security efforts against
small-scale attackers. It's the fact that he is so dismissive of the
threat that large attackers play that is what bothers me. But if I am
being divisive I understand.

I posted a clarification of what the reward is for exactly on the
forums: https://bitcointalk.org/index.php?topic=179612.msg1881800#msg1881800

On Thu, Apr 18, 2013 at 8:14 AM, Peter Todd <pete@petertodd.org> wrote:
> On Thu, Apr 18, 2013 at 06:07:23AM +0000, John Dillon wrote:
>> Gavin do you actually agree with Mike on this stuff like he implies?
>> Because if you do, I think people should know. Myself I wouldn't want
>> to be contributing to your salary as a foundation member if you don't
>> take Bitcoin security seriously.
>
> FWIW Gavin has spent quite a bit of time and effort ensuring that
> Bitcoin is resistent to DoS attacks, as well as spearheading a move
> towards better testing. The latter in particular is helpful against
> chain-forking bugs, so better testing is very much a security issue. He
> also spearheaded P2SH, and the current efforts to get a payment protocol
> implemented. I'm less convinced about his stance against attackers that
> pose a threat to the system as a whole, but it's not fair to accuse him
> of not taking security seriously.
>
>> Strict replacement by fee should be written so it can be tested
>> properly and people in the Bitcoin ecosystem use proper security
>> practices with regard to unconfirmed transactions. I'm willing to
>> pledge $500USD to anyone who implements it. That is write the core
>> functionality that does replacement by fee, and a simple 'undo' RPC
>> command. I would do it myself but my programming is rusty.
>
> You should clarify if you want this patch to compute fees recursively or
> not, IE, should the patch include fees paid by child transactions in how
> it computes the total fee the transaction pays. Doing this is
> non-trivial, although Luke-Jr has written a patch to do this without
> replacement: https://github.com/bitcoin/bitcoin/pull/1647
>
> Also, clarify if you want unit-tests and similar things included in the
> implementation.
>
> --
> 'peter'[:-1]@petertodd.org

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

[Jeff Garzik]

On Fri, Apr 19, 2013 at 12:38 AM, John Dillon
<john.dillon892@googlemail.com> wrote:
> I understand that Gavin has spent effort on security efforts against
> small-scale attackers. It's the fact that he is so dismissive of the
> threat that large attackers play that is what bothers me. But if I am
> being divisive I understand.

I cannot speak for Gavin, but speaking more generally, large attackers
tend to belong in a thought-class all their own.

Example 1:  if some super-ASIC miner arises with 90% of hash power,
and he starts behaving in a way contrary to the useful functioning of
bitcoin, the community might decide to change the PoW algorithm at
block height N.

Example 2:  If someone large DDoS's the entire P2P network, which is
possible, manual intervention would be required to straighten out the
mess.

In each case, it's more about the community's mutual defense actions
than any prepared defense.

Speaking even more generally, bitcoin may be a billion-dollar
invention, but that doesn't mean it has any funding for network
defense!  Unless cost structures and user attitudes change,
development and deployment of major defense strategies seems unlikely.
 Which implies the community will simply wait for a [attack |
explosion | crisis], and then hope we can unwind/repair the damage
afterwards.

-- 
Jeff Garzik
exMULTI, Inc.
jgarzik@exmulti.com

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

[Mike Hearn]

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

When did I say DoS was unimportant? I just wrote a giant email explaining
how it can be resolved.

I think it's worth pointing out that Bitcoin was launched with no DoS
protection at all, and it's still here. There are still obvious DoS bugs
being fixed with every release. So yes, it's important to robustify the
code, but not to the extent of not having any features. If Satoshi had
taken that perspective Bitcoin might not exist at all. We can have our cake
and eat it.

RE: shutting down services dependent on replacement. No, good users of
replacement would still end up taking priority over the constantly churning
DoS replacements. The most you can shut down is one contract. Obviously, if
there's no form of tx replacement at all then the "tried and doesn't work"
state is the same as "never tried", which doesn't seem like a win.

The testnet is trivially DoSable today by anyone who cares to do so, there
are hardly any nodes and most people get coins from the faucet. Look at how
quickly people got upset when somebody drained it. As Jeff has pointed out,
there could theoretically be a "nextnet" but the overhead of setting one up
doesn't seem worth it. If somebody wanted to troll developers they could
easily DoS testnet and nextnet simultaneously with bandwidth to spare.


> That #3 has not been noticed before shows that for all this hot air
> no-one has ever bothered making an implementation of the idea.
>

Yes, I noticed it a few days ago when making some notes, but figured I
would indeed make an prototype implementation and then just put all the
details and latest protocols on the wiki at once. As nobody indeed noticed
the bug for years apparently nobody else is working on this so it didn't
seem urgent to update.

Your proposed alternative doesn't seem any different DoS wise. Someone can
still broadcast a long series of incrementally different transactions and
have miners replace them. So you still need prioritisation of work. It's
useful anyway for other reasons. And as you point out yourself, it's still
susceptible to the problem that you end up running out of money because
it's all been spent on fees.

BTW $500 is rather low for the amount of work required. If you added a zero
onto that there might be more takers.

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

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

[Peter Todd]

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

On Thu, Apr 18, 2013 at 10:32:24AM +0200, Mike Hearn wrote:
> RE: shutting down services dependent on replacement. No, good users of
> replacement would still end up taking priority over the constantly churning
> DoS replacements. The most you can shut down is one contract. Obviously, if
> there's no form of tx replacement at all then the "tried and doesn't work"
> state is the same as "never tried", which doesn't seem like a win.

Yeah, an attack is a bit more subtle than perhaps John Dillon realizes.
Assuming that nodes prioritize the transactions with the fewest total
replacements first it becomes a multiplier on the standard attack of
just broadcasting transactions. So for non-replacement users it's
probably not that bad.

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.

What's worse, the attack itself can be just a large number of these
micropayment sessions, IE, no bogus sessions at all.

> The testnet is trivially DoSable today by anyone who cares to do so, there
> are hardly any nodes and most people get coins from the faucet. Look at how

It's *easily* DoSable, not trivially. Testnet has all the same
fee/priority rules that Bitcoin has, so any attack still costs some
amount of coins. For instance I did the math once on what it would cost
to flood testnet with 1MB blocks, and it came out to IIRC $100/month or
so in terms of lost mining revenue. Small, but still not trivial.

non-final nLockTime floods and timewarp assisted can be easily done mind
you, but the former is easy to fix and the latter is relatively tricky
to pull off and still requires some mining expenditure.

> Your proposed alternative doesn't seem any different DoS wise. Someone can
> still broadcast a long series of incrementally different transactions and
> have miners replace them. So you still need prioritisation of work. It's
> useful anyway for other reasons. And as you point out yourself, it's still
> susceptible to the problem that you end up running out of money because
> it's all been spent on fees.

John's proposing something that would work in conjunction with fees, so
it's no different than the MIN_RELAY_FEE that has quite successfully
prevented flooding on mainnet. For that matter, what he proposed can be
used even with non-final == non-standard, which means the replacement
transactions can't be broadcast onto the network at all until they can
be mined.

Actually, that's an interesting point: one way to do replacement
anti-DoS would be to only allow each input a given number of chances to
do a replacement. Provided your design is asymmetric in who the attacker
would be, and the inputs controlled by the defender outnumber the
attacker, the defender can always count on doing the last replacement.

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.


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

> BTW $500 is rather low for the amount of work required. If you added a zero
> onto that there might be more takers.

If he's reasonable about the scope, IE just a initial implementation for
further evaluation, I figure it's about two days work. $250/day is
enough that I'd give it a go - I already looked into how to implement it
anyway.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Peter Todd]

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

On Thu, Apr 18, 2013 at 05:04:44AM -0400, Peter Todd wrote:
> 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.

...and actually, that's not a problem if the defender is online, because
they can just broadcast the highest sequence numbered tx, which blocks
further broadcasts by the attacker. You still need some way of
distinguishing the two acts, by time is probably fine, but it'd make a
real attack difficult.

Of course, regardless you are still asking nodes to set aside however
many KB/second to tx replacement transactions, and they're all going to
use different settings, which makes overall network convergence
impossible to guarantee as legit replacement transactions outnumber
non-legit ones. Any protocol requiring the broadcast of more than one or
two replacements, either normally or against an attacker, just isn't
going to be reliable. But many don't, so they're probably doable.


But lets see some working code first...

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Mike Hearn]

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

> ...and actually, that's not a problem if the defender is online, because
> they can just broadcast the highest sequence numbered tx, which blocks
> further broadcasts by the attacker.


Good point - transactions can be ordered by highest version seen before
they're signature checked. Even without that improvement it's still rather
tricky to win the race though.

I'm intending on making a prototype for myself at some point soon, probably
in bitcoinj. I've been making notes and writing some initial code - I did
successfully replace a transation on my own little testnet, then I figured
I'd submit the patch so it's easier for others to play with it. But I
haven't got the whole thing working end to end yet.

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

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

[Mike Hearn]

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

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

[Mike Hearn]

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

On Thu, Apr 18, 2013 at 11:28 AM, Mike Hearn <mike@plan99.net> wrote:

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

Sorry brainfart, s/cores/cpus/. I think the 20k/sec was with full usage of
a hyperthreaded quad core CPU.

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

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

[Peter Todd]

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

On Thu, Apr 18, 2013 at 11:28:48AM +0200, Mike Hearn wrote:
> 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.

Mike, for the love of god, it's not acceptable to require Bitcoin
validating and mining nodes to buy unlimited bandwidth. The attacker
just has to spend more outgoing bandwidth than some fraction of the
network hashing power has incoming bandwidth (individually speaking) for
convergence to fail.

But anyway, as I said in my follow up email, with correct prioritization
it's probably a tractable problem.

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

Testnet has 40 nodes online right now that can be seen by my seeder. To
shut down all those nodes with a standard DoS attack would take at least
40 times more bandwidth than required by a tx-replacement DoS attack.

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

You can always add dummy inputs.

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

Well, all that making them relayable enables is letting all parties to a
transaction be offline when the nLockTime expires, so I'm not really
sure it's worth doing, at least immediately. Weakening the non-final ==
non-standard test to give a window of, say, 3 blocks, would be fine I
think.

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

The whole point of tx-replacement by fee is that the algorithm doesn't
need to be fixed. It makes it very clear that unconfirmed transactions
aren't trustworthy, and levels the playing field between you and people
posessing lots of hashing power. Nodes can independently choose their
replacement policy and the system still works. It also makes adjusting
fees after the fact easy, again, functionality that we really need right
now.

John's adjusting micropayments proposal would work best in conjuction
with some reputation stuff, like buying a fidelity bond promising you
will play nice with tx replacement. Implementing such bonds is a bit
subtle, because random chance can cause an earlier tx to be mined rather
than a latter, but you can, for instance, rebut accusations of fraud in
that case by simply creating an additional tx that pays the full amount
if a partial tx accidentally gets mined. Come to think of it, such a
system could be useful for inter-bank settlement, providing a security
guarantee somewhere between a standard transaction and a fully off-chain
transaction, at the cost of a single transaction fee.

More importantly, it's not subject to sudden "oh shit, slush's pool got
hacked and is doing double spends!" disasters. People should not be
trusting multiple mining pools run by individuals as hobbies on insecure
VPS services with the security of their payments, and zero-conf
transactions do exactly that. Not to mention the ~25% of hashing power
controlled by parties of unknown origin.

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Mike Hearn]

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

Indeed, as I mentioned in my first mail, nodes can be told how much
bandwidth they're allowed to use and then prioritize within that, so I
don't see any way convergence can fail. And regardless, I used 10mbit for
the calculations, that isn't exactly unlimited. My home internet connection
is better than that. It's just an arbitrary choice that lets us get a feel
for the numbers. We can see that even with a lot of replacements, an
attacker would have a hard time matching up his flood with when a block is
actually solved.

On the wider point - how many people DoS things with their own bandwidth?
The point of DNS reflection and/or botnets is you use other peoples
bandwidth. The attacks on Mt Gox are supposedly 80 gigabit+, which is
enough to take out all of the main network simultaneously. We can't do
anything about that. So I agree we should work to avoid opening up new DoS
attacks, but we should also be realistic about what can be accomplished.
The kind of people trying to manipulate Mt Gox could nuke the entire P2P
network off the face of the internet with the flick of a switch, presumably
the reason they aren't doing that it would to use Satoshi's phrasing
"undermine the validity of their own wealth".


> sure it's worth doing, at least immediately. Weakening the non-final ==
>
non-standard test to give a window of, say, 3 blocks, would be fine I
> think.
>

Sure. I think Gavin wants some kind of wider memory pool limiter policy
which would encompass such a thing already.

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

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

[Gavin Andresen]

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

> sure it's worth doing, at least immediately. Weakening the non-final ==
>>
> non-standard test to give a window of, say, 3 blocks, would be fine I
>> think.
>>
>
> Sure. I think Gavin wants some kind of wider memory pool limiter policy
> which would encompass such a thing already.
>

Yes.

I don't want to spend any time thinking about memory pool transaction
replacement until after we pay some technical debt:

+ Memory-limited memory pool, with relay policy matching block-creation
policy
+ Child-pays-for-parent fees
+ Auto-computed fees, based on transactions moving from the memory pool
into blocks


-- 
--
Gavin Andresen

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

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

[Mike Hearn]

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

> Or are you talking about some sort of new decentralized high frequency
> trading system that is self-matching and self-clearing? (I'd be very
> interested in hearing more if this is the case).
>

I'm using the term "high frequency trading" because Satoshi did. Like the
way he used the word "contract" it is perhaps a bit misleading, but we lack
anything better to describe this new concept.

Today HFT typically means companies that submits tons of micro-trades to
centralised asset exchanges to try and exploit statistically expected
correlations. HFT using tx replacement has nothing to do this with - it is
instead a way that N parties can negotiate amongst themselves as fast as
they can compute and verify signatures.

Here is how Satoshi explained it to me, in his words:

An unrecorded open transaction can keep being replaced until nLockTime.  It
may contain payments by multiple parties.  Each input owner signs their
input.  For a new version to be written, each must sign a higher sequence
number (see IsNewerThan).  By signing, an input owner says "I agree to put
my money in, if everyone puts their money in and the outputs are this."
 There are other options in SignatureHash such as SIGHASH_SINGLE which
means "I agree, as long as this one output (i.e. mine) is what I want, I
don't care what you do with the other outputs.".  If that's written with a
high nSequenceNumber, the party can bow out of the negotiation except for
that one stipulation, or sign SIGHASH_NONE and bow out completely.

The parties could create a pre-agreed default option by creating a higher
nSequenceNumber tx using OP_CHECKMULTISIG that requires a subset of parties
to sign to complete the signature.  The parties hold this tx in reserve and
if need be, pass it around until it has enough signatures.

One use of nLockTime is high frequency trades between a set of parties.
 They can keep updating a tx by unanimous agreement.  The party giving
money would be the first to sign the next version.  If one party stops
agreeing to changes, then the last state will be recorded at nLockTime.  If
desired, a default transaction can be prepared after each version so n-1
parties can push an unresponsive party out.  Intermediate transactions do
not need to be broadcast.  Only the final outcome gets recorded by the
network.  Just before nLockTime, the parties and a few witness nodes
broadcast the highest sequence tx they saw.

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

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

[Jeremy Spilman]

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

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

[Peter Todd]

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

On Fri, Apr 19, 2013 at 06:48:11PM -0700, Jeremy Spilman wrote:
>  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

Note that with OP_DEPTH we can remove the small chance of the payee
vanishing and putting the funds in limbo:

    <height + n> OP_DEPTH OP_LESSTHAN
    IF 2 PK1 PK2 CHECKMULTISIG
    ELSE PK1 CHECKSIG
    ENDIF

Though that shows how to implement OP_DEPTH as a true soft-fork we're
probably best off doing it as part of a script v2 using the soft-fork
mechanism I outlined before when talking about fidelity-bonded ledgers.
(best to do MAST (merklized abstract syntax tree) support at the same
time)

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

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

[Jeff Garzik]

On Thu, Jul 18, 2013 at 7:13 AM, Peter Todd <pete@petertodd.org> wrote:
> Note that with OP_DEPTH we can remove the small chance of the payee
> vanishing and putting the funds in limbo:

What are the costs, benefits, and risks associated with scripts no
longer being stateless, as OP_DEPTH would seem to introduce?

-- 
Jeff Garzik
Senior Software Engineer and open source evangelist
BitPay, Inc.      https://bitpay.com/

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

[Peter Todd]

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

On Thu, Jul 18, 2013 at 08:53:55AM -0400, Jeff Garzik wrote:
> On Thu, Jul 18, 2013 at 7:13 AM, Peter Todd <pete@petertodd.org> wrote:
> > Note that with OP_DEPTH we can remove the small chance of the payee
> > vanishing and putting the funds in limbo:
> 
> What are the costs, benefits, and risks associated with scripts no
> longer being stateless, as OP_DEPTH would seem to introduce?

Satoshi was worried that in the event of a re-org long chains of
transactions could become invalid and thus impossible to include in the
blockchain again, however that's equally possibly through tx mutability
or double-spends;(1) I don't think it's a valid concern in general. When
accepting any payment you need to take the chance of a re-org into
account, and if the payment is large enough it'll call for more confirms
on that basis. It does increase that (small) risk however and a client
may want to trace the transaction chain back a few steps when accepting
a very large payment in leu of just waiting for more confirms.

1) Also via non-standard transactions as SetBestChain() calls
mempool.accept() which still applies IsStandard(). We also recently
broke re-acceptance of transactions with dependencies as they are
currently added in reverse order, broken when Matt removed the
fIgnoreMissingInputs flag.


Not a problem limited to OP_DEPTH either: consider the following
probabalistic payment:

    PREVBLOCKHASH HASH n LESSTHAN VERIFY <pubkey> CHECKSIG

Obviously in a re-org the chance of it being succesfully included is
slim. (this example is simplistic and is vulnerable to double-spends in
a number of ways)


Mempool and relay code will have to take into account that a transaction
that can be included in the next block may not be possible to include in
the block after that for the purposes of protecting against tx-flood DoS
attacks - not an important issue unless we loosen IsStandard()

-- 
'peter'[:-1]@petertodd.org
0000000000000090344430e3956a709039288ceeb473fff6c1b68e70ee7169c4

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Peter Todd]

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

On Thu, Jul 18, 2013 at 07:13:53AM -0400, Peter Todd wrote:
> Note that with OP_DEPTH we can remove the small chance of the payee
> vanishing and putting the funds in limbo:
> 
>     <height + n> OP_DEPTH OP_LESSTHAN
>     IF 2 PK1 PK2 CHECKMULTISIG
>     ELSE PK1 CHECKSIG
>     ENDIF
> 
> Though that shows how to implement OP_DEPTH as a true soft-fork we're
> probably best off doing it as part of a script v2 using the soft-fork
> mechanism I outlined before when talking about fidelity-bonded ledgers.
> (best to do MAST (merklized abstract syntax tree) support at the same
> time)

jl2012 pointed out we already have an OP_DEPTH instruction that returns
the number of items on the stack. In the future we should use the terms
OP_BLOCKHEIGHT, OP_TXOUTHEIGHT, OP_TXOUTDEPTH to talk about hypothetical
instructions that put the block height, confirmed txout height, and
confirmed txout depth on the stack. Thus the above example would now be:

     <height + n> BLOCKDEPTH LESSTHAN
     IF 2 <pk-payor> <pk-payee> CHECKMULTISIG
     ELSE <pk-payor> CHECKSIG
     ENDIF

-- 
'peter'[:-1]@petertodd.org
0000000000000013030f49fe3eed5e7f9388c4ecc237b7a847ca93255836bc3b

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

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

[Jeremy Spilman]

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

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

[Mike Hearn]

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

Yes, this is an excellent observation. Thanks Jeremy and Peter. It's much
less general than full blown tx replacement+lock times, but for the case of
a channel between two people that only ever increases in one direction, it
can work. Thanks. I will try implementing this myself for testing on the
main network.

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

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

[John Dillon]

Sorry I don't have time to reply more in depth, but I wanted to say to
Jeremy (especially) and Peter I'm very impressed to see such a good
design be created so fast that does not depend on replacement at all.
This is a great example of how often the right approach to a problem
is to accept that the easy solution will not work, and find a way to
overcome the issue, rather than trying to paper over the easy
solution's problems with insecure design. I'm reminded of Peter's work
on fidelity bonded banking to overcome Bitcoin's scalability problem,
although that needs to become real, and soon, so we can find all the
flaws in it that will only become apparent when the idea is
implemented for real.

Jeremy: There does not seem to be a PGP key listed for your email
address. Is that correct?

On Sat, Apr 20, 2013 at 8:51 PM, Jeremy Spilman
<jeremy.spilman@gmail.com> wrote:
> 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.
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>