Handle transaction reordering attacks

[ttmc]

When transactions arrive at a node, can the node undetectably change their order (sequence) before writing them to the backlog? Similarly, can a node change the order that it writes transactions (from the same public key) to blocks? It wouldn't have to do this on a large scale; it could just switch the order of two transactions.

Sometimes it doesn't matter if the order of two transactions gets changed, but sometimes it does. For example, if Bob first transfers his dog to Jack, and shortly thereafter tries to transfer it to Mike, the second transfer should fail because Bob no longer owns the dog. Now imagine if the "transfer to Mike" transaction gets re-ordered to come before the "transfer to Jack" transaction...

Possible solutions

• Add a "sequence_number" to the transaction data model. Each client public key would generate a sequence of transactions over time and the sequence number would increase by 1 for each new transaction: 1, 2, 3, ... When validating a transaction, you'd check to ensure that the sequence number is equal to (the last sequence number from that public key) + 1
• Instead of sequence numbers, all transactions from the same public key could be required to include the hash of the previous transaction from that public key (unless there was no previous transaction from that public key).
• Give clients the ability to send multiple transactions in one “ordered transaction package” so that the ordering is clear and can’t be changed by a node without detection. How to reliably unpack them?
• Give clients the ability to send a transaction of the form: “I’m about to send a series of transactions with the following IDs/hashes and here is the order in which they should be processed.” Then the client waits for that transaction to be in a valid block before sending the listed transactions.

Non-solutions

• Use at the client-provided timestamps in the transactions to determine their true order. This is a non-solution because we can't trust timestamps. In fact, we might get rid of timestamps entirely so as to save others from using them by mistake. See issue #132 . While it's true that clients have no incentive to send transactions with out-of-order timestamps, their system clock might still be broken, inaccurate, or compromised.

Related issue: issue #327

[ssadler]

Unfortunately I think this is Jack's problem isn't it? Our HTTP server replies with "202 ACCEPTED" for this reason, that the transaction has been accepted for processing but it is not yet complete. Jack must then demand that Bob wait until the transaction part of a valid block, ie, it's a payment clearing time.

In the possible solutions above, neither sequence number nor hash of previous transaction are a solution to the possible double spending issue.

[ttmc]

This issue isn't about catching double-spending. We already do that. The second transaction would be the one deemed invalid, because it's trying to spend an output that's already spent. The problem is that a malicious node could change which transaction is the second one.

[ttmc]

Right now, we can't guarantee that some transactions sent from a client in the order A, B, C will get processed in the same order (A, B, C). One way to ensure that would be to add a "client sequence number" (integer) to the body of the transaction model, with the idea that a transaction can't be processed until all sequence numbers before it have been processed. (Or maybe the transaction is considered invalid and dropped if there are some earlier sequence numbers not yet in the committed valid transactions [i.e. not yet in the blockchain]).

This could go along with the idea of modifying the transaction model to require every transaction be signed independently of whatever is in the fulfillments in the inputs. The public key of the signer would identify which series of sequence numbers this transaction belongs to.