Scalability
===========

What are the scalability issues for blockchain?
  Want to process more transactions per second--what is bottleneck?
    2 possible bottlenecks: block size or transaction processing
  Want to reduce size of the blockchain state needed by full nodes
  Also want to reduce data needed for SPV wallets

Can Bitcoin just increase the blocksize?  Not without a hard fork
  Bitcoin hates hard forks, and in fact Bitcoin cash (BCH) is such a fork

Another idea: soft-fork move some data out of main block (SegWit)
  Recall transactions can have separate "Witness data"
    Stored in separate Merkle tree outside main block
    Bogus 0-BTC coinbase output has RETURN PUSH <0xaa21a9ed || merkle-root>
    Witness data organized in same order as transaction inputs
  Introduce 2 new ScriptPKs:
    P2WPKH - OP_0 <20-byte Public-Key-Hash>      (the 0 is a version number)
      ScriptSig empty, witness data: <signature> <pubkey>
      Can be nested inside a P2SH for backwards-compatible address
    P2WSH - OP_0 <32-byte script hash>
      ScriptSig empty, witness data: <stack-val> [<stack-val> ...] <script>
  Allows more transactions per block - 4 million "units"
    Transaction data now costs 4 "units", witness data 1 "unit"
  Note two other huge benefits of this scheme:
    Solves malleability - signature no longer affects txid
    You can calculate the transaction id of an unsigned transaction
      E.g., sign a transaction to spend a UTXO that doesn't exist yet

SegWit is great idea, turned out to be very difficult to deploy
  To lock in a change, 95% of miners (by hash power) must signal support
  Couldn't get support. Speculation: Asicboost https://arxiv.org/abs/1604.00575
    SHA256 processes input in 64-byte chunks:
      Expand each chunk, then compress it with state to get new state
    Bitcoin header is 80 bytes, requires two chunks
          4   version      Block version information
          32  prev_block   Hash of previous block
          32  merkle_root  Transactions in this block
          4   timestamp    When block created
          4   bits         Hash target = (bits&0xffffff) << 8*(bits>>24 - 3)
          4   nonce        Nonce used to generate this block
      Last 4 bytes of Merkle root lie in second chunk
    Optimization: find Merkle roots that collide in last 4 bytes
      (Not so hard with birthday paradox)
      Now for each nonce and all collisions, only expand second block once
      Potentially ~20% faster
    Technique is patented, but Bitmain might support it; controversial
    But finding Merkle collisions harder with SegWit
      Typically just reorder transactions, now must reorder witness data, too
  Idea: who cares if miners support it, they need to sell Bitcoin
    Led to movement for "User-activated soft fork" (UASF)
    Different activation mechanisms for UASF and miner-activated
      Danger of split caused Bitcoin price to tank somewhat
    Last-minute compromise (BIP91) averted the split

But even better than more transactions per block is off-chain transactions
  Idea:  Use chain for net settlement, not gross settlement
  Say A buys coffee from B every day, only wants to hit blockchain once/month
  Idea 1:  Place deposit 30 coins in 2-of-2 A+B multisig escrow UTXO E
    Day 1: A signs tx A1 on E paying B 1 coin, and A 29 coins change
    Day 2: A signs tx A2 on E paying B 2 coins, and A 28 coins change
    End of month: B co-signs and submits only last transaction An to close tab
  What's wrong here?  If B disappears, A loses unspent funds!
  How to fix?  Remember timelock?  let A reclaim funds if B doesn't close tab
    Use SegWit for funding transaction E, so know txid before signing it
    B signs refund tx C1 sending E back to A, with locktime now + 30 days
    A signs and submits E only once she has C1 signed by B
  Still two annoying problems
    - What if you want to reverse the channel (B pays A)?
    - You still have to touch the blockchain once per month

How might we reverse channel?  Create alternate refund transaction
  A signs closing transaction C2 for B, locked to 1 day earlier than C1
    Now B can sign B1, B2, paying A by giving her half-signed transactions
    Each transaction is better for A than last, so no incentive to cheat
  But we are shortening the clock each time we reverse direction

New feature: recycle sequence field of input for relative timelock (BIP68)
  Low 16 bits specify time or block height since corresponding output mined
    Not very useful example: C1 could use sequence for locktime relative to E
  OP_CheckSequenceVerify (BIP 112) can require minimum delay on input
    To sequence field what OP_CheckLockTimeVerify does to locktime
  Idea: use OP_CSV to let A *revoke* her transaction
    Use this ScriptSig for funding transaction(E):
      HASH160 <CR-HASH> EQUAL IF <PKB>
      ELSE "24h" OP_CSV DROP <PKA> ENDIF CHECKSIG
    B can immediately spend this UTXO if he knows hash preimage CR of CR-HASH
    A can spend this UTXO 24 hours after it hits the blockchain
  Now when A signs A1, she also gives B R, revoking E
  For bidirectional, each of A, B gives the other a *commitment transaction*
    E.g., A signs transaction splitting balance and gives to B, letting
      - A claim its output immediately if B signs and submits transaction
      - B claim its output 24 hours after submitting the transaction
      - A claim B's output if A can produce CRB (chosen by B)
    B signs the mirror image of this transaction and gives to A
  For subsequent transactions, each of A and B gives the other a 
    So channel never expires!
  Use same idea to make channel reversible
    At each step, both sides sign a commitment transaction.  E.g., for 28-2
      A signs tx giving A 28 BTC immediately, B 2 BTC w. OP_CSV 1 day
      B signs tx giving A 28 BTC w. OP_CSV 1 day, B 2 BTC immediately
      Each of A,B reveals hash revoking any prior transaction
  Note: instead of hashlocking, can also revoke by revealing private keys
  This is great, except that funding transaction must still hit blockchain
    Don't want to create N^2 channels for N people
    Too much state, too many coins locked up

Idea: route payments through third parties
  A and B each have bi-directional payment channel to C
  A sends 1 BTC to C, then C sends 0.99 BTC to B (keeping small fee)
  What can go wrong here?
    1. C just keep the funds if she is not honest
    2. B denies receiving funds, claims 0.99 BTC from someone else via C

Use idea of "pay to contract"
  B picks random value R, gives A H(R), then signs dumb (legal) contract:
    "I'll consider myself paid by A if I she produces hash preimage of H(R)"
  Remember hash-locked contracts?  Can solve #2
    HASH160 <R-HASH> EQUALVERIFY <PKB> CHECKSIG
  How about solving #1?  Warmup: how to pay via C with no channels?
  Remember Hash Time-Locked contracts (HTLC)?  A can reclaim at time T
    IF HASH256 <R-HASH> EQUALVERIFY <PKB>
    ELSE <T> OP_CLTV DROP <PKA> ENDIF CHECKSIG
  Use a cascading series of payments with shorter expiration times
    A pays C with expiration now + 2 days
    C pays B with expiration now + 1 day
    B reveals pre-image R to claim funds (so legally received them)
    C sees R, uses it to claim funds from A
  What happens if B reveals R after 1.1 days?
    A pays, C gets to keep the money, but A satisfied B's legal contract
  What happens if B reveals R after 2.1 days? contract satisfied for free

How to do this with channels?  (see BIP 112)
  Now each commitment transaction has 3 outputs:
    Pay to A, pay to B, and pay to A or B depending if R known by time T
  Construct a *revocable* HTLC for the third output
  - In commitment transaction A gives to C, third output has:
      HASH160 DUP <R-HASH> EQUAL
      IF "24h" CHECKSEQUENCEVERIFY 2DROP <PKC>
      ELSE <CRC-Hash> EQUAL NOTIF <T> CHECKLOCKTIMEVERIFY DROP ENDIF
           <PKA> ENDIF
      CHECKSIG
    So A can spend if C revoked by revealing CRC, or if time T is passed
    C can spend by revealing R and waiting 24h in case revoked
  - In commitment transaction from C to A
      HASH160 DUP <R-HASH> EQUAL SWAP <CRA-Hash> EQUAL ADD
      IF <PKC>
      ELSE <T> CHECKLOCKTIMEVERIFY "24h" CHECKSEQUENCEVERIFY 2DROP <PKA> ENDIF
      CHECKSIG
    So C can spend immediately if it knows either R or CRA
    A must wait until time T and until 24 hours after submitted
  Good reference:  <https://github.com/ElementsProject/lightning/blob/master/doc/deployable-lightning.pdf>

This is called lightning; currently implemented in specification called Bolt
  <https://github.com/lightningnetwork/lightning-rfc>
  P2P network for discovery of nodes, channels
  E.g., Channel establishment protocol between funder A and fundee B:
    +-------+                              +-------+
    |       |--(1)---  open_channel  ----->|       |
    |       |<-(2)--  accept_channel  -----|       |
    |       |                              |       |
    |   A   |--(3)--  funding_created  --->|   B   |
    |       |<-(4)--  funding_signed  -----|       |
    |       |                              |       |
    |       |--(5)--- funding_locked  ---->|       | (indicates sufficient
    |       |<-(6)--- funding_locked  -----|       | block depth for anchor)
    +-------+                              +-------+
  See network explorer <https://1ml.com>:  4k nodes, 12k channels, 112 BTC
  Note: routing fees can be negative as well as positive--why?
    May want to incentivize people to refill depleted channels
  Note 2: works across block chains: A->C on BTC, with C->B on LTC
    open_channel message includes "chain_hash" identifying chain
    R can release payments on two blockchains, just like cross-chain swap!