Proposal: Base58 encoded HD Wallet root key with optional encryption

[riplin]

Recent changes:

24-04-2014 - Changed the preH and PostH calculation. Again.
21-04-2014 - Changed the preH and postH calculation.
15-02-2014 - Updated wording of various parts.
06-02-2014 - Added Will Yager's implementation as reference.
05-02-2014 - Changed prefix to 2 bytes, 'RK' and 'rk' for clear version and encrypted version respectively.
05-02-2014 - Added entropy field to encrypted version, moved KDF field from prefix into entropy field.
05-02-2014 - Changed computation of H to use PBKDF2-HMAC-SHA512 instead of Scrypt.
05-02-2014 - Changed checksum field to bloom field in encrypted version. Now supports 2 passwords.
27-12-2013 - Added some clarifications such as password character set (UTF-8) and endianness of fields.
26-12-2013 - Changed checksum to double SHA256 of private key, added 3^rd party KDF support.
01-10-2013 - Expanded the salt to be prefix + date + checksum and renamed 'master seed' to 'root key'.
24-07-2013 - Added user selectable KDF + parameters, encoded in the prefix.
22-07-2013 - Added 2 byte creation date field, as a result, the prefix is expanded to 3 bytes.


BIP:
Title: Base58 encoded HD Wallet root key with optional encryption
Authors: Jean-Paul Kogelman, William Yager
Status: Draft
Type: Informational
Created: 18-07-2013

Abstract

This proposal describes a method for encoding and optionally encrypting a Bitcoin Hierarchical Deterministic (HD) Wallet root key. Encoded root keys are intended for use on paper wallets. Each string contains all the information needed to verify and reconstitute an HD wallet except for the optional passphrases. The encrypted version uses salting and a user selectable key derivation function (KDF) + parameters to resist brute-force attacks at varying degrees and optionally a second password for plausible deniability.

The method provides two encoding methodologies in 3 lengths each (16, 32 and 64 byte root keys). One is a clear version of the root key with verification information for integrity checking and the other is an encrypted representation.

Additionally a 2 byte compressed date field is present to limit the block chain rescan on wallet import.


Motivation

The extended private keys proposed in BIP 0032 are long, fixed length records and don't offer any form of security. The root key used to generate the HD wallet is typically shorter than the extended master private key that results from it.

A compact representation of the root key is easier to handle and a 2-factor version of the root key record allows for safe storage and the creation of paper wallets by 3^rd parties. The KDF and its parameters are user selectable, allowing for a varying level of resistance against brute force attacks. This proposal currently defines 5 sets of parameters with room for 27 more that can be defined at a later date. Implementors are advised to contact the author with new KDF proposals.

Copyright

This proposal is hereby placed in the public domain.

Rationale

User story: As a Bitcoin user who uses HD wallets, I would like the ability to store my wallet root key in a compact form as a paper wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to have a 3rd party create a paper wallet with my root key in it, without having access to the funds stored in the wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to choose the strength of the root key depending on my security requirements and how I wish to store it.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to import a root key into a simplified payment verification (SPV) client without having to redownload the entire block chain, but rater a limited range, to find associated transactions.

User story: As a Bitcoin user who uses HD wallets, I would like to choose the KDF and its parameters that is used to hash the passphrase that protects my root key to fit my security needs and available processing power.

User story: As a Bitcoin user who uses HD wallets, I would like to outsource the KDF computation to a 3^rd party with more processing power.

User story: As a Bitcoin user who uses HD wallets, I would like to have a second password that can decrypt a second root key.

Specification

This proposal makes use of the following functions and definitions:

All input/output text is to be UTF-8 encoded

AES256Encrypt, AES256Decrypt: The AES block cipher, applied in ECB mode.

SHA256, SHA512: The hash algorithms of the same name.

HMAC-SHA512: The HMAC message authentication code algorithm, using SHA512 as the hash function

PBKDF2-HMAC-SHA512: The PBKDF2 key derivation algorithm, described in PKCS #5 v2.0 and RFC 2898, using HMAC-SHA512 as the pseudorandom function

Scrypt: The key stretching algorithm of the same name

Base58Check: The textual data encoding frequently used by various Bitcoin-related systems

"Root Key": The 16/32/64 byte value encoded in the wallet. This value is used to derive the private keys for addresses in the Bitcoin Wallet

"Master Key": The primary Bitcoin private key, which is derived from the Root Key

"||" refers to concatenation, not the logical OR operation

"G", "N": Constants defined as part of the secp256k1 elliptic curve. G is an elliptic curve point, and N is a large positive integer.

Prefix

The Base58Check representation of the wallet will start with "RK" (Root Key) if the wallet is unencrypted, and will start with "rk" if the wallet is encrypted.

Proposed specification

Unencrypted wallet:

Prefixes:
0x28C1: 16 byte root key, no encryption. 24 byte total length
0x4AC5: 32 byte root key, no encryption. 40 byte total length
0xFBB3: 64 byte root key, no encryption. 72 byte total length

These are constant bytes that appear at the beginning of the Base58Check-encoded record, and their presence causes the resulting string to have a predictable prefix.

"date" is a 2-byte, little endian field containing the number of weeks since jan 1st 2013. It is used to optimize blockchain scan upon wallet import.

"checksum" is the first 4 bytes of SHA256(SHA256(master_secret)), where master_secret is the "Master Secret Key (I_L)" from the BIP32 specification. In other words, "checksum"=SHA256(SHA256(HMAC-SHA512("Bitcoin seed", root_key)[0:32]))[0:4].

"root_key" is the 16/32/64 byte root key used for the HD wallet

In summary, the clear wallet looks like this:
[prefix, 2 bytes][date, 2 bytes][checksum, 4 bytes][root_key, 16/32/64 bytes]

Range in Base58Check encoding for clear 16 byte root key (prefix RK):
Minimum value: RK52zvuD3xRhwto8JDTonxhru6awsFfNqKCTmT (based on 0x28 0xC1 plus twenty-two 0x00's)
Maximum value: RKCsfF9RpLnrxo1kp2o7mfWYeAV1NNYxWSMRym (based on 0x28 0xC1 plus twenty-two 0xFF's)

Range in Base58Check encoding for clear 32 byte root key (prefix RK):
Minimum value: RK15fXAj9BEMooghtx2gY5YrSh23LYKS8mZnaz8oYf1EDnqAwtAADGMVUDHG (based on 0x4A 0xC5 plus thirty-eight 0x00's)
Maximum value: RK5MUEoFU24QARcsX5HR2ieCjem468hDeQm4J2aH5zsCVJXUCGn6nsVQEFhN (based on 0x4A 0xC5 plus thirty-eight 0xFF's)

Range in Base58Check encoding for clear 64 byte root key (prefix RK):
Minimum value: RK1uXsCQAKqaa2s7YBDeaLS2KTqZcNjjQSgdSfDv4fqGkTw8KBfZ2ND4Cp7vHdzhjJ2C2Jtf4CwgScR nXvpzuQT2W4Vj2SgCyfBgpTzF (based on 0xFB 0xB3 plus seventy 0x00's)
Maximum value: RK3B9TMn55dey3an1oHpwB81FPZboakivYtqFvCaeknPzPK4iTvoFKzxVWKcD9YfJwjkyS36bqnSqji bUurcQ7J2EsQww5zPpJNzqjkw (based on 0xFB 0xB3 plus seventy 0xFF's)


Encrypted wallet:

Prefixes:

0xF83F: 16 byte root key, encrypted. 26 byte total length
0x6731: 32 byte root key, encrypted. 43 byte total length
0x4EB4: 64 byte root key, encrypted. 76 byte total length

These are constant bytes that appear at the beginning of the Base58Check-encoded record, and their presence causes the resulting string to have a predictable prefix.

"date" is a 2-byte, little endian field containing the number of weeks since jan 1st 2013. It is used to optimize blockchain scan upon wallet import. The maximum value of 0xFFFF results in: jan 1st 3269

"entropy" is a 2/3/4 byte (corresponding to whether the key is 16/32/64 bytes) field. The first five bits contain the KDF type, and all other bits contain random data. This is used as a salt to make cracking the wallet password harder.

"bloom_filter" is a 4 byte little-endian field containing a bloom filter to check that the user entered their password correctly.

"encrypted_root_key" is the 16/32/64 byte encrypted root key used for the HD wallet

In summary, the encrypted wallet looks like this:
[prefix, 2 bytes][date, 2 bytes][entropy, 2/3/4 bytes][bloom_filter, 4 bytes][encrypted_root_key, 16/32/64 bytes]


Range in Base58Check encoding for encrypted 16 byte root key (prefix rk):
Minimum value: rk2V4R2ys91WigNPL5nots6a97rfMnwTkPAb2XgNo (based on 0xF8 0x3F plus twenty-four 0x00's)
Maximum value: rk57mv9oertBLsHfncAvqnbetCBdNS1gFHQaFsD3p (based on 0xF8 0x3F plus twenty-four 0xFF's)

Range in Base58Check encoding for encrypted 32 byte root key (prefix rk):
Minimum value: rk1CYsqKjsbXa7uvncEaW4XSeVzcpq1U9yDMxd2cWwfkGf1FMjENaVThYpLRNwqo (based on 0x67 0x31 plus fourty-one 0x00's)
Maximum value: rk7Xw5b6fidaCk489LhaiMqHkZo7RYGTmzvJY9A5joxe8KXAn8BC66cmQPYYYvy8 (based on 0x67 0x31 plus fourty-one 0xFF's)

Range in Base58Check encoding for encrypted 64 byte root key (prefix rk):
Minimum value: rk48BmQWeQbATSXbP5U6XVsXRJTs4Ea1TVZBbHLPPsboCFyxDj2Jaz2JAJno97hq6dq2bANLuWydY8Q SZgKVGhPRZazXt1swPXwzVLw1QnVAz (based on 0x4E 0xB4 plus seventy-four 0x00's)
Maximum value: rkCRtT9R9kuAapCaLQFif5uo8gUrjgKsvYmGGTpX2ZTjTfwe9M7A6KezTh7f4FDxfZFVbHypodMNnNd mWYb8mzTokHXVR1u7KicrLLFFu7GJW (based on 0x4E 0xB4 plus seventy-four 0xFF's)


Encoding of KDF + parameters:

A number of KDF functions are available, to accommodate a wide range of possible use cases. The KDFs are defined as follows:

ID	KDF	Parameters
0x00	scrypt	n = 214, r = 8, p = 8
0x01	scrypt	n = 216, r = 16, p = 16
0x02	scrypt	n = 218, r = 16, p = 16
0x08	PBKDF2-HMAC-SHA512	iterations = 216
0x09	PBKDF2-HMAC-SHA512	iterations = 221

All other possible values (3-7 and 10-31) are reserved.

Please note that KDFs 1 and 2 will probably not run on mobile devices. KDFs 8 and 9 are very memory efficient.

Generation of date:

The purpose of the date field is to make scanning the blockchain for transactions to/from this wallet faster. The date *must* be on or before the date of the first transaction to/from the wallet. If the date is unknown (e.g. on an embedded device) or the user does not wish to reveal the wallet creation date, this field can be set to zero (which may incur a performance penalty for the wallet software). When importing, it is advised to start scanning from a few days before the encoded date. The date field is a little-endian integer containing the number of weeks, rounded down, since Jan 1st 2013.

Examples:

sep 18th 2013 - jan 1st 2013 =  260 days =  37 weeks 1 day = rounded down becomes 0x0025
mar  3rd 2027 - jan 1st 2013 = 5174 days = 739 weeks 1 day = rounded down becomes 0x02E3

Derivation of Master Key from Root Key (please see BIP 0032 for a full description of HD wallets):

1. Take 16/32/64 byte Root Key. Call it S
2. Calculate I = HMAC-SHA512(key = "Bitcoin seed", msg = S)
3. Let I_L = I[0:32]. I_L is the Master Key
4. If I_L is 0 or I_L >= N, where N is the curve order of Secp256k1 (the elliptic curve used by Bitcoin), the Root Key is invalid and a new one should be chosen.

Encryption:

Let "passphrase" be the user's chosen passphrase
Let "fake_passphrase" be the user's chosen second passphrase, or a randomly generated string if the user chose not to use a second passphrase
Let "KDF" be the chosen key derivation function
Let "root_key" be the 16/32/64 byte Root Key

1. Create the correct "Prefix" and "Date" field
2. Create the random "Entropy" field and encode the KDF number in the top 5 bits
3. Let "salt" = Prefix || Date || Entropy
4. Calculate "preH" = PBKDF2-HMAC-SHA512(key = salt, msg = passphrase, iterations = 10000, output_len = 64)
5. Calculate "strongH" = KDF(msg = preH[0:32], salt = preH[0:32], output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "H" = PBKDF2-HMAC-SHA512(msg = preH, salt = strongH, iterations = 1, output_len = len(root_key) + 32)
7. Calculate "whitened_key" = root_key XOR H[0:len(root_key)]
8. Calculate "encrypted_key" = AES256Encrypt(message = whitened_key, key = HR), where HR is the last 32 bytes of H
9. Calculate "fake_key" by decrypting encrypted_key with fake_passphrase
10. Calculate "bloom_filter", containing root_key and fake_key. See the "Bloom Filter" section for more info.

encrypted_wallet = Prefix || Date || Entropy || bloom_filter || encrypted_key

Decryption of Root Key:

Let "passphrase" be the passphrase provided by the user

1. Extract "Prefix", "Date", "Entropy", "bloom_filter", and "encrypted_key" from the encrypted wallet
2. Determine the correct KDF from the top 5 bits of Entropy.
3. Let "salt" = Prefix || Date || Entropy
4. Perform steps 4 through 6 of Encryption to derive "H"
5. Calculate "whitened_key" = AES256Decrypt(message = encrypted_key, key = HR), where HR is the last 32 bytes of H
6. Calculate "root_key" = whitened_key XOR H[0:len(whitened_key)]
7. Verify that root_key is a member of bloom_filter

Bloom Filter:

The Bloom Filter is a data structure that allows us to check, within a range of probability, whether or not some piece of data has been added to it. In this case, we want to make sure that the user entered their password correctly, so we're checking that the decrypted root_key corresponds to the one that was added to the bloom filter when the wallet was created.

Bloom Filter Creation:

1. Let "bloom_filter" be an empty (set to all zeros) 32-bit, little-endian integer
2. To add an element "X" to bloom_filter,
3. Calculate "E" = SHA256(SHA256(HMAC-SHA512("Bitcoin seed", X)[0:32]))[0:11]. Note, this corresponds to the same algorithm used as a checksum for un-encrypted wallets. It also corresponds to the double-SHA of the Master Key.
4. For each of the 11 bytes in E (call each byte "B"):
4a.   calculate "N" = B & 0x1F. N will range from 0 to 31. Set the Nth bit in bloom_filter to 1

You can add more items to the bloom filter, if desired. However, the filter parameters are optimized for 2 items (one "real" password/wallet, and one "fake" password/wallet). Please note that adding more items will drastically increase the chance of a false positive when entering a password. The chance of a password similar to a correct password passing the filter becomes more likely. This will generate a different Root Key and not the original one the user intended to decrypt.

Bloom Filter Verification:

Let "X" be some item
Let "bloom_filter" be the Bloom Filter you want to check if X belongs to

1. Calculate "x_only_filter", which is a Bloom Filter with X added to it
2. Ensure that any bit that is set in x_only_filter is also set in bloom_filter (i.e. x_only_filter & bloom_filter == x_only_filter)
3. If all bits set in x_only_filter are also set in bloom_filter, you know X is probably a member of bloom_filter. If not, X is definitely *not* a member of bloom_filter.

Suggestions for implementers of proposal with alt-chains

This proposal is network and coin agnostic (so long as the coin in question uses SECP256K1 ECC).

Reference implementation

Python reference implementation: https://github.com/wyager/Encrypted-HD-wallet

Acknowledgements

Mike Caldwell for BIP 0038, which this proposal borrows heavily from.

See Also

BIP 0032 Hierarchical Deterministic Wallets: https://en.bitcoin.it/wiki/BIP_0032
BIP 0038 Passphrase-protected private key: https://en.bitcoin.it/wiki/BIP_0038

Test vectors

The primary password will always decrypt the same root key, regardless of KDF selection, however, the secondary password will generate a different root key for every KDF.

Clarification:
Root Key: The BIP32 root key.
Private Key: IL in BIP32 parlance.
Salt Entropy: The random data used to generate the salt. With this, wallet generation can be tested deterministically. If you use this salt data, your encrypted wallets should *exactly* match the encrypted wallets listed here.

Test 1:

Root Key	000102030405060708090a0b0c0d0e0f
Private Key	e8f32e723decf4051aefac8e2c93c9c5b214313817cdb01a1494b917c8436b35
Creation Date	04-02-2014
Cleartext Wallet	RK6nEaou4eFQC4SfrHtdh9jpnEme4K9dt2jBmG
Password	Satoshi
Second Password	Alpaca
Salt Entropy	abcd
Encrypted with KDF 0	rk354bQrbuzi9tVCt48rv9CCrc1Mi7sk9m3Yykpt3
Second Private Key 0	cf345038e7b0068d50e796756a3df60314f6edb7bc47c9ee7b4d73678668cdcb
Encrypted with KDF 1	rk354bf4mvtwNXcLdcfppZECW4AoUBvTB8S23agNs
Second Private Key 1	632c122124ba9905be5e02078d36ba63b7588edd2c68f1b385b9d6c2ca3e0817
Encrypted with KDF 8	rk354dNXRL2jSEL5Neh6ndDsxNgvRoP3Tt4oMqLTV
Second Private Key 8	a44ca5f6b4f38385e4a5cc751ace5d2117e3305aee52827286cbc981f00e80da
Encrypted with KDF 9	rk354dcjNKEyDFwVgYrdCQnkZYpUWzhyjMY16enLT
Second Private Key 9	29e35fd44226c74117022b7e3079687bc2fa6391998753bc978509a8d9c5c323

Test 2:

Root Key	7f0ad7d595be13e6fe4cf1fa0fbb6ae9c26c5d9b09920709414982b6363d5844
Private Key	08965cb883e1c8783d72b65a0b7104d64baa9412eb655a6f05c5aaa6103781be
Creation Date	04-02-2014
Cleartext Wallet	RK22qqMb3CozsQfTTbSVsLEgXcjekut99SuSHn6urU4vWxjiQneHWVYabWgv
Password	Nakamoto
Second Password	hunter2
Salt Entropy	defg
Encrypted with KDF 0	rk2cMHcqyHdHNudopX8ZXwbrXgXK182FXpQJgiNdJbDGZXUpdWjfayTqi9tryTbS
Second Private Key 0	7645740391ba1c5ef56286a1f43e8f95ac0b66de3bffb5ad3922ec140b7ad28f
Encrypted with KDF 1	rk2cMJD2R82kefxdoLEmXM3B8ox336pr2mbUNasLvEGKpZHzUMToWQyWmn6Y7szk
Second Private Key 1	ffd47e0d8fa64a9a696b4c3b7128fe416f1363aee1ddf6acfd2dd433c2e6bee6
Encrypted with KDF 8	rk2cMNLHXGrjxDyBtQvM1Ef5AxiGgtHympDceeMoCqj9mhqteoeFtPRpc1PXXMfd
Second Private Key 8	96b831152e40d5461470729b88429c340de9c117c0d2af7564f91eb7e5f18443
Encrypted with KDF 9	rk2cMNvTy3VED3dCysRmZ6JswXAN2eYtA5oWegufDYNr7YQx2QHLbp3iie49u9Wf
Second Private Key 9	391edef21757317e5bf1df133c0000ae86f982ad3b340ab5876a33fb057930a8

Test 3:

Root Key	fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8 a8784817e7b7875726f6c696663605d5a5754514e4b484542
Private Key	4b03d6fc340455b363f51020ad3ecca4f0850280cf436c70c727923f6db46c3e
Creation Date	04-02-2014
Cleartext Wallet	RK2BvY13FUD6bX25tA7XDyfAn7zbXSL8pR6TRE3EHZZ8qBm9qEyZRih8x1XhhcZwjcTfpe1Qjydn4KU dia8Wf1NshUusP1D38i88MLU9
Password	Vires In Numeris
Second Password	Quis Custodiet Ipsos Custodes?
Salt Entropy	hijk
Encrypted with KDF 0	rk5ySVNYwdRMDLnyxs1pXCdN3wrcBdPziWUudFidmwSfcJaZKPH8U24WSegPhidQiD7tXejMNQfxrAR h9JG8jLFtMY39fo9unpB4PsPSKymqy
Second Private Key 0	0625f1c1e50cb7c3f302ff37d5eaa0fe20f45b10eb13634f4403b71dd3e49526
Encrypted with KDF 1	rk5ySW9NGHgAxs48UvF5oWvb6PHsZte43p1vjKmYuybLyGNrSMVHAkypTfb9qLFNTFixfCrxqnT3a8V c5UoTcBzRxjLQAwYMoB7YcmzCWdVtD
Second Private Key 1	4a525d10640a9ccd26bbcc1af8a4803803e97628b7e7b6f0db5376c94021c83b
Encrypted with KDF 8	rk5ySbZ5WuX3ba2Pudt1HE6iDQf7cSMg4zTsWbMKdFhucAwJEjNwH48oqCC52mbh3jxTQEGXN294Azx YsDbJowkiHSocGqWh7SFy24sE9KHGn
Second Private Key 8	83d025017755701dbfcf5b50d07a95a99d517c15f40f0bec5529ae1cc3e39ba0
Encrypted with KDF 9	rk5yScKtqZmWe5FAB54x7WvvuxDSnNg81J3CADPdh4GJ4t2QaHckv8iuWF2spbC6uDC7DSM3GkYSQvN tz88su2h89vj9yUpmECmeELH2TkzM5
Second Private Key 9	c16e82babbf14512c9acde344a817693d2f401d2c73c7aeacdd21c455a9d5dd8

Test 4:

Root Key	6ca4a27ac660c683340f59353b1375a9
Private Key	f544dd076ffe8fb68aa81ca9a33059946e9a91f8d95258ae1b7a1db6215ce51a
Creation Date	04-02-2014
Cleartext Wallet	RK6nEmXZj2nqgtCVWk3s7Suvz2XtWrdhDPpJqS
Password	聡中本
Second Password	Bitcoin
Salt Entropy	lmno
Encrypted with KDF 0	rk354bWG9c8dupPhhYsKgFEcZ8uqxV7JKbvbsmnzh
Second Private Key 0	b5af32696fe4bd75015d55f52a5bec16af4de74c256458ba8fdba7702509b7ca
Encrypted with KDF 1	rk354bkUKo7gu3vhdadunrCUSSjJuQrQwyRXoydTE
Second Private Key 1	de80aba55dee465b979a71a90d43c9a1f594eaaa30086944b8280603783ff4b8
Encrypted with KDF 8	rk354dTvdLGCSSPHP8tjFeLXMhwybvE47szr2jUPH
Second Private Key 8	54b9fbe968a76327b452d0f7af1c74dfff34cddc4884ec6c65d1d1f66b3df79d
Encrypted with KDF 9	rk354di8idN7qLmnbYSsFgjPbeHQ4b9CxSSviqXiH
Second Private Key 9	247f6877db617c7a28a45c44a97041d055f0c664f109e2b6c1f3d9702dcaaeaa

[riplin]

Reserved.

[grau]

I think this is somewhat missing the needs.

Serialization of BIP32 is given and is sufficient for cold storage, perhaps with the addition of sipa's suggestion in a IRC:
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).

Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.

[apetersson]

i hope there will be a consensus across wallets how to expand the hierachy.

that way you could deduct the hierachy from the blockchain. im some cases additional hierachy metadata is still neccessary. (if you generate millions of nodes without ever using them, for example)

[riplin]

I think this is somewhat missing the needs.

Serialization of BIP32 is given and is sufficient for cold storage

I respectfully disagree.

The current solution of extended public and private keys requires you to store this:

xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi

versus my proposal of storing this:

wsHb15443fYPmneEXskd6wUZeP15fCiA69n

This is for a 128 bit seed. A 256 bit seed (more than sufficient entropy) would only require this:

wsFp1uM2gFhd2PuRzmNFReRud71hgmVwPoc7cGpxuvgETRsv8J1wHNANJ


Please note that these wallet seeds can be (and the ones shown above are) encrypted, whereas private extended keys are always in clear form.

perhaps with the addition of sipa's suggestion in a IRC:
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).

Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.

Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.

I'm not sure if representing a tree of sufficient complexity in human readable form is even desirable, but that's my personal opinion.

I think that the hierarchy is a great place for people to innovate. As you said, sequencing on the unix time is a great place to start, however, you have 256 levels at your disposal so you could simply write out your sub tree in readable form: .../2013/07/20/18/45/16/... would work too.

[grau]

The current solution of extended public and private keys requires you to store this:

xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi

versus my proposal of storing this:

wsHb15443fYPmneEXskd6wUZeP15fCiA69n

Yes, it is shorter but that alone would not justify to define a new standard, since the BIP32 serialization fits into a QR code square that is only 13% taller and wider than your code.

Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.

That is my point. Being able to recreate the wallet master key from encrypted seed is nice, but I think need more to be able to efficiently recreate the wallet.

1. Importing of a private key into the wallet is rather expensive without knowing the key inception time point (that would limit the scan to blocks thereafter), hence the suggestion with key@inception

2. The seed alone is not sufficient to recreate the wallet since scanning for all possible hierarchies is prohibitively expensive.

[riplin]

The current solution of extended public and private keys requires you to store this:

xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi

versus my proposal of storing this:

wsHb15443fYPmneEXskd6wUZeP15fCiA69n

Yes, it is shorter but that alone would not justify to define a new standard,

You are ignoring the optional encryption.

since the BIP32 serialization fits into a QR code square that is only 13% taller and wider than your code.

The QR code of the extended private key is ~50% taller and wider and has ~75% more surface area than the master seed.

Master seed QR code:


Extended private key QR code:

Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.

That is my point. Being able to recreate the wallet master key from encrypted seed is nice,

And that's all this is. A way to efficiently store the master seed with the option to encrypt it. Nothing more.

but I think need more to be able to efficiently recreate the wallet.

1. Importing of a private key into the wallet is rather expensive without knowing the key inception time point (that would limit the scan to blocks thereafter), hence the suggestion with key@inception

I'm sorry, English isn't my first language, so I may have overlooked that you were proposing I add a time field. My bad. That's doable, although 64bit is pretty fine grained, considering that blocks are generated roughly every 10 minutes and transactions don't have timestamps, Something like a 32bit field would do just fine, maybe it's possible to go even smaller.

2. The seed alone is not sufficient to recreate the wallet since scanning for all possible hierarchies is prohibitively expensive.

This is true. However, that's not what this proposal is trying to solve. Also, the extended private key doesn't solve this problem either.


Edit: If we allow overscanning a little bit, say a weeks worth of blocks (shouldn't take too long), then you'd be able to get to the year 3265 if you stored 2 bytes worth of weeks since the genesis block. If you allowed for overscanning by a month, you'd get to the year 7470 with a 2 byte timestamp.

[grau]

You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N

32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.

I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.

[riplin]

You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N

I just grabbed the first online QR encoder that came up in google.

32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.

Have you read my edit? I think it's probably sufficient to store weeks (or months) since genesis, rather than a full timestamp.

I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.

It's just too much data, I think that's a problem best left to specific wallet implementations.

[grau]

You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N

I just grabbed the first online QR encoder that came up in google.

32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.

Have you read my edit? I think it's probably sufficient to store weeks (or months) since genesis, rather than a full timestamp.

I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.

It's just too much data, I think that's a problem best left to specific wallet implementations.

Standards are better built on top of other standards, therefore I would not invent a new time format. The amount of trees you save with those bytes is negligible.

I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.

However, your proposal is an intermediary step between key and wallet serialization and that is my original point. We do not need a new key serialization, but we need a wallet serialization.

[riplin]

We do not need a new key serialization,

We?

I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.

I'm open to suggestions.

[grau]

We do not need a new key serialization,

We?

I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.

I'm open to suggestions.

This is getting dumb.

You asked for comments but can't handle them. I should have said I and you should not have picked on "We" as if this would have been qualifying the content of my comment.

[riplin]

We do not need a new key serialization,

We?

I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.

I'm open to suggestions.

This is getting dumb.

You asked for comments but can't handle them. I should have said I and you should not have picked on "We" as if this would have been qualifying the content of my comment.

I can handle comments just fine. We were having a good discussion about the timestamp for example. I just find it a bit strange that you are so dismissive about this proposal to the point of using 'we' as if you speak for the entire community. But ok, let's ignore that.

It's an informative BIP, so you are free to ignore it.

It's obvious from several of your comments that you are looking for a solution that can serialize an entire hierarchical wallet, yet I've made it clear that this proposal does not cover that.

But as stated earlier, I'm open to suggestions on how one could efficiently serialize a hierarchical wallet structure, even though that's slightly off topic.

[grau]

But as stated earlier, I'm open to suggestions on how one could efficiently serialize a hierarchical wallet structure, even though that's slightly off topic.

Each key is identified by a variable length sequence of integers. Those sequences can be efficiently compressed since they form a tree (repeating prefixes). I am interested in the topic but do not have the time to work on it now.

[riplin]

Added creation date field to proposal.

[jspilman]

I think a standard format for encrypted backup of the key material (not the hierarchy) is useful.

The heart of any password-based encryption is the KDF -- in this case you've chosen scrypt with n=2^14, r = 8, p = 8.  Just a quick benchmark on my desktop shows this runs at about 25 iters / sec, using about 12MB of RAM per thread, which may be "slow enough", but hard to say definitively. By comparison n=16, r = 16, p = 16 which runs at about 2 iter / sec, using 100MB of RAM for per  thread...  or even n = 18, r = 16, p = 16 which runs at 0.5 / sec, using 500MB of RAM per thread.

Since we're talking about backing up 128 bits, I think it's reasonable to assume the end-user could either just memorize a 128-bit mnemonic (e.g. BIP39), and then they don't need a password (or a backup) at all, or alternatively they would use a password with most likely, significantly less than 128-bits of entropy.

The trade-off of using stricter 'scrypt' parameters is some devices may not be suitable for running even a single iteration. The problem is, if you target your settings to make these devices usable, you're throwing away a lot of the benefit of 'scrypt' -- to make brute-force attacks expensive across a wide range of devices, including GPU and ASIC.

A couple possible options:

  1) Do nothing -- Keep 14/8/8 as the standard hard-coded settings for the KDF as it's "slow enough"
  2) Increase difficulty -- Then we need to decide what the "right" settings are, including what the maximum RAM requirement should be
  3) Provide some means of using different difficulties since there's no one-size-fits-all

Ultimately #3 would come down to somehow encoding the KDF/difficulty -- there are a few ways to do it...

  3a) Add a one or two byte KDF enum -- 00 could mean "scrypt/14-8-8".  01 = "scrypt/16-16-16", 02 = "scrypt/18-16-16", etc.  This has the advantage of allowing us to keep the format and use KDFs other than scrypt if desired. Possibly include a default of "scrypt/14-8-8" if these bytes were not present.

  3b) Hard code assumption that the KDF is scrypt, and give a 2 or 3 byte encoding of the scrypt parameters that were used.  Possibly include a default of 14-8-8 if these bytes were not present.

[riplin]

How about:

3c) Base the settings on seed length? There are currently 3 seed lengths: 128bit, 256bit and 512bit.

128bit seed: 14,8,8
256bit seed: 16,16,16
512bit seed: 18,16,16

Additionally, I could add more seed lengths to the proposal, like 192bit and 384bit.

[jspilman]

Interesting idea, but I'm not sure why KDF strength should be linked to seed length?

A 128-bit seed is suitable given the overall BIP32 design; you can make it bigger but it doesn't really buy you anything. If 128-bits isn't enough, much bigger things are probably broken.

A stronger KDF, on the other hand, is all about deterring brute-force attacks.  It might be perfectly reasonable for it to take 60 seconds or longer to run the KDF when I'm restoring my HD wallet from cold storage.

Ultimately the difficulty factor for the KDF will have to change over time to respond to advances in hardware and software, so it's definitely "planned obsolescence" to pick a fixed difficulty. In other words, the entire proposal becomes less and less secure over time (easier to brute-force) if users or implementers can't scale up the difficulty.

It's less clear how well 'scrypt' itself will scale over time, but at least it "should" be able to scale up, barring any fundamental weakness being discovered in its design. So exposing some degree of control of the scrypt parameters should mean the proposal can still protect against brute-force attacks as well 5 years from now as it does today.

For what it's worth, I read that LTC uses scrypt with 10-1-1 and right now the network is doing 24GH/s.

My last thought is KDF speed also varies with the use case. If I'm encrypting/decrypting the seed every time I unlock my smartphone and open up my wallet app, obviously that's going to need to run a lot faster than if I'm backing up my "life savings cold wallet" from a desktop app which I only plan to make deposits to over the next 10 years. So different apps could expose radically different timings to the end user (I'm not saying the end-user would/should know enough to pick the timings themselves).

Does anyone know how fast 14-8-8 even runs on an older Android or a Raspberry Pi? For all I know, even though I'd like something slower than 14-8-8 on my desktop, the same could be totally unusable for mobile.

[justusranvier]

I'm having trouble seeing any value whatsoever in wallet encryption.

Given the amount of computing power available to attackers (botnets, GPU mining farms, etc), you'd need to use scrypt parameters so onerous (multiple days on a regular PC) that there would be a significant chance of a single-bit error occurring during the calculations.

[riplin]

Interesting idea, but I'm not sure why KDF strength should be linked to seed length?

The idea was, if you choose a low entropy seed, then you're not too worried about security. Sure, you don't want your wallet hacked, but there's value in a small seed and lighter scrypt parameters. If you're going for a 512 bit seed, then you're probably not too concerned about it taking a bit when you're importing the seed. So basically a 1:1 relationship between seed length and scrypt difficulty. It also saves me from having to add another field to store encryption settings. Just to be clear, I'm not ruling out adding an extra byte, it's just that I need a little bit more convincing.

A 128-bit seed is suitable given the overall BIP32 design; you can make it bigger but it doesn't really buy you anything. If 128-bits isn't enough, much bigger things are probably broken.

As mentioned in BIP32, increasing entropy does have an effect on it:

Generate a seed S of a chosen length (at least 128 bits, but 256 is advised) from a (P)RNG.

A stronger KDF, on the other hand, is all about deterring brute-force attacks.  It might be perfectly reasonable for it to take 60 seconds or longer to run the KDF when I'm restoring my HD wallet from cold storage.

The settings currently in the proposal come from BIP38. Here's the discussion thread. I recommend reading it since the same questions came up there: https://bitcointalk.org/index.php?topic=129317.0

The thing to take away from it is:

As he has it right now, it takes about a second to decode on my machine if you know the password. This would make it so that this could run on a phone in javascript at this difficulty when the password is known. Same machine would take half a year to crack 5 character single case. Make that upper lower and you're 12 years. Obviously, he had twenty machines and was not using the un-compiled code. For waht he is proposing the current hashing length is sufficient. If I'm calculating all of this right make it alpha numeric upper lower and that same thing takes 29 years on my single computer.

So that's assuming upper, lower, alpha numeric, 5 characters. Remember, you don't necessarily have to increase the scrypt parameters to get better security. The length of your passphrase has the same effect.

Ultimately the difficulty factor for the KDF will have to change over time to respond to advances in hardware and software, so it's definitely "planned obsolescence" to pick a fixed difficulty. In other words, the entire proposal becomes less and less secure over time (easier to brute-force) if users or implementers can't scale up the difficulty.

It's less clear how well 'scrypt' itself will scale over time, but at least it "should" be able to scale up, barring any fundamental weakness being discovered in its design. So exposing some degree of control of the scrypt parameters should mean the proposal can still protect against brute-force attacks as well 5 years from now as it does today.

Sure, it becomes easier to brute force, but from the numbers given above, you still need a significant amount of time to brute force a 5 character passphrase. Eventually, it all comes down to two things. 1: When is it secure enough for you? 2: How does it affect the default use case (user imports key, enters password, has to wait). Right now that's about 1 second, maybe less on your machine, but for me it's 1 sec.

My last thought is KDF speed also varies with the use case. If I'm encrypting/decrypting the seed every time I unlock my smartphone and open up my wallet app, obviously that's going to need to run a lot faster than if I'm backing up my "life savings cold wallet" from a desktop app which I only plan to make deposits to over the next 10 years. So different apps could expose radically different timings to the end user (I'm not saying the end-user would/should know enough to pick the timings themselves).

The wallet on your phone doesn't have to store the seed in the same format as proposed here. It could use a completely different encryption scheme for internal storage.

Anyway, it's an interesting argument and I'll have a look at it tomorrow to see what adding an extra settings byte would do, but I'd love to hear some other people weigh in on this matter.