Schnorr Signatures

Source

This document is sourced from the MinaProtocol/mina repository, compatible branch, commit 217c823fb14d4c8b08ceba0404c5b8a624e90e14.

Title: Mina Schnorr Signatures Author: Izaak Mecklker (izaak@o1labs.org) Status: Draft Type: Informational License: BSD-2-Clause

Updates

• December 2021, Joseph Spadavecchia (joseph@o1labs.org) Updated to latest curves and signing algorithm

Introduction

This document proposes a standard for Mina Schnorr signatures over the elliptic curve Pallas Pasta. It is adapted from BIP 340.

Copyright

This document is licensed under the 2-clause BSD license.

Description

We first build up the algebraic formulation of the signature scheme by going through the design choices. Afterwards, we specify the exact encodings and operations.

Design

Schnorr signature variant Elliptic Curve Schnorr signatures for message m and public key P generally involve a point R, integers e and s picked by the signer, and generator G which satisfy e = H(R || m) and sG = R + eP. Two formulations exist, depending on whether the signer reveals e or R:

1. Signatures are (e,s) that satisfy e = H(sG - eP || m). This avoids minor complexity introduced by the encoding of the point R in the signature (see paragraphs "Encoding the sign of R" and "Implicit Y coordinate" further below in this subsection).
2. Signatures are (R,s) that satisfy sG = R + H(R || m)P. This supports batch verification, as there are no elliptic curve operations inside the hashes.

We choose the R-option to support batch verification.

Key prefixing When using the verification rule above directly, it is possible for a third party to convert a signature (R,s) for key P into a signature (R,s + aH(R || m)) for key P + aG and the same message, for any integer a. To combat this, we choose key prefixed¹ Schnorr signatures; changing the equation to sG = R + H(m1 || P || R || m2 ) where m1 is the field elements of the message m and m2 is the rest of the message.

Encoding the sign of R As we chose the R-option above, we're required to encode the point R into the signature. Several possibilities exist:

1. Encoding the full X and Y coordinates of R, resulting in a 96-byte signature.
2. Encoding the full X coordinate, but only whether Y is even or odd (like compressed public keys). This would result in a 65-byte signature.
3. Encoding only the X coordinate, leaving us with 64-byte signature.

Using the first option would be slightly more efficient for verification (around 5%), but we prioritize compactness, and therefore choose option 3.

Implicit Y coordinate In order to support batch verification, the Y coordinate of R cannot be ambiguous (every valid X coordinate has two possible Y coordinates). We have a choice between several options for symmetry breaking:

1. Implicitly choosing the Y coordinate that is in the lower half.
2. Implicitly choosing the Y coordinate that is even².

We choose option 2 as it is a bit simpler to implement.

Final scheme As a result, our final scheme ends up using signatures (r,s) where r is the X coordinate of a point R on the curve whose Y coordinate is even, and which satisfies sG = R + H(r || P || m)P.

Specification

We first describe the verification algorithm, and then the signature algorithm.

The following convention is used, with constants as defined for Mina's version of Pasta Pallas:

• Lowercase variables represent integers or byte arrays.
  • The constant p refers to the field size, 28948022309329048855892746252171976963363056481941560715954676764349967630337
  • The constant n refers to the curve order, 28948022309329048855892746252171976963363056481941647379679742748393362948097
  • The constant a refers to the first curve parameter which is 0
  • The constant b refers to the other curve parameter which is 5
• Uppercase variables refer to points on the curve with equation y^2 = x^3 + ax + b over the integers modulo p.
  • infinite(P) returns whether or not P is the point at infinity
  • x(P) and y(P) refer to the X and Y coordinates of a point P (assuming it is not infinity)
  • The constant G refers to the generator, for which x(G) = 1 and y(G) = 12418654782883325593414442427049395787963493412651469444558597405572177144507
  • Addition of points refers to the usual elliptic curve group operation.
  • Multiplication of an integer and a point refers to the repeated application of the group operation
  • Base field and scalar field elements are represented in little-endian order
