Towards Web3: Ed25519, Ed448 and Ed2551-Dilithium

When it all comes down to it, Web 3 — at its lowest layer — involves the trusted digital signing of transactions and will start to properly…

Towards Web3: Ed25519, Ed448 and Ed2551-Dilithium

When it all comes down to it, Web 3 — at its lowest layer — involves the trusted digital signing of transactions and will start to properly integrate digital trust into our Internet. It will support the true integration of the digital identity of the citizen into our digital world, and in the integration of their wallets (and which would store their private key).

The two main methods for achieving a digital signature at the current time are ECDSA (as used by Bitcoin and Ethereum) and EdDSA (as used by IOTA and many other applications). Both have their advantages. If we need compatibility with EVM (Ethereum Virtual Machine), we will probably focus on ECDSA. This signature method also allows us to derive the public key used to verify the transaction, which makes it easier to check a signature against a public identifier (and which is derived from a private key). With EdDSA, we have special features which allow us to aggregate the public keys used for the signing process into a single verifiable public key, along with being able to aggregate digital signatures into a single verifiable signature. Another key feature of EdDSA is that it allows for computation to be distributed, which is a key feature of Web 3, and where we break away from the centralised approach of our existing Internet.

Overall, the EdDSA method is probably more scalable into the future, so let’s have a look at it, and implement it using the Cloudflare CIRCL library.

Ed25519 and Ed448

With digital signatures, we create a key pair: a private (or secret) key and a public (or verifier) key. We can store this key pair in our wallet, and then use the key when we have to sign for something. Basically for a signature, we take a hash of a message and then apply our private key to produce a signature. This is typically in the form of an R and an s value (R,s). These values can then be used with the public key and the message to verify the signature.

With Ed25519 we use the well-known Curve 25519 elliptic curve, and convert it into a digital signature method. This uses 256-bit values for the private and public key and gives us 128-bit equivalent security. Overall it uses a prime number of:

2²⁵⁵-19

For 224-bit security, we would use Ed448 and which uses Curve 448. This uses a 448-bit prime number:

2⁴⁴⁸-2²²⁴-1

With Ed25519, Bob first generates a 256-bit random number for his private key (priv) and then creates the public key with:

pub=H(priv)[:32]⋅B

and where B is the base point on the curve, and where H() is a hash function (SHA-512). In this case, we take the lower 32 bytes of the SHA-512 hash. Normally, we just define this as the y coordinate of the point. The public key is thus 32 bytes long (256 bits). To compute the signature, we generate:

r=H_int(H(priv)[32:]||M)(mod l)

and where H_int() is a hash function (SHA-512) and converted to an integer value. In this case, we take the upper 32 bytes for the calculation. The value of l is the order of the curve. Then M is the byte value of the message. With “||” we append the bytes together. We then convert this to a point on the curve with:

R=r⋅B

Next, we compute:

h=Hint(R||pub||M)(mod l)

and:

s=Hint(priv))[:32]

S=(r+h⋅s)(modl)

The signature is then (R,S). Bob sends M, R, S and pub to Alice. Alice then computes:

k=H(R||pub||M)(mod l)

P1=S⋅B

P2=R+k⋅pub

and if P1 is equal to P2, the signature verifies. This works because:

P1=S⋅B=(r+h⋅s(modl))⋅B=r⋅B+h⋅s⋅B=R+h⋅pub=P2

Note that l is the order of the curve (l=2252+27742317777372353535851937790883648493).

The great advantage of using Ed25519 over ECDSA is that we can aggregate signatures and public keys. Here is an overview of the maths involved:

There are three main modes [RFC 8032] that we can have: Ed25519 (pure EdDSA, as we have defined above), Ed25519Ph (where the message is hashed), and Ed25519Ctx (and where we add a context message):

Ed25519 (pure Ed25519). r=Hint(H(priv)[32:]||M)(mod l)
Ed25519Ph (with pre-hash). r=Hint(H(priv)[32:]||H(M))(mod l). In this case, the message will be hashed with SHA-512 before it is used.
Ed25519Ctx (with context). r=Hint(H(priv)[32:]||M||Ctx)(mod l) and where Ctx is a context string.

Coding

The following is an outline of the code that uses the Cloudflare CIRCL library [here]:

package main

import (
	"fmt"
	"os"

	"github.com/cloudflare/circl/sign"
	"github.com/cloudflare/circl/sign/schemes"
)

