Exercises

1. Devise a BFT algorithm that is secure against one faulty node out of seven, but can be disrupted by two faulty nodes

2. Why did I choose the number seven in the previous question?

3. Fill in the details in the correctness proof of PSL's algoritm for the case $n=4$.

4. *Prove the general case by induction, using the previous problem as the base of induction

5. A sybil resistance method is called linear if the amount of voting power you get is proportional to the amount of resources you provide (in the regime where it is considered secure). For example, Bitcoin is linear, because if you have a fraction $\alpha$ of the global network, then you can create a fraction of at most $3\alpha/2$ of the blocks. A system is better than linear if buying a larger fraction of the blocks has diminishing returns. For example, one could argue that a voter registry is better than linear because voting twice is considerably more than twice harder than voting once. Can a permissionless Sybil resistance be better than linear?

6. Let $\mathsf{H}$ be a collision resistant hash function. That is, a hash function for each it is hard to find two distinct inputs $s\ne s'$ such that $\mathsf{H}(s) = \mathsf{H}(s')$. A hash is double-length random preimage resistant if given $\mathsf{H}(s)$ for some $s$ that was uniformly sampled from all strings who are twice as long as the output length of $\mathsf{H}$.

   1. Show that if $\mathsf{H}$ is collision resistant then it is also double-length random preimage resistant (hint: first convince yourself that collisions must exist, and infact, there should be many of them)

   2. Show that collision resistance is stronger than double-length random preimage resistance in the following way: let $\mathsf{H}$ be collision resistant hash function, then according to the previous clause it is also double-length random preimage resistant. Show that $\mathsf{H}$ can be slightly modified to another function $\mathsf{H'}$ that is no longer collision resistant but is still double-length random preimage resistant

   3. *The SHA-256 hash function is not really a random oracle. It can be distinguished from a random oracle because it is susceptible to a "length extension attack". Read about this (for example in Boneh and Shoup’s open access Graduate Course in Applied Cryptography, section 8.7), understand the attack, and explain why it is not a concern for Bitcoin's Sybil resistance.

7. When discussing timestamp manipulations in Bitcoin's difficulty adjustment, we said that the adjustment cannot be based on just two blocks, because then it only takes compromising these two blocks to allow arbitrary manipulations difficulty adjustment. On the other hand, the final solution we suggested (which we can further simplify without hardly damage the result by using the first and last block instead if the minimal and maximal timestamps) does seem to only depend on two blocks, completely disregarding the timestamps of all other blocks. Are how these observations not contradictory?

8. What would be the consequences of trying to impose deterministic finality on a PoW blockchain by prohibiting reorgs of some shallow depth (say, an hour)?

9. Can you solve the rich-get-richer problem by implementing diminishing returns (that is, by making the reward decrease as the amount of coined staked by the same person increases)?