Provable Cryptography for Bitcoin: An Introduction (Workbook)

This meticulously crafted material is available for download at this GitHub link. Designed to coincide with a multi-day interactive event, the workbook underwent substantial refinement and testing, thanks in large part to participant feedback. This process ensured that the content was both polished and practical, reflecting real-world application and understanding.

Diving into the content, the workbook spans a variety of topics crucial to grasping the nuances of Bitcoin cryptography. These include introductory concepts such as algorithms, hash functions, and asymptotic security, as well as more specialized subjects like reductions, commitments, accumulators, and one-time signatures. Notably, it delves into discrete logarithm problems, the random oracle model, programmable ROM, forking lemma, and signatures, with a particular emphasis on signatures with key tweaking. The structured approach aims to equip readers with a thorough background necessary for understanding advanced cryptographic signatures, especially those based on discrete logarithms, and to hone their ability to formalize security notions for cryptographic primitives—a skill vital for developing and reviewing cryptographic protocols.

One of the primary ambitions of this workbook is to provide a foundation that enables users to comprehend state-of-the-art papers on cryptographic signatures and their security proofs. It targets a detailed exploration of discrete-logarithm-based signatures, exemplified by the DahLIAS interactive aggregate signature scheme. Additionally, the workbook stresses the importance of accurately defining what a protocol intends to achieve through systematic introduction to key proof techniques and security formalization. By engaging with the exercises, readers gradually build intuition and hands-on experience with theoretical concepts, exploring how minor adjustments to security definitions or cryptographic schemes can significantly impact security proofs.

A notable achievement highlighted within the workbook is the development of a preliminary proof for the Schnorr sign-to-contract scheme—a feat not previously accomplished to the author's knowledge. This underscores the workbook's role not only as an educational tool but also as a platform for pioneering cryptographic research.

Regarding prerequisites, the workbook requires familiarity with modular arithmetic and basic probability theory, though an introductory understanding of cryptography is beneficial. For those looking to prepare adequately, Nadav Kohen's prework material offers an excellent starting point, accessible via this link.

The creators of the workbook encourage feedback, corrections, and suggestions to further refine this valuable resource. They invite contributions through issues or pull requests on the GitHub repository, reflecting a commitment to ongoing improvement and collaboration. This workbook stands as a robust resource for anyone eager to deepen their knowledge of the cryptographic principles that underpin Bitcoin and related technologies.