Proposed solution to the latency problem (vending machine problem).

[mkrogh]

Hi

I started a thread about the lack of fast local double spending verification a
week ago.  I was away for a week, and couldn't follow up on the thread. During
this week, I became even more positive about bitcoin. Contrary to what I said
last week,  I think that bitcoin could be a stand alone system; no issuer based
systems are needed to coexist with bitcoin. Bitcoin could be the real thing!
Kudos to all that have participated in it.  However, fast verification of the
absence of double spending is still important. I think, I have a solution that
more or less achieves it.

I should stress, that the underlying bitcoin architecture is completely
unchanged. My solution is living on top of bitcoin, so to speak.

Key to fast double spending verifications is to give coins a "location". A coin
can be local to such and such server in New York, for instance.  A New York
coin can be spent anywhere. It is valid anywhere etc. It is just that you can
expect faster double spending verification in NY.  Coins don't have to have a
location.

My proposed solution is to incorporate an extra field in outgoing transactions
designating a double spending verification server.  A coin's double spending
verification server is the one of the last outgoing transaction, of course.

The participants of the network are

1. Double spending verification servers. They do not exist in the current
system. The operation of a specific server is to receive a transaction for a
coin belonging to them, put it in a data store, and reply whether there is an
earlier transaction with the same coin.  In the case of no earlier transaction
just reply "ok", in the case of an earlier transaction reply "Double spending
attempt. The first transaction with this coin is so and so ..... ". The double
spending verification servers could be identified by a public key. This public
key might be the field stored in the coin. Some other database relates public
keys to ip addresses, dns or physical locations. The reply from the verifier
could be signed to prove the absence of interception.

2. The payer. The payer can choose a double spending verification server for
the outgoing transaction. Usually, one would choose the local one, or one that
is thought to be local for the payee. But anything goes, including choosing
nothing.

3. The payee. The payee will look at the double spending verification server of
the ingoing transaction, and send a request to this server.  If the reply is
"ok", the payee can trust the payment. If not, the payment is rejected. The
block chain is still the final judge, of course.  The super paranoid payee can
just wait for block incorporation, and is not forced to deal with the double
spending verifiers at all.

4. The bitcoin nodes. They will contact the double spending verifiers about
each transaction. If there is a double spending attempt, they will work on the
transaction suggested by the double spending verification server. This point is
crucial. The bitcoin nodes don't care how to resolve a double spending attempt,
so they just follow the advice of the corresponding double spending verifier.
This point is also what makes it possible for the payee to accept a payment as
soon as the double spending verifier has accepted it; the payee will know that
most honest nodes will favor this transaction.

So, a visit to a vending machine in would go as follows. The vending machine
would suggest some double spending verifiers that it trusts and publish the
latency for each of them. The wallet would choose the coin with the lowest
latency according to these figures, and pay with it. The vending machine would
contact the verifier and presumably get an ok, and release the product. It is
possible to prepare a wallet for a visit by making an exchange to oneself and
choose a new verifier. So on the plane to Australia, you transfer coins to
yourself and change the verifiers. When you arrive at the vending machine in
Australia, you will get millisecond response. But even, if the verifier is in
the US, the latency is still low. Much lower than block incorporation.

What if a verifier cheats? This will only happen a few times. You can publish
that you got an ok from a verifier, and then later the transaction was rejected
by the bitcoin network. It is even possible to use signatures to prove that the
verifier cheated if necessary. There will probably be quite few
verifiers compared to bitcoin nodes.

A group of people that wants to make some ultra fast local trading can then
meet close to a verifier, or run a verifier themselves, exchange their coins to
become local to this verifier, and start their high frequency trading. They can
all trust the absence of double spending without waiting for global
verification or block incorporation. 

Again, the bitcoin block chain is the final judge. This is just a voluntary
system on top.

Please, tell me if anything was unclear or I am missing something.

[Gavin Andresen]

Your proposal seems needlessly complicated.

How about:

The vending machine talks to a "Bitcoin+ Payment Verification Systems, Incorporated" server.

The Bitcoin+ Payment Verification System is basically just a bitcoin node, with really fast international network connections and a little extra code to detect attempted double-spends.  If it detects a double-spend attempt, it rejects the transaction.  Otherwise, it accepts the transaction and blasts the transaction into the payment network over its really fast, as-low-latency-as-possible connections.

