1 of 19

Real-Time Recursive Routing in Payment Channel Network: �A Bidding-based Design�

1

Jiayuan Liu∗,1, Canhui Chen∗,1, Lulu Zhou2 and Zhixuan Fang1,3

September, 2022

1 Tsinghua University, 2 Yale University, 3 Shanghai Qi Zhi Institute

2 of 19

Authors

2

1 Tsinghua University, 2 Yale University, 3 Shanghai Qi Zhi Institute

Jiayuan Liu∗,1

Canhui Chen∗,1

Lulu Zhou2

Zhixuan Fang1,3

3 of 19

Outline

  • Introduction
    • Motivation and contribution
    • Payment channel network (PCN)
    • Routing in PCN
  • Real-Time Recursive Routing (RTRR)
    • Auction phase
    • Recursive outsourcing
    • Implementation
    • Performance guarantee
  • Experiments

3

4 of 19

Introduction

  • Scalability problem in blockchain systems
    • Blocks are limited in size and frequency
    • Long waiting time or expensive transaction fee
  • Layer-2 Off-chain methods
    • A promising solution to scalability problem
    • One fundamental building block: payment channel
  • Our contributions
    • Design an efficient protocol RTRR for transaction routing in PCN: faster and lower cost compared with source routing
    • RTRR supports dynamic pricing and decentralized routing
    • Propose a protocol HTLC-bid to ensure security

4

5 of 19

Payment Channel Network (PCN)

  • Payment Channel

​

5

$3

$5

Alice

Bob

Total channel escrow = $8

Tx: Alice send Bob $2

➖$2

​

+$2

​

6 of 19

Payment Channel Network (PCN)

  • Payment Channel

​

​

​

​

​

​

  • Transaction completed on payment channel without on-chain commitment.
  • If conflict exists, either side can close the channel and update the value through an on-chain transaction.

​

​

6

$1

$7

Alice

Bob

Tx: Alice send Bob $2

Total channel escrow = $8

$3 ➖$2 = $1

​

$5 +$2 = $7

​

7 of 19

Payment Channel Network (PCN)

  • PCN

​

7

Alice

Bob

Charlie

Tx: Alice send Charlie $2

$3

$5

$4

$7

8 of 19

Payment Channel Network (PCN)

  • PCN

​

8

Alice

Bob

Charlie

Tx: Alice send Bob $2

$3

$5

$4

$7

Tx: Bob send Charlie $2

$1

$7

$2

$9

More participants => Network

9 of 19

Payment Channel Network (PCN)

  • Hashed Time-lock Contract (HTLC)
    • Preimage R of a hash value h(R) serves as a proof of success, known only by destination node before transfer

9

Alice

Bob

Charlie

Hash Lock

 

 

Hash Lock

 

Alice

Bob

Charlie

 

Alice

Bob

Charlie

Hash Lock

 

 

 

10 of 19

Routing in PCN

  • Routing

The problem of selecting intermediate nodes to ensure successful and efficient transaction transfer in PCN.

  • Source routing

The sender specifies the relay route for each transaction

  • Concerns of source routing
    • Require global information
    • Hard to deal with dynamic structure
    • Huge processing load on source nodes
  • Our method: Real-Time Recursive Routing (RTRR)
    • Flexible and decentralized routing approach
    • Local information only

10

11 of 19

RTRR: Auction Phase

11

pi: Tx success probability from current node vi to target node

v1

v2

v3

vK-1

vK

s

p1

p2

p3

pK-1

pK

Preceding node on tx route

fi : bid (tx fee) proposed by node vi

f1

f2

f3

fK-1

fK

 

Assume node s selects v2 as its subsequent node

12 of 19

RTRR: Recursive Outsourcing

12

pi: Tx success probability from current node vi to target node

v1

v2

v3

vK-1

vK

s

fi : bid (tx fee) proposed by node vi

f1

f2

f3

fK-1

fK

Preceding node on tx route

ṽ1

ṽ2

ṽ3

ṽK-1

ṽK

 

 

 

 

 

 

 

 

 

 

 

 

Assume node s selects v2 as its subsequent node

13 of 19

Implementation

  • HTLC-bid: a variant of the original HTLC protocol
    • Add a bidding lock of a short period of time
    • Implement security deposit to ensure truthfulness

​

13

Alice

Bob

 

  1. Bob signs and sends to Alice a contract: HTLC-bid (value = μ, fee = f, security deposit = d, transfer lock Tt , bidding lock Tb , sig(Bob)). After this step, security deposit is locked on Bob’s side.
  2. If Alice selects the contract within Tb , she signs on and sends back to Bob the HTLC-bid contract. After this step, value and fee are locked on Alice’s side.

3(a). Case 1 -- Successful (the transaction succeeds within Tt ). Bob receives all locked funds (μ + f + d), i.e., receiving the value and fee, and get back the security deposit locked on his side.

3(b). Case 2 – Impassable. Alice receives all locked funds (μ + f + d), i.e., receiving deposit as compensation, and get back the value and fee locked on her side.

d

Alice

Bob

 

d

μ+f

Send HTLC-bid contract with sig(Bob)

Send back HTLC-bid with sig(Alice, sig(Bob))

 

Alice

Bob

Hash Lock with h(R)

 

μ+f+d

0

 

Send back correct preimage R

Hash Lock with h(R)

Alice

Bob

Hash Lock with h(R)

 

μ+f+d

 

Case Impassable:

Case Successful:

0

 

14 of 19

14

Response timeout τ

u (auctioneer)

v1 (bidder 1)

v2 (bidder 2)

Request bidding:

tx(value, destination)

Request bidding:

tx(value, destination)

Decide fee f1

Bidding: HTLC-bid

(value, f1+d1, Tt, Tb, sig1(1))

Decide fee f2

Bidding: HTLC-bid

(value, f2+d2, Tt, Tb, sig2(2))

Bidding lock

Bidding lock

Case 1: Successful

Case 2: Impassable

Restart auction

Requesting bidding on its neighbors

Get preimage from

subsequent node

Send back preimage

[Update channel balance]

Balance: +f2

Balance: -f2

Balance: -d2

Balance: +d2

No preimage received in Timeout Tt

[Update channel balance]

Select and sign contract: sigu(2)

……

Transfer lock (Tt)

Transfer lock (Tt)

Auction

Outsourcing

RTRR

Protocol:

15 of 19

Performance Guarantee

15

​

K

L

θ

η’s lower bound

1

5

5

0.8

50.1%

2

5

10

0.8

77.8%

3

5

5

0.5

59.2%

16 of 19

Experiment Settings

  • Routing Schemes
    • RTRR (ours)
    • Shortest-Path Routing
    • Min-Cost Routing
    • Water-Filling Routing
    • Routing Scheme in Spider
  • PCN Structures
    • Random Graph
    • Original Lightning Network (1,917 nodes, 58 supernodes)
    • Lightning Network without Supernodes

​

​

16

17 of 19

Experiment Results

17

18 of 19

Summary

  • Propose RTRR, a routing scheme in PCN
    • Distributed routing and HTLC-bid protocol
    • Dynamic pricing with only local information
    • Strong privacy protection
  • Model dynamic pricing as an auction process
    • Derived equilibrium bidding strategy
  • Performance advantage over source routing
    • Higher transaction success rate
    • Less delay and lower transaction fee

18

19 of 19

THANKS

19