  Payment channels are the most prominent solution to the blockchain
scalability problem. We introduce the problem of network design with fees for
payment channels from the perspective of a Payment Service Provider (PSP).
Given a set of transactions, we examine the optimal graph structure and fee
assignment to maximize the PSP's profit. A customer prefers to route
transactions through the PSP's network if the cheapest path from sender to
receiver is financially interesting, i.e., if the path costs less than the
blockchain fee. When the graph structure is a tree, and the PSP facilitates all
transactions, the problem can be formulated as a linear program. For a path
graph, we present a polynomial time algorithm to assign optimal fees. We also
show that the star network, where the center is an additional node acting as an
intermediary, is a near-optimal solution to the network design problem.
