COMP90088: Cryptocurrencies and decentralised ledgers Semester 1 2022
Tutorial Sheet, Week 9 Week of May 2, 2022
1. Idioms of use: Consider the transaction graph in the figure below: rectangles represent transactions, empty circles represent fresh addresses, and filled in circles represent addresses controlled by the named entity (i.e., ‘A’ stands for Alice, ‘B’ stands for Bob, and ‘C’ stands for Carol). An edge labeled “change” means that the end node is the change address for that transaction, as identified by the heuristics discussed in class. Note that not every transaction has an identified change address.
a. Discuss the “joint-control” heuristic and situations in which it may be inaccurate. Are there any transactions in the diagram below where the joint-control heuristic can be ruled out?
Copyright By PowCoder代写 加微信 powcoder
b. Can an observer identify who was paid by Bob in the transaction marked (1)? Explain how or explain why they cannot be identified with certainty. If the entity that Bob paid can’t be identified, describe the anonymity set this payer has.
c. Can an observer identify who paid Carol? Explain how or explain why she cannot be identified with certainty. If the entity that paid Carol can’t be identified, describe the anonymity set this payer has.
2. Confidential transactions. Recall that in Confidential Transactions each input/output value xi is represented using a Pedersen commitment:
ci = gx_i·hr_i
Each of ci, g, h are elements in a finite cyclic group 𝔾 (e.g. the group of integers mod p for some prime p, or elliptic curve points). Assume the group 𝔾 is of known order q (a prime) and g and h are both generators of 𝔾.
The security of this scheme relies on the fact that logg(h), the discrete logarithm of h to the base g, is unknown. Note that in a finite cyclic group, knowing logg(h) is equivalent to knowing logh(g).
Recall that the binding property of this scheme says that given a value ci, there should be at most one opening known (e.g. one value of xi, ri that satisfies the above equation).
a. Show that, for a given Pedersen commitment c = gx·hr, if you can find two other values x’, r’ such that c = gx’·hr’, you can compute the logg(h).
Actual Confidential Transactions rely on a slightly different property. Recall that an extra term is provided to prove that the sum of (committed) inputs is equal to the sum of (committed) outputs. For a 2-to-2 transaction, for example, given inputs c1 and c2 and outputs c3 and c4, a value r5 must be provided such that c1·c2=c3·c4·hr_5. This proves that x1+x2 = x3+x4 [mod q], as required to prove the transaction is square.1 This value is computed as r5=(r1+r2)-(r3+r4) [mod q]
b. Suppose an attacker knows that h=gz for some value z. Show that given any values c1,c2,c3,c4 (with all of the x, r values known) the attacker can compute a value r5 that will satisfy the equation. Hence, they can create transactions which increase (or decrease) the money supply.
c. Suppose that have one transaction that satisfies c1·c2=c3·c4·hr_5 even though x1+x2 ≠ x3+x4 [mod q]. Given all of the x, r values, show you can compute logg(h).
Taken together, parts (b) and (c) prove that the security of Confidential Transactions is equivalent to the discrete log problem.
1 Crucially, zero-knowledge range proofs must also be provided to show that the xi values are in the range 0 ≤ xi ≤ xmax ≪ q for some value xmax which is the largest allowable transaction value (e.g. equal to the entire money supply). This ensures there is no overflow mod q.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com