# SlowMist: Ed25519 Implementation Principles and Scalability Issues

Ed25519 is an elliptic curve-based digital signature algorithm that is efficient, secure, and widely used. It is used in TLS 1.3, SSH, Tor, ZCash, WhatsApp, and Signal, among others. This article mainly discusses the following:

1. Introduce some group theory knowledge to give everyone an intuition for the principles of Ed25519 and its scalability issues. If you want to understand it more deeply, you need to refer to other materials;

2. Explain the implementation of ed25519 in version 1.0.1 of the rust library ed25519-dalek;

3. Explain the issue of scalability of the library.

Mathematical Points Review

Definition and Properties of Groups

Group theory is the content of abstract algebra research, but some ideas of abstract algebra are very familiar to programmers. Inheritance in object-oriented programming is a good example. We all know that after a subclass inherits from a superclass, it can use the methods defined in the superclass. Abstract algebra can be understood as defining some properties of an abstract data structure, and theorems derived from these properties hold for all subclasses.

Using the metaphor just now, let’s see how the data structure group is defined. Many interesting theorems can be derived from this: A few examples: ## Group Theory Terminology Lagrange’s Theorem

Now let’s introduce a very interesting theorem, the derivation of this theorem is referenced in the video at the end of the article.

“The order of a group can be divided by the order of a subgroup.”

Why is this theorem interesting? Not only because the proof process strings together many of the concepts just introduced, but also because of the following conclusion: Implementation of Ed25519

Now let’s talk about Ed25519, which is one of the EdDSA algorithms. EdDSA has 11 parameters (https://datatracker.ietf.org/doc/html/rfc8032#autoid-3), and the specific selection of these parameters has a significant impact on the security and performance of the algorithm. For the specific selection of Ed25519, please refer to the link (https://datatracker.ietf.org/doc/html/rfc8032#autoid-9).

Additionally, it’s worth mentioning that this algorithm uses an elliptic curve called Curve25519 (https://datatracker.ietf.org/doc/html/rfc7748#autoid-5). As for elliptic curves, all we need to know is that there are many, many points on them, and that adding those points together results in a new point that is also on the curve. These points and their addition form a group. Note that the elliptic curve addition (https://www.wikiwand.com/en/Elliptic_curve_point_multiplication) has a special definition.

We agree on the following notation: This is an interactive algorithm, but it doesn’t matter. There’s a technique called the Fiat – Shamir heuristic (https://link.springer.com/chapter/10.1007%2F3-540-47721-7_12), which can transform any interactive algorithm into a non-interactive algorithm. In the end, we’ll use a non-interactive algorithm.

Signature algorithms provide us with the following API:   Code address (https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/public.rs#L322-L355)

# Scalability Issue

There are many things to pay attention to when implementing and using cryptographic algorithms. When we say a digital signature algorithm is secure, we generally mean that even if an attacker can obtain the signature of any message (Chosen Message Attack), the attacker still cannot forge the signature. Ed25519 satisfies this property, but it does not mean that Ed25519 is absolutely secure. The original paper also mentions that the scalability issue is acceptable, and the original algorithm has this issue.  