Schnorr Signatures in Go

Figured that while I’m getting into the mess of cryptography and some funky prime curve cyclic number theory, and learning Golang for a new startup I’m working on, I might as well try cover the Schnorr signature scheme in Go.

Let’s work with an asymmetric cryptosystem based off of the discrete log problem (any ‘ole one that deals with elliptic curves would do).

To simplify operations working with elliptic curves, we’ll utilize a handy library dedis/kyber.

Here are our imports as usual:

import (
   "gopkg.in/dedis/kyber.v2"
   "gopkg.in/dedis/kyber.v2/group/edwards25519"
   "fmt"
)

To signify how nice kyber is as a library, we define the base point of an elliptic curve to be a generator G. By picking a random scalar to be our private key x, we can derive our public key y which is y = x * G.

In other words, we perform operations in the additive group of our elliptic curve x times.

Everything above could be represented in the following code:

privateKey := curve.Scalar().Pick(curve.RandomStream())
publicKey := curve.Point().Mul(privateKey, curve.Point().Base())

fmt.Printf("Generated private key: %s\n", privateKey)
fmt.Printf("Derived public key: %s\n\n", publicKey)

As you may have guessed from the curve, we’re going to be working with the elliptic curve group Edwards 25519 which is popularly used by another signature scheme variant known as EdDSA.

For our hashing function which will fingerprint our message to be signed, we’ll be using SHA256.

We’ll also define a nice struct to hold some set of data that’ll represent our messages signature, and our plain-text hashing function

var curve = edwards25519.NewBlakeSHA256Ed25519()
var sha256 = curve.Hash()

type Signature struct {
   r kyber.Point
   s kyber.Scalar
}
func Hash(s string) kyber.Scalar {
   sha256.Reset()
   sha256.Write([]byte(s))

   return curve.Scalar().SetBytes(sha256.Sum(nil))
}

So, let’s dive into the scheme.

Working around the discrete log scenario, we will be taking advantage of a trapdoor function which basically stands for a function whose inverse is extremely difficult to compute.

Thankfully, as the hash we are choosing (SHA256) has a great property of being incredibly resistant to collision attacks, it works great for the Schnorr scheme as follows.

We define a signature verification function where:

H'(m, s, e) = H(m || s * G + e * y)
… which is defined to have verified some set of data when H'(m, s, e) = e.

m is the message being signed, s is part 1 of our signature, and e is the hash of our message concatenated with a variable r which is part 2 of our signature.

m, r, s, e, G, y are distributed publicly for users to verify that some user under an asymmetric key pair defined by x, y truly signed a given message m.

To prove that only a user (or users if under attack) who owns such a key pair could possibly create the signature components r, s for message m such that H’(m, s, e) = e, recall that y = x * G :

H'(m, s, e) = e = H(m || s * G + e * y)
e = H(m || s * G + e * y)
e = H(m || s * G + e * x * G)
e = H(m || G(s + e * x))

As s, e and m are already known, the only way to have the conditional statement being e == e being true is that the private key x is known by a user. Q.E.D…?

To sign a message m and derive the signature components r and s, we pick a random scalark to be a seed for our signature scheme.

We operate in the multiplicative group of our curve k times around our generator point G to derive r = k * G. k is what we define to be our residual sum that makes/breaks the whole scheme, as we define:

k = s + e * x ; hence H'(m, s, e) = H(m || k * G) = H(m || r) = e .

Hence, after deriving r, get e = H(m || r) and derive:

s = k - e * x

and you’ve got your signature (r, s) ready!

In Go, this would be how you’d represent it:

// m: Message
// x: Private key
func Sign(m string, x kyber.Scalar) Signature {
   // Get the base of the curve.
   g := curve.Point().Base()

   // Pick a random k from allowed set.
   k := curve.Scalar().Pick(curve.RandomStream())

   // r = k * G (a.k.a the same operation as r = g^k)
   r := curve.Point().Mul(k, g)

   // Hash(m || r)
   e := Hash(m + r.String())

   // s = k - e * x
   s := curve.Scalar().Sub(k, curve.Scalar().Mul(e, x))

   return Signature{r: r, s: s}
}

