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.

DAOs Are Not Scary, Part 2: Reducing Barriers

In the last installment of this series, we talked about what “smart contracts” (or, perhaps more accurately, “self-enforcing contracts”) are, and discussed in detail the two main mechanisms through which these contracts can have “force”: smart property and “factum” currencies. We also discussed the limits of smart contracts, and how a smart contract-enabled legal system might use a combination of human judgement and automatic execution to achieve the best possible outcomes. But what is the point of these contracts? Why automate? Why is it better to have our relationships regulated and controlled by algorithms rather than humans? These are the tough questions that this article, and the next, intends to tackle.

A Tale of Two Industries

The first, and most obvious, benefit of using internet-driven technology to automate anything is the exact same that we have seen the internet, and Bitcoin, already provide in the spheres of communications and commerce: it increases efficiency and reduces barriers to entry. One very good example of this effect providing meaningful benefits in the traditional world is the publishing industry. In the 1970s, if you wanted to write a book, there was a large number of opaque, centralized intermediaries that you would need to go through before your book would get to a consumer. First, you would need a publishing company, which would also handle editing and marketing for you and provide a quality control function to the consumer. Second, the book would need to be distributed, and then finally it would be sold at each individual bookstore. Each part of the chain would take a large cut; at the end, you would be lucky to get more than ten percent of the revenue from each copy as a royalty. Notice the use of the term “royalty”, implying that you the author of the book are simply just another extraneous part of the chain that deserves a few percent as a cut rather than, well, the single most important person without whom the book would not even exist in the first place. Now, the situation is greatly improved. We now have distinct printing companies, marketing companies and bookstores, with a clear and defined role for each one and plenty of competition in each industry – and if you’re okay with keeping it purely digital, you can just publish on Kindle and get 70%.

Now, let’s consider a very similar example, but with a completely different industry: consumer protection, or more specifically escrow. Escrow is a very important function in commerce, and especially commerce online; when you buy a product from a small online store or from a merchant on Ebay, you are participating in a transaction where neither side has a substantial reputation, and so when you send the money by default there is no way to be sure that you will actually get anything to show for it. Escrow provides the solution: instead of sending the money to the merchant directly, you first send the money to an escrow agent, and the escrow agent then waits for you to confirm that you received the item. If you confirm, then the escrow agent sends the money along, and if the merchant confirms that they can’t send the item then the escrow agent gives you your money back. If there’s a dispute, an adjudication process begins, and the escrow agent decides which side has the better case.

The way it’s implemented today, however, escrow is handled by centralized entities, and is thrown in together with a large number of other functions. On the online marketplace Ebay, for example, Ebay serves the role of providing a server for the seller to host their product page on, a search and price comparison function for products, and a rating system for buyers and sellers. Ebay also owns Paypal, which actually moves the money from the seller to the buyer and serves as the escrow agent. Essentially, this is exactly the same situation that book publishing was in in the 1970s, although in fairness to Ebay sellers do get quite a bit more than 10% of their money. So how can we make an ideal marketplace with cryptocurrencies and smart contracts? If we wanted to be extreme about it, we could make the marketplace decentralized, using a Diaspora-like model to allow a seller to host their products on a specialized site, on their own server or on a Decentralized Dropbox implementation, use a Namecoin-like system for sellers to store their identities and keep a web of trust on the blockchain. However, what we’re looking at now is a more moderate and simple goal: separating out the function of the escrow agent from the payment system. Fortunately, Bitcoin offers a solution: multisignature transactions.

Introducing Multisig

Multisignature transactions allow a user to send funds to an address with three private keys, such that you need two of those keys to unlock the funds (multisigs can also be 1-of-3, 6-of-9, or anything else, but in practice 2-of-3 is the most useful). The way to apply this to escrow is simple: create a 2-of-3 escrow between the buyer, the seller and the escrow agent, have the buyer send funds into it and when a transaction is complete the buyer and the seller sign a transaction to complete the escrow. If there is a dispute, the escrow agent picks which side has the more convincing case, and signs a transaction with them to send them the funds. On a technological level, this is slightly complicated, but fortunately Bitrated has come up with a site that makes the process quite easy for the average user.

Of course, in its current form, Bitrated is not perfect, and we do not see that much Bitcoin commerce using it. The interface is arguably not as easy as it could be, especially since most people are not used to the idea of storing specific per-transaction links for a few weeks, and it would be much more powerful if it was integrated into a fully-fledged merchant package. One design might be a KryptoKit-like web app, showing each user a list of “open” buys and sells and providing a “finalize”, “accept”, “cancel” and “dispute” button for each one; users would then be able to interact with the multisig system just as if it was a standard payment processor, but then get a notification to finalize or dispute their purchases after a few weeks.

But if Bitrated does get its interface right and starts to see mass adoption, what will that accomplish? Once again, the answer is reduced barriers to entry. Currently, getting into the consumer escrow and arbitration business is hard. In order to be an escrow service, you essentially need to build an entire platform and an ecosystem, so that consumers and merchants operate through you. You also can’t just be the one escrowing the money – you also need to be the one transferring the money in the first place. Ebay needs to have, and control, Paypal, in order for half of its consumer protection to work. With Bitrated, this all changes. Anyone can become an escrow agent and arbitrator, and an Ebay-like marketplace (perhaps CryptoThrift or the upcoming Egora) can have a rating system for arbitrators as well as buyers and sellers. Alternatively, the system could handle arbitration in the background similarly to how Uber handles taxi drivers: anyone could become an arbitrator after a vetting process, and the system would automatically reward arbitrators with good ratings and fire those with bad ratings. Fees would drop, likely substantially below even the 2.9% charged by Paypal alone.

