Zexe: Enabling Decentralized Private Computation (SBC19)

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