#  DPCN: Towards Deadline-aware Payment Channel Networks

Wenhui Wang, Ke Mu, Xuetao Wei Wenhui Wang, Ke Mu, Xuetao Wei are with the
Department of Computer Science and Engineering, Southern University of Science
and Technology, Shenzhen, China, 518000.

###### Abstract

Payment channel is a class of techniques designed to solve the scalability
problem of blockchain. By establishing channels off the blockchain to form
payment channel networks (PCNs), users can make instant payments without
interacting with the blockchain, avoiding the problems of long transaction
consensus delays and high transaction fees. Recently, the optimization of PCNs
has mainly focused on improving the network throughput via multi-path routing.
However, the transaction’s atomicity comes at a non-trivial cost for
transaction completion latency that affects user experience in deadline-
sensitive applications of PCNs, which is ignored by previous work. For the
first time, we propose a new framework DPCN to consider the deadlines of
transactions for payment channel networks while improving the success ratio of
transactions. DPCN is enabled via a synergy of three components: (1) deadline-
based dynamic transaction split mechanism that splits the transaction
according to current network status and the transaction’s deadline; (2)
deadline-aware transaction scheduling that prioritizes near-deadline
transactions; (3) deadline-aware transaction congestion avoidance algorithm,
which uses a path window to balance transactions with different deadlines. Our
extensive experiments show that compared with existing methods, DPCN can well
meet the needs of transactions with different deadlines and ensure a higher
success ratio for transactions in the payment channel networks.

###### Index Terms:

Blockchain, Payment Channel Networks, Transactions, Deadline, Time-sensitive
Applications

##  1 Introduction

Despite many efforts to improve its efficiency [1, 2, 3, 4], blockchain still
suffers from poor scalability, which introduces high latency to decentralized
applications. For instance, the Bitcoin[5] network can only process 7
transactions per second on average and the Ethereum[6] network just provides
15 transactions per second. In contrast, Visa[7] can process 1700 tx/s on
average and over 47000 tx/s at the peak. Blockchain is hard to scale since the
underlying consensus protocol is not efficient enough. Transactions are passed
through the network and need to be processed by all participants in the
blockchain to maintain the consistent state change in a decentralized
environment.

At present, there are two major solutions to handle the scalability challenge
in blockchain, namely, first-layer solutions (L1) and second-layer solutions
(L2). First-layer solutions mainly focus on the optimization of the underlying
design of blockchain, while the second-layer solutions aim to transfer parts
of storage or computation tasks to other platforms to scale up the throughput
of blockchain. A leading proposal among the second layer solutions is called
the payment channel. A payment channel is one of the cryptocurrency
transactions that enables users to deposit or escrow their funds on the
blockchain for payments with a prespecified user on any off-chain platform.
For example, if Alice and Bob attempt to make transactions in a payment
channel, they need to deposit some funds on the blockchain first to establish
a channel. Then, when the channel is open, Alice and Bob can send signed
transactions to each other through this channel without any verification on
the blockchain.

To get the deposit funds back from the blockchain, Alice or Bob can send the
most recent signed transactions to the blockchain to close the payment
channel. A network composed of multiple payment channels is called payment
channel networks (PCNs). PCNs allow users that do not have direct payment
channels in between to complete their transactions through a multi-hop path in
the network. PCNs have been receiving growing attention these years and have
also been deployed by many popular blockchains to improve the throughput and
reduce the latency, for example, the Lighting network[8] used for Bitcoin and
the Raiden network[9] for Ethererum.

Existing approaches[10, 11, 12, 13] mainly focused on the routing problem in
PCNs to provide high-throughput transactions, e.g., multi-path routing by
splitting the transaction into sub-transactions that are routed along multiple
paths. However, the requirement of transaction atomicity comes at a non-
trivial cost for latency, due to either network congestion or half-way
incomplete sub-transactions. Such latency is unbearable for some deadline-
sensitive applications (For example, instant transactions on exchanges[14,
15], interactive blockchain games[16, 17]). Therefore, it is strongly desired
for PCNs to allocate and schedule resources to meet the deadline requirements
of these time-sensitive payment applications. Approaches [18, 19] proposed for
the Internet cannot be simply applied to the PCNs, as the problem we solve in
PCNs differs from it in crucial ways. In the Internet, the capacity of each
link is unchanged when sending packets. However, payment channels can only be
able to send transactions by moving a finite amount of funds from one end to
another in the channel. Thus, the capacity of each channel (the maximum funds
it can send) varies dynamically after every payment in the channel. As a
consequence, PCNs are more dynamic than the Internet and it is more
challenging to guarantee transactions’ completion time in PCNs.

In this paper, we present DPCN, a new framework that considers the deadlines
of transactions in the payment channel networks while improving the success
ratio of transactions. DPCN is enabled via a synergy of three components: (1)
deadline-based dynamic transaction split mechanism: we find that the
completion time of a transaction is affected by the size of the transaction
being split into. Deadline-based transaction split runs dynamically according
to current network and transaction status. We use the window size of the path
to correspond to the state of the path. We estimate the average processing
time required for the path to process one transaction based on the completion
of previous transactions on this path. Based on both the window size of the
path and the ratio of the deadline of the transaction to the average
processing time of the transaction on this path, the transactions of different
deadlines are split into different sizes. Namely, the shorter the
transaction’s deadline is, the larger the amount of fund-units of split sub-
transactions is; (2) deadline-aware transaction scheduling: deadline-aware
transaction scheduling algorithm runs according to the remaining time of the
transaction. We give priority to transactions with shorter deadlines. The
transaction with the shortest deadline is picked up first from the waiting
queue of the channel and sent to the channel for processing; (3) deadline-
aware transaction congestion avoidance algorithm: when a transaction is queued
at an intermediate node(a router) in the network for more than a certain
period of time, we mark the transaction. This indicates that congestion is
likely to occur in the network. This marked information will be forwarded to
the sender together with the confirmation information after the receiver
receives the transaction. For each path, we use the marked information and the
completion status of the transaction in the most recent period of time to
maintain a window (same as the window mentioned in deadline-based dynamic
transaction split). We dynamically adjust the size of the window to limit the
number of transactions sent to the path, so as to avoid the occurrence of
congestion as much as possible, which ultimately avoids transaction failures
due to long transaction processing time caused by network congestion. We
conduct extensive experiments to evaluate DPCN under various settings, e.g.,
different topologies, channel sizes and transaction sizes. Experimental
results show that DPCN is a very promising framework for deadline-aware
payment channel networks.

Our contributions can be summarized as follows:

  * •

We propose DPCN, a new framework to consider the deadlines of transactions in
payment channel networks for time-sensitive applications while improving the
success ratio of transactions.

  * •

The key novelty of DPCN is a synergy of three components, namely, deadline-
based transaction split, deadline-aware transaction scheduling, and deadline-
aware transaction congestion avoidance algorithm. Our framework DPCN
synergizes these techniques to effectively improve the success ratio of
transactions while meeting their deadline requirements.

  * •

We prototype DPCN and extensive results show that DPCN can improve the success
ratio of transactions compared to the state-of-the-art work.

##  2 Background and Motivation

###  2.1 Payment Channel

The payment channel is one of the second layer solutions that move transaction
processing away from the blockchain. A payment channel is established by two
parties and allows them to send transactions to the blockchain only when the
channel is opened and closed. After a channel is opened, users can conduct any
number of transactions without participating in the consensus on the chain,
which greatly improves the transaction throughput and reduces delays. The life
cycle of a payment channel can be divided into three parts: channel
establishment, transaction submission, and channel closure. Figure 1 shows an
example of a simple bidirectional payment channel (a payment channel can be
bidirectional or unidirectional). In order to establish a channel, two parties
construct a smart contract on the blockchain and deposit a certain amount of
funds into a multi-signature wallet. Then, they create a transaction. The
approval of this transaction on the blockchain initiates the channel. After
that, in the transaction submission phase, both parties can use this channel
to send multiple payments without interacting with the blockchain. The
transaction used in payment channel is called commitment transaction and needs
to be signed by two parties. It updates the state of the channel like a
transaction on the blockchain. Any party can submit a settlement transaction
to the blockchain, or if one of the parties accidentally disconnects, the
single party will submit the final commitment transaction to the chain. The
settlement transaction represents the final state of the channel and is
settled on the blockchain.

Figure 1: An example of a payment channel. First, Alice deposits 5 coins, Bob
deposits 6 coins, and the initial state of the channel is (Alice:5, Bob: 6).
Afterward, they make multiple transactions. Finally, the channel is closed,
and the final status is updated to (Alice: 9, Bob: 2).

###  2.2 Payment Channel Networks

Figure 2: An example of PCNs: Alice sends 2 coins to Dave through Erin, the
left figure shows the initial state of PCNs, the right figure shows the state
after the transaction is completed.

