A proposal for fast POS transactions with Bitcoin

[cjp]

This diagram shows some additions I want to make to the Bitcoin architecture. An explanation follows below the image.


Normal Bitcoin transactions follow the black arrows:
2. The buyer instructs his PC to publish the transaction on the Bitcoin
network. For this, the PC uses the seller address and the amount (both
transferred in an non-standardized way outside the Bitcoin network),
and the buyer's private keys, which are stored on the buyer's device.
6. Miners pick up unverified transactions to put them in new blocks.
7. Approximately 10 minutes later, a miner manages to construct a new
block with the transaction in it, and adds it to the block chain.
8/9. Both the buyer and seller can follow the verification process by
monitoring the block chain. After approximately one hour, the
transaction is buried under 6 blocks in the chain, which is the moment
when most Bitcoin users consider the transaction verified.

Depending on the required verification confidence, the whole process
can take up to an hour. This is definitely too long for application
in POS (Point Of Sale) transactions, where transactions must not
take more than a few seconds.

The 'classical' approach would be to accept a lower quality of
verification. For POS transactions, even waiting for a single block
would take too much time, so the only classical verification method
would be to monitor the pool of unverified transactions, to check
whether there is any double-spending. This method is not guaranteed
to work, and especially in a very large Bitcoin network, where
it takes more than a few seconds for transactions to reach all network
nodes, this creates a risk for the seller.

For fast, reliable and convenient POS transactions, I propose an
addition to the Bitcoin architecture, which consists of the red arrows.
The figure assumes that the buyer uses a smart phone or some other
portable, programmable device. The device needs a connection with the
Bitcoin network: this can either be an independent connection (e.g.
using mobile Internet), or it can be tunneled through the Internet
connection of the seller.

The first addition is arrow 1. I propose to make one or a small
number of standardized ways to transfer transaction information
(such as seller Bitcoin address, and the amount) between the POS
terminal and the buyer device. NFC or QR codes would be suitable
media for this.

The buyer confirms the transaction by publishing the transaction in
the Bitcoin network (2). There, the transaction follows the normal
"slow" verification route (6/7/8/9).

The second addition allows to speed up the verification process.
In addition to publishing the transaction (2), the buyer also signs
the transaction, and (3) sends it to a node in the "Fast Verification
Network", which will be described later. Nodes in the Fast
Verification Network quickly check the transaction against the
existing transactions (4), and if it is OK, it is signed and
transferred further through the network, until it reaches the POS
terminal (5). The signatures received with the transaction through
the Fast Verification Network give the seller an initial verification
within a few seconds. Final verification reaches buyer and seller in
the classical way (8, 9).

The reason why the signature received through (5) can act as
verification is that nodes in the Fast Verification Network do not
connect to each other randomly: instead, a link is only made when
the two nodes trust each other. If a node signs a transaction and
sends it to a neighbor, and later the transaction turns out to be
a rejected double-spend, the node is obliged to pay the corresponding
amount of bitcoins to the same neighbor. This means that, even if
the payment turns out to be a double-spend, the seller can still
receive his payment by requesting it from his nearest neighbor in the
Fast Verification Network. As long as all nodes are honest towards
their direct neighbors, this means that eventually the buyer will
have to do the payment to his access point in the Fast Verification
Network.

Normally, when a node sends a signed transaction to another node,
the receiving node has to trust the sending node. Trust can be
reversed if the sending node sends a certain amount of bitcoins to
the receiving node PRIOR to establishing the connection. If the
receiving node has no trust at all in the sending node, this prior
payment creates a maximum for the value of transactions that can be
sent simultaneously over the link.

Trust can be obtained in a number of different ways, e.g. knowledge of
the real-world identity of a neighboring node, or an online reputation
rating system.

So, what do you think? Is this a useful addition to the Bitcoin
infrastructure? Do you see any issues, or possible improvements?

[1714065255]

1714065255

[1714065255]

1714065255

[1714065255]

1714065255

[1714065255]

1714065255

[riush]

This is pretty much how I imagine established banks, which already have a way to manage trust towards one another, will be using bitcoin one day

As long as all nodes are honest

