Haseeb-Qureshi/zexe.md

## zexe.md

      
    Raw
  

              zexe.md
            
          
    Zexe: Enabling Decentralized Private Computation

Speaker: Pratyush Mishra


How can we do computing on distributed ledgers?

Many existing systems for smart contract execution

Ethereum, Tezos, EOS, etc.


They all work through re-computation—every party redundantly performs the computations to agree on state
This comes with scalability tradeoffs

Recomputing all of these programs is costly
Weakest computers (e.g. cell phones) can't keep up recomputing all transactions
This makes the network bottlenecked by the weakest nodes

Consensus-layer improvements can't make this any better


And privacy tradeoffs too

Anyone can see the executed program, inputs, and who invoked it
Permanently stored on the ledger


How can we fix these issues?


ZEXE is a ledger-based system that lets users conduct offline computations and publish transactions that attest to computations' correctness

Privacy: the transaction reveals no info about the offline computation
Succinctness: transactions are tiny and can be verified efficiently

|tx| < 1KB, verify(tx) in < 50ms


Functionality:

extensibility (user-defined functions)
isolation (malicious functions do not affect honest ones)
inter-process communication (functions should be able to interact)


Example applications:

private user-defined assets
private stablecoins
private DEXes


This talk won't describe ZEXE directly (you're not smart enough)

But we'll define some systems that use ZEXE and that will illustrate its properties


Trading digital assets

Custom, user-defined assets are the most successful application of smart contracts
E.g. ERC-20, ERC-721, stablecoins, etc.
How to trade such assets?

Centralized exchanges, but come on, that's boring
Decentralized exchanges—users control assets, that's cool

But no privacy

Every trade is settled on the ledger
Transactions reveal participating parties, assets, and values
Also enables frontrunning! Both by miners and users


Also high transaction costs


How to create private user-defined assets?

Zerocash paradigm

Every txn consumes old coins and creates new coins
Senders, receivers, and values are provably hidden
Every txn contains:

old coin serial numbers
new coin commitments
zero-knowledge proof showing that...

serial number corresponds to an entry in the UTXO set

somewhere in merkle tree, proven via merkle proof


shows that serial number was computed correctly given the coin's secret key
for new coins, shows that commitment corresponds to an actual coin
and asserts that input and output values are conserved (no value created or destroyed)


Zerocash achieves ideal anonymity for a single-asset blockchain


But we want to do this for multiple assets!
How to do this?
You could run Zerocash for every asset individually...

But then each asset would have its own separate anonymity pool
For long-tail assets, that's not a big anonymity set


You want each asset to somehow share in the same anonymity pool!
You can adapt Zerocash for coins to hold not just the VALUE of a UTXO...

But also an asset identifier, like an asset ID

E.g., ETH might be 1, WBTC might be 2, USDC as 3...


In the ZKP, now prove that not that the value is conserved...

but that the value is preserved FOR EACH ASSET ID
i.e., no new WBTC are created, no new ETH are created, and so on


So what does this buy us?

Multiple, private, user-defined assets in the same transaction

All in the same anonymity pool!


But assets are still isolated... they can't interact
This is problematic for interactions between assets, like DEXes


How can we generalize this construction to work with DEXes?

We add another field to each coin:

A "death predicate"

Basically a Bitcoin Script like predicate that you must satisfy to spend a coin


How to use this protocol to perform private atomic swaps

This is the key primitive for constructing DEXes
Basically you create a specific "death predicate" for a coin

In essence, checks that this coin is swapped within a txn for a given amount of a different asset


This gives us an atomic swap!
But how do we get order creation, order discovery, or trade finalization?


Many DEX Architectures have been proposed for this

Order-based DEXes

There's a central order book of orders published by makers

Order is tuple of (asset A, asset B, value A, value B)


Takers can scan for open orders and fill them
E.g. Radar Relay, IDEX


Index-based DEXes

Index maintains list of "intents-to-trade" published by makers

Intents are tuples of (asset A, asset B, public key)
No prices, just people who are interested in trading that asset


Takers scan for open orders and fill them

But filling these orders requires interacting with the maker


E.g. AirSwap


This talk will show how to construct an Index-based DEX (or Intent-based DEX)

Normal Intent-based DEXes have privacy leakage

When two parties find each other and then trade, that trade is settled transparently onchain
E.g., 5 units of OMG from Alice were traded for 2.5 units of USDC from Bob


But we want privacy in our system!

Trade privacy—no information about participants should be revealed
Trade confidentiality—no information about assets and values should be revealed


Here's how it would work:

Once maker and taker see order and decide they want to interactively trade...
Maker constructs a death predicate...

Which says he wants asset B, of value V
Sends this coin to the taker, along with secret key to claim the coin


If taker has corresponding coin of asset B and value V,

then he can send that coin to A
which satisfies the death predicate, allowing B to redeem A's send


This trade is both anonymous and confidential thanks to the augmented Zerocash protocol!


Boom, a private DEX!
Are we done?

N-n-n-n-n-not yet


What about assets with more complex policies?

Such as stablecoins or security tokens that have blacklists and whitelists
Easy—you already have death predicates, but let's add birth predicates!
Each coin has a birth predicate and a death predicate

A birth predicate could be used a whitelist or blacklist for new coin creation


Cool, so we built a private DEX. This system was kind of ad hoc though...

What we did with ZEXE was formalize how to create any system like this
In other words, a nano-kernel for maintaining on-chain records
Minimalist shared execution environment that defines rules for computing on these records
Given this, we construct a cryptographic primitive: decentralized private computation

This realizes a ledger-based records nano-kernel

In which transactions reveal NO information about computations


Take this theoretical primitive and construct a system: ZEXE

Leverage techniques from SNARKs, recursive composition, and efficient circuit design
Only the person performing the computation has to perform the computation

No redundancy like in other blockchains


Performance?

If you want to conduct a transaction with 2 inputs, 2 outputs

Takes about 80 seconds to create a transaction (purely the cryptography)
We expect this to halve at some point in the future