Smart Contracts

Smart contracts in general take this same basic idea, and push it much further. Instead of relying on a platform like Bitfinex to hedge one’s Bitcoin holdings or speculate in either direction at high leverage, one can use a blockchain-based financial derivatives contract with a decentralized order book, leaving no central party to take any fees. The ongoing cost of maintaining an exchange, complete with operational security, server management, DDoS protection, marketing and legal expenses, could be replaced with a one-time effort to write the contract, likely in less than 100 lines of code, and another one-time effort to make a pretty interface. From that point on, the entire system would be free except for network fees. File storage platforms like Dropbox could be similarly replaced; although, since hard disk space costs money, the system would not be free, it would likely be substantially cheaper than it is today. It would also help equalize the market by making it easy to participate on the supply side: anyone with a big hard drive, or even a small hard drive with some extra space, can simply install the app and start earning money renting out their unused space.

Instead of relying on legal contracts using expensive (and often, especially in international circumstances and poor countries, ineffective) court systems, or even moderately expensive private arbitration services, business relationships can be governed by smart contracts where those parts of the contract that do need human interpretation can be segregated into many specialized parts. There might be judges specializing in determining whether or not a product shipped (ideally, this would be the postal system itself), judges specializing in determining whether web application designs meet specifications, judges specializing in adjudicating certain classes of property insurance claims with a $0.75 fee by examining satellite images, and there would be contract writers skilled in intelligently integrating each one. Specialization has its advantages, and is the reason why society moved beyond running after bears with stone clubs and picking berries, but one of its weaknesses has always been the fact that it requires intermediaries to manage and function, including intermediaries specifically to manage the relationship between the intermediaries. Smart contracts can remove the latter category almost completely, allowing for an even greater degree of specialization, along with lower barriers to entry within each now shrunken category.

However, this increase in efficiency is only one part of the puzzle. The other part, and perhaps the more important one, has to do with a topic that many cryptocurrency advocates hold dear: reducing trust. We will cover that in the next installment of this series.

DAOs Are Not Scary, Part 1: Self-Enforcing Contracts And Factum Law

Many of the concepts that we promote over in Ethereum land may seem incredibly futuristic, and perhaps even frightening, at times. We talk about so-called “smart contracts” that execute themselves without any need, or any opportunity, for human intervention or involvement, people forming Skynet-like “decentralized autonomous organizations” that live entirely on the cloud and yet control powerful financial resources and can incentivize people to do very real things in the physical world, decentralized “math-based law”, and a seemingly utopian quest to create some kind of fully trust-free society. To the uninformed user, and especially to those who have not even heard of plain old Bitcoin, it can be hard to see how these kinds of things are possible, and if they are why they can possibly be desirable. The purpose of this series will be to dissect these ideas in detail, and show exactly what we mean by each one, discussing its properties, advantages and limitations.

The first installment of the series will talk about so-called “smart contracts”. Smart contracts are an idea that has been around for several decades, but was given its current name and first substantially brought to the (cryptography-inclined) public’s attention by Nick Szabo in 2005. In essence, the definition of a smart contract is simple: a smart contract is a contract that enforces itself. That is to say, whereas a regular contract is a piece of paper (or more recently PDF document) containing text which implicitly asks for a judge to order a party to send money (or other property) to another party under certain conditions, a smart contract is a computer program that can be run on hardware which automatically executes those conditions. Nick Szabo uses the example of a vending machine:

A canonical real-life example, which we might consider to be the primitive ancestor of smart contracts, is the humble vending machine. Within a limited amount of potential loss (the amount in the till should be less than the cost of breaching the mechanism), the machine takes in coins, and via a simple mechanism, which makes a freshman computer science problem in design with finite automata, dispense change and product according to the displayed price. The vending machine is a contract with bearer: anybody with coins can participate in an exchange with the vendor. The lockbox and other security mechanisms protect the stored coins and contents from attackers, sufficiently to allow profitable deployment of vending machines in a wide variety of areas.

Smart contracts are the application of this concept to, well, lots of things. We can have smart financial contracts that automatically shuffle money around based on certain formulas and conditions, smart domain name sale orders that give the domain to whoever first sends in $200, perhaps even smart insurance contracts that control bank accounts and automatically pay out based on some trusted source (or combination of sources) supplying data about real-world events.

Smart Property

At this point, however, one obvious question arises: how are these contracts going to be enforced? Just like traditional contracts, which are not worth the paper they’re written on unless there’s an actual judge backed by legal power enforcing them, smart contracts needs to be “plugged in” to some system in order to actually have power to do anything. The most obvious, and oldest, solution is hardware, an idea that also goes by the name “smart property”. Nick Szabo’s vending machine is the canonical example here. Inside the vending machine, there is a sort of proto-smart-contract, containing a set of computer code that looks something like this:

