Stats on malled transactions

[DeathAndTaxes]

Wouldn't a better fix be to change the client behavior such that there is only one correct way to encode a transaction (with enforcement to begin in some future block), removing the possibility of malleability?

That is the long term fix.  You essentially are talking about transaction immutability.  However it can't simply be a client side "feature" as an attacker would just modify their client.  It will need to be enforced by the protocol.   That means (most likely) a hard fork and there just is no way to do that "fast and easy".   The situation is made more complex by the fact that ECDSA signatures are not "unique" it is possible for more than one set of inputs to produce the same signature. 

Simple version:
Long Term Goal (hopefully share unanimously by core developers):  Make unconfirmed tx ids immutable (or at least immutable to third parties).
Short Term Goal: Client behavior in dealing with mutable tx ids needs to be more consistent and expected until we get to the long term goal.

As a historical note.  Adding P2SH was a much simpler fork to the protocol.  From the time that P2SH code was completed to the time P2SH was supported by the protocol was about 8 months.

[phelix]

Seems we are back to business as usual.
2014-02-12 393
Updating OP.

Is this because of the attacker / the exchanges on hold?

Or is it because pools updated their software with the 0.8 fixes?

The attacker stopped.  Why and for long run remains unknown.  A patched client doesn't prevent the duplicates from existing so if tx were still being duplicated they should show up.

I thought 0.8+ clients did not relay some (the current?) malled transactions...


