Skip to content

Instantly share code, notes, and snippets.

@ChristopherA
Last active December 13, 2024 23:38
Show Gist options
  • Save ChristopherA/82e1bc62be7e7be922dfe02202688922 to your computer and use it in GitHub Desktop.
Save ChristopherA/82e1bc62be7e7be922dfe02202688922 to your computer and use it in GitHub Desktop.
Schnorr Opportunities

Links to Schnorr Opportunities

OVERVIEW: A hub of links exploring the potential of Schnorr signatures and related cryptographic innovations. It highlights their applications in enhancing efficiency, privacy, and functionality across blockchain systems, particularly Bitcoin, while also emphasizing broader implications for secure protocols, multisignature schemes, and decentralized technologies. These annotated links are to foundational articles, research, and discussions, offering insights into the transformative opportunities these Schnorr related opportunities present.

Status & Copyright

Annotated Links

Schnorr Basics

Allen-Schnorr-Intro-2023

  • A Layperson’s Intro to Schnorr (2023-10-24). [web article]. Allen, Christopher. Retrieved 2024-12-12 from Blockchain Commons: https://www.BlockchainCommons.com/musings/Schnorr-Intro/. Cross-posted at Life With Alacrity: https://www.LifeWithAlacrity.com/article/musings-schnorr/.

    TAGS: #SchnorrSignatures #DigitalSignatures #Cryptography #SignatureAggregation #ThresholdSignatures #BlindSignatures #AdapterSignatures #FiniteFields #EllipticCurveCryptography #Bitcoin

    SHORT ABSTRACT: "This article provides an accessible introduction to Schnorr signatures, highlighting their compactness, efficiency, and advanced cryptographic capabilities such as signature aggregation, threshold signatures, and blind signatures. It also delves into the mathematical foundations underpinning Schnorr signatures, including finite fields and elliptic curve cryptography."

    KEY POINTS:

    • Compactness: Schnorr signatures are small, even when there are multiple signers.
    • Signature Aggregation: Multiple signatures can be aggregated together and look exactly like a single signature.
    • Faster Verification: Due to their small size and aggregation capabilities, Schnorr signatures can be verified quickly.
    • Threshold Signatures: Multisignatures requiring a certain quorum of participants are possible.
    • Blind Signatures: Signatures can be made while hiding the content.
    • Adapter Signatures: Signatures can be hidden by other values.
    • Mathematical Foundation: Schnorr signatures depend on finite field math and elliptic curves, such as Bitcoin’s secp256k1.
    • Schnorr in a Nutshell (8 Bits): Uses simple math in a relatable 8-bit context to explain Schnorr's compactness, aggregation, and verification.

    KEY QUOTES:

    • "Schnorr signatures have been a long time coming, but now that they’re finally here, they open up broad new cryptographic frontiers..."
    • "I discovered RSA, which secures its signatures using prime numbers, in college. But it was when I later encountered Schnorr, built on finite fields, that I met the first cryptography that I truly fell in love with."
    • "Beyond all of their new benefits, I fell in love with Schnorr signatures because they were elegant."
    • "The aggregation of signatures was done with simple mathematical operations. You added two signatures together and they were aggregated!"
    • "Think of finite fields as domains where numbers play by a unique set of rules."
    • "Schnorr in 8 Bits: Add up 2 + 3, modulo 7 (5). It's the simplicity and elegance of modular arithmetic that powers Schnorr's capabilities."
    • "Schnorr’s aggregation capabilities could redefine the scalability of blockchain systems by significantly reducing the size of transactions."

Adapter Signatures

  • Adaptor Signatures (n.d.). [web article]. Bitcoin Optech. Retrieved 2024-10-09 from: https://bitcoinops.org/en/topics/adaptor-signatures/.

    TAGS: #AdaptorSignatures #Bitcoin #SchnorrSignatures #CryptographicProtocols #PrivacyEnhancement #AtomicSwaps #BitcoinContracts #CryptographicAdaptors #DigitalSignatures #ScriptlessScripts

    SHORT ABSTRACT: "Adaptor signatures are cryptographic tools that commit to a hidden value, revealing it only when combined with a corresponding signature. They offer efficiency and privacy advantages for Bitcoin contracts compared to traditional hashlocks, playing a critical role in advanced mechanisms like atomic swaps, coinswaps, and multiparty contracts."

    KEY POINTS:

    • Efficiency Over Hashlocks: Adaptor signatures do not need to be published on-chain, unlike hashlocks, which makes them more efficient and private.
    • Coinswap Mechanism: Describes how two parties can use adaptors to securely commit to transactions, ensuring atomicity in a payment set.
    • Hidden Value Commitment: The cryptographic commitment made by adaptor signatures ensures that only the intended recipient can derive the hidden value.
    • Privacy Improvement: Since adaptor signatures are indistinguishable from regular digital signatures, they enhance privacy compared to traditional locking methods.
    • Use of Schnorr Signatures: The examples rely on Schnorr signatures (BIP340), which allows efficient and flexible manipulation in Bitcoin transactions.
    • Multiparty Signatures Combination: Adaptor signatures are often combined with multiparty signatures to prevent double-spending and enhance security in contracts.
    • Applicability in Various Use Cases: Potential use in payment channels, discreet log contracts, and other advanced Bitcoin use cases where locking mechanisms are needed.
    • Timelocked Refund: The mechanism can incorporate a timelock to ensure refund options if one party refuses to sign.
    • Multiparty ECDSA Challenges: Adaptor signatures could be implemented with ECDSA but require novel, potentially slower or less efficient algorithms.

    KEY QUOTES:

    • "Adaptor signatures are auxiliary signature data that commit to a hidden value. When an adaptor is combined with a corresponding signature, it reveals the hidden value."
    • "Signature adaptors never need to be published on-chain, giving adaptors significant efficiency and privacy advantages over hashlocks."
    • "Adaptor signatures are usually proposed to be combined with multiparty signature schemes such as MuSig to allow the published signature to look like a single-party signature, enhancing privacy and efficiency."
    • "This makes adaptors a powerful tool for implementing locking in bitcoin contracts."
    • "Contracts in Bitcoin often require a locking mechanism to ensure the atomicity of a set of payments—either all the payments succeed or all of them fail."
  • Scriptless Scripts (2017-05-10). [presentation slides]. Poelstra, Andrew. Milan Bitcoin Meetup. Retrieved 2024-12-05 from: https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2017-05-milan-meetup/slides.pdf.

    TAGS: #ScriptlessScripts #Mimblewimble #BitcoinPrivacy #CryptographicProtocols #DigitalSignatures #SchnorrSignatures #AtomicSwaps #ZeroKnowledgePayments #Cryptocurrency #BlockchainScaling

    SHORT ABSTRACT: "This presentation introduces scriptless scripts, a cryptographic method that enhances privacy and scalability for blockchain transactions. It explains how traditional scripts used in Bitcoin compromise privacy and demonstrates how scriptless scripts, through Schnorr signatures, enable more efficient smart contracts while preserving transaction confidentiality."

    KEY POINTS:

    • Definition of Scriptless Scripts: Scriptless scripts leverage digital signatures for the enforcement of smart contracts without exposing the contract details on the blockchain.
    • Mimblewimble's Design: Mimblewimble is introduced as a blockchain design entirely based on scriptless scripts, significantly improving privacy and scalability.
    • Privacy Advantages: Compared to traditional Bitcoin scripting, scriptless scripts minimize the visibility of transaction details, enhancing privacy.
    • Schnorr Signatures Utilization: Uses Schnorr signatures to make transactions more compact and prevent exposure of contract logic to the blockchain network.
    • Adaptor Signatures: Adaptor signatures allow for conditional payments and other complex operations while maintaining the confidentiality of the underlying contract logic.
    • Atomic Cross-chain Swaps: Details how scriptless scripts can be used to implement atomic swaps across different blockchain networks, improving interoperability.
    • Denial and Deniability: The use of adaptor signatures provides deniability, making transactions appear unrelated even if they are linked.
    • Re-blindability Feature: Adaptor signatures can be re-blinded, enhancing the unlinkability of transactions across multiple stages.
    • Open Challenges: Notes ongoing challenges, including the adaptation of ECDSA, managing locktimes, and understanding the broader implications of scriptless scripts.
    • Future Potential: Suggests that Mimblewimble, combined with other scriptless constructions, could become a comprehensive solution for secure, private, and scalable blockchain transactions.

    KEY QUOTES:

    • "Scriptless scripts: magicking digital signatures so that they can only be created by faithful execution of a smart contract."
    • "With scriptless scripts, the only visible things are public keys (i.e., uniformly random curvepoints) and digital signatures."
    • "Zero-Knowledge Contingent payments... use the signature hash in place of H and now you have a scriptless script ZKCP."
    • "Adaptor signatures work across blockchains, even if they use different EC groups, though this requires a bit more work."
    • "Mimblewimble is the ultimate scriptless script... adding validity requirements with zero overhead or even visibility to the network."
  • One-Time Verifiably Encrypted Signatures: A.K.A. Adaptor Signatures (October 2019). [academic paper]. Fournier, Lloyd. Retrieved 2024-10-09 from GitHub repository "LLFourn/one-time-VES": https://github.com/LLFourn/one-time-VES/blob/master/main.pdf.

    TAGS: #Bitcoin #Cryptography #AdaptorSignatures #VerifiablyEncryptedSignatures #Layer2Protocols #SmartContracts #ScriptlessScripts #ECDSA #SchnorrSignatures #CryptographicSecurity #FairSignatureExchange

    SHORT ABSTRACT: "This paper provides a formal analysis of adaptor signatures as an isolated cryptographic primitive within Bitcoin-like ledgers, introducing the concept of one-time verifiably encrypted signatures (one-time VES). It contrasts them with the well-established notion of verifiably encrypted signatures (VES) and demonstrates how Schnorr and ECDSA adaptor signature schemes can be utilized to enhance layer-2 protocol functionalities, even achieving fair signature exchange without trusted third parties."

    KEY POINTS:

    • Adaptor Signatures as Smart Contracts: Demonstrates how adaptor signatures achieve smart contract-like behavior without utilizing Bitcoin's native script language, allowing for "scriptless scripts."
    • One-Time VES Concept: Introduces one-time verifiably encrypted signatures, emphasizing their unique property of decryption key recovery upon signature reveal.
    • Security Model for Bitcoin Layer-2: Revises the existing definitions of verifiably encrypted signatures to fit the Bitcoin layer-2 model, removing assumptions about trusted third parties.
    • Schnorr vs ECDSA: Compares Schnorr and ECDSA adaptor signature schemes, noting the practical viability of Schnorr and highlighting a non-fatal flaw in ECDSA’s implementation.
    • Applications in Scriptless Protocols: Surveys the use of one-time VES in atomic swaps, payment channels, discreet log contracts, and other scriptless layer-2 protocols, demonstrating efficiency and confidentiality improvements.
    • ECDSA One-Time VES Challenges: Identifies that ECDSA one-time VES unintentionally leaks Diffie-Hellman tuples but remains suitable for certain layer-2 applications.
    • Semi-Scriptless Protocols: Proposes a workaround for current Bitcoin infrastructure, allowing protocols to use a simplified OP_CHECKMULTISIG to implement scriptless behavior while waiting for a Schnorr upgrade.
    • Two-Party Encrypted Signing Protocol: Describes the use of a two-party encrypted signing protocol, particularly with the Schnorr scheme, for achieving scriptless signatures.
    • Fair Signature Exchange Without Trusted Parties: Highlights the ability of one-time VES to achieve fair signature exchange without a trusted third party, critical in decentralized environments.

    KEY QUOTES:

    • "On Bitcoin-like ledgers, smart contract functionality can be realised without using the ledger's native smart contract language through the 'adaptor signature' technique."

    • "An adaptor signature is a kind of partial signature that, if completed, will reveal valuable information to the signer."

    • "In this work, we conduct the first formal analysis of the adaptor signature as an isolated primitive."

    • "We find that it offers similar functionality to the already well-established concept of verifiably encrypted signatures (VES) with one notable difference: the decryption key can be recovered from the ciphertext and the decrypted signature."

    • "To capture this property, we formally introduce the notion of one-time verifiably encrypted signatures."

    • "Schnorr admits a less elegant interactive multi-signature scheme, but a very efficient one-time VES scheme. Additionally, it should be possible to create a Schnorr (not one-time) VES scheme with general zero-knowledge proof techniques where as a one-time VES for BLS looks much less likely. This trade off deserves further exploration."

  • Adaptors Generalised (2024-10-08). [blog post]. AdamISZ. Retrieved 2024-12-05 from Waxwing's Blog: https://reyify.com/blog/adaptors-generalised/.

    TAGS: #AdaptorSignatures #Bitcoin #CryptographicAdaptors #MultidimensionalCryptography #SigmaProtocols #ZeroKnowledgeProofs #CryptographicVerification #DiscreteLogProblem #EllipticCurve #DigitalSignatures

    SHORT ABSTRACT: "The author delves into the generalization of adaptor signatures for Bitcoin and beyond, focusing on multidimensional adaptors. The discussion includes adapting Σ-protocols for alternate homomorphisms and explores the possibility of generalizing adaptors for discrete log equivalences (DLEQ). The blog post presents potential constructions for verification mechanisms directly on the blockchain and evaluates their limitations and possibilities."

    KEY POINTS:

    • Multidimensional Adaptors: Discusses extending adaptors from one-dimensional to multidimensional applications, especially for cryptographic commitments.
    • Representation Problem: Highlights the difficulty of finding discrete log relationships with alternate generators, crucial to adaptor security.
    • Σ-Protocols for Alternate Homomorphisms: Uses adapted Σ-protocols involving non-standard generators, maintaining properties like soundness and zero-knowledge.
    • Verification with Fiat-Shamir Heuristic: Uses hash challenges as part of the Fiat-Shamir heuristic for building adaptors.
    • Discrete Log Equivalence (DLEQ): Examines applying adaptors to DLEQ proofs, outlining challenges in ensuring valid verification.
    • Half-Adaptor for DLEQ: Proposes a "half-adaptor" approach for partial proof of discrete log equivalence, exploring its security.
    • Applicability in Bitcoin: Considers practical on-chain verification scenarios and the challenges posed by interactivity in the verification process.
    • Interactive vs Non-Interactive Proofs: Highlights limitations of the current interactive nature of adaptors and the desire for direct blockchain enforceability.

    KEY QUOTES:

    • "Having the proof of a statement over arbitrary bases/generators be able to 'unlock' a payment has enormous potential applications, but one usually imagines the verification occurring directly onchain."
    • "The security of this construction relies on the hardness of the representation problem, which underpins the entire multidimensional adaptor concept."
    • "This multidimensional adaptor never serves as a proof of knowledge, which is a crucial limitation when considering the direct enforceability of such schemes in cryptographic applications."
    • "The interesting aspect here is that multidimensionality seems to give us some flexibility that one-dimensional adaptors simply don’t have, allowing for richer proof structures, even if they're more complex to handle."
    • "Adaptor signatures are indeed a bridge: they're somewhere between full non-interactive proof of knowledge and a mere demonstration of cooperation, and that makes them particularly intriguing for practical use cases."
  • Bitcoin PIPEs: Covenants and ZKPs on Bitcoin Without Soft Fork (2024-05-01). [PDF]. Komarov, Mikhail. Retrieved 2024-12-05 from allocin.it: https://www.allocin.it/uploads/placeholder-bitcoin.pdf.

    TAGS: #BitcoinPIPE #ZeroKnowledgeProofs #BitcoinL1 #BitcoinCovenants #FHMIPE #PlaceholderProofSystem #SchnorrSignatures #CryptographicVerification #BitcoinScript #PolynomialEncryption

    SHORT ABSTRACT: "This paper proposes a new approach for enabling the verification of zero-knowledge proofs (ZKPs) on Bitcoin's Layer 1 using Bitcoin PIPEs, without requiring a soft fork. The author presents a framework that incorporates Polynomial Inner Product Encryption (PIPE) for ZKP verification and suggests a method to emulate missing Bitcoin covenants. This approach aims to overcome the limitations of Bitcoin Script and open new possibilities for implementing zkRollups and other application-specific covenants on Bitcoin."

    KEY POINTS:

    • Covenant Emulation: Proposes emulating missing covenants (e.g., CAT) using Bitcoin PIPEs, avoiding a soft fork to enable ZKP verification on Bitcoin's L1.
    • FH-MIPE for Placeholder Verification: Uses Function-Hiding Multi-Input Predicate Encryption (FH-MIPE) to create a new covenant mechanism that allows verifying Placeholder proofs on Bitcoin.
    • Polynomial Inner Product Encryption: Introduces a PIPE-based verification scheme that emulates the functionality of absent opcodes like OP_CAT, crucial for proof verification.
    • Complex Verification without Protocol Upgrade: Describes a verification method that doesn’t require a Bitcoin protocol upgrade but instead utilizes cryptographic techniques to overcome script limitations.
    • Application-Specific Covenants: Enables the creation of specialized covenants for zkRollups and other applications, using new Bitcoin PIPEs to enforce verification conditions directly in Bitcoin L1.
    • Enhanced Bitcoin Scripting Capabilities: The approach significantly extends Bitcoin Script's capabilities, facilitating on-chain verification of zero-knowledge proofs.
    • Recursive Proof Systems: Discusses how recursive verification, in combination with PIPEs, can enable efficient proof systems on Bitcoin without needing Turing completeness.
    • Schnorr Signature Integration: Suggests embedding a Schnorr signing key within the predicate, enabling signature generation only if certain verification conditions are met.

    KEY QUOTES:

    • "The proposed use of Bitcoin PIPEs introduces a new method for verifying ZKPs without modifying the Bitcoin protocol, thus avoiding the need for community consensus."
    • "The function-hiding aspect of the PIPE ensures that the secret signing key remains secure, even during the verification of complex cryptographic conditions."
    • "This approach to verification not only addresses the current limitations of Bitcoin Script but also expands the types of applications that can be implemented directly on Bitcoin L1."
    • "Having covenants implemented as Bitcoin PIPEs means that non-interactive protocol definitions can improve security assumptions to native Bitcoin L1-level ones."
    • "Embedding Placeholder verification as a Bitcoin PIPE covenant allows for a full proof verification, improving security to the strongest assumptions without requiring a challenger oracle in the verification protocol."
  • Simple Three-Round Multiparty Schnorr Signing with Full Simulatability (2022). [research paper]. Lindell, Yehuda. Cryptology ePrint Archive, Paper 2022/374. Retrieved 2024-12-13 from: https://eprint.iacr.org/2022/374. Also available in PDF format: https://eprint.iacr.org/2022/374.pdf.

    TAGS: #MultipartySigning #SchnorrSignatures #ThreeRoundProtocol #Simulatability #ConcurrentComposition #CryptographicSecurity #ThresholdSignatures

    SHORT ABSTRACT: "This paper introduces a three-round multiparty protocol for generating Schnorr signatures, overcoming the limitations of two-round protocols. It ensures full simulatability and security under concurrent composition, leveraging standard cryptographic assumptions and offering practical flexibility in real-world applications."

    COMMENTARY: "Unlike FROST, which focuses on two-round Schnorr-based threshold signature schemes with optimizations for efficiency, this paper's proposal emphasizes full simulatability and security under concurrent composition, achieved through an additional third round. While FROST is designed for scenarios prioritizing minimal interaction, the protocol in this paper offers enhanced security guarantees, particularly in adversarial or concurrently executed environments. Compared to ROAST, which addresses robustness and liveness in signing under unreliable networks by reusing FROST's two-round design, this proposal provides a fundamentally different focus on strong theoretical guarantees, such as simulatability and concurrent compositional security, rather than practical resiliency in unreliable networks."

    KEY POINTS:

    • Multiparty Signing Protocols: The protocol enables a set of parties to collaboratively generate a Schnorr signature, with the private signing key shared among them, ensuring that only a quorum can produce a valid signature.
    • Three-Round Protocol: Unlike many existing two-round protocols that may lack full simulatability or security under concurrent composition, this protocol operates in three rounds, achieving these security properties.
    • Full Simulatability: The protocol is fully simulatable in the sense of multiparty computation (MPC) real/ideal security definitions, allowing for a rigorous security proof.
    • Concurrent Composition Security: It maintains security under concurrent composition, meaning it remains secure even when multiple protocol instances are executed simultaneously.
    • Standard Assumptions: The security proof relies on standard cryptographic assumptions, avoiding non-standard or ad-hoc assumptions often used in other protocols.
    • Ideal Functionality Realization: The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model.
    • Practical Considerations: It does not assume that all parties start with the message to be signed or the identities of participating parties, allowing these parameters to be agreed upon as the protocol progresses, which aligns with practical deployment scenarios.

    KEY QUOTES:

    • "In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature."
    • "Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) utilize non-standard assumptions of different types in their proofs of security."
    • "The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives)."
    • "In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice."
    • "The main technical contribution of this paper is the design of a simple three-round protocol that achieves full security with full simulatability."
    • "Our protocol ensures that an adversary cannot forge signatures or learn anything about the private key other than what is revealed by the signatures themselves."
    • "To the best of our knowledge, this is the first three-round multiparty Schnorr signing protocol that achieves full security under concurrent composition."

Unsorted and minimally annotated:

  • Achieving Maximum Efficiency in Schnorr-based Multi-signature and Applications in Blockchain (2023). [paper]. Peng Zhang, Fa Ge, and Yuhong Liu. Retrieved 2024-12-21 from arXiv: https://arxiv.org/abs/2305.13699.

    This paper introduces MEMS, a two-round multi-signature scheme that addresses $k$-sum attacks by incorporating a Public Third Party (PTP). The scheme enhances efficiency and security in blockchain applications by reducing communication overhead and maintaining computational costs comparable to basic Schnorr signatures.

  • HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures (2024). [paper]. Renas Bacho et al. Retrieved 2024-12-21 from IACR ePrint Archive: https://eprint.iacr.org/2024/280.

    HARTS presents a threshold Schnorr signature scheme that achieves adaptive security and robustness in asynchronous networks. It supports high-threshold configurations, making it suitable for applications requiring strong security guarantees, such as distributed ledger technologies.

  • Dynamic-FROST: Schnorr Threshold Signatures with a Flexible Committee (2024). [paper]. Annalisa Cimatti et al. Retrieved 2024-12-21 from IACR ePrint Archive: https://eprint.iacr.org/2024/896.

    Dynamic-FROST extends the FROST threshold signature scheme by enabling dynamic changes in both the committee and threshold value without relying on a trusted third party. This flexibility is advantageous for applications like consensus algorithms and blockchain wallets that require adaptable security parameters.

  • Simple Schnorr Multi-Signatures with Applications to Bitcoin (2018). [paper]. Gregory Maxwell et al. Retrieved 2024-12-21 from IACR ePrint Archive: https://eprint.iacr.org/2018/068.

    This foundational paper introduces MuSig, a Schnorr-based multi-signature scheme that allows key aggregation and is provably secure in the plain public-key model. MuSig enhances performance and user privacy in Bitcoin by enabling efficient multi-signature transactions.

  • SPRINT: High-Throughput Robust Distributed Schnorr Signatures (2023). [paper]. Fabrice Benhamouda et al. Retrieved 2024-12-21 from IACR ePrint Archive: https://eprint.iacr.org/2023/427.

    SPRINT describes high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols are designed for asynchronous networks and are suitable for implementing signature services over public blockchains with many validators.

  • Concurrently Secure Blind Schnorr Signatures (2022). [paper]. Georg Fuchsbauer and Mathias Wolf. Retrieved 2024-12-21 from IACR ePrint Archive: https://eprint.iacr.org/2022/1676.

    This paper presents a concurrently secure blind-signing protocol for Schnorr signatures, compatible with standard implementations over 256-bit elliptic curves. It introduces the notion of predicate blind signatures, enabling the signer to define predicates that the blindly signed message must satisfy, with applications in privacy-preserving protocols.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment