A proposal for a digital stock exchange.

What if stock trades were purely digital cryptographic transactions between peers?

The “market” can be defined as information recording a self-consistent stream of “transactions.” Each “transaction” records an event — that is to say, a trade, an issue, a filing, a bid, an ask, an establishment of credentials, etc. Any peer in posession of the transaction stream can verify its self-consistency against a set of known rules and can check the validity of a proposed trade according to those same rules.

Most instances of “cheating” in the markets – that is to say, things we need to guard against – manifest as inconsistent history. For example, when someone is selling something, you want to be absolutely sure that it is something they have in fact bought at some previous time, and that they’re selling no more than they have purchased. When someone is buying something, you need to check and see that they have acquired somewhere the money to use to buy it and that they haven’t yet used that money to buy anything else. When someone is trying to cheat, they inevitably must try to do something inconsistent with the history of who owns the issues and who has the money.

So, if we have a system in which the history of the market so far is known to the actors and checking a new transaction against it for consistency is automatic and fast, we have a system in which most forms of cheating can be immediately detected. It comes down to a method of reaching a consensus about what history actually is, bearing in mind that a cheater (or many cheaters) will be actively trying to misrepresent it.

This is the basic protocol on which Bitcoin operates. Bitcoin clients continually download the history of all bitcoin transactions made, keeping abreast of their current disposition. That way, when someone tries to spend a bitcoin, the client knows whether he actually has it to spend or not. Of course, what the client actually knows is whether a particular “wallet” has that coin to spend or not; there is some anonymity/confidentiality built into bitcoin in that it is NOT generally known which actors are in control of which wallets. You can have one wallet, or thousands, or people can share wallets, or whatever. In fact, there are even wallets nobody has control of anymore, because there are people who have lost cryptographic keys and can’t spend them anymore.

In cryptography, there is a general agreement problem called the Byzantine General’s Problem. Purely cryptographic solutions to the problem require an amount of bandwidth that doesn’t scale to more than a hundred actors very well, and the market at large is millions of actors. However, there is a solution to the problem that requires far less communication bandwidth, subject to the restriction that no actor has computing resources greater than the sum of the computing resources of of all other actors combined. The way it works is that if the history you’re looking at contains evidence that the computing resources of a majority of parties to the protocol have been required to produce it, then you can be assured that it has not been created without the cooperation of that majority of the peers. The Bitcoin protocol is based on this solution. In practice the computing resources are those of a limited group known as “miners”, and the assurance is that nobody can cheat without compute resources greater than that of a majority of the miners. More explanation later about that.

Anyway; the bitcoin “open transaction record” is encoded in a series of blocks, each of which represents approximately ten minutes of history. The clients check each block of the history for consistency as they download it; if they detect any inconsistency, they’ll immediately discard that version of history and look around for another one. Whatever is the longest history chain they can find containing no inconsistencies, they assume it’s the “real” history of bitcoin. Once a client is up-to-date, it participates in passing around all the transactions it hears about (the protocol is reminiscent of NNTP) rejecting any which are inconsistent with the history plus other transactions they’ve learned about so far.

Normally, when a new history block is received, it simply extends the chain of history that the client is working with, but if someone is playing silly buggers, or if there’s a coincidence of epic proportions, then it is possible that they receive a valid history block which would replace the last history block on the chain, or even replace an earlier one. If it would replace an earlier block, then it’s a shorter history chain, so they drop it. If it represents a chain as long as the current chain they’ve accepted, they keep it, but continue working on the one they’ve accepted first. In that case whichever chain gets extended with a new history block first (and thus becomes the longest history chain) replaces the one they’ve been working on.

Someone adds a block to the history, containing all the transactions they know about which aren’t recorded in the history already, when they succeed in solving a cryptographic hash function on their history chain so far plus the set of transactions they’re adding. Then the new block goes around, like any other transaction. Most of the clients will already know most of the transactions involved; they just need to know any transactions they haven’t heard about already, the definition of the block (which transactions it contains), and the block-creating transaction with its cryptographic hash itself. The cryptographic hash function is easy and quick to check, but takes, on average, ten minutes of the entire computing resources of all the people who are working on the problem to create.

