What If Ethereum Lived on a Treap? Or, Blockchains Charging Rent

Although truly solving blockchain scalability fundamentally, that is to say figuring out a solution to the problem that every node must process every transaction, is a very hard problem, and all suggested solutions rely on either highly advanced cryptography or intricate multi-blockchain architectures, partial solutions that provide a constant-factor improvement over the way Bitcoin does things are actually quite easy to find. In Ethereum, for example, we have the concept of a separate state tree and transaction history, allowing miners to easily store only existing account states and not historical transaction outputs that are no longer relevant and thereby drastically reducing the amount of storage that would be required; if Bitcoin is any indication, savings should be around 90%. Another improvement is the use of accounts instead of coins/UTXO as the fundamental unit, allowing each user to take up less than a hundred bytes on the blockchain regardless of how many transactions go in and out of their account. Of course, both of these are partially, or perhaps even fully, offset by the fact that Ethereum has a much larger scope, intending to use the blockchain for much more than just monetary transactions, but even if that is true it makes scalability all the more necessary. What I am about to describe in this article is another anti-bloat strategy that could potentially be used to achieve very substantial gains, this time targeting the issue of “dust”.

Dust, in simple terms, refers to the accumulation of tiny outputs (or accounts) on the blockchain, perhaps with only a fraction of a cent worth of coin, that are either dumped onto the blockchain maliciously or are simply too low-value to be even worth the increased transaction fee to send. On Ethereum, dust of the second kind can also consist of accounts that have zero balance left, perhaps because the user might want to switch to a different private key for security reasons. Dust is a serious problem; it is estimated that the majority of the Bitcoin blockchain is dust, and in the case of Litecoin something like 90% of the outputs are the result of a single malicious blockchain spam attack that took place back to 2011. In Ethereum, there is a storage fee on SSTORE in order to charge for adding something to the state, and the floating block limit system ensures that even a malicious miner has no significant advantage in this regard, but there is no concept of a fee charged over time; hence, there is no protection or incentive against a Litecoin-style attack affecting the Ethereum blockchain as well. But what if there was one? What if the blockchain could charge rent?

The basic idea behind charging rent is simple. Each account would keep track of how much space it takes up, including the [ nonce, balance, code, state_root ] header RLP and the storage tree, and then every block the balance would go down by RENTFEE multiplied by the amount of space taken up (which can be measured in bytes, for simplicity normalizing the total memory load of each storage slot to 64 bytes). If the balance of an account drops below zero, it would disappear from the blockchain. The hard part is implementation. Actually implementing this scheme is in one way easier and in one way harder than expected. The easy part is that you do not need to actually update every account every block; all you do is keep track of the last block during which the account was manipulated and the amount of space taken up by the account in the header RLP and then read just the account every time computation accesses it. The hard part, however, is deleting accounts with negative balance. You might think that you can just scan through all accounts from time to time and then remove the ones with negative balances from the database; the problem is, however, that such a mechanism doesn’t play nicely with Patricia trees. What if a new user joins the network at block 100000, wants to download the state tree, and there are some deleted accounts? Some nodes will have to store the deleted accounts to justify the empty spots, the hashes corresponding to nothing, in the trie. What if a light client wants a proof of execution for some particular transaction? Then the node supplying the proof will have to include the deleted accounts. One approach is to have a “cleansing block” every 100000 blocks that scans through the entire state and clears out the cruft. However, what if there was a more elegant solution?

Treaps

One elegant data structure in computer science is something called a treap. A treap, as one might or probably might not understand from the name, is a structure which is simultaneously a tree and a heap. To review the relevant data structure theory, a heap) is a binary tree, where each node except for leaves has one or two children, where each node has a lower value than its children and the lowest-value node is at the top, and what data structure theorists normally call a tree is a binary tree where values are arranged in sorted order left to right (ie. a node is always greater than its left child and less than its right child, if present). A treap combines the two by having nodes with both a key and a priority; the keys are arranged horizontally and the priorities vertically. Although there can be many heaps for each set of priorities, and many binary trees for each set of values, as it turns out it can be proven that there is always exactly one treap that matches every set of (priority, value) pairs.

Also, as it turns out, there is an easy (ie. log-time) algorithm for adding and removing a value from the treap, and the mathematical property that there is only one treap for every set of (priority, value) pairs means that treaps are deterministic, and both of these things together make treaps a potential strong candidate for replacing Patricia trees as the state tree data structure. But then, the question is, what would we use for priorities? The answer is simple: the priority of a node is the expected block number at which the node would disappear. The cleaning process would then simply consist of repeatedly kicking off nodes at the top of the treap, a log-time process that can be done at the end of every block.

However, there is one implementation difficulty that makes treaps somewhat challenging for this purpose: treaps are not guaranteed to be shallow. For example, consider the values [[5, 100], [6, 120], [7, 140], [8, 160], [9, 180]]. The treap for those would unfortunately look like this:

Now, imagine that an attacker generates ten thousand addresses, and puts them into sorted order. The attacker then creates an account with the first private key, and gives it enough ether to survive until block 450000. The attacker then gives the second private key enough ether to survive until block 450001. The third private key lasts until 450002, and so forth until the last account susrvives until block 459999. All of these go into the blockchain. Now, the blockchain will have a chain of ten thousand values each of which is below and to the right of all of the previous. Now, the attacker starts sending transactions to the addresses in the second half of the list. Each of those transactions will require ten thousand database accesses to go through the treap to process. Basically, a denial of service attack through trie manipulation. Can we mitigate this by having the priorities decided according to a more clever semi-randomized algorithm? Not really; even if priorities were completely random, there is an algorithm using which the attacker would be able to generate a 10000-length subsequence of accounts that have both address and priority in increasing order in a hundred million steps. Can we mitigate this by updating the treap bottom-up instead of top-down? Also no; the fact that these are Merkle trees means that we basically have to use functional algorithms to get anywhere.

So what can we do? One approach is to figure out a way to patch this attack. The simplest option would likely involve having a higher cost to purchasing priority the more levels you go down the tree. If the treap is currently 30 levels deep but your addition would increase it to 31 levels, the extra level would be a cost that must be paid for. However, this requires the trie nodes to include a built-in height variable, making the data structure somewhat more complicated and less minimalistic and pure. Another approach is to take the idea behind treaps, and create a data structure that has the same effect using plain old boring Patricia trees. This is the solution that is used in databases such as MySQL, and is called “indices“. Basically, instead of one trie we have two tries. One trie is a mapping of address to account header, and the other trie is a mapping of time-to-live to address. At the end of every block, the left side of the TTL trie is scanned, and as long as there are nodes that need to be deleted they are repeatedly removed from both tries. When a new node is added it is added to both tries, and when a node is updated a naive implementation would update it in both tries if the TTL is changed as a result of the transaction, but a more sophisticated setup might be made where the second update is only done in a more limited subset of cases; for example, one might create a system where a node needs to “purchase TTL” in blocks of 90 days, and this purchase happens automatically every time a node gets onto the chopping block – and if the node is too poor then of course it drops off the edge.

Consequences

So now we have three strategies: treaps with heights, tries with time-to-live indices and the “cleansing block”. Which one works best is an empirical question; the TTL approach would arguably be the easiest to graft onto existing code, but any one of the three could prove most effective assuming the inefficiencies of adding such a system, as well as the usability concerns of having disappearing contracts, are less severe than the gains. What would the effects of any of these strategies be? First of all, some contracts would need to start charging a micro-fee; even passive pieces of code like an elliptic curve signature verifier would need to continually spend funds to justify their existence, and those funds would have to come from somewhere. If a contract cannot afford to do this, then the contract could just store a hash and the onus would be on the transaction sender to send the contract the code that it is supposed to execute; the contract would then check the hash of the code and if the hash matches the code would be run. Name-registry applications might decide to work somewhat differently, storing most of their registrations using some Merkle tree-based offchain mechanism in order to reduce their rent.

However, there is also another more subtle consequence: account nonce resets. For example, suppose that I have an account, and I received and sent some transactions from that account. In order to prevent replay attacks (ie. if I send 10 ETH to Bob, Bob should not be able to republish the same transaction in order to get another 10 ETH), each transaction includes a “nonce” counter that increments after every transaction. Thus, the account header stores the current transaction nonce, and if the current nonce is 2 then the only transaction that will be accepted is one with a nonce of 2, at which point the nonce will go up to 3. If accounts disappear, then nonces could reset to 0, leading to potentially dangerous situations if a user accumulates some funds in an account, then lets the balance drop to zero and the account disappear, and then refills it. One solution would be for transactions to have a maximum block number, which can be set to 10 days in the future by defauly, and then require all withdrawals to leave enough balance for the account to last another 10 days; this way, old transactions with nonce 0 would be too old to replay. However, this adds another inefficiency, and must be balanced with the benefit of blockchains charging rent.

As another interesting point, the history of the blockchain would become relevant again; some dapps, wishing to store some data forever, would store it in a transaction instead of the state, and then use past block headers as an immutable rent-free datastore. The existence of applications which do this would mean that Ethereum clients would have to store at least a headers-only version of the history, compromising Ethereum’s “the present state is all that matters” ideology. However, an alternative solution might be to have a contract maintaining a Merkle mountain range, putting the responsibility onto those users that benefit from particular pieces of information being stored to maintain log-sized Merkle tree proofs with the contract remaining under a kilobyte in size.

As a final objection, what if storage space is not the most problematic point of pressure with regard to scalability? What if the main issue is with bandwidth or computation? If the problem is computation, then there are some convenient hacks that can be made; for example, the protocol might be expanded to include both transactions and state transition deltas into the block, and nodes would be free to only check a portion of the deltas (say, 10%) and then quickly gossip about inconsistencies to each other. If it’s bandwidth, then the problem is harder; it means that we simply cannot have every node downloading every transaction, so some kind of tree-chains solution is the only way to move forward. On the other hand, if space is the problem, then rent-charging blockchains are very likely the way to go.

On Long-Term Cryptocurrency Distribution Models

One of the challenges when creating a new cryptocurrency is figuring out what the distribution model is going to be. Who is going to receive the currency units, at what time, and what is the mechanism that decides? Despite the crucial importance of this question, there has actually been comparatively little thought into the issue compared with other aspects of currency, like consensus algorithms and feature sets. The question is particularly challenging because, just like many other problems in the cryptocurrency space that have parallels in the “real world” at large, cryptocurrencies also face the requirement of decentralization: it is considered unacceptable to have a cryptographic platforms whose continued operation depends on the existence of any specific party in the long term. Given this rather stringent requirement, how should a new currency distribute itself?

So far, the problem is still in its very early stages of discussion. While the question of short-term distribution is a highly dynamic debate between different types of asset carryovers, one-way transfers, two-way pegs, pre-mines, pre-sales and other mechanisms coming out almost every month, long-term distribution in nearly every cryptocurrency now follows one of two strategies: nothing at all, or mining. The reason why having a fixed never-growing supply is undesirable is obvious: it encourages wealth concentration and creates a static community of holders without an effective way for new people to get in, and it means that the coin has no way to incentive any specific kind of activity in the long term. The issue with mining, however, is more subtle. Cryptocurrency mining generally serves two functions; first, it provides a way of securing the network, and second, it serves as a distribution model, giving hundreds of thousands of people around the world a way of getting access to a few coins. So far, mining has been considered necessary for the former, and an effective way of doing the latter. More recently, however, there has been a substantial amount of interest and research into proof of stake, including strategies such as transactions as proof-of-stake, delegated proof of stake and a partial solution to nothing-at-stake, Slasher, suggesting that mining might not be necessary after all. Second, the rise of both ASICs and professional GPU farms is turning mining itself into an increasingly concentrated and quasi-centralized community, so any new mining-distributed currency will quickly be dominated by professional companies and not “the people” at large. If both trends continue, and mining proves to be a bad model for distribution, it will therefore need to be replaced. But then, the question is, by what?

So far, we know of several answers:

  • Pretend that the problem does not exist. This is the solution that has been taken by most proof-of-stake cryptocurrencies, and surprisingly enough even proof-of-work currencies, today.
  • Centralized distribution: let some central authority hand out coins according to some formula.
  • Useful proof-of-work: hand out coins to anyone who performs a particular socially useful computation, eg. weather prediction. This algorithm need not be used for consensus; it can exist simply to distribute coins while proof-of-stake does the hard work of maintaining consensus.
  • Algorithmic consensus distribution. Essentially, some kind of dynamic, adaptive consensus-based process for determining who gets new coins.

The second is theoretically the most powerful; currency units can be distributed either to everyone in the world for maximum fairness or to pay bounties for protocol development, external charitable causes or anything else. However, at the same time actually using such a mechanism arguably kills the whole point of a cryptocurrency: that it is decentralized and depends on no specific party for its continued existence. Thus, we can think of the centralized distributor as an ideal that we want to approach, sort of like the ideal of a bureaucrat god found in economic efficiency theory, and see how close to that ideal we can approach while still maintaining a structure that is guaranteed, or at least highly likely, to remain stable in the long term.

Useful Proof of Work As Distribution: A Relaxed Algorithm

Useful proof of work is likely the simpler idea. Initially, it was considered impossible to make a proof of work based on useful computation because of the verification problem: a proof-of-work task cannot take longer than a few thousands steps because every node in the network also needs to verify it to accept the block. Primecoin was the closest we got, and even there computing chains of prime numbers is not really all that useful. Now, thanks to the existence of a programming environment with a built-in computational stack trace mechanism, there is actually an alternative approach that removes this particular obstacle, using spot-checking and deposit sacrifices to make sure that work is being done correctly. The approximate algorithm for doing so is as follows.

1. Suppose that F(k) is a function that takes 32 bytes of random data as an input, carries out some computation taking n steps (where n is fairly large, say ten billion) and then returns a value R which is socially useful.
2. In order to perform one round of mining, start off by choosing a random m, and let B be the block header. Let k = sha3(B + m) as the seed.
3. Define a function STEP(P, D) -> D' where P is the program code, D is some tuple of data perhaps including stack, memory and program counter representing the state of the computation, and STEP carries out one computational step and returns the modified computational state D'.
4. Let D[0] = { pc: 0, stack: [], memory: [k] } (or some other construction involving k in a different computational model). Let D[i] = STEP(P, D[i-1]) where P is the program corresponding to the evaluation of F. D[n] should, in some appropriate fashion, contain the result of F.
5. Define H as a hash function of D[i]; something like sha3(pc + str(stack) + str(memory)) satisfies as a quick-and-dirty option. Let H[i] = H(D[i]). Compute all D[i] and all H[i] and let R be the root of a Merkle tree of all H[i]. If R < 2^256 / D then the work is valid and the miner is entitled to a reward.

Basically, we take the state of the program after each computational step (we can optionally make STEP process the execution of a few thousand computational steps for greater efficiency; this does not seriously compromise anything), and build a Merkle tree out of the whole thing and look at the root. This is somewhat tricky to implement; fortunately, however, the Ethereum virtual machine and block structure is already almost an exact replica of this algorithm, so one could take that code and use it almost verbatim.

The algorithm described above by itself has an obvious hole in it: it is not easy-to-verify, so fraudulent miners can easily pollute the network with bad-seeming blocks. Thus, as an anti-spam and anti-fraud mechanism, we require the following:

1. To be able to mine, nodes must purchase a “mining bond” of price N * R (say, R = 10^18 and N = 100), which returns to the miner after 10000 blocks. Each mining bond allows the miner to submit one work at a time.
2. If a miner submits a seemingly-valid work, including the m and k values, the root, and the socially useful output, then the mining bond reward increases by R
3. Anyone else with a mining bond can check the work themselves. If the Merkle root at the end is inconsistent, then they can publish a “challenge” transaction consisting of some number (say, 16) of sub-nodes. At that point, the original submitter has the choice of either giving up (as defined by not posting a response within 25 blocks), sacrificing their entire mining bond to the checker, or make a “response” transaction pointing out the first of those subnodes that they disagree with. If a response is submitted, the challenger must respond going down one level further, providing the sixteen subnodes between the last agreed subnode and the first disagreed subnode, and so forth, until the process converges upon the interval between two adjacent H[i] and H[i+1] values in the tree. At that point, the miner must submit the values of D[i] and D[i+1] in a transaction, which is considered valid if and only if P(D[i]) = D[i+1].

The problem is, however, that the process of checking takes as long as the original computation itself, so there does need to be an explanation as to why anyone would do it. If all miners attempt to cheat frequently, then it makes sense to perform spot-checks in order to collect the deposit (which we assumed to be 100x), but if miners realize this and as a result don’t cheat then there is no longer an incentive to check, so no one would check and miners would have free rein to cheat. This is a classic hawk-dove equilibrium paradox, and can be solved by game theory (here, we assume that mining has a cost of 0.5 and a reward of 1):

Cheats Does not cheat
Checks (-100, 101) (0.5,-0.5)
Does not check (1,0) (0.5,0)

Computing a mixed-strategy equilibrium in this simplified two-player model shows the miner cheating 0.5% of the time and the checker checking 0.5% of the time; under those two conditions, each player is indifferent to the strategy of the other so there is no opportunity for either one to further optimize and cheat. If we push closer to the economic equilibrium of mining and we say that mining has a cost of 0.9, then the equilibrium has a cheating rate of 0.9% and a checking rate of 0.9%. Thus, economically driven spot-checking is a legitimate strategy for ratting out fraudulent mining attempts, and can keep cheating rates arbitrarily low if we are willing to push up collateral requirements.

So what kind of work can we do? First of all, it might be better not to include computation that is incapable of handling noise, ie. where a bad answer accepted as a good answer does more than 100x as much bad as an actual good answer. Second, the algorithm here allows for work that is not easy-to-verify, but it does nothing to allow work that is data-heavy. For example, SETI is data-heavy – you need to have a picture of the sky in order to search it for aliens. Third, the algorithm must be parallelization-friendly. Running a machine learning algorithm on terabytes of data is not really something that can be split into discrete chunks, even large-sized ones. The second criterion can potentially be relaxed; because there isn’t really any benefit to mining with bad data versus good data, an SETI foundation can be set up which provides a stream of data for miners to work with, and adds a very small subsidy to encourage miners to use it. Theoretically, the foundation can even be decentralized and run as a proof-of-stake-voting algorithm on a blockchain. The simplest kind of socially useful computation to use, however, might be genetic algorithms. Genetic algorithms are often used to find solutions to problems that are intractable in closed-form, like finding optimal radio antenna shapes, spaceflight trajectories, aerodynamic shapes, and so forth; the blockchain may provide an ideal environment for doing such computation on everyone’s nodes for free. Certain classes of data search and aggregation puzzles could also potentially be split up, though they are much more data-heavy whereas genetic algorithms are close to data-free once launched.

Parliaments And Better Algorithms

Algorithmic consensus distribution is the more interesting possibility. What if there can be a consensus algorithm to distribute tokens over time, where that algorithm can reward arbitrary good work? For example, one might want to pay bounties to people who contribute to the ecosystem, or even to the world in general. The simplest approach here seems to be to randomly select a “parliament” – every N blocks, stakeholders can vote on 200 nodes that will make the decision of where the newly generated funds will go.

The obvious question to ask is: what are the economics of this? In theory, the nodes will want to select the distribution that optimally benefits the community as a whole, so as to maximize their chance of getting re-elected. However, are there opportunities for corruption? We all know that traditional democracy is highly imperfect, so how do we know that our crypto-enabled wealth distribution scheme will be any better? Fortunately, there is one strong argument to be made that it actually will be. The reason is that traditional democracies have a number of very serious failure modes; for example, a parliament can seize people’s property, conscript people into armies for war, restrict free speech, etc. In this case, however, there is a very clear and obvious upper bound on how much damage a parliament could do: it could redirect the money to split among itself. There is also the risk that the parliament will crowdfund something which is a public bad to society, but a public good among themselves (eg. a war), but they have no existing military apparatus to latch onto and no existing public consensus that they are supposed to be using coercive power for any reason at all so they are in no better a position to do such a thing than any other group commanding a similar level of economic resources. Thus, if we suppose that parliaments fail, say, 33% of the time, then we can see how in a democracy this would be catastrophic but here it only means that the distribution mechanism becomes 67% as useful as it could be.

Another criticism is that such a mechanism, no matter how it may be constructed, will invariably create some sort of political governance class, and thus will stabilize around a particular small set of political viewpoints, generate its own form of inequality, and eventually lead to a long-term hostile takeover. This would be limited in effect, but even still at its worst 100% of the new currency issuance will be siphoned off by a crypto-political elite. One solution is to make parliaments randomly selected (ie. demarchy) rather than elected, reducing the chance of such conspiracies further but at the cost of weakening the parliament’s expected level of expertise on optimal distribution and its ability to form long-term consistent institutions; however, if we want to create a system that has the political image of being neutral and decentralized that is perhaps something that we actually want.

However, we probably can, and certainly must at least try, to be more imaginative. Parliaments and voting are only the simplest and crudest form of having a decentralized organization; there are almost certainly better alternatives based on principles such as holarchy, liquid democracy, futarchy and various combinations of these and other ideas that we have not thought of but that will become possible because of the much higher degree of both interconnectedness and information processing efficiency provided by modern technology. Ideally, as much of the process as possible would be in some fashion automated – the process should function as a DAO, not a DO, and the position of highest power, or the closest philosophical analog of such a thing, should be held by an algorithm and not a set of people – perhaps a sacrifice from the point of view of optimality at any particular time, but, one might argue, a boon for long-term stability, and an especially appropriate choice for a cryptographic platform that intends to claim some concept of neutrality.

A simple futarchy-based implementation might work as follows. Suppose that there are N projects asking for a grant consisting of the entire currency supply to be distributed during some time period, and the desire is to select the one that will maximize the value of the coin after one year. We create N sub-tokens, T[0] ... T[N-1], where the value of T[i] is zero if project i does not get chosen but can be redeemed for one currency unit after one year if the project does get chosen. Then, we create subtokens R[0] ... R[N-1], where the value of R[i] is zero if the project does not get chosen or an amount of currency units equal to 232 computational steps in value (we include a small useful-PoW or useless-PoW market into the coin for this purpose) if the project does get chosen. Now, suppose that the probability of project i getting chosen is P[i] and the value of the token in the event that project i gets chosen after one year is V[i]. We note that the value of T[i] is P[i] * V[i] and the value of R[i] is P[i] * K where K is the cost of computing 232 computational steps. Hence, the project with maximum P[i] / R[i] also maximizes V[i] / K and hence V[i], so that project is assumed to maximize the value of the coin and hence chosen. The only challenge left is figuring out what the risks of market manipulation attacks are assuming there are individual parties with non-negligible market power. This strategy seems more mathematically clean and less vulnerable to turning into something centralized, but on the other hand there seem to be fewer safeguards to prevent it from becoming evil. The best response might simply be that a coin run by an evil DAO will lose public support, and hence will lose value, so the futarchy algorithm itself might select against such undesirable actions. Second, of course, the futarchy does not command a military and there is no pre-existing public consensus that it is entitled to employ any kind of coercion.

Ultimately, both of these approaches could be combined. One can have a parliament, or a futarchy, select useful proof of work algorithms or even data for specific useful proof of work algorithms, or one can have a parliament or futarchy with useful proof of work as its voting mechanism. However, one important conclusion here is that both of the algorithms described are complicated; there is no easy solution to figuring out how to distribute coins in a good way. Which, given the state of the financial system at large, makes sense; if it was easy to distribute coins fairly then the US dollar and other fiat currencies would have likely been overthrown in favor of such alternatives in at least some parts of the world a long time ago. Because of the complexity involved, it is unlikely that either of these will be used for ether itself; ether is intended to be boring crypto-gasoline with simple properties to target maximum stability and reliability, not a super-advanced economically innovative decentralized autonomous organization. So if you want to see GeneticAlgoCoin, FutarchyCoin and ParliamentCoin developed, feel free to run them on top of Ethereum as sub-currencies; the Serpent compiler is all yours to play with.

Credit to Neal Koblitz for suggesting the idea of spot-checking and convincing me of the importance of useful PoW, Robin Hanson for inventing futarchy, and realistically probably at least several cryptographers who came up with the concept of multi-round challenge-response protocols before me

Long-Range Attacks: The Serious Problem With Adaptive Proof of Work

Our current proof of work design, blockchain-based proof of work, is the second iteration of our attempt to create a mining algorithm that is guaranteed to remain CPU-friendly and resistant to optimization by specialized hardware (ASICs) in the long term. Our first attempt, Dagger, tried to take the idea of memory-hard algorithms like Scrypt one step further by creating an algorithm which is memory-hard to compute, but memory-easy to verify, using directed acyclic graphs (basically, trees where each node has multiple parents). Our current strategy takes a much more rigorous track: make the proof of work involve executing random contracts from the blockchain. Because the Ethereum scripting language is Turing-complete, an ASIC that can execute Ethereum scripts is by definition an ASIC for general computation, ie. a CPU – a much more elegant argument than “this is memory-hard so you can’t parallelize as much”. Of course, there are issues of “well, can you make specific optimizations and still get a large speedup”, but it can be argued that those are minor kinks to be worked out over time. The solution is also elegant because it is simultaneously an economic one: if someone does create an ASIC, then others will have the incentive to look for types of computation that the ASIC can’t do and “pollute” the blockchain with such contracts. Unfortunately, however, there is one much larger obstacle to such schemes in general, and one which is unfortunately to some degree fundamental: long-range attacks.

A long-range attack basically works as follows. In a traditional 51% attack, I put 100 bitcoins into a fresh new account, then send those 100 bitcoins to a merchant in exchange for some instant-delivery digital good (say, litecoins). I wait for delivery (eg. after 6 confirmations), but then I immediately start working on a new blockchain starting from one block before the transaction sending the 100 bitcoins, and put in a transaction instead sending those bitcoins back to myself. I then put more mining power into my fork than the rest of the network combined is putting into the main chain, and eventually my fork overtakes the main chain and thereby becomes the main chain, so at the end I have both the bitcoins and the litecoins. In a long-range attack, instead of starting a fork 6 blocks back, I start the fork 60000 blocks back, or even at the genesis block.

In Bitcoin, such a fork is useless, since you’re just increasing the amount of time you would need to catch up. In blockchain-based proof of work, however, it is a serious problem. The reason is that if you start a fork straight from the genesis block, then while your mining will be slow at first, after a few hundred blocks you will be able to fill the blockchain up with contracts that are very easy for you to mine, but difficult for everyone else. One example of such a contract is simply:

i = 0
while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:
    i = i + 1

You know that the contract will take exactly one million rounds before the hash matches up, so you can calculate exactly how many steps and how much gas it will take to run and what the state will be at the end immediately, but other people will have no choice but to actually run through the code. An important property of such a scheme, a necessary consequence of the halting problem, is that it is actually impossible (as in, mathematically provably impossible, not Hollywood impossible) to construct a mechanism for detecting such clever contracts in the general case without actually running them. Hence, the long-range-attacker could fill the blockchain with such contracts, “mine” them, and convince the network that it is doing a massive amount of work when it is actually just taking the shortcut. Thus, after a few days, our attacker will be “mining” billions of times faster than the main chain, and thereby quickly overtake it.

Notice that the above attack assumes little about how the algorithm actually works; all it assumes is that the condition for producing a valid block is dependent on the blockchain itself, and there is a wide range of variability in how much influence on the blockchain a single unit of computational power can have. One solution involves artificially capping the variability; this is done by requiring a tree-hashed computational stack trace alongside the contract algorithm, which is something that cannot be shortcut-generated because even if you know that the computation will terminate after 1 million steps and produce a certain output you still need to run those million steps yourself to produce all of the intermediate hashes. However, although this solves the long-range-attack problem it also ensures that the primary computation is not general computation, but rather computing lots and lots of SHA3s – making the algorithm once again vulnerable to specialized hardware.

Proof of Stake

A version of this attack also exists for naively implemented proof of stake algorithms. In a naively implemented proof of stake, suppose that there is an attacker with 1% of all coins at or shortly after the genesis block. That attacker then starts their own chain, and starts mining it. Although the attacker will find themselves selected for producing a block only 1% of the time, they can easily produce 100 times as many blocks, and simply create a longer blockchain in that way. Originally, I thought that this problem was fundamental, but in reality it’s an issue that can be worked around. One solution, for example, is to note that every block must have a timestamp, and users reject chains with timestamps that are far ahead of their own. A long-range attack will thus have to fit into the same length of time, but because it involves a much smaller quantity of currency units its score will be much lower. Another alternative is to require at least some percentage (say, 30%) of all coins to endorse either every block or every Nth block, thereby absolutely preventing all attacks with less than that percent of coins. Our own PoS algorithm, Slasher, can easily be retrofitted with either of these solutions.

Thus, in the long term, it seems like either pure proof of stake or hybrid PoW/PoS are the way that blockchains are going to go. In the case of a hybrid PoW/PoS, one can easily have a scheme where PoS is used to resolve the issue described above with BBPoW. What we’ll go with for Ethereum 1.0 may be proof of stake, it might be a hybrid scheme, and it might be boring old SHA3, with the understanding that ASICs will not be developed since manufacturers would see no benefit with the impending arrival of Ethereum 2.0. However, there is still one challenge that arguably remains unresolved: the distribution model. For my own thoughts on that, stay tuned for the next part of this series.

DAOs, DACs, DAs and More: An Incomplete Terminology Guide

One of the most popular topics in the digital consensus space (a new term for cryptocurrency 2.0 that I’m beta-testing) is the concept of decentralized autonomous entities. There are now a number of groups rapidly getting involved in the space, including Bitshares (also known as Invictus Innovations) developing “decentralized autonomous companies”, BitAngels’ David Johnston with decentralized applications, our own concept of decentralized autonomous corporations which has since transformed into the much more general and not necessarily financial “decentralized autonomous organizations” (DAOs); all in all, it is safe to say that “DAOism” is well on its way to becoming a quasi-cyber-religion. However, one of the hidden problems lurking beneath the space is a rather blatant one: no one even knows what all of these invididual terms mean. What exactly is a decentralized organization, what is the difference between an organization and an application, and what even makes something autonomous in the first place? Many of us have been frustrated by the lack of coherent terminology here; as Bitshares’ Daniel Larimer points out, “everyone thinks a DAC is just a way of IPOing your centralized company.” The intent of this article will be to delve into some of these concepts, and see if we can come up with at least the beginnings of a coherent understanding of what all of these things actually are.

