diff options
-rw-r--r-- | README.mediawiki | 24 | ||||
-rw-r--r-- | bip-0032.mediawiki | 3 | ||||
-rw-r--r-- | bip-0068.mediawiki | 265 | ||||
-rw-r--r-- | bip-0083.mediawiki | 92 | ||||
-rw-r--r-- | bip-0107.mediawiki | 16 | ||||
-rw-r--r-- | bip-0122.mediawiki | 16 | ||||
-rw-r--r-- | bip-0124.mediawiki | 123 | ||||
-rw-r--r-- | bip-0131.mediawiki | 82 | ||||
-rw-r--r-- | bip-0141.mediawiki | 219 | ||||
-rw-r--r-- | bip-0142.mediawiki | 180 | ||||
-rw-r--r-- | bip-0143.mediawiki | 12 | ||||
-rw-r--r-- | bip-0144.mediawiki | 4 |
12 files changed, 690 insertions, 346 deletions
diff --git a/README.mediawiki b/README.mediawiki index dec53f9..7584102 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -252,7 +252,7 @@ Those proposing changes should consider that ultimately consent may rest with th | OP_CHECKLOCKTIMEVERIFY | Peter Todd | Standard -| Draft +| Accepted |- | [[bip-0066.mediawiki|66]] | Strict DER signatures @@ -302,6 +302,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0083.mediawiki|83]] +| Dynamic Hierarchical Deterministic Key Trees +| Eric Lombrozo +| Standard +| Draft +|- | [[bip-0099.mediawiki|99]] | Motivation and deployment of consensus rule changes ([soft/hard]forks) | Jorge Timón @@ -386,6 +392,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Informational | Draft |- +| [[bip-0124.mediawiki|124]] +| Hierarchical Deterministic Script Templates +| Eric Lombrozo, William Swanson +| Informational +| Draft +|- | [[bip-0125.mediawiki|125]] | Opt-in Full Replace-by-Fee Signaling | David Harding, Peter Todd @@ -398,6 +410,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0131.mediawiki|131]] +| "Coalescing Transaction" Specification (wildcard inputs) +| Chris Priest +| Standard +| Draft +|- | [[bip-0140.mediawiki|140]] | Normalized TXID | Christian Decker @@ -411,13 +429,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Draft |- | [[bip-0142.mediawiki|142]] -| Address Formats for Witness Program +| Address Format for Segregated Witness | Johnson Lau | Standard | Draft |- | [[bip-0143.mediawiki|143]] -| Transaction signature verification for version 0 and version 1 witness program +| Transaction Signature Verification for Version 0 Witness Program | Johnson Lau, Pieter Wuille | Standard | Draft diff --git a/bip-0032.mediawiki b/bip-0032.mediawiki index 28541f5..ac0ed99 100644 --- a/bip-0032.mediawiki +++ b/bip-0032.mediawiki @@ -259,7 +259,7 @@ PyCoin (https://github.com/richardkiss/pycoin) is a suite of utilities for deali 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 +A C++ implementation is available at https://github.com/ciphrex/mSIGNA/blob/master/deps/CoinCore/src/hdkeys.h An Objective-C implementation is available at https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCKeychain.h @@ -281,4 +281,5 @@ A Haskell implementation is available at https://github.com/haskoin/haskoin toge * 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. +* Eric Lombrozo for reviewing and revising this BIP. * Mike Caldwell for the version bytes to obtain human-recognizable Base58 strings. diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index 55905af..e93d748 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -49,139 +49,160 @@ The block produced time is equal to the median-time-past of its previous block. When the relative lock-time is block-based, it is interpreted as a minimum block-height constraint over the input's age. A relative block-based lock-time of zero indicates an input which can be included in any block. More generally, a relative block lock-time n can be included n blocks after the mining date of the output it is spending, or any block thereafter. -This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus and non-consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise: +==Implementation== + +A reference implementation is provided by the following pull request + +https://github.com/bitcoin/bitcoin/pull/7184 <pre> - enum { - /* Interpret sequence numbers as relative lock-time constraints. */ - LOCKTIME_VERIFY_SEQUENCE = (1 << 0), - }; - - /* Setting nSequence to this value for every input in a transaction - * disables nLockTime. */ - static const uint32_t SEQUENCE_FINAL = 0xffffffff; - - /* If this flag set, CTxIn::nSequence is NOT interpreted as a - * relative lock-time. Setting the most significant bit of a - * sequence number disabled relative lock-time. */ - static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31); +enum { + /* Interpret sequence numbers as relative lock-time constraints. */ + LOCKTIME_VERIFY_SEQUENCE = (1 << 0), +}; - /* If CTxIn::nSequence encodes a relative lock-time and this flag - * is set, the relative lock-time has units of 512 seconds, - * otherwise it specifies blocks with a granularity of 1. */ - static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22); +/* Setting nSequence to this value for every input in a transaction + * disables nLockTime. */ +static const uint32_t SEQUENCE_FINAL = 0xffffffff; - /* If CTxIn::nSequence encodes a relative lock-time, this mask is - * applied to extract that lock-time from the sequence field. */ - static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff; +/* If this flag set, CTxIn::nSequence is NOT interpreted as a + * relative lock-time. Setting the most significant bit of a + * sequence number disabled relative lock-time. */ +static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31); - /* In order to use the same number of bits to encode roughly the - * same wall-clock duration, and because blocks are naturally - * limited to occur every 600s on average, the minimum granularity - * for time-based relative lock-time is fixed at 512 seconds. - * Converting from CTxIn::nSequence to seconds is performed by - * multiplying by 512 = 2^9, or equivalently shifting up by - * 9 bits. */ - static const int SEQUENCE_LOCKTIME_GRANULARITY = 9; +/* If CTxIn::nSequence encodes a relative lock-time and this flag + * is set, the relative lock-time has units of 512 seconds, + * otherwise it specifies blocks with a granularity of 1. */ +static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22); - int64_t LockTime(const CTransaction &tx, int flags, const std::vector<int>* prevHeights, const CBlockIndex& block) - { - assert(prevHeights == NULL || prevHeights->size() == tx.vin.size()); - int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST) - ? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast() - : block.GetBlockTime(); - - bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2 - && flags & LOCKTIME_VERIFY_SEQUENCE; - - // Will be set to the equivalent height- and time-based nLockTime - // values that would be necessary to satisfy all relative lock- - // time constraints given our view of block chain history. - int nMinHeight = 0; - int64_t nMinTime = 0; - // Will remain equal to true if all inputs are finalized - // (CTxIn::SEQUENCE_FINAL). - bool fFinalized = true; - for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { - const CTxIn& txin = tx.vin[txinIndex]; - // Set a flag if we witness an input that isn't finalized. - if (txin.nSequence == CTxIn::SEQUENCE_FINAL) - continue; - else - fFinalized = false; +/* If CTxIn::nSequence encodes a relative lock-time, this mask is + * applied to extract that lock-time from the sequence field. */ +static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff; - // Do not enforce sequence numbers as a relative lock time - // unless we have been instructed to, and a view has been - // provided. - if (!fEnforceBIP68) - continue; +/* In order to use the same number of bits to encode roughly the + * same wall-clock duration, and because blocks are naturally + * limited to occur every 600s on average, the minimum granularity + * for time-based relative lock-time is fixed at 512 seconds. + * Converting from CTxIn::nSequence to seconds is performed by + * multiplying by 512 = 2^9, or equivalently shifting up by + * 9 bits. */ +static const int SEQUENCE_LOCKTIME_GRANULARITY = 9; - // Sequence numbers with the most significant bit set are not - // treated as relative lock-times, nor are they given any - // consensus-enforced meaning at this point. - if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) - continue; - - if (prevHeights == NULL) - continue; - - int nCoinHeight = (*prevHeights)[txinIndex]; - - if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) { - - int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast(); - - // Time-based relative lock-times are measured from the - // smallest allowed timestamp of the block containing the - // txout being spent, which is the median time past of the - // block prior. - nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1); - } else { - // We subtract 1 from relative lock-times because a lock- - // time of 0 has the semantics of "same block," so a lock- - // time of 1 should mean "next block," but nLockTime has - // the semantics of "last invalid block height." - nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1); - } +/** + * Calculates the block height and time which the transaction must be later than + * in order to be considered final in the context of BIP 68. It also removes + * from the vector of input heights any entries which did not correspond to sequence + * locked inputs as they do not affect the calculation. + */ +static std::pair<int, int64_t> CalculateSequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block) +{ + assert(prevHeights->size() == tx.vin.size()); + + // Will be set to the equivalent height- and time-based nLockTime + // values that would be necessary to satisfy all relative lock- + // time constraints given our view of block chain history. + // The semantics of nLockTime are the last invalid height/time, so + // use -1 to have the effect of any height or time being valid. + int nMinHeight = -1; + int64_t nMinTime = -1; + + // tx.nVersion is signed integer so requires cast to unsigned otherwise + // we would be doing a signed comparison and half the range of nVersion + // wouldn't support BIP 68. + bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2 + && flags & LOCKTIME_VERIFY_SEQUENCE; + + // Do not enforce sequence numbers as a relative lock time + // unless we have been instructed to + if (!fEnforceBIP68) { + return std::make_pair(nMinHeight, nMinTime); + } + + for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { + const CTxIn& txin = tx.vin[txinIndex]; + + // Sequence numbers with the most significant bit set are not + // treated as relative lock-times, nor are they given any + // consensus-enforced meaning at this point. + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) { + // The height of this input is not relevant for sequence locks + (*prevHeights)[txinIndex] = 0; + continue; } - - // If all sequence numbers are CTxIn::SEQUENCE_FINAL, the - // transaction is considered final and nLockTime constraints - // are not enforced. - if (fFinalized) - return 0; - - if ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD) - nMinHeight = std::max(nMinHeight, (int)tx.nLockTime); - else - nMinTime = std::max(nMinTime, (int64_t)tx.nLockTime); - - if (nMinHeight >= block.nHeight) - return nMinHeight; - - if (nMinTime >= nBlockTime) - return nMinTime; - - return 0; - }</pre> - -Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be updated as well, since the semantics of the return value has been inverted. - -==Example: Bidirectional payment channel== -A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1 BTC output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. - -Alice desires to send Bob a payment of 0.1 BTC. She does so by constructing a transaction spending the 1 BTC output and sending 0.1 BTC to Bob and 0.9 BTC back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1 BTC, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2 BTC, then 0.3 BTC to Bob with a relative lock-time of 29 days from creation of the channel. - -Bob now desires to send Alice a refund of 0.25 BTC. He does so by constructing a transaction spending the 1btc output and sending 0.95 BTC (= 0.7 BTC + 0.25 BTC) to Alice and 0.05 BTC to himself. Since Bob will still have in his logs the transaction giving him 0.7 BTC 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures. - -Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by finalizing the input (nSequence = MAX_INT) and both parties signing. - -==Implementation== - -A reference implementation is provided by the following pull request + int nCoinHeight = (*prevHeights)[txinIndex]; + + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) { + int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast(); + + // Time-based relative lock-times are measured from the + // smallest allowed timestamp of the block containing the + // txout being spent, which is the median time past of the + // block prior. + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1); + } else { + // We subtract 1 from relative lock-times because a lock- + // time of 0 has the semantics of "same block," so a lock- + // time of 1 should mean "next block," but nLockTime has + // the semantics of "last invalid block height." + nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1); + } + } + + return std::make_pair(nMinHeight, nMinTime); +} + +static bool EvaluateSequenceLocks(const CBlockIndex& block, std::pair<int, int64_t> lockPair) +{ + int64_t nBlockTime = block.pprev ? block.pprev->GetMedianTimePast() : 0; + if (lockPair.first >= block.nHeight || lockPair.second >= nBlockTime) + return false; + + return true; +} + +bool SequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block) +{ + return EvaluateSequenceLocks(block, CalculateSequenceLocks(tx, flags, prevHeights, block)); +} + +bool CheckSequenceLocks(const CTransaction &tx, int flags) +{ + AssertLockHeld(cs_main); + + CBlockIndex* tip = chainActive.Tip(); + CBlockIndex index; + index.pprev = tip; + // CheckSequenceLocks() uses chainActive.Height()+1 to evaluate + // height based locks because when SequenceLocks() is called within + // CBlock::AcceptBlock(), the height of the block *being* + // evaluated is what is used. Thus if we want to know if a + // transaction can be part of the *next* block, we need to call + // SequenceLocks() with one more than chainActive.Height(). + index.nHeight = tip->nHeight + 1; + + // pcoinsTip contains the UTXO set for chainActive.Tip() + CCoinsViewMemPool viewMemPool(pcoinsTip, mempool); + std::vector<int> prevheights; + prevheights.resize(tx.vin.size()); + for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { + const CTxIn& txin = tx.vin[txinIndex]; + CCoins coins; + if (!viewMemPool.GetCoins(txin.prevout.hash, coins)) { + return error("%s: Missing input", __func__); + } + if (coins.nHeight == MEMPOOL_HEIGHT) { + // Assume all mempool transaction confirm in the next block + prevheights[txinIndex] = tip->nHeight + 1; + } else { + prevheights[txinIndex] = coins.nHeight; + } + } -https://github.com/bitcoin/bitcoin/pull/6312 + std::pair<int, int64_t> lockPair = CalculateSequenceLocks(tx, flags, &prevheights, index); + return EvaluateSequenceLocks(index, lockPair); +} +</pre> ==Acknowledgments== diff --git a/bip-0083.mediawiki b/bip-0083.mediawiki new file mode 100644 index 0000000..d1da645 --- /dev/null +++ b/bip-0083.mediawiki @@ -0,0 +1,92 @@ +<pre> + BIP: BIP-83 + Title: Dynamic Hierarchical Deterministic Key Trees + Author: Eric Lombrozo <eric@ciphrex.com> + Status: Draft + Type: Standard + Created: 2015-11-16 +</pre> + +==Abstract== + +This BIP defines a scheme for key derivation that allows for dynamic creation of key hierarchies based on the algorithm described in BIP32. + +==Motivation== + +Several proposals have been made to try to standardize a structure for hierarchical deterministic wallets for the sake of interoperability (reference BIP32, BIP44, BIP45). However, all proposals to date have tried to impose a specific structure upfront without providing any flexibility for dynamic creation of new hierarchical levels with different semantics or mapping between different applications that use distinct structures. + +Instead of attempting to impose a specific structure upfront, this BIP proposes that we design the derivation in such a way that we can continue extending hierarchies arbitrarily and indefinitely. + +==Specification== + +BIP32 provides a hierarchical derivation scheme where every node in the tree can be either used to derive child nodes or used as a signing key for ECDSA. This means that as soon as we choose to use a node as a signing key, we can no longer derive children from that node. To draw an analogy to file systems, each node is either a file or a directory but never both. However, given the need to predictably know the location of new children, it is generally not a good idea to mix both signing keys and parent nodes at the same level in the hierarchy. This means that as soon as we've decided that a particular level in the hierarchy is to be used for signing keys, we've lost the ability to nest deeper levels into the tree. + +At every level of the hierarchy, we reserve the child with index 0 to allow further nesting, and for signing key parent nodes use child indices 1 to MAX_INDEX (2<sup>31</sup> - 1) for signing keys. We can use either hardened or nonhardened derivation. + +Let p denote a specific signing key parent node and k be an index greater than 0. The children signing keys are then: + +p / k + +with k > 0. + +To create sublevels, we derive the nested nodes: + +p / 0 / n + +with n ≥ 0. + +Each of these nodes can now contain signing key children of their own, and again we reserve index 0 to allow deeper nesting. + +==Notation== + +We propose the following shorthand for writing nested node derivations: + +p // n instead of p / 0 / n + +p //' n instead of p / 0' / n + +==Mappings== + +Rather than specifying upfront which path is to be used for a specific purpose (i.e. external invoicing vs. internal change), different applications can specify arbitrary parent nodes and derivation paths. This allows for nesting of sublevels to arbitrary depth with application-specified semantics. Rather than trying to specify use cases upfront, we leave the design completely open-ended. Different applications can exchange these mappings for interoperability. Eventually, if certain mappings become popular, application user interfaces can provide convenient shortcuts or use them as defaults. + +Note that BIP32 suggests reserving child 0 for the derivation of signing keys rather than sublevels. It is not really necessary to reserve signing key parents, however, as each key's parent's path can be explicitly stated. But unless we reserve a child for sublevel derivation, we lose the ability to nest deeper levels into the hierarchy. While we could reserve any arbitrary index for nesting sublevels, reserving child 0 seems simplest to implement, leaving all indices > 0 for contiguously indexed signing keys. We could also use MAX_INDEX (2<sup>31</sup> - 1) for this purpose. However, we believe doing so introduces more ideosyncracies into the semantics and will present a problem if we ever decide to extend the scheme to use indices larger than 31 bits. + +==Use Cases== + +===Account Hierarchies=== + +For all that follows, we assume that key indices k > 0 and parent node indices n ≥ 0. + +From a master seed m, we can construct a default account using the following derivations for nonhardened signing keys: + +m / 1 / k (for change/internal outputs) + +m / 2 / k (for invoice/external outputs) + +To create subaccount a<sub>n</sub>, we use: + +a<sub>n</sub> = m // n + +To generate keys for subaccount a<sub>n</sub>, we use: + +a<sub>n</sub> / 1 / k (for change/internal outputs) + +a<sub>n</sub> / 2 / k (for invoice/external outputs) + +We can continue creating subaccounts indefinitely using this scheme. + +===Bidirectional Payment Channels=== + +In order to create a bidirectional payment channel, it is necessary that previous commitments be revokable. In order to revoke previous commitments, each party reveals a secret to the other that would allow them to steal the funds in the channel if a transaction for a previous commitment is inserted into the blockchain. + +By allowing for arbitrary nesting of sublevels, we can construct decision trees of arbitrary depth and revoke an entire branch by revealing a parent node used to derive all the children. + +==References== + +* [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] +* [[https://lightning.network/lightning-network-paper.pdf|Lightning Network Whitepaper]] + +==Copyright== + +This document is placed in the public domain. + diff --git a/bip-0107.mediawiki b/bip-0107.mediawiki index 88a2c99..4e96173 100644 --- a/bip-0107.mediawiki +++ b/bip-0107.mediawiki @@ -16,11 +16,11 @@ This BIP proposes a dynamic limit to the block size based on transaction volume. Over the next few years, large infrastructure investments will be made into: # Improving global network connectivity -# Improving block propogation across the Bitcoin network +# Improving block propagation 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. +* 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 augment 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. @@ -44,7 +44,7 @@ Over the next few years, large infrastructure investments will be made into: ** <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 +* When the dynamic rules for increasing the block size go live on January 1st 2020, the starting maximum block size will 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. @@ -59,7 +59,7 @@ For example: *** 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. +*** 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 distance 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: @@ -67,16 +67,16 @@ For example: ***# 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 +*** Increases in the block size are designed to be conservative and in balance with the number of theoretical opportunities 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. +Similar deployment model to BIP101: +<blockquote>Activation is achieved when 750 of 1,000 consecutive blocks in the best chain have a version number with the first, second, third, and thirtieth bits set (0x20000007 in hex). The activation time will be the timestamp of the 750'th block plus a two week (1,209,600 second) grace period to give any remaining miners or services time to upgrade to support larger blocks.</blockquote> ==Acknowledgements== -Thanks to Austin Hill, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. +Thanks to Austin Williams, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. ==Copyright== diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index 902aa02..d59e353 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -23,7 +23,7 @@ The same happens with posts and messages that reference some particular txs or b The URI follow this form: - <nowiki>blockchain:[//chain]</type/hash></nowiki> + <nowiki>blockchain:[//<chain>]/<tx|block|address>/<hash></nowiki> Where: @@ -52,6 +52,18 @@ Where: | |} +====ABNF grammar==== + +<pre> +blockchainuri = "blockchain:" ["//" chain] "/" object +object = ("tx" "/" hash) / ("block" "/" (hash / blockheight)) / + ("address" "/" address) +chain = hash +hash = 64HEXDIG +blockheight = 1*15DIGIT ; 15 is somehow arbitrary, i.e. a "small" int. +address = base58 ; https://en.wikipedia.org/wiki/Base58 +</pre> + ---- ===Definition of chain ID=== @@ -109,4 +121,4 @@ Thanks to Richard Moore, Matt Whitlock, Andreas Schildbach for suggestions about ==Copyright== -This document is placed in the public domain.
\ No newline at end of file +This document is placed in the public domain. diff --git a/bip-0124.mediawiki b/bip-0124.mediawiki new file mode 100644 index 0000000..1c98db8 --- /dev/null +++ b/bip-0124.mediawiki @@ -0,0 +1,123 @@ +<pre> + BIP: BIP-124 + Title: Hierarchical Deterministic Script Templates + Authors: Eric Lombrozo <eric@ciphrex.com>, William Swanson + Status: Draft + Type: Informational + Created: 2015-11-20 + + Post-History: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011795.html +</pre> + +==Abstract== + +This BIP defines a script template format that can be used by wallets to deterministically generate scripts with specific authorization policies using the key derivation mechanism defined in BIP32. + +==Motivation== + +Currently existing wallets typically issue scripts in only a tiny handful of widely used formats. The most popular formats are pay-to-pubkey-hash and m-of-n pay-to-script-hash (BIP16). However, different wallets tend to use mutually incompatible derivation schemes to generate signing keys and construct scripts from them. Moreover, with the advent of hashlocked and timelocked contracts (BIP65, BIP112), it is necessary for different wallets to be able to cooperatively generate even more sophisticated scripts. + +In addition, there's a lot of ongoing work in the development of multilayered protocols that use the blockchain as a settlement layer (i.e. the Lightning Network). These efforts require sufficiently generalized templates to allow for rapidly evolving script designs. + +This BIP provides a generalized format for constructing a script template that guarantees that different wallets will all produce the same scripts for a given set of derivation paths according to BIP32. + +==Specification== + +===Keys=== + +An individual key is determined by a BIP32 derivation path and an index. For convenience, we introduce the following notation: + +'''A'''<sub>k</sub> = (derivation path for A)/k + +===Key Groups=== + +Let '''m'''<sub>i</sub> denote distinct BIP32 derivation paths. We define a key group of n keys as a set of key derivation paths with a free index k: + +{'''K'''<sub>k</sub>} = { '''m'''<sub>1</sub>/k, '''m'''<sub>2</sub>/k, '''m'''<sub>3</sub>/k, ..., '''m'''<sub>n</sub>/k } + +Key groups are useful for constructing scripts that are symmetric in a set of keys. Scripts are symmetric in a set of keys if the semantics of the script is unaffected by permutations of the keys. Key groups enforce a canonical form and can improve privacy. + +===Sorting=== + +We define a lexicographic sorting of the keys. (TODO: specification of sorting conventions - compressed pubkeys, encoding, etc...) + +Define {'''K'''<sub>k</sub>}<sub>j</sub> to be the jth element of the sorted keys for derivation index k. + +===Script Templates=== + +We construct script templates by inserting placeholders for data into a script. To denote a placeholder, we use the following notation: + +''Script''('''A''') = opcodes ['''A'''] opcodes + +We extend this notation to an arbitrary number of placeholders: + +''Script''('''X1''', '''X2''', ..., '''Xn''') = opcodes ['''X1'''] opcodes ['''X2'''] opcodes ... opcodes ['''Xn'''] opcodes + +We introduce the following convenient notation for sorted key groups: + +[{'''K'''<sub>k</sub>}] = [{'''K'''<sub>k</sub>}<sub>1</sub>] [{'''K'''<sub>k</sub>}<sub>2</sub>] ... [{'''K'''<sub>k</sub>}<sub>n</sub>] + +===Operations on Keys=== + +In some applications, we might want to insert the result of some operation performed on a key rather than the key itself into the script. For example, we might want to insert a Hash160 of key '''A'''<sub>k</sub>. We can use the following notation: + +[''Hash160''('''A'''<sub>k</sub>)] + +===Encoding=== + +TODO + +==Examples== + +===2-of-3 Multisig=== + +The script template is defined by: + +''Script''('''X''') = 2 ['''X'''] 3 OP_CHECKMULTISIG + +Letting '''K'''<sub>k</sub> = { '''m'''<sub>1</sub>/k, '''m'''<sub>2</sub>/k, '''m'''<sub>3</sub>/k }, the ''k''th script for this key group is denoted by ''Script''({'''K'''<sub>k</sub>}). + +===1-of-1 or 2-of-3=== + +The script template is defined by: + +''Script''('''A''', '''B''') = <br> + OP_DUP ['''A'''] OP_CHECKSIG<br> + OP_NOTIF<br> + 2 ['''B'''] 3 OP_CHECKMULTISIGVERIFY <br> + OP_NOTIF<br> + OP_ENDIF<br> + OP_TRUE<br> + +Let '''M'''<sub>k</sub> = '''m'''/k be a key of a superuser that can authorize all transactions and {'''K'''<sub>k</sub>} be a key group of three users that can only authorize transactions if at least two of them agree. + +The ''k''th script is given by ''Script''('''M'''<sub>k</sub>, {'''K'''<sub>k</sub>}). + +===Timelocked Contract=== + +The output is payable to Alice immediately if she knows the private key for '''A'''<sub>k</sub>. Bob must know the private key for '''B'''<sub>k</sub> and also wait for a timeout '''t''' before being able to spend the output. + +The script template is defined by: + +''Script''('''A''', '''B''', '''T''') = <br> + OP_IF <br> + OP_DUP OP_HASH160 [''Hash160''('''A''')] OP_EQUALVERIFY OP_CHECKSIG <br> + OP_ELSE <br> + ['''T'''] OP_CHECKLOCKTIMEVERIFY OP_DROP <br> + OP_DUP OP_HASH160 [''Hash160''('''B''')] OP_EQUALVERIFY OP_CHECKSIG <br> + OP_ENDIF + +The ''k''th script with timeout '''t''' is given by ''Script''('''A'''<sub>k</sub>, '''B'''<sub>k</sub>, '''t'''). + +==References== + +* [[bip-0016.mediawiki|BIP16 - Pay to Script Hash]] +* [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] +* [[bip-0065.mediawiki|BIP65 - OP_CHECKLOCKTIMEVERIFY]] +* [[bip-0112.mediawiki|BIP112 - CHECKSEQUENCEVERIFY]] +* [[https://lightning.network/lightning-network-paper.pdf|Lightning Network Whitepaper]] + +==Copyright== + +This document is placed in the public domain. + diff --git a/bip-0131.mediawiki b/bip-0131.mediawiki new file mode 100644 index 0000000..c30ef54 --- /dev/null +++ b/bip-0131.mediawiki @@ -0,0 +1,82 @@ +<pre> + BIP: 131 + Title: "Coalescing Transaction" Specification (wildcard inputs) + Author: Chris Priest <cp368202@ohiou.edu> + Status: Draft + Type: Standards Track + Created: 2015-11-30 +</pre> + +==Abstract== + +This specification defines a new type of transaction that supplements (not replaces) +normal "non coalescing" bitcoin transactions. + +==Motivation== + +Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend +from multiple inputs with the exact same scriptPubKey, you have to list each +input separately, along with the same signature multiple times, even though the signature expresses the same information. +This bloats the transaction size and makes it expensive to spend from small value inputs. + +Because small value inputs are expensive to send, they remain in the UTXO pool +which full nodes have to keep around. It is believed that long term increase of the UTXO +set can have negative scaling consequences on the network. + +If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending +to the network, this problem is projected to get worse. In other words, as transaction +fees increase, the minimum economical value of a spending a UTXO will increase. + +==Specification== + +=== Redefinition of Transaction version === + +First, this BIP redefines the version field on transactions. The first four bytes +are defined as the version number, while the last four bytes are defined as the +transaction type. Type "0000" denotes normal transactions, and "0001" defines +coalescing transaction. + +Examples: + +version 1 transaction with normal inputs: + version: 10000000 + +version 2 transaction with normal inputs: + version: 20000000 + +version 2 transaction with coalescing inputs: + version: 20000001 + +Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all +inputs present in the transaction. + +=== Wildcard inputs === + +A coalescing transaction is formulated the exact same way as a version 1 transaction +with one exception: each input is treated as a "wildcard input". + +A wildcard input beings the value of all inputs with the exact same scriptPubKey +in a block lower or equal to the block the wildcard input is confirmed into. + +== Changes needed to implement == + +The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. + +1. <b>Full Node Coalescing validation</b> - When a full node receives a coalescing transaction, it has to +aggregate the value of all the UTXOs in the blockchain older than the input +with the same scriptPubKey. If this value is greater than or equal to the +amount of all outputs, then that coalescing transaction is valid and can be propagated. + +2. <b>Full Node Non-Coalescing validation</b> - When a non-coalescing transaction comes in, the code needs to be modified +to check if each input has not been spent by a coalescing transaction. If there exist any +coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, +then the UTXO has been spent and the transaction is invalid. + +3. <b>Wallet</b> - The user facing wallet portion of the reference client should notify +the user when their wallet contains many UTXOs that qualify it to benefit from +a coalescing transaction. Wallets should not simply replace non-coalescing transactions +with coalescing transactions in all instances. + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki index ac44d87..74fbf0f 100644 --- a/bip-0141.mediawiki +++ b/bip-0141.mediawiki @@ -21,7 +21,7 @@ The entirety of the transaction's effects are determined by output consumption ( 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): +# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was signed are no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach ([https://github.com/bitcoin/bips/edit/master/bip-0062.mediawiki 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 @@ -30,164 +30,145 @@ By removing this data from the transaction structure committed to the transactio # '''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. +#* New script system could be introduced without any limitation from the existing script semantic. For example, a new transaction digest algorithm for transaction signature verification is described in [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143] ==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 new block rule is added which requires a commitment to the witness hashes, the double SHA256 of a transaction including witnesses. The witness hash of coinbase transaction 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. +The commitment is recorded in a scriptPubKey of the coinbase transaction. It must be at least 38 bytes, with the first 6-byte of 0x6a24aa21a9ed, that is: + + 1-byte - OP_RETURN (0x6a) + 1-byte - Push the following 36 bytes (0x24) + 4-byte - Commitment header (0xaa21a9ed) + 32-byte - Commitment hash: Double-SHA256(witness root hash|witness nonce) + + 39th byte onwards: Optional data with no consensus meaning + +and the coinbase's input's witness must consist of a single 32-byte array for the witness nonce. -==== 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) +If there are more than one scriptPubKey matching the pattern, the one with highest output index is assumed to be the commitment. -Locator of the witness root hash is defined as: +=== Witness program === -<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> +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". -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. +New rules for scriptSig: +* 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. -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. +If the version byte is 0, and the witness program is 20 bytes, +* It is interpreted as a pay-to-witness-public-key-hash (P2WPKH) program. +* The witness must consist of exactly 2 items. The first one is a signature, and the second one is a public key. +* HASH160 of the public key must match the 20-byte witness program. +* After normal script evaluation, the signature is verified against the public key with CHECKSIG operation. The verification must result in a single TRUE on the stack. -====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) +If the version byte is 0, and the witness program is 32 bytes, +* It is interpreted as a pay-to-witness-script-hash (P2WSH) program. +* The witness must consist of an input stack to feed to the script, followed by a serialized script. +* The serialized script is popped off the initial witness stack. SHA256 of the serialized script must match the 32-byte witness program. +* The serialized script 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. -Locator of the witness root hash is defined as: +If the version byte is 0, but the witness program is neither 20 nor 32 bytes, the script must fail. -<pre>SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)</pre> +If the version byte is 1 to 16, no further interpretation of the witness program or witness happens. -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. +=== Other consensus critical limits === -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 ==== -=== Block size limit === -Blocks are currently limited to 1 MB total size. We change this restriction as follows: +Blocks are currently limited to 1,000,000 bytes (1MB) 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. +''Block cost'' is defined. The cost of each byte in the existing header and transactions is 4, while the cost of each byte in witness data is 1. -The new rule is s<sub>v</sub> <= 1 MB. +The new rule is total ''block cost'' ≤ 4,000,000. -=== Witness program === +==== Sigops ==== -* 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. +Sigops per block is currently limited to 20,000. We change this restriction as follows: -** 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. +''Sigop cost'' is defined. The cost of a sigop in traditoinal script is 4, while the cost of a sigop in witness program is 1. -=== Other consensus critical constraints === +The new rule is total ''sigop cost'' ≤ 80,000. -== Block size analysis == -WORK IN PROGRESS +== Examples == -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> +=== P2WPKH witness program === -With some transformation it could be shown that: -<pre> - TBS = CBS / (1 - WA * PR) - = VBS / (1 - WA * PR * (1 - WD)) -</pre> +The following example is a version 0 pay-to-witness-public-key-hash (P2WPKH) witness program: -In order to keep the proposal as a soft fork, the CBS must not have a upper limit higher than 1MB. + witness: <signature> <pubkey> + scriptSig: (empty) + scriptPubKey: 0 <20-byte-hash> + (0x0014{20-byte-hash}) -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%. +The '0' in scriptPubKey indicates the following push is a version 0 witness program. The length of the witness program indicates that it is a P2WPKH type. The witness must consist of exactly 2 items. The HASH160 of the pubkey in witness must match the witness program. +The signature is verified as + <signature> <pubkey> CHECKSIG -== Examples == +Comparing with a traditional P2PKH output, the P2WPKH equivalent occupies 3 less bytes in the scriptPubKey, and moves the signature and public key from scriptSig to witness. -=== Version 0 witness program === +=== P2WSH witness program === -The following example is a version 0 witness program, equivalent to the existing Pay-to-Pubkey-Hash (P2PKH) output. +The following example is an 1-of-2 multi-signature version 0 pay-to-witness-script-hash (P2WSH) witness program. - witness: <signature> <pubkey> + witness: 0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG> scriptSig: (empty) - scriptPubKey: OP_0 <0x76A914{20-byte-hash-value}88AC> + scriptPubKey: 0 <32-byte-hash> + (0x0020{32-byte-hash}) -The OP_0 indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: +The '0' in scriptPubKey indicates the following push is a version 0 witness program. The length of the witness program indicates that it is a P2WSH type. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash in scriptPubKey, and deserialized: - DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + 1 <pubkey1> <pubkey2> 2 CHECKMULTISIG -The script is executed with the data from witness +The script is executed with the remaining data from witness: - <signature> <pubkey> DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + 0 <signature1> 1 <pubkey1> <pubkey2> 2 CHECKMULTISIG -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. +A P2WSH witness program allows arbitrarily large script as the 520-byte push limit is bypassed. -=== Version 1 witness program === +The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of BIP16 P2SH. The increased size improves security against possible collision attacks, as 2<sup>80</sup> work is not infeasible anymore (By the end of 2015, 2<sup>84</sup> hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent BIP16 P2SH output but is moved to witness. -The following example is an 1-of-2 multi-signature version 1 witness program. +=== Witness program nested in BIP16 P2SH === - witness: 0 <signature1> <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> - scriptSig: (empty) - scriptPubKey: OP_1 <0x{32-byte-hash-value}> +The following example is the same 1-of-2 multi-signature P2WSH witness program, but nested in a BIP16 P2SH output. -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: + witness: 0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG> + scriptSig: <0 <32-byte-hash>> + (0x0020{32-byte-hash}) + scriptPubKey: HASH160 <20-byte-hash> EQUAL + (0xA914{20-byte-hash}87) - 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG +The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash in scriptPubKey, and interpreted as: -The script is executed with the remaining data from witness: + 0 <32-byte-hash> - 0 <signature1> 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG +The P2WSH witness program is then executed as described in the previous example -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. +Comparing with the previous 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. -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. +=== Extensible commitment structure === -=== Witness program nested in Pay-to-Script-Hash === +The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce currently has no consensus meaning, but in the future allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in +coinbase becomes: -The following example is the same 1-of-2 multi-signature version 1 witness program, but nested in a P2SH output. + Double-SHA256(Witness root hash|Hash(new commitment|witness nonce)) - 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 +For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. -The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash-value in scriptPubKey, and interpreted as: +Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, MUST NOT use the witness nonce to preserve the ability to do upgrades of the Bitcoin consensus protocol. - 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. +The optional data space following the commitment also leaves room for metadata of future softforks, and MUST NOT be used for other purpose. === 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. @@ -197,7 +178,9 @@ Such setups is not possible with BIP62 as the malleability fix, since the spendi 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: @@ -206,9 +189,15 @@ In the current Bitcoin protocol, it is possible to generate compact fraud proof # 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. +Extra witness data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify: + +# Sum trees for transaction fee can be committed making it possible to construct short proofs that the miner does not add excessive fees to the coinbase transaction. Similar for the block size and sigop count limit. +# 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. + +These commitments could be included in the extensible commitment structure 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. @@ -216,23 +205,26 @@ Examples of new script system include Schnorr signatures which reduce the size o 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). +Currently there is only one nLockTime field in a transaction and all inputs must share the same value. [https://github.com/bitcoin/bips/edit/master/bip-0068.mediawiki 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 [https://github.com/bitcoin/bips/edit/master/bip-0065.mediawiki BIP65] and [https://github.com/bitcoin/bips/edit/master/bip-0112.mediawiki 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. + +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 where the witness programs are equal to 0, which the script must fail). 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) +* Sending bitcoin to upgraded wallets using a P2SH address (less efficient) +* Sending bitcoin to upgraded wallets using a native witness program (more efficient) through [https://github.com/bitcoin/bips/blob/master/bip-0070.mediawiki BIP70] payment protocol '''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) +* Sending bitcoin to upgraded wallets using a native witness program if BIP70 is not supported == Deployment == @@ -248,7 +240,6 @@ invalid, and all further blocks enforce the new rules. 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, @@ -258,10 +249,20 @@ 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 + +https://github.com/sipa/bitcoin/commits/segwit3 + +== References == + +*[[bip-0016.mediawiki|BIP16 Pay to Script Hash]] +*[[bip-0142.mediawiki|BIP142 Address Formats for Segregated Witness]] +*[[bip-0143.mediawiki|BIP143 Transaction Signature Verification for Version 0 Witness Program]] +*[[bip-0144.mediawiki|BIP144 Segregated Witness (Peer Services)]] == Copyright == + This document is placed in the public domain. diff --git a/bip-0142.mediawiki b/bip-0142.mediawiki index 7efeca7..7d7b1d2 100644 --- a/bip-0142.mediawiki +++ b/bip-0142.mediawiki @@ -1,6 +1,6 @@ <pre> BIP: 142 - Title: Address Formats for Witness Program + Title: Address Format for Segregated Witness Author: Johnson Lau <jl2012@xbt.hk> Status: Draft Type: Standards Track @@ -9,149 +9,143 @@ == 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. +This BIP describes new types of Bitcoin address to support native segregated witness transactions with 20-byte and 32-byte program. == Motivation == -To define standard payment addresses for native segwit transactions to promote early adoption of the more efficient transaction method. +To define standard payment address for native segregated witness (segwit) transactions to promote early adoption of the more efficient transaction method. == Specification == -=== P2PKH segwit address === +The new Bitcoin address format defined is for the Pay-to-Witness-Public-Key-Hash (P2WPKH) and Pay-to-Witness-Script-Hash (P2WSH) transaction described in segregated witness soft fork (BIP141). The scriptPubKey is an OP_0 followed by a push of 20-byte-hash (P2WPKH) or 32-byte hash (P2WSH). -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. +The new address is encoded in a simlar way as existing address formats: + + base58-encode: + [1-byte address version] + [1-byte witness program version] + [0x00] + [20/32-byte-hash] + [4-byte checksum] + +For P2WPKH address, the address version is 6 (0x06) for a main-network address or 3 (0x03) for a testnet address. -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. +For P2WSH address, the address version is 10 (0x0A) for a main-network address or 40 (0x28) for a testnet address. -=== General segwit address === +The witness program version is an 1-byte value between 0 (0x00) and 16 (0x10). Only version 0 is defined in BIP141. Versions 1 to 16 are reserved for future extensions. -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. +Following the witness program version is a 0x00 padding to make sure that each witness program version will have an unique prefix. -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 +Following the padding is the program hash, 20 byte for a P2WPKH address and 32 byte for a P2WSH address. + +The 4-byte checksum is the first four bytes of the double SHA256 hash of the serialization of the previous items. + +All addresses generated with this scheme will have a constant length, with 36 digits for 20-byte and 53 digits for 32-byte. Different witness program version will have an unique prefix shown in the following table: + +{|class="wikitable" style="text-align: center;" +|- +!rowspan=3 style=""|Witness program version +!colspan=4 style=""|Hash size +|- +!colspan=2 style=""|20-byte (36 digits) +!colspan=2 style=""|32-byte (53 digits) +|- +!Mainnet +!Testnet +!Mainnet +!Testnet +|- +|0||p2||QW||7Xh||T7n +|- +|1||p4||QY||7Xq||T7w +|- +|2||p6||Qa||7Xz||T85 +|- +|3||p7||Qc||7Y9||T8E +|- +|4||pA||Qe||7YH||T8N +|- +|5||pB||Qf||7YS||T8X +|- +|6||pD||Qh||7Ya||T8g +|- +|7||pF||Qj||7Yj||T8p +|- +|8||pG||Qm||7Yt||T8y |- -| 0 || y || 8 || e || 16 || o || 24 || a +|9||pJ||Qn||7Z2||T97 |- -| 1 || b || 9 || j || 17 || t || 25 || 2 +|10||pL||Qp||7ZB||T9G |- -| 2 || n || 10 || k || 18 || 1 || 26 || 4 +|11||pN||Qr||7ZK||T9Q |- -| 3 || d || 11 || m || 19 || u || 27 || 5 +|12||pQ||Qt||7ZU||T9Z |- -| 4 || r || 12 || c || 20 || w || 28 || h +|13||pS||Qv||7Zc||T9i |- -| 5 || f || 13 || p || 21 || i || 29 || 7 +|14||pT||Qw||7Zm||T9r |- -| 6 || g || 14 || q || 22 || s || 30 || 6 +|15||pV||Qy||7Zv||TA1 +|- +|16||pX||R1||7a4||TA9 |- -| 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: +The BIP141 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. +* Segwit-in-P2SH is a BIP16 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. +As the BIP13 P2SH address has been defined in 2012, using segwit-in-P2SH allows most existing wallets to pay a segwit-compatible wallet without any upgrade. However, this method requires more block space 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. +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. It is believed that the proposed P2WPKH and P2WSH address format 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. +While P2WPKH address is specific for simple payment to a single public key, P2WSH address allows arbitrarily complex segwit transactions, resemble to the BIP13 P2SH address. == 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 not backward compatible. However, an older implementation will report the new address type 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. +This proposal is forward compatible to the future versions of witness program of 20 and 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 + +When the same public key is encoded as P2WPKH, the scriptPubKey becomes: + + OP_0 <010966776006953D5567439E5E39F86A0D273BEE> + +Using 0x06 as witness version, followed 0x00 as witness version, and a 0x00 padding, the equivalent P2WPKH address is: + + p2xtZoXeX5X8BP8JfFhQK2nD3emtjch7UeFm + +== Reference implementation == == 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 +* [[bip-0016.mediawiki|BIP 16: Pay to Script Hash]] +* [[bip-0070.mediawiki|BIP 70: Payment Protocal]] +* [[bip-0141.mediawiki|BIP 141: Segregated Witness]] == Copyright == This work is placed in the public domain. diff --git a/bip-0143.mediawiki b/bip-0143.mediawiki index 276e2cb..3d7e856 100644 --- a/bip-0143.mediawiki +++ b/bip-0143.mediawiki @@ -1,6 +1,6 @@ <pre> BIP: 143 - Title: Transaction signature verification for version 0 and version 1 witness program + Title: Transaction Signature Verification for Version 0 Witness Program Author: Johnson Lau <jl2012@xbt.hk> Pieter Wuille <pieter.wuille@gmail.com> Status: Draft @@ -9,7 +9,7 @@ </pre> == Abstract == -This proposal defines a new transaction digest algorithm for signature verification in version 0 and version 1 witness program, in order to minimize redundant data hashing in verification, and to cover the input value by the signature. +This proposal defines a new transaction digest algorithm for signature verification in version 0 witness program, in order to minimize redundant data hashing in verification, and to cover the input value by the signature. == Motivation == There are 4 ECDSA signature verification codes in the original Bitcoin script system: CHECKSIG, CHECKSIGVERIFY, CHECKMULTISIG, CHECKMULTISIGVERIFY (“sigops”). According to the sighash type (ALL, NONE, SINGLE, ANYONECANPAY), a transaction digest is generated with a double SHA256 of a serialized subset of the transaction, and the signature is verified against this digest with a given public key. The detailed procedure is described in a Bitcoin Wiki article. <ref name=wiki>[https://en.bitcoin.it/wiki/OP_CHECKSIG]</ref> @@ -19,10 +19,10 @@ Unfortunately, there are at least 2 weaknesses in the original transaction diges * For the verification of each signature, the amount of data hashing is proportional to the size of the transaction. Therefore, data hashing grows in O(n<sup>2</sup>) as the number of sigops in a transaction increases. While a 1 MB block would normally take 2 seconds to verify with an average computer in 2015, a 1MB transaction with 5569 sigops may take 25 seconds to verify. This could be fixed by optimizing the digest algorithm by introducing some reusable “midstate”, so the time complexity becomes O(n). <ref>[https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2013-2292 CVE-2013-2292]</ref><ref>[https://bitcointalk.org/?topic=140078 New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify]</ref><ref>[http://rusty.ozlabs.org/?p=522 The Megatransaction: Why Does It Take 25 Seconds?]</ref> * The algorithm does not involve the amount of Bitcoin being spent by the input. This is usually not a problem for online network nodes as they could request for the specified transaction to acquire the output value. For an offline transaction signing device ("cold wallet"), however, the unknowing of input amount makes it impossible to calculate the exact amount being spent and the transaction fee. To cope with this problem a cold wallet must also acquire the full transaction being spent, which could be a big obstacle in the implementation of lightweight, air-gapped wallet. By including the input value of part of the transaction digest, a cold wallet may safely sign a transaction by learning the value from an untrusted source. In the case that a wrong value is provided and signed, the signature would be invalid and no funding might be lost. <ref>[https://bitcointalk.org/index.php?topic=181734.0 SIGHASH_WITHINPUTVALUE: Super-lightweight HW wallets and offline data]</ref> -Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. <ref>[https://github.com/CodeShark/bips/blob/segwit/bip-codeshark-jl2012-segwit.mediawiki BIPx: Segregated Witness (Consensus layer)]</ref> +Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. <ref>[https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141: Segregated Witness (Consensus layer)]</ref> == Specification == -A new transaction digest algorithm is defined, but only applicable to sigops in version 0 and version 1 witness program: +A new transaction digest algorithm is defined, but only applicable to sigops in version 0 witness program: Double SHA256 of the serialization of: 1. nVersion of the transaction 2. hashPrevouts @@ -114,7 +114,7 @@ Refer to the reference implementation, reproduced below, for the precise algorit == Deployment == -This proposal is deployed with Segregated Witness softfork (BIP x) +This proposal is deployed with Segregated Witness softfork (BIP 141) == Backward compatibility == @@ -122,7 +122,7 @@ As a soft fork, older software will continue to operate without modification. No == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit +https://github.com/sipa/bitcoin/commits/segwit3 == References == diff --git a/bip-0144.mediawiki b/bip-0144.mediawiki index ed8cf2b..736fadd 100644 --- a/bip-0144.mediawiki +++ b/bip-0144.mediawiki @@ -12,7 +12,7 @@ This BIP defines new messages and serialization formats for propagation of transactions and blocks committing to segregated witness structures. ==Motivation== -In addition to defining witness structures and requiring commitments in future blocks (BIPxxxx - Consensus segwit BIP), new mechanisms must be defined to allow peers to advertise support for segregated witness and to relay the witness structures and request them from other peers without breaking compatibility with older nodes. +In addition to defining witness structures and requiring commitments in future blocks ([https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141] - Consensus segwit BIP), new mechanisms must be defined to allow peers to advertise support for segregated witness and to relay the witness structures and request them from other peers without breaking compatibility with older nodes. ==Specification== @@ -116,7 +116,7 @@ MSG_WITNESS_BLOCK requests will return a block message with transactions that ha 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 +https://github.com/sipa/bitcoin/commits/segwit3 == Copyright == This document is placed in the public domain. |