The cryptographic hash function basically amounts to “append a 64-bit nonce to this history-so-far and then apply this hash; if it comes up less than the difficulty target, then you are the winner and your new block is added to the official history. If it comes up greater than the difficulty target, then you lose so keep trying.” There is an additional provision though; Every so often the difficulty is adjusted (the odds on the lottery change) to keep the blocks about ten minutes apart.  This is part of the protocol. Every client knows to expect it, and they will automatically reject (as being inconsistent according to their known rules) a new block that doesn’t record the correct modified difficulty target.

The reason people work on the hashing function is because that is how bitcoins get minted. The “winner” who creates the block that becomes part of the official history gets to add a transaction to the record in which 25 shiny new bitcoins are added to the economy, in a wallet controlled by him. This is the only way new bitcoins can be created which will be accepted as “real” by the clients who check the history.

Anyway, the result is that there are a lot of “bitcoin miners” who focus intensive computer resources on the hashing problem. In the early days it was written in plain-ol-C and people did it on their CPU’s, but the competition’s been escalating with better computer power and higher bitcoin values, so it’s done in parallel on GPU’s now, and people are emerging with FPGA’s and new products based on custom ASICS that are making GPU miners obsolete. If you’re still using a CPU (even one of the really good modern ones), you’re going to spend more on electricity than you make in bitcoin.

If you want to “undo” a transaction, you have to first stop its spread to other clients. In practice the only way you can do that is by immediately making a conflicting transaction which you communicate to more clients faster. Meanwhile, the other parties to the original transaction have a head start in communicating the transaction you actually made. If you wait until you *know* that there was a better transaction you could have made, you will not win that race.

In theory, there is another way; if you can produce a history block (with valid hash) with a conflicting transaction, then you can cause clients to reject your original transaction even after they’ve received it – provided no other history block for its place on the chain yet exists. But producing a history block requires you to solve that hash, and you’re not likely to do that before someone else solves a hash including the transaction you originally made. Again, time is of the essence. If you wait until a history block including your original transaction exists, then you’re sunk because to get anything else accepted you then have to produce blocks *FASTER* than all the miners put together, in order that your “preferred” history should become the accepted one.

So, if you can undo a transaction, what do you win? You win the right to have *immediately* made a different conflicting transaction, generally before there is more than a second or two to see which would have been the better of the two. If you try to go more than a second or two, then you’ll have to come up with more compute resources than the miners who are using custom ASICs and FPGAs to compute hashes orders of magnitude faster than any cloud you can hire for a million bucks. And finally, there is absolutely no way that any history where you made both transactions will ever be accepted, so whichever way you go, must necessarily be a way that you could have gone “honestly”.

Knowing all this, the people who do transactions in bitcoins regard them as “final” in the sense that they cannot be undone, when they are two or three blocks deep in the history chain; at that point nobody can possibly have the compute resources to stay ahead of the miners, and if there is another chain out there of equal length, then some miners would be working on it so the last two or three blocks wouldn’t have been produced at “normal” speed (a slight fallacy is in play here in that the blocks are produced randomly, rather than in a process requiring constant time; that is, observations about another chain impairing the speed of block production are only true in a probabilistic sense; nevertheless, it’s good reasoning in practice).

My observation is that this protocol has been (reasonably) proven with Bitcoin; but it’s more general than what they’re using it for. It’s a general agreement protocol for ensuring that the actors can perform only transactions which are valid according to a known, agreed-on set of rules and consistent according to a known, agreed-on history. When you apply that more generally, that’s applicable to any market in digital goods. Financial instruments can be digital.

So, consider the implications if this method of tracking the movement of bitcoins between wallets is extended to record the movement of stocks, bonds, etc, between wallets. What transpires is that any actor who’s buying stocks can be assured that they are real and that the actor who’s selling them actually has them to sell; meanwhile the seller can be assured that the buyer is using money that actually exists and which is actually controlled by the buyer to make the transaction. If the instruments and currency are both digital, then clearing can be done in the same transaction.

