Do Bitcoin and Digital Currency Have a Future? - Harvard ...

The Proof is in the Pudding: Proofs of Work for Solving Discrete Logarithms

Cryptology ePrint Archive: Report 2018/939
Date: 2018-10-05
Author(s): Marcella Hastings, Nadia Heninger, Eric Wustrow

Link to Paper

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

  1. SpaceMint: A cryptocurrency based on proofs of space. In: FC’18. Springer (2018)
  2. Back, A.: Hashcash-a denial of service counter-measure (2002)
  3. Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: CRYPTO 2018. Springer International Publishing (2018)
  4. Barbulescu, R., Gaudry, P., Joux, A., Thom´e, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: EUROCRYPT’14 (2014)
  5. Barker, E., Chen, L., Roginsky, A., Vassilev, A., Davis, R.: SP 800-56A Revision 3. Recommendation for pair-wise key establishment schemes using discrete logarithm cryptography. National Institute of Standards & Technology (2018)
  6. Biryukov, A., Pustogarov, I.: Proof-of-work as anonymous micropayment: Rewarding a Tor relay. In: FC’15. Springer (2015)
  7. Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Rubinstein, A., Tromer, E.: The hunting of the SNARK. Journal of Cryptology 30(4) (2017)
  8. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (Jul 1970).
  9. Boneh, D., Bonneau, J., B¨unz, B., Fisch, B.: Verifiable delay functions. In: Annual International Cryptology Conference. pp. 757–788. Springer (2018)
  10. Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. International Journal of Applied Cryptography 2(3) (2012)
  11. Buterin, V.: Uncle rate and transaction fee analysis,
  12. Certicom ECC challenge (1997),, Updated 10 Nov 2009. Accessed via Web Archive
  13. Diffie, W., Hellman, M.: New directions in cryptography. IEEE transactions on Information Theory 22(6), 644–654 (1976)
  14. Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Annual International Cryptology Conference. pp. 139–147. Springer (1992)
  15. Ethereum Project: Ethereum white paper,\#modified-ghost-implementation
  16. Gordon, D.M.: Discrete logarithms in GF(P) using the number field sieve. SIAM J. Discret. Math. 6(1), 124–138 (Feb 1993).
  17. Jakobsson, M., Juels, A.: Proofs of work and bread pudding protocols. In: Secure Information Networks, pp. 258–272. Springer (1999)
  18. King, S.: Primecoin: Cryptocurrency with prime number proof-of-work (2013)
  19. Kleinjung, T., Diem, C., Lenstra, A.K., Priplata, C., Stahlke, C.: Computation of a 768-bit prime field discrete logarithm. In: EUROCRYPT’17. Springer (2017)
  20. Lepinski, M., Kent, S.: Additional Diffie-Hellman groups for use with IETF standards. RFC 5114, RFC Editor (2008),
  21. Lochter, M.: Blockchain as cryptanalytic tool. Cryptology ePrint Archive, Report 2018/893 (2018),
  22. Miller, A., Juels, A., Shi, E., Parno, B., Katz, J.: Permacoin: Repurposing Bitcoin work for data preservation. In: 2014 IEEE S&P. pp. 475–490. IEEE (2014)
  23. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. White paper (2008)
  24. National Institute of Standards and Technology: FIPS PUB 186-4: Digital Signature Standard (DSS). National Institute of Standards and Technology (Jul 2013)
  25. Percival, C., Josefsson, S.: The scrypt password-based key derivation function. RFC 7914, RFC Editor (Aug 2016),
  26. Pollard, J.M.: Monte carlo methods for index computation (mod p). In: Mathematics of Computation. vol. 32 (1978)
  27. Poon, J., Buterin, V.: Plasma: Scalable autonomous smart contracts (2017)
  28. Shanks, D.: Class number, a theory of factorization, and genera. In: Proc. of Symp. Math. Soc., 1971. vol. 20, pp. 41–440 (1971)
  29. Sompolinsky, Y., Zohar, A.: Secure high-rate transaction processing in Bitcoin. In: FC’15. pp. 507–527. Springer (2015)
  30. Teske, E.: Speeding up Pollard’s rho method for computing discrete logarithms. In: ANTS-III. pp. 541–554. Springer-Verlag, Berlin, Heidelberg (1998)
  31. Valenta, L., Adrian, D., Sanso, A., Cohney, S., Fried, J., Hastings, M., Halderman, J.A., Heninger, N.: Measuring small subgroup attacks against Diffie-Hellman. In: NDSS (2017)
  32. Valenta, L., Sullivan, N., Sanso, A., Heninger, N.: In search of CurveSwap: Measuring elliptic curve implementations in the wild. In: EuroS&P. IEEE (2018)
  33. Van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. Journal of cryptology 12(1), 1–28 (1999)
  34. de Vries, A.: Bitcoin’s growing energy problem. Joule 2(5), 801–805 (2018)
  35. Wenger, E., Wolfger, P.: Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs. Journal of Cryptographic Engineering (2016)
  36. Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: International workshop on selected areas in cryptography. Springer (1998)
  37. Wustrow, E., VanderSloot, B.: DDoSCoin: Cryptocurrency with a malicious proofof-work. In: WOOT (2016)
