Threshold Ed25519 — It’s Just Magical And Fit For A More Resilient and Trusted World

Threshold Ed25519 — It’s Just Magical And Fit For A More Resilient and Trusted World

Well, Satoshi selected ECDSA for his cryptocurrency, and it has worked well. There were a few little problems along the way, such as in not selecting a random nonce value, and also in repeating a nonce. But overall it has proven to be a good selection. But, is it the future of digital signatures? Well, it’s not going to go away, but there’s an even better signature method: Ed25519. If there is no need to keep compatibility with Bitcoin and Ethereum, Ed25519 is an excellent selection. In fact, IOTA selected it for their signing infrastructure, and many distributed applications are now moving away from ECDSA and moving towards Ed25519.

The key to the success of Ed25519 is the usage of the Schnorr signature scheme, and where we can basically aggregate public keys into a single signing key. A basic adding operation is all that is required.

But, Ed25519 also has a magical secret … it allows a private key to be split into shares using a threshold policy, and then for each party to sign for a transaction using their secret share. It is magical! Basically, we could create a key pair on a computer, and then split the private key into a number of shares and distribute it onto trusted nodes. When required to sign a transaction, each node can then sign with their part of the private key share, and then the signer could gather these secrets and aggregate them together to create a valid signature, and which matches the original public key.

A bit of theory

If you want a doodle, here is the basic method used in Ed25519:

Let’s have a quick look at the method that is used with Ed25519 [here]:

Overall we have a number of rounds:

And that’s it. We have commitments, and where each of the parties works together to create a shared signature and never reveal the private key used for the signature (R,S). The public key becomes the aggregation of the public keys from each party.

The following is an outline of the code using the Coinbase Krytology library [here]:

package main

import (
	"fmt"
	"os"

	"github.com/coinbase/kryptology/pkg/ted25519/ted25519"
)

func main() {

	msg := "Hello 123"

	argCount := len(os.Args[1:])

	if argCount > 0 {
		msg = os.Args[1]
	}
	message := []byte(msg)

	config := ted25519.ShareConfiguration{T: 2, N: 3}
	pub, secretShares, _, _ := ted25519.GenerateSharedKey(&config)

	// Each party generates a nonce and we combine them together into an aggregate one
	noncePub1, nonceShares1, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[0], pub, message)
	noncePub2, nonceShares2, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[1], pub, message)
	noncePub3, nonceShares3, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[2], pub, message)

	nonceShares := []*ted25519.NonceShare{
		nonceShares1[0].Add(nonceShares2[0]).Add(nonceShares3[0]),
		nonceShares1[1].Add(nonceShares2[1]).Add(nonceShares3[1]),
		nonceShares1[2].Add(nonceShares2[2]).Add(nonceShares3[2]),
	}

	noncePub := ted25519.GeAdd(ted25519.GeAdd(noncePub1, noncePub2), noncePub3)

	sig1 := ted25519.TSign(message, secretShares[0], pub, nonceShares[0], noncePub)
	sig2 := ted25519.TSign(message, secretShares[1], pub, nonceShares[1], noncePub)
	sig3 := ted25519.TSign(message, secretShares[2], pub, nonceShares[2], noncePub)

	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("Public key: %x\n", pub.Bytes())

	fmt.Printf("\nThreshold Sig1: %x\n", sig1.Bytes())
	fmt.Printf("Threshold Sig2: %x\n", sig2.Bytes())
	fmt.Printf("Threshold Sig3: %x\n\n", sig3.Bytes())

	sig, _ := ted25519.Aggregate([]*ted25519.PartialSignature{sig1, sig3}, &config)
	fmt.Printf("Rebuild signature with share 1 and 3: %x\n", sig)
	sig, _ = ted25519.Aggregate([]*ted25519.PartialSignature{sig2, sig3}, &config)
	fmt.Printf("Rebuild signature with share 2 and 3: %x\n", sig)

	ok, _ := ted25519.Verify(pub, message, sig)

	if ok {
		fmt.Printf("\nSignature verified")
	} else {
		fmt.Printf("\nSignature unverified")
	}

}

A sample run with the message of “Hello” and merging shares 1 and 3, and 2 and 3 [here]:

Message: Hello
Public key: 32f3de6fe91c3120d1ed6536181aaf4a17a3cc414c15cbcaaf7e76734770a723

Threshold Sig1: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bee19a3df5ec71a880889bc69159794c59c1eb18b816414dc928d30e88c27ff0b
Threshold Sig2: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6b36f588b97b9105677d2a9bc7a66a0f63573f83a05007f507b093b96ea8d23604
Threshold Sig3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6b6ba464f0b2be029ec86871c816386915126055b51faad533cd9942f5c37d6e0c

Rebuild signature with share 1 and 3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bb96ac7a8279a1d51bd4ae668a5c93a13e2fdde76b2c133b07587a761717cc703
Rebuild signature with share 2 and 3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bb96ac7a8279a1d51bd4ae668a5c93a13e2fdde76b2c133b07587a761717cc703

Signature verified

Conclusions

This is a wonderful method, and would allow us to distribute private keys across a distributed network, and where none of the parties has the signing keys. We can support Byzantine fault tolerance with a few malicious parties, or which can fail. Here’s the code:

https://asecuritysite.com/signatures/ted25519

In terms of creating a threshold method for ECDSA (as used in Bitcoin and Ethereum), it is not that easy, but here are examples:

If you don’t have to keep compatibility with Bitcoin, then Ed25519 is a great way to go, as we see with the IOTA network.