Once you’ve made your transaction, you are assured that that transaction can become part of the official history only if no transaction inconsistent with it also becomes part of the official history. If you “double spend” your money or “double sell” your instruments, only one of those transactions will ever be accepted by any client. When a history block gets appended to the chain containing one transaction, the other transaction will have “never happened” as far as any client can see.

There is one problem with a “straight” adaptation of the scheme though, and that is bandwidth. As of 2013, there are over 1e8 trades per day – sometimes as many as 1e9 on days with heavy trading. Each trade includes at least 4 transactions (bid, ask, commit, notify/verify) and depends on some unspecified number more (issues, credentials, previous transactions proving that the instruments exchanged legitimately belong to the people involved, etc). In order to scale to that kind of volume, the system would need to be capable of handling at least 1e11 transactions per day, which is to say about a million per second. Few individual peers can handle that kind of volume.

This is where you can apply Merkle trees. Let individual peers create smaller “blocks” of history, according to which issues they’re tracking and what they’re doing. The hashes on these smaller blocks, not including the individual transaction records, can be gathered into larger blocks, eventually extending the “history chain” itself.

A crucial property of these smaller blocks is that they are additive; the net movement of issues and money in individual transactions sums to the net movement of those things for the block. Likewise the net movement of issues and money for the individual blocks sums to the net movement of those things for a larger block that they’re gathered into. At the head of the tree, you’re putting together blocks that represent recent history with the chain that represents history so far; the result is a “snapshot” of the current distribution of assets, where every contributing block can be verified down to the level of individual transactions.

Now, my ideas here are somewhat woolly so far. What I have in mind is a discontinuous model for the market itself. That is, buy and sell orders (limit orders) accumulate over some period of time, then the market “opens” for one instant, finds the price at which the greatest volume can be traded, executes all the trades it can at that price, starting with the oldest, and closes again until the next instant, an unpredictable few minutes hence. The idea behind that model is to cut the bid/ask spread to zero and allow liquidity to accumulate until the execution of the trades.

There’s been a trend toward ever-smaller trades in an ever more twitchy market because of speed; faster market infrastructure and autotrading have been increasing the ratio of trades to liquidity, often resulting in feedback loops that operate well beyond the ability of humans to react. A discontinuous model where liquidity accumulates until trades are made would allow time for people to actually think about and react to each market period, and would allow larger trades with a well-defined effect on liquidity; in fact you could enter a liquidity-limited order.

A liquidity-limited order would be much like a regular order, except you could say “…but don’t execute this trade for any amount greater than $FOO percent of the volume traded in this period.”

But as I say, the particulars of a market created in this way is all woolly. My observation is that within a few limits, whatever rules one makes for a new market, if those rules are automatically checkable, then it is possible to devise a peer-to-peer protocol that implements that market and actively prevents most cheating.

The idea that a market operating during widely-separated “instants” might be beneficial is one evolution of the security model. I am thinking of the probabilistic event of solving a block hash on a set of transactions as being part of the process of making/ clearing those transactions. A peer taking the part of the “market maker” for some issue would thereby create a mini-block of transactions in that issue that would eventually become part of the history tree.

It would be that block solution that started those transactions on their way to being irrevocable. This procedure would provide an instant compute-time barrier to someone trying to undo a transaction, so the block would be well dispersed before he could come up with an alternate-history block having a solved hash. This isn’t absolutely
necessary — but it would certainly add considerably to the security of the whole system.

But there are certainly difficult questions associated with it, not least of which is the effect of sudden bad news (say an explosion in a fertilizer plant) on the market (say in grain futures). There has always been the risk of trading with someone who has heard information you haven’t; a deliberate stochastic period for liquidity to accumulate would introduce the risk that someone who places his order before the news happens may wind up trading with someone who placed his trade order after the news happened.

Leave a Reply