Ethereum Basics

​

Joseph Bonneau

​

2017 Summer School on Cyber & Computer Security

​

Technion

Talks on Ethereum today

Morning:

- Basic overview

- hands-on demo

​

Afternoon:

- Security issues

- Proof-of-stake

The road to Ethereum

“Smart contracts” conceptualized by Szabo in 1994

A smart contract is a computerized transaction protocol that executes the terms of a contract. The general objectives are to satisfy common contractual conditions (such as payment terms, liens, confidentiality, and even enforcement), minimize exceptions both malicious and accidental, and minimize the need for trusted intermediaries. Related economic goals include lowering fraud loss, arbitrations and enforcement costs, and other transaction costs.

​

-Nick Szabo “The Idea of Smart Contracts”

A “dumb contract” example: pay for a hash pre-image

Alice will reveal to Bob a value x such that SHA-256(x) = 0x2a...

​

In exchange, Bob will pay US$10.

​

If Alice does not reveal by July 1, 2017, then she will pay a penalty of US$1 per day that she is late, up to US$100.

​

Signed:

Traditional contracts vs. smart contracts

Recall: Bitcoin has a simple scripting language

"tx_out":[

{

"value":"10.12287097",

"scriptPubKey":"OP_DUP OP_HASH160 69e...3d42e OP_EQUALVERIFY OP_CHECKSIG"

},

...

]

​

​

“Spending” requires specifying half of a script

OP_DUP

OP_HASH160

<69e02e18...>

OP_EQUALVERIFY

OP_CHECKSIG

<30440220...>

<0467d2c9...>

scriptSig

scriptPubKey

TO VERIFY: Concatenated script must execute completely with no errors

Bitcoin script execution example

<sig> <pubKey> OP_DUP OP_HASH160 <pubKeyHash?> OP_EQUALVERIFY OP_CHECKSIG

<sig>

✓

<pubKey>

<pubKey>

<pubKeyHash?>

<pubKeyHash>

true

Bitcoin scripting language (“Script”)

Design goals

• Built for Bitcoin (inspired by Forth)
• Simple, compact
• Support for cryptography
• Stack-based
• No looping
• Not Turing-complete
• Time/memory usage bound by program size

​

image via Jessie St. Amand

I am not impressed

Some useful contracts can be done in Bitcoin

• Proof-of-burn
• MULTISIG/access control trees
• Pay-for-hash-preimage
• Multi-party lotteries
• Atomic cross-chain currency exchange
• Micropayment/payment channels
• Greatly improved with OP_CHECKLOCKTIME

Extending Bitcoin functionality

Bitcoin script left developers wanting more

By adding a few opcodes to Bitcoin script, we could support:

• Distributed naming (Namecoin)
• Financial instruments (OpenBazaar, MasterCoin)
• Prediction markets (Futurecoin)
• And many more...

Namecoin was the first fork of Bitcoin

Goal: distributed naming, similar functionality to DNS

3 new opcodes:

• NAME_NEW
• NAME_FIRST_UPDATE
• NAME_UPDATE

​

Namecoin introduces three new opcodes

NAME_NEW: H(r, “jbonneau”)

​

​

​

​

NAME_FIRST_UPDATE: r, “jbonneau”, {"ip" : "68.178.254.235"}

​

​

​

​

NAME_UPDATE: r, “jbonneau”, {"ip6" : "2001:4860:0:1001::68"}

12 block delay (frontrunning)

Namecoin introduces new global state

NAME_NEW y

NAME_FIRST_UPDATE jbonneau,r; 68...

NAME_UPDATE jbonneau, 2001:...

google → 172.217.18.110 [owner: K_g]

reddit → 151.101.65.140 [owner: K_r]

google → 172.217.18.110 [owner: K_g]

reddit → 151.101.65.140 [owner: K_r]

y → {pending} [owner: K_j]

google → 172.217.18.110 [owner: K_g]

reddit → 151.101.65.140 [owner: K_r]

jbonneau → 68.178.254.235 [owner: K_j]

google → 172.217.18.110 [owner: K_g]

reddit → 151.101.65.140 [owner: K_r]

jbonneau → 2001:... [owner: K_j]

Namecoin introduces new fees, incentives

Several requirements for new functionality

Bitcoin left these three implicit

Bitcoin scripts only succeed/fail. No side effects on global state

Miners can produce blocks which are very costly to verify

This state is implicit

Replicated State Machines

Replicated state machines are the classic abstraction

• Set of possible states S
• Set of possible inputs I
• Set of possible outputs O

​

• Transition function f: S × I → S × O

​

• Start state s ∈ S (genesis block)

​

​

​

“Blockchain” is an ordered list of inputs w/consensus

“State” is really just a compression of history

Inputs: Ø

Outputs: 25→Alice

Inputs: 1[0]

Outputs: 17→Bob, 8→Alice

SIGNED(Alice)

time

is this valid?

Inefficient: Scan blockchain to check for validity

Inputs: 2[0]

Outputs: 8→Carol, 7→Bob

SIGNED(Bob)

Inputs: 2[1]

Outputs: 6→David, 2→Alice

SIGNED(Alice)

1

2

3

4

Efficient: track UTXO set

{1[0]: 25, A}

{2[0]: 17, B; 2[1]: 8, A}

{2[1]: 8, A; 3[0]: 8, C, 3[1]: 7,B}

Blockchains may include explicit state commitments

Explicit state offers many advantages

• Inconsistencies surface immediately
• Light clients can quickly get current state
• Can efficiently verify sequence between any two blocks

Ethereum: A universal RSM

To get Turing-completeness:

• Set of possible states S
• Set of possible inputs I
• Set of possible outputs O

​

• Transition function f: S × I → S × O

​

• Start state s ∈ S (genesis block)

​

​

​

Include arbitrary programs

Interpret programs

Universality brings on classic OS problems

• What state can a tx change?
• memory protection
• How many resources can a contract use?
• resource contention

Ethereum in one slide

• States S = a map from addresses to state

​

• Inputs I (transactions)

​

• Transition f:
• validate signature
• run to.code(from, data, value, startgas, gasprice)
• Start state: ∅

may affect the state of any address

The Ethereum blockchain structure

prev

nonce

difficulty

miner

extra

height

time

state root

transaction root

receipt root

The Ethereum blockchain structure

prev

nonce

difficulty

miner

extra

height

time

state root

transaction root

receipt root

The Ethereum blockchain structure

prev

nonce

difficulty

miner

extra

height

time

state root

transaction root

receipt root

Ethereum addresses can be accounts or contracts

Volatile fields

Note: no UTXOs in Ethereum

Three* types of transaction in Ethereum

Three* types of transaction in Ethereum

Three* types of transaction in Ethereum

Example:

NameCoin in Ethereum

Ethereum code written in Solidity, compiled to EVM

Ethereum VM Bytecode

Stack Language

LLL

Viper, Serpent

Solidity

Functional, macros,

looks like scheme

Types, invariants, looks like Javascript

Looks like python

Looks like Forth.

Defined in Yellowpaper

Ethereum

Virtual

Machine

EVM is stack-based, like BTC script

Features

• 1024-depth stack
• 32-byte words
• Accelerated crypto
• SHA-3
• Big num multiply
• GF-256 operations

PUSH1 0

CALLDATALOAD

SLOAD

NOT

PUSH1 9

JUMPI

STOP

JUMPDEST

PUSH1 32

CALLDATALOAD

PUSH1 0

CALLDATALOAD

SSTORE

​

EVM memory model offers a lot of space

Storage: {0,1}²⁵⁶→{0,1}²⁵⁶ map (persistent)

Memory: {0,1}²⁵⁶→{0,1}²⁵⁶ map (volatile between tx)

• in other words, both can represent 2²⁶⁴ bits!
• arranged in 256-bit words
• all memory is zero-initialized

​

​

Storage in Ethereum is very expensive. Limiting memory use is critical

EVM provides basic API for I/O

Input:

• tx info: sender, value, gas limit
• resource use: gas remaining, memory used
• block info: depth, timestamp, miner, hash

Output:

• send messages (call other contracts and/or send money)
• write to logs
• self destruct

Subtleties to contract calls

• Data: unlimited params/return values
• Direct mapped to memory address + size

​

• Exceptions: out of gas, bad jump, etc.
• No state changes persisted
• Control returns to caller

​

• Call stack limit: 1024
• Calls from 1024th frame will fail

Efficient map commitments

How can Ethereum commit to so much state?

Recall: storage is a {0,1}²⁵⁶→{0,1}²⁵⁶ map

Requirements:

• 2ⁿ keys supported
• k keys with a non-zero value
• O(1) commitment size
• O(lg k) update cost
• O(lg k) proofs (even for zero values)

