EIPs/EIPS/eip-2645.md

eip	title	author	discussions-to	status	type	category	created
2645	Hierarchical Deterministic Wallet for Layer-2	Tom Brand <tom@starkware.co>, Louis Guthmann <louis@starkware.co>	https://ethereum-magicians.org/t/hierarchical-deterministic-wallet-for-computation-integrity-proof-cip-layer-2/4286	Stagnant	Standards Track	ERC	2020-05-13

Simple Summary

In the context of Computation Integrity Proof (CIP) Layer-2 solutions such as ZK-Rollups, users are required to sign messages on new elliptic curves optimized for those environnements. We leverage existing work on Key Derivation (BIP32, BIP39 and BIP44) to define an efficient way to securely produce CIP L2s private keys, as well as creating domain separation between Layer-2 applications.

Abstract

We provide a Derivation Path allowing a user to derive hierarchical keys for Layer-2 solutions depending on the zk-technology, the application, the user’s Layer-1 address, as well as an efficient grinding method to enforce the private key distribution within the curve domain. The propose Derivation Path is defined as follow

m / purpose' / layer' / application' / eth_address_1' / eth_address_2' / index

Motivation

In the context of Computation Integrity Proof (CIP) Layer-2 solutions such as ZK-Rollups, users are required to sign messages on new elliptic curves optimized for those environnements. Extensive work has been done to make it secure on Bitcoin via BIP32, BIP39 and BIP44. These protocols are the standard for wallets in the entire industry, independent of the underlying blockchain. As Layer-2 solutions are taking off, it is a necessary requirement to maintain the same standard and security in this new space.

Specification

Starkware keys are derived with the following BIP43-compatible derivation path, with direct inspiration from BIP44:

m / purpose' / layer' / application' / eth_address_1' / eth_address_2' / index

where:

• m - the seed.
• purpose - 2645 (the number of this EIP).
• layer - the 31 lowest bits of sha256 on the layer name. Serve as a domain separator between different technologies. In the context of starkex, the value would be 579218131.
• application - the 31 lowest bits of sha256 of the application name. Serve as a domain separator between different applications. In the context of DeversiFi in June 2020, it is the 31 lowest bits of sha256(starkexdvf) and the value would be 1393043894.
• eth_address_1 / eth_address_2 - the first and second 31 lowest bits of the corresponding eth_address.
• index - to allow multiple keys per eth_address.

As example, the expected path for address 0x0000....0000 assuming seed m and index 0 in the context of DeversiFi in June 2020: m/2645'/579218131'/1393043894'/0'/0'/0

The key derivation should follow the following algorithm

N = 2**256
n = Layer2 curve order
path = stark derivation path
BIP32() = Official BIP-0032 derivation function on secp256k1
hash = SHA256
i = 0
root_key = BIP32(path)
while True:
	key = hash(root_key|i)
	if (key < (N - (N % n))):
		return key % n
	i++

This algorithm has been defined to maintain efficiency on existing restricted devices.

Nota Bene: At each round, the probability for a key to be greater than (N - (N % n)) is < 2^(-5).

Rationale

This EIP specifies two aspects of keys derivation in the context of Hierarchical Wallets:

• Derivation Path
• Grinding Algorithm to enforce a uniform distribution over the elliptic curve. The derivation path is defined to allow efficient keys separation based on technology and application while maintaining a 1-1 relation with the Layer-1 wallet. In such a way, losing EIP-2645 wallets falls back to losing the Layer-1 wallet.

Backwards Compatibility

This standard complies with BIP43.

Security Considerations

This EIP has been defined to maintain separation of keys while providing foolproof logic on key derivation.

Copyright

Copyright and related rights waived via CC0.