Distributed Systems ETH 2020

Ethereum is a distributed state machine. It promises to run arbitrary computer programs in a blockchain.
Smart contracts are programs deployed on the ETH blockchain that have associated storage and can execute arbitrary complex logic.

In ETH up to two "uncles" are allowed additionally to the parent.

There are externally owned accounts (EOAs) that are controlled by individuals with a secret key and contract accounts (CAs) that are for smart contracts.

• Nonce: counts how many transactions the account of the sender of the transaction has already sent.
• address of the recipient.
• signature by the user controlling the EOA.
• Value: The amount of Wei to transfer
• Data: Optional, can be accessed by smart contracts.
• StartGas: maximum amount of computation this transaction is allowed to use.
• GasPrice: How many Wei per unit of Gas the sender is paying. a high GasPrice will make sure that the transaction is executed more quickly.

• simple transaction: transfers some native currency from one EOA to another
• smart contract creation transaction: recipient address field set to 0, data field set to compiled EVM code, used to deploy code as a smart contract, it is deployed after it has been mined "sufficiently deep"
• smart contract execution transaction: smart contract address as recipient and code to execute a specific function of that contract in its data field

In Ethereum, like in Bitcoin, a block is a collection of transactions that is considered a part of the canonical history of transactions. Among other things, a block contains: pointers to parent and up to two uncles, the hash of the root node of a trie structure populated with each transaction of the block, the hash of the root node of the state trie (after transactions have been executed).

A smart contract hub is a payment hub that is realized by a smart contract on a blockchain and an off-chain server. The smart contract and the server together enable off-chain payments between users that joined the hub.

• Chain: Accounts hold lottery tickets according to their stake. The lottery is pseudo-random, in the sense that hash functions computed on the state of the blockchain will select which account is winning. The winning account can extend the longest chain by a block, and earn the block reward.
• BFT: The lottery winner only gets to propose a block to be added to the blockchain. A committee then votes (yes, byzantine fault tolerance) whether to accept that block into the blockchain. If no agreement is reached, this process is repeated.

Fork problem, nothing at stake attack: just extend all forks

It can tolerate f < n byzantine failures while terminating in f+1 rounds

It does not fulfil the validity conditions (would need f<n/2 byzantine nodes)

We consider a system with n = 3f +1 nodes, and additionally an unbounded number of clients. There are at most f byzantine nodes, and clients can be byzantine as well. The network is asynchronous, and messages have variable delay and can get lost. Clients send requests that correct nodes have to order to achieve state replication.

Each node will consider one node to be primary and the rest backups.

A view v is a non-negative integer representing the node’s local perception of the system. We say that node u is in view v as long as node u considers node p = v mod n to be the primary.

1. The nodes receive a request and relay it to the primary.

2. The primary sends a pre-prepare-message to all backups, informing them that it wants to execute that request with the sequence number specified in the message.

3. Backups send prepare-messages to all nodes, informing them that they agree with that suggestion. (Needs 2f including its own)

4. All nodes send commit-messages to all nodes, informing everyone that they have committed to execute the request with that sequence number. (needs 2f+1 including its own)

5. They execute the request and inform the client.

Prepared Certificate: 2f prepare- messages (including ni’s own, if it is a backup) form together with the pre-prepare-message for (v, s, r) a prepared-certificate.

If a node was able to create a prepared-certificate for (v,s,r) then no node can create one for (v,s,r') with r != r'

Commit Certificate: 2f + 1 commit-messages (including ni’s own)  form a committed-certificate and allow to safely execute the request once all requests with lower sequence numbers have been executed.

Client considers request as processed when it has received f+1 reply messages

When backup b accepts request r it starts a local faulty-timer that will only stop once b executes r. If it expires the backup considers the primary faulty and triggers a view change.

New-view-certificate: 2f+1 view-change messages for the same view form this certificate.

as soon as a node sends its view-change message for view v+1 it starts its faulty-timer and stops it once it accepts a for v+1

Design a game in which nodes have an incentive to behave nicely.

a message propose(t,c) is chosen if it is stored by a majority of servers

if a command c is executed by some servers, all servers eventually execute c

There are n nodes of which at most f might crash (n-f correct). Node i starts with an input value v_i. The nodes must decide for one of those values satisfying the following properties:

1. agreement: all correct nodes decide for the same value
2. termination: all correct nodes terminate in finite time
3. validity: the decision must be an input value of a node

• We say that a system is fully defined (at any point during the execution) by its configuration C. The configuration includes the state of every node, and all messages that are in transit (sent but not yet received).
• C is critical if C is bivalent but all configurations that are direct children of C are univalent

• A configuration C is univalent if the decision value is determined independently of what happens afterwards (only one decision is possible). (univalent for value v -> v-valent)
  Nodes need not be aware of this!
• C is bivalent if the nodes might decide for 0 or 1
   

The configuration tree is a directed tree of configurations. Its root is C0 (fully characterised by the input values), The edges are transitions (characterised by event (u,m), node u receiving message m), every configuration has all applicable transitions as outgoing edges.

No.

If a system is in a bivalent configuration it must reach a critical configuration within finite time or it does not always solve consensus.

If a config tree contains a critical configuration crashing a single node can create a bivalent leaf

--> NO

It achieves binary consensus with expected runtime O(2^n) if up to f < n/2 nodes crash.

(there is no consensus algorithm for the asynchronous model that tolerates f >= n/2 failures)

Use a shared coin instead of choosing v_i completely randomly.

A node which can have arbitrary behaviour (also malicious) is called byzantine.

1. any-input validity: decision value must be the input of any node
2. correct-input validity: decision value must the the input of a correct node
3. all-same validity: if all correct nodes start with the same input v, the decision value must be v
4. median validity: if the input values are orderable byzantine outliers can be prevented by agreeing on a value close to the median of the correct input values

f < n/3

There is at least one phase with a correct king and after such a phase the correct nodes will not change their value anymore.

f+1

Ben-Or for f < n/10
worst case running time: exponential in number of nodes n
If on line 12 a random oracle call is used instead only a constant number of rounds is expected

The blackboard is a trusted authority which supports two operations: write message, read all written values.

uses an optimal n^2 coin flips

cannot tolerate a single byzantine

• best effort broadcast: ensures that a message that is sent from a correct node to another will eventually be received and accepted
• reliable broadcast: ensures that the nodes eventually agree on all accepted messages

FIFO reliable broadcast defines an order in which the messages are accepted in the system.

Tolerates f<n/3 byz, f<n/2 crashes

Let t,n ∈ N with 1 ≤ t ≤ n. An algorithm that distributes a secret among n participants such that t participants need to collaborate to recover the secret is called a (t, n)-threshold secret sharing scheme.