CS代写 COMP90088 (2022) Tutorial Week 11 Solutions

COMP90088 (2022) Tutorial Week 11 Solutions
Address compaction
A standard P2PKH output (scriptPubKey) looks like:
which is then reduced to:

Copyright By PowCoder代写 加微信 powcoder

OP_HASH160
OP_EQUALVERIFY OP_CHECKSIG
OP_LOOKUP_KEY
OP_CHECKSIG
This saves a total of 16 bytes (two 1-byte opcodes are saved and a 6-byte index is used instead of a 20-byte hash).
A standard P2PKH input (scriptSig) looks like:
which is then reduced to just:
saving 33 bytes, the size of a compressed public key.
At that rate (500 million keys per 10 years), it would take 20 years to generate 230 (a billion) unique keys. The 6-byte address space would last for about 26×8−30 × 20 years, or over 5 million years. But this may be misleading as there are already about 233 humans. It would be exhausted in about about 90 years if everybody generated 1 address/day. A larger value like 8 or 10 bytes would be required for a sustainable global currency.
If keys are never reused (as is advised for privacy in most cases), then there are no savings. It would also create a table in which miners have to store data (keys) forever unless some expiry and renewal process was built in. An attacker could register tons of keys and never use them, filling up the table.
Ethereum is an account-based ledger, so key information is already only stored once. Fur- thermore public keys are never stored on-chain due to the way Ethereum rederives them during ECDSA verification in key-recovery mode. So this exact idea wouldn’t work. But Ethereum could still switch to a model where addresses are handed out sequentially, rather than as hashes, and this would lead to some savings comparable to the answer for part (a) only.
Aggregate BLS signature
Just a quick note: you should have seen the dot product of vectors as an example of a bilinear map. For ⃗u,⃗v ∈ R3, the dot product ⃗u·⃗v = 􏰃3i=1 uivi is bilinear: (a⃗u)·(b⃗v) = ab(⃗u·⃗v). Just note that the group operation on vectors in R3 is addition (which is often the convention for groups of points on elliptic curves over prime fields) rather than multiplication (used in the solutions below), so the notation here uses coefficients rather than indices.
For this problem, we are dealing with a group of prime order, so it is cyclic and abelian (commutative).

a. We want to show that if e(g, σi) = e(gxi , H(mi)) for all i, then e(g, σ∗) = 􏰄i e(gxi , H(mi)). We have:
e(g, σ∗) = e(g, 􏰅 σi) i
= 􏰅 e(g, σi) i
= 􏰅 e(gxi , H(mi)) i
by definition of σ∗ by the pairing corollary since each individual signature verifies.
Thus if each individual signature verifies, their aggregate signature will also verify.
b. The attacker first generates a random value y and computes gy. Then they choose their
public key K = gy/K = gyK−1. We then have the product K K = gy. The aggregate 21112
signature can be given as σ∗ = H(m)y. We need to show that e(g,σ∗) = 􏰄2i=1 e(Ki,H(m)). We have:
e(g,σ∗) = e(g,H(m)y) = e(gy,H(m))
= e(K1K2, H(m))
= e(K1 , H (m)) · e(K2 , H (m))
by our definition of σ∗ by bilinearity by choice of K2 by the pairing corollary.
Thus a valid aggregate signature has been made. From the last line, it appears that both Alice and the attacker had signed message m. In reality, this m will have been chosen by the attacker and never signed by Alice at all. The suggestion in the next question where distinct messages are required will mitigate this attack.
c. Yes, this is reasonable. Signatures already include a nonce which is never repeated per key. It suffices to make these nonces globally unique. Another option is to prepend the key to each message being signed.

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com