Bootstrapping A Decentralized Autonomous Corporation: Part I

Corporations, US presidential candidate Mitt Romney reminds us, are people. Whether or not you agree with the conclusions that his partisans draw from that claim, the statement certainly carries a large amount of truth. What is a corporation, after all, but a certain group of people working together under a set of specific rules? When a corporation owns property, what that really means is that there is a legal contract stating that the property can only be used for certain purposes under the control of those people who are currently its board of directors – a designation itself modifiable by a particular set of shareholder. If a corporation does something, it’s because its board of directors has agreed that it should be done. If a corporation hires employees, it means that the employees are agreeing to provide services to the corporation’s customers under a particular set of rules, particularly involving payment. When a corporation has limited liability, it means that specific people have been granted extra privileges to act with reduced fear of legal prosecution by the government – a group of people with more rights than ordinary people acting alone, but ultimately people nonetheless. In any case, it’s nothing more than people and contracts all the way down.

However, here a very interesting question arises: do we really need the people? On the one hand, the answer is yes: although in some post-Singularity future machines will be able to survive all on their own, for the forseeable future some kind of human action will simply be necessary to interact with the physical world. On the other hand, however, over the past two hundred years the answer has been increasingly no. The industrial revolution allowed us, for the first time, to start replacing human labor with machines on a large scale, and now we have advanced digitized factories and robotic arms that produce complex goods like automobiles all on their own. But this is only automating the bottom; removing the need for rank and file manual laborers, and replacing them with a smaller number of professionals to maintain the robots, while the management of the company remains untouched. The question is, can we approach the problem from the other direction: even if we still need human beings to perform certain specialized tasks, can we remove the management from the equation instead?

Most companies have some kind of mission statement; often it’s about making money for shareholders; at other times, it includes some moral imperative to do with the particular product that they are creating, and other goals like helping communities sometimes enter the mix, at least in theory. Right now, that mission statement exists only insofar as the board of directors, and ultimately the shareholders, interpret it. But what if, with the power of modern information technology, we can encode the mission statement into code; that is, create an inviolable contract that generates revenue, pays people to perform some function, and finds hardware for itself to run on, all without any need for top-down human direction?

As Let’s Talk Bitcoin’s Daniel Larmier pointed out in his own exploration on this concept, in a sense Bitcoin itself can be thought of as a very early prototype of exactly such a thing. Bitcoin has 21 million shares, and these shares are owned by what can be considered Bitcoin’s shareholders. It has employees, and it has a protocol for paying them: 25 BTC to one random member of the workforce roughly every ten minutes. It even has its own marketing department, to a large extent made up of the shareholders themselves. However, it is also very limited. It knows almost nothing about the world except for the current time, it has no way of changing any aspect of its function aside from the difficulty, and it does not actually do anything per se; it simply exists, and leaves it up to the world to recognize it. The question is: can we do better?

Computation

The first challenge is obvious: how would such a corporation actually make any decisions? It’s easy to write code that, at least given predictable environments, takes a given input and calculates a desired action to take. But who is going to run the code? If the code simply exists as a computer program on some particular machine, what is stopping the owner of that machine from shutting the whole thing down, or even modifying its code to make it send all of its money to himself? To this problem, there is only one effective answer: distributed computing.

However, the kind of distributed computing that we are looking for here is not the same as the distributed computing in projects like SETI@home and Folding@home; in those cases, there is still a central server collecting data from the distributed nodes and sending out requests. Here, rather, we need the kind of distributed computing that we see in Bitcoin: a set of rules that decentrally self-validates its own computation. In Bitcoin, this is accomplished by a simple majority vote: if you are not helping to compute the blockchain with the majority network power, your blocks will get discarded and you will get no block reward. The theory is that no single attacker will have enough computer power to subvert this mechanism, so the only viable strategy is essentially to “go with the flow” and act honestly to help support the network and receive one’s block reward. So can we simply apply this mechanism to decentralized computation? That is, can we simply ask every computer in the network to evaluate a program, and then reward only those whose answer matches the majority vote? The answer is, unfortunately, no. Bitcoin is a special case because Bitcoin is simple: it is just a currency, carrying no property or private data of its own. A virtual corporation, on the other hand, would likely need to store the private key to its Bitcoin wallet – a piece of data which should be available in its entirety to no one, not to everyone in the way that Bitcoin transactions are. But, of course, the private key must still be usable. Thus, what we need is some system of signing transactions, and even generating Bitcoin addresses, that can be computed in a decentralized way. Fortunately, Bitcoin allows us to do exactly that.