Note however, every single time we sign messages we should always pick a completely new k with a truly random source of information (you could even seed it with H(m || x) given H(x)'s unique pre-image property!).

With k = s + e * x, lets get a set of signatures for two different messages(r0, s0, e0) and (r1, s1, e1).

** note thatron the i'th index is derived from e and s on the i'th index through: r = s * G + e * y .

If k were to be the same for the two messages, denote:

k = s0 + e0 * x = s1 + e1 * x
s0 + e0 * x = s1 + e1 * x
(s0 - s1) = (e1 - e0) * x
(s0 - s1) / (e1 - e) = x

… and hence, if you aren’t careful, with a fixed k you could be leaking the user’s private key x!

One cool thing you could derive out of this equation given the signature components, and message is the user’s public key as well.

This could be one method for verifying a signature by deriving the public key from the signature.

Simply recall that as r = s * G + e * y, we can derive y by:

y = (r - s * G) * (1 / e)

… which in Go can easily be represented as:

// m: Message
// S: Signature
func PublicKey(m string, S Signature) kyber.Point {
   // Create a generator.
   g := curve.Point().Base()

   // e = Hash(m || r)
   e := Hash(m + S.r.String())

   // y = (r - s * G) * (1 / e)
   y := curve.Point().Sub(S.r, curve.Point().Mul(S.s, g))
   y = curve.Point().Mul(curve.Scalar().Div(curve.Scalar().One(), e), y)

   return y
}

However, a much nicer method to verify a signature would be to see if the multiplicative and additive operations on our elliptic curve group yields the same point positioned as s * G.

This would thus not require us to compute using our expensive hash function two times per verification round.

With signature components someone sends us (r, s), and their public key and plain-text message, we first attain e = H(m || r) and derive:

r = s * G + e * y
s * G = r - e * y

… and check if the derived s * G from r is equivalent to purely calculating s * G . Remember, the only way s * G would match is if the components (r, s) derived using the asymmetric key pair (x, y) truly belonged and was only known by a particular person.

Otherwise, the trapdoor function would not be fulfilled and hence the scheme remains secure.

Now, in Go…

// m: Message
// s: Signature
// y: Public key
func Verify(m string, S Signature, y kyber.Point) bool {
   // Create a generator.
   g := curve.Point().Base()

   // e = Hash(m || r)
   e := Hash(m + S.r.String())

   // Attempt to reconstruct 's * G' with a provided signature; s * G = r - e * y
   sGv := curve.Point().Sub(S.r, curve.Point().Mul(e, y))

   // Construct the actual 's * G'
   sG := curve.Point().Mul(S.s, g)

   // Equality check; ensure signature and public key outputs to s * G.
   return sG.Equal(sGv)
}

… and now our Schnorr scheme is ready for whatever! Better distributed DAG pruning operations perhaps.

What’s awesome about this was that it was achieved all through some high school algebra (which gets hindered a bit by elliptic curve group operations).

Here’s a little test case I made with a nice helper print function:

func (S Signature) String() string {
   return fmt.Sprintf("(r=%s, s=%s)", S.r, S.s)
}
func main() {
   privateKey := curve.Scalar().Pick(curve.RandomStream())
   publicKey := curve.Point().Mul(privateKey, curve.Point().Base())

   fmt.Printf("Generated private key: %s\n", privateKey)
   fmt.Printf("Derived public key: %s\n\n", publicKey)

   message := "We're gonna be signing this!"

   signature := Sign(message, privateKey)
   fmt.Printf("Signature %s\n\n", signature)

   derivedPublicKey := PublicKey(message, signature)
   fmt.Printf("Derived public key: %s\n", derivedPublicKey)
   fmt.Printf("Are the original and derived public keys the same? %t\n", publicKey.Equal(derivedPublicKey))
   fmt.Printf("Is the signature legit w.r.t the original public key? %t\n\n", Verify(message, signature, publicKey))

   fakePublicKey := curve.Point().Mul(curve.Scalar().Neg(curve.Scalar().One()), publicKey)
   fmt.Printf("Fake public key: %s\n", fakePublicKey)
   fmt.Printf("Is the signature legit w.r.t a fake public key? %t\n", Verify(message, signature, fakePublicKey))
}

Now, when it comes towards applications of utilizing Schnorr as a form of partial group/threshold signatures (ring signatures) in all kinds of fun decentralized applications, it is relatively easily to implement.

Though, I would like to leave that as an exercise to you.

Feel free to read up on some more of the math here: https://www.deadalnix.me/2017/02/17/schnorr-signatures-for-not-so-dummies/

Enjoy :). If you want the source code up on Github, let me know.

Also, Read

• The Best Crypto Trading Bots
• The Best Bitcoin Hardware wallet
• The Best Crypto Tax Software
• Best Crypto Trading Platforms
• Best Wallet for Uniswap
• Best Crypto Lending Platforms
• Top DeFi Projects
• Bitsgap review — A Crypto Trading Bot That Makes Easy Money
• Quadency Review- A Crypto Trading Bot Made For Professionals
• 3commas Review | An Excellent Crypto Trading Bot
• 3Commas vs Cryptohopper
• The Idiots Guide to Margin Trading on Bitmex
• The Definitive Guide to Crypto Swing Trading
• Bitmex Advanced Margin Trading Guide
• Best Crypto APIs for Developers
• Crypto arbitrage guide: How to make money as a beginner
• Top Bitcoin Node Providers
• Best Crypto Charting Tool

Get Best Software Deals Directly In Your Inbox