Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Privacy-Preserving Decentralized Micropayments
Onion Routing in Lightning
Olaoluwa Osuntokun
roasbeeflaolu@lightning.network
Lightning Labs

Scaling Bitcoin Milan, 2016

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security AssumptionsFuture Directions

123456Intro to Onion Routing
Overview
Sphinx: A Compact and Provably Secure Mix Format
Overview
Lightning’s Sphinx Extensions
Performance Considerations
HORNET: High-speed Onion Routing at the Network Layer
Overview
Optimizations over Sphinx
In-Network Payment Negotiation
Forward Secrecy
Replay Protection
Key Rotation
Security Assumptions
Future Directions

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network LayerForward Secrecy
Security Assumptions
Future Directions

Overview

Overview - Onion Routing

Distributed set of Onion Routers (OR) [1]
Users create circuits with sub-set of nodes
Difficult for OR’s to gain more info thanpredecessor+successor in path
Low Latency – usable within greater Internet
Notable success: Tor: 2nd Generation Onion Router [2]B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward SecrecySecurity Assumptions
Future Directions

Overview

Domain Application - Lightning

Goals: privacy + censorship resistance
Each node in network doubles as an OR
Source routing: sender fully specifies route payments take:
Path length
Absolute time-locks (CLTV )Fees at each hop
Inter-chain links

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Lightning’s Sphinx Extensions
Performance Considerations

Sphinx

Provably secure Mix Format [3]Header: routing instructions
Body: end-to-end message

Sphinx header+body is re-obsfucated at each hop
Intermediate OR’s unable to distinguish one packet fromanother (IND-CPA)

Entire packet remains fixed-sized through processing
Intermediate OR’s gain no positional informaiton

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Lightning’s Sphinx Extensions
Performance Considerations

Sphinx - Key Agreement

Sender needs to derive unique shared-secret for each hop
Used to encrypt+authenticate packet fields

To achieve unlink-ability, group-element for DH need tochange at each hop
Past solutions: include N group-elements within packet, one
for each hop
Sphinx’s solution: repeatedly blind (randomize) a single groupelement

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Lightning’s Sphinx Extensions
Performance Considerations

This One Little Trick Drives Adversaries Insane!
Source derives unique session key: x
Source obtains list of OR pubkeys: {N1 , N2 , N3 , ....Ni }Source computes the per-hop group element:a0 = g x
a1 = ga2 = gx b0
b1x b0s0 = N1xb0 = h(a0 , s0 )x b0

s1 = N2b1x b0

s2 = N2

b1 = h(a1 , s1 )b2 = h(a2 , s2 )...
Each hop re-blinds (bi ) the group-element for their successor basedon the random group-element (ai ) and shared secret (si )!
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Lightning’s Sphinx Extensions
Performance Considerations

Packet Processing
ProcessSphinxPacket (packet)
a, header , MAC , body ← packets ← ax ?
ˆ = MAC (s, header ||body )MAC

ˆ ! = MAC
if MACREJECT
endif? indicates an asymmetric
cryptographic operationparse shifts the bytes, anddecrypts a layer fromheader+bodyâ ← ah(s,a) ?
ˆ = parse(s, header , body )nextHop, packetˆreturn nextHop, packet
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward SecrecySecurity Assumptions
Future Directions

Overview
Lightning’s Sphinx Extensions
Performance Considerations

Sphinx Modifications
Onion Routing spec draft, led by Christian Decker [4]Addition of version-byte toheader
Packet now contains aper-hop payload
Entire packet protectedunder MAC
Switch from AES-SHA256
to ChaCha20-Poly1305
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future DirectionsOverview
Lightning’s Sphinx Extensions
Performance Considerations

Performance Considerations
Two asymmetric crypto operations now in critical-path forforwarding:1

DH operation to derive shared-secret

2

Exponentiation/Scalar-Multiplication to re-blindgroup-element

OR’s need to maintain per-session circuit state
Circuit: payment hash, incoming link, outgoing link
Needs to be persisted to disk to survive restarts

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Optimizations over Sphinx
In-Network Payment Negotiation

Overview

Progression of Onion Routing to achieve efficientinternet-scale data forwarding [5]Eliminates asymmetric crypto operations duringdata-forwarding
Creates a bi-directional ephemeral circuit during set up

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Optimizations over Sphinx
In-Network Payment Negotiation

HORNET’s Optimizations

