Pith. sign in

REVIEW 29 references

Online Payment Network Design

T0 review · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For a single payment channel, no randomized or deterministic online algorithm is competitive, and matching the offline optimum requires at least n-2 advice bits.

arxiv 1908.00432 v1 pith:DHVOVS4P submitted 2019-08-01 cs.DS cs.DC

Georgia Avarikioti , Kenan Besic , Yuyi Wang , Roger Wattenhofer This is my paper · ORCID
classification cs.DScs.DC
keywords paymentproblemchannelscoordinatordesignnetworkonlinetransactions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Payment channels let two parties move money off the blockchain by updating a shared balance. A Payment Service Provider (PSP) can open a channel between two customers and lock capital on both sides. Transactions arrive one by one, and the PSP must decide on the spot whether to accept each one. The only constraint is that the balance on each side of the channel never goes negative. The PSP wants to accept as many transactions as possible, like an online admissions problem with a budget that shifts left and right.

This paper asks whether any online rule can do almost as well as an all-knowing planner that sees the whole transaction sequence. The answer is no. For a single channel, no deterministic rule has a bounded competitive ratio, a result inherited from the authors' earlier work. This paper adds that randomization does not help against an adversary that adapts to the algorithm's decisions, and it also fails against a weaker adversary that fixes the whole sequence in advance. The proof uses the standard connection between randomized algorithms and algorithms that receive a few bits of advice: if a small number of advice bits cannot encode the right strategy, then randomness cannot guarantee a good competitive ratio either.

The paper also studies resource augmentation, giving the online algorithm more capital than the offline optimum. Even with nearly double the capital, no deterministic algorithm is competitive. A separate minimization version, where the goal is to minimize rejected transactions, also admits no competitive randomized algorithm. The results are presented as a series of theorems and corollaries, with the main technical tool being a family of hard transaction sequences that force the algorithm to guess a hidden number.

Extended reading notes

Core claim

The paper's central assertion is that no competitive randomized algorithm exists against oblivious adversaries for the online single-channel payment network design problem (Corollary 1), and that even with h<2 times the capital no competitive deterministic algorithm exists (Theorem 6). If correct, these results close the single-channel online case for deterministic, randomized, and advice-based algorithms.

Load-bearing premise

The lower-bound constructions depend on an informally specified 'loop' transaction sequence that is feasible only when the algorithm has transferred the exact required amount of capital before the loop starts. The paper never formally defines this loop, and the claimed general lower bound in Theorem 3 (n-2 advice bits) is only proven for n=3. If the loop can be partially accepted by a misprepared algorithm, or if the n=3 argument does not generalize, the stated bounds are not established.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters or invented physical entities. The model uses standard online algorithm concepts; the only ad hoc ingredient is the hard-instance construction with the undefined loop sequence.

assumptions (5)
  • standard math Ben-David et al. Theorems 2.1 and 2.2 relating randomized algorithms against adaptive online, oblivious, and adaptive offline adversaries.
    Used in Theorem 1 to convert a hypothetical randomized adaptive-online algorithm into a deterministic algorithm, contradicting [3].
  • standard math Theorem 19 of Avarikioti et al. [3]: no competitive deterministic online algorithm for the single channel.
    Cited as the base impossibility that Theorem 1 derives a contradiction from.
  • standard math Yao's principle for expected competitive ratios of randomized online algorithms.
    Used in Theorems 5 and 8 to convert advice lower bounds into randomized lower bounds.
  • ad hoc to paper The 'loop' transaction sequence has the property that it is only fully feasible when the algorithm has transferred exactly x capital, and any misprepared algorithm accepts at most f(n)+1 transactions before it.
    This is the load-bearing property of all lower-bound constructions in Sections 3.2, 3.3, and 3.5, but the sequence is never formally specified.
  • standard math The advice complexity framework: an algorithm reading b(n) advice bits has at most 2^{b(n)} distinct behaviors.
    Used for the pigeonhole arguments in Theorems 4, 5, 7, and 8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Payment Network Design." pith.science (2026). https://pith.science/paper/DHVOVS4P

@misc{pith2026190800432,
  author       = {Pith},
  title        = {Pith review of: Online Payment Network Design},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DHVOVS4P}},
  note         = {Machine review of arXiv:1908.00432}
}
read the original abstract

Payment channels allow transactions between participants of the blockchain to be executed securely off-chain, and thus provide a promising solution for the scalability problem of popular blockchains. We study the online network design problem for payment channels, assuming a central coordinator. We focus on a single channel, where the coordinator desires to maximize the number of accepted transactions under given capital constraints. Despite the simplicity of the problem, we present a flurry of impossibility results, both for deterministic and randomized algorithms against adaptive as well as oblivious adversaries.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 27 canonical work pages

  1. [1]

    In: Data Privacy Management, Cryptocurrencies a nd Blockchain Tech- nology, pp

    Avarikioti, G., Janssen, G., Wang, Y., Wattenhofer, R.: P ayment network design with fees. In: Data Privacy Management, Cryptocurrencies a nd Blockchain Tech- nology, pp. 76–84. Springer (2018)

    work page 2018

  2. [2]

    Avarikioti, G., Kogias, E.K., Wattenhofer, R.: Brick: As ynchronous state channels (2019)

    work page 2019

  3. [3]

    In: 29th International Symposium on Algorithms and Computation (IS AAC), Jiaoxi, Yilan County, Taiwan (December 2018)

    Avarikioti, G., Wang, Y., Wattenhofer, R.: Algorithmic C hannel Design. In: 29th International Symposium on Algorithms and Computation (IS AAC), Jiaoxi, Yilan County, Taiwan (December 2018)

    work page 2018

  4. [4]

    In: Algorithmica

    Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigders on, A.: On the power of randomization in online algorithms. In: Algorithmica. p p. 379–386 (1990)

    work page 1990

  5. [5]

    Cam- bridge University Press, New York, NY, USA (1998)

    Borodin, A., El-Yaniv, R.: Online Computation and Compet itive Analysis. Cam- bridge University Press, New York, NY, USA (1998)

    work page 1998

  6. [6]

    https://github.com/ethereum/wiki/wiki/White-Paper (2013)

    Buterin, V.: Ethereum: A next-generation smart contract and decentralized appli- cation platform. https://github.com/ethereum/wiki/wiki/White-Paper (2013)

    work page 2013

  7. [7]

    Coleman, J., Horne, L., Xuanji, L.: Counterfactual: Gene ralized state channels (2018)

    work page 2018

  8. [8]

    In: International Conference on Financial Cr yptography and Data Security

    Croman, K., Decker, C., Eyal, I., Gencer, A.E., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Sirer, E.G., Song, D., Wattenhofer, R.: On scaling decentralized blockchains. In: International Conference on Financial Cr yptography and Data Security. pp. 106–125. Springer (2016)

    work page 2016

Show all 29 references
  1. [9]

    Decker, C., Russell, R., Osuntokun, O.: eltoo: A simple la yer2 protocol for bitcoin (2018)

    2018

  2. [10]

    In: Symposium on Self-Stabi lizing Systems

    Decker, C., Wattenhofer, R.: A fast and scalable payment network with bitcoin duplex micropayment channels. In: Symposium on Self-Stabi lizing Systems. pp. 3–18. Springer (2015)

    2015

  3. [11]

    IACR Cryptology e Print Archive 2017, 635 (2017)

    Dziembowski, S., Eckey, L., Faust, S., Malinowski, D.: P erun: Virtual payment channels over cryptographic currencies. IACR Cryptology e Print Archive 2017, 635 (2017)

    2017

  4. [12]

    Avarikioti et al

    Green, M., Miers, I.: Bolt: Anonymous payment channels f or decentralized curren- cies (10 2017) 14 G. Avarikioti et al

    2017

  5. [13]

    IACR Cryptology ePrint Archive 2019, 360 (2019), https://eprint.iacr.org/2019/360

    Gudgeon, L., Moreno-Sanchez, P., Roos, S., McCorry, P., Gervais, A.: Sok: Off the chain transactions. IACR Cryptology ePrint Archive 2019, 360 (2019), https://eprint.iacr.org/2019/360

    2019

  6. [14]

    In : Network and Dis- tributed System Security Symposium (2017)

    Heilman, E., Alshenibr, L., Baldimtsi, F., Scafuro, A., Goldberg, S.: Tumblebit: An untrusted bitcoin-compatible anonymous payment hub. In : Network and Dis- tributed System Security Symposium (2017)

    2017

  7. [15]

    Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as c lairvoyance. J. ACM 47(4), 617–643 (Jul 2000)

    2000

  8. [16]

    Cryptology ePrint Archive, Report 2018/642 (2018), https://eprint.iacr.org/2018/642

    Khalil, R., Gervais, A., Felley, G.: Nocust - a securely s calable commit-chain. Cryptology ePrint Archive, Report 2018/642 (2018), https://eprint.iacr.org/2018/642

    2018

  9. [17]

    In: 2018 IEEE Symposium on Security and Privacy (SP)

    Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., Ford, B.: Om- niledger: A secure, scale-out, decentralized ledger via sh arding. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 583–598. IEEE (2 018)

    2018

  10. [18]

    Springer Publishing Company, Incorporated, 1st edn

    Komm, D.: An Introduction to Online Computation: Determ inism, Randomiza- tion, Advice. Springer Publishing Company, Incorporated, 1st edn. (2016)

    2016

  11. [19]

    In: ACM Conference on Computer and Communications Security (2016)

    Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S ., Saxena, P.: A secure sharding protocol for open blockchains. In: ACM Conference on Computer and Communications Security (2016)

    2016

  12. [20]

    arXiv preprint arXiv:1702.05812 (2017)

    Miller, A., Bentov, I., Kumaresan, R., Cordi, C., McCorr y, P.: Sprites and state channels: Payment networks that go faster than lightn ing. arXiv preprint arXiv:1702.05812 (2017)

    2017 arXiv

  13. [21]

    Moreno-Sanchez, P., Kate, A., Maffei, M.: Silentwhisper s: Enforcing security and privacy in decentralized credit networks (2017)

    2017

  14. [22]

    Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash s ystem (2018), http://bitcoin.org/bitcoin.pdf

    2018

  15. [23]

    Poon, J., Buterin, V.: Plasma: Scalable autonomous smar t contracts (2017)

    2017

  16. [24]

    Poon, J., Dryja, T.: The bitcoin lightning network: Scal able off-chain instant pay- ments (2015), https://lightning.network

    2015

  17. [25]

    Prihodko, P., Zhigulin, S., Sahno, M., Ostrovskiy, A., O suntokun, O.: Flare : An approach to routing in lightning network white paper (2016)

    2016

  18. [26]

    arXiv preprint arXiv:1709.05748 (2017)

    Roos, S., Moreno-Sanchez, P., Kate, A., Goldberg, I.: Se ttling payments fast and private: Efficient decentralized routing for path-based tra nsactions. arXiv preprint arXiv:1709.05748 (2017)

    2017 arXiv

  19. [27]

    https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html , accessed: 2019-04-17

    Spilman, J.: Anti dos for tx replacement. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html , accessed: 2019-04-17

    2013

  20. [28]

    https://usa.visa.com/dam/VCOM/download/corporate/media/visanet-technology/aboutvisafactsheet.pdf (2018), acccessed: 10.04.2019

    Visa Inc.: Fact sheet - visa. https://usa.visa.com/dam/VCOM/download/corporate/media/visanet-technology/aboutvisafactsheet.pdf (2018), acccessed: 10.04.2019

    2018

  21. [29]

    In: 18th Annual Symposium on Foundations of Computer Scienc e (sfcs 1977)

    Yao, A.C.C.: Probabilistic computations: Toward a unifi ed measure of complexity. In: 18th Annual Symposium on Foundations of Computer Scienc e (sfcs 1977). pp. 222–227. IEEE (1977)

    1977

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.