Consider the following protocol for the Byzantine Broadcast (BB) problem:
The sender (node \(1\) of \(\{1,2,\ldots,n\}\)) receives the bit \(b \in \{0,1\}\) as input.
Round 1: Node \(1\) sends \(\langle b\rangle_1\) to every node (including itself).
Round 2: Every node \(i\) does the following: If a single bit \(\langle b'\rangle_1\) is received, send the message \(\langle b'\rangle_i\) to everyone, else send \(\langle 0\rangle_i\) to everyone.
Round 3: If node \(i\) has seen a single bit \(\langle b'\rangle_j\) from every \(j \neq i\), then node \(i\) outputs \(b'\). Else node \(i\) outputs \(0\).
Does this protocol solve the BB problem? In order words, does it satisfy both the Consistency and Validity requirements? If so, argue that this is true. If not, give an attack that breaks one of the two properties (use as few corrupted nodes as possible).
Recall the Dolev-Strong protocol for distributed consensus:
There are \(n\) nodes and node \(1\) is the designated sender. The sender receives an input bit \(b \in \{0,1\}\).
Initially every node \(i\) has a set \(\mathsf{extr}_i = \emptyset\) of extracted bits.
Protocol:
Round 0: The sender sends \(\langle b\rangle_1\) to every node.
For each round \(r=1,\ldots,f+1\):
For every message \(\langle \tilde{b}\rangle_{1,j_1,j_2,\ldots,j_{r-1}}\) that node \(i\) receives with \(r\) signatures from distinct nodes (including the sender): If \(\tilde{b} \notin \mathsf{extr}_i\), then add \(\tilde{b}\) to \(\mathsf{extr}_i\) and send \(\langle \tilde{b}\rangle_{1,j_1,\ldots,j_{r-1},i}\) to everyone.
At the end of round \(f+1\): If \(|\mathsf{extr}_i|=1\), then node \(i\) outputs the bit in \(\mathsf{extr}_i\). Otherwise, node \(i\) outputs \(0\).
Present a protocol in which the sender receives an \(\ell\)-bit message \(m \in \{0,1\}^{\ell}\) and wants to propagate it to all the nodes. Consistency and Validity are defined as before. As for Dolev-Strong, your protocol should be secure as long as the number of corrupted nodes is at most \(f \leq n\).
Analyze each of these (flawed) implementations of the Dolev-Strong protocol and present an attack using as few corrupted nodes as possible. In each case, explain which of the two defining properties your attack violates.
Suppose that in step 2 of the DS protocol, we only check for a message \(\langle \tilde{b}\rangle_{j_0,j_1,j_2,\ldots,j_{r-1}}\) with \(r\) signatures from distinct nodes with \(1 \notin \{j_1,j_2,\ldots,j_{r-1}\}\).
Suppose that the digital signature scheme is buggy and it’s possible for an attacker to forge the signatures of honest players.
Recall that a block in some blockchain is a \(4\)-tuple:
\[\left[h_{-1}, \eta, \mathsf{tx}, h\right],\]where \(h_{-1}\) is the previous hash, \(\eta\) is the “puzzle solution”, \(\mathsf{tx}\) is the set of transactions to be recorded on the chain, and \(h = \mathsf{H}(h_{-1},\eta,\mathsf{tx})\).
Recall also that this block is valid if it holds that
\[h = \mathsf{H}(h_{-1}, \eta, \mathsf{tx}) < D,\]where \(D\) is the hardness parameter (and we interpret the output of \(\mathsf{H}\) as an integer).
For this problem, you will use sha256 to implement $\mathsf{H}$. You can look up the documentation for hashlib in Python. To create a hash of a \(3\)-tuple, consider the example code:
import hashlib h = hashlib.sha256() h.update(h_prev) h.update(eta) h.update(tx) hash = int.from_bytes(h.digest(), byteorder='little')
Note that h.update takes a bytestring as input. It doesn’t matter how you convert between ints, strings, and bytes as long as you are consistent (e.g., use a consistent byteorder).
Suppose you have a target for the amount of time it should take to create a new block on the chain. For this problem, use TARGET_TIME = 10.0 (seconds).
Clearly the total computational power associated to mining can change throughout the life of the blockchain, and therefore it makes sense that the security parameter \(D\) is dynamic.
Implement code that repeatedly creates valid new blocks with \(\mathsf{tx}\) equal to the block index (\(\mathsf{tx}=0,1,2,\ldots\)), where the security parameter \(D_j\) is allowed to change. You can start with an arbitrary \(D_0\) (for instance, \(D_0 = 0.01 \cdot 2^{256}\) makes sense).
Write a loop that creates a blockchain of length \(100\) and records the elapsed time for the creation of each new block. If elapsed < TARGET_TIME, update the security parameter as \(D_{j+1} = D_j/2\), and otherwise \(D_{j+1} = 2 D_j\).
For this part, include your code, as well as a log of the \(100\) blocks, the time elapsed in creating the block, and the security parameter for each block.
Plot a histogram of the elapsed block times and compute the mean and variance of the elapsed times.
Since a transaction is only recorded to the chain when the block containing it is produced, discuss briefly the implications of the variance you recorded in part (b).
Try to implement a better update rule for the security parameter \(D_j\). Explain your update rule and include the code.
Plot a histogram as in part (b) and compute the mean and variance of the elapsed times in creating a blockchain of length \(100\).
Discuss briefly why your update rule is better or worse than the update rule in part (a), in the context of your answer to (c).
To simulate the effects of dynamically-changing mining power, suppose you add a slowdown parameter that changes for every block. If the parameter is \(s\), then your code should execute time.sleep(s) in every iteration of the loop that searches for a puzzle solution \(\eta\).
For every one of the \(100\) blocks, you should choose the sleep parameter via s = random.uniform(0.000,0.001).
Plot two histograms of the elapsed times and compute the mean and variance of the elapsed times using first the update rule of part (a), and then the update rule for part (d).