Skip to content

Assignment 3

Jump to bottom
Gijs Van Laer edited this page Nov 12, 2020 · 3 revisions

Assignment 3

Out: 12 November 2020

Due: 23 November 2020 - 11:59pm

  1. Beyond Proof-of-Work. Recall the Avalanche protocol, and the simpler instances on which it is based (Slush, Snowflake, etc.). Particularly, recall the Slush (the most basic instance, not Byzantine fault-tolerant) protocol which involves nodes which are initially uncolored, query a random sample of the network for a color, and respond to queries either with their color (if already colored) or with the color in the query before initiating their own query sampling.

    Describe why a network of honest (non-Byzantine) Slush nodes eventually reach consensus on a color.

  2. Mix aggregation. Suppose Bitcoin was changed such that transactions can have at most two inputs and two outputs. Alice, Bob, and Carol each have a single UTXO worth 1BTC. They want to mix their coins among the three of them so that three output UTXOs are worth 1 BTC each and they are perfectly shuffled. They decide to do the following: Alice and Bob post a transaction with their two bitcoins as input and two fresh addresses, X and Y, as outputs, each holding 1 BTC. Alice controls one address and Bob controls the other, but an observer cannot tell which is which. Suppose X is listed as the first output in this transactions. Next, Carol and the owner of X post a similar transaction: Carol's coin and coin X are the inputs, and two fresh addresses W and Z are the outputs, each holding 1 BTC. Carol controls one address and the owner of X controls the other. As before, an observer cannot tell which is which. They use Y,Z,W as the final shuffled coins.

    Mixer

    1. What is the anonymity set for Z?

    2. Assuming that each mix independently assigns equal probability to both outcomes, what is the probability that Alice controls address W?

    3. Suppose at a later time it is revealed that Bob controls W. What else does this reveal?

For the following two questions, Research the attack mentioned in lecture and provide a summary of the types of attacks which fall into this category. Why does this attack not affect Proof-of-Work systems?

  1. Stake Grinding

  2. Nothing At Stake

  3. Ethereum Payment Channel Consider a one-sided payment channel in Ethereum using a hash function H. The scheme works as follows: to setup the channel Alice chooses a random x and computes y = H(n)(x) (here H(n)(x) means iterating the function H n times starting at x, so that H(2)(x) = H(H(x))). Alice then creates a contract with n units of currency and embeds the value y in the contract (and sends y to Bob). To pay Bob a total of k units (for k < n), she sends Bob the value xk = H(n−k)(x). Of course, Alice can send these k units one at a time, by sending x1 = H(n−1)(x) to Bob, then x2 = H(n−2)(x), and so on. Each xi allows Bob to claim a unit of currency from the contract.

  • What security property should the hash function H satisfy to ensure that Bob cannot steal more money than Alice intended to give him?
  • As a function of n and k, how many hashes does the contract need to compute before distributing funds? How much data will Bob need to store?
  • In practice, we want to minimize the resources consumed by the contract as gas is expensive. Since the above scheme is a linear chain, you might guess that it can be improved using a tree structure. Describe an improved scheme using a Merkle tree that reduces the gas cost to only O(logn) hashes. What are the storage and computation costs (in terms of n and k) for Alice, Bob?
  1. Co-chains Algorand uses co-chains. Explain what a co-chain is, what features it delivers, and what the benefits of co-chains are.

Clone this wiki locally