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
Define Nash equilibrium.
A Nash Equilibrium (NE) is a strategy profile in which no player can improve by unilaterally changing its strategy.
e.g. all players play dominant strategy
Find NE: write down every best response, find all NE
Define price of anarchy (PoA).
Let NE_ be the NE with the highest cost. The PoA is defined as
\(PoA = {cost(NE_-) \over cost(SO)}\)
Define optimistic price of anarchy (OPoA).
Let NE+ be the NE with the smallest cost. The OPoA is
\(OPoA = {cost(NE_+) \over cost(SO)}\)
What is Braess' Paradox?
Adding a super fast road between u and v can increase the travel time.
What is a mixed NE?
Every game has a mixed NE, this means strategies are chosen non-deterministically.
Define auction.
One good is sold to a group of bidders, Each bidder has a secret value z_i for the good and tells his bid b_i to the auctioneer. The auctioneer sells the good to one bidder for a price p.
Define truthful auction.
An auction is truthful if no player v_i can gain anything by not stating the truth, i.e. b_i = z_i
Truthful bidding is a dominant strategy in a second price auction.
How does storage using consistent hashing work?
Hash unique filename of movie and unique parameters of each node h(u) -> [0,1) and store the movie on the node if the hashes are minimal.
Define churn.
Nodes exhibit a high churn if they constantly join and leave the distributed system.
What properties should our virtual network have?
homogeneous: no node should play a dominant role, no node should be a single point of failure.
The nodes should have IDs, in the universe [0, 1)
Every node should have a small degree
small diameter, routing should be easy. If a node does not have the information about a data item, then it should know which neighbor to ask. Within a few (polylogarithmic in n) hops, one should find the node that has the correct information.
What does a (m,d) mesh M(m,d) look like?
What does T(m,d) torus look like?
The mesh is a graph with node set V=[m]^d, [m] means the set {0, 1, ..., m-1}.
The edges \(E = \{\{(a_1,...,a_d),(b_1,...,b_d)\} | a_i,b_i \in [m], \sum_{i=1}^d |a_i-b_i| = 1 \}\)
The T(m,d) torus is an (m,x) mesh and additionally wrap-around edges.
M(2,d) = T(2,d): d-dimensional hypercube
What does the d-dimensional butterfly BF(d) look like?
Let d ∈ N. The d-dimensional butterfly BF(d) is a graph with node set V =[d+1]×[2]^d and an edge set E = E1 ∪ E2 with
\(E_1= \{\{ (i, \alpha),(i+1, \alpha) \} | i \in [d], \alpha \in [2]^d\}\)
and
\(E_2 = \{\{ (i, \alpha),(i+1, \beta) \} | i \in [d], \alpha, \beta \in [2]^d, \alpha \oplus \beta = 2^i \}\)
it has (d+1)2^d nodes, 2d*2^d edges and degree 4
What does a CCC(d) look like?
A cube-connected cycle network is a graph with node set \(V = \{(a,p) | a \in [2]^d, p \in [d]\}\)
and edge set i-am-very-much-not-going-to-type-this-as-I-wont-be-able-to-remember-anyway
What does a Shuffle-Exchange SE(d) look like?
It is defined as an unidirected graph...
What does a b-ary DeBruijn graph of dimension d DB(b,d) look like?
It is an unidirected graph with node set V = {v \in [b]^d} and edge set E that contains all edges {v, w} with the property that \(w \in \{ (x,v_1, ...v_{d-1}): x \in [b], \text{where } v=(v_1, ..., v_d)\}\)
Define Skip List.
The skip list is an ordinary ordered linked list of objects, augmented with additional forward links. The ordinary linked list is the level 0 of the skip list. In addition, every object is promoted to level 1 with probability 1/2. As for level 0, all level 1 objects are connected by a linked list. In general, every object on level i is promoted to the next level with probability 1/2. A special start-object points to the smallest/first object on each level.
Search, insert, delete in O(log n)
Define distributed hash table.
A distributed hash table (DHT) is a distributed data structure that implements a distributed storage. A DHT should support at least (i) a search (for a key) and (ii) an insert (key, object) operation, possibly also (iii) a delete (key) operation.
can be implemented as a hypercubic overlay network
What is DHT with Churn?
We have a fully scalable, efficient distributed storage system which tolerates O(log n) worst-case joins and/or crashes per constant time interval. As in other storage systems, nodes have O(log n) overlay neighbors, and the usual operations (e.g., search, insert) take time O(log n).
How does selfish mining look like?
releases oldest unpublished block if more than two blocks ahead
it depends on ration of the selfish miner's mining power and the share of altruistic mining power if selfish mining is rational
altruistic = 0 -> break even at 1/3
altruistic = 1/2 -> selfish 1/4
Define DAG-blockchain and DAG weight.
In a DAG-blockchain the genesis block does not reference other blocks. Every other block has at least one (and possibly multiple references) to previous blocks. All references should be relevant in the sense that a reference does not already include another reference recursively.
The weight of a dag-ancestor block a with respect to a block b is defined as the number of tree-descendants of a in the set of dag-ancestors of b. If two blocks a and a′ have the same weight, we use the hashes of a and a′ to break ties.
Define (DAG) parent order.
Let x and y be any pair of dag-parents of b, and z be the lowest common tree-ancestor of x and y. x′ and y′ are the tree- children of z that are tree-ancestors of x and y respectively. If x′ has a higher weight than y′, then block b orders dag-parent x before y.
How To Order: "one part of sub-DAG is heavier => earlier in ordering"
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
