User:Casascius/Base58Check-encoded objects proposal
This page describes a BIP (Bitcoin Improvement Proposal).
BIP: Draft Title: Basic security features and standardization for Bitcoin private keys Author: Mike Caldwell <firstname.lastname@example.org> Status: Draft Type: Standards Track Created: 2012-08-02
- 1 Abstract
- 2 History
- 3 Overview
- 4 Proposal for redefinition of the "version byte"
- 5 Proposal to standardize the Sipa-format key
- 6 Proposal to standardize the private key format indicating compression
- 7 Proposed encoding for a passphrase-protected private key
- 8 Proposed specification for a multi-part key using EC multiplication
- 9 Proposed specification for a RAID-like recovery record for a multi-part key
With the increasing popularity of the use of paper wallets as offline Bitcoin storage, there is a growing demand for ways to make that offline storage more secure, for various reasons of the user's choice. Currently, there exists no straightforward way to encrypt a paper Bitcoin wallet.
There is also growing demand for paper wallets that can be split and saved in redundant geographical locations or with different trusted parties, or which are generated in individual parts by multiple machines so that no single machine ever has access to the entire private key prior to redemption. This proposal introduces a standard based on elliptic curve multiplication where Base58Check-encoded strings and/or QR codes can be used to represent parts of a multi-part key. This proposal also introduces a simple standard format for denoting a RAID-like recovery record, so that a multi-part key can be distributed and redeemed in a fashion that tolerates the loss of any one part of the key.
This proposal also seeks to define unique prefixes on Base58Check-encoded strings so that they convey useful visual information to a user, and requests that other developers maintain awareness of the string prefixes and maximize their usefulness to the user.
Proposal for redefinition of the "version byte"
Before going into proposals for different formats, I want to first make a proposal that will ensure that the formats I'm about to introduce remain easy for users to understand and use. I want the prefix (the first one or two characters of each Base58Check-encoded string) to be learnable and recognizable by users, and for them to have consistent meanings, the same way we know that a Bitcoin address always starts with a 1, and something that doesn't start with a 1 isn't a Bitcoin address.
Currently, all objects in Bitcoin when encoded in Base58Check have a "version byte". For example, a Bitcoin address has a byte of 0. A private key has a byte of 0x80. Derivative "altcoins" follow the scheme as well, and therefore their addresses and other objects are easily identified programmatically.
As a result of this practice, all Base58encoded objects tend to have similar prefixes that have come to be used to identify the object by users. A Bitcoin address always starts with a '1', a private key always starts with a '5'. Testnet coins and altcoin addresses can similarly be identified visually by their prefix.
I propose that the "numberspace" in this version byte as used by implementers yield its importance to the "prefixspace" as seen by users. It is much more important that users be able to grasp Bitcoin concepts than it is for us to assign "version" bytes using some sort of sequential orthodoxy.
I propose that this byte be redefined as an "object identifier prefix". Object types should be recognized by two attributes: this prefix, as well as the payload length. Because the payload cannot be arbitrarily shortened or lengthened accidentally by users (the checksum will catch omissions or insertions), the payload length is a safe attribute for reliable recognition of objects.
This keeps things consistent with the way Bitcoin is implemented now. For example, a 21-byte Base58Check-encoded string where the first byte is 0x00 is safely assumed to be a Bitcoin address. Two elements are reliably consistent: the 0x00 byte, and the 21-byte total length.
For maximum control over the resulting prefix that will be seen by the user, I propose that the object identifier prefix can be specified either as one byte, or as more than one byte, if needed. The criteria for deciding whether any given Base58Check string is an object of a certain type is both an exact match on the length, as well as an exact match on all the prefix bytes required to specify the object.
Proposal to standardize the Sipa-format key
- User story: As a Bitcoin user who uses paper wallets or who imports/exports private keys, I don't want to have to worry about different applications that use different formats to represent private keys. I don't want to have to learn about multiple proprietary private key formats just to know which format I should use. I would like the private key format to be just as simple and universal as the Bitcoin address format.
Indicates an uncompressed private key. Widely accepted as "wallet import format", "sipa format".
No changes are proposed to this specification. Rather, it is proposed that this format be considered the standard way of representing a regular uncompressed Bitcoin private key any time there is a need to present one to the user. Specifically, this contemplates discouraging and/or deprecating export and display of any of the following formats (but they should all be recognized as valid input)
- Base64 (except when dealing with the private key material as raw binary data)
- Hexadecimal (except when dealing with the private key material as raw binary data)
- The "internal base58 format" used by Blockchain.info (which is 32 raw bytes encoded in base58 with no prefix or checksum)
- Any other non-standard or proprietary formats that do not provide any features beyond what is present in the Sipa-format key.
Minikeys should similarly be accepted as import whenever possible, but not displayed. Applications should always display and export the standard format key, except where displaying or exporting a minikey is explicitly desired as a feature.
- Version byte (object identifier prefix): 0x80
- Payload bytes (beyond prefix): 32
- How the user sees it: Always 51 characters beginning with '5' (specifically: 5H, 5J, or 5K)
- Range in base58 encoding:
- Lowest possible value: 5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAbuatmU
- Highest possible value: 5Km2kuu7vtFDPpxywn4u3NLu8iSdrqhxWT8tUKjeEXs2f9yxoWz
Proposal to standardize the private key format indicating compression
- Version byte: 0x80
- Payload bytes (beyond prefix): 33 (32 for the key, plus the constant 0x01)
- How the user sees it: Always 52 characters, beginning with K or L
- Lowest possible value: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73Nd2Mcv1
- Highest possible value: L5oLkpV3aqBjhki6LmvChTCq73v9gyymzzMpBbhDLjDpKCuAXpsi
- User story: As a Bitcoin user who uses paper wallets or who imports/exports private keys, I don't want to have to learn the difference between private keys that start with '5' and ones that start with something else, if there are no differences that pertain to me as a user or the way I use the key or what I can do with it.
Whether we like it or not, many users (particularly power users) will see base58 encoded objects, such as on paper wallets.
Since the distinction of compressed/uncompressed is of little practical difference to the user, and the question "why is this one 5 and that one K/L" an unnecessary burden that disregards simplicity, I propose a different encoding that both preserves the '5' and keeps a visual distinction there (in the second character) for those who can make use of it.
Backward compatibility with the current specification can be easily maintained under this proposal by always accepting the existing compressed private key format as input, but applications should only output strings in the proposed format.
- Version byte (object identifier prefix): 0x82
- Payload bytes (beyond prefix): 32
- How the user sees it: Always 51 characters beginning with '5' (specifically: 5M, 5N, or 5P)
- Range in base58 encoding:
- Lowest possible value: 5Mhmw9M9nJvSXeYgrMgtzgwg3q4MWYYqJ6CziURYEBsR9t6VP82
- Highest possible value: 5PeX7NoBdjbffU8PkwJtx1YSxwg5AFPi5jH6xd7SDqsoeMcxpoG
- Note: By using 0x82 instead of 0x81 we ensure the second character always visually divulges the compressed status. If we used 0x81, then the prefix '5K' could belong to either, and would be ambiguous.
Proposed encoding for a passphrase-protected private key
- User story: As a Bitcoin user who uses paper wallets, I would like the ability to add encryption, so that my Bitcoin paper storage can be two factor: something I have plus something I know.
This proposal contemplates existence of a private key that requires a decryption passphrase before it can be used.
I propose having the Base58Check-encoded string start with a '6'. The number '6' is intended to represent, from the perspective of the user, "a private key that needs something else to be usable" - an umbrella definition that could include keys participating in multisig transactions. The second character ought to give a hint as to what is needed, and for an AES256-encoded key based on the SHA256 hash of a passphrase, I propose the lowercase letter p.
I propose the string having an optional 14 bits of password typo resistance. That is, a 14-bit checksum of the password may be added so that the vast majority of password typos can be detected and reported to the user, rather than inadvertently accepted as correct, which will simply yield the wrong private key and frustrate the user. This checksum is optional, and a bit flag is defined for the purpose of disabling it.
The choice of a low-bitcount checksum is intended to reduce its usefulness to someone attempting to crack the password.
To encrypt the key requires the AES256Encrypt function, which takes a 16-byte input and a 32-byte key and yields a 16-byte output. The SHA256 hash of the passphrase is used as the 32-bit key given to the AES functions.
- firsthalf: AES256Encrypt(bitcoinprivkey[0...15], SHA256(passphrase))
- lasthalf: AES256Encrypt(bitcoinprivkey[16...31] xor firsthalf[0...15], SHA256(passphrase))
Decryption is the reverse:
- firsthalf: AES256Decrypt(ciphertext[0...15], SHA256(passphrase))
- lasthalf: AES256Decrypt(ciphertext[16...31], SHA256(passphrase)) xor firsthalf[0...15]
To keep the size of the encrypted key down, no initialization vectors are used.
- Object identifier prefix: 0x0205
- How the user sees it: 54 characters always starting with '6p'
- Count of payload bytes (beyond prefix): 34
- 2 bytes: compressed flag and passphrase typo resistance (1 bit: passphrase enable/disable, 14 bits: passphrase checksum, 1 bit: compressed flag)
- 16 bytes: firsthalf: AES256Encrypt(bitcoinprivkey[0...15], SHA256(passphrase))
- 16 bytes: lasthalf: AES256Encrypt(bitcoinprivkey[16...31] xor firsthalf, SHA256(passphrase))
- Range in base58check encoding:
- Minimum value: 6pZbbCzeNu7567y9swhRL8zC4yXioQc6oaUmwPMof6zvChFcMrTmMp
- Maximum value: 6ptXqrvUjVYbnPvXPrC2S4tRVvAFdXBKDUC7K96C9ukAKogUFQynhy
Passphrase typo resistance bytes: The most significant bit is the enable(0)/disable(1) bit, the next 14 bits hold the passphrase checksum. The checksum is defined as SHA256(correct passphrase + "?")[0...1] & 0x7FFE. The least significant bit is 0 for an uncompressed key, and 1 for a compressed key.
If the passphrase is disabled, the passphrase checksum bits MUST be 0 (so the two bytes will be 0x8000 or 0x8001).
The valid range of the passphrase typo resistance bytes are 0x0000 thru 0x8001. Values above 0x8001 are excluded from the definition of keys valid for this proposal. Note that if the value were to be above 0xabb9, the prefix "6p" is lost and becomes "6q".
- Passphrase: "VIRES IN NUMERIS"
- Sample Bitcoin private key to be encrypted: 5Ki8KQ65ihzzoex9BjarbMjUATaFYMmWZ4eLmBnjj9fdhKqm3VR / F967E2BEEFCEC703A4737E42124D7BB3 34A34CC345446B9B163576B7C7A36266
- SHA256("VIRES IN NUMERIS"): 8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD
- AES256Encrypt(F967E2BEEFCEC703A4737E42124D7BB3,8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD) = b5dde5769a8b031139cdcc54f2f5f98b
- 34A34CC345446B9B163576B7C7A36266 xor b5dde5769a8b031139cdcc54f2f5f98b = 817EA9B5DFCF688A2FF8BAE335569BED
- AES256Encrypt(817EA9B5DFCF688A2FF8BAE335569BED,8967A8562255672471ACB316E705593454040FA41E3883AD5A8C3576E5DC03DD) = 8b899125ebf86b82a54fb898077188f6
- First 16 bits of SHA256("VIRES IN NUMERIS?"): B2C4, and 0x7ffe = 0x32c4
- What to Base58Check encode: 0205 32C4 b5dde5769a8b031139cdcc54f2f5f98b 8b899125ebf86b82a54fb898077188f6
- Resulting encrypted private key: 6ph7B7aqL4aBkQY2sJs8MZdJ1MwjEJSgLDiRoBrqAXsAbjmdQecEi3
Proposed specification for a multi-part key using EC multiplication
- User story: As a Bitcoin user who uses paper wallets or who imports/exports private keys, I would like the ability to secure my private key by separating it into parts and keeping the parts in more than one geographic location, or entrusted to more than one person.
- User story 2: As a Bitcoin user who uses paper wallets, I don't trust any single computer to generate my keys, as my computer could be infected by malware or under the control of someone else. I would like to generate paper wallets using a method that involves two or more separate computers (and/or smartphone), so I can benefit from the much lower likelihood that a single attacker has control over all of the computers being used, and so I can enjoy security even if an attacker is able to get access to some of my key material.
I propose a private key format that can self-specify that it is a single part of a multi-part key, and which can specify how many other parts are needed to reconstitute the complete key. Under this proposal, each part is a factor, and the key is reconstituted using elliptic curve multiplication.
The proposal contemplates a four-bit field that specifies how many parts (up to 15) are needed to complete the key.
The proposal also contemplates an 11-bit field that is used for matching purposes - so the individual parts can be identified as likely belonging to each other, and that they form the correct address when put together. This allows a user interface to know to ask for other parts, to know how many parts to ask for, to reject parts that don't belong (e.g. they belong to a different key), and to confirm that all parts are likely present when provided.
- Object identifier prefix: 0x0211
- How the user sees it: 54 characters always starting with the prefix '6x'
- Count of payload bytes (beyond the prefix): 34
- 2 bytes: bit-mapped field
- 4 most significant bits: number of total parts required, minus two. A value of 0-13 here allows for 2-15 parts. Values above 13 break the '6x' prefix and are disallowed.
- 11 bits: checksum
- 1 least significant bit: compressed private key flag (0=uncompressed 1=compressed)
- 32 bytes: factor representing partial private key
The checksum taken on the resulting Bitcoin address is defined as SHA256(BitcoinAddress[0...1]) & 0x0FFE, where BitcoinAddress is a base58check-encoded string representation of the address that should result when all parts are reconstituted. Taking the SHA256 of the Bitcoin address is chosen as preferable over taking something directly from the hash160 of the bitcoin address, to reduce the possibility that the common practice of generating "vanity addresses" does not result in an increased likelihood of collisions on the checksum field.
Proposed specification for a RAID-like recovery record for a multi-part key
- User story: As a Bitcoin user who uses paper wallets or who imports/exports private keys in parts, I would like the ability to secure my multi-part keys against the potential loss or destruction of one of the parts.
I propose a format that isn't itself a key or key part: rather, it is a simple parity-based recovery record for a multi-part private key, that can be used in place of any one missing part. It functions similar to RAID-5 as used in disk technology.
This format looks similar to a single part of a multi-part key, including the bitmapped fields denoting the number of parts and the checksum of the Bitcoin address, except for a different object identifier prefix. The data payload is a simple XOR sum of the payloads in all of the parts being protected. With that sum, any one missing part can be completely recalculated using standard parity math.
For the purpose of counting "parts" for the "total parts required" field, the recovery record is optional and is not considered a part. If a 3-part key is created along with a recovery record (so there are 4 base58check-encoded strings, recovery possible with any three), then all of the records (including the recovery record) shall indicate the key has three parts. Including this in the recovery record allows a user interface to be aware of what it expects if the recovery record is provided first: for example, a user interface, upon being presented a recovery record for a 3-part key, will know to ask for two more parts. It also facilitates rejection of parts that don't belong to the key being recovered.
Capability for only one recovery record per multi-part set is proposed here, for the sake of simplicity, and the fact that XOR and SHA256 are widely understood and available on all relevant platforms. More elaborate schemes (such as two or more recovery records using syndromes similar to use in RAID-6) are certainly possible, but avoided in this proposal to maximize the developer audience likely to be able to implement the proposal completely.
- Object identifier prefix: 0x0208
- How the user sees it: 54 characters always starting with the prefix '6r'
- Count of payload bytes (beyond the prefix): 34
- 2 bytes: bit-mapped field, which must be identical to the corresponding 2-byte field in the partial keys to which the recovery record belongs (range of valid values: 0...0x8001)
- 32 bytes: result of XORing the 32 bytes of all of the partial keys