func main() {
	modename := "Ed25519"

	m := "Hello"

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

	if argCount > 0 {
		modename = os.Args[1]
	}

	if argCount > 1 {
		m = os.Args[2]
	}

	mode := schemes.ByName(modename)

	pk, sk, _ := mode.GenerateKey()

	msg := []byte(m)
	opts := &sign.SignatureOpts{}
	signature := mode.Sign(sk, msg, opts)

	fmt.Printf("CIRCL Signatures\n\n")
	fmt.Printf("Signature method: %s \n", modename)
	fmt.Printf("Message: %s \n\n", msg)
	skbin, _ := sk.MarshalBinary()
	fmt.Printf("Private key: %x [showing first 32 bytes]\n", skbin[:32])
	fmt.Printf(" - Private key length: %d\n", len(skbin))
	pkbin, _ := sk.MarshalBinary()
	fmt.Printf("Public key: %x [showing first 32 bytes]\n", pkbin)
	fmt.Printf(" - Public key length: %d\n", len(pkbin))

	fmt.Printf("Signature: %x [showing first 32 bytes]\n", signature[:32])
	fmt.Printf(" - Signature length: %d \n", len(signature))

	if !mode.Verify(pk, msg, signature, opts) {
		panic("Signature has NOT been verified!")
	} else {
		fmt.Printf("Signature has been verified!")
	}

A sample run for Ed25519 is [here]:

CIRCL Signatures

Signature method: Ed25519 
Message: Hello

Private key: 9b5ab3255af6dadc6617d4561920ca1f01e7471887f171a5a18a2fde5776073d [showing first 32 bytes]
 - Private key length: 64
Public key: 9b5ab3255af6dadc6617d4561920ca1f01e7471887f171a5a18a2fde5776073d [showing first 32 bytes]
 - Public key length: 64
Signature: 3d97019e0420f43098044280f021fef52d347da25832a4177b5052786f4edfc3 [showing first 32 bytes]
 - Signature length: 64 
Signature has been verified!

A sample run for Ed448 is [here]:

CIRCL Signatures

Signature method: Ed448 
Message: Hello

Private key: e1be32ff5822ef8a44adf5e290e79dbda1db9e6ef6b2857f592cd53b866e8b77 [showing first 32 bytes]
 - Private key length: 114
Public key: e1be32ff5822ef8a44adf5e290e79dbda1db9e6ef6b2857f592cd53b866e8b77 [showing first 32 bytes]
 - Public key length: 114
Signature: d76ea76c46841572edd7142f1e3598199d563e0de5a6fd2ff7bdde6de331ee89 [showing first 32 bytes]
 - Signature length: 114 
Signature has been verified!

And we can even integrate a quantum robust element to Ed25519. Here is a sample run for Ed25519-Dilithium2 [here]:

CIRCL Signatures

Signature method: Ed25519-Dilithium2 
Message: Hello

Private key: 73649b69fcbaf7ef753bedbebd598fcf7a4cc8bd85dc8ec3c0e564389893e5ec [showing first 32 bytes]
 - Private key length: 2560
Public key: 73649b69fcbaf7ef753bedbebd598fcf7a4cc8bd85dc8ec3c0e564389893e5ec [showing first 32 bytes]
 - Public key length: 2560
Signature: c63a0b2c213d47020f1c2283f14531e2647bc402526a476c559a2c81c537aee2 [showing first 32 bytes]
 - Signature length: 2484 
Signature has been verified!

A sample run for Ed448-Dilithium3 :

CIRCL Signatures

Signature method: Ed448-Dilithium3 
Message: Hello

Private key: 8e521eed1cce7b5010e1b88472449f5bb9181142e9751e84f099d8a14f7b0ce3 [showing first 32 bytes]
 - Private key length: 4057
Public key: 8e521eed1cce7b5010e1b88472449f5bb9181142e9751e84f099d8a14f7b0ce3 [showing first 32 bytes]
 - Public key length: 4057
Signature: ae6ac74a19dc0842e9abe49522c6617f32b9fb867de6d4b93b553176fed6ee7f [showing first 32 bytes]
 - Signature length: 3407 
Signature has been verified!

Conclusions

We have built an Internet that has very little trust built into it, and we have patched it with simple methods. Our digital future must be towards an infrastructure that properly integrates trust, and the usage of private keys and digital signatures must be at the core of this, and where we move away from a world that integrates fake trust.