  Payment channel networks (PCNs) are among the most promising solutions to the
scalability issues in permissionless blockchains, by allowing parties to pay
each other off-chain through a path of payment channels (PCs). However, routing
transactions comes at a cost which is proportional to the number of
intermediaries, since each charges a fee for the routing service. Furthermore,
analogous to other networks, malicious intermediaries in the payment path can
lead to security and privacy threats. Virtual channels (VCs), i.e., bridges
over PC paths, mitigate the above PCN issues, as an intermediary participates
only once to set up the VC and is then excluded from every future VC
transaction. However, similar to PCs, creating a VC has a cost that must be
paid out of the bridged PCs' balance. Currently, we are missing guidelines to
where and how many VCs to set up. Ideally, VCs should minimize transaction
costs while mitigating security and privacy threats from on-path adversaries.
  In this work, we address for the first time the VC setup problem, formalizing
it as an optimization problem. We present an integer linear program (ILP) to
compute the globally optimal VC setup strategy in terms of transaction costs,
security, and privacy. We then accompany the computationally heavy ILP with a
fast local greedy algorithm. Our model and algorithms can be used with any
on-path adversary, given that its strategy can be expressed as a set of
corrupted nodes that is estimated by the honest nodes. We conduct an evaluation
of the greedy algorithm over a snapshot of the Lightning Network (LN), the
largest Bitcoin-based PCN. Our results confirm on real-world data that our
greedy strategy minimizes costs while protecting against security and privacy
threats of on-path adversaries. These findings may serve the LN community as
guidelines for the deployment of VCs.
