Quisquis: A New Design for Anonymous Cryptocurrencies

Speaker: Prastudy Fauzi

Bitcoin and Anonymity
- "Bitcoin is like Twitter for your bank account" — Ian Miers
Current Anonymous Cryptocurrencies and Their Limitations
- Dash, Monero, Zcash
- What technologies do they use?
- Tumblers (Dash), Ring signatures (Monero), SNARKs (Zcash)
- Questions you should ask yourself:
  - Do these protocols require coordination?
  - Do they have plausible deniability?
  - Provably anonymous?
  - Require trust in third parties?
  - How large are the UTXOs?
- On Tumblers
  - Centralized tumblers are easy, but requires trust
  - Decentralized tumblers are complex and require interactive, but are provably secure
    - See TumbleBit, etc
- On Ring Signatures
  - Ring Signatures allow multiple signers to have indistinguishable signatures
  - How to use Ring Signatures for anonymity?
    - Every UTXO, when it is spent, is involved in a ring signature
    - But since the ring has many plausible inputs, you don't know for sure that it was spent
    - Hence, you usually cannot prune the UTXO set, because you don't know what was actually spent
    - Thus the UTXO set keeps growing and growing! This is bad.
    - There are times when insufficient ring sizes and decoy selection can cause inputs to be revealed
      - Via process of elimination
  - On Zero Knowledge Proofs
    - Privacy-wise, can think of them as an extension of ring signatures, using fancier crypto
    - Can hide in anonymity sets (number of potential inputs) of UNBOUNDED size
      - I.e., the entire shielded pool in Zcash could be the input of a shielded txn
    - But generation time for transactions are high! And need for trusted setup.
  - Drawbacks with these?
    - Nothing offers all of anonymity, deniability, and theft prevention
    - Zcash and Monero cause monotonic growth of the UTXO set
    - Zcash is not particularly efficient
QuisQuis basic idea
- S wants to send money to R—how to hide?
- Add decoy transactions flying around to provide cover and anonymity
- But wait... how to construct those decoy transactions?
  - Can we move other people's money without their approval...?
  - While also preventing theft?
- What if we have A send money to A', where A' is a random looking address OWNED by A?
  - For this, we need updatable public keys
    - public key can be "updated" with nonce to produce pk'
      - but should still verify the same signature as original public key
    - we want an unforgeable construction—given pk', you shouldn't be able to learn sk.
- QuisQuis construction:
  - Gen -> pk = (g^s, g^sx) = (u, v), sk = x
    - I.e., pk is raising a group element to some exponent s and then a multiple of that exponent, x * s
    - Your private key is the x that u is raised to, producing v
  - Update(pk, r) -> pk' = (u^r, v^r)
    - I.e., you can tweak the public key by raising both elements to an exponent r
    - Becomes (g^sr, g^sxr)
      - The relationship between u and v is retained
  - Correct: yep
  - indistinguishable: any two pairs cannot be told apart from random without knowing x
  - Unforgeability: you can only find x if you've broken the discrete log
- Basic QuisQuis transaction:
  - Real input pk_s
  - Real output pk_r
  - Run update(pk_r) -> pk_r'
  - Pick random pk_A from UTXO set
  - Run update(pk_A) -> pk_A'
  - Then provide a zero-knowledge proof for the following statement:
    - "N - 1 public keys were updated correctly (hiding which ones)"
    - "I know the secret key corresponding to the last public key (and therefore I can spend it)"
- Towards the full construction...
  - This was of course simplistic
    - We assumed every PK held exactly 1 coin
    - Thus, no need to obscure PKs holding multiple UTXOs
    - Or having different values
  - We want to deal with variable amounts associated to keys
    - While also hiding amounts!
  - Instead, we'll have each public key have an associated balance, bl
    - The balance is stored in a homomorphic commitment
      - This allows it to be modified without knowing its value
    - Transactions are now "redistributions of value" among all balances
  - Accounts
    - Now pairs of public keys and commitments to the balance
    - acct = (pk, Com(pk, bl))
      - pk = (u, v)
      - Com(pk, bl) = (u^r, g^bl * v^r)
  - Accounts can be updated similarly
    - Update(acct = (pk, Com), v)
      - pk' = Update(pk)
      - c' = c * Com(pk, v)
      - Output acct' = (pk', c')
    - Worth noting:
      - The secret key is the same
      - Value can be increased/decreased by v
      - acct' cannot be linked to original acct!
- True QuisQuis transactions
  - Real sender: acct_s (loses v of currency)
  - Real receiver: acct_r (receives v of currency)
  - Pick random acct_A from UTXO set
  - Run update(acct_s, -v) -> acct_s'
  - Run update(acct_r, +v) -> acct_r'
  - Run update(acct_A, 0) -> acct_A'
    - This is your anonymity set!
  - Construct ZK proof that everything was done correctly:
    - All accounts were updated correctly, with amounts >= 0
    - Except one, for which I knew the secret key, whose balance was >= v
- Properties of QuisQuis
  - UTXO set does not grow
    - Only last version of accounts need be stored
  - Theft prevention
    - Can only withdraw from your own account (assuming balance is positive)
  - Anonymity
    - Updated accounts in the output are unlinkable to accounts in the input set
    - Commitments hide the value
    - ZK proof hides the relationship between inputs/outputs and the value that was transferred
  - Implemented the ZK proofs in Go:
    - Anonymity set of 4 requires 6.5KB txn size, 124ms generation, 25ms verification
    - 16 requires 13.4KB txn size, 471ms generation, 71ms verification
    - 64 requires 36KB txn size, 2110ms generation, 251ms verification
  - Zcash is 0.29KB txn size, 27,000ms generation, 8 verification
    - This seems pre-JubJub? Generation is down to ~3000ms AFAIK
  - Monero is 2.71KB txn size, 982ms generation, 46ms verification
  - This puts QuisQuis at ~5x txn size of Monero, 40x size of Zcash
    - Also 2x slower verification than Monero, 10x slower than Zcash
    - But much faster proof generation than both (471 QQ vs 982 XMR vs 21K ZEC)
  - Cool!

Haseeb-Qureshi/quisquis.md

Quisquis: A New Design for Anonymous Cryptocurrencies

Speaker: Prastudy Fauzi