​

Key insight:

Optimize for efficient storage of zeroized values

Non-solution: use a binary tree, paths encode address

Alice

Bob

Carol

David

0

0

0

0

0

0

0

1

1

1

1

1

1

1

Problem:

Requires O(2ⁿ) computation

Optimization #1: pre-compute all sizes of empty tree

Empty[2]

Empty[1]

Alice

Bob

Empty[1]

Carol

David

0

0

0

0

0

0

1

1

1

1

1

1

This almost works!

Proofs are length O(lg n)

Optimization #2: shrink all single subtrees; store prefix

“01”, Alice

“0”, Bob

“”, Carol

“”, David

0

0

0

1

1

1

This works!

Proofs are length O(lg k)

“kv node”

“diverge node”

Ethereum’s “Merkle PATRICIA tree” has a few quirks

• Used in two main places
• overall state
• per-contract storage
• 16-ary
• proofs ~4x longer
• paths can be < 256 bits
• “1”, “01” are distinct
• Really 2²⁵⁷-1 addresses

Gas and transaction limits

Ethereum is like Ryanair: pay to board, then keep paying

Gas in Ethereum is a necessary evil

• All miners must evaluate all transactions
• limit computation cost
• All miners must store all state
• limit storage use
• Short-cut the halting problem
• Finite GAS_LIMIT ensures all programs halt

Observe:

Bitcoin also employs a (crude) means to pay for resources consumed

Every operation has a fixed gas cost

Gas metering is complex

​

1. Transactions specify START_GAS, GAS_PRICE
2. If START_GAS ⨉ GAS_PRICE > caller.balance, halt
3. Deduct START_GAS ⨉ GAS_PRICE from caller.balance
4. Set GAS = START_GAS
5. Run code, deducting from GAS
6. For negative values, add to GAS_REFUND
1. GAS only decreases
7. After termination, add GAS + GAS_REFUND to caller.balance

Out-of-gas exceptions are bad news

• State reverts to previous value
• Except that START_GAS * GAS_PRICE is still deducted

Callers can choose how much gas to send

A:

function a():

assert(msg.gas == 100);

x = B.b.gas(10)()

return x + “ World!”

​

​

​

​

​

​

B:

function b():

assert msg.gas == 10

y = C.c.gas(5)()

​

assert(y == 0);

// out of gas

return “Hello”

​

​

C:

function c():

assert(msg.gas == 5);

while (true) {

Loop

}

​

return “Bonjour”

Out of gas

“Hello”

100

10

5

“Hello World!”

Gas today is typically 5⨉10^-9 ether = 9⨉10^-7 USD

Economics of gas are similar to transaction fees

• Miners choose transactions based on GAS_PRICE

​

• In theory, they should not care which opcodes are used
• In practice, some “overpriced” opcodes may be preferred

​

• Maximum gas limit per block
• Miners can slowly raise it, each block votes

​

Solidity

Solidity should look familiar

• Syntax looks like C++, JavaScript etc.

​

• Contracts look like classes/objects
• Can mark functions internal

​

• Static typing
• Most types can be cast e.g. bool(x)

​

Solidity types

• bool, uint8, uint16, ... uint256, int8, ... int256
• address
• string
• byte[]
• mapping(keyType ==> valueType)

Clever implementation of maps in Solidity

mapping(string => uint256) balances;

​

• every item requires at least one 256-bit word
• balances[“Andrew”] is 0 if “Andrew” doesn’t exist or if “Andrew” has 0 balance
• to delete a key, set balances[“Andrew’] = 0
• Cannot delete an entire map!

0

2²⁵⁶

H(“balances”|”Bob”)

H(“balances”|”Joe”)

H(“balances”|”Alice”)

15

15

100

Polite contracts call throw on errors

uint8 numCandidates;

uint32 votingFee;

mapping(address => bool) hasVoted;

mapping(uint8 => uint32) numVotes;

​

/// Cast a vote for a designated candidate

function castVote(uint8 candidate) {

if (msg.value < votingFee)

return;

if (hasVoted[msg.sender])

throw;

​

hasVoted[msg.sender] = true;

numVotes[candidate] += 1;

}

Throw ensures no effects persisted except gas consumption

Solidity gotchas (many more tomorrow)

• Member variables public by default
• Setters, getters automatically provided
• Functions must be marked payable to accept funds
• Member variables go to storage by default
• Method variables go to memory
• Fallback function()
• Called if no function specified (e.g. send)
• Called if non-existent function called
• msg.sender vs. tx.origin

https://solidity.readthedocs.io/en/develop/solidity-in-depth.html

Solidity and EVM may outgrow Ethereum itself

- Enterprise Ethereum Alliance, still in infancy (Announced Feb 28)

​

-Goal: support EVM, Solidity and tools for private blockchains

- maintain compatibility with Ethereum network

​

Don’t like Solidity? Write your own language!

Ethereum VM Bytecode

Stack Language

Lower-Level Language

Viper

Solidity

Typed, looks like JS

Untyped, looks like python

Looks like Forth.

Defined in Yellowpaper

Your work here

Typed, looks like Go

Bamboo

Looks like Norse poetry

Ethereum project

Ethereum is “run” by the Ethereum Foundation

Compatible “alt-clients” exist (e.g. Parity, Consensys)

​

Ethereum blockchain is different than Bitcoins

Hard Forks are planned in Ethereum

Ethereum has been chasing Bitcoin

Source: coinmarketcap.com

Price has been a wild ride recently

http://eth.rollercoaster.one/

https://ethereumprice.org/

Research challenges

Ethereum makes data public by default

​

• Proposals:
• Project Alchemy-exchange Eth for Zcash
• SNARKs for token-issuing contracts
• Acceleration within EVM?
• Hawk: The blockchain model of cryptography and privacy-preserving smart contracts [Khosba et al. 2016]

Verifying consistency of Ethereum implementations

​

• at least 7 EVM implementations
• C++, Go, Haskell, Java, Python, Ruby, Rust

​

• Inconsistency can be exploited to cause a hard fork!

Verifying correctness of Ethereum contracts

Can you spot the bug?

Scaling is limited as nodes verify all contracts

​

• Can’t always determine which state a tx will change

​

• Goal is to support sharding
• Most nodes track only a random subset of contracts
• Super nodes process cross-shard communication
• Details get complicated... great research topic!

https://github.com/ethereum/wiki/wiki/Sharding-FAQ

Proof-of-stake to replace proof-of-work?

https://medium.com/@VitalikButerin/safety-under-dynamic-validator-sets-ef0c3bbdf9f6

Explore more!

Explore the blockchain: https://etherscan.io

State of the Dapps: https://dapps.ethercasts.com/

More this week!

• Tuesday: Practical programming exercise!

​

• Wednesday: Security issues in smart contract programming

Verifying consistency of Ethereum implementations

​

• There are at least 7 EVM implementations
• C++, Go, Haskell, Java, Python, Ruby, Rust

​

• Any EVM inconsistency can be exploited to cause a hard fork!

Bitcoin script instructions

256 opcodes total (15 disabled, 75 reserved)

• Arithmetic
• If/then
• Logic/data handling
• Crypto!
• Hashes
• Signature verification
• Multi-signature verification

Side note: Namecoin got the incentives badly wrong

% of all Namecoin registrations

#Names claimed

An empirical study of Namecoin and lessons for decentralized namespace design

Harry Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau and Arvind Narayanan. WEIS 2015

Three levels of contract call in Ethereum

Original message:

Results of a call to C:

Modifiers ease repetitive safety checks

address public owner;

uint public electionEnd;

​

modifier onlyBy(address _account){

require(msg.sender == _account);

_;

}

​

modifier onlyAfter(uint _block) {

require(block.blocknumber >= _block);

_;

}

​

function endElection()

onlyBy(owner) onlyAfter(electionEnd){

​

Built-in support for calling other contracts

- Contract member variables if public, automatically defines a “getter”

- Modifiers payable, constant, returns(), also modifiers can be user defined

- Macros / Internal Functions internal modifier -> does not require a “message”

- Type conversions int(x), uint256(x), bool(x)

- Structs, arrays, mappings, memory vs storage

array: int[2] x; hashmap mapping ( int[2] => int );

- Throwing exceptions throw; // exceptions contain no data

- Units (currency: “eth”, “wei”, etc.) 3 * (2 eth)

• a.send(x) sends x to address a
• returns 0 if this fails due to call stack

​

• foo.call.value(3).gas(20764)( bytes4(sha3("bar()")));
• also callcode, delegatecall
• default is 0 value, all available gas

​

• new constructor deploys a new contract
• Careful, it’s expensive!

Remember:

Smart contracts code is fixed forever.

Calls required to update functionality