ERC-2333 BLS12-381 key generation standard (BLS12-381 Key Generation)
Review · Accounts & wallets · created 2019-09-30
Defines a method for deriving, from a single secret seed, effectively unlimited BLS12-381 keys in a tree structure. The derivation process also produces a quantum-safe emergency backup signing method as a byproduct.
Why it is needed
Ethereum's beacon chain signs using the elliptic curve BLS12-381, but BIP32, the previously widely used key derivation standard, does not fit this curve. BIP32 discards values larger than the curve's order as invalid keys, and given BLS12-381's private key subgroup order and the entropy size used, more than 54% of keys generated via BIP32 end up invalid. Furthermore, if a standard is introduced after users have already begun generating keys, tools diverge in their approaches, making it hard to move between key management systems. Finally, to prepare for a scenario where a sudden advance in quantum computing renders BLS12-381 insecure, a mechanism is needed to switch to a new signature scheme using pre-shared public keys. This standard solves all three problems at once.
In depth
Tree structure and path notation
A key is determined by the tree's seed and a path. The root master key is written as m, and depth is separated by /. The master key's first child is m / 0, and its siblings are m / i for 0 <= i < 2**32. Deriving a child key requires only the parent's private key and the child's index, so knowing a single ancestor key allows deriving the entire branch beneath it. Which path is used for which purpose is left open for separate standards to define.
derive_master_SK: generating the master key
The input is seed, the source of entropy for the entire tree, which must be an octet string of 256 bits or more. The procedure is a single line: SK = HKDF_mod_r(seed). The seed is ideally derived from a mnemonic, and is intended to use BIP-39's mnemonic_to_seed method. Test case 0 builds the seed from the mnemonic "abandon ... about" and the passphrase "TREZOR", allowing the entire stack from mnemonic to child key to be verified.
derive_child_SK: deriving a child key
Takes the parent private key parent_SK and an index index (0 <= index < 2^32), and returns the child private key. The procedure has two steps. First, parent_SK_to_lamport_PK(parent_SK, index) obtains the compressed Lamport public key, which is then fed into HKDF_mod_r to produce the child key. In other words, every child key is produced via a Lamport intermediate key, and this design is the key to building in quantum-resistant backup at no extra cost.
The process of generating the Lamport intermediate key
IKM_to_lamport_SK takes the secret string IKM and a salt, stretches them with RFC5869 HKDF-Extract and HKDF-Expand (SHA256), then slices the output into 32-octet chunks to build a 255-element Lamport private key array. parent_SK_to_lamport_PK sets salt = I2OSP(index, 4) and IKM = I2OSP(parent_SK, 32), builds Lamport keys lamport_0 and lamport_1 from IKM and its bit-flipped counterpart not_IKM, hashes all 510 pieces with SHA256, concatenates them, and compresses the result with SHA256 again to get a 32-octet compressed public key. Because HKDF can only stretch up to 255 times the input length, there are 255 chunks, which gives the Lamport backup signature a security strength of 127.5 bits.
HKDF_mod_r: hashing into the BLS private key subgroup
HKDF_mod_r converts a secret input of at least 256 bits into an element of the BLS12-381 private key subgroup (0 <= SK < r). The salt starts from the 20-octet ASCII string "BLS-SIG-KEYGEN-SALT-"; if the result is 0 the salt is rehashed and the process repeats, and the output length is L = ceil((3 * ceil(log2(r))) / 16) = 48. This function matches KeyGen in the IETF BLS signature standard draft, so the same seed produces the same key, and it has been reviewed by many cryptographers. There is modulo bias, but it is considered negligible since the 48-byte output is more than 2^128 times larger than the curve order. Because the standard draft has changed, this function was updated on September 17, 2020, so implementations should confirm they are using the latest version.
How the quantum-resistant backup works, and its cost
Lamport signatures were adopted as the backup mechanism because they are a simple quantum-resistant signature scheme that only needs a secure hash function. Publishing the Lamport public key for a given BLS key involves proving that the public key is a pre-image of the BLS private key, and this process reveals the BLS private key, so the Lamport signature can only be used once, after which that BLS key can no longer be trusted. In exchange, there is no need to store a separate backup key. Since it is designed only for a one-time migration to a new signature scheme, the large size of Lamport keys is not considered a problem.
Only hardened keys are supported, incompatible with BIP32/44 paths
BIP32 and BIP44 provide both hardened and non-hardened keys, but this standard provides only hardened keys. Non-hardened keys are mainly useful in UTXO systems where it is not a burden for balances to be spread across multiple accounts, are of little use elsewhere, and the group operation that enables non-hardened derivation is itself vulnerable to quantum computers. It is therefore incompatible with BIP32/BIP44-style paths that use non-hardened keys. Since this is not for secp256k1 keys, there are no other backward compatibility concerns.
Proposal status: Review
The status of this document is Review, meaning it is a proposal that has not yet been finalized and whose content may change. In fact, the key derivation method was updated once in September 2020 to track a change in the BLS signature standard draft.