ERC-2333: BLS12-381 Key Generation

Simple Summary

---

This EIP is a method based on a tree structure for deriving BLS private keys from a single source of entropy while providing a post-quantum cryptographic fallback for each key.

Abstract

---

This standard is a method for deriving a tree-hierarchy of BLS12-381 keys based on an entropy seed. Starting with the aforementioned seed, a tree of keys is built out using only the parent node's private key and the index of the desired child. This allows for a practically limitless number of keys to be derived for many different purposes while only requiring knowledge of a single ancestor key in the tree. This allows for keys, or families thereof, to be provisioned for different purposes by further standards.

In addition to the above, this method of deriving keys provides an emergency backup signature scheme that is resistant to quantum computers for in the event that BLS12-381 is ever deemed insecure.

A note on purpose

---

This specification is designed not only to be an Ethereum 2.0 standard, but one that is adopted by the wider community who have adopted BLS signatures over BLS12-381. It is therefore important also to consider the needs of the wider industry along with those specific to Ethereum. As a part of these considerations, it is the intention of the author that this standard eventually migrate to a more neutral repository in the future.

Motivation

---

Deficiencies of the existing mechanism

The curve BLS12-381 used for BLS signatures within Ethereum 2.0 (alongside many other projects) mandates a new key derivation scheme. The most commonly used scheme for key derivation within Ethereum 1.x is BIP32 (also known as HD derivation) which deems keys greater than the curve order invalid. Based on the order of the private key subgroup of BLS12-381 and the size of the entropy utilised, more than 54% of keys generated by BIP32 would be invalid. (secp256k1 keys derived by BIP32 are invalid with probability less than 1 in 2^-127.)

Establishing a multi-chain standard early on

By establishing a standard before the first users begin to generate their keys, the hope is that a single standard is highly pervasive and therefore can be assumed to be the method by which the majority of keys are provided. This is valuable for two reasons, firstly in order for a post-quantum backup mechanism to be effective, there needs to be an enshrined mechanism whereby users can switch to a post-quantum signature scheme with pre-shared public keys (something this EIP provides at 0 extra storage cost). Secondly, this unifies the inter- and intra-chain ecosystem by having common tooling ideally allowing users to switch between key-management systems.

A post-quantum backup

This key derivation scheme has a Lamport key pair which is generated as a intermediate step in the key generation process. This key pair can be used to provide a Lamport signature which is a useful backup in the event of BLS12-381 no longer being considered secure (in the event of quantum computing making a sudden advancement, for example). The idea is the Lamport signature will act as a bridge to a new signature scheme which is deemed to be secure.

Specification

---

Version

Due to the evolving BLS signatures CFRG draft (currently v4), the KeyGen function was updated, meaning that hkdf_mod_r no longer reflected what appeared in the BLS standard. This EIP was updated on the 17th of September 2020 to reflect this new method for deriving keys, if you are implementing this EIP, please make sure your version is up to date.

Specification

Keys are defined in terms of a tree structure where a key is determined by the tree's seed and a tree path. This is very useful as one can start with a single source of entropy and build out a practically unlimited number of keys. The specification can be broken into two sub-components: generating the master key, and constructing a child key from its parent. The master key is used as the root of the tree and then the tree is built in layers on top of this root.

The Tree Structure

The key tree is defined purely through the relationship between a child-node and its ancestors. Starting with the root of the tree, the master key, a child node can be derived by knowing the parent's private key and the index of the child. The tree is broken up into depths which are indicated by / and the master node is described as m. The first child of the master node is therefore described as m / 0 and m / 0's siblings are m / i for all 0 <= i < 2**32.

Key derivation

Every key generated via the key derivation process derives a child key via a set of intermediate Lamport keys. The idea behind the Lamport keys is to provide a post-quantum backup in case BLS12-381 is no longer deemed secure. At a high level, the key derivation process works by using the parent node's privkey as an entropy source for the Lamport private keys which are then hashed together into a compressed Lamport public key, this public key is then hashed into BLS12-381's private key group.

IKM_to_lamport_SK

Inputs

• IKM, a secret octet string
• salt, an octet string

Outputs

• lamport_SK, an array of 255 32-octet strings

Definitions

• HKDF-Extract is as defined in RFC5869, instantiated with SHA256
• HKDF-Expand is as defined in RFC5869, instantiated with SHA256
• K = 32 is the digest size (in octets) of the hash function (SHA256)
• L = K * 255 is the HKDF output size (in octets)
• "" is the empty string
• bytes_split is a function takes in an octet string and splits it into K-byte chunks which are returned as an array

Procedure

parent_SK_to_lamport_PK

Inputs

• parent_SK, the BLS Secret Key of the parent node
• index, the index of the desired child node, an integer 0 <= index < 2^32

Outputs

• lamport_PK, the compressed lamport PK, a 32 octet string

Definitions

• I2OSP is as defined in RFC3447 (Big endian decoding)
• flip_bits is a function that returns the bitwise negation of its input
• "" is the empty string
• a | b is the concatenation of a with b

Procedure

Note: The indexing, i, in the above procedure iterates from 1 to 255 (inclusive). This is due to the limit to which HKDF can stretch the input bytes (255 times the length of the input bytes). The result of this is that the security of the lamport-backup signature is *only* 127.5 bit.