• Functions and operations:
  • || refers to either array concatenation or bit string concatenation
  • [s]G refers to elliptic curve scalar multiplication of s with generator G
  • blake2b - Blake2b cryptographic hash function with 32-byte output size
  • poseidon_3w - Poseidon cryptographic hash function for Mina
  • scalar(r) refers to the scalar field element obtained from random bytes r by dropping two MSB bits
  • s(σ) refers to scalar field component of signature σ
  • b(σ) refers to base field component of signature σ
  • x(P) refers to x-coordinate of point P
  • y(P) refers to y-coordinate of point P
  • odd(e) - true if base field element e is odd, false otherwise
  • negate(s) - negation of scalar field element s
  • fields(m) - vector containing components of message m that are base field elements
  • bits(m) - all other parts of message m that are not in fields(m)
  • pack(byte) - convert byte into 8 bits little-endian order
  • pack(e) - convert base field element e into 255 bits little-endian order
  • pack(E) - convert vector of base field elements E = [e1, ..., en] into bit string pack(e1) || ... || pack(en)
  • pack(s) - convert scalar field element s into 255 bits little-endian order
  • unpack(bits) - convert bit string bits = b₁b₂...b₂₅₅b₂₅₆...b₅₁₀... into vector of base field elements [e1, e2, ..., en] where e1 = b₁...b₂₅₅0, e2 = b₂₅₆...b₅₁₀0 and so on, such that the last element is zero-padded to 255 bits if necessary.
  • iv(id) - unique poseidon_3w initialization vector for blockchain instance identified with id:
    • Testnet (id = 0x00)

      [
          28132119227444686413214523693400847740858213284875453355294308721084881982354,
          24895072146662946646133617369498198544578131474807621989761680811592073367193,
          3216013753133880902260672769141972972810073620591719805178695684388949134646
      ]

    • Mainnet (id = 0x01)

      [
          25220214331362653986409717908235786107802222826119905443072293294098933388948,
          7563646774167489166725044360539949525624365058064455335567047240620397351731,
          171774671134240704318655896509797243441784148630375331692878460323037832932,
      ]

The following helper functions are required.

Nonce derivation

• Input:
  • Secret key d: an integer in the range 1..n-1
  • Public key P: a curve point
  • Message m: message to be signed
  • Network id id: blockchain instance identifier
• Definition: derive_nonce(d, P, m, id) =
  • Let bytes = pack(fields(m)) || pack(x(P)) || pack(y(P)) || pack(d) || pack(id)
  • Let digest = blake2b(bytes)
• Output: scalar(digest)

Message hash

• Input:
  • Public key P: a curve point
  • Base field element rx: X coordinate of nonce point
  • Message m: message to be signed
  • Network id id: blockchain instance identifier
• Definition: message_hash(P, rx, m, id) =
  • Let fields = fields(m) || x(P) || y(P) || xr || unpack(bits(m))
  • Let b = poseidon_3w(iv(id), fields)
• Output: scalar(b)

The signing and verification algorithms are as follows.

Signature verification

• Input:
  • Public key P: a curve point
  • Message m: message
  • Signature σ: signature on m
  • Network id id: blockchain instance identifier
• The signature is valid if and only if the algorithm below does not fail.
  • Let e = message_hash(P, b(σ), m, id)
  • Let R = [s(σ)]G - [e]P
  • Fail if infinite(R) OR odd(y(R)) OR x(R) != b(σ)

Signature generation

• Input:
  • Secret key d: an integer in the range 1..n-1
  • Public key P: a curve point
  • Message m: message to be signed
  • Network id id: blockchain instance identifier
• To sign m for public key P = dG:
  • Let k = derive_nonce(d, P, m, id)
  • Let R = [k]G
  • If odd(y(R)) then negate(k)
  • Let e = message_hash(P, x(R), m, id)
  • Let s = k + e*d
• The signature σ = (x(R), s)

Above deterministic derivation of R is designed specifically for this signing algorithm and may not be secure when used in other signature schemes. For example, using the same derivation in the MuSig multi-signature scheme leaks the secret key (see the MuSig paper for details).

Note that this is not a unique signature scheme: while this algorithm will always produce the same signature for a given message and public key, k (and hence R) may be generated in other ways (such as by a CSPRNG) producing a different, but still valid, signature.

