ECDSA vs Ed25519

ECDSA and Schnorr signatures(Ed25519) are two cryptographic techniques used to ensure the authenticity and integrity of digital messages.

We are writing this post to explain the difference between Ethereum and Ton’s signature scheme and help the developers integrate with Eigen zkVM. More posts about the integration will follow up in the future.

ECDSA

ECDSA is an adaptation of the Digital Signature Algorithm (DSA) that works over elliptic curve groups. The main principles involve:

1. Key Generation:

• Private Key: Select a random integer d as the private key, where d is less than the order of the elliptic curve group.
• Public Key: Compute the public key Q by multiplying the generator point G of the curve by the private key d (i.e., Q=dG).

2. Signature Generation:

• Select a random integer k for each signature.
• Compute the point (𝑥_1,𝑦_1)=𝑘𝐺
• Calculate 𝑟=𝑥_1mod 𝑛 (if r=0, choose a different k).
• Compute 𝑠=𝑘^{−1}(𝐻(𝑚)+𝑟𝑑)mod 𝑛 where H(m) is the hash of the message.
• The signature is the pair (r, s).

3. Signature Verification:

• Verify that r and s are within the valid range.
• Compute 𝑢_1=𝑠^{−1}𝐻(𝑚)mod 𝑛 and 𝑢_2=𝑠^{−1}𝑟mod 𝑛
• Calculate the point (𝑥_1,𝑦_1)=𝑢_1 𑁦𝐺+𝑢_2 𑁦 𝑄
• The signature is valid if 𝑥1mod 𝑛=𝑟.

Schnorr Signature

Schnorr signatures are known for their simplicity and security properties. The key steps are:

1. Key Generation:

• Like ECDSA, select a private key a and compute the public key A=a 𑁦G.

2. Signature Generation:

• Choose a random k and compute R=k 𑁦G.
• Compute the challenge e=H(R∥A∥m) where ∥ denotes concatenation.
• Calculate s=k−aemodn.
• The signature is the pair (R, s).

3. Signature Verification:

• Compute e=H(R∥A∥m).
• Check if s 𑁦G=R+e 𑁦A. If this equation holds, the signature is valid.

ECDSA and Schnorr signatures Comparison

1. Mathematical Foundations

• ECDSA: It is based on the principles of elliptic curve cryptography and the Digital Signature Algorithm (DSA). ECDSA generates a signature in two parts, commonly denoted as (r, s), which depend on the elliptic curve parameters, a randomly chosen number, the hash of the message, and the signer’s private key.
• Schnorr: This algorithm relies on the properties of elliptic curves and simple modular arithmetic. Schnorr signatures can be more straightforward and more amenable to certain algebraic manipulations compared to ECDSA. It produces a single value as a signature, often simpler to handle with less room for error in its implementation.

2. Signature Size

• ECDSA: The signature size is typically twice the size of the key. For example, a 256-bit key results in a 512-bit signature.
• Schnorr: It generally offers smaller and more compact signatures compared to ECDSA. For the same security level, Schnorr signatures are shorter, making them more efficient in terms of storage and bandwidth.

3. Security

• ECDSA: The security of ECDSA depends significantly on the quality of the randomness used during signature generation. Poor randomness can lead to security vulnerabilities.
• Schnorr: It is considered to offer better security characteristics in some respects. One of the advantages is that it is non-malleable, which means the signature cannot be changed without access to the private key.

4. Computational Efficiency

• ECDSA: The computation involves multiple steps of modular arithmetic, which can be computationally intensive.
• Schnorr: Typically requires fewer computations than ECDSA, leading to faster signature verification, which is advantageous for systems where verification speed is critical.

5. Linearity

• Schnorr: One significant advantage is its linearity, which allows for simple and secure multi-signature schemes and signature aggregation. This property is highly beneficial in systems like blockchain, where reducing transaction size is crucial.
• ECDSA: Does not naturally support such features due to its more complex mathematical structure, making it less favorable for systems requiring multi-signature capabilities.

6. Adoption and Usage

• ECDSA: Widely adopted and used in many standards like SSL/TLS, Bitcoin, and other blockchain technologies.
• Schnorr: Although not as widely used historically, its adoption is increasing, especially with its recent integration into Bitcoin (via Taproot), which enhances the privacy and efficiency of transactions.

Schnorr signatures are generally seen as an improvement over ECDSA in many respects, particularly in terms of simplicity, efficiency, and multi-signature capabilities. However, ECDSA remains popular due to its widespread deployment and integration into existing digital infrastructures. Their choice often depends on specific application requirements and existing system compatibility.