$\forall(m,\phi),(m^{\prime},\phi^{\prime})\in\mathcal{C}(p^{\Phi}):m=m^{\prime}\Rightarrow\phi=\phi^{\prime}$.

We now show that if the lemma holds for any well-formed RETE net
$(N_{h},p_{h})$ with join-tree height $h$, it also holds for any well-formed
RETE net $(N,p)$ with join-tree height $h+1$.

Since $h+1\geq 1$, it holds that
$(N^{\Phi},p^{\Phi})=localize((N,p))=(N^{\Phi}_{\bowtie}\cup N^{\Phi}_{l}\cup
N^{\Phi}_{r}\cup RPS_{l}\cup RPS_{r},p^{\Phi})$, with
$(N^{\Phi}_{l},p^{\Phi}_{l})=localize((N_{l},p_{l}))$ and
$(N^{\Phi}_{r},p^{\Phi}_{r})=localize((N_{r},p_{r}))$, where $p_{l}$ is the
left dependency of the join node $p$ with associated subtree $N_{l}$ and
$p_{r}$ is the right dependency of $p$ with associated subtree $N_{r}$. Since
both $N_{l}$ and $N_{r}$ must have a join-tree height less than $h+1$, by the
induction hypothesis it follows that
$\forall(m,\phi),(m^{\prime},\phi^{\prime})\in\mathcal{C}(p^{\Phi}_{l}):m=m^{\prime}\Rightarrow\phi=\phi^{\prime}$
and
$\forall(m,\phi),(m^{\prime},\phi^{\prime})\in\mathcal{C}(p^{\Phi}_{r}):m=m^{\prime}\Rightarrow\phi=\phi^{\prime}$.
By the semantics of the marking-sensitive join node $p^{\Phi}$, which has
$p^{\Phi}_{l}$ and $p^{\Phi}_{r}$ as left respectively right dependency, it
must follow that
$\forall(m,\phi),(m^{\prime},\phi^{\prime})\in\mathcal{C}(p^{\Phi}):m=m^{\prime}\Rightarrow\phi=\phi^{\prime}$.

From the correctness of the base case and the induction step then follows the
correctness of the lemma.

We say that a marking-sensitive RETE net $(X^{\Phi},p^{\Phi}_{X})$ is a
_modular extension_ of $(N^{\Phi},p^{\Phi})$ if $N^{\Phi}\subseteq X^{\Phi}$
and $\forall e\in E^{X^{\Phi}}:s^{X^{\Phi}}(e)\in V^{N^{\Phi}}\wedge
t^{X^{\Phi}}(e)\in V^{N^{\Phi}}\Rightarrow e\in E^{N^{\Phi}}$.

We say that an execution order $O$ for $(N^{\Phi},p^{\Phi})$ is _robust under
modular extension_ if for any modular extension $(X^{\Phi},p^{\Phi}_{X})$,
host graph $H$, and starting configuration $\mathcal{C}_{0}$ for
$(X^{\Phi},p^{\Phi}_{X})$, it holds that
$\mathcal{C}=execute(O,X^{\Phi},H,H_{p},\mathcal{C_{0}})$ is consistent for
all RETE nodes $n\in V^{N^{\Phi}}$.

The execution order $O=order((N^{\Phi},p^{\Phi}))$ is indeed robust under
modular extension:

###### Lemma 13

Given a well-formed RETE net $(N,p)$, the execution order
$O=order((N^{\Phi},p^{\Phi}))$ for $(N^{\Phi},p^{\Phi})=localize((N,p))$ is
robust under modular extension.

###### Proof

We prove the lemma by induction over the height $h$ of the join tree $N$.

We begin by showing that the lemma holds for the base case of $h=0$, where $N$
consists of a single edge input node. Thus,
$(N^{\Phi},p^{\Phi})=localize((N,p))=(LNS(p),p^{\Phi})$, that is, the marking-
sensitive RETE graph is given by a single local navigation structure. This
graph contains no cyclic dependencies on current results. A modular extension
$(X^{\Phi},p^{\Phi}_{X})$ of $(N^{\Phi},p^{\Phi})$ may not add any
dependencies between nodes in $V^{N^{\Phi}}$ and hence cannot create any
cycles. Since $O$ contains all nodes in $V^{N^{\Phi}}$ and no node execution
in $O$ can impact the target result set of a previous node, after executing
$O=toposort(N^{\Phi})^{-1}$ with some starting configuration $\mathcal{C}_{0}$
for $(X^{\Phi},p^{\Phi}_{X})$, the resulting configuration
$\mathcal{C}_{1}=execute(O,X^{\Phi},H,H_{p},\mathcal{C}_{0})$ must thus be
consistent for all nodes $n\in V^{N^{\Phi}}$.

We now show that, if it holds that $O_{h}=order((N^{\Phi}_{h},p^{\Phi}_{h}))$
with $(N^{\Phi}_{h},p^{\Phi}_{h})=localize((N_{h},p_{h}))$ is robust under
modular extension for any well-formed RETE net $(N_{h},p_{h})$ with join-tree
height less than or equal to $h$, it follows that
$O=order((N^{\Phi},p^{\Phi}))$ with $(N^{\Phi},p^{\Phi})=localize(N,p)$ is
robust under modular extension for any well-formed RETE net $(N,p)$ with join-
tree height $h+1$.

Since $h+1\geq 1$, it follows that $p$ is a join node, which has a left
dependency $p_{l}$, which is the root of a RETE subtree $N_{l}$, and a right
dependency $p_{r}$, which is the root of a RETE subtree $N_{r}$. Hence,
$(N^{\Phi},p^{\Phi})=(N^{\Phi}_{\bowtie}\cup N^{\Phi}_{l}\cup N^{\Phi}_{r}\cup
RPS_{l}\cup RPS_{r},p^{\Phi})$, with
$(N^{\Phi}_{l},p^{\Phi}_{l})=localize((N_{l},p_{l}))$,
$(N^{\Phi}_{r},p^{\Phi}_{r})=localize((N_{r},p_{r}))$, $N^{\Phi}_{\bowtie}$ a
RETE net fragment consisting of a marking-sensitive join $p^{\Phi}$ with left
dependency $p^{\Phi}_{l}$ and right dependency $p^{\Phi}_{r}$,
$RPS_{l}=RPS(N^{\Phi}_{r},p^{\Phi}_{l})$, and
$RPS_{r}=RPS(N^{\Phi}_{l},p^{\Phi}_{r}))$. The execution order is thus given
by $O=order((N^{\Phi},p^{\Phi}))=order(RPS_{r})\circ order(N^{\Phi}_{l})\circ
order(RPS_{l})\circ order(N^{\Phi}_{r})\circ order(RPS_{r})\circ
order(N^{\Phi}_{l})\circ order(N^{\Phi}_{\bowtie})$.

Given some modular extension $(X^{\Phi},p^{\Phi}_{X})$ of
$(N^{\Phi},p^{\Phi})$, we can observe that $(X^{\Phi},p^{\Phi}_{X})$ is also a
modular extension of both $(N^{\Phi}_{l},p^{\Phi}_{l})$ and
$(N^{\Phi}_{r},p^{\Phi}_{r})$ by definition. Furthermore, because $N$ has a
join-tree height of $h+1$, it follows that $N_{l}$ and $N_{r}$ must have join-
tree height $h_{l}\leq h$ respectively $h_{r}\leq h$.

Some initial configuration $\mathcal{C}_{0}$ for $(X^{\Phi},p^{\Phi}_{X})$ may
be inconsistent for all of the nodes in $N^{\Phi}$. Because $RPS_{l}$ just
consists of three consecutive RETE nodes and the modular extension $X^{\Phi}$
may not add additional dependencies between nodes in $N^{\Phi}$, it follows
that
$\mathcal{C}_{0.1}=execute(order(RPS_{r}),X^{\Phi},H,H_{p},\mathcal{C}_{0})$
is consistent for all nodes in $V^{RPS_{r}}$.

Since, by the induction hypothesis, we know that
$O_{l}=order((N^{\Phi}_{l},p^{\Phi}_{l}))$ is robust under modular extension
and $(X^{\Phi},p^{\Phi}_{X})$ is a modular extension of
$(N^{\Phi}_{l},p^{\Phi}_{l})$ and since no node in $V^{RPS_{r}}$ depends on a
node in $N^{\Phi}_{l}$, it follows that after executing $O_{l}$, the resulting
configuration
$\mathcal{C}_{0.2}=execute(O_{l},X^{\Phi},H,H_{p},\mathcal{C}_{0.1})$ is
consistent for all nodes in $V^{N^{\Phi}_{l}}\cup V^{RPS_{r}}$.

Since no node in $V^{N^{\Phi}_{l}}\cup V^{RPS_{r}}$ depends on any node in
$RPS_{l}$, by the same logic as for $RPS_{r}$, we know that
$\mathcal{C}_{0.3}=execute(order(RPS_{l}),X^{\Phi},H,H_{p},\mathcal{C}_{0.2})$
must be consistent for all nodes in $V^{N^{\Phi}_{l}}\cup V^{RPS_{l}}\cup
V^{RPS_{r}}$.

Due to the robustness under modular extension of
$O_{r}=order((N^{\Phi}_{r},p^{\Phi}_{r}))$ and because among nodes in
$V^{N^{\Phi}_{l}}\cup V^{RPS_{l}}\cup V^{RPS_{r}}$, only the marking filter
node $[\phi>h+1]_{l}^{\Phi}$ in $V^{RPS_{r}}$ depends on a node in
$V^{N^{\Phi}_{r}}$,
$\mathcal{C}_{0.4}=execute(O_{r},X^{\Phi},H,H_{p},\mathcal{C}_{0.3})$ then
must be consistent for all nodes in
$V^{N^{\Phi}}\setminus(\\{[\phi>h+1]_{l}^{\Phi}\\}\cup
V^{N^{\Phi}_{\bowtie}})$.

By similar logic,
$\mathcal{C}_{0.5}=execute(order(RPS_{r}),X^{\Phi},H,H_{p},\mathcal{C}_{0.4})$
is then consistent for all nodes in
$V^{N^{\Phi}}\setminus(\\{[\cup]^{\Phi}_{v}\\}\cup V^{N^{\Phi}_{\bowtie}})$,
where $[\cup]^{\Phi}_{v}$ is the union node in $N^{\Phi}_{l}$ that depends on
the marking assignment node $[\phi:=h+1]^{\Phi}$ in $RPS_{r}$.