It would be fun to try and find the source nodes (given they can be distinguished and it's not a large botnet). Of course this is not a solution (Tor, intermediate node, ...).
1. Get well connected, don't relay malled txs
2. Wait until a malled tx propagates through the network
3. Drop the 50% connections that you receive the malled tx from last
4. goto 1

optional 3b. ddos the #1 node on the list until it stops

The network police might come handy with some types of ddos attacks

I wonder if anybody ever tried homing in on a malicious node like this.

[BradZimdack]

About 0-conf: for small, day by day payments they were absolutely safe. The cost to perform a double spend was simply not worth the cost of a coffee. Now, that changes, 0-conf are not safe even if the buyer is 100% honest and the cost of the product is negligible: again we cannot downplay the effect of that, it's quite serious.

It is important now with mass mutation attack going on to distinguish between

0 confirm tx where all inputs are confirmed
vs
0 confirm tx where one or more inputs are also 0 confirm.

Distinguishing between those two types of transactions is fine from a technical point of view but we'd never be able to explain that difference to a customer.  I'm mostly concerned about the customer service problems this will create.  Alice gets her donut because she spent confirmed inputs.  Bob doesn't get his donut because he spent unconfirmed change.  Neither Alice nor Bob have clue what any of that means.  How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?

Are there any ideas on whether a technical solution to this problem will be forthcoming or any suggested workarounds?

[phelix]

Wouldn't a better fix be to change the client behavior such that there is only one correct way to encode a transaction (with enforcement to begin in some future block), removing the possibility of malleability?

That is the long term fix.  You essentially are talking about transaction immutability.  However it can't simply be a client side "feature" as an attacker would just modify their client.  It will need to be enforced by the protocol.   That means (most likely) a hard fork and there just is no way to do that "fast and easy".   The situation is made more complex by the fact that ECDSA signatures are not "unique" it is possible for more than one set of inputs to produce the same signature. 

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

[Richy_T]

Seems obvious to me. You don't try and spend what you don't know you have. Maybe that means wallets have to jump through hoops or you just don't get your donut but to my mind, that's what it boils down to. Bitcoin is supposed to be about cold, hard facts not payday loans.

[thenoblebot]

I thought 0.8+ clients did not relay some (the current?) malled transactions...


It would be fun to try and find the source nodes (given they can be distinguished and it's not a large botnet). Of course this is not a solution (Tor, intermediate node, ...).
1. Get well connected, don't relay malled txs
2. Wait until a malled tx propagates through the network
3. Drop the 50% connections that you receive the malled tx from last
4. goto 1

optional 3b. ddos the #1 node on the list until it stops

The network police might come handy with some types of ddos attacks

I wonder if anybody ever tried homing in on a malicious node like this.

Hey,

I have been working on the idea about trying to find the rogue nodes/pool over the past day or so. Check this thread for more https://bitcointalk.org/index.php?topic=463350.0. Its a simple idea that I have thought about but I cant implement it on my own because I am not a programmer. Maybe you could contribute ?

Cheers

[DeathAndTaxes]

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

What is a malled tx look like?  There are many ways that a tx can be mutated that makes identifying the "correct" one impossible.  Most nodes and pools already drop the duplicate the issue is the duplicate is getting to the pool before the original.  It wouldn't end up in a block otherwise.

If you have two tx each are equally valid and correct, how do you know which one was mutated after sending?   You can't so you do what you already do.  You keep the one you receive first and you drop the other one.  That means if the mutated tx gets to a miner's memory pool first, it will get included in a block.

[DeathAndTaxes]

How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?

You probably won't be able to so the only solution is to prevent it from happening to begin with.

Honestly until tx ids are immutable, the use of unconfirmed change outputs is just going to cause mass chaos.

The client waiting until change is confirmed isn't "ideal".  The ideal solution is to make tx ids immutable but that is a long term fix.  In the interim a user (possibly) having to wait for the change to be confirmed is far superior to transactions randomly breaking and non-technical users and merchants trying to figure out why it seems to just fail randomly.  The later is just going to kill adoption. 

[phelix]

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

What is a malled tx look like?  There are many ways that a tx can be mutated that makes identifying the "correct" one impossible.  Most nodes and pools already drop the duplicate the issue is the duplicate is getting to the pool before the original.  It wouldn't end up in a block otherwise.

If you have two tx each are equally valid and correct, how do you know which one was mutated after sending?   You can't so you do what you already do.  You keep the one you receive first and you drop the other one.  That means if the mutated tx gets to a miner's memory pool first, it will get included in a block.

I thought it was possible to determine if a tx looks like it was created by the standard client or not. Should this not be possible or there are too many different legitimate tx styles out there then I guess we will have to deal with malled txs.

[BradZimdack]

How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?

You probably won't be able to so the only solution is to prevent it from happening to begin with.

So basically stop accepting 0-conf transactions for all purposes, even from trusted customers, until all wallet software has been updated to not spend unconfirmed change?  This seems like an extremely severe setback for bitcoin adoption and its utility in general.

[phelix]

https://bitcointalk.org/index.php?topic=463945  [RFC] Detecting Malled Transactions

[klondike_bar]

my bitcoin-qt is virtually useless as it is including mauled transactions in its balance. blockchain wallet is fine though.

however, its been 22 confirmations since i sent a deposit to btc-e, i have no idea why it isnt added to my account yet

[DeathAndTaxes]

How do we explain to Bob that he doesn't get his donut without resulting in a fist fight, a discrimination lawsuit, an all day seminar on the technical workings of the blockchain, giving away a free donut, and/or potentially losing Bob as a regular customer?

You probably won't be able to so the only solution is to prevent it from happening to begin with.

So basically stop accepting 0-conf transactions for all purposes, even from trusted customers, until all wallet software has been updated to not spend unconfirmed change?  This seems like an extremely severe setback for bitcoin adoption and its utility in general.

The issue isn't 0-conf transactions.  It is 0-confirm tx which use as their inputs the unconfirmed outputs of another transaction.

All Bitcoin clients ALREADY prevent the client from spending unconfirmed outputs for lots of very good reasons.   However since the wallet can "trusts itself" they wallet makes an exception for unconfirmed CHANGE.   Obviously no user is going to double spend themselves.   So the prior tx will eventually confirm and that means the change will eventually confirm as well.

Except if an attack mutates the original tx, then the original will never confirm, the duplicate will.  That means the change output is now invalid and the subsequent tx will never confirm.

Simple version:
This isn't about 0-conf tx.  This is about transactions using the as their input 0-conf outputs.

[Richy_T]

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

What is a malled tx look like?  There are many ways that a tx can be mutated that makes identifying the "correct" one impossible.  Most nodes and pools already drop the duplicate the issue is the duplicate is getting to the pool before the original.  It wouldn't end up in a block otherwise.

If you have two tx each are equally valid and correct, how do you know which one was mutated after sending?   You can't so you do what you already do.  You keep the one you receive first and you drop the other one.  That means if the mutated tx gets to a miner's memory pool first, it will get included in a block.

I thought it was possible to determine if a tx looks like it was created by the standard client or not. Should this not be possible or there are too many different legitimate tx styles out there then I guess we will have to deal with malled txs.

All that really needs to be done is for transactions to be reformatted to standard format and txids generated from that. Any other txid would be invalid. Surely?

[DeathAndTaxes]

What about a soft fork: pools don't include malled txs and clients don't relay them. I think this would very quickly solve the problem.

What is a malled tx look like?  There are many ways that a tx can be mutated that makes identifying the "correct" one impossible.  Most nodes and pools already drop the duplicate the issue is the duplicate is getting to the pool before the original.  It wouldn't end up in a block otherwise.

If you have two tx each are equally valid and correct, how do you know which one was mutated after sending?   You can't so you do what you already do.  You keep the one you receive first and you drop the other one.  That means if the mutated tx gets to a miner's memory pool first, it will get included in a block.

I thought it was possible to determine if a tx looks like it was created by the standard client or not. Should this not be possible or there are too many different legitimate tx styles out there then I guess we will have to deal with malled txs.

All that really needs to be done is for transactions to be reformatted to standard format and txids generated from that. Any other txid would be invalid. Surely?

That is a rather large "all" by itself as the input script is rather "loose".  That isn't all you need to do though.  ECDSA signatures are not immutable - Ouch. You also need to restrict signatures to a single "form" (DER) as OpenSSL (which Bitcoin uses) validates a variety of forms - double ouch.

To produce immutable hashes you need to:
a) Limit signatures to DER.  OpenSSL verifies non canonical forms of signatures.  Initially Bitcoin was no more restrictive than OpenSSL.  Since v0.8 Bitcoin, non-DER signatures are non standard and are not relayed by nodes running v0.8+.  This was MtGox problem their "Goxxed v0" custom client was creating non-DER signatures and thus the tx were being dropped by most nodes.

b) Make ECDSA Signatures immutable.  ECDSA signatures are not immutable, they were never designed to be and they never will be.  ECDSA will produce the same signature with both S and -S for a given payload and priv key.  So same tx data, same signature, different hash.  To resolve this "Bitcoin signatures" will need to be more restrictive than ECDSA signatures.  In other words all (future) valid Bitcoin signatures are valid ECDSA signatures, but not all valid ECDSA signatures will be valid Bitcoin signatures.

