COMP90088: Cryptocurrencies and decentralised ledgers Semester 1 2022
Tutorial Sheet, Week 10 Week of May 9, 2022
1. Pseudorandom committee selection: Many efficient distributed consensus protocols rely on sampling a few users to be members of a committee for a certain round or set of rounds (called an epoch). An important security goal is for it to be unlikely for an adversary to control a sufficient majority of the chosen committee to attack in any round/epoch.
Assume the following:
Copyright By PowCoder代写 加微信 powcoder
¡ñ Committees are composed of N participants
¡ñ The per-epoch consensus protocol requires no more than f corrupt nodes selected
¡ñ A fraction h of all users in the system are honest (not corrupt)
¡ñ The probability of selecting a committee with more than f corrupt nodes can be at most 2-¦Ë
a. Express the above requirements as a mathematical equation
b. Create a simple spreadsheet (or a computer program or script) that allows you to
experiment with the above values
c. Suppose that h=80% of users are honest and the per-epoch consensus protocol only
requires an honest majority (f < N/2). How large does N need to support a security
parameter of ¦Ë=64 (that is, a probability of at most 2-64 of failure?
d. Suppose that h=80% of users are honest but the per-epoch consensus protocol requires
two-thirds honest participants (f < N/3). How large does N need to support a security
parameter of ¦Ë=64 (that is, a probability of at most 2-64 of failure?
e. What is the downside of choosing a larger N in a protocol like Algorand, in which every
participant must broadcast confirmatory signatures in each round?
f. What is the downside of choosing a larger N in a round-based proof-of-stake protocol, in which each committee member is assigned to produce a block in exactly one of the N
slots in an epoch?
2. Alternate puzzles: For a hash function H: {0,1}* ¡ú {1,...,2256}, consider the following puzzle: given a challenge c and a difficulty d, find nonces n1 ¡ n2 such that:
H(c,n1) = H(c,n2) (mod d)
That is, the miner must find two nonces that collide under H modulo d. Clearly, puzzle solutions
are easy to verify and the difficulty can be adjusted granularly.
a. A simple algorithm is to repeatedly choose a random nonce n and add (H(c, n) mod d, n)
to a dictionary L stored to allow efficient search by hash outputs, mod d (such as a hash map). The algorithm terminates when the last hash value added to L collides with some hash value already in L. For given values of d, approximately how many invocations of H are required in expectation to generate a solution n1,n2? How much memory does this use for a standard hash table? What other key-value dictionary structure might you use? Hint: it will be helpful to remember the birthday paradox (week 2 tutorial).
b. Consider a simple algorithm with limited memory that chooses one random nonce n1 and then repeatedly chooses a random nonce n2 until it finds an n2 that collides with n1. How many invocations of H will this algorithm use in expectation?
Remark: There is a clever constant-memory algorithm that finds a solution in the same asymptotic time as part (A), but using only constant memory.
c. A puzzle is progress-free if for all h,k (where h¡¤k< B for some large bound B) the probability of finding a solution after computing h¡¤k hashes is k times higher than the probability of finding a solution after computing h hashes. Is this puzzle progress-free?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com