Crate jubjub_schnorr
source ·Expand description
§jubjub-schnorr
This crate provides a Rust implementation of the Schnorr signature scheme for the JubJub elliptic curve group, using the Poseidon hash function. This implementation is designed by the Dusk team.
§About
The Schnorr signature scheme, named after its creator Claus Schnorr, is a digital signature scheme renowned for its simplicity. The scheme provides a simple method of creating short signatures.
The implementation has been created using the jubjub
elliptic curve and the Poseidon
hash function, the paper for which can be found here.
The signature scheme is implemented within the Phoenix transaction model and is based on the Schnorr Sigma protocol, compiled alongside the Fiat–Shamir transformation, to serve as a non-interactive signature scheme. Specifically, the Phoenix protocol employs a variant that utilizes double Schnorr signatures, verifiable with double public keys, enabling the delegation of computational processes within the protocol’s later stages.
The repository also includes an implementation of the SpeedyMuSig
Schnorr-based multisignature scheme described here (pag. 19). It allows several signers to create a signature that proves a message to be signed by them all, given their public keys. The signature can be verified using the same function used for the standard Schnorr signature, using the sum of all the signers’ public keys.
§Library Structure
The library is partitioned into the following components:
- Keys: Module containing the secret key structure for signing messages, as well as the public key and the double public key structures used in verification.
- Signatures: Module containing the standard and double signature structs as well as functions to verify the validity of Schnorr signatures and double Schnorr signatures.
- Gadgets: Contains the Plonk gadgets for in-circuit verification of Schnorr signatures and double Schnorr Signatures.
§Signature Scheme Description
§Notation
In the following:
- Multiplication of a point $P$ by a scalar $s$ stands for adding $P$ $s$-times to itself.
- $\mathbb{F}_q$ is the prime finite field of order $q$
- for a prime $q$: $\mathbb{F}_q^× = \mathbb{F}_q \setminus 0$ contains all nonzero elements of $\mathbb{F}_q$.
§Single Signature
§Setup
In this library we implement our Schnorr signature scheme on the jubjub elliptic curve, specifically we have:
- a finite field $\mathbb{F}_q$ over prime $q$, in this implementation this field corresponds to the scalar field of the elliptic curve BLS12-381
- an elliptic curve $E / \mathbb{F}_q$, in our case this is the jubjub elliptic curve
- a subgroup $\mathbb{G} \in E(\mathbb{F}_q)$ of curve points, with prime order $p$
- a fixed generator point $G \in \mathbb{G}$
- a cryptographic hash function $H : {0 , 1}^∗ \rightarrow \mathbb{F}_p$ where $\mathbb{F}_p$ is the scalar field of the jubjub elliptic curve.
§Key generation
- Choose a private signing key, $sk \in \mathbb{F}_p^×$.
- The public verification key is $PK = skG \in \mathbb{G}$.
§Signing
To sign a message $m \in \mathbb{F}_q^×$:
- Choose a random private nonce $r \in \mathbb{F}_p^×$.
- Compute nonce point $R = rG \in \mathbb{G}$.
- Compute challenge hash $c = H(R \parallel $PK \parallel m) \in \mathbb{F}_p$ where $\parallel$ denotes concatenation and $R$ is represented as a bit string.
- Compute $u = r − sk \cdot c \in \mathbb{F}_p$.
The signature is the tuple $(u, R) \in \mathbb{F}_p \times \mathbb{G}$.
§Verifying
- Compute challenge hash $c = H(R \parallel $PK \parallel m) \in \mathbb{F}_p$.
- Verify that $uG + cPK = R$.
If the signature was signed with the secret key corresponding to $PK$, this will hold true, since:
$$ uG + cPK = (r - sk\cdot c)G + (sk\cdot c)G = (r - sk\cdot c + sk\cdot c)G = rG = R $$
§Double Signature
§Setup
Same as in the single signature above with the addition of another generator point $G’ \in \mathbb{G}$, that is different from $G$ and whose discrete logarithm relation with $G$ is unknown.
§Key generation
- Choose a private signing key, $sk \in \mathbb{F}_p^×$.
- The public verification key is the tuple $(PK, PK’)$ with $PK = skG \in \mathbb{G}$ and $PK’ = skG’ \in \mathbb{G}$.
§Signing
To sign a message $m \in \mathbb{F}_q^×$:
- Choose a random private nonce $r \in \mathbb{F}_p^×$.
- Compute nonce points $R = rG \in \mathbb{G}$ and $R’ = rG’ \in \mathbb{G}$.
- Compute challenge hash $c = H(R \parallel R’ \parallel $PK \parallel m) \in \mathbb{F}_p$ where $\parallel$ denotes concatenation and $R, R’$ are represented as a bit strings.
- Compute $u = r − sk \cdot c \in \mathbb{F}_p$.
The signature is the tuple $(u, R, R’) \in \mathbb{F}_p \times \mathbb{G} \times \mathbb{G}$.
§Verifying
- Compute challenge hash $c = H(R \parallel R’ \parallel $PK \parallel m) \in \mathbb{F}_p$.
- Verify that $rG + cPK = R$ and $uG’ + cPK’ = R’$.
If the signature was signed with the correct private key, this should hold true because:
$$ uG + cPK = (r - sk\cdot c)G + (sk\cdot c)G = (r - sk\cdot c + sk\cdot c)G = rG = R $$
and
$$ uG’ + cPK’ = (r - sk\cdot c)G’ + (sk\cdot c)G’ = (r - sk\cdot c + sk\cdot c)G’ = rG’ = R’ $$
§Notes on Security and Implementation
The implemented signature scheme is existentially unforgeable under chosen-message attacks assuming the hardness of the discrete logarithm problem in the random oracle model. This property is detailed in Section 12.5.1 of Katz and Lindell’s Introduction to Modern Cryptography.
While the basic Schnorr signature scheme is a widely recognized construct, the double-key variant as employed by Phoenix is a novel introduction. In the context of the transaction protocol, this allows for the delegation of proof computations without compromising the confidentiality of the signer’s secret key.
§Usage
To integrate the jubjub-schnorr
crate into your project, add it with the following command:
cargo add jubjub-schnorr
A basic example demonstrating how to generate and verify a Schnorr signature:
use dusk_bls12_381::BlsScalar;
use jubjub_schnorr::{SecretKey};
use rand::rngs::StdRng;
use rand::SeedableRng;
use ff::Field;
fn main() {
// Setup
let mut rng = StdRng::seed_from_u64(1234u64);
let message = BlsScalar::random(&mut rng);
// Key generation
let sk = SecretKey::random(&mut rng);
// Standard Schnorr signature scheme:
use jubjub_schnorr::PublicKey;
let pk = PublicKey::from(&sk);
let signature = sk.sign(&mut rng, message);
assert!(pk.verify(&signature, message).is_ok(), "The signature should be valid.");
// Double Dusk-Schnorr signature scheme:
use jubjub_schnorr::PublicKeyDouble;
let pk = PublicKeyDouble::from(&sk);
let signature = sk.sign_double(&mut rng, message);
assert!(pk.verify(&signature, message).is_ok(), "The signature should be valid.");
// Dusk-Schnorr signature scheme with variable generator:
use dusk_jubjub::{GENERATOR_EXTENDED, JubJubScalar};
use jubjub_schnorr::PublicKeyVarGen;
let generator = GENERATOR_EXTENDED * JubJubScalar::from(42u64);
let sk = sk.with_variable_generator(generator);
let pk = PublicKeyVarGen::from(&sk);
let signature = sk.sign(&mut rng, message);
assert!(pk.verify(&signature, message).is_ok(), "The signature should be valid.");
}
§Licensing
This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
Copyright (c) DUSK NETWORK. All rights reserved.
Structs§
- Structure representing a
PublicKey
, consisting of aJubJubExtended
point on the JubJub curve. This public key allows for the verification of signatures created with its corresponding secret key without revealing the secret key itself. - Structure representing a
PublicKeyDouble
, consisting of twoJubJubExtended
poinst on the JubJub curve. - Structure representing a
PublicKeyVarGen
, consisting of a public keyJubJubExtended
point and a variable generatorJubJubExtended
point on the JubJub curve. This public key allows for the verification of signatures created with its corresponding variable generator secret key without revealing the secret key itself. - Structure representing a
SecretKey
, represented as a private scalar in the JubJub scalar field. - Structure representing a
SecretKeyVarGen
, represented as a private scalar in the JubJub scalar field, with a variable generator, represented as a point on the JubJub curve. - An Schnorr signature, produced by signing a message with a
SecretKey
. - Structure representing a Schnorr signature with a double-key mechanism.
- An Schnorr SignatureVarGen, produced by signing a message with a
SecretKeyVarGen
.
Enums§
- Standard error for the interface