The purpose of the Schnorr protocol is to allow one to prove the knowledge of a discrete logarithm without revealing its value.
The Schnorr protocol is an example of a Sigma protocol (-protocol). A
Sigma protocol is a three-step protocol in which communication between prover
and verifier goes forwards once, then backwards, then forwards again. In
general terms:
The protocol is defined for a cyclic group of order .
The prover aims to convince the verifier that he knows some private value .
Therefore,
(see [1]) will be her public key. In order to prove
knowledge of it, the prover interacts with the verifier in three passes:
-
The prover commits to a random private value
, chosen in the range
. This is the first message commitment
.
-
The verifier replies with a
challenge
chosen at random from.
-
After receiving the
challenge
, the prover sends the third and last message (the response).
The verifier accepts, if:
- The prover's public key,
, is a valid public key. It means that it must be a valid point on the curve and
is not a point at infinity, where
is the cofactor of the curve.
- The prover's commitment value is equal to
Zero knowledge proofs are a way by which one party succeeds in convincing
another party that she knows a private value without exposing any information
apart from the fact that she knows the value
.
All proof systems have two requirements:
-
Completeness: An honest verifier will be convinced of this fact by an untrusted prover.
-
Soundness: No prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small probability.
It is assumed that the verifier is always honest.
The original Schnorr identification scheme is made non-interactive through a Fiat-Shamir transformation, assuming that there exists a secure cryptographic hash function (i.e., the so-called random oracle model).
An oracle is considered to be a black box that outputs unpredictable but
deterministic random values in response to a certain input. That means that,
given the same input, the oracle will give back the same random output. The
input to the random oracle, in the Fiat-Shamir heuristic, is specifically the
transcript of the interaction up to that point. The challenge is then redefined
as , where
is a secure cryptographic hash
function like SHA-256. The bit length of the hash output should be at least
equal to that of the order
of the considered subgroup.
An example of the Schnorr protocol for Non-Interactive Zero-Knowledge Proofs looks as follows.
testSchnorrNIZK :: IO Bool
testSchnorrNIZK = do
-- Setup
let curveName = Curve25519
basePoint = Curve.g curveName
keyPair@(pk, sk) <- genKeys curveName basePoint
-- Prover
proof <- Schnorr.prove curveName basePoint keyPair
-- Verifier
pure (Schnorr.verify curveName basePoint pk proof)
This Schnorr implementation offers support for both SECP256k1 and Curve25519 curves, which are Koblitz and Montgomery curves, respectively.
- SECP256k1
- Curve25519
References:
- Hao, F. "Schnorr Non-interactive Zero-Knowledge Proof." Newcastle University, UK, 2017
- Schnorr Non-interactive Zero-Knowledge Proof https://tools.ietf.org/html/rfc8235
Notation:
: multiplication of a point
with a scalar
over an elliptic curve defined over a finite field modulo a prime number
This is experimental code meant for research-grade projects only. Please do not use this code in production until it has matured significantly.
Copyright 2018-2020 Adjoint Inc
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http:https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.