Optimizations

Many techniques are known for optimizing elliptic curve implementations. Several of them apply here, but are out of scope for this document. Two are listed below however, as they are relevant to the design decisions:

Jacobi symbol The function jacobi(x) is defined as above, but can be computed more efficiently using an extended GCD algorithm.

Jacobian coordinates Elliptic Curve operations can be implemented more efficiently by using Jacobian coordinates. Elliptic Curve operations implemented this way avoid many intermediate modular inverses (which are computationally expensive), and the scheme proposed in this document is in fact designed to not need any inversions at all for verification. When operating on a point P with Jacobian coordinates (x,y,z) which is not the point at infinity and for which x(P) is defined as x / z^2 and y(P) is defined as y / z^3:

• jacobi(y(P)) can be implemented as jacobi(yz mod p).
• x(P) ≠ r can be implemented as x ≠ z^2^r mod p.

Applications

There are several interesting applications beyond simple signatures. While recent academic papers claim that they are also possible with ECDSA, consensus support for Schnorr signature verification would significantly simplify the constructions.

Multisignatures and threshold signatures

By means of an interactive scheme such as MuSig, participants can produce a combined public key which they can jointly sign for. This allows n-of-n multisignatures which, from a verifier's perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus CHECKMULTISIG or other means.

Further, by combining Schnorr signatures with Pedersen Secret Sharing, it is possible to obtain an interactive threshold signature scheme that ensures that signatures can only be produced by arbitrary but predetermined sets of signers. For example, k-of-n threshold signatures can be realized this way. Furthermore, it is possible to replace the combination of participant keys in this scheme with MuSig, though the security of that combination still needs analysis.

Adaptor signatures

Adaptor signatures can be produced by a signer by offsetting his public nonce with a known point T = tG, but not offsetting his secret nonce. A correct signature (or partial signature, as individual signers' contributions to a multisignature are called) on the same message with same nonce will then be equal to the adaptor signature offset by t, meaning that learning t is equivalent to learning a correct signature. This can be used to enable atomic swaps or even general payment channels in which the atomicity of disjoint transactions is ensured using the signatures themselves, rather than Bitcoin script support. The resulting transactions will appear to verifiers to be no different from ordinary single-signer transactions, except perhaps for the inclusion of locktime refund logic.

Adaptor signatures, beyond the efficiency and privacy benefits of encoding script semantics into constant-sized signatures, have additional benefits over traditional hash-based payment channels. Specifically, the secret values t may be reblinded between hops, allowing long chains of transactions to be made atomic while even the participants cannot identify which transactions are part of the chain. Also, because the secret values are chosen at signing time, rather than key generation time, existing outputs may be repurposed for different applications without recourse to the blockchain, even multiple times.

Blind signatures

Schnorr signatures admit a very simple blind signature construction which is a signature that a signer produces at the behest of another party without learning what he has signed. These can for example be used in Partially Blind Atomic Swaps, a construction to enable transferring of coins, mediated by an untrusted escrow agent, without connecting the transactors in the public blockchain transaction graph.

While the traditional Schnorr blind signatures are vulnerable to Wagner's attack, there are a number of mitigations which allow them to be usable in practice without any known attacks. Nevertheless, more analysis is required to be confident about the security of the blind signature scheme.

Reference code

1. C - Mina c-reference-signer
2. OCaml - Ocaml signer-reference

Implementations

1. Rust - O(1) Labs proof-systems - mina-signer crate
2. OCaml - Mina Protocol - signature_lib module
3. C - Ledger hardware wallet - ledger-app-mina

Acknowledgements

This document was adapted by Izaak Meckler from Peter Wiulle's BIP. The original acknowledgements are included below.

Footnotes

This document is the result of many discussions around Schnorr based signatures over the years, and had input from Johnson Lau, Greg Maxwell, Jonas Nick, Andrew Poelstra, Tim Ruffing, Rusty Russell, and Anthony Towns.

Footnotes

1. A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification. ↩

2. Since p is odd, negation modulo p will map even numbers to odd numbers and the other way around. This means that for a valid X coordinate, one of the corresponding Y coordinates will be even, and the other will be odd. ↩