HKDF_mod_r

hkdf_mod_r() is used to hash 32 random bytes into the subgroup of the BLS12-381 private keys.

Inputs

• IKM, a secret octet string >= 256 bits in length
• key_info, an optional octet string (default="", the empty string)

Outputs

• SK, the corresponding secret key, an integer 0 <= SK < r.

Definitions

• HKDF-Extract is as defined in RFC5869, instantiated with hash H.
• HKDF-Expand is as defined in RFC5869, instantiated with hash H.
• L is the integer given by ceil((3 * ceil(log2(r))) / 16).(L=48)
• "BLS-SIG-KEYGEN-SALT-" is an ASCII string comprising 20 octets.
• OS2IP is as defined in RFC3447 (Big endian encoding)
• I2OSP is as defined in RFC3447 (Big endian decoding)
• r is the order of the BLS 12-381 curve defined in the v4 draft IETF BLS signature scheme standard r=52435875175126190479447740508185965837690552500527637822603658699938581184513

Procedure

derive_child_SK

The child key derivation function takes in the parent's private key and the index of the child and returns the child private key.

Inputs

• parent_SK, the secret key of the parent node, a big endian encoded integer
• index, the index of the desired child node, an integer 0 <= index < 2^32

Outputs

• child_SK, the secret key of the child node, a big endian encoded integer

Procedure

derive_master_SK

The child key derivation function takes in the parent's private key and the index of the child and returns the child private key. The seed should ideally be derived from a mnemonic, with the intention being that BIP39 mnemonics, with the associated mnemonic_to_seed method be used.

Inputs

• seed, the source entropy for the entire tree, a octet string >= 256 bits in length

Outputs

• SK, the secret key of master node within the tree, a big endian encoded integer

Procedure

Rationale

---

Lamport signatures

Lamport signatures are used as the backup mechanism because of their relative simplicity for a post-quantum signature scheme. Lamport signatures are very easy both to explain and implement as the sole cryptographic dependency is a secure hash function. This is important as it minimises the complexity of implementing this standard as well as the compute time for deriving a key. Lamport signatures have very large key sizes which make them impractical for many use cases, but this is not deemed to be an issue in this case as this scheme is only meant to be a once-off event to migrate to a new scheme.

Revealing the associated Lamport public key for a corresponding BLS key is done by verifying that the Lamport public key is the pre-image of the corresponding BLS private key (which in turn is verified against the BLS public key). This means that using a key's Lamport signature reveals the BLS private key rendering the BLS key pair unsafe. This has the upside of not requiring additional storage space for backup keys alongside BLS keys but does require that the Lamport signatures be used once and that the BLS key is no longer trusted after that point.

The Lamport signatures used within this scheme have 255 bits worth of security, not 256. This is done because HKDF-SHA256, the mechanism used to stretch a key's entropy, has a length-limit of 255 * hash_function_digest_size. The 1-bit reduction in security is deemed preferable over increasing the complexity of the entropy stretching mechanism.

SHA256

SHA256 is used as the hash function throughout this standard as it is the hash function chosen by the IETF BLS signature proposed standard. Using a single hash function for everything decreases the number of cryptographic primitives required to implement the entire BLS standardised key-stack while reducing the surface for flaws in the overall system.

hkdf_mod_r()

The function hkdf_mod_r() in this standard is the same as the KeyGen function described in the proposed standard and therefore the private key obtained from KeyGen is equal to that obtained from hkdf_mod_r for the same seed bytes. This means that common engineering can be done when implementing this function. Additionally because of its inclusion in an IETF standard, it has had much scrutiny by many cryptographers and cryptanalysts, thereby lending credence to its safety as a key derivation mechanism.

While hkdf_mod_r() has modulo bias, the magnitude of this bias is minuscule (the output size of HKDF is set to 48 bytes which is greater 2¹²⁸ time larger than the curve order). This bias is deemed acceptable in light of the simplicity of the constant time scheme.

Only using hardened keys

Widely accepted standards that existed before this one (BIP32 and BIP44) utilise the notion of hardened and non-hardened keys whereas this specification only offers the former. Non-hardened keys are primarily useful in a UTXO system in which having one's balance spilt amongst many accounts does not present much additionally complexity, but such keys are much less useful outside of this context. Further complicating matters is the problem of deriving non-hardened keys using a post-quantum signature scheme as non-hardened keys are made possible by the very group arithmetic quantum computers gain an advantage over.

Backwards Compatibility

---

There are no major backwards compatibility issues brought upon by this EIP as it is not designed for use within Ethereum 1.0 as it currently stands. That said, this standard is not compatible with BIP32/ BIP44 style paths as paths specified by these systems make use of non-hardened keys, something that does not exist within this standard.

Test Cases

---

Test Case 0

This test case can be extended to test the entire mnemonic-to-child_SK stack, assuming BIP39 is used as the mnemonic generation mechanism. Using the following parameters, the above seed can be calculated:

This test case can be extended to test the entire mnemonic-to -child_SK stack, assuming BIP39 is used as the mnemonic generation mechanism. Using the following parameters, the above seed can be calculated:

Test Case 1

Test Case 2

Test Case 3

Test Vector with Intermediate values

Implementation

---

• Python

Copyright

---

Copyright and related rights waived via CC0.