The Math Behind Bitcoin - CoinDesk

Compact Multi-Signatures for Smaller Blockchains

Cryptology ePrint Archive: Report 2018/483
Date: 2018-06-10
Author(s): Dan Boneh, Manu Drijvers, Gregory Neven

Link to Paper


Abstract
We construct new multi-signature schemes that provide new functionality. Our schemes are designed to reduce the size of the Bitcoin blockchain, but are useful in many other settings where multi-signatures are needed. All our constructions support both signature compression and public-key aggregation. Hence, to verify that a number of parties signed a common message m, the verifier only needs a short multi-signature, a short aggregation of their public keys, and the message m. We give new constructions that are derived from Schnorr signatures and from BLS signatures. Our constructions are in the plain public key model, meaning that users do not need to prove knowledge or possession of their secret key.
In addition, we construct the first short accountable-subgroup multi-signature (ASM) scheme. An ASM scheme enables any subset S of a set of n parties to sign a message m so that a valid signature discloses which subset generated the signature (hence the subset S is accountable for signing m). We construct the first ASM scheme where signature size is only O(k) bits over the description of S, where k is the security parameter. Similarly, the aggregate public key is only O(k) bits, independent of n. The signing process is non-interactive. Our ASM scheme is very practical and well suited for compressing the data needed to spend funds from a t-of-n Multisig Bitcoin address, for any (polynomial size) t and n.

