Bitcoin Forum

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 (https://en.bitcoin.it/wiki/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

Reserved.

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.

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)

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.



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.

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.


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.

You are ignoring the optional encryption.



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:
https://i.imgur.com/UMNM7kL.png

Extended private key QR code:
https://i.imgur.com/QSpfLGi.png



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



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.


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.

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.

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


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


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.

We?


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.

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.

Added creation date field to proposal.

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.

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.

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.

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.

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. :)


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




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:


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.


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.


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.

It's an offline wallet for one, so most of the security comes from the fact that it's pretty hard to steal. Second, it's the last line of defence. See my comment above about the time it takes to crack even a 5 character password. It's pretty significant. And lastly, what are the chances that 1: someone breaks into your house. 2: he finds your paper wallet, 3: he knows what it is, 4: he has a bot net / gpu mining farm to brute force it.

The cost of breaking the password is based on the strength of the password AND the strength of the KDF. If the password is 'password', nothing will save you. If your password is random 14 character case-sensitive alphanumeric (80 bit), your KDF can even be a single round of SHA512, and it would take the entire BTC network 63 years at the current hashrate (300,000GH/s) to break it.

If the password is 9 random lowercase alphanumeric, that's 46-bits of entropy, or about 50 trillion guesses to decrypt. If you were using scrypt/10-1-1 (LTC) and you had the whole LTC mining network (24GH/s) at your disposal, you could bust through that in 30 minutes. scrypt/18-16-16 however would reduce 24GH/s *well below* 24MH/s for the same network, meaning now the entire network would take 30,000 minutes (20 days) to decrypt the file, which is plenty of time to move funds after your house is broken into and your encrypted paper wallet is stolen.  (Yes, that assumes you know your house was broken in the first place.)  A single iteration of scrypt/18-16-16 takes less than a second on my i7, it's quite manageable.

Now if Satoshi put 1,000,000 BTC into an password-based encrypted wallet and published it on the internet, and promised not to move the funds for exactly 5 years, with a random 12 character case-sensitive alphanumeric (71 bits of entropy) and scrypt/18-16-16 KDF, actually, I think those bitcoin would be pretty damn safe. The cost to decrypt is reasonably in-line with the value of the coins themselves.

TL;DR the point is to increase the cost to steal the funds. The tradeoff is increased risk of losing funds through forgetting the password.  There's no free lunch, but some people will chose to encrypt their paper wallets, and in that case, it would be nice if there was a standard agreed-upon way to do it.

Ok, point taken.

I think I've found a nice way to have multiple encryption parameters, preserving the 'ws' prefix and be backwards compatible with the current test vectors.


128 bit seed:

prefix 0x14D60D : scrypt 14, 8, 8
prefix 0x14D60E : ...
prefix 0x14D60F : ...
prefix 0x14D610 : ...
prefix 0x14D611 : ...
...


256 bit seed:
prefix 0x263AA2 : scrypt 14, 8, 8
prefix 0x263AA3 : ...
prefix 0x263AA4 : ...
prefix 0x263AA5 : ...
prefix 0x263AA6 : ...
...


512 bit seed:
prefix 0x023804 : scrypt 14, 8, 8
prefix 0x023805 : ...
prefix 0x023806 : ...
prefix 0x023807 : ...
prefix 0x023808 : ...
...

And more can obviously be added.

So now it's a simple matter of defining a bunch. :)

Added user selectable KDF + parameters, encoded in the prefix.

Hm. Why are such weak KDFs supported?  Considering that you can now obtain specialized crackers for bc.i wallets that do ~10m passwords per second on a gpu, I'm a little more concerned about the systemic risk of weak KDFs than I was before.

Although I agree that the scrypt 2¹⁴/8/8 KDF isn't very strong, consider that using a 10 character password with upper, lower, numbers and special chars (say 72 different characters) is still going to take you over 5,935 years on average to crack at 10M hashes per second. And that's ignoring the AES / EC public key generation / double SHA256 part that you need to do to verify if it's correct.

The main reason it's in there is for mobile. The scrypt 2¹⁶/16/16 is probably not even going to run on a mobile device and my laptop (rmbp) has trouble running scrypt 2¹⁸/16/16 (but that's probably due to the scrypt implementation I'm using).

Currently there are 3 defined KDF's with 29 left to be defined. If you have any suggestions, that would be awesome.

Scrypt on typical Android mobile is hardly able to run with more than 2^14/8/8

Since key birth is added, this became an interesting BIP. I consider supporting it as master backup format for the BeBop wallet.

That ignores how people actually use passwords, if you have space to store that much entropy you're not actually far from just putting the whole key there. Typical passwords have much lower entropy than that and can be found with far fewer attempts than you'd expect from a uniform probability model.

That said, I'd actually forgotten how the scrypt memory hardness was effected by the parameters, I thought it was just N*128 bytes, which is hardly memory hard considering script memory/computation trade-offs, but it's actually N*R*128, which is a good improvement here. So I'm a bit less than 8 times less concerned than I was before. :P

Basically, there is a bit of a moral hazard with supporting an insecure KDF— users are known to use bad keys, and application developers are known to use the most inefficient code possible in JS and then force users to the insecure KDFs, and everyone has to follow along for compatiblity. These are well established behaviors in the bitcoin world. But I think your minimum is probably fine.