Constructs an Onion Circuit witha double-pass:Sphinx used for session
initialization
Intermediates OR’s populate
a Forwarding Segment

HORNET Session Setup Packet
type hops

EXP

Sphinx Header

HORNET Data Packet
type hops

nonce

AHDR

Sphinx Payload
Data Payload
FS Payload

Allows for forward secrecy
within set-up phase
Figure 1: HORNET packet formats.

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

generator of G.
Let r be the maximum length of a path, i.e., the maximum numberof nodes
onina Lightningpath, including
the destination. We denote theOnionRouting– roasbeef

IntroRouting
ing information Rif , S’s DH public key
yif , toandOnion
the established
Sphinx:and Provably
SecureMix Format
symmetric
key A
snCompact
S. During
this processing
thef shared withi
HORNET: High-speed
Onion Routing at the Network Layer
integrity of the CHDR is verified.
Forward Secrecy

2. nfi obtains EXP from CHDR and checks Security
that EXP Assumptions
is not expired.
Future Directions
nfi also verifies that Rif is valid.
3. To provide forward secrecy, the shared key snf is not used forithe data transmission phase,since s depends on n ’s longHORNET’sOptimizations

fifterm DH key. Instead, ni generates an ephemeral DH key pair(x′ f , y ′ f ) and derives sfi byni ni
x′ fsfi = (yif ) ni
(5)This is the symmetric key that is included in nfi ’s FS and usednfi

Circuit state pushed to theendpoints:

during the data transmission phase.

HORNET packets carryinformation completeforwarding
f′ into5. ni adds itsnecessary
FS fi and MD = yfor
the FS payload PF S .

4. nfi generates its FS FS fi by using its local symmetric key SVi
to encrypt sfi , Rif , and EXP:
FS fi = FS _ CREATE(SVi , {sfi ∥ Rif ∥ EXP})(6)nfi

PF S ′ = ADD _ FS(snf , F Sif , y ′ f , PF S )nii

Node state reduced to SV (7)nsymmetric key (O(1)
later retrieve y ′ and derive the symmetric key sfi shared withnstorage)f

2. S retrieves the FSes for the nodes on the forward path {FS fi }:fbackward path {FS i }:{FS bi } = RETRIEVE _ FSES({sbi }, PF S b )
(12)
!
"!
"
With the FSes for all nodes on both paths, FS fi and FS bi ,S is ready to start the data transmission phase.

4.4 Data Transmission Phase

Each HORNET data packet contains an anonymous header AHDR
and an onion-encrypted payload O as shown in Figure 1. Figure 2
demonstrates the details of an AHDR. The AHDR allows each intermediate node along the path to retrieve its per-session state in theform of an FS and process the onion-encrypted data payload. Allprocessing of data packets in HORNET only involves symmetrickey cryptography, therefore supporting fast packet processing.
03248

Adding y ′ f as the meta-data into the FS payload allows S toAnonymous Header

ni for the session. The MAC computed using snf shared bei

Solely symmetricncryptography
used for data
6. Finally node nfi assembles the processed packet P➊ = {CHDR ∥forwarding′′ } and routes it to the next node accordingSHDRf ∥ SP ′ ∥ P
tween S and nfi (Line 5 in Algorithm 1) allows S to authenticate
the DH public key y ′ f .
iFS

to the routing information Rif .

Destination Processing. As the last node on the forward path, D
B2BE 1EFA
ADA4
7BB9
4C59
6505 nodes:
9E25 AA74
8703
processes
P➊ in68C1
the sameway
as theprevious
it processes

Forwarding Segment (FS)0FS
MAC
Blinded FSes

ifif

Overview{FS i } = RETRIEVE _ FSES({si }, PF S f )(11)
Optimizations over Sphinx
3.
S
directly
extracts
from PF S b the FSes for the nodes on theIn-Network PaymentNegotiation
b48*hops

8RS

16EXP

Shared Key
Encrypted
Onion Encrypted

Figure 2: Format of a HORNET anonymous header with details of a forwarding segment (FS).

At the beginning of the data transmission phase, S creates twoAHDR s, one for the forward path ( AHDRf ) and one for the backward path (AHDRb ), by using FSes collected during the setup phase.
AHDRf enables S to send data payloads to D. To enable D to transmit data payloads back, S sends AHDRb as payload in the first datapacket. If this packet is lost, the source would notice from the fact

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Optimizations over Sphinx
In-Network Payment Negotiation

