Distributed Systems ETH 2020

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