The obvious thing to use instead of scrypt is cantena (http://eprint.iacr.org/2013/525) since script has data-dependent access patterns that leak key material in contexts where timing or power analysis are risks. Might be interesting to get a recommendation from colin percival.

Some other random questions. Is there a reason base64 was not considered? These keys are all too long for the one click copying and reading applications where base58 is somewhat better for... base 64 is 10% smaller and with the right padding can result in a deterministic length. We decided to go with base64 for signmessage and I don't think we've regretted it.

Is there a reason that the sale is HASH256(Base58Check(RIPEMD160(SHA256(K)))) instead of the simpler HASH256(K)?  This avoids a needless entropy bottleneck, additional computations, and an indirect network binding. If you want to bind the network you could just add a network string: HASH256("BITCOIN"+K)

Is there a reason the date and KDF code is not included in the derivation of the salt e.g. salt = length + prefix + date + HASH256(length + prefix + date + K)[0..3]? (length is 16/32/64 or such).  This alternative construction puts the prefix and date under your authentication code, and also increases the space of possible salt values. (the latter probably not very important, though OS password hardening seems to use 64 bit salts typically, but the former sounds useful and important)

Minor bug, your input seed can be 64 bytes, but the rest of the text assumes 32, e.g. the offsets for the whitening and aes key. This should be clarified.
(As an aside I am happy you whiten the input to the EBC mode cipher).

Should the master generation procedure just reference BIP32?

Has there been no interest from wallet implementers in a possible span parameter: e.g. "this key has addresses assigned out to position X?"

For sure. I am hoping for this evolving more into a description of the wallet, not just the master key seed. Master key birth is the first step.
The next would be topology of the tree (again with births) from this root and highest address used on the leafs.

True. But there's not much we can do in software to protect against bad passwords (other than running the obvious checks). You're storing the master key of an entire wallet. When generating one of these codes, it's probably a good idea to make a big deal out of password strength when asking for it


I'll have a look at this, thanks!


This proposal started off as an extension of BIP 0038, which influenced most of the choices, like the initial scrypt 2¹⁴/8/8 KDF and encryption scheme / encoding scheme.


I like the network dependency the way it is, because it's clearly defined how to handle alts.  HASH256("BITCOIN"+K) means that I'd have to define it for all the alts as well, including testnet.

In addition to this, if you now look at the parts needed to verify if a password is correct, you need:

Selected KDF, AES, EC Public key derivation, SHA256+RIPEMD160, HASH256, bigint math to go to string (mod 58), another HASH256. All of this will significantly affect the effectiveness of a GPU based attack.


Sounds good, I'll have a look at updating this.


I'm not sure what you're referring to:


The 32 mentioned here is the AES key length.


I'll add an explicit mention of this.


There has, however, I'm still not entirely convinced I'd want to store a tree structure in the encoding. The point was to make this as compact as possible in order to create a paper wallet out of it.

I guess some form of notation could be added along side it to indicate the tree structure. But even then, I expect the tree structure to grow over time.

Hm. Is an internal network binding really desirable? wouldn't it be preferable to use a prefix character?

The base58 encode can be done without bitint math, it's just a less obvious implementation. Does make a embedded C implementation more of a pain. You get your attack hardness from your KDF... these other operations make the implementation more complicated... which also may make people more likely to roll their own rather than use your scheme. I would encourage thinking about it some.

Sorry, my inability to read. The word 'seed' in the text seems to have given me trouble I keep reading past it. What you're encrypting is a root key. :) I think I keep thinking it's a salt.

Yea, I just wanted to see if there was something simple like a depth counter that would satisfy people, serializing a tree would be kind of ugly in a compact format.

The current proposal has 6 prefix values. I guess we could make the alts use new prefixes, but considering that these could be (and if the proposal goes onto the wiki, probably will be) listed on the prefix (https://en.bitcoin.it/wiki/List_of_address_prefixes) page (many alts are listed there), this could get out of hand real quick.


All operations performed here are already needed in one way or another (except for AES) in any self respecting Bitcoin client. In the current form, that part is shared with BIP 0038. Although I agree that a HASH256("BITCOIN"+K) is easier, I haven't heard any complaints about code complexity here or in the BIP 0038 thread.

As for people rolling their own solutions, I think that interoperability far outweighs the complexity though.


I could go through and rename it root key. Far more descriptive.

I've changed the salt to be prefix + date + checksum. I've also renamed it 'root key' instead of 'master seed'.

I contacted the Catena authors and they're currently developing an improved version. They also sent me a copy of their code, but they don't consider it to be a proper reference implementation.

End users are notoriously bad at selecting strong passwords (hmm... need a special character, let me put ! at the end). One way to handle this is by letting the software generate a random password using the full key space. This allows you to reason about the combined strength of the KDF and the entropy it works on. Obviously a randomly generated 14 character password is impossible to remember, so this forces the user to put it on paper, which is good.

I would love to see some calculations on the strength of scrypt with selected parameters for various amounts of entropy. The best source I found so far is from a presentation by Colin Percival's (scrypt author): http://www.tarsnap.com/scrypt/scrypt-slides.pdf
His presentation outline the cost of breaking scrypt for various parameters in one year. The interesting part is on page 16-18.
With:
which is about 65 bits of entropy.
He estimates that it will cost you:
 $43B to brute force in one year with parameters (N=2^14, r=8, p=1)
 $175T to brute force in one year with parameters (N=2^14, r=8, p=8)

Measuring the cost to brute force is ingenious in a Bitcoin context as it gives normal people an idea about what they are dealing with and the amount of funds they are willing to protect under certain scrypt parameters.

I cannot tell whether his numbers still hold, some time has passed since then. In the meantime we have seen scrypt mining, albeit with pretty small memory requirements (N=2^10, r=1, p=1). Thoughts?

I pointed this out in another thread, and to Mike Caldwell in relation to BIP 38, but I think people are not aware.

You do not need to do work when you create the key.  Only when you decrypt it.

Instead of k=scrypt(salt=0,iter=65536,mem=1GB,passphrase) you can use random 16-bit salt k=scrypt(salt=16,iter=0,mem=1GB,passphrase) with a salt you securely delete after key generation.  The work is the same and the setup cost trivial for a smart phone.  Obviously its easy to create key stretches you cant undo even with a super computer or the entire bitcoin network, so you have to apply strict sanity checking to the parameter choices.

(As an curiosity aside, to create asymmetric work decryption with symmetric crypto, is an extremely old design, due to Martin Hellman which led to the discover of public key cryptography, practically cryptographic archeology :)

You can also adjust the difficulty over time, by deleting another bit to adjust for moore's law once a year or so without changing keys and addresses.  You can after the fact harden your KDF.  eg if the bitcoin become worth more, or if you start simple and end up with more holdings relying on it.


I have another KDF approach also based on a blind version of Rivest et al's time-lock puzzle which allows third parties to do the KDF work for you, in zero-knowledge for a fee.  At litecoin prices it allows you to add 44bits to your KDF for a fee of 50c.  (or 40bits for a fee of 3c).  Lower than the bitcoin fee.  That can make grinding even  relatively weak password economically infeasible and litecoin-like networks are probably the most efficient rentable computer on the planet.

It gives GPU miners something to do and allows a smartphone to directly provide massive KDF security.  Your private key, if encrypted, once in the hands of your attacker - be that physical laptop theft, cyber criminals from an online or USB bios attack, law enforcement investigation - *becomes* a brain-wallet.

I encourage people to consider the offloadable KDF approach.  It provides a combined cryptographic/economic defense and level of assurance to brainwallets and stored-wallets that is not feasible otherwise.


Have you looked at what bitcoin armory does?  They are using scrypt's romix which is has a memory hard security proof, but tweaked slightly for cpu/memory.

Btw I presume people know that scrypt has TMTO tradeoffs and is was actually not designed to prevent that.

Adam

Some of the concerns about KDF costs could potentially work by making the KDF work delegatable.

Adam3us' blind puzzles are probably a bit too far rocket-science for this BIP, but simply restructuring the encryption like:

Key = HMAC(  KDF(HMAC(passphrase,salt)), passphrase||salt)

This would make it possible for a mobile device to ask a fast computer to do that KDF for it without completely losing all security.  Mike Caldwell had indicated that the ability to delegate was a shortcoming of BIP38 that he'd like to see addressed.

Sorry for the late reply, I was AFK for a while.

gmaxwell,

I'll see what I can do to add support for adding delegatable KDF work.



Adam,


You need both the encrypted and clear version of the key during generation. The end result contains a partial hash of the root address, so you won't be able to get around doing the work at least once when generating a key.

As for the rest of your proposal, it's a bit above my head. Would gmaxwell's proposal open up the possibility to do what you proposed? If not, what kind of additional changes would you suggest to make it work?

You do have the key.  My point is you can do it fast before you delete the salt.  After you delete the salt it becomes hard as you have to search for the salt.

You do not need to do work when you create the key.  Only when you decrypt it.


Replying to gmaxwell now I have another idea.  Secure offload with symmetric crypto no blinding.

Adam

But I think you can do it by making 100 KDFs, and add 50 of them together mod n.  Then you shuffle them send all 100 to the network, it does the KDF stretching which is expensive, sends the 100 back to you.  You pull out the 50 that are correct combine and decrypt.

https://bitcointalk.org/index.php?topic=330819.msg3548144#msg3548144

what makes it hard is the network doesnt know which 50 of 100 which is work ~2^128.  There is no closeness metric so you have to brute force.

Adam

I'm not so sure about that.

Your (correct) KDF queries are generated from the password, and perhaps a salt.  Right?

We're assuming that the attacker somehow has your encrypted wallet key. He's trying to guess your password, and he's previously done KDF work for you.

The attacker guesses your password is "bob", now he generates the resulting KDF queries and sees that they match the work you asked him to do. He goes and simulates your full process, looks up his saved kdf results, and can now steal your coin.

The problem there is because the process is deterministic given your password and the wallet seed he can just regenerate the correct queries and ignore the chaff ones. (Unless you have a KDF which has some homomorphism that allows blinding, and I think thats both asking too much of implementors and escaping from the realm of memory hard KDFs that we'd prefer to use)

Yes you are right.  It was written in great haste as I was leaving, figured this out shortly afterwards.

The problem is the network can be expected to cache your correct password result after KDF.

Therefore the only thing this could be good for is a one use signature (eg a big stash that you dont touch except once to sell it).

Or if you have a seed encrypted 1000 times with each different salt and the same password, and you securely delete the respective encrypted seed after each use.

50 choose 100 doesnt seem to help that picture.


I think the Rivest & Wagner time-lock puzzle (which I extended with blinding) might be somewhat memory hardenable if one used bigger RSA key than necessary for security.  Not really tried to analyse it from that perspective so far, there may also be some parallelization opportunities or TMTOs.

The basic RSA blind signature is rather simple, eg used in the coinjoin protocol right.  The blinding variant I use for blinding the time-lock puzzle is quite similar.  Maybe it wouldnt be so bad if a simple reference implementation in OpenSSL were provided.

Adam

Standardizing wallet root key encryption is a good idea. The proposal looks solid.

My only concern is this: If this proposal is adopted to replace single-key encryption as defined in BIP38, it should maintain the ability to decode those formats to the extent possible. This because BIP38, while still technically a 'draft', has proven very useful and has already been widely adopted for paper wallet encryption, many applications already use BIP38 in production. In addition to some applications for physical bitcoins (i.e. Casascius coins), other applications are also being proposed which rely on heavily on BIP38 'standards' (i.e. OpenCXP, POS using NFC, etc).

Should BIP38 (single key) encryption perhaps be maintained on its own since it already has specific applications? - Or is this intended to supercede or somehow merge with BIP38?

I never intended for my proposal to replace BIP 38.

In fact, I contacted Mike prior to posting my proposal to integrate it into BIP 38. He felt that it was different enough to warrant its own BIP, so I went ahead with that. Having said that, I can see why people would want to replace BIP 38 with this one, but there's one key feature that this proposal doesn't offer that makes BIP 38 still a very useful standard and that's 3rd party key generation (with the passphrase / confirmation codes). I don't think that's something this BIP can offer, so even if this BIP were to replace BIP 38, there would still be use cases for BIP 38 to thrive.

Well, I certainly intend it to replace BIP38.  BIP38 was dropped onto the wiki without any public review or discussion and contains a number of unfortunate shortcomings which are corrected here.

The WRT third party generation, I think this proposal does accommodate that in a not-quite 1:1 manner... in that you can send someone off your encrypted key to transcribe.  Though even if it doesn't thats just a single use case— the fact that BIP38 can only accommodate a single address is a reason something should replace it even for that use case. Though I'm not sure how common that usecase will be in the future considering recent regulatory activity.

Possible scenario:

The police or mafia or whoever find your cold wallet. They iterate over all known addresses in the blockchain and find that an address with a hash matching your master public Bitcoin address has been used before. Maybe they want the owner of that address for some crime (like money laundering). Maybe they think you owe them protection money. Either way, they have some very strong, 32-bit evidence that you own the master address for this wallet.

Possible solutions:

1. Use a random salt and encrypt these 4 bytes along with everything else. Unfortunately, this increases length.

2. Use SHA256(SHA256(privkey))[0:3] or something instead. The information leak is much less useful that way. The absolute worst possible case (if SHA2 is broken completely, which is another issue) is that they've reduced the security of your master private key by 32 bits. Not a big deal.

I think the issue was more the fact that Mike was selling loaded coins and not the wallet aspect of it.

I haven't updated the spec yet to support 3rd party hashing. Hopefully I'll get around to that the coming weeks.


You're right, however, this only applies to the first key generated off the salt. I'll update the spec to mention this issue and to avoid using the top level key pair.

On a similar vein, I would prefer it if the date was an optional field or wasn't present at all.

For one, it's an information leak. They know roughly when I created the address, which could be used as evidence.

Second off, how are clients supposed to use it? What happens if the clock on the computer you used was wrong? Does the client just not look for old transactions? IMO, anyone who is really concerned about reducing blockchain scan time can use some kind of data structure suited to the task. It's a good idea, but I think the risks and potential software problems associated outweigh the benefits.

We can also shave off two bytes, or just use it for a random salt.

How could this be used as evidence? It can be easily changed to include a different date if you prefer or you can just set it to 0. If you don't use the top key pair, there's no way to tie any transactions to this key. The date doesn't prove anything in and of itself.


You can pull the date from the top block in the blockchain when creating the key.

I can't change it after the fact if it's used in the salt, and I doubt most implementations would add the extra dialogue option to fake the date. And what if I accidentally changed it to the wrong date, well after the first actual transaction? As for use as evidence: "Mr. Smith, one of our suspects, created this new wallet the same week our perp received a thousand BTC... awfully suspicious."

I don't intend to use this algorithm on a networked computer, so I can't use the blockchain or ntpd. In fact, my target is a Raspberry Pi with no network connection (and also no RTC), so the fact that the date is integrated into the spec would be kind of a pain.

Like I said, it's a good idea, but I don't think it will end up being worth the hassle. Someone could always just write on their cold wallet "I made this on December 3" and then if the client supports after-date lookups they can use that feature.

Then set the date to 0, problem solved. You can write your own implementation or you can modify an (eventually) existing one if you want.

Let's look at the pros and cons of having a date field.

Pros:

If the wallet generator implements the date field, and if the user wants to use the date field, and if the Bitcoin client they're importing to supports the date field, and if they don't put the wrong date in, they can save maybe a few minutes on a block chain rescan.

Cons:

It's an information leak.

It increases the size of the string by two bytes.

It will break things if the generator has an incorrect clock.

It will increase software complexity a little bit on the generator side and possibly a *lot* on the Bitcoin client side.

I disagree. Even if you feel it's an information leak, you can set it to 0 and the problem is solved.


True, but I consider that a minor issue.


The resolution is a week. Your clock would have to be off by that much into the future before it becomes an issue.


This is simply not true. Iterating over the blockchain to find the scan start point requires minimal effort. In fact, it's no different than doing a full scan, the only difference is when you actually start parsing the transactions in a block.

What if the software I'm using doesn't let me set it to zero? Yes, I can change it, but can every end-user?

Those two bytes could either be shaved off or used for something more useful.

What if my platform doesn't have a clock *at all*? I might need to automate this process.

What are client devs to do if the date is wrong? Do they throw an error? Crash? In some cases, they can't even know that the date is wrong without scanning the entire blockchain anyway. How would you propose working around that?

I really don't see the benefit of the date field. There are only a few situations where it will be useful at all, and even when it is useful, it saves minutes at most. Why is that so important?

You're the first to bring up this issue whereas I've had several requests to include a time field to limit blockchain rescan. It's a non-issue. If you really want it to be zero, that's a feature you can request from developers of the client of your choice.


I have yet to encounter a single computer that doesn't have a clock.


You don't need to scan the entire blockchain to figure out the time. You only need to look at the top block.


It might save minutes now, but the blockchain will only get bigger and this will become a bigger issue.



The date field stays.

Requests from whom?

The Raspberry Pi doesn't have a clock. It's one of the most popular computer platforms out there.

I don't think you're seeing the issue; What if the encrypted wallet has an incorrect date string? How is the client to know? If it just skips ahead to the date listed on the encrypted wallet, it could miss a whole bunch of important transactions. How do you propose we deal with that without re-scanning the entire blockchain anyway? Any solution I can think of removes the utility of a date code in the first place.

As the blockchain gets bigger, computers get faster. If it was ever really an issue, we could just have an auxiliary data structure that records first transaction date for any given address (which means no date code is needed).

Why are you speaking like this is so final? You haven't really given a compelling argument for the necessity of the date field, and I think I've given several strong arguments against it. I'd like to hear from others what they think.

From myself and probably any SPV wallet author too. This is a common feature in wallets which makes an _enormous_ performance difference for both full nodes and SPV nodes, and anything else without an enormous disk wasting historical index.

Dates with keys is a feature already supported in every SPV wallet, as well as Bitcoin-qt. It makes a huge impact on rescanning speed.

If it's incorrect and you're able to scan without it, then go ahead and ignore it. Asking for an approximately correct date while generating a key is simply not a burden. If you're unable to handle this then you're going to garble up the addresses and send coins off into space.

Because it's a major requested feature and you can simply opt out of it either on the generation (set to 0) or use (ignore it) side.

Fair enough. I can see the big advantage with SPV nodes.
 

I do worry about determining whether or not the reported "creation date" is far ahead of the actual "creation date". It's possible to miss transactions that occurred before the "creation date" and fail silently.

Request for a date field from Mike Hearn: http://sourceforge.net/p/bitcoin/mailman/message/31201149/

Request for a date field from Tamás Blummer : https://bitcointalk.org/index.php?topic=258678.msg2766686#msg2766686


Then set it to 0 on the Pi.


Even if the computer that generated the seed was off by several days, it would still cover it. The date field is by week. And if you find mismatching transaction history (funds being spent that haven't been found during the scan), you can default back to whole chain scanning.


It's not about speed it's about touching lots of data. You don't want to have to go through the entire blockchain in an SPV client, especially on a mobile platform.

Alright, understood. But this still bugs me. What if there *is* no mismatching transaction history? The address could have done a bunch of stuff before the "creation" date. As long as no txouts generated in that time period are used by the wallet after the "creation" date, you would never know. There would be no indication that you had to default back to whole chain scanning.

But I admit, this is a much smaller issue than the other ones I brought up (which have been addressed).

Implemented it here: https://github.com/wyager/Encrypted-HD-wallet

I followed the suggestion of the checksum being SHA256(SHA256(private_key))[0:3] instead of SHA256(SHA256(bitcoin_address))[0:3].

It's not heavily tested, but as far as I can tell it works fine.

I just boarded a plane, so I can't look at I right now, but a quick question for gmaxwell and others about using the hash of the private key instead of the address: yes / no?

Block number might be a reasonable alternative to a date? Less arbitrary?

Good thinking, but that actually exacerbates the problem I brought up earlier (that some computers aren't internet connected). The block production time is actually a tad unpredictable, since sometimes (in fact, for the last few months) the network hash rate grows so fast that the difficulty adjustment algorithm can't compensate enough to keep the average block production time very close to 10 minutes. Therefore, it's effectively impossible for an offline wallet generator (which is probably one of the most common uses of these wallet encryption algorithms) to get an accurate, or even semi-accurate, block number. But date can trivially be mapped to block height on a networked machine, once the coins are being spent.

Regardless of how it found its way to the wiki (over a year ago), BIP38 has already become the defacto standard for single key encryption for off-line storage, possibly since there wasn't really anything else out there. Many (most?) paper wallets now support it, along with at least one major wallet (Blockchain).

To be sure it may have a few shortcomings like fixed scrypt parameters, but its actually pretty versatile and cryptographically sound for its intended use: Encrypting single private keys and third-party key generation - it appears that it was never really intended to create/backup deterministic wallets, so these aren't necessarily shortcomings anyway, since the standards probably don't have much overlap for most use cases.

I've changed the checksum to be a double SHA256 of the private key instead of the address string and I changed the hashing so it can be outsourced to a 3^rd party.

would it be possible to modify the checksum to a bloom filter so that you can do plausible deniability with multiple passwords?

Great. I'm working to update my reference implementation.

I'm a little confused on the 3rd party thing, though. What is the need for this?

Also, a few questions on the implementation side of things:


1. Why do we use key=salt, msg=passphrase in 8. but key=passphrase, msg=salt in 10.?

2. Can you please expand on step 9.? If we're using scrypt, we also need to provide an output length parameter. What should that be? Why do we use preH for both salt and message? Is that safe?

Great! Make sure you can parse the test vectors. :) Also, apetersson's suggestion of changing the checksum to a bloom filter is interesting. The only thing I worry about is losing entropy, so anyone here that knows how to construct a sufficiently obfuscated bloom filter that's both useful and doesn't affect entropy too much, please let us know.


On page 2 in this thread, there's discussion on having 3^rd party KDF support added.


If the 3^rd party that does the key stretching for us is malicious, and preH and postH are the same, he has all he needs to decrypt our root key (should he ever get his hands on it). By using a different salt in step 11, that's no longer the case and he'll have to brute force it.


Oops, you're right. Length of strongH = 64 bytes. I'll update the spec. Using preH as salt and message is perfectly fine. It's basically the same as not having a salt like SHA256.

Thanks. Some small suggested changes:

1. Specify endianness of the each field. In your examples, the prefix is big-endian, but the date is little-endian. I recommend big-endian for all fields (since in many scripting languages, it's easier to go from an integer to a big-endian string than a little-endian string).

2. Recommend that client implementers check the blockchain, say, a day before the beginning of the "recorded" date to account for slightly incorrect date calculations. Either that or specify that the date code should be based on date minus one day.

All test vectors passed in my implementation!

Please specify that unicode passwords (like the chinese one you gave in the test vectors) should be converted to UTF-8.

Bitcoin is little endian, with exception of big int math. BIP 38 is also little endian, with exception of prefix. I've clarified that the date field is little endian.


Done.


Yay!


Done.

I've been doing some tests with the bloom code in the qt client, and if I understand it correctly, when set to 4 expected elements and a 1% false positive rate, the bloom filter is 4 bytes in size with 5 hash functions.

So that would generate up to 20 random bits of data in the 4 byte field. I think that's sufficient to keep the entropy up. Also, since it's 4 elements, that's 4 potential passwords that could be used.

In other words, I could modify the spec to encode up to 4 passwords into the checksum instead of the double SHA256 of the private key. Any less than 4 passwords would be filled with 5 random bits of data in the checksum for obfuscation.

What do you guys think?

For plausible deniability it should be possible to mine an alternate password that create a key that passes the checksum as is.

Created an implementation in Java that passes all test vectors:

https://github.com/bitsofproof/supernode/blob/master/api/src/main/java/com/bitsofproof/supernode/wallet/EncryptedHDRoot.java

The test cases are converted to JSON:

https://github.com/bitsofproof/supernode/blob/master/api/src/test/resources/EncryptedHDRoot.json
and were run with this unit test:
https://github.com/bitsofproof/supernode/blob/master/api/src/test/java/com/bitsofproof/supernode/api/EncryptedHDRootTest.java

If you mean mining a password on the current checksum (as currently defined in the spec), then you've got quite a bit of work ahead of you. Matching a 32bit checksum is a lot of work and the resulting password could be total gibberish and pretty hard to remember, not to mention that you're basically brute forcing the KDF, which is was chosen to resist such attacks. Or am I misunderstanding what you mean?


Awesome! :)

Yes, its a lot of work, but doable and the denial is then rather plausible. If you think that is too big of a hurdle then reduce the checksum length.


Storing the HD root is useful.
Recreating the keys that are used on the block chain needs however further conventions, so it can be done in a scalable manner.

Let's call the keys generated by the root key(0), key(1), key (3)....

Now let us assume that if key (n) is first used in block b, then there should be no reference to key(m) (m > n) in any block before b. With this rule one can efficiently scan the block chain in a single pass using a look ahead window of w:

Assume key(s) is used after block b (identified by the birth date of the root) and scan subsequent blocks. If any key (m) (s<=m<s+w) is used then continue scanning with w := w + m - s; from that block on.

Note that the search window increases during the scan. A good HD wallet software would further optimize the use of keys such that it seeks to reduce the search window by spending outputs on keys earlier in the key sequence. It would seek to re-set first key index s with a new birth date.

Therefore I suggest to extend the proposal with a start key index (4 bytes) and a look ahead window (4 bytes).

Actually 2 bytes should be more than enough for look ahead.

Grau, if I'm understanding you correctly, you say that we could optimize blockchain scan times by only using keys serially? So the root key is used in the blockchain before any derivative keys, and those are used before any of their derivative keys, etc.

How do you propose to enforce this? Prevent users from choosing which address they'd like to use? It seems like that would put some annoying limitations on flexibility.


I agree with riplin that brute forcing a 32 bit hash is not a viable solution. Not only would the plausibly deniable passwords be very hard to remember, but it would take forever!

The bloom filter is interesting. You could choose arbitrary passwords to use for plausible deniability.

A HD root can generate 2^32-1 keys and any of these keys might be the root for a further derivation. Now assume you get a HD root and would want to determine the funds associated with it. It is not feasible to find them in absence of assumptions. I suggested some assumptions I keep while developing HD wallets.

Assumptions:

1. : the root you have identifies leafs of the hierarchy. If not then use the same assumptions on the sub-levels on-by-one.
2. : if key(n) derivable from the current root is first used in block b then key(m) | m>n is not used in block d | d < b.
3. : if you do not find a use for key (n) then there is no use of any key (m) | m > n + w.

You might not like to have the assumptions, but I think they are sensible. I can not see how you implement scaleable discovery of funds associated with a root without these or similar assumptions.

If brute forcing the checksum for an alternate password is not feasible with 4 bytes then reduce the checksum length instead of introducing a more complex concept.

I think that the HD root is actually useless in absence of limiting assumption on its key use that allow efficient discovery of associated funds.

Assume you get a HD root where random child keys are used to store funds with, and even random child keys were used to start an other hierarchy level.. and so on. Now write an algorithm that finds the funds associated with that root in human timescale.

I think the best default structure is a case where the root is used to produced an unlimited number of first level children (in sequence), and each child produces a linear series of payment addresses (also in in sequence).

Each first-level child of the root seed is called a payment channel.

Payment channel 0 is the internal use channel. It's where the client produces individual receive addresses and puts change outputs.

Each subsequent payment channel is given to individual senders as an xpub.

If Alice wants to receive bitcoins from Bob, she generates the next unused payment channel and gives the the appropriate xpub to Bob. Now Bob always knows how to send funds to Alice without any further key exchange (TOFU security). Bob can now tell his client "send X btc to Alice" and the client automatically does the right thing, and Alice's client already knows which addresses to expect future payments at because both clients are being sane and increment indexes monotonically.

Your suggested assumption is equivalent with mine with a look ahead window of 1. I think that is too strict and give you an example why:

Assume Alice generates addresses for bills as consecutive keys of a root (or sub-root does not matter). Most bills get paid a few not.

Now Alice loses her hard drive that recorded all transactions but has the HD root stored. With an look ahead window of say 10, she would re-discover bill payments even if there are some gaps in between them in her key space.

I'm fine with configurable lookahead windows, but I don't see how that fits into your example.

Alice presumably is receiving bill payments from a large number of payees.

Each of those payees should be generating deposit addresses themselves from a unique xpub Alice gave each of them.

If a payee does not pay a bill one month, there's absolutely no reason at all they should skip ahead.

Alice should also not be specifying the addresses to which each payee should send payment for a specific bill.

I like in the current proposal that it checks the validity of the key not that of the passphrase.

The passphrase could actually be BIP39 input, then you have pronounceable passphrase for the real or any brute forced alternate password.
If brute forcing 32 bits is not feasible just reduce the checksum length.

Usually it is not the payee who generates the addresses, but the one issuing the bill. It is also natural to associate 1-1 a bill with an address, as also the payment protocol suggests.

Then the payment protocol is broken and wrong from a privacy and commerce perspective, probably written by somebody with no business experience in net D (http://en.wikipedia.org/wiki/Net_30) billing.

The person issuing the bill has no idea how many transactions and addresses the payee needs to use to make a payment and shouldn't care.

Let me give you an example based on how companies actually do business in the real world. When factory A's maintenance department orders supplies from Grainger, (http://www.grainger.com) Grainger makes no assumptions at all about how that invoice will ultimately be paid. It might be paid all at once in a single payment. There might be multiple invoices outstanding and the factory cuts a single check that covers all of them. There probably will be be a many-to-many relationship between the number of invoices and the number of payments.

Any accounting system that assumes a 1:1 invoice to payment relationships is hopelessly broken in the real world and should be discarded. Don't build that kind of brokenness into a protocol from the very beginning, especially when there are real negative privacy implications associated with doing so.

I agree that more than one transaction might be used to pay a bill, but do not see how that disallows that those transactions send to the same address.
I also do not see the privacy violation you claim this imposes. What did I miss?

I don't even know where to start if you're not already aware of the reasons why addresses should never be reused. That's pretty fundamental to the blockchain model.

http://bitcoin.org/en/bitcoin-for-developers

https://bitcointalk.org/index.php?topic=334316.0

http://coinconsultancy.com/2013/07/10/reclaiming-financial-privacy-with-hd-wallets/

http://www.coindesk.com/merge-avoidance-privacy-bitcoin/

You must be joking. I leave this as is as this is off topic here.

Ok, now I'm really concerned.

You're seriously saying you don't see why two transactions in the form (A->C, B->C) have a privacy problem that the two transactions (A->C, B->D) don't have?

You used to be a nice chap, so I put aside my embarrassment that you think I would not understand the basics and attempt to elaborate:

Yes, re-using addresses is bad in general and should be avoided if done for no reason, but is not a dogma.
In case of a bill where the address is generated to collect payments for that bill, I see no problem with it. But even if you would want to address that one could create more than one address for a bill that the payee can chose from. Still I think that the person who creates the bill should be in control of where he wants to receive the money and not hop that the payee makes some sensible choice out of a huge range he has to potentially monitor.

You're vastly underestimating the problem.

Actions which reduce privacy are, by the nature of the blockchain, permanent and their ramifications are not always apparent at the time of the event. Actions today which may seem to be no big deal are only going to grow in severity over time as blockchain analysis techniques get more advanced. Dogmatically avoiding address reuse is the only responsible policy. It's not sufficient to ensure privacy but it is a minimum necessary condition.

Putting control over privacy in the hands of businesses who hand out invoices guarantees it will be destroyed because many businesses are privacy-hostile or just don't give a shit. The only possibility of having good behaviour on the network is if the required actions are under the control of the payers, not the payees. This is where control over privacy should properly reside anyway because it leaves both sides free to choose how much privacy they do or do not want. A payee who receives unmerged outputs to distinct addresses is free to merge them if he or she wants, but a payer who is only allowed a single address to pay to has someone else's privacy police imposed on them unilaterally.

The attack vector you're describing exists no matter how many addresses are used for a transaction. A malicious customer could send 1000 separate outputs to the same address just as easily as he should send 1 output to 1000 separate addresses.

I understand your concern and support any remedy to it to the extent it is feasible - means can be implemented efficiently.

Both of us propose unique addresses per bill. Now let's review the choices:

1. The creator of the bill (business) presents the address(es) - This is potentially bad for the privacy of the payee since it could be poorly chosen such as: recurring, customer linked or master public key leaked.

2. The customer pick the address(es) - This is potentially bad for the business since it could reveal its revenue to competitor if customer re-uses or leaks the master public.

Whoever creates the address has the means of hurting the privacy of the other.

You value privacy of the customer higher and I sympathize with that, but do not support it for pragmatic reasons, that are:
The customer will likely use simpler software and several devices. Chances that he is not tracking the sequence numbers correctly or is leaking the master public are good. There is also a scale issue. If one assumes that businesses have magnitudes more customer than the number of businesses a customer deals with, then it is likely that 2. would magnify the effort on monitoring and reconciling payments on the side that already has the bigger problem.

The customer doesn't have "the" master public key, they have one specific to them. At worst, they can leak the amount they, and only they, have paid.

Any serious B2B or B2C business is already using net accounting that does not assume a 1:1 relationship between invoices and payment - if they weren't things would blow up all the time.

Think about it: a phone company issues a $50 invoice to a customer in November. The customer is late with the payment and hasn't paid by the time the December bill posts. Now he owes $100.

The customer can pay that as a $100 lump sum and the phone company's accounting system will have no problem whatsoever. The customer can even pay $75 when the December bill posts, and then $25 a week later. Their accounting system will have no problems keeping track of which invoices are paid and which are outstanding in either case.

Maybe I need to write up a guide to business accounting practises for Bitcoin developers as a blog post. Implementing net accounting is not hard, but if somebody naively implements accounting with an embedded assumption that for every invoice there will be exactly one payment things are going to fail hard for somebody when real life fails to live up to the requirements of their accounting model.

I get your point with the net accounting, but do not think that it has to be solved with giving the customer the choice of addresses to use. The business can net across payments received and bills written and keep track of the outstanding amount also while generating addresses. Newly issued bills could also indicate and expect net outstanding amount on their address.

I look forward to your blog post. Please also address my concern there that the customer would need more sophisticated wallet maintaining his master public at the business and his last used sequence across his devices / wallet instances otherwise it converges to a more complicated, but equivalent model of the business providing the address.

Since the last points I raised on-topic are important for a scaleable implementation, may I re-quote:



I suggest to include the start key sequence (n) corresponding the key birth date and the size of the look ahead window (w) into the proposal. A wallet should seek to limit the expansion of the key set during the scan by spending older outputs and re-set n with birth date whenever possible. 4 bytes are needed for n, 2 bytes should be sufficient for w.

If the business tells the client the next unused index value each time it sends an invoice that would solve the problem you describe without removing the client's ability to choose how many new addresses to use

The business would also have to re-tell the master public in case the customer does not have it at hand and we are back to square one.

Not really. An xpub + index hint does not restrict the customer's client in the same way a single address or static list of addresses restricts the client.

I do not see the fundamental difference between xpub + index and an address list to choose from. The business has to limit the index range it monitors for performance reasons, that is effectively giving an address list.

Actually the business has to send xpub with every bill otherwise we would need yet an other more complex protocol for key revoke in case previously used key was compromised.

I think that for reasons of performance at the receiver side, simplicity and privacy at the payee side, it makes sense that the receiver generates a choice of addresses valid for any payment starting with the time point of that bill.

And yes, receiver should track outstanding amount by netting all previous bills and funds received on any address previously communicated. That however is a requirement of bookkeeping either.

There is an other reason why the receiver has to provide a payment address with the bill: By doing so, receiver declares that he is in (exclusive) control of the key that belongs to that address, so a payment made to that is received by him. It is not deniable.

The receiver however has to be able to revoke that declaration for the future, since he might lose keys or might have legitimate reasons for using a new master key generating the addresses (be it for performance or a merger). The simplest way of implicit revoke is to agree that with any new bill, and new address with it, all previous addresses are no longer valid for payment. There should also be an explicit expiry for the bill, so a new one with new address is issued if the previous is not paid.

Add the requirement that new bills should indicate net outstanding amount and the option that a bill could offer more than one new address and we are all happy.

Last message on-topic:
https://bitcointalk.org/index.php?topic=258678.msg4180842#msg4180842

I think it's impossible to enforce that addresses are used in sequence, considering that customers won't pay in sequence, refund addresses given to suppliers could be funded months after issuance, etc.

So how would you scan the blockchain to reconstruct the tree? Well, it's an issue of scale mostly. Using lookahead windows is a quite narrow view and will cause problems very quickly.

So instead, construct a bloom filter that will filter the blockchain a few days since birth of the root key. Constructing a bloom filter that scans for a million possible addresses would take 1,198,132 bytes, with 6 hash functions for a false positive hit rate of 1%. No need to keep all those addresses in memory.

Second, you can construct a hash table with a 4 byte partial hash of the address as key, that will then give you the hierarchy where the key lives. If you get a hit on the hash table, you can then reconstruct the branch and do a full address match. Should it hit, you can keep the branch in memory, and even expand your coverage, should the address live near an edge of the tree currently in the bloom filter / hash table.

Even if you were to expand this to 10 million addresses, you'd still only need 11,981,322 bytes of memory for the bloom filter. The hash table is a little heavier, but is still quite manageable.

In other words, this scales quite well and does a far better job at finding relevant transactions than any kind of window based scanning can ever do.

Assuming that the master public is not disclosed, then it is only the owner of the master key capable to add to the set of known members of the sequence. He can impose a maximum gap by not disclosing more than w new addresses until one of them is used on the block chain.


We have not a 1 or 10 million possible addresses but 2^32 that is 429 times 10 million. Scale your numbers accordingly. Also keep in mind that retrieving those 1% false positives is not cheap plus lookup is usually not just for transactions benefiting an address but for transactions that spend that output.

I think you will revert to the suggestions after you attempted to implement a HD scan. I did.

BTW even instantiating 2^32 addresses is a significant task (2^32 HmacSHA512 + 2^32 * EC add + 2^31 EC multiplication + 2 * SHA256 + RIPEM160) then you have a few hashes to look up a bloom filter of 4 GB to identify 1% false positives, that is 42 million
random accesses to a database.

And all you have with that are transactions that deposited to the address. Then you need further passes to find those transactions spending those deposits.

go for it.

There's no reason to scan all possible addresses at the same time. You could make a sliding window with a bloom filter the same way you would with your 100 address lookahead. That 1% will be culled mostly by that hash table that you've got after it passes the bloom filter. And the last step with the branch reconstruction culls 100% of the false positives that managed to get through.

Either way, there's no need to include a lookahead count in the encoding.

As for the sequence start, what's the value of having a non zero sequence start number?

I do not get it.

What do you build the bloom filter on? What does a hit tell you and how does that help you to reconstruct funds accessible to keys derivable from the HD root? Forget the tree for the moment just enlighten me on how you would handle a flat key space of size 2^32 used in random order.

Granted, you wouldn't be able to handle a 2^32 space in random order without constructing a bloom filter of that size, but when you create a ridiculously large 'window' of, say, 10 million addresses, and start scanning with that, you basically no longer care much about the fact that payments may come in out of sequence even if you give the addresses out in sequence (mostly because the out-of-order-ness will be in the 100's or 1000's range).

You start constructing a second bloom filter when you start to hit addresses that are getting close to the upper limit that you're currently scanning (say, 500,000 under your 10m boundary) and slowly keep adding to the second filter. When you haven't found a positive hit in the first filter, for X blocks / transactions / whatever metric you want to use, you can discard it and start working on the third filter, etc.

As for what you build a bloom filter on, it's the same bloom filter that SPV clients use to request transactions from peers. They send a bit field with randomly set bits that correspond to indices generated by hash values based on the address used (either sender or receiver). The number of indices (what I called hash functions previously) and the bloom filter size can be varied. In the case of Bitcoin-qt / bitcoinj, the bloom is limited to 36,000 bytes maximum. It's a flat array, so lookups are constant regardless of size or number of elements covered.

The filter guarantees that all addresses you're looking for will pass the filter, but the reverse is not true. It's possible that unrelated addresses can pass the filter (and in bitcoin-qt / bitcoinj this is actually used to preserve privacy, by dirtying up the filter a bit).

It's a really fast and lightweight way to filter big amounts of data down to mostly what you're looking for plus some cruft. Then you can move on to more expensive filters, like hash tables and finally doing exact matches.

Here's the bloom filter wiki if you want to read up on it some more: http://en.wikipedia.org/wiki/Bloom_filter

Just a note for thread readability to others trying to follow this:
payee = recipient ; payor = sender of payment

Payee appears to be used to refer to the payor in this thread?

So you create 10 million addresses of the HD root - lets ignore that this is already a computation intensive task -, then you ask a giant bloom filter you previously populated with addresses used on the block chain and bingo you figure that 100.000 (1%) of them is possible used on the block chain. Does that tell you anything about the funds on them, nope. You still need to fetch 100.000 using some traditional database index on address. Does that tell you the funds on them ? nope. Since even those you feteched might be spent already and you would need to also fetch transaction eventually spending those outputs. Is this sufficient? nope You are marely done with 1/400th of the key space. This is you call feasible algorithm? me not.

BTW, I am familiar with the bloom filter and use in my Bitcoin implementation not only for SPV support. You should rather be more curious of how I solved the problem of figuring funds for HD root instead of proclaiming without any practical experience that the parameters I propose are not needed.

My fault. I used customer = payee although the customer in the discussion was payor.

There is no need to populate the scanner with 10M addresses, I merely used that number to indicate that it scales very well countering your statement on page 4 of this thread:


The argument that I have to scan the entire 2^32 keyspace is silly. It only needs to scan / move the window along until it reaches the top block and you're not even going to get close to the 2^32 address limit in any dimension of the tree. I'm quite sure your solution doesn't scan the 2^32 keyspace either.


The way you asked the question and the fact that you referred to a bloom filter as a 'complex concept' made me think you hadn't used bloom filters before. My bad.


In any event, brute forcing a password to fit a checksum is silly. This could take hours, even days. I'd have to reduce the checksum down to 2 or even 1 byte depending on the used KDF to make this a feasible method of finding an alternate password.


I'm not 'proclaiming' anything. I'm merely offering an algorithm that scales fine. I'm sure your implementation works magnificently for your HD wallet usage, that doesn't mean that it works for everyone.  But instead of making us ask, why not just share your scanning algorithm here for the people reading along?

Certainly, my solution uses a minuscule key space, to have that is the whole point of its assumptions.

Well, I retreat from arguing with an algorithm that is not implemented and postpone discussion of this topic until I see an actual implementation of what you describe or until you recognize the nature of the problem.

Regarding brute forcing the check sum: It does not really matter if it takes days or weeks. It is a precautionary measure to create a fake solution in addition to the real one. One only have to have it ready in case the plausible denial should be exercised, which is not a panned event in the near future. The harder the problem is the more plausible the denial. As said earlier passphrase input could be BIP39 encoded, this way any brute forced bit pattern will look equally plausible.

The algorithm is outlined in this thread and I open sourced the BOP Bitcoin implementation that includes this. I continue improving it free of charge for the community and even implemented this proposal there. Can I substantiate my claims better?

This all seems needlessly complex just to facilitate reasonable scan times. How does Electrum do it from just a seed?

Re. bloom filters: I think we may have a different idea of how to implement that. My suggestion:
SHA(SHA(privkey)) is used, instead of as a checksum, as a bloom filter element.
The user enters any other passwords they want to "allow", and the subsequent private key is generated. SHA(SHA(privkey2)) is also added to the bloom filter.

The user, then, can choose an arbitrary number of wallets to encode, with arbitrary passwords. This makes memorization easy, and they won't have to tell anyone "Oh yeah, my password is #!fb3$". They can just make it "jesus" or "1234" or whatever and but a few mBTC in that wallet. Fewer wallets means better password checking reliability, of course.

You do not need to get the details why this is hard, just recognize that the only reason we have key birth date is because it reduces scan time. This lesson was learned while importing ordinary (WIF) keys or re-scanning the wallet.

Now, developers who implement a HD scan will recognize that birth date is not sufficient for reasonable scan time, but at least a look ahead window is needed to master the task and that eventually birth date might be re-set if start-index is also there. Certainly these assumptions require that the Wallet software that uses HD complies with that. I do not see why this would be a problem why is it important to protect freedom of key sequence use. The point of HD is to avoid key reuse and loss through missing backups. Both can be achieved even if there are restrictions on what key to use next.

http://bitcoinism.blogspot.com/2014/01/business-accounting-and-bitcoin-privacy.html

This thread hasn't had a lot of activity recently. Here's what I'd say:

Bloom filter based on SHA(SHA(privkey)) is interesting. Allows for plausible deniability by encoding multiple wallets (different wallets are accessed by using a different password). If OP wants to change the spec to a simple bloom filter, I'd be in support of that. Proposed algorithm:

let m (number of bits in field) = 32
let n (number of passwords inserted) = 2 (assuming 1 "real" password and 1 "fake" password. This is only for optimization; the algorithm supports more)

To minimize the probability of a false collision, we want to use (m/n)ln(2) "hash functions" per password, so

let k (number of set bits per password) = (32/2)ln(2) = 11.09 = ~11

The probability of false positives is (1-e^(-kn/m))^k = (1-e^(-22/32))^11 =  ~.000458

Now, this is much larger than the chance of a false positive with just straight up SHA(SHA(privkey)), but the ability to add arbitrary passwords is pretty awesome. I would like to encourage discussion on this. I am honestly on the fence about this one; both are good solutions.

SHA(SHA(privkey)):
    pro: Very low chance of the user accidentally opening wallet with wrong password
    con: If compelled to decrypt wallet, there's no easy way to avoid actually giving them your real wallet info
Bloom filter:
    pro: Very easy to add a fake/secondary wallet (which you can actually put a little bit of money in) with any fake password you want. Plausible deniability.
    con: Higher chance of user incorrectly entering password.

Pseudocode:

English description:
Create a real password P1 and a "fake" password P2. The user can specify P2 if they want a "fake" password that will decrypt to a valid wallet. If the user doesn't want a "fake" password, P2 is to be randomly generated (so all users have a similar bloom filter). For each password P0...Pn:
    1. Decrypt the wallet and calculate the master secret key Kn
    2. Calculate SHA(SHA(Kn)) and call this Hn  (Hn[0:4] is currently used in the spec as a wallet checksum)
    3. For each of the first 11 bytes in Hn (let's call each byte Hn_i):
         a. Take the lowest 5 bits of Hn_i. Call this number (which ranges from 0 to 31) D
         b. Set the Dth bit of the bloom filter to 1


I think the existing date field is sufficient for optimization. It doubt it would be worth the effort to put more detail in the wallet spec. I would like to hear from gmaxwell and other client devs on this, since they're the authority on SPV optimization. Yes, we can optimize scan times by putting restrictions on the order of wallet generation, but I think that belongs in a separate BIP.

I guess 2 passwords is sufficient and the collision chance is significantly lower than the 4 password proposal I gave in this thread. However, I would like some more feedback from others before making this change.


Seems simple enough.


I posted a question to the bitcoin-dev mailing list asking for feedback on HD wallet import strategies. I haven't had any replies.

Bump. Would like to hear opinions on bloom filter.

Would it be possible to slightly modify the spec to allow for only non-scrypt hashing algorithms?

That would involve adding, say, SHA512 as a KDF, and getting rid of the fixed "scrypt.hash" in the encryption/decryption functions.

2 reasons this might be a good idea:
1. Some people trust SHA more than Scrypt
2. Scrypt is hard on embedded devices. SHA isn't.

As a KDF?  Can you provide some evidence for that?

I've never seen someone suggest that but perhaps they should.

In any case it absolutely should not use SHA512 as a KDF. SHA512 is a hash function, not a KDF, and it does not make an acceptably secure option.

If instead you were saying PBKDF2-SHA512, okay— but probably not worth the complexity to include more mandatory code.

The parameters selected should work on embedded devices. And with the support for delegation it doesn't matter quite as much if the selected parmeters didn't work on some device.

Agreed. The whole point of using Scrypt is to reduce the number of brute force attempts per second. SHA is very suitable for optimization whereas Scrypt less so.

gmaxwell, do you have any thoughts on changing the checksum to be a bloom filter so 2 passwords can be used (for plausible deniability)?

Granted, there isn't a whole lot of skepticism of scrypt, but people do recognize that scrypt is not as thoroughly vetted as, say, PBKDF2-SHA*. For those worried about, say, side channel attacks on memory usage, not using scrypt may be preferable.

Let's say we use the absolute minimum scrypt parameters for our embedded device. The most memory-efficient KDF function (KDF 0 in this spec) will use over 16MB of RAM, which is too high for many very small/cheap devices. Yes, we can delegate out the strong hashing, but this might not always be practical or wanted. Users may not have access to a stronger device (think of a very small, cheap, autonomous wallet generator device), or may not trust a stronger device enough to use it and possibly reduce their security to that of HMAC-SHA512.

Of course, there's also the non-offloadable scrypt hash later on. However, the parameters of 10,1,1 are so small that it's probably barely any better than PBKDF2-SHA512 for attack resistance.


Assume an external device must be used for strong hashing. If the external device is compromised, and the attacker has access to the encrypted wallet such that they can determine the salt, the security of the passphrase is limited to HMAC-SHA512 anyway.

If we allow for, say, PBKDF2-SHA512 to be used for strongH generation, it can be run on extremely memory-contrained devices. I also really doubt that the second, non-offloadable scrypt with parameters 10,1,1 is much better than PBKDF2-SHA512.

That one is only done for key stretching and the hypothetical "what if the 3rd party gets a hold of your wallet" situation. It's not the main protection against brute-force attacks.


Here's an interesting thread on PBKDF2: http://stackoverflow.com/questions/4433216/password-encryption-pbkdf2-using-sha512-x-1000-vs-bcrypt

Look at that table.

I'd rather introduce an extra Scrypt option that's a bit weaker than 14,8,8 over introducing PBKDF2-SHA512.


Additionally, about the bloom filtering, I think we're going to have a bit of an issue with that one. The checksum as it currently exists is part of the salt used when generating preH. We won't be able to do that if we introduce the bloom filter. This will lower the entropy of the salt considerably.

The Mycelium Wallet on Android already uses scrypt for its password-protected backups, and for BIP38. On very old devices we have trouble running this, so we will have to introduce a "weaker" version for devices with < 20MB per process.

For a future standard for HD wallet, non-hardcoded scrypt parameters would be preferable, depending on password length and device speed and usage frequency, and usecases (offline device) the desired parameters could be different. I like scrypt, though. If it turns out that scrypt is broken, there should be a V2 of this spec, with a new hashing algo, or the ability to specify the KDF algo.

Some comments on what i have read so far:

1) direct encoding of scrypt parameters would be preferable as direct values as opposed to versioned parameter lists (up& downwards compatible)

2) The generation date is not really that important. Maybe other wallets need it but out software would ignore it with the current scheme, but i see how it potentially speeds up initial syncing for a fresh backup. but thinking long-term it will not help much, since the time between backup and restore will always increase.

3) If the KDF is offloadable, make sure that the "non-offloadable" part does not strictly require a scrypt implementation, so that it may run on devices with very limited resources. (think future revisions of embedded devices)

4) We absolutely want the checksum with bloom filtering in future, so that the user may specify additional passwords/pins for multiple identities. Our non-trivial job will be to design a wallet format that preserves the deniability with the stored metadata.
again, the chosen parameters should not be hard-coded, but i can imagine that default values like 4 bytes with 6 hash functions (optimum for N=4, p=0.02) would make sense.
the question is, do we want to push the plausible deniability so far, as to obfuscate the fact how many additional passwords possibly exists? if so, we would hit a limit after adding 4 passwords,

5) what i do not fully understand, is how bloom filtering impacts the preH entropy. can you elaborate on this?

We've got 32 possible KDFs. Surely that's enough to have a Scrypt parameter set for every hardware platform that wants to implement this? Additionally, I want to add support for catena in the future as it fixes some issues found in Scrypt. See: https://github.com/cforler/catena


It uses Scrypt 10,1,1 purely for the key stretching. I didn't want to muck about with a fixed output length hash function, because I potentially need more bytes than SHA512 currently provides.


I'm right there with you, but I also want to preserve the entropy of preH's salt.



Currently the checksum is a subsection of the hash of the HD wallet master private key and is used in the salt.

Since for the second password we basically don't know what the key is until we decrypt for the first time, we can't change the bloom.

We'd either have to remove the checksum from the salt (losing entropy) or change the input of the bloom (not being based on the HD wallet master private key).

1. I'm aware of this. However, you haven't addressed the fact that, if the device processing the delegated "strong" hash is compromised, the security of the wallet is reduced to that of HMAC-SHA512, which is significantly lower than *either* Scrypt of PBKDF2-SHA512. There are two possibilities here:

     a.) No PBKDF2-SHA512. Memory constrained devices are *forced* to use external device to calculate strong hash. This introduces a huge new attack surface, because if the external device is compromised, only a single HMAC-SHA512 stands in the way.

     b.) We allow PBKDF2-SHA512. Memory constrained devices at least have the *option* of stretching the key on their own. Remember, no one is forced to use PBKDF2-SHA512. Attack surface is significantly diminished.

2. Yes, Scrypt is effective, but clearly so is PBKDF2. I'm not suggesting replacing Scrypt; merely allowing people not to use it.

3. Why not both? There are additional advantages to having PBKDF2-SHA512 as well as Scrypt. Beyond the fact that it's friendlier for memory-constrained devices, it could also simplify code (It would be possible to have an embedded device with only SHA2-family hashes, which I know are easily implemented on even very weak 8-bit microcontrollers), and would allow people who don't trust Scrypt yet to use only NIST-certified and thoroughly time-vetted hash algorithms.

4. This is true. Something to consider. I have a suggestion at the end of this post.


Absolutely agree. I think having PBKDF2-SHA512 as an option (not the only option!) would nicely address 1, 3, and your non-enumerated concerns. In case Scrypt is broken (or more likely, is vulnerable to memory/timing side channel attacks), there should be no *mandatory* usage of Scrypt; it should simply be one of the selectable KDFs. I suggest replacing the 10,1,1 Scrypt with PBKDF2-SHA512. StrongH is where all the big key stretching comes from anyway, so we might as well limit our usage of Scrypt to that.

Re. 5), the problem is this. The bloom filter is a function of (salt, password, encrypted data). Therefore, we can't use the bloom filter in the salt, because then we would get that the bloom filter is a function of ((version, date, bloom filter), password, encrypted data). It's impossible to have the bloom filter be a function of itself. I have an alternate suggestion at the end of this post.


1. Indeed. If we have enough KDF codes for Scrypt and Catena, don't we have enough KDF codes for one or two PBKDF2-SHA512s?

2. PBKDF2-SHA512 provides an arbitrary number of output bytes! It would be a *very* simple addition to the spec, because it does basically the exact same thing as Scrypt.

3. Perhaps we can do both.


Summary:

1. There isn't really any reason to not at least *allow* PBKDF2-SHA512 as one of the available KDFs.

2. It would be easier for embedded and mobile devices if Scrypt wasn't mandatory.

3. The Scrypt with parameters 10,1,1 might as well be replaced with PBKDF2-SHA512.

4. The bloom filter as I described it earlier would negatively impact salt entropy. It would be best if we could re-work this.


Alternate bloom filter proposal:
It's acceptable to use strongH without a salt here, because we're only revealing 10 or fewer bits of the password hash. We're not revealing enough information about the password to do any damage. This means the bloom filter is a function of *both* passwords (one of which may be random), so it still adds useful entropy to the salt.

How many iterations do you suggest if we were to add this as one of the KDFs?


Very well, I'll see if I can rework it to use PBKDF2-SHA512 for the preH and postH sorry, I meant for H.


This means doing the strong hash multiple times and not being able to outsource it. I think it's fine to use something like a double SHA256 here. It's not going to leak anything useful anyway.

1. We have a lot of KDF codes to spare. I would recommend 2 or even 3 PBKDF2-HMAC-SHA512 versions (just like we have with Scrypt). We are not too focused on performance, so these are my suggested iteration counts:

65536 (2^16). More than most existing implementations use for the faster PBKDF2-HMAC-SHA256. Acceptable performance on very resource-constrained embedded systems.

2097152 (2^21). Very heavy. In Python, takes 30+seconds to do this many rounds of HMAC-SHA512. Probably takes at least a few seconds in well-optimized C.

And, if we want a really heavy option (although honestly, I think the Scrypt options are probably fine for this), we can also do

67108864 (2^26). For the very paranoid.

2. Great! Like I said, it should be pretty much a drop-in to the list of KDFs. It would work pretty much exactly the same. What do you think about using it for the final key-stretch (the Scrypt with parameters 10,1,1)? If we got rid of the 10,1,1 Scrypt or replaced it with PBKDF2-HMAC-SHA512, people could stick to explicitly NIST-approved memory-constant crypto. Good for the paranoid and good for embedded developers.

3. I agree. Revised code:

Actually, come to think of it, this gives a brute-force attack a big optimization. They only have to test against the bloom filter now. There's no need to do the strong hash. So this has to be hashed using the strong hash.

Actually, it makes you wonder whether or not the key needs to be encrypted with a strong KDF at all at that point. If the strong KDF is used to generate the bloom filter, then the hash used to encrypt is going to be irrelevant, right? As an attacker, you're testing to see if you generated a password that passes the bloom filter and you move on from there, so that's the step that should be costly.

So that means that this is the step that has to be outsourced. And that means that we need a good salt for this step. So we're right back where we started.

OK, we have two options here:

1. Use strongH(password) to calculate bloom filter. Slow, but secure. Unfortunately, this can not be delegated. So perhaps a no-go.

2. Use sha(password) to calculate bloom filter. Fast, but reduces the password search space by up to eleven-ish bits (I think). I thought you were saying you were OK with this. However, I guess eleven-ish bits is a little high for me.

Alternate proposed solution:


This still allows the attacker to reduce the search space by something like 2^11, but at the expense of doing 2^16 extra rounds of PBKDF2-HMAC-SHA512 per checked password.

Even the lowest-end device can handle this without delegation.

There's a third option. Basically, if we want the same security as we have right now, the bloom has to be based on the full decryption pass and thus can't be part of the salt.

So we need to add some extra bytes for salt entropy. Currently, the prefix is 3 bytes long. I'll have to check, but if we add 1 or 2 extra bytes, it'll become 2 bytes again, giving us either 11 or 19 bits of extra entropy (+ 5 bits for KDF selection).

I'll try and have a look at that tomorrow.

Ok, I've done some searching and unfortunately, there are no 2 byte prefixes for all 3 possible lengths if we increase everything by 1 or 2 bytes. But I found a way to make it work if we increase by 1/2/3 bytes for the 16/32/64 byte root keys respectively. Not ideal, but at least there's a pattern.

I've also changed the prefix from 'ws' and 'WS' to 'rk' and 'RK', something I wanted to do ever since the term 'root key' was introduced.

The unencrypted lengths stay the same, but the prefix length is reduced to 2 bytes, giving us one extra byte.

Actually, 1 byte less works for the unencrypted variant. Updated the table.

Length	Prefix	Min	Max	Count
24	RK	0x28C1	0x28C6	6
40	RK	0x4AC5	0x4AD1	13
72	RK	0xFBB3	0xFBDE	44
26	rk	0xF83F	0xF853	21
43	rk	0x6731	0x6739	9
76	rk	0x4EB4	0x4EB9	6

So the unencrypted format becomes something like:

prefix(2 bytes) + date(2 bytes) + checksum(4 bytes) + root key(16/32/64 bytes)


The encrypted format becomes something like:

prefix(2 bytes) + date(2 bytes) + KDF(5 bits) + entropy(11/19/27 bits) + bloom filter(4 bytes) + encrypted root key(16/32/64 bytes)


Thoughts?

This proposal is next up for development in my bip32utils library.  Do you have any indication yet what a BIP number might be for it, and do you have a proposed short name for it?  Otherwise, I'll call it the "riplin export format" :)

No BIP number as of yet. I'll have to ask the list again, once we've finished the bloom filter stuff.