In-Network Payment Negotiation
Currently, payment negotiation assumed to be out-of-band:

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Overview
Optimizations over Sphinx
In-Network Payment Negotiation

In-Network Payment Negotiation
With HORNET, payment
negotiation can be done purely
over the network
Reduces payment info tosimply: < nodePubKey >Ideal for the streaming
payment setting!
Additional payment hashes
exchanged over HORNET
circuitStreamlines possible network
layer payment fragmentation
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Replay Protection
Key Rotation

Shared Secret Log

Without replay protection, packets can be re-injected into thenetwork, possibly leaking route information.
Solution: remember all past shared secrets, rejecting”double-spends”.
Problem: log of shared secrets grows unbounded
If we periodically rotate keys, can garbage collect prior log entries!

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeefIntro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Replay Protection
Key Rotation

Active Key Rotation

Use the network communication layer (irc, broadcast, etc) toadvertise new keys
Key advertisements authenticated via current identity key
Advertise staggered overlapping windows to allow loosely
synchronized rotation
Active rotation incurs additional bandwidth overhead, can weeliminate this?

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Replay Protection
Key Rotation

Passive Key Rotation - First Attempt

Using BIP 32 Public Derivation, the edges can rotate passively
Initially communicate:
Master Public Key (MPK )Anchor: < blockhash >Edges then passively rotate keys (eg, every 144 blocks fromanchor)
However, compromise of child priv key, and MPK defeats forward
secrecy!

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Replay Protection
Key Rotation

Passive Key Rotation - Second PassUsing pairing cryptography, we can achieve non-interactive passive
key rotation![6]We modify the Boneh-Franklin Identity Based Encryption(BF-IBE)[7] scheme to our domain:
Three cyclic groups: G, Ĝ, GT for prime order q.
A bilinear pairing: e : G × Ĝ → GT : e(g a , ĝ b ) = e(g , ĝ )ab

Each node generates a master secret: s, and advertises y = g s

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Replay Protection
Key Rotation

Passive Key Rotation - Second Pass
Given H a full-domain hash function: H : {0, 1}∗ → Ĝ?
Rotation:Assuming a BF-IBE setting: ID = H(blockHash)
Each nodes is it’s own Private Key Generator (PKG )PKG extraction: n = ID s = H(blockHash)s
Key agreement:
Given Sphinx pseudonym: R = g r (recall our ”little trick”)
Source derives secret: e(y , ID)r , node derives secret: e(R, n)e(y , ID)r = e(g s , Hid )r = e(R, n) = e(g r , Hid s ) = e(g , Hid )rs
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion RoutingSphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions

Limitations

In practice, security relies on high-degree of path diversity
Additional correlation possible via payment values, link
capacities, etc.
Active network analysis via timing attacks, packet sizes, etc.

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network LayerForward Secrecy
Security Assumptions
Future Directions

Future Directions

Integrate HORNET
Sphinx (a prerequisite) currently implemented in lnd andlightningd

Per-hop payload structure: inter-chain, timeouts, amounts,etc.
Investigation into alternative higher-latency systems: mix-net,DC-net, etc.
Non-source-routed privacy schemes

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions[Goldschlag et al., 1997] D. M. Goldschlag, M. Reed, and P.
Syverson
Hiding Routing Information, 1997.
[The Tor Project, 2016]
https://www.torproject.org, 2016.
[Sphinx: A Compact and Provably Secure Mix Format, 2009]
G. Danezis and I. Goldberg
IEEE Symposium on Security and Privacy, 2009.
https://github.com/cdecker/lightningrfc/blob/master/bolts/onion-protocol.md[HORNET: High-speed Onion Routing at the Network Layer,
2015] Chen Chen et al.
ACM CCS, 2015.
B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef

Intro to Onion Routing
Sphinx: A Compact and Provably Secure Mix Format
HORNET: High-speed Onion Routing at the Network Layer
Forward Secrecy
Security Assumptions
Future Directions[Pairing-Based Onion Routing, 2007] A. Kate, G. M.
Zaverucha, and I. Goldberg
PETS ’07, 2007.
[Identity-Based Encryption from the Weil Pairing, 2001] D.
Boneh and M. Franklin
Advances in Cryptology - CRYPTO’01, 2001.

B2BE 1EFA 68C1 ADA4 7BB9 4C59 6505 9E25 AA74 8703

Onion Routing in Lightning – roasbeef