Decentralized exchanges ======================= Lightning scales payments. What about scaling Ethereum smart contracts? Warmup: Let's outsource verification of smart contract execution (TrueBit) Not re-executing smart contracts saves Miners computation--more tx/sec But what if they mine a block with incorrect smart contract results? Idea: outsource verification Allow anyone to challenge that a contract was properly executed Reward someone who successfully challenges a smart contract execution Intentionally include bad executions, incentivizing people to check But how can miners efficiently adjudicate challenges? Require solver to checkpoint state at many points during computation Challenger performs binary search to fine first incorrect computation step Minder need only replicate one step to see it was executed incorrectly Should give constant factor improvement in tx/sec--can we do better? Straw man: use sidechains to scale the number of transactions/sec Move ETH to 2-way pegged sidechain Transact in parallel on sidechain When done, move funds back to root chain (ETH mainnet) or other sidechain If possible, use cross-chain swaps to root or between sidechains Problem? How to trust sidechain miners? What if sidechain forks/misbehaves? Idea: Use bonded side-chains based on proof-of-stake with root chain stake If validators misbehave, have root chain adjudicate problem Must allow people to raise fraud when sending funds back to root chain Use bonded proofs of which transactions spent/unspent Roll back bad blocks and slash bad miner's ETH stake on root chain Plasma: Scalable Autonomous Smart Contracts (https://plasma.io/) Effectively bonded trustless child chain, using proof-of-stake For each 100 blocks, validator only gets rewarded up to percentate stake No incentive to mine more than your fair share of blocks Encourages round-robin, without hard-coding mechanism for doing so Correct chain tip is the chain with highest summed weight of mining rewards Child chain root block gets included in parent chain All child validators must also be parent chain full nodes Tree-structured child chains admit compact proofs Contracts are maintained in the root chain Child maintains UTXO set that subdivides balance in root chain account Use trie for merkelized proofs, and bitmap parsable by others Allow fraud proofs for all state transitions like TrueBit E.g., prove an input is in the UTXO set, or that a tx was properly signed state transitions should include a signature, state updates (e.g. destination, amount, token, and any other associated state data), as well as some kind of TTL for expiration and a commitment to a particular block. Fast finalization of transactions: 1. A signs, broadcasts payment to B in child plasma chain 2. Transaction included in child block whose header committed to parent 3. A & B get block and sign acknowledgment submitted to next child block Ensures there was no block withholding attack [Alternative: finalize when hash preimage released, for cross-child] Slow finalization when things go wrong: Only #1: A doesn't know if transaction committed, can withdraw Only #1-2: A may or may not withdraw depending on what B knows Parent to child deposit Send coins to contract on parent chain, but recoverable for some period The child chain includes an "incoming transaction proof" After which depositor gets information to generate a fraud proof Depositor signs activation message for transaction on child chain Once it has seen incoming transaction proof commitment Means depositor knows s/he can withdraw funds from child chain Withdrawal from child to parent Signed withdrawal submitted to parent blockchain (whole UTXOs only) Request discloses UTXO bitmap position Also includes large bond to penalize false request Child validators see parent, so now prevent spending of withdrawn UTXO Wait predefined timeout period for anyone to submit disputes If anyone can prove UTXO already spent, withdrawal aborted & bond slashed Wait another timeout for parent to hear of withdrawals at lower block height Ensures committed withdrawals are processed in child chain order After timeout, process withdrawals in child chain order What happens under a block-withholding attack? Can still withdraw even if child blocks unavailable But users only have a limited window to exit (like lightning) Can organize "mass exit" to a replacement plasma blockchain Users sign that they have not finalized their UTXOs Mass exit initiation transaction (MEIT) contains merkelized UTXO bitmap Can use plasma recursively to scale to arbitrarily high transaction rates What's the downside? Cross-chain doesn't necessarily scale What's wrong with centralized token exchanges? Most trade volume today handled by such exchanges (coinbase, kraken, binance) But requires giving custody of your tokens to the exchange Serious solvency, fraud risk (c.f. mtgox) May miss out on forks and airdrops if exchange doesn't claim No transparency means you might not get the best price Different prices across exchanges for some tokens Not arbitraged because... low volume? withdrawal limits? regulatory issues? So why not just reimplement binance-like orderbook as a dApp? API: makeOffer, cancelOffer trade ERC20 tokens at some price hypothetical dApp automatically fills crossing orders Cost - lots of gas required to do order matching in solidity particularly expensive for market makers frequently updating offers Scalability - most centralized exchanges had growing pains, dApps harder Governance - how to update code? whom to hold responsible? Block time - updating offers at 15sec granularity hard for market makers 3-way trade-off between: update time, spread, and depth high update times => large spreads and/or market maker needs lots of tokens Missing functionality - inability to short is bad for market makers Note: open problem, but potentially promising research topic So why not implement your market maker as a dApp? Bancor did this Automatically price token based on supply (#issued) and reserve token balance Arbitrarily set constant reserve ration (CRR) parameter, e.g., 10% Price = reserve-token-balance / (supply * CRR) + dApp reacts to each trade without waiting for a block confirmation - knows nothing of external markets and will always trail them Read a devastating takedown of Bancor here: 0x approach: "Off-chain relay with on-chain settlement" (Fig. 2) Maker and Taker approve DEX contract to access their ERC20 token balances Maker creates signed order structure completely off chain (Fig. 3) Offers valueA units of tokenA for valueB units of tokenB Also include expiration time, fees, and a fee recipient A taker then signs such an order and sends it to the DEX Optionally includes a valueFill amount to buy fewer tokenA than offered DEX transfers tokenB from taker to maker, tokenA from maker to taker DEX records filled amount for each order it fills or partially fills Prevents replay, allows multiple takers for big order DEX contract API overview: fillOrder - execute an order matchOrders - take two crossing orders and have them fill each other cancelOrder - record order (if not seen), set filled amount to valueA cancelOrdersUpTo - cancel a batch of orders (use salt field as counter) several more, especially for supporting batching efficiently As a taker, how do you get an order? [Any way you want] Build off-chain order relays that provide order matching service Can use order fees to compensate relay service Fees can also be paid to a contract for complex payout E.g., reward multiple nodes that have forwarded order through P2P network What guarantee does taker have of getting the best price? None But taker must sign order and call fillOrder, so can check price What if taker does not fill order? Ultimately, orders like options, but makers typically pocket the spread Possible annoyance if market matches one buyer to one order But market can give multiple takers same large offer Takers can also submit a batch orders How do you upgrade the DEX contract? Straw man, just release new contract, users start using Bad for liquidity if everyone does not update simultaneously Instead, use proxy that can upgrade underlying DEX contract version But who can update what proxy points to? ZRX token holders vote ZRX also used to pay fees to relayers ZRX also used to vote on token registry Assigns human-readable names to traded tokens Could the Fed & ECB issue 1T USD and 1T EUR as ERC-20 tokens, trade on 0x? Proxy presents too much risk--can buy all ZRX and steal $1T What if we fix DEX contract and don't allow upgrades? Unfortunately, with $1T "bug bounty", consensus layer is vulnerable Just rent a bunch of GPUs to fork ETH chain and double-spend $1T How can a blockchain secure arbitrarily valuable tokens? Stellar: build native token and DEX support into blockchain Unlike solidity, can heavily optimize implementation around DEX Also want very low gas fees and very low block time And need to support tokens with bigger market cap than blockchain Last two points require non-mining based consensus Don't want to rely on transaction fees to incentivize consensus Asset issuers themselves need the ability to veto double-spends Can't trust anyone else if you have the most valuable asset Finally, since less general, try to be less error prone than Ethereum Non Turing-complete transactions just atomically execute list of operations Stellar consensus protocol (SCP): decentralized Byzantine agreement Achieves consensus among known validators, relying digital signatures Stellar validator like Bitcoin full node, *not* like Bitcoin miner No need to pay validators to incentivize them Each asset issuer runs/designates an official validator (and public key) E.g., "to redeem token, send it back to us & wait for *our* validator" Protects issuer against forks (assuming its own validator is secure) Also tells token holders which validators provide finality Problem: How to achieve consensus among validators Strawman: Use PBFT (3f+1 validators, tolerate f faults)--What's wrong? Who gets to pick these 3f+1 validators? (too much centralized control) How to protect token issuers not among the 3f+1? Key idea: define quorum in a decentralized way using *quorum slices* Each node designates one or more sets of nodes called quorum slices Sets of nodes big or important enough to represent whole network If you pick only one quorum slice, guaranteed to stay in sync with it If you pick multiple (for redundancy) will stay in sync with one of them Examples of plausible quorum slices: - Require validators of top 10 assets by market cap - Require 7/10 of top 10 assets (to survive outages) - Require 2/3 of validators from each of top 10 (organizations may have multiple validators for availability) - Require just the one bank where all your checks get deposited (reasonable for an end user--you are toast if your bank is bad) Define quorum as a set containing a quorum slice of each member E.g., your slice is just your bank, but your bank depends on other banks Smallest quorum for you includes many banks Transitivity leads to global quorums in decentralized way Requires assumption of global interdependence analogies: internet peering, existing correspondent banking relationships Which replaces PoW assumption that all miners want to maximize ETH No longer depend on value of cryptocurrency to secure issued tokens SCP eliminates cost of mining, improves on delay (5-second block time) Still need to ensure DEX is efficient Design decisions conducive to an efficient DEX Chose data model easily represented in database tables. 4 basic types: - Accounts: Metadata and list of signers (e.g., public keys) - Trust lines (bad name): An account's balance in some asset - Offers: Offers to trade X amount of one asset for another - Data: simple key-value store associated with each account Make history (blockchain) much cheaper than space in database (~UTXO set) Don't require history to validate database or initialize a validator Include database checkpoint in each consensus value Don't even serve history from a validator Push history off to separate storage infrastructure (e.g., a CDN) Stragglers downloading history should not affect validator performance Allows small transaction fee Allows higher charges for occupying database, but refundable Database entries increase minimum balance on an account c.f. Ethereum SELFDESTRUCT or deleting storage Can take money back by deleting data (deleting offers, merging accounts) How to change tx fees or upgrade protocol? Vote in decentralized quorums Consensus value actually includes 3 things: Timestamp - Time at ledger close Ledger state - Hash tree of ledger state, latest txs, and tx results Upgrades - Changes in parameters or upgrade protocol Each validator recognizes three categories up upgrades Desired - Administrator has configured validator to vote for this Valid - Validator knows how to implement it Invalid - Not supported (e.g., upgrade to unknown protocol version) If Desired reaches quorum threshold, system implements upgrade If many consider invalid, will not reach quorum