References
  1. Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM CCS 10: 17th Conference on Computer and Communications Security. pp. 473–484. ACM Press, Chicago, Illinois, USA (Oct 4–8, 2010)
  2. Andresen, G.: m-of-n standard transactions. Bitcoin improvement proposal (BIP) 0011 (2011)
  3. Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 08: 15th Conference on Computer and Communications Security. pp. 449–458. ACM Press, Alexandria, Virginia, USA (Oct 27–31, 2008)
  4. Bagherzandi, A., Jarecki, S.: Multisignatures using proofs of secret key possession, as secure as the Diffie-Hellman problem. In: Ostrovsky, R., Prisco, R.D., Visconti, I. (eds.) SCN 08: 6th International Conference on Security in Communication Networks. Lecture Notes in Computer Science, vol. 5229, pp. 218–235. Springer, Heidelberg, Germany, Amalfi, Italy (Sep 10–12, 2008)
  5. Bansarkhani, R.E., Sturm, J.: An efficient lattice-based multisignature scheme with applications to bitcoins. In: Foresti, S., Persiano, G. (eds.) CANS 16: 15th International Conference on Cryptology and Network Security. Lecture Notes in Computer Science, vol. 10052, pp. 140–155. Springer, Heidelberg, Germany, Milan, Italy (Nov 14–16, 2016)
  6. Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003: 10th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 3006, pp. 17–25. Springer, Heidelberg, Germany, Ottawa, Ontario, Canada (Aug 14–15, 2004)
  7. Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007: 34th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 4596, pp. 411–422. Springer, Heidelberg, Germany, Wroclaw, Poland (Jul 9–13, 2007)
  8. Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSAinversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16(3), 185–215 (Jun 2003)
  9. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., Vimercati, S. (eds.) ACM CCS 06: 13th Conference on Computer and Communications Security. pp. 390–399. ACM Press, Alexandria, Virginia, USA (Oct 30 – Nov 3, 2006)
  10. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y. (ed.) PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 2567, pp. 31–46. Springer, Heidelberg, Germany, Miami, FL, USA (Jan 6–8, 2003)
  11. Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM CCS 07: 14th Conference on Computer and Communications Security. pp. 276–285. ACM Press, Alexandria, Virginia, USA (Oct 28–31, 2007)
  12. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) Advances in Cryptology – EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 416–432. Springer, Heidelberg, Germany, Warsaw, Poland (May 4–8, 2003)
  13. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) Advances in Cryptology – ASIACRYPT 2001. Lecture Notes in Computer Science, vol. 2248, pp. 514–532. Springer, Heidelberg, Germany, Gold Coast, Australia (Dec 9–13, 2001)
  14. Brogle, K., Goldberg, S., Reyzin, L.: Sequential aggregate signatures with lazy verification from trapdoor permutations - (extended abstract). In: Wang, X., Sako, K. (eds.) Advances in Cryptology – ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 644–662. Springer, Heidelberg, Germany, Beijing, China (Dec 2–6, 2012)
  15. Budroni, A., Pintore, F.: Efficient hash maps to G2 on BLS curves. Cryptology ePrint Archive, Report 2017/419 (2017), http://eprint.iacr.org/2017/419
  16. Burmester, M., Desmedt, Y., Doi, H., Mambo, M., Okamoto, E., Tada, M., Yoshifuji, Y.: A structured ElGamal-type multisignature scheme. In: Imai, H., Zheng, Y. (eds.) PKC 2000: 3rd International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 1751, pp. 466–483. Springer, Heidelberg, Germany, Melbourne, Victoria, Australia (Jan 18–20, 2000)
  17. Castelluccia, C., Jarecki, S., Kim, J., Tsudik, G.: A robust multisignatures scheme with applications to acknowledgment aggregation. In: Blundo, C., Cimato, S. (eds.) SCN 04: 4th International Conference on Security in Communication Networks. Lecture Notes in Computer Science, vol. 3352, pp. 193–207. Springer, Heidelberg, Germany, Amalfi, Italy (Sep 8–10, 2005)
  18. Certicom Research: Sec 2: Recommended elliptic curve domain parameters. Tech. rep., Certicom Research (2010)
  19. Chang, C.C., Leu, J.J., Huang, P.C., Lee, W.B.: A scheme for obtaining a message from the digital multisignature. In: Imai, H., Zheng, Y. (eds.) PKC’98: 1st International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 1431, pp. 154–163. Springer, Heidelberg, Germany, Pacifico Yokohama, Japan (Feb 5–6, 1998)
  20. Coron, J.S., Naccache, D.: Boneh et al.’s k-element aggregate extraction assumption is equivalent to the Diffie-Hellman assumption. In: Laih, C.S. (ed.) Advances in Cryptology – ASIACRYPT 2003. Lecture Notes in Computer Science, vol. 2894, pp. 392–397. Springer, Heidelberg, Germany, Taipei, Taiwan (Nov 30 – Dec 4, 2003)
  21. Drijvers, M., EdalatNejad, K., Ford, B., Neven, G.: Okamoto beats Schnorr: On the provable security of multi-signatures. Cryptology ePrint Archive, Report 2018/417 (2018), https://eprint.iacr.org/2018/417
  22. Fuentes-Casta˜neda, L., Knapp, E., Rodr´ıguez-Henr´ıquez, F.: Faster hashing to ð2. In: Miri, A., Vaudenay, S. (eds.) SAC 2011: 18th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 7118, pp. 412–430. Springer, Heidelberg, Germany, Toronto, Ontario, Canada (Aug 11–12, 2012)
  23. Gentry, C., O’Neill, A., Reyzin, L.: A unified framework for trapdoor-permutationbased sequential aggregate signatures. In: Abdalla, M., Dahab, R. (eds.) PKC 2018: 21st International Conference on Theory and Practice of Public Key Cryptography, Part II. Lecture Notes in Computer Science, vol. 10770, pp. 34–57. Springer, Heidelberg, Germany, Rio de Janeiro, Brazil (Mar 25–29, 2018)
  24. Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography. Lecture Notes in Computer Science, vol. 3958, pp. 257–273. Springer, Heidelberg, Germany, New York, NY, USA (Apr 24–26, 2006)
  25. Hardjono, T., Zheng, Y.: A practical digital multisignature scheme based on discrete logarithms. In: Seberry, J., Zheng, Y. (eds.) Advances in Cryptology – AUSCRYPT’92. Lecture Notes in Computer Science, vol. 718, pp. 122–132. Springer, Heidelberg, Germany, Gold Coast, Queensland, Australia (Dec 13–16, 1993)
  26. Harn, L.: Group-oriented (t, n) threshold digital signature scheme and digital multisignature. IEE Proceedings-Computers and Digital Techniques 141(5), 307–313 (1994)
  27. Horster, P., Michels, M., Petersen, H.: Meta-multisignature schemes based on the discrete logarithm problem. In: Information Securitythe Next Decade. pp. 128–142. Springer (1995)
  28. Itakura, K., Nakamura, K.: A public-key cryptosystem suitable for digital multisignatures. Tech. rep., NEC Research and Development (1983)
  29. Komano, Y., Ohta, K., Shimbo, A., Kawamura, S.: Formal security model of multisignatures. In: Katsikas, S.K., Lopez, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006: 9th International Conference on Information Security. Lecture Notes in Computer Science, vol. 4176, pp. 146–160. Springer, Heidelberg, Germany, Samos Island, Greece (Aug 30 – Sep 2, 2006)
  30. Le, D.P., Bonnecaze, A., Gabillon, A.: Multisignatures as secure as the DiffieHellman problem in the plain public-key model. In: Shacham, H., Waters, B. (eds.) PAIRING 2009: 3rd International Conference on Pairing-based Cryptography. Lecture Notes in Computer Science, vol. 5671, pp. 35–51. Springer, Heidelberg, Germany, Palo Alto, CA, USA (Aug 12–14, 2009)
  31. Li, C.M., Hwang, T., Lee, N.Y.: Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders. In: Santis, A.D. (ed.) Advances in Cryptology – EUROCRYPT’94. Lecture Notes in Computer Science, vol. 950, pp. 194–204. Springer, Heidelberg, Germany, Perugia, Italy (May 9–12, 1995)
  32. Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) Advances in Cryptology – EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 465–485. Springer, Heidelberg, Germany, St. Petersburg, Russia (May 28 – Jun 1, 2006)
  33. Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology – EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 74–90. Springer, Heidelberg, Germany, Interlaken, Switzerland (May 2–6, 2004)
  34. Ma, C., Weng, J., Li, Y., Deng, R.: Efficient discrete logarithm based multisignature scheme in the plain public key model. Designs, Codes and Cryptography 54(2), 121–133 (2010)
  35. Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple schnorr multi-signatures with applications to bitcoin. Cryptology ePrint Archive, Report 2018/068 (2018), https://eprint.iacr.org/2018/068/20180118:124757
  36. Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple schnorr multi-signatures with applications to bitcoin. Cryptology ePrint Archive, Report 2018/068 (2018), https://eprint.iacr.org/2018/068/20180520:191909
  37. Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) Advances in Cryptology – CRYPTO’87. Lecture Notes in Computer Science, vol. 293, pp. 369–378. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16–20, 1988)
  38. Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: Extended abstract. In: ACM CCS 01: 8th Conference on Computer and Communications Security. pp. 245–254. ACM Press, Philadelphia, PA, USA (Nov 5–8, 2001)
  39. Michels, M., Horster, P.: On the risk of disruption in several multiparty signature schemes. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 334–345. Springer (1996)
  40. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008), http://bitcoin.org/bitcoin.pdf
  41. Neven, G.: Efficient sequential aggregate signed data. In: Smart, N.P. (ed.) Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 52–69. Springer, Heidelberg, Germany, Istanbul, Turkey (Apr 13–17, 2008)
  42. Ohta, K., Okamoto, T.: A digital multisignature scheme based on the Fiat-Shamir scheme. In: Imai, H., Rivest, R.L., Matsumoto, T. (eds.) Advances in Cryptology – ASIACRYPT’91. Lecture Notes in Computer Science, vol. 739, pp. 139–148. Springer, Heidelberg, Germany, Fujiyoshida, Japan (Nov 11–14, 1993)
  43. Ohta, K., Okamoto, T.: Multi-signature schemes secure against active insider attacks. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 82(1), 21–31 (1999)
  44. Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Brickell, E.F. (ed.) Advances in Cryptology – CRYPTO’92. Lecture Notes in Computer Science, vol. 740, pp. 31–53. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16–20, 1993)
  45. Park, S., Park, S., Kim, K., Won, D.: Two efficient RSA multisignature schemes. In: Han, Y., Okamoto, T., Qing, S. (eds.) ICICS 97: 1st International Conference on Information and Communication Security. Lecture Notes in Computer Science, vol. 1334, pp. 217–222. Springer, Heidelberg, Germany, Beijing, China (Nov 11–14, 1997)
  46. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361–396 (2000)
  47. Ristenpart, T., Yilek, S.: The power of proofs-of-possession: Securing multiparty signatures against rogue-key attacks. In: Naor, M. (ed.) Advances in Cryptology – EUROCRYPT 2007. Lecture Notes in Computer Science, vol. 4515, pp. 228–245. Springer, Heidelberg, Germany, Barcelona, Spain (May 20–24, 2007)
  48. Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991)
  49. Scott, M., Benger, N., Charlemagne, M., Perez, L.J.D., Kachisa, E.J.: Fast hashing to g2 on pairing-friendly curves. In: Shacham, H., Waters, B. (eds.) PAIRING 2009: 3rd International Conference on Pairing-based Cryptography. Lecture Notes in Computer Science, vol. 5671, pp. 102–113. Springer, Heidelberg, Germany, Palo Alto, CA, USA (Aug 12–14, 2009)
