Gavin, not with my proposal. The earth bitcoin nodes do not collaborate with the New York vending machine. They will follow the protocol for local verifications, and hence not work on the NY spending. This system requires that the majority work according to the protocol in any case.

I did not specify how honest bitcoin nodes work exactly. Here is one possibility.

When a node sees a new transaction, T, it does the following in pseudocode.

If (ingoing T has double spending verifier) {
 send request to verifier;
 if (response == ok) {
  put T into block and try to generate a hash;
 } else if (reponse == double spending, use transaction S) {
  put S into block and try to generate a hash;                       <- this is what would happen in your example
 } else { 
  // time out, verifier is out of order. The time out should take place after a time which is larger than a round trip to the verifier.
  put T into block
 } else {
  // T has no double spending verifier
  put T into block
}

In the Mars example, the following would happen.

S is the transaction on Mars, T is the one on earth.
T and S have the same ingoing coin, which is marked with a Mars verifier.

1a. You pay the Mars vending machine with T
1b. Your cousin pays the NY vending machine with S

2a. The Mars vending machine contacts the verifier and the network with S.
2b. The NY vending contacts the verifier and the network with T.

3a. The verifier receives S and replies "ok" to the Mars vending machine.
3b. Nodes will begin to see T and S on their respective planets. The nodes will follow the pseudocode above. Only outlaws will try to get S or T into blocks. The outlaws have
too little CPU  power and hence will not have generated any blocks yet.

4. The Mars vending machine release the candy bar after seeing the "ok".

A long time will pass. Neither S nor T are in any block, since the majority of the CPU power is in the "wait for verifier response mode". Other unrelated blocks are generated.

5. The verifier's repsonse will reach Earth, and the majority of the nodes will start working on S.

6. S gets into a block and more blocks are added later.


The NY vending machine can only take the coin if it controls a lot of CPU power and can generate a block, but the whole bitcoin system is built on the assumption that the vast majority of CPU power is honest. And being honest with my proposal means following the pseudocode above.

I should have specified this pseudocode in the original post. I didn't do it, because this protocol is one of several variations of the same theme, and I didn't want to be that specific. One variation is that the nodes could start working on T as soon as they get it, but that would break down in this case unless the difficulty was increased to a time much beyond the Mars latency, i.e. many hours.