User:Casascius/Base58Check-encoded objects proposal

This page describes a BIP (Bitcoin Improvement Proposal). Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

  BIP: Draft
  Title: Basic security features and standardization for Bitcoin private keys
  Author: Mike Caldwell <casascius@mc2cs.com>
  Status: Draft
  Type: Standards Track
  Created: 2012-08-02

Abstract

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.

Specification

• 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

Present specification

• 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

Rationale

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.

Proposed specification

• 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 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.

Proposed specification

• 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.

Proposed specification

• 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