Skip to content

Schnorr Signatures#

The Schnorr signature scheme is a key cryptographic primitive in Ergo, allowing for efficient, simple, and secure signatures. Whether verifying a transaction or proving the ownership of a private key on-chain, Schnorr signatures play a central role. This page explains how to verify a Schnorr signature in ErgoScript, starting from basic signing and verification steps to advanced on-chain validation.

Overview#

Ergo uses the Secp256k1 elliptic curve (the same curve used in Bitcoin), denoted as G, for its Schnorr signature scheme. The Schnorr signature allows a user to prove knowledge of a private key without revealing the key itself.

Key Setup:#

  1. The secret key is an integer x.
  2. The corresponding public key is Y = g^x, where g is the generator of the elliptic curve group G.

Schnorr Signing Process#

To sign a message M (the hash of the message), follow these steps:

  1. Generate a random integer r and compute U = g^r.
  2. Compute the challenge c = Hash(U || M).
  3. Compute the response s = r - cx.

The signature is the pair (c, s), which is sent to the verifier.

Schnorr Signature Verification#

Schnorr Identification#

Before diving into signature verification, it's helpful to understand the Schnorr identification process, a variant of Schnorr signatures:

  • Instead of sending (c, s), the prover sends (U, s) (a group element and an integer).
  • The verifier computes c = Hash(U || M) and checks if: [ g^s = U / Y^c ] This works because: [ g^s = g^{r - cx} = g^r / (g^x)^c = U / Y^c ]

Schnorr Signature Verification#

For Schnorr signatures, the signature (c, s) is verified differently. The verifier computes U = g^s \cdot Y^c and checks if: [ c = Hash(U || M) ] This process ensures that the signature is valid and was produced by the holder of the secret key corresponding to the public key Y.

On-Chain Verification in ErgoScript#

In ErgoScript, verifying a Schnorr signature involves reconstructing U on-chain and checking the challenge.

ErgoScript Example:#

{ 
  // Getting the generator of the elliptic curve group 
  val g: GroupElement = groupGenerator

  // Getting the public key Y from R4
  val Y = SELF.R4[GroupElement].get

  // Getting the message M from R5
  val M = SELF.R5[Coll[Byte]].get

  // Retrieving the c value (challenge) from context variable 0
  val cBytes = getVar .get
  val c = byteArrayToBigInt(cBytes)

  // Retrieving the s value (response) from context variable 1
  val s = getVar .get

  // Calculating U = g^s * Y^c
  val U = g.exp(s).multiply(Y.exp(c)).getEncoded // as a byte array

  // Checking if the Schnorr signature is valid
  sigmaProp(cBytes == sha256(U ++ M))
}

Script Explanation:#

  • The generator of the elliptic curve is retrieved using groupGenerator.
  • The public key Y is stored in the register R4 of the transaction box.
  • The message M (hash of the original message) is stored in register R5.
  • The challenge c and response s (signature components) are retrieved from context variables.
  • The script verifies the Schnorr signature by checking that the reconstructed U matches the hash used to generate c.

Reference Test:#

The complete off-chain and on-chain interaction, including signature generation and verification, can be seen in this test case.

Advanced Schnorr Validation Off-Chain#

Efficient Off-Chain Code:#

In off-chain code, you can reduce complexity by using a simpler form of Schnorr validation. The problem arises from the fact that ErgoScript only supports 256-bit integers, so it's crucial to ensure that the signature integers fit within this constraint.

{
    val message = ...
    // Compute challenge
    val e: Coll[Byte] = blake2b256(message)
    val eInt = byteArrayToBigInt(e) // Challenge as big integer

    // Retrieve a of signature (a, z)
    val a = getVar .get
    val aBytes = a.getEncoded

    // Retrieve z of signature (a, z)
    val zBytes = getVar .get
    val z = byteArrayToBigInt(zBytes)

    // Verify signature by checking if g^z = a * Y^e
    val properSignature = g.exp(z) == a.multiply(holder.exp(eInt))

    sigmaProp(properSignature)
}

Off-Chain Signature Generation:#

To ensure z (part of the signature) fits within 255 bits, the following code iterates over possible random values until a valid z is found:

  def randBigInt: BigInt = {
    val random = new SecureRandom()
    val values = new Array 
    random.nextBytes(values)
    BigInt(values).mod(SecP256K1.q)
  }

  @tailrec
  def sign(msg: Array[Byte], secretKey: BigInt): (GroupElement, BigInt) = {
    val r = randBigInt
    val g: GroupElement = CryptoConstants.dlogGroup.generator
    val a: GroupElement = g.exp(r.bigInteger)
    val z = (r + secretKey * BigInt(scorex.crypto.hash.Blake2b256(msg))) % CryptoConstants.groupOrder

    if(z.bitLength <= 255) {
      (a, z)
    } else {
      sign(msg, secretKey)
    }
  }

For further examples of constructing off-chain transactions and verifying them on-chain, refer to the ChainCash repository.

Considerations and Limitations#

  • Weak Fiat-Shamir Transformation: In this setup, the Schnorr scheme uses a weak Fiat-Shamir transformation. This is acceptable for many use cases because the public key remains fixed. However, for certain advanced applications, it may be necessary to apply a stronger transformation.

Conclusion#

Schnorr signatures in Ergo provide a powerful, efficient, and flexible way to handle cryptographic authentication both on-chain and off-chain. Whether it's a simple transaction signature or a complex proof involving multi-signatures or privacy-preserving mechanisms, ErgoScript’s built-in support for Schnorr signatures makes it easy to implement.

For more details, explore:

  • The SchnorrSpec test case, which demonstrates both on-chain verification of Schnorr signatures and off-chain signature generation in ErgoScript.
  • The ChainCash repository for further examples of Schnorr-based signature transactions and how to integrate them in more complex use cases.

By understanding and leveraging Schnorr signatures in Ergo, you can implement secure, efficient, and scalable cryptographic proofs for a variety of applications, ranging from simple transactions to privacy-preserving protocols like atomic swaps, ring signatures, and threshold signatures.

Resources#

  1. Schnorr Signature Paper: MuSig: A New Multi-Signature Standard – A foundational paper on Schnorr multi-signatures.
  2. Adaptor Signatures: Adaptor Signatures for Cross-Chain Protocols – A deep dive into the use of Schnorr signatures for atomic swaps and privacy-preserving transactions.
  3. Elliptic Curve Cryptography: SecP256K1 Curve Information – Detailed information on the elliptic curve used in both Bitcoin and Ergo.
  4. SigmaBoolean Documentation: SigmaBoolean in Ergo – Documentation on how to use SigmaBoolean and generalized Schnorr proofs in Ergo smart contracts.