A proposal for a simple cryptocurrency

This is a look at an new way of creating a cryptocurrency as an alternative to blockchains.

tldr

A protocol can be designed for transferring payments across the internet, it requires some degree of prior trust of at least some peers. Incorporating transaction fees in the protocol reduces the amount of trust needed.

Introduction

To design it we go back to the basic requirements of a cryptocurrency.

The requirements are:

To be able to transfer money from one node (an instance of the software) to another
Resistant to nodes double-spending money or disappearing with debt
No single node can control the network

The system outlined below meets these requirements.

There is also a list of requirements for a cryptocurrency here:

All transactions should be made over the Internet
We do not want to have a central authority that will process transactions
Users should be anonymous and identified only by their virtual identity
A single user can have as many virtual identities as he or she likes
Value supply (new virtual bills) must be added in a controlled way

This system also meets these requirements.

Note the above only demand a way of transferring money from one instance of the software to another, not to store money like Bitcoin. Although any system that can transfer money can be a basis for a cryptocurrency if it is combined with a trusted entity that will convert between the cryptocurrency and a fiat one.

Algorithm Overview

To explore how this could work let’s look at how it money is transferred digitally without a cryptocurrency, using the conventional method of an app provided by a bank.

Supposing someone has a bank account and an app from the bank that lets them pay money. Now suppose the bank makes a payment to the customer – the amount owed by the bank (the account balance) is just increased in both the customer app and the banks database.

If the bank wanted proof that the payment was made then they could have the customer’s app send a digitally signed receipt back showing that the customer accepted the payment and the new amount owed.

Similarly if the customer makes a payment to the bank then the amount owed is increased. The bank could send a certificate back as proof of the new amount owed.

If all transactions between the two parties are accompanied by a signed receipt then the customer can prove the bank owes at least the amount it owes, and the bank can prove it owes no more than the amount it does.

For example:

A owes $10 to B

B sends a certificate stating $5 is being paid by A

A now owes $5 to B.

A can prove it owes no more than $5 by showing the list of certificates between the two nodes

We can show it like this:


A reduces debt to B  ==  A is paid by B
or 
A -> B  == B pays A

Now consider the case when there are two customers (A and C), both with the same bank (B) who want to make a payment from one to the other.

A payment from C to A means the amount the bank owes C is reduced and the amount the bank owes A is increased.

If all nodes want to prove the amount sent, then they all sign a certificate showing the total transaction

If A repudiates receiving the payment, C can show the signed certificate from A.

We can show the transaction like this:

A -> B -> C == A is paid by C

As well as reducing debt the payment can also be made by increasing debt in the opposite sense, for example increasing the amount C owes B.

This scheme can be extended with more nodes:


A -> B -> C -> D  == D pays A

Reducing the debts in a sequence of nodes is equivalent to a payment made from the end node to the beginning, in other words the payment completes a loop.

The fact that in trivial cases this system reduces to known good solutions (except with the addition of receipts) is evidence we are on the right track.

One apparent flaw in the above system is that each node has to owe at least one other node an amount to begin with.

This is solved with the idea of collateral – this is the amount a node trusts another node to owe it. The collateral is gained by the receiving node paying transaction fees to all the other nodes in a loop.

For instance in this example:

A -> B -> C -> D

A pays the other nodes A .. C a transaction fee of a percentage of the amount transferred. This payment is made by adding to the amount A owes the other nodes.

The amount by which each node trusts another node is the maximum amount the other node has owed in the past, in other words if A has owed $X in the past to B, then B will assume the total it can trust A with is $X, so if A has currently owes $Y to B, then B will trust A with up to an additional $(X-Y).

In this way the collateral each node has increases with the number of transactions it takes part in, giving an incentive for nodes to take part in transactions.

Bootstrapping

In addition to the mechanism of transaction fees above there is a need to create initial credits, otherwise when a node joins the network it could not take part in any transactions.

In practice this means a node has to trust another node with an initial debt.

This may against the spirit of a cryptocurrency – but note this has to be done with existing cryptocurrency schemes; when a user ‘buys’ coins through a broker, the user has to trust the broker with their fiat currency until the broker pays them the crypto-coins.

This trust is based on out-of-band means, namely the reputation of the broker. In our case the trust in encoded in the network rather than left implicit.

The credit is created by a user paying a trusted broker a sum and the broker sending a message to their node telling it that their node owes the users node that sum.

As described above the user will then trust the broker node up to that sum in the future.

Arguably this is less effective than other cryptocurrency systems because it assumes a continuing trust, while other systems only rely on a temporary out-of-band trust.

Against this you can balance the lower transaction costs and faster processing. So long as for some use cases this network is better than the existing banking system it may be worthwhile – sometimes the perfect is the enemy of the good.

Transaction fees

The main way credit is created is with transaction fees. As described above, these are paid by the receiver to each other node involved in the transaction (for instance 0.1% split over all nodes). This reflects that the trust each node deserves increases with the number of transactions it takes part in. The amount of debt other nodes trust it with is proportional to the number of transactions it has taken part in.

The transaction fees are a fixed percentage of the amount divided between all the nodes, so an attacker can’t benefit from cartelling.

Each node therefore keeps two values for each other node it interacts with: the amount currently owed/owing and the total amount it will trust the other with, which is the same as the maximum historically owed by that node.

So the additional amount node A will trust B to owe it is the amount B has previously paid to A. This stops node B from paying A with the intent to owe more and not pay it in the future, as if B intends to not pay in the future, there is no advantage in paying now.

To put it another way, the amount trusted is the high water mark of the amount owed.

The more money a node has in the network the easier it is to find a loop (as money owed to it by other nodes is how it receives payments). This means some transaction fees owed to the node should be kept as a ‘reserve’.

Apart from ‘trusted’ nodes that deposit fiat currency (as above) fraud is not possible, because the most amount any node can owe other nodes are the transaction fees owing. A node disappearing from the network or refusing to take part in transactions results in the user simply keeping their transaction fees.

A node has no incentive in refusing to take part in a transaction because any transaction only increases the amount owed it by other nodes.

As a Currency

The system as described is only a way of transferring a fiat currency, and relies on trusting a subset of nodes so arguably this is not really a cryptocurrency. However it meets the requirements above. It can be modified to allow for an arbitrary currency, provided only you have a broker that can convert between the currency and a fiat currency.

This system cannot be used to store currency like BitCoin, in fact the typical use case is as an alternative to bank transfer system SWIFT or systems like PayPal, but which allows anyone to set up a ‘bank’ provided they can prove they are trustworthy.

Routing

To complete a payment, the payer and payee nodes need to find a route through other nodes where all in the loop owe credit to the next one along. In addition, each needs to owe more than or equal to the amount to be transferred.

To do this, we can use a variant of Dijkstra’s algorithm.

Dijkstra’s algorithm assumes you know the whole network. However we need to do it in parallel and with each node only knowing those it owes credit to.

This can be done by the paying node creating a list of nodes that it owes (or it can pay), and asking other nodes for the list of nodes they can pay and updating the list accordingly. Repeating until it finds the payee node. This is effectively running Dijkstra’s algorithm from the paying node.

There are other algorithms that would work and optimisations that can be made that make better use of nodes working in parallel, however this shows it is possible.

Routing Performance

Dijkstra’s algorithm has an average case performance of O(e +v.log(v)) where e=the number of edges and v=number of nodes. If users make similar numbers of transactions, we can assume e is proportional to v . This gives us the traffic per transaction per node of O(v.log(v)). However if the distance between payee and payer nodes is on average a constant (as might be the case) then with optimisations it reduces to an average of O(1).

Certificates

When a transaction is made a receipt of the total transaction is sent round all the nodes in the loop, and signed by each. A receipt is just a hash of the transaction signed with the nodes key.

A node A can generate a proof that another node B owes it a certain amount by listing the receipts of payments A has made to B (signed by B and sent to A as part of the transaction). B may repudiate that by showing receipts of payments made by B to A.

This provides non-deniability of a transaction.

For this to work the receiver should be the first to sign, then the recipet is sent round the loop to the payer.

This proof of debt can be used when trust is enforced by an out-of-band mechanism.

Enhancements

Another way to increase debt between nodes would be to allow software agents to run in return for payments, or allow use of other resources to build up credit.

Next steps

The next step is to develop code to run the nodes, and embed in a test simulator to mimic real world use and measure metrics.

Alternatives

This system is similar to xCurrent, used by the Ripple network, with the addition of transaction fees.

Limitations

As stated above you cannot use this network for storing money or speculating, like bitcoin.

There is a need for each node to trust at least one node initially, similarly to trusting a broker to buy a cryptocurrency.