Smart contracts

A smart contract is the simplest form of decentralized automation, and is most easily and accurately defined as follows: a smart contract is a mechanism involving digital assets and two or more parties, where some or all of the parties put assets in and assets are automatically redistributed among those parties according to a formula based on certain data that is not known at the time the contract is initiated.

One example of a smart contract would be an employment agreement: A wants to pay $500 to B to build a website. The contract would work as follows: A puts $500 into the contract, and the funds are locked up. When B finishes the website, B can send a message to the contract asking to unlock the funds. If A agrees, the funds are released. If B decides not to finish the website, B can quit by sending a message to relinquish the funds. If B claims that he finished the website, but A does not agree, then after a 7-day waiting period it’s up to judge J to provide a verdict in A or B’s favor.

The key property of a smart contract is simple: there is only a fixed number of parties. The parties do not all have to be known at initialization-time; a sell order, where A offers to sell 50 units of asset A to anyone who can provide 10 units of asset B, is also a smart contract. Smart contracts can run on forever; hedging contracts and escrow contracts are good examples there. However, smart contracts that run on forever should still have a fixed number of parties (eg. an entire decentralized exchange is not a smart contract), and contracts that are not intended to exist forever are smart contracts because existing for a finite time necessarily implies the involvement of a finite number of parties.

Note that there is one gray area here: contracts which are finite on one side, but infinite on the other side. For example, if I want to hedge the value of my digital assets, I might want to create a contract where anyone can freely enter and leave. Hence, the other side of the contract, the parties that are speculating on the asset at 2x leverage, has an unbounded number of parties, but my side of the contract does not. Here, I propose the following divide: if the side with a bounded number of parties is the side that intends to receive a specific service (ie. is a consumer), then it is a smart contract; however, if the side with a bounded number of parties is just in it for profit (ie. is a producer), then it is not.

Autonomous Agents

Autonomous agents are on the other side of the automation spectrum; in an autonomous agent, there is no necessary specific human involvement at all; that is to say, while some degree of human effort might be necessary to build the hardware that the agent runs on, there is no need for any humans to exist that are aware of the agent’s existence. One example of an autonomous agent that already exists today would be a computer virus; the virus survives by replicating itself from machine to machine without deliberate human action, and exists almost as a biological organism. A more benign entity would be a decentralized self-replicating cloud computing service; such a system would start off running an automated business on one virtual private server, and then once its profits increase it would rent other servers and install its own software on them, adding them to its network.

A full autonomous agent, or a full artificial intelligence, is the dream of science fiction; such an entity would be able to adjust to arbitrary changes in circumstances, and even expand to manufacture the hardware needed for its own sustainability in theory. Between that, and single purpose agents like computer viruses, is a large range of possibilities, on a scale which can alternatively be described as intelligence or versatility. For example, the self-replicating cloud service, in its simplest form, would only be able to rent servers from a specific set of providers (eg. Amazon, Microtronix and Namecheap). A more complex version, however, should be able to figure out how to rent a server from any provider given only a link to its website, and then use any search engine to locate new websites (and, of course, new search engines in case Google fails). The next level from there would involve upgrading its own software, perhaps using evolutionary algorithms, or being able to adapt to new paradigms of server rental (eg. make offers for ordinary users to install its software and earn funds with their desktops), and then the penultimate step consists of being able to discover and enter new industries (the ultimate step, of course, is generalizing completely into a full AI).

Autonomous agents are some of the hardest things to create, because in order to be successful they need to be able to navigate in an environment that is not just complicated and rapidly changing, but also hostile. If a web hosting provider wants to be unscrupulous, they might specifically locate all instances of the service, and then replace them with nodes that cheat in some fashion; an autonomous agent must be able to detect such cheating and remove or at least neutralize cheating nodes from the system.

Decentralized Applications

A decentralized application is similar to a smart contract, but different in two key ways. First of all, a decentralized application has an unbounded number of participants on all sides of the market. Second, a decentralized application need not be necessarily financial. Because of this second requirement, decentralized applications are actually some of the easiest things to write (or at least, were the easiest before generalized digital consensus platforms came along). For example, BitTorrent qualifies as a decentralized application, as do Popcorn Time, BitMessage, Tor and Maidsafe (note that Maidsafe is also itself a platform for other decentralized applications).

Generally, decentralized applications fall into two classes, likely with a substantial gray area between the two. The first class is a fully anonymous decentralized application. Here, it does not matter who the nodes are; every participant is essentially anonymous and the system is made up of a series of instant atomic interactions. BitTorrent and BitMessage are examples of this. The second class is a reputation-based decentralized application, where the system (or at least nodes in the system) keep track of nodes, and nodes maintain status inside of the application with a mechanism that is purely maintained for the purpose of ensuring trust. Status should not be transferable or have de-facto monetary value. Maidsafe is an example of this. Of course, purity is impossible – even a BitTorrent-like system needs to have peers maintain reputation-like statistics of other peers for anti-DDoS purposes; however, the role that these statistics play is purely in the background and very limited in scope.

An interesting gray area between decentralized applications and “something else” is applications like Bitcoin and Namecoin; these differ from traditional applications because they create ecosystems and there is a concept of virtual property that has value inside the context of this ecosystem, in Bitcoin’s case bitcoins and in Namecoin’s case namecoins and domain names. As we’ll see below, my classification of decentralized autonomous organizations touches on such concepts, and it is not quite clear exactly where they sit.

Decentralized Organizations

In general, a human organization can be defined as combination of two things: a set of property, and a protocol for a set of individuals, which may or may not be divided into certain classes with different conditions for entering or leaving the set, to interact with each other including rules for under what circumstances the individuals may use certain parts of the property. For example, consider a simple corporation running a chain of stores. The corporation has three classes of members: investors, employees and customers. The membership rule for investors is that of a fixed-size (or optionally quorum-adjustable size) slice of virtual property; you buy some virtual property to get in, and you become an investor until you sell your shares. Employees need to be hired by either investors or other employees specifically authorized by investors (or other employees authorized by other employees authorized by investors, and so on recursively) to participate, and can also be fired in the same way, and customers are an open-membership system where anyone can freely interact with the store in the obvious officially sanctioned way for any time. Suppliers, in this model, are equivalent to employees. A nonprofit charity has a somewhat different structure, involving donors and members (charity recipients may or may not be considered members; the alternative view sees the positive increments in the recipients’ welfare as being the charity’s “product”).

The idea of a decentralized organization takes the same concept of an organization, and decentralizes it. Instead of a hierarchical structure managed by a set of humans interacting in person and controlling property via the legal system, a decentralized organization involves a set of humans interacting with each other according to a protocol specified in code, and enforced on the blockchain. A DO may or may not make use of the legal system for some protection of its physical property, but even there such usage is secondary. For example, one can take the shareholder-owned corporation above, and transplant it entirely on the blockchain; a long-running blockchain-based contract maintains a record of each individual’s holdings of their shares, and on-blockchain voting would allow the shareholders to select the positions of the board of directors and the employees. Smart property systems can also be integrated into the blockchain directly, potentially allowing DOs to control vehicles, safety deposit boxes and buildings.

Decentralized Autonomous Organizations

Here, we get into what is perhaps the holy grail, the thing that has the murkiest definition of all: decentralized autonomous organizations, and their corporate subclass, decentralized autonomous corporations (or, more recently, “companies”). The ideal of a decentralized autonomous organization is easy to describe: it is an entity that lives on the internet and exists autonomously, but also heavily relies on hiring individuals to perform certain tasks that the automaton itself cannot do.

Given the above, the important part of the definition is actually to focus on what a DAO is not, and what is not a DAO and is instead either a DO, a DA or an automated agent/AI. First of all, let’s consider DAs. The main difference between a DA and a DAO is that a DAO has internal capital; that is, a DAO contains some kind of internal property that is valuable in some way, and it has the ability to use that property as a mechanism for rewarding certain activities. BitTorrent has no internal property, and Bitcloud/Maidsafe-like systems have reputation but that reputation is not a saleable asset. Bitcoin and Namecoin, on the other hand, do. However, plain old DOs also have internal capital, as do autonomous agents.

Second, we can look at DOs. The obvious difference between a DO and a DAO, and the one inherent in the language, is the word “autonomous”; that is, in a DO the humans are the ones making the decisions, and a DAO is something that, in some fashion, makes decisions for itself. This is a surprisingly tricky distinction to define because, as dictatorships are always keen to point out, there is really no difference between a certain set of actors making decisions directly and that set of actors controlling all of the information through which decisions are made. In Bitcoin, a 51% attack between a small number of mining pools can make the blockchain reverse transactions, and in a hypothetical decentralized autonomous corporation the providers of the data inputs can all collude to make the DAC think that sending all of its money to 1FxkfJQLJTXpW6QmxGT6oF43ZH959ns8Cq constitutes paying for a million nodes’ worth of computing power for ten years. However, there is obviously a meaningful distinction between the two, and so we do need to define it.

My own effort at defining the difference is as follows. DOs and DAOs are both vulnerable to collusion attacks, where (in the best case) a majority or (in worse cases) a significant percentage of a certain type of members collude to specifically direct the D*O’s activity. However, the difference is this: in a DAO collusion attacks are treated as a bug, whereas in a DO they are a feature. In a democracy, for example, the whole point is that a plurality of members choose what they like best and that solution gets executed; in Bitcoin’s on the other hand, the “default” behavior that happens when everyone acts according to individual interest without any desire for a specific outcome is the intent, and a 51% attack to favor a specific blockchain is an aberration. This appeal to social consensus is similar to the definition of a government: if a local gang starts charging a property tax to all shopowners, it may even get away with it in certain parts of the world, but no significant portion of the population will treat it as legitimate, whereas if a government starts doing the same the public response will be tilted in the other direction.

Bitcoin is an interesting case here. In general, it seems to be much closer to a DAO than a DO. However, there was one incident in 2013 where the reality proved to be rather different. What happened was that an exceptional block was (at least we hope) accidentally produced, which was treated as valid according to the BitcoinQt 0.8 clients, but invalid according to the rules of BitcoinQt 0.7. The blockchain forked, with some nodes following the blockchain after this exceptional block (we’ll call this chain B1), and the other nodes that saw that block as invalid working on a separate blockchain (which we’ll call B2). Most mining pools had upgraded to BitcoinQt 0.8, so they followed B1, but most users were still on 0.7 and so followed B2. The mining pool operators came together on IRC chat, and agreed to switch their pools to mining on B2, since that outcome would be simpler for users because it would not require them to upgrade, and after six hours the B2 chain overtook B1 as a result of this deliberate action, and B1 fell away. Thus, in this case, there was a deliberate 51% attack which was seen by the community as legitimate, making Bitcoin a DO rather than a DAO. In most cases, however, this does not happen, so the best way to classify Bitcoin would be as a DAO with an imperfection in its implementation of autonomy.

However, others are not content to classify Bitcoin as a DAO, because it is not really smart enough. Bitcoin does not think, it does not go out and “hire” people with the exception of the mining protocol, and it follows simple rules the upgrading process for which is more DO-like than DAO-like. People with this view would see a DAO as something that has a large degree of autonomous intelligence of its own. However, the issue with this view is that there must be a distinction made between a DAO and an AA/AI. The distinction here is arguably this: an AI is completely autonomous, whereas a DAO still requires heavy involvement from humans specifically interacting according to a protocol defined by the DAO in order to operate. We can classify DAOs, DOs (and plain old Os), AIs and a fourth category, plain old robots, according to a good old quadrant chart, with another quadrant chart to classify entities that do not have internal capital thus altogether making a cube:

DAOs == automation at the center, humans at the edges. Thus, on the whole, it makes most sense to see Bitcoin and Namecoin as DAOs, albeit ones that barely cross the threshold from the DA mark. The other important distinction is internal capital; a DAO without internal capital is a DA and an organization without internal capital is a forum; the G8, for example, would qualify as a forum. DCs in the graph above are “decentralized communities”; an example of that might be something like a decentralized Reddit, where there is a decentralized platform, but there is also a community around that platform, and it is somewhat ambiguous whether the community or the protocol is truly “in charge”.

Decentralized Autonomous Corporations

Decentralized autonomous corporations/companies are a smaller topic, because they are basically a subclass of DAOs, but they are worth mentioning. Since the main exponent of DAC as terminology is Daniel Larimer, we will borrow as a definition the point that he himself consistently promotes: a DAC pays dividends. That is, there is a concept of shares in a DAC which are purchaseable and tradeable in some fashion, and those shares potentially entitle their holders to continual receipts based on the DAC’s success. A DAO is non-profit; though you can make money in a DAO, the way to do that is by participating in its ecosystem and not by providing investment into the DAO itself. Obviously, this distinction is a murky one; all DAOs contain internal capital that can be owned, and the value of that internal capital can easily go up as the DAO becomes more powerful/popular, so a large portion of DAOs are inevitably going to be DAC-like to some extent.

Thus, the distinction is more of a fluid one and hinges on emphasis: to what extent are dividends the main point, and to what extent is it about earning tokens by participation? Also, to what extent does the concept of a “share” exist as opposed to simple virtual property? For example, a membership on a nonprofit board is not really a share, because membership frequently gets granted and confiscated at will, something which would be unacceptable for something classified as investable property, and a bitcoin is not a share because a bitcoin does not entitle you to any claim on profits or decision-making ability inside the system, whereas a share in a corporation definitely is a share. In the end, perhaps the distinction might ultimately be the surprisingly obscure point of whether or not the profit mechanism and the consensus mechanism are the same thing.

The above definitions are still not close to complete; there will likely be gray areas and holes in them, and exactly what kind of automation a DO must have before it becomes a DAO is a very hard question to answer. Additionally, there is also the question of how all of these things should be built. An AI, for example, should likely exist as a network of private servers, each one running often proprietary local code, whereas a DO should be fully open source and blockchain-based. Between those two extremes, there is a large number of different paradigms to pursue. How much of the intelligence should be in the core code? Should genetic algorithms be used for updating code, or should it be futarchy or some voting or vetting mechanism based on individuals? Should membership be corporate-style, with sellable and transferable shares, or nonprofit-style, where members can vote other members in and out? Should blockchains be proof of work, proof of stake, or reputation-based? Should DAOs try to maintain balances in other currencies, or should they only reward behavior by issuing their own internal token? These are all hard problems and we have only just begun scratching the surface of them.

Serpent upgrades: More Fun Stuff

For an intro tutorial to Serpent, see http://blog.ethereum.org/2014/04/10/pyethereum-and-serpent-programming-guide-2/

Over the past two weeks our primary focus has been getting all of the clients updated to PoC5 compatibility, and it definitely has been a long road. Among the changes to the VM include:

  • The new init/code mechanism: basically, when you create a contract, the code provided will execute immediately, and then the return value of that code will be what becomes the contract’s code. This allows us to have contract initialization code, but still keep to the same format of [nonce, price, gas, to, value, data] for both transactions and contract creation, also making it easier to create new contracts via forwarding contracts
  • Reordering transaction and contract data: the order is now [nonce, price, gas, to, value, data] in transactions and [gas, to, value, datain, datainsz, dataout, dataoutsz] in messages. Note that Serpent retains the send(to, value, gas), o = msg(to, value, gas, datain, datainsz) and o = msg(to, value, gas, datain, datainsz, dataoutsz) parameters.
  • Fee adjustments: transaction creation now has a fee of 500 gas, and several other fees were updated.
  • The CODECOPY and CALLDATACOPY opcodes: CODECOPY takes code_index, mem_index, len as arguments, and copies the code from code_index ... code_index+len-1 to memory mem_index ... mem_index+len-1. These are very useful when combined with init/code. There is also now CODESIZE.

The largest changes, however, have been to the architecture surrounding the protocol. On the GUI side, the C++ and Go clients are evolving rapidly, and we will see more updates from that side coming very shortly. If you have been following Ethereum closely, you have likely seen Denny’s Lotto, a full implementation of a lottery, plus GUI, written and executed inside the C++ client. From here on, the C++ client will shift toward being a more developer-oriented tool, whereas the Go client will start to focus on being a user-facing application (or rather, meta-application). On the compiler side, Serpent has undergone a number of substantial improvements.

First, the code. You can peek into the Serpent compiler under the hood and you will be able to see all of the functions available, together with their precise translations into EVM code. For example, we have:

72:     ['access', 2, 1,
73:         ['', '', 32, 'MUL', 'ADD', 'MLOAD']],

This means that what access(x,y) is actually doing under the hood is it’s recursively compiling whatever x and y actually are, and then loading the memory at index x + y * 32; hence, x is the pointer to the start of the array and y is the index. This code structure has been around since PoC4, but now I have upgraded the meta-language used to describe translations even further, so as to include even if, while and init/code in this construction (before they were special cases); now, only set and seq remain as special cases, and if I wanted to I could even remove seq by reimplementing it as a rewrite rule.

The largest changes so far have been for PoC5 compatibility. For example, if you run serpent compile_to_assembly 'return(msg.data[0]*2)', you will see:

["$begincode_0.endcode_0", "DUP", "MSIZE", "SWAP", "MSIZE", "$begincode_0", "CALLDATACOPY", "RETURN", "~begincode_0", "#CODE_BEGIN", 2, 0, "CALLDATALOAD", "MUL", "MSIZE", "SWAP", "MSIZE", "MSTORE", 32, "SWAP", "RETURN", "#CODE_END", "~endcode_0"]

The actual code there is just:

[2, 0, "CALLDATALOAD", "MUL", "MSIZE", "SWAP", "MSIZE", "MSTORE", 32, "SWAP", "RETURN"]

If you want to see what’s going on here, suppose that a message is coming in with its first datum being 5. We thus have:

2 -> Stack: [2]
0 -> Stack: [2, 0]
CALLDATALOAD -> Stack: [2,5]
MUL -> Stack: [10]
MSIZE -> Stack: [10, 0]
SWAP -> Stack: [0, 10]
MSIZE -> Stack: [0, 10, 0]
MSTORE -> Stack: [0], Memory: [0, 0, 0 ... 10]
32 -> Stack: [0, 32], Memory: [0, 0, 0 ... 10]
SWAP -> Stack: [32, 0], Memory: [0, 0, 0 ... 10]
RETURN

The last RETURN returns the 32 memory bytes starting from 0, or [0, 0, 0 ... 10], or the number 10.

Now, let’s analyze the wrapper code.

["$begincode_0.endcode_0", "DUP", "MSIZE", "SWAP", "MSIZE", "$begincode_0", "CALLDATACOPY", "RETURN", "~begincode_0", "#CODE_BEGIN", ..... , "#CODE_END", "~endcode_0"]

I elided the inner code explained above to make things clearer. The first thing we see are two labels, ~begincode_0 and ~endcode_0, and the #CODE_BEGIN and #CODE_END guards. The labels mark the beginning and end of the inner code, and the guards are there for the later stages of the compiler, which understands that everything between the guards should be compiled as if it is a separate program. Now, let’s look at the first parts of the code. In this case, we have ~begincode_0 at position 10 and ~endcode_0 at position 24 in the final code. $begincode_0 and $endcode_0 are used to refer to these positions, and $begincode_0.endcode_0 refers to the length of the interval between them, 14. Now, remember that during contract initialization the call data is the code that you’re feeding in. Thus, we have:

14 -> Stack: [14]
DUP -> Stack: [14, 14]
MSIZE -> Stack: [14, 14, 0]
SWAP -> Stack: [14, 0, 14]
MSIZE -> Stack: [14, 0, 14, 0]
10 -> Stack: [14, 0, 14, 0, 10]
CALLDATACOPY -> Stack: [14, 0] Memory: [ ... ]
RETURN

Notice how the first half of the code cleverly set up the stack so that it would push the inner code into memory indices 0…13, and then immediately return that chunk of memory. In the final compiled code, 600e515b525b600a37f26002600035025b525b54602052f2, the inner code sits nicely to the right of the initializer code that simply returns it. In more complex contracts, initializers can also serve functions like setting certain storage slots to values, or even calling or creating other contracts.

Now, let us introduce the latest and most fun feature of Serpent: imports. One common use case in contract land is that you want to give a contract the ability to spawn off new contracts. Problem is, how to you put the code for the spawned contracts into the spawner contracts? Before, the only solution was the uncomfortable approach of compiling the newer contracts first, and then putting the compiled code into an array. Now, we have a better solution: import.

Put the following into returnten.se:

x = create(tx.gas - 100, 0, import(mul2.se))
return(msg(x,0,tx.gas-100,[5],1))

Now, put the following into mul2.se:

return(msg.data[0]*2)

Now, if you serpent compile returnten.se and run the contract, you notice that, voila, it returns ten. The reason why is obvious. The returnten.se contract creates an instance of the mul2.se contract, and then calls it with the value 5. mul2.se, as the name suggests, is a doubler, and so it returns 5*2 = 10. Note that import is not a function in the standard sense; x = import('123.se') will fail, and import only works in the very specific context of create.

Now, suppose you are creating a 1000-line monster contract and want to split it up into files. To do that, we use inset. Into outer.se, put:

if msg.data[0] == 1:
  inset(inner.se)

And into inner.se, put:

return(3)

Running serpent compile outer.se gives you a nice piece of compiled code that returns 3 if the msg.data[0] argument is equal to one. And that’s all there is to it.

Upcoming updates to Serpent include:

  • An improvement of this mechanism so it doesn’t load the inner code twice if you try to use import twice with the same filename
  • String literals
  • Space and code-efficiency improvements for array literals
  • A debugging decorator (ie. a compiling function which tells you what lines of Serpent correspond to what bytes of compiled code)

In the short term, though, my own effort will focus on bugfixes, a cross-client test suite, and continued work on ethereumjs-lib.

Decentralized Protocol Monetization and Forks

The idea of releasing a new currency as a mechanism for funding protocol development is perhaps one of the most interesting economic innovations to come out of the cryptocurrency space. In the past twenty years, we have seen a growing centralization in the protocols that underlie the internet, with the rise of proprietary chat systems and social networks like Facebook, and a large part of the reason for this trend has been the need for monetization; if Facebook was cryptographically secure and decentralized, the developers would have no way to make money by data mining their users’ activities and taking a 30% cut of their internal currency, and so decentralized alternatives to Facebook have largely fizzled due to lack of institutional support and funding. With decentralized protocols, however, we have discovered a new mechanism for monetizing them: create internal assets, and sell them to pay for the development of the protocol.

In general, so far we know of two classes of “internal assets” that can be sold in this way; first, there is the idea of creating an internal token system, a crypto-fuel with a floating price that has some value in the network, and second, one can introduce name registrations; for example, a decentralized Twitter might fund itself by building in its own decentralized username registration mechanism similar to Namecoin and selling off the 1-4 letter names. This new monetization model is powerful, and in the first of the two above-described implementations already has a number of proven successes, but it is also incredibly non-intrusive – it requires no licensing schemes, proprietary software, crippleware or privacy infringement, and in fact no one actually has to explicitly “pay” for anything at all (if you buy tokens you are just swapping into a different asset, which may well even go up in value relative to other assets). However, in this model there is one concern that many people have raised, and that is the question of forks. In short, if one releases a new decentralized protocol that is based on a token system, why won’t someone else release a fork with either their own token system, or a token system that is somehow tied to an asset with an existing userbase, and if one releases a decentralized Twitter with a built-in name registration system why won’t someone release a fork that points to their own name registration system, or even the original Namecoin?

In traditional business, there are two solutions to the problem. One is to give up the idea of making everything open-source, and keep at least the latest version of the client proprietary. The other is to release the protocol for free, and then sell services. Of course, both approaches have their own very well-understood flaws. In the context of a decentralized blockchain application, most of the benefits of decentralization are lost when the code becomes proprietary – with a proprietary mining algorithm, for example, there is no way to prove that it does not have a backdoor for its developers, and is therefore equivalent to the developers simply running a centralized server and asking the community to trust them. The second approach, selling services, is also flawed; first, the revenue is in most cases vastly insufficient, and second, it incentivizes the organization to produce only a minimal decentralized protocol in order to then sell centralized services on top, rather than building up an entire decentralized ecosystem.

Many decentralized projects are pursuing neither of these strategies; for example, Ethereum itself is 100% open source, and have been since even before the day that it publicly launched. Many protocol organizations, including our own, are interested in transforming themselves into “decentralized autonomous organizations”, which necessarily implies a very high degree of transparency. Given this, what is a decentralized protocol’s “moat” against forks? What stops another group from taking all of our code and research ready-made and creating their own version of the blockchain, perhaps with one or two superior features (or simply having a large endowment and dumping it all into superior marketing), and taking us over? The question is a difficult one, but it has a number of interesting answers, both in terms of Ethereum specifically and decentralized protocols as a whole.

On Flimsy Moats and Dictators

In order to answer the question, it is important to first understand that, in the space of tech companies and especially social networking startups, a large number of them are literally backed by almost nothing but social consensus. Theoretically, it is entirely possible for all of the employees at Snapchat, Tinder, Twitter or any other such startup to all suddenly agree to quit and start their own business, completely rebuild all of the software from scratch within months, and then immediately proceed to build a superior product. The only reason why such companies have any valuation at all is a set of two coordination problems: the problem of getting all employees to quit at the same time, and the problem of getting all of the customers to simultaneously move over onto the new network. In the context of a service like Dropbox, the latter issue does not exist; because Dropbox is just as useful to each individual if one other person is using it or a million, there is no reason why people can’t move over a few at a time. In the context of a social network, which is useless unless everyone else is already on it, the problem is fundamental.

In the abstract, this may seem like a flimsy justification for why tech companies are valuable; when thinking about something that represents billions of dollars of value, one naturally expects that value to be backed up by something tangible like physical resources or government force, not just some ethereal instantiation of the fact that it’s hard for large groups of people to suddenly move from one social configuration to another. In reality, however, even physical resources and government force are backed by nothing but a social coordination problem – if 70% of the victims of a dictatorship were to simultaneously rise up against their dictator, the government would get toppled pretty quickly, and yet most dictators even running rather brutally oppressive regimes are quite comfortable sitting in their lofty thrones knowing that such a thing will almost certainly not happen.

Given this background in theory, what exactly are the social coordination problems backing up a decentralized blockchain? What exactly is the “moat” that is backing up the value of the “official” Ethereum blockchain or Mastercoin state transition system, and ether as a mechanism of storing value and paying for transaction fees, as opposed to alternate clones like “aethereum“? Specifically, what are the necessary factors that make the original version of a given decentralized protocol superior, when all of its underlying features can easily be cloned, and even improved upon as soon as a group discovers even one flaw in the original (in the case of Bitcoin, for example, one can trivially improve the Bitcoin protocol by removing the requirement for multisig spending transactions to have an extraneous zero in the spending script code, an anti-feature which was introduced accidentally)? As it turns out, there is quite a lot.

Teams

First of all, every project has a core development team. In fact, this aspect is actually stronger in the case of a decentralized token system than a traditional tech company. While in a traditional tech company, there might be only a very small number of people with shares in the company and who are thus incentivized to stick with it and see it succeed, in the case of a decentralized token system there are dozens or even hundreds of people holding tokens associated with the project; in fact, many people actually choose to be paid predominantly in tokens. In the case of Ethereum, for example, the size of the list of people who will be receiving ether as compensation for work done currently stands at sixty-eight, and will increase even further as time goes on. And all of these tokens are, of course, untradeable until the protocol actually launches, so all of the token holders are strongly incentivized to do their best to ensure that the system does as well as possible. Thus, the team, the set of people who know the most about how the protocol works from the experience of having actually developed it, is a decentralized project’s core asset that competitive spinoffs cannot so easily “fork” and replicate, and it is the team that will be responsible for much of the rest of the project’s “moat”.

Network Effects of Exposure

The simplest reason why people will use the original blockchain and not a fork is simple: it’s the default. People hear about Bitcoin first, so they go to bitcoin.org and download the Bitcoin client, and use Bitcoin to buy and sell goods and services, not Bitcoin Scrypt. For the same reason, people use the official version of most open-source projects and not any of the thousands of forks, buy music, books and movies instead of trying to download them via torrents, and use popular Bitcoin wallets instead of less popular ones. Any fork of a given protocol necessarily comes after the original, and is therefore much less likely to gain media attention.

Moral Pressure

Another important reason why the original version of a protocol is more likely to gain media attention than a fork is plain old public morality: people believe that the developers of a project deserve to get compensated, and so a fork which is developed with the primary purpose of depriving the developers of compensation is likely to be viewed negatively, or at least less favorably, by many people. This moral effect can be a very powerful one, and contributes heavily to the original protocol’s greater exposure; the best empirical evidence for this is likely the success of services like Netflix over filesharing-based alternatives.

At the same time, however, if the original developers of a protocol start taking development in an undesirable direction (eg. introducing backdoors, introducing excessively intrusive monetization vehicles, or even just being too plain slow), then the moral effect can rapidly turn on its head and even support the first credible effort to try to wrest away a project from its creators; following the prior example, the pertinent example here is the media success of the Pirate Bay and Popcorn Time. Thus, moral pressure can work both for and against a decentralized protocol, and it is the protocol developers’ responsibility to ensure that the community opinion of their project remains positive, and serves as an important check-and-balance to make sure that the core team behind a project continues to move the project forward at a solid pace and in an agreeable direction.

Network Effects of Currency Unit Liquidity

One argument that is often raised against forks of Bitcoin is the idea of liquidity, or specifically market depth: smaller currencies are inherently weaker than larger currencies because there are fewer people buying and selling them, and so you will move the price much more if you try to sell a large amount. However, this argument is only important up to a certain point; once a currency reaches a sufficient size, it has enough market depth to cover all ordinary usage, and so additional depth provides little value. Hence, this network effect provides a moderately strong edge against forks with a new token system, which will have very low market depth to start off, although at the cost of a slight disadvantage against forks that tie in existing large currencies via two-way-pegging mechanisms.

Ecosystemic Network Effects

An important feature of decentralized protocols, and social protocols in general, is that they also build ecosystems. On a social network, for example, there is a one-dimensional network effect: a social network is more useful if more people use it. With a currency, that effect becomes two-dimensional: a currency attracts more users if there are more merchants, and more merchants if there are more users. Once development effort, security and liquidity come into play, this increases to three to six dimensions. All of these interdependencies make it hard for a new version of a social network to bore its way into mainstream acceptance, as initially it starts off with nothing.

