Schnorr Signature Scheme in Erlang
Implementing the Schnorr signature scheme in Erlang with minimal dependencies
Abstract
Nostr protocol was mainly designed by Bitcoin developers, or at least, people attracted by the Bitcoin ecosystem. Unfortunately, Erlang/OTP do not have all the cryptographic primitives to build a fully compliant nostr application from scratch without using external dependencies. Indeed, Erlang/OTP is already delivered with `crypto` and `public_key` modules to deal with classical cryptographic functionalities, principally used by SSL/TLS protocol stack. Bitcoin is using, on its side, lot of "unconventional" features -- or not generally offered by default libraries.
This article is the first one implementing cryptographic functions in Erlang. `nostr` protocol relies on elliptic curve cryptography, in particular `secp256k1` curve. Instead of using Elliptic Curve Digital Signature Algorithm (ECDSA) or Edwards-curve Digital Signature Algorithm (EdDSA), nostr is using Schnorr signature scheme like the Bitcoin project and defined in BIP-0340.
This article has been redacted in February and March 2023. It describes the methodologies applied and describe the methods used to implement the first NIP from nostr
protocol in Erlang with a minimal amount of dependencies. The following code has been tested using Erlang/OTP R25 running on OPENBSD-72-CURRENT and Parrot Linux (a Debian like distribution).
Schnorr Signature in Pure Erlang
Erlang is a multi-purpose language using its own virtual machine called the BEAM 1 -- a short name for Bogdan's Erlang Abstract Machine -- and greatly inspired by the Warren Abstract Machine 2 (WAM). It was created to help creating distributed enviroment. Usually, low level languages are used to implement cryptographic functions, this article will show its possible to have decent performances with great features when using high level languages.
The first Schnorr signature scheme designed for Bitcoin 3 was defined in BIP-0340 4. This scheme can also be found in BIP-0341 5 and BIP-0342 6 specifications. The implementation reference was made in Python 7 8.
Schnorr signature 9 -- likes any other cryptographic scheme -- is hard to implement. Fortunately, because Bitcoin is used by lot of people around the world, this signature protocol has been explained many times and anyone can find interesting resources on this topic 10 11 12 13 14 without buying a single book.
Collecting Information
Starting with a small overview 15, Schnorr signature scheme seems to have a strong security proofs, to be simple, to be fast and to have the property to create secrets without additional exchange.
Many implementation of this scheme can be found out there, in C 16 17, C++ 18, Elixir 19 20 21, Go 22, Python 23 24 25, Java 26 or Javascript 27 28.
Implementing Schnorr Signature Scheme
Like previously said, the reference implementation was made in Python. This language is not using the same paradigm than Erlang, Python is a script-like language using oriented object programming, while Erlang is a distributed and functional programming language. The way the code will be created will be quite different, and will require small adaptation. Modulo operator and pow
functions are, for example, not the same in these two universes. Functions with same behaviors than these two will need to be created on the Erlang side, a dedicated section for each of them will be available in this part of the article.
Dealing with asymetric cryptography -- even more elliptic curves -- can be quite complex and a well designed interface should avoid even smallest frictions with the developers. Functions to create standard and secure keys should be available. In this implementation, the nostrlib_schnorr:new_privatekey/0
will be a wrapper of the crypto:generate_key/2
function. A secp256k1 private key a 32bytes (256bits) random number and could also have been generated using crypto:strong_rand_bytes/1
function as well but we are assuming the functions provided by the Erlang team in crypto
module are already doing all the validation and are configuring the recommended parameterss 29.
% generate a private key using crypto:generate_key/2
{_PublicKey, <<PrivateKey:256/bitstring>>}
= crypto:generate_key(ecdh, secp256k1).
% generate a private key using crypto:strong_rand_bytes/1
<<PrivateKey:256/bitstring>>
= crypto:strong_rand_bytes(32).
% generate a private key using nostrlib_schnorr:new_private_key/0.
{ok, <<PrivateKey:256/bitstring>>}
= nostrlib_schnorr:new_private_key().
A public key, derived from the private key, is also required. The one provided by crypto:generate_key/2
is not suitable for our needs. A specific point on the curve is required and defined in BIP-0340, an operation on this same point is also required. The function to generate a public key with nostrlib
is nostrlib_schnorr:new_publickey/1
, where the first and only argument to pass is a valid private key (32bytes length bitstring).
{ok, <<PublicKey:256>>}
= nostrlib_schnorr:new_public_key(PrivateKey).
The Schnorr signature scheme can only sign 32bytes (256bits) messages, the BIP-0340 specification uses SHA256 as main hashing function to produce a 256bits fixed length hash as message. The crypto
module offers the function crypto:hash/2
to generate this payload, where the first argument will be the atom sha256
and the second argument will be the content to hash. This value can be signed by the functions nostrlib_schnorr:sign/2
or nostrlib_schnorr:sign/3
where the first argument is the hash previously generated and the second argument is the private key. The signature returned is a 64bytes (512bits) fixed length bitstring.
% create a hash from data, in this example, a raw bitstring.
<<Message:256/bitstring>>
= crypto:hash(sha256, <<"my data">>).
% create a signature with default aux_data (set to 0).
{ok, <<Signature:512/bitstring>>}
= nostrlib_schnorr:sign(Message, PrivateKey).
% create a signature with aux_data set to 0 (manually).
{ok, <<Signature:512bitstring>>}
= nostrlib_schnorr:sign(Message, PrivateKey, <<0:256>>).
To be sure this scheme is working, the signature must be verified with the public key. This feature can be done by using nostrlib_schnorr:verify/3
function, where the first argument is the hash produced with the raw message, the second argument is the public key and the last one is the signature. If the signature is valid, this function returns true
otherwise it will return false
.
true = nostrlib_schnorr:verify(Message, PublicKey, Signature).
Those interfaces are similar to the one offered by the reference implementation in Python and the ones present in other open-source implementations available on the web.
Requirement: Floored Modulo
Different version of the modulo operator 30 exists with Erlang, rem/2
, div/2
, math:fmod/2
or crypto:mod_pow/3
. The 3 firsts previously quoted operators and/or functions are using truncated modulo. The crypto:mod_pow/3
in other hand, could have been a good and powerful function if it was compatible with negative integers...
rem/2
or div/2
operators are using truncated modulo, Schnorr signature scheme uses floored modulo. By change, a similar problem has already be solved on stack overflow. Why reusing the wheel if a decent solution exists into the wild?
mod(0,_) -> 0;
mod(X,Y) when X > 0 -> X rem Y;
mod(X,Y) when X < 0 ->
K = (-X div Y)+1,
PositiveX = X+K*Y,
PositiveX rem Y.
This new function must be tested though. The %
operator in Python is already doing the job, then, it can be used to generate a list of valid input and output. The following script -- present in extra
directry -- generates 256 lines of CSV, with the inputs and the output.
#!/usr/bin/env python
# check_mod.py
# Usage: python check_mod.py > mod.csv
import sys
import string
import secrets
limit = 256
generator = secrets.SystemRandom()
start = -(2**256)
end = 2**256
for i in range(limit):
a = generator.randrange(start, end)
m = generator.randrange(0,end)
r = a % m
l = ",".join([str(i),str(a),str(m),str(r)])
print(l)
The CSV file is then opened and parsed on the Erlang side and another function is executed to check if the inputs and outputs are the same.
% same result can be found by executing the python
% script directly from the BEAM, instead of opening
% a file and read its content
% os:cmd("python check_mod.py").
CheckPow = fun (File) ->
{ok, Content} = file:read_file(File),
Lines = re:split(Content, "\n"),
Splitted = lists:map(fun(X) -> re:split(X, ",") end, Lines),
Result = [ { binary_to_integer(I)
, binary_to_integer(R) =:=
nostrlib_schnorr:mod(binary_to_integer(A)
,binary_to_integer(M))}
|| [I,A,M,R] <- Splitted
],
[] =:= lists:filter(fun({_,false}) -> true; (_) -> false end, Result)
end.
true =:= CheckPow("mod.csv").
This function was not the most difficult to implement but was critical. Modulo operator is a standard operation in cryptography and must be compatible with other implementations.
Requirement: Modular Pow
In Erlang, the pow
function can be done using math:pow/2
or by using crypto:mod_pow/3
, unfortunately, both of them are not natively compatible with the pow()
function present in the Python built-in functions. It is the very same issue than the one with the modulo
operator. In Erlang, math:pow/2
is returning a float and is limited in size. First problem: float, no one wants to deal with float, even more in cryptography. Second problem: With elliptic curves, the size matters and its generatelly more than 256bits long. In other hand, crypto:mod_pow/3
is not allowing negative numbers in input, and it will be a problem because the reference implementation is using signed numbers. Then, based on the requirement, nostrlib_schnorr
module requires a "modular pow" implementation 31.
The naive implementation of this function can easily be constructed in Erlang using only standard operators and the BIFs, unfortunately, this is quite slow, but it works.
% first implementation
modular_pow(1,0,_) -> 1;
modular_pow(0,1,_) -> 0;
modular_pow(_,_,1) -> 0;
modular_pow(Base, Exponent, Modulus) ->
NewBase = mod2(Base, Modulus),
modular_pow(NewBase, Exponent, Modulus, 1).
modular_pow(_Base, 0, _Modulus, Return) -> Return;
modular_pow(Base, Exponent, Modulus, Return) ->
case mod2(Exponent, 2) =:= 1 of
true ->
R2 = mod2(Return * Base, Modulus),
E2 = Exponent bsr 1,
B2 = mod2(Base*Base, Modulus),
modular_pow(B2, E2, Modulus, R2);
false ->
E2 = Exponent bsr 1,
B2 = mod2(Base*Base, Modulus),
modular_pow(B2, E2, Modulus, Return)
end.
A second implementation, still using default operators and BIFs, has been implemented. The speed was still pretty slow, but the returned values were valid.
% second implementation
pow(1,0,_) -> 1;
pow(0,1,_) -> 0;
pow(_,_,1) -> 0;
pow(Base, Exponent, Modulus) ->
case 1 band Exponent of
1 ->
modular_pow(Base, Exponent, Modulus, Base);
0 ->
modular_pow(Base, Exponent, Modulus, 1)
end.
modular_pow(_Base, 0, _Modulus, Return) -> Return;
modular_pow(Base, Exponent, Modulus, Return) ->
E2 = Exponent bsr 1,
B2 = mod(Base*Base, Modulus),
case E2 band 1 of
1 ->
modular_pow(B2, E2, Modulus, mod(Return*B2, Modulus));
_ ->
modular_pow(B2, E2, Modulus, Return)
end.
The main problem of the crypto:mod_pow/3
function was directly related to the first argument. When a negative value was given, the returned values were wrong. Well, why not then apply a part of the custom modular pow when the value is negative, and then, crypto:mod_pow/3
when the first argument is positive? That's the third implementation and the one currently used.
% third implementation
pow(1,0,_) -> 1;
pow(0,1,_) -> 0;
pow(_,_,1) -> 0;
pow(Base, Exponent, Modulus) when Base > 0 ->
bitstring_to_integer(crypto:mod_pow(Base, Exponent, Modulus));
pow(Base, Exponent, Modulus) when Base < 0 ->
case 1 band Exponent of
1 ->
modular_pow(Base, Exponent, Modulus, Base);
0 ->
modular_pow(Base, Exponent, Modulus, 1)
end.
modular_pow(_Base, 0, _Modulus, Return) -> Return;
modular_pow(Base, Exponent, Modulus, Return) ->
E2 = Exponent bsr 1,
B2 = mod(Base*Base, Modulus),
case E2 band 1 of
1 ->
modular_pow(B2, E2, Modulus, mod(Return*B2, Modulus));
_ ->
modular_pow(B2, E2, Modulus, Return)
end.
This "hack" is working when using the test suite, but, the numbers of tests are limited. To be sure the implement is correct, correct values generated from Python can be reused in Erlang. The following script export (available in extra
directory in the project) exports the input and the output of the pow
function in CSV format.
#!/usr/bin/env python3
# check_pow.py
# Usage: python3 check_pow.py > pow.csv
import sys
import secrets
limit = 256
generator = secrets.SystemRandom()
start = -(2**256)
end = 2**256
for i in range(limit):
a = generator.randrange(start, end)
b = generator.randrange(0,end)
m = generator.randrange(0,end)
p = pow(a, b, m)
l = ",".join([str(i),str(a),str(b),str(m),str(p)])
print(l)
When executed, the resulting CSV file can be read again by a small function in Erlang, converting the CSV columns to integer values and applying them a check function (this script can also be found in extra
directory).
% same result can be found by executing the python
% script directly from the BEAM, instead of opening
% a file and read its content
% os:cmd("python check_pow.py").
CheckPow = fun (File) ->
{ok, Content} = file:read_file(File),
Lines = re:split(Content, "\n"),
Splitted = lists:map(fun(X) -> re:split(X, ",") end, Lines),
Result = [ { binary_to_integer(I)
, binary_to_integer(P) =:=
nostrlib_schnorr:pow(binary_to_integer(A)
,binary_to_integer(B)
,binary_to_integer(M))}
|| [I,A,B,M,P] <- Splitted
],
[] =:= lists:filter(fun({_,false}) -> true; (_) -> false end, Result)
end.
true =:= CheckPow("pow.csv").
More than 100k values have been tested to check if the implementation was working, and at this time, no crash was reported. This implementation is working pretty well, and have decent performance result. It could be used in test and development environment without problem, but will probably require small optimization to be used in production. It will be a good reason to work on exponentiation 32 33, fast exponentiation 34 35 36 37 and its derivates optimizations 38 39 40 41 42...
Benchmarking the Solution
Both implementations have been tested with fprof
. This application is available by default on all Erlang/OTP releases and can be really helpful to diagnose an application. Here the quick and dirty way to execute it, these functions needs to be executed in an Erlang shell.
fprof:start().
fprof:apply(nostrlib_schnorr, test, []).
fprof:profile().
fprof:analyse().
The execution time of the first implementations were quite similar, around 7 seconds. In other hand, the last implementation using crypto:mod_pow/3
improved significantly the speed of execution, lowering it down to 1.794 seconds. There is no perfect solution, but this one offer a good compromise between speed and safety, at least for an application in development phase.
Conclusion
This article showed how to implement a cryptographic algorithm with Erlang/OTP, based on a reference implementation in Python, without using any external dependencies. It is a mandatory requirement to implement NIP/0143 and needed by its implementation in Erlang. The code is still very slow, but no optimizations have been done. In less than a week, the Schnorr signature scheme has been fully implemented, tested and documented. This code can already be reused by other Erlang/OTP project just by importing nostrlib_schnorr.erl
file. The code produced was only tested by one developer, and was never audited by professional cryptographer though. Using it in production is risky but will be the subject for another article.
If the readers are a bit curious and interested by the Schnorr signature scheme, the official implementation used by the Bitcoin project can be seen on Github 44 45 46.
https://en.wikipedia.org/wiki/BEAM_(Erlang_virtual_machine) ↩
https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki ↩
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki ↩
https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki ↩
https://github.com/bitcoin/bips/tree/master/bip-0340/reference.py ↩
https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv ↩
Youtube: Lecture 17: Elliptic Curve Cryptography (ECC) by Christof Paar ↩
Youtube: Schnorr signatures for Bitcoin: challenges and opportunities - BPASE '18 ↩
Youtube: Schnorr Digital Signature ↩
https://github.com/WebOfTrustInfo/rwot1-sf/blob/master/topics-and-advance-readings/Schnorr-Signatures--An-Overview.md ↩
https://github.com/RiverFinancial/bitcoinex/blob/master/lib/secp256k1/schnorr.ex ↩
SEC 2: Recommended Elliptic Curve Domain Parameters, section 2.4.1 ↩
Fast Modular Exponentiation by David Egan ↩
Efficient modular exponentiation algorithms by Eli Bendersky ↩
Fast exponentiation by John D. Cook ↩
IACR: Outsoursing Modular Exponentiation in Cryptographic Web Applications ↩
Efficient Elliptic Curve Exponentiation Using Mixed Coordinates ↩
Efficient modular exponential algorithms compatiblewith hardware implementation of public-key cryptography ↩
Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms ↩
An Efficient Montgomery Exponentiation Algorithm for Cryptographic Applications ↩