交易截止时间约束下的支付通道网络交易处理策略研究

支付通道是一类旨在解决区块链可扩展性的技术。通过在区块链外建立支付通道，形成支付通道网络（payment channel networks, PCNs），用户无需与区块链交互即可进行即时支付，避免了交易共识延迟长、交易费用高的问题。
最近，对于支付通道网络的优化主要集中在通过多路径路由来提高网络吞吐量。然而，交易的原子性以不小的交易完成延迟为代价，这会影响基于支付通道网络的截止时间敏感的应用程序的用户体验，而以前的工作忽略了这一点。本文中首次提出了一个新的框架 DPCN 来考虑支付通道网络的交易截止时间，同时提高交易的成功率。DPCN 是通过三个组件的协同作用实现的：(1) 基于截止时间的动态交易拆分机制，根据当前网络状态和交易的截止时间拆分交易；(2) 基于交易截止时间的调度机制，优先考虑距离截止时间较近的交易；（3）基于交易截止时间的拥塞避免算法，它使用路径窗口来平衡具有不同截止时间的交易。本文中，通过设置多种不同的拓扑结构与交易特征在模拟的支付通道网络上做了大量实验，与最先进的方法进行对比, 从而对 DPCN 进行评估。实验表明相比于现有方法，DPCN能够很好地满足不同截止时间的交易的需求，保证支付通道网络中交易有较高的成功率。

[1]ZAMANI M, MOVAHEDI M, RAYKOVA M. Rapidchain: Scaling blockchain via full sharding[C]//ACM CCS. 2018.

[2]LI W, FENG C, ZHANG L, et al. A scalable multi-layer pbft consensus for blockchain[J]. IEEETransactions on Parallel and Distributed Systems, 2021, 32(5): 1146-1160.

[3]WANG J, WANG H. Monoxide: Scale out blockchains with asynchronous consensus zones[C]//USENIX NSDI. 2019.

[4]GILAD Y, HEMO R, MICALI S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies[C]//ACM SOSP. 2017.

[5]Bitcoin[EB/OL]. 2021. https://bitcoin.org/en/.

[6]Ethereum[EB/OL]. 2021. https://www.ethereum.org/.

[7]Visa[EB/OL]. 2021. https://usa.visa.com/run-your-business/small-business-tools/retail.html.

[8]The lightning network[EB/OL]. 2021. https://lightning.network/.

[9]The raiden network[EB/OL]. 2021. https://raiden.network/.

[10]PRIHODKO P, ZHIGULIN S, SAHNO M, et al. Flare: An approach to routing in lightningnetwork[J]. White Paper, 2016.

[11]MALAVOLTA G, MORENO-SANCHEZ P, KATE A, et al. Silentwhispers: Enforcing securityand privacy in decentralized credit networks[C]//NDSS. 2017.

[12]ROOS S, MORENO-SANCHEZ P, KATE A, et al. Settling payments fast and private: Efficientdecentralized routing for path-based transactions[J]. arXiv preprint arXiv:1709.05748, 2017.

[13]WANG P, XU H, JIN X, et al. Flash: efficient dynamic routing for offchain networks[C]//ACMCoNEXT. 2019.

[14]Coinbase[EB/OL]. 2021. https://www.coinbase.com/.

[15]Binance[EB/OL]. 2021. https://www.binance.com/en.

[16]Cryptoblades[EB/OL]. 2021. https://www.cryptoblades.io/.

[17]Splinterlands[EB/OL]. 2021. https://splinterlands.com/.

[18]VAMANAN B, HASAN J, VIJAYKUMAR T. Deadline-aware datacenter tcp (d2tcp)[C]//ACMSIGCOMM. 2012.

[19]ALIZADEH M, GREENBERG A, MALTZ D A, et al. Data center tcp (dctcp)[C]//ACM SIGCOMM. 2010.

[20]CHAUHAN A, MALVIYA O P, VERMA M, et al. Blockchain and scalability[C]//2018 IEEEInternational Conference on Software Quality, Reliability and Security Companion (QRS-C).IEEE, 2018: 122-128.

[21]GILBERT S, LYNCH N. Brewer’s conjecture and the feasibility of consistent, available,partition-tolerant web services[J]. Acm Sigact News, 2002, 33(2): 51-59.

[22]LOMBROZO E, LAU J, WUILLE P. Segregated witness (consensus layer)[J]. Bitcoin CoreDevelop. Team, Tech. Rep. BIP, 2015, 141.

[23]LUU L, NARAYANAN V, ZHENG C, et al. A secure sharding protocol for open blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and CommunicationsSecurity. 2016: 17-30.

[24]LI C, LI P, ZHOU D, et al. A decentralized blockchain with high throughput and fast confirmation[C]//2020 USENIX Annual Technical Conference (USENIX ATC20). 2020: 515-528.

[25]POON J, DRYJA T. The bitcoin lightning network: Scalable off-chain instant payments[Z].2016.

[26]BACK A, CORALLO M, DASHJR L, et al. Enabling blockchain innovations with peggedsidechains[J]. URL: http://www. opensciencereview. com/papers/123/enablingblockchaininnovations-with-pegged-sidechains, 2014, 72.

[27]WOOD G. Polkadot: Vision for a heterogeneous multi-chain framework[J]. White Paper, 2016,21: 2327-4662.

[28]Polkadot[EB/OL]. 2022. https://polkadot.network/.

[29]YU R, XUE G, KILARI V T, et al. Coinexpress: A fast payment routing mechanism inblockchain-based payment channel networks[C]//IEEE ICCCN. 2018.

[30]FORD L R, FULKERSON D R. Maximal flow through a network[J]. Canadian journal ofMathematics, 1956, 8: 399-404.

[31]KHALIL R, GERVAIS A. Revive: Rebalancing off-blockchain payment networks[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 439-453.

[32]LIN S, ZHANG J, WU W. Fstr: funds skewness aware transaction routing for payment channelnetworks[C]//2020 50th Annual IEEE/IFIP International Conference on Dependable Systemsand Networks (DSN). IEEE, 2020: 464-475.

[33]XUE H, HUANG Q, BAO Y. Epa-route: Routing payment channel network with high success rate and low payment fees[C]//2021 IEEE 41st International Conference on DistributedComputing Systems (ICDCS). IEEE, 2021: 227-237.

[34]SIVARAMAN V, VENKATAKRISHNAN S B, RUAN K, et al. High throughput cryptocurrency routing in payment channel networks[C]//USENIX NSDI. 2020.

[35]HABER S, STORNETTA W S. How to time-stamp a digital document[C]//Conference on theTheory and Application of Cryptography. Springer, 1990: 437-455.

[36]BAYER D, HABER S, STORNETTA W S. Improving the efficiency and reliability of digitaltime-stamping[M]//Sequences Ii. Springer, 1993: 329-334.

[37]HABER S, STORNETTA W S. Secure names for bit-strings[C]//Proceedings of the 4th ACMConference on Computer and Communications Security. 1997: 28-35.

[38]NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[J]. Decentralized BusinessReview, 2008: 21260.

[39]Coin selection[EB/OL]. 2022. https://bitcoin.design/guide/glossary/coin-selection/.

[40]DWORK C, NAOR M. Pricing via processing or combatting junk mail[C]//Annual internationalcryptology conference. Springer, 1992: 139-147.

[41]Ethereum staking[EB/OL]. 2022. https://ethereum.org/zh/staking/.

[42]LAMPORT L, SHOSTAK R, PEASE M. The byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.

[43]CASTRO M, LISKOV B, et al. Practical byzantine fault tolerance[C]//OsDI: volume 99. 1999:173-186.

[44]Fisco bcos[EB/OL]. 2022. http://www.fisco-bcos.org/.

[45]SZABO N. Formalizing and securing relationships on public networks[J]. First monday, 1997.

[46]Oracle[EB/OL]. 2022. https://ethereum.org/zh/developers/docs/oracles/.

[47]POON J, DRYJA T. The bitcoin lightning network: Scalable off-chain instant payments[J].2016.

[48]Sha-2[EB/OL]. 2022. https://en.wikipedia.org/wiki/SHA-2.

[49]MISRA S, XUE G, YANG D. Polynomial time approximations for multi-path routing withbandwidth and delay constraints[C]//IEEE INFOCOM 2009. IEEE, 2009: 558-566.

[50]WERMAN S, ZOHAR A. Avoiding deadlocks in payment channel networks[M]//Data PrivacyManagement, Cryptocurrencies and Blockchain Technology. Springer, 2018: 175-187.

[51]OSUNTOKUN O. Atomic multi-path payments over lightning.[EB/OL]. 2018. https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/000993.html.

[52]SIVARAMAN V, VENKATAKRISHNAN S B, ALIZADEH M, et al. Routing cryptocurrencywith the spider network[C]//ACM HotNets. 2018.

[53]LIU C L, LAYLAND J W. Scheduling algorithms for multiprogramming in a hard-real-timeenvironment[J]. Journal of the ACM (JACM), 1973, 20(1): 46-61.

[54]FALL K R, STEVENS W R. Tcp/ip illustrated, volume 1: The protocols[M]. addison-Wesley,2011.

[55]ALLMAN M, PAXSON V, STEVENS W, et al. Tcp congestion control[J]. 1999.

[56]SRIKANT R. The mathematics of internet congestion control[M]. Springer Science & BusinessMedia, 2004.

[57]FLOYD S. Tcp and explicit congestion notification[J]. ACM SIGCOMM Computer Communication Review, 1994, 24(5): 8-23.

[58]RAMAKRISHNAN K, FLOYD S, BLACK D, et al. The addition of explicit congestion notification (ecn) to ip[J]. 2001.

[59]POYNTON C. Digital video and hd: Algorithms and interfaces[M]. Elsevier, 2012.

[60]CHIU D M, JAIN R. Analysis of the increase and decrease algorithms for congestion avoidancein computer networks[J]. Computer Networks and ISDN systems, 1989, 17(1): 1-14.

[61]Omnet++[EB/OL]. 2021. http://omnetpp.org/.

[62]VARGA A, HORNIG R. An overview of the omnet++ simulation environment[C]//Proceedingsof the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops. 2008: 1-10.

[63]WATTS D J, STROGATZ S H. Collective dynamics of ‘smallworld’networks[J]. Nature,393: 440–442.

[64]Watts strogatz model[EB/OL]. 2021. https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model.

[65]Barabási–albert model[EB/OL]. 2021. https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model.

[66]HU P, LAU W C. A survey and taxonomy of graph sampling[J]. arXiv preprint arXiv:1308.5865,2013.