Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi
Created February 4, 2019 03:46
Show Gist options
  • Save Haseeb-Qureshi/9f3e3300775277aa3c88e570d3a8d601 to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/9f3e3300775277aa3c88e570d3a8d601 to your computer and use it in GitHub Desktop.
Zexe: Enabling Decentralized Private Computation (SBC19)

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