COMP90088 (2022) Tutorial Week 2 Solutions
Merkle trees
Nodes labelled 6, 7, d and e are required for a proof that shows that node 7 is in this set. Nodes 6 and 7 from the proof are used to re-compute node c, which is used with node d from the proof to re-compute node f, which is then combined with node e from the proof to re-compute node g. The hash of g is then compared with the Merkle tree’s stored hash to determine inclusion of node 7 in the Merkle tree.
A proof that a data node labelled as node 3 does not exist in the sorted Merkle tree would include the inclusion proofs of nodes 2 and 4. Following verification of these two inclusion proofs, verification that nodes 2 and 4 are adjacent would determine non-membership of a node 3 in the tree.
Copyright By PowCoder代写 加微信 powcoder
An inclusion proof would only need to store nodes up to the layer log2(k) rather than up to the root (layer 0). In principal, you can think of this as k separate Merkle sub-trees. Therefore, an inclusion proof is Θ(log2(n) − log2(k)) = Θ(log(n/k)) in size.
Signature schemes
If the attacker is limited to some number of operations polynomial in λ, then the number of random keypairs they could generate and test is less than 2λ, for sufficiently large λ. For the probability of winning the existential forgery game to be less than 2−λ, the size of the keyspace should therefore be 22λ. Thus, the minimum key length is 2λ.
Similarly, an attacker is limited to generating and testing less than 2λ random signatures for an arbitrary message. The space of all signatures should have size 22λ, so the minimum signature size is also 2λ.
Birthday paradox revisited
Whatever the first person’s birthday is, there is a 1/365 chance that the other person’s birthday coincides with it (assuming uniform distribution of birthdays, which is not true in real life).
Assign an indicator random variable Ip to the distinct pair labelled p, such that Ip = 1 if the pair p of people share the same birthday (and Ip = 0 otherwise). Linearity of expectations gives
E( Ip) = E(Ip) (1) pp
=( 1 ×1+364×0) (2) p 365 365
(3) There is one collision when one pair of people shares a birthday. Solving for the expected
N 1 = 2 365.
N 1 =1 (4) 2 365
N(N − 1) = 1 (5) 2×365 √
N=1± 2921. (6) 2
Therefore, N = 28 is the smallest number of people such that the expected number of pairs who share the same birthday exceeds 1.
Imagine a game where we keep adding people with uniformly sampled birthdays to a group, until we stop after exactly one collision occurs. Let X be a random variable which equals the number of people in the group after stopping. We have:
Pr(X = n) = 365 364 . . . 365 − n + 2 × n − 1 , (7) 365 365 365 365
where 2 ≤ n ≤ 366. The traditional formulation asks for the median of this distribution, where as the mean of this distribution gives the expected number of people required for there to be a collision. Due to the shape of this distribution, these two values are different. Note that this value is slightly different to the number of people required so that the expected num- ber of collisions is at least one (which we determined in part c.), but they are approximately equal. The wording of probability questions can be extremely subtle.
There are N triplets, and there is a 1/3652 chance that everyone in a given triplet shares 3
the same birthday. Similar to before, we solve N/3652 = 1 to give at least N = 94 people 3
before we can expect a triple to share a birthday.
Bitcoin addresses
A string of n base56 symbols encodes one of 56n values. There are 2160 distinct bit-strings of length 160. Solving 56n = 2160 gives n = log56(2160) ≈ 27.6, so at least 28 base56 symbols are needed for a Bitcoin address.
Some characters like 1, I and l are excluded from the base56 character set due to visual ambiguity. You wouldn’t want to pay Bitcoin to the wrong address where you accidentally typed 1 instead of I.
If the hash function is collision resistant, then it would be difficult to generate a keypair whose public key hashed to the same address. Therefore it is still secure to distribute the hash of the public key as an address, given a collision resistant hash function.
If the Bitcoin received under the public key hash are locked under standard P2PKH scripts, then Mallory will be able to spend the Bitcoin in Bob’s wallets, since Mallory’s resulting transaction will still verify under the P2PKH script.
A birthday attack is used to find any pair of colliding inputs. Here, Mallory needs to find an input which collides with a specific output: Bob’s address. Therefore the birthday attack does not apply in this case. If Mallory knows Bob’s public key (because he might have previously signed some transaction) and the hash has second-preimage resistance, then Mallory would need to generate 2t different keypairs so that one of them can be expected to derive the correct address. (Note that collision resistance implies second-preimage resistance).
number of pairs which share a birthday:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com