Haseeb-Qureshi/multi_hop_locks.md

## multi_hop_locks.md

      
    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