| tip | title | description | author | discussions-to | status | type | layer | created |
|---|---|---|---|---|---|---|---|---|
14 |
Ed25519 Validation |
Adopt https://zips.z.cash/zip-0215 to explicitly define Ed25519 validation criteria |
Gal Rogozinski (@GalRogozinski) <gal.rogozinski@iota.org>, Wolfgang Welz (@Wollac) <wolfgang.welz@iota.org> |
Active |
Standards |
Core |
2020-10-30 |
The IOTA protocol uses Ed25519 signatures to assure the authenticity of transactions in Chrysalis. However, although Ed25519 is standardized in IETF RFC 8032, it does not define strict validation criteria. As a result, compatible implementations do not need to agree on whether a particular signature is valid or not. While this might be acceptable for classical message signing, it is unacceptable in the context of consensus critical applications like IOTA.
This RFC proposes to adopt ZIP-215 to explicitly define validation criteria. This mainly involves the following sections of the Ed25519 spec:
- decoding of elliptic curve points as described in Section 5.1.3
- validation itself as described in Section 5.1.7
Based on Chalkias et al. 2020 we know that:
- Not all implementations follow the decoding rules defined in RFC 8032, but instead accept non-canonically encoded inputs.
- The RFC 8032 provides two alternative verification equations, whereas one is stronger than the other. Different implementations use different equations and therefore validation results vary even across implementations that follow the RFC 8032.
This lack of consistent validation behavior is especially critical for IOTA as they can cause a breach of consensus across node implementations! For example, one node implementation may consider a particular transaction valid and mutate the ledger state accordingly, while a different implementation may discard the same transaction due to invalidity. This would result in a network fork and could only be resolved outside of the protocol. Therefore, an explicit and unambiguous definition of validation criteria, such as ZIP-215, is necessary.
Furthermore, it is important to note that the holder of the secret key can produce more than one valid distinct signature. Such transactions with the same essence but different signatures are considered as double spends by the consensus protocol and handled accordingly. While this does not pose a problem for the core protocol, it may be a problem for 2nd layer solutions, similar to how transaction malleability in bitcoin presented an issue for the lightning network.
In order to have consistent validation of Ed25519 signatures for all edge cases and throughout different implementations, this RFC proposes explicit validation criteria. These three criteria must be checked to evaluate whether a signature is valid.
Using the notation and Ed25519 parameters as described in the RFC 8032, the criteria are defined as follows:
- Accept non-canonical encodings of A and R.
- Reject values for S that are greater or equal than L.
- Use the equation [8][S]B = [8]R + [8][k]A' for validation.
In the following, we will explain each of these in more detail.
The Curve25519 is defined over the finite field of order p=2255−19. A curve point (x,y) is encoded into its compressed 32-byte representation, namely by the 255-bit encoding of the field element y followed by a single sign bit that is 1 for negative x (see RFC 8032, Section 3.1) and 0 otherwise. This approach provides a unique encoding for each valid point. However, there are two classes of edge cases representing non-canonical encodings of valid points:
- encoding a y-coordinate as y + p
- encoding a curve point (0,y) with the sign bit set to 1
In contrast to RFC 8032, it is not required that the encodings of A and R are canonical. As long as the corresponding (x,y) is a valid curve point, any of such edge cases will be accepted.
The RFC 8032 mentions two alternative verification equations:
- [8][S]B = [8]R + [8][k]A'
- [S]B = R + [k]A'
Each honestly generated signature following RFC 8032 satisfies the second, cofactorless equation and thus, also the first equation. However, the opposite is not true. This is due to the fact that dishonestly generated nonce R and public key A' might have order other than L. Testing whether a point has order L is costly. The first, cofactored equation accepts more nonces and public keys including dishonestly generated ones but lets us skip costly order checks. This has the impact that each secret key has not one but eight corresponding public keys. However all those public keys correspond to different addresses.
There are solutions only satisfying the first equation but not the latter. This ambiguity in RFC 8032 has led to the current situation in which different implementations rely on different verification equations.
Ed25519 also supports batch signature verification, which allows verifying several signatures in a single step, much faster than verifying signatures one-by-one. Without going into detail, there are also two alternative verification equations for the batch verification:
[8][∑zᵢsᵢ] B = [8]∑[zᵢ]Rᵢ + [8]∑[zᵢhᵢ]Aᵢ and its corresponding cofactorless version. However, only cofactored verifications, single and batch, are compatible with each other. All other combinations are inconsistent and can lead to false positives or false negatives (see Chalkias et al. 2020, Section 3.2) for certain edge-cases introduced by an attacker.
Thus, in order to allow batch signature verification and its faster performance in IOTA nodes, the cofactored version must be used for validation, i.e. the group equation [8][S]B = [8]R + [8][k]A' for the single verification.
Since non-canonical encodings of A and R are allowed, it is crucial to also specify which representation must be used for the hash functions:
- The provided binary encodings of A and R must be used as input to the hash function H instead of their canonical – and potentially different – representation.
- During transaction validation, when the public key A is checked against the output's address, the provided binary encoding must be used for the BLAKE2b-256 hash instead of its canonical representation.
The non-negative integer S is encoded into 32 bytes as part of the signature. However, a third party could replace S with S' = S + n·L for any natural n with S' < 2256 and the modified signature R || S' would still pass verification. Requiring a value less than L resolves this malleability issue. Unfortunately, this check is not present in all common Ed25519 implementations.
Analogous to RFC 8032, the encoding of S must represent an integer less than L.
It is not possible for an external party to mutate R and still pass verification. The owner of the secret key, however, can create many different signatures for the same content: While Ed25519 defines a deterministic method of calculating the integer scalar r from the private key and the message, it is impossible to tell during signature verification if the point R = [r]B was created properly or any other scalar has been used.
As a result, there is a practically countless amount of different valid signatures corresponding to a certain message and public key.
We allow users to have a zero-scalar secret key and consider eight corresponding public keys valid. However, users should not use it as it is equivalent to publishing one's secret key. This also has the impact that any valid signature produced with a zero-scalar secret key will authenticate any message thus making it "super"-malleable.
The test vectors are taken directly from Chalkias et al. 2020. Here, pub_key corresponds to the encoding of A and address is a 33-byte Ed25519 Address as described in TIP-7. The address is computed by hashing A. As mentioned in the paper, for test case #10 the key A is reduced before hashing, while in the others it is not. The key valid denotes whether the corresponding item represents a valid signature for the provided address and message or not.
- Allowing non-canonical encodings is a direct contradiction of RFC 8032 and rather unintuitive. Furthermore, it introduces alternative encodings for a handful of points on the curve. Even though such points will, for all practical purposes, never occur in honest signatures, it still theoretically introduces an external party malleability vector.
- The cofactored validation is computationally slightly more expensive than the cofactorless version since it requires a multiplication by 8.
In the IOTA protocol, the Transaction ID corresponds to the hash over the entire transaction including the actual signature bytes. Therefore, it is absolutely crucial that (valid) signatures are not malleable by a public attacker, i.e. that the used Ed25519 variant is strongly-unforgeable. Allowing non-canonical point encodings does not introduce the same attack vector. As such, both options would lead to valid Ed25519 variants.
Unfortunately, the Ed25519 ref10 reference implementation as well as other implementations accept non-canonical points. As such, rejecting those inputs now would introduce a breaking change. While this might be acceptable for the IOTA protocol itself, since no Ed25519 signatures have been added to the ledger prior to this RFC, other consensus-critical applications require this backward compatibility with previously accepted signatures. Due to these considerations, the criterion was included in ZIP-215 to allow a seamless transition for existing consensus-critical contexts. This RFC aims to rather follow the existing ZIP-215 specification for compatibility and maintainability than to create a new standard.
Using the cofactorless validation poses a similar breaking change since signatures accepted by implementations using the cofactored validation would then be rejected. More importantly, however, in order to be able to use the much faster batch verification, the cofactored version is required.
Copyright and related rights waived via CC0.