COMP90088: Cryptocurrencies and decentralised ledgers Semester 1 2022
Tutorial Sheet, Week 11 Week of May 16, 2022
1. Address compaction: Public keys in Bitcoin consume a non-trivial portion of the system’s bandwidth. With Pay-to-Pubkey-Hash (P2PKH) transactions, by far the most common type, the public key is included in every redeeming transaction in which it is used.
Computer scientists hate repeating data and love layers of indirection. Hence the following proposal: why not store a list of all public keys in Bitcoin, giving each one a serial number based on the order in which it was first used? This would enable shorter transactions by only specifying the serial number of a key, rather than the entire key.
Copyright By PowCoder代写 加微信 powcoder
This (optional) new format would register a new key as follows:
OP_REGISTER_KEY
The new OP_REGISTER_KEY opcode would take the top value on the stack and store it in a global key lookup table (leaving it on the stack as well). Subsequent transactions could use the same key like:
OP_LOOKUP_KEY
The new OP_LOOKUP_KEY opcode would pop the top value on the stack, look it up in the global key table, and push the result onto the stack. Assume the key lookup indices are 6 bytes.
a. For a standard P2PKH transaction output, how many bytes would be saved for transactions sending money to a key that has been previously used?
b. For a standard P2PKH transaction input, how many bytes would be saved for transactions spending money using a key that has been previously used?
c. Is a 6-byte key index enough? How long would you expect this to last under current trends, given that roughly 500 M unique Bitcoin addresses have been created in its first decade? Do you think it will safe well into the future?
d. Explain possible downsides of this approach. Quantify the extra cost of this approach for validators and explain possible new attacks on the system.
e. Would a similar approach make sense for Ethereum? Why or why not?
2. Aggregate BLS signature: Recall from lecture the definition of a BLS signature:
○ KeyGen() →x, gx (points on an elliptic curve, sometimes written as x, xG)
○ Sign(x, m) → H(m)x (Hash function produces a pseudorandom curve point)
○ Verify(K=gx, m, σ=H(m)x) → e(g,σ) ≟ e(gx,H(m))
The verification works because of the bilinear property of the pairing function e(): ∀ a, b, g ∊ G1, h∊ G2: e(ga, hb) = e(g, h)ab
A useful corollary of this property which can be easily derived is:
∀ x∊G1, y∊G1,h∊G2:e(xy,h)=e(x,h)e(y,h) ∀ g∊G1, x∊G2,y∊G2:e(g,xy)=e(g,x)e(g,y)
BLS signatures have the amazing property of efficient signature aggregation. Given a set of keys K1=gx_1, … Kn=gx_n; a set of messages m1, … , mn and valid signatures σ1, … , σn, an aggregate can be computed as:
Aggregate(σ1, … , σn) = σ* = ∏ σi AggVerify(K1, … , Kn; σ*; m1, … , mn) = e(g,σ*) ≟ ∏e(K i,H(mi))
a. It might help you to first verify algebraically, using the bilinear property of e(), that if all individual signatures verify then their aggregate signature will also verify.
b. Unfortunately the logical inverse of (a) is not immediately true. That is, just because an “aggregate signature” verifies does not mean all individual signatures were valid. To see why, consider the case of aggregating just two signatures on the same message m: (K1, σ1) and (K2, σ2). Suppose that (K1, σ1) is chosen by a victim Alice. The attacker wants to choose a rogue key K2 such that they can compute an aggregate signature σ* that will verify for K1, K2 and m, m. Show how the attacker can compute such a K2 algebraically.
Hint: the attacker they will not know the corresponding private key for K2
c. The standard defense1 for the attack defined in (b) is to ensure that every message in an aggregate signature is distinct, in which cas it can be proven that computing an aggregate signature requires knowing a signature for each individual message. Is this reasonable to enforce in a cryptocurrency context?
1 Another defense is to require a zero-knowledge proof-of-knowledge of the private key for each public key used in an aggregation.
The verification algorithm is then:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com