I'd say call it HD wallet root key. :)

I'm down for increasing the length a bit with a random salt. I don't have any strong opinions on how this is done, but it sounds good to me.

That would also mean we could go back to my original idea about sha(sha(privkey)) being used as a bloom filter element.

Yes. I'm making the change right now. I'm currently updating the test vectors and adding new ones, plus second password.

Updated the spec.

Changed prefix to 2 bytes, 'RK' and 'rk' for clear version and encrypted version respectively.
Added entropy field to encrypted version, moved KDF field from prefix into entropy field.
Changed computation of H to use PBKDF2-HMAC-SHA512 instead of Scrypt.
Changed checksum field to bloom field in encrypted version. Now supports 2 passwords.

Updated reference implementation. Now supports newest spec, as well as secondary "fake" passwords.

https://github.com/wyager/Encrypted-HD-wallet

Please excuse my ignorance, but does this spec allow for the "intermediate code" that BIP38 uses?  Ie. would it be possible for a third party to generate you a passphrase-protected HD wallet, with them having no knowledge of the passphrase?

The question might already be answered in the spec but I couldn't spot it.

Thanks

No. Due to how BIP32 works, that's not possible. The initial key in BIP32 is not derived using ECC, but is generated using HMAC-SHA512. So the same trick as used in BIP38 is not possible.

Updated wording of parts of the spec.

Suggestion: Replace all instances of bare HMAC-SHA512 with PBKDF2-HMAC-SHA512, like so.


A tiny bit of extra computational time (a few seconds on a slow ARM, a few milliseconds on a PC; small compared to the time spent on strongH), but offers a lot of extra protection in the event preH is compromised. Also makes the code a bit more consistent.

Changed the preH and postH calculation, updated the test vectors.

Snazzy approach to denyablity. I certantly like it better than what some other people have done.

Do you have any number on the false positive rate for the no-specified second key?  How does it compare to "two 16 bit check values, ordered randomly"? Presumably its better when there is no second key or where you've done some brute force search to find two that share their bloom bits?

Is there an advantage I'm not seeing to this approach instead of

preH=PBKDF2-HMAC-SHA512(salt,passphrase)
strongH=KDF(preH[first 256 bits])
H = HMAC-SHA512(preH,strongH)

?

This construction seems simpler and faster—or, more importantly, would allow moving the computation budget from postH into preH where it could add more strength against dictionary attack by the delegatee.

The false positive rate with two keys in the filter is about 1 in 40,000. A bit better than the false positive rate of two 16-bit filters, which is about 1 in 33,000 (if my reasoning is correct).

You *could* avoid inserting a second key, but we required a second key in the spec so that all users have plausible deniability. E.g. "We see there are more than 11 bits in your bloom filter. A user with nothing to hide would have no second password, so you must be hiding something!"


Even in the way we have it set up now, if an attacker can get their hands on strongH as well as the encrypted wallet, they can skip the first 8192 rounds of PBKDF2, hence the last 2048 rounds. Basically just extra safety against a dictionary attack on both strongH and the wallet.

I just figured it was more likely for a compromised delegatee to leak preH/postH and not the encrypted wallet (since the delegatee doesn't necessarily know encrypted wallet), so I suggested protecting more against leaking preH/postH than against leaking preH/postH *and* the encrypted wallet.

Sounds good. Yes, it would be ~1/65536*2.  I was about to suggest something where you need N of M of even smaller checksums and then realized that the bloom filter is basically the limit case of that.   If you don't want to support more than two values, you could specify having more than 11 extra 1s is also regarded as a false match.   E.g. if this key only sets 8 ones and there are 20 set in the filter (including these) then then also regard it as a false positive (because there is no possible single second value which would result in more than 11 bits being set).

The structure I gave has the same property.  :)   If you have StrongH and the encrypted wallet you still need the whole output of the initial KDF, which means you need to know or guess the password and grind the initial KDF.

Good thinking. However, H must be PBKDF2-HMAC-SHA512 with >= 1 round, so that we can produce an H of arbitrary length. I'm down for this change.

I'll send this proposal off to riplin:

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)


I've generated the relevant test vectors as well.

Updated.

I did a simple empirical test of the false positive rate, mostly to check to see how much rejecting results with too many bits set improved things, and because I'm too lazy to check the math. I found much lower performance than expected:


#include <stdio.h>
#include <stdint.h>
#include <stdlib.h> /*random()*/
#include <assert.h>

uint32_t toflt(uint64_t x)
{
  int i;
  uint32_t result=0;
  for(i=0;i<11;i++)
  {
    result |= 1U<<(x&31);
    x>>=5;
  }
  return result;
}

int chkflt(uint32_t flt, uint64_t x)
{
  int i;
  uint32_t flt2=0;
  int result=1;
  for(i=0;i<11;i++)
  {
    if (!((1U<<(x&31))&flt)){
      result=0;
      break;
    }
    flt2 |= 1U<<(x&31);
    x>>=5;
  }
  if (__builtin_popcount(flt&(~flt2))>11)return 0;
  return result;
}

int main(int argc, char **argv)
{
  int i;
  uint64_t total=0;
  uint64_t fp=0;
  (void)argc;
  (void)argv;
  assert(RAND_MAX == 2147483647);
  for(i=0;i<9973;i++)
  {
    int j;
    uint64_t x;
    uint64_t y;
    uint32_t flt;
    x = ((uint64_t)random()<<24)^random();
    y = ((uint64_t)random()<<24)^random();
    flt = toflt(x)|toflt(y);
    for(j=0;j<1021;j++){
      uint64_t x2;
      int match;
      x2 = ((uint64_t)random()<<24)^random();
      match = chkflt(flt,x2);
      if (x2==x || x2==y){
        if(!match){
          printf("Something bad happened.\n");
          exit(1);
        } else {
          continue;
        }
      }
      total++;
      fp+=match;
    }
  }
  printf("%llu false positives out of %llu tests.\n",(long long unsigned)fp,(long long unsigned)total);
  return 0;
}


Which yields 7508 false positives out of 10182433 tests or 8148 with the too-many test disabled.

I think thats an unacceptably high failure rate.  The one of two 16 bit check values approach gets me 289 with the same sequence. (I could argue that the 16 bit check is too lossy too, considering that someone might get the password wrong, use the result to generate public keys, then later be able to recover the funds— but I think on the balance the denyability feature is pretty good.)

What am I screwing up here? A copy using /dev/urandom instead of random() gets the same results, so it's not just random() having some odd correlations or a low period.

Agreed. The bloom filter does not perform as well as expected.

The two 16-bit hashes is fine by me. It would remove a bit of functionality, but 99% of use cases probably just want two passwords.

The bloom basically gives us 2 things, an easy way to detect typo's and in the event of a brute-force attack, it yields a significant number of false positives which all require a full scan of the blockchain, which I thought was a nice trade-off for the lower number of entropy bits.

If that first feature is somehow not effective enough, we could either tweak the bloom arguments or move to the 16 bit method that gmaxwell proposed.

If you really want more than two, you could search for either a seed or set of passwords (if the seed is fixed by prior use, since password searching is strictly slower) resulting in check value sharing.

I'm not sure how valuable the blockchain scan is, since what you'd do there is extract all addresses seen in the blockchain into a bloom filter ... one which fits in L3 cache can have a low enough false positive rate to be effective.

I think the false positive rate of the bloom filter is a bit too high for comfort.

Unfortunately, it's already fully optimized for two inserted elements.

The 16-bit filters will offer better password checking, and they will also have a high enough false positive rate to frustrate attackers.

So, is this proposal stable enough now to turn into a formal BIP?  Is this in progress already? I would like to add a second implementation of this, as part of my bip32utils package.

Finally, would it be too much of a stretch to be able to use this encoding as way to export an extended private key from inside the hierarchy, instead of at the root?  It would fit in the "64 byte root key" encoding.

Is anyone still working on this?