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