submitted by dj-gutz to myrXiv [link] [comments]

A Formal Treatment of Hardware Wallets

Cryptology ePrint Archive: Report 2019/034
Date: 2019-01-14
Author(s): Myrto Arapinis, Andriana Gkaniatsou, Dimitris Karakostas, Aggelos Kiayias

Link to Paper


Abstract
Bitcoin, being the most successful cryptocurrency, has been repeatedly attacked with many users losing their funds. The industry's response to securing the user's assets is to offer tamper-resistant hardware wallets. Although such wallets are considered to be the most secure means for managing an account, no formal attempt has been previously done to identify, model and formally verify their properties. This paper provides the first formal model of the Bitcoin hardware wallet operations. We identify the properties and security parameters of a Bitcoin wallet and formally define them in the Universal Composition (UC) Framework. We present a modular treatment of a hardware wallet ecosystem, by realizing the wallet functionality in a hybrid setting defined by a set of protocols. This approach allows us to capture in detail the wallet's components, their interaction and the potential threats. We deduce the wallet's security by proving that it is secure under common cryptographic assumptions, provided that there is no deviation in the protocol execution. Finally, we define the attacks that are successful under a protocol deviation, and analyze the security of commercially available wallets.

References
  1. KeepKey. https://keepkey.com/ (2018), [Online; accessed 1-Sep-2018]
  2. Ledger Receive Attack. https://www.docdroid.net/Jug5LX3/ledger-receive-address-attack.pdf (2018), [Online; accessed 19-Sep-2018]
  3. Trezor. https://trezor.io/ (2018), [Online; accessed 1-Sep-2018]
  4. Alois, J.: Ethereum parity hack may impact eth 500.000 or 146 million (2017)
  5. Atzei, N., Bartoletti, M., Lande, S., Zunino, R.: A formal model of bitcoin transactions. Financial Cryptography and Data Security. LNCS, Springer (2018)
  6. Badertscher, C., Maurer, U., Tschudi, D., Zikas, V.: Bitcoin as a transaction ledger: A composable treatment. pp. 324–356 (2017)
  7. Bamert, T., Decker, C., Wattenhofer, R., Welten, S.: Bluewallet: The secure bitcoin wallet. In: International Workshop on Security and Trust Management. pp. 65–80. Springer (2014)
  8. Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J.A., Felten, E.W.: Sok: Research perspectives and challenges for bitcoin and cryptocurrencies. In: Security and Privacy (SP), 2015 IEEE Symposium on. pp. 104–121. IEEE (2015)
  9. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. pp. 136–145 (2001)
  10. Canetti, R.: Universally composable signatures, certification and authentication. Cryptology ePrint Archive, Report 2003/239 (2003), http://eprint.iacr.org/2003/239
  11. Canetti, R., Krawczyk, H.: Universally composable notions of key exchange and secure channels. Cryptology ePrint Archive, Report 2002/059 (2002), http://eprint.iacr.org/2002/059
  12. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: Analysis and applications. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 281–310. Springer (2015)
  13. Gentilal, M., Martins, P., Sousa, L.: Trustzone-backed bitcoin wallet. In: Proceedings of the Fourth Workshop on Cryptography and Security in Computing Systems. pp. 25–28. ACM (2017)
  14. Gkaniatsou, A., Arapinis, M., Kiayias, A.: Low-level attacks in bitcoin wallets. In: International Conference on Information Security. pp. 233–253. Springer (2017)
  15. Heilman, E., Kendler, A., Zohar, A.: Eclipse attacks on bitcoin’s peer-to-peer network.
  16. Hsiao, H.C., Lin, Y.H., Studer, A., Studer, C., Wang, K.H., Kikuchi, H., Perrig, A., Sun, H.M., Yang, B.Y.: A study of user-friendly hash comparison schemes. In: Computer Security Applications Conference, 2009. ACSAC’09. Annual. pp. 105–114. IEEE (2009)
  17. Huang, D.Y., Dharmdasani, H., Meiklejohn, S., Dave, V., Grier, C., McCoy, D., Savage, S., Weaver, N., Snoeren, A.C., Levchenko, K.: Botcoin: Monetizing stolen cycles. In: NDSS. Citeseer (2014)
  18. Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ecdsa). International journal of information security 1(1), 36–63 (2001)
  19. Lim, I.K., Kim, Y.H., Lee, J.G., Lee, J.P., Nam-Gung, H., Lee, J.K.: The analysis and countermeasures on security breach of bitcoin. In: International Conference on Computational Science and Its Applications. pp. 720–732. Springer (2014)
  20. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008)
  21. Parker, L.: Bitcoin stealing malware evolves again. https://bravenewcoin.com/news/bitcoin-stealing-malware-evolves-again/ (2016), [Online; accessed 1-Sep-2018]
  22. Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 643–673. Springer (2017)
  23. Penard, W., van Werkhoven, T.: On the secure hash algorithm family. Cryptography in Context pp. 1–18 (2008)
  24. Tan, J., Bauer, L., Bonneau, J., Cranor, L.F., Thomas, J., Ur, B.: Can unicorns help users compare crypto key fingerprints? In: Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems. pp. 3787–3798. ACM (2017)
  25. Uzun, E., Karvonen, K., Asokan, N.: Usability analysis of secure pairing methods. In: International Conference on Financial Cryptography and Data Security. pp. 307–324. Springer (2007)
  26. Vasek, M., Bonneau, J., Ryan Castellucci, C.K., Moore, T.: The bitcoin brain drain: a short paper on the use and abuse of bitcoin brain wallets. Financial Cryptography and Data Security, Lecture Notes in Computer Science. Springer (2016)
  27. Volotikin, S.: Software attacks on hardware wallets. Black Hat USA 2018 (2018)
  28. Wuille, P.: Hierarchical Deterministic Wallets. https://en.bitcoin.it/wiki/BIP_0032 (2018), [Online; accessed 1-Sep-2018]
submitted by dj-gutz to myrXiv [link] [comments]

It is time to usher in a new phase of Bitcoin development - based not on crypto & hashing & networking (that stuff's already done), but based on clever refactorings of datastructures in pursuit of massive and perhaps unlimited new forms of scaling

Debates among devs are normal and important.
Debates between programmers are the epitome of decentralized development and as such they are arguably the most important mechanism that will ensure the ongoing success of the Bitcoin (or cryptocurrencies) project.
Therefore, we would be wise to encourage such debates, rather than trying to make them go away by calling them "personal attacks".
In the real world, there aren't a whole lot of different ways to hammer a nail into a board or pour cement into a hole - but in the abstract world of mathematics and programming, there are many, many different ways to represent and manipulate a data structure, limited only by our imaginations, so it is actually appropriate to expect and even demand lots of jostling and critiquing from our programmers as they "try to invent a better mousetrap."
In fact, this is the kind of informal jockeying and shop talk that always has gone on and always will go on among mathematicians and programmers - and quite rightly so, because it is precisely the mechanism whereby they maintain order among their ranks, by making subtle and cogent observations about who knows what.
A famous example of this typical sort of jockeying and shop talk can be seen elsewhere in the ongoing debates between programmers of the "procedural" / "object-oriented" school (C/C++, Java) versus the "functional" school (Haskell, ML). It's always quite an eye-opener for a procedural programmer who's been using "loops" all their life, when they finally discover how to use an "iterator" in functional programming. They both "accomplish" the same thing of course - but in radically and subtly different ways, since an iterator in a functional language is a "first-class citizen" which can be passed around as an argument parameterizing a function, etc. - allowing much more compact and expressive (and sometimes even more efficient) code.
Different Bitcoin dev skill sets are required for different stages of Bitcoin's life cycle
An example of the debate between various devs can be seen here:
It is "clear that Greg Maxwell actually has a fairly superficial understanding of large swaths of computer science, information theory, physics and mathematics."- Dr. Peter Rizun (managing editor of the journal Ledger)
https://np.reddit.com/btc/comments/3xok2o/it_is_clear_that_greg_maxwell_unullc_actually_has/
What Peter R is saying here is simply that a different skill set is needed to usefully contribute to Bitcoin development now that it has moved well beyond its "proof-of-concept and initial rollout" stages (hey, this thing actually works) and is now trying to move into its "massive scaling" stages (let's try to roll this thing out to millions or billions of people).
Bitcoin's "proof-of-concept and initial rollout" stages
Initially, during the "proof-of-concept and initial rollout" stages, the skill set that was required to be a "Bitcoin dev" merely involved knowing enough cryptography, hashing, networking, "game theory", rudimentary economics, and C/C++ programming in order to be able to understand Satoshi's original vision and implementation, doing some simple and obvious refactorings, cleanups and optimizations while respecting the overall design decisions captured in the original C/C++ code, and maintaining the brilliant "game theory" incentives baked therein - the most notable of all being of course that thing which some mathematicians have taken to calling "Nakamoto Consensus" (which could be seen as a useful emerging mathematical-historical term along the lines of Nash Equilibrium, etc.) - ie, Satoshi's brilliant cobbling-together of several existing concepts from crypto and hashing and game theory and rudimentary economics in order to provide a good-enough solution to the long-standing Byzantine Generals Problem which mathematicians and programmers had heretofore (for decades) considered to be unsolvable.
In particular, during the "proof-of-concept and initial rollout" stages, the crypto and hashing stuff is all pretty much done: the elliptic-curve cryptography has been decided upon (and by the way Satoshi very carefully managed to pick one of the few elliptic curves that is NSA-proof) and the various hashing algorithms (SHA, RIPE) are actually quite old from previous work, and the recipe for combining them all together has been battle-tested and it should work fine for the next few decades or so (assuming that practical quantum computing is probably not going come along on that time scale).
Similar, during the "proof-of-concept and initial rollout" stages, the networking and incentives and game theory are all pretty much done: the way the mempool gets relayed, the way miners race to solve blocks while trying to minimize orphaning, and the incentives provided currently mainly by the coinbase subsidy and to be provided much later (after more halvings and/or more increases in volume and price) mainly by transaction fees - this stuff has also been decided upon, and is working well enough (within the parameters of our existing imperfect regulatory and economic landscape and networking topology, where things such as ASIC chips, cheap electricity and cooling in China, and the Great Firewall of China have come to the fore as major factors driving decisions about who mines where).
Bitcoin's "massive scaling" stages
Now, as we attempt to enter the "massive scaling" stage, a different skill set is required. As I've outlined above, the crypto and the hashing and the incentives are all pretty much done now - and mining has become concentrated where it's most profitable, and we are actually starting to hit the "capacity ceiling" a few times (up till now just some spam attacks and stress tests - but soon, more worryingly, possibly even with the next few months, really hitting the capacity ceiling with "real" transactions).
Early scaling debates centered around blocksize
And so, for the past year, we've gone through the never-ending debates on scaling - most of them focusing up till now (perhaps rather naïvely, some have argued) on the notion of "maximum blocksize", which was set at 1 MB by Satoshi as a temporary anti-spam kludge.
The smallblock proponents have been claiming that pretty much all "scaling solutions" based on simply increasing the maximum blocksize could have bad effects such as decreasing the number of nodes (decreasing this important type of decentralization) or increasing the number of orphans (decreasing profits for certain miners) - so they have been quite adamant in resisting any such proposals.
Meanwhile the bigblock proponents have been claiming that increased adoption (higher price and volume) should be more than enough to eventually offset / counteract any supposed decrease in node count and miner profits that might happen immediately after bigblocks would be rolled out.
For the most part, both sides appear to be arguing in good faith (with the possible exception of private companies hoping to be able to peddle future, for-profit "solutions" to the "problem" of artificially scarce level-one on-chain block space - eg, Blockstream's Lightning Network) - so the battles have raged on, the community has become divided, and investors are becoming hesitant.
New approaches transcending the blocksize debates
In this mathematical-historical context, it is important to understand the fundamental difference in approach taken by Peter__R. He is neither arguing for smallblocks nor for bigblocks nor for a level-2 solution. He is instead (with his recently released groundbreaking paper on Subchains - not to be confused with sidechains or treechains =) sidestepping and transcending those approaches to focus on an entirely different, heretofore largely unexplored approach to the problem - the novel concept of "nested subchains":
By nesting subchains, weak block confirmation times approaching the theoretical limits imposed by speed-of-light constraints would become possible with future technology improvements.
Now, this is a new paper, and it will still undergo a lot of peer review before we can be sure that it can deliver on what it promises. But at first glance, it is very promising - not least of all because it is attacking the whole problem of "scaling" from a new and possibly highly productive angle: not involving bigblocks or smallblocks or bolt-ons (LN) but instead examining the novel possibility of decomposing the monolithic "blocks" being appended to the "chain" into some sort of "substructures" ("subchains"), in the hopes that this may permit some sort of efficiencies and economies at the network relay level.
"Substructural refactoring"-based approaches
So what we are seeing here is essentially a different mathematical technique being applied, for the first time, to a different part of the problem in an attempt to provide a "massive scaling" solution for Bitcoin. (I'm not sure what to call this technique - but the name "substructural refactoring" is the first thing that comes to mind.)
While there had indeed been some sporadic discussions among existing devs along the lines of "weak blocks" and "subchains", this paper from Peter R is apparently the first time that anyone has made a comprehensive attempt to tie all the ideas together in a serious presentation including, in particular, detailed analysis of how subchains would dovetail with infrastructure (bandwidth and processing) constraints and miner incentives in order for this to actually work in practice.
Graphs reminiscent of elasticity and equilibrium graphs from economics
For example, if you skim through the PDF you'll see the kinds of graphs you often see in economics papers involving concepts such as elasticity and equilibrium and optimization (eg, a graph where there's a "gap" between two curves which we're hoping will decrease in size, or another graph where there's a descending curve and an ascending curve which intersect at some presumably optimum point).
Now, you can see from the vagueness of some my arguments and illustrations above that I am by no means an expert in the mathematics and economics involved here, but am instead merely a curious bystander with only a hobbyist's understanding of these complex subjects (although a rather mature one at that, having worked most of my long and chequered career in math and programming and finance).
But I am fairly confident that what we are seeing here is the emergence of a new sort of "skill set" which will be needed from the kind of Bitcoin developers who can lead us to a successful future where millions or billions of people (and perhaps also machines) are able to transact routinely and directly on the blockchain.
And if a developer like Peter R wants to direct some criticism at another developer who has failed to have these insights, I think that is a natural manifestation of human ego and competitiveness which is healthy to keep these guys on their toes.
A new era of Bitcoin development
The time for tweaking the crypto and hashing is long past - which means that the skills of guys like nullc and petertodd may no longer as important as they were in the past. (In fact, there are entirely other objections can be raised against Peter Todd, given his proclivity for proving that he can, at the mathematical level, break systems which actually do work "good enough" by relying on constraints imposed at the "social level" - a level which PTodd evidently does not much believe in. For the most egregious example of this, see his decision to force his Opt-In (soon to become On-By-Default) Full RBF - which breaks existing "good-enough" risk mitigation practices many business had up till now relied on to profitably use zero-conf for retail.)
Likewise the skills of adam3us may also not be as important as they were in the past: he is, after all, the guy who invented ecash, so he is clearly a brilliant cryptographer and pioneer cypherpunk who laid the groundwork for what Bitcoin has become today, but it is unclear whether he now has (or ever had) the vision to appreciate how big (and fast) Bitcoin can become (at "level 1" - ie, directly on the blockchain itself).
In this regard, it is important to point out the serious lack of vision and optimism on the part of nullc and petertodd and adam3us:
TL;DR: Times are a-changin'. The old dev skill sets for Bitcoin's early years (crypto, hashing, networking) are becoming less important, while new dev skill sets are becoming more important (such as something one might call "substructural refactoring"). We should encourage competition as new devs emerge who have these new skill sets, because they may be the way out of the "dead end" of the blocksize-based approaches to scaling, opening up massive and perhaps unlimited new forms of "fractal-like" scaling instead.
submitted by ydtm to btc [link] [comments]

Elliptic Curve Cryptography Overview - YouTube Elliptic Curves - Computerphile - YouTube Math Behind Bitcoin and Elliptic Curve Cryptography ... Elliptic Curve Diffie Hellman - YouTube KenFM - YouTube

Currently Bitcoin uses secp256k1 with the ECDSA algorithm, though the same curve with the same public/private keys can be used in some other algorithms such as Schnorr. secp256k1 was almost never used before Bitcoin became popular, but it is now gaining in popularity due to its several nice properties. Most commonly-used curves have a random structure, but secp256k1 was constructed in a ... In the particular case of bitcoin, the elliptic curve that is used is known as the Koblitz curve secp256k1, ... and two other parameters: the difficulty and a nonce (a number used only once). These two parameters play a very important role in the bitcoin mining process. By its own design, the time elapsed between the inclusion of two consecutive blocks in the bitcoin blockchain should be about ... the elliptic curve secp256k1 can be considered as somewhat ’rigid’ meaning that almost all parameters are transparent to the public and hence can be assumed to benotgeneratedinordertobeweak. Bitcoin uses elliptic curve cryptography for its keys and signatures, but the specific secp256k1 curve used is rather unusual. The ECDSA keys used to generate Bitcoin addresses and sign ... Elliptic Curve Digital Signatures and Their Application in the Bitcoin Crypto-currency Transactions Benjamin K. Kikwai 16 October 2017 Abstract- . The Elliptic Curve Digital Signature Al- gorithm (ECDSA), de nes a technique for generating and validating digital signatures. We start by review-ing the mathematics behind the Digital Signature Algo-rithm (DSA) and its elliptic curve analogue ...

[index] [21623] [10824] [50322] [24052] [47833] [28754] [29244] [4620] [14389] [14961]

Elliptic Curve Cryptography Overview - YouTube

Learn more advanced front-end and full-stack development at: https://www.fullstackacademy.com Elliptic Curve Cryptography (ECC) is a type of public key crypt... Elliptic curve cryptography is the backbone behind bitcoin technology and other crypto currencies, especially when it comes to to protecting your digital ass... Elliptic Curve Cryptography (ECC) Parameters and Types: secp256k1, Curve 25519, and NIST - Duration: 12:37. Bill Buchanan OBE 3,064 views. 12:37. Elliptic Curve Cryptography Overview - Duration ... This feature is not available right now. Please try again later. A short video I put together that describes the basics of the Elliptic Curve Diffie-Hellman protocol for key exchanges. There is an error at around 5:30 wher...

#