Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi

Haseeb-Qureshi/quisquis.md

Created February 3, 2019 05:41
Show Gist options
  • Save Haseeb-Qureshi/7c077b9a9cb731e718cbf05daef40ac9 to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/7c077b9a9cb731e718cbf05daef40ac9 to your computer and use it in GitHub Desktop.
Download ZIP
Quisquis: A New Design for Anonymous Cryptocurrencies (SBC19)
Raw
quisquis.md

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!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment