Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi

Haseeb-Qureshi/multi_hop_locks.md

Created February 3, 2019 17:47
Show Gist options
  • Save Haseeb-Qureshi/56caec2ccf58eef13d2c31e440d94a25 to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/56caec2ccf58eef13d2c31e440d94a25 to your computer and use it in GitHub Desktop.
Download ZIP
Privacy-preserving Multi-hop Locks for Blockchain Scalability and Interoperability (SBC19)
Raw
multi_hop_locks.md

Privacy-preserving Multi-hop Locks for Blockchain Scalability and Interoperability

Speaker: Pedro Monero-Sanchez

  • Payment channels are a widely pursued layer 2 scaling solution
    • But they only solve for bidirectional payments (between the two parties who open the channel)
  • What if we build a payment channel network?
    • Naive solution—every pair of parties (N^2) opens a channel with each other
      • But then we need to lock up an exorbitant amount of capital in all these channels
    • Instead, let's open a few channels for each party
      • And rely on other intermediary channels to reach the intended receiver
    • This is the core idea of all payment channel networks
      • Ex:
        • Bitcoin: Lightning network, c-lightning, Eclair
        • Ethereum: Raiden
        • Zcash: Bolt
        • And eventually each blockchain might need a similar network for payments scalability
  • Security in payment channel network
    • "Balance security"
      • Honest users should not lose coins in an off-chain payment
    • Security tool:
      • We use hash-time lock contracts (HTLCs), which are payments that are conditioned on revealing the preimage to a hash function
        • We do multihop payment by chaining these HTLCs
          • (this is the core of the Lightning Network)
      • E.g., if you're routing a payment from A -> B -> C
        • C comes up with an H(x) = y
        • C communicates her hash, y, to A
        • A sends a payment to B with an HTLC that will be released given the preimage of y
        • B sends a payment to C with an HTLC that will be released given the preimage of y as well
          • (Note: A must send more than B sends, since A needs to pay B a small routing fee)
        • C reveals x, which unlocks her payment from B
        • B, seeing that x, also reveals on his own HTLC which releases the payment from A
        • Note: HTLCs have a timeout in case C goes offline or full payment route is not found
  • Novel "Wormhole Attack"
    • Idea: exclude intermediate honest users from successful completion
    • Consequence: Adversary can steal routing fees from honest users
    • E.g., imagine a long payment chain of A -> M -> B -> M -> C
      • M controls two links in the payment chain, sandwiching B
      • Imagine routing fees are A, 1.3 -> M, 1.2 -> C, 1.1 -> M, 1.0 -> C
      • When M gets the preimage x from C, he can report to B (the guy stuck in the middle) that the payment failed...
        • This cancels the 1.2 payment to B and the 1.1 payment from B...
      • But M then reports to A, in the first hop, that the payment succeeded!
      • Thus he receives 1.3 from A and only paid out 1 to C, despite only routing for two hops (gets 50% more routing fees than he should)
    • This attack is caused by each hop having the same preimage
    • This might seem unimportant, but fees are the key incentive behind payment channel networks!
      • The more intermediaries, the more profitable this attack
  • Privacy in payment channel networks
    • What we want is "Relationship anonymity"
      • I.e., the adversary cannot tell who is paying to whom
    • If an adversary has channels open with end users, this property is trivially broken
      • Just look and see if payment from A -> M -> ... -> M -> C has the same HTLC hash
  • Other practical considerations
    • Scalability issues
      • Need two keys to define a deposit (i.e., which channel?)
      • Payment condition + signatures required onchain
    • Privacy issues
      • All pairwise users who are sharing a channel are revealed onchain
    • Interoperability
      • Chain needs support for whatever specific hash function you're using in the reveal game
  • Summary of current payment channel networks
    • They're a cool idea, but have a long way to go
    • Security is mediocre (see wormhole attack)
    • Privacy is nonexistent
      • Can not only snoop on transactions by routing payments...
      • But payment identities are incentivized to be long-lived
      • And are all payment channels are registered on-chain with addresses in the clear
    • Interoperability requires all networks to use the same hash function to interoperate
    • The TX sizes are large
      • Need two keys and an HTLC script for each channel
  • How can we improve this state of affairs?
    • Improve usage of signatures
      • 2-party ECDSA Signing (Lindell '17)
        • Jointly compute a signature on a txn
        • Requires knowledge of both sk_A and sk_B
        • Can be publicly verified using pk_AB
          • pk_AB := (pk_A * pk_B) * G
        • Now a channel opening only requires 1 key, not 2
        • Save some bytes!
      • But wait, there's more...
      • What if we encode the conditions (HTLC) in the signature itself?
      • Scriptless Scripts! (SS-Schnorr)
        • Technique originally proposed by Andrew Poelstra
        • "Encode" payment condition within the Schnorr signatures
        • Unfortunately, Schnorr is not used yet in many cryptocurrencies
        • In their paper:
          • Show how to encode similar scripts into ECDSA
          • Provide formal description and security analysis
          • Scriptless scripts based on ECDSA are compatible with Bitcoin today!
  • How to do Scriptless Scripts with ECDSA?
    • Was previously an open problem
    • Main challenge is the signature structure:
      • Schnorr: r + sk * m
        • Where m is script
      • Easy linear combination of two signatures:
        • (r1 + r2) + (sk1 + sk2) * m
      • ECDSA: r^-1 * Rx * sk + r^-1 * m
      • Complex combination of two signatures:
        • (r1^-1 * r2^-2 * Rx * sk1 * sk2) + (r1^-1 * r2^-2) * m
        • wut
        • Requires interaction between the users
      • Requires inverse, x coordinate of a point, and multiplicative shares of the secret key
        • A bit more complicated than Schnorr
    • See the paper for details & analysis
  • How does it work?
    • Given A sending a payment to B, and a condition C (condition will be defined by a public & private key)
    • First, A and B create pk_AB and combine randomness, R := (pk_C, r_A, r_B)
    • B sends his "1/3 signature" to A
    • A sends his "1/3 signature" to B
    • When B learns the sk_C, he puts together the whole signature
      • And now this signature can be used to close the channel on the blockchain
    • In essence, the first two stages are the lock, and learning sk_C is the release phase
    • Note that when you make multiple chained ECDSA payments, because the conditions are all different, each of the signatures / "locks" are different and look randomized
      • This gives you security (no chain of identical hash preimages)
      • And privacy! Routes look random except to sender & recipient
  • Summary
    • Can be extended to arbitrary number of hops
    • Compatible with Bitcoin
      • Lightning devs are currently implementing & testing this protocol
    • Security is better, only one secret per user & no routing attacks!
      • Solves the wormhole attack
    • Privacy is better, randomized conditions per hop!
    • Interoperability is better, only ECDSA required!
      • Can also be combined with multiple signature types along different hops
    • Transaction sizes are smaller!
      • Condition & keys are compressed into only one key
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment