Would this improve anonimity and reduce (somewhat) blockchain data overhead?

[Kazimir]

Suppose I send x bitcoins from A to P, and someone else sends y bitcoins from B to Q.

This could also be done in a single transaction, sending x+y bitcoins from A & B, with two outputs, x to P and y to Q. Or am I mistaken here?

(well, if I understood correctly, technically you don't just send x bitcoins from A to P, but you send all bitcoins from A to two outputs: x to P and the remainer (change) back to A or another address that belongs to the same owner as A)

The thing with Bitcoin anonimity is, if you see two or more addresses together at the input side of a transaction, you can assume they're in the same wallet, thus having the same owner.

If the above 'transaction combining' would be applied randomly on transactions that were initially unrelated, this assumption could no longer be made.

However, I don't know if this is possible at all? If a node confirms the transactions, could it decide to combine them, merging two transaction into a single new one? Or is this impossible without making the transaction invalid? (I'm not 100% familiar with the exact transactions protocol specs and the way they're signed and confirmed - obviously a node does have the signature of A en B to send x and y bitcoins to P and Q, respectively)

[DeathAndTaxes]

It is not possible.  Transactions are signed by the private key of the input being used.  You can't combine two tx from multiple parties without trusting either the other party or a third party.

Note in your example if entity A & B send a tx to node Z it doesn't matter even if node Z "could" combine them into a single tx node Z still knows A was sending coins to P and B was sending coins to Q.

[kokjo]

Suppose I send x bitcoins from A to P, and someone else sends y bitcoins from B to Q.

This could also be done in a single transaction, sending x+y bitcoins from A & B, with two outputs, x to P and y to Q. Or am I mistaken here?

(well, if I understood correctly, technically you don't just send x bitcoins from A to P, but you send all bitcoins from A to two outputs: x to P and the remainer (change) back to A or another address that belongs to the same owner as A)

The thing with Bitcoin anonimity is, if you see two or more addresses together at the input side of a transaction, you can assume they're in the same wallet, thus having the same owner.

If the above 'transaction combining' would be applied randomly on transactions that were initially unrelated, this assumption could no longer be made.

However, I don't know if this is possible at all? If a node confirms the transactions, could it decide to combine them, merging two transaction into a single new one? Or is this impossible without making the transaction invalid? (I'm not 100% familiar with the exact transactions protocol specs and the way they're signed and confirmed - obviously a node does have the signature of A en B to send x and y bitcoins to P and Q, respectively)

yes it is possible.

BUT, you can not modify a transaction, so a random node in the network could not merge two transaction. for this to work both senders should corporate, but not necessarily trust eachother.

[Gavin Andresen]

I actually created and spent some "input from wallet a", "input from wallet b" private testnet transactions earlier this week (I'm working on some lower-level RPC commands for bitcoind -- see https://gist.github.com/2839617  for the half-baked spec).

Somebody could build a transaction-combining service on top of those low-level RPC commands, although I suspect to be really resistant to sophisticated network analysis doing "one or more inputs from A in,  one or more from B in, ApayToSomebody Achange BpayToSomebodyElse Bchange out" won't help much.  There is a lot of prior work on "mix networks" and maintaining anonymity, and the only thing I know about it is that it is a hard problem to get right.