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

2013-07-18 Thread Peter Todd
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


signature.asc
Description: Digital signature
--
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk___
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

2013-07-18 Thread Jeff Garzik
On Thu, Jul 18, 2013 at 7:13 AM, Peter Todd p...@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/

--
See everything from the browser to the database with AppDynamics
Get end-to-end visibility with application monitoring from AppDynamics
Isolate bottlenecks and diagnose root cause in seconds.
Start your free trial of AppDynamics Pro today!
http://pubads.g.doubleclick.net/gampad/clk?id=48808831iu=/4140/ostg.clktrk
___
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

2013-04-23 Thread 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.spil...@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


--
Try New Relic Now  We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service 
that delivers powerful full stack analytics. Optimize and monitor your
browser, app,  servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_apr
___
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

2013-04-22 Thread Mike Hearn
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.
--
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

2013-04-20 Thread Jeremy Spilman
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


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

2013-04-19 Thread Jeremy Spilman
 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
--
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

2013-04-18 Thread John Dillon
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On Wed, Apr 17, 2013 at 9:48 AM, Mike Hearn m...@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 

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

2013-04-18 Thread Peter Todd
On Thu, Apr 18, 2013 at 06:07:23AM +, 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


signature.asc
Description: Digital signature
--
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

2013-04-18 Thread Mike Hearn
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.
--
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

2013-04-18 Thread Peter Todd
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


signature.asc
Description: Digital signature
--
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

2013-04-18 Thread Peter Todd
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


signature.asc
Description: Digital signature
--
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

2013-04-18 Thread Mike Hearn
 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.
--
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

2013-04-18 Thread Mike Hearn
On Thu, Apr 18, 2013 at 11:28 AM, Mike Hearn m...@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.
--
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

2013-04-18 Thread Mike Hearn
 ...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.
--
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

2013-04-18 Thread Peter Todd
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


signature.asc
Description: Digital signature
--
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

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

2013-04-18 Thread Mike Hearn
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.
--
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

2013-04-18 Thread Gavin Andresen
 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
--
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

2013-04-18 Thread 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 p...@petertodd.org wrote:
 On Thu, Apr 18, 2013 at 06:07:23AM +, 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

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

2013-04-18 Thread Jeff Garzik
On Fri, Apr 19, 2013 at 12:38 AM, John Dillon
john.dillon...@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.
jgar...@exmulti.com

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

2013-04-17 Thread Mike Hearn
 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.
--
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

2013-04-17 Thread Alan Reiner
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 

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

2013-04-16 Thread Peter Todd
Post tge malicious miners and other bits so we can evaluate the system as a 
whole. 

Mike Hearn m...@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