Here we search for the holy grail of micropayments: a decentralized transaction system that can scale to the volume of the internet itself; the promised land where transactions are plentiful as UDP packets, fast as ping, and as cheap as bandwidth itself.
Motivation
Bitcoin is a working example of a decentralized transaction network. It’s Proof of Work scheme has certainly proved itself to work in the field, but at the cost of zero parallel scaling: transactions are redundantly replicated across all full nodes, so the maximum performance of the system is nearly equivalent to the maximum performance of a single node. The nascent network still has room to scale, but eventually will run into the bandwidth and storage limitations of the acceptable minimum requirements for a full bitcoin node. The interesting recent proposals for performance provide a constant multiplier, they don’t change the asymptotic scaling which is and will be O(N).
There are many interesting applications of distributed transaction networks that have vastly higher performance requirements. The financial markets of the world such as NASDAQ, BATS and kin are a good starting point, but really just the tip of the iceberg. Sans any and all performance limitations, what kind of applications could a vastly scalable micro-transaction network enable?
For inspiration we can look to the future vision of an impending AI-singularity: an explosion in computation and intelligence leading to a world quickly populated by an endless sea of software agents ranging from the smallest dedicated trading bots on up to the true superintelligences: vastened minds thinking orders of magnitude faster and deeper than mere biological brains. The key constraint on the intelligence explosion is the locality of physics as expressed by the speed of light. The faster an agent thinks, the slower the outside world becomes. Latency and bandwidth become vastly more restrictive. The future is perhaps dominated by localized pocket civilizations around the size of a city block: a vast expansion of virtual inner space. A globally synchronous protocol like Bitcoin has little place in this future.
Even before the full intelligence explosion begins in earnest, a scalable micropayment network could enable an Agoric Computing revolution. Many real world problems of interest can be formalized as multi-agent / multi-utility function coordination problems that are well addressed by market systems.
Imagine a smart traffic marketplace where automated vehicles rent out their time, road lane usage is rented, user agents bid for service, and various options and derivatives are used to predict and hedge traffic events.
Open markets could potentially solve a key problem with the health industry: the misalignment of financial incentives. Consumers have an interest in maximizing quality and quantity of lifespan. Medical companies currently have a greater financial interest in recurring product revenue via indefinite medication rather than one-off cures. Health/Life insurance could be revolutionized by creating a marketplace for insurance contracts and associated derivatives such that health research innovators could profit from the true economic value of actually curing or even preventing diseases.
A marketplace for grid computational resources itself could enable entire new classes of massive dynamic software ( indeed we are already seeing the early stages of this with nascent cloud computing markets such as Amazon’s EC2).
Lofty Goals
The ideal transaction network would have the following qualities:
- throughput: peak aggregate transaction rate approaching the theoretical maximum: transaction message size / total network bandwidth (zero duplication overhead)
- latency: most transactions add little additional latency beyond the minimum packet traversal from sender to destination
- security of ownership: private control of assets is near-guaranteed
- uniqueness of assets should be cheaply verifiable and counterfeit-resistant
- robustness: high systemic existential security: large-scale redundancy via P2P decentralization
Bitcoin scores well in terms of goals 3,4,5 at the expense of performance goals 1 and 2. The aggregate bandwidth cost of a single transaction in the bitcoin network is roughly B = O(N*C), where N is the number of nodes, and C the bandwidth cost of a single transaction packet. Thus the total transaction throughput T scales as T = O(N*B / N*C): which B is the per-node bandwidth, and thus is just a constant: T = O(B/C). Ideally we want the average transaction to visit only a tiny fraction of the node network so that B << O(N*C) ~ O(C) and thus T ~ O(N*B/C).
Starting from this perspective on the problem, the throughput and latency performance constraints suggest that any highly scalable solution network must be both sparse and local: the great majority of transactions should only propagate to a handful of network peers. Guided by this insight, we can search the landscape of digital asset protocols to find solutions that best optimize over performance and security tradeoffs.
The core of digital poperty networks like bitgold/bitcoin is a cryptographic ownership chain. For the sake of simplicity, we will start with indivisible quantual assets, similar to the early bitgold idea. These assets naturally form sets to represent different categories of assets, but let’s start with a simple currency which we can call the quoin. As part of the initial consensus protocol, we can consider the set of all quoins to be pre-existent and ordered as strings: for example QU0001, QU0002, etc up to some established limit of N units. Each quoin is associated with a single public cryptographic key identifying its owner, ala bitcoin. (the cryptographic implementation details are irrelevant for this discussion). Quoins further each have a preassigned value or denomination distributed according to an exponential such as 2^d, where d is a simple lookup table function based on the quoin index (transactions of arbitrary value would thus involve multiple quoins and returning change, similar to physical currency). The set of quoins can thus be considered a flat array structure where each entry stores the public key identifying the current registered owner of that quoin.
Proof of ownership can simply be established by a chain or linked list of signed transactions. It may seem odd and cumbersome to constrain these quoins to be indivisible, but this avoids complex transaction graphs. The transaction chain for each quoin is unique, independent, and does not require any form of timestamping.
The core security problem with such a simple system is double-spending. Notice however that a double-spend creates an obvious violation of the protocol: a branch in what should be a single-linked transaction chain – which is easily detectable as two transactions which share a previous link. Any solution to this problem requires additional overhead for relaying transactions to independent third party nodes who can help resolve the protocol violation in favor of one of the potential paths.
What may not be obvious is that a fully centralized solution is far from ideal: a central verification node would amount to a critical bandwidth and latency bottleneck. Any massively scalable protocol must widely distribute dispute arbitration authority across the network.
The core idea of LSDQ is to consider trust, dispute arbitration and consensus from an economic incentive perspective. The protocol can remain extremely simple by pushing much of the responsibility for dispute arbitration onto the nodes themselves, exploiting a degree of local predictive intelligence embedded in each software agent.
There are numerous potential fork-resolution protocols that converge on a stable consensus. The simplest and perhaps most effective is a weighted quorom protocol: forks are resolved in favor of the link that receives the most weighted votes. Crucially the votes are weighted by asset ownership share: in the quoin example each quoin would have a vote proportional to its denominational value. Each quoin could be used to cast one weighted vote per fork dispute, multiple votes are protocol violations and thus discarded.
Todo: only first encountered vote is considered, rest are considered fraudulent – double-voting?
The weighted quorom approach is a form of micro-democracy; and as such can be considered a pure Proof of Stake system, but it is much simpler than PoS as conceived in bitcoin derivatives such as peercoin. The key difference is that a weighted quorom protocol has nothing to do with new asset/coin creation: there is no ‘mining’ in the core protocol, it cleanly separates asset creation from transaction verification. Weighted quorom can be combined with just about any initial asset allocation or dynamic creation algorithm.
Weighted quorum by itself is not very interesting from a performance perspective: in the worst case a full quorum could result in a linear number of additional verification messages spawned for each transaction, taking us right back to square one. The key to fast transaction verification is selective intelligent pruning of messages.
We start with the following observations/assumptions:
- The wealth distribution (and thus voting weights) is approximately a pareto distribution (power law)
- Transaction sizes are likewise sparsely distributed from either a power law or exponential family
Agents can use a probabilistic approach to determine when and where to send verification requests. If the face value of a particular quoin is V, the expected value to a recipient agent A can either converge to V (if the transaction is ultimately validated by weighted quorum), or 0 if the quoin is determined to be a forgery (ie the transaction is not on the highest weighted-fork).
The discounted value dvalue(Q[i]) of a quoin Q[i] is thus the face value fvalue(Q[i]) discounted by the probability of forgery(double-spend): dvalue(Q[i]) = p(valid(Q[i])) * fvalue(Q[i]). The recipient can send out query messages to other nodes on the network, asking them to investigate the transfer chain and vote on the valid path. Each of these queries can itself involve a smaller (and perhaps conditional) micro-payment to reward the investigating node for the computational work of the query and resulting vote (ie a transaction fee) – and for large transactions this process can recurse with further requests (and increasingly smaller payments) percolating along the network until reaching diminishing returns.
The verification process can be cast as a general utility/profit maximization problem to which we can apply various machine learning approaches.
As a simple starting point, consider a greedy algorithm for a verification agent. The verification agent is a process which stores the history of many quoins, is well connected to important peers, and accepts micropayments for verification requests. It charges or expects a micro-payment per request, and reliably responds to valid requests concerning a quoin with a small return packet containing some relevant portion of the transaction history and a signed vote. The incoming request itself will embed the most recent transaction or two, so a well connected verification agent will naturally build up a partial view of the full transaction database as a side effect of its core business. And of course it can also send requests to other verification nodes as needed.
The simple verification agent receives a stream of incoming requests and has an action set consisting of: 1.) null (wait), 2.) send response packet to customer, 3.) send request packet to peer. For simplicity assume that all packet types are of a standardized size and thus have a fixed bandwidth cost C. The agent maintains a set of incoming requests R concerning the validity of query quoins Q, each of which has an attached micro-payment X, where the value of a quoin is ie: value(X[i]). Responding to a request R[i] consists of fetching the histories of quoins Q[i] and X[i], checking the cryptographic chain and known weighted votes, and then sending a signed response packet with the valid history (probably compressed) which also functions as a vote on that history.
The core game-theoretic principle for these agents is tit-for-tat. Honest/cooperative agents are profit-motivated and thus expect payments/rewards in excess of costs. In this simplified model the balance of payment or utility U[i] for verification request R[i] is just the discounted value of the incoming micro-payment minus the fixed response cost:
U[i] = fvalue(X[i])*p( valid(X[i]) ) – C.
In fact all agents will have a similar model where C is the cost function for whatever service the agent is providing. The utility of sending out a history vote request can then be derived from the expected consensus gain it provides, ie an increase in p( valid(X[i]) ).
The current estimated future posterior probability of X[i]’s validity after receiving a hypothetical vote from a peer k is p'( valid(X[i]) | H(X[i],k)’ ). Thus the expected value of sending out request H(X[i], k) for quoin X[i] to peer k is:
ev(H(X[i]), k) = fvalue(X[i])*( p'( valid(X[i]) | H(X[i], k) ) – p( valid(X[i])) )
and the expected profit is: ev( H(X[i], k) ) – C.
Note that the gain from sending out a vote request in this model is due to its potential to increase the group confidence and thus value in a quoin, rather than pure information gain. Thus it is only profitable to send requests when the agent expects them to increase the probability of a quoin’s validity, ie p'( valid(X[i]) | H[X[i]]’ ) > p( valid(X[i])). The agent does not spend time sending out vote requests for quoins it already believes to be losers.
The core of an effective verifier is in the predictive functions: p( valid(X[i])) and p'( valid(X[i]) | H(X[i], k)’ ). A sophisticated agent can employ general model-driven prediction techniques such as reinforcement learning, ANN, SVM, etc using the various transactional history datasets for training, along with competitive simulation contest results. Game theory suggests that a smart agent can be expected to employ some degree of randomness in its decisions to foil double-spenders who could otherwise perfectly predict its routing decisions and thus more easily split the network.
Regardless of the estimation technique used, we can expect that the p(valid(X)) type functions will have a characteristic shape. The initial probability or prior should at least reflect the general likelihood of double-spends across the entire system, but should also incorporate trust: past knowledge about the owner of X. If the owner has a long history of honesty, this should substantially decrease the prior of fraud. Likewise the fraud prior will perhaps depend on the size of the transaction. Beyond that, the final posterior should increase asymptotically to a maximum approaching 100% as votes accumulate.
The p(valid(X) | H(X[i], k)) term depends on the vote weight node k controls, so all else being equal requests will be directed firstly and most often towards high-weight nodes. An efficient agent will also consider the local network topology in its decisions, and perhaps employ multicast routing.
Keep in mind that consensus does not depend on the predictive functions an agent employs for optimizing transaction processing. The key to eventual consensus is that honest nodes always vote to accept the first variant of any transaction they discover, and honest nodes never change their votes, double-vote or double-spend. Local agent intelligence enables the network to scale massively by minimizing the effort expended to detect dishonesty and thus minimizing transaction costs.
Performance
The distribution of transaction values can be expected to take a power-law or perhaps exponential form such that the majority of transactions are small micropayments and large transactions are fairly rare. For very small micropayments exchanged for sub-second computational services, the value of the transaction can approach a small multiple of the cost of message bandwidth. The transaction fee could thus approach zero for the smallest micropayments.
For small transactions between trusted nodes, the predictive models outlined earlier suggest an absurdly low probability of double-spends such that investigative requests are unwarranted. However the predictive confidence in a chain also decreases exponentially with the length of all unverified steps.
This results in a dynamic where small clicks of nodes with high inter-mutual trust can exchange in long sequences of rapid micro-transactions with little external network interaction, until eventually the chains reach some trust limits where external verification and auditing becomes warranted. These chains can be compressed with hash-tree techniques combined with randomized auditing to reduce the cost of exporting quoins out of a click.
As the transaction value increases, the cost of a double-spend and thus expected value of confirmation packets increases in proportion. The maximum worthwhile effort does hit a ceiling around the cost of securing a quorum of votes. Interestingly enough, a highly inequitable wealth distribution actually reduces the number of messages required to secure a firm majority, reducing transaction costs. For example, assume a population of about 10,000 verification nodes, and a pareto distribution such that the upper 10% control 50% of the votes. The maximum cost of verification – which as discussed earlier should apply only to a tiny fraction of transactions – would thus require touching only about 10% of the network: around 1,000 messages. Assuming a bandwidth cost of about $0.10 per gigabyte and an average message size of 1KB would give an upper transaction cost of just $0.0001, or 1/100th of a penny. Which of course is rather ridiculously cheap, but that’s more or less the point.
Enter the Singularity 