Since a certain amount of funds are required to be locked after the channel is
established, and a long consensus process on the blockchain is required when
creating and closing channels, it is impractical to establish payment channels
between all pairs of parties who want to make a transaction. If two users want
to conduct a transaction but do not have a directly connected payment channel,
the transaction needs to be relayed by intermediate nodes to complete the
multi-hop payment. In this case, multiple payment channels need to be used. A
collection of bidirectional payment channels forms payment channel networks
(PCNs). Figure 2 shows a simple payment channel networks. Suppose Alice wants
to send coins to Dave multiple times. Since there is no directly connected
channel between them, Alice needs to find a path to complete the transaction.
There are two paths available in the current network: 1. Alice $\rightarrow$
Erin $\rightarrow$ Dave. 2. Alice $\rightarrow$ Bob $\rightarrow$ Dave. Taking
path 1 as an example, Erin as an intermediate node, the entire transaction
will be split into two parts: Alice sends 2 coins to Erin; Erin sends 2 coins
to Dave. The hash-time-lock contract (HTLC)[20] is usually used to ensure that
the entire transaction can be completed, that is, to prevent Erin from not
forwarding the transaction after receiving the coins, so as to ensure the
security and the atomicity of the entire transaction is achieved. In the
example above, the HTLC guarantees that if and only if after Dave receives the
coins from Erin, Erin can get the coins sent from Alice. Otherwise, after a
certain period time, the entire transfer process fails and Alice will be
refunded.

###  2.3 State of the Art: Spider

Spider[21] considered packetizing transactions and multi-path routing
transactions. It mainly includes two parts: (1) by setting the maximum
transmission unit (MTU), Spider divides a transaction into $n$ parts regarding
the size of the MTU, and routes these $n$ transactions through k paths to
ensure that even the channel capacity is small, large transactions can still
be completed, which greatly increases the success ratio of transactions and
the throughput of the system; (2) by using the multi-path congestion control
protocol to control the number of transactions sent to the PCNs, Spider marks
transaction packets in the routing process and returns the marking information
to the sender, thereby balancing the fund resources of each channel and
avoiding channel unavailability due to exhaustion of funds.

###  2.4 Motivation

Figure 3: Success ratio for different topologies with the mean channel size
4000

Although Spider is successful in improving network throughput, it is a
deadline-agnostic protocol, which does not distinguish between transactions
with different deadlines. Without carefully considering such requirements,
time-insensitive transactions are likely to be processed in priority over
time-sensitive transactions. As a result, time-sensitive transactions may miss
their deadlines in Spider, which ultimately impacts user experience.

We further present our motivation of the problem via experiments as shown in
Figure 3. For the existing approach Spider, we choose three networks with
different topologies, set the average channel capacity to 4000, and set
different deadlines for transactions to conduct comparative experiments. In
Figure 3, we can see that, when the transaction deadline is longer, the system
can obviously achieve a higher transaction success ratio. However, when we set
a shorter deadline for some transactions, the transaction success ratio of
PCNs drops significantly. That’s because existing approaches are deadline-
agnostic, the transactions with a longer deadline may be processed before
those with a shorter one when PCNs are congested, causing the failure of time-
sensitive transactions. Therefore, a deadline-aware framework is required to
perform differentiated processing for transactions with different deadlines.
This could ensure that near-deadline transactions can be completed as soon as
possible. Actually, for a transaction, if one of the split sub-transactions
fails, the entire transaction will fail.

##  3  Design of DPCN

In this section, we propose a novel framework called deadline-aware payment
channel networks DPCN. Focusing on transactions with different deadlines, we
provide a well-designed mechanisms to achieve a higher transaction success
ratio as well as minor impact on the throughput of payment network. In brief,
DPCN is enabled via a synergy of three components: (a) deadline-based
transaction split mechanism; (b) deadline-aware transaction scheduling; and
(c) deadline-aware transaction congestion avoidance algorithm.

###  3.1 Prerequisites

Transaction Deadline: Transaction deadline is the maximum time a transaction
can be used from its initialization to completion in PCNs. If the processing
time of transaction exceeds the deadline, the transaction will fail.

Atomicity of Transactions: In order to make better use of the resources of the
network, we split a single transaction into multiple smaller sub-transactions
and send them through different paths independently. As previous work[13, 21]
did, we follow the assumption of the atomicity of the entire transaction can
be guaranteed. It can be achieved by Atomic Multi-Path Payments (AMP) [22],
the receiver won’t be paid at all until all sub-transactions are completed.
The design and implementation of such mechanism is beyond this paper.

Transaction Confirmation and Cancellation:  For example, as shown in Figure 2,
for path Alice $\rightarrow$ Bob $\rightarrow$ Carol, if Alice wants to make a
transaction $Tx$ with Carol through Bob. The transaction $Tx$ contains the
transaction of $Alice$ and $Bob$ and the transaction of $Bob$ and $Carol$,
respectively called $Tx_{1}$ and $Tx_{2}$. We say transaction $Tx$ has been
confirmed only when both transaction $Tx_{1}$ and $Tx_{2}$ are completed, the
fund-units in transaction $Tx$ is called the confirmed fund-units. Otherwise,
these fund-units are called unconfirmed fund-units. Note that transaction $Tx$
is canceled when there is a failure in either transaction $Tx_{1}$ or
$Tx_{2}$. Since the transaction has been cancelled, this part of the funds
will be removed from the unconfirmed funds.

Transaction Split Size:  If split size is $a$ and the fund-units of a
transaction is $b$, a transaction is split into $\left\lfloor
a/b\right\rfloor$ sub-transactions of the fund-units $a$, and the remaining
fund-units less than $a$ is used as a sub-transaction.

Figure 4: The windows corresponding to paths. There are two paths between the
sender and the receiver and each path has a window

Path Window Size: We define path window size as the maximum fund-units that
are not confirmed on a path (from sender to receiver) at any point of the
time. Only when the sum of a transaction’s fund-units and unconfirmed fund-
units on the path is less than the window size, the transaction can be sent to
this path. Otherwise, the transaction will enter into the queue of the sender
and wait. As shown in Figure 4, suppose there are $2$ paths between the sender
and the receiver. For each path, we assign a window. Considering a transaction
$Tx$ needs to send $f_{1}$ fund-units through path $1$. The unconfirmed fund-
units on the path $1$ is $f_{2}$, and the window size on the path $1$ is
$f_{w}$. Only when $f_{1}+f_{2}<f_{w}$, the transaction $Tx$ can be sent to
path $1$ for processing. The window size can limit the transaction sending
speed of the sender and avoid network congestion in the PCNs. Note that the
window size is not the same as the remaining fund-units on a path, and must be
smaller than the minimum remaining fund-units of any channel on this path.

End Hosts: End hosts are responsible for generating transactions according to
the specified workload and sending the transactions to the PCNs. When an end
host receives a transaction from other end hosts, it will return a
confirmation message back along the same path. That is, all nodes of PCNs that
wish to transact constitute end hosts, and each pair of end hosts acts as the
sender and receiver of the transaction. We use the same prerequisite as
previous work did[13, 21]: all end hosts have the knowledge of the topology
and the capacity of each channel in PCNs, but do not know the current balance
of the channels. End hosts compute appropriate paths based on the topology.

Routers: The routers, as intermediate nodes on the transaction path, are
responsible for forwarding the transactions from the senders to the receivers
and transferring the receivers’ confirmation messages back to the senders.
When a transaction is forwarded on a certain channel, the router locks the
funds for it and decreases the corresponding channel capacity. The router only
unlocks the transaction funds as it receives the confirmation message from
final receivers, and then increases the channel’s balance. If the channel
corresponding to the router does not have enough funds to lock, the
transaction will wait in the channel’s queue until the transaction is selected
for forwarding according to certain scheduling rules via our proposed
deadline-aware transaction scheduling. When the queue is full, the arriving
transaction will be dropped and a failure message will be returned to the end
host.

###  3.2 Deadline-based Dynamic Transaction Split Mechanism

The main challenge of the current transaction processing mechanism in PCNs is
to find channels with sufficient balance on nodes to forward an incoming
transaction. However, since the sender of the transaction does not know the
current available balance of each channel, one direction of the channel may
not have enough balance to forward the transaction, which will cause the
transaction to fail. Therefore, in order to improve the success ratio of
transactions and make better use of resources of the network, people try to
split the transaction into multiple smaller sub-transactions and send them to
different paths for processing. Previous work[21, 23] has proved that this
greatly increases the probability of successful transactions and increases the
throughput of PCNs. We consider that different transaction split sizes may
affect the completion time of the transaction. Intuitively, the greater the
number of sub-transactions that the transaction is split into, the more time
it needs to process the transaction, and the transaction delay may increase.
To prove this hypothesis, we use the simulator in [21], the topology(with 106
nodes and 265 payment channels) sampled from the Lightning Network and set the
mean channel size to 4000 to test the average completion time of transactions
of different sizes and the success ratio of all transactions for different
transaction split sizes. We find that, although the split size of large
transactions has little effect on the completion time, appropriately
increasing the split size of the transaction can effectively reduce the
completion time of the transaction for small transactions. As shown in Figure
5 and 6, when the split size is $50$, compared to split size $1$, the average
completion time of small transactions is reduced by more than $20\%$, while
the successful volume ratio of transactions only drops by $7\%$. This is
because, when splitting transactions into an excessive number of smaller ones
in a network with large transactions handling capability, the growing
transactions will cause delays to be prominent. However, when the transaction
split size is too large, the success ratio of the transaction drops
significantly. This is because, if the split size is too large, it is likely
to exceed the available capacity limit of some channels in the network,
resulting in transaction failure. Therefore, for transactions with different
needs, an appropriate transaction split size should be selected according to
the current network status.