If it later turns out that the transaction actually WAS invalid, Bitcoin+ Payment Verification Systems, Incorporated absorbs the cost of the fraud.
Bitcoin+ Payment Verification Systems, Incorporated, of course, charges the vending machine merchant a fee for providing such excellent service.  They're constantly competing with their arch-rivals, "Better Merchant Services, Incorporated" to balance latency, fees, and fraud to maximize profit.

[mkrogh]

Gavin, your solution has high latency. I want to solve the problem of locality. You can get double spending verification at a time scale that does not grow with the total size of the network.

There are two uses of this. One is for high speed trading, i.e. millisecond latency, the other is for huge networks. The vending machine might be on Mars for that matter.

This is why locality should be built in in some way.

Your method is simply too slow for me, otherwise it works of course. On this planet, your method would preclude verifications faster than 200 milliseconds say.
The speed of light is the fundamental problem.

[Gavin Andresen]

I'm better at thinking through things using specific examples, so bear with me:  let's use Mars as the extreme case, and say I'm on Mars and want to double-spend some bitcoins.

I talk to my cousin in New York, and send him some coins with the "Mars" locality.  We agree that we'll use the same coins to buy candy bars on January 1, 2040, 10:00:00 UTC, me on Mars and him in New York.

So the New York candy machine just rejects my cousin's transaction OR makes him wait the 40 minutes for communication between Earth and Mars?  Wouldn't it be more likely that the New York candy machine just accepts the transaction after seeing no double-spends after, oh, I dunno, maybe two seconds?

After all, Bitcoin+ Payment Verification Systems, Incorporated knows it is highly connected into the majority Bitcoin network with very low latency, so it knows that if it blasts a transaction into the network and doesn't see a double-spend after two seconds the chances are very, very, very good that it will be declared the first spend.

If the New York payment system accepts the transaction every time, then the Mars verifier will lose every time.  I'm pretty sure the New York folks will tell the Mars folks "tough cookies, you should set up MarsCoin for low-latency transactions up there."

I don't know much about high speed trading with millisecond latency, and, frankly, don't care much about high speed trading with millisecond latency.  It wouldn't bother me at all if you can't use Bitcoin for that (and you have to set up a SpeedyCoin system for doing that sort of thing).

[Red]

Mars is more extreme but there is an ATM in Antarctica.

http://www.needcoffee.com/2010/01/12/antarctica-atm-interview/

:-)

I like this article because it points out the difference between currency and money. There is a fixed amount of currency in Antarctica, but that amount is completely unrelated to how much money the people there own. (mere account balances)  Yet, bafflingly to some, the system works quite swimmingly for all involved.

The mars situation could work exactly the same way.

[mkrogh]

I'm better at thinking through things using specific examples, so bear with me:  let's use Mars as the extreme case, and say I'm on Mars and want to double-spend some bitcoins.

I talk to my cousin in New York, and send him some coins with the "Mars" locality.  We agree that we'll use the same coins to buy candy bars on January 1, 2040, 10:00:00 UTC, me on Mars and him in New York.

So the New York candy machine just rejects my cousin's transaction OR makes him wait the 40 minutes for communication between Earth and Mars?  Wouldn't it be more likely that the New York candy machine just accepts the transaction after seeing no double-spends after, oh, I dunno, maybe two seconds?

Not in my system, because the bitcoin nodes would not work on a transaction before it was accepted by the verifier or before a certain time out has passed if the verifier doesn't respond.

Also, there could be a lot of cpu power on Mars as well. So, the New York vending machine shouldn't accept a Mars coin within several hours.

After all, Bitcoin+ Payment Verification Systems, Incorporated knows it is highly connected into the majority Bitcoin network with very low latency, so it knows that if it blasts a transaction into the network and doesn't see a double-spend after two seconds the chances are very, very, very good that it will be declared the first spend.

On earth, yes, but not in the Mars example. Most bitcoin nodes are far away.

If the New York payment system accepts the transaction every time, then the Mars verifier will lose every time.  I'm pretty sure the New York folks will tell the Mars folks "tough cookies, you should set up MarsCoin for low-latency transactions up there."
[\quote]

I am not sure we are talking about the same setup. Are you talking about a single node on Mars and many on earth. That is a very special situation.

I don't know much about high speed trading with millisecond latency, and, frankly, don't care much about high speed trading with millisecond latency.  It wouldn't bother me at all if you can't use Bitcoin for that (and you have to set up a SpeedyCoin system for doing that sort of thing).

Why, when it is as easy as I describe (unless I am missing something). Actually, I don't think my proposal is complicated. Maybe, I just haven't expressed myself clearly enough.

Red, interesting about Antarctica. I just don't see the connection. They are certainly connecting to a bank account, and they will wait for the communication to go back to the rest of the world. So, you probably have to wait for several seconds if you withdraw at that ATM.

[Gavin Andresen]

Also, there could be a lot of cpu power on Mars as well. So, the New York vending machine shouldn't accept a Mars coin within several hours.

My point is that if there is a lot less cpu power on Mars, then the Mars nodes will ALWAYS lose the "create the longest block chain" race.  So the New York nodes will ALWAYS have the advantage.

And it is nice to say the New York vending machine "shouldn't accept a Mars coin within several hours,"  but, in my experience, "shouldn't" doesn't cut it.  If the New York candy machine CAN make the sale and keep the coins, it WILL.

[mkrogh]

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.

[Gavin Andresen]

.... This system requires that the majority work according to the protocol in any case.
...
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.

Right, that's my issue with your proposal:  what incentive does the NY vending machine have to be honest?  It can be "dishonest", ignore verifiers all-together, and accept more transactions (better for it) with less work (also better for it).

[mkrogh]

The NY vending machine can not generate blocks on its own. It has way too little CPU power for that.  The vending machine can be as dishonest as it wants to as long as it is
CPU dwarfed by honest nodes. Actually, I wouldn't even call it dishonest. Someone paid for a candy bar. But it can not force the coin to go to itself.
The vending machine's average time to generate a block could be years. It would only have an hour or so before all honest nodes are working to incorporate the Mars vending
machine's transaction.

[Insti]

I do not think that millisecond transaction processing is a necessary feature for Bitcoin. If this is what you really want you should probably build a different system.
If you want to interface it with Bitcoin,  just have an exchange which accumulates transactions and post batches to Bitcoins at a speed that Bitcoin can cope with (seconds).

Generally: I agree with gavinandresen.

[mkrogh]

A different system. Why?
That different system would be a fork of bitcoin with 200 extra lines of code, or so, plus some verifiers which are just hash tables communicating with a simple http protocol.

The issue is this. The current bitcoin system has some freedom in what transaction a node works on, given a double spending attempt.
Right now, as I understand it, a node works on the first transaction it sees. Only after seeing a block with another transaction, will it change its mind.

Another possibility would be to flip a coin when a node has several colliding transactions.
Another possibility would be to ask a globally predefined node.
Another possibility would be to ask whoever the node feels like asking.

It doesn't matter; bitcoin works in any case. At some point a block will be generated with one of the transactions in all cases.

I want to use that freedom. The power of the proposal is that you have the ingoing transaction supply a name of a verifier.
There is nothing to lose by asking the proposed verifier, and there is a lot to win, namely ultrafast local trade.

By having the nodes put a transaction on hold, until either a timeout or a reply from the verifier, you can even have ultrafast local trade on Mars even though
most of the network is located on Earth. The general time loss by having the timeout is trivial, since it is similar to the latency in any case. On Earth it is within 200 milliseconds extra, say, in the worst case. The time delay is only large in exactly the cases where you want it. For instance, a Mars local coin, used in a vending machine on Earth. This is exactly the situation where suspicion is warranted.     

I hope someone understands what I am saying.

Cheers.

[lfm]

I started a thread about the lack of fast local double spending verification a week ago.  I was away for a week, and couldn't follow up on the thread. During this week, I became even more positive about bitcoin. Contrary to what I said last week,  I think that bitcoin could be a stand alone system; no issuer based systems are needed to coexist with bitcoin. Bitcoin could be the real thing! Kudos to all that have participated in it.  However, fast verification of the absence of double spending is still important. I think, I have a solution that more or less achieves it.

This all seems like overkill. If you need quick transactions you can always use something like mybitcoin.com where transfers between two members are instant. If you don't like mybitcoin then start your own.

If you cant agree with your customers on one to trust then your issues are such that you should, I think, just put up with the delays of the main bitcoin system. Any trust - verification system will impose delays I think. Consider when the store clerk has to phone VISA for a suspicious credit card.

[Come-from-Beyond]

So? Is the vending machine problem solved? If the answer is affirmative could someone tell where it's implemented in hardware and how it works, plz?