Distributed Systems ETH 2020
Distributed Systems Lecture ETH 2020
Distributed Systems Lecture ETH 2020
What is Ethereum?
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.
What are the two ETH accounts?
There are externally owned accounts (EOAs) that are controlled by individuals with a secret key and contract accounts (CAs) that are for smart contracts.
What things does an ETH transaction contain?
- 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.
What types of transactions are there in ETH?
- 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
What does an ETH block look like?
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).
How does a smart contract (Payment) hub look like?
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.
What is chain-based and BFT-based proof-of-stake?
- 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
What does byzantine agreement with authentication look like?
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)
What is the system model for the Practical Byzantine Fault Tolerance (PBFT) protocol?
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.
What is a view in PBFT context?
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.
Give a high level overview of the PBFT agreement protocol.
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.
What does the PBFT pre-prepare phase look like?
What does the PBFT Prepare Phase look like?
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'
What does the PBFT Commit Phase look like?
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.
What does the PBFT execute phase look like?
Client considers request as processed when it has received f+1 reply messages
What is the PBFT faulty timer?
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.
What does the PBFT view change protocol view change phase look like?
New-view-certificate: 2f+1 view-change messages for the same view form this certificate.
What does the PBFT view change protocol new view phase for the primary look like?
What does the PBFT view change protocol new view phase for the backup look like?
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
What is the goal of mechanism design?
Design a game in which nodes have an incentive to behave nicely.
What is a ticket and what properties does it have?
A ticket is a weaker form of a lock with the following properties:
- reissuable: server can issue more tickets even if previous ones not yet returned
- expiration: server only accepts most recently issued ticket
What does the Paxos Protocol look like?
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
Define consensus and name its properties.
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:
- agreement: all correct nodes decide for the same value
- termination: all correct nodes terminate in finite time
- validity: the decision must be an input value of a node
Define configuration and critical configuration.
- 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
Define univalent and bivalent.
- 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
Define configuration tree.
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.
Is there a deterministic algorithm which always achieves consensus in the asynchronous model with f>0?
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
What does the randomized Consensus Protocol look like?
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)
How can we make the randomized consensus constant time?
Use a shared coin instead of choosing v_i completely randomly.
Define byzantine.
A node which can have arbitrary behaviour (also malicious) is called byzantine.
Define 4 different kinds of validity.
- any-input validity: decision value must be the input of any node
- correct-input validity: decision value must the the input of a correct node
- all-same validity: if all correct nodes start with the same input v, the decision value must be v
- 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
What is the max. number of byzantine nodes such that byzantine agreement can be reached?
f < n/3
What does the King Algorithm look like?
There is at least one phase with a correct king and after such a phase the correct nodes will not change their value anymore.
How many rounds does a synchronous algorithm solving consensus in the presenece of f crashing nodes need if nodes decide for the minimum seen value?
f+1
What does the algorithm for asynchronous byzantine agreement look like?
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
Define the blackboard model for shared coins.
The blackboard is a trusted authority which supports two operations: write message, read all written values.
What does the crash-resilient shared coin with blackboard look like?
uses an optimal n^2 coin flips
cannot tolerate a single byzantine
Define best-effort and reliable broadcast.
- 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
What does Fifo reliable broadcast look like?
FIFO reliable broadcast defines an order in which the messages are accepted in the system.
Tolerates f<n/3 byz, f<n/2 crashes
Define threshold secret sharing.
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.
-
- 1 / 129
-
Flashcards
How can we make the randomized consensus constant time?
Use a shared coin instead of choosing v_i completely randomly.
Define byzantine.
A node which can have arbitrary behaviour (also malicious) is called byzantine.
Define 4 different kinds of validity.
- any-input validity: decision value must be the input of any node
- correct-input validity: decision value must the the input of a correct node
- all-same validity: if all correct nodes start with the same input v, the decision value must be v
- 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
What is the max. number of byzantine nodes such that byzantine agreement can be reached?
f < n/3
What does the King Algorithm look like?
There is at least one phase with a correct king and after such a phase the correct nodes will not change their value anymore.
How many rounds does a synchronous algorithm solving consensus in the presenece of f crashing nodes need if nodes decide for the minimum seen value?
f+1
What does the algorithm for asynchronous byzantine agreement look like?
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
Define the blackboard model for shared coins.
The blackboard is a trusted authority which supports two operations: write message, read all written values.
What does the crash-resilient shared coin with blackboard look like?
uses an optimal n^2 coin flips
cannot tolerate a single byzantine
Define best-effort and reliable broadcast.
- 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
What does Fifo reliable broadcast look like?
FIFO reliable broadcast defines an order in which the messages are accepted in the system.
Tolerates f<n/3 byz, f<n/2 crashes
Define threshold secret sharing.
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.
How does the synchronous byzantine shared coin with hashes look like?
1: Each node has a public key that is known to all nodes.
2: Let r be the current round of Algorithm 17.21
3: Broadcast msg(r)u, i.e., round number r signed by node u
4: Compute hv = hash(msg(r)v) for all received messages msg(r)v 5: Let hmin = minv hv
6: return least significant bit of hmin
Define execution.
An execution E is a set of operations on one or multiple objects executed by a set of nodes.
Define sequential execution.
An execution restricted to a single node is a sequential execution. All operations are executed sequentially.
Define semantic equivalence.
Two executions are semantically equivalent if they contain exactly the same operations and each pair of corresponding operations has the same effect in both executions
Define linearizability. And explain when it applies.
An execution E is called linearizable if there is a sequence of operations S such that
- S is correct and semantically equivalent to E
- whenever f<g for two operations then also f<g in S
E is linearizable iff there exist linearization points (some point f_ in f) such that the sequential execution S that results in ordering the operations according to those is semantically equivalent to E.
Define sequential consistency.
E is called sequentially consistent if there is a sequence of operations S such that
- S is correct and semantically equivalent to E
- whenever f<g for two operations on the same node in E then also f<g in S
Define quiescent consistency.
E is called quiescently consistent if there is a sequence of operations S such that
- S is correct and semantically equivalent to E
- let t be some quiescent point, for every t and every pair of operations g<t and h>t we also have g<h in S
Explain how quiescent consistency, sequential consistency and linarizability are related.
linearizability --> sequential and quiescent consistency
nothing else
Define linearizable system.
A system is called linearizable if it ensures that every possible execution is linearizable. (same for the consistencies)
Define composable.
Give composable example.
A consistency model is called composable if it holds:
If for every object o the restricted execution E|o (only operations involving o) is consistent then also E is consistent.
Linearizability is composable.
Sequential consistency is not composable.
Define happened-before-consistency.
An execution E is called happened-before consistent if there is a sequence of operations S such that:
- S is correct and semantically equivalent to E
- whenever f -> g for two operations also f < g in S
This is equal to sequential consistency.
Define (strong) logical clock.
A logical clock is a family of functions c_u that map every operation on node u to some logical time c_u(f) such that the happened before relation -> is respected:
g -> h --> c_u(g) < c_u(h)
strong logical clock: <-->
What does a Lamport clock look like?
Lamport clocks are logical clocks.
What does a vector clock look like?
With define c_u < c_v iff so for all entries -> vector clocks are strong logical clocks.
Define consistent snapshot.
A cut C (prefix of distributed execution) is a consistent snapshot if for every operation g in C with f -> g C also contains f
What is the measure of concurrency?
The concurrency measure of an execution E = (S_1, ..., S_n) is defined as the ratio:
\(m(e) = { \mu - \mu_s \over \mu_c - \mu_s}\)
With \(\mu\) being the number of consistent snapshots of E.
Define span.
A span s is a named and timed operation representing a contiguous sequence of operations on one node. A span has a start and finish time. (= Tasks)
A span may causally depend on other spans -> ChildOf: parent depends on result of child / FollowsFrom: just invokes child.
A trace is the graph representing the hierarchy of spans.
What does a token-based mutual exclusion algorithm look like?
What does a distributed mutual exclusion algorithm (without tokens) look like?
No SoF, however one node crashes -> requestion node waits forever.
Define clock error and its parts.
Clock error / skew is the difference between two clocks
\(t = (1 + \delta)t^* + \zeta(t^*)\)
Drift \(\delta\) is the predictable clock error.
Jitter \(\zeta\) is the unpredictablle random noise of the clock error
What is PTP?
The precision time protocol is a clock synchronization protocol similar to NTP but uses medium access control layer timestamps. (Removes unknown delay from passing through software stack.)
What is a system clock?
The system clock in a computer is an oscillator used to synchronize all components on the motherboard.
Must have low jitter.
What is the GPS?
The global positioning system satellites continuously transmit their position and time code.
The satellites use a unique pseudo-random noise (PRN) sequence for their signal transmissions.
What is GPS acquisition?
Acquisition is the process in a GPS receiver that finds the visible satellite signals and detects the delays of the PRN sequences and the Doppler shifts of the signals.
What is an A-GPS?
An assisted GPS receiver fetches the satellite orbit parameters and other navigation data from the internet. -> reduces data transmission time (TTFF).
What is collective detection?
Collective detection (CD) is a maximum likelihood snapshot receiver localization method, which does not de- termine an arrival time for each satellite, but rather combine all the available information and take a decision only at the end of the computation.
Define local and global clock skew.
In a network of nodes the local clock skew is the skew between neighboring nodes while the global clock skew is the maximum skew between any two nodes. It is \(\Omega(D)\) where D is the diameter of the network.
Define (minimal, majority) quorum.
V set of nodes, a quorum is a subset of these nodes. A quorum system is a set of quorums such that every two quorums intersect.
It's called minimal if no quorum is a subset of another.
In a majority quorum system every quorum has \(\lfloor {n \over 2} \rfloor + 1\) nodes, its asymptotic failure probability is 0.
