Quisquis: A New Design for Anonymous Cryptocurrencies

Most existing cryptocurrencies do not provide users with any meaningful levels of privacy. This has prompted the creation of privacy- enhanced cryptocurrencies, which however, also su􏰁er from some drawbacks: in both Monero and Zcash, the set of potential unspent coins is always growing, which means users cannot store a concise representation of the blockchain. Additionally, Zcash requires a common reference string and the fact that addresses are reused multiple times in Monero has led to attacks to its anonymity.
We propose a new design for anonymous cryptocurrencies, Quisquis, that achieves provably secure notions of anonymity. Quisquis stores a relatively small amount of data, does not require trusted setup, and in Quisquis each address appears on the blockchain at most twice: once when it is generated as output of a transaction, and once when it is spent as input to a transaction. Our result is achieved by combining a DDH-based tool (that we call updatable keys) with effi􏰂cient zero-knowledge arguments.

Transcript

1. Quisquis: A New Design for Anonymous Cryptocurrencies Prastudy Fauzi, Sarah Meiklejohn, Rebekah Mercer, and Claudio Orlandi
 Aarhus University / University College, London Thanks Claudio and Prastudy for slide inspiration!
2. Cryptocurrencies Network layer Transaction layer Consensus layer 2
3. The UTXO model 5 2 3 3
4. The UTXO model 5 2 3 4
5. The UTXO model 5 2 3 6 5
6. The UTXO model 5 2 3 6 5 2 3 6 1 6
7. The UTXO model 5 2 3 For reference, as of September 2019, the bitcoin blockchain is 243GB in size, but its UTXO set is only ~5GB. 5 2 3 6 1 7
8. Private cryptocurrencies There are different primitives available to help us: • Tumblers • Ring signatures • Zero-knowledge proofs/ zkSNARKS • Batching/aggregating
 
 
 8
9. Private cryptocurrencies And different questions to consider: • Coordination? • Trust in third parties? • Size of UTXO set? • Assumptions? • Plausible deniability? • Provable anonymity? 9 There are different primitives available to help us: • Tumblers • Ring signatures • Zero-knowledge proofs/ zkSNARKS • Batching/aggregating
 
 

10. The UTXO model in private cryptocurrencies y z x 10
11. The UTXO model in private cryptocurrencies y z x u 11
12. The UTXO model in private cryptocurrencies y z x u 2 w y z x u 12
13. In private cryptocurrencies, does the size of the UTXO set always increase? • In private cryptocurrencies based on ring signatures, typical transactions look like this: } + 13
14. • In private cryptocurrencies based on ring signatures, typical transactions look like this: } + • So here, the UTXO set size does always increase. In private cryptocurrencies, does the size of the UTXO set always increase? 14
15. • In private cryptocurrencies based on zero knowledge proofs, the situation looks like this: In private cryptocurrencies, does the size of the UTXO set always increase? 15
16. • In private cryptocurrencies based on zero knowledge proofs, the situation looks like this: In private cryptocurrencies, does the size of the UTXO set always increase? 16 • So here, the UTXO set size does always increase too.
17. • But this property isn’t inherent! • We use the following tools in order to get around this, in the UTXO and the account based setting: • Updatable public keys • Lightweight zero knowledge proofs In private cryptocurrencies, does the size of the UTXO set always increase? 17
18. The idea pks pk1 pk2 } { pk4 pk3 pkr We want to perform n-to-n transactions, without interaction.
 pks wants to send money to pkr, adding transactions from pk1 and pk2 to pk3 and pk4 for anonymity. 18
19. The idea How do we move other people’s money, while also preventing theft? pks pk1 pk2 } { pk4 pk3 pkr 19
20. An idea that doesn’t work The sender chooses random public keys and includes them in the transaction, with the constraint that the money stays where it is. This is great because it prevents theft! But it provides no anonymity. pks pk1 pk2 } { pk2 pk1 pkr 20
21. pks pk1 pk2 } { pk2’ pk1’ pkr But what if we have a way to update public keys! An idea that does work! 21
22. Updatable public keys pk1 pk2 pk3 pk4 22
23. Updatable public keys } { Updatable public keys allow users to create updated public keys, without changing the underlying secret key. pk1 pk2 pk3 pk4 pk1’ pk2’ pk3’ pk4’ 23
24. Updatable public keys } { Shuffling these keys then allows us to hide which of the updated keys is associated with which initial key. pk1 pk2 pk3 pk4 pk1’ pk2’ pk3’ pk4’ 24
25. Updatable public keys } {pknew Updated public keys are indistinguishable from freshly generated public keys. pk1’ pk2’ pk4’ pk1 pk2 pk3 pk4 25
26. Updatable public keys Senders take the keys of other users, including their intended recipients, to form a list of public keys that act as the input to a transaction. pks pkr pk1 pk2 } { pk1’ pk2’ pks’ pkr’ 26
27. Updatable public key construction 27 • Gen( ) : sk = x; choose random s; 
 pk = (gs, gsx) = (a, b) • Update(pk) : choose random r; pk’ = (ar, br) 
 
 Correctness : ✅

28. Updatable public key construction 28 • Gen( ) : sk = x; choose random s; 
 pk = (gs, gsx) = (a, b) • Update(pk) : choose random r; pk’ = (ar, br) 
 
 Indistinguishability : (a, b, ar, br) ~ (a, b, ar, bs), from DDH
29. Updatable public key construction 29 • Gen( ) : sk = x; choose random s; 
 pk = (gs, gsx) = (a, b) • Update(pk) : choose random r; pk’ = (ar, br) 
 
 Unforgeability : outputting x from pk is equivalent to breaking DL
30. We associate each public key with a secret value, and call this pair an account.
 } { Account based model pks, vs pkr, vr pk1, v1 pk2, v2 pks’, vs’ pkr’, vr’ pk1’, v1’ pk2’, v2’ 30
31. Updatable account construction • Accounts are a public key and a commitment to a balance associated with the public key. • We have pk defined as before ((a, b) = (gs, gsx)), and the commitment com(pk, v) = (a, gvb) 31
32. Anatomy of a transaction - Sender: pks
 - Receiver: pkr
 - Random: pk1, pk2 32 - pkr’ = Update(pkr)
 - pk1’ = Update(pk1)
 - pk2’ = Update(pk2) } { pks, vs pkr, vr pk1, v1 pk2, v2 pks’, vs’ pkr’, vr’ pk1’, v1’ pk2’, v2’
33. Anatomy of a transaction Accompanied by a zkp for the following:
 - not revealing which ones, “n - 1 of these public keys were updated using Update( )”;
 - “I know the sk corresponding to the last public key” 33 } { pks, vs pkr, vr pk1, v1 pk2, v2 pks’, vs’ pkr’, vr’ pk1’, v1’ pk2’, v2’
34. Lightweight zero- knowledge proofs • The sender proves that they have correctly updated the keys and have not taken money from anyone except themselves. • The witness for the zero-knowledge proof is limited to this single transaction, so we use discrete-log-based techniques. • Other tradeoffs could be achieved instead: it is possible to instantiate Quisquis with zk-SNARKs. 34
35. Lightweight zero- knowledge proofs • The sender proves that they have correctly updated the keys and have not taken money from anyone except themselves. • The witness for the zero-knowledge proof is limited to this single transaction, so we use discrete-log-based techniques. • Other tradeoffs could be achieved instead: it is possible to instantiate Quisquis with zk-SNARKs. 35
36. Lightweight zero- knowledge proofs • The sender proves that they have correctly updated the keys and have not taken money from anyone except themselves. • The witness for the zero-knowledge proof is limited to this single transaction, so we use discrete-log-based techniques. • Other tradeoffs could be achieved instead: it is possible to instantiate Quisquis with zk-SNARKs. 36
37. • We need to prove three statements about each transaction: • No balances go below zero. • Total value in is equal to the total value out. • For each public key in the initial set, either: • You know the private key, and the value decreased, or the new key is an updated version of the old key, and the value has not changed. Making a lightweight proof 37
38. • We need to prove three statements about each transaction: • No balances go below zero. • Total value in is equal to the total value out. • For each public key in the initial set, either: • You know the private key, and the value decreased, or the new key is an updated version of the old key, and the value has not changed. Making a lightweight proof 38
39. • We need to prove three statements about each transaction: • No balances go below zero. • Total value in is equal to the total value out. • For each public key in the initial set, either: • You know the private key, and the value decreased, or the new key is an updated version of the old key, and the value has not changed. Making a lightweight proof 39
40. • We need to prove three statements about each transaction: • No balances go below zero. • Total value in is equal to the total value out. • For each public key in the initial set, either: • You know the private key, and the value decreased, or the new key is an updated version of the old key, and the value has not changed. Making a lightweight proof 40
41. • The most straightforward way to prove these statements would be with an OR proof for each of the public keys selected. Making a lightweight proof 41
42. • This means, for each of them, there is a proof that says ‘either I know the sk of this pk OR it’s an updated pk and the value is the same as before’ • This means the size of the proofs would be proportional to the number of parties in a transaction, multiplied by the number of options for statements. • Instead, we can make use of shuffle arguments, with an intermediate offline step. Making a lightweight proof 42
43. • This means, for each of them, there is a proof that says ‘either I know the sk of this pk OR it’s an updated pk and the value is the same as before’ • This means the size of the proofs would be proportional to the number of parties in a transaction, multiplied by the number of options for statements. • Instead, we can make use of shuffle arguments, with an intermediate offline step. Making a lightweight proof 43
44. • This means, for each of them, there is a proof that says ‘either I know the sk of this pk OR it’s an updated pk and the value is the same as before’ • This means the size of the proofs would be proportional to the number of parties in a transaction, multiplied by the number of options for statements. • Instead, we can make use of shuffle arguments, with an intermediate offline step. Making a lightweight proof 44
45. • The sender selects their anonymity set, puts their own pks at the top, the recipients’ pks next, and the anonymity set pks after that. Making a lightweight proof 45 pks, vs pkr, vr pk1, v1 pk2, v2
46. • They prove they know sks of pks, vs does not go below zero, the vi are unchanged, and the total value is unchanged. Making a lightweight proof 46 pks, vs pkr, vr pk1, v1 pk2, v2 pks’, vs-v pkr’, vr+v pk1’, v1’ pk2’, v2’
47. • Keys are shuffled with a verifiable shuffle, and the proof and output public keys and values are sent to the network as a transaction. pks, vs pkr, vr pk1, v1 pk2, v2 pks’, vs-v pkr’, vr+v pk1’, v1’ pk2’, v2’ pks’, vs-v pkr’, vr+v pk1’, v1’ pk2’, v2’ Making a lightweight proof 47
48. Comparisons 48
49. Benchmarks 49
50. Thanks! Questions? Quisquis summary & future directions: - Non-growing UTXO set: theoretical and practical optimisations - Theft prevention: 
 other applications for updatable public keys and design principle? - Anonymity: 
 empirical analysis? 50