diff options
-rw-r--r-- | README.mediawiki | 38 | ||||
-rw-r--r-- | bip-0001.mediawiki | 2 | ||||
-rw-r--r-- | bip-0065.mediawiki | 2 | ||||
-rw-r--r-- | bip-0107.mediawiki | 83 | ||||
-rw-r--r-- | bip-0122.mediawiki | 112 | ||||
-rw-r--r-- | bip-0122/chainid.png | bin | 0 -> 2967 bytes | |||
-rw-r--r-- | bip-0125.mediawiki | 187 | ||||
-rw-r--r-- | bip-0140.mediawiki | 113 | ||||
-rw-r--r-- | bip-0141.mediawiki | 267 | ||||
-rw-r--r-- | bip-0142.mediawiki | 157 |
10 files changed, 958 insertions, 3 deletions
diff --git a/README.mediawiki b/README.mediawiki index beb59e5..8ff6e56 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -1,4 +1,4 @@ -People wishing to submit BIPs, first should propose their idea or document to the mailing list. After discussion they should email Greg Maxwell <gmaxwell@gmail.com>. After copy-editing and acceptance, it will be published here. +People wishing to submit BIPs, first should propose their idea or document to the mailing list. After discussion they should email Luke Dashjr <luke_bipeditor@dashjr.org>. After copy-editing and acceptance, it will be published here. We are fairly liberal with approving BIPs, and try not to be too involved in decision making on behalf of the community. The exception is in very rare cases of dispute resolution when a decision is contentious and cannot be agreed upon. In those cases, the conservative option will always be preferred. @@ -338,6 +338,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0107.mediawiki|107]] +| Dynamic limit on the block size +| Washington Y. Sanchez +| Standard +| Draft +|- | [[bip-0111.mediawiki|111]] | NODE_BLOOM service bit | Matt Corallo and Peter Todd @@ -368,18 +374,48 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0122.mediawiki|121]] +| URI scheme for Blockchain references / exploration +| Marco Pontello +| Standard +| Draft +|- | [[bip-0123.mediawiki|123]] | BIP Classification | Eric Lombrozo | Informational | Draft |- +| [[bip-0125.mediawiki|125]] +| Opt-in Full Replace-by-Fee Signaling +| David Harding, Peter Todd +| Standard +| Draft +|- | [[bip-0130.mediawiki|130]] | sendheaders message | Suhas Daftuar | Standard | Draft |- +| [[bip-0140.mediawiki|140]] +| Normalized TXID +| Christian Decker +| Standard +| Draft +|- +| [[bip-0141.mediawiki|141]] +| Segregated Witness (Consensus layer) +| Eric Lombrozo, Johnson Lau, and Pieter Wuille +| Standard +| Draft +|- +| [[bip-0142.mediawiki|142]] +| Address Formats for Witness Program +| Johnson Lau +| Standard +| Draft +|- | [[bip-0143.mediawiki|143]] | Transaction signature verification for version 0 and version 1 witness program | Johnson Lau, Pieter Wuille diff --git a/bip-0001.mediawiki b/bip-0001.mediawiki index faa8029..db7a6ef 100644 --- a/bip-0001.mediawiki +++ b/bip-0001.mediawiki @@ -143,7 +143,7 @@ If you are interested in assuming ownership of a BIP, send a message asking to t ==BIP Editors== -The current BIP editor is Gregory Maxwell who can be contacted at [[mailto:gmaxwell@gmail.com|gmaxwell@gmail.com]]. +The current BIP editor is Luke Dashjr who can be contacted at [[mailto:luke_bipeditor@dashjr.org|luke_bipeditor@dashjr.org]]. ==BIP Editor Responsibilities & Workflow== diff --git a/bip-0065.mediawiki b/bip-0065.mediawiki index 1bd0da8..df995de 100644 --- a/bip-0065.mediawiki +++ b/bip-0065.mediawiki @@ -2,7 +2,7 @@ BIP: 65 Title: OP_CHECKLOCKTIMEVERIFY Author: Peter Todd <pete@petertodd.org> - Status: Draft + Status: Accepted Type: Standards Track Created: 2014-10-01 </pre> diff --git a/bip-0107.mediawiki b/bip-0107.mediawiki new file mode 100644 index 0000000..88a2c99 --- /dev/null +++ b/bip-0107.mediawiki @@ -0,0 +1,83 @@ +<pre> + BIP: 107 + Title: Dynamic limit on the block size + Author: Dr Washington Y. Sanchez <washington.sanchez@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-09-11 +</pre> + +==Abstract== + +This BIP proposes a dynamic limit to the block size based on transaction volume. + +==Motivation== + +Over the next few years, large infrastructure investments will be made into: + +# Improving global network connectivity +# Improving block propogation across the Bitcoin network +# Layer 2 services and networks for off-chain transactions +# General efficiency improvements to transactions and the blockchain + +* While there is a consensus between Bitcoin developers, miners, businesses and users that the block size needs to be increased, there is a lingering concern over the potential unintended consequences that may agument the trend towards network and mining centralization (largely driven by mining hardware such as ASICs) and thereby threaten the security of the network. +* In contrast, failing to respond to elevated on-chain transaction volume may lead to a consumer-failure of Bitcoin, where ordinary users - having enjoyed over 6 years of submitting transactions on-chain at relatively low cost - will be priced out of blockchain with the emergence of a prohibitive 'fee market'. +* These two concerns must be delicately balanced so that all users can benefit from a robust, scalable, and neutral network. + +==Specification== + +* Increases in the block size will occur in 2 phases +* '''Phase 1''' +** The block size will be increased similar to [[https://twitter.com/adam3us/status/636410827969421312|Adam Back's proposal]], as a safe runway prior to switching to Phase 2, while network and protocol infrastructure is improved +** The schedule: +*** ''2016-2017:'' 2 MB +*** ''2018-2019:'' 4 MB +*** ''2020:'' 6 MB +* '''Phase 2''' +** In 2020, the maximum block size will be increased dynamically according to sustained increases in transaction volume +** Every 4032 blocks (~4 weeks), a CHECK will be performed to determine if a raise in the maximum block size should occur +*** This calculates to a theoretical maximum of 13 increases per year +** IF of the last >= 3025 blocks were >=60% full, the maximum block size will be increased by 10% +** The maximum block size can only ever be increased, not decreased +* The default <code>limitfreerelay</code> will also be raised in proportion to maximum block size increases +** Transactions without fees can continue to be submitted and relayed on the network as per normal +** <code>limitfreerelay</code> also helps counter attempts to trigger a block size increase by 'penny-flooding' + +For example: +* When the dynamic rules for increasing the block size go live on January 1st 2020, the starting maximum block size wil be 6 MB +* IF >=3025 blocks are >= 3.6 MB, the new maximum block size become 6.6 MB. +* The theoretical maximum block size at the end of 2020 would be ~20.7 MB, assuming all 13 increases are triggered every 4 weeks by the end of the year. + +==Rationale== + +* '''Phase 1''' +** This runway has a schedule for conservative increases to the block size in order to relieve transaction volume pressure while allowing network and protocol infrastructure improvements to be made, as well as layer 2 services to emerge +* '''Phase 2''' +** Why 60% full blocks? +*** IF blocks are 60% full, they count as a ''vote'' towards increasing the block size +*** If this parameter is too low, the trigger sensitivity may be too high and vulnerable to spam attacks or miner collusion +*** Setting the parameter too high may set the trigger sensitivity too low, causing transaction delays that are trying to be avoided in the first place +*** Between September 2013-2015, the standard deviation measured from average block size (n=730 data points from blockchain.info) was ~ 0.13 MB or 13% of the maximum block size +**** If blocks needed to be 90% full before an increase were triggered, normal variance in the average block size would mean some blocks would be full before an increase could be triggered +*** Therefore, we need a ''safe distance'' away from the maximum block size to avoid normal block size variance hitting the limit. The 60% level represents a 3 standard deviation distrance from the limit. +** Why 3025 blocks? +*** The assessment period is 4032 blocks or ~ 4 weeks, with the threshold set as 4032 blocks/0.75 + 1 +*** Increases in the maximum block size should only occur after a sustained trend can be observed in order to: +***# Demonstrate a market-driven secular elevation in the transaction volume +***# Increase the cost to trigger an increase by spam attacks or miner collusion with zero fee transactions +*** In other words, increases to the maximum block size must be conservative but meaningful to relieve transaction volume pressure in response to true market demand +** Why 10% increase in the block size? +*** Increases in the block size are designed to be conservative and in balance with the number of theoretical opportunitites to increase the block size per year +*** Makes any resources spent for spam attacks or miner collusion relatively expensive to achieve a minor increase in the block size. A sustained attack would need to be launched that may be too costly, and ideally detectable by the community + +==Deployment== +''From BIP66:'' +We reuse the double-threshold switchover mechanism from BIP 34, with the same thresholds, but for nVersion = ''n''. The new rules are in effect for every block (at height H) with nVersion = ''n'' and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = ''n''. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = ''n'', nVersion = ''n-1'' blocks become invalid, and all further blocks enforce the new rules. + +==Acknowledgements== + +Thanks to Austin Hill, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. + +==Copyright== + +This work is placed in the public domain. diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki new file mode 100644 index 0000000..902aa02 --- /dev/null +++ b/bip-0122.mediawiki @@ -0,0 +1,112 @@ +<pre> + BIP: 122 + Title: URI scheme for Blockchain references / exploration + Author: Marco Pontello <marcopon@gmail.com> + Status: Draft + Type: Standards Track + Created: 29 August 2015 + Post-History: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010712.html +</pre> + +==Abstract== + +This BIP propose an URI scheme for looking up blocks, transactions, addresses on a Blockchain explorer, or in general to make proper Blockchain references + +==Motivation== + +The purpose of this URI scheme is to enable users to handle all the requests for details about blocks, transactions, etc. with their preferred tool (being that a web service or a local application). +Currently a Bitcoin client usually points to an arbitrary blockchain explorer when the user looks for the details of a transaction, or let him choose from a limited list of possible alternatives. +Other times resorting to cut&paste is needed. +The same happens with posts and messages that reference some particular txs or blocks, if they provide links at all. + +==Specification== + +The URI follow this form: + + <nowiki>blockchain:[//chain]</type/hash></nowiki> + +Where: + +{| class="wikitable" +! style="text-align: center;" | Element +! colspan="2" style="text-align: center;" | Description +! +|- +| chain +| colspan="2" | '''chain ID''' (see below) of the desired chain, leading 0s included. If omitted (which would be the usual case), Bitcoin main net is assumed. +| optional +|- +| rowspan="3" | type +| tx +| for transactions. +| rowspan="3" | +|- +| block +| for blocks (supports both hash or height). +|- +| address +| for addresses. +|- +| hash +| colspan="2" | the relevant hash to refer to (leading zeros included), or block height. +| +|} + +---- +===Definition of chain ID=== + +The '''chain ID''' of a chain is the block hash of the corresponding genesis block. For forked chains, it's the block hash of the first block after fork. + +So, for example: +<pre> +Bitcoin main : 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f +Bitcoin test : 000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943 +Bitcoin regtest: 0f9188f13cb7b2c71f2a335e3a4fc328bf5beb436012afca590b1a11466e2206 +</pre> + +An example of forked chain (Feathercoin, that forked Litecoin): + +<img src=bip-0122/chainid.png></img> + +<pre> +Litecoin : 12a765e31ffd4059bada1e25190f6e98c99d9714d334efa41a195a7e7e04bfe2 +Feathercoin: fdbe99b90c90bae7505796461471d89ae8388ab953997aa06a355bbda8d915cb +</pre> + + +==Examples== + +A transaction on Bitcoin main net: + blockchain:/tx/b462ae6eb8bdae2e060239a2a3ea5d9c3e0f9ef34d9717beb2dcf0ed42cee7da + +A block on Bitcoin main net: + blockchain:/block/00000000000000000119af5bcae2926df54ae262e9071a94a99c913cc217cc72 +or + blockchain:/block/372338 + +An address on Bitcoin main net: + blockchain:/address/16EW6Rv9P9AxFDBrZV816dD4sj1EAYUX3f + +A transaction on Bitcoin test net: + blockchain://000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943/tx/3b95a766d7a99b87188d6875c8484cb2b310b78459b7816d4dfc3f0f7e04281a + +==Rationale== + +From the point of view of a wallet (or other Blockchain related tool) developer that need to show any kind of Blockchain references, using this scheme mean that he can simply make it a blockchain: link and be done with it, without having to worry about any specific Blockchain explorer or provide a means for the user to select one. + +Blockchain explorers in turn will simply offer to handle the blockchain: URI, the first time the user visit their website, or launch/install the application, or even set themselves if there isn't already one. + +Users get the convenience of using always their preferred explorer, which can be especially handy on mobile devices, where juggling with cut&paste is far from ideal. + +== Sample implementation == + +[https://github.com/MarcoPon/blockchain-exploration Demo Blockchain: URI handler on GitHub] + +==Acknowledgements== +Thanks to Btc Drak for suggesting to provide support for different networks. +Thanks to Jorge Timon for the idea of using genesis blocks hashes to identify them. +Thanks to Richard Moore, Matt Whitlock, Andreas Schildbach for suggestions about the structure and hierarchy of the URI scheme. + +==Copyright== + +This document is placed in the public domain.
\ No newline at end of file diff --git a/bip-0122/chainid.png b/bip-0122/chainid.png Binary files differnew file mode 100644 index 0000000..ab6957a --- /dev/null +++ b/bip-0122/chainid.png diff --git a/bip-0125.mediawiki b/bip-0125.mediawiki new file mode 100644 index 0000000..63788e9 --- /dev/null +++ b/bip-0125.mediawiki @@ -0,0 +1,187 @@ +<pre> + BIP: 125 + Title: Opt-in Full Replace-by-Fee Signaling + Author: David A. Harding <dave@dtrt.org>, Peter Todd <pete@petertodd.org> + Status: Draft + Type: Standards Track + Created: 2015-12-04 +</pre> + +==Abstract== + +Many nodes today will not replace any transaction in their mempool with +another transaction that spends the same inputs, making it difficult for +spenders to adjust their previously-sent transactions to deal with +unexpected confirmation delays or to perform other useful replacements. + +The opt-in full Replace-by-Fee (opt-in full-RBF) signaling policy +described here allows spenders to add a signal to a transaction indicating +that they want to be able to replace that transaction in the future. +In response to this signal, + +* Nodes may allow transactions containing this signal to be replaced in their mempools. + +* The recipient or recipients of a transaction containing this signal may choose not to treat it as payment until it has been confirmed, eliminating the risk that the spender will use allowed replacements to defraud them. + +Nodes and recipients may continue to treat transactions without the +signal the same way they treated them before, preserving the existing +status quo. + +==Summary== + +This policy specifies two ways a transaction can signal that it is +replaceable. + +* '''Explicit signaling:''' A transaction is considered to have opted in to allowing replacement of itself if any of its inputs have an nSequence number less than (0xffffffff - 1). + +* '''Inherited signaling:''' Transactions that don't explicitly signal replaceability are replaceable under this policy for as long as any one of their ancestors signals replaceability and remains unconfirmed. + +===Implementation Details=== + +The initial implementation expected in Bitcoin Core 0.12.0 uses the following rules: + +One or more transactions currently in the mempool (original +transactions) will be replaced by a new transaction (replacement +transaction) that spends one or more of the same inputs if, + +# The original transactions signal replaceability explicitly or through inheritance as described in the above Summary section. + +# The replacement transaction pays an absolute higher fee than the sum paid by the original transactions. + +# The replacement transaction does not contain any new unconfirmed inputs that did not previously appear in the mempool. (Unconfirmed inputs are inputs spending outputs from currently unconfirmed transactions.) + +# The replacement transaction must pay for its own bandwidth in addition to the amount paid by the original transactions at or above the rate set by the node's minimum relay fee setting. For example, if the minimum relay fee is 1 satoshi/byte and the replacement transaction is 500 bytes total, then the replacement must pay a fee at least 500 satoshis higher than the sum of the originals. + +# The number of original transactions to be replaced and their descendant transactions which will be evicted from the mempool must not exceed a total of 100 transactions. + +The initial implementation may be seen in +[https://github.com/bitcoin/bitcoin/pull/6871 Bitcoin Core PR#6871] +and specifically the master branch commits from +5891f870d68d90408aa5ce5b597fb574f2d2cbca to +16a2f93629f75d182871f288f0396afe6cdc8504 (inclusive). + +===Receiving wallet policy=== + +Wallets that display unconfirmed transactions to users or that provide +data about unconfirmed transactions to automated systems should consider +doing one of the following: + +# Conveying additional suspicion about opt-in full-RBF transactions to the user or data consumer. + +# Ignoring the opt-in transaction until it has been confirmed. + +Because descendant transactions may also be replaceable under this +policy through inherited signaling, any method used to process opt-in +full-RBF transactions should be inherited by any descendant transactions +for as long as any ancestor opt-in full-RBF transactions remain +unconfirmed. + +===Spending wallet policy=== + +Wallets that don't want to signal replaceability should use either a max +sequence number (0xffffffff) or a sequence number of (0xffffffff-1) when +then also want to use locktime; all known wallets currently do this. +They should also take care not to spend any unconfirmed transaction that +signals replaceability explicitly or through inherited signaling; most wallets also +currently do this by not spending any unconfirmed transactions except +for those they created themselves. + +Wallets that do want to make replacements should use explicit signaling +and meet the criteria described above in the Implementation Details +section. A +[https://en.bitcoin.it/wiki/Transaction_replacement Bitcoin Wiki page] +has been created to help wallet authors track deployed mempool policies +relating to transaction replacement. + +The initial implementation makes use of P2P protocol reject messages for +rejected replacements, allowing P2P clients to determine whether their +replacements were initially accepted by their peers. Standard P2P +lightweight client practice of sending to some peers while listening for +relays from other peers should allow clients to determine whether the +replacement has propagated. + +==Motivation== + +Satoshi Nakamoto's original Bitcoin implementation provided the +nSequence number field in each input to +[https://github.com/trottier/original-bitcoin/blob/master/src/main.cpp#L434 allow replacement] +of transactions containing that input within the +mempool. When receiving replacements, nodes were supposed to replace +transactions whose inputs had lower sequence numbers with transactions +that had higher sequence numbers. + +In that implementation, replacement transactions did not have to pay +additional fees, so there was no direct incentive for miners to +include the replacement and no built-in rate limiting that prevented +overuse of relay node bandwidth. Nakamoto +[https://github.com/bitcoin/bitcoin/commit/05454818dc7ed92f577a1a1ef6798049f17a52e7#diff-118fcbaaba162ba17933c7893247df3aR522 removed replacement] +from Bitcoin version 0.3.12, leaving only the +comment, "Disable replacement feature for now". + +Replacing transactions with higher-fee transactions provided a way for +spenders to align their desires with miners, but by the time a +Replace-by-Fee (RBF) patch was available to re-enable replacement, some +receivers had begun to expect that the first version of a transaction +they saw was highly likely to be the version of the transaction to be +confirmed, and so some users advocated that replacement should be +disallowed. + +To address those concerns, a variation on RBF was created that +required that the replacement transaction pay all of same outputs as +the original transaction in equal or greater amount. This was called +RBF First Seen Safe (RBF-FSS), and the original RBF became known as +full-RBF. Although agreeable to recipients who relied on the +first-seen version of a transaction, each use of RBF-FSS required +adding an extra input to a transaction, resulting in wallets being +unable to use it if they had no spare inputs, a loss of privacy when +inputs from different origins get used in the same transaction, and a +wasteful increase in transaction byte size. + +Opt-in full-RBF uses Nakamoto's original semantics (with a slight +tweak to allow locktime users to opt-out) to signal that replacement +is possible, providing first-seen users with the ability to ignore +those transactions while also allowing for the efficiency benefits +of full-RBF. + +There are no known problematic interactions between opt-in full-RBF and +other uses of nSequence. Specifically, opt-in full-RBF is compatible +with consensus-enforced locktime as provided in the Bitcoin 0.1 +implementation, draft BIP68 (Relative lock-time using consensus-enforced +sequence numbers), and draft BIP112 (CHECKSEQUENCEVERIFY). + +==Deployment== + +Now, and since Bitcoin's first release, 100% of the network hash rate +mines transactions using opt-in full-RBF semantics (sequence less than +(0xffffffff - 1)). + +Opt-in full-RBF as a default mempool replacement policy among nodes +and miners is expected to become widespread as they upgrade to Bitcoin +Core 0.12.0 (release expected Jan/Feb 2016) and similar node software +such as Bitcoin LJR. + +Actual replacement may be unreliable until two conditions have been satisfied: + +# Enough nodes have upgraded to support it, providing a relay path for replacements to go from spending wallets to miners controlling significant amounts of hash rate. + +# Enough hash rate has upgraded to support replacement, allowing for reasonable probability that a replacement can be mined. + +==Client support== + +No known wallet currently creates transactions by default with +nSequence set below (0xffffffff - 1), so no known existing wallet +explicitly signals replaceability by default. No known popular wallet +spends other users' unconfirmed transactions by default, so no known +existing wallets signals inherited replaceability. + +==See also== + +# [https://en.bitcoin.it/wiki/Transaction_replacement Transaction Replaceability on Bitcoin Wiki] targeted at helping wallet authors use RBF + +# Tools for creating opt-in full-RBF transactions: https://github.com/petertodd/replace-by-fee-tools#replace-by-fee-tools + +# [https://www.reddit.com/r/Bitcoin/comments/3urm8o/optin_rbf_is_misunderstood_ask_questions_about_it/ Reddit: Questions about opt-in RBF] targeted at helping community members understand opt-in full-RBF + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-0140.mediawiki b/bip-0140.mediawiki new file mode 100644 index 0000000..b187a49 --- /dev/null +++ b/bip-0140.mediawiki @@ -0,0 +1,113 @@ +<pre> + BIP: 140 + Title: Normalized TXID + Author: Christian Decker <decker.christian@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-10-14 +</pre> +== Abstract == + +This BIP describes the use of normalized transaction IDs (NTXIDs) in order to eliminate transaction malleability, both in the third-party modification scenario as well as the participant modification scenario. The transaction ID is normalized by removing the signature scripts from transactions before computing its hash. The normalized transaction hashes are then used during the signature creation and signature verification of dependent transactions. + +== Motivation == + +Transaction malleability refers to the fact that transactions can be modified, either by one of the signers by re-signing the transaction or a third-party by modifying the signature representation. This is a problem since any modification to the serialized representation also changes the hash of the transaction, which is used by spending transaction to reference the funds that are being transferred. If a transaction is modified and later confirmed by ending up in the blockchain all transactions that depended on the original transaction are no longer valid, and thus orphaned. + +BIPs 62<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki|BIP 62 - Dealing with malleability]]</ref> and 66<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki|BIP 66 - Strict DER signatures]]</ref> alleviate the problem of third-party modification by defining a canonical representation of the signatures. However, checking the canonical representation is complex and may not eliminate all sources of third-party malleability. Furthermore, these BIPs do not address modifications by one of the signers, i.e., re-signing the transaction, because signers can produce any number of signatures due to the random parameter in ECDSA. + +This proposal eliminates malleability by removing the malleable signatures from the hash used to reference the outputs spent by a transaction. The new hash used to reference an output is called the ''normalized transaction ID''. The integrity of all data that is used to reference the output is guaranteed by the signature itself, and any modification that would change the normalized transaction ID would also invalidate the signature itself. + +Besides eliminating transaction malleability as a source of problems it also allows the use of transaction templates. Transaction templates simplify higher level protocols and allows new uses. They allow an unsigned template transaction to be used as a basis for a sequence of transaction and only once the sequence matches the signers' expectations they provide the necessary signatures for the template to become valid, thus opting in to the sequence. + +== Specification == + +The use of normalized transaction IDs is introduced as a softfork. The specification is divided into three parts: + +* Computation of the normalized transaction ID +* Introduction of a new extensible signature verification opcode to enable softfork deployment +* Changes to the UTXO tracking to enable normalized transaction ID lookup + +=== Normalized Transaction ID computation === + +In order to calculate the normalized transaction ID, the signature script is stripped from each input of the transaction of non-coinbase transactions and each input is normalized. Stripping the signature script is achieved by setting the script's length to 0 and removing the <code>uchar[]</code> array from the <code>TxIn</code>.<ref>[[https://en.bitcoin.it/wiki/Protocol_Specification#tx|Protocol Specification: TX]]</ref> +Inputs are then normalized by replacing the hash of each previous transaction with its normalized version if available, i.e., the normalized hash of the previous transaction that created the output being spent in the current transaction. Version 1 transactions do not have a normalized transaction ID hence the non-normalized transaction ID is used for input normalization. + +The normalized transaction ID is then computed as the double <code>SHA 256</code> hash of the normalized transaction matching the existing transaction ID computation. The normalized transaction ID remains unchanged even if the signatures of the transaction are replaced/malleated and describe a class of semantically identical transactions. In the following we use ''transaction instance ID'' to refer to the transaction ID computed on the transaction including signatures. Normalized transaction IDs for coinbase transactions are computed with the signature script in the coinbase input, in order to avoid hash collisions. + +=== OP_CHECKSIGEX === +This BIP introduces a new opcode <code>OP_CHECKSIGEX</code> which replaces <code>OP_NOP4</code>. <code>OP_CHECKSIGEX</code> subsumes <code>OP_CHECKSIGVERIFY</code> and <code>OP_CHECKMULTISIGVERIFY</code>, and extends them by accepting a new <code>VERSION</code> parameter. The version parameter is a single integer pushed onto the stack before invoking <code>OP_CHECKSIGEX</code> and is used to group and evolve future versions of signature checking opcodes. + +When executed <code>OP_CHECKSIGEX</code> pops the version from the stack and then performs the signature check according to the specified version. If the verifying client does not support the specified version, i.e., the version was defined after the release of the client, the client must treat the <code>OP_CHECKSIGEX</code> as an <code>OP_NOP</code>. + +==== Version 1 ==== + +The first version of <code>OP_CHECKSIGEX</code> (<code>VERSION=1</code>) implements normalized transaction IDs and uses Schnorr signatures instead of the current ECDSA signatures. + +Version 1 introduces the following new standard script format: + + m {pubkey}...{pubkey} n v OP_CHECKSIGEX + +with matching scriptSig format: + + {signature}...{signature} + +This is the standard ''m-of-n'' script defined in [https://github.com/bitcoin/bips/blob/master/bip-0011.mediawiki BIP 11] with an additional version parameter <code>v</code> and the new opcode. Singlesig transactions are encoded as ''1-of-1'' transactions. + +The existing <code>OP_CHECKMULTISIG</code> and <code>OP_CHECKMULTISIGVERIFY</code> have a bug<ref>[[https://bitcoin.org/en/developer-guide#multisig|Developer Documentation - Multisig]]</ref> that pops one argument too many from the stack. This bug is not reproduced in the implementation of OP_CHECKSIGEX, so the canonical solution of pushing a dummy value onto the stack is not necessary. + +The normalization is achieved by normalizing the transaction before computing the signaturehash, i.e., the hash that is signed. +The transaction must be normalized by replacing all transaction IDs in the inputs by their normalized variants and stripping the signature scripts. The normalized transction IDs are computed as described in the previous section. This normalization step is performed both when creating the signatures as well as when checking the signatures. + +=== Tracking Normalized Transaction IDs === + +The transaction version is bumped to 2. The new version signals to clients receiving the transaction that they should track the normalized transaction ID along with the transaction instance ID in the unspent transaction output (UTXO) set. Upon receiving a version 2 transaction the client computes the normalized transaction ID, annotates the outputs with it, and adds them into the UTXO set indexed by the transaction instance ID as before. Transactions continue using the transaction instance ID to reference the outputs, but while checking the signature they may get normalized. All network messages continue to use the transaction instance ID to reference the transaction, specifically <code>inv</code>, <code>getdata</code>, <code>tx</code> and <code>block</code> messages still use transaction instance IDs, not the normalized transaction IDs. + +Outputs created by version 1 transactions are not annotated with the normalized transaction ID, and when normalizing the hashes in transaction inputs referencing version 1 outputs are not modified. + +== Rationale == + +=== Normalization === +Normalized transaction IDs are provably non-malleable since no data is included in the signaturehash whose integrity is not also proven in the signature, thus any modification causing the hash to change will also invalidate the signature. +Normalized transactions are secure as they still use cryptographic hashes over all the semantic information of the transaction, i.e., the inputs, outputs and metadata, thus it is still computationally infeasible to cause a hash collision between transactions. + +There are a number of advantages to using normalized transaction IDs: + +* Like BIP 62 and BIP 66 it solves the problem of third-parties picking transactions out of the network, modifying them and reinjecting them. +* ''m-of-n'' multisig outputs are often used in higher level protocols<ref>[[http://www.tik.ee.ethz.ch/file/716b955c130e6c703fac336ea17b1670/duplex-micropayment-channels.pdf|A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels ]]</ref><ref>[[http://lightning.network/lightning-network-paper.pdf|The Bitcoin Lightning Network: +Scalable Off-Chain Instant Payments]]</ref> in which several parties sign a transaction. Without normalized transaction IDs it is trivial for one party to re-sign a transaction, hence changing the transaction hash and invalidating any transaction built on top of its outputs. Normalized transaction IDs force the ID not to change, even if a party replaces its signature. +* Many higher level protocols build structures of transactions on top of multisig outputs that are not completely signed. This is currently not possible without one party holding a fully signed transaction and then calculating the ID. It is desirable to be able to build successive transactions without one party collecting all signatures, and thus possibly lock in funds unilaterally. Normalized transaction IDs allow the use of transaction templates, i.e., completely unsigned transactions upon which further transactions can be built, and only once every party is assured the structure matches its expectations it signs the template, thus validating the template. + +The only occurence in which transactions can still be modified unilaterally is in the case <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code> or <code>SIGHASH_ANYONECANPAY</code> is used. This however is not problematic since in these cases the creator of the transaction explicitly allows modification. + +In case of a transaction becoming invalid due to one of the inputs being malleated it is necessary to modify the spending transaction to reference the modified transaction ID. However, the signatures, which only use the normalized IDs, remain valid as long as the semantics of the funding transaction remain unchanged. An observer in the network may fix the transaction and reinject a corrected version. + +Using version 2 for transactions is an explicit opt-in to the normalized ID tracking and a simple upgrade for existing clients. It avoids having to reprocess the entire blockchain and computing the normalized transaction IDs for existing outputs in the UTXO. This would be further complicated by having to recursively compute normalized transaction IDs down to the coinbase transactions which created the coins. + +Tracking the normalized transaction IDs in the UTXO requires the storage of an additional hash per transaction whose outputs are not completely spent, which at 7,000,000 transactions with unspent outputs amounts to 224MB additional storage on disk. + +The coinbase transactions have been checked for hash-collisions and no collisions were found except for the coinbase transactions in blocks at heights 91842 and 91880, which are known to be identical<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0030.mediawiki|BIP 30 - Duplicate transactions]]</ref>, and motivated the introduction of BIP 34.<ref>[[https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki|Block v2, Height in Coinbase]]</ref> Since coinbase transactions are invalid if transmitted outside of a block it is not possible to modify them on the fly and since they only mature after being included for a long time in the blockchain they are considered safe. + +=== OP_CHECKSIGEX === + +The new opcode <code>OP_CHECKSIGEX</code> was introduced in order to allow the use of normalized transaction IDs as a softfork and in order to keep the number of <code>OP_NOP</code>s needed to a bare minimum, while enabling future soft-fork updates to the signing algorithms. + +The additional argument containing the version can be pushed on the stack using a single byte up to version 16 (<code>OP_1</code> - <code>OP_16</code>), resulting in one byte overhead for this script type. Using the standard multisig format also for 1-of-1 transactions add an additional 2 bytes, however it also removes the bug requiring a dummy push, resulting in a single byte overhead. +Furthermore, using Schnorr signatures instead of ECDSA brings a number of improvements that reduce the size of transactions (''m-of-m'' is the same size as ''1-of-1'') and increase verification speed (batch signature validation by summing up keys and signatures). The code is already in bitcoin/secp256k1 and can be merged in. We limited the description of this BIP to re-using BIP 11 style ''m-of-n'' scripts to keep it short, however Schnorr also allows a number of more complex applications which we defer to future BIPs. + +Version 0 was intentionally skipped in order to guarantee that the top-most element before <code>OP_CHECKSIGEX</code> is non-zero. This is necessary to guarantee that non-upgraded clients, which interpret <code>OP_CHECKSIGEX</code> as <code>OP_NOP4</code>, do not end up with a zero value on top of the stack after execution, which would be interpreted as script failure. + +=== Impact === + +This is a softfork which replaces <code>OP_NOP4</code> with the new implementation of <code>OP_CHECKSIGEX</code>, as such the impact on the network is minimal. Wallets that do not implement this opcode will not be able to verify the validity of the scripts, however if transactions using <code>OP_CHECKSIGEX</code> are included in blocks they will accept them and track the inputs correctly. This is guaranteed since the transaction inputs still use the non-normalized transaction ID to reference the outputs to be claimed, hence non-upgraded wallets can still lookup the outputs and mark them as spent. Furthermore, clients that do not implement this BIP are unable to identify outputs using this script as their own, however upgrading and rescanning the blockchain will make them available. + +== See also == + +* [[bip-0062.mediawiki|BIP 62: Dealing with malleability]] +* [[bip-0066.mediawiki|BIP 66: Strict DER Signatures]] + +== References == +<references> + +==Copyright== +This document is placed in the public domain.
\ No newline at end of file diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki new file mode 100644 index 0000000..ac44d87 --- /dev/null +++ b/bip-0141.mediawiki @@ -0,0 +1,267 @@ +<pre> + BIP: 141 + Title: Segregated Witness (Consensus layer) + Author: Eric Lombrozo <elombrozo@gmail.com> + Johnson Lau <jl2012@xbt.hk> + Pieter Wuille <pieter.wuille@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-12-21 +</pre> + +==Abstract== + +This BIP defines a new structure called a "witness" that is committed to blocks separately from the transaction merkle tree. This structure contains data required to check transaction validity but not required to determine transaction effects. In particular, scripts and signatures are moved into this new structure. + +The witness is committed in a tree that is nested into the block's existing merkle root via the coinbase transaction for the purpose of making this BIP soft fork compatible. A future hard fork can place this tree in its own branch. + +==Motivation== + +The entirety of the transaction's effects are determined by output consumption (spends) and new output creation. Other transaction data, and signatures in particular, are only required to validate the blockchain state, not to determine it. + +By removing this data from the transaction structure committed to the transaction merkle tree, several problems are fixed: + +# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was authorized is no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach (BIP62): +#* It prevents involuntary transaction malleability for any type of scripts, as long as all inputs are signed (with at least one CHECKSIG or CHECKMULTISIG operation) +#* In the case of an m-of-n CHECKMULTISIG script, a transaction is malleable only with agreement of m private key holders (as opposed to only 1 private key holder with BIP62) +#* It prevents involuntary transaction malleability due to unknown ECDSA signature malleability +#* It allows creation of unconfirmed transaction dependency chains without counterparty risk, an important feature for offchain protocols such as the Lightning Network +# '''Transmission of signature data becomes optional'''. It is needed only if a peer is trying to validate a transaction instead of just checking its existence. This reduces the size of SPV proofs and potentially improves the privacy of SPV clients as they can download more transactions using the same bandwidth. +# '''Some constraints could be bypassed with a soft fork''' by moving part of the transaction data to a structure unknown to current protocol, for example: +#* Size of witness could be ignored / discounted when calculating the block size, effectively increasing the block size to some extent +#* Hard coded constants, such as maximum data push size (520 bytes) or sigops limit could be reevaluated or removed +#* New script system could be introduced without any limitation from the existing script semantic +# '''Additional data required for fraud proofs can be added to witness'''. Extra data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify. +#* Backlinks for the outputs spent by the transaction's inputs can be provided. These backlinks consist of a block hash and an offset that thin clients can easily query and check to verify that the outputs exist. +#* Sum trees for transaction inputs and outputs can be committed making it possible to construct short proofs that no new coins are created in any noncoinbase transaction and that the miner does not add excessive fees to the coinbase transaction. + +==Specification== + +=== Commitment structure === + +!!!DRAFT ONLY!!! + +A new block rule is added which requires a commitment to the witness hashes in the coinbase (or an OP_RETURN output of a specific transaction, or somewhere else) + +(Hardfork after x year to move the commitment to block header?) + +Witness hash is the double SHA256 of a transaction including witnesses: http://blockhawk.net/diagrams/witnesstx.png. For the coinbase transaction, its witness hash is assumed to be 0x0000....0000. + +A witness root hash is calculated with all those witness hashes as leaves, in a way similar to the hashMerkleRoot in the block header. + +No witness data is allowed in blocks that don't commit to witness data, as this would otherwise leave room from spam. + +==== Proposal 1: balance tree (the current implementation) ==== +The commitment is a push of exactly 41 bytes: +*The first 4 bytes are commitment header: 0xaa21a9ed +*The next 4 bytes describe a nonce +*The next 1 byte is the "levels bytes", describes the number of levels in a Merkle tree (0 to 32) +*The next 32 bytes is a commitment root hash (not the witness root hash) + +Locator of the witness root hash is defined as: + +<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> + +The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. + +The coinbase's input's witness must consist of a single byte array of 32 * levels bytes, and are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. + +====Proposal 2: imbalance tree==== +The commitment is a push of exactly 40 bytes: +*The first 4 bytes are commitment header: 0xaa21a9ed +*The next 4 bytes describe a nonce +*The next 32 bytes is a commitment root hash (not the witness root hash) + +Locator of the witness root hash is defined as: + +<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> + +The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. + +The coinbase's input's witness must consist of a single byte array, which the size must be a multiple of 32 bytes but not bigger than 32*32 bytes. These are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. Depth of the commitment is determined by the length of the path. If the depth of the tree is 0, the path should be represented by 0x00, and the witness root hash will be same as the commitment root hash. + +=== Block size limit === +Blocks are currently limited to 1 MB total size. We change this restriction as follows: + +We define a base block size s<sub>b</sub> consisting of the existing header and transactions, a witness size s<sub>w</sub> consisting of only the size of the witness data, and a virtual block size s<sub>v</sub> = s<sub>b</sub> + s<sub>w</sub>/4. + +The new rule is s<sub>v</sub> <= 1 MB. + +=== Witness program === + +* A scriptPubKey (or redeemScript as defined in BIP16/P2SH) that consists of a 1-byte push opcode (for 0 to 16) followed by a data push between 2 and 32 bytes gets a new special meaning. The value of the first push is called the "version byte". The following byte vector pushed is called the "witness program". +** In case the scriptPubKey pushes a version byte and witness program directly, the scriptSig must be exactly empty. +** In case the redeemScript pushes a version byte and witness program, the scriptSig must be exactly the single push of the redeemScript. + +** If the version byte is 0, the WP is the actual script. +*** The script is executed after normal script evaluation but with data from the witness rather than the scriptSig. +*** The program must not fail, and result in exactly a single TRUE on the stack. +** If the version byte is 1, the WP must be 32 bytes, as a SHA256 hash of the actual script. +*** The witness must consist of an input stack to feed to the program, followed by the serialized program. +*** The serialized program is popped off the initial witness stack. Hash of the serialized program must match the hash pushed in the witness program. +*** The serialized program is deserialized, and executed after normal script evaluation with the remaining witness stack. +*** The script must not fail, and result in exactly a single TRUE on the stack. +** If the version byte is 2 to 16, no further interpretation of the witness program or witness happens. + +=== Other consensus critical constraints === + +== Block size analysis == +WORK IN PROGRESS + +Definitions: +<pre> + Core block size (CBS): The block size as seen by a non-upgrading full node + Witness size (WS): The total size of witness data in a block + Total block size (TBS): CBS + WS + Witness discount (WD): A discount factor for witness data in VBS calculation (1 = no discount) + Virtual block size (VBS): CBS + (WS * WD) + Witness adoption (WA): Proportion (in size) of new format transactions among all transactions + Prunable ratio (PR): Proportion of signature data size in a transaction +</pre> + +With some transformation it could be shown that: +<pre> + TBS = CBS / (1 - WA * PR) + = VBS / (1 - WA * PR * (1 - WD)) +</pre> + +In order to keep the proposal as a soft fork, the CBS must not have a upper limit higher than 1MB. + +The PR heavily depends on the transaction script type and input-output ratio. For example, the PR of 1-in 2-out P2PKH and 1-in 1-out 2-of-2 multisig P2SH are about 47% and 72% respectively. According to the data presented by Pieter Wuille on 7 December 2015, the current average PR on the blockchain is about 60%. + + + +== Examples == + +=== Version 0 witness program === + +The following example is a version 0 witness program, equivalent to the existing Pay-to-Pubkey-Hash (P2PKH) output. + + witness: <signature> <pubkey> + scriptSig: (empty) + scriptPubKey: OP_0 <0x76A914{20-byte-hash-value}88AC> + +The OP_0 indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: + + DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + +The script is executed with the data from witness + + <signature> <pubkey> DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + +Comparing with a P2PKH output, the witness program equivalent occupies 2 more bytes in the scriptPubKey, while moving the signature and public key from scriptSig to witness. + +=== Version 1 witness program === + +The following example is an 1-of-2 multi-signature version 1 witness program. + + witness: 0 <signature1> <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> + scriptSig: (empty) + scriptPubKey: OP_1 <0x{32-byte-hash-value}> + +The OP_1 in scriptPubKey indicates the following push is a version 1 witness program. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash-value in scriptPubKey, and deserialized: + + 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + +The script is executed with the remaining data from witness: + + 0 <signature1> 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + +Since the actual program is larger than 32 bytes, it cannot be accommodated in a version 0 witness program. A version 1 witness program allows arbitrarily large script as the 520-byte push limit is bypassed. + +The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of P2SH. The increased size improves security against possible collision attacks, as 2^80 work is not infeasible anymore (By the end of 2015, 2^84 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent P2SH output but is moved to witness. + +=== Witness program nested in Pay-to-Script-Hash === + +The following example is the same 1-of-2 multi-signature version 1 witness program, but nested in a P2SH output. + + witness: 0 <signature1> <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> + scriptSig: <0x5120{32-byte-hash-value}> + scriptPubKey: HASH160 <20-byte-hash-value> EQUAL + +The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash-value in scriptPubKey, and interpreted as: + + OP_1 <0x{32-byte-hash-value}> + +The version 1 witness program is then executed as described in the last example + +Comparing with the last example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig, which is not prunable in transmission. Although a nested witness program is less efficient in many ways, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. + +=== Trust-free unconfirmed transaction dependency chain === +Segregated witness fixes the problem of transaction malleability fundamentally, which enables the building of unconfirmed transaction dependency chains in a trust-free manner. + +Two parties, Alice and Bob, may agree to send certain amount of Bitcoin to a 2-of-2 multisig output (the "funding transaction"). Without signing the funding transaction, they may create another transaction, time-locked in the future, spending the 2-of-2 multisig output to third account(s) (the "spending transaction"). Alice and Bob will sign the spending transaction and exchange the signatures. After examining the signatures, they will sign and commit the funding transaction to the blockchain. Without further action, the spending transaction will be confirmed after the lock-time and release the funding according to the original contract. It also retains the flexibility of revoking the original contract before the lock-time, by another spending transaction with shorter lock-time, but only with mutual-agreement of both parties. + +Such setups is not possible with BIP62 as the malleability fix, since the spending transaction could not be created without both parties first signing the funding transaction. If Alice reveals the funding transaction signature before Bob does, Bob is able to lock up the funding indefinitely without ever signing the spending transaction. + +Unconfirmed transaction dependency chain is a fundamental building block of more sophisticated payment networks, such as duplex micropayment channel and the Lightning Network, which have the potential to greatly improve the scalability and efficiency of the Bitcoin system. + +== Future extensions == +=== Compact fraud proof for SPV nodes === +Bitcoin right now only has two real security models. A user either runs a full-node which validates every block with all rules in the system, or a SPV (Simple Payment Verification) client which only validates the headers as a proof of publication of some transactions. The Bitcoin whitepaper suggested that SPV nodes may accept alerts from full nodes when they detect an invalid block, prompting the SPV node to download the questioned blocks and transactions for validation. This approach, however, could become a DoS attack vector as there is virtually no cost to generate a false alarm. An alarm must come with a compact, yet deterministic fraud proof. + +In the current Bitcoin protocol, it is possible to generate compact fraud proof for almost all rules except a few: + +# It is not possible to prove a miner has introduced too many Bitcoins in the coinbase transaction outputs without showing the whole block itself and all input transactions. +# It is not possible to prove the violation of any block specific constraints, such as size and sigop limits, without showing the whole block (and all input transactions in the case of sigop limit) +# It is not possible to prove the spending of a non-existing input without showing all transaction IDs in the blockchain way back to the genesis block. + +It is possible to prove the first 2 types of fraud if a block is committed to a Merkle-sum-tree of the fee, size, and sigop count of each transaction. It is also possible to prove the last type of fraud if a block is committed to a Merkle tree with the originating block height and transaction index of all inputs. These commitments could be included in the extensible witness commitment through a soft fork and will be transparent to nodes that do not understand such new rules. + +=== New script system === +Since a version byte is pushed before a witness program, and programs with unknown versions are always considered as anyone-can-spend script, it is possible to introduce any new script system with a soft fork. The witness as a structure is not restricted by any existing script semantics and constraints, the 520-byte push limit in particular, and therefore allows arbitrarily large scripts and signatures. + +Examples of new script system include Schnorr signatures which reduce the size of multisig transactions dramatically, Lamport signature which is quantum computing resistance, and Merklized abstract syntax trees which allow very compact witness for conditional scripts with extreme complexity. + +The 32-byte limitation for witness program could be easily extended through a soft fork in case a stronger hash function is needed in the future. The version byte is also expandable through a softfork. + +=== Per-input lock-time and relative-lock-time === +Currently there is only one nLockTime field in a transaction and all inputs must share the same value. BIP68 enables per-input relative-lock-time using the nSequence field, however, with a limited lock-time period and resolution. + +With a soft fork, it is possible to introduce a separate witness structure to allow per-input lock-time and relative-lock-time, and a new script system that could sign and manipulate the new data (like BIP65 and BIP112). + +== Backward compatibility == +As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs as anyone-can-spend scripts (except a few edge cases in version 0 witness programs which are provably unspendable with original script semantics). Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. Non-upgraded nodes are strongly encouraged to upgrade in order to take advantage of the new features. + +'''What a non-upgraded wallet can do''' + +* Receiving bitcoin from non-upgraded and upgraded wallets +* Sending bitcoin to non-upgraded wallets +* Sending bitcoin to upgraded wallets using a P2SH address (a less efficient way to use segregated witness) + +'''What a non-upgraded wallet cannot do''' + +* Validating segregated witness transaction. It assumes such a transaction is always valid +* Sending bitcoin to upgraded wallets using a native witness program (a more efficient way to use segregated witness) + +== Deployment == + +We reuse the double-threshold IsSuperMajority() switchover mechanism used in +BIP65 with the same thresholds, but for nVersion = 5. The new rules are +in effect for every block (at height H) with nVersion = 5 and at least +750 out of 1000 blocks preceding it (with heights H-1000..H-1) also +have nVersion >= 5. Furthermore, when 950 out of the 1000 blocks +preceding a block do have nVersion >= 5, nVersion < 5 blocks become +invalid, and all further blocks enforce the new rules. + +(It should be noted that BIP9 involves permanently setting a high-order bit to +1 which results in nVersion >= all prior IsSuperMajority() soft-forks and thus +no bits in nVersion are permanently lost.) + + +=== SPV Clients === + +While SPV clients are unable to fully validate blocks, +they are able to validate block headers and, thus, can check block version and proof-of-work. +SPV clients should reject nVersion < 5 blocks if 950 out of 1000 preceding blocks have +nVersion >= 5 to prevent false confirmations from the remaining 5% of +non-upgraded miners when the 95% threshold has been reached. + +== Credits == +Special thanks to Gregory Maxwell for originating many of the ideas in this BIP and Luke-Jr for figuring out how to deploy this as a soft fork. + +== Reference Implementation == +https://github.com/sipa/bitcoin/commits/segwit + +== Copyright == +This document is placed in the public domain. diff --git a/bip-0142.mediawiki b/bip-0142.mediawiki new file mode 100644 index 0000000..7efeca7 --- /dev/null +++ b/bip-0142.mediawiki @@ -0,0 +1,157 @@ +<pre> + BIP: 142 + Title: Address Formats for Witness Program + Author: Johnson Lau <jl2012@xbt.hk> + Status: Draft + Type: Standards Track + Created: 2015-12-24 +</pre> + +== Abstract == + +This BIP describes 2 new types of Bitcoin address to support native Segregated Witness (segwit) transactions. The first type resembles the original P2PKH base-58 address. The second type is a z-base-32 representation of a witness program with Damm algorithm checksum, which supports arbitrarily complex transactions, and is forward compatible to new version witness programs in the future. + +== Motivation == + +To define standard payment addresses for native segwit transactions to promote early adoption of the more efficient transaction method. + +== Specification == + +=== P2PKH segwit address === + +The first new Bitcoin address format defined is specific to pay-to-public-key-hash segwit transaction. The scriptPubKey is a single push of version-0 witness program in this form, + <0x0076A914{20-byte-hash-value}88AC> +The new address is encoded exactly in the same way as the original pay-to-public-key-hash address: + base58-encode: [1-byte version][20-byte-hash-value][4-byte checksum] +Version byte is 0x19 for a main-network address, 0x41 for a testnet address. The following 20-byte is the public key hash. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and public key hash. + +All addresses generated with this scheme will a constant length of 34 characters, with a "B" prefix for main-network and "T" prefix for testnet. + +=== General segwit address === + +The second new bitcoin address format defined is applicable to witness program of version 0 to 15 with a length of 2 to 32 bytes. + +The z-base-32 character set is used: +{|class="wikitable" style="width:40ex; text-align: center; margin: 0 auto 0 auto;" +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +!width="12%"|Value +!width="12%"|Symbol +|- +| 0 || y || 8 || e || 16 || o || 24 || a +|- +| 1 || b || 9 || j || 17 || t || 25 || 2 +|- +| 2 || n || 10 || k || 18 || 1 || 26 || 4 +|- +| 3 || d || 11 || m || 19 || u || 27 || 5 +|- +| 4 || r || 12 || c || 20 || w || 28 || h +|- +| 5 || f || 13 || p || 21 || i || 29 || 7 +|- +| 6 || g || 14 || q || 22 || s || 30 || 6 +|- +| 7 || 8 || 15 || x || 23 || z || 31 || 9 +|} + +It is case-insensitive and includes all alphanumeric characters excluding 0, 2, l, v. The order of alphabet is chosen so that less ambiguous alphabet characters will appear more frequently than others. + +An address is a 270-bit string in z-base-32 with the following components: + + 5 address version bits + 5 length bits + 4 witness program version bits + 256 witness program bits + +The address version bits is 00001<sub>b</sub> for the main-network and 11001<sub>b</sub> for the testnet. + +Value of the length bits is the length of the witness program in byte minus 1. + +Witness program version bits indicates version of the witness program (v0 to v15). + +The witness program is padded with leading 0<sub>b</sub> to 256 bits. + +The 270-bit string is transformed to z-base-32 with 54 digits. + +The 54-digit raw address is then divided into 9 equal segments. For each segment, a checksum is calculated with Damm algorithm and appended to the end of the segment. This makes the length increases to 63 digits. + +A second round of checksum is calculated by taking the digits in the same position of the 9 segments, and appended to the end of the address. This is the final address with 69 digits. + + +== Rationale == + +The segregated witness soft fork (BIP x) defines 2 ways of encoding "witness program", a data push of 2 to 32 bytes: + +* A native witness program output is a scriptPubKey with a push of version byte followed by a push of witness program, and nothing else; +* A witness program in P2SH is a P2SH redeemScript with a push of version byte followed by a push of witness program, while the scriptPubKey looks like a normal P2SH output. + +As the P2SH address has been defined in 2012, using witness program in P2SH allows most existing wallets to pay a segwit-compatible wallet without any upgrade. However, this method requires more block space and is less collision-resistance than a native witness program, and is only a short-term solution to make the transition smoother. Eventually, all users are expected to use the more efficient native witness program as the primary payment method. + +The drawbacks of Bitcoin addresses have been extensively discussed in BIP13. Since then, better payment methods have been proposed or deployed, for example: +*BIP47 Reusable Payment Codes for Hierarchical Deterministic Wallets +*BIP63 Stealth Addresses +*BIP70 Payment protocol + +However, none of these are as widely adopted as the suboptimal base-58 scriptPubKey template addresses, which is still a standard for the whole eco-system, from wallets, block explorers, merchants, exchanges, to end users. As P2PKH transactions are still dominating the blockchain, the author believes that the proposed P2PKH segwit addresses is the easiest way for wallets and services to adopt native witness program, which is particularly important in the context of scaling the capacity of the blockchain. + +The P2PKH segwit addresses only allow simple payment to a single public key. For arbitrarily complex segwit transactions, the general segwit address is used. The use of z-base-32 eliminates case-sensitiveness and simplifies transformation to and from hexadecimals. The Damm algorithm checksum allows detection of all single-digit errors and all adjacent transposition errors. With the excellent upgradability of witness program, this proposal is also forward compatible to new version witness programs that is not longer than 32 bytes. + +== Compatibility == + +This proposal is not backward 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. + +This proposal is forward compatible to any new witness program format with version 2 to 15 and length of 2 to 32 bytes. + +== Example == + +=== P2PKH segwit address === + +The following public key, + 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6 +when encoded as a P2PKH template, would become: + DUP HASH160 <010966776006953D5567439E5E39F86A0D273BEE> EQUALVERIFY CHECKSIG +And the corresponding version 1 Bitcoin address is + 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM +When the same script is encoded as a version 0 witness program, the scriptPubKey becomes: + OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC> +Using 0x19 as the address version, the equivalent witness program address is: + B4YZZ3nMBETWVF9ZSfotSwTxVnqhdkTi7r + +=== General segwit address === + +With the same 25 bytes version 0 witness program in the last example: + OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC> +The address version bits is 00001<sub>b</sub> + 00001<sub>b</sub> +The lengths bits is 11000<sub>b</sub> (24 = 25 - 1) + 00001-11000<sub>b</sub> +The witness program version bits is 0000 + 00001-11000-0000<sub>b</sub> +Appended by the zero-padded witness program + 00001-11000-0000-0-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-11101...01100 +The 270-bit string is transformed to z-base-32 with 54 digits and split into 9 equal segments: + bayyyy -yyyyyy -yyq4wt -eyejc3 -5sybwi -8iksqo -h6mah9 -o4oprh -767nfc +Calculate the Damm checksum for each segment: + For example: Damm(bayyyy) = 7 + bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4 +Calculate the Damm checksum for digits in the same position of different segments: + For example: Damm(byye58ho7) = j + bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4-jwk86o + +== Implementation == + +From arbitrary witness program to general segwit address: https://gist.github.com/jl2012/760b0f952715b8b6c608 + +== References == + +* [[bip-0013.mediawiki|BIP 13: Address Format for pay-to-script-hash]] +* [[bip-0016.mediawiki|BIP 16: Pay to Script Hash (aka "/P2SH/")]] +* [[bip-xxxx.mediawiki|BIP x: Segregated Witness]] https://github.com/bitcoin/bips/pull/265 + +== Copyright == +This work is placed in the public domain. |