Resource Burning for Permissionless Systems (Invited Paper) | SpringerLink
Skip to main content
Springer Nature Link
Log in

Resource Burning for Permissionless Systems (Invited Paper)

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12156))

  • 410 Accesses

Abstract

Proof-of-work puzzles and CAPTCHAS consume enormous amounts of energy and time. These techniques are examples of resource burning: verifiable consumption of resources solely to convey information.

Can these costs be eliminated? It seems unlikely since resource burning shares similarities with “money burning” and “costly signaling”, which are foundational to game theory, biology, and economics. Can these costs be reduced? Yes, research shows we can significantly lower the asymptotic costs of resource burning in many different settings.

In this paper, we survey the literature on resource burning; take positions based on predictions of how the tool is likely to evolve; and propose several open problems targeted at the theoretical distributed-computing research community.

“It’s not about money, it’s about sending a message.”

The Joker  [107]

This work is supported by the National Science Foundation grants NSF-CNS-1816250 and NSF-CNS-1816076.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    This is equivalent to what is referred to as the “battle of the sexes” game in  [29].

  2. 2.

    On the positive side, smart students stay smart!.

  3. 3.

    Resource burning refers to the game-theoretic money burning technique; resource testing refers to that technique specifically applied in the wireless domain.

  4. 4.

    Informally, this refers to a scheme where the source makes a “capability” request and, if approved by the receiver, will then obtain prioritized service from those routers along the path between the source and the receiver.

References

  1. Abadi, M., Burrows, M., Manasse, M., Wobber, T.: Moderately hard, memory-bound functions. ACM Trans. Internet Technol. (TOIT) 5(2), 299–327 (2005)

    Article  Google Scholar 

  2. Abraham, I., Malkhi, D.: The Blockchain Consensus Layer and BFT. Bull. EATCS: Distrib. Comput. Column (2017)

    Google Scholar 

  3. Abraham, I., Malkhi, D., Dobzinski, O.: Land: stretch \((1 + \epsilon )\) locality-aware networks for DHTs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 550–559 (2004)

    Google Scholar 

  4. Aggarwal, A., Movahedi, M., Saia, J., Zamani, M.: Bootstrapping public blockchains without a trusted setup. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 366–368. ACM (2019)

    Google Scholar 

  5. Akoglu, L., Chandy, R., Faloutsos, C.: Opinion fraud detection in online reviews by network effects. In: Seventh International AAAI Conference on Weblogs and Social Media (2013)

    Google Scholar 

  6. Ali, I.M., Caprolu, M., Pietro, R.D.: Foundations, properties, and security applications of puzzles: a survey. CoRR abs/1904.10164 (2019). http://arxiv.org/abs/1904.10164

  7. Alvisi, L., Clement, A., Epasto, A., Lattanzi, S., Panconesi, A.: SoK: the evolution of sybil defense via social networks. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 382–396 (2013)

    Google Scholar 

  8. Hertig, A.: Ethereum’s big switch: the new roadmap to proof-of-stake (2017). urlwww.coindesk.com/ethereums-big-switch-the-new-roadmap-to-proof-of-stake/. Accessed 28 Nov 2019

  9. Anderson, T., Roscoe, T., Wetherall, D.: Preventing internet denial-of-service with capabilities. ACM SIGCOMM Comput. Commun. Rev. 34(1), 39–44 (2004)

    Article  Google Scholar 

  10. Andrychowicz, M., Dziembowski, S.: PoW-based distributed cryptography with no trusted setup. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 379–399. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_19

    Chapter  Google Scholar 

  11. Aspnes, J., Jackson, C., Krishnamurthy, A.: Exposing computationally-challenged byzantine impostors. Technical report, Technical Report YALEU/DCS/TR-1332, Yale University (2005). http://www.cs.yale.edu/homes/aspnes/papers/tr1332.pdf

  12. Aspnes, J., Shah, G.: Skip graphs. In: Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384–393 (2003)

    Google Scholar 

  13. Ateniese, G., Bonacina, I., Faonio, A., Galesi, N.: Proofs of space: when space is of the essence. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 538–557. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10879-7_31

    Chapter  Google Scholar 

  14. Augustine, J., Molla, A.R., Morsy, E., Pandurangan, G., Robinson, P., Upfal, E.: Storage and search in dynamic peer-to-peer networks. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 53–62 (2013)

    Google Scholar 

  15. Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine agreement in dynamic networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 74–83 (2013)

    Google Scholar 

  16. Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine leader election in dynamic networks. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 276–291. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48653-5_19

    Chapter  Google Scholar 

  17. Augustine, J., Pandurangan, G., Robinson, P., Roche, S., Upfal, E.: Enabling robust and efficient distributed computation in dynamic peer-to-peer networks. In: Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 350–369 (2015)

    Google Scholar 

  18. Augustine, J., Pandurangan, G., Robinson, P., Upfal, E.: Towards robust and efficient computation in dynamic peer-to-peer networks. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 551–569 (2012)

    Google Scholar 

  19. Aura, T., Nikander, P., Leiwo, J.: DOS-resistant authentication with client puzzles. In: Christianson, B., Malcolm, J.A., Crispo, B., Roe, M. (eds.) Security Protocols 2000. LNCS, vol. 2133, pp. 170–177. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44810-1_22

    Chapter  Google Scholar 

  20. Awerbuch, B., Scheideler, C.: The hyperring: a low-congestion deterministic data structure for distributed environments. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 318–327 (2004)

    Google Scholar 

  21. Awerbuch, B., Scheideler, C.: Robust random number generation for peer-to-peer systems. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 275–289. Springer, Heidelberg (2006). https://doi.org/10.1007/11945529_20

    Chapter  Google Scholar 

  22. Awerbuch, B., Scheideler, C.: Towards a scalable and robust DHT. In: Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 318–327 (2006)

    Google Scholar 

  23. Awerbuch, B., Scheideler, C.: Towards scalable and robust overlay networks. In: Proceedings of the 6th International Workshop on Peer-to-Peer Systems (IPTPS), p. n. pag. (2007)

    Google Scholar 

  24. Baird, H.S., Moll, M.A., Wang, S.Y.: ScatterType: a legible but hard-to-segment CAPTCHA. In: Proceedings of the Eighth International Conference on Document Analysis and Recognition (ICDAR), pp. 935–939 (2005)

    Google Scholar 

  25. Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 789–819. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_26

    Chapter  Google Scholar 

  26. Bazzi, R.A., Konjevod, G.: On the establishment of distinct identities in overlay networks. In: Proceedings 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 312–320 (2005)

    Google Scholar 

  27. Bentov, I., Lee, C., Mizrahi, A., Rosenfeld, M.: Proof of activity: extending bitcoin’s proof of work via proof of stake [extended abstract] y. ACM SIGMETRICS Perform. Eval. Rev. 42(3), 34–37 (2014)

    Article  Google Scholar 

  28. Beutel, A., Xu, W., Guruswami, V., Palow, C., Faloutsos, C.: CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In: Proceedings of the 22nd International Conference on World Wide Web (WWW), pp. 119–130 (2013)

    Google Scholar 

  29. Binmore, K., et al.: Playing for Real: A Text on Game Theory. Oxford University Press, Oxford (2007)

    Book  MATH  Google Scholar 

  30. BitcoinWiki: Bitcoinwiki network (2019). https://en.bitcoin.it/wiki/Network. Accessed 28 Nov 2019

  31. Borisov, N.: Computational puzzles as sybil defenses. In: Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing (P2P), pp. 171–176 (2006)

    Google Scholar 

  32. Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.S.: Secure routing for structured peer-to-peer overlay networks. In: Proceedings of the 5th Usenix Symposium on Operating Systems Design and Implementation (OSDI), pp. 299–314 (2002)

    Google Scholar 

  33. CBS News, A.P.: Buyer beware: scourge of fake reviews hitting Amazon, Walmart and other major retailers (2019). https://www.cbsnews.com/news/buyer-beware-a-scourge-of-fake-online-reviews-is-hitting-amazon-walmart-and-other-major-retailers/

  34. Chau, D.H., Pandit, S., Faloutsos, C.: Detecting fraudulent personalities in networks of online auctioneers. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) PKDD 2006. LNCS (LNAI), vol. 4213, pp. 103–114. Springer, Heidelberg (2006). https://doi.org/10.1007/11871637_14

    Chapter  Google Scholar 

  35. CoinDesk: Vulnerable? Ethereum’s Casper Tech Takes Criticism at Curacao Event (2018). https://www.coindesk.com/fundamentally-vulnerable-ethereums-casper-tech-takes-criticism-curacao

  36. Cracked: I get paid to write fake reviews for amazon (2016). https://www.cracked.com/personal-experiences-2376-i-get-paid-to-write-fake-reviews-amazon.html

  37. Danezis, G., Lesniewski-Laas, C., Kaashoek, M.F., Anderson, R.: Sybil-resistant DHT routing. In: di Vimercati, S.C., Syverson, P., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 305–318. Springer, Heidelberg (2005). https://doi.org/10.1007/11555827_18

    Chapter  Google Scholar 

  38. Demirbas, M., Song, Y.: An RSSI-based scheme for sybil attack detection in wireless sensor networks. In: Proceedings of the 2006 International Symposium on on World of Wireless, Mobile and Multimedia Networks (WOWMOM), pp. 564–570 (2006)

    Google Scholar 

  39. Digiconomist: Bitcoin energy consumption index (2020). https://digiconomist.net/bitcoin-energy-consumption

  40. Dinger, J., Hartenstein, H.: Defending the sybil attack in P2P networks: taxonomy, challenges, and a proposal for self-registration. In: Proceedings of the First International Conference on Availability, Reliability and Security (ARES), pp. 756–763 (2006)

    Google Scholar 

  41. Douceur, J.R.: The sybil attack. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 251–260. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_24

    Chapter  Google Scholar 

  42. Dwork, C., Goldberg, A., Naor, M.: On memory-bound functions for fighting spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_25

    Chapter  Google Scholar 

  43. Dwork, C., Naor, M.: Pricing via Processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10

    Chapter  Google Scholar 

  44. Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_29

    Chapter  Google Scholar 

  45. Easley, D., Kleinberg, J., et al.: Networks, Crowds, and Markets, vol. 8. Cambridge University Press, Cambridge (2010)

    Book  MATH  Google Scholar 

  46. Falkner, J., Piatek, M., John, J.P., Krishnamurthy, A., Anderson, T.: Profiling a million user DHT. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, pp. 129–134 (2007)

    Google Scholar 

  47. Fiat, A., Saia, J.: Censorship resistant peer-to-peer content addressable networks. In: Proceedings of the Thirteenth ACM Symposium on Discrete Algorithms (SODA), pp. 94–103 (2002)

    Google Scholar 

  48. Fiat, A., Saia, J., Young, M.: Making chord robust to byzantine attacks. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 803–814. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_71

    Chapter  Google Scholar 

  49. FitzGibbon, C.D., Fanshawe, J.H.: Stotting in Thomson’s gazelles: an honest signal of condition. Behav. Ecol. Sociobiol. 23(2), 69–74 (1988)

    Article  Google Scholar 

  50. Forbes: Amazon’s fake review problem is getting worse (2019). https://www.forbes.com/sites/emmawoollacott/2019/04/16/amazons-fake-review-problem-is-getting-worse/#f6988195f525

  51. Fraigniaud, P., Gauron, P.: D2B: a de bruijn based content-addressable network. Theoret. Comput. Sci. 355(1), 65–79 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  52. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10

    Chapter  Google Scholar 

  53. Gil, S., Kumar, S., Mazumder, M., Katabi, D., Rus, D.: Guaranteeing spoof-resilient multi-robot networks. In: Proceedings of Robotics: Science and Systems, Rome, Italy, July 2015

    Google Scholar 

  54. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles (SOSP), pp. 51–68 (2017)

    Google Scholar 

  55. Gilbert, S., Newport, C., Zheng, C.: Who are you? Secure identities in ad hoc networks. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 227–242. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45174-8_16

    Chapter  Google Scholar 

  56. Gilbert, S., Zheng, C.: SybilCast: broadcast on the open airwaves. In: Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 130–139 (2013)

    Google Scholar 

  57. Guerraoui, R., Huc, F., Kermarrec, A.M.: Highly dynamic distributed computing with byzantine failures. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC), pp. 176–183 (2013)

    Google Scholar 

  58. Gupta, D., Saia, J., Young, M.: Proof of work without all the work. In: Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN) (2018)

    Google Scholar 

  59. Gupta, D., Saia, J., Young, M.: Peace through superior puzzling: an asymmetric sybil defense. In: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1083–1094 (2019)

    Google Scholar 

  60. Gupta, D., Saia, J., Young, M.: ToGCom: an asymmetric sybil defense. arXiv preprint arXiv:2006.02893 (2020)

  61. Hartline, J.D., Roughgarden, T.: Optimal mechanism design and money burning. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 75–84 (2008)

    Google Scholar 

  62. Harvey, N.J.A., Jones, M.B., Saroiu, S., Theimer, M., Wolman, A.: Skipnet: a scalable overlay network with practical locality properties. In: USENIX Symposium on Internet Technologies and Systems (2003)

    Google Scholar 

  63. Heilman, E., Kendler, A., Zohar, A., Goldberg, S.: Eclipse attacks on bitcoin’s peer-to-peer network. In: Proceedings of the 24th USENIX Conference on Security Symposium, pp. 129–144 (2015)

    Google Scholar 

  64. Heydari, A., AliTavakoli, M., Salim, N., Heydari, Z.: Detection of review spam: a survey. Expert Syst. Appl. 42(7), 3634–3642 (2015). https://doi.org/10.1016/j.eswa.2014.12.029. http://www.sciencedirect.com/science/article/pii/S0957417414008082

    Article  Google Scholar 

  65. Hildrum, K., Kubiatowicz, J.: Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 321–336. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39989-6_23

    Chapter  Google Scholar 

  66. Hooi, B., Song, H.A., Beutel, A., Shah, N., Shin, K., Faloutsos, C.: FRAUDAR: bounding graph fraud in the face of camouflage. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 895–904. Association for Computing Machinery, New York (2016). https://doi.org/10.1145/2939672.2939747

  67. Hou, R., Jahja, I., Luu, L., Saxena, P., Yu, H.: Randomized view reconciliation in permissionless distributed systems, pp. 2528–2536 (2018)

    Google Scholar 

  68. Huck, S., Müller, W.: Burning money and (pseudo) first-mover advantages: an experimental study on forward induction. Games Econ. Behav. 51(1), 109–127 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  69. Hunt, K.M.: Gaming the system: fake online reviews v. consumer law. Comput. Law Secur. Rev. 31(1), 3–25 (2015). http://www.sciencedirect.com/science/article/pii/S0267364914001824

    Article  Google Scholar 

  70. Hussain, A., Heidemann, J., Papadopoulos, C.: A framework for classifying denial of service attacks. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pp. 99–110 (2003)

    Google Scholar 

  71. Jagadish, H., Ooi, B.C., Vu, Q.H.: BATON: a balanced tree structure for peer-to-peer networks. In: Proceedings of the 31st International conference on Very Large Data Bases (VLDB), pp. 661–672 (2005)

    Google Scholar 

  72. Jaiyeola, M.O., Patron, K., Saia, J., Young, M., Zhou, Q.M.: Tiny groups tackle byzantine adversaries. In: Proceedings of the IEEE International Parallel and Distributed Processing Symposium, IPDPS, pp. 1030–1039 (2018)

    Google Scholar 

  73. Jindal, N., Liu, B.: Opinion spam and analysis. In: Proceedings of the 2008 International Conference on Web Search and Data Mining, pp. 219–230 (2008)

    Google Scholar 

  74. Johansen, H., Allavena, A., van Renesse, R.: Fireflies: scalable support for intrusion-tolerant network overlays. In: ACM SIGOPS Operating Systems Review, pp. 3–13 (2006)

    Google Scholar 

  75. John, R., Cherian, J.P., Kizhakkethottam, J.J.: A survey of techniques to prevent sybil attacks. In: Proceedings of the International Conference on Soft-Computing and Networks Security (ICSNS), pp. 1–6 (2015)

    Google Scholar 

  76. Juels, A., Brainard, J.: Client puzzles: a cryptographic countermeasure against connection depletion attacks. In: Proceedings of the Network and Distributed System Security Symposium (NDSS), pp. 151–165 (1999)

    Google Scholar 

  77. Kaiser, E., Feng, W.C.: Mod\(\_\)kaPoW: mitigating DoS with transparent proof-of-work. In: Proceedings of the 2007 ACM CoNEXT Conference, pp. 74:1–74:2 (2007)

    Google Scholar 

  78. Kapadia, A., Triandopoulos, N.: Halo: High-assurance locate for distributed hash tables. In: Proceedings of the Network and Distributed System Security Symposium (NDSS) (2008)

    Google Scholar 

  79. Karami, A., Zhou, B.: Online review spam detection by new linguistic features. In: iConference 2015 Proceedings (2015)

    Google Scholar 

  80. Kaashoek, M.F., Karger, D.R.: Koorde: a simple degree-optimal distributed hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol. 2735, pp. 98–107. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45172-3_9

    Chapter  Google Scholar 

  81. Katz, J., Miller, A., Shi, E.: Pseudonymous secure computation from time-lock puzzles. IACR Cryptol. ePrint Arch. 2014, 857 (2014). http://eprint.iacr.org/2014/857

  82. Khan, S.M., Mallesh, N., Nambiar, A., Wright, M.K.: The dynamics of salsa: a robust structured P2P system. Netw. Protocols Algorithms 2, 40–60 (2010)

    Google Scholar 

  83. Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357–388. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12

    Chapter  Google Scholar 

  84. Knockel, J., Saad, G., Saia, J.: Self-healing of byzantine faults. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 98–112. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03089-0_8

    Chapter  Google Scholar 

  85. Laurie, B., Clayton, R.: “Proof-of-work” proves not to work. In: Proceedings of the 3rd Annual Workshop on Economics and Information Security (WEIS) (2004)

    Google Scholar 

  86. Lesniewski-Laas, C., Kaashoek, M.F.: Whanau: a sybil-proof distributed hash table. In: Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation, NSDI 2010 , p. 8 (2010)

    Google Scholar 

  87. Li, D., Lu, X., Wu, J.: FISSIONE: a scalable constant degree and low congestion DHT scheme based on Kautz graphs. In: Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1677–1688 (2005)

    Google Scholar 

  88. Li, F., Mittal, P., Caesar, M., Borisov, N.: SybilControl: practical sybil defense with computational puzzles. In: Proceedings of the Seventh ACM Workshop on Scalable Trusted Computing, pp. 67–78 (2012)

    Google Scholar 

  89. Lin, I.C., Liao, T.C.: A survey of blockchain security issues and challenges. IJ Netw. Secur. 19(5), 653–659 (2017)

    Google Scholar 

  90. Liu, D., Camp, L.J.: Proof of work can work. In: Proceedings of the 5th Workshop on the Economics of Information Security (WEIS) (2006)

    Google Scholar 

  91. Liu, Y., Bild, D.R., Dick, R.P., Mao, Z.M., Wallach, D.S.: The Mason test: a defense against sybil attacks in wireless networks without trusted authorities. IEEE Trans. Mob. Comput. 14(11), 2376–2391 (2015)

    Article  Google Scholar 

  92. Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., Saxena, P.: A secure sharding protocol for open blockchains. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 17–30 (2016)

    Google Scholar 

  93. Malbon, J.: Taking fake online consumer reviews seriously. J. Consum. Policy 36(2), 139–157 (2013)

    Article  Google Scholar 

  94. Malliga, S., Tamilarasi, A., Janani, M.: Filtering spoofed traffic at source end for defending against DoS/DDoS attacks. In: Proceedings of the International Conference on Computing, Communication and Networking, pp. 1–5. IEEE (2008)

    Google Scholar 

  95. Mankins, D., Krishnan, R., Boyd, C., Zao, J., Frentz, M.: Mitigating distributed denial of service attacks with dynamic resource pricing. In: Proceedings of the Seventeenth Annual Computer Security Applications Conference, pp. 411–421. IEEE (2001)

    Google Scholar 

  96. Maymounkov, P., Mazières, D.: Kademlia: a peer-to-peer information system based on the XOR metric. In: Druschel, P., Kaashoek, F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 53–65. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45748-8_5

    Chapter  MATH  Google Scholar 

  97. Miller, A., et al.: Discovering bitcoin’s public topology and influential nodes (2015). http://cs.umd.edu/projects/coinscope/coinscope.pdf

  98. Miller, G.: Spent: Sex, Evolution, and Consumer Behavior. Penguin, New York (2009)

    Google Scholar 

  99. Mohaisen, A., Hollenbeck, S.: Improving social network-based sybil defenses by rewiring and augmenting social graphs. In: Kim, Y., Lee, H., Perrig, A. (eds.) WISA 2013. LNCS, vol. 8267, pp. 65–80. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-05149-9_5

    Chapter  Google Scholar 

  100. Mohaisen, A., Kim, J.: The sybil attacks and defenses: a survey. Smart Comput. Rev. 3(6), 480–489 (2013)

    Article  Google Scholar 

  101. Mónica, D., Leitao, L., Rodrigues, L., Ribeiro, C.: On the use of radio resource tests in wireless ad-hoc networks. In: Proceedings of the 3rd Workshop on Recent Advances on Intrusion-Tolerant Systems, pp. 21–26 (2009)

    Google Scholar 

  102. Moran, T., Orlov, I.: Simple proofs of space-time and rational proofs of storage. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 381–409. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_14

    Chapter  Google Scholar 

  103. Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008). http://bitcoin.org/bitcoin.pdf

  104. Nambiar, A., Wright, M.: Salsa: a structured approach to large-scale anonymity. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 17–26 (2006)

    Google Scholar 

  105. Naor, M., Wieder, U.: Novel architectures for P2P applications: the continuous-discrete approach. In: Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2003)

    Google Scholar 

  106. Newsome, J., Shi, E., Song, D., Perrig, A.: The sybil attack in sensor networks: analysis & defenses. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN), pp. 259–268 (2004)

    Google Scholar 

  107. Nolan, C.: The Dark Knight. Quote from the scene where the Joker sets a large pile of money ablaze (2008)

    Google Scholar 

  108. Noureddine, M.A., et al.: Revisiting client puzzles for state exhaustion attacks resilience. In: Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 617–629 (2019)

    Google Scholar 

  109. Oikonomou, G., Mirkovic, J.: Modeling human behavior for defense against flash-crowd attacks. In: Proceedings of the IEEE International Conference on Communications, pp. 1–6. IEEE (2009)

    Google Scholar 

  110. Ott, M., Choi, Y., Cardie, C., Hancock, J.T.: Finding deceptive opinion spam by any stretch of the imagination. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 309–319. Association for Computational Linguistics, USA (2011)

    Google Scholar 

  111. Park, S., Kwon, A., Fuchsbauer, G., Gaži, P., Alwen, J., Pietrzak, K.: SpaceMint: a cryptocurrency based on proofs of space. In: Meiklejohn, S., Sako, K. (eds.) FC 2018. LNCS, vol. 10957, pp. 480–499. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-58387-6_26

    Chapter  Google Scholar 

  112. Parno, B., Wendlandt, D., Shi, E., Perrig, A., Maggs, B., Hu, Y.C.: Portcullis: protecting connection setup from denial-of-capability attacks. ACM SIGCOMM Comput. Commun. Rev. 37(4), 289–300 (2007)

    Article  Google Scholar 

  113. Penn, D.J.: The evolutionary roots of our environmental problems: toward a darwinian ecology. Q. Rev. Biol. 78(3), 275–301 (2003)

    Article  Google Scholar 

  114. Pogue, D.: Time to kill off captchas. Sci. Am. 306(3), 23–23 (2012)

    Article  Google Scholar 

  115. Rayana, S., Akoglu, L.: Collective opinion spam detection: bridging review networks and metadata. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2015, pp. 985–994. Association for Computing Machinery, New York (2015). https://doi.org/10.1145/2783258.2783370

  116. Rowaihy, H., Enck, W., McDaniel, P., La Porta, T.: Limiting Sybil attacks in structured P2P networks. In: Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM), pp. 2596–2600 (2007)

    Google Scholar 

  117. Rowstron, A.I.T., Druschel, P.: Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms, pp. 329–350 (2001)

    Google Scholar 

  118. Saad, G.: The Evolutionary Bases of Consumption. Psychology Press (2007)

    Google Scholar 

  119. Saad, G., Vongas, J.G.: The effect of conspicuous consumption on men’s testosterone levels. Organ. Behav. Hum. Decis. Process. 110(2), 80–92 (2009)

    Article  Google Scholar 

  120. Saad, G., Saia, J.: Self-healing computation. In: Proceedings of the International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 195–210 (2014)

    Google Scholar 

  121. Saad, G., Saia, J.: A theoretical and empirical evaluation of an algorithm for self-healing computation. Distrib. Comput. 30(6), 391–412 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  122. Saia, J., Young, M.: Reducing communication costs in robust peer-to-peer networks. Inform. Process. Lett. 106(4), 152–158 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  123. Savage, D., Zhang, X., Yu, X., Chou, P., Wang, Q.: Detection of opinion spam based on anomalous rating deviation. Expert Syst. Appl. 42(22), 8650–8657 (2015). https://doi.org/10.1016/j.eswa.2015.07.019. http://www.sciencedirect.com/science/article/pii/S0957417415004790

    Article  Google Scholar 

  124. Scheideler, C., Schmid, S.: A distributed and oblivious heap. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 571–582. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02930-1_47

    Chapter  MATH  Google Scholar 

  125. Sen, S., Freedman, M.J.: Commensal cuckoo: secure group partitioning for large-scale services. ACM SIGOPS Oper. Syst. 46(1), 33–39 (2012)

    Article  Google Scholar 

  126. Shoker, A.: Sustainable blockchain through proof of exercise. In: 2017 IEEE 16th International Symposium on Network Computing and Applications (NCA), pp. 1–9. IEEE (2017)

    Google Scholar 

  127. Singh, A., Ngan, T.W., Druschel, P., Wallach, D.S.: Eclipse attacks on overlay networks: threats and defenses. In: Proceedings IEEE International Conference on Computer Communications (INFOCOM), pp. 1–12 (2006)

    Google Scholar 

  128. Steiner, M., En-Najjary, T., Biersack, E.W.: A global view of KAD. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, pp. 117–122 (2007)

    Google Scholar 

  129. Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pp. 149–160 (2001)

    Google Scholar 

  130. Stoica, I., et al.: Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11(1), 17–32 (2003). https://doi.org/10.1109/TNET.2002.808407

    Article  Google Scholar 

  131. Sundie, J.M., Kenrick, D.T., Griskevicius, V., Tybur, J.M., Vohs, K.D., Beal, D.J.: Peacocks, porsches, and thorstein veblen: Conspicuous consumption as a sexual signaling system. J. Pers. Soc. Psychol. 100(4), 664 (2011)

    Article  Google Scholar 

  132. Tegeler, F., Fu, X.: SybilConf: computational puzzles for confining sybil attacks. In: Proceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM), pp. 1–2 (2010)

    Google Scholar 

  133. The Guardian, G.M.: The need to protect the internet from ‘astroturfing’ grows ever more urgent (2011). https://www.theguardian.com/environment/georgemonbiot/2011/feb/23/need-to-protect-internet-from-astroturfing

  134. Thorstein, V.: The Theory of the Leisure Class: An Economic Study of Institutions. BW Huebsch, New York (1912)

    Google Scholar 

  135. Urdaneta, G., Pierre, G., van Steen, M.: A survey of DHT security techniques. ACM Comput. Surv. 43(2), 1–53 (2011)

    Article  MATH  Google Scholar 

  136. von Ahn, L., Blum, M., Hopper, N.J., Langford, J.: CAPTCHA: using hard AI problems for security. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 294–311. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_18

    Chapter  Google Scholar 

  137. Von Ahn, L., Maurer, B., McMillen, C., Abraham, D., Blum, M.: reCAPTCHA: human-based character recognition via web security measures. Science 321(5895), 1465–1468 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  138. Walfish, M., Vutukuru, M., Balakrishnan, H., Karger, D., Shenker, S.: DDoS defense by offense. In: Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pp. 303–314 (2006)

    Google Scholar 

  139. Walfish, M., Vutukuru, M., Balakrishnan, H., Karger, D., Shenker, S.: DDoS defense by offense. ACM Trans. Comput. Syst. (TOCS) 28(1), 3 (2010)

    Article  Google Scholar 

  140. Wang, H., Zhu, Y., Hu, Y.: An efficient and secure peer-to-peer overlay network. In: Proceedings of the IEEE Conference on Local Computer Networks, pp. 764–771 (2005)

    Google Scholar 

  141. Wang, L., Kangasharju, J.: Measuring large-scale distributed systems: case of BitTorrent mainline DHT. In: IEEE 13th International Conference on Peer-to-Peer Computing (P2P), pp. 1–10 (2013)

    Google Scholar 

  142. Wang, X., Reiter, M.K.: Defending against denial-of-service attacks with puzzle auctions. In: Proceedings of the 2003 IEEE Symposium on Security and Privacy, p. 78 (2003)

    Google Scholar 

  143. Wei, W., Xu, F., Tan, C.C., Li, Q.: SybilDefender: a defense mechanism for sybil attacks in large social networks. IEEE Trans. Parallel Distrib. Syst. 24(12), 2492–2502 (2013)

    Article  Google Scholar 

  144. Wu, Y., Ngai, E.W., Wu, P., Wu, C.: Fake online reviews: literature review, synthesis, and directions for future research. Decis. Support Syst. 132, 113280 (2020). https://doi.org/10.1016/j.dss.2020.113280. http://www.sciencedirect.com/science/article/pii/S016792362030035X

    Article  Google Scholar 

  145. Xie, S., Wang, G., Lin, S., Yu, P.S.: Review spam detection via temporal pattern discovery. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 823–831. Association for Computing Machinery, New York (2012). https://doi.org/10.1145/2339530.2339662

  146. Xie, S., Wang, G., Lin, S., Yu, P.S.: Review spam detection via time series pattern discovery. In: Proceedings of the 21st International Conference on World Wide Web, WWW 2012 Companion, pp. 635–636. Association for Computing Machinery, New York (2012). https://doi.org/10.1145/2187980.2188164

  147. Yan, J., El Ahmad, A.S.: Captcha robustness: a security engineering perspective. Computer 44(2), 54–60 (2011)

    Article  Google Scholar 

  148. Yan, J., El Ahmad, A.S.: Usability of CAPTCHAs or usability issues in CAPTCHA design. In: Proceedings of the 4th Symposium on Usable Privacy and Security, SOUPS 2008, pp. 44–52. Association for Computing Machinery, New York (2008). https://doi.org/10.1145/1408664.1408671

  149. Yang, X., Wetherall, D., Anderson, T.: TVA: A DoS-limiting network architecture. IEEE/ACM Trans. Netw. 16(6), 1267–1280 (2008)

    Article  Google Scholar 

  150. Ma, Y., Li, F.: Detecting review spam: challenges and opportunities. In: 8th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), pp. 651–654 (2012)

    Google Scholar 

  151. Young, M., Kate, A., Goldberg, I., Karsten, M.: Towards practical communication in Byzantine-resistant DHTs. IEEE/ACM Trans. Netw. 21(1), 190–203 (2013)

    Article  Google Scholar 

  152. Yu, H.: Sybil defenses via social networks: a tutorial and survey. SIGACT News 42(3), 80–101 (2011)

    Article  Google Scholar 

  153. Yu, H., Gibbons, P.B., Kaminsky, M., Xiao, F.: SybilLimit: a near-optimal social network defense against sybil attacks. IEEE/ACM Trans. Netw. 18(3), 885–898 (2010)

    Article  Google Scholar 

  154. Yu, H., Kaminsky, M., Gibbons, P.B., Flaxman, A.: SybilGuard: defending against sybil attacks via social networks. In: Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM) vol. 36, pp. 267–278, August 2006

    Google Scholar 

  155. Yu, S., Thapngam, T., Liu, J., Wei, S., Zhou, W.: Discriminating DDoS flows from flash crowds using information distance. In: Proceedings of the Third International Conference on Network and System Security, pp. 351–356. IEEE (2009)

    Google Scholar 

  156. Zahavi, A.: Mate selection - a selection for a handicap. J. Theor. Biol. 53(1), 205–214 (1975)

    Article  Google Scholar 

  157. Zargar, S.T., Joshi, J., Tipper, D.: A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks. IEEE Commun. Surv. Tutor. 15(4), 2046–2069 (2013)

    Article  Google Scholar 

  158. Zatloukal, K.C., Harvey, N.J.A.: Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 308–317 (2004)

    Google Scholar 

Download references

Acknowledgements

We are grateful to the organizers of SIROCCO 2020 for inviting this paper, and we thank Valerie King for helpful feedback on our manuscript.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of New Mexico, Albuquerque, NM, USA

    Diksha Gupta & Jared Saia

  2. Department of Computer Science and Engineering, Mississippi State University, Mississippi State, MS, USA

    Maxwell Young

Authors
  1. Diksha Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jared Saia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maxwell Young
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Diksha Gupta .

Editor information

Editors and Affiliations

  1. Computer Science, CIDSE, Arizona State University, Tempe, AZ, USA

    Andrea Werneck Richa

  2. Department of Computer Science, Paderborn University, Paderborn, Germany

    Christian Scheideler

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gupta, D., Saia, J., Young, M. (2020). Resource Burning for Permissionless Systems (Invited Paper). In: Richa, A., Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2020. Lecture Notes in Computer Science(), vol 12156. Springer, Cham. https://doi.org/10.1007/978-3-030-54921-3_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-54921-3_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-54920-6

  • Online ISBN: 978-3-030-54921-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation