A Bitcoin Improvement Proposal, or "BIP" is a design document that, through a process of comment, review and community consensus can become an influential standard for the improvement of the bitcoin system. This appendix contains a number of selected BIPs that are important in the history and future of bitcoin. The original BIPs can be found on github at https://github.com/bitcoin/bips, which is considered the authoritative source for BIPs. They are included here as a handy reference.
BIP: 1 Title: BIP Purpose and Guidelines Status: Accepted Type: Standards Track Created: 2011-08-19
BIP stands for Bitcoin Improvement Proposal. A BIP is a design document providing information to the Bitcoin community, or describing a new feature for Bitcoin or its processes or environment. The BIP should provide a concise technical specification of the feature and a rationale for the feature.
We intend BIPs to be the primary mechanisms for proposing new features, for collecting community input on an issue, and for documenting the design decisions that have gone into Bitcoin. The BIP author is responsible for building consensus within the community and documenting dissenting opinions.
Because the BIPs are maintained as text files in a versioned repository, their revision history is the historical record of the feature proposal .
There are three kinds of BIP:
-
A Standards Track BIP describes any change that affects most or all Bitcoin implementations, such as a change to the network protocol, a change in block or transaction validity rules, or any change or addition that affects the interoperability of applications using Bitcoin.
-
An Informational BIP describes a Bitcoin design issue, or provides general guidelines or information to the Bitcoin community, but does not propose a new feature. Informational BIPs do not necessarily represent a Bitcoin community consensus or recommendation, so users and implementors are free to ignore Informational BIPs or follow their advice.
-
A Process BIP describes a process surrounding Bitcoin, or proposes a change to (or an event in) a process. Process BIPs are like Standards Track BIPs but apply to areas other than the Bitcoin protocol itself. They may propose an implementation, but not to Bitcoin’s codebase; they often require community consensus; unlike Informational BIPs, they are more than recommendations, and users are typically not free to ignore them. Examples include procedures, guidelines, changes to the decision-making process, and changes to the tools or environment used in Bitcoin development. Any meta-BIP is also considered a Process BIP.
The BIP editors assign BIP numbers and change their status. Please send all BIP-related email to the BIP editor, which is listed under BIP Editors below. Also see BIP Editor Responsibilities & Workflow.
The BIP process begins with a new idea for Bitcoin. It is highly recommended that a single BIP contain a single key proposal or new idea. Small enhancements or patches often don’t need a BIP and can be injected into the Bitcoin development work flow with a patch submission to the Bitcoin issue tracker. The more focused the BIP, the more successful it tends to be. The BIP editor reserves the right to reject BIP proposals if they appear too unfocused or too broad. If in doubt, split your BIP into several well-focused ones.
Each BIP must have a champion — someone who writes the BIP using the style and format described below, shepherds the discussions in the appropriate forums, and attempts to build community consensus around the idea. The BIP champion (a.k.a. Author) should first attempt to ascertain whether the idea is BIP-able. Posting to the [email protected] mailing list (and maybe the Development&Technical Discussion forum) is the best way to go about this.
Vetting an idea publicly before going as far as writing a BIP is meant to save the potential author time. Many ideas have been brought forward for changing Bitcoin that have been rejected for various reasons. Asking the Bitcoin community first if an idea is original helps prevent too much time being spent on something that is guaranteed to be rejected based on prior discussions (searching the internet does not always do the trick). It also helps to make sure the idea is applicable to the entire community and not just the author. Just because an idea sounds good to the author does not mean it will work for most people in most areas where Bitcoin is used.
Once the champion has asked the Bitcoin community as to whether an idea has any chance of acceptance, a draft BIP should be presented to [email protected]. This gives the author a chance to flesh out the draft BIP to make properly formatted, of high quality, and to address initial concerns about the proposal.
Following a discussion, the proposal should be sent to the Bitcoin-dev list and the BIP editor with the draft BIP. This draft must be written in BIP style as described below, else it will be sent back without further regard until proper formatting rules are followed.
If the BIP editor approves, he will assign the BIP a number, label it as Standards Track, Informational, or Process, give it status "Draft", and add it to the git repository. The BIP editor will not unreasonably deny a BIP. Reasons for denying BIP status include duplication of effort, being technically unsound, not providing proper motivation or addressing backwards compatibility, or not in keeping with the Bitcoin philosophy.
The BIP author may update the Draft as necessary in the git repository. Updates to drafts may also be submitted by the author as pull requests.
Standards Track BIPs consist of two parts, a design document and a reference implementation. The BIP should be reviewed and accepted before a reference implementation is begun, unless a reference implementation will aid people in studying the BIP. Standards Track BIPs must include an implementation — in the form of code, a patch, or a URL to same — before it can be considered Final.
BIP authors are responsible for collecting community feedback on a BIP before submitting it for review. However, wherever possible, long open-ended discussions on public mailing lists should be avoided. Strategies to keep the discussions efficient include: setting up a separate SIG mailing list for the topic, having the BIP author accept private comments in the early design phases, setting up a wiki page or git repository, etc. BIP authors should use their discretion here.
For a BIP to be accepted it must meet certain minimum criteria. It must be a clear and complete description of the proposed enhancement. The enhancement must represent a net improvement. The proposed implementation, if applicable, must be solid and must not complicate the protocol unduly.
Once a BIP has been accepted, the reference implementation must be completed. When the reference implementation is complete and accepted by the community, the status will be changed to "Final".
A BIP can also be assigned status "Deferred". The BIP author or editor can assign the BIP this status when no progress is being made on the BIP. Once a BIP is deferred, the BIP editor can re-assign it to draft status.
A BIP can also be "Rejected". Perhaps after all is said and done it was not a good idea. It is still important to have a record of this fact.
BIPs can also be superseded by a different BIP, rendering the original obsolete. This is intended for Informational BIPs, where version 2 of an API can replace version 1.
The possible paths of the status of BIPs are as follows:
Some Informational and Process BIPs may also have a status of "Active" if they are never meant to be completed. E.g. BIP 1 (this BIP).
Each BIP should have the following parts:
-
Preamble — RFC 822 style headers containing meta-data about the BIP, including the BIP number, a short descriptive title (limited to a maximum of 44 characters), the names, and optionally the contact info for each author, etc.
-
Abstract — a short (~200 word) description of the technical issue being addressed.
-
Copyright/public domain — Each BIP must either be explicitly labelled as placed in the public domain (see this BIP as an example) or licensed under the Open Publication License.
-
Specification — The technical specification should describe the syntax and semantics of any new feature. The specification should be detailed enough to allow competing, interoperable implementations for any of the current Bitcoin platforms (Satoshi, BitcoinJ, bitcoin-js, libbitcoin).
-
Motivation — The motivation is critical for BIPs that want to change the Bitcoin protocol. It should clearly explain why the existing protocol specification is inadequate to address the problem that the BIP solves. BIP submissions without sufficient motivation may be rejected outright.
-
Rationale — The rationale fleshes out the specification by describing what motivated the design and why particular design decisions were made. It should describe alternate designs that were considered and related work, e.g. how the feature is supported in other languages.
-
The rationale should provide evidence of consensus within the community and discuss important objections or concerns raised during discussion.
-
Backwards Compatibility — All BIPs that introduce backwards incompatibilities must include a section describing these incompatibilities and their severity. The BIP must explain how the author proposes to deal with these incompatibilities. BIP submissions without a sufficient backwards compatibility treatise may be rejected outright.
-
Reference Implementation — The reference implementation must be completed before any BIP is given status "Final", but it need not be completed before the BIP is accepted. It is better to finish the specification and rationale first and reach consensus on it before writing code.
-
The final implementation must include test code and documentation appropriate for the Bitcoin protocol.
BIPs should be written in mediawiki or markdown format. Image files should be included in a subdirectory for that BIP.
Each BIP must begin with an RFC 822 style header preamble. The headers must appear in the following order. Headers marked with "*" are optional and are described below. All other headers are required.
BIP: <BIP number>
Title: <BIP title>
Author: <list of authors' real names and optionally, email addrs>
* Discussions-To: <email address>
Status: <Draft | Active | Accepted | Deferred | Rejected |
Withdrawn | Final | Superseded>
Type: <Standards Track | Informational | Process>
Created: <date created on, in ISO 8601 (yyyy-mm-dd) format>
* Post-History: <dates of postings to bitcoin mailing list>
* Replaces: <BIP number>
* Superseded-By: <BIP number>
* Resolution: <url>
The Author header lists the names, and optionally the email addresses of all the authors/owners of the BIP. The format of the Author header value must be
Random J. User
if the email address is included, and just
Random J. User
if the address is not given.
If there are multiple authors, each should be on a separate line following RFC 2822 continuation line conventions.
Note: The Resolution header is required for Standards Track BIPs only. It contains a URL that should point to an email message or other web resource where the pronouncement about the BIP is made.
While a BIP is in private discussions (usually during the initial Draft phase), a Discussions-To header will indicate the mailing list or URL where the BIP is being discussed. No Discussions-To header is necessary if the BIP is being discussed privately with the author, or on the bitcoin email mailing lists.
The Type header specifies the type of BIP: Standards Track, Informational, or Process.
The Created header records the date that the BIP was assigned a number, while Post-History is used to record the dates of when new versions of the BIP are posted to bitcoin mailing lists. Both headers should be in yyyy-mm-dd format, e.g. 2001-08-14.
BIPs may have a Requires header, indicating the BIP numbers that this BIP depends on.
BIPs may also have a Superseded-By header indicating that a BIP has been rendered obsolete by a later document; the value is the number of the BIP that replaces the current document. The newer BIP must have a Replaces header containing the number of the BIP that it rendered obsolete. Auxiliary Files
BIPs may include auxiliary files such as diagrams. Such files must be named BIP-XXXX-Y.ext, where "XXXX" is the BIP number, "Y" is a serial number (starting at 1), and "ext" is replaced by the actual file extension (e.g. "png").
It occasionally becomes necessary to transfer ownership of BIPs to a new champion. In general, we’d like to retain the original author as a co-author of the transferred BIP, but that’s really up to the original author. A good reason to transfer ownership is because the original author no longer has the time or interest in updating it or following through with the BIP process, or has fallen off the face of the 'net (i.e. is unreachable or not responding to email). A bad reason to transfer ownership is because you don’t agree with the direction of the BIP. We try to build consensus around a BIP, but if that’s not possible, you can always submit a competing BIP.
If you are interested in assuming ownership of a BIP, send a message asking to take over, addressed to both the original author and the BIP editor. If the original author doesn’t respond to email in a timely manner, the BIP editor will make a unilateral decision (it’s not like such decisions can’t be reversed :).
The current BIP editor is Gregory Maxwell who can be contacted at [email protected].
A BIP editor must subscribe to the Bitcoin development mailing list. All BIP-related correspondence should be sent (or CC’d) to [email protected].
For each new BIP that comes in an editor does the following:
-
Read the BIP to check if it is ready: sound and complete. The ideas must make technical sense, even if they don’t seem likely to be accepted.
-
The title should accurately describe the content.
-
Edit the BIP for language (spelling, grammar, sentence structure, etc.), markup (for reST BIPs), code style (examples should match BIP 8 & 7).
If the BIP isn’t ready, the editor will send it back to the author for revision, with specific instructions.
Once the BIP is ready for the repository, the BIP editor will:
-
Assign a BIP number (almost always just the next available number, but sometimes it’s a special/joke number, like 666 or 3141).
-
Add the BIP to the bitcoin/bips repository on GitHub.
-
List the BIP in README.mediawiki
-
Send email back to the BIP author with next steps (post to bitcoin mailing list).
Many BIPs are written and maintained by developers with write access to the Bitcoin codebase. The BIP editors monitor BIP changes, and correct any structure, grammar, spelling, or markup mistakes we see.
The editors don’t pass judgement on BIPs. We merely do the administrative & editorial part. Except for times like this, there’s relatively low volume.
This document was derived heavily from Python’s PEP-0001. In many places text was simply copied and modified. Although the PEP-0001 text was written by Barry Warsaw, Jeremy Hylton, and David Goodger, they are not responsible for its use in the Bitcoin Improvement Process, and should not be bothered with technical questions specific to Bitcoin or the BIP process. Please direct all comments to the BIP editors or the Bitcoin development mailing list.
BIP: 11 Title: M-of-N Standard Transactions Author: Gavin Andresen <[email protected]> Status: Accepted Type: Standards Track Created: 2011-10-18 Post-History: 2011-10-02
This BIP proposes M-of-N-signatures required transactions as a new 'standard' transaction type.
Enable secured wallets, escrow transactions, and other use cases where redeeming funds requires more than a single signature.
A couple of motivating use cases:
-
A wallet secured by a "wallet protection service" (WPS). 2-of-2 signatures required transactions will be used, with one signature coming from the (possibly compromised) computer with the wallet and the second signature coming from the WPS. When sending protected bitcoins, the user’s bitcoin client will contact the WPS with the proposed transaction and it can then contact the user for confirmation that they initiated the transaction and that the transaction details are correct. Details for how clients and WPS’s communicate are outside the scope of this BIP. Side note: customers should insist that their wallet protection service provide them with copies of the private key(s) used to secure their wallets that they can safely store off-line, so that their coins can be spent even if the WPS goes out of business.
-
Three-party escrow (buyer, seller and trusted dispute agent). 2-of-3 signatures required transactions will be used. The buyer and seller and agent will each provide a public key, and the buyer will then send coins into a 2-of-3 CHECKMULTISIG transaction and send the seller and the agent the transaction id. The seller will fulfill their obligation and then ask the buyer to co-sign a transaction ( already signed by seller ) that sends the tied-up coins to him (seller).
If the buyer and seller cannot agree, then the agent can, with the cooperation of either buyer or seller, decide what happens to the tied-up coins. Details of how buyer, seller, and agent communicate to gather signatures or public keys are outside the scope of this BIP.
A new standard transaction type (scriptPubKey) that is relayed by clients and included in mined blocks:
m {pubkey}…{pubkey} n OP_CHECKMULTISIG
But only for n less than or equal to 3.
OP_CHECKMULTISIG transactions are redeemed using a standard scriptSig:
OP_0 …signatures…
(OP_0 is required because of a bug in OP_CHECKMULTISIG; it pops one too many items off the execution stack, so a dummy value must be placed on the stack).
The current Satoshi bitcoin client does not relay or mine transactions with scriptSigs larger than 200 bytes; to accomodate 3-signature transactions, this will be increased to 500 bytes.
OP_CHECKMULTISIG is already an enabled opcode, and is the most straightforward way to support several important use cases.
One argument against using OP_CHECKMULTISIG is that old clients and miners count it as "20 sigops" for purposes of computing how many signature operations are in a block, and there is a hard limit of 20,000 sigops per block-- meaning a maximum of 1,000 multisig transactions per block. Creating multisig transactions using multiple OP_CHECKSIG operations allows more of them per block.
The counter-argument is that these new multi-signature transactions will be used in combination with OP_EVAL (see the OP_EVAL BIP), and will be counted accurately. And in any case, as transaction volume rises the hard-coded maximum block size will have to be addressed, and the rules for counting number-of-signature-operations-in-a-block can be addressed at that time.
A weaker argument is OP_CHECKMULTISIG should not be used because it pops one too many items off the stack during validation. Adding an extra OP_0 placeholder to the scriptSig adds only 1 byte to the transaction, and any alternative that avoids OP_CHECKMULTISIG adds at least several bytes of opcodes.
OP_CHECKMULTISIG is already supported by old clients and miners as a non-standard transaction type.
BIP: 13 Title: Address Format for pay-to-script-hash Author: Gavin Andresen <[email protected]> Status: Final Type: Standards Track Created: 2011-10-18
This BIP describes a new type of Bitcoin address to support arbitrarily complex transactions. Complexity in this context is defined as what information is needed by the recipient to respend the received coins, in contrast to needing a single ECDSA private key as in current implementations of Bitcoin.
In essence, an address encoded under this proposal represents the encoded hash of a script, rather than the encoded hash of an ECDSA public key.
Enable "end-to-end" secure wallets and payments to fund escrow transactions or other complex transactions. Enable third-party wallet security services.
The new bitcoin address type is constructed in the same manner as existing bitcoin addresses (see link:Base58Check encoding[Base58Check encoding]):
base58-encode: [one-byte version][20-byte hash][4-byte checksum]
Version byte is 5 for a main-network address, 196 for a testnet address. The 20-byte hash is the hash of the script that will be used to redeem the coins. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and hash.
One criticism is that bitcoin addresses should be deprecated in favor of a more user-friendly mechanism for payments, and that this will just encourage continued use of a poorly designed mechanism.
Another criticism is that bitcoin addresses are inherently insecure because there is no identity information tied to them; if you only have a bitcoin address, how can you be certain that you’re paying who or what you think you’re paying?
Furthermore, truncating SHA256 is not an optimal checksum; there are much better error-detecting algorithms. If we are introducing a new form of Bitcoin address, then perhaps a better algorithm should be used.
This is one piece of the simplest path to a more secure bitcoin infrastructure. It is not intended to solve all of bitcoin’s usability or security issues, but to be an incremental improvement over what exists today. A future BIP or BIPs should propose more user-friendly mechanisms for making payments, or for verifying that you’re sending a payment to the Free Software Foundation and not Joe Random Hacker.
Assuming that typing in bitcoin addresses manually will become increasingly rare in the future, and given that the existing checksum method for bitcoin addresses seems to work "well enough" in practice and has already been implemented multiple times, the Author believes no change to the checksum algorithm is necessary.
The leading version bytes are chosen so that, after base58 encoding, the leading character is consistent: for the main network, byte 5 becomes the character '3'. For the testnet, byte 196 is encoded into '2'.
This proposal is not backwards compatible, but it fails gracefully-- if an older implementation is given one of these new bitcoin addresses, it will report the address as invalid and will refuse to create a transaction.
See base58.cpp1/base58.h at https://github.com/bitcoin/bitcoin/src
BIP: 14 Title: BIP Protocol Version and User Agent Author: Amir Taaki <[email protected]> Patrick Strateman <[email protected]> Status: Accepted Type: Standards Track Created: 2011-11-10 Post-History: 2011-11-02
In this document, bitcoin will be used to refer to the protocol while Satoshi will refer to the current client in order to prevent confusion.
Bitcoin as a protocol began life with the Satoshi client. Now that the community is diversifying, a number of alternative clients with their own codebases written in a variety of languages (Java, Python, Javascript, C++) are rapidly developing their own feature-sets.
Embedded in the protocol is a version number. Primarily this version number is in the "version" and "getblocks" messages, but is also in the "block" message to indicate the software version that created that block. Currently this version number is the same version number as that of the client. This document is a proposal to separate the protocol version from the client version, together with a proposed method to do so.
With non-separated version numbers, every release of the Satoshi client will increase its internal version number. Primarily this holds every other client hostage to a game of catch-up with Satoshi version number schemes. This plays against the decentralised nature of bitcoin, by forcing every software release to remain in step with the release schedule of one group of bitcoin developers.
Version bumping can also introduce incompatibilities and fracture the network. In order that the health of the network is maintained, the development of the protocol as a shared common collaborative process requires being split off from the implementation of that protocol. Neutral third entities to guide the protocol with representatives from all groups, present the chance for bitcoin to grow in a positive manner with minimal risks.
By using a protocol version, we set all implementations on the network to a common standard. Everybody is able to agree within their confines what is protocol and what is implementation-dependent. A user agent string is offered as a 'vanity-plate' for clients to distinguish themselves in the network.
Separation of the network protocol from the implemention, and forming development of said protocol by means of a mutual consensus among participants, has the democratic disadvantage when agreement is hard to reach on contentious issues. To mitigate this issue, strong communication channels and fast release schedules are needed, and are outside the scope of this document (concerning a process-BIP type).
User agents provide extra tracking information that is useful for keeping tabs on network data such as client implementations used or common architectures/operating-systems. In the rare case they may even provide an emergency method of shunning faulty clients that threaten network health- although this is strongly unrecommended and extremely bad form. The user agent does not provide a method for clients to work around and behave differently to different implementations, as this will lead to protocol fracturing.
In short:
-
Protocol version: way to distinguish between nodes and behave different accordingly.
-
User agent: simple informational tool. Protocol should not be modified depending on user agent.
RFC 1945 vaguely specifies a user agent to be a string of the product with optional comments.
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.6) Gecko/20100127 Gentoo Shiretoko/3.5.6
User agents are most often parsed by computers more than humans. The space delimited format, does not provide an easy, fast or efficient way for parsing. The data contains no structure indicating hierarchy in this placement.
The most immediate pieces of information there are the browser product, rendering engine and the build (Gentoo Shiretoko) together with version number. Various other pieces of information as included as comments such as desktop environment, platform, language and revision number of the build.
The version field in "version" and "getblocks" packets will become the protocol version number. The version number in the "blocks" reflects the protocol version from when that block was created.
The currently unused sub_version_num field in "version" packets will become the new user-agent string.
Bitcoin user agents are a modified browser user agent with more structure to aid parsers and provide some coherence. In bitcoin, the software usually works like a stack starting from the core code-base up to the end graphical interface. Therefore the user agent strings codify this relationship.
Basic format:
/Name:Version/Name:Version/…/
Example:
/Satoshi:5.64/bitcoin-qt:0.4/
/Satoshi:5.12/Spesmilo:0.8/
Here bitcoin-qt and Spesmilo may use protocol version 5.0, however the internal codebase they use are different versions of the same software. The version numbers are not defined to any strict format, although this guide recommends:
-
Version numbers in the form of Major.Minor.Revision (2.6.41)
-
Repository builds using a date in the format of YYYYMMDD (20110128)
For git repository builds, implementations are free to use the git commitish. However the issue lies in that it is not immediately obvious without the repository which version precedes another. For this reason, we lightly recommend dates in the format specified above, although this is by no means a requirement.
Optional -r1, -r2, … can be appended to user agent version numbers. This is another light recommendation, but not a requirement. Implementations are free to specify version numbers in whatever format needed insofar as it does not include (, ), : or / to interfere with the user agent syntax.
An optional comments field after the version number is also allowed. Comments should be delimited by brackets (…). The contents of comments is entirely implementation defined although this BIP recommends the use of semi-colons ; as a delimiter between pieces of information.
Example:
/BitcoinJ:0.2(iPad; U; CPU OS 3_2_1)/AndroidBuild:0.8/
Reserved symbols are therefore: / : ( )
They should not be misused beyond what is specified in this section.
-
/ separates the code-stack
-
:: specifies the implementation version of the particular stack
-
( and ) delimits a comment which optionally separates data using ;
When this document was published, the bitcoin protocol and Satoshi client versions were currently at 0.5 and undergoing changes. In order to minimise disruption and allow the undergoing changes to be completed, the next protocol version at 0.6 became peeled from the client version (also at 0.6). As of that time (January 2012), protocol and implementation version numbers are distinct from each other.
BIP: 16 Title: Pay to Script Hash Author: Gavin Andresen <[email protected]> Status: Final Type: Standards Track Created: 2012-01-03
[[abstract]]
Abstract
~~~~~~~~
This BIP describes a new "standard" transaction type for the Bitcoin
scripting system, and defines additional validation rules that apply
only to the new transactions.
[[motivation]]
Motivation
~~~~~~~~~~
The purpose of pay-to-script-hash is to move the responsibility for
supplying the conditions to redeem a transaction from the sender of the
funds to the redeemer.
The benefit is allowing a sender to fund any arbitrary transaction, no
matter how complicated, using a fixed-length 20-byte hash that is short
enough to scan from a QR code or easily copied and pasted.
[[specification]]
Specification
~~~~~~~~~~~~~
A new standard transaction type that is relayed and included in mined
blocks is defined:
` OP_HASH160 [20-byte-hash-value] OP_EQUAL`
[20-byte-hash-value] shall be the push-20-bytes-onto-the-stack opcode
(0x14) followed by exactly 20 bytes.
This new transaction type is redeemed by a standard scriptSig:
` ...signatures... {serialized script}`
Transactions that redeem these pay-to-script outpoints are only
considered standard if the _serialized script_ - also referred to as the
_redeemScript_ - is, itself, one of the other standard transaction
types.
The rules for validating these outpoints when relaying transactions or
considering them for inclusion in a new block are as follows:
1. Validation fails if there are any operations other than "push data"
operations in the scriptSig.
2. Normal validation is done: an initial stack is created from the
signatures and \{serialized script}, and the hash of the script is
computed and validation fails immediately if it does not match the hash
in the outpoint.
3. \{serialized script} is popped off the initial stack, and the
transaction is validated again using the popped stack and the
deserialized script as the scriptPubKey.
These new rules should only be applied when validating transactions in
blocks with timestamps >= 1333238400 (Apr 1 2012)
footnote:[https://github.com/bitcoin/bitcoin/commit/8f188ece3c82c4cf5d52a3363e7643c23169c0ff[Remove
-bip16 and -paytoscripthashtime command-line arguments]]. There are
transaction earlier than 13333238400 in the block chain that fail these
new validation rules.
footnote:[http://blockexplorer.com/tx/6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192[Transaction
6a26d2ecb67f27d1fa5524763b49029d7106e91e3cc05743073461a719776192]].
Older transactions must be validated under the old rules. (see the
Backwards Compatibility section for details).
For example, the scriptPubKey and corresponding scriptSig for a
one-signature-required transaction is:
` scriptSig: [signature] {[pubkey] OP_CHECKSIG}` +
` scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL`
Signature operations in the \{serialized script} shall contribute to the
maximum number allowed per block (20,000) as follows:
1. OP_CHECKSIG and OP_CHECKSIGVERIFY count as 1 signature operation,
whether or not they are evaluated.
2. OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY immediately preceded by
OP_1 through OP_16 are counted as 1 to 16 signature operation, whether
or not they are evaluated.
3. All other OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY are counted as
20 signature operations.
Examples:
+3 signature operations:
` {2 [pubkey1] [pubkey2] [pubkey3] 3 OP_CHECKMULTISIG}`
+22 signature operations
` {OP_CHECKSIG OP_IF OP_CHECKSIGVERIFY OP_ELSE OP_CHECKMULTISIGVERIFY OP_ENDIF}`
[[rationale]]
Rationale
~~~~~~~~~
This BIP replaces BIP 12, which proposed a new Script opcode ("OP_EVAL")
to accomplish everything in this BIP and more.
The Motivation for this BIP (and BIP 13, the pay-to-script-hash address
type) is somewhat controversial; several people feel that it is
unnecessary, and complex/multisignature transaction types should be
supported by simply giving the sender the complete \{serialized script}.
The author believes that this BIP will minimize the changes needed to
all of the supporting infrastructure that has already been created to
send funds to a base58-encoded-20-byte bitcoin addresses, allowing
merchants and exchanges and other software to start supporting
multisignature transactions sooner.
Recognizing one 'special' form of scriptPubKey and performing extra
validation when it is detected is ugly. However, the consensus is that
the alternatives are either uglier, are more complex to implement,
and/or expand the power of the expression language in dangerous ways.
The signature operation counting rules are intended to be easy and quick
to implement by statically scanning the \{serialized script}. Bitcoin
imposes a maximum-number-of-signature-operations per block to prevent
denial-of-service attacks on miners. If there was no limit, a rogue
miner might broadcast a block that required hundreds of thousands of
ECDSA signature operations to validate, and it might be able to get a
head start computing the next block while the rest of the network worked
to validate the current one.
There is a 1-confirmation attack on old implementations, but it is
expensive and difficult in practice. The attack is:
1. Attacker creates a pay-to-script-hash transaction that is valid as
seen by old software, but invalid for new implementation, and sends
themselves some coins using it.
2. Attacker also creates a standard transaction that spends the
pay-to-script transaction, and pays the victim who is running old
software.
3. Attacker mines a block that contains both transactions.
If the victim accepts the 1-confirmation payment, then the attacker wins
because both transactions will be invalidated when the rest of the
network overwrites the attacker's invalid block.
The attack is expensive because it requires the attacker create a block
that they know will be invalidated by the rest of the network. It is
difficult because creating blocks is difficult and users should not
accept 1-confirmation transactions for higher-value transactions.
[[backwards-compatibility]]
Backwards Compatibility
~~~~~~~~~~~~~~~~~~~~~~~
These transactions are non-standard to old implementations, which will
(typically) not relay them or include them in blocks.
Old implementations will validate that the serialize script's hash
value matches when they validate blocks created by software that fully
support this BIP, but will do no other validation.
Avoiding a block-chain split by malicious pay-to-script transactions
requires careful handling of one case:
* A pay-to-script-hash transaction that is invalid for new
clients/miners but valid for old clients/miners.
To gracefully upgrade and ensure no long-lasting block-chain split
occurs, more than 50% of miners must support full validation of the new
transaction type and must switch from the old validation rules to the
new rules at the same time.
To judge whether or not more than 50% of hashing power supports this
BIP, miners are asked to upgrade their software and put the string
"/P2SH/" in the input of the coinbase transaction for blocks that they
create.
On February 1, 2012, the block-chain will be examined to determine the
number of blocks supporting pay-to-script-hash for the previous 7 days.
If 550 or more contain "/P2SH/" in their coinbase, then all blocks with
timestamps after 15 Feb 2012, 00:00:00 GMT shall have their
pay-to-script-hash transactions fully validated. Approximately 1,000
blocks are created in a week; 550 should, therefore, be approximately
55% of the network supporting the new feature.
If a majority of hashing power does not support the new validation
rules, then rollout will be postponed (or rejected if it becomes clear
that a majority will never be achieved).
[[byte-limitation-on-serialized-script-size]]
520-byte limitation on serialized script size
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
As a consequence of the requirement for backwards compatiblity the
serialized script is itself subject to the same rules as any other
PUSHDATA operation, including the rule that no data greater than 520
bytes may be pushed to the stack. Thus is it not possible to spend a
P2SH output if the redemption script it refers to is >520 bytes in
length. For instance while the OP_CHECKMULTISIG opcode can itself accept
up to 20 pubkeys, with 33-byte compressed pubkeys it is only possible to
spend a P2SH output requiring a maximum of 15 pubkeys to redeem: 3 bytes
+ 15 pubkeys * 34 bytes/pubkey = 513 bytes.
[[reference-implementation]]
Reference Implementation
~~~~~~~~~~~~~~~~~~~~~~~~
https://gist.github.com/gavinandresen/3966071
[[see-also]]
See Also
~~~~~~~~
* https://bitcointalk.org/index.php?topic=46538
* The link:bip-0013.mediawiki[Address format for Pay to Script Hash BIP]
* M-of-N Multisignature Transactions link:bip-0011.mediawiki[BIP 11]
* link:bip-0016/qa.mediawiki[Quality Assurance test checklist]
[[references]]
References
~~~~~~~~~~
---------------------------------------------------
BIP: 21
Title: URI Scheme
Author: Nils Schneider <[email protected]>
Matt Corallo <[email protected]>
Status: Accepted
Type: Standards Track
Created: 2012-01-29
---------------------------------------------------
This BIP is a modification of an earlier link:bip-0020.mediawiki[BIP
0020] by Luke Dashjr. BIP 0020 was based off an earlier document by Nils
Schneider. The alternative payment amounts in BIP 0020 have been
removed.
[[abstract]]
Abstract
~~~~~~~~
This BIP proposes a URI scheme for making Bitcoin payments.
[[motivation]]
Motivation
~~~~~~~~~~
The purpose of this URI scheme is to enable users to easily make
payments by simply clicking links on webpages or scanning QR Codes.
[[specification]]
Specification
~~~~~~~~~~~~~
[[general-rules-for-handling-important]]
General rules for handling (important!)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Bitcoin clients MUST NOT act on URIs without getting the user's
authorization. They SHOULD require the user to manually approve each
payment individually, though in some cases they MAY allow the user to
automatically make this decision.
[[operating-system-integration]]
Operating system integration
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Graphical bitcoin clients SHOULD register themselves as the handler for
the "bitcoin:" URI scheme by default, if no other handler is already
registered. If there is already a registered handler, they MAY prompt
the user to change it once when they first run the client.
[[general-format]]
General Format
^^^^^^^^^^^^^^
Bitcoin URIs follow the general format for URIs as set forth in RFC
3986. The path component consists of a bitcoin address, and the query
component provides additional payment options.
Elements of the query component may contain characters outside the valid
range. These must first be encoded according to UTF-8, and then each
octet of the corresponding UTF-8 sequence must be percent-encoded as
described in RFC 3986.
[[abnf-grammar]]
ABNF grammar
^^^^^^^^^^^^
(See also link:#Simpler_syntax[a simpler representation of syntax])
`bitcoinurn = "bitcoin:" bitcoinaddress [ "?" bitcoinparams ]` +
`bitcoinaddress = *base58` +
`bitcoinparams = bitcoinparam [ "&" bitcoinparams ]` +
`bitcoinparam = [ amountparam / labelparam / messageparam / otherparam / reqparam ]` +
`amountparam = "amount=" *digit [ "." *digit ]` +
`labelparam = "label=" *qchar` +
`messageparam = "message=" *qchar` +
`otherparam = qchar *qchar [ "=" *qchar ]` +
`reqparam = "req-" qchar *qchar [ "=" *qchar ]`
Here, "qchar" corresponds to valid characters of an RFC 3986 URI query
component, excluding the "=" and "&" characters, which this BIP takes as
separators.
The scheme component ("bitcoin:") is case-insensitive, and
implementations must accept any combination of uppercase and lowercase
letters. The rest of the URI is case-sensitive, including the query
parameter keys.
[[query-keys]]
Query Keys
^^^^^^^^^^
* label: Label for that address (e.g. name of receiver)
* address: bitcoin address
* message: message that describes the transaction to the user
(link:#Examples[see examples below])
* size: amount of base bitcoin units (link:#Transfer_amount/size[see
below])
* (others): optional, for future extensions
[[transfer-amountsize]]
Transfer amount/size
++++++++++++++++++++
If an amount is provided, it MUST be specified in decimal BTC. All
amounts MUST contain no commas and use a period (.) as the separating
character to separate whole numbers and decimal fractions. I.e.
amount=50.00 or amount=50 is treated as 50 BTC, and amount=50,000.00 is
invalid.
Bitcoin clients MAY display the amount in any format that is not
intended to deceive the user. They SHOULD choose a format that is
foremost least confusing, and only after that most reasonable given the
amount requested. For example, so long as the majority of users work in
BTC units, values should always be displayed in BTC by default, even if
mBTC or TBC would otherwise be a more logical interpretation of the
amount.
[[rationale]]
Rationale
~~~~~~~~~
[[payment-identifiers-not-person-identifiers]]
Payment identifiers, not person identifiers
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Current best practices are that a unique address should be used for
every transaction. Therefore, a URI scheme should not represent an
exchange of personal information, but a one-time payment.
[[accessibility-uri-scheme-name]]
Accessibility (URI scheme name)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Should someone from the outside happen to see such a URI, the URI scheme
name already gives a description. A quick search should then do the rest
to help them find the resources needed to make their payment. Other
proposed names sound much more cryptic; the chance that someone googles
that out of curiosity are much slimmer. Also, very likely, what he will
find are mostly technical specifications - not the best introduction to
bitcoin.
[[forward-compatibility]]
Forward compatibility
~~~~~~~~~~~~~~~~~~~~~
Variables which are prefixed with a req- are considered required. If a
client does not implement any variables which are prefixed with req-, it
MUST consider the entire URI invalid. Any other variables which are not
implemented, but which are not prefixed with a req-, can be safely
ignored.
[[backward-compatibility]]
Backward compatibility
~~~~~~~~~~~~~~~~~~~~~~
As this BIP is written, several clients already implement a bitcoin: URI
scheme similar to this one, however usually without the additional
"req-" prefix requirement. Thus, it is recommended that additional
variables prefixed with req- not be used in a mission-critical way until
a grace period of 6 months from the finalization of this BIP has passed
in order to allow client developers to release new versions, and users
of old clients to upgrade.
[[appendix]]
Appendix
~~~~~~~~
[[simpler-syntax]]
Simpler syntax
^^^^^^^^^^^^^^
This section is non-normative and does not cover all possible syntax.
Please see the BNF grammar above for the normative syntax.
[foo] means optional, <bar> are placeholders
`bitcoin:<address>[?amount=<amount>][?label=<label>][?message=<message>]`
[[examples]]
Examples
^^^^^^^^
Just the address:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W`]
Address with name:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?label=Luke-Jr[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?label=Luke-Jr`]
Request 20.30 BTC to "Luke-Jr":
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=20.3&label=Luke-Jr[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=20.3&label=Luke-Jr`]
Request 50 BTC with message:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=50&label=Luke-Jr&message=Donation%20for%20project%20xyz[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?amount=50&label=Luke-Jr&message=Donation%20for%20project%20xyz`]
Some future version that has variables which are (currently) not
understood and required and thus invalid:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?req-somethingyoudontunderstand=50&req-somethingelseyoudontget=999[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?req-somethingyoudontunderstand=50&req-somethingelseyoudontget=999`]
Some future version that has variables which are (currently) not
understood but not required and thus valid:
bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?somethingyoudontunderstand=50&somethingelseyoudontget=999[`bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?somethingyoudontunderstand=50&somethingelseyoudontget=999`]
Characters must be URI encoded properly.
[[reference-implementations]]
Reference Implementations
~~~~~~~~~~~~~~~~~~~~~~~~~
[[bitcoin-clients]]
Bitcoin clients
^^^^^^^^^^^^^^^
* Bitcoin-Qt supports the old version of Bitcoin URIs (ie without the
req- prefix), with Windows and KDE integration as of commit
70f55355e29c8e45b607e782c5d76609d23cc858.
---------------------------------------------
BIP: 22
Title: getblocktemplate - Fundamentals
Author: Luke Dashjr <[email protected]>
Status: Accepted
Type: Standards Track
Created: 2012-02-28
---------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This BIP describes a new JSON-RPC method for "smart" Bitcoin miners and
proxies. Instead of sending a simple block header for hashing, the
entire block structure is sent, and left to the miner to (optionally)
customize and assemble.
[[specification]]
Specification
~~~~~~~~~~~~~
[[block-template-request]]
Block Template Request
^^^^^^^^^^^^^^^^^^^^^^
A JSON-RPC method is defined, called "getblocktemplate". It accepts
exactly one argument, which MUST be an Object of request parameters. If
the request parameters include a "mode" key, that is used to explicitly
select between the default "template" request or a
link:bip-0023.mediawiki#Block_Proposal["proposal"].
Block template creation can be influenced by various parameters:
[cols="",options="header",]
|=======================================================================
|colspan=4|template request
|Key |Required |Type |Description
|capabilities a| |Array of Strings |SHOULD contain a list of the
following, to indicate client-side support:
#Optional:_Long_Polling["longpoll"], "coinbasetxn", "coinbasevalue",
link:bip-0023.mediawiki#Block_Proposal["proposal"],
link:bip-0023.mediawiki#Logical_Services["serverlist"], "workid", and
any of the link:bip-0023.mediawiki#Mutations[mutations]
|mode a| |String |MUST be "template" or omitted
|=======================================================================
getblocktemplate MUST return a JSON Object containing the following
keys:
[cols="",options="header",]
|=======================================================================
|colspan=4| template
|Key |Required |Type |Description
|bits a| |String |the compressed difficulty in hexadecimal
|curtime a| |Number |the current time as seen by the server (recommended
for block time) - note this is not necessarily the system clock, and
must fall within the mintime/maxtime rules
|height a| |Number |the height of the block we are looking for
|previousblockhash a| |String |the hash of the previous block, in
big-endian hexadecimal
|sigoplimit a| |Number |number of sigops allowed in blocks
|sizelimit a| |Number |number of bytes allowed in blocks
|transactions a| |Array of Objects |Objects containing
link:#Transactions_Object_Format[information for Bitcoin transactions]
(excluding coinbase)
|version a| |Number |always 1 or 2 (at least for bitcoin) - clients MUST
understand the implications of the version they use (eg, comply with
link:bip-0034.mediawiki[BIP 0034] for version 2)
|coinbaseaux a| |Object |data that SHOULD be included in the coinbase's
scriptSig content. Only the values (hexadecimal byte-for-byte) in this
Object should be included, not the keys. This does not include the block
height, which is required to be included in the scriptSig by
link:bip-0034.mediawiki[BIP 0034]. It is advisable to encode values
inside "PUSH" opcodes, so as to not inadvertantly expend SIGOPs (which
are counted toward limits, despite not being executed).
|coinbasetxn a| |Object |link:#Transactions_Object_Format[information
for coinbase transaction]
|coinbasevalue a| |Number |total funds available for the coinbase (in
Satoshis)
|workid a| |String |if provided, this value must be returned with
results (see link:#Block_Submission[Block Submission])
|=======================================================================
[[transactions-object-format]]
Transactions Object Format
++++++++++++++++++++++++++
The Objects listed in the response's "transactions" key contains these
keys:
[cols="",options="header",]
|=======================================================================
|colspan=3|template "transactions" element
|Key |Type |Description
|data |String |transaction data encoded in hexadecimal (byte-for-byte)
|depends |Array of Numbers |other transactions before this one (by
1-based index in "transactions" list) that must be present in the final
block if this one is; if key is not present, dependencies are unknown
and clients MUST NOT assume there aren't any
|fee |Number |difference in value between transaction inputs and outputs
(in Satoshis); for coinbase transactions, this is a negative Number of
the total collected block fees (ie, not including the block subsidy); if
key is not present, fee is unknown and clients MUST NOT assume there
isn't one
|hash |String |hash/id encoded in little-endian hexadecimal
|required |Boolean |if provided and true, this transaction must be in
the final block
|sigops |Number |total number of SigOps, as counted for purposes of
block limits; if key is not present, sigop count is unknown and clients
MUST NOT assume there aren't any
|=======================================================================
Only the "data" key is required, but servers should provide the others
if they are known.
[[block-submission]]
Block Submission
^^^^^^^^^^^^^^^^
A JSON-RPC method is defined, called "submitblock", to submit potential
blocks (or shares). It accepts two arguments: the first is always a
String of the hex-encoded block data to submit; the second is an Object
of parameters, and is optional if parameters are not needed.
[cols="",options="header",]
|=======================================================================
|colspan=3|submitblock parameters (2nd argument)
|Key |Type |Description
|workid |String |if the server provided a workid, it MUST be included
with submissions
|=======================================================================
This method MUST return either null (when a share is accepted), a String
describing briefly the reason the share was rejected, or an Object of
these with a key for each merged-mining chain the share was submitted
to.
[[optional-long-polling]]
Optional: Long Polling
^^^^^^^^^^^^^^^^^^^^^^
[cols="",options="header",]
|=======================================================================
|template request
|Key |Type |Description
|capabilities |Array of Strings |miners which support long polling
SHOULD provide a list including the String "longpoll"
|longpollid |String |"longpollid" of job to monitor for expiration;
required and valid only for long poll requests
|=======================================================================
[cols="",options="header",]
|=======================================================================
|template
|Key |Type |Description
|longpollid |String |identifier for long poll request; MUST be omitted
if the server does not support long polling
|longpolluri |String |if provided, an alternate URI to use for long poll
requests
|submitold |Boolean |only relevant for long poll responses: indicates if
work received prior to this response remains potentially valid (default)
and should have its shares submitted; if false, the miner may wish to
discard its share queue
|=======================================================================
If the server supports long polling, it MUST include a "longpollid" key
in block templates, and it MUST be unique for each event: any given
"longpollid" should check for only one condition and not be reused. For
example, a server which has a long poll wakeup only for new blocks might
use the previous block hash. However, clients should not assume the
"longpollid" has any specific meaning. It MAY supply the "longpolluri"
key with a relative or absolute URI, which MAY specify a completely
different resource than the original connection, including port number.
If "longpolluri" is provided by the server, clients MUST only attempt to
use that URI for longpoll requests.
Clients MAY start a longpoll request with a standard JSON-RPC request
(in the case of HTTP transport, POST with data) and same authorization,
setting the "longpollid" parameter in the request to the value provided
by the server.
This request SHOULD NOT be processed nor answered by the server until it
wishes to replace the current block data as identified by the
"longpollid". Clients SHOULD make this request with a very long request
timeout and MUST accept servers sending a partial response in advance
(such as HTTP headers with "chunked" Transfer-Encoding), and only
delaying the completion of the final JSON response until processing.
Upon receiving a completed response:
* Only if "submitold" is provided and false, the client MAY discard the
results of past operations and MUST begin working on the new work
immediately.
* The client SHOULD begin working on the new work received as soon as
possible, if not immediately.
* The client SHOULD make a new request to the same long polling URI.
If a client receives an incomplete or invalid response, it SHOULD retry
the request with an exponential backoff. Clients MAY implement this
backoff with limitations (such as maximum backoff time) or any algorithm
as deemed suitable. It is, however, forbidden to simply retry
immediately with no delay after more than one failure. In the case of a
"Forbidden" response (for example, HTTP 403), a client SHOULD NOT
attempt to retry without user intervention.
[[optional-template-tweaking]]
Optional: Template Tweaking
^^^^^^^^^^^^^^^^^^^^^^^^^^^
[cols="",options="header",]
|=======================================================================
|template request
|Key |Type |Description
|sigoplimit |Number or Boolean |maximum number of sigops to include in
template
|sizelimit |Number or Boolean |maximum number of bytes to use for the
entire block
|maxversion |Number |highest block version number supported
|=======================================================================
For "sigoplimit" and "sizelimit", negative values and zero are offset
from the server-determined block maximum. If a Boolean is provided and
true, the default limit is used; if false, the server is instructed not
to use any limits on returned template. Servers SHOULD respect these
desired maximums, but are NOT required to: clients SHOULD check that the
returned template satisfies their requirements appropriately.
[[appendix-example-rejection-reasons]]
Appendix: Example Rejection Reasons
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Possible reasons a share may be rejected include, but are not limited
to:
[cols="",options="header",]
|=======================================================================
|colspan=2| share rejection reasons
|Reason |Description
|bad-cb-flag |the server detected a feature-signifying flag that it does
not allow
|bad-cb-length |the coinbase was too long (bitcoin limit is 100 bytes)
|bad-cb-prefix |the server only allows appending to the coinbase, but it
was modified beyond that
|bad-diffbits |"bits" were changed
|bad-prevblk |the previous-block is not the one the server intends to
build on
|bad-txnmrklroot |the block header's merkle root did not match the
transaction merkle tree
|bad-txns |the server didn't like something about the transactions in
the block
|bad-version |the version was wrong
|duplicate |the server already processed this block data
|high-hash |the block header did not hash to a value lower than the
specified target
|rejected |a generic rejection without details
|stale-prevblk |the previous-block is no longer the one the server
intends to build on
|stale-work |the work this block was based on is no longer accepted
|time-invalid |the time was not acceptable
|time-too-new |the time was too far in the future
|time-too-old |the time was too far in the past
|unknown-user |the user submitting the block was not recognized
|unknown-work |the template or workid could not be identified
|=======================================================================
[[motivation]]
Motivation
~~~~~~~~~~
bitcoind's JSON-RPC server can no longer support the load of generating
the work required to productively mine Bitcoin, and external software
specializing in work generation has become necessary. At the same time,
new independent node implementations are maturing to the point where
they will also be able to support miners.
A common standard for communicating block construction details is
necessary to ensure compatibility between the full nodes and work
generation software.
[[rationale]]
Rationale
~~~~~~~~~
Why not just deal with transactions as hashes (txids)?
* Servers might not have access to the transaction database, or miners
may wish to include transactions not broadcast to the network as a
whole.
* Miners may opt not to do full transaction verification, and may not
have access to the transaction database on their end.
What is the purpose of "workid"?
* If servers allow all mutations, it may be hard to identify which job
it is based on. While it may be possible to verify the submission by its
content, it is much easier to compare it to the job issued. It is very
easy for the miner to keep track of this. Therefore, using a "workid" is
a very cheap solution to enable more mutations.
Why should "sigops" be provided for transactions?
* Due to the link:bip-0016.mediawiki[BIP 0016] changes regarding rules
on block sigops, it is impossible to count sigops from the transactions
themselves (the sigops in the scriptCheck must also be included in the
count).
[[reference-implementation]]
Reference Implementation
~~~~~~~~~~~~~~~~~~~~~~~~
* https://gitorious.org/bitcoin/eloipool[Eloipool (server)]
* http://gitorious.org/bitcoin/libblkmaker[libblkmaker (client)]
* https://github.com/bitcoin/bitcoin/pull/936/files[bitcoind (minimal
server)]
[[see-also]]
See Also
~~~~~~~~
* link:bip-0023.mediawiki[BIP 23: getblocktemplate - Pooled Mining]
---------------------------------------------
BIP: 23
Title: getblocktemplate - Pooled Mining
Author: Luke Dashjr <[email protected]>
Status: Accepted
Type: Standards Track
Created: 2012-02-28
---------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This BIP describes extensions to the getblocktemplate JSON-RPC call to
enhance pooled mining.
[[specification]]
Specification
~~~~~~~~~~~~~
Note that all sections of this specification are optional extensions on
top of link:BIP 0022[BIP 22].
[[summary-support-levels]]
Summary Support Levels
^^^^^^^^^^^^^^^^^^^^^^
Something can be said to have BIP 23 Level 1 support if it implements at
least:
* http://www.ietf.org/rfc/rfc1945.txt[RFC 1945]
* http://json-rpc.org/wiki/specification[JSON-RPC 1.0]
* link:bip-0022.mediawiki[BIP 22 (non-optional sections)]
* bip-0022.mediawiki#Optional:_Long_Polling[BIP 22 Long Polling]
* link:#Basic_Pool_Extensions[BIP 23 Basic Pool Extensions]
* link:#Mutations[BIP 23 Mutation "coinbase/append"]
* link:#Submission_Abbreviation[BIP 23 Submission Abbreviation
"submit/coinbase"]
* link:#Mutations[BIP 23 Mutation "time/increment"] (only required for
servers)
It can be said to have BIP 23 Level 2 support if it also implements:
* link:#Mutations[BIP 23 Mutation "transactions/add"]
* link:#Block_Proposals[BIP 23 Block Proposals]
[[basic-pool-extensions]]
Basic Pool Extensions
^^^^^^^^^^^^^^^^^^^^^
[cols="",options="header",]
|==================================================================
|template request
|Key |Type |Description
|target |String |desired target for block template (may be ignored)
|==================================================================
[cols="",options="header",]
|=======================================================================
|template
|Key |Type |Description
|expires |Number |how many seconds (beginning from when the server sent
the response) this work is valid for, at most
|target |String |the number which valid results must be less than, in
big-endian hexadecimal
|=======================================================================
[[block-proposal]]
Block Proposal
^^^^^^^^^^^^^^
Servers may indicate support for proposing blocks by including a
capability string in their original template:
[cols="",options="header",]
|=======================================================================
|template
|Key |Type |Description
|capabilities |Array of Strings |MAY contain "proposal" to indicate
support for block proposal
|reject-reason |String |Reason the proposal was invalid as-is (only
applicable in response to proposals)
|=======================================================================
If supported, a miner MAY propose a block to the server for general
validation at any point before the job expires. This is accomplished by
calling getblocktemplate with two keys:
[cols="",options="header",]
|=======================================================================
|colspan=3| getblocktemplate parameters
|Key |Type |Description
|data |String |MUST be hex-encoded block data
|mode |String |MUST be "proposal"
|workid |String |if the server provided a workid, it MUST be included
with proposals
|=======================================================================
The block data MUST be validated and checked against the server's usual
acceptance rules (excluding the check for a valid proof-of-work). If it
is found to be in violation of any of these rules, the server MUST
return one of the following:
* Null if it is acceptable as-is, with the same workid (if any) as
provided. Note that this SHOULD NOT invalidate the old template's claim
to the same workid.
* A String giving the reason for the rejection (see
link:bip-0022.mediawiki#appendix-example-rejection-reasons[example
rejection reasons]).
* A "delta" block template (with changes needed); in this case, any
missing keys are assumed to default to those in the proposed block or,
if not applicable, the original block template it was based on. This
template MAY also include a "reject-reason" key with a String of the
reason for rejection.
It is RECOMMENDED that servers which merely need to track the proposed
block for later share/* submissions, return a simple Object of the form:
`{"workid":"new workid"}`
Clients SHOULD assume their proposed block will remain valid if the only
changes they make are to the portion of the coinbase scriptSig they
themselves provided (if any) and the time header. Servers SHOULD NOT
break this assumption without good cause.
[[mutations]]
Mutations
^^^^^^^^^
[cols="",options="header",]
|=======================================================================
|template request
|Key |Type |Description
|nonces |Number |size of nonce range the miner needs; if not provided,
the server SHOULD assume the client requires 2^32^
|=======================================================================
[cols="",options="header",]
|=======================================================================
|colspan=3| template
|Key |Type |Description
|maxtime |Number |the maximum time allowed
|maxtimeoff |Number |the maximum time allowed (as a moving offset from
"curtime" - every second, the actual maxtime is incremented by 1; for
example, "maxtimeoff":0 means "time" may be incremented by 1 every
second)
|mintime |Number |the minimum time allowed
|mintimeoff |Number |the minimum time allowed (as a moving offset from
"curtime")
|mutable |Array of Strings |different manipulations that the server
explicitly allows to be made
|noncerange |String |two 32-bit integers, concatenated in big-endian
hexadecimal, which represent the valid ranges of nonces the miner may
scan
|=======================================================================
If the block template contains a "mutable" key, it is a list of these to
signify modifications the miner is allowed to make:
[cols="",options="header",]
|=======================================================================
|colspan=2| mutations
|Value |Significance
|coinbase/append |append the provided coinbase scriptSig
|coinbase |provide their own coinbase; if one is provided, it may be
replaced or modified (implied if "coinbasetxn" omitted)
|generation |add or remove outputs from the coinbase/generation
transaction (implied if "coinbasetxn" omitted)
|time/increment |change the time header to a value after "time" (implied
if "maxtime" or "maxtimeoff" are provided)
|time/decrement |change the time header to a value before "time"
(implied if "mintime" is provided)
|time |modify the time header of the block
|transactions/add (or "transactions") |add other valid transactions to
the block (implied if "transactions" omitted from result)
|prevblock |use the work with other previous-blocks; this implicitly
allows removing transactions that are no longer valid (but clients
SHOULD attempt to propose removal of any required transactions); it also
implies adjusting "height" as necessary
|version/force |encode the provide block version, even if the miner
doesn't understand it
|version/reduce |use an older block version than the one provided (for
example, if the client does not support the version provided)
|=======================================================================
[[submission-abbreviation]]
Submission Abbreviation
^^^^^^^^^^^^^^^^^^^^^^^
[cols="",options="header",]
|=======================================================================
|colspan=3| template
|Key |Type |Description
|fulltarget |String |the number which full results should be less than,
in big-endian hexadecimal (see "share/*" mutations)
|mutable |Array of Strings |different manipulations that the server
explicitly allows to be made, including abbreviations
|=======================================================================
If the block template contains a "mutable" key, it is a list of these to
signify modifications the miner is allowed to make:
[cols="",options="header",]
|=======================================================================
|colspan=2| abbreviation mutations
|Value |Significance
|submit/hash |each transaction being sent in a request, that the client
is certain the server knows about, may be replaced by its hash in
little-endian hexadecimal, prepended by a ":" character
|submit/coinbase |if the "transactions" provided by the server are used
as-is with no changes, submissions may omit transactions after the
coinbase (transaction count varint remains included with the full number
of transactions)
|submit/truncate |if the "coinbasetxn" and "transactions" provided by
the server are used as-is with no changes, submissions may contain only
the block header; if only the scriptSig of "coinbasetxn" is modified,
the params Object MUST contain a "coinbasesig" key with the content, or
a "coinbaseadd" with appended data (if only appending)
|share/coinbase |same as "submit/coinbase", but only if the block hash
is greater than "fulltarget"
|share/merkle |if the block hash is greater than "fulltarget", the
non-coinbase transactions may be replaced with a merkle chain connecting
it to the root
|share/truncate |same as "submit/truncate", but only if the block hash
is greater than "fulltarget"
|=======================================================================
[[format-of-data-for-merkle-only-shares]]
Format of Data for Merkle-Only Shares
+++++++++++++++++++++++++++++++++++++
The format used for submitting shares with the "share/merkle" mutation
shall be the 80-byte block header, the total number of transactions
encoded in Bitcoin variable length number format, the coinbase
transaction, and then finally the little-endian SHA256 hashes of each
link in the merkle chain connecting it to the merkle root.
[[logical-services]]
Logical Services
^^^^^^^^^^^^^^^^
[cols="",options="header",]
|=======================================================================
|template request
|Key |Type |Description
|capabilities |Array of Strings |miners which support this SHOULD
provide a list including the String "serverlist"
|=======================================================================
[cols="",options="header",]
|=======================================================================
|colspan=3| template
|Key |Type |Description
|serverlist |Array of Objects |list of servers in this single logical
service
|=======================================================================
If the "serverlist" parameter is provided, clients MAY choose to
intelligently treat the server as part of a larger single logical
service.
Each host Object in the Array is comprised of the following fields:
[cols="",options="header",]
|=======================================================================
|colspan=3| serverlist element
|Key |Type |Description
|uri |String |URI of the individual server; if authentication
information is omitted, the same authentication used for this request
MUST be assumed
|avoid |Number |number of seconds to avoid using this server
|priority |Number |an integer priority of this host (default: 0)
|sticky |Number |number of seconds to stick to this server when used
|update |Boolean |whether this server may update the serverlist
(default: true)
|weight |Number |a relative weight for hosts with the same priority
(default: 1)
|=======================================================================
When choosing which actual server to get the next job from, URIs MUST be
tried in order of their "priority" key, lowest Number first. Where the
priority of URIs is the same, they should be chosen from in random
order, weighed by their "weight" key. Work proposals and submissions
MUST be made to the same server that issued the job. Clients MAY attempt
to submit to other servers if, and only if, the original server cannot
be reached. If cross-server share submissions are desired, services
SHOULD instead use the equivalent domain name system (DNS) features
(RFCs http://tools.ietf.org/html/rfc1794[1794] and
http://tools.ietf.org/html/rfc2782[2782]).
Updates to the Logical Service server list may only be made by the
original server, or servers listed with the "update" key missing or
true. Clients MAY choose to advertise serverlist capability to servers
with a false "update" key, but if so, MUST treat the server list
provided as a subset of the current one, only considered in the context
of this server. At least one server with "update" privilege MUST be
attempted at least once daily.
If the "sticky" key is provided, then when that server is used, it
should be used consistently for at least that many seconds, if possible.
A permanent change in server URI MAY be indicated with a simple
"serverlist" parameter:
`"serverlist":[{"uri": "`http://newserver[`http://newserver`]`"}]`
A temporary delegation to another server for 5 minutes MAY be indicated
likewise:
`"serverlist":[{"uri": "", avoid: 300}, {"uri": "`http://newserver[`http://newserver`]`", "update": false}]`
[[motivation]]
Motivation
~~~~~~~~~~
There is reasonable concerns about mining currently being too
centralized on pools, and the amount of control these pools hold. By
exposing the details of the block proposals to the miners, they are
enabled to audit and possibly modify the block before hashing it.
To encourage widespread adoption, this BIP should be a complete superset
of the existing centralized getwork protocol, so pools are not required
to make substantial changes to adopt it.
[[rationale]]
Rationale
~~~~~~~~~
Why allow servers to restrict the complete coinbase and nonce range?
* This is necessary to provide a complete superset of JSON-RPC getwork
functionality, so that pools may opt to enable auditing without
significantly changing or increasing the complexity of their share
validation or mining policies.
* Since noncerange is optional (both for getwork and this BIP), neither
clients nor servers are required to support it.
Why specify "time/*" mutations at all?
* In most cases, these are implied by the
mintime/mintimecur/maxtime/maxtimecur keys, but there may be cases that
there are no applicable minimums/maximums.
What is the purpose of the "prevblock" mutation?
* There are often cases where a miner has processed a new block before
the server. If the server allows "prevblock" mutation, the miner may
begin mining on the new block immediately, without waiting for a new
template.
Why must both "mintime"/"maxtime" and "mintimeoff"/"maxtimeoff" keys be
defined?
* In some cases, the limits may be unrelated to the current time (such
as the Bitcoin network itself; the minimum is always a fixed median
time)
* In other cases, the limits may be bounded by other rules (many pools
limit the time header to within 5 minutes of when the share is submitted
to them).
Is "target" really needed?
* Some pools work with lower targets, and should not be expected to
waste bandwidth ignoring shares that don't meet it.
* Required to be a proper superset of getwork.
* As mining hashrates grow, some miners may need the ability to request
a lower target from their pools to be able to manage their bandwidth
use.
What is the purpose of the "hash" transaction list format?
* Non-mining tools may wish to simply get a list of memory pool
transactions.
* Humans may wish to view their current memory pool.
[[reference-implementation]]
Reference Implementation
~~~~~~~~~~~~~~~~~~~~~~~~
* http://gitorious.org/bitcoin/libblkmaker[libblkmaker]
* https://gitorious.org/bitcoin/eloipool[Eloipool]
* https://github.com/bitcoin/bitcoin/pull/936/files[bitcoind]
[[see-also]]
See Also
~~~~~~~~
* link:bip-0022.mediawiki[BIP 22: getblocktemplate - Fundamentals]
-------------------------------------------------
BIP: 30
Title: Duplicate transactions
Author: Pieter Wuille <[email protected]>
Status: Final
Type: Standards Track
Created: 2012-02-22
-------------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This document gives a specification for dealing with duplicate
transactions in the block chain, in an attempt to solve certain problems
the reference implementations has with them.
[[motivation]]
Motivation
~~~~~~~~~~
So far, the Bitcoin reference implementation always assumed duplicate
transactions (transactions with the same identifier) didn't exist. This
is not true; in particular coinbases are easy to duplicate, and by
building on duplicate coinbases, duplicate normal transactions are
possible as well. Recently, an attack that exploits the reference
implementation's dealing with duplicate transactions was described and
demonstrated. It allows reverting fully-confirmed transactions to a
single confirmation, making them vulnerable to become unspendable
entirely. Another attack is possible that allows forking the block chain
for a subset of the network.
[[specification]]
Specification
~~~~~~~~~~~~~
To counter this problem, the following network rule is introduced:
* Blocks are not allowed to contain a transaction whose identifier
matches that of an earlier, not-fully-spent transaction in the same
chain.
This rule initially applied to all blocks whose timestamp is after March
15, 2012, 00:00 UTC (testnet: February 20, 2012 00:00 UTC). It was later
extended by Commit
https://github.com/bitcoin/bitcoin/commit/ab91bf39b7c11e9c86bb2043c24f0f377f1cf514[Apply
BIP30 checks to all blocks except the two historic violations.] to apply
to all blocks except the two historic blocks at heights 91842 and 91880
on the main chain that had to be grandfathered in.
[[rationale]]
Rationale
~~~~~~~~~
Whatever solution is used, the following law must be obeyed to guarantee
sane behaviour: the set of usable transactions outputs must not be
modified by adding blocks to the chain and removing them again. This
happens during a reorganisation, and the current Bitcoin reference
implementation does not obey this law in case the temporarily added
blocks contain a duplicate transaction.
There are several potential solutions to this problem:
1. Guarantee that all coinbases are unique, making duplicate
transactions very hard to create.
2. Remember previous remaining outputs of a given transaction
identifier, in case a new transaction with the same identifier is added.
3. Only allow duplicate transactions in case the previous instance of
the transaction had no spendable outputs left. Removing a block from the
chain can then safely reset the removed transaction's outputs to
nothing.
The first option is probably the most complete one, as it also
guarantees transaction identifiers are unique. However, implementing it
requires several changes that need to be accepted throughout the
network. Furthermore, it does not prevent duplicate transactions based
on earlier duplicate coinbases. The second option is impossible to
implement in a forward-compatible way, as it potentially renders
currently-invalid blocks valid. In this document we choose for the third
option, because it only requires a trivial change.
Fully-spent transactions are allowed to be duplicated in order not to
hinder pruning at some point in the future. Not allowing any transaction
to be duplicated would require evidence to be kept for each transaction
ever made.
[[backward-compatibility]]
Backward compatibility
~~~~~~~~~~~~~~~~~~~~~~
The addition of this rule only makes some previously-valid blocks
invalid. This implies that if the rule is implemented by a supermajority
of miners, it is not possible to fork the block chain in a permanent way
between nodes with and without the new rule.
[[implementation]]
Implementation
~~~~~~~~~~~~~~
A patch for the reference client can be found on
https://github.com/sipa/bitcoin/tree/nooverwritetx
This BIP was implemented in Commit
https://github.com/bitcoin/bitcoin/commit/a206b0ea12eb4606b93323268fc81a4f1f952531[Do
not allow overwriting unspent transactions (BIP 30)] There have been
additional commits to refine the implementation of this BIP.
[[acknowledgements]]
Acknowledgements
~~~~~~~~~~~~~~~~
Thanks to Russell O'Connor for finding and demonstrating this problem,
and helping test the patch.
RECENT CHANGES:
* (16 Apr 2013) Added private derivation for i ≥ 0x80000000 (less risk
of parent private key leakage)
* (30 Apr 2013) Switched from multiplication by I~L~ to addition of I~L~
(faster, easier implementation)
* (25 May 2013) Added test vectors
* (15 Jan 2014) Rename keys with index ≥ 0x8000000 to hardened keys, and
add explicit conversion functions.
-------------------------------------------
BIP: 32
Title: Hierarchical Deterministic Wallets
Author: Pieter Wuille
Status: Accepted
Type: Informational
Created: 2012-02-11
-------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This document describes hierarchical determinstic wallets (or "HD
Wallets"): wallets which can be shared partially or entirely with
different systems, each with or without the ability to spend coins.
The specification is intended to set a standard for deterministic
wallets that can be interchanged between different clients. Although the
wallets described here have many features, not all are required by
supporting clients.
The specification consists of two parts. In a first part, a system for
deriving a tree of keypairs from a single seed is presented. The second
part demonstrates how to build a wallet structure on top of such a tree.
[[motivation]]
Motivation
~~~~~~~~~~
The Bitcoin reference client uses randomly generated keys. In order to
avoid the necessity for a backup after every transaction, (by default)
100 keys are cached in a pool of reserve keys. Still, these wallets are
not intended to be shared and used on several systems simultaneously.
They support hiding their private keys by using the wallet encrypt
feature and not sharing the password, but such "neutered" wallets lose
the power to generate public keys as well.
Deterministic wallets do not require such frequent backups, and elliptic
curve mathematics permit schemes where one can calculate the public keys
without revealing the private keys. This permits for example a webshop
business to let its webserver generate fresh addresses (public key
hashes) for each order or for each customer, without giving the
webserver access to the corresponding private keys (which are required
for spending the received funds).
However, deterministic wallets typically consist of a single "chain" of
keypairs. The fact that there is only one chain means that sharing a
wallet happens on an all-or-nothing basis. However, in some cases one
only wants some (public) keys to be shared and recoverable. In the
example of a webshop, the webserver does not need access to all public
keys of the merchant's wallet; only to those addresses which are used to
receive customer's payments, and not for example the change addresses
that are generated when the merchant spends money. Hierarchical
deterministic wallets allow such selective sharing by supporting
multiple keypair chains, derived from a single root.
[[specification-key-derivation]]
Specification: Key derivation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[[conventions]]
Conventions
^^^^^^^^^^^
In the rest of this text we will assume the public key cryptography used
in Bitcoin, namely elliptic curve cryptography using the field and curve
parameters defined by secp256k1
(http://www.secg.org/index.php?action=secg,docs_secg). Variables below
are either:
* Integers modulo the order of the curve (referred to as n).
* Coordinates of points on the curve.
* Byte sequences.
Addition (+) of two coordinate pair is defined as application of the EC
group operation. Concatenation (||) is the operation of appending one
byte sequence onto another.
As standard conversion functions, we assume:
* point(p): returns the coordinate pair resulting from EC point
multiplication (repeated application of the EC group operation) of the
secp256k1 base point with the integer p.
* ser~32~(i): serialize a 32-bit unsigned integer i as a 4-byte
sequence, most significant byte first.
* ser~256~(p): serializes the integer p as a 32-byte sequence, most
significant byte first.
* ser~P~(P): serializes the coordinate pair P = (x,y) as a byte sequence
using SEC1's compressed form: (0x02 or 0x03) || ser~256~(x), where the
header byte depends on the parity of the omitted y coordinate.
* parse~256~(p): interprets a 32-byte sequence as a 256-bit number, most
significant byte first.
[[extended-keys]]
Extended keys
^^^^^^^^^^^^^
In what follows, we will define a function that derives a number of
child keys from a parent key. In order to prevent these from depending
solely on the key itself, we extend both private and public keys first
with an extra 256 bits of entropy. This extension, called the chain
code, is identical for corresponding private and public keys, and
consists of 32 bytes.
We represent an extended private key as (k, c), with k the normal
private key, and c the chain code. An extended public key is represented
as (K, c), with K = point(k) and c the chain code.
Each extended key has 2^31^ normal child keys, and 2^31^ hardened child
keys. Each of these child keys has an index. The normal child keys use
indices 0 through 2^31^-1. The hardened child keys use indices 2^31^
through 2^32^-1. To ease notation for hardened key indices, a number
i~H~ represents i+2^31^.
[[child-key-derivation-ckd-functions]]
Child key derivation (CKD) functions
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Given a parent extended key and an index i, it is possible to compute
the corresponding child extended key. The algorithm to do so depends on
whether the child is a hardened key or not (or, equivalently, whether i
≥ 2^31^), and whether we're talking about private or public keys.
[[private-parent-key-private-child-key]]
Private parent key → private child key
++++++++++++++++++++++++++++++++++++++
The function CKDpriv((k~par~, c~par~), i) → (k~i~, c~i~) computes a
child extended private key from the parent extended private key:
* Check whether i ≥ 2^31^ (whether the child is a hardened key).
** If so (hardened child): let I = HMAC-SHA512(Key = c~par~, Data = 0x00
|| ser~256~(k~par~) || ser~32~(i)). (Note: The 0x00 pads the private key
to make it 33 bytes long.)
** If not (normal child): let I = HMAC-SHA512(Key = c~par~, Data =
ser~P~(point(k~par~)) || ser~32~(i)).
* Split I into two 32-byte sequences, I~L~ and I~R~.
* The returned child key k~i~ is parse~256~(I~L~) + k~par~ (mod n).
* The returned chain code c~i~ is I~R~.
* In case parse~256~(I~L~) ≥ n or k~i~ = 0, the resulting key is
invalid, and one should proceed with the next value for i. (Note: this
has probability lower than 1 in 2^127^.)
The HMAC-SHA512 function is specified in
http://tools.ietf.org/html/rfc4231[RFC 4231].
[[public-parent-key-public-child-key]]
Public parent key → public child key
++++++++++++++++++++++++++++++++++++
The function CKDpub((K~par~, c~par~), i) → (K~i~, c~i~) computes a child
extended public key from the parent extended public key. It is only
defined for non-hardened child keys.
* Check whether i ≥ 2^31^ (whether the child is a hardened key).
** If so (hardened child): return failure
** If not (normal child): let I = HMAC-SHA512(Key = c~par~, Data =
ser~P~(K~par~) || ser~32~(i)).
* Split I into two 32-byte sequences, I~L~ and I~R~.
* The returned child key K~i~ is point(parse~256~(I~L~)) + K~par~.
* The returned chain code c~i~ is I~R~.
* In case parse~256~(I~L~) ≥ n or K~i~ is the point at infinity, the
resulting key is invalid, and one should proceed with the next value for
i.
[[private-parent-key-public-child-key]]
Private parent key → public child key
+++++++++++++++++++++++++++++++++++++
The function N((k, c)) → (K, c) computes the extended public key
corresponding to an extended private key (the "neutered" version, as it
removes the ability to sign transactions).
* The returned key K is point(k).
* The returned chain code c is just the passed chain code.
To compute the public child key of a parent private key:
* N(CKDpriv((k~par~, c~par~), i)) (works always).
* CKDpub(N(k~par~, c~par~), i) (works only for non-hardened child keys).
The fact that they are equivalent is what makes non-hardened keys useful
(one can derive child public keys of a given parent key without knowing
any private key), and also what distinguishes them from hardened keys.
The reason for not always using non-hardened keys (which are more
useful) is security; see further for more information.
[[public-parent-key-private-child-key]]
Public parent key → private child key
+++++++++++++++++++++++++++++++++++++
This is not possible.
[[the-key-tree]]
The key tree
^^^^^^^^^^^^
The next step is cascading several CKD constructions to build a tree. We
start with one root, the master extended key m. By evaluating
CKDpriv(m,i) for several values of i, we get a number of level-1 derived
nodes. As each of these is again an extended key, CKDpriv can be applied
to those as well.
To shorten notation, we will write CKDpriv(CKDpriv(CKDpriv(m,3~H~),2),5)
as m/3~H~/2/5. Equivalently for public keys, we write
CKDpub(CKDpub(CKDpub(M,3),2,5) as M/3/2/5. This results in the following
identities:
* N(m/a/b/c) = N(m/a/b)/c = N(m/a)/b/c = N(m)/a/b/c = M/a/b/c.
* N(m/a~H~/b/c) = N(m/a~H~/b)/c = N(m/a~H~)/b/c.
However, N(m/a~H~) cannot be rewritten as N(m)/a~H~, as the latter is
not possible.
Each leaf node in the tree corresponds to an actual key, while the
internal nodes correspond to the collections of keys that descend from
them. The chain codes of the leaf nodes are ignored, and only their
embedded private or public key is relevant. Because of this
construction, knowing an extended private key allows reconstruction of
all descendant private keys and public keys, and knowing an extended
public keys allows reconstruction of all descendant non-hardened public
keys.
[[key-identifiers]]
Key identifiers
^^^^^^^^^^^^^^^
Extended keys can be identified by the Hash160 (RIPEMD160 after SHA256)
of the serialized public key, ignoring the chain code. This corresponds
exactly to the data used in traditional Bitcoin addresses. It is not
advised to represent this data in base58 format though, as it may be
interpreted as an address that way (and wallet software is not required
to accept payment to the chain key itself).
The first 32 bits of the identifier are called the key fingerprint.
[[serialization-format]]
Serialization format
^^^^^^^^^^^^^^^^^^^^
Extended public and private keys are serialized as follows:
* 4 byte: version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private;
testnet: 0x043587CF public, 0x04358394 private)
* 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys,
....
* 4 bytes: the fingerprint of the parent's key (0x00000000 if master
key)
* 4 bytes: child number. This is ser~32~(i) for i in x~i~ = x~par~/i,
with x~i~ the key being serialized. (0x00000000 if master key)
* 32 bytes: the chain code
* 33 bytes: the public key or private key data (ser~P~(K) for public
keys, 0x00 || ser~256~(k) for private keys)
This 78 byte structure can be encoded like other Bitcoin data in Base58,
by first adding 32 checksum bits (derived from the double SHA-256
checksum), and then converting to the Base58 representation. This
results in a Base58-encoded string of up to 112 characters. Because of
the choice of the version bytes, the Base58 representation will start
with "xprv" or "xpub" on mainnet, "tprv" or "tpub" on testnet.
Note that the fingerprint of the parent only serves as a fast way to
detect parent and child nodes in software, and software must be willing
to deal with collisions. Internally, the full 160-bit identifier could
be used.
When importing a serialized extended public key, implementations must
verify whether the X coordinate in the public key data corresponds to a
point on the curve. If not, the extended public key is invalid.
[[master-key-generation]]
Master key generation
^^^^^^^^^^^^^^^^^^^^^
The total number of possible extended keypairs is almost 2^512^, but the
produced keys are only 256 bits long, and offer about half of that in
terms of security. Therefore, master keys are not generated directly,
but instead from a potentially short seed value.
* Generate a seed byte sequence S of a chosen length (between 128 and
512 bits; 256 bits is advised) from a (P)RNG.
* Calculate I = HMAC-SHA512(Key = "Bitcoin seed", Data = S)
* Split I into two 32-byte sequences, I~L~ and I~R~.
* Use parse~256~(I~L~) as master secret key, and I~R~ as master chain
code.
In case I~L~ is 0 or ≥n, the master key is invalid.
[[specification-wallet-structure]]
Specification: Wallet structure
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The previous sections specified key trees and their nodes. The next step
is imposing a wallet structure on this tree. The layout defined in this
section is a default only, though clients are encouraged to mimick it
for compatibility, even if not all features are supported.
[[the-default-wallet-layout]]
The default wallet layout
^^^^^^^^^^^^^^^^^^^^^^^^^
An HDW is organized as several 'accounts'. Accounts are numbered, the
default account ("") being number 0. Clients are not required to support
more than one account - if not, they only use the default account.
Each account is composed of two keypair chains: an internal and an
external one. The external keychain is used to generate new public
addresses, while the internal keychain is used for all other operations
(change addresses, generation addresses, ..., anything that doesn't need
to be communicated). Clients that do not support separate keychains for
these should use the external one for everything.
* m/i~H~/0/k corresponds to the k'th keypair of the external chain of
account number i of the HDW derived from master m.
* m/i~H~/1/k corresponds to the k'th keypair of the internal chain of
account number i of the HDW derived from master m.
[[use-cases]]
Use cases
^^^^^^^^^
[[full-wallet-sharing-m]]
Full wallet sharing: m
++++++++++++++++++++++
In cases where two systems need to access a single shared wallet, and
both need to be able to perform spendings, one needs to share the master
private extended key. Nodes can keep a pool of N look-ahead keys cached
for external chains, to watch for incoming payments. The look-ahead for
internal chains can be very small, as no gaps are to be expected here.
An extra look-ahead could be active for the first unused account's
chains - triggering the creation of a new account when used. Note that
the name of the account will still need to be entered manually and
cannot be synchronized via the block chain.
[[audits-nm]]
Audits: N(m/*)
++++++++++++++
In case an auditor needs full access to the list of incoming and
outgoing payments, one can share all account public extended keys. This
will allow the auditor to see all transactions from and to the wallet,
in all accounts, but not a single secret key.
[[per-office-balances-mih]]
Per-office balances: m/i~H~
+++++++++++++++++++++++++++
When a business has several independent offices, they can all use
wallets derived from a single master. This will allow the headquarters
to maintain a super-wallet that sees all incoming and outgoing
transactions of all offices, and even permit moving money between the
offices.
[[recurrent-business-to-business-transactions-nmih0]]
Recurrent business-to-business transactions: N(m/i~H~/0)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
In case two business partners often transfer money, one can use the
extended public key for the external chain of a specific account (M/i
h/0) as a sort of "super address", allowing frequent transactions that
cannot (easily) be associated, but without needing to request a new
address for each payment. Such a mechanism could also be used by mining
pool operators as variable payout address.
[[unsecure-money-receiver-nmih0]]
Unsecure money receiver: N(m/i~H~/0)
++++++++++++++++++++++++++++++++++++
When an unsecure webserver is used to run an e-commerce site, it needs
to know public addresses that are used to receive payments. The
webserver only needs to know the public extended key of the external
chain of a single account. This means someone illegally obtaining access
to the webserver can at most see all incoming payments, but will not
(trivially) be able to distinguish outgoing transactions, nor see
payments received by other webservers if there are several ones.
[[compatibility]]
Compatibility
~~~~~~~~~~~~~
To comply with this standard, a client must at least be able to import
an extended public or private key, to give access to its direct
descendants as wallet keys. The wallet structure
(master/account/chain/subchain) presented in the second part of the
specification is advisory only, but is suggested as a minimal structure
for easy compatibility - even when no separate accounts or distinction
between internal and external chains is made. However, implementations
may deviate from it for specific needs; more complex applications may
call for a more complex tree structure.
[[security]]
Security
~~~~~~~~
In addition to the expectations from the EC public-key cryptography
itself:
* Given a public key K, an attacker cannot find the corresponding
private key more efficiently than by solving the EC discrete logarithm
problem (assumed to require 2^128^ group operations).
the intended security properties of this standard are:
* Given a child extended private key (k~i~,c~i~) and the integer i, an
attacker cannot find the parent private key k~par~ more efficiently than
a 2^256^ brute force of HMAC-SHA512.
* Given any number (2 ≤ N ≤ 2^32^-1) of (index, extended private key)
tuples (i~j~,(k~i~j~~,c~i~j~~)), with distinct i~j~'s, determining
whether they are derived from a common parent extended private key
(i.e., whether there exists a (k~par~,c~par~) such that for each j in
(0..N-1) CKDpriv((k~par~,c~par~),i~j~)=(k~i~j~~,c~i~j~~)), cannot be
done more efficiently than a 2^256^ brute force of HMAC-SHA512.
Note however that the following properties does not exist:
* Given a parent extended public key (K~par~,c~par~) and a child public
key (K~i~), it is hard to find i.
* Given a parent extended public key (K~par~,c~par~) and a non-hardened
child private key (k~i~), it is hard to find k~par~.
[[implications]]
Implications
^^^^^^^^^^^^
Private and public keys must be kept safe as usual. Leaking a private
key means access to coins - leaking a public key can mean loss of
privacy.
Somewhat more care must be taken regarding extended keys, as these
correspond to an entire (sub)tree of keys.
One weakness that may not be immediately obvious, is that knowledge of
the extended public key + any non-hardened private key descending from
it is equivalent to knowing the extended private key (and thus every
private and public key descending from it). This means that extended
public keys must be treated more carefully than regular public keys. It
is also the reason for the existence of hardened keys, and why they are
used for the account level in the tree. This way, a leak of
account-specific (or below) private key never risks compromising the
master or other accounts.
[[test-vectors]]
Test Vectors
~~~~~~~~~~~~
[[test-vector-1]]
Test vector 1
^^^^^^^^^^^^^
Master (hex): 000102030405060708090a0b0c0d0e0f
* Chain m
** ext pub:
xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8
** ext prv:
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
* Chain m/0~H~
** ext pub:
xpub68Gmy5EdvgibQVfPdqkBBCHxA5htiqg55crXYuXoQRKfDBFA1WEjWgP6LHhwBZeNK1VTsfTFUHCdrfp1bgwQ9xv5ski8PX9rL2dZXvgGDnw
** ext prv:
xprv9uHRZZhk6KAJC1avXpDAp4MDc3sQKNxDiPvvkX8Br5ngLNv1TxvUxt4cV1rGL5hj6KCesnDYUhd7oWgT11eZG7XnxHrnYeSvkzY7d2bhkJ7
* Chain m/0~H~/1
** ext pub:
xpub6ASuArnXKPbfEwhqN6e3mwBcDTgzisQN1wXN9BJcM47sSikHjJf3UFHKkNAWbWMiGj7Wf5uMash7SyYq527Hqck2AxYysAA7xmALppuCkwQ
** ext prv:
xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs
* Chain m/0~H~/1/2~H~
** ext pub:
xpub6D4BDPcP2GT577Vvch3R8wDkScZWzQzMMUm3PWbmWvVJrZwQY4VUNgqFJPMM3No2dFDFGTsxxpG5uJh7n7epu4trkrX7x7DogT5Uv6fcLW5
** ext prv:
xprv9z4pot5VBttmtdRTWfWQmoH1taj2axGVzFqSb8C9xaxKymcFzXBDptWmT7FwuEzG3ryjH4ktypQSAewRiNMjANTtpgP4mLTj34bhnZX7UiM
* Chain m/0~H~/1/2~H~/2
** ext pub:
xpub6FHa3pjLCk84BayeJxFW2SP4XRrFd1JYnxeLeU8EqN3vDfZmbqBqaGJAyiLjTAwm6ZLRQUMv1ZACTj37sR62cfN7fe5JnJ7dh8zL4fiyLHV
** ext prv:
xprvA2JDeKCSNNZky6uBCviVfJSKyQ1mDYahRjijr5idH2WwLsEd4Hsb2Tyh8RfQMuPh7f7RtyzTtdrbdqqsunu5Mm3wDvUAKRHSC34sJ7in334
* Chain m/0~H~/1/2~H~/2/1000000000
** ext pub:
xpub6H1LXWLaKsWFhvm6RVpEL9P4KfRZSW7abD2ttkWP3SSQvnyA8FSVqNTEcYFgJS2UaFcxupHiYkro49S8yGasTvXEYBVPamhGW6cFJodrTHy
** ext prv:
xprvA41z7zogVVwxVSgdKUHDy1SKmdb533PjDz7J6N6mV6uS3ze1ai8FHa8kmHScGpWmj4WggLyQjgPie1rFSruoUihUZREPSL39UNdE3BBDu76
[[test-vector-2]]
Test vector 2
^^^^^^^^^^^^^
Master (hex):
fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542
* Chain m
** ext pub:
xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB
** ext prv:
xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U
* Chain m/0
** ext pub:
xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7ERfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH
** ext prv:
xprv9vHkqa6EV4sPZHYqZznhT2NPtPCjKuDKGY38FBWLvgaDx45zo9WQRUT3dKYnjwih2yJD9mkrocEZXo1ex8G81dwSM1fwqWpWkeS3v86pgKt
* Chain m/0/2147483647~H~
** ext pub:
xpub6ASAVgeehLbnwdqV6UKMHVzgqAG8Gr6riv3Fxxpj8ksbH9ebxaEyBLZ85ySDhKiLDBrQSARLq1uNRts8RuJiHjaDMBU4Zn9h8LZNnBC5y4a
** ext prv:
xprv9wSp6B7kry3Vj9m1zSnLvN3xH8RdsPP1Mh7fAaR7aRLcQMKTR2vidYEeEg2mUCTAwCd6vnxVrcjfy2kRgVsFawNzmjuHc2YmYRmagcEPdU9
* Chain m/0/2147483647~H~/1
** ext pub:
xpub6DF8uhdarytz3FWdA8TvFSvvAh8dP3283MY7p2V4SeE2wyWmG5mg5EwVvmdMVCQcoNJxGoWaU9DCWh89LojfZ537wTfunKau47EL2dhHKon
** ext prv:
xprv9zFnWC6h2cLgpmSA46vutJzBcfJ8yaJGg8cX1e5StJh45BBciYTRXSd25UEPVuesF9yog62tGAQtHjXajPPdbRCHuWS6T8XA2ECKADdw4Ef
* Chain m/0/2147483647~H~/1/2147483646~H~
** ext pub:
xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL
** ext prv:
xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc
* Chain m/0/2147483647~H~/1/2147483646~H~/2
** ext pub:
xpub6FnCn6nSzZAw5Tw7cgR9bi15UV96gLZhjDstkXXxvCLsUXBGXPdSnLFbdpq8p9HmGsApME5hQTZ3emM2rnY5agb9rXpVGyy3bdW6EEgAtqt
** ext prv:
xprvA2nrNbFZABcdryreWet9Ea4LvTJcGsqrMzxHx98MMrotbir7yrKCEXw7nadnHM8Dq38EGfSh6dqA9QWTyefMLEcBYJUuekgW4BYPJcr9E7j
[[implementations]]
Implementations
~~~~~~~~~~~~~~~
Two Python implementations exist:
PyCoin (https://github.com/richardkiss/pycoin) is a suite of utilities
for dealing with Bitcoin that includes BIP0032 wallet features.
BIP32Utils (https://github.com/jmcorgan/bip32utils) is a library and
command line interface specifically focused on BIP0032 wallets and
scripting.
A Java implementation is available at
https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java
A C++ implementation is available at
https://github.com/CodeShark/CoinClasses/tree/master/tests/hdwallets
An Objective-C implementation is available at
https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCKeychain.h
A Ruby implementation is available at https://github.com/wink/money-tree
A Go implementation is available at
https://github.com/WeMeetAgain/go-hdwallet
A JavaScript implementation is available at
https://github.com/sarchar/brainwallet.github.com/tree/bip32
A PHP implemetation is available at
https://github.com/Bit-Wasp/bitcoin-lib-php
A C# implementation is available at
https://github.com/NicolasDorier/NBitcoin (ExtKey, ExtPubKey)
[[acknowledgements]]
Acknowledgements
~~~~~~~~~~~~~~~~
* Gregory Maxwell for the original idea of type-2 deterministic wallets,
and many discussions about it.
* Alan Reiner for the implementation of this scheme in Armory, and the
suggestions that followed from that.
* Mike Caldwell for the version bytes to obtain human-recognizable
Base58 strings.
BIP: 34 Title: Block v2, Height in Coinbase Author: Gavin Andresen <[email protected]> Status: Accepted Type: Standards Track Created: 2012-07-06
[[abstract]]
Abstract
~~~~~~~~
Bitcoin blocks and transactions are versioned binary structures. Both
currently use version 1. This BIP introduces an upgrade path for
versioned transactions and blocks. A unique value is added to newly
produced coinbase transactions, and blocks are updated to version 2.
[[motivation]]
Motivation
~~~~~~~~~~
1. Clarify and exercise the mechanism whereby the bitcoin network
collectively consents to upgrade transaction or block binary structures,
rules and behaviors.
2. Enforce block and transaction uniqueness, and assist unconnected
block validation.
[[specification]]
Specification
~~~~~~~~~~~~~
1. Treat transactions with a version greater than 1 as non-standard
(official Satoshi client will not mine or relay them).
2. Add height as the first item in the coinbase transaction's
scriptSig, and increase block version to 2. The format of the height is
"serialized CScript" -- first byte is number of bytes in the number
(will be 0x03 on main net for the next 300 or so years), following bytes
are little-endian representation of the number. Height is the height of
the mined block in the block chain, where the genesis block is height
zero (0).
3. 75% rule: If 750 of the last 1,000 blocks are version 2 or greater,
reject invalid version 2 blocks. (testnet3: 51 of last 100)
4. 95% rule ("Point of no return"): If 950 of the last 1,000 blocks are
version 2 or greater, reject all version 1 blocks. (testnet3: 75 of last
100)
[[backward-compatibility]]
Backward compatibility
~~~~~~~~~~~~~~~~~~~~~~
All older clients are compatible with this change. Users and merchants
should not be impacted. Miners are strongly recommended to upgrade to
version 2 blocks. Once 95% of the miners have upgraded to version 2, the
remainder will be orphaned if they fail to upgrade.
[[implementation]]
Implementation
~~~~~~~~~~~~~~
https://github.com/bitcoin/bitcoin/pull/1526
-------------------------------------------
BIP: 35
Title: mempool message
Author: Jeff Garzik <[email protected]>
Status: Accepted
Type: Standards Track
Created: 2012-08-16
-------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
Make a network node's transaction memory pool accessible via a new
"mempool" message. Extend the existing "getdata" message behavior to
permit accessing the transaction memory pool.
[[motivation]]
Motivation
~~~~~~~~~~
Several use cases make it desireable to expose a network node's
transaction memory pool:
1. SPV clients, wishing to obtain zero-confirmation transactions sent
or received.
2. Miners, to avoid missing lucrative fees, downloading existing
network transactions after a restart.
3. Remote network diagnostics.
[[specification]]
Specification
~~~~~~~~~~~~~
1. The mempool message is defined as an empty message where pchCommand
== "mempool"
2. Upon receipt of a "mempool" message, the node will respond with an
"inv" message containing MSG_TX hashes of all the transactions in the
node's transaction memory pool, if any.
3. The typical node behavior in response to an "inv" is "getdata".
However, the reference Satoshi implementation ignores requests for
transaction hashes outside that which is recently relayed. To support
"mempool", an implementation must extend its "getdata" message support
to querying the memory pool.
4. Feature discovery is enabled by checking two "version" message
attributes:
1. Protocol version >= 60002
2. NODE_NETWORK bit set in nServices
Note that existing implementations drop "inv" messages with a vector
size > 50000.
[[backward-compatibility]]
Backward compatibility
~~~~~~~~~~~~~~~~~~~~~~
Older clients remain 100% compatible and interoperable after this
change.
[[implementation]]
Implementation
~~~~~~~~~~~~~~
https://github.com/bitcoin/bitcoin/pull/1641
-----------------------------------------------------------------------
BIP: 37
Title: Connection Bloom filtering
Author: Mike Hearn <[email protected]>, Matt Corallo <[email protected]>
Status: Accepted
Type: Standards Track
Created: 2012-10-24
-----------------------------------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This BIP adds new support to the peer-to-peer protocol that allows peers
to reduce the amount of transaction data they are sent. Peers have the
option of setting _filters_ on each connection they make after the
version handshake has completed. A filter is defined as a
http://en.wikipedia.org/wiki/Bloom_filter[Bloom filter] on data derived
from transactions. A Bloom filter is a probabilistic data structure
which allows for testing set membership - they can have false positives
but not false negatives.
This document will not go into the details of how Bloom filters work and
the reader is referred to Wikipedia for an introduction to the topic.
[[motivation]]
Motivation
~~~~~~~~~~
As Bitcoin grows in usage the amount of bandwidth needed to download
blocks and transaction broadcasts increases. Clients implementing
_simplified payment verification_ do not attempt to fully verify the
block chain, instead just checking that block headers connect together
correctly and trusting that the transactions in a chain of high
difficulty are in fact valid. See the Bitcoin paper for more detail on
this mode.
Today, link:Simplified_Payment_Verification[SPV] clients have to
download the entire contents of blocks and all broadcast transactions,
only to throw away the vast majority of the transactions that are not
relevant to their wallets. This slows down their synchronization
process, wastes users bandwidth (which on phones is often metered) and
increases memory usage. All three problems are triggering real user
complaints for the Android "Bitcoin Wallet" app which implements SPV
mode. In order to make chain synchronization fast, cheap and able to run
on older phones with limited memory we want to have remote peers throw
away irrelevant transactions before sending them across the network.
[[design-rationale]]
Design rationale
~~~~~~~~~~~~~~~~
The most obvious way to implement the stated goal would be for clients
to upload lists of their keys to the remote node. We take a more complex
approach for the following reasons:
* Privacy: Because Bloom filters are probabilistic, with the false
positive rate chosen by the client, nodes can trade off precision vs
bandwidth usage. A node with access to lots of bandwidth may choose to
have a high FP rate, meaning the remote peer cannot accurately know
which transactions belong to the client and which don't. A node with
very little bandwidth may choose to use a very accurate filter meaning
that they only get sent transactions actually relevant to their wallet,
but remote peers may be able to correlate transactions with IP addresses
(and each other).
* Bloom filters are compact and testing membership in them is fast. This
results in satisfying performance characteristics with minimal risk of
opening up potential for DoS attacks.
[[specification]]
Specification
~~~~~~~~~~~~~
[[new-messages]]
New messages
^^^^^^^^^^^^
We start by adding three new messages to the protocol:
* `filterload`, which sets the current Bloom filter on the connection
* `filteradd`, which adds the given data element to the connections
current filter without requiring a completely new one to be set
* `filterclear`, which deletes the current filter and goes back to
regular pre-BIP37 usage.
Note that there is no filterremove command because by their nature,
Bloom filters are append-only data structures. Once an element is added
it cannot be removed again without rebuilding the entire structure from
scratch.
The `filterload` command is defined as follows:
[cols=",,,",options="header",]
|=======================================================================
|Field Size |Description |Data type |Comments
|? |filter |uint8_t[] |The filter itself is simply a bit field of
arbitrary byte-aligned size. The maximum size is 36,000 bytes.
|4 |nHashFuncs |uint32_t |The number of hash functions to use in this
filter. The maximum value allowed in this field is 50.
|4 |nTweak |uint32_t |A random value to add to the seed value in the
hash function used by the bloom filter.
|1 |nFlags |uint8_t |A set of flags that control how matched items are
added to the filter.
|=======================================================================
See below for a description of the Bloom filter algorithm and how to
select nHashFuncs and filter size for a desired false positive rate.
Upon receiving a `filterload` command, the remote peer will immediately
restrict the broadcast transactions it announces (in inv packets) to
transactions matching the filter, where the matching algorithm is
specified below. The flags control the update behaviour of the matching
algorithm.
The `filteradd` command is defined as follows:
[cols=",,,",options="header",]
|==================================================================
|Field Size |Description |Data type |Comments
|? |data |uint8_t[] |The data element to add to the current filter.
|==================================================================
The data field must be smaller than or equal to 520 bytes in size (the
maximum size of any potentially matched object).
The given data element will be added to the Bloom filter. A filter must
have been previously provided using `filterload`. This command is useful
if a new key or script is added to a clients wallet whilst it has
connections to the network open, it avoids the need to re-calculate and
send an entirely new filter to every peer (though doing so is usually
advisable to maintain anonymity).
The `filterclear` command has no arguments at all.
After a filter has been set, nodes don't merely stop announcing
non-matching transactions, they can also serve filtered blocks. A
filtered block is defined by the `merkleblock` message and is defined
like this:
[cols=",,,",options="header",]
|=======================================================================
|Field Size |Description |Data type |Comments
|4 |version |uint32_t |Block version information, based upon the
software version creating this block
|32 |prev_block |char[32] |The hash value of the previous block this
particular block references
|32 |merkle_root |char[32] |The reference to a Merkle tree collection
which is a hash of all transactions related to this block
|4 |timestamp |uint32_t |A timestamp recording when this block was
created (Limited to 2106!)
|4 |bits |uint32_t |The calculated difficulty target being used for this
block
|4 |nonce |uint32_t |The nonce used to generate this block… to allow
variations of the header and compute different hashes
|4 |total_transactions |uint32_t |Number of transactions in the block
(including unmatched ones)
|? |hashes |uint256[] |hashes in depth-first order (including standard
varint size prefix)
|? |flags |byte[] |flag bits, packed per 8 in a byte, least significant
bit first (including standard varint size prefix)
|=======================================================================
See below for the format of the partial merkle tree hashes and flags.
Thus, a `merkleblock` message is a block header, plus a part of a merkle
tree which can be used to extract identifying information for
transactions that matched the filter and prove that the matching
transaction data really did appear in the solved block. Clients can use
this data to be sure that the remote node is not feeding them fake
transactions that never appeared in a real block, although lying through
omission is still possible.
[[extensions-to-existing-messages]]
Extensions to existing messages
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The `version` command is extended with a new field:
[cols=",,,",options="header",]
|=======================================================================
|Field Size |Description |Data type |Comments
|1 byte |fRelay |bool |If false then broadcast transactions will not be
announced until a filter\{load,add,clear} command is received. If
missing or true, no change in protocol behaviour occurs.
|=======================================================================
SPV clients that wish to use Bloom filtering would normally set fRelay
to false in the version message, then set a filter based on their wallet
(or a subset of it, if they are overlapping different peers). Being able
to opt-out of inv messages until the filter is set prevents a client
being flooded with traffic in the brief window of time between finishing
version handshaking and setting the filter.
The `getdata` command is extended to allow a new type in the `inv`
submessage. The type field can now be `MSG_FILTERED_BLOCK (== 3)` rather
than `MSG_BLOCK`. If no filter has been set on the connection, a request
for filtered blocks is ignored. If a filter has been set, a
`merkleblock` message is returned for the requested block hash. In
addition, because a `merkleblock` message contains only a list of
transaction hashes, transactions matching the filter should also be sent
in separate tx messages after the merkleblock is sent. This avoids a
slow roundtrip that would otherwise be required (receive hashes, didn't
see some of these transactions yet, ask for them). Note that because
there is currently no way to request transactions which are already in a
block from a node (aside from requesting the full block), the set of
matching transactions that the requesting node hasn't either received or
announced with an inv must be sent and any additional transactions which
match the filter may also be sent. This allows for clients (such as the
reference client) to limit the number of invs it must remember a given
node to have announced while still providing nodes with, at a minimum,
all the transactions it needs.
[[filter-matching-algorithm]]
Filter matching algorithm
^^^^^^^^^^^^^^^^^^^^^^^^^
The filter can be tested against arbitrary pieces of data, to see if
that data was inserted by the client. Therefore the question arises of
what pieces of data should be inserted/tested.
To determine if a transaction matches the filter, the following
algorithm is used. Once a match is found the algorithm aborts.
1. Test the hash of the transaction itself.
2. For each output, test each data element of the output script. This
means each hash and key in the output script is tested independently.
*Important:* if an output matches whilst testing a transaction, the node
might need to update the filter by inserting the serialized COutPoint
structure. See below for more details.
3. For each input, test the serialized COutPoint structure.
4. For each input, test each data element of the input script (note:
input scripts only ever contain data elements).
5. Otherwise there is no match.
In this way addresses, keys and script hashes (for P2SH outputs) can all
be added to the filter. You can also match against classes of
transactions that are marked with well known data elements in either
inputs or outputs, for example, to implement various forms of
link:Smart property[Smart property].
The test for outpoints is there to ensure you can find transactions
spending outputs in your wallet, even though you don't know anything
about their form. As you can see, once set on a connection the filter is
*not static* and can change throughout the connections lifetime. This is
done to avoid the following race condition:
1. A client sets a filter matching a key in their wallet. They then
start downloading the block chain. The part of the chain that the client
is missing is requested using getblocks.
2. The first block is read from disk by the serving peer. It contains
TX 1 which sends money to the clients key. It matches the filter and is
thus sent to the client.
3. The second block is read from disk by the serving peer. It contains
TX 2 which spends TX 1. However TX 2 does not contain any of the clients
keys and is thus not sent. The client does not know the money they
received was already spent.
By updating the bloom filter atomically in step 2 with the discovered
outpoint, the filter will match against TX 2 in step 3 and the client
will learn about all relevant transactions, despite that there is no
pause between the node processing the first and second blocks.
The nFlags field of the filter controls the nodes precise update
behaviour and is a bit field.
* `BLOOM_UPDATE_NONE (0)` means the filter is not adjusted when a match
is found.
* `BLOOM_UPDATE_ALL (1)` means if the filter matches any data element in
a scriptPubKey the outpoint is serialized and inserted into the filter.
* `BLOOM_UPDATE_P2PUBKEY_ONLY (2)` means the outpoint is inserted into
the filter only if a data element in the scriptPubKey is matched, and
that script is of the standard "pay to pubkey" or "pay to multisig"
forms.
These distinctions are useful to avoid too-rapid degradation of the
filter due to an increasing false positive rate. We can observe that a
wallet which expects to receive only payments of the standard
pay-to-address form doesn't need automatic filter updates because any
transaction that spends one of its own outputs has a predictable data
element in the input (the pubkey that hashes to the address). If a
wallet might receive pay-to-address outputs and also pay-to-pubkey or
pay-to-multisig outputs then BLOOM_UPDATE_P2PUBKEY_ONLY is appropriate,
as it avoids unnecessary expansions of the filter for the most common
types of output but still ensures correct behaviour with payments that
explicitly specify keys.
Obviously, nFlags == 1 or nFlags == 2 mean that the filter will get
dirtier as more of the chain is scanned. Clients should monitor the
observed false positive rate and periodically refresh the filter with a
clean one.
[[partial-merkle-branch-format]]
Partial Merkle branch format
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
A _Merkle tree_ is a way of arranging a set of items as leaf nodes of
tree in which the interior nodes are hashes of the concatenations of
their child hashes. The root node is called the _Merkle root_. Every
Bitcoin block contains a Merkle root of the tree formed from the blocks
transactions. By providing some elements of the trees interior nodes
(called a _Merkle branch_) a proof is formed that the given transaction
was indeed in the block when it was being mined, but the size of the
proof is much smaller than the size of the original block.
[[constructing-a-partial-merkle-tree-object]]
Constructing a partial merkle tree object
+++++++++++++++++++++++++++++++++++++++++
* Traverse the merkle tree from the root down, and for each encountered
node:
** Check whether this node corresponds to a leaf node (transaction) that
is to be included OR any parent thereof:
*** If so, append a '1' bit to the flag bits
*** Otherwise, append a '0' bit.
** Check whether this node is a internal node (non-leaf) AND is the
parent of an included leaf node:
*** If so:
**** Descend into its left child node, and process the subtree beneath
it entirely (depth-first).
**** If this node has a right child node too, descend into it as well.
*** Otherwise: append this node's hash to the hash list.
[[parsing-a-partial-merkle-tree-object]]
Parsing a partial merkle tree object
++++++++++++++++++++++++++++++++++++
As the partial block message contains the number of transactions in the
entire block, the shape of the merkle tree is known before hand. Again,
traverse this tree, computing traversed node's hashes along the way:
* Read a bit from the flag bit list:
** If it is '0':
*** Read a hash from the hashes list, and return it as this node's hash.
** If it is '1' and this is a leaf node:
*** Read a hash from the hashes list, store it as a matched txid, and
return it as this node's hash.
** If it is '1' and this is an internal node:
*** Descend into its left child tree, and store its computed hash as L.
*** If this node has a right child as well:
**** Descend into its right child, and store its computed hash as R.
**** If L == R, the partial merkle tree object is invalid.
**** Return Hash(L || R).
*** If this node has no right child, return Hash(L || L).
The partial merkle tree object is only valid if:
* All hashes in the hash list were consumed and no more.
* All bits in the flag bits list were consumed (except padding to make
it into a full byte), and no more.
* The hash computed for the root node matches the block header's merkle
root.
* The block header is valid, and matches its claimed proof of work.
* In two-child nodes, the hash of the left and right branches was never
equal.
[[bloom-filter-format]]
Bloom filter format
^^^^^^^^^^^^^^^^^^^
A Bloom filter is a bit-field in which bits are set based on feeding the
data element to a set of different hash functions. The number of hash
functions used is a parameter of the filter. In Bitcoin we use version 3
of the 32-bit Murmur hash function. To get N "different" hash functions
we simply initialize the Murmur algorithm with the following formula:
`nHashNum * 0xFBA4C795 + nTweak`
i.e. if the filter is initialized with 4 hash functions and a tweak of
0x00000005, when the second function (index 1) is needed h1 would be
equal to 4221880218.
When loading a filter with the `filterload` command, there are two
parameters that can be chosen. One is the size of the filter in bytes.
The other is the number of hash functions to use. To select the
parameters you can use the following formulas:
Let N be the number of elements you wish to insert into the set and P be
the probability of a false positive, where 1.0 is "match everything" and
zero is unachievable.
The size S of the filter in bytes is given by
`(-1 / pow(log(2), 2) * N * log(P)) / 8`. Of course you must ensure it
does not go over the maximum size (36,000: selected as it represents a
filter of 20,000 items with false positive rate of < 0.1% or 10,000
items and a false positive rate of < 0.0001%).
The number of hash functions required is given by `S * 8 / N * log(2)`.
[[copyright]]
Copyright
~~~~~~~~~
This document is placed in the public domain.
----------------------------------------------------------------------------------------------------------------------------------
BIP: 38
Title: Passphrase-protected private key
Authors: Mike Caldwell
Aaron Voisine <[email protected]>
Status: Draft (Some confusion applies: The announcements for this never made it to the list, so it hasn't had public discussion)
Type: Standards Track
Created: 2012-11-20
----------------------------------------------------------------------------------------------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
A method is proposed for encrypting and encoding a passphrase-protected
Bitcoin private key record in the form of a 58-character
Base58Check-encoded printable string. Encrypted private key records are
intended for use on paper wallets and physical Bitcoins. Each record
string contains all the information needed to reconstitute the private
key except for a passphrase, and the methodology uses salting and
_scrypt_ to resist brute-force attacks.
The method provides two encoding methodologies - one permitting any
known private key to be encrypted with any passphrase, and another
permitting a shared private key generation scheme where the party
generating the final key string and its associated Bitcoin address (such
as a physical bitcoin manufacturer) knows only a string derived from the
original passphrase, and where the original passphrase is needed in
order to actually redeem funds sent to the associated Bitcoin address.
A 32-bit hash of the resulting Bitcoin address is encoded in plaintext
within each encrypted key, so it can be correlated to a Bitcoin address
with reasonable probability by someone not knowing the passphrase. The
complete Bitcoin address can be derived through successful decryption of
the key record.
[[motivation]]
Motivation
~~~~~~~~~~
The motivation to make this proposal stems from observations of the way
physical bitcoins and paper wallets are used.
An issuer of physical bitcoins must be trustworthy and trusted. Even if
trustworthy, users are rightful to be skeptical about a third party with
theoretical access to take their funds. A physical bitcoin that cannot
be compromised by its issuer is always more intrinsically valuable than
one that can.
A two-factor physical bitcoin solution is highly useful to individuals
and organizations wishing to securely own bitcoins without any risk of
electronic theft and without the responsibility of climbing the
technological learning curve necessary to produce such an environment
themselves. Two-factor physical bitcoins allow a secure storage solution
to be put in a box and sold on the open market, greatly enlarging the
number of people who are able to securely store bitcoins.
Existing methodologies for creating two-factor physical bitcoins are
limited and cumbersome. At the time of this proposal, a user could
create their own private key, submit the public key to the physical
bitcoin issuer, and then receive a physical bitcoin that must be kept
together with some sort of record of the user-generated private key, and
finally, must be redeemed through a tool. The fact that the physical
bitcoin must be kept together with a user-produced private key negates
much of the benefit of the physical bitcoin - the user may as well just
print and maintain a private key.
A standardized password-protected private key format makes acquiring and
redeeming two-factor physical bitcoins simpler for the user. Instead of
maintaining a private key that cannot be memorized, the user may choose
a passphrase of their choice. The passphrase may be much shorter than
the length of a typical private key, short enough that they could use a
label or engraver to permanently commit their passphrase to their
physical Bitcoin piece once they have received it. By adopting a
standard way to encrypt a private key, we maximize the possibility that
they'll be able to redeem their funds in the venue of their choice,
rather than relying on an executable redemption tool they may not wish
to download.
Password and passphrase-protected private keys enable new practical use
cases for sending bitcoins from person to person. Someone wanting to
send bitcoins through postal mail could send a password-protected paper
wallet and give the recipient the passphrase over the phone or e-mail,
making the transfer safe from interception of either channel. A user of
paper wallets or Bitcoin banknote-style vouchers ("cash") could carry
funded encrypted private keys while leaving a copy at home as an element
of protection against accidental loss or theft. A user of paper wallets
who leaves bitcoins in a bank vault or safety deposit box could keep the
password at home or share it with trusted associates as protection
against someone at the bank gaining access to the paper wallets and
spending from them. The foreseeable and unforeseeable use cases for
password-protected private keys are numerous.
[[copyright]]
Copyright
~~~~~~~~~
This proposal is hereby placed in the public domain.
[[rationale]]
Rationale
~~~~~~~~~
::
_*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._
+
_*User story:* As a Bitcoin user who would like to pay a person or a
company with a private key, I do not want to worry that any part of
the communication path may result in the interception of the key and
theft of my funds. I would prefer to offer an encrypted private key,
and then follow it up with the password using a different
communication channel (e.g. a phone call or SMS)._
+
_*User story:* (EC-multiplied keys) As a user of physical bitcoins, I
would like a third party to be able to create password-protected
Bitcoin private keys for me, without them knowing the password, so I
can benefit from the physical bitcoin without the issuer having access
to the private key. I would like to be able to choose a password whose
minimum length and required format does not preclude me from
memorizing it or engraving it on my physical bitcoin, without exposing
me to an undue risk of password cracking and/or theft by the
manufacturer of the item._
+
'*'User story:* (EC multiplied keys) As a user of paper wallets, I
would like the ability to generate a large number of Bitcoin addresses
protected by the same password, while enjoying a high degree of
security (highly expensive scrypt parameters), but without having to
incur the scrypt delay for each address I generate.
[[specification]]
Specification
~~~~~~~~~~~~~
This proposal makes use of the following functions and definitions:
* *AES256Encrypt, AES256Decrypt*: the simple form of the well-known AES
block cipher without consideration for initialization vectors or block
chaining. Each of these functions takes a 256-bit key and 16 bytes of
input, and deterministically yields 16 bytes of output.
* *SHA256*, a well-known hashing algorithm that takes an arbitrary
number of bytes as input and deterministically yields a 32-byte hash.
* *scrypt*: A well-known key derivation algorithm. It takes the
following parameters: (string) password, (string) salt, (int) n, (int)
r, (int) p, (int) length, and deterministically yields an array of bytes
whose length is equal to the length parameter.
* *ECMultiply*: Multiplication of an elliptic curve point by a scalar
integer with respect to the secp256k1 elliptic curve.
* *G, N*: Constants defined as part of the secp256k1 elliptic curve. G
is an elliptic curve point, and N is a large positive integer.
* *Base58Check*: a method for encoding arrays of bytes using 58
alphanumeric characters commonly used in the Bitcoin ecosystem.
[[prefix]]
Prefix
^^^^^^
It is proposed that the resulting 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 be understood in the future to include
keys participating in multisig transactions, and was chosen with
deference to the existing prefix '5' most commonly observed in
link:Wallet Import Format[Wallet Import Format] which denotes an
unencrypted private key.
It is proposed that the second character ought to give a hint as to what
is needed as a second factor, and for an encrypted key requiring a
passphrase, the uppercase letter P is proposed.
To keep the size of the encrypted key down, no initialization vectors
(IVs) are used in the AES encryption. Rather, suitable values for
IV-like use are derived using scrypt from the passphrase and from using
a 32-bit hash of the resulting Bitcoin address as salt.
[[proposed-specification]]
Proposed specification
^^^^^^^^^^^^^^^^^^^^^^
* Object identifier prefix: 0x0142 (non-EC-multiplied) or 0x0143
(EC-multiplied). 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.
* How the user sees it: 58 characters always starting with '6P'
** Visual cues are present in the third character for visually
identifying the EC-multiply and compress flag.
* Count of payload bytes (beyond prefix): 37
** 1 byte (_flagbyte_):
*** the most significant two bits are set as follows to preserve the
visibility of the compression flag in the prefix, as well as to keep the
payload within the range of allowable values that keep the "6P" prefix
intact. For non-EC-multiplied keys, the bits are 11. For EC-multiplied
keys, the bits are 00.
*** the bit with value 0x20 when set indicates the key should be
converted to a bitcoin address using the compressed public key format.
*** the bits with values 0x10 and 0x08 are reserved for a future
specification that contemplates using multisig as a way to combine the
factors such that parties in possession of the separate factors can
independently sign a proposed transaction without requiring that any
party possess both factors. These bits must be 0 to comply with this
version of the specification.
*** the bit with value 0x04 indicates whether a lot and sequence number
are encoded into the first factor, and activates special behavior for
including them in the decryption process. This applies to EC-multiplied
keys only. Must be 0 for non-EC-multiplied keys.
*** remaining bits are reserved for future use and must all be 0 to
comply with this version of the specification.
** 4 bytes: SHA256(SHA256(expected_bitcoin_address))[0...3], used both
for typo checking and as salt
** 16 bytes: Contents depend on whether EC multiplication is used.
** 16 bytes: lasthalf: An AES-encrypted key material record (contents
depend on whether EC multiplication is used)
* Range in base58check encoding for non-EC-multiplied keys without
compression (prefix 6PR):
** Minimum value:
6PRHv1jg1ytiE4kT2QtrUz8gEjMQghZDWg1FuxjdYDzjUkcJeGdFj9q9Vi (based on 01
42 C0 plus thirty-six 00's)
** Maximum value:
6PRWdmoT1ZursVcr5NiD14p5bHrKVGPG7yeEoEeRb8FVaqYSHnZTLEbYsU (based on 01
42 C0 plus thirty-six FF's)
* Range in base58check encoding for non-EC-multiplied keys with
compression (prefix 6PY):
** Minimum value:
6PYJxKpVnkXUsnZAfD2B5ZsZafJYNp4ezQQeCjs39494qUUXLnXijLx6LG (based on 01
42 E0 plus thirty-six 00's)
** Maximum value:
6PYXg5tGnLYdXDRZiAqXbeYxwDoTBNthbi3d61mqBxPpwZQezJTvQHsCnk (based on 01
42 E0 plus thirty-six FF's)
* Range in base58check encoding for EC-multiplied keys without
compression (prefix 6Pf):
** Minimum value:
6PfKzduKZXAFXWMtJ19Vg9cSvbFg4va6U8p2VWzSjtHQCCLk3JSBpUvfpf (based on 01
43 00 plus thirty-six 00's)
** Maximum value:
6PfYiPy6Z7BQAwEHLxxrCEHrH9kasVQ95ST1NnuEnnYAJHGsgpNPQ9dTHc (based on 01
43 00 plus thirty-six FF's)
* Range in base58check encoding for non-EC-multiplied keys with
compression (prefix 6Pn):
** Minimum value:
6PnM2wz9LHo2BEAbvoGpGjMLGXCom35XwsDQnJ7rLiRjYvCxjpLenmoBsR (based on 01
43 20 plus thirty-six 00's)
** Maximum value:
6PnZki3vKspApf2zym6Anp2jd5hiZbuaZArPfa2ePcgVf196PLGrQNyVUh (based on 01
43 20 plus thirty-six FF's)
[[encryption-when-ec-multiply-flag-is-not-used]]
Encryption when EC multiply flag is not used
++++++++++++++++++++++++++++++++++++++++++++
Encrypting a private key without the EC multiplication offers the
advantage that any known private key can be encrypted. The party
performing the encryption must know the passphrase.
Encryption steps:
1. Compute the Bitcoin address (ASCII), and take the first four bytes
of SHA256(SHA256()) of it. Let's call this "addresshash".
2. Derive a key from the passphrase using scrypt
* Parameters: _passphrase_ is the passphrase itself encoded in UTF-8.
salt is _addresshash_ from the earlier step, n=16384, r=8, p=8,
length=64 (n, r, p are provisional and subject to consensus)
* Let's split the resulting 64 bytes in half, and call them
_derivedhalf1_ and _derivedhalf2_.
3. Do AES256Encrypt(bitcoinprivkey[0...15] xor derivedhalf1[0...15],
derivedhalf2), call the 16-byte result _encryptedhalf1_
4. Do AES256Encrypt(bitcoinprivkey[16...31] xor derivedhalf1[16...31],
derivedhalf2), call the 16-byte result _encryptedhalf2_
The encrypted private key is the Base58Check-encoded concatenation of
the following, which totals 39 bytes without Base58 checksum:
* 0x01 0x42 + _flagbyte_ + _salt_ + _encryptedhalf1_ + _encryptedhalf2_
Decryption steps:
1. Collect encrypted private key and passphrase from user.
2. Derive _derivedhalf1_ and _derivedhalf2_ by passing the passphrase
and _addresshash_ into scrypt function.
3. Decrypt _encryptedhalf1_ and _encryptedhalf2_ using AES256Decrypt,
merge them to form the encrypted private key.
4. Convert that private key into a Bitcoin address, honoring the
compression preference specified in _flagbyte_ of the encrypted key
record.
5. Hash the Bitcoin address, and verify that _addresshash_ from the
encrypted private key record matches the hash. If not, report that the
passphrase entry was incorrect.
[[encryption-when-ec-multiply-mode-is-used]]
Encryption when EC multiply mode is used
++++++++++++++++++++++++++++++++++++++++
Encrypting a private key with EC multiplication offers the ability for
someone to generate encrypted keys knowing only an EC point derived from
the original passphrase and some salt generated by the passphrase's
owner, and without knowing the passphrase itself. Only the person who
knows the original passphrase can decrypt the private key. A code known
as an _intermediate code_ conveys the information needed to generate
such a key without knowledge of the passphrase.
This methodology does not offer the ability to encrypt a known private
key - this means that the process of creating encrypted keys is also the
process of generating new addresses. On the other hand, this serves a
security benefit for someone possessing an address generated this way:
if the address can be recreated by decrypting its private key with a
passphrase, and it's a strong passphrase one can be certain only he
knows himself, then he can safely conclude that nobody could know the
private key to that address.
The person who knows the passphrase and who is the intended beneficiary
of the private keys is called the _owner_. He will generate one or more
"intermediate codes", which are the first factor of a two-factor
redemption system, and will give them to someone else we'll call
_printer_, who generates a key pair with an intermediate code can know
the address and encrypted private key, but cannot decrypt the private
key without the original passphrase.
An intermediate code should, but is not required to, embed a printable
"lot" and "sequence" number for the benefit of the user. The proposal
forces these lot and sequence numbers to be included in any valid
private keys generated from them. An owner who has requested multiple
private keys to be generated for him will be advised by applications to
ensure that each private key has a unique lot and sequence number
consistent with the intermediate codes he generated. These mainly help
protect _owner_ from potential mistakes and/or attacks that could be
made by _printer_.
The "lot" and "sequence" number are combined into a single 32 bit
number. 20 bits are used for the lot number and 12 bits are used for the
sequence number, such that the lot number can be any decimal number
between 0 and 1048575, and the sequence number can be any decimal number
between 0 and 4095. For programs that generate batches of intermediate
codes for an _owner_, it is recommended that lot numbers be chosen at
random within the range 100000-999999 and that sequence numbers are
assigned starting with 1.
Steps performed by _owner_ to generate a single intermediate code, if
lot and sequence numbers are being included:
1. Generate 4 random bytes, call them _ownersalt_.
2. Encode the lot and sequence numbers as a 4 byte quantity
(big-endian): lotnumber * 4096 + sequencenumber. Call these four bytes
_lotsequence_.
3. Concatenate _ownersalt_ + _lotsequence_ and call this
_ownerentropy_.
4. Derive a key from the passphrase using scrypt
* Parameters: _passphrase_ is the passphrase itself encoded in UTF-8.
salt is _ownersalt_. n=16384, r=8, p=8, length=32.
* Call the resulting 32 bytes _prefactor_.
* Take SHA256(SHA256(_prefactor_ + _ownerentropy_)) and call this
_passfactor_.
5. Compute the elliptic curve point G * _passfactor_, and convert the
result to compressed notation (33 bytes). Call this _passpoint_.
Compressed notation is used for this purpose regardless of whether the
intent is to create Bitcoin addresses with or without compressed public
keys.
6. Convey _ownersalt_ and _passpoint_ to the party generating the keys,
along with a checksum to ensure integrity.
* The following Base58Check-encoded format is recommended for this
purpose: magic bytes "2C E9 B3 E1 FF 39 E2 51" followed by
_ownerentropy_, and then _passpoint_. The resulting string will start
with the word "passphrase" due to the constant bytes, will be 72
characters in length, and encodes 49 bytes (8 bytes constant + 8 bytes
_ownerentropy_ + 33 bytes _passpoint_). The checksum is handled in the
Base58Check encoding. The resulting string is called
_intermediate_passphrase_string_.
If lot and sequence numbers are not being included, then follow the same
procedure with the following changes:
* _ownersalt_ is 8 random bytes instead of 4, and _lotsequence_ is
omitted. _ownerentropy_ becomes an alias for _ownersalt_.
* The SHA256 conversion of _prefactor_ to _passfactor_ is omitted.
Instead, the output of scrypt is used directly as _passfactor_.
* The magic bytes are "2C E9 B3 E1 FF 39 E2 53" instead (the last byte
is 0x53 instead of 0x51).
Steps to create new encrypted private keys given
_intermediate_passphrase_string_ from _owner_ (so we have
_ownerentropy_, and _passpoint_, but we do not have _passfactor_ or the
passphrase):
1. Set _flagbyte_.
* Turn on bit 0x20 if the Bitcoin address will be formed by hashing the
compressed public key (optional, saves space, but many Bitcoin
implementations aren't compatible with it)
* Turn on bit 0x04 if _ownerentropy_ contains a value for _lotsequence_.
(While it has no effect on the keypair generation process, the
decryption process needs this flag to know how to process
_ownerentropy_)
2. Generate 24 random bytes, call this _seedb_. Take
SHA256(SHA256(_seedb_)) to yield 32 bytes, call this _factorb_.
3. ECMultiply _passpoint_ by _factorb_. Use the resulting EC point as a
public key and hash it into a Bitcoin address using either compressed or
uncompressed public key methodology (specify which methodology is used
inside _flagbyte_). This is the generated Bitcoin address, call it
_generatedaddress_.
4. Take the first four bytes of SHA256(SHA256(_generatedaddress_)) and
call it _addresshash_.
5. Now we will encrypt _seedb_. Derive a second key from _passpoint_
using scrypt
* Parameters: _passphrase_ is _passpoint_ provided from the first party
(expressed in binary as 33 bytes). _salt_ is _addresshash_ +
_ownerentropy_, n=1024, r=1, p=1, length=64. The "+" operator is
concatenation.
* Split the result into two 32-byte halves and call them _derivedhalf1_
and _derivedhalf2_.
6. Do AES256Encrypt(seedb[0...15] xor derivedhalf1[0...15],
derivedhalf2), call the 16-byte result _encryptedpart1_
7. Do AES256Encrypt((encryptedpart1[8...15] + seedb[16...23]) xor
derivedhalf1[16...31], derivedhalf2), call the 16-byte result
_encryptedpart2_. The "+" operator is concatenation.
The encrypted private key is the Base58Check-encoded concatenation of
the following, which totals 39 bytes without Base58 checksum:
* 0x01 0x43 + _flagbyte_ + _addresshash_ + _ownerentropy_ +
_encryptedpart1_[0...7] + _encryptedpart2_
[[confirmation-code]]
Confirmation code
The party generating the Bitcoin address has the option to return a
_confirmation code_ back to _owner_ which allows _owner_ to
independently verify that he has been given a Bitcoin address that
actually depends on his passphrase, and to confirm the lot and sequence
numbers (if applicable). This protects _owner_ from being given a
Bitcoin address by the second party that is unrelated to the key
derivation and possibly spendable by the second party. If a Bitcoin
address given to _owner_ can be successfully regenerated through the
confirmation process, _owner_ can be reasonably assured that any
spending without the passphrase is infeasible. This confirmation code is
75 characters starting with "cfrm38".
To generate it, we need _flagbyte_, _ownerentropy_, _factorb_,
_derivedhalf1_ and _derivedhalf2_ from the original encryption
operation.
1. ECMultiply _factorb_ by G, call the result _pointb_. The result is
33 bytes.
2. The first byte is 0x02 or 0x03. XOR it by (derivedhalf2[31] & 0x01),
call the resulting byte _pointbprefix_.
3. Do AES256Encrypt(pointb[1...16] xor derivedhalf1[0...15],
derivedhalf2) and call the result _pointbx1_.
4. Do AES256Encrypt(pointb[17...32] xor derivedhalf1[16...31],
derivedhalf2) and call the result _pointbx2_.
5. Concatenate _pointbprefix_ + _pointbx1_ + _pointbx2_ (total 33
bytes) and call the result _encryptedpointb_.
The result is a Base58Check-encoded concatenation of the following:
* 0x64 0x3B 0xF6 0xA8 0x9A + _flagbyte_ + _addresshash_ + _ownerentropy_
+ _encryptedpointb_
A confirmation tool, given a passphrase and a confirmation code, can
recalculate the address, verify the address hash, and then assert the
following: "It is confirmed that Bitcoin address _address_ depends on
this passphrase". If applicable: "The lot number is _lotnumber_ and the
sequence number is _sequencenumber_."
To recalculate the address:
1. Derive _passfactor_ using scrypt with _ownerentropy_ and the user's
passphrase and use it to recompute _passpoint_
2. Derive decryption key for _pointb_ using scrypt with _passpoint_,
_addresshash_, and _ownerentropy_
3. Decrypt _encryptedpointb_ to yield _pointb_
4. ECMultiply _pointb_ by _passfactor_. Use the resulting EC point as a
public key and hash it into _address_ using either compressed or
uncompressed public key methodology as specifid in _flagbyte_.
[[decryption]]
Decryption
1. Collect encrypted private key and passphrase from user.
2. Derive _passfactor_ using scrypt with _ownerentropy_ and the user's
passphrase and use it to recompute _passpoint_
3. Derive decryption key for _seedb_ using scrypt with _passpoint_,
_addresshash_, and _ownersalt_
4. Decrypt _encryptedpart2_ using AES256Decrypt to yield the last 8
bytes of _seedb_ and the last 8 bytes of _encryptedpart1_.
5. Decrypt _encryptedpart1_ to yield the remainder of _seedb_.
6. Use _seedb_ to compute _factorb_.
7. Multiply _passfactor_ by _factorb_ mod N to yield the private key
associated with _generatedaddress_.
8. Convert that private key into a Bitcoin address, honoring the
compression preference specified in the encrypted key.
9. Hash the Bitcoin address, and verify that _addresshash_ from the
encrypted private key record matches the hash. If not, report that the
passphrase entry was incorrect.
[[backwards-compatibility]]
Backwards compatibility
~~~~~~~~~~~~~~~~~~~~~~~
Backwards compatibility is minimally applicable since this is a new
standard that at most extends link:Wallet Import Format[Wallet Import
Format]. It is assumed that an entry point for private key data may also
accept existing formats of private keys (such as hexadecimal and
link:Wallet Import Format[Wallet Import Format]); this draft uses a key
format that cannot be mistaken for any existing one and preserves
auto-detection capabilities.
[[suggestions-for-implementers-of-proposal-with-alt-chains]]
Suggestions for implementers of proposal with alt-chains
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
If this proposal is accepted into alt-chains, it is requested that the
unused flag bytes not be used for denoting that the key belongs to an
alt-chain.
Alt-chain implementers should exploit the address hash for this purpose.
Since each operation in this proposal involves hashing a text
representation of a coin address which (for Bitcoin) includes the
leading '1', an alt-chain can easily be denoted simply by using the
alt-chain's preferred format for representing an address. Alt-chain
implementers may also change the prefix such that encrypted addresses do
not start with "6P".
[[discussion-item-scrypt-parameters]]
Discussion item: scrypt parameters
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This proposal leaves the scrypt parameters up in the air. The following
items are proposed for consideration:
The main goal of scrypt is to reduce the feasibility of brute force
attacks. It must be assumed that an attacker will be able to use an
efficient implementation of scrypt. The parameters should force a highly
efficient implementation of scrypt to wait a decent amount of time to
slow attacks.
On the other hand, an unavoidably likely place where scrypt will be
implemented is using slow interpreted languages such as javascript. What
might take milliseconds on an efficient scrypt implementation may take
seconds in javascript.
It is believed, however, that someone using a javascript implementation
is probably dealing with codes by hand, one at a time, rather than
generating or processing large batches of codes. Thus, a wait time of
several seconds is acceptable to a user.
A private key redemption process that forces a server to consume several
seconds of CPU time would discourage implementation by the server owner,
because they would be opening up a denial of service avenue by inviting
users to make numerous attempts to invoke the redemption process.
However, it's also feasible for the server owner to implement his
redemption process in such a way that the decryption is done by the
user's browser, offloading the task from his own server (and providing
another reason why the chosen scrypt parameters should be tolerant of
javascript-based decryptors).
The preliminary values of 16384, 8, and 8 are hoped to offer the
following properties:
* Encryption/decryption in javascript requiring several seconds per
operation
* Use of the parallelization parameter provides a modest opportunity for
speedups in environments where concurrent threading is available - such
environments would be selected for processes that must handle bulk
quantities of encryption/decryption operations. Estimated time for an
operation is in the tens or hundreds of milliseconds.
[[reference-implementation]]
Reference implementation
~~~~~~~~~~~~~~~~~~~~~~~~
Added to alpha version of Casascius Bitcoin Address Utility for Windows
available at:
* via https: https://casascius.com/btcaddress-alpha.zip
* at github: https://github.com/casascius/Bitcoin-Address-Utility
Click "Tools" then "PPEC Keygen" (provisional name)
[[test-vectors]]
Test vectors
~~~~~~~~~~~~
[[no-compression-no-ec-multiply]]
No compression, no EC multiply
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Test 1:
* Passphrase: TestingOneTwoThree
* Encrypted: 6PRVWUbkzzsbcVac2qwfssoUJAN1Xhrg6bNk8J7Nzm5H7kxEbn2Nh2ZoGg
* Unencrypted (WIF): 5KN7MzqK5wt2TP1fQCYyHBtDrXdJuXbUzm4A9rKAteGu3Qi5CVR
* Unencrypted (hex):
CBF4B9F70470856BB4F40F80B87EDB90865997FFEE6DF315AB166D713AF433A5
Test 2:
* Passphrase: Satoshi
* Encrypted: 6PRNFFkZc2NZ6dJqFfhRoFNMR9Lnyj7dYGrzdgXXVMXcxoKTePPX1dWByq
* Unencrypted (WIF): 5HtasZ6ofTHP6HCwTqTkLDuLQisYPah7aUnSKfC7h4hMUVw2gi5
* Unencrypted (hex):
09C2686880095B1A4C249EE3AC4EEA8A014F11E6F986D0B5025AC1F39AFBD9AE
[[compression-no-ec-multiply]]
Compression, no EC multiply
^^^^^^^^^^^^^^^^^^^^^^^^^^^
Test 1:
* Passphrase: TestingOneTwoThree
* Encrypted: 6PYNKZ1EAgYgmQfmNVamxyXVWHzK5s6DGhwP4J5o44cvXdoY7sRzhtpUeo
* Unencrypted (WIF):
L44B5gGEpqEDRS9vVPz7QT35jcBG2r3CZwSwQ4fCewXAhAhqGVpP
* Unencrypted (hex):
CBF4B9F70470856BB4F40F80B87EDB90865997FFEE6DF315AB166D713AF433A5
Test 2:
* Passphrase: Satoshi
* Encrypted: 6PYLtMnXvfG3oJde97zRyLYFZCYizPU5T3LwgdYJz1fRhh16bU7u6PPmY7
* Unencrypted (WIF):
KwYgW8gcxj1JWJXhPSu4Fqwzfhp5Yfi42mdYmMa4XqK7NJxXUSK7
* Unencrypted (hex):
09C2686880095B1A4C249EE3AC4EEA8A014F11E6F986D0B5025AC1F39AFBD9AE
[[ec-multiply-no-compression-no-lotsequence-numbers]]
EC multiply, no compression, no lot/sequence numbers
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Test 1:
* Passphrase: TestingOneTwoThree
* Passphrase code:
passphrasepxFy57B9v8HtUsszJYKReoNDV6VHjUSGt8EVJmux9n1J3Ltf1gRxyDGXqnf9qm
* Encrypted key:
6PfQu77ygVyJLZjfvMLyhLMQbYnu5uguoJJ4kMCLqWwPEdfpwANVS76gTX
* Bitcoin address: 1PE6TQi6HTVNz5DLwB1LcpMBALubfuN2z2
* Unencrypted private key (WIF):
5K4caxezwjGCGfnoPTZ8tMcJBLB7Jvyjv4xxeacadhq8nLisLR2
* Unencrypted private key (hex):
A43A940577F4E97F5C4D39EB14FF083A98187C64EA7C99EF7CE460833959A519
Test 2:
* Passphrase: Satoshi
* Passphrase code:
passphraseoRDGAXTWzbp72eVbtUDdn1rwpgPUGjNZEc6CGBo8i5EC1FPW8wcnLdq4ThKzAS
* Encrypted key:
6PfLGnQs6VZnrNpmVKfjotbnQuaJK4KZoPFrAjx1JMJUa1Ft8gnf5WxfKd
* Bitcoin address: 1CqzrtZC6mXSAhoxtFwVjz8LtwLJjDYU3V
* Unencrypted private key (WIF):
5KJ51SgxWaAYR13zd9ReMhJpwrcX47xTJh2D3fGPG9CM8vkv5sH
* Unencrypted private key (hex):
C2C8036DF268F498099350718C4A3EF3984D2BE84618C2650F5171DCC5EB660A
[[ec-multiply-no-compression-lotsequence-numbers]]
EC multiply, no compression, lot/sequence numbers
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Test 1:
* Passphrase: MOLON LABE
* Passphrase code:
passphraseaB8feaLQDENqCgr4gKZpmf4VoaT6qdjJNJiv7fsKvjqavcJxvuR1hy25aTu5sX
* Encrypted key:
6PgNBNNzDkKdhkT6uJntUXwwzQV8Rr2tZcbkDcuC9DZRsS6AtHts4Ypo1j
* Bitcoin address: 1Jscj8ALrYu2y9TD8NrpvDBugPedmbj4Yh
* Unencrypted private key (WIF):
5JLdxTtcTHcfYcmJsNVy1v2PMDx432JPoYcBTVVRHpPaxUrdtf8
* Unencrypted private key (hex):
44EA95AFBF138356A05EA32110DFD627232D0F2991AD221187BE356F19FA8190
* Confirmation code:
cfrm38V8aXBn7JWA1ESmFMUn6erxeBGZGAxJPY4e36S9QWkzZKtaVqLNMgnifETYw7BPwWC9aPD
* Lot/Sequence: 263183/1
Test 2:
* Passphrase (all letters are Greek - test UTF-8 compatibility with
this): ΜΟΛΩΝ ΛΑΒΕ
* Passphrase code:
passphrased3z9rQJHSyBkNBwTRPkUGNVEVrUAcfAXDyRU1V28ie6hNFbqDwbFBvsTK7yWVK
* Encrypted private key:
6PgGWtx25kUg8QWvwuJAgorN6k9FbE25rv5dMRwu5SKMnfpfVe5mar2ngH
* Bitcoin address: 1Lurmih3KruL4xDB5FmHof38yawNtP9oGf
* Unencrypted private key (WIF):
5KMKKuUmAkiNbA3DazMQiLfDq47qs8MAEThm4yL8R2PhV1ov33D
* Unencrypted private key (hex):
CA2759AA4ADB0F96C414F36ABEB8DB59342985BE9FA50FAAC228C8E7D90E3006
* Confirmation code:
cfrm38V8G4qq2ywYEFfWLD5Cc6msj9UwsG2Mj4Z6QdGJAFQpdatZLavkgRd1i4iBMdRngDqDs51
* Lot/Sequence: 806938/1
----------------------------------------------------------
BIP: BIP-0039
Title: Mnemonic code for generating deterministic keys
Authors: Marek Palatinus <[email protected]>
Pavol Rusnak <[email protected]>
ThomasV <[email protected]>
Aaron Voisine <[email protected]>
Sean Bowe <[email protected]>
Status: Draft
Type: Standards Track
Created: 2013-09-10
----------------------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This BIP describes the implementation of a mnemonic code or mnemonic
sentence -- a group of easy to remember words -- for the generation of
deterministic wallets.
It consists of two parts: generating the mnenomic, and converting it
into a binary seed. This seed can be later used to generate
deterministic wallets using BIP-0032 or similar methods.
[[motivation]]
Motivation
~~~~~~~~~~
A mnenomic code or sentence is superior for human interaction compared
to the handling of raw binary or hexidecimal representations of a wallet
seed. The sentence could be written on paper or spoken over the
telephone.
This guide meant to be as a way to transport computer-generated
randomnes over human readable transcription. It's not a way how to
process user-created sentences (also known as brainwallet) to wallet
seed.
[[generating-the-mnemonic]]
Generating the mnemonic
~~~~~~~~~~~~~~~~~~~~~~~
The mnemonic must encode entropy in any multiple of 32 bits. With larger
entropy security is improved but the sentence length increases. We can
refer to the initial entropy length as ENT. The recommended size of ENT
is 128-256 bits.
First, an initial entropy of ENT bits is generated. A checksum is
generated by taking the first
--------
ENT / 32
--------
bits of its SHA256 hash. This checksum is appended to the end of the
initial entropy. Next, these concatenated bits are are split into groups
of 11 bits, each encoding a number from 0-2047, serving as an index to a
wordlist. Later, we will convert these numbers into words and use the
joined words as a mnemonic sentence.
The following table describes the relation between the initial entropy
length (ENT), the checksum length (CS) and length of the generated
mnemonic sentence (MS) in words.
------------------------------
CS = ENT / 32
MS = (ENT + CS) / 11
| ENT | CS | ENT+CS | MS |
+-------+----+--------+------+
| 128 | 4 | 132 | 12 |
| 160 | 5 | 165 | 15 |
| 192 | 6 | 198 | 18 |
| 224 | 7 | 231 | 21 |
| 256 | 8 | 264 | 24 |
------------------------------
[[wordlist]]
Wordlist
~~~~~~~~
An ideal wordlist has the following characteristics:
\a) smart selection of words
` - wordlist is created in such way that it's enough to type the first four` +
` letters to unambiguously identify the word`
\b) similar words avoided
` - word pairs like "build" and "built", "woman" and "women", or "quick" and "quickly"` +
` not only make remembering the sentence difficult, but are also more error` +
` prone and more difficult to guess`
\c) sorted wordlists
` - wordlist is sorted which allows for more efficient lookup of the code words` +
` (i.e. implementation can use binary search instead of linear search)` +
` - this also allows trie (prefix tree) to be used, e.g. for better compression`
The wordlist can contain native characters, but they have to be encoded
in UTF-8 using Normalization Form Compatibility Decomposition (NFKD).
[[from-mnemonic-to-seed]]
From mnemonic to seed
~~~~~~~~~~~~~~~~~~~~~
A user may decide to protect their mnemonic by passphrase. If a
passphrase is not present, an empty string "" is used instead.
To create a binary seed from the mnemonic, we use PBKDF2 function with a
mnemonic sentence (in UTF-8 NFKD) used as a password and string
"mnemonic" + passphrase (again in UTF-8 NFKD) used as a salt. Iteration
count is set to 2048 and HMAC-SHA512 is used as a pseudo-random
function. Desired length of the derived key is 512 bits (= 64 bytes).
This seed can be later used to generate deterministic wallets using
BIP-0032 or similar methods.
The conversion of the mnemonic sentence to binary seed is completely
independent from generating the sentence. This results in rather simple
code; there are no constraints on sentence structure and clients are
free to implement their own wordlists or even whole sentence generators,
allowing for flexibility in wordlists for typo detection or other
purposes.
Although using mnemonic not generated by algorithm described in
"Generating the mnemonic" section is possible, this is not advised and
software must compute checksum of the mnemonic sentence using wordlist
and issue a warning if it is invalid.
Described method also provides plausible deniability, because every
passphrase generates a valid seed (and thus deterministic wallet) but
only the correct one will make the desired wallet available.
[[wordlists]]
Wordlists
~~~~~~~~~
* link:bip-0039/english.txt[English]
[[test-vectors]]
Test vectors
~~~~~~~~~~~~
See https://github.com/trezor/python-mnemonic/blob/master/vectors.json
[[reference-implementation]]
Reference Implementation
~~~~~~~~~~~~~~~~~~~~~~~~
Reference implementation including wordlists is available from
http://github.com/trezor/python-mnemonic
[[other-implementations]]
Other Implementations
~~~~~~~~~~~~~~~~~~~~~
Objective-C - https://github.com/nybex/NYMnemonic
------------------------------------------------------------
BIP: BIP-0044
Title: Multi-Account Hierarchy for Deterministic Wallets
Authors: Marek Palatinus <[email protected]>
Pavol Rusnak <[email protected]>
Status: Draft
Type: Standards Track
Created: 2014-04-24
------------------------------------------------------------
[[abstract]]
Abstract
~~~~~~~~
This BIP defines a logical hierarchy for deterministic wallets based on
an algorithm described in BIP-0032 (BIP32 from now on) and purpose
scheme described in BIP-0043 (BIP43 from now on).
This BIP is a particular application of BIP43.
[[motivation]]
Motivation
~~~~~~~~~~
The hierarchy proposed in this paper is quite comprehensive. It allows
the handling of multiple coins, multiple accounts, external and internal
chains per account and millions of addresses per chain.
[[path-levels]]
Path levels
~~~~~~~~~~~
We define the following 5 levels in BIP32 path:
-------------------------------------------------------------
m / purpose' / coin_type' / account' / change / address_index
-------------------------------------------------------------
Apostrophe in the path indicates that BIP32 hardened derivation is used.
Each level has a special meaning, described in the chapters below.
[[purpose]]
Purpose
^^^^^^^
Purpose is a constant set to 44' (or 0x8000002C) following the BIP43
recommendation. It indicates that the subtree of this node is used
according to this specification.
Hardened derivation is used at this level.
[[coin-type]]
Coin type
^^^^^^^^^
One master node (seed) can be used for unlimited number of independent
cryptocoins such as Bitcoin, Litecoin or Namecoin. However, sharing the
same space for various cryptocoins has some disadvantages.
This level creates a separate subtree for every cryptocoin, avoiding
reusing addresses across cryptocoins and improving privacy issues.
Coin type is a constant, set for each cryptocoin. Cryptocoin developers
may ask for registering unused number for their project.
The list of already allocated coin types is in the chapter "Registered
coin types" below.
Hardened derivation is used at this level.
[[account]]
Account
^^^^^^^
This level splits the key space into independent user identities, so the
wallet never mixes the coins across different accounts.
Users can use these accounts to organize the funds in the same fashion
as bank accounts; for donation purposes (where all addresses are
considered public), for saving purposes, for common expenses etc.
Accounts are numbered from index 0 in sequentially increasing manner.
This number is used as child index in BIP32 derivation.
Hardened derivation is used at this level.
Software should prevent a creation of an account if a previous account
does not have a transaction history (meaning none of its addresses have
been used before).
Software needs to discover all used accounts after importing the seed
from an external source. Such an algorithm is described in "Account
discovery" chapter.
[[change]]
Change
^^^^^^
Constant 0 is used for external chain and constant 1 for internal chain
(also known as change addresses). External chain is used for addresses
that are meant to be visible outside of the wallet (e.g. for receiving
payments). Internal chain is used for addresses which are not meant to
be visible outside of the wallet and is used for return transaction
change.
Public derivation is used at this level.
[[index]]
Index
^^^^^
Addresses are numbered from index 0 in sequentially increasing manner.
This number is used as child index in BIP32 derivation.
Public derivation is used at this level.
[[account-discovery]]
Account discovery
~~~~~~~~~~~~~~~~~
When the master seed is imported from an external source the software
should start to discover the accounts in the following manner:
1. derive the first account's node (index = 0)
2. derive the external chain node of this account
3. scan addresses of the external chain; respect the gap limit
described below
4. if no transactions are found on the external chain, stop discovery
5. if there are some transactions, increase the account index and go to
step 1
This algorithm is successful because software should disallow creation
of new accounts if previous one has no transaction history, as described
in chapter "Account" above.
Please note that the algorithm works with the transaction history, not
account balances, so you can have an account with 0 total coins and the
algorithm will still continue with discovery.
[[address-gap-limit]]
Address gap limit
^^^^^^^^^^^^^^^^^
Address gap limit is currently set to 20. If the software hits 20 unused
addresses in a row, it expects there are no used addresses beyond this
point and stops searching the address chain.
Wallet software should warn when the user is trying to exceed the gap
limit on an external chain by generating a new address.
[[registered-coin-types]]
Registered coin types
~~~~~~~~~~~~~~~~~~~~~
These are the registered coin types for usage in level 2 of BIP44
described in chapter "Coin type" above.
All these constants are used as hardened derivation.
[cols=",,",options="header",]
|==============================
|index |hexa |coin
|0 |0x80000000 |Bitcoin
|1 |0x80000001 |Bitcoin Testnet
|==============================
[[examples]]
Examples
~~~~~~~~
[cols=",,,,",options="header",]
|====================================================================
|coin |account |chain |address |path
|Bitcoin |first |external |first |m / 44' / 0' / 0' / 0 / 0
|Bitcoin |first |external |second |m / 44' / 0' / 0' / 0 / 1
|Bitcoin |first |change |first |m / 44' / 0' / 0' / 1 / 0
|Bitcoin |first |change |second |m / 44' / 0' / 0' / 1 / 1
|Bitcoin |second |external |first |m / 44' / 0' / 1' / 0 / 0
|Bitcoin |second |external |second |m / 44' / 0' / 1' / 0 / 1
|Bitcoin |second |change |first |m / 44' / 0' / 1' / 1 / 0
|Bitcoin |second |change |second |m / 44' / 0' / 1' / 1 / 1
|Bitcoin Testnet |first |external |first |m / 44' / 1' / 0' / 0 / 0
|Bitcoin Testnet |first |external |second |m / 44' / 1' / 0' / 0 / 1
|Bitcoin Testnet |first |change |first |m / 44' / 1' / 0' / 1 / 0
|Bitcoin Testnet |first |change |second |m / 44' / 1' / 0' / 1 / 1
|Bitcoin Testnet |second |external |first |m / 44' / 1' / 1' / 0 / 0
|Bitcoin Testnet |second |external |second |m / 44' / 1' / 1' / 0 / 1
|Bitcoin Testnet |second |change |first |m / 44' / 1' / 1' / 1 / 0
|Bitcoin Testnet |second |change |second |m / 44' / 1' / 1' / 1 / 1
|====================================================================
[[compatible-wallets]]
Compatible wallets
~~~~~~~~~~~~~~~~~~
* https://mytrezor.com[myTREZOR web wallet]
(https://github.com/trezor/webwallet[source])
[[reference]]
Reference
~~~~~~~~~
* link:bip-0032.mediawiki[BIP32 - Hierarchical Deterministic Wallets]
* link:bip-0043.mediawiki[BIP43 - Purpose Field for Deterministic
Wallets]
BIP: 70 Title: Payment Protocol Author: Gavin Andresen <[email protected]> Status: Draft Type: Standards Track Created: 2013-07-29
[[abstract]]
Abstract
~~~~~~~~
This BIP describes a protocol for communication between a merchant and
their customer, enabling both a better customer experience and better
security against man-in-the-middle attacks on the payment process.
[[motivation]]
Motivation
~~~~~~~~~~
The current, minimal Bitcoin payment protocol operates as follows:
1. Customer adds items to an online shopping basket, and decides to pay
using Bitcoin.
2. Merchant generates a unique payment address, associates it with the
customer's order, and asks the customer to pay.
3. Customer copies the Bitcoin address from the merchant's web page and
pastes it into whatever wallet they are using OR follows a bitcoin: link
and their wallet is launched with the amount to be paid.
4. Customer authorizes payment to the merchant's address and broadcasts
the transaction through the Bitcoin p2p network.
5. Merchant's server detects payment and after sufficient transaction
confirmations considers the transaction final.
This BIP extends the above protocol to support several new features:
1. Human-readable, secure payment destinations-- customers will be
asked to authorize payment to "example.com" instead of an inscrutable,
34-character bitcoin address.
2. Secure proof of payment, which the customer can use in case of a
dispute with the merchant.
3. Resistance from man-in-the-middle attacks that replace a merchant's
bitcoin address with an attacker's address before a transaction is
authorized with a hardware wallet.
4. Payment received messages, so the customer knows immediately that
the merchant has received, and has processed (or is processing) their
payment.
5. Refund addresses, automatically given to the merchant by the
customer's wallet software, so merchants do not have to contact
customers before refunding overpayments or orders that cannot be
fulfilled for some reason.
[[protocol]]
Protocol
~~~~~~~~
This BIP describes payment protocol messages encoded using Google's
Protocol Buffers, authenticated using X.509 certificates, and
communicated over http/https. Future BIPs might extend this payment
protocol to other encodings, PKI systems, or transport protocols.
The payment protocol consists of three messages; PaymentRequest,
Payment, and PaymentACK, and begins with the customer somehow indicating
that they are ready to pay and the merchant's server responding with a
PaymentRequest message:
[[messages]]
Messages
~~~~~~~~
The Protocol Buffers messages are defined in
link:bip-0070/paymentrequest.proto[paymentrequest.proto].
[[output]]
Output
^^^^^^
Outputs are used in PaymentRequest messages to specify where a payment
(or part of a payment) should be sent. They are also used in Payment
messages to specify where a refund should be sent.
---------------------------------------------
message Output {
optional uint64 amount = 1 [default = 0];
optional bytes script = 2;
}
---------------------------------------------
[cols=",",]
|=======================================================================
|amount |Number of satoshis (0.00000001 BTC) to be paid
|script |a "TxOut" script where payment should be sent. This will
normally be one of the standard Bitcoin transaction scripts (e.g. pubkey
OP_CHECKSIG). This is optional to enable future extensions to this
protocol that derive Outputs from a master public key and the
PaymentRequest data itself.
|=======================================================================
[[paymentdetailspaymentrequest]]
PaymentDetails/PaymentRequest
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Payment requests are split into two messages to support future
extensibility. The bulk of the information is contained in the
PaymentDetails message. It is wrapped inside a PaymentRequest message,
which contains meta-information about the merchant and a digital
signature.
-------------------------------------------------------
message PaymentDetails {
optional string network = 1 [default = "main"];
repeated Output outputs = 2;
required uint64 time = 3;
optional uint64 expires = 4;
optional string memo = 5;
optional string payment_url = 6;
optional bytes merchant_data = 7;
}
-------------------------------------------------------
[cols=",",]
|=======================================================================
|network |either "main" for payments on the production Bitcoin network,
or "test" for payments on test network. If a client receives a
PaymentRequest for a network it does not support it must reject the
request.
|outputs |one or more outputs where Bitcoins are to be sent. If the sum
of outputs.amount is zero, the customer will be asked how much to pay,
and the bitcoin client may choose any or all of the Outputs (if there
are more than one) for payment. If the sum of outputs.amount is
non-zero, then the customer will be asked to pay the sum, and the
payment shall be split among the Outputs with non-zero amounts (if there
are more than one; Outputs with zero amounts shall be ignored).
|time |Unix timestamp (seconds since 1-Jan-1970 UTC) when the
PaymentRequest was created.
|expires |Unix timestamp (UTC) after which the PaymentRequest should be
considered invalid.
|memo |UTF-8 encoded, plain-text (no formatting) note that should be
displayed to the customer, explaining what this PaymentRequest is for.
|payment_url |Secure (usually https) location where a Payment message
(see below) may be sent to obtain a PaymentACK.
|merchant_data |Arbitrary data that may be used by the merchant to
identify the PaymentRequest. May be omitted if the merchant does not
need to associate Payments with PaymentRequest or if they associate each
PaymentRequest with a separate payment address.
|=======================================================================
The payment_url specified in the PaymentDetails should remain valid at
least until the PaymentDetails expires (or as long as possible if the
PaymentDetails does not expire). Note that this is irrespective of any
state change in the underlying payment request; for example cancellation
of an order should not invalidate the payment_url, as it is important
that the merchant's server can record mis-payments in order to refund
the payment.
A PaymentRequest is PaymentDetails optionally tied to a merchant's
identity:
------------------------------------------------------------------
message PaymentRequest {
optional uint32 payment_details_version = 1 [default = 1];
optional string pki_type = 2 [default = "none"];
optional bytes pki_data = 3;
required bytes serialized_payment_details = 4;
optional bytes signature = 5;
}
------------------------------------------------------------------
[cols=",",]
|=======================================================================
|payment_details_version |See below for a discussion of
versioning/upgrading.
|pki_type |public-key infrastructure (PKI) system being used to identify
the merchant. All implementation should support "none", "x509+sha256"
and "x509+sha1".
|pki_data |PKI-system data that identifies the merchant and can be used
to create a digital signature. In the case of X.509 certificates,
pki_data contains one or more X.509 certificates (see Certificates
section below).
|serialized_payment_details |A protocol-buffer serialized PaymentDetails
message.
|signature |digital signature over a hash of the protocol buffer
serialized variation of the PaymentRequest message, with all fields
serialized in numerical order (all current protocol buffer
implementations serialize fields in numerical order) and signed using
the public key in pki_data. Before serialization, the signature field
must be set to an empty value so that the field is included in the
signed PaymentRequest hash but contains no data.
|=======================================================================
When a Bitcoin wallet application receives a PaymentRequest, it must
authorize payment by doing the following:
1. Validate the merchant's identity and signature using the PKI system,
if the pki_type is not "none".
2. Validate that customer's system unix time (UTC) is before
PaymentDetails.expires. If it is not, then the payment request must be
rejected.
3. Display the merchant's identity and ask the customer if they would
like to submit payment (e.g. display the "Common Name" in the first
X.509 certificate).
PaymentRequest messages larger than 50,000 bytes should be rejected by
the wallet application, to mitigate denial-of-service attacks.
[[payment]]
Payment
^^^^^^^
Payment messages are sent after the customer has authorized payment:
-----------------------------------------
message Payment {
optional bytes merchant_data = 1;
repeated bytes transactions = 2;
repeated Output refund_to = 3;
optional string memo = 4;
}
-----------------------------------------
[cols=",",]
|=======================================================================
|merchant_data |copied from PaymentDetails.merchant_data. Merchants may
use invoice numbers or any other data they require to match Payments to
PaymentRequests. Note that malicious clients may modify the
merchant_data, so should be authenticated in some way (for example,
signed with a merchant-only key).
|transactions |One or more valid, signed Bitcoin transactions that fully
pay the PaymentRequest
|refund_to |One or more outputs where the merchant may return funds, if
necessary. The merchant may return funds using these outputs for up to 2
months after the time of the payment request. After that time has
expired, parties must negotiate if returning of funds becomes necessary.
|memo |UTF-8 encoded, plain-text note from the customer to the merchant.
|=======================================================================
If the customer authorizes payment, then the Bitcoin client:
1. Creates and signs one or more transactions that satisfy (pay in
full) PaymentDetails.outputs
2. Validate that customer's system unix time (UTC) is still before
PaymentDetails.expires. If it is not, the payment should be cancelled.
3. Broadcast the transactions on the Bitcoin p2p network.
4. If PaymentDetails.payment_url is specified, POST a Payment message
to that URL. The Payment message is serialized and sent as the body of
the POST request.
Errors communicating with the payment_url server should be communicated
to the user. In the scenario where the merchant's server receives
multiple identical Payment messages for an individual PaymentRequest, it
must acknowledge each. The second and further PaymentACK messages sent
from the merchant's server may vary by memo field to indicate current
state of the Payment (for example number of confirmations seen on the
network). This is required in order to ensure that in case of a
transport level failure during transmission, recovery is possible by the
Bitcoin client re-sending the Payment message.
PaymentDetails.payment_url should be secure against man-in-the-middle
attacks that might alter Payment.refund_to (if using HTTP, it must be
TLS-protected).
Wallet software sending Payment messages via HTTP must set appropriate
Content-Type and Accept headers, as specified in BIP 71:
-----------------------------------------
Content-Type: application/bitcoin-payment
Accept: application/bitcoin-paymentack
-----------------------------------------
When the merchant's server receives the Payment message, it must
determine whether or not the transactions satisfy conditions of payment.
If and only if they do, if should broadcast the transaction(s) on the
Bitcoin p2p network.
Payment messages larger than 50,000 bytes should be rejected by the
merchant's server, to mitigate denial-of-service attacks.
[[paymentack]]
PaymentACK
^^^^^^^^^^
PaymentACK is the final message in the payment protocol; it is sent from
the merchant's server to the bitcoin wallet in response to a Payment
message:
-------------------------------------
message PaymentACK {
required Payment payment = 1;
optional string memo = 2;
}
-------------------------------------
[cols=",",]
|=======================================================================
|payment |Copy of the Payment message that triggered this PaymentACK.
Clients may ignore this if they implement another way of associating
Payments with PaymentACKs.
|memo |UTF-8 encoded note that should be displayed to the customer
giving the status of the transaction (e.g. "Payment of 1 BTC for eleven
tribbles accepted for processing.")
|=======================================================================
PaymentACK messages larger than 60,000 bytes should be rejected by the
wallet application, to mitigate denial-of-service attacks. This is
larger than the limits on Payment and PaymentRequest messages as
PaymentACK contains a full Payment message within it.
[[localization]]
Localization
~~~~~~~~~~~~
Merchants that support multiple languages should generate
language-specific PaymentRequests, and either associate the language
with the request or embed a language tag in the request's merchant_data.
They should also generate a language-specific PaymentACK based on the
original request.
For example: A greek-speaking customer browsing the Greek version of a
merchant's website clicks on a "Αγορά τώρα" link, which generates a
PaymentRequest with merchant_data set to "lang=el&basketId=11252". The
customer pays, their bitcoin client sends a Payment message, and the
merchant's website responds with PaymentACK.message "σας ευχαριστούμε".
[[certificates]]
Certificates
~~~~~~~~~~~~
The default PKI system is X.509 certificates (the same system used to
authenticate web servers). The format of pki_data when pki_type is
"x509+sha256" or "x509+sha1" is a protocol-buffer-encoded certificate
chain:
---------------------------------------
message X509Certificates {
repeated bytes certificate = 1;
}
---------------------------------------
If pki_type is "x509+sha256", then the PaymentRequest message is hashed
using the SHA256 algorithm to produce the message digest that is signed.
If pki_type is "x509+sha1", then the SHA1 algorithm is used.
Each certificate is a DER [ITU.X690.1994] PKIX certificate value. The
certificate containing the public key of the entity that digitally
signed the PaymentRequest must be the first certificate. This MUST be
followed by additional certificates, with each subsequent certificate
being the one used to certify the previous one, up to (but not
including) a trusted root authority. The trusted root authority MAY be
included. The recipient must verify the certificate chain according to
[RFC5280] and reject the PaymentRequest if any validation failure
occurs.
Trusted root certificates may be obtained from the operating system; if
validation is done on a device without an operating system, the
http://www.mozilla.org/projects/security/certs/included/index.html[Mozilla
root store] is recommended.
[[extensibility]]
Extensibility
~~~~~~~~~~~~~
The protocol buffers serialization format is designed to be extensible.
In particular, new, optional fields can be added to a message and will
be ignored (but saved/re-transmitted) by old implementations.
PaymentDetails messages may be extended with new optional fields and
still be considered "version 1." Old implementations will be able to
validate signatures against PaymentRequests containing the new fields,
but (obviously) will not be able to display whatever information is
contained in the new, optional fields to the user.
If it becomes necessary at some point in the future for merchants to
produce PaymentRequest messages that are accepted *only* by new
implementations, they can do so by defining a new PaymentDetails message
with version=2. Old implementations should let the user know that they
need to upgrade their software when they get an up-version
PaymentDetails message.
Implementations that need to extend messages in this specification shall
use tags starting at 1000, and shall update the
link:bip-0070/extensions.mediawiki[extensions page] via pull-req to
avoid conflicts with other extensions.
[[references]]
References
~~~~~~~~~~
link:bip-0071.mediawiki[BIP 0071] : Payment Protocol mime types
link:bip-0072.mediawiki[BIP 0072] : Payment Protocol bitcoin: URI
extensions
Public-Key Infrastructure (X.509) working group :
http://datatracker.ietf.org/wg/pkix/charter/
Protocol Buffers : https://developers.google.com/protocol-buffers/
[[see-also]]
See Also
~~~~~~~~
Javascript Object Signing and Encryption working group :
http://datatracker.ietf.org/wg/jose/
Wikipedia's page on Invoices: http://en.wikipedia.org/wiki/Invoice
especially the list of Electronic Invoice standards
sipa's payment protocol proposal: https://gist.github.com/1237788
ThomasV's "Signed Aliases" proposal : http://ecdsa.org/bitcoin_URIs.html
Homomorphic Payment Addresses and the Pay-to-Contract Protocol :
http://arxiv.org/abs/1212.3257
BIP: 71 Title: Payment Protocol MIME types Author: Gavin Andresen <[email protected]> Status: Draft Type: Standards Track Created: 2013-07-29
[[abstract]] Abstract ~~~~~~~~ This BIP defines a MIME (RFC 2046) Media Type for Bitcoin payment request messages. [[motivation]] Motivation ~~~~~~~~~~ Wallet or server software that sends payment protocol messages over email or http should follow Internet standards for properly encapsulating the messages. [[specification]] Specification ~~~~~~~~~~~~~ The Media Type (Content-Type in HTML/email headers) for bitcoin protocol messages shall be: [cols=",",] |================================================== |Message |Type/Subtype |PaymentRequest |application/bitcoin-paymentrequest |Payment |application/bitcoin-payment |PaymentACK |application/bitcoin-paymentack |================================================== Payment protocol messages are encoded in binary. [[example]] Example ~~~~~~~ A web server generating a PaymentRequest message to initiate the payment protocol would precede the binary message data with the following headers: ------------------------------------------------ Content-Type: application/bitcoin-paymentrequest Content-Transfer-Encoding: binary ------------------------------------------------ ----------------------------------------------------- BIP: 72 Title: bitcoin: uri extensions for Payment Protocol Author: Gavin Andresen <[email protected]> Status: Draft Type: Standards Track Created: 2013-07-29 ----------------------------------------------------- [[abstract]] Abstract ~~~~~~~~ This BIP describes an extension to the bitcoin: URI scheme (BIP 21) to support the payment protocol (BIP 70). [[motivation]] Motivation ~~~~~~~~~~ Allow users to click on a link in a web page or email to initiate the payment protocol, while being backwards-compatible with existing bitcoin wallets. [[specification]] Specification ~~~~~~~~~~~~~ The bitcoin: URI scheme is extended with an additional, optional "r" parameter, whose value is a URL from which a PaymentRequest message should be fetched (characters not allowed within the scope of a query parameter must be percent-encoded as described in RFC 3986 and bip-0021). If the "r" parameter is provided and backwards compatibility is not required, then the bitcoin address portion of the URI may be omitted (the URI will be of the form: bitcoin:?r=... ). When Bitcoin wallet software that supports this BIP receives a bitcoin: URI with a request parameter, it should ignore the bitcoin address/amount/label/message in the URI and instead fetch a PaymentRequest message and then follow the payment protocol, as described in BIP 70. Bitcoin wallets must support fetching PaymentRequests via http and https protocols; they may support other protocols. Wallets must include an "Accept" HTTP header in HTTP(s) requests (as defined in RFC 2616): ------------------------------------------ Accept: application/bitcoin-paymentrequest ------------------------------------------ If a PaymentRequest cannot be obtained (perhaps the server is unavailable), then the customer should be informed that the merchant's payment processing system is unavailable. In the case of an HTTP request, status codes which are neither success nor error (such as redirect) should be handled as outlined in RFC 2616. [[compatibility]] Compatibility ~~~~~~~~~~~~~ Wallet software that does not support this BIP will simply ignore the r parameter and will initiate a payment to bitcoin address. [[examples]] Examples ~~~~~~~~ A backwards-compatible request: ------------------------------------------------------------------------------------------------------ bitcoin:mq7se9wy2egettFxPbmn99cK8v5AFq55Lx?amount=0.11&r=https://merchant.com/pay.php?h%3D2a8628fc2fbe ------------------------------------------------------------------------------------------------------ Non-backwards-compatible equivalent: -------------------------------------------------------- bitcoin:?r=https://merchant.com/pay.php?h%3D2a8628fc2fbe -------------------------------------------------------- [[references]] References ~~~~~~~~~~ http://www.w3.org/Protocols/rfc2616/rfc2616.html[RFC 2616] : Hypertext Transfer Protocol -- HTTP/1.1