if button_pressed == "Coca Cola" and money_inserted >= 1.75:
    release("Coca Cola")
    return_change(money_inserted - 1.75)

else if button_pressed == "Aquafina Water" and money_inserted >= 1.25:
    release("Aquafina Water")
    return_change(money_inserted - 1.25)

else if ...

The contract has four “hooks” into the outside world: the button_pressed and money_inserted variables as input, and the release and return_change commands as output. All four of these depend on hardware, although we focus on the last three because human input is generally considered to be a trivial problem. If the contract was running on an Android phone from 2007, it would be useless; the Android phone has no way of knowing how much money was inserted into a slot, and certainly cannot release Coca Cola bottles or return change. On a vending machine, on the other hand, the contract carries some “force”, backed by the vending machine’s internal Coca Cola holdings and its physical security preventing people from just taking the Coca Cola without following the rules of the contract.

Another, more futuristic, application of smart property is rental cars: imagine a world where everyone has their own private key on a smartphone, and there is a car such that when you pay $100 to a certain address the car automatically starts responding commands signed by your private key for a day. The same principle can also be applied to houses. If that sounds far-fetched, keep in mind that office buildings are largely smart property already: access is controlled by access cards, and the question of which (if any) doors each card is valid for is determined by a piece of code linked to a database. And if the company has an HR system that automatically processes employment contracts and activates new employees access cards, then that employment contract is, to a slight extent, a smart contract.

Smart Money and Factum Society

However, physical property is very limited in what it can do. Physical property has a limited amount of security, so you cannot practically do anything interesting with more than a few tens of thousands of dollars with a smart-property setup. And ultimately, the most interesting contracts involve transferring money. But how can we actually make that work? Right now, we basically can’t. We can, theoretically, give contracts the login details to our bank accounts, and then have the contract send money under some conditions, but the problem is that this kind of contract is not really “self-enforcing”. The party making the contract can always simply turn the contract off just before payment is due, or drain their bank account, or even simply change the password to the account. Ultimately, no matter how the contract is integrated into the system, someone has the ability to shut it off.

How can we solve the problem? Ultimately, the answer is one that is radical in the context of our wider society, but already very much old news in the world of Bitcoin: we need a new kind of money. So far, the evolution of money has followed three stages: commodity money, commodity-backed money and fiat money. Commodity money is simple: it’s money that is valuable because it is also simultaneously a commodity that has some “intrinsic” use value. Silver and gold are perfect examples, and in more traditional societies we also have tea, salt (etymology note: this is where the word “salary” comes from), seashells and the like. Next came commodity-backed money – banks issuing certificates that are valuable because they are redeemable for gold. Finally, we have fiat money. The “fiat” in “fiat money” is just like in “fiat lux“, except instead of God saying “let there be light” it’s the federal government saying “let there be money”. The money has value largely because the government issuing it accepts that money, and only that money, as payment for taxes and fees, alongside several other legal privileges.

With Bitcoin, however, we have a new kind of money: factum money. The difference between fiat money and factum money is this: whereas fiat money is put into existence, and maintained, by a government (or, theoretically, some other kind of agency) producing it, factum money just is. Factum money is simply a balance sheet, with a few rules on how that balance sheet can be updated, and that money is valid among that set of users which decides to accept it. Bitcoin is the first example, but there are more. For example, one can have an alternative rule, which states that only bitcoins coming out of a certain “genesis transaction”, count as part of the balance sheet; this is called “colored coins”, and is also a kind of factum money (unless those colored coins are fiat or commodity-backed).

The main promise of factum money, in fact, is precisely the fact that it meshes so well with smart contracts. The main problem with smart contracts is enforcement: if a contract says to send $200 to Bob if X happens, and X does happen, how do we ensure that $200 actually gets sent to Bob. The solution with factum money is incredibly elegant: the definition of the money, or more precisely the definition of the current balance sheet, is the result of executing all of the contracts. Thus, if X does happen, then everyone will agree that Bob has the extra $200, and if X does not happen then everyone will agree that Bob has whatever Bob had before.

This is actually a much more revolutionary development than you might think at first; with factum money, we have created a way for contracts, and perhaps even law in general, to work, and be effective, without relying on any kind of mechanism whatsoever to enforce it. Want a $100 fine for littering? Then define a currency so that you have 100 units less if you litter, and convince people to accept it. Now, that particular example is very far-fetched, and likely impractical without a few major caveats which we will discuss below, but it shows the general principle, and there are many more moderate examples of this kind of principle that definitely can be put to work.

Just How Smart Are Smart Contracts?

Smart contracts are obviously very effective for any kind of financial applications, or more generally any kind of swaps between two different factum assets. One example is a domain name sale; a domain, like google.com, is a factum asset, since it’s backed by a database on a server that only carries any weight because we accept it, and money can obviously be factum as well. Right now, selling a domain is a complicated process that often requires specialized services; in the future, you may be able to package up a sale offer into a smart contract and put it on the blockchain, and if anyone takes it both sides of the trade will happen automatically – no possibility of fraud involved. Going back to the world of currencies, decentralized exchange is another example, and we can also do financial contracts such as hedging and leverage trading.

However, there are places where smart contracts are not so good. Consider, for example, the case of an employment contract: A agrees to do a certain task for B in exchange for payment of X units of currency C. The payment part is easy to smart-contract-ify. However, there is a part that is not so easy: verifying that the work actually took place. If the work is in the physical world, this is pretty much impossible, since blockchains don’t have any way of accessing the physical world. Even if it’s a website, there is still the question of assessing quality, and although computer programs can use machine learning algorithms to judge such characteristics quite effectively in certain cases, it is incredibly hard to do so in a public contract without opening the door for employees “gaming the system”. Sometimes, a society ruled by algorithms is just not quite good enough.

Fortunately, there is a moderate solution that can capture the best of both worlds: judges. A judge in a regular court has essentially unlimited power to do what they want, and the process of judging does not have a particularly good interface; people need to file a suit, wait a significant length of time for a trial, and the judge eventually makes a decision which is enforced by the legal system – itself not a paragon of lightning-quick efficiency. Private arbitration often manages to be cheaper and faster than courts, but even there the problems are still the same. Judges in a factum world, on the other hand, are very much different. A smart contract for employment might look like this:

if says(B,"A did the job") or says(J,"A did the job"):
    send(200, A)

else if says(A,"A did not do the job") or says(J,"A did not do the job"):
    send(200, B)

says is a signature verification algorithm; says(P,T) basically checks if someone had submitted a message with text T and a digital signature that verifies using P’s public key. So how does this contract work? First, the employer would send 200 currency units into the contract, where they would sit in escrow. In most cases, the employer and employee are honest, so either A quits and releases the funds back to B by signing a message saying “A did not do the job” or A does the job, B verifies that A did the job, and the contract releases the funds to A. However, if A does the job, and B disagrees, then it’s up to judge J to say that either A did the job or A did not do the job.

Note that J’s power is very carefully delineated; all that J has the right to do is say that either A did the job or A did not do the job. A more sophisticated contract might also give J the right to grant judgements within the range between the two extremes. J does not have the right to say that A actually deserves 600 currency units, or that by the way the entire relationship is illegal and J should get the 200 units, or anything else outside of the clearly defined boundaries. And J’s power is enforced by factum – the contract contains J’s public key, and thus the funds automatically go to A or B based on the boundaries. The contract can even require messages from 2 out of 3 judges, or it can have separate judges judge separate aspects of the work and have the contract automatically assign B’s work a quality score based on those ratings. Any contract can simply plug in any judge in exactly the way that they want, whether to judge the truth or falsehood of a specific fact, provide a measurement of some variable, or be one of the parties facilitating the arrangement.

How will this be better than the current system? In short, what this introduces is “judges as a service”. Now, in order to become a “judge” you need to get hired at a private arbitration firm or a government court or start your own. In a cryptographically enabled factum law system, being a judge simply requires having a public key and a computer with internet access. As counterintuitive as it sounds, not all judges need to be well-versed in law. Some judges can specialize in, for example, determining whether or not a product was shipped correctly (ideally, the postal system would do this). Other judges can verify the completion of employment contracts. Others would appraise damages for insurance contracts. It would be up to the contract writer to plug in judges of each type in the appropriate places in the contract, and the part of the contract that can be defined purely in computer code will be.

And that’s all there is to it.

The next part of this series will talk about the concept of trust, and what cryptographers and Bitcoin advocates really mean when they talk about building a “trust-free” society.

Ethereum Scalability and Decentralization Updates

Scalability is now at the forefront of the technical discussion in the cryptocurrency scene. The Bitcoin blockchain is currently over 12 GB in size, requiring a period of several days for a new bitcoind node to fully synchronize, the UTXO set that must be stored in RAM is approaching 500 MB, and continued software improvements in the source code are simply not enough to alleviate the trend. With every passing year, it becomes more and more difficult for an ordinary user to locally run a fully functional Bitcoin node on their own desktop, and even as the price, merchant acceptance and popularity of Bitcoin has skyrocketed the number of full nodes in the network has essentially stayed the same since 2011. The 1 MB block size limit currently puts a theoretical cap on this growth, but at a high cost: the Bitcoin network cannot process more than 7 transactions per second. If the popularity of Bitcoin jumps up tenfold yet again, then the limit will force the transaction fee up to nearly a dollar, making Bitcoin less useful than Paypal. If there is one problem that an effective implementation of cryptocurrency 2.0 needs to solve, it is this.

The reason why we in the cryptocurrency spaceare having these problems, and are making so little headway toward coming up with a solution, is that there one fundamental issue with all cryptocurrency designs that needs to be addressed. Out of all of the various proof of work, proof of stake and reputational consensus-based blockchain designs that have been proposed, not a single one has managed to overcome the same core problem: that every single full node must process every single transaction. Having nodes that can process every transaction, even up to a level of thousands of transactions per second, is possible; centralized systems like Paypal, Mastercard and banking servers do it just fine. However, the problem is that it takes a large quantity of resources to set up such a server, and so there is no incentive for anyone except a few large businesses to do it. Once that happens, then those few nodes are potentially vulnerable to profit motive and regulatory pressure, and may start making theoretically unauthorized changes to the state, like giving themselves free money, and all other users, which are dependent on those centralized nodes for security, would have no way of proving that the block is invalid since they do not have the resources to process the entire block.

In Ethereum, as of this point, we have no fundamental improvements over the principle that every full node must process every transaction. There have been ingenious ideas proposed by various Bitcoin developers involving multiple merge-mined chains with a protocol for moving funds from one chain to another, and these will be a large part of our cryptocurrency research effort, but at this point research into how to implement this optimally is not yet mature. However, with the introduction of Block Protocol 2.0 (BP2), we have a protocol that, while not getting past the fundamental blockchain scalability flaw, does get us partway there: as long as at least one honest full node exists (and, for anti-spam reasons, has at least 0.01% mining power or ether ownership), “light clients” that only download a small amount of data from the blockchain can retain the same level of security as full nodes.

What Is A Light Client?

The basic idea behind a light client is that, thanks to a data structure present in Bitcoin (and, in a modified form, Ethereum) called a Merkle tree, it is possible to construct a proof that a certain transaction is in a block, such that the proof is much smaller than the block itself. Right now, a Bitcoin block is about 150 KB in size; a Merkle proof of a transaction is about half a kilobyte. If Bitcoin blocks become 2 GB in size, the proofs might expand to a whole kilobyte. To construct a proof, one simply needs to follow the “branch” of the tree all the way up from the transaction to the root, and provide the nodes on the side every step of the way. Using this mechanism, light clients can be assured that transactions sent to them (or from them) actually made it into a block.

This makes it substantially harder for malicious miners to trick light clients. If, in a hypothetical world where running a full node was completely impractical for ordinary users, a user wanted to claim that they sent 10 BTC to a merchant with not enough resources to download the entire block, the merchant would not be helpless; they would ask for a proof that a transaction sending 10 BTC to them is actually in the block. If the attacker is a miner, they can potentially be more sophisticated and actually put such a transaction into a block, but have it spend funds (ie. UTXO) that do not actually exist. However, even here there is a defense: the light client can ask for a second Merkle tree proof showing that the funds that the 10 BTC transaction is spending also exist, and so on down to some safe block depth. From the point of view of a miner using a light client, this morphs into a challenge-response protocol: full nodes verifying transactions, upon detecting that a transaction spent an output that does not exist, can publish a “challenge” to the network, and other nodes (likely the miner of that block) would need to publish a “response” consisting of a Merkle tree proof showing that the outputs in question do actually exist in some previous block. However, there is one weakness in this protocol in Bitcoin: transaction fees. A malicious miner can publish a block giving themselves a 1000 BTC reward, and other miners running light clients would have no way of knowing that this block is invalid without adding up all of the fees from all of the transactions themselves; for all they know, someone else could have been crazy enough to actually add 975 BTC worth of fees.

BP2

With the previous Block Protocol 1.0, Ethereum was even worse; there was no way for a light client to even verify that the state tree of a block was a valid consequence of the parent state and the transaction list. In fact, the only way to get any assurances at all was for a node to run through every transaction and sequentially apply them to the parent state themselves. BP2, however, adds some stronger assurances. With BP2, every block now has three trees: a state tree, a transaction tree, and a stack trace tree providing the intermediate root of the state tree and the transaction tree after each step. This allows for a challenge-response protocol that, in simplified form, works as follows:

1. Miner M publishes block B. Perhaps the miner is malicious, in which case the block updates the state incorrectly at some point.
2. Light node L receives block B, and does basic proof of work and structural validity checks on the header. If these checks pass, then L starts off treating the block as legitimate, though unconfirmed.
3. Full node F receives block B, and starts doing a full verification process, applying each transaction to the parent state, and making sure that each intermediate state matches the intermediate state provided by the miner. Suppose that F finds an inconsistency at point k. Then, F broadcasts a “challenge” to the network consisting of the hash of B and the value k.
4. L receives the challenge, and temporarily flags B as untrustworthy.
5. If F’s claim is false, and the block is valid at that point, then M can produce a proof of localized consistency by showing a Merkle tree proof of point k in the stack trace, point k+1 in the stack trace, and the subset of Merkle tree nodes in the state and transaction tree that were modified during the process of updating from k to k+1. L can then verify the proof by taking M’s word on the validity of the block up to point k, manually running the update from k to k+1 (this consists of processing a single transaction), and making sure the root hashes match what M provided at the end. L would, of course, also check that the Merkle tree proof for the values at state k and k+1 is valid.
6. If F’s claim is true, then M would not be able to come up with a response, and after some period of time L would discard B outright.

Note that currently the model is for transaction fees to be burned, not distributed to miners, so the weakness in Bitcoin’s light client protocol does not apply. However, even if we decided to change this, the protocol can easily be adapted to handle it; the stack trace would simply also keep a running counter of transaction fees alongside the state and transaction list. As an anti-spam measure, in order for F’s challenge to be valid, F needs to have either mined one of the last 10000 blocks or have held 0.01% of the total supply of ether for at least some period of time. If a full node sends a false challenge, meaning that a miner successfully responds to it, light nodes can blacklist the node’s public key.