By the semantics of the marking assignment node $[\phi:=h+1]$ in $RPS_{r}$ and
no node in $V^{N^{\Phi}_{l}}$ depending on any other node in
$order(RPS_{l})\circ order(N^{\Phi}_{r})\circ order(RPS_{r})$, we know that
$\forall n_{X}\in V^{X^{\Phi}}:(\exists e\in
E^{X^{\Phi}}:t^{X^{\Phi}}=n_{X}\wedge s^{X^{\Phi}}\in
V^{N^{\Phi}_{l}})\Rightarrow\forall(m,\phi)\in(\mathcal{C}_{0.5}(n_{X})\setminus\mathcal{C}_{0.4}(n_{X}))\cup(\mathcal{C}_{0.4}(n_{X})\setminus\mathcal{C}_{0.5}(n_{X})):\phi\leq
h+1$. Furthermore, $\mathcal{C}_{0.4}$ is consistent for all nodes in
$V^{N^{\Phi}_{l}}$ and it holds that $\forall n\in
V^{N^{\Phi}_{l}}:\mathcal{C}_{0.5}(n)=\mathcal{C}_{0.4}(n)$. By the induction
hypothesis, we know that the execution order $order(N^{\Phi}_{h-1})$ is robust
under modular extension for any localized RETE net
$(N^{\Phi}_{h-1},p^{\Phi}_{h-1})=localize((N_{h-1},p_{h-1}))$, if
$(N_{h-1},p_{h-1})$ is a well-formed RETE net with join tree height
$h^{\prime}<h$. Finally, $N_{l}$ must have a join tree height of
$h^{\prime}<h+1$.

Thus, by Lemma 4, it follows for
$\mathcal{C}_{0.6}=execute(O_{l},X^{\Phi},H,H_{p},\mathcal{C}_{0.5})$ that
$\forall(m,\phi)\in(\mathcal{C}_{0.6}(p^{\Phi}_{l})\setminus\mathcal{C}_{0.5}(p^{\Phi}_{l}))\cup(\mathcal{C}_{0.5}(p^{\Phi}_{l})\setminus\mathcal{C}_{0.6}(p^{\Phi}_{l})):\phi\leq
h+1$. Because no node in $V^{N^{\Phi}}\setminus V^{N^{\Phi}_{l}}$ other than
the marking filter node $[\phi>h+1]_{r}^{\Phi}$ can depend on any node in
$V^{N^{\Phi}_{l}}$, because $O_{l}$ is robust under modular extension, and by
the semantics of $[\phi>h+1]_{r}^{\Phi}$, it then follows that
$\mathcal{C}_{0.6}$ is consistent for all nodes in $V^{N^{\Phi}}\setminus
V^{N^{\Phi}_{\bowtie}}$.

Since $N^{\Phi}_{\bowtie}$ consists only of a marking-sensitive join node
which no other node in $V^{N^{\Phi}}$ depends on, it follows that
$\mathcal{C}_{1}=execute(order(N^{\Phi}_{\bowtie},X^{\Phi},H,H_{p},\mathcal{C}_{0.6})=execute(order((N^{\Phi},p^{\Phi})),H,\mathcal{C}_{0})$
must be consistent for all nodes in $V^{N^{\Phi}}$. It thus follows that
$order((N^{\Phi},p^{\Phi}))$ must be robust under modular extension for any
well-formed RETE net $(N,p)$ with join-tree height $h+1$.

From the correctness of the base case and the induction step then follows the
correctness of the lemma.

###### Lemma 14

Let $H$ be a graph, $H_{p}\subseteq H$, $[v\rightarrow_{n}w]^{\Phi}\in
V^{N^{\Phi}}$ a forward navigation node with dependency $n^{\Phi}_{v}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[v\rightarrow_{n}w]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{v}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi})=\mathcal{C}^{\Phi}_{1}([v\rightarrow_{n}w]^{\Phi})$.
Executing $[v\rightarrow_{n}w]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([v\rightarrow_{n}w]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R}+N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps,
where $S^{+}_{D}=\sum_{m\in M^{+}_{D}}|m|$ with
$M^{+}_{D}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{v})\\}$,
$S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([v\rightarrow_{n}w]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi})\\}$,
$N^{\uparrow}_{D}=|\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{v})\setminus\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v})|$,
and
$N^{\uparrow}_{R}=|\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi})\setminus\mathcal{C}^{\Phi}_{2}([v\rightarrow_{n}w]^{\Phi})|$.

###### Proof

Assuming changes to the result set of $n^{\Phi}_{v}$ are cached and
$\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[v\rightarrow_{n}w]^{\Phi}$ can be executed in two
phases.

First execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v})$ that represent newly added matches
compared to $\mathcal{C}^{\Phi}_{0}$, constructs the corresponding
intermediate results for $[v\rightarrow_{n}w]^{\Phi}$, and adds them to
$\mathcal{C}^{\Phi}_{1}([v\rightarrow_{n}w]^{\Phi})$. Given a suitable
representation of $H$ that allows efficient retrieval of edges adjacent to a
node and assuming indexing structures that allow insertion times into result
sets linear in match size, this takes $O(S^{+}_{D}+S^{+}_{R})$ steps.

Second, execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v})$ that represent matches whose marking
has been increased compared to $\mathcal{C}^{\Phi}_{0}$ and adjusts the
marking of the corresponding intermediate results in
$\mathcal{C}^{\Phi}_{1}([v\rightarrow_{n}w]^{\Phi})$. By modifying
intermediate results for $n^{\Phi}_{v}$ on a change of marking instead of
creating new tuples and by maintaining appropriate references between the
intermediate results for $n^{\Phi}_{v}$ and for $[v\rightarrow_{n}w]^{\Phi}$,
this can be achieved in $O(N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps.

This yields the stated complexity.

###### Lemma 15

Let $H$ be a graph, $H_{p}\subseteq H$, $[w\leftarrow_{n}v]^{\Phi}\in
V^{N^{\Phi}}$ a backward navigation node with dependency $n^{\Phi}_{w}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[w\leftarrow_{n}v]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{w}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi})=\mathcal{C}^{\Phi}_{1}([w\leftarrow_{n}v]^{\Phi})$.
Executing $[w\leftarrow_{n}v]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([w\leftarrow_{n}v]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R}+N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps,
where $S^{+}_{D}=\sum_{m\in M^{+}_{D}}|m|$ with
$M^{+}_{D}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{w})\\}$,
$S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([w\leftarrow_{n}v]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi})\\}$,
$N^{\uparrow}_{D}=|\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{w})\setminus\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w})|$,
and
$N^{\uparrow}_{R}=|\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi})\setminus\mathcal{C}^{\Phi}_{2}([w\leftarrow_{n}v]^{\Phi})|$.

###### Proof

Assuming changes to the result set of $n^{\Phi}_{w}$ are cached and
$\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[w\leftarrow_{n}v]^{\Phi}$ can be executed in two
phases.

First execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w})$ that represent newly added matches
compared to $\mathcal{C}^{\Phi}_{0}$, constructs the corresponding
intermediate results for $[w\leftarrow_{n}v]^{\Phi}$, and adds them to
$\mathcal{C}^{\Phi}_{1}([w\leftarrow_{n}v]^{\Phi})$. Given a suitable
representation of $H$ that allows efficient retrieval of edges adjacent to a
node and assuming indexing structures that allow insertion times into result
sets linear in match size, this takes $O(S^{+}_{D}+S^{+}_{R})$ steps.

Second, execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w})$ that represent matches whose marking
has been increased compared to $\mathcal{C}^{\Phi}_{0}$ and adjusts the
marking of the corresponding intermediate results in
$\mathcal{C}^{\Phi}_{1}([w\leftarrow_{n}v]^{\Phi})$. By modifying intermediate
results for $n^{\Phi}_{w}$ on a change of marking instead of creating new
tuples and by maintaining appropriate references between the intermediate
results for $n^{\Phi}_{w}$ and for $[w\leftarrow_{n}v]^{\Phi}$, this can be
achieved in $O(N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps.

This yields the stated complexity.

###### Lemma 16

Let $H$ be a graph, $H_{p}\subseteq H$, $[\pi_{Q}]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive projection node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\pi_{Q}]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi})=\mathcal{C}^{\Phi}_{1}([\pi_{Q}]^{\Phi})$.
Executing the marking-sensitive projection node $[\pi_{Q}]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([\pi_{Q}]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R}+N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps,
where $S^{+}_{D}=\sum_{m\in M^{+}_{D}}|m|$ with
$M^{+}_{D}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\\}$,
$S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\pi_{Q}]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi})\\}$,
$N^{\uparrow}_{D}=|\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\setminus\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})|$,
and
$N^{\uparrow}_{R}=|\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi})\setminus\mathcal{C}^{\Phi}_{2}([\pi_{Q}]^{\Phi})|$.

###### Proof

Assuming changes to the result set of $n^{\Phi}_{\alpha}$ are cached and
$\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[\pi_{Q}]^{\Phi}$ can be executed in two phases.

First execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that represent newly added matches
compared to $\mathcal{C}^{\Phi}_{0}$, constructs the corresponding
intermediate results for $[\pi_{Q}]^{\Phi}$, and adds them to
$\mathcal{C}^{\Phi}_{1}([\pi_{Q}]^{\Phi})$ if they are not yet present.
Assuming indexing structures that allow presence check and insertion times
linear in match size, this takes $O(S^{+}_{D}+S^{+}_{R})$ steps.

Second, execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that represent matches whose
marking has been increased compared to $\mathcal{C}^{\Phi}_{0}$ and adjusts
the marking of the corresponding intermediate results in
$\mathcal{C}^{\Phi}_{1}([\pi_{Q}]^{\Phi})$, if its current marking is lower.
By modifying intermediate results for $n^{\Phi}_{\alpha}$ on a change of
marking instead of creating new tuples and by maintaining appropriate
references between the intermediate results for $n^{\Phi}_{\alpha}$ and for
$[\pi_{Q}]^{\Phi}$, this can be achieved in
$O(N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps.

This yields the stated complexity.

###### Lemma 17

Let $H$ be a graph, $H_{p}\subseteq H$, $[\cup]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive union node with dependencies $N^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\cup]^{\Phi}$, $\forall
n^{\Phi}_{\alpha}\in
N^{\Phi}_{\alpha}:\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi})=\mathcal{C}^{\Phi}_{1}([\cup]^{\Phi})$.
Executing $[\cup]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([\cup]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R}+N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps,
where $S^{+}_{D}=\sum_{n^{\Phi}_{\alpha}\in N^{\Phi}_{\alpha}}\sum_{m\in
M^{+}_{n^{\Phi}_{\alpha}}}|m|$ with
$M^{+}_{n^{\Phi}_{\alpha}}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\\}$,
$S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\cup]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi})\\}$,
$N^{\uparrow}_{D}=\sum_{n^{\Phi}_{\alpha}\in
N^{\Phi}_{\alpha}}|\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\setminus\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})|$,
and
$N^{\uparrow}_{R}=|\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi})\setminus\mathcal{C}^{\Phi}_{2}([\cup]^{\Phi})|$.

###### Proof

Assuming changes to the result sets of nodes in $N^{\Phi}_{\alpha}$ are cached
and $\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[\cup]^{\Phi}$ can be executed in two phases.

First, for each $n^{\Phi}_{\alpha}\in N^{\Phi}_{\alpha}$, execution iterates
over the intermediate results in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$
that represent newly added matches compared to $\mathcal{C}^{\Phi}_{0}$, and
retrieves the corresponding intermediate result from
$\mathcal{C}^{\Phi}_{1}([\cup]^{\Phi})$ if there is any. If there is one,
execution then checks whether the newly added dependency match has a higher
marking and potentially modifies the marking in
$\mathcal{C}^{\Phi}_{1}([\cup]^{\Phi})$. Otherwise, the intermediate result
for $[\cup]^{\Phi}$ corresponding to the newly added match is constructed and
added to $\mathcal{C}^{\Phi}_{1}([\cup]^{\Phi})$. Assuming indexing structures
that allow retrieval and insertion times linear in match size, this takes
$O(S^{+}_{D}+S^{+}_{R})$ steps for all $n^{\Phi}_{\alpha}$.

