1 of 30

LN as a Directed Graph

Single-Funded Channel Topology

Thaddeus Dryja <rx@awsomnet.org>

DG717

2016-04-11

2 of 30

LN recap

Make channel between 2 nodes
Update channel state
Close co-operatively via interactive multisig
Close non-cooperatively with stored signatures and timeout

3 of 30

LN recap

Multi-hop via trustless HTLC
Channels are edges of a graph
Traverse graph via HTLCs
Off-chain payments:

In non-adversarial conditions, big speed and throughput increases
In adversarial conditions, falls back to similar security as underlying network

4 of 30

How to build the network

A and B want to make a channel

But wait… do they? Why?
Do they know each other?

Dual-funded channels are useful but tricky

A’s UTXO

B’s UTXO

Channel outpoint

(A&B)

2-in 1-out fund TX

5 of 30

Dual-funded channels

Some trust involved
You’re signing your UTXOs away!
Do they really want a channel? Or do they just want to waste your time (and your money’s time?)
Timing, identity, fun stuff

A’s UTXO

B’s UTXO

Channel outpoint

2-in 1-out fund TX

6 of 30

Single-funded channels

Simple: A asks B for a pubkey, then tells B about the channel.
B has nothing at risk, never signs their UTXOs.
Couple payment and channel creation. While A funds completely, initial state allocates money to B.

A’s UTXO

Channel outpoint

(A&B)

1-in 1-out fund TX

7 of 30

Channel exhaustion

Exhausted channels must be avoided in general
Makes attacks free:

state 5 I have 0 coins, in state 4 I had >0 coins.
Broadcast state 4! I have nothing to lose!

Don’t accept state transitions that would exhaust the other side
Don’t try to exhaust from your side

8 of 30

Channel exhaustion exception

At state 0, channel exhaustion is OK.
There is no previous non-exhausted state to broadcast, so there’s no attack
Helps flexibility of single-funded channels:

A can make a “full push channel” to B. Open a 1 coin channel and send the whole coin over. (A is exhausted)
A can open a “zero push channel” to B. Open a 1 coin channel and send nothing. (B is exhausted)

9 of 30

Simplest possible UI

pay(dest, amt)
Can payment be made with existing channels?
If yes, do that! (whole point of LN) Done.
If no, make a full push channel to dest. Done.
Works!

10 of 30

Directed -> Undirected

Channels can start out exhausted, but won’t be for long
Anyone trying to send you funds can use those channels
The arrows in the directed graph may not point the direction you think
Can make cycles

sender

receiver

11 of 30

TX efficiency

