Haseeb-Qureshi/quisquis.md

## quisquis.md

      
    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!