A fast, low-cost payment network for small Bitcoin transactions

1. Introduction

Bitcoin is a completely decentralized internet currency, which offers certain advantages over traditional government-issued currencies. However, a complete transition of an entire economy to Bitcoin-based payments can be problematic:

In a typical economy, there are huge numbers of small transactions. If all transactions end up in the block chain, the amount of data in the block chain will become very large. This will make it costly for Bitcoin nodes to maintain full copies of the block chain. Miners will require transaction fees to cover these costs, especially when the number of generated coins per block decreases to zero. This will make Bitcoin relatively expensive, and unsuitable for small transactions.
For many transactions, especially the smaller transactions, confirmation is required, e.g. in supermarkets or vending machines. Bitcoin can only reliably confirm transactions in a 10 minute to 1 hour time period, which is much too long for typical POS transactions.

This document describes a method for addressing these issues, by providing a payment and confirmation mechanism outside the main Bitcoin network. The approach in this document is very similar to the Ripple project, but there are some differences as well:

Instead of friend-to-friend borrowing, the concept described here uses a shared Bitcoin wallet. This is intended to reduce the risk that the bankruptcy of one person causes the bankruptcy of other people. As it is not possible to find out how many debts a person has in the network (possibly by using a large number of accounts), financial regulation is impossible, and other mechanisms must be in place to prevent large-scale economic collapse. The use of a shared wallet instead of debts is such a mechanism.
The concept described here uses Bitcoin as the only currency. It might be possible that in the future new features are added, such as gateways to the Ripple network, or some method for reliably using different currencies for the transactions and the shared wallets.

2. Concepts

User

A person or organization who uses the payment network.

Account

A node in the payment network, capable of making, transferring and receiving payments. A user is the owner of one or more accounts.

Server

A computer system that operates zero or more accounts. Every account is operated by exactly one server (which may optionally consist of several hardware/software components). Operating an account consists of performing all account-related actions on behalf of the owner of the account.

Service provider

A person or organization who runs one or more servers for operating the accounts of other persons or organizations. The owners of these accounts have to trust the service provider for correct operation of these accounts.

Account address

An account address is a Bitcoin address that is associated with an account.

As an account may need to create signatures that are consistent with its addresses, the private keys that correspond to the addresses of an account need to be accessible for the server that operates the account.

An account can have multiple addresses associated with it, but an address can only be associated with a single account. If multiple servers claim to host an account with a certain address, and manage to prove it by providing correct signatures, it is recommended for the owner of the account to migrate to another address, which is hosted on a single server.

An account address can be used for communicating with an account, and for making payments to an account.

Direct connection

A direct communication channel between two accounts. A server can communicate directly with the server that operates an account, either by querying other servers in the network for the network address of that server (e.g. IP address, or a TOR hidden service name), or by some arbitrary other method of opening a communication channel.

Direct connections are encrypted, so that only the servers that operate the accounts have access to the data being exchanged.

Indirect connection

An indirect communication channel between two accounts. A server can communicate indirectly with the server that operates an account by finding another server in the network which acts as a proxy between the two servers. This is intended as a fall-back method for when none of the network addresses of the account-holding server is of a type supported by the contact-seeking server, so that a direct connection is not possible.

Like direct connections, indirect connections are also encrypted. The proxy server has no access to the plaintext messages.

Bitcoin transaction

A traditional Bitcoin transaction, which ends up in the Bitcoin block chain. Bitcoin transactions are used every now and then in the fast payment network to compensate long-term payment inbalances, but they can also be used as a fall-back method if a payment can not be done on the fast payment network (e.g. because an account address is not known in the fast payment network).

Network transaction

A transaction between two accounts, which takes place over the fast payment network. A network transaction contains the following items:

the public key of the receiving account
the public keys of all intermediate accounts and the paying account
the value (in BTC) to be transferred to the receiving account
arbitrary meta-data, typically used to describe additional agreements between payer and receiver. This can for instance be a receipt. This meta-data can optionally be encrypted.

A network transaction is only considered to be committed when it is signed by all involved accounts. These signatures are checked against the public keys listed in the transaction itself.

Personal wallet

A collection of Bitcoins that are owned by exactly one user. The user who owns the bitcoins has the private keys which enable the user to do payments from the personal wallet.

Shared wallet

A collection of Bitcoins that are shared between two users. Bitcoins are added to the shared wallet with an output script that requires two signatures for spending the bitcoins. Each user has exactly one of the two private keys necessary for spending the bitcoins, so spending the coins is only possible if both users agree.

Part

The value in BTC that may be withdrawn from a shared wallet by one of its users. The parts of both users are established by mutual agreement between both users. When there is full agreement between both users, the sum of the parts equals the total value stored in the shared wallet.

Part specification

A data structure which describes the parts of a shared wallet. A part specification is only considered valid if it is the most recent one that is signed by both users. A part specification contains the following items:

A timestamp, which can be used to find the most recent specification that is signed by both users
The part of the first user
The part of the second user
A list, where each item consists of the following:
- a Bitcoin transaction
- the change that must be applied to the part of the first user, if the Bitcoin transaction is accepted into the Bitcoin block chain
- the change that must be applied to the part of the second user, if the Bitcoin transaction is accepted into the Bitcoin block chain
- A block count that, when reached by the block chain while the transaction is not yet accepted, indicates that this item must be removed from the part specification without applying the part changes
A list, where each item consists of the following:
- a network transaction
- the change that must be applied to the part of the first user, if the network transaction is signed by all accounts involved in the transaction
- the change that must be applied to the part of the second user, if the Bitcoin transaction is signed by all accounts involved in the transaction
- A timestamp which, when reached, indicates that this item must be removed from the part specification without applying the part changes

Trust connection

A direct connection between two accounts, which allows transfer of payments. A trust connection is associated with the following items:

a shared wallet, which is shared between the owners of the two accounts
the public/private key pairs used by the two users, which are used for
- signing part specifications
- encrypting all messages exchanged between the accounts
- withdrawing bitcoins from the shared wallet
Each user only sends his public key to the other user. The private key is stored on the server of the corresponding account, and should not be accessible for the other user.
a part specification for the shared wallet, which is regularly updated when transactions are performed

Trust route

An indirect connection between two accounts, which allows transfer of a single payment. A trust route is established over a chain of trust connections. A trust route has a limited lifetime, and it is terminated either when a network transaction is performed over the trust route, or when a time-out happens. A trust route has a payment value associated with it, and it is directional: payment can only happen in one direction.

Route opening

The process by which a trust route is established. One of the end points is the initiator of the trust route; the other end point needs to have an account address that is listed in routing tables through the network. Route opening requests are sent between accounts over trust connections, starting at the initiator, until they reach the other end point of the trust route. At accounts with more than two trust connections, routing tables are used to choose the trust connection which is most likely to result in establishing the route.

Network payment

A payment which involves a network transaction instead of a Bitcoin transaction. A network payment is performed in the following way:

A connection (either direct or indirect) is established between the payer and the receiver. They agree on the value to be paid, and the meta-data of the network transaction.
A trust route is opened between between the payer and the receiver. It seems to make most sense to let the payer initiate the trust route, but there is no reason why the receiver wouldn't be the one to initiate the route. The trust route and the connection together form a circle over which the payment is performed.
The receiver creates a new public/private key pair and sends the public key towards his nearest neighbor in the trust route. Every account in the trust route creates a new public/private key pair, and sends his own public key together with the received keys to the next account in the trust route. In the end, the payer receives all public keys.
The payer creates the network transaction for the payment, which includes all public keys, and sends it over the connection to the receiver.
The receiver sends the transaction back to the payer, over the trust route, so that all involved accounts have the transaction. The accounts add the transaction to the part specifications of the trust connections that form the trust route. Each node, including the receiver but not the payer, also sends a signature together with the transaction. Each signature signs (a hash of) the transaction, and corresponds with one of the public keys in the transaction.
The payer receives the transaction from the trust route, together with all signatures except his own signature. The payer adds his own signature, and sends all signatures over the connection to the receiver.
The signatures are sent over the trust route from the receiver back to the payer. At each step, the signatures act as proof that the transaction is committed, and the part specifications are adjusted accordingly. Finally, the payer receives all signatures back, and the transaction is fully committed.

Transaction unrolling

The process by which a network transaction which is not signed by all parties is removed from the part specifications in which it is mentioned.

When one of the accounts in the trust route discovers that a time-out has occurred before the account received all signatures for the transaction, then the account will contact the neighboring account in the trust route with the request to remove the transaction from the part specification of their trust connection. After the time-out, the neighboring account may only refuse this by providing all signatures of the transaction.