Trust can be obtained in a number of different ways, e.g. knowledge of
the real-world identity of a neighboring node, or an online reputation
rating system.

IMHO this is the real issue that needs to be solved in a distributed and decentralized way.

Edit: Maybe Open Transactions can help here, unfortunately I haven't had the time to look into that in more detail...

[cjp]

As long as all nodes are honest

Trust can be obtained in a number of different ways, e.g. knowledge of
the real-world identity of a neighboring node, or an online reputation
rating system.

IMHO this is the real issue that needs to be solved in a distributed and decentralized way.

If one of the nodes is not honest, that does not make the system completely useless. Only the node who decided to trust the dishonest node will lose money; the other nodes will not be at risk. I think the system will generally be self-correcting: nodes will warn each other for dishonest parties, and close down links or make links to unreliable nodes more expensive.

What would a routing protocol for this network look like? I suppose it will be something like TCP/IP, with some discovery system to find out which nodes are on which side of the network...

[TierNolan]

IMHO this is the real issue that needs to be solved in a distributed and decentralized way.

Edit: Maybe Open Transactions can help here, unfortunately I haven't had the time to look into that in more detail...

Trust could be established by paying in advance or something.

Also, all nodes don't actually need to be honest.  The requirement is that the nodes just need to honour their commitments.

In the verification process, there needs to be a trust link between buyer and the seller.  The bitcoin network is used as a clearing system rather than a transaction system.

I assume that process is something like

A -10-> B -50-> C -20-> D

The number in the arrow is how many bitcoins of trust exist.

A trusts B for up to 10 bitcoins.

If D wants to send A one bitcoin, a routing system is used to find a chain that has at least that much trust (so detects the above path).

D says to C "I will pay you 1 BTC unless the transaction is accepted within 90 mins".  C says the same to B and then B says the same to A.

A now knows that he can accept the transaction.  Trust has been stressed by 1 BTC along the chain, so now it is

A -9-> B -49-> C -19-> D

If C decides to not pay B, then B will still pay A, since he promised.  B would also probably remove C from his trust list.

When the transaction gets 6 confirms, then promise ends and the trust chain goes back to full strength.

A -10-> B -50-> C -20-> D

These trust links could be anyone.  Someone could list a few of their close friends as trusted for up to say BTC 2-3.

The client would automatically update the trust system and pay promised amounts through the trust system.  Leaving your client connected to the internet would get you fees, if people send their money though your trust links.

To stiff your friends would require that you modify the default client.

[JoelKatz]

IMHO this is the real issue that needs to be solved in a distributed and decentralized way.

This does solve this in a distributed and decentralized way. Each node only has to trust those nodes it has a direct relationship with. The system of trust as a whole is distributed and decentralized. You can only be ripped of by someone you chose to trust.

[gmaxwell]

So, what do you think? Is this a useful addition to the Bitcoin
infrastructure? Do you see any issues, or possible improvements?

Congrats, you've invented Ripple: http://ripple-project.org/(2013 Edit: The ripple name was acquired and the new ripple is nothing like the old ripple. Any comments I made about ripple prior to Feb 2013 apply to the old system.)

I hadn't considered using it this way. I think thats very cool

But what it doesn't do is reduce the block-chain volume of transactions for small payments.  In a world where bitcoin is being used for POS that kind of transaction hiding is also valuable. Bitcoin's security comes from the fact that everyone sees everything.  That kind of security is justified for the whole wealth of the world— not so justified for soda-pop transactions.   We can usually trust centralized institutions enough to handle our soda pop purchases without funny business.

So, really I think you've added something else useful to the ecosystem of ways to address fast transactions:

(1) Wait, don't do things fast.
(2) Take a risk
(3) Use a third party insurance service who uses good network visibility and miner relationships to gauge risk and have them approve it.
(4) Use escrow transactions to bind funds to a third party approver who is trusted not to sign double spends.
(5) Use a classic centralized processor that you keep deposits with. (this will be essential early on as we still need to interface with classic payment networks). Also has the huge advantage of hiding its internal transactions from bitcoin, all the network sees is periodic settlements.
(6) Your ripple(see edit above)-esq solution

I expect that all of these things will exist in various places, at various times, and in various mixtures. (In some ways, I guess your solution is a distributed version of (3)) Diversity is a good thing.

From recent discussion on bitcoin-dev:
(7) When a node sees a second transaction trying to spend an input which is already used by an in-memory-pool transaction (attempted double spend), it generates a double-spend-warning message per affected input which identifies the first two observed transactions using this input.  The warning is flooded (and validated by each node), and can be used to reduce the risk in option (2) above.

[JoelKatz]

But what it doesn't do is reduce the block-chain volume of transactions for small payments.  In a world where bitcoin is being used for POS that kind of transaction hiding is also valuable. Bitcoin's security comes from the fact that everyone sees everything.  That kind of security is justified for the whole wealth of the world— not so justified for soda-pop transactions.   We can usually trust centralized institutions enough to handle our soda pop purchases without funny business.

It could be adjusted to reduce transaction volume. If the nodes settle up with each other, there's no need to perform the actual transaction. Ripple could use bitcoin to settle up, settling only when rippling failed or asymmetries built up that exceeded the trust levels.

[TierNolan]

Ripple could use bitcoin to settle up, settling only when rippling failed or asymmetries built up that exceeded the trust levels.

Exactly, if you have a +/- 2 BTC trust link with someone, you could use the main network to move the account back to 0, only if it exceeds +/- 1.5 BTC.

If the flow through the link it reasonably balanced, you mightn't have to settle up very often at all.

In fact, by adjusting the fees you could bias the flow back to zero without any need to settle.

However, with bitcoin to settle the account cheaply, there isn't much point in trying to keep it balanced, unless transaction fees earned are less than the bitcoin transaction fees to balance the link.

It looks like there was a suggestion in February on both this forum and the Ripply google group that the 2 systems work well together, but doesn't look like much happened.

Ripple doesn't seem to do all the transactions at once.  You effectively give your friends IOUs which they can trade, even if you are offline.

[gmaxwell]

Ripple could use bitcoin to settle up, settling only when rippling failed or asymmetries built up that exceeded the trust levels.

It looks like there was a suggestion in February on both this forum and the Ripply google group that the 2 systems work well together, but doesn't look like much happened.

Ripple doesn't seem to do all the transactions at once.  You effectively give your friends IOUs which they can trade, even if you are offline.

Hm. Yea, I've been pretty skeptical of ripple in general, but backed with bitcoin and automatic true-ups (why not settle frequently?) that seems like a pretty compelling combination...

I liked the proposal where here where the secured transaction is exposed to the fast network rather than just using the blind IOUs of ripple(Edit 2013: Ripple's name was sold to a new, largely unrelated system).  Trust for someone to not double spend funds that they appear to have is quite different from general credit. Though it could be done in some other way where the unspent bitcoin balance secures the ripple activity, without actually being turned into a bitcoin transaction (still allowing transaction hiding to reduce the load on bitcoin). But there might be interesting privacy challenges with that.

Now mix in something namecoinish to have persistent bound identities to hang trust on...

[jav]

Hm. Yea, I've been pretty skeptical of ripple in general, but backed with bitcoin and automatic true-ups (why not settle frequently?) that seems like a pretty compelling combination...

I agree. I think that a Bitcoin-specific Ripple system has lots of promise. I haven't really tried Ripple much, but I always worry that maximum credit level might quickly be reached on some routes and then the system doesn't work until a manual debt settle. For example a popular online store will probably mostly have flowing cash towards them and quickly reaching the credit limit with the nodes that trust the store.

Since Ripple supports arbitrary currencies it can't really do automatic debt settlement. But if you would limit it to Bitcoin you could occasionally do automatic Bitcoin payments.

Unfortunately the Ripple project doesn't have all that much software written. They only have centralized servers (so all the trust connections are maintained on a single server) which is nice to play around with, but ultimately it should be decentralized. They are working on a decentralized version, but its mostly in the design phase and I'm not holding my breath, because it's a very hard problem. Since you need to be able to find trust paths connecting different people that might be registered on different servers etc.

An idea I was toying around with: Maybe go for a simple prototype first where routes are manually. So you would have to tell the system specifically that you want to route your payment through alice@server1 -> bob@server1 -> claire@server2 (assuming there is trust between alice<->bob and bob<->claire). The system would keep track of the credit limits alice<->bob and bob<->claire and would occasionally settle the debt with a standard Bitcoin payment.

[TierNolan]

Hm. Yea, I've been pretty skeptical of ripple in general, but backed with bitcoin and automatic true-ups (why not settle frequently?) that seems like a pretty compelling combination...

Settling requires the payment of the bitcoin transaction fee.

At worst, it would require a transaction for every link in the chain.  This could cause an increase in the load on the bitcoin network.

Sending the money to a distant node could be used to balance all links along the way.  There could be a problem with trust for that though.  

If A owes money to B, who owes to C, who owes to D, then A just needs to send money to D.

A would then own an IOU from D, which isn't someone he actually trusts.  

The IOU would need to say "D owes the bearer BTC 1, on condition that transaction <hash> is incorporated into the bitcoin chain before block number <number>".

A could get C to swap the IOU with one that says "C owes ...." and then B to swap that one for "B owes ...." and finally cash that one with B directly.

Once B has given the IOU, A would then submit the payment to the bitcoin network.  If someone along the chain refuses to transfer the IOU, then A just doesn't submit the transaction and it expires when the bitcoin chain hits that block number + 6.

How does Ripple normally handle double spending of IOUs?  If the first person to cash in the IOU gets it, then offline verification of IOUs is impossible.

I liked the proposal where here where the secured transaction is exposed to the fast network rather than just using the blind IOUs of ripple.  Trust for someone to not double spend funds that they appear to have is quite different from general credit.

When you sign a transaction, you are at risk that the person will somehow double spend.  There does need to be a link of trust.

If miners published the blocks that they are currently working on, then you could verify that 90%+ of the mining power is committed to including the transaction.  Miners may not want to be spammed by users asking about transactions, but aggregators should be able to pay to get their current transaction list.  They could then operate the fast network.

If the transaction is covered by 90% of the miners, then it is likely to be accepted.

Though it could be done in some other way where the unspent bitcoin balance secures the ripple activity, without actually being turned into a bitcoin transaction (still allowing transaction hiding to reduce the load on bitcoin). But there might be interesting privacy challenges with that.

If Ripple switched to issuing Chaum blind signatures, then the IOUs would be more difficult to trace.

Since bitcoin is inherently online, is the Chaum system overkill?  The whole idea was that it would cover double spending in offline networks.

[TierNolan]

I agree. I think that a Bitcoin-specific Ripple system has lots of promise. I haven't really tried Ripple much, but I always worry that maximum credit level might quickly be reached on some routes and then the system doesn't work until a manual debt settle. For example a popular online store will probably mostly have flowing cash towards them and quickly reaching the credit limit with the nodes that trust the store.

Exactly.  The problem is that for a system like Paypal most nodes are either sources or sinks (buyers or sellers).  This means that you need an out of channel payment system for settling, but then why not just use that directly.

Ripple + bitcoin gets fast transactions from ripple with bitcoin acting as the clearing system.

But if you would limit it to Bitcoin you could occasionally do automatic Bitcoin payments.

As long as there are people willing to exchange bitcoins for cash, you could still use the bitcoin system for handling the clearing system, as long as the two ends of the transaction have links to a local exchange.

An idea I was toying around with: Maybe go for a simple prototype first where routes are manually. So you would have to tell the system specifically that you want to route your payment through alice@server1 -> bob@server1 -> claire@server2 (assuming there is trust between alice<->bob and bob<->claire). The system would keep track of the credit limits alice<->bob and bob<->claire and would occasionally settle the debt with a standard Bitcoin payment.

I think manual routing is worse than having a central server do it (unless the central server goes offline).

Routing could work like IP routing.  However, that means that each routing node needs to store a table entry for every other node.  As an added complication, the size of the link needs to be taken into account.

For example, if there were two paths from A to B, then it isn't clear which one you should add to the routing table.

A -10-> B
A -100-> C -100-> B

If A wants to send 1 BTC, then it can send via the first link, but for more than 10, it has to use the second link.

The routing tables would adjust much more often, as with every transaction the size of the link changes.

The routing system could be hierarchical.  A number of nodes which have good connections to each other could form a group and then top level routing would contain routes between groups rather than routes between individual nodes.  This would work like the network/sub-net system on the internet.

[JoelKatz]

How does Ripple normally handle double spending of IOUs?  If the first person to cash in the IOU gets it, then offline verification of IOUs is impossible.

These issues not that difficult to solve. Everybody who takes IOUs keeps track of what IOUs they have paid. Every payment on an IOU is signed by the recipient.

Say I trust you to owe me up to 20 bitcoins and you currently owe me 10 bitcoins. You present an IOU. I pay you 10 bitcoins. You send me a receipt. We now have a zero balance.

If you present me the IOU again, I can present to you the receipt proving I paid it.

If I pay you and you refuse to provide me an IOU, then you are breaching the trust I extended to you. Non-receipting is treated the same as non-payment, it's a breach.

To avoid having to track IOUs and receipts forever, two nodes could mutually sign a balance certificate. If you claim I owe you 10 BTC from a receipt dated last year, I can present a signed certificate of zero balance from last week to prove it must have been settled. Refusing to sign balance certificates could also be considered a breach of trust.

Offline verification of IOUs is not needed. This is fundamentally an online processing system where each node decides to extend trust. If you're not online, you can't do anything until you are. If you stay offline and refuse to redeem IOUs, you are again breaching trust.

[jav]

An idea I was toying around with: Maybe go for a simple prototype first where routes are manually. So you would have to tell the system specifically that you want to route your payment through alice@server1 -> bob@server1 -> claire@server2 (assuming there is trust between alice<->bob and bob<->claire). The system would keep track of the credit limits alice<->bob and bob<->claire and would occasionally settle the debt with a standard Bitcoin payment.

I think manual routing is worse than having a central server do it (unless the central server goes offline).

When you say central server, are you thinking of a server that does only the routing or also the automatic Bitcoin debt settlement? If it's the latter, that already exists: MyBitcoin.com, with the added benefit, that no trust connections are necessary. Everybody can pay everybody else on MyBitcoin.com instantaneously as long as they have an account there with enough Bitcoins.

If the central server only does the routing and the automatic debt settlement is done by the individual nodes then that can be seen as an addon to my proposal. Which seems indeed like a good idea: Have a decentralized system that only supports manual routes and then have a well-known directory server where everybody publishes their trust connections and can query for routes.

At some later stage that directory server can then be replaced by a mechanism that figures out the routes without requiring a central server.

On using Internet-like routing: That is a good suggestion! Although I wonder about privacy and whether it would be possible to do all that and still allow participants to not reveal all the people they trust. That might be too much to ask for, giving the complexity of the problem already, but maybe some of the other requirements could be eased (like not requiring the algorithm to find an optimal path, but use some kind of heuristic to have a good chance of finding a decent path). To me it seems like there are a lot of tradeoffs to consider.

On that note, I wonder how much of this discussion has already happened within the Ripple community. I haven't gone through their archives in much detail, but for those who are interested, I think much of the discussion regarding Ripple systems is happening over here: https://groups.google.com/group/rippleusers .

[TierNolan]

I think manual routing is worse than having a central server do it (unless the central server goes offline).

When you say central server, are you thinking of a server that does only the routing or also the automatic Bitcoin debt settlement?

I was thinking of a server that sets up the routing instead of having to manually enter the routes.

A distributed routing system is preferred to manual routing or a central server though.

Have a decentralized system that only supports manual routes and then have a well-known directory server where everybody publishes their trust connections and can query for routes.

Sounds reasonable.

On using Internet-like routing: That is a good suggestion!

Maybe solving a hash gets you the right to create a group and therefore a link in the routing tables.

These could expire.  All members of the group would need to do some processing to keep the group's ID code valid.

With a hierarchical system, each member would support the group and the group that the group is a sub-group of etc.

Although I wonder about privacy and whether it would be possible to do all that and still allow participants to not reveal all the people they trust. That might be too much to ask for, giving the complexity of the problem already, but maybe some of the other requirements could be eased (like not requiring the algorithm to find an optimal path, but use some kind of heuristic to have a good chance of finding a decent path). To me it seems like there are a lot of tradeoffs to consider.

If the trust links are created based on RL friendships, then it doesn't seem that easy to keep things secret.

You could create trust links with random people if you are willing to risk it.  This would allow the creation of an anonymous node.

For example, if I send you 0.1 BTC and ask you to send it back to me, then if you do, I know you are trustworthy for at least that much. 

If there are reasonable fees for providing trust links, then it might even be worth does it at random.  Effectively, if there are a shortage of links, then it is worth spamming random nodes to create links.

Broadcasting a promise to pay (and incorporating it in the chain) would allow nodes to build up general trust levels.

On that note, I wonder how much of this discussion has already happened within the Ripple community. I haven't gone through their archives in much detail, but for those who are interested, I think much of the discussion regarding Ripple systems is happening over here: https://groups.google.com/group/rippleusers .

I had a quick look and some there think bitcoins are a bubble .

[rfugger]

Hi.  I'm the founder of the Ripple project.  Nice to see Ripple being discussed as a real-time transaction overlay for Bitcoin.  I think the two are complementary -- Bitcoin is decentralized virtual gold, and Ripple is decentralized virtual banking. 

I'm working on a generic Ripple server to support the next version of Ripplepay.com that I intend to release as open source.  It won't be distributed at first, but it would work as a central server to query for routes (and also to process transactions atomically, which is probably actually a harder problem than routing in a distributed setup).  My design for a distributed Ripple protocol is here:

http://ripple-project.org/Protocol/Protocol05

Comments and suggestions are welcome.  If anyone is interested in helping with this, or just interested in implementing some kind of Bitcoin banking on top of it, let me know.

Thanks,
Ryan

[TierNolan]

and also to process transactions atomically, which is probably actually a harder problem than routing in a distributed setup

Yeah, I was wondering how you were planning to handle that.  A node could end up holding an IOU to the last link and then suddenly the transaction is canceled and he has an IOU from someone he doesn't trust.

Making the IOUs conditional on a transaction occurring in the bitcoin block-chain would resolve that, but would have a 1 hour or so delay before a transaction can be confirmed expired.

[rfugger]

Yeah, I was wondering how you were planning to handle that.  A node could end up holding an IOU to the last link and then suddenly the transaction is canceled and he has an IOU from someone he doesn't trust.

The mechanism is that each node first promises the one ahead that it will pass an IOU in exchange for a commit token signed by a certain key, determined by the last node (the payment recipient).  Once all the promises are made, the recipient generates a commit token and passes it back to the previous node in exchange for an IOU, and so on back to the first node (the payer).

This is enough if all the nodes remain online and they are all well-behaved, but in case not, I've proposed a system of commit registries as an extension that should be fairly robust against node failure and cheating:

https://groups.google.com/forum/#!msg/rippleusers/Ruy_QIb0AAY/fUF5bGNJWXkJ

Ryan

[TierNolan]

This is enough if all the nodes remain online and they are all well-behaved, but in case not, I've proposed a system of commit registries as an extension that should be fairly robust against node failure and cheating:

https://groups.google.com/forum/#!msg/rippleusers/Ruy_QIb0AAY/fUF5bGNJWXkJ

I think that is similar to the suggestion to use the bitcoin chain itself as register.

You promise to pay subject to the bitcoin payment actually happening before a certain block number.  The bitcoin block chain can also be used to add arbitrary messages into the block chain, though this is discouraged.  These are effectively permanently timestamped as part of the bitcoin transfer system.

That means that each ripple transaction has to be matched by a bitcoin transaction.

For small payments, it should be possible to only reset the chain every few ripple transactions.  This prevents the bitcoin chain being used to certify that the main transaction took place.

[TierNolan]

http://ripple-project.org/Protocol/Protocol05

You should add a packet length field to your message system.

This allows older clients to ignore (or forward) any new packet types.  It also allows clients to use non-standard packets.