Altogether, what this means is that, unlike Bitcoin, Ethereum will likely still be fully secure, including against fraudulent issuance attacks, even if only a small number of full nodes exist; as long as at least one full node is honest, verifying blocks and publishing challenges where appropriate, light clients can rely on it to point out which blocks are flawed. Note that there is one weakness in this protocol: you now need to know all transactions ahead of time before processing a block, and adding new transactions requires substantial effort to recalculate intermediate stack trace values, so the process of producing a block will be more inefficient. However, it is likely possible to patch the protocol to get around this, and if it is possible then BP2.1 will have such a fix.

Blockchain-based Mining

We have not finalized the details of this, but Ethereum will likely use something similar to the following for its mining algorithm:

1. Let H[i] = sha3(sha3(block header without nonce) ++ nonce ++ i) for i in [0 ...16]
2. Let N be the number of transactions in the block.
3. Let T[i] be the (H[i] mod N)th transaction in the block.
4. Let S be the parent block state.
5. Apply T[0] ... T[15] to S, and let the resulting state be S'.
6. Let x = sha3(S'.root)
7. The block is valid if x * difficulty <= 2^256

This has the following properties:

1. This is extremely memory-hard, even more so than Dagger, since mining effectively requires access to the entire blockchain. However it is parallelizable with shared disk space, so it will likely be GPU-dominated, not CPU-dominated as Dagger originally hoped to be.
2. It is memory-easy to verify, since a proof of validity consists of only the relatively small subset of Patricia nodes that are used while processing T[0] ... T[15]
3. All miners essentially have to be full nodes; asking the network for block data for every nonce is prohibitively slow. Thus there will be a larger number of full nodes in Ethereum than in Bitcoin.
4. As a result of (3), one of the major motivations to use centralized mining pools, the fact that they allow miners to operate without downloading the entire blockchain, is nullified. The other main reason to use mining pools, the fact that they even out the payout rate, can be assomplished just as easily with the decentralized p2pool (which we will likely end up supporting with development resources)
5. ASICs for this mining algorithm are simultaneously ASICs for transaction processing, so Ethereum ASICs will help solve the scalability problem.

From here, there is only really one optimization that can be made: figuring out some way to get past the obstacle that every full node must process every transaction. This is a hard problem; a truly scalable and effective solution will take a while to develop. However, this is a strong start, and may even end up as one of the key ingredients to a final solution.

Important Statement regarding the Ether pre-sale

The Ethereum Project has had the incredible privilege to launch its PoC testnet and engage the crypto-currency community over the past two months. During our experiences, we’ve encountered a lot of passionate support and wonderful questions that have helped us refine our thoughts and goals including the process we will eventually use to sell ether. This said, we have not finalized the structure and format for the ether presale and thus we do not recommend, encourage, or endorse any attempt to sell, trade, or acquire ether.

We have recently become aware of peercover.com announcing a fundraising structure based in some way upon ether- they are in no way associated with the Ethereum project, do not speak for it, and are, in our opinion, doing a disservice to the Ethereum community by possibly leading their own clients into a situation that they don’t understand. Offering to sell ether that doesn’t yet exist to mislead purchasers can only be considered irresponsible at this point. Buyer beware.

We request that peercover.com cease to offer ether forwards, until there is more information released on the Ethereum project, the potential value of the ether cryptofuel, and until lawyers in various countries clarify what the securities and regulatory issues might be in selling ether to the public in various countries.

Why Not Just Use X? An Instructive Example from Bitcoin

Bitcoin developer Gregory Maxwell writes the following on Reddit:

There is a design flaw in the Bitcoin protocol where its possible for a third party to take a valid transaction of yours and mutate it in a way which leaves it valid and functionally identical but with a different transaction ID. This greatly complicates writing correct wallet software, and it can be used abusively to invalidate long chains of unconfirmed transactions that depend on the non-mutant transaction (since transactions refer to each other by txid).

This issue arises from several sources, one of them being OpenSSL’s willingness to accept and make sense of signatures with invalid encodings. A normal ECDSA signature encodes two large integers, the encoding isn’t constant length— if there are leading zeros you are supposed to drop them.

It’s easy to write software that assumes the signature will be a constant length and then leave extra leading zeros in them.

This is a very interesting cautionary tale, and is particularly important because situations like these are part of the reason why we have made certain design decisions in our development philosophy. Specifically, the issue is this: many people continue to bring up the point that we are in many places unnecessarily reinventing the wheel, creating our own serialization format, RLP, instead of using the existing protobuf and we’re building an application-specific scripting language instead of “just using Lua”. This is a very valid concern; not-invented-here syndrome is a commonly-used pejorative, so doing such in-house development does require justification.

And the cautionary tale I quoted above provides precisely the perfect example of the justification that I will provide. External technologies, whether protobuf, Lua or OpenSSL, are very good, and have years of development behind them, but in many cases they were never designed with the perfect consensus, determinism and cryptographic integrity in mind that cryptocurrencies require. The OpenSSL situation above is the perfect example; aside from cryptocurrencies, there really is no other situations where the fact that you can take a valid signature and turn it into another valid signature with a different hash is a significant problem, and yet here it’s fatal. One of our core principles in Ethereum is simplicity; the protocol should be as simple as possible, and the protocol should not contain any black boxes. Every single feature of every single sub-protocol should be precisely 100% documented on the whitepaper or wiki, and implemented using that as a specification (ie. test-driven development). Doing this for an existing software package is arguably almost as hard as building an entirely new package from scratch; in fact, it may even be harder, since existing software packages often have more complexity than they need to in order to be feature-complete, whereas our alternatives do not – read the protobuf spec and compare it to the RLP spec to understand what I mean.

Note that the above principle has its limits. For example, we are certainly not foolish enough to start inventing our own hash algorithms, instead using the universally acclaimed and well-vetted SHA3, and for signatures we’re using the same old secp256k1 as Bitcoin, although we’re using RLP to store the v,r,s triple (the v is an extra two bits for public key recovery purposes) instead of the OpenSSL buffer protocol. These kinds of situations are the ones where “just using X” is precisely the right thing to do, because X has a clean and well-understood interface and there are no subtle differences between different implementations. The SHA3 of the empty string is c5d2460186...a470 in C++, in Python, and in Javascript; there’s no debate about it. In between these two extremes, it’s basically a matter of finding the right balance.

Cryptographic Code Obfuscation: Decentralized Autonomous Organizations Are About to Take a Huge Leap Forward

There have been a number of very interesting developments in cryptography in the past few years. Satoshi’s blockchain notwithstanding, perhaps the first major breakthrough after blinding and zero-knowledge proofs is fully homomorphic encryption, a technology which allows you to upload your data onto a server in an encrypted form so that the server can then perform calculations on it and send you back the results all without having any idea what the data is. In 2013, we saw the beginnings of succinct computational integrity and privacy (SCIP), a toolkit pioneered by Eli ben Sasson in Israel that lets you cryptographically prove that you carried out some computation and got a certain output. On the more mundane side, we now have sponge functions, an innovation that substantially simplifies the previous mess of hash functions, stream ciphers and pseudorandom number generators into a beautiful, single construction. Most recently of all, however, there has been another major development in the cryptographic scene, and one whose applications are potentially very far-reaching both in the cryptocurrency space and for software as a whole: obfuscation.

The idea behind obfuscation is an old one, and cryptographers have been trying to crack the problem for years. The problem behind obfuscation is this: is it possible to somehow encrypt a program to produce another program that does the same thing, but which is completely opaque so there is no way to understand what is going on inside? The most obvious use case is proprietary software – if you have a program that incorporates advanced algorithms, and want to let users use the program on specific inputs without being able to reverse-engineer the algorithm, the only way to do such a thing is to obfuscate the code. Proprietary software is for obvious reasons unpopular among the tech community, so the idea has not seen a lot of enthusiasm, a problem compounded by the fact that each and every time a company would try to put an obfuscation scheme into practice it would quickly get broken. Five years ago, researchers put what might perhaps seem to be a final nail in the coffin: a mathematical proof, using arguments vaguely similar to those used to show the impossibility of the halting problem, that a general purpose obfuscator that converts any program into a “black box” is impossible.

At the same time, however, the cryptography community began to follow a different path. Understanding that the “black box” ideal of perfect obfuscation will never be achieved, researchers set out to instead aim for a weaker target: indistinguishability obfuscation. The definition of an indistinguishability obfuscator is this: given two programs A and B that compute the same function, if an effective indistinguishability obfuscator O computes two new programs X=O(A) and Y=O(B), given X and Y there is no (computationally feasible) way to determine which of X and Y came from A and which came from B. In theory, this is the best that anyone can do; if there is a better obfuscator, P, then if you put A and P(A) through the indistinguishability obfuscator O, there would be no way to tell between O(A) and O(P(A)), meaning that the extra step of adding P could not hide any information about the inner workings of the program that O does not. Creating such an obfuscator is the problem which many cryptographers have occupied themselves with for the last five years. And in 2013, UCLA cryptographer Amit Sahai, homomorphic encryption pioneer Craig Gentry and several other researchers figured out how to do it.

Does the indistinguishability obfuscator actually hide private data inside the program? To see what the answer is, consider the following. Suppose your secret password is bobalot_13048, and the SHA256 of the password starts with 00b9bbe6345de82f. Now, construct two programs. A just outputs 00b9bbe6345de82f, whereas B actually stores bobalot_13048 inside, and when you run it it computes SHA256(bobalot_13048) and returns the first 16 hex digits of the output. According to the indistinguishability property, O(A) and O(B) are indistinguishable. If there was some way to extract bobalot_13048 from B, it would therefore be possible to extract bobalot_13048 from A, which essentially implies that you can break SHA256 (or by extension any hash function for that matter). By standard assumptions, this is impossible, so therefore the obfuscator must also make it impossible to uncover bobalot_13048 from B. Thus, we can be pretty sure that Sahai’s obfuscator does actually obfuscate.

So What’s The Point?

In many ways, code obfuscation is one of the holy grails of cryptography. To understand why, consider just how easily nearly every other primitive can be implemented with it. Want public key encryption? Take any symmetric-key encryption scheme, and construct a decryptor with your secret key built in. Obfuscate it, and publish that on the web. You now have a public key. Want a signature scheme? Public key encryption provides that for you as an easy corollary. Want fully homomorphic encryption? Construct a program which takes two numbers as an input, decrypts them, adds the results, and encrypts it, and obfuscate the program. Do the same for multiplication, send both programs to the server, and the server will swap in your adder and multiplier into its code and perform your computation.

However, aside from that, obfuscation is powerful in another key way, and one which has profound consequences particularly in the field of cryptocurrencies and decentralized autonomous organizations: publicly running contracts can now contain private data. On top of second-generation blockchains like Ethereum, it will be possible to run so-called “autonomous agents” (or, when the agents primarily serve as a voting system between human actors, “decentralized autonomous organizations”) whose code gets executed entirely on the blockchain, and which have the power to maintain a currency balance and send transactions inside the Ethereum system. For example, one might have a contract for a non-profit organization that contains a currency balance, with a rule that the funds can be withdrawn or spent if 67% of the organization’s members agree on the amount and destination to send.

Unlike Bitcoin’s vaguely similar multisig functionality, the rules can be extremely flexible, for example allowing a maximum of 1% per day to be withdrawn with only 33% consent, or making the organization a for-profit company whose shares are tradable and whose shareholders automatically receive dividends. Up until now it has been thought that such contracts are fundamentally limited – they can only have an effect inside the Ethereum network, and perhaps other systems which deliberately set themselves up to listen to the Ethereum network. With obfuscation, however, there are new possibilities.

Consider the simplest case: an obfuscated Ethereum contract can contain a private key to an address inside the Bitcoin network, and use that private key to sign Bitcoin transactions when the contract’s conditions are met. Thus, as long as the Ethereum blockchain exists, one can effectively use Ethereum as a sort of controller for money that exists inside of Bitcoin. From there, however, things only get more interesting. Suppose now that you want a decentralized organization to have control of a bank account. With an obfuscated contract, you can have the contract hold the login details to the website of a bank account, and have the contract carry out an entire HTTPS session with the bank, logging in and then authorizing certain transfers. You would need some user to act as an intermediary sending packets between the bank and the contract, but this would be a completely trust-free role, like an internet service provider, and anyone could trivially do it and even receive a reward for the task. Autonomous agents can now also have social networking accounts, accounts to virtual private servers to carry out more heavy-duty computations than what can be done on a blockchain, and pretty much anything that a normal human or proprietary server can.

Looking Forward

Thus, we can see that in the next few years decentralized autonomous organizations are potentially going to become much more powerful than they are today. But what are the consequences going to be? In the developed world, the hope is that there will be a massive reduction in the cost of setting up a new business, organization or partnership, and a tool for creating organizations that are much more difficult to corrupt. Much of the time, organizations are bound by rules which are really little more than gentlemen’s agreements in practice, and once some of the organization’s members gain a certain measure of power they gain the ability to twist every interpretation in their favor.

Up until now, the only partial solution was codifying certain rules into contracts and laws – a solution which has its strengths, but which also has its weaknesses, as laws are numerous and very complicated to navigate without the help of a (often very expensive) professional. With DAOs, there is now also another alternative: making an organization whose organizational bylaws are 100% crystal clear, embedded in mathematical code. Of course, there are many things with definitions that are simply too fuzzy to be mathematically defined; in those cases, we will still need some arbitrators, but their role will be reduced to a limited commodity-like function circumscribed by the contract, rather than having potentially full control over everything.

In the developing world, however, things will be much more drastic. The developed world has access to a legal system that is at times semi-corrupt, but whose main problems are otherwise simply that it’s too biased toward lawyers and too outdated, bureaucratic and inefficient. The developing world, on the other hand, is plagues by legal systems that are fully corrupt at best, and actively conspiring to pillage their subjects at worst. There, nearly all businesses are gentleman’s agreements, and opportunities for people to betray each other exist at every step. The mathematically encoded organizational bylaws that DAOs can have are not just an alternative; they may potentially be the first legal system that people have that is actually there to help them. Arbitrators can build up their reputations online, as can organizations themselves. Ultimately, perhaps on-blockchain voting, like that being pioneered by BitCongress, may even form a basis for new experimental governments. If Africa can leapfrog straight from word of mouth communications to mobile phones, why not go from tribal legal systems with the interference of local governments straight to DAOs?

Many will of course be concerned that having uncontrollable entities moving money around is dangerous, as there are considerable possibilities for criminal activity with these kinds of powers. To that, however, one can make two simple rebuttals. First, although these decentralized autonomous organizations will be impossible to shut down, they will certainly be very easy to monitor and track every step of the way. It will be possible to detect when one of these entities makes a transaction, it will be easy to see what its balance and relationships are, and it will be possible to glean a lot of information about its organizational structure if voting is done on the blockchain. Much like Bitcoin, DAOs are likely far too transparent to be practical for much of the underworld; as FINCEN director Jennifer Shasky Calvery has recently said, “cash is probably still the best medium for laundering money”. Second, ultimately DAOs cannot do anything normal organizations cannot do; all they are is a set of voting rules for a group of humans or other human-controlled agents to manage ownership of digital assets. Even if a DAO cannot be shut down, its members certainly can be just as if they were running a plain old normal organization offline.

Whatever the dominant applications of this new technology turn out to be, one thing is looking more and more certain: cryptography and distributed consensus are about to make the world a whole lot more interesting.