Second, for each $n^{\Phi}_{\alpha}\in N^{\Phi}_{\alpha}$, execution iterates
over the intermediate results in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$
that represent matches whose marking has been increased compared to
$\mathcal{C}^{\Phi}_{0}$ and adjusts the marking of the corresponding
intermediate results in $\mathcal{C}^{\Phi}_{1}([\cup]^{\Phi})$, if its
current marking is lower. By modifying intermediate results for
$n^{\Phi}_{\alpha}$ on a change of marking instead of creating new tuples and
by maintaining appropriate references between the intermediate results for
$n^{\Phi}_{\alpha}$ and for $[\cup]^{\Phi}$, this can be achieved in
$O(N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps for all $n^{\Phi}_{\alpha}$.

This yields the stated complexity.

###### Lemma 18

Let $H$ be a graph, $H_{p}\subseteq H$, $[\phi>x]^{\Phi}\in V^{N^{\Phi}}$ a
marking filter node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi>x]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi})=\mathcal{C}^{\Phi}_{1}([\phi>x]^{\Phi})$.
Executing $[\phi>x]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([\phi>x]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R}+N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps,
where $S^{+}_{D}=\sum_{m\in M^{+}_{D}}|m|$ with
$M^{+}_{D}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\\}$,
$S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi})\\}$,
$N^{\uparrow}_{D}=|\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\setminus\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})|$,
and
$N^{\uparrow}_{R}=|\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi})\setminus\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi})|$.

###### Proof

Assuming changes to the result set of $n^{\Phi}_{\alpha}$ are cached and
$\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[\phi>x]^{\Phi}$ can be executed in two phases.

First execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that represent newly added matches
compared to $\mathcal{C}^{\Phi}_{0}$ and constructs the corresponding
intermediate results for $[\phi>x]^{\Phi}$. Each such constructed result with
a marking higher than $x$ is then added to
$\mathcal{C}^{\Phi}_{1}([\phi>x]^{\Phi})$. Constructed tuples with lower
marking are stored separatly to potentially be added later, already locating
their insertion position into $\mathcal{C}^{\Phi}_{1}([\phi>x]^{\Phi})$.
Assuming indexing structures that allow insertion times linear in match size,
this takes $O(S^{+}_{D}+S^{+}_{R})$ steps.

Second, execution iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that represent matches whose
marking has been increased compared to $\mathcal{C}^{\Phi}_{0}$ and adjusts
the marking of the corresponding intermediate results in
$\mathcal{C}^{\Phi}_{1}([\phi>x]^{\Phi})$ or in the separate storage. If an
intermediate result in the separate storage now has a marking higher than $x$,
it is added into its previously located position in
$\mathcal{C}^{\Phi}_{1}([\phi>x]^{\Phi})$. By modifying intermediate results
for $n^{\Phi}_{\alpha}$ on a change of marking instead of creating new tuples
and by maintaining appropriate references between the intermediate results for
$n^{\Phi}_{\alpha}$ and for $[\phi>x]^{\Phi}$, this can be achieved in
$O(N^{\uparrow}_{D}+N^{\uparrow}_{R})$ steps.

This yields the stated complexity.

###### Lemma 19

Let $H$ be a graph, $H_{p}\subseteq H$, $[\phi:=x]^{\Phi}\in V^{N^{\Phi}}$ a
marking filter node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi:=x]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$,
and
$\mathcal{C}^{\Phi}_{0}([\phi:=x]^{\Phi})=\mathcal{C}^{\Phi}_{1}([\phi:=x]^{\Phi})$.
Executing $[\phi:=x]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{2}=execute([\phi:=x]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
then takes $O(S^{+}_{D}+S^{+}_{R})$ steps, where $S^{+}_{D}=\sum_{m\in
M^{+}_{D}}|m|$ with
$M^{+}_{D}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})\\}$
and $S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$ with
$M^{+}_{R}=\\{m|\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi})\wedge\nexists(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi})\\}$.

###### Proof

Assuming changes to the result set of $n^{\Phi}_{\alpha}$ are cached and
$\mathcal{C}^{\Phi}_{1}$ is available for modification into
$\mathcal{C}^{\Phi}_{2}$, $[\phi:=x]^{\Phi}$ can be executed as follows:

Execution simply iterates over the intermediate results in
$\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that represent newly added matches
compared to $\mathcal{C}^{\Phi}_{0}$ and constructs the corresponding
intermediate results for $[\phi:=x]^{\Phi}$. Each such constructed result is
then added to $\mathcal{C}^{\Phi}_{1}([\phi:=x]^{\Phi})$. Assuming indexing
structures that allow insertion times linear in match size, this takes
$O(S^{+}_{D}+S^{+}_{R})$ steps.

Modifications to $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$ that add no new
matches but only change the marking of already present matches do not affect
the target result set of $[\phi:=x]^{\Phi}$ and can hence be ignored.

This yields the stated complexity.

###### Lemma 20

Let $H$ be a graph, $H_{p}\subseteq H$, $[v]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive vertex input node, and $\mathcal{C}^{\Phi}_{0}$ a
configuration such that $\mathcal{C}^{\Phi}_{0}([v]^{\Phi})=\emptyset$.
Executing $[v]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{1}=execute([v]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{0})$
then takes $O(S^{+}_{R})$ steps, where $S^{+}_{R}=\sum_{m\in M^{+}_{R}}|m|$
with
$M^{+}_{R}=\\{m|\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}([v]^{\Phi})\\}$.

###### Proof

Assuming $\mathcal{C}^{\Phi}_{0}$ is available for modification into
$\mathcal{C}^{\Phi}_{1}$, $[v]^{\Phi}$ can be executed by simply retrieving
the matching vertices from $H_{p}$, constructing the trivial matches, and
adding them to $\mathcal{C}^{\Phi}_{0}([v]^{\Phi})$. Assuming a represnetation
of $H_{p}$ that allows efficient retrieval of the matching vertices and
indexing structures that allow insertion times linear in match size, this
takes $O(S^{+}_{R})$ steps.

###### Lemma 21

Let $H$ be a graph, $H_{p}\subseteq H$, $[v]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive vertex input node, and $\mathcal{C}^{\Phi}_{0}$ a
configuration such that $\mathcal{C}^{\Phi}_{0}([v]^{\Phi})$ is consistent for
$[v]^{\Phi}$. Executing $[v]^{\Phi}$ via
$\mathcal{C}^{\Phi}_{1}=execute([v]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{0})$
then takes $O(1)$ steps.

###### Proof

Assuming $\mathcal{C}^{\Phi}_{0}$ can be reused as $\mathcal{C}^{\Phi}_{1}$,
no changes have to be made to $\mathcal{C}^{\Phi}_{0}$, yielding an execution
time in $O(1)$.

###### Lemma 22

Let $H$ be a graph, $H_{p}\subseteq H$, $[v\rightarrow_{n}w]^{\Phi}\in
V^{N^{\Phi}}$ a forward navigation node with dependency $n^{\Phi}_{v}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[v\rightarrow_{n}w]^{\Phi}$ and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{v}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([v\rightarrow_{n}w]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([v\rightarrow_{n}w]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[v\rightarrow_{n}w]^{\Phi}$, it
must hold that there exists some tuple
$(m_{v},\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{v})$ such that
$m(v)=m_{v}(v)$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{v},\phi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{v})$ such that
$\phi_{0}\leq\phi_{1}$. By the semantics of the forward navigation node, it
then follows that
$(m,\phi_{1})\in\mathcal{C}^{\Phi}_{2}([v\rightarrow_{n}w]^{\Phi})$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v\rightarrow_{n}w]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([v\rightarrow_{n}w]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 23

Let $H$ be a graph, $H_{p}\subseteq H$, $[w\leftarrow_{n}v]^{\Phi}\in
V^{N^{\Phi}}$ a backward navigation node with dependency $n^{\Phi}_{w}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[w\leftarrow_{n}v]^{\Phi}$ and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{w}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([w\leftarrow_{n}v]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([w\leftarrow_{n}v]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[w\leftarrow_{n}v]^{\Phi}$, it
must hold that there exists some tuple
$(m_{w},\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{w})$ such that
$m(v)=m_{w}(w)$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{w},\phi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{w})$ such that
$\phi_{0}\leq\phi_{1}$. By the semantics of the backward navigation node, it
then follows that
$(m,\phi_{1})\in\mathcal{C}^{\Phi}_{2}([w\leftarrow_{n}v]^{\Phi})$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([w\leftarrow_{n}v]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([w\leftarrow_{n}v]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 24

Let $H$ be a graph, $H_{p}\subseteq H$, $[\pi_{Q}]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive projection node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\pi_{Q}]^{\Phi}$ and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([\pi_{Q}]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\pi_{Q}]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\pi_{Q}]^{\Phi}$, it must hold
that there exists some tuple
$(m_{\alpha},\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})$ such that
$m|_{Q}=m_{\alpha}|_{Q}$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{\alpha},\phi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$
such that $\phi_{0}\leq\phi_{1}$. By the semantics of the marking-sensitive
projection node, it then follows that
$(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\pi_{Q}]^{\Phi})$ for some
$\phi_{2}\geq\phi_{1}$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\pi_{Q}]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\pi_{Q}]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 25

Let $H$ be a graph, $H_{p}\subseteq H$, $[\cup]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive union node with a set of dependencies $N^{\Phi}_{\alpha}$,
and $\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such
that $\mathcal{C}^{\Phi}_{0}$ is consistent for $[\cup]^{\Phi}$ and $\forall
n^{\Phi}_{\alpha}\in
N^{\Phi}_{\alpha}:\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([\cup]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\cup]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\cup]^{\Phi}$, it must hold that
$(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})$ for some
$n^{\Phi}_{\alpha}\in N^{\Phi}_{\alpha}$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{\alpha},\phi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$
such that $\phi_{0}\leq\phi_{1}$. By the semantics of the marking-sensitive
union node, it then follows that
$(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\cup]^{\Phi})$ for some
$\phi_{2}\geq\phi_{1}$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\cup]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\cup]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 26

Let $H$ be a graph, $H_{p}\subseteq H$, $[\phi>x]^{\Phi}\in V^{N^{\Phi}}$ a
marking filter node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi>x]^{\Phi}$ and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([\phi>x]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi>x]^{\Phi}$, it must hold
that $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{\alpha},\phi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$
such that $\phi_{0}\leq\phi_{1}$. By the semantics of the marking filter node,
it then follows that $(m,\phi_{1})\in\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi})$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi>x]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi>x]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 27

Let $H$ be a graph, $H_{p}\subseteq H$, $[\phi:=x]^{\Phi}\in V^{N^{\Phi}}$ a
marking assignment node with dependency $n^{\Phi}_{\alpha}$, and
$\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$ configurations such that
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi:=x]^{\Phi}$ and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([\phi:=x]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi:=x]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi:=x]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi:=x]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\phi:=x]^{\Phi}$, it must hold
that $\phi_{0}=x$ and there exists some tuple
$(m,\psi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{\alpha})$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be a
tuple $(m_{\alpha},\psi_{1})$ in $\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{\alpha})$.
By the semantics of the marking assignment node, it then follows that
$(m,x)\in\mathcal{C}^{\Phi}_{2}([\phi:=x]^{\Phi})$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\phi:=x]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\phi:=x]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 28

Let $H$ be a graph, $H_{p}\subseteq H$, $[v]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive vertex input node, and $\mathcal{C}^{\Phi}_{0}$ and
$\mathcal{C}^{\Phi}_{1}$ configurations such that $\mathcal{C}^{\Phi}_{0}$ is
consistent for $[v]^{\Phi}$. It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([v]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([v]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

By the semantics of the marking-sensitive vertex input node and
$\mathcal{C}^{\Phi}_{0}$ being consistent for $[v]^{\Phi}$ and $H$, it follows
that $\mathcal{C}^{\Phi}_{0}([v]^{\Phi})=\mathcal{C}^{\Phi}_{1}([v]^{\Phi})$
and thus
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([v]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([v]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Lemma 29

Let $H$ be a graph, $H_{p}\subseteq H$, $[\bowtie]^{\Phi}\in V^{N^{\Phi}}$ a
marking-sensitive join node with dependencies $n^{\Phi}_{l}$ and
$n^{\Phi}_{r}$, and $\mathcal{C}^{\Phi}_{0}$ and $\mathcal{C}^{\Phi}_{1}$
configurations such that $\mathcal{C}^{\Phi}_{0}$ is consistent for
$[\bowtie]^{\Phi}$,
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{l}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{l}):\phi_{0}\leq\phi_{1}$,
and
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{r}):\exists(m,\phi_{1})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{r}):\phi_{0}\leq\phi_{1}$.
It then holds for the configuration
$\mathcal{C}^{\Phi}_{2}=execute([\bowtie]^{\Phi},N^{\Phi},H,H_{p},\mathcal{C}^{\Phi}_{1})$
that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\bowtie]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\bowtie]^{\Phi}):\phi_{0}\leq\phi_{2}$.

###### Proof

Let $(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\bowtie]^{\Phi})$. Since
$\mathcal{C}^{\Phi}_{0}$ is consistent for $[\bowtie]^{\Phi}$, there must
exist some tuples
$(m_{l},\psi_{0}^{l})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{l})$ and
$(m_{r},\psi_{0}^{r})\in\mathcal{C}^{\Phi}_{0}(n^{\Phi}_{r})$ such that
$m_{l}\cup m_{r}=m$ and $\phi_{0}=max(\psi_{0}^{l},\psi_{0}^{r})$.

By the assumption regarding $\mathcal{C}^{\Phi}_{1}$, there must then be
tuples $(m_{l},\psi_{1}^{l})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{l})$ and
$(m_{r},\psi_{1}^{r})\in\mathcal{C}^{\Phi}_{1}(n^{\Phi}_{r})$ such that
$\psi_{0}^{l}\leq\psi_{1}^{l}$ and $\psi_{0}^{r}\leq\psi_{1}^{r}$. By the
semantics of the marking assignment node, it then follows that
$(m,max(\psi_{1}^{l},\psi_{1}^{r}))\in\mathcal{C}^{\Phi}_{2}([\bowtie]^{\Phi})$,
with $max(\psi_{1}^{l}\psi_{1}^{r})\geq max(\psi_{0}^{l}\psi_{0}^{r})$.

It thus follows that
$\forall(m,\phi_{0})\in\mathcal{C}^{\Phi}_{0}([\bowtie]^{\Phi}):\exists(m,\phi_{2})\in\mathcal{C}^{\Phi}_{2}([\bowtie]^{\Phi}):\phi_{0}\leq\phi_{2}$.


#  _LightPIR_ : Privacy-Preserving Route Discovery
for Payment Channel Networks

Krzysztof Pietrzak‡111This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (682815 - TOCNeT)
<EMAIL_ADDRESS>Iosif Salem§
<EMAIL_ADDRESS>Stefan Schmid§222This project has received funding
from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (864228 - AdjustNet)
<EMAIL_ADDRESS>Michelle Yeo‡
<EMAIL_ADDRESS>‡IST Austria
§Faculty of Computer Science, University of Vienna

###### Abstract

Payment channel networks are a promising approach to improve the scalability
of cryptocurrencies: they allow to perform transactions in a peer-to-peer
fashion, along multi-hop routes in the network, without requiring consensus on
the blockchain. However, during the discovery of cost-efficient routes for the
transaction, critical information may be revealed about the transacting
entities.

This paper initiates the study of privacy-preserving route discovery
mechanisms for payment channel networks. In particular, we present LightPIR,
an approach which allows a source to efficiently discover a shortest path to
its destination without revealing any information about the endpoints of the
transaction. The two main observations which allow for an efficient solution
in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were
developed to preprocess “street network like” graphs so one can later
efficiently compute shortest paths – also work well for the graphs underlying
payment channel networks, and that (2) hub labelling algorithms can be
directly combined with private information retrieval.

LightPIR relies on a simple hub labeling heuristic on top of existing hub
labeling algorithms which leverages the specific topological features of
cryptocurrency networks to further minimize storage and bandwidth overheads.
In a case study considering the Lightning network, we show that our approach
is an order of magnitude more efficient compared to a privacy-preserving
baseline based on using private information retrieval on a database that
stores all pairs shortest paths.

##  1 Introduction

As the popularity of cryptocurrencies is growing explosively, the inefficiency
of the underlying consensus protocol increasingly becomes a bottleneck,
preventing fast payments at scale. A promising solution to this scalability
challenge are emerging payment channel networks [1, 2] such as the Lightning
network [3], which allow to perform transactions off-chain, without requiring
consensus on the blockchain. In a nutshell, a payment channel is a
cryptocurrency transaction which escrows or dedicates money on the blockchain
for exchange with a given user and duration. Users can also interact if they
do not share a direct payment channel: they can route transactions through
intermediaries. To incentivize nodes (the intermediaries) to contribute to the
transaction routing, payment channel networks typically allow intermediaries
to charge nodes which route through them a nominal fee. This is also the
approach taken in the Lightning network which serves us as a case study in
this paper.

Payment channel networks however also introduce new challenges. In particular,
since different routes come at different fees, nodes require scalable
mechanisms to discover “short” (i.e., low-cost) routes. To ensure scalability
and support lightweight nodes (e.g., wallets) in the network, these route
discovery mechanisms must be efficient, both in terms of disk space and
control traffic. Especially since payment channel networks can be more dynamic
compared to classic communication networks (e.g., channels and liquidities can
change over time) [1], it is crucial that resource-constrained nodes do not
have to store and maintain the entire network topology to be able to compute a
route toward the transaction’s target. Thus, over the last years, several
innovative approaches for a more scalable routing in payment channel networks
have been proposed [4, 5, 6, 7, 8, 9]. For example, Lightning introduced the
notion of trampoline nodes [6] to provide route discovery services to light-
weight clients. The trampoline nodes are more powerful nodes which know the
entire topology (e.g., using gossiping); a wallet then just needs to know how
to reach the route server nodes in its neighborhood and can then request the
desired route.

Besides scalability, payment channel networks also need to provide a high
degree of privacy: it is critical that other nodes in the payment channel
networks cannot learn who transacts with whom. In order to provide anonymity
in the transaction routing, payment channel networks typically implement onion
routing [10, 5, 7]. However, while onion routing provides security for the
routing process, it does not provide security for the route _discovery_
process. In particular, by requesting shortest paths to certain destinations
from the route discovery servers (e.g., the trampoline nodes in Lightning), a
node may reveal critical information about its planned financial transactions
[11, 12].

Motivated by this shortcoming of state-of-the-art payment channel networks,
this paper initiates the study of the design of scalable privacy-preserving
route discovery mechanisms for payment channel networks.

The main contribution of this paper is the first scalable and privacy-
preserving route discovery mechanism for payment channel networks,
LightPIR333The name stands for private information retrieval for Lightning-
like networks.. LightPIR provides information theoretic security guarantees,
and is evaluated both analytically as well as empirically, using the Lightning
network. We show that our approach is efficient and practical, and may hence
be useful also in other networks where the security of route discovery is
critical. Concretely, we tested our approach with different snapshots of the
Lightning network taken over a period of two years and our heuristic produces
a small hub database (about 2MB), which at the moment is an improvement by an
order of magnitude compared to the size of the complete network. With the
growth of the network, this discrepancy will change further in favor of
approaches similar to ours.

As a contribution to the research community and to ensure reproducibility, we
will release the code of our implementation together with this paper.

The remainder of this paper is organized as follows. In Section 2 we formally
define the problem we consider. Section 3 presents several alternative
solutions to our problem and highlights the potential drawbacks of each
solution. We then proceed to state our main contributions in Section 4 which
is an efficient solution that combines PIR and hub-labelling to solve our
problem; our solution also relies on a heuristic which optimises the hub set
sizes, to further improve efficiency. Section 5 contains an evaluation of our
method on various snapshots of the Lightning network over a two year period.
In Section 6 we review related work, and finally we discuss future research
directions in Section 7.

##  2 Problem Statement

We model a payment network by a public directed graph $G=(V,E)$, where each
edge $e\in E$ has some cost $c(e)\geq 0$. The nodes are the clients and an
edge $e=(u,v)$ means there’s a channel available from $u$ to $v$ with
transaction cost $c(e)$. We reserve the letters $n=|V|$ to denote the number
of vertices, $m=|E|$ to denote the number of edges, $\delta=|E|/|V|$ to denote
the average degree and $d$ for the edge length of the longest shortest path in
$G$ (if all edge costs are identical this is just the diameter). We assume the
nodes are labelled by $\lambda$-bit strings, while $\lambda=\lceil\log
n\rceil$ is sufficient, we leave this as a parameter as one might want to use
longer labels in practice.

Below we give our definition of a _private route discovery mechanism_. The
definition is very similar to the classic definition of private information
retrieval (PIR): on the one hand, is more restricted as we only consider the
particular problem of retrieving shortest paths; on the other hand it is more
general as the client is not just supposed to recover some database entry, but
can perform a more general computation on the retrieved answers to compute the
path.

###  2.1 Private Route Discovery Mechanism (PRDM) Definition

The involved parties are a content provider ${\cal CP}$, a set of servers
${\cal S}_{1},\ldots,{\cal S}_{k}$ and a client ${\cal C}$.

The content provider ${\cal CP}$ gets as input a graph $G=(V,E)$ and processes
it into $t$ databases ${\sf DB}_{1},\ldots,{\sf DB}_{k}$. ${\sf DB}_{i}$ is
then sent to ${\cal S}_{i}$.

The client ${\cal C}$ on input two nodes $s,t\in V$ can now interact with the
servers and the correctness property we require that ${\cal C}$’s final output
is a shortest path from $s$ to $t$ in $G$ (assuming ${\cal CP}$ and the ${\cal
S}_{i}$’s follow the protocol).

The security guarantee we require is $(\ell,k)$-privacy: the view of any of
the $\ell>0$ out of the $k$ servers should not reveal any information about
the query $s,t$.

We are interested in finding efficient schemes, that is, the scheme has to
scale well with the potential growth of the Lightning network.

##  3 Possible Approaches and Drawbacks

We start by giving a description of several schemes that fulfill both the
correctness property and the security guarantee as described above but have
varying degrees of efficiency. Note that for this problem efficiency can be
defined in terms of several costs, namely, the amount of storage incurred by
the server or the client, the amount of computation involved on the server or
the client sides in order to get the final output, and the amount of data
communicated between the client and the server. The amounts of storage
incurred by the server and the client are most crucial parameters and our main
focus in the following. Another important cost is the amount of computation
the client incurs in order to retrieve the desired shortest path, as client-
side machines are typically not as powerful as server-side machines. We start
with discussing the most naive solutions, gradually augmenting them with
simple strategies to improve their efficiency. To provide a summary of the
efficiency of each method, we present all the relevant asymptotic costs
described above for each method in Table 1.

| Server | Communi– | Server | Client | Client
---|---|---|---|---|---
| storage | cation | computation | computation | storage
Trivial solution | $\mathcal{O}(n\lambda\Delta)$ | $\mathcal{O}(n\lambda\Delta)$ | $\mathcal{O}(1)$ | $\mathcal{O}(m+n\log n)$ | $\mathcal{O}(n\lambda\Delta)$
APSP solution | $\mathcal{O}(n^{2}d\lambda)$ | $\mathcal{O}(n^{2}d\lambda)$ | $\mathcal{O}(n^{3})$ | $\mathcal{O}(1)$ | $\mathcal{O}(n^{2}d\lambda)$
APSP + PIR | $\mathcal{O}(n^{2}d\lambda)$ | $\mathcal{O}(n\sqrt{d\lambda})$ | $\mathcal{O}(n^{3}+n^{2}d\lambda)$ | $\mathcal{O}(n\sqrt{d\lambda})$ | $\mathcal{O}(1)$
APSP + Hub Labelling | $\mathcal{O}(nhd\lambda)$ | $\mathcal{O}(nhd\lambda)$ | $\mathcal{O}(n^{3}+n^{2}\max(d,$ | $\mathcal{O}(h)$ | $\mathcal{O}(nhd\lambda)$
|  |  | $\log n)\log d)$ |  |
Our solution |  |  | $\mathcal{O}(n^{3}+nhd\lambda$ |  |
(APSP + PIR + HL) | $\bm{\mathcal{O}(nhd\lambda)}$ | $\mathcal{O}(\sqrt{nhd\lambda})$ | $+n^{2}\max(d,$ | $\mathcal{O}(h+\sqrt{nhd\lambda})$ | $\mathcal{O}(hd\lambda)$
|  |  | $\log n)\log d)$ |  |
Table 1: Asymptotic server and client side storage, communication, and
computation cost for the trivial solution, the APSP solution, the APSP
solution with a PIR, the APSP solution with Hub Labelling, and our solution
which is the APSP solution with a PIR and Hub Labelling (HL). $n$ is the
number of vertices in the graph, $m$ is the number of edges, $\Delta$ is the
maximum degree of each vertex, $\lambda$ is the length of the binary
representation of each vertex, $d$ is the length of the longest shortest path
in the graph, and $h$ is the maximal hub set size.

###  3.1 Trivial Solution: Downloading Entire Graph

A trivial $(1,1)$-private solution is to simply have the client download the
entire graph and compute the shortest path locally. Although the server does
not need to perform any computation for this solution, the communication from
server to client is significant, i.e., the entire graph of size
$\approx\lambda\cdot n\cdot\delta$, and the client has to perform a non-
trivial computation (e.g., Dijkstra which is $\mathcal{O}(m+n\log n)$) to
retrieve the desired shortest path. In addition, the client also has to store
the entire graph. Taking into account the fact that in most cases clients only
sporadically send small amounts of queries, and also that the underlying
network needs to be frequently updated to account for new users and channels,
it is useful to push the heavy computation and storage burden to the server;
the latter typically runs on machines with superior hardware and storage
capacity.

###  3.2 Server Computes All Pairs Shortest Paths

A natural $(1,1)$-private solution which pushes the burden of computation onto
the server is for the server to precompute and store all the all pair shortest
paths (APSPs). This solution gives a database with $N=n(n-1)\approx n^{2}$
entries (every pair of nodes) with entries of length $L=\lambda\cdot d$, i.e.,
the $\lambda$ bit labels of the $\leq d$ nodes for each path.

Naturally the amount of computation the server would have to do to compute
these APSPs ($\mathcal{O}(n^{3})$) increases compared to the previous trivial
$(1,1)$-private solution where the server does not have to perform any
computation. Nevertheless this factor is not as crucial as the stored database
size ($\mathcal{O}(n^{2}d\lambda)$), which grows quadratically with $n$. Even
for the moderate sized Lightning network with $n\approx 7000$, this gives an
almost $2TB$ database (with $d=9$ and $\lambda=20$ bit labels).

In addition, to maintain privacy, the client cannot simply query the server
for the desired index, as this blatantly reveals the path information. The
client would therefore have to download the entire database from the server to
hide their query. Thus, the price of a constant client-side computation cost
is an additional client-side storage and communication cost of
$\mathcal{O}(n^{2}d\lambda)$ (see Table 1).

###  3.3 Trivial PRDM from Private Information Retrieval (PIR) Using APSPs

In a $(\ell,k)$-private information retrieval (PIR) scheme we have $k$
servers, each holding a copy of a database ${\sf DB}$ which contains $N$
entries, each $L$ bits long. A client ${\cal C}$ who want to learn ${\sf
DB}[i]$ for some $i$, computes queries $q_{i}$ to every ${\cal S}_{i}$, and
then can (efficiently) compute ${\sf DB}[i]$ from the answers
$a_{1},\ldots,a_{k}$. The security property ($\ell$-privacy) requires that any
union of $\ell$ servers cannot learn anything about the query $i$.

The paper introducing PIR [13, Corollary 4.2.1.] has a particularly simple
$(1,2)$-private PIR where the communication complexity is just
$4\max\\{L,\sqrt{N\cdot L}\\}$, in particular, that’s $4L$ if $L\geq N$.444In
this construction we think of ${\sf DB}$ as an $L\times N$ matrix when $L\geq
N$, $q_{1}\in\\{0,1\\}^{N}$ is random and $q_{2}=q_{1}\oplus e_{i}$ where
$e_{i}$ is the zero vector with the $i$th position set to $1$. From the
answers $a_{i}={\sf DB}\cdot q_{i}$ the client computes $a_{1}\oplus
a_{2}={\sf DB}\cdot e_{i}={\sf DB}[i]\ni\\{0,1\\}^{L}$. If $L<N$ one does
almost the same but thinks of ${\sf DB}$ as a $\sqrt{N\cdot
L}\times\sqrt{N\cdot L}$ matrix.

We can get a $(\ell,k)$-private mechanism using a $(\ell,k)$-private
information retrieval on top of the APSP solution. Using a PIR protocol
similar to [13] and assuming that the storage size of each shortest path is
smaller that the total number of entries in the database, i.e.
$d\cdot\lambda<n^{2}$, this solution reduces the communication cost between
the client and servers from $\mathcal{O}(n^{2}d\lambda)$ to
$\mathcal{O}(n\sqrt{d\lambda})$ as shown in Table 1. In addition, the client
now does not need to download and store the database but just has to perform
$\mathcal{O}(n\sqrt{d\lambda})$ XOR operations to get the desired shortest
path so the client-side storage cost is a constant.

From Table 1, we see that this solution incurs a larger asymptotic computation
cost on both the server and client side compared to the vanilla APSP solution.
Specifically, the server has to perform $\mathcal{O}(n^{2}d\lambda)$ XOR
operations upon each query from the client in addition to the initial
$\mathcal{O}(n^{3})$ computations to get the APSPs. These cost increases are
not too alarming as, firstly, server-side computation costs are not as
important as user-side computation and storage costs. More importantly, the
length of the longest shortest path in the Lightning network $d$ is very small
and unlikely to increase much as the network grows due to the centralised
nature of the network (see Section 4.2.1), and we can reasonably assume
$\lambda\ll n$.

The server-side storage requirements of this solution is unfortunately the
same as the vanilla APSP solution and is the main drawback of this approach.
In addition, the PIR protocol requires the servers to perform XOR computations
linear in the size of the entire database in response to every query. Thus it
would be highly beneficial if the database could be kept in memory. As
outlined above, for Lightning that is already not possible with this approach.

###  3.4 Hub Labelling

In a hub labelling scheme [14] one preprocesses a graph such that later, one
can efficiently find shortest paths in-between any two nodes. For some graphs,
in particular street networks, the preprocessed data is _much_ smaller than
storing all pairwise shortest paths.

Concretely, given $G=(V,E)$ the idea is to precompute APSPs. Then compute for
every vertex $v\in V$ a set of hubs $hub(v)\subset V$ such that for all
$u,v\in V$, the shortest path from $u$ to $v$ (if $G$ is directed also from
$v$ to $u$) contains a vertex that lies in the intersection of their hub sets
$hub(u)\cap hub(v)$. This is the _covering property_ of the hub sets.

The preprocessed ${\sf DB}$ now contains, for every $v\in V$ its hub set
$hub(v)$ and for every $u\in hub(v)$ the shortest path from $v$ to $u$ (and
$u$ to $v$).

If $h=\max_{v\in V}\\{|hub(v)|\\}$ is the size of the largest hub, we can
think of the preprocessed data ${\sf DB}$ as a database with $n=|V|$ entries
of length $L=h\cdot\lambda\cdot d$ bits, i.e., for every $v\in V$ we have
$hub(v)\leq h$ paths, each of length $\leq d$, and thus the asymptotic server-
side storage drops from $\mathcal{O}(n^{2}d\lambda)$ to
$\mathcal{O}(nhd\lambda)$. For $h\ll n$, which is the case for the Lightning
network (see Section 5), this allows us to achieve at least an order of
magnitude reduction in server-side storage costs.

Compared to the vanilla APSP solution, adding hub-labelling increases the
asymptotic server-side computation by an additive factor of $n^{2}\max(d,\log
n)\log d$. The increase in computation cost is due to the hitting set
computation for each radius. Nevertheless we note that the increase is not big
as $d\ll n$ in the Lightning network and so the main cost is still the
$\mathcal{O}(n^{3})$ from the APSP computation. In addition, server-side
computation is not as important as server-side storage, and these computations
are also not costs incurred with every query but need only to be be done
relatively infrequently, for instance every two weeks or so to take into
account changes in the underlying network topology.

The main drawback of this solution is that the client needs to download the
entire database to maintain the security guarantee. This would incur an
asymptotic storage cost of $\mathcal{O}(nhd\lambda)$ which is problematic as
client-side machines have less storage capacity compared to server-side
machines.

##  4 The LightPIR Approach

Figure 1: A plot showing the number of nodes for each degree in the largest
strongly component (scc) of the Lightning network on January 2021. The
distribution of degrees is quite similar in Lightning network snapshots taken
in dates within the past two years.

Given the above considerations, we are now ready to present our proposed
solution, LightPIR.

###  4.1 Basic Approach

In a nutshell, our construction of a private route discovery mechanism
augments the basic APSP solution with both a PIR protocol (specifically a
2-server RAID-PIR protocol [15] which is similar in flavour to [13]) and hub
labelling. A client who wants to learn the shortest path from $u$ to $v$ will
query the PIR servers for the $u,v$ entries, which will be the hub sets of $u$
and $v$ respectively. Then, the client should perform a set intersection of
the two hub sets, which will be non-empty by the covering property of these
hubs, and determine the $w\in hub(u)\cap hub(v)$ for which the length of the
path $u\rightarrow w$ plus the length of $w\rightarrow v$ is minimized. The
path $u\rightarrow w\rightarrow v$ is the sought shortest path from $u$ to
$v$.

LightPIR reaps the benefit of a lower asymptotic storage cost of
$\mathcal{O}(nhd\lambda)$ from hub labelling and a lower asymptotic
communication cost of $\mathcal{O}(\sqrt{nhd\lambda})$ from the 2-server PIR
protocol. The composition of these two techniques also lowers the per query
asymptotic server-side computation due to the PIR protocol from
$\mathcal{O}(n^{2}d\lambda)$ XOR operations to $\mathcal{O}(nhd\lambda)$.
Compared to the vanilla APSP solution, the user now has to perform some
computation to determine the desired shortest path. This computation is
extremely simple, basically $\mathcal{O}(\sqrt{nhd\lambda})$ XOR operations to
privately recover the query result from the servers and a set intersection on
two moderately sized sets of at most $h\ll n$ to get the shortest path, and
thus can be performed by even the weakest clients. Finally we note that
although the asymptotic server and user side computation costs is higher in
our solution compared to the APSP solution with hub labelling, the asymptotic
storage incurred by the user drops from $\mathcal{O}(nhd\lambda)$ to
$\mathcal{O}(hd\lambda)$ since the user just has to store the hub sets of the
desired source and target nodes instead of all the hub sets of all nodes.
Again, since $h\ll n$ in the case of the Lightning network, this is at least
an order of magnitude drop in client-side storage requirements.

###  4.2 Optimization of Hub Sets

In order to lower the database storage further, LightPIR relies on a heuristic
which leverages the specific topology of the Lightning network to optimize the
size of hub sets. We first begin with a brief description of the Lightning
network topology and then describe the heuristic.

####  4.2.1 Network Topology Characteristics

To understand and exploit the specific topological characteristics of payment
channel networks, we downloaded a number of historical snapshots of the
Lightning network from the Lightning github repositories [16, 17]. For
instance, a representative network snapshot on January 2021 comprises of 6,376
nodes, 39,993 channels, and 3,650 strongly connected components, although
except for the largest one, almost all of the rest components have only a very
small number of nodes. We thus focus our analysis on the largest connected
component of each snapshot. The one of January 2021 has 2,707 nodes and
comprises a majority (31,350) of the total number of channels.

As can be seen from Figure 1, the majority of the nodes in the largest
component of the Lightning network have very low degrees and about 100 nodes
have degrees of $>100$. The largest component also has a relatively small
diameter of 9. We can therefore infer a large degree of centralisation in the
Lightning network, with a few central nodes of high degree connected to each
other as well as connected to shorter chains of vertices (see Figure 2a).

A channel (i.e. an edge) between two nodes in the network is weighted by its
channel fee. This usually comprises of a base fee which is independent of the
amount one wishes to move through the channel, and an amount-specific rate fee
which depends on the amount sent across the channel. Table 2 (Section 5)
includes a number of network characteristics for a number of snapshots of the
Lightning network over the past two years.

(a) Figure 2a

(b) Figure 2b

Figure 2: Figure 2a shows a graph created from star graphs where the centers
of the graphs form a clique. A few paths of length in $[r+1,2r]$ for $r=2$
with a (red) cover point on each path are shown. A ball (neighborhood) of
radius $2r=4$ is shown, and it contains a substantial fraction of the graph,
and thus the cover points. Figure 2b shows a street network with 4 shortest
paths of length in $(r,2r]$ (for $r\approx 500m$) and a cover point of those
paths (in red) highlighted. A ball (neighborhood) with radius 2r (one with
center at the starting point of a path shown in purple) will only contain
cover points resulting from relatively few paths “in the neighbourhood”.

####  4.2.2 Hub Set Computation: Greedy Heuristic

Input: $G=(V,E)$, the network topology and $\ell$, the number of high degree
nodes to use as base

1

Output: $\overline{\mathcal{HD}}(G)$ (bound on $\mathcal{HD}(G)$) and
$hubs(u),\,\forall u\in V$

2

3$APSP\leftarrow allPairsShortestPaths(G)$;

4

5$radii\leftarrow\\{2^{i}\,|\,i\in\mathbb{N}\land 2^{i}\leq diameter(G)\\}$;

6

7$base\leftarrow highDegreeNodes[0:\ell-1]$;

8

/* compute shortest path sets */

for $r\in radii$ do $shortestPaths(r)\leftarrow\emptyset$;

/* init */

9 for  _$path\in APSP$_ do

10 for  _$r\in radii$_ do

11 if  _$r <|path|\leq 2r\land base\cap path=\emptyset$_ then

12 $shortestPaths(r).add(path)$;

13

14

15

16

/* compute hitting sets and covers */

17 for  _$r\in radii$_ do

18 $cover[r]\leftarrow base\cup hittingSet(shortestPaths(r))$;

19

/* compute $N_{2r}^{\overline{G}}(u)\cap cover[r]$ sizes & hubs */

20 $\overline{G}\leftarrow G\setminus base$;

for $u\in V$ do $hubs(u)\leftarrow\emptyset$;

/* init $hubs$ */

21 for  _$(u,r):u\in V\land r\in radii$_ do

22 $hubs\\_in\\_neighb(u,r)\leftarrow base\cup(N_{2r}^{\overline{G}}(u)\cap
cover[r])$;

23 $hubs(u)\leftarrow hubs(u)\cup(hubs\\_in\\_neighb(u,r))$;

24

25

26$\overline{\mathcal{HD}}(G)=\max_{u,r}|hubs\\_in\\_neighb(u,r)|$;

Algorithm 1 LightPIR’s hub set optimization

One way of computing the hubs for each node in the network is to make use of
the highway dimension (HD) algorithm [18, 19]. Intuitively, HD is a graph
metric that captures the size of a subset of nodes that intersects all
shortest paths of non-trivial length. In order to compute the HD, we compute
sets of nodes that intersect all paths of size $(r,2r]$ for a small set of
radii and measure how sparse these sets are in the network. In the following,
we explain how we use these sets to compute the hubs for each network node
(Algorithm 1).

In [18], the authors give a definition of HD based on shortest-path covers and
also give an approximation algorithm to compute the HD of a network using this
definition. In [19], the authors present a modification that improves their
earlier work, which also applies to the shortest-path covers algorithm. We
further modify this approximation algorithm with a heuristic from observing
the topology of the Lightning network, as shown in Algorithm 1, to both return
a hub set for each node in the network, and also maintain an upper bound on
the HD of the network. That is, we always overapproximate the HD but never
underapproximate it.

We present a few necessary ingredients from [19, Section 4], before
elaborating on our heuristic. Let $G=(V,E)$ be the network topology. The
neighborhood $N_{x}(u)$ of a node $u\in V$ for a radius $x$ is the set of all
nodes that appear in a path $P$, such that $v\in P$ and $|P|\leq x$, where
$|P|$ denotes the length of the path $P$ ($N_{x}(v)$ contains the same number
of nodes as the ball with center $u$ and radius $x$). Moreover, a set $C$ of
nodes is a $(k,r)$-shortest path cover ($(k,r)$-SPC) of $G$ if and only if (I)
for each shortest path $P$, such that $r<|P|\leq 2r$, $P\cap C\neq\emptyset$
and (II) $\forall u\in V$, $|C\cap N_{2r}(u)|\leq k$. Then, if $G$ has HD $h$,
then for any $r>0$ there exists an $(h,r)$-SPC of $G$. Thus, the authors claim
that by using the greedy $\mathcal{O}(\log n)$ approximation for computing
hitting sets, we can combine the above into an algorithm that computes a bound
of HD in $\mathcal{O}(h\log n)$, where $h=\mathcal{HD}(G)$ is the highway
dimension of $G$. Specifically, given a hitting set $cover[r]$ of all pairs
shortest paths of length in $(r,2r]$, they make sure that condition I holds
and then they can fulfill Condition II by taking all $cover[r]\cap N_{2r}(v)$
intersections for all $v\in V$ and setting $k$ to be the maximum size of those
intersections. As mentioned in [14], it suffices to compute the above with the
set of radii $r\in\\{2^{i}\,|\,i\in\mathbb{N}\land 2^{i}\leq diameter(G)\\}$.
Of course, an exact hitting set algorithm would give a smaller $cover[r]$, but
computing it is NP-hard.

Our heuristic is based on the key observation that, due to the centralised
nature of the network, high degree nodes in the Lightning network appear in a
vast majority of shortest paths, as opposed to the less dense and centralised
road networks for which HD was originally designed (Figure 2b). Thus many
neighborhoods for center $u$ and radius $2r$ include these high degree nodes,
which work as gateways to many remote nodes. We denote by $base(\ell)$ the set
of the $\ell$ nodes with the highest degree (in short, $base$). We noticed
that for network topologies similar to the one of Lightning removing the base
nodes after computing the covers can significantly reduce the HD (Figure 2a).
Specifically, we adapt the HD computation by first computing the cover sets as
in [18, 19], but then removing the base nodes and all the edges connected to
the base nodes to obtain the topology $\overline{G}=G\setminus base$, in which
we compute the per-node hubs as follows. That is the hub set of node $u$ for
radius $2r$ is defined by
$hubs\\_in\\_neighb(u,r)=base\cup(N^{\overline{G}}_{2r}(u)\cap cover[r])$,
where $N^{\overline{G}}_{2r}(u)$ is the neighborhood $N_{2r}(u)$ computed in
$\overline{G}$. Note that [19] (in addition to [18]) requires that the path
weights are unique integers, but this is easily achieved with insignificant
perturbations of edge weights (in our case we initially set the weights to be
the channel base fees and then perturbed them). We illustrate this heuristic
in Algorithm 1 and show that it correctly computes an upper bound
$\overline{\mathcal{HD}}(G)$ of $\mathcal{HD}(G)$ in Lemma 1.

######  Lemma 1.

Algorithm 1 computes an upper bound of $\mathcal{HD}(G)$.

###### Proof.

We prove that for any two communicating nodes $s$ and $d$, there exists a hub
node in the set of hubs that lies on the shortest path between $s$ and $d$,
$SP(s,d)$. Let $|SP(s,d)|=k$ and let $r$ be the radius for which $r<k\leq 2r$
(there has to be at least one such radius as our set of radii covers all
shortest paths). If $SP(s,d)\subset N_{2r}^{\overline{G}}(s)$, i.e. if
$SP(s,d)$ entirely appears in the neighborhood with center $s$ and radius $2r$
in the resulting topology after removing $base$ from $G$, then the hub for $s$
and $d$ is in $SP(s,d)\cap cover[r]$, as $cover[r]$ hits all shortest paths of
length in $(r,2r]$. Otherwise, if $SP(s,d)$ does not entirely appear in
$N_{2r}^{\overline{G}}(s)$, then there exist at least one node in $base$ that
intersects $SP(s,d)$. Since $base$ is included in the set of hubs (Algorithm
1, line 1), then the proof is complete. ∎

Note that from the proof of Lemma 1, we guarantee the covering property and
hence correctness of the hub sets: the hub set of any node covers all shortest
paths from that node to any other node in the network. This means that any two
hub sets in a connected network must certainly have a non-empty intersection.

The time complexity of Algorithm 1 is computed as follows. The APSP step takes
$\mathcal{O}(n^{3})$ and the partitioning of APSP according to their length
takes $\mathcal{O}(n^{2}\log d)$. The computation of covers, which includes
the computation of hitting sets (greedy heuristic costs
$\mathcal{O}(n^{2}\max(d,\log n))$), takes $\mathcal{O}((n^{2}\max(d,\log
n))\cdot\log d)$ and the hub computation takes $\mathcal{O}(n\log d)$. Thus,
in total $\mathcal{O}(n^{3}+n^{2}\log d+(n^{2}\max(d,\log n))\log d+n\log
d)=\mathcal{O}(n^{3}+n^{2}\max(d,\log n)\log d)$ (cf. Table 1). In practice,
the diameters of the Lightning network snapshots that we used to test
Algorithm 1 were quite small, thus the running time was dominated by the APSP
computation (which was a matter of minutes).

##  5 Empirical Evaluation

Table 2: Lightning Network Snapshot Characteristics and Evaluation Results (scc stands for strongly connected component(s), $V$ for the set of nodes, $E$ for the set of channels, and $D$ for the diameter) |  |  |  | largest scc
---|---|---|---|---
date | $|V|$ | $|E|$ | scc |  |  |  | baseline | heuristic | base | max | hub DB | exec.
|  |  |  | $|V|$ | $|E|$ | $D$ | HD | HD | size | hub set | size | time
|  |  |  |  |  |  | bound | bound |  | size | (MB) | (h)
13-03-2019 | 3480 | 45071 | 994 | 2480 | 42025 | 7 | 386 | 209 | 100 | 271 | 1.5 | 2.03
13-07-2019 | 4469 | 53084 | 1804 | 2661 | 46733 | 7 | 312 | 191 | 100 | 248 | 1.4 | 1.41
13-09-2019 | 4733 | 51508 | 2027 | 2706 | 45774 | 7 | 389 | 228 | 100 | 304 | 2.1 | 2.64
13-11-2019 | 4598 | 44784 | 2158 | 2422 | 38011 | 6 | 306 | 186 | 110 | 235 | 1.2 | 1.31
13-03-2020 | 5070 | 48340 | 2356 | 2712 | 41571 | 6 | 368 | 212 | 100 | 270 | 1.7 | 2.67
13-05-2020 | 5557 | 49569 | 2570 | 2985 | 42093 | 8 | 347 | 196 | 100 | 257 | 1.6 | 1.98
13-07-2020 | 5888 | 51932 | 2748 | 3136 | 44005 | 7 | 361 | 211 | 100 | 286 | 1.8 | 2.27
13-09-2020 | 5972 | 51783 | 2800 | 3171 | 43844 | 7 | 373 | 220 | 112 | 285 | 1.8 | 2.47
13-11-2020 | 6074 | 48361 | 2978 | 3089 | 40695 | 8 | 419 | 253 | 103 | 315 | 2.3 | 2.96
13-01-2021 | 6376 | 39993 | 3650 | 2707 | 31350 | 9 | 422 | 259 | 106 | 314 | 1.8 | 1.83

To provide a first empirical evaluation of our approach, we implemented
LightPIR (the code will be released together with this paper) and ran
experiments on historical snapshots of the Lightning network from the
Lightning network gossip repository [17]. In general, we find that our
approach indeed achieves an improvement by an order of magnitude in terms of
storage requirements and a roughly 40% reduction in the highway dimension of
each snapshot, which directly translates to a reduced hubs database.

##### Setup

In our experiments, we used a virtual machine with 24 cores (Intel Xeon CPUs
E5-2650 v4 at 2.20GHz) and 16 GB RAM, running Ubuntu 18.04.1 LTS. Our
experiments were implemented in Python (version 3.7.6) using networkx [20]
among other libraries.

##### Data

The extracted snapshots range from March 2019 to the current state (January
2021) with the smallest snapshot having 3,480 nodes and the largest having
6,376 nodes. We ignore earlier snapshots as they have too few nodes. We
performed our empirical evaluation on the largest strongly connected component
(SCC) in the snapshot and we found that although the network size almost
doubles from March 2019 to January 2021, the number of nodes in the largest
SCC remains pretty consistent across all snapshots ($\approx 2500$ nodes). The
first seven columns of Table 2 give a complete view of the datasets used.

Figure 3: The x-axis shows the different base set sizes tested (a base with
size $\ell$ includes the $\ell$ nodes with the highest degree) and the y-axis
shows the corresponding highway dimension bound. The baseline computation
corresponds to the values for base size 0, which are the highest. We run our
heuristic with the base size that minimizes the highway dimension bound (thus
also the hub database) and reported the results in Table 2. Figure 4: Box
plots of hub sizes (in number of nodes) for a number of snapshots of the
Lightning network. The green line shows the second quartile (median), the
bottom and top of each box show the first and third quartiles, respectively,
and the extended lines out of each box (whiskers) end at the min (bottom) and
max (top) values of the datasets.

##### Results

We computed the optimal base size for the largest SCC in each snapshot by
running a binary search to find the size of the base set that minimises the
approximate highway dimension of the SCC as computed by our algorithm ($\ell$
in Algorithm 1’s input). The baseline algorithm of [18, 19] is the one where
$\ell=0$, i.e., there the base set is empty. As shown in Figure 3, for most
Lightning network snapshots a base size of around $100$ nodes minimises the
approximate highway dimension of the largest SCC. In fact, the reduction in
highway dimension is around 40$\%$ across all snapshots when compared to the
baseline (see Table 2 baseline HD bound vs heuristic HD bound).

Across all snapshots the median hub set size as computed by our algorithm is
between 150 to 200 nodes, with the maximum hub set size being 315 nodes. The
distribution of hub sizes for each snapshot is shown in Figure 4. Given that
the average size for storing each snapshot is about 13MB, our method provides
an overall reduction of an order of magnitude in terms of the hub set sizes
(cf. second last column of Table 2). Due to the inclusion of the base, the
minimum hub set size is at least 100. Specifically, as shown in Table 2, the
average database size across all snapshots is 1.65MB.

The running time for each snapshot is about two hours (last column of Table
2). This includes the search for the base size that minimizes the HD (and thus
the hubs database). Thus, it is possible to run our algorithm periodically to
update the hub sets as the lightning network topology changes.

##  6 Related Work and Novelty

While the security of blockchains, e.g., related to the underlying consensus
protocols [21, 22] but also related to the interconnecting network [23], has
been extensively investigated, much less is known about the security of the
recent concept of payment channel networks. The security aspects of payment
channel networks considered so far mainly revolve around connectivity [24] and
the multi-hop routing of payments [9, 25, 12]. We refer the reader to the
surveys [26, 2] for an overview of specific threats related to hot wallets,
mass exits, synchronizing protocols, among others.

Prior work on route discovery primarily focused on efficiency. For example,
SpeedyMurmurs [5] (which extends VOUTE [27]) and SilentWhispers [7] rely on
clever protocols to speed up route discovery by two orders of magnitude, while
maintaining the same success ratio. Another interesting approach is pursued in
the SpiderNetwork [8]: the payments are split into units and the route
discovery algorithm routes each of them individually (similarly to a packet-
switched network). This method however also does not account for privacy and
cost effectiveness. To trade off high throughput and probing overhead Flash
[28] distinguishes between mice and elephant payments, splitting elephant
flows across multiple flows. Flare [4] proposes to improve scalability of
route discovery by determining beacon nodes, an approach which also motivates
our model in this paper. To overcome the cost overheads of multi-hop routing,
thee off-chain channel network Perun [29] introduces a notion of virtual
payment channels; while this allows to avoid intermediaries for each payment,
it does not solve the discovery problem.

Private route discovery on street networks has been explored in [30]. Their
work is similar to ours in that they also use a PIR protocol to privately
retrieve shortest path entries in a database. The main difference is the
database compression technique: in [30] the authors develop a compression
algorithm specific to the grid-like structure of street networks in North
America (i.e. each node has degree 4 corresponding to the 4 cardinal
directions), whereas we use hub labelling which has good compression
guarantees on generic networks and we develop an additional heuristic based on
the topology of the Lightning network to get small hubs set sizes.

Our work is motivated by recent empirical work demonstrating issues with
confidentiality during the route discovery process in the Lightning network
[11, 12]. To the best of our knowledge, the only work suggesting a more secure
route discovery mechanism is MAPPCN [31], which however does not account of
the information leaking problem addressed in this paper.

Our paper also builds upon classic works on efficient shortest path
computations on extremely large networks [32, 33, 34]. Of particular interest
in our context are algorithms based on transit node routing (TNR) [35], which
focus on networks in which a small set of vertices covers most shortest paths,
i.e., networks with small so-called highway dimension. Recently, Abraham et
al. [18, 19] proved theoretical guarantees on the efficiency of common
shortest path search algorithms for graphs which satisfy this property. The
hub-labelling algorithm [14, 36] is a variant of TNR and it was shown to be
significantly faster compared to other state of the art shortest path
algorithms when tested on real world road networks [14]. In this paper, we
build upon this approach to scalable routing, tailoring it to the specific
topological properties of payment channel networks.

Information theoretic PIR protocols were first introduced by Chor et al. [13].
With 2 servers and a simple linear bit summation scheme, they achieve perfect
privacy with a communication complexity of $\mathcal{O}(n^{1/3})$. Since then,
follow up work in this area has mainly focused on lowering the communication
complexity [37, 38, 39, 40, 15]. Recently, Beimel et al. [41] achieved a
communication complexity of $n^{\mathcal{O}(\frac{\log\log k}{k\log k})}$ with
$k$ servers using locally decodable codes. Under the conjecture that there are
infinitely many Mersenne primes, Yekhanin [42] removed the dependency on large
$k$ in the communication complexity bound and achieved a communication
complexity of $n^{\mathcal{O}(\frac{1}{\log\log n})}$ for a 3 server PIR
protocol. Although these newer protocols achieve a much lower communication
complexity compared to the original protocol, the techniques used in these
protocols are also much more complicated. As these benefits from a lower
communication complexity are not that pertinent to us, we focus on simpler PIR
protocols which are similar to [13] in this paper.

PIR protocols have already been successfully deployed in many contexts, such
as DNS [43], private presence service [44], and private retrieval of security
updates [45]. However, we are not aware of any applications of PIRs in the
context of payment channel networks.

##  7 Future Work

We understand our work as a first step and would like to highlight three
interesting directions of future work.

Firstly, when shortest paths are not unique, most available algorithms for
selecting a shortest path out of a set of paths of equal length just select a
random one from the set. In terms of reducing the size of the hub set, one can
design smarter algorithms that do not select the path randomly, but optimise
for paths with a larger vertex overlap with the set of other paths already
selected. This ensures that when we greedily select vertices to be in the hub
set, we would select vertices that cover a larger set of paths and so could
potentially decrease the size of the hub set.

Secondly, our current heuristics to calculate the highway dimension of the
network and to reduce the size of the hub sets are heavily inspired by the
topology of the Lightning network. It would be interesting to track the
topology of the Lightning network as the network grows in size, to see if
there are significant changes and to think about how to incorporate these
changes in the network topology to further optimise the hub set sizes.

Lastly, we note that the network topology and thus the hub sets change with
the amount of Bitcoins a user wants to send, e.g., due to the capacity
limitation of channels in the network (i.e. the amount of Bitcoins each
channel can forward). For instance the shortest path from Alice to Bob might
go through Charlie when Alice wants to send 1 Btc but the path might have to
go through Dave when Alice wants to send 10 Btc because Charlie cannot forward
more than 1 Btc. Additionally, the topology could also change due to the way
the fees are calculated. The fees on channels comprise of a base fee and a
rate fee which depends on the amount sent over the channel and thus the
shortest path information could change drastically between sending small or
large amounts of Bitcoin. Since we do not yet take into account fees, our
current work can be seen as optimised for sending a fixed amount of Bitcoin
and thus an interesting future direction would be to take into account the
amount of Bitcoins a user wants to send and design a similarly efficient and
private method of extracting shortest paths.

## References

  * [1] L. Gudgeon, P. Moreno-Sanchez, S. Roos, P. McCorry, and A. Gervais, “Sok: Off the chain transactions.” _IACR Cryptol. ePrint Arch._ , vol. 2019, p. 360, 2019.
  * [2] M. Dotan, Y.-A. Pignolet, S. Schmid, S. Tochner, and A. Zohar., “Survey on blockchain networking: Context, state-of-the-art, challenges,” in _Proc. ACM Computing Surveys (CSUR)_ , 2021.
  * [3] J. Poon and T. Dryja, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016.
  * [4] P. Prihodko, S. Zhigulin, M. Sahno, A. Ostrovskiy, and O. Osuntokun, “Flare: An approach to routing in lightning network,” _White Paper_ , 2016.
  * [5] S. Roos, P. Moreno-Sanchez, A. Kate, and I. Goldberg, “Settling payments fast and private: Efficient decentralized routing for path-based transactions,” _arXiv preprint arXiv:1709.05748_ , 2017.
  * [6] B. Weekly, “Outsourcing route computation with trampoline payments,” in _https://bitcointechweekly.com/front/outsourcing-route-computation-with-trampoline-payments/_ , 2019\.
  * [7] G. Malavolta, P. Moreno-Sanchez, A. Kate, and M. Maffei, “Silentwhispers: Enforcing security and privacy in decentralized credit networks.” in _NDSS_ , 2017.
  * [8] V. Sivaraman, S. B. Venkatakrishnan, M. Alizadeh, G. Fanti, and P. Viswanath, “Routing cryptocurrency with the spider network,” in _Proceedings of the 17th ACM Workshop on Hot Topics in Networks_ , 2018, pp. 29–35.
  * [9] S. Tochner, A. Zohar, and S. Schmid, “Route hijacking and dos in off-chain networks,” in _Proc. ACM Conference on Advances in Financial Technologies (AFT)_ , 2020.
  * [10] R. Dingledine, N. Mathewson, and P. Syverson, “Tor: The second-generation onion router,” Naval Research Lab Washington DC, Tech. Rep., 2004.
  * [11] S. Tochner and S. Schmid, “On search friction of route discovery in offchain networks,” in _Proc. IEEE International Conference on Blockchain (Blockchain)_ , 2020.
  * [12] U. Nisslmueller, K.-T. Foerster, S. Schmid, and C. Decker, “Toward active and passive confidentiality attacks on cryptocurrency off-chain networks,” in _Proc. 6th International Conference on Information Systems Security and Privacy (ICISSP)_ , 2020.
  * [13] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private information retrieval,” _J. ACM_ , vol. 45, no. 6, pp. 965–981, 1998. [Online]. Available: https://doi.org/10.1145/293347.293350
  * [14] I. Abraham, D. Delling, A. Goldberg, and R. Werneck, “A hub-based labeling algorithm for shortest paths in road networks,” 01 2011, pp. 230–241.
  * [15] D. Demmler, A. Herzberg, and T. Schneider, “RAID-PIR: practical multi-server PIR,” in _Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, CCSW ’14, Scottsdale, Arizona, USA, November 7, 2014_ , G. Ahn, A. Oprea, and R. Safavi-Naini, Eds. ACM, 2014, pp. 45–56. [Online]. Available: https://doi.org/10.1145/2664168.2664181
  * [16] “Lightning network daemon,” https://github.com/lightningnetwork/lnd.
  * [17] C. Decker, “Lightning network research; topology, datasets,” https://github.com/lnresearch/topology, accessed: 2020-10-01.
  * [18] I. Abraham, A. Fiat, A. Goldberg, and R. Werneck, “Highway dimension, shortest paths, and provably efficient algorithms,” in _Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)_. Society for Industrial and Applied Mathematics, January 2010. [Online]. Available: https://www.microsoft.com/en-us/research/publication/highway-dimension-shortest-paths-and-provably-efficient-algorithms/
  * [19] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, “Vc-dimension and shortest path algorithms,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2011, pp. 690–699.
  * [20] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” in _Proceedings of the 7th Python in Science Conference_ , G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15.
  * [21] A. Gervais, G. O. Karame, K. Wüst, V. Glykantzis, H. Ritzdorf, and S. Capkun, “On the security and performance of proof of work blockchains,” in _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016, pp. 3–16.
  * [22] K. Wüst and A. Gervais, “Ethereum eclipse attacks,” ETH Zurich, Tech. Rep., 2016.
  * [23] A. Gervais, H. Ritzdorf, G. O. Karame, and S. Capkun, “Tampering with the delivery of blocks and transactions in bitcoin,” in _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ , 2015, pp. 692–705.
  * [24] E. Rohrer, J. Malliaris, and F. Tschorsch, “Discharged payment channels: Quantifying the lightning network’s resilience to topology-based attacks,” in _2019 IEEE European Symposium on Security and Privacy Workshops (EuroS &PW)_. IEEE, 2019, pp. 347–356.
  * [25] G. Malavolta, P. Moreno-Sanchez, A. Kate, M. Maffei, and S. Ravi, “Concurrency and privacy with payment-channel networks,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 455–471.
  * [26] L. Gudgeon, P. Moreno-Sanchez, S. Roos, P. McCorry, and A. Gervais, “Sok: Layer-two blockchain protocols,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2020, pp. 201–226.
  * [27] S. Roos, M. Beck, and T. Strufe, “Voute-virtual overlays using tree embeddings,” _arXiv preprint arXiv:1601.06119_ , 2016.
  * [28] P. Wang, H. Xu, X. Jin, and T. Wang, “Flash: efficient dynamic routing for offchain networks,” in _Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies_ , 2019, pp. 370–381.
  * [29] S. Dziembowski, L. Eckey, S. Faust, and D. Malinowski, “Perun: Virtual payment hubs over cryptocurrencies,” in _2019 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2019, pp. 106–123.
  * [30] D. J. Wu, J. Zimmerman, J. Planul, and J. C. Mitchell, “Privacy-preserving shortest path computation,” _CoRR_ , vol. abs/1601.02281, 2016. [Online]. Available: http://arxiv.org/abs/1601.02281
  * [31] S. Tripathy and S. K. Mohanty, “Mappcn: Multi-hop anonymous and privacy-preserving payment channel network,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2020, pp. 481–495.
  * [32] A. V. Goldberg and C. Harrelson, “Computing the shortest path: _A_ search meets graph theory,” in _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005_. SIAM, 2005, pp. 156–165. [Online]. Available: http://dl.acm.org/citation.cfm?id=1070432.1070455
  * [33] U. Lauther, “An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags,” in _The Shortest Path Problem, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 13-14, 2006_ , ser. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Eds., vol. 74. DIMACS/AMS, 2006, pp. 19–39. [Online]. Available: https://doi.org/10.1090/dimacs/074/02
  * [34] R. J. Gutman, “Reach-based routing: A new approach to shortest path algorithms optimized for road networks,” in _Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, January 10, 2004_ , L. Arge, G. F. Italiano, and R. Sedgewick, Eds. SIAM, 2004, pp. 100–111.
  * [35] H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes, “In transit to constant time shortest-path queries in road networks,” in _Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007_. SIAM, 2007. [Online]. Available: https://doi.org/10.1137/1.9781611972870.5
  * [36] I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck, “Hierarchical hub labelings for shortest paths,” in _Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings_ , ser. Lecture Notes in Computer Science, L. Epstein and P. Ferragina, Eds., vol. 7501. Springer, 2012, pp. 24–35. [Online]. Available: https://doi.org/10.1007/978-3-642-33090-2_4
  * [37] A. Beimel and Y. Ishai, “Information-theoretic private information retrieval: A unified construction,” in _In Proceedings of 28th ICALP_ , 2001, pp. 912–926.
  * [38] A. Beimel, Y. Ishai, E. Kushilevitz, and J. Raymond, “Breaking the o(n1/(2k-1)) barrier for information-theoretic private information retrieval,” in _43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings_. IEEE Computer Society, 2002, pp. 261–270. [Online]. Available: https://doi.org/10.1109/SFCS.2002.1181949
  * [39] Z. Dvir and S. Gopi, “2-server pir with subpolynomial communication,” _Journal of the ACM (JACM)_ , vol. 63, no. 4, pp. 1–15, 2016.
  * [40] K. Efremenko, “3-query locally decodable codes of subexponential length,” _SIAM J. Comput._ , vol. 41, no. 6, pp. 1694–1703, 2012. [Online]. Available: https://doi.org/10.1137/090772721
  * [41] A. Beimel, Y. Ishai, E. Kushilevitz, and J. Raymond, “Breaking the o(n/sup 1/(2k-1)/) barrier for information-theoretic private information retrieval,” _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002\. Proceedings._ , pp. 261–270, 2002.
  * [42] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” _J. ACM_ , vol. 55, no. 1, Feb. 2008. [Online]. Available: https://doi.org/10.1145/1326554.1326555
  * [43] F. Zhao, Y. Hori, and K. Sakurai, “Two-servers PIR based DNS query scheme with privacy-preserving,” in _The 2007 International Conference on Intelligent Pervasive Computing, IPC 2007, Jeju Island, Korea, 11-13 October 2007_. IEEE Computer Society, 2007, pp. 299–302. [Online]. Available: https://doi.org/10.1109/IPC.2007.27
  * [44] N. Borisov, G. Danezis, and I. Goldberg, “Dp5: A private presence service,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2015, pp. 24 – 4, 2015\.
  * [45] J. Cappos, “Avoiding theoretical optimality to efficiently and privately retrieve security updates,” vol. 7859, 04 2013, pp. 386–394.