This is the second in my series of amateur cryptography ramblings — "How to encode a message in a deck of cards" being the first. After reading about David Chaum's blind signature digital cash scheme, I observed that the characteristics of Chaum's "bank" prevent it from being completely anonymous in all respects. In his system, the bank must be a landed, meatspace entity, because the users of the bank's cash must present themselves to the bank non-anonymously in order to redeem their cash. Therefore, if the government decided that digital cash was too sketchy and ought to be banned or regulated (which is likely, considering its potential for less-than-reputable uses), Chaum's bank is in trouble.
I present a system in which cash is never redeemed per se — instead, its value derives from its rarity, in much the same way as collectible cards can be extremely expensive while possessing little intrinsic value. My system has the advantages that it is anonymous for both buyers and sellers, does not require a landed bank, and simultaneously avoids the need for the cash to be backed by physical assets.
The nitty-gritty details of the cryptography behind the protocol are largely irrelevant. All that we need to know is that the following are required:
Running signature chains
A running signature chain (RSC) is a list of entries. Each entry has two parts: a public key; and a hash of that public key, signed with the private key corresponding to the public key in the previous entry. The person who knows the private key corresponding to the last public key in the RSC (which we will call the ownership key) is the one who owns the virtual "coin".
Suppose we have a public forum, a place where an unlimited amount of information can be posted and accessed by anyone. (We will describe later how this can be implemented). If Alice wants to give a coin to Bob, they follow the following procedure:
- Bob generates a public/private key pair.
- Bob sends the public key to Alice, while keeping the corresponding private key secret.
- Alice finds the hash of the key sent to her by Bob and signs it with her ownership key.
- Alice creates a new entry consisting of Bob's public key and her signature of it. She posts this to the public forum as the latest entry in the RSC.
- Bob verifies that the payment has been made by checking the public forum to make sure that his key is now at the end of the list, and that Alice's signature of it is valid.
Bob now owns the coin insofar as he knows the new ownership key (since he generated it), and can now repeat the procedure to give the coin to someone else. Note that Alice cannot double-spend the coin, since anyone who tries to verify her signature will find that it is invalid, because her key is no longer at the end of the RSC.
Implementing the public forum
If the public forum is completely centralized, then the central server will need to store a record of every entry of every RSC from beginning to end, in order to make it clear that the operators are not fraudulently stealing coins. Furthermore, no one has any economic incentive to expend the large amount of resources required to operate such a server: to charge for its use would defeat the whole purpose of an anonymous money system, and, since operators of the central server are anonymous, they can simply get tired of it all and shut down the server, and nobody could do anything about it.
On the other hand, if the public forum is completely decentralized, then every user needs to keep a copy of the latest entry of every RSC, and Bob needs to send his new entry to every other user. While this could work with a small number of coins and users, our purpose is to make a monetary system that can be widely used. With any significant number of coins or users, the completely decentralized approach is too resource-intensive for its users.
Therefore, the best solution is a "distributed trust" scheme. A user may choose to be an active node or a passive node.
Active nodes
An active node must A: store locally a database of the final entries of all the RSCs, B: continuously update this database in real time as coins are spent and new entries are added to the RSCs, and C: assist other active nodes in doing the same. One method of doing this would be to have every active node forward every new entry to every other active node — each active node would always have an up-to-date database. But as with the "completely decentralized" scenario, this approach is tremendously inefficient. We therefore seek a way to keep all the active nodes up-to-date without requiring each to send a huge number of messages all the time.
I have devised a rather complicated way of accomplishing this that also prevents someone from "free-riding" by receiving updates from other active nodes but not sending updates to others in turn. Each active node negotiates a mutual information pact (MIP) with about 10-20 other active nodes. A mutual information pact between two active nodes is a promise that each will send the other new RSC entries when they are received. If Carol and Dave have active nodes and such an agreement, then Carol should expect to receive new entries from Dave about as often as she sends him new entries (and vice-versa). If there is any significant deviation from this proportion, then it is clear that the MIP is being violated, and it can be terminated. Each party has an incentive to make good on the MIP so that other active nodes will help them keep their databases updated, which is necessary to avoid being fooled into accepting invalid coins. Also, a MIP should include a fixed expiration date, so that the connectivity of the network is constantly changing and is difficult to manipulate.
With this method, it is very likely that any two active nodes are separated by only a handful of links, so it will only take a short time for a new entry to reach all of them. Furthermore, it is very difficult to coordinate a fraudulent effort to prevent a certain entry from reaching all the nodes (which would enable a coin to be double-spent), since there are so many points that would need to be compromised.
To start a new active node, you must simply form a collection of MIPs with other active nodes*. As coins are spent, you will accumulate a database of up-to-date RSC entries. Although you have no previous RSC entries with which to verify the new ones coming in, you can trust them because of the improbability that several unrelated active nodes that do not know each other's identities are sending you identical but fraudulent entries.
*See "Renewal of coins" for more details.
Passive nodes
A passive node does not need to store any information locally, except for the ownership keys for the coins that it owns; however, it is more reliant upon the trustworthiness of active nodes.
Similarly to an active node, a passive node must negotiate a mutual transmission pact (MTP) with 10-20 active nodes. An MTP is slightly different from an MIP. If Carol is an active node, and Alice/Bob is a passive node, then the MTP would state that for a fixed term Carol will answer Alice/Bob's requests for final RSC entries (step 7 in the procedure below), and Alice/Bob will send Carol any new entries that s/he has generated (step 4 in the procedure below).
If Alice and Bob are both passive nodes, Alice would send Bob a coin by the following procedure:
- Bob generates a public/private key pair.
- Bob sends the public key to Alice, while keeping the corresponding private key secret.
- Alice finds the hash of the key sent to her by Bob and signs it with her ownership key.
- Alice creates a new entry consisting of Bob's public key and her signature of it. This is the latest entry in the RSC. She sends it to the active nodes that she has MTPs with.
- The active nodes that receive Alice's message verify the signature using the currently-last entry in the RSC.
- If it is valid, they relay it along to the active nodes that they have MIPs with, and those active nodes verify the signature and do the same, and so on, until all active nodes have received Alice's new entry.
- Bob verifies that the payment has been made by requesting the latest entry in the RSC from all the active nodes that he has MTPs with. If he receives from all of the active nodes the very same public key he sent to Alice, then the transaction is complete.
It is clear that Alice/Bob wants Carol (an active node) to answer her/his requests, since s/he needs the last entry in an RSC in order to verify that any coins sent to her/him have been properly sent. What is less clear is that Carol actually wants Alice/Bob to send newly-generated entries to her. But consider that Carol also has MIPs with other active nodes. If Carol refuses to accept Alice/Bob's submissions, then the active nodes with whom she has MIPs will notice that she is not sending as much information as she is receiving, and the MIPs will be broken.
Initiating the protocol
When the protocol is started, a central authority (CA) will need to generate all the keys that will be at the heads of the RSCs, since an RSC must start somewhere, and the chain of authentication must eventually trace back to an initial, publicly-known key. Therefore, the CA will know all the ownership keys and own all the coins at the beginning. Economically speaking, it is impossible for the CA to simply proceed to spend all the coins, because nobody will perceive the coins as having any value unless they are already commonly used (a Catch-22).
Therefore, the CA must find some way of giving away the coins to the general public, so that the coins will begin to be used. A naive solution would be to simply transfer a certain amount of digital cash to anyone who asks, but this runs into the problem of determining whether one person is making multiple requests. This would be undesirable because we want the cash to be distributed to as many people as fairly as possible.
This is where the CAPTCHA comes in. To initialize the system, the CA publishes the full database of the initial entries in the RSCs, and announces a date and time several weeks or months in the future during which a CAPTCHA-solving contest will be held. (The advance warning will enable people to arrange their schedules to accommodate the contest, download any software necessary to participate in the contest, and hone their fast CAPTCHA-solving techniques to perfection. Presumably, information about the contest would be spread virally through the Internet.) The contest lasts for a short period of time (perhaps an hour or two), and during that time any online identity that solves a CAPTCHA will be rewarded with a certain amount of cash. There is no limit on the number of CAPTCHA solutions that one person can submit, thus avoiding the problem of trying to prevent multiple identity spoofing, while the nature of the CAPTCHA ensures that each participant will get an approximately equal amount of cash, limited by the number of CAPTCHAs it is humanly possible to solve in the given time.
Because the CA and all the users of the money are anonymous entities with no location in particular, it is unfair (as well as an obstacle to wide distribution of the coins) to, for example, schedule the contest for a time that is 7PM in Western Europe but 2AM in East Asia. A simple solution is to hold multiple contests such that people from all time zones have a reasonable chance to participate.
Practical considerations
Coin denominations
One disadvantage of this system is that the coins are unique and indivisible, so a large number of coins would need to be transferred in a big-money transaction. The effects of this problem can be minimized by using different denominations of coins, just as (most) users of physical cash use large-denomination bills for expensive purchases rather than truckloads of the lowest-denomination coins available. The CA cannot simply declare a certain batch of coins to have a certain value and expect people to accept them as such — continuing with the trading-card analogy, value derives from rarity, so if the CA declares that a coin from List B is worth 10 times more than a coin from List A, then there must be 10 times as many coins in List A as in List B.
By distributing a full selection of different denominations from the beginning, the CA makes it easier for people to make transactions of various orders of magnitude, allowing micropayment systems to coexist with expensive software, gambling, etc. Since, however, the coins cannot be divided or fused, you must make use of cash exchange services to convert your coins, just as is done with physical cash.
Using different denominations allows for a better resolution of value without increasing the number of actual coins. For example, suppose the CA creates 1,048,576,000 coins at the beginning. Suppose further that half of them (524,288,000 coins) are designated as having 1 unit of value, a quarter (262,144,000 coins) have 2 units of value, an eighth (131,072,000 coins) have 4 units of value, and so on until the twentieth stage, where 1,000 coins have 524,288 units of value. Each of the 20 stages contains 524,288,000 units of value, so the entire money supply contains over 10 billion units, even though there are only about 1 billion coins.
Resource requirements
The 1-billion-coin figure is a large estimate for what would be necessary for a sufficiently smooth economy. Even so, the resources required for this many coins is not that large. Using elliptic curve cryptography, reasonable security can be achieved with 128-bit keys. Therefore, an active node only needs to store about 128 billion bits (less than 15 GB) in order to have a complete database of all of the final RSC entries. Note that the active nodes do not need to store the signature part of the entry — the signature is only used to verify that the entry is valid, and it can be deleted once this verification is done.
Regardless of the number of users, each node only has to deal with the few dozen other nodes that they have MIPs or MTPs with. The number of requests that the nodes must handle is affected only by the ratio of passive nodes to active nodes, which, if anything, might be expected to decrease over time as technology advances and operating an active node becomes less difficult.
Renewal of coins
To renew a coin is to send it to oneself. For example, if Alice owns a coin, she would generate a new key, sign it with the current ownership key, and submit the new entry to the network, playing the role of both sender and receiver. The only reason why you would want to do this is if you have a large hoard of coins that you do not spend very often. If you allow a coin to age too much without renewing it, then as the population of active nodes turns over, the RSC for that coin will be lost, since new active nodes will not receive a trustworthy new entry unless the coin is spent while a significant number of active nodes can attest to the validity of a new entry for its RSC. To alleviate this problem, some people might operate a "hyperactive node" that stores a publicly-available, up-to-date database of all RSCs from the original CA-issued entries up to the present, but this cannot be relied upon, as there is little economic incentive for anyone to do this.
Uses and escrow
I have so far not mentioned much about how this form of money would actually be used. It may be used for purchasing bandwidth, gambling, or information-centered economic activities such as consulting, teaching, lawyering, or software development.
If Alice hires Bob to produce some sort of informational good or service, then she does not want to pay him until he actually does the work. On the other hand, Bob does not want to do the work unless he knows that he will be paid. If neither of them knows who the other one is, then it is impossible to enforce any sort of contract. A solution (which is already used in other areas) is to have a trusted third-party escrow agency hold on to the money and the product until the agreement is fulfilled. Such an agency could charge for this service, but it would need to have a long-attested reputation that is worth more than the agency would gain by simply absconding with all the deposits it is holding.
Other services may allow a user to sell their virtual coins for real-world money at the market price, or to trade them for other physical goods. This would allow virtual wealth to translate into something you can eat or live in.
Economic analysis
The money supply in this system is fixed by the initial publication of the RSCs by the CA at the beginning. New coins cannot be created because there is no one who is able to do so (unless the users are willing to entrust the CA with this task, which the market will determine). If anything, coins will actually be destroyed by neglect or people who lose the ownership keys and consequently cannot do anything with their coins. Therefore, the trend will be that the coins will decrease in number, and increase in value slightly over time. I am not an economist, but I do not believe that this would result in a perverse incentive to hoard coins, since the more valuable the coins become, the more assiduous people will be to ensure that their coins will not be destroyed.
Conclusion
I do not foresee that this system would be implemented anytime soon. A certain amount of computing speed is necessary that may not be widely available for another decade or so. Still, in my presumptuousness, I hope that "Huser's Protocol" will catch on someday.