Figure 5: Average latency with different split sizes Figure 6: Success ratio
with different split sizes

Based on the experiments above, we observe that a reasonable transaction split
size can effectively affect the transaction processing time. For instance,
increasing the split size of a time-sensitive transaction appropriately can
definitely reduce the number of transactions to be processed in the network,
which can also reduce the transaction processing delay and increase the
probability of transaction success. Instead of splitting them to the same size
as prior work[21], we dynamically split the size of the transaction.

We use a heuristic algorithm to split the transaction based on the three
following conditions: the deadline of the transaction, the average completion
time and the average window size of all paths associated with the transaction.

For a transaction $Tx$, the split size is as follows:

$\displaystyle SplitSize$ $\displaystyle=WS_{avg}\times\gamma$ (1)
$\displaystyle\gamma$ $\displaystyle=\frac{1}{1+c^{-(x-b)}}$ (2)
$\displaystyle x$ $\displaystyle=\frac{Tx_{deadline}}{P_{avgTime}}$ (3)

$WS_{avg}$ represents the average value of the window size of all paths
between sender $Tx_{s}$ and receiver $Tx_{r}$. $P_{avgTime}$ represents the
average value of the time required to complete one transaction on all paths.
This time includes the entire time from the transactions were sent to
completion, including the time when the transactions are being routed, waiting
in the queue, and so on. $c$ and $b$ are two constants, which are used to
control the size of the split.

Figure 7: The function graph of $\gamma$

The window size of the path can well reflect the processing capacity of the
path. Assuming that the sender of the current transaction $Tx$ is
$Tx_{sender}$ and the receiver is $Tx_{receiver}$, we select all paths whose
starting point is $Tx_{sender}$ and ending point $Tx_{receiver}$, and
calculate the average window size $WS_{avg}$ and the average completion time
$P_{avgTime}$ for a transaction (Note that, the calculation approach of the
average completion time of a transaction on a path is given in 3.4.) We take
$WS_{avg}$ as the upper limit of the size of a transaction split. After that,
we calculate the split size of the transaction according to the deadline of
the current transaction.

As shown in Equation 3, we calculate the urgency factor $x$ of the current
transaction, and the larger $x$ indicates the current transaction is more
urgent. Intuitively, when the $x$ is larger, we hope the transaction can be
processed at a faster speed. Therefore, it needs to be split into multiple
sub-transactions with larger fund-units that are smaller than is $WS_{avg}$.
Conversely, a longer processing time has less impact on whether the
transaction with a larger $x$ can be successfully completed. So it can be
split into multiple sub-transactions with smaller fund-units. We define
$\gamma$ as the split factor of the transaction, and the split size is
$WS_{avg}\times\gamma$. The definition of $\gamma$ is shown in Equation 2 and
the functional image of $\gamma$ is shown in Figure 7. The change trend of
this function can well meet our requirements. As $x$ increases, the value of
$\gamma$ gradually increases, that is, the size of the split gradually
increases. Before $x$ reaches $b$, the growth rate gradually increases, and
the growth rate reaches the maximum point when $x$ is equal to $b$. After
that, the growth rate decreases. We consider that the more urgent the
transaction is, the size of the transaction split is as large as possible,
that is, we make the size of $\gamma$ grow as fast as possible. However, when
the value of $x$ is too large, the transaction may not be completed
eventually. Although we increase the size of the split, as $x$ increases, the
growth of the split size, that is, the growth rate of $\gamma$ will be
reduced. This will prevent transactions with a high probability of failure
from occupying network resources too much.

###  3.3 Deadline-aware Transaction Scheduling

When the arriving transactions exceed the channel’s processing capacity, they
will wait in the channel’s queue. Deadline-aware transaction scheduling aims
to solve the issue: how to determine the processing order of queued
transactions when the channel is congested? In our framework DPCN, we mainly
consider two related parameters to sort the transactions: remaining time
($RT$) and transaction size ($TS$). The remaining time represents the maximum
time that the transaction can be processed in the PCNs from the current time.
Similar to the earliest deadline first[24], we firstly prioritize $RT$ as the
first indicator, which means that the transactions with shorter remaining time
will get higher processing priority. Then, when there is a tie or no deadline,
we consider the transaction size in the following. We use $TS$ as the second
indicator, transactions with smaller $TS$ will get higher priority in our
approach.

###  3.4 Deadline-aware Transaction Congestion Avoidance Algorithm

In order to alleviate network congestion caused by the excessive number of
transactions in PCNs, we propose a congestion avoidance algorithm inspired
from [18, 25, 26, 27] for PCNs that provides non-equivalent resources for
transactions of different deadlines. In our approach, when the waiting time of
a transaction in the router of the PCNs exceeds a certain threshold $\delta$,
the router will mark the transaction. The marked information will be forwarded
to the sender together with the confirmation information after the receiver
receives the transaction. This mark information indicates that the path in the
network may be congested. Then, the sender can adjust the path’s window size
based on this feedback information to control the number of transactions sent
to the path, so as to avoid network congestion, like the explicit congestion
notification(ECN)[28, 29]. The window size of each path represents their
transaction processing capacity in the current state. It also shows the upper
bound of the transaction amount that can be sent without confirmation on a
certain path.

Next, our problem is how to adjust the size of the window based on
transaction’s deadline. We use the following algorithm to adjust the window
size of the paths connected to the end hosts to limit the number of
transactions sent to PCNs.

For path $j$ in PCNs, we use $k$ to represent the proportion of marked
transactions in the feedback information received by end hosts within a
certain period $t_{interval}$. $e$ is a constant, which is the weight given to
new sample $k$. We use $\alpha$ to represent the current congestion state of
transactions in the network. The new congestion state can be updated instantly
by previous state $\alpha$ and current proportion of marked transaction $k$,
as shown in Equation (4).

$\alpha=(1-e)\times\alpha+e\times k$ (4)

Then, we try to estimate the time required to complete the transaction on the
path $j$, which is represented by $ET_{j}$. Note that, unlike traditional
computer networks, the completion time of a transaction on a path has nothing
to do with the size of the transaction. This is because, as long as the path
has enough balance, a large transaction and a small transaction are processed
in the same way. When a transaction $Tx$ is completed on the path $j$, we
calculate its completion time $t$ on this path,
$t=Tx_{timeCompletion}-Tx_{timeSent}$. Based on the previous state of $ET_{j}$
and current time $t$, we update the value of $ET_{j}$, $y$ is a constant,
which is the weight given to the new sample $t$.

$ET_{j}=(1-y)\times ET_{j}+y\times t$ (5)

After obtaining $ET_{j}$, we can estimate the time required for a transaction
to complete on the path $j$. We use $d$ to indicate the urgency of the
transaction $Tx$. The larger $d$ is, the closer the deadline is. As is shown
in Equation 6, if a transaction’s estimated finish time is less than the
deadline, the value of $d$ is less than $1$, otherwise, the value of $d$ is
greater than $1$.

$d=\frac{ET_{j}}{Tx_{deadline}}$ (6)

Finally, in order to change the size of the window, we define a penalty
function $p$ related to $d$, as shown in Equation (7). Intuitively, $p$
increases the processing opportunity of transactions with shorter remaining
time and decreases those with longer remaining time. This function was
originally proposed in [30], which was called gamma-correction.

$p={\alpha}^{d}$ (7)

Based on the penalty function $p$, we adjust the size of the window of the
path $j$ based on the equation (8). This equation is similar to the control
mechanism of AIMD[31] in TCP. Here $g$ and $\beta$ are constants, used to
adjust the window size. Different from the ddl-agnostic window adjustment
method in spider[21], our method better matches the characteristics of
transaction deadlines and thus can better guarantee the success rate of
deadline-sensitive transactions.

$\displaystyle W$
$\displaystyle=\left\\{\begin{array}[]{lll}W\times(1-\frac{p}{g}),&p>0,\\\
W+\beta,&p=0.\\\ \end{array}\right.$ (8)

In order to ensure that transactions can be completed on time under
congestion, the number of transactions in PCNs should be reduced regarding
their deadlines. Specifically, the number should be reduced to a greater
degree if the transaction deadline is longer.

Algorithm 1 Path window adjustment algorithm for end hosts

0: ack message: $aMsg$ totalTransactions: $totTx$ totalTransactionsMarked:
$totTxMark$

0: Window size for $path_{j}$ $W$

1: $totTx\leftarrow totTx+1$

2: if aMsg.isMarked then

3: $totTxMark\leftarrow totTxMark+1$

4: end if

5: if $totTx>txThreshold$ then

6: $k\leftarrow\frac{totTxMark}{totTx}$

7: $\alpha\leftarrow(1-e)\times\alpha+e\times k$

8: $totTx\leftarrow 0$, $totTxMark\leftarrow 0$

9: end if

10: $t\leftarrow nowTime-aMsg.timeSent$

11: $estimatedTime\leftarrow(1-y)\times estimatedTime+y\times t$

12: $d\leftarrow\frac{estimatedTime}{aMsg.deadline}$

13: $p\leftarrow{\alpha}^{d}$

14: if $p>0$ then

15: $W\leftarrow W\times(1-\frac{p}{g})$

16: else

17: $W\leftarrow W+\beta$

18: end if

Note that $\alpha$ is a number less than or equal to $1$. When the proportion
of congested marked transactions increases (as $\alpha$ gradually increases to
$1$), for transactions with a long remaining time (corresponding to $d<1$),
the value of the penalty function increases rapidly. In addition, the window
size is reduced, and the number of such transactions is also reduced rapidly.
At the same time, for transactions with a short remaining time (corresponding
to $d>1$), the value of the penalty function increases slowly, so as to ensure
that this type of transaction can be sent as soon as possible. As shown in
Equation 8, when there is congestion, the window will be reduced by
$\frac{p}{g}$. It ensures that transactions with shorter deadlines have fewer
backoffs than higher deadlines. When there is no congestion, the proportion of
transactions with a congestion mark is $0$ ($\alpha=0$), the window is
increased by $\beta$, which means that more transactions can be sent.

The adjustment process of the window is as shown in Algorithm 1. Data fields
in $aMsg$ in algorithm1 are shown in Table I.

TABLE I: Data in the confirm message forwarded by routers

Field | Description
---|---
txTD | The split transaction ID
receiver | The receiver of the fund-units
pathIndex | The pathIndex for this transaction processing path
timeSent | The time the transaction was sent
isSuccess | If the transaction has been successfully completed
amount | The number of fund-units for this transaction
hasDeadline | If the transaction has deadline
deadline | The transaction’s deadline
isMarked | If the transaction has been marked
largerTxID | The ID of the transaction before the split

##  4 Evaluation

In this section, we evaluate the performance of DPCN, and compare it with the
state-of-the-art PCNs transaction processing approaches under different
conditions. As mentioned in previous work [21], IO bottleneck problem in
Lighting Network Daemon(LND)[32] causes variations of tens of seconds in
transaction latency even on small topologies, which shows it cannot accurately
test the system’s performance. Therefore, we build our simulator based on the
code in [21], which has only a small difference in the success ratio from that
in the real network.

###  4.1 Experimental Setup

Our experiments are conducted on a cluster of servers with two Intel® Xeon®
Silver 4210 CPUs and 128GB memory. We build DPCN based on the code in [21],
which uses the OMNET++ simulator[33] to model PCNs.

Topology. We use three topologies: Watts-Strogatz small world topology [34,
35] (50 nodes and 200 edges), scale-free Barabasi-Albert topology [36](50
nodes and 336 edges) and subnetwork(106 nodes and 265 edges) sampled[37] from
Lighting Network(LN) on July 15,2019(over 5000 nodes and 34000 edges). These
topologies are the same ones used by [21]. For each channel, the capacity is
sampled according to the actual capacity in the Lightning Network[8] on July
15, 2019, and scaled up appropriately to generate a network structure with
different average channel capacities. The values of average channel capacities
are 900, 1350, 2750, 4000, and 8750, respectively. For the LN subnetwork, we
set the transmission delay between 0.29ms and 130ms in the LN. In the other
two networks, we set the transmission delay to 30ms for each link.

Workload. We set each end-host to send an average of 30 transactions per
second, including 10 receivers, and transactions arrive as a Poisson process.
For each set of experiments, we use five random different sets of transaction
data and use the average as the result. Previous work[13, 21] pointed out that
the distribution of transactions on the existing PCNs is highly skewed,
namely, most of the transaction amount is small and the proportion of
transactions with large amounts is small. Therefore, we use the proportion
shown in Figure 8 to allocate the size of the transaction amount in the
workload. If the transaction has a deadline, we set the deadline of the
transaction as shown in Table II. Note that, due to the lack of data in real
scenarios, the deadlines of transactions in Table II may be different from the
real situation, but they can still reflect the characteristics of different
transactions.

Figure 8: Transaction size distribution TABLE II:  Transaction deadline for different sizes Size | 5 | 15 | 30 | 80 | 150 | 400 | 1000
---|---|---|---|---|---|---|---
Deadline | 0.6 | 0.7 | 0.8 | 0.9 | 1.1 | 1.5 | 2.0

Figure 9: Success ratio for three topologies

Figure 10: Success volume for three topologies

Figure 11: Success ratio for different transaction sizes of three topologies
with mean channel size 4000.

Figure 12: Success ratio for different transaction sizes of three topologies
with mean channel size 2750

State-of-the-Art Approaches: We compare our system DPCN with two state-of-the-
art approaches:

  * •

Spider [21]: The transaction is sent from the host to the PCNs. Each host has
a global topology view of the network and calculates the $k$ edge-disjoint
widest paths from the sender to the receiver. For a transaction to be sent, it
is first divided into several equal parts according to the maximum
transmission unit (MTU) size, and these transactions are sent to these $k$
paths. Only when the window size of a certain path is not less than the sum of
the current transaction amount and the unconfirmed transaction amount on the
path, the transaction can be processed on the path. Otherwise, the transaction
is placed in the end host’s queue, and processed according to First-In-First-
Out (FIFO) rules. When the transaction queue time at the intermediate routing
node exceeds a predetermined threshold, the routing node marks the
transaction. After receiving the receiver’s acknowledgment message, the router
sends this feedback information to the sender with the acknowledgment message,
and then the sender adjusts the size of the window of this path according to
the mark information.

  * •

Waterfilling [23]: Waterfilling also splits the transaction into fund-units
and sends these transactions to $k$ edge-disjoint widest paths. For every
path, the sender first calculates the minimum channel balance along the path
before sending the transaction. After obtaining all paths’ balance
information, the sender calculates the current available balance of every path
based on the bottleneck balance and the size of the unconfirmed transaction,
and then sends one split transaction to the path with the largest current
available balance. If the maximum available balance of all paths is less than
the size of current transaction’s fund-units, this transaction is placed in
the sender’s queue to wait for the next available path.

Metrics: We use success ratio and success volume as metrics in the evaluation.
The success ratio is defined as the ratio of completed transactions to the
total number of generated transactions. All the above numbers count the number
of original transactions before splitting, i.e. success ratio represents the
success rate of original transactions without splitting. The entire
transaction is completed only when all split sub-transactions are completed.
Success volume is equal to the ratio of the total fund-units of successful
sub-transactions to the total fund-units of all the sub-transactions. Note
that sub-transactions here refer to split transactions.

Parameters: For each transaction, we send the split sub-transactions through
up to $8$ paths for processing. For the transaction splitting, if a
transaction has no deadline, we fix its split size at $20$ fund-units.
Otherwise, we set $c$ in equation 2 to $8$ and $b$ to $0.8$. We set the
weighted average $e$ in equation 4 is $0.3$ and $y$ in equation 5 is $0.3$.
The threshold of waiting time of a transaction in the router $\delta$
mentioned in Section 3.4 is $0.2s$. For scale free and small world networks,
we set $g$ in equation 8 as $8.0$ and $\beta$ as $1.3$. For the network with
sampled lighting network topology, we set $g$ in equation 8 as $7.0$ and
$\beta$ as $0.8$.

###  4.2 All Transactions Have Deadlines

In the following, we evaluate the performance of different approaches when all
transactions have deadlines.

(a) Mean Channel Size 4000

(b) Mean Channel Size 2750

(c) Success ratio

Figure 13:  Success ratio for transactions with deadlines Figure 14:  Mean
channel size 4000 Figure 15:  Mean channel size 900

Overall performance. We evaluate the performance of DPCN with other approaches
by different mean channel sizes varying from 900 to 8750. As shown in Figure
9, the success ratio of DPCN has a significant improvement compared to the
other two approaches. The success ratio is increased by 11%-40% compared to
Spider, and 26%-54% compared to Waterfiling for all three topplogies. Figure
10 shows that DPCN also performs better than existing approaches on success
volume. The success volume is increased by more than 33% compared with
Waterfilling and 10% compared with Spider for most cases. Note that, for the
scale-free topology, the result of Spider is better than DPCN in some cases.
This is just because the success volume includes the completion of split sub-
transactions, Spider splits one transaction into some 1 fund-unit sub-
transactions, these transactions are small enough and easier to complete in
the network. However, if one of the sub-transactions is not completed because
of a timeout, the entire transaction fails. It can be seen from Figures 9 and
10 that although Spider’s success volume is very high, Spider’s success ratio
is not as high as its success volume. In contrast, our DPCN has a better
performance for both success ratio and success volume.

Performance for different transaction sizes. Due to space limitation, we only
show the success ratio of transactions when the mean channel sizes are 4000
and 2750, respectively. From Figures 11 and 12, we can see that regardless of
the size of the mean channel and the transaction, DPCN can effectively improve
the success ratio of transactions with deadlines. When the mean channel size
is 4000, compared with Spider and Waterfilling, the success ratio increases by
more than 10% in most cases. Compared with Spider, when the transaction amount
is between 15 and 80 fund-units, there is an increase of around 15%.
Meanwhile, compared with Waterfilling, for transactions larger than 80 fund-
units, the success ratio increases around 22%. When the mean channel size is
2750, the success ratio increases 19% and 25%, respectively.

Figure 16: Mean channel size 4000 Figure 17: Mean channel size 2750

Performance for different network sizes. We use the scale-free topology and
set the mean channel size to 900 and 4000. We increase the number of nodes in
the network from 20 to 80, and compare success ratios as shown in Figures 14
and 15. When the network size is small, the number of channels required to
complete each transaction is smaller, and the processing time is shorter, so
the success ratio is higher at this time. However, when the number of nodes in
the network is too large, the topology of the network will become more
complex, and the path required for a transaction to complete may become longer
(the number of channels needs to be increased), which will increase the
processing time of a transaction. Therefore, when the number of nodes in the
network increases from 20 to 80, the success ratio of transactions in the
network decreases. However, from Figures 14 and 15, we can see that the change
in the number of nodes has a minor impact on the success ratio, which
indicates that our DPCN is robust enough to handle networks with different
nodes.

###  4.3 Mixing Deadline and Non-deadline Transactions

Performance for different transaction sizes. We evaluate our DPCN when
transactions with deadlines and without deadlines are mixed. As shown in Table
II, we have seven transaction sizes in our evaluation. We randomly select 20%
of transactions with each size and set these transactions to have no deadline.
Since the arrival order of transactions is random, these transactions with no
deadline may arrive earlier than those with deadlines and have already
occupied network resources for processing, resulting in that transactions with
deadlines cannot be processed in a timely manner. As shown in Figures13 , for
scale-free topology, DPCN has an average of 5% and 14% increase in the success
ratio of transactions with deadline, compared to Spider and Waterfilling
respectively. This is because existing approaches are deadline agnostic, and
transactions without deadlines are likely to occupy the resources of time-
critical transactions. Different from these approaches, DPCN (1) prioritizes
transactions with tight deadlines as much as possible, (2)makes the size of
time-critical transactions as large as possible, thereby reducing transaction
processing time, and (3) dynamically adjusts the window size according to the
deadline and the completion time of the transactions. Even under the
interference of transactions without deadlines, transactions with deadlines
still have a higher success ratio.

Performance for different ratios of transactions with deadlines. We evaluate
DPCN’s performance when the proportion of transactions with deadlines is
different. We set the topology structure to scale-free and the proportion
varies from 0.6 to 1.0. We compare the success ratio when the mean channel
sizes are 4000 and 2750 respectively. From Figure 16 and 17, we can see that
our DPCN is robust enough to handle a wide spectrum of deadline distributions
and can effectively improve the success ratio of transactions with deadlines.

##  5 Related Work

None of previous work considered the deadlines of transactions in payment
channel networks for time-sensitive applications while improving the success
ratio of transactions.

The first payment channel networks proposed by the Lightning Network[8] routed
transactions along the shortest path. Although transactions on Lighting
Network can be completed in a shorter time than processing transactions on
blockchain, the Lightning Network still faces the problem of insufficient
transaction success ratio and throughput. In order to solve these problems,
various algorithms have been proposed for PCNs. Flash[13] differentiated
transactions of different sizes. For small transactions, they used the routing
table to route the transaction based on the shortest path; for large
transactions, they used the modified maximum flow algorithm for transaction
routing. CoinExpress[38] modified the Ford-Fulkerson algorithm for maximum
flow[39], and proposed a distributed approach to route the transaction. These
approaches were based on network flow. In addition, there were approaches
based on landmark nodes[40] and approaches based on data networks.
SilentWhispers[11] proposed a two-way breadth-first search(BFS) to find the
shortest path from the sender to the landmark and the shortest path from the
landmark to the receiver. They used this path through the landmark as the
routing path of the transaction. In order to solve privacy disclosure problem
such as balances in the payment channel of intermediate nodes, this paper
proposes a secret-sharing-based multi-party computation and digital signature
chains to protect private data in the payment channel networks. Different from
SilentWhispers, the landmark node in SpeedyMurmurs[12] used the tree-based
graph embedding approach to provide the transaction path. Compared to
approaches based on network flow and landmark nodes, the approaches based on
data networks fully considered dynamics of the actual payment channel
networks. In Spider [21], similar to data packets in a data network, each
transaction is split into several fund-units and routed through different
paths.

Other remotely related work is as follows. D3[41] required the sender,
receiver, and switch to participate in the optimization, the core idea of
which is to implement differentiated services for various streams based on
deadlines. D2TCP[18] combined the advantages of DCTCP and D3. It considered
not only the congestion avoidance, but also the flow deadline. However, these
approaches, which inspired us in our design, cannot be simply applied to the
PCNs, as the problem we solve in PCNs differs from it in crucial ways. In the
Internet, the capacity of each link is unchanged when sending packets, while
the capacity of each channel varies dynamically after every payment in the
channel. PCNs are more dynamic than Internet and it is more challenging to
guarantee transactions’ completion time in PCNs.

##  6 CONCLUSION

In this paper, we have presented a new framework DPCN, which considers
transaction deadlines in the payment channel networks. We have proposed to
enable such framework via a synergy of three techniques, deadline-based
dynamic transaction split, deadline-aware transaction scheduling and
congestion avoidance algorithm. Our framework DPCN can ensure that time-
sensitive transactions can be completed within the specified time, while
improving the success ratio of transactions of PCNs. Our extensive evaluation
results have shown that DPCN has significantly outperformed the state-of-the-
art approaches.

## References

  * [1] M. Zamani, M. Movahedi, and M. Raykova, “Rapidchain: Scaling blockchain via full sharding,” in _ACM CCS_ , 2018.
  * [2] W. Li, C. Feng, L. Zhang _et al._ , “A scalable multi-layer pbft consensus for blockchain,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 5, pp. 1146–1160, 2021.
  * [3] J. Wang and H. Wang, “Monoxide: Scale out blockchains with asynchronous consensus zones,” in _USENIX NSDI_ , 2019.
  * [4] Y. Gilad, R. Hemo, S. Micali _et al._ , “Algorand: Scaling byzantine agreements for cryptocurrencies,” in _ACM SOSP_ , 2017.
  * [5] Bitcoin, https://bitcoin.org/en/, 2021.
  * [6] “Ethereum,” https://www.ethereum.org/, 2021.
  * [7] “Visa,” https://usa.visa.com/run-your-business/small-business-tools/retail.html, 2021\.
  * [8] “The lightning network,” https://lightning.network/, 2021.
  * [9] “The raiden network,” https://raiden.network/, 2021.
  * [10] P. Prihodko, S. Zhigulin, M. Sahno _et al._ , “Flare: An approach to routing in lightning network,” _White Paper_ , 2016.
  * [11] G. Malavolta, P. Moreno-Sanchez, A. Kate _et al._ , “Silentwhispers: Enforcing security and privacy in decentralized credit networks,” in _NDSS_ , 2017.
  * [12] S. Roos, P. Moreno-Sanchez, A. Kate _et al._ , “Settling payments fast and private: Efficient decentralized routing for path-based transactions,” _arXiv preprint arXiv:1709.05748_ , 2017.
  * [13] P. Wang, H. Xu, X. Jin _et al._ , “Flash: efficient dynamic routing for offchain networks,” in _ACM CoNEXT_ , 2019.
  * [14] “Coinbase,” https://www.coinbase.com/, 2021.
  * [15] “Binance,” https://www.binance.com/en, 2021.
  * [16] “Cryptoblades,” https://www.cryptoblades.io/, 2021.
  * [17] “Splinterlands,” https://splinterlands.com/, 2021.
  * [18] B. Vamanan, J. Hasan, and T. Vijaykumar, “Deadline-aware datacenter tcp (d2tcp),” in _ACM SIGCOMM_ , 2012.
  * [19] M. Alizadeh, A. Greenberg, D. A. Maltz _et al._ , “Data center tcp (dctcp),” in _ACM SIGCOMM_ , 2010.
  * [20] J. Poon and T. Dryja, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016.
  * [21] V. Sivaraman, S. B. Venkatakrishnan, K. Ruan _et al._ , “High throughput cryptocurrency routing in payment channel networks,” in _USENIX NSDI_ , 2020\.
  * [22] O. Osuntokun, “Atomic multi-path payments over lightning.” 2018. [Online]. Available: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/000993.html
  * [23] V. Sivaraman, S. B. Venkatakrishnan, M. Alizadeh _et al._ , “Routing cryptocurrency with the spider network,” in _ACM HotNets_ , 2018.
  * [24] C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” _Journal of the ACM (JACM)_ , vol. 20, no. 1, pp. 46–61, 1973.
  * [25] K. R. Fall and W. R. Stevens, _TCP/IP illustrated, volume 1: The protocols_. addison-Wesley, 2011.
  * [26] M. Allman, V. Paxson, W. Stevens _et al._ , “Tcp congestion control,” 1999\.
  * [27] R. Srikant, _The mathematics of Internet congestion control_. Springer Science & Business Media, 2004.
  * [28] S. Floyd, “Tcp and explicit congestion notification,” _ACM SIGCOMM Computer Communication Review_ , vol. 24, no. 5, pp. 8–23, 1994.
  * [29] K. Ramakrishnan, S. Floyd, D. Black _et al._ , “The addition of explicit congestion notification (ecn) to ip,” 2001.
  * [30] C. Poynton, _Digital video and HD: Algorithms and Interfaces_. Elsevier, 2012.
  * [31] D.-M. Chiu and R. Jain, “Analysis of the increase and decrease algorithms for congestion avoidance in computer networks,” _Computer Networks and ISDN systems_ , vol. 17, no. 1, pp. 1–14, 1989.
  * [32] “Lightning network daemon,” https://github.com/lightningnetwork/lnd, 2021\.
  * [33] “Omnet++,” http://omnetpp.org/, 2021.
  * [34] “Watts strogatz model,” https://en.wikipedia.org/wiki/Watts\%E2\%80\%93Strogatz_model, 2021.
  * [35] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘smallworld’ networks,” _Nature_ , vol. 393, p. 440–442.
  * [36] “Barabási–albert model,” https://en.wikipedia.org/wiki/Barab\%C3\%A1si\%E2\%80\%93Albert_model, 2021\.
  * [37] P. Hu and W. C. Lau, “A survey and taxonomy of graph sampling,” _arXiv preprint arXiv:1308.5865_ , 2013.
  * [38] R. Yu, G. Xue, V. T. Kilari _et al._ , “Coinexpress: A fast payment routing mechanism in blockchain-based payment channel networks,” in _IEEE ICCCN_ , 2018.
  * [39] L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,” _Canadian journal of Mathematics_ , vol. 8, pp. 399–404, 1956.
  * [40] P. F. Tsuchiya, “The landmark hierarchy: A new hierarchy for routing in very large networks,” in _ACM SIGCOMM_ , 1988.
  * [41] C. Wilson, H. Ballani, T. Karagiannis _et al._ , “Better never than late: Meeting deadlines in datacenter networks,” in _ACM SIGCOMM_ , 2011.


# Full-color photon-counting single-pixel imaging

Ya-Nan Zhao  Hebei Key Laboratory of Optic-Electronic Information and
Materials, College of Physics Science & Technology, Hebei University, Baoding
071002, Hebei Province, China  Hong-Yun Hou  Hebei Key Laboratory of Optic-
Electronic Information and Materials, College of Physics Science & Technology,
Hebei University, Baoding 071002, Hebei Province, China  Jia-Cheng Han  Hebei
Key Laboratory of Optic-Electronic Information and Materials, College of
Physics Science & Technology, Hebei University, Baoding 071002, Hebei
Province, China  Hong-Chao Liu  Institute of Applied Physics and Materials
Engineering, University of Macau, Avenida da Universidade, Taipa, Macao SAR,
China  Su-Heng Zhang<EMAIL_ADDRESS>Hebei Key Laboratory of Optic-
Electronic Information and Materials, College of Physics Science & Technology,
Hebei University, Baoding 071002, Hebei Province, China  De-Zhong Cao  School
of Opto-Electric Information Science and Technology, Yantai University, Yantai
264005, Shandong Province, China  Bao-Lai Liang<EMAIL_ADDRESS>Hebei
Key Laboratory of Optic-Electronic Information and Materials, College of
Physics Science & Technology, Hebei University, Baoding 071002, Hebei
Province, China

###### Abstract

We propose and experimentally demonstrate a high-efficiency single-pixel
imaging (SPI) scheme by integrating time-correlated single-photon counting
(TCSPC) with time-division multiplexing to acquire full-color images at
extremely low light level. This SPI scheme uses a digital micromirror device
to modulate a sequence of laser pulses with preset delays to achieve three-
color structured illumination, then employs a photomultiplier tube into the
TCSPC module to achieve photon-counting detection. By exploiting the time-
resolved capabilities of TCSPC, we demodulate the spectrum-image-encoded
signals, and then reconstruct high-quality full-color images in a single-round
of measurement. Based on this scheme, the strategies such as single-step
measurement, high-speed projection, and undersampling can further improve the
imaging efficiency.

Single-pixel imaging (SPI), which reconstructs images from the signals of a
fixed single-pixel detector, has received increasing attentions in recent
years [1]. As a representative of computational imaging schemes, photon-
counting single-pixel imaging (PCSPI) allows one to utilize time-correlated
single-photon counting (TCSPC) to capture intensity profiles and three-
dimensional structures at extremely low light level. Benefiting from TCSPC,
PCSPI has two significant performance advantages: high sensitivity and precise
timing resolution. Combined with compressed sensing, spatial correlations,
total variation constraints, PCSPI enables fewer imaging photons [2, 3, 4],
faster imaging acquisition [5, 6], longer imaging distances [7, 8], and lower
imaging noise [9]. In addition, photon-counting detectors, especially
photomultiplier tubes (PMTs), have a wide spectral response range. Therefore,
the PCSPI should also enable full-color imaging at extremely low light level.

In conventional SPI, a direct method to obtain full-color images is to acquire
the red (R), green (G), and blue (B) components separately in three rounds of
measurement. However, this would consume triple of the time of monochromatic
imaging, making SPI inefficient and hard to be implemented. Several methods
have been proposed to enhance the imaging efficiency of full-color SPI. Welsh
et al. proposed to use three spectrally filtered single-pixel detectors to
obtain the RGB components separately [10]. This approach can acquire full-
color images in one round of measurement, but increases the complexity of the
detection system. Subsequently, with the help of time-division multiplexing
(TDM) [11] and spatial multi-modulation [12, 13, 14, 15], full-color SPI
schemes with one single-pixel detector in one round of measurement have been
achieved. These schemes can reduce the multispectral imaging time to
monochrome imaging time without significantly increasing the complexity of the
imaging system. Recently, Kanno et al. used frequency-time-division
multiplexing to achieve ultrafast two-color single-pixel microscopy [16]. In
addition, by exploiting the sparsity of natural images and human visual
characters, it has been found that appropriate undersampling can be performed
to further improve the efficiency of full-color SPI [17, 18]. If these full-
color SPI approaches are introduced into photon-counting imaging to achieve
efficient full-color PCSPI, it will be of great interest on account of its
important applications under extreme environments, such as night vision,
remote sensing, and biological imaging.

In this letter, we propose and experimentally demonstrate a high-efficient
full-color PCSPI scheme. We extend the spectral resolution capability of PCSPI
by integrating it with TDM. Specifically, the proposed scheme utilizes a
sequence of red, green, and blue laser pulses with preset delays for light
source, a digital micromirror device (DMD) for structured illumination, and a
PMT with the help of TCSPC module for photon-counting detection. By exploiting
the powerful time-resolved capabilities of TCSPC, we are able to demodulate
spectrum-image-encoded signals, and then reconstruct full-color images. As a
proof-of-principle demonstration, we use this method to experimentally acquire
a high-quality full-color image of a color slide of a small rocket in one
round of measurement through the Hadamard basis scan (HBS). The strategies to
further improve the imaging efficiency are also discussed, such as using
single-step measurement, increasing the projection rate, and undersampling
imaging.

The schematic of our proposed full-color PCSPI system is depicted in Fig. 1. A
supercontinuum picosecond pulsed laser (SuperK EXTREME, NKT) is employed as
the light source, and its repetition rate is set at $f_{L}=15.6$ MHz.

Figure 1: Schematic of our full-color PCSPI. M, plane mirror; DM1, DM2,
longpass dichroic mirrors with cut-on wavelengths of $505$ nm and $605$ nm;
BPF1, BPF2, BPF3, bandpass filters with $10$ nm bandwidth and centered at
$480$ nm, $550$ nm, and $670$ nm; CM, multimode fiber collimator; FCB,
$3\times 1$ fiber combiner.

A tunable multi-line filter (SuperK SELECT, NKT) is used to select three
monochromatic pulsed lights with center wavelengths of 480 nm, 550 nm, and 670
nm from the supercontinuum laser and adjust their intensities to the desired
value (See Supplement 1, Section 1). The selected three-wavelength pulsed beam
is split into three delay paths by two longpass dichroic mirrors
(GCC-414003/6, Daheng Optics). Three bandpass filters (BP480/550/670, Ruiyan)
are placed in three delay paths, respectively, to remove the light from other
bands. In each delay path, the monochromatic pulsed light is coupled into a
fiber of designed length to produce a suitable delay time. Then, all three
monochromatic pulsed lights with different pulses delay times are combined
into a single fiber via a $3\times 1$ fiber combiner (YS1N3, Yousheng). This
combined pulsed light is coupled into a beam expander (GCO-2503, Daheng) via a
collimator, and then incident on a DMD (F4100, Xintong). The DMD is used to
convert the incident pulsed beam into a sequence of light patterns. These
light patterns work as structured illumination to be projected onto the target
object via a projection lens. Neutral density filters are used to attenuate
the light intensity to the level of single-photon counting detection. A color
slide of a small rocket is used as the target object, where the image is
located within a rectangular region of $2.6\text{ mm}\times 4.2\text{ mm}$, as
shown by the inset of Fig. 1. The transmitted light from the color slide is
redirected by a mirror to a collecting lens, and then focused onto a PMT
(R928, Hamamatsu) that operates in Geiger-mode to detect arrivals of
individual photon. To improve the photon detection efficiency, a ground glass
is placed in front of the PMT to uniform the spatial intensity distribution of
the transmitted object light. A TCSPC module (PicoHarp 300, PicoQuant) that is
triggered by the periodic sync signals from the pulsed laser, is used to
record the photon count events from PMT and the marker signals from DMD. The
TCSPC module works in time-tagged time-resolved (TTTR) mode so that the delay
time of each photon event with respect to the previous laser sync event is
recorded with picosecond resolution. In addition, the photon events and the
marker events are time tagged by counting sync events from the beginning of
the experiment .

To efficiently obtain full-color imaging, the approach of HBS is used. The
two-dimensional Hadamard transform pair is defined as

$\displaystyle\bm{F}$ $\displaystyle=\bm{H}\bm{f}\bm{H},$ (1)
$\displaystyle\bm{f}$ $\displaystyle=\frac{1}{N^{2}}\bm{H}\bm{F}\bm{H},$ (2)

where $\bm{f}$ represents the spatial sampling matrix of the object, $\bm{F}$
represents the spectrum matrix of the object, $\bm{H}$ denotes the Walsh
ordered Hadamard matrix, $N$ is the order of Hadamard matrix. It is worth
noting that $\bm{f}$ needs to be a square matrix on the order of $N$. The
complete set of Hadamard basis patterns can be generated as follows

$\left\\{\bm{P}_{uv}|\bm{P}_{uv}=\bm{H}^{T}_{u}\bm{H}_{v},\;u,\,v=0,1,\cdots,N-1\right\\},$
(3)

where $\bm{H}_{u}$, $\bm{H}_{v}$ are the $u$-th, $v$-th row vectors of
$\bm{H}$, respectively. Then the spectrum coefficient $F(u,v)$ can be written
as

$F(u,v)=\langle\bm{f},\bm{P}_{uv}\rangle_{\mathrm{F}},\quad
u,v=0,1,\cdots,N-1,$ (4)

where the $\langle\cdot,\cdot\rangle_{\mathrm{F}}$ denotes the Frobenius inner
product. According to Eq. (4), each spectrum coefficient can be acquired one
by one, hence this method is called HBS.

Differential measurement is a common implementation of HBS. In order to
acquire each spectrum coefficient $F(u,v)$ using intensity modulation, each
basis pattern $\bm{P}_{uv}$ is transformed into two non-negative patterns as
follows

$\displaystyle\bm{P}^{(+)}_{uv}$
$\displaystyle=\frac{1}{2}\left(1+\bm{P}_{uv}\right),$ (5)
$\displaystyle\bm{P}^{(-)}_{uv}$
$\displaystyle=\frac{1}{2}\left(1-\bm{P}_{uv}\right).$ (6)

These two non-negative patterns are projected onto the object in turn, and the
transmitted object light intensities measured by the single-pixel detector are

$\displaystyle D^{(+)}(u,v)$
$\displaystyle=k\langle\bm{f},I_{s}\bm{P}^{(+)}_{uv}+I_{a}b(u,v)\rangle_{\mathrm{F}},$
(7) $\displaystyle D^{(-)}(u,v)$
$\displaystyle=k\langle\bm{f},I_{s}\bm{P}^{(-)}_{uv}+I_{a}b(u,v)\rangle_{\mathrm{F}},$
(8)

where $k$ represents the quantum efficiency of the single-pixel detector,
$I_{s}$ represents the light source intensity, and $I_{a}b(u,v)$ represents
background light intensity. By differential intensity signals between the
positive and inverse patterns, the corresponding spectrum coefficient can be
achieved, i.e.

$F(u,v)=\alpha[D^{(+)}(u,v)-D^{(-)}(u,v)],$ (9)

where $\alpha=1/kI_{s}$. The background light hardly changes during the
measurement of the couple of patterns. Therefore, the differential method can
also remove the background light very well. During the imaging process, the
whole set of non-negative patterns

$\left\\{\bm{P}^{(+)}_{uv},\;\bm{P}^{(-)}_{uv}\big{|}u,\,v=0,1,\cdots,N-1\right\\}$
(10)

are projected one by one, and then the spectrum of the object can be acquired
as

$\bm{F}=\alpha\left[\bm{D}^{(+)}-\bm{D}^{(-)}\right].$ (11)

Finally, according to Eq. (2), the image of the object can be reconstructed by
inverting the Hadamard spectrum.

Differential measurement requires $2N^{2}$ non-negative basis patterns to
reconstruct an $N\times N$ pixels image. In present experiments the resolution
of all reconstructed images is set to $64\times 64$ pixels. Thus, for
differential measurement, the total number of non-negative patterns to be
projected is $M=8192$. The projection rate of DMD is set at $f_{D}=1000$ Hz.
Therefore, the image acquisition time is $t_{A}=M/f_{D}=8.192$ s. During image
acquisition, the light pulses output by the laser are $N_{L}=f_{L}\times
t_{A}\times 3\approx 3.834\times 10^{8}$, in which the factor of 3 comes from
RGB light pulses, and the total photon counts given by the PMT are about
$7.644\times 10^{6}$. Thus, only 2% of laser pulses generate a photon count at
the PMT, which maintains single-photon counting detection.

The TCSPC module records the delay time for each photon event with respect to
the sync laser trigger. So a histogram of the photon counts can be drawn with
respect to the delay time, as shown in Fig. 2.

Figure 2: The histogram of the photon counts with respect to the delay times
during the image acquisition. The width of the delay time bin is $16$ ps. The
vertical axis is log-10 scale. The photon counts located in the B, G and R
shaded regions are generated by the transmitted object light of the
corresponding color. The three associated peaks are formed due to afterpulses.

There are three main peaks, indicated by RGB ribbons, respectively. They are
generated by the transmitted object light pulses of the corresponding color.
The width of these main peaks is $3$ ns, depending on the response time of the
TCSPC system, and the separation between main peaks is about $24$ ns,
depending on the optical path difference between the delay paths. Three
associated peaks are also observed, but these are fake signals formed due to
the afterpulses in the PMT.

The photon counts within each main peak are highly time-correlated, being
overwhelmingly generated by the signal light pulses of the corresponding
color, while the photon counts outside the peak are mainly background counts
and dark counts. In order to reduce the impacts from dark counts and
background counts, only photon counts within the three shaded regions are
selected to reconstruct the corresponding RGB color component of the full-
color image. Based on the time-tag of the photon events, each photon count can
correlate with the projection pattern that generated it. Then all the photon
counts from the same projection pattern are accumulated as the bucket
intensity measured by the PMT. By using Eqs. (11) and (2), the B, G, and R
component images can be reconstructed from the corresponding photon counts, as
shown in Figs. 3(a) – (c). The ultimate full-color image, as shown in Fig.
3(d), has good imaging quality with normal color. It should be noted that the
relative height of the main peaks in the photon counts histogram affect the
color balance of the reconstructed ultimate full-color image. In our
experiments, we made the heights of the three main peaks to be nearly equal,
as shown in Fig. 2, through independent adjustment of each color light
intensity, and then the ultimate full-color image showed a good color balance.
However, if the heights of the main peaks are significantly different, the
ultimate full-color image will show color imbalance (See Supplement 1, Section
2).

Figure 3: Experimentally reconstructed images with differential measurement.
(a) – (c) B, G , and R component images reconstructed from the corresponding
photon counts; (d) full-color composite image.

In order to obtain appropriate spatial resolution and imaging range, the
projection patterns are resized to $192\times 192$ pixels by the nearest-
neighbor interpolation process and then displayed onto the DMD. The light
patterns modulated by the DMD are projected onto the object at a magnification
of $2.52$. Thus the spatial resolution and size of the reconstructed image are
about $103.42$ µm and $6.62$ mm, respectively.

The above differential method requires two measurements to obtain a spectrum
coefficient, which can effectively eliminate the influence of background
light, but doubles measurements. Recently, Xiao et al. proposed a single-step
measurement method to reduce half of the measurements [19]. Its principle is
as follows. By substituting Eq. (5) into Eq. (7) yields

$D^{(+)}(u,v)=\frac{kI_{s}}{2}F(0,0)+\frac{kI_{s}}{2}F(u,v)+kI_{a}F(0,0)b(u,v).$
(12)

Let $F^{\prime}(u,v)=\alpha[2D^{(+)}(u,v)-D^{(+)}(0,0)]$, then it can be find
that $F^{\prime}(u,v)=F(u,v)+\beta b^{\prime}(u,v)$, where
$\beta=(I_{a}/I_{s})F(0,0)$, $b^{\prime}(u,v)=2b(u,v)-b(0,0)$. This indicates
that each spectrum coefficient can be obtained by just a single-step
measurement. During image acquisition, only the positive patterns are
measured, and the entire Hadamard spectrum can be obtained as

$\bm{F}^{\prime}=\alpha[2\bm{D}^{(+)}-D^{(+)}(0,0)].$ (13)

However, the measured spectrum contains a background term, i.e.
$\bm{F}^{\prime}=\bm{F}+\beta\bm{b}^{\prime}$. If the Hadamard inversion of
the measured spectrum is performed directly, the reconstructed image can be
expressed as $\bm{f}^{\prime}=\bm{f}+\beta\bm{B}^{\prime}/N^{2}$, where
$\bm{B}^{\prime}=\bm{B}+\bm{B}_{e}$, $\bm{B}=\bm{H}\bm{b}\bm{H}$,
$\bm{B}_{e}=\bm{H}\left[\bm{b}-b(0,0)\right]\bm{H}$. Note that the influence
of the background light on each measured spectrum coefficient is statistically
homogeneous, but not on the reconstructed image.

The energy of the background spectrum $\bm{B}$ is mainly concentrated around
the upper left corner, while the relative changes $\bm{b}-b(0,0)$ of the
background are associated with the high-frequency components, and the energy
of its spectrum $\bm{B}_{e}$ is mainly concentrated around the other corners.
Therefore, when the image of the object has no energy distribution at the edge
of the imaging area, the background term can be separated for reasonable
estimation. Let $\beta\bm{\hat{B}}^{\prime}/N^{2}$ represents the estimation
of the background term, the estimation of the Hadamard spectrum of object can
be written as $\bm{\hat{F}}=\bm{F}^{\prime}-\beta\bm{\hat{b}}^{\prime}$, where
$\bm{\hat{b}}^{\prime}=\bm{H}\bm{\hat{B}}^{\prime}\bm{H}/N^{2}$. Then perform
the inverse Hadamard transform to obtain the estimation of the object image.

Based on the single-step measurement technique, one can increase the
projection rate of DMD, and reduce the measurements by under-sampling to
further improve efficiency. The reconstructed images using the single-step
method with different projection rates and different sampling ratios are shown
in Fig. 4.

Figure 4: Experimentally reconstructed images with single-step measurement at
different projection rates and different sampling ratios.

Since the rocket image is located within the target region, the part outside
the target region in the reconstructed image is considered as the background
term (See Supplement 1, section 3). As the projection rate $f_{D}$ increases,
the noise of the reconstructed image increases significantly. This is because
the projection rate $f_{D}$ increases, the dwell time of every single
projection pattern is shortened, and the photon counts are more affected by
the Poisson noise. As the sampling ratio $R$ decreases, the reconstructed
image gradually lost its details. However, the noise is also reduced by
spatially smoothing. Therefore, it is possible to quickly acquire the contours
of the object at high projection rate and low sampling ratio.

For reference, the structural similarity index (SSIM) and the peak signal-to-
noise ratio (PSNR) are used to quantitatively evaluate the quality of
reconstructed images in Fig. 4. The calculation of these quality parameters is
based on the target region of the differential reconstructed image. The
reconstructed image quality with single-step measurement is more susceptible
to the sampling strategy. Although the commonly used zig-zag strategy can
preserve more details [20], it may also introduce more noise. To solve this
issue, we propose a new sampling strategy, named hyperbolic sampling strategy,
which only acquire the spectrum coefficients whose spatial frequency $u,\,v$
satisfy $\left[(N-1-u)(N-1-v)\right]^{{1}/{2}}\geq\rho_{c}$, where $\rho_{c}$
is called cutoff frequency, and takes the values in the range $[0,\;N-1]$ (See
Supplement 1, Section 4).

In conclusion, we demonstrate an efficient full-color PCSPI scheme. This PCSPI
scheme fully exploits the time-resolved capabilities of TCSPC to acquire a
full-color image, using only one single-pixel detector in a single round of
measurements. Benefiting from TDM, this method takes time to acquire a full-
color image the same as that for a monochromatic image. Based on this scheme,
one can also use single-step measurement, high-speed projection, and
undersampling to further improve imaging efficiency, which offers a
possibility to achieve full-color imaging of 3D realistic moving objects at
extremely low light level. In addition, this scheme can also be adopted by
other computational imaging techniques to achieve multispectral imaging.

## Funding

Natural Science Foundation of Hebei province (F2019201446); Start-up Research
Grant of University of Macau (SRG2019-00174-IAPME); National Natural Science
Foundation of China (NSFC) (11204062, 11674273).

## Disclosures

The authors declare no conflicts of interest.

## Supplement document

See Supplement 1 for supporting content.

## References

  * Gibson  _et al._ [2020] G. M. Gibson, S. D. Johnson, and M. J. Padgett, Single-pixel imaging 12 years on: A review, Optics Express 28, 28190 (2020).
  * Kirmani  _et al._ [2014] A. Kirmani, D. Venkatraman, D. Shin, A. Colaço, F. N. C. Wong, J. H. Shapiro, and V. K. Goyal, First-Photon Imaging, Science 343, 58 (2014).
  * Yang  _et al._ [2015] Y. Yang, J. Shi, F. Cao, J. Peng, and G. Zeng, Computational imaging based on time-correlated single-photon-counting technique at low light level, Applied Optics 54, 9277 (2015).
  * Liu  _et al._ [2020] X. Liu, J. Shi, L. Sun, Y. Li, J. Fan, and G. Zeng, Photon-limited single-pixel imaging, Optics Express 28, 8132 (2020).
  * Howland  _et al._ [2013] G. A. Howland, D. J. Lum, M. R. Ware, and J. C. Howell, Photon counting compressive depth mapping, Optics Express 21, 23822 (2013).
  * Liu  _et al._ [2018] X. Liu, J. Shi, X. Wu, and G. Zeng, Fast first-photon ghost imaging, Scientific Reports 8, 5012 (2018).
  * Pawlikowska  _et al._ [2017] A. M. Pawlikowska, A. Halimi, R. A. Lamb, and G. S. Buller, Single-photon three-dimensional imaging at up to 10 kilometers range, Optics Express 25, 11919 (2017).
  * Li  _et al._ [2021] Z.-P. Li, J.-T. Ye, X. Huang, P.-Y. Jiang, Y. Cao, Y. Hong, C. Yu, J. Zhang, Q. Zhang, C.-Z. Peng, F. Xu, and J.-W. Pan, Single-photon imaging over 200 km, Optica 8, 344 (2021).
  * Chen  _et al._ [2020] W. Chen, S. Li, and X. Tian, Robust single-photon counting imaging with spatially correlated and total variation constraints, Optics Express 28, 2625 (2020).
  * Welsh  _et al._ [2013] S. S. Welsh, M. P. Edgar, R. Bowman, P. Jonathan, B. Sun, and M. J. Padgett, Fast full-color computational imaging with single-pixel detectors, Optics Express 21, 23068 (2013).
  * Salvador-Balaguer  _et al._ [2015] E. Salvador-Balaguer, P. Clemente, E. Tajauerce, F. Pla, and J. Lancis, Full-color stereoscopic imaging with a single-pixel photodetector, Journal of Display Technology , 1 (2015).
  * Huang and Shi [2017] J. Huang and D. Shi, Multispectral computational ghost imaging with multiplexed illumination, Journal of Optics 19, 075701 (2017).
  * Li  _et al._ [2017] Z. Li, J. Suo, X. Hu, C. Deng, J. Fan, and Q. Dai, Efficient single-pixel multispectral imaging via non-mechanical spatio-spectral modulation, Scientific Reports 7, 41435 (2017).
  * Zhang  _et al._ [2018] Z. Zhang, S. Liu, J. Peng, M. Yao, G. Zheng, and J. Zhong, Simultaneous spatial, spectral, and 3D compressive imaging via efficient Fourier single-pixel measurements, Optica 5, 315 (2018).
  * Ye  _et al._ [2021] Z. Ye, J. Xiong, and H.-C. Liu, Ghost Difference Imaging Using One Single-Pixel Detector, Physical Review Applied 15, 034035 (2021).
  * Kanno  _et al._ [2020] H. Kanno, H. Mikami, and K. Goda, High-speed single-pixel imaging by frequency-time-division multiplexing, Optics Letters 45, 2339 (2020).
  * Yan  _et al._ [2016] Y. Yan, H. Dai, X. Liu, W. He, Q. Chen, and G. Gu, Colored adaptive compressed imaging with a single photodiode, Applied Optics 55, 3711 (2016).
  * Qiu  _et al._ [2020] Z. Qiu, Z. Zhang, and J. Zhong, Efficient full-color single-pixel imaging based on the human vision property—“giving in to the blues”, Optics Letters 45, 3046 (2020).
  * Xiao  _et al._ [2019] Y. Xiao, L. Zhou, and W. Chen, Direct Single-Step Measurement of Hadamard Spectrum Using Single-Pixel Optical Detection, IEEE Photonics Technology Letters 31, 845 (2019).
  * Zhang  _et al._ [2017] Z. Zhang, X. Wang, G. Zheng, and J. Zhong, Hadamard single-pixel imaging versus Fourier single-pixel imaging, Optics Express 25, 19619 (2017).