In the case of Ethereum, the tightly integrated nature of the currency system actually makes the network effect in some respects highly multi-dimensional. The relevant property of the Ethereum architecture is the first-class-citizen property of contracts: contracts can interact with, send and receive messages from and hold accounts with other contracts much like external accounts can. This allows you to cleverly pull together long chains of contracts and applications, using contracts of different types at each step of the interaction process. For example, I might hold some shares of a decentralized autonomous organization (contract A), where the shares are held on a decentralized market (contract B) in a multisignature account (contract C) for added security. The co-signer of said multisig account is paranoid about quantum computing, so he uses custom cryptography (contract D) based on verifying Lamport signatures for authentication. The organization would then store some of its funds in a USD-pegged asset using a financial derivatives market (contract F) using a combination of centralized and decentralized data feeds (contracts G, H, I), and internally uses a name registration system (contract J) to store all of the functions that it calls. A single transaction may end up calling all of these contracts multiple times.

Liquid markets for on-blockchain assets, liquid markets for message publication, and a robust ecosystem of DAOs, decentralized exchanges, financial markets and data feeds all support each other and make the Ethereum blockchain stronger. The Ethereum blockchain is not just a blockchain; it’s really one large decentralized computer where all of the components are tightly linked together, and each component provides additional tools for other components to play with.

Bugs and Attacks

This is a small point, but an important one. There is always a risk that either the protocol or the client implementation will be flawed in some way. As hard as the Bitcoin developers have tried, the bitcoind source code has had problems crop up over the years, and twice in Bitcoin’s history (specifically, the integer overflow exploit in 2010 and the fork in 2013) such problems have even led to a consensus failure that required manual resolution. In theory, developers of every protocol try as hard as they can to ensure that bugs never happen in the first place. In practice, of course, there is always a chance that something will slip by, the price will start crashing ten or twenty percent within an hour, and it will be up to the developers, the miners and the large businesses to quickly push out and coordinate a fix. Sometimes, such errors may not even be the protocol’s fault; a massive megacorporate or government-sponsored 51% attack or a globally coordinated distributed denial of service on the entire network are also possibilities, and might need special measures to be dealt with. Thus, as decentralized as peer to peer protocols aspire to be, ultimately they do benefit considerably from some degree of institutional support in times of crisis – support that the original developers who understand the protocol and software best are the best-equipped to provide.

Protocol upgrades

Ethereum 1.0 is far from perfect, and between our discussions on the development roadmap and the Hard Problems of Cryptocurrency we have been very open about admitting this. There are plenty of ways that blockchain technology could be improved, ranging from research on price-stabilized currencies to better fee structures, alternative consensus models and, as a holy grail, multi-blockchain architectures or SCIP. However, the intricacies of actually coming up with the math and then implementing these mechanisms, are in many cases even figuring out whether or not they are even possible, are sufficiently complex that we have decided there is a large list of features we are simply not going to do for Ethereum 1.0. To that end, we have established the long-term roadmap that we will release Ethereum 1.0 in Q4 2014 at the latest, and at the same time we have already started to set up efforts to research the kinds of improvements that we can theoretically add, specifically in terms of scalability, with a plan to crystallize them into Ethereum 2.0 at some point around 2016. Ethereum 2.0 will use “ether 2.0” as its currency, where the main initial mechanism for obtaining a unit of ether 2.0 is simply to provably destroy a unit of ether 1.0.

Thus, the currency inside of a protocol is backed not just by the utility and network effects of the current implementation of that protocol, but also the promise of better future versions of the protocol to come. Of course, cryptocurrency protocols are hard to change, and in practice Bitcoin has proven very difficult to change in the short term, but more large-scale re-architectures are actually somewhat easier to implement than small changes when one looks at the ratio of effort to effect. We have already seen the Master Protocol make several upgrades, and we will likely see Ethereum 2.0, 3.0 and perhaps even further over the next few years and decades.

What’s the Point?

Finally, the most important argument of all is, what’s the point of a fork? In the case of Bitcoin, there are many reasons to fork the code – you might want to add support for more transaction types, change the currency supply, replace the currency with a centralized alternative backed by the US dollar, or change the type of cryptography used. If a protocol is correctly generalized, however, there simply is no way to improve that can’t be replicated inside the protocol itself. For example, if you are using Ripple then you can use Ripple equally easily to store XRP, cryptocurrencies, fiat currencies, local community currencies or Little Bobby’s Magic Token Points. Hence, concerns about optimal monetary policy, politicization or depoliticization of money or many of the other debates surrounding Bitcoin have no bearing on the success of the Ripple protocol itself. In the case of Ethereum, the protocol has a generic programming language, making the system even more malleable: if someone comes up with a blockchain-based system that is better than Ethereum in some fashion (with the exception of secure near-instant block times), then someone else can fork it right back inside of Ethereum itself by simply implementing it as a contract. This fork would immediately benefit from Ethereum’s ecosystemic network effects, allowing users to benefit from both the superior feature and the ability to interface seamlessly and directly with an existing ecosystem of liquid markets, data feeds and DAOs. Using this power of the contract mechanism, Ethereum will be able to contain side-chains of Bitcoin, Litecoin and Dogecoin (yes, even Scrypt-based coins can be turned into side-chains via computational stacktraces and an economically incentivized challenge-response protocol), name registrations, post-quantum cryptography and an unlimited number of other features.

Thus, on the whole decentralized protocols lie in an interesting place in the modern economy. On the one hand, much like Bitcoin itself, they are in a very clear way “backed by nothing”. On the other hand, they actually have quite a powerful backing underneath, and one that is difficult to unseat; in practice, we have seen very few examples of any open source software fork unseating the original, both in the cryptocurrency space and outside of it. Nothing has unseated Bitcoin, nothing has unseated Litecoin and nothing has unseated Dogecoin. The only forks that do gain serious community acceptance are the ones that add a large body of new features, and these forks always succeed in carving out a niche of their own. Fortunately, we still have many decades to go in seeing exactly how the decentralized protocol ecosystem is going to play out.

Pyethereum and Serpent Programming Guide

The content of this tutorial is intended to apply to PoC5. Most of the instructions given below will not work in the older PoC4 implementations of AlethZero (C++) and Ethereal (Go)

Over the last few weeks, we have made a large number of changes to the Ethereum protocol. POC4, introducing a large body of changes made by Gavin Wood and myself, was announced as an informal description two weeks ago, and has been formally specified in Gavin Wood’s “yellow paper” at http://gavwood.com/Paper.pdf. The protocol spec did change substantially, but at the same time things are solidifying; we know why we want transactions to pay fees instead of contracts, so that’s not likely to change, we know that code and data will be separate, and the byte-based code and memory and 32-byte-block-based stack and storage are unlikely to change, and we know that the workings of the EVM in general will be similar to what they are now instead of some kind of elaborate Merkle-code-tree construction. POC4 has given myself what I wanted out of Ethereum Script 2, Gavin a much more optimization-friendly VM architecture, and users a shiny new currency. Meanwhile, Chen Houwu, Heiko Kees and Konrad Feldmeier have taken the lead as our main Python developers, and the networking side of the pyethereum client is getting to the point where it is getting ready to talk to Go and C++. At the same time, aside from all of the managerial tasks that are part and parcel of having a key role in a large project, I have taken it upon myself to bring up to speed the pyethereum VM implementation and the compiler for the HLL programming language.

The purpose of this post will be to provide an in-depth technical tutorial into the workings of pyethereum and Serpent, and show you how you can start writing the tools to build your own contracts and applications. The Bitcoin Expo hackathon is happening today and tomorrow, so feel free to make an Ethereum contract your project if you are among those attending.

First of all, importantly, HLL is no longer called HLL; the language is now called Serpent. Why? Because it’s basically Python.

With recent upgrades to the compiler, Serpent is now a highly feature-filled programming language, with powerful features including:

  • Arrays (eg. x[0] = 123)
  • Array literals (eg. x = [ 34, 56, 78 ])
  • Nested arrays (eg. z = [ 34, [ 5, 6 ], y ])
  • Hex support (eg. receiving_address = 0xb156066c2978d7b9188f2467b815d4c62ae32fe2)
  • String support (eg. x = "cow")
  • Inline message calling (eg. usdprice = eth * msg(ethcontract,0,tx.gas-100,[500],1))
  • Out of line message calling (eg. msg(multifeedcontract,0,tx.gas-100,inparray,5,outarray,5))
  • Simple value sending operation (eg. send(receiver, value, tx.gas-100))
  • Returning values (eg. return(45) and return([10,20,30,40],4))
  • Treating message data and storage as arrays (eg. contract.storage[1000] = msg.data[0])
  • Byte arrays (eg. x = bytes(100), setch(x,45,"c")), y = getch(x,45)

The intent of the Serpent language is to make programming smart contracts and decetralized applications in Ethereum as easy as programming boring command line apps is in Python. The language is designed to be maximally clean and maximally simple, combining the benefits of a compiled language with an easy-to-use coding experience. Just the logic, and nothing but the logic. Unfortunately, floating point numbers are missing, as are higher-order constructs like list comprehensions and closures, but aside from that Serpent has basically everything that you need.

Getting Started

So how do you code in Serpent? The first step is to set up the development and execution environment. To do this, first download two libraries: pyethereum and serpent. The simplest way to download is to either download the zip files from Github and unpack them, or run git clone http://github.com/ethereum/pyethereum and git clone http://github.com/ethereum/serpent. Then, enter the pyethereum directory, and run sudo python setup.py install to install pyethereum to your system, and do the same with serpent.

Now that the software is downloaded, let’s get right to it. To start off, try this:

> serpent compile_to_assembly 'x = 5'
["$begincode_0.endcode_0", "DUP", "MSIZE", "SWAP", "MSIZE", "$begincode_0", "CALLDATACOPY", "RETURN", "~begincode_0", "#CODE_BEGIN", 5, 0, "MSTORE", "#CODE_END", "~endcode_0"]

The compile_to_assembly instruction compiles the code down into an intermediate human-readable “assembly language” format rather than plain old bytecode. Using plain old serpent compile would give you the much more incomprehensible but compact 6005515b525b600a37f26005600054. In this case, the “core” of the code is [5, 0, "MSTORE"], putting the value 5 into memory slot 0, and the rest of the code basically says to return a contract containing that code. Another command that you may find useful is serpent get_vars; this will give you a list of all the variables together with their associated memory indices. In this case, you get {'x': 0}, meaning that the compiler is choosing to use the memory index 0 to store the variable x. The last interesting command is parse to convert Serpent into an intermediate high-level parse tree. Now, since Serpent is a programming language, we want to run programs, and so ideally we would like to actually create contracts and run them as quickly as possible. Let’s try that. First, open a file, call it “namecoin.se“, and put the following code into it:

if !contract.storage[msg.data[0]]:
    contract.storage[msg.data[0]] = msg.data[1]
    return(1)
else:
    return(0)

This is the two-line Namecoin example that we love so much, but embellished with return values to make it easier to work with for this tutorial. Typing serpent compile namecoin.se should give:

6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f2

Now, let’s see if we can actually get the code running. To do that, the first step is actually to create for ourselves an account. The process here is almost exactly the same as in my Python Bitcoin library pybitcointools; in general, anyone who is familiar with pybitcointools should feel right at home in pyethereum, although unfortunately in pyethereum it was not really practical to stick to pybitcointools’ “no classes” mantra in the code. The first step is to generate a private key:

> pyethtool sha3 cow
c85ef7d79691fe79573b1a7064c19c1a9819ebdbd1faaab1a8ec92344438aaf4

In production code, you should obviously replace “cow” with an actually secure password. If you want your account to be a “brainwallet” that you can easily remember, my main advice is to prepend a username, eg. “vbuterin:bl@hbl@hm0nk33y#!$!%”, ensuring that attackers need to target you individually instead of performing a blanket attack on everyone simultaneously; assuming 10000 brainwallet users this reduces your risk from a trial-and-error attack by 99.99%.

If you want to use your key later, on any standard Linux shell you can also type in key=`pyethtool sha3 cow`, and then use $key to use the key thereafter. We’ll use that format here from now on, so if you are following along then you should also do both:

> key=`pyethtool sha3 cow`
> code=`serpent compile namecoin.se`

So now, let’s keep going.

> addr=`pyethtool privtoaddr $key`
> echo $addr
cd2a3d9f938e13cd947ec05abc7fe734df8dd826

Now, we create a new genesis block, and we’ll set the initial endowment to 1018 wei (1 ether) for your address.

> genesis=`pyethtool mkgenesis $addr 1000000000000000000`
> echo $genesis
f8b2f8aea00000000000000000000000000000000000000000000000000000000000000000a01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347940000000000000000000000000000000000000000a0bcddd284bf396739c224dba0411566c891c32115feb998a3e2b4e61f3f35582a80834000008087038d7ea4c68000830f4240808080a004994f67dc55b09e814ab7ffc8df3686b4afb2bb53e60eae97ef043fe03fb829c0c0

Now that we have that out of the way, we can get to actually doing stuff to the block. The only way to do anything in a blockchain-based architecture, in general, is to create and apply a transaction. Here, we will need multiple transactions: the first to create the contract, and then the latter ones to actually use it. Here’s contract creation:

> unsignedtx=`pyethtool mkcontract 0 0 $code`
> echo $unsignedtx
f83c8085e8d4a510008227108080af6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f2
> tx=`pyethtool sign $unsignedtx $key`
> echo $tx
f87f8085e8d4a510008227108080af6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f21ca04565b5a48b29ef623ad2caffe0917a3fc6a6f1b50f1df06876f3caa6fb4957c6a0123c928257c1f248fb3d362c125a0aea091ab08467efb52f8c3676ca73d727bf

Or, the easier way:

> tx=`pyethtool mkcontract 0 0 $code | pyethtool -s sign $key`
> echo $tx
f87f8085e8d4a510008227108080af6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f21ca04565b5a48b29ef623ad2caffe0917a3fc6a6f1b50f1df06876f3caa6fb4957c6a0123c928257c1f248fb3d362c125a0aea091ab08467efb52f8c3676ca73d727bf

The first field in mkcontract is a nonce, which must be equal to the number of transactions you already sent from that account. The purpose of requiring a nonce is to prevent replay attacks; otherwise, if you sent Bob 200 ether, Bob could simply replay that transaction over and over again until you run out of money, whereas here due to the nonce requirement the transaction can only go through once. The second field is the amount of ether to send (in the case of contract creation, the amount of ether to initially provide to the contract), and the third field is the code. Note that the Transaction.contract function call also has two more fields between value and recipient: gasprice and startgas. Pyethtool is nice to you and initializes these values to 1 szabo (ie. 1012 wei or one millionth of an ether) per gas and 10000 gas, respectively. This will give you a theoretical maximum of 10000 computational steps for the code to run, although in practice it may run out after 1000 if you use many expensive operations. Finally, once you create the transaction, you need to sign it with your private key.

Once that’s done, we just, well:

> pyethtool applytx $genesis $tx
{"result": "da7ce79725418f4f6e13bf5f520c89cec5f6a974", "block": "f9017ef8d0a00000000000000000000000000000000000000000000000000000000000000000a01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347940000000000000000000000000000000000000000a00bcec36bf7ffc27418b1746986574526efeb09b34f733039749f291f778d4aaca03575f60ad6c929d7c98a50a12ff1ef9b07ecf3182e74962872064648a66f3da0834000008087038d7ea4c68000830f42408204b08080a004994f67dc55b09e814ab7ffc8df3686b4afb2bb53e60eae97ef043fe03fb829f8a9f8a7b881f87f8085e8d4a510008227108080af6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f21ca04565b5a48b29ef623ad2caffe0917a3fc6a6f1b50f1df06876f3caa6fb4957c6a0123c928257c1f248fb3d362c125a0aea091ab08467efb52f8c3676ca73d727bfa00bcec36bf7ffc27418b1746986574526efeb09b34f733039749f291f778d4aac8204b0c0"}

This gives you two values. The first is the address of the contract, and the second is the new block data. Note that the block data does not represent the entire block; there is also the state data hidden in the statedb folder. Hence, if you try to deserialize the block on a fresh machine it likely will not work. From the values returned, set the first value to contract and the second to med so we can use them later. Now, we need to craft a transaction to actually use this contract. Suppose we want to register “george” to 45. To do that, however, we first need to do another annoying chore: package up the data. Fortunately, the serpent compiler has a utility for doing just that:

> data=`echo '["george",45]' | serpent -j encode_datalist`
> echo $data
000000000000000000000000000000000000000000000000000067656f726765000000000000000000000000000000000000000000000000000000000000002d

The namecoin contract takes data in two fields, the key and the value, so we simply put them into a JSON array and use Serpent to encode it. The encoder can accept strings and numbers as the individual elements in the array. Note that unfortunately Python’s JSON decoder requires double quotes for internal strings; "['george',45]" would not work.

Now, we do this:

> tx2=`pyethtool mktx 1 $contract 0 $data | pyethtool -s sign $key`
> echo $tx2
f8a50185e8d4a5100082271094da7ce79725418f4f6e13bf5f520c89cec5f6a97480b840000000000000000000000000000000000000000000000000000067656f726765000000000000000000000000000000000000000000000000000000000000002d1ba064363844c718f0f38907d39508adb2c2b9134e52e7d436fb20965044c01f41c2a0e1123d26cf810c4ef9d397974e2fc336d16e452d71df3c3d7245b40ed12c603b

And:

> pyethtool applytx $med $tx2
{"result": "0000000000000000000000000000000000000000000000000000000000000001", "block": "f9024ef8d0a00000000000000000000000000000000000000000000000000000000000000000a01dcc4de8dec75d7aab85b567b6ccd41ad312451b948a7413f0a142fd40d49347940000000000000000000000000000000000000000a066d2524d921fadb5056983cf4bb215d339cdaeb7048b8913bfdf8fe867eb5682a0d669d3b5cfb150e4ef7f900cc613b0231abc8551544c389ddcd6668f784c4cb3834000008087038d7ea4c68000830f4240820a8f8080a004994f67dc55b09e814ab7ffc8df3686b4afb2bb53e60eae97ef043fe03fb829f90178f8a7b881f87f8085e8d4a510008227108080af6025515b525b600a37f260003556601b596020356000355760015b525b54602052f260255860005b525b54602052f21ca04565b5a48b29ef623ad2caffe0917a3fc6a6f1b50f1df06876f3caa6fb4957c6a0123c928257c1f248fb3d362c125a0aea091ab08467efb52f8c3676ca73d727bfa00bcec36bf7ffc27418b1746986574526efeb09b34f733039749f291f778d4aac8204b0f8cdb8a7f8a50185e8d4a5100082271094da7ce79725418f4f6e13bf5f520c89cec5f6a97480b840000000000000000000000000000000000000000000000000000067656f726765000000000000000000000000000000000000000000000000000000000000002d1ba064363844c718f0f38907d39508adb2c2b9134e52e7d436fb20965044c01f41c2a0e1123d26cf810c4ef9d397974e2fc336d16e452d71df3c3d7245b40ed12c603ba066d2524d921fadb5056983cf4bb215d339cdaeb7048b8913bfdf8fe867eb5682820a8fc0"}

Registration successful! The result here is two values, just as before: the first is the new block state, and the second is the response returned by the contract. Based on the definition of the contract above, “1” means success. Now, just to be sure, let’s set end to the block hex returned by the previous command and peek at the state:

> pyethtool getstate $end
{'nonce': '\x04\x99Og\xdcU\xb0\x9e\x81J\xb7\xff\xc8\xdf6\x86\xb4\xaf\xb2\xbbS\xe6\x0e\xae\x97\xef\x04?\xe0?\xb8)', 'min_gas_price': 1000000000000000L, 'extra_data': '', 'state_root': 'f\xd2RM\x92\x1f\xad\xb5\x05i\x83\xcfK\xb2\x15\xd39\xcd\xae\xb7\x04\x8b\x89\x13\xbf\xdf\x8f\xe8g\xebV\x82', 'difficulty': 4194304L, 'timestamp': 0L, 'number': 0L, 'gas_used': 2703L, 'coinbase': '0000000000000000000000000000000000000000', 'tx_list_root': '\xd6i\xd3\xb5\xcf\xb1P\xe4\xef\x7f\x90\x0c\xc6\x13\xb0#\x1a\xbc\x85QTL8\x9d\xdc\xd6f\x8fxLL\xb3', 'state': {'0000000000000000000000000000000000000000': {'nonce': 0L, 'balance': 2703000000000000L, 'storage': {}, 'code': ''}, 'da7ce79725418f4f6e13bf5f520c89cec5f6a974': {'nonce': 0L, 'balance': 0L, 'storage': {113685359126373L: 45L}, 'code': '60003556601b596020356000355760015b525b54602052f260255860005b525b54602052f2'}, 'cd2a3d9f938e13cd947ec05abc7fe734df8dd826': {'nonce': 2L, 'balance': 997297000000000000L, 'storage': {}, 'code': ''}}, 'uncles_hash': '\x1d\xccM\xe8\xde\xc7]z\xab\x85\xb5g\xb6\xcc\xd4\x1a\xd3\x12E\x1b\x94\x8at\x13\xf0\xa1B\xfd@\xd4\x93G', 'prevhash': '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', 'gas_limit': 1000000L}

You can see the contract account near the beginning of the state description, with “george” registered to 45 as expected. We’re done! As an exercise, try constructing two more transactions, one registering “george” to 60 and another registering “harry” to 80. If you apply them all sequentially after these two, the one registering “george” to 60 should return 0, but the one registering “harry” to 80 should succceed.

Doing it in Python

That’s pyethtool, the command line utility. Now, how does it work using pyethereum itself? As it turns out, it’s surprisingly easy. Here’s the session:

>>> import serpent
>>> from pyethereum import transactions, blocks, processblock, utils
>>> code = serpent.compile(open('namecoin.se').read())
>>> key = utils.sha3('cow')
>>> addr = utils.privtoaddr(key)
>>> genesis = blocks.genesis({ addr: 10**18 })
>>> tx1 = transactions.contract(0,10**12,10000,0,code).sign(key)
>>> result, contract = processblock.apply_tx(genesis,tx1)
>>> tx2 = transactions.Transaction(1,10**12,10000,contract,0,serpent.encode_datalist(['george',45])).sign(key)
>>> result, ans = processblock.apply_tx(genesis,tx2)
>>> serpent.decode_datalist(ans)
[1]
>>> genesis.to_dict()
'nonce': '\x04\x99Og\xdcU\xb0\x9e\x81J\xb7\xff\xc8\xdf6\x86\xb4\xaf\xb2\xbbS\xe6\x0e\xae\x97\xef\x04?\xe0?\xb8)', 'min_gas_price': 1000000000000000L, 'extra_data': '', 'state_root': '', 'difficulty': 4194304, 'timestamp': 0, 'number': 0, 'gas_used': 2712L, 'coinbase': '0000000000000000000000000000000000000000', 'tx_list_root': '\x17\x90\x87\x966\xbdb!\x14|R\xb0& \xb04\x90\xb9bs\x12\x85\x90\xdaB\xed\x83n*\x8eE\x8e', 'state': {'0000000000000000000000000000000000000000': {'nonce': 0L, 'balance': 2712000000000000L, 'storage': {}, 'code': ''}, 'da7ce79725418f4f6e13bf5f520c89cec5f6a974': {'nonce': 0L, 'balance': 0L, 'storage': {113685359126373L: 45L}, 'code': '60003556601e596020356000355760015b525b54602052f260285860005b525b54602052f2'}, 'cd2a3d9f938e13cd947ec05abc7fe734df8dd826': {'nonce': 2L, 'balance': 997288000000000000L, 'storage': {}, 'code': ''}}, 'uncles_hash': '\x1d\xccM\xe8\xde\xc7]z\xab\x85\xb5g\xb6\xcc\xd4\x1a\xd3\x12E\x1b\x94\x8at\x13\xf0\xa1B\xfd@\xd4\x93G', 'prevhash': '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00', 'gas_limit': 1000000}
>>> genesis.get_balance(addr)
997288000000000000L
>>> genesis.get_storage_data(contract,'george')
45L

Another important command is processblock.debug = 1; this starts printing code execution step by step, helping you debug what is wrong in your contract code – or my pyethereum VM or Serpent implementation!

Getting into the Code

So that’s your introduction to how to use pyethereum. Now, let’s get into the most fun part, writing contracts. For reading efficiency, let’s provide the Namecoin contract again:

if !contract.storage[msg.data[0]]:
    contract.storage[msg.data[0]] = msg.data[1]
    return(1)
else:
    return(0)

What does this contract do? Essentially, this contract implements a name registration database by simply using that as the sole function of the long-term storage of the contract. Contract code theoretically has three places to put data: stack, memory and storage. Of those three, stack and memory are used implicitly in Serpent to support arithmetic and variables, but long-term storage is the only one that survives once execution is over. Here, when you register “george” to 45, the contract first checks if contract.storage["george"] is not nonzero, ie. is zero. If it is, then it sets that storage index to the value provided, 45, and then returns 1. If it is not, then it returns zero. Note that this contract has no way for other contracts to access it; it is only really usable by external applications. More advanced name registries would have an API for contracts to fetch the data associated with a name as well.

Now, on to a more intricate example:

init:
    contract.storage[0xcd2a3d9f938e13cd947ec05abc7fe734df8dd826] = 1000000
code:
    if msg.datasize == 1:
        addr = msg.data[0]
        return(contract.storage[addr])
    else:
        from = msg.sender
        fromvalue = contract.storage[from]
        to = msg.data[0]
        value = msg.data[1]
        if fromvalue >= value:
            contract.storage[from] = fromvalue - value
            contract.storage[to] = contract.storage[to] + value
            return(1)
        else:
            return(0)

This is the “currency contract”, or more precisely an embellished version of it with return values to make debugging easier. This contract is interesting for several reasons. First, it has an initialization step, which gets called when the contract is first made. This initializes an account with 1000000 currency units owned by that account.

After that, there are two code paths. First, incoming messages might contain only one data field. In that case, these messages are treated as balance queries, and simply return the balance of the queried address. Note that msg.data[0] provides the integer at bytes 0…31 of the transaction data, msg.data[1] provides the integer at bytes 32…63, and so forth. This is a convenience introduced in Serpent; the underlying transaction data is all byte-based. Incidentally, this is why we needed to use Serpent’s encode_datalist function to generate the transaction data.

Second, incoming messages might contain two data fields. In that case, the messages are treated as requests to send to that address. The sender is inferred from the sender of the message, and the recipient and the value are taken from the first two fields (ie. first 64 bytes) in msg.data. If there is enough money to transfer, it transfers the money and returns 1; otherwise it returns 0.

Challenge: create a currency contract which takes a fee, denominated in its internal currency, from every transaction, and refunds a small amount of ether to everyone sending a successful transaction, so people (or contracts) who want to deal in this currency would not have to worry about simultaneously maintaining currency and ether balances themselves. The contract would also include a third transaction type, perhaps taking 0 arguments, through which someone can buy internal currency units from the contract by sending it ether. The contract should keep track of two variables: its own balance in its currency, and its ether balance, and it should dynamically adjust the transaction fee and the exchange rate in order to keep both its ether balance and its internal currency balance in bal- uh, in an approximate equilibrium.

Contracts Calling Contracts

This is a proprietary data feed contract:

owner = 0xcd2a3d9f938e13cd947ec05abc7fe734df8dd826
if msg.sender == owner and msg.datasize == 2:
    contract.storage[msg.data[0]] = msg.data[1]
    return(1)
else:
    return(contract.storage[msg.data[0]])

This contract is designed to work as a key/value that can be edited only by its owner, but also also allows anyone to query its contents; the point is for the owner to use various storage indices to record changing data like the USD price of ether. Here, there are two main “clauses” in the contract, one for modifying storage which triggers if a key and a value are provided and the message originates from the contract’s owner, and the other for just reading storage. The msg.datasize variable tells you the number of 32-byte data fields there is in the message data. There are no particularly new features here; this contract is actually fairly simple, and I encourage you to first follow and make sure you understand the logic involved and then play with the contract, instantiating it in a block and then pushing set and query transactions to it.

The interesting part, however, comes when we use this contract inside of another contract. Meet this monstrosity, a hedging contract:

if !contract.storage[1000]:
    contract.storage[1000] = msg.sender
    contract.storage[1002] = msg.value
    contract.storage[1003] = msg.data[0]
    contract.storage[1004] = msg.data[1]
    return(1)
elif !contract.storage[1001]:
    ethvalue = contract.storage[1002]
    if msg.value >= ethvalue:
        contract.storage[1001] = msg.sender
    datasource = contract.storage[1003]
    dataindex = contract.storage[1004]
    othervalue = ethvalue * msg(datasource,0,tx.gas-100,[dataindex],1)
    contract.storage[1005] = othervalue
    contract.storage[1006] = block.timestamp + 86400
    return([2,othervalue],2)
else:
    datasource = contract.storage[1003]
    dataindex = contract.storage[1004]
    othervalue = contract.storage[1005]
    ethvalue = othervalue / msg(dataindex,0,tx.gas-100,[datasource],1)
    if ethvalue >= contract.balance: 
        send(contract.storage[1000],contract.balance,tx.gas-100)
        return(3)
    elif block.timestamp > contract.storage[1006]:
        send(contract.storage[1001],contract.balance - ethvalue,tx.gas-100)
        send(contract.storage[1000],ethvalue,tx.gas-100)
        return(4)
    else:
        return(5)

This contract is bulky because it’s designed to be more testing-friendly; an optimal implementation is roughly half the size. The contract works as follows:

1. Party A sends in X ether alongside a data feed contract D and a currency code C as data items, and is registered at contract storage index 1000. X, D and C are registered in contract storage indices 1002, 1003 and 1004. In this case, suppose that the currency code represents USD.
2. Party B sends in X ether, and is registered at contract storage index 1001. The contract then calls D with data C to determine the price of ether in the given currency, and uses this to compute V, the amount of value in USD sent by each party. V is stored at index 1005, and an expiry time set to 24 hours in the future is stored at index 1006.
3. Maybe, the price of ether in USD drops by more than 50%. If this happens, then there is not enough ether in the contract altogether to pay V USD. To prevent this, as soon as the price slips under the 50% mark, anyone (usually A) can ping the contract to withdraw all 2X ether into A’s address and thereby recover to A’s address almost all of the amount, as measured in USD, that A put in, and leave B with nothing. If this happens, the contract returns 3.
4. Otherwise, after one day, anyone can send a transaction to “ping” the contract and cause it to send V USD worth of ether to A and the remaining ether to B, returning 4.
5. If there is no “margin call” or “expiry” event, then a ping to the contract does nothing and returns 5.

The point of the hedging contract is that A benefits by always getting back the same quantity of USD that he put in, and B benefits if he believes that the value of ether will go up, since a 10% rise in the ether price will, in this circumstance, give him a 20% profit. USD can of course be substituted with anything, including CNY, gold or the consumer price index.

The important new features explored here are msg, send and array literals. msg and send are both ways of sending message to other contracts. The syntaxes are:

send(to, value, gas)
out = msg(to¸ value, gas, datastart, datalength)
msg(to, value, gas, datastart, datalength, outstart, outlength)

Send is simpler, assuming that all you want to do is send money with no bells and whistles involved. The latter two are equivalent ways of sending a message to another contract, differing only in how they handle the output: the first caps output to 32 bytes and sticks it straight into a variable, whereas the second takes in two arguments for the position in memory where to dump the output. The “output” of a message is blank if the recipient is not-yet-existent, an externally owned account, or does not explicitly specify a return value, and if the output does specify a return value then the output is that value (“value” in this context being an arbitrary-length byte array, not a 32-byte number). These two are thus both ways of saying the same thing:

d = array(3)
d[0] = 5
d[1] = 10
d[2] = 15
x = msg(A, B, C, d, 3)

And:

d = array(3)
d[0] = 5
d[1] = 10
d[2] = 15
w = array(1)
msg(A, B, C, d, 3, w, 1)
x = w[0]

In the contract example above, we used the data feed contract to provide the price of ether in USD, and then directly plugged it into the formula othervalue = ethvalue * msg(datasource,0,tx.gas-100,[dataindex],1).

Array literals are another nice convenience feature; the truly optimal way to write the above code is as follows:

x = msg(A, B, C, [5, 10, 15], 3)

Note that you unfortunately still need to specify the array length. However, here the array itself is created and referenced all inline, without needing to manually set things up. All of the magic is done by the Serpent compiler.

So that’s basically it for today. What might you want to code in Serpent? Well, here are a few possibilities:

1. SchellingCoin
2. A contract-based implementation of JustDice.
3. Some skeleton code for a decentralized organization.
4. A board game (eg. chess, Go)
5. A decentralized exchange, with a contract-based order book, between ether and the sub-currency contract given above.
6. Any of the other examples in our whitepaper

Enjoy, and have fun! Also, if you do find any bugs in pyethereum or Serpent, please be sure to point them out.

See also: list of Serpent language operations

SchellingCoin: A Minimal-Trust Universal Data Feed

One of the main applications of Ethereum that people have been interested in is financial contracts and derivatives. Although financial derivatives have acquired a reputation as a highly risky and destabilizing device with the sole function of enriching speculators, the underlying concept in fact has a number of legitimate uses, some of which actually help people protect themselves against the volatility of financial markets.

The main idea here is called “hedging”, and is best explained in the context of Bitcoin, where ordinary businesses and individuals with no desire to take massive risks end up needing to deal with high volumes of a risky asset (BTC). Hedging works as follows. Suppose that Jane is a business owner who accepts Bitcoin for payments and uses it to pay employees, and on average she expects that she will need to keep 100 BTC on hand at any time. Sometimes, this amount might change; it could be 20 BTC or it could be 160 BTC. However, she is not at all excited about the prospect of seeing her BTC drop 23% in value in a single day and losing several months worth of salary. Currently, the “standard” solution is for Jane to set up her business to accept payments via BitPay or Coinbase, paying a 1% fee to have the bitcoins instantly converted into money in her bank account. When she wants to pay BTC, she would need to buy the bitcoins back and send them out, paying 1% again (if not more).

Hedging provides a different approach. Instead of constantly trading BTC back and forth, Jane creates an account on a financial derivatives market, and enters into a contract for difference. In this CFD, Jane agrees to put in $20000 worth of BTC, and get back (in BTC) $20000 plus $100 for every dollar that the BTC price drops. If the BTC price rises, she loses $100 per dollar. Thus, if the value of one bitcoin decreases by $45, Jane would lose $4500 in the value of her bitcoins, but she would gain $4500 in the CFD. Of course, the money does not come out of nowhere; on the other side of the contract is a speculator, betting that the price of BTC will go up, and if it does then Jane will gain in the value of BTC and lose in the CFD, and the speculator would gain in the CFD.

Given this basic ingredient, Jane has three strategies for using it to manage risk:

  1. She can keep the CFD at $100 to $1 forever, and if her exposure is off by some amount then she can take that smaller risk.
  2. Jane can have a bot constantly adjust the CFD to her supply of BTC on hand, paying some fees for this but not nearly as much as with Bitpay and Coinbase.
  3. Thanks to the magic of Ethereum contracts, she can make a CFD that automatically listens to her account balance and retargets itself to her balance, forcing the speculator to assume whatever exposure she needs (within limits), and the speculator will participate in many such contracts to even out their exposure

So how do we do CFDs? In Ethereum, it’s easy; just write a contract to do what you want. Here, I provide a specialized version of a CFD that I am calling a “hedging contract”, which acts as a pure self-contained store of value: you put 1000 ether in, you get the same USD value of ether out (unless the value of ether drops so much that the entire contract doesn’t have enough to cover you, in which case you gain the right to immediately withdraw everything and enter into a new hedging contract):

if contract.storage[1000] == 0:
    if tx.value < 1000 * 10^18:
        stop
    contract.storage[1000] = 1
    contract.storage[1001] = 998 * block.contract_storage(D)[I]
    contract.storage[1002] = block.timestamp + 30 * 86400
    contract.storage[1003] = tx.sender
else:
    ethervalue = contract.storage[1001] / block.contract_storage(D)[I]
    if ethervalue >= 5000:
        mktx(contract.storage[1003],5000 * 10^18,0,0)
    else if block.timestamp > contract.storage[1002]:
        mktx(contract.storage[1003],ethervalue * 10^18,0,0)
        mktx(A,(5000 - ethervalue) * 10^18,0,0)

If you understand ETH-HLL, you can figure that example out, and if you can’t it basically does what the description says (the speculator puts up the contract with 4000 ETH, the counterparty enters into it with 1000 ETH, and there’s an expiry date after 30 days after which anyone can “ping” the contract to return $x worth of ETH to the counterparty and the rest to the speculator). We’ll release better ETH-HLL guides soon, but for now understanding the fine details of the contract is not necessary.

However, all of this has a problem: it requires some trusted source from which to grab the price of ETH/USD. This is much less of a problem than the other approach, involving trusted to create USD-backed cryptographic assets, because it requires much less infrastructure and the incentive to cheat is much smaller, but from a cryptographic purist standpoint it’s not perfect. The fundamental problem is this: cryptography alone has no way of finding out that much about the outside world. You can learn a bit about computational power through proof of work, and you can get some market data between one crypto-asset and another by having an on-chain market, but ultimately there is no term in mathematical algorithms for something like the temperature in Berlin. There is no inherent way cryptography can tell you whether the correct answer is 11’C, 17’C or 2725’C; you need human judgement for that (or thermometers, but then you need human judgement to determine which thermometers are trustworthy).

Schelling time

Here, I provide a mechanism that allows you to create a decentralized data feed. The economics of it are not perfect, and if large collusions are possible then it may break down, but it is likely close to the best that we can do. In this case, we will use the price of ETH/USD as an example; the temperature in Berlin, the world GDP or even the result of a computation that does not lend itself to efficient verifiability can also be used.

The mechanism relies on a concept known as Schelling points. The way it works is at follows. Suppose you and another prisoner are kept in separate rooms, and the guards give you two identical pieces of paper with a few numbers on them. If both of you choose the same number, then you will be released; otherwise, because human rights are not particularly relevant in the land of game theory, you will be thrown in solitary confinement for the rest of your lives. The numbers are as follows:

    14237 59049 76241 81259 90215 100000 132156 157604

Which number do you pick? In theory, these are all arbitrary numbers, and you will pick a random one and have a probability of 1/8 of choosing the same one and getting out of prison. In practice, however, the probability is much higher, because most people choose 100000. Why 100000? Because each prisoner believes that the number 100000 is somehow “special”, and each prisoner believes that the other believes that 100000 is “special”, and so forth infinitely recursively – an instance of common knowledge. Thus each prisoner, believing that the other is more likely to choose 100000, will choose 100000 themselves. Obviously, this is an infinitely recursive chain of logic that’s not ultimately “backed” by anything except itself, but cryptocurrency users reading this article should by now be very comfortable with relying on such concepts.

This mechanism is how SchellingCoin works. The basic protocol is as follows:

1. During an even-numbered block, all users can submit a hash of the ETH/USD price together with their Ethereum address
2. During the block after, users can submit the value whose hash they provided in the previous block.
3. Define the “correctly submitted values” as all values N where H(N+ADDR) was submitted in the first block and N was submitted in the second block, both messages were signed/sent by the account with address ADDR and ADDR is one of the allowed participants in the system.
4. Sort the correctly submitted values (if many values are the same, have a secondary sort by H(N+PREVHASH+ADDR) where PREVHASH is the hash of the last block)
5. Every user who submitted a correctly submitted value between the 25th and 75th percentile gains a reward of N tokens (which we’ll call “schells”)

The protocol does not include a specific mechanism for preventing sybil attacks; it is assumed that proof of work, proof of stake or some other similar solution will be used.

So why does this work? Essentially, for the same reason why the prisoner example above worked; the truth is arguably the most powerful Schelling point out there. Everyone wants to provide the correct answer because everyone expects that everyone else will provide the correct answer and the protocol encourages everyone to provide what everyone else provides. Criminal investigators have been using SchellingCoin for centuries, putting prisoners into separate rooms and asking them all for their stories on what happened at a given event, relying on the fact that it’s easy to be consistent with many other people if you tell the truth but nearly impossible to coordinate on any specific lie.

Problems and Limits

What are the vulnerabilities? In general, collusion attacks. Most trivially, if any entity controls more than 50% of all votes, they can basically unilaterally set the median to whatever they want. On the other hand, if there are a near-infinite number of discrete non-communicating entities, then each individual entity has essentially zero impact on the result; realistically, there will be many entities giving the exact same value so there will not even be an opportunity to adjust the result slightly by voting falsely.

However, in the middle it gets hazy. If one entity controls 49% of votes, they can all pre-announce that they will vote for some false value, and others will also go with that value out of fear that everyone else will and if they don’t they will be left out. But here is the really fun part: even if one entity controls 1% of votes, if that entity pre-announces some false value that they will vote for and announces that they will give 0.00001 schells to whoever votes for that value, then there are now two Schelling points: the truth and the entity’s value. However, the entity’s value contains an incentive to vote for it, so theoretically that Schelling point is superior and everyone will go for it instead.

In practice, however, this is obviously absurd, in the same category as the famous result that in a prisoner’s dilemma with a preset finite number of rounds the optimal strategy is to cheat every round; the argument is that on the last round there’s no room to punish cheating, so the incentive is to cheat, on the second last round both players know that the other will cheat on the next round for that reason anyway so the incentive is to cheat, and so on recursively to the first round. In practice, people are not capable of processing arbitrary-depth recursion, and in this case in practice there is a massive coordination problem in unseating the dominant Schelling point, which only gets worse because everyone that benefits from the SchellingCoin has an incentive to attempt to censor any communication of an attempt to disrupt it. Thus, a 49% coalition will likely be able to break SchellingCoin, but a 1% coalition will not. Where is the middle ground? Perhaps only time will tell.

Another potential concern is micro-cheating. If the underlying datum is a value that frequently makes slight changes, which the price is, then if most participants in the SchellingCoin are simultaneously participants in a system that uses that SchellingCoin, they may have the incentive to slightly tweak their answers in one direction, trying to keep within the 25/75 boundary but at the same time push the median up (or down) very slightly to benefit themselves. Other users will predict the presence of micro-disruption, and will thus tweak their answers in that direction themselves to try to stay within the median. Thus, if people think that micro-cheating is possible, then micro-cheating may be possible, and if they do not think so then it will not be – a common result in Schelling point schemes.

There are two ways of dealing with the problem. First, we can try to define the value very unambiguously – eg. “the last ask price of ETH/USD on exchange XYZ at a time HH:MM:00”, so that a very large portion of answers end up exactly the same and there is no possibility to move the median at all by micro-cheating. However, this introduces centralization in the definition, so needs to be handled carefully. An alternative is to be coarse-grained, defining “the price of ETH/USD rounded to two significant digits”. Second, we can simply work hard to make the underlying system for picking users avoid biases, both by being decentralization-friendly (ie. proof-of-stake over proof-of-work) and by including users who are likely to have incentives in opposite directions.

Thus, if we combine SchellingCoin and contracts for difference, what we have is a cryptographic asset that I have previously identified as a holy grail of cryptocurrency: an asset which maintains a stable value and is simultaneously trust-free. Trust-free is of course a relative term; given the current distribution of mining pools Bitcoin’s “trust-free” voting is far from completely free of any trust, but the challenge is to make the protocol as decentralized and future-proof as we can. Many of these “holy grails” are not reachable perfectly; even the ones that we think we’ve already reached we often really haven’t (eg. decentralized sybil attack resistance), but every step toward the ultimate goal counts.

Mining for Schells

The interesting part about SchellingCoin is that it can be used for more than just price feeds. SchellingCoin can tell you the temperature in Berlin, the world’s GDP or, most interestingly of all, the result of a computation. Some computations can be efficiently verified; for example, if I wanted a number N such that the last twelve digits of 3N are 737543007707, that’s hard to compute, but if you submit the value then it’s very easy for a contract or mining algorithm to verify it and automatically provide a reward. Other computations, however, cannot be efficiently verified, and most useful computation falls into the latter category. SchellingCoin provides a way of using the network as an actual distributed cloud computing system by copying the work among N parties instead of every computer in the network and rewarding only those who provide the most common result.

For added efficiency, a more intricate multi-step protocol can have one node do the computation and only use SchellingCoin to “spot-check” only a random 1% of the work, allowing for perhaps less than 2x cryptographic overhead. A deposit requirement and harsh penalties for providing an answer that turns out not to pass scrutiny can be used to limit fraud, and another option is to let anyone redo the work and “suggest” a verification index to the network to apply SchellingCoin on if they discover any faults.

The protocol described above is not a new idea; as I mentioned earlier, it is simply a generalization of a centuries-old criminal investigation practice, and in fact Bitcoin’s mining algorithm basically is a SchellingCoin on the order of transactions. But the idea can potentially be taken much further, provided that the flaws prove to be surmountable. SchellingCoin for ETH/USD can be used to provide a decentralized dollar; SchellingCoin for computation can be used to provide distributed AWS (albeit with no privacy, but we can wait for efficient obfuscation for that).

Thanks to:

  • Neal Koblitz, for suggesting the idea of using a spot checking repeated computation approach to provide a “useful proof of work”
  • David Friedman, for introducing me to the concept of Schelling points in his “positive account of property rights”
  • Thomas Schelling, for coming up with the concept in the first place
  • An individual I talked to two months ago whose identity I unfortunately forgot for providing the idea of incorporating Schelling schemes into Ethereum

The Latest EVM: “Ethereum Is A Trust-Free Closure System”

In the past two weeks our lead C++ developer, Gavin Wood, and myself have been spending a lot of time meeting the local Ethereum community in San Francisco and Silicon Valley. We were very excited to see such a large amount of interest in our project, and the fact that after only two months we have a meetup group that comes together every week, just like the Bitcoin meetup, with over thirty people attending each time. People in the community are taking it upon themselves to make educational videos, organize events and experiment with contracts, and one person is even independently starting to write an implementation of Ethereum in node.js. At the same time, however, we had the chance to take another look at the Ethereum protocols, see where things are still imperfect, and agree on a large array of changes that will be integrated, likely with only minimal modification, into the PoC 3.5 clients.

Transactions as Closures

In ES1 and ES2, the MKTX opcode, which allowed contracts to send transactions triggering other contracts, had one very non-intuitive feature: although one would naturally expect MKTX to be like a function call, processing the entire transaction immediately and then continuing on with the rest of the code, in reality MKTX did not work this way. Instead, the execution of the call is deferred toward the end – when MKTX was called, a new transaction would be pushed to the front of the transaction stack of the block, and when the execution of the first transaction ends the execution of the second transaction begins. For example, this is something that you might expect to work:

    x = array()
    x[0] = "george"
    x[1] = MYPUBKEY

    mktx(NAMECOIN,10^20,x,2)

    if contract.storage(NAMECOIN)["george"] == MYPUBKEY:
        registration_successful = 1
    else:
        registration_successful = 0

    // do more stuff...

Use the namecoin contract to try to register “george”, then use the EXTRO opcode to see if the registration is successful. This seems like it should work. However, of course, it doesn’t.

In EVM3 (no longer ES3), we fix this problem. We do this by taking an idea from ES2 – creating a concept of reusable code, functions and software libraries, and an idea from ES1 – keeping it simple by keeping code as a sequential set of instructions in the state, and merging the two together into a concept of “message calls”. A message call is an operation executed from inside a contract which takes a destination address, an ether value, and some data as input and calls the contract with that ether value and data, but which also, unlike a transaction, returns data as an output. There is thus also a new RETURN opcode which allows contract execution to return data.

With this system, contracts can now be much more powerful. Contracts of the traditional sort, performing certain data upon receiving message calls, can still exist. But now, however, two other design patterns also become possible. First, one can now create a proprietary data feed contract; for example, Bloomberg can publish a contract into which they push various asset prices and other market data, and include in its contract an API that returns the internal data as long as the incoming message call sends at least 1 finney along with it. The fee can’t go too high; otherwise contracts that fetch data from the Bloomberg contract once per block and then provide a cheaper passthrough will be profitable. However, even with fees equal to the value of perhaps a quarter of a transaction fee, such a data-feeding business may end up being very viable. The EXTRO opcode is removed to facilitate this functionality, ie. contracts are now opaque from inside the system, although from the outside one can obviously simply look at the Merkle tree.

Second, it is possible to create contracts that represent functions; for example, one can have a SHA256 contract or an ECMUL contract to compute those respective functions. There is one problem with this: twenty bytes to store the address to call a particular function might be a bit much. However, this can be solved by creating one “stdlib” contract which contains a few hundred clauses for common functions, and contracts can store the address of this contract once as a variable and then access it many times simply as “x” (technically, “PUSH 0 MLOAD”). This is the EVM3 way of integrating the other major idea from ES2, the concept of standard libraries.

Ether and Gas

Another important change is this: contracts no longer pay for contract execution, transactions do. When you send a transaction, you now need to include a BASEFEE and a maximum number of steps that you’re willing to pay for. At the start of transaction execution, the BASEFEE multiplied by the maxsteps is immediately subtracted from your balance. A new counter is then instantiated, called GAS, that starts off with the number of steps that you have left. Then, transaction execution starts as before. Every step costs 1 GAS, and execution continues until either it naturally halts, at which point all remaining gas times the provided BASEFEE is returned to the sender, or the execution runs out of GAS; in that case, all execution is reverted but the entire fee is still paid.

This approach has two important benefits. First, it allows miners to know ahead of time the maximum quantity of GAS that a transaction will consume. Second, and much more importantly, it allows contract writers to spend much less time focusing on making the contract “defensible” against dummy transactions that try to sabotage the contract by forcing it to pay fees. For example, consider the old 5-line Namecoin:

    if tx.value < block.basefee * 200:
        stop
    if !contract.storage[tx.data[0]] or tx.data[0] = 100:
        contract.storage[tx.data[0]] = tx.data[1]

Two lines, no checks. Much simpler. Focus on the logic, not the protocol details. The main weakness of the approach is that it means that, if you send a transaction to a contract, you need to precalculate how long the execution will take (or at least set a reasonable upper bound you’re willing to pay), and the contract has the power to get into an infinite loop, use up all the gas, and force you to pay your fee with no effect. However, this is arguably a non-issue; when you send a transaction to someone, you are already implicitly trusting them not to throw the money into a ditch (or at least not complain if they do), and it’s up to the contract to be reasonable. Contracts may even choose to include a flag stating how much gas they expect to require (I hereby nominate prepending “PUSH 4 JMP ” to execution code as a voluntary standard)

There is one important extension to this idea, which applies to the concept of message calls: when a contract makes a message call, the contract also specifies the amount of gas that the contract on the other end of the call has to use. Just as at the top level, the receiving contract can either finish execution in time or it can run out of gas, at which point execution reverts to the start of the call but the gas is still consumed. Alternatively, contracts can put a zero in the gas fields; in that case, they are trusting the sub-contract with all remaining gas. The main reason why this is necessary is to allow automatic contracts and human-controlled contracts to interact with each other; if only the option of calling a contract with all remaining gas was available, then automatic contracts would not be able to use any human-controlled contracts without absolutely trusting their owners. This would make m-of-n data feed applications essentially nonviable. On the other hand, this does introduce the weakness that the execution engine will need to include the ability to revert to certain previous points (specifically, the start of a message call).

The New Terminology Guide

With all of the new concepts that we have introduced, we have standardized on a few new terms that we will use; hopefully, this will help clear up discussion on the various topics.

  • External Actor: A person or other entity able to interface to an Ethereum node, but external to the world of Ethereum. It can interact with Ethereum through depositing signed Transactions and inspecting the block-chain and associated state. Has one (or more) intrinsic Accounts.
  • Address: A 160-bit code used for identifying Accounts.
  • Account: Accounts have an intrinsic balance and transaction count maintained as part of the Ethereum state. They are owned either by External Actors or intrinsically (as an indentity) an Autonomous Object within Ethereum. If an Account identifies an Autonomous Object, then Ethereum will also maintain a Storage State particular to that Account. Each Account has a single Address that identifies it.
  • Transaction: A piece of data, signed by an External Actor. It represents either a Message or a new Autonomous Object. Transactions are recorded into each block of the block-chain.
  • Autonomous Object: A virtual object existant only within the hypothetical state of Ethereum. Has an intrinsic address. Incorporated only as the state of the storage component of the VM.
  • Storage State: The information particular to a given Autonomous Object that is maintained between the times that it runs.
  • Message: Data (as a set of bytes) and Value (specified as Ether) that is passed between two Accounts in a perfectly trusted way, either through the deterministic operation of an Autonomous Object or the cryptographically secure signature of the Transaction.
  • Message Call: The act of passing a message from one Account to another. If the destination account is an Autonomous Object, then the VM will be started with the state of said Object and the Message acted upon. If the message sender is an Autonomous Object, then the Call passes any data returned from the VM operation.
  • Gas: The fundamental network cost unit. Paid for exclusively by Ether (as of PoC-3.5), which is converted freely to and from Gas as required. Gas does not exist outside of the internal Ethereum computation engine; its price is set by the Transaction and miners are free to ignore Transactions whose Gas price is too low.

Long Term View

Soon, we will release a full formal spec of the above changes, including a new version of the whitepaper that takes into account all of these modifications, as well as a new version of the client that implements it. Later on, further changes to the EVM will likely be made, but the ETH-HLL will be changed as little as possible; thus, it is perfectly safe to write contracts in ETH-HLL now and they will continue to work even if the language changes.

We still do not have a final idea of how we will deal with mandatory fees; the current stop-gap approach is now to have a block limit of 1000000 operations (ie. GAS spent) per block. Economically, a mandatory fee and a mandatory block limit are essentially equivalent; however, the block limit is somewhat more generic and theoretically allows a limited number of transactions to get in for free. There will be a blog post covering our latest thoughts on the fee issue shortly. The other idea that I had, stack traces, may also be implemented later.

In the long term, maybe even beyond Ethereum 1.0, perhaps the holy grail is attack the last two “intrinsic” parts of the system, and see if we can turn them too into contracts: ether and ECDSA. In such a system, ether would still be the privileged currency in the system; the current thinking is that we will premine the ether contract into the index “1” so it takes nineteen fewer bytes to use it. However, the execution engine would become simpler since there would no longer be any concept of a currency – instead, it would all be about contracts and message calls. Another interesting benefit is that this would allow ether and ECDSA to be decoupled, making ether optionally quantum-proof; if you want, you could make an ether account using an NTRU or Lamport contract instead. A detriment, however, is that proof of stake would not be possible without a currency that is intrinsic at the protocol level; that may be a good reason not to go in this direction.

The Question of Mining

There are a lot of interesting changes to the Ethereum protocol that are in the works, which will hopefully improve the power of the system, add further features such as light-client friendliness and a higher degree of extensibility, and make Ethereum contracts easier to code. Theoretically, none of these changes are necessary; the Ethereum protocol is fine as it stands today, and can theoretically be released as is once the clients are further built up somewhat; rather, the changes are there to make Ethereum better. However, there is one design objective of Ethereum where the light at the end of the tunnel is a bit further: mining decentralization. Although we always have the backup option of simply sticking with Dagger, Slasher or SHA3, it is entirely unclear that any of those algorithms can truly remain decentralized and mining pool and ASIC-resistant in the long term (Slasher is guaranteed to be decentralized because it’s proof of stake, but has its own moderately problematic flaws).

The basic idea behind the mining algorithm that we want to use is essentially in place; however, as in many cases, the devil is in the details.

This version of the Ethereum mining algorithm is a Hashcash-based implementation, similar to Bitcoin’s SHA256 and Litecoin’s scrypt; the idea is for the miner to repeatedly compute a pseudorandom function on a block and a nonce, trying a different nonce each time, until eventually some nonce produces a result which starts with a large number of zeroes. The only room to innovate in this kind of implementation is changing the function; in Ethereum’s case, the rough outline of the function, taking the blockchain state (defined as the header, the current state tree, and all the data of the last 16 blocks), is as follows:

1. Let `h[i] = sha3(sha3(block_header) ++ nonce ++ i)` for `0 <= i <= 15`
2. Let `S` be the blockchain state 16 blocks ago.
3. Let `C[i]` be the transaction count of the block `i` blocks ago. Let `T[i]` be the `(h[i] mod C[i])`th transaction from the block `i` blocks ago.
4. Apply `T[0]`, `T[1]` … `T[15]` sequentially to `S`. However, every time the transaction leads to processing a contract, (pseudo-)randomly make minor modifications to the code of all contracts affected.
5. Let `S'` be the resulting state. Let `r` be the sha3 of the root of `S'`.

If `r <= 2^256 / diff`, then `nonce` is a valid nonce.

To summarize in non-programmatic language, the mining algorithm requires the miner to grab a few random transactions from the last 16 blocks, run the computation of applying them to the state 16 blocks ago with a few random modifications, and then take the hash of the result. Every new nonce that the miner tries, the miner would have to repeat this process over again, with a new set of random transactions and modifications each time.

The benefits of this are:

1. It requires the entire blockchain state to mine, essentially requiring every miner to be a full node. This helps with network decentralization, because a larger number of full nodes exist.
2. Because every miner is now required to be a full node, mining pools become much less useful. In the Bitcoin world, mining pools serve two key purposes. First, pools even out the mining reward; instead of every block providing a miner with a 0.0001% chance of mining a $16,000 block, a miner can mine into the pool and the pool gives the miner a 1% chance of receiving a payout of $1.60. Second, however, pools also provide centralized block validation. Instead of having to run a full Bitcoin client themselves, a miner can simply grab block header data from the pool and mine using that data without actually verifying the block for themselves. With this algorithm, the second argument is moot, and the first concern can be adequately met by peer-to-peer pools that do not give control of a significant portion of network hashpower to a centralized service.
3. It's ASIC-resistant almost by definition. Because the EVM language is Turing-complete, any kind of computation that can be done in a normal programming language can be encoded into EVM code. Therefore, an ASIC that can run all of EVM is by necessity an ASIC for generalized computation – in other words, a CPU. This also has a Primecoin-like social benefit: effort spent toward building EVM ASICs also havs the side benefit of building hardware to make the network faster.
4. The algorithm is relatively computationally quick to verify, although there is no “nice” verification formula that can be run inside EVM code.

However, there are still several major challenges that remain. First, it is not entirely clear that the system of picking random transactions actually ends up requiring the miner to use the entire blockchain. Ideally, the blockchain accesses would be random; in such a setup, a miner with half the blockchain would succeed only on about 1 in 216 nonces. In reality, however, 95% of all transactions will likely use 5% of the blockchain; in such a system, a node with 5% of the memory will only take a slowdown penalty of about 2x.

Second, and more importantly, however, it is difficult to say how much an EVM miner could be optimized. The algorithm definition above asks the miner to “randomly make minor modifications” to the contract. This part is crucial. The reason is this: most transactions have results that are independent of each other; the transactions might be of the form “A sends to B”, “C sends to D”, “E sends to contract F that affects G and H”, etc, with no overlap. Hence, without random modification there would be little need for an EVM miner to actually do much computation; the computation would happen once, and then the miner would just precompute and store the deltas and apply them immediately. The random modifications mean that the miner has to actually make new EVM computations each time the algorithm is run. However, this solution is itself imperfect in two ways. First of all, random modifications can potentially easily result in what would otherwise be very complex and intricate calculations simply ending early, or at least calulations for which the optimizations are very different from the optimizations applied to standard transactions. Second, mining algorithms may deliberately skip complex contracts in favor of simple or easily optimizable ones. There are heuristic tricks for battling both problems, but it is entirely unclear exactly what those heuristics would be.

Another interesting point in favor of this kind of mining is that even if optimized hardware miners emerge, the community has the ability to work together to essentially change the mining algorithm by “poisoning” the transaction pool. Engineers can analyze existing ASICs, determine what their optimizations are, and dump transactions into the blockchain that such optimizations simply do not work with. If 5% of all transactions are effectively poisoned, then ASICs cannot possibly have a speedup of more than 20x. The nice thing is that there is a reason why people would pay the transaction fees to do this: each individual ASIC company has the incentive to poison the well for its competitors.

These are all challenges that we will be working on heavily in the next few months.