Distributed Systems ETH 2020

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.

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.

An access strategy Z defines the probability P_Z(Q) of accessing a quorum \(Q \in S\) s.t. \(\sum_{Q \in S} P_Z(Q) = 1\).

• the load of an access strategy Z on a node v_i is \(L_Z(v_i)=\sum_{Q \in S; v_i \in Q} P_Z(Q) \)
• the load induced by access strategy Z on a quorum system S is the maximal load induced by Z on any node\(L_z(s)=max_{v_i \in S}L_z(v_i)\)
• the load of a quorum system S is \(L(S) = min_ZL_Z(S)\)

• work of a quorum Q iis the number of nodes W(Q) = |Q|
• the work induced by access strategy Z on a quorum system S is the expected number of nodes accessed \(W_z(S)= \sum_{Q \in S}P_Z(Q) \cdot W(Q)\)
• the work of a quorum system S is \(W(S) = min_zW_z(S)\)

square matrix with side length \(\sqrt{n}\),  consisting of \(\sqrt{n}\) quorums.
work is 2\(\sqrt{n}\) -1 and the load of every node is in \(\Theta(1/\sqrt{n})\)

Its resilience is \(\sqrt{n}\) -1

Its asymptotic failure probability is 1.

1: Attempt to lock the nodes one by one, ordered by their identifiers

2: Should a node be already locked, release all locks and start over

If any f nodes from a quorum system S can fail such that there is still a quorum without failed nodes, then S is f-resilient The largest such f is the resilience R(S).

Consider n = dhr nodes, arranged in a rectangular grid with h · r rows and d columns. Each group of r rows is a band, and r elements in a column restricted to a band are called a mini-column. A quorum consists of one mini-column in every band and one element from each mini-column of one band; thus every quorum has d + hr − 1 elements. The B-Grid quorum system consists of all such quorums.

A quorum system is f-disseminating if 

1. the intersection of two different quorums always contains f+1 nodes, and 

2. for any set of f byzantine nodes there is at least one quorum without byzantine nodes.
need more than 3f nodes

A quorum system is f-masking if 1. the intersection of two different quorums always contains 2f+1 nodes and 2. for any set of f byzantine nodes there is at least one quorum without byzantine nodes.

need more than 4f nodes

L(S) >=\(\sqrt{(2f+1)/n}\)

An f-masking grid quorum system is constructed as the grid quorum system but each quorum contains one full column and f+1 rows of nodes with \(2f +1\leq \sqrt{n}\).

two quorums overlap in at least 2f+2 nodes.

The M-grid quorum system is constructed as the grid quorum as well but each quorum contains \(\sqrt{f+1}\) rows and

\(\sqrt{f+1}\) columns of nodes with \(f \leq \sqrt{n-1/}2\)

A quorum system is f-opaque if the following two properties hold for any set of f byzantine nodes F and any two different quorums Q_1, Q_2:

\(|(Q_1 \cap Q_2) \setminus F| > |(Q_2 \cap F)\cup (Q_2 \setminus Q_1)|\)

\((F \cap Q) = \emptyset \) for some Q

needs n > 5f nodes

L(S) >= 1/2

solves the problem of out-of-date nodes.

• Consistency: all nodes in the system agree on the current state of the system
• availability: the system is operational and instantly processing incoming requests
• partition tolerance: the ability to continue operating correctly even in the presence of a network partition
• CAP theorem: it is impossible for a distributed system to provide all three at once.

If no new updates to the shared state are issued, then eventually the system is in a quiescent state and the shared state is consistent. (conflict resolution mechanism required)

An address is derived from a public key. The key pair is used to uniquely identify the owner of funds of an address.

It is composed of a network identifier byte, the hash of the pk and a checksum.

An output is a tuple consisting of an amount of bitcoins and a spending condition. Most commonly the spending condition requires a valid signature associated with the private key of an address.
Spending conditions are scripts.

They have two states: spent and unspent.

the set of unspent transaction outputs (UXTOs) and some additional global parameters.

An input is a tuple consisting of a reference to a previously created output and arguments (signature) to the spending condition, proving that the transaction creator has the permission to spend the referenced output.

data structure that describes the transfer of bitcoins from spenders to recipients.

It onsists of a number of inputs and new outputs. The inputs result in the referenced outputs spent (removed from the UTXO), and the new outputs being added to the UTXO.

A doublespend is a situation in which multiple transactions attempt to spend the same output. Only one transaction can be valid since outputs can onnly be spent once. When nodes accept different transactions in a doublespend the shared state becomes inconsistent.

transactions are either unconfirmed or confirmed

Proof-of-Work (PoW) is a mechanism that allows a party to prove to another party that a certain amount of computational resources has been utilized for a period of time. A function F_d(c,x) → {true,false}, where difficulty d is a positive number, while challenge c and nonce x are usually bit-strings, is called a Proof-of-Work function if it has following properties:

1. F_d(c,x) is fast to compute if d, c, and x are given.

2. For fixed parameters d and c, finding x such that Fd(c, x) = true is com- putationally difficult but feasible. The difficulty d is used to adjust the time to find such an x.

Bitcoin:  Fd(c, x) → SHA256(SHA256(c|x)) < 2^224/d with challenge c given.

A block is a data structure used to communicate incremental changes to the local state of a node. A block consists of a list of transactions, a reference to a previous block and a nonce. A block lists some transactions the block creator (“miner”) has accepted to its memory pool since the previous block. A node finds and broadcasts a block when it finds a valid nonce for its PoW function.

The first transaction of a block is the reward transaction.

The longest path from the genesis block to a leaf. Only this longest path is a valid transaction history.

1. comptute UTXO for the path leading to b_max

2. clean up the memory pool: remove transactions that were confirmed in a block in the current path, removing transactions that conflict with confirmed transactions, adding transactions that were confirmed in the previous path but are no longer confirmed in the current path.

A smart contract is an agreement between two or more parties, encoded in such a way that the correct execution is guaranteed by the blockchain.

Bitcoin provides a mechanism to make trans- actions invalid until some time in the future: timelocks. A transaction may specify a locktime: the earliest time, expressed in either a Unix timestamp or a blockchain height, at which it may be included in a block and therefore be confirmed.

The node receiving it keeps the transaction in memory.
A timelocked transaction can be replaced.

When an output can be claimed by providing a single signature it is called a singlesig output. In contrast the script of multisig outputs specifies a set of m public keys and requires k-of-m (with k ≤ m) valid signatures from distinct matching public keys from that set in order to be valid.

t_s: setup transaction

only two transactions actually going to the blockchain -> less fees