The first solution that might immediately come to mind is multisignature addresses; given a set of a thousand computers that can be relied upon to probably continue supporting the corporations, have each of them create a private key, and generate a 501-of-1000 multisignature address between them. To spend the funds, simply construct a transaction with signatures from any 501 nodes and broadcast it into the blockchain. The problem here is obvious: the transaction would be too large. Each signature makes up about seventy bytes, so 501 of them would make a 35 KB transaction – which is very difficult to get accepted into the network as bitcoind by default refuses transactions with any script above 10,000 bytes. Second, the solution is specific to Bitcoin; if the corporation wants to store private data for non-financial purposes, multisignature scripts are useless. Multisignature addresses work because there is a Bitcoin network evaluating them, and placing transactions into the blockchain depending on whether or not the evaluation succeeds. In the case of private data, an analogous solution would essentially require some decentralized authority to store the data and give it out only if a request has 501 out of 1000 signatures as needed – putting us right back where we started.

However, there is still hope in another solution; the general name given to this by cryptographers is “secure multiparty computation”. In secure multiparty computation, the inputs to a program (or, more precisely, the inputs to a simulated “circuit”, as secure multiparty computation cannot handle “if” statements and conditional looping) are split up using an algorithm calledShamir’s Secret Sharing, and a piece of the information is given to each participant. Shamir’s Secret Sharing can be used to split up any data into N pieces such that any K of them, but no K-1 of them, are sufficient to recover the original data – you choose what K and N are when running the algorithm. 2-of-3, 5-of-10 and 501-of-1000 are all possible. A circuit can then be evaluated on the pieces of data in a decentralized way, such that at the end of the computation everyone has a piece of the result of the computation, but at no point during the computation does any single individual get even the slightest glimpse of what is going on. Finally, the pieces are put together to reveal the result. The runtime of the algorithm is O(n3), meaning that the number of computational steps that it takes to evaluate a computation is roughly proportional to the cube of the number of participants; at 10 nodes, 1000 computational steps, and at 1000 nodes 1 billion steps. A simple billion-step loop in C++ takes about twenty seconds on my own laptop, and servers can do it in a fraction of a second, so 1000 nodes is currently roughly at the limit of computational practicality.

As it turns out, secure multiparty computation can be used to generate Bitcoin addresses and sign transactions. For address generation, the protocol is simple:

1. Everyone generates a random number as a private key.
2. Everyone calculates the public key corresponding to the private key.
3. Everyone reveals their public key, and uses Shamir’s Secret Sharing algorithm to calculate a public key that can be reconstructed from any 501 of the thousand public keys revealed.
4. An address is generated from that public key.

Because public keys can be added, subtracted , multiplied and even divided by integers, surprisingly this algorithm works exactly as you would expect. If everyone were to then put together a 501-of-1000 private key in the same way, that private key would be able to spend the money sent to the address generated by applying the 501-of-1000 algorithm to the corresponding public keys. This works because Shamir’s Secret Sharing is really just an algebraic formula – that is to say, it uses only addition, subtraction, multiplication and division, and one can compute this formula “over” public keys just as easily as with addresses; as a result, it doesn’t matter if the private key to public key conversion is done before the algebra or after it. Signing transactions can be done in a similar way, although the process is somewhat more complicated.

The beauty of secure multiparty computation is that it extends beyond just Bitcoin; it can just as easily be used to run the artificial intelligence algorithm that the corporation relies on to operate. So-called “machine learning”, the common name for a set of algorithms that detect patterns in real-world data and allow computers to model it without human intervention and are employed heavily in fields like spam filters and self-driving cars, is also “just algebra”, and can be implemented in secure multiparty computation as well. Really, any computation can, if that computation is broken down into a circuit on the input’s individual bits. There is naturally some limit to the complexity that is possible; converting complex algorithms into circuits often introduces additional complexity, and, as described above, Shamir’s Secret Sharing can get expensive all by itself. Thus, it should only really be used to implement the “core” of the algorithm; more complex high-level thinking tasks are best resolved by outside contractors.

Excited about this topic? Look forward to parts 2, 3 and 4: how decentralized corporations can interact with the outside world, how some simple secure multiparty computation circuits work on a mathematical level, and two examples of how these decentralized corporations can make a difference in the real world.

See also:

http://letstalkbitcoin.com/is-bitcoin-overpaying-for-false-security/