c) Allow only one form of input script for a given outcome.  The Bitcoin protocol is rather loose when it comes to op-codes in the input script.  It is possible to make some changes to these and still produce the same output (just like 3 + 2 = 3 + 2 +0).  Fixing this aspect will require tighter rules on what is a valid input script.


That is a lot to do, test, and get right.  Think of the "upgrading a plane in flight" analogy.

It can be done is phases to provide a safer path to the hard fork.
First the improved rules would be implemented in new version of clients (i.e. all clients would always use a +S instead of a + or -S) but clients wouldn't treat the "worse" tx any differently.
Next clients would favor "better" form of the transaction (i.e. if a node receives duplicates it will keep the one with the +S).
Next clients would consider the "worse" forms to be non-standard and would refuse to relay them (i.e. -S = non-standard, and tx is dropped by an upgraded node but still valid if in a block).
Finally clients would tx which break the new "better" rules to be invalid (i.e. after block # XXXXXXXXXX a tx with a -S is invalid, a block containing a tx with a -S is invalid).

It isn't going to happen overnight so in the interim mutable transaction ids are just a reality for Bitcoin.

[Richy_T]

Interesting. More involved than it sounded.

[oakpacific]

I am curious as to how the client knows in the first place if a transaction has propagated, thus allowing spending uncofirmed changed output? I mean your ISP can MITM you or all the nodes  connected can just drop it, if you put your tinfoil hat on.

Maybe the miners can be configured to respond to queries about if a transaction is in the mempool, but that opens them up to possible DDOS attacks.

[DeathAndTaxes]

I am curious as to how the client knows in the first place if a transaction has propagated, thus allowing spending uncofirmed changed output? I mean your ISP can MITM you or all the nodes  connected can just drop it, if you put your tinfoil hat on.

It doesn't it will just keep rebroadcasting periodically.  If you are concerned about that scenario, ensure you have a high number of peers and use a vpn tunnel to get "past" your ISP.  No client does this but you could design a client so that it only broadcasts a tx randomly to some of its peers.  If the tx fully propagates the network the other half should inform you about it.  If they don't that would be a warning sign.  The node could also rotate peers to make isolation even more difficult.

For a commercial entity this can be taken a step further by putting a number of geo diverse listening nodes out that which communicate with your main node via an out of band channel.  We use a setup similar to that to troubleshoot customer reports of "transaction not showing up".  The listening nodes can also be used by 0-confirm merchants to look for things like double spend attempts.  If you imagine a 0-confirm merchant who has 8 listening nodes setup around the world each with an average of 2,000 peers connected, there may be some overlap put lets assume that gives the merchant 10,000 or so unique peers.  If any one of those 10,000 unique peers is relayed the double spend, then it would be relayed to one of the listening nodes who would alert the main node.

[itod]

For a commercial entity this can be taken a step further by putting a number of geo diverse listening nodes out that which communicate with your main node via an out of band channel.  We use a setup similar to that to troubleshoot customer reports of "transaction not showing up".  The listening nodes can also be used by 0-confirm merchants to look for things like double spend attempts.  If you imagine a 0-confirm merchant who has 8 listening nodes setup around the world each with an average of 2,000 peers connected, there may be some overlap put lets assume that gives the merchant 10,000 or so unique peers.  If any one of those 10,000 unique peers is relayed the double spend, then it would be relayed to one of the listening nodes who would alert the main node.

Nice idea. Is this deployed already? Open source by any chance?

[Jan]

I am curious as to how the client knows in the first place if a transaction has propagated, thus allowing spending uncofirmed changed output? I mean your ISP can MITM you or all the nodes  connected can just drop it, if you put your tinfoil hat on.

It doesn't it will just keep rebroadcasting periodically.  If you are concerned about that scenario, ensure you have a high number of peers and use a vpn tunnel to get "past" your ISP.  No client does this but you could design a client so that it only broadcasts a tx randomly to some of its peers.  If the tx fully propagates the network the other half should inform you about it.  If they don't that would be a warning sign.  The node could also rotate peers to make isolation even more difficult.

For a commercial entity this can be taken a step further by putting a number of geo diverse listening nodes out that which communicate with your main node via an out of band channel.  We use a setup similar to that to troubleshoot customer reports of "transaction not showing up".  The listening nodes can also be used by 0-confirm merchants to look for things like double spend attempts.  If you imagine a 0-confirm merchant who has 8 listening nodes setup around the world each with an average of 2,000 peers connected, there may be some overlap put lets assume that gives the merchant 10,000 or so unique peers.  If any one of those 10,000 unique peers is relayed the double spend, then it would be relayed to one of the listening nodes who would alert the main node.

And you can go even further.
- make your transaction confidence depend on the depth and width of the parent chain of unconfirmed transactions
- has any unconfirmed parent been malled
- has any unconfirmed parent been attempted double spent
- have sufficient feed been paid for unconfirmed parents
- do any unconfirmed parents have an nlocktime
- are any unconfirmed parents non-standard

These parameters are what the new Mycelium p2p trading feature uses to determine the 0-99% "transaction confidence".
In the end you can never be 100% certain, not even when a transaction has gotten its first confirmation, but you can use it as a tool and throw in  other circumstances like the value of the goods exchanged, your trust in the peer etc.