COMP90088 (2022) Tutorial Week 10 Solutions
Pseudorandom committee selection
The binomial distribution
N k N−k Pr(k;N,h)= k h (1−h)
Copyright By PowCoder代写 加微信 powcoder
gives the probability that the committee of N participants has exactly k honest members, where each member has independent probability h of being honest. We then set
2−λ = Pr(k;N,h)
which gives the probability that there at most f corrupt users in the committee.
TakeabinomialCDF,suchaslambda = -np.log2(scipy.stats.binom.cdf(N – f – 1, N, h)) using Python NumPy and SciPy.
N=185andf=92yieldsλ≈64. N=847andf=282yieldsλ≈64.
More communication/bandwidth is required.
There’s no bandwidth issue here, since only one block signed by the committee member for that slot in the epoch needs to be broadcast. However, with a larger committee size, the epochs themselves are longer, increasing the potential for adaptive attacks to be made against committee members assigned to slots later in the epoch. Long epochs might also incentivise attackers to hoard coins just before committee selection so that their larger stake gives them a higher probability of being selected.
Alternate puzzles
Using the approximation where we count pairs (see the tutorial 2 solutions), we get k(k−1) = 2d, where k is the number of invocations after which we can expect one collision. Thus
This is known as a second-preimage attack. Each n2 has probability d−1 of colliding with n1. Thus, d invocations are expected. Floyd’s cycle-finding algorithm is the clever algorithm. How can cycle detection be used to generate hash collisions?
Check this plot for the birthday paradox’s probability for not having everyone with distinct birthdays. This is clearly non-linear, so this puzzle is not progress-free.
c. d. e. f.
2d. A standard hash table requires O(d) space. If d is too large for this hash table to be held in memory, there are other dictionary structures that could be considered, includ- ing tree-based structures (recall self-balancing binary search trees from your undergraduate algorithms studies, for example).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com