Over-funding channels can help
Lots of channels between the same 2 nodes is kindof ugly.
But, channels are super cheap to make (only 12 bytes more than p2wpkh)
Also cheap to close (2of2 multisig, but vsize only ~25 bytes more.

12 of 30

TX efficiency

All the complex transactions (preimages, HTLCs, timeouts) will basically never happen.
Oxygen mask TXs

Open channel without payment only for new use cases

13 of 30

The real problem

People have been talking (arguing?) about scalability for a while
Propagation, capacity, centralization, block size, segwit, XT, hard forks, soft forks, salad forks
Everyone’s been ignoring the REAL problem with bitcoin’s scalability...

14 of 30

Downward scalability

Bitcoin only has 8 decimal places (“satoshis”)
1 USD is 250,000 satoshis
A micro-payment is 10^-6 USD(µSD) = 0.25 satoshi

Bitcoin does not support micro-payments.

(unless the price of 1 bitcoin falls below $100)

15 of 30

Sub-satoshi

Sure you could TRUST your channel counterparty. But where’s the fun in that?
How to subdivide without trust?
Probabilistic payments

Rivest’s “Peppercoin” (early 2000s)
Based on inequality of LSBs of an RSA sig

Previous ideas of this in bitcoin

(Rafael Pass and abhi shelat 2015)

16 of 30

Probabilistic payment

How to pay someone a satoshi with an agreed upon probability?
No trusted 3rd party
Where to get randomness?
Limited opcodes (fun opcodes all disabled)

17 of 30

Probabilistic payment

Op code to use: OP_SIZE
Basic idea: 2-party envy-free cake cutting (divide and choose)
Divider picks a pre-image length

(pre-image bytes are from /dev/urandom or can be from some hash tree or whatever)

Divider sends hash
Chooser picks pre-image length based on hash
Choose the wrong length, get the Satoshi

18 of 30

Probabilistic payment

Making it iterative needs a few more steps
Done in a “limbo” channel (can’t be closed un-cooperatively for a number of blocks)
Dave divides, Carol chooses
Dave is paying Carol 0.5 satoshi

(0.000000005 BTC) (5 nanoBTC)

19 of 30

Probabilistic payment

Carol makes random Y1, Y2, (normal length) hashes both and sends the hashes to Dave
Dave makes X (L bytes long), hashes, and makes 2 output scripts. (3 paths to spend each) Puts script in txout, txin is channel outpoint, Signs both, sends txs to Carol

Script 1 / Tx 1

SigCarol && 10 blocks ||

SigDave && Y1 ||

SigDave && len(X) == 20

Script 2 / Tx 2

SigCarol && 10 blocks ||

SigDave && Y2 ||

SigDave && len(X) == 21

20 of 30

Carol’s choices

Carol now has 2 half signed TXs. She can:
Nothing
Sign & broadcast both
Sign & broadcast TX1
Sign & broadcast TX2
Choose TX1, sign and send sig, Y1 to Dave
Choose TX2, sign and send sig, Y2 to Dave

21 of 30

1: Nothing

Channel is in limbo for 20 blocks or so. Dave is like “what the heck Carol” and closes after that

22 of 30

2: Sign & broadcast both

This is really the same as signing and broadcasting only one
She’s just letting the miners choose which TX happens instead of picking herself
Once one gets into a block, Dave proceeds as if that one is chosen

23 of 30

3/4: Sign & broadcast a chosen TX

If she chose the WRONG length, she wins after 10 blocks
If she chose the RIGHT length, Dave sweeps immediately

Script 1 / Tx 1

SigCarol && 10 blocks ||

SigDave && Y1 ||

SigDave && len(X) == 20

Script 2 / Tx 2

SigCarol && 10 blocks ||

SigDave && Y2 ||

SigDave && len(X)==21

24 of 30

5/6: Sign & send sig and other Y preimage

Choose 20, sign TX1 and send Y2 to Dave
Claims TX1, Revokes claim on TX2
Carol can no longer sign and broadcast TX2 as she loses even if len(X)==21
Dave can broadcast TX1 and only TX1. He reveals X and they say GG

Script 1 / Tx 1

SigCarol && 10 blocks ||

SigDave && Y1 ||

SigDave && len(X) == 20

Script 2 / Tx 2

SigCarol && 10 blocks ||

SigDave && Y2 ||

SigDave && len(X)==21

25 of 30

Probabilistic payment: iterate

After Carol sends Y1, sig2, Dave needs to reveal X. They both know who gets the satoshi
The cooperate and update the channel state based on where the satoshi goes. If they don’t, either can close at the updated state
Note that for sub-satoshi, these TXs actually have 2 outputs -

TX1(script1:49, script2:51) TX2(script2:49, script1:51)

26 of 30

Probabilistic payment: timing

When Carol gets the 2 TXs from Dave, she considers that a payment
Carol can unilaterally close with the probability of an incremented satoshi
Deliver goods, then respond with length choice

27 of 30

Probabilistic payment: probabilities

Just described 0.5 chance; for 0.333 chance, there are 3 scripts, for lengths 20, 21, 22
Can have 0.25, 0.1... Can’t really do 0.001 though (preimages get too long to manage)
But does get us at least one OOM scalability

28 of 30

Probabilistic payment: probabilities

Relies on collision resistance of hash function; if Dave can do ~2⁸⁰ work and find a collision with different lengths, he can cheat
OK, just use hash256 instead of hash160…
But ~2⁸⁰ work costs way more than a satoshi
Can actually do 12/13 byte pre-images! 2⁹⁶ work for Carol to break (pre-image attack), and would be 2⁴⁸ for Dave to collide… but there are no colliding 12 byte pre-images

29 of 30

Summary

Single funded channels are easier
Exhausted channels are bad, but exhausted-on-open is OK
Network can grow with single funded, TXs are cheap
The real scalability problem has been ignored… until now
Pre-Image Length Probabilistic Payments (PILPP?) can scale Bitcoin into the true micro-payment range
Trustless nano-payments (femto, atto?) possible with chains of PILPPs
Avoid divisibility forks (hard / soft / spork)
May have low demand with current price of Bitcoin, but we need to plan for the future. Also it’s fun!

30 of 30

Questions

There probably are some
But they’re not written on this slide

Because causality

Thanks to: DG717 for hosting, Denise & Michael for setting this up, sponsors for pizza, and everyone for coming!