submitted by dj-gutz to myrXiv [link] [comments]

Bitcoin Rush  Episode #13 The Bitcoin Group #1 - Walmart and Bitcoin, and Bitcoin, Bitcoin Trust, Bitcoin Mining Bitcoin At $1 Million By 2020 Is Still Possible And Might ... Davi Barker Spreads Peace, Liberty, & Bitcoin thebitcoingroup - YouTube

Bitcoin Pro Review. No need to panic! If you don’t join the Bitcoin Pro scam trading platform a truly genuine money-making opportunity will come along. However, we can pretty much guarantee that if you do decide to signup and invest using this blacklisted software and fake trading app, you will end up losing your initial investment! David says: October 3, 2011 at 8:29 am. We have gold silver and bitcoins at so think of us as your monetary umbrella 🙂 I enjoyed reading your article and it makes me happy to see another person i respect understand bitcoin. pip010 says: October 3, 2011 at 9:48 am. first thing I realized about BC is that it still works on a good old economic principle : scarcity and demand ... The Bitcoin Trader is just one of those many scams which we have exposed for you. Read this Bitcoin Trader review to know why it is a scam. Bitcoin Trader Review. Starting off the review, it seems that the scammers have decided that they would use bitcoins as their base. Recently we have observed that all scams that come up revolve around bitcoins in some way or the other. The Bitcoin Trader ... Bitcoin Pro is one of the tools they’re using now to defraud people. It’s useless and worthless. Whatever lies the promoters are releasing has lost impact on smart investors. It’s only the newbies that are carelessly funding their crappy robot. If you doubt our findings, go ahead and read everything we discovered about Bitcoin Pro scam. Bitcoin Pro Scam Review! This platform is ... David Wittenburg, from his vantage point as a “former numismatist,” suggested that such currencies “arise in times of need (e.g., tokens when official currency is scarce) and they disappear when government offers a better alternative.” Many agreed with Dan Shypua that “the block-chain technology underpinning Bitcoin is the important part of the story. This technology will transform ...

[index] [35504] [823] [39484] [43221] [26936] [39774] [34717] [8726] [37186] [46518]

Bitcoin Rush Episode #13

Davi Barker - Authoritarian Sociopathy - Libertopia 2013 If you enjoyed this video and would like to see more, please support Red Pill Recording by donating Bitcoins to this address ... BUILD YOUR DREAM BUSINESS IN 8 WEEKS: 2021 SUMMIT TICKETS: NEW MASTERCLASS EACH WEEK: http://londonr... Btc Berlin Opening Party CryptoEdge Solutions TheOpenMinute with Davi Barker BlockCypher Petition to Israel Btc donations will be used w... This video is unavailable. Watch Queue Queue. Watch Queue Queue The Bitcoin Group, the American Original, for over the last ten seconds, the sharpest satoshis, the best bitcoins, the hardest crypocurrency talk.