COMP90088: Cryptocurrencies and decentralised ledgers Semester 1 2022
Homework 4
due: Thursday 2022-05-19 22:00 AEST
1. Mix aggregation (1.5 marks): Suppose Bitcoin was changed such that transactions can have at most two inputs and two outputs (as is the case in Zcash, for example). Alice, Bob, and Carol each have a single UTXO worth 1 BTC. They want to mix their coins (without a trusted server) resulting in three output UTXOs worth 1 BTC each which they are perfectly shuffled: all six (3!) permutations are equally likely. They decide to do the following: Alice and Bob post a transaction with their two bitcoins as input and two fresh addresses, X and Y, as outputs, each holding 1 BTC. Alice controls one address and Bob controls the other, but an observer cannot tell which is which. Suppose X is listed as the first output in this transaction. Next, Carol and the owner of X post a similar transaction: Carol¡¯s coin and the coin X are the inputs, and two fresh addresses W and Z are the outputs, each holding 1 BTC. Carol controls one address and the owner of X controls the other. As before, an observer cannot tell which is which. They use Y,Z,W as the final shuffled coins. Pictorially, the mixing process looks as follows:
Copyright By PowCoder代写 加微信 powcoder
a. What are the weighted anonymity sets for the addresses Y, Z, and W? Assume that each mix independently assigns equal probability to both outcomes.
b. Suppose at a later time it is revealed that Bob controls W. What else does this reveal?
c. Clearly this mix is inadequate as the six possible permutations are not equally likely. By adding one more 2-to-2 transaction, can you help Alice, Bob, and Carol design a better mix so that all six (3!) permutations are equally likely to an outside observer?
Hint: Adding one extra mix transaction is sufficient. The three 2-to-2 mixes can function independently, but one or more of the mixes must choose the ordering of outputs non-uniformly. You should describe the probabilities for each mix¡¯s outcomes if they are not uniform.
2. Selecting block proposers (2 marks): In a protocol like Algorand, participants privately compute a VRF output using their private key, which you can assume is a random real number between 0 and 1. For block bi, for each coin cj the coin¡¯s owner computes the following (using the private key kj assigned to the coin):
VRF(bi-1, cj, kj) < t/W
Assume that all coin owners compute and check the VRF for each coin they own. W is the total number of coins currently in circulation. In the limit as W grows to infinity:
a. In terms of t what is the expected number of coins per round which satisfy the above inequality, enabling their owner to act as block proposer for the round?
b. In terms of t, what is the probability in a given round that no participant will be able to propose a block?
c. In terms of t, what is the probability in a given round that there will be more than one coin which satisfies the above inequality and hence multiple blocks can be proposed?
d. In practical deployments, what problems are caused in a round if no block is proposed? What about a round where multiple blocks are proposed? Given this, should designers favor one type of failure over the other?
3. BLS Aggregate Signatures (1.5 marks). The BLS signature scheme supports aggregation. That is, given a set of messages m1... mn, public keys K1... Kn, and signatures ¦Ò1... ¦Òn there is an efficient O(n) function ¦Ò* = AggregateSigs(¦Ò1... ¦Òn) such that VerifyAggregateSig(K1... Kn,m1... mn, ¦Ò*) returns true if and only if for all 1 ¡Ü i ¡Ü n, VerifySig(Ki, mi, ¦Òi) returns true. The aggregated signature (like all BLS signatures) is just 256 bits. This can be useful in a cryptocurrency context.
a. Suppose Bitcoin wanted to add this feature to compress blocks. Each miner will now take all of the signatures in each block and aggregate them, producing a single aggregate signature for the block which is broadcast. Provide an estimate of how much bandwidth this would save for a full client verifying Block #735273 in the Bitcoin blockchain. How much would the cost savings vary for different blocks if different Bitcoin features are used more or less often?
b. Perform the same calculation for the cost savings possible from using aggregate signatures in Ethereum, using Block #14728204 as a case study. Again, how much would the savings vary as different features of Ethereum are used more or less often?
c. How could this be used to improve the efficiency of the Bitcoin-NG proposal? You don¡¯t need to look at concrete numbers in this case (since this isn¡¯t implemented anywhere yet).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com