A Private Bitcoin Payment Network with Reduced Transaction Fees and Confirmation Times

Since its introduction, Bitcoin cryptocurrency has revolutionized the way payment systems can be designed in a purely distributed manner through its novel Blockchain data structure. While Bitcoin has opened new opportunities, it has been long criticized for its slow transaction confirmation times and high transaction fees. To address this issue, one of the recently emerging solutions is to build a payment channel network (PCN) on top of Bitcoin where the transactions can be made without writing to blockchain. Specifically, a PCN is a network where the users connect either directly or indirectly to send payments to each other in a trustless way. Being backed by the blockchain technology, PCNs satisfy a robust and flexible medium where the exchange of assets become frictionless and thus enable faster transactions with negligible fees. For example, Lightning Network, a second layer network built on top of the Bitcoin network, is being actively developed and it makes Bitcoin possible to be used for micro-payments. However, PCNs including LN bring new challenges on centralization, robustness and privacy as they accept more users. Such problems threaten the very idea of decentralization that comes with blockchain. Therefore, in this dissertation we target the problem of PCN topology formation that will come with ideal features and continue to grow without violating such characteristics. Specifically, we focused on the design of methods for obtaining peer-to-peer (P2P) decentralized PCN topologies. Inspiring from the multi-commodity flow problem, we first developed an optimal solution to establish the perfect PCN topology by utilizing mixed-integer programming. We solve this problem for the required capacities within the network for uninterrupted operation. Second, as mixed integer programming is proved to be NP-compete in complexity, we developed a heuristic optimization approach to take the solution into the polynomial-time domain. Third, to further enable scalability, we developed a new sub-optimal heuristic algorithm using the Dijkstra\u27s shortest path algorithm. Finally, we turned our attention to privacy preservation problem for transactions and augmented each of the proposed approaches with privacy guarantees. Evaluation results indicate that our proposed approaches can enable desirable PCN topology features while respecting the privacy requirements