diff options
31 files changed, 2345 insertions, 43 deletions
diff --git a/README.mediawiki b/README.mediawiki index 56f15d5..7726db8 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -19,6 +19,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Active |- +| [[bip-0009.mediawiki|9]] +| Version bits with timeout and delay +| Pieter Wuille, Peter Todd, Greg Maxwell, Rusty Russell +| Informational +| Draft +|- | [[bip-0010.mediawiki|10]] | Multi-Sig Transaction Distribution | Alan Reiner @@ -64,8 +70,8 @@ Those proposing changes should consider that ultimately consent may rest with th | [[bip-0017.mediawiki|17]] | OP_CHECKHASHVERIFY (CHV) | Luke Dashjr +| Standard | Withdrawn -| Draft |- | [[bip-0018.mediawiki|18]] | hashScriptCheck @@ -199,6 +205,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0047.mediawiki|47]] +| Reusable Payment Codes for Hierarchical Deterministic Wallets +| Justus Ranvier +| Informational +| Draft +|- | [[bip-0050.mediawiki|50]] | March 2013 Chain Fork Post-Mortem | Gavin Andresen @@ -254,6 +266,18 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0068.mediawiki|68]] +| Consensus-enforced transaction replacement signalled via sequence numbers +| Mark Friedenbach +| Standard +| Draft +|- +| [[bip-0069.mediawiki|69]] +| Lexicographical Indexing of Transaction Inputs and Outputs +| Kristov Atlas +| Standard +| Draft +|- | [[bip-0070.mediawiki|70]] | Payment protocol | Gavin Andresen @@ -277,6 +301,60 @@ Those proposing changes should consider that ultimately consent may rest with th | Stephen Pair | Standard | Draft +|- +| [[bip-0101.mediawiki|101]] +| Increase maximum block size +| Gavin Andresen +| Standard +| Draft +|- +| [[bip-0102.mediawiki|101]] +| Block size increase to 2MB +| Jeff Garzik +| Standard +| Draft +|- +| [[bip-0105.mediawiki|105]] +| Consensus based block size retargeting algorithm +| BtcDrak +| Standard +| Draft +|- +| [[bip-0106.mediawiki|106]] +| Dynamically Controlled Bitcoin Block Size Max Cap +| Upal Chakraborty +| Standard +| Draft +|- +| [[bip-0111.mediawiki|111]] +| NODE_BLOOM service bit +| Matt Corallo and Peter Todd +| Standard +| Draft +|- +| [[bip-0112.mediawiki|112]] +| CHECKSEQUENCEVERIFY +| BtcDrak and Mark Friedenbach +| Standard +| Draft +|- +| [[bip-0113.mediawiki|113]] +| Median time-past as endpoint for lock-time calculations +| Thomas Kerin and Mark Friedenbach +| Standard +| Draft +|- +| [[bip-0120.mediawiki|120]] +| Proof of Payment +| Kalle Rosenbaum +| Standard +| Draft +|- +| [[bip-0121.mediawiki|121]] +| Proof of Payment URI scheme +| Kalle Rosenbaum +| Standard +| Draft |} <!-- IMPORTANT! See the instructions at the top of this page, do NOT JUST add BIPs here! --> diff --git a/bip-0001.mediawiki b/bip-0001.mediawiki index 5c8a544..c18ebd3 100644 --- a/bip-0001.mediawiki +++ b/bip-0001.mediawiki @@ -27,11 +27,11 @@ The BIP editors assign BIP numbers and change their status. Please send all BIP- The BIP process begins with a new idea for Bitcoin. It is highly recommended that a single BIP contain a single key proposal or new idea. Small enhancements or patches often don't need a BIP and can be injected into the Bitcoin development work flow with a patch submission to the Bitcoin issue tracker. The more focused the BIP, the more successful it tends to be. The BIP editor reserves the right to reject BIP proposals if they appear too unfocused or too broad. If in doubt, split your BIP into several well-focused ones. -Each BIP must have a champion -- someone who writes the BIP using the style and format described below, shepherds the discussions in the appropriate forums, and attempts to build community consensus around the idea. The BIP champion (a.k.a. Author) should first attempt to ascertain whether the idea is BIP-able. Posting to the [http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development bitcoin-development@lists.sourceforge.net] mailing list (and maybe the [https://bitcointalk.org/index.php?board=6.0 Development&Technical Discussion] forum) is the best way to go about this. +Each BIP must have a champion -- someone who writes the BIP using the style and format described below, shepherds the discussions in the appropriate forums, and attempts to build community consensus around the idea. The BIP champion (a.k.a. Author) should first attempt to ascertain whether the idea is BIP-able. Posting to the [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev] mailing list (and maybe the [https://bitcointalk.org/index.php?board=6.0 Development&Technical Discussion] forum) is the best way to go about this. Vetting an idea publicly before going as far as writing a BIP is meant to save the potential author time. Many ideas have been brought forward for changing Bitcoin that have been rejected for various reasons. Asking the Bitcoin community first if an idea is original helps prevent too much time being spent on something that is guaranteed to be rejected based on prior discussions (searching the internet does not always do the trick). It also helps to make sure the idea is applicable to the entire community and not just the author. Just because an idea sounds good to the author does not mean it will work for most people in most areas where Bitcoin is used. -Once the champion has asked the Bitcoin community as to whether an idea has any chance of acceptance, a draft BIP should be presented to [http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development bitcoin-development@lists.sourceforge.net]. This gives the author a chance to flesh out the draft BIP to make properly formatted, of high quality, and to address initial concerns about the proposal. +Once the champion has asked the Bitcoin community as to whether an idea has any chance of acceptance, a draft BIP should be presented to [https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev bitcoin-dev@lists.linuxfoundation.org]. This gives the author a chance to flesh out the draft BIP to make properly formatted, of high quality, and to address initial concerns about the proposal. Following a discussion, the proposal should be sent to the Bitcoin-dev list and the BIP editor with the draft BIP. This draft must be written in BIP style as described below, else it will be sent back without further regard until proper formatting rules are followed. diff --git a/bip-0009.mediawiki b/bip-0009.mediawiki new file mode 100644 index 0000000..b160810 --- /dev/null +++ b/bip-0009.mediawiki @@ -0,0 +1,168 @@ +<pre> + BIP: 9 + Title: Version bits with timeout and delay + Author: Pieter Wuille <pieter.wuille@gmail.com>, Peter Todd <pete@petertodd.org>, Greg Maxwell <greg@xiph.org>, Rusty Russell <rusty@rustcorp.com.au> + Status: Draft + Type: Informational Track + Created: 2015-10-04 +</pre> + +==Abstract== + +This document specifies a proposed change to the semantics of the 'version' field in Bitcoin blocks, allowing multiple backward-compatible changes (further called "soft forks") to be deployed in parallel. It relies on interpreting the version field as a bit vector, where each bit can be used to track an independent change. These are tallied each retarget period. Once the consensus change succeeds or times out, there is a "fallow" pause after which the bit can be reused for later changes. + +==Motivation== + +BIP 34 introduced a mechanism for doing soft-forking changes without a predefined flag timestamp (or flag block height), instead relying on measuring miner support indicated by a higher version number in block headers. As it relies on comparing version numbers as integers however, it only supports one single change being rolled out at once, requiring coordination between proposals, and does not allow for permanent rejection: as long as one soft fork is not fully rolled out, no future one can be scheduled. + +In addition, BIP 34 made the integer comparison (nVersion >= 2) a consensus rule after its 95% threshold was reached, removing 2<sup>31</sup>+2 values from the set of valid version numbers (all negative numbers, as nVersion is interpreted as a signed integer, as well as 0 and 1). This indicates another downside this approach: every upgrade permanently restricts the set of allowed nVersion field values. This approach was later reused in BIP 66, which further removed nVersion = 2 as valid option. As will be shown further, this is unnecessary. + +==Specification== + +===Mechanism=== + +'''Bit flags''' +We are permitting several independent soft forks to be deployed in parallel. For each, a bit B is chosen from the set {0,1,2,...,28}, which is not currently in use for any other ongoing soft fork. Miners signal intent to enforce the new rules associated with the proposed soft fork by setting bit 1<sup>B</sup> in nVersion to 1 in their blocks. + +'''High bits''' +The highest 3 bits are set to 001, so the range of actually possible nVersion values is [0x20000000...0x3FFFFFFF], inclusive. This leaves two future upgrades for different mechanisms (top bits 010 and 011), while complying to the constraints set by BIP34 and BIP66. Having more than 29 available bits for parallel soft forks does not add anything anyway, as the (nVersion >= 3) requirement already makes that impossible. + +'''States''' +With every softfork proposal we associate a state BState, which begins +at ''defined'', and can be ''locked-in'', ''activated'', +or ''failed''. Transitions are considered after each +retarget period. + +'''Soft Fork Support''' +Software which supports the change should begin by setting B in all blocks +mined until it is resolved. + + if (BState != activated && BState != failed) { + SetBInBlock(); + } + +'''Success: Lock-in Threshold''' +If bit B is set in 1916 (1512 on testnet) or +more of the 2016 blocks within a retarget period, it is considered +''locked-in''. Miners should continue setting bit B, so uptake is +visible. + + if (NextBlockHeight % 2016 == 0) { + if (BState == defined && Previous2016BlocksCountB() >= 1916) { + BState = locked-in; + BActiveHeight = NextBlockHeight + 2016; + } + } + +'''Success: Activation Delay''' +The consensus rules related to ''locked-in'' soft fork will be enforced in +the second retarget period; ie. there is a one retarget period in +which the remaining 5% can upgrade. At the that activation block and +after, miners should stop setting bit B, which may be reused for a different soft fork. + + if (BState == locked-in && NextBlockHeight == BActiveHeight) { + BState = activated; + ApplyRulesForBFromNextBlock(); + /* B can be reused, immediately */ + } + +'''Failure: Timeout''' +A soft fork proposal should include a ''timeout''. This is measured +as the beginning of a calendar year as per this table (suggest +adding three to the current calendar year when drafting the soft fork proposal): + +{| +! Timeout Year +! >= Seconds +! Timeout Year +! >= Seconds +|- +|2018 +|1514764800 +|2026 +|1767225600 +|- +|2019 +|1546300800 +|2027 +|1798761600 +|- +|2020 +|1577836800 +|2028 +|1830297600 +|- +|2021 +|1609459200 +|2029 +|1861920000 +|- +|2022 +|1640995200 +|2030 +|1893456000 +|- +|2023 +|1672531200 +|2031 +|1924992000 +|- +|2024 +|1704067200 +|2032 +|1956528000 +|- +|2025 +|1735689600 +|2033 +|1988150400 +|} + +If the soft fork still not ''locked-in'' and the +GetMedianTimePast() of a block following a retarget period is at or +past this timeout, miners should cease setting this bit. + + if (NextBlockHeight % 2016 == 0) { + if (BState == defined && GetMedianTimePast(nextblock) >= BFinalYear) { + BState = failed; + } + } + +After another retarget period (to allow detection of buggy miners), +the bit may be reused. + +'''Warning system''' +To support upgrade warnings, an extra "unknown upgrade" is tracked, using the "implicit bit" mask = (block.nVersion & ~expectedVersion) != 0. Mask will be non-zero whenever an unexpected bit is set in nVersion. Whenever lock-in for the unknown upgrade is detected, the software should warn loudly about the upcoming soft fork. It should warn even more loudly after the next retarget period. + +'''Forks''' +It should be noted that the states are maintained along block chain +branches, but may need recomputation when a reorganization happens. + +===Support for future changes=== + +The mechanism described above is very generic, and variations are possible for future soft forks. Here are some ideas that can be taken into account. + +'''Modified thresholds''' +The 95% threshold (based on in BIP 34) does not have to be maintained for eternity, but changes should take the effect on the warning system into account. In particular, having a lock-in threshold that is incompatible with the one used for the warning system may have long-term effects, as the warning system cannot rely on a permanently detectable condition anymore. + +'''Conflicting soft forks''' +At some point, two mutually exclusive soft forks may be proposed. The naive way to deal with this is to never create software that implements both, but that is making a bet that at least one side is guaranteed to lose. Better would be to encode "soft fork X cannot be locked-in" as consensus rule for the conflicting soft fork - allowing software that supports both, but can never trigger conflicting changes. + +'''Multi-stage soft forks''' +Soft forks right now are typically treated as booleans: they go from an inactive to an active state in blocks. Perhaps at some point there is demand for a change that has a larger number of stages, with additional validation rules that get enabled one by one. The above mechanism can be adapted to support this, by interpreting a combination of bits as an integer, rather than as isolated bits. The warning system is compatible with this, as (nVersion & ~nExpectedVersion) will always be non-zero for increasing integers. + +== Rationale == + +The failure timeout allows eventual reuse of bits even if a soft fork was +never activated, so it's clear that the new use of the bit refers to a +new BIP. It's deliberately very course grained, to take into account +reasonable development and deployment delays. There are unlikely to be +enough failed proposals to cause a bit shortage. + +The fallow period at the conclusion of a soft fork attempt allows some +detection of buggy clients, and allows time for warnings and software +upgrades for successful soft forks. + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-0017.mediawiki b/bip-0017.mediawiki index 07dca96..44011d5 100644 --- a/bip-0017.mediawiki +++ b/bip-0017.mediawiki @@ -2,8 +2,8 @@ BIP: 17 Title: OP_CHECKHASHVERIFY (CHV) Author: Luke Dashjr <luke+bip17@dashjr.org> - Status: Draft - Type: Withdrawn + Status: Withdrawn + Type: Standards Track Created: 2012-01-18 </pre> diff --git a/bip-0021.mediawiki b/bip-0021.mediawiki index 00d9a53..2706926 100644 --- a/bip-0021.mediawiki +++ b/bip-0021.mediawiki @@ -56,6 +56,7 @@ The scheme component ("bitcoin:") is case-insensitive, and implementations must *address: bitcoin address *message: message that describes the transaction to the user ([[#Examples|see examples below]]) *size: amount of base bitcoin units ([[#Transfer amount/size|see below]]) +*paycode: payment code (BIP-47) *(others): optional, for future extensions ==== Transfer amount/size ==== @@ -67,6 +68,11 @@ I.e. amount=50.00 or amount=50 is treated as 50 BTC, and amount=50,000.00 is inv Bitcoin clients MAY display the amount in any format that is not intended to deceive the user. They SHOULD choose a format that is foremost least confusing, and only after that most reasonable given the amount requested. For example, so long as the majority of users work in BTC units, values should always be displayed in BTC by default, even if mBTC or TBC would otherwise be a more logical interpretation of the amount. + +==== Payment code ==== + +If a URI provides a payment code, and if the client supports BIP-47, then the resulting transaction SHOULD construct a transaction per BIP-47 instead of using the address provided in the URI. + == Rationale == ===Payment identifiers, not person identifiers=== @@ -122,3 +128,6 @@ Characters must be URI encoded properly. === Bitcoin clients === * Bitcoin-Qt supports the old version of Bitcoin URIs (ie without the req- prefix), with Windows and KDE integration as of commit 70f55355e29c8e45b607e782c5d76609d23cc858. +==References== + +* [[bip-0047.mediawiki|BIP47 - Reusable Payment Codes for Hierarchical Deterministic Wallets]] diff --git a/bip-0032.mediawiki b/bip-0032.mediawiki index 902a5eb..28541f5 100644 --- a/bip-0032.mediawiki +++ b/bip-0032.mediawiki @@ -209,7 +209,7 @@ It is also the reason for the existence of hardened keys, and why they are used ===Test vector 1=== -Master (hex): 000102030405060708090a0b0c0d0e0f +Seed (hex): 000102030405060708090a0b0c0d0e0f * Chain m ** ext pub: xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8 ** ext prv: xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi @@ -231,7 +231,7 @@ Master (hex): 000102030405060708090a0b0c0d0e0f ===Test vector 2=== -Master (hex): fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542 +Seed (hex): fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542 * Chain m ** ext pub: xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB ** ext prv: xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U diff --git a/bip-0045.mediawiki b/bip-0045.mediawiki index 3710ce8..f93319d 100644 --- a/bip-0045.mediawiki +++ b/bip-0045.mediawiki @@ -49,7 +49,7 @@ Purpose is a constant set to 45, following the BIP43 recommendation. It indicates that the subtree of this node is used according to this specification. <code> -m / purpose' / * +m / 45' / * </code> Hardened derivation is used at this level. @@ -76,11 +76,11 @@ purpose public keys: 03f76588e06c0d688617ef365d1e58a7f1aa84daa3801380b1e7f12acc9a69cd13 </pre> -it should use `m / purpose ' / 0 / *` for +it should use `m / 45 ' / 0 / *` for `039863fb5f07b667d9b1ca68773c6e6cdbcac0088ffba9af46f6f6acd153d44463`, -`m / purpose ' / 1 / *` for +`m / 45 ' / 1 / *` for `03a473275a750a20b7b71ebeadfec83130c014da4b53f1c4743fcf342af6589a38`, -and `m / purpose ' / 2 / *` for +and `m / 45 ' / 2 / *` for `03f76588e06c0d688617ef365d1e58a7f1aa84daa3801380b1e7f12acc9a69cd13`, as dictated by their lexicographical order. @@ -99,7 +99,7 @@ chain is used for addresses which are not meant to be visible outside of the wallet and is used for return transaction change. For example, if cosigner 2 wants to generate a change address, he would use -`m / purpose ' / 2 / 1 / *`, and `m / purpose ' / 2 / 0 / *` for a receive +`m / 45 ' / 2 / 1 / *`, and `m / 45 ' / 2 / 0 / *` for a receive address. Non-hardened derivation is used at this level. @@ -134,7 +134,7 @@ others using the next index, and calculate the needed script for the address. Example: Cosigner #2 wants to receive a payment to the shared wallet. His last used index on his own branch is 4. Then, the path for the next receive -address is `m/$purpose/2/1/5`. He uses this same path in all of the cosigners +address is `m/45'/2/0/5`. He uses this same path in all of the cosigners trees to generate a public key for each one, and from that he gets the new p2sh address. ====Change address case==== @@ -145,7 +145,7 @@ using a separate index to track the used change addresses. Example: Cosigner #5 wants to send a payment from the shared wallet, for which he'll need a change address. His last used change index on his own branch is -11. Then, the path for the next change address is `m/$purpose/5/0/12`. He uses +11. Then, the path for the next change address is `m/45'/5/1/12`. He uses this same path in all of the cosigners trees to generate a public key for each one, and from that he gets the new p2sh address. @@ -165,27 +165,23 @@ protocol to accept or reject it, belong to another BIP, in my opinion. ===Address discovery=== When the master seed is imported from an external source the software should -start to discover the accounts in the following manner: +start to discover the addresses in the following manner: -# derive the first account's node (index = 0) -# derive the external chain node of this account -# scan addresses of the external chain; respect the gap limit described below -# if no transactions are found on the external chain stop discovery -# if there are some transactions, increase the account index and go to step 1 +# for each cosigner: +# derive the cosigner's node (`m / 45' / cosigner_index`) +# for both the external and internal chains on this node (`m / 45' / cosigner_index / 0` and `m / 45' / cosigner_index / 1`): +# scan addresses of the chain; respect the gap limit described below -This algorithm is correct, because software should disallow creation of new -accounts if previous one has no transaction history as described in chapter -"Account" above. - -Please note that the algorithm works with the transaction history, not account -balances, so you can have account with total 0 coins and the algorithm will -still continue with discovery. +Please note that the algorithm uses the transaction history, not address +balances, so even if the address has 0 coins, the program should continue with discovery. +Opposite to BIP44, each cosigner branch needs to be checked, +even if the earlier ones don't have transactions ===Address gap limit=== -Address gap limit is currently set to 20. If the software hits 20 unused -addresses in a row, it expects there are no used addresses beyond this point -and stops searching the address chain. +Address gap limit is currently set to 20. If the software hits 20 unused +addresses (no transactions associated with that address) in a row, it expects +there are no used addresses beyond this point and stops searching the address chain. Wallet software should warn when user is trying to exceed the gap limit on an external chain by generating a new address. diff --git a/bip-0047.mediawiki b/bip-0047.mediawiki new file mode 100644 index 0000000..8247e00 --- /dev/null +++ b/bip-0047.mediawiki @@ -0,0 +1,259 @@ +RECENT CHANGES: + +* (21 Sep 2015) Correct base58check version byte + +* (18 Sep 2015) Clarify decoding of notification transactions + +<pre> + BIP: 47 + Title: Reusable Payment Codes for Hierarchical Deterministic Wallets + Authors: Justus Ranvier <justus@openbitcoinprivacyproject.org> + Status: Draft + Type: Informational + Created: 2015-04-24 +</pre> + +==Abstract== + +This BIP defines a technique for creating a payment code which can be publicly advertised and associated with a real-life identity without creating the loss of security or privacy inherent to P2PKH address reuse. + +This BIP is a particular application of BIP43 and is intended to supplement HD wallets which implement BIP44. + +The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. + +==Motivation== + +Payment codes add identity information to transactions which is useful in a merchant-customer interaction while protecting the privacy of users. Payment codes provide the privacy benefits of Darkwallet-style Stealth Addresses to SPV clients without requiring the assistance of a trusted full node and while greatly reducing reliance on blockchain storage. + +==Path levels== + +We define the following 3 levels in BIP32 path: + +<pre> +m / purpose' / coin_type' / identity' +</pre> + +Apostrophe in the path indicates that BIP32 hardened derivation is used. + +Each level has a special meaning, described in the chapters below. + +===Purpose=== + +Purpose is a constant set to 47' (or 0x8000002F) following the BIP43 recommendation. It indicates that the subtree of this node is used according to this specification. + +===Coin type=== + +The coin type field is identical to the same field in BIP44 + +Hardened derivation is used at this level. + +===Identity=== + +Identity is a particular extended public/private key pair. The extended public key is a payment code. + +Identities SHOULD have 1:1 correspondence with a BIP44 account, as in each BIP44 account in an HD wallet should be assigned exactly one payment code which shares the same index value. + +Hardened derivation is used at this level. + +Except where noted, all keys derived from a payment code use the public derivation method. + +====Binary Serialization==== + +A payment code contains the following elements: + +* Byte 0: type. required value: 0x01 +* Byte 1: features bit field. All bits must be zero except where specified elsewhere in this specification +** Bit 0: Bitmessage notification +** Bits 1-7: reserved +* Byte 2: sign. required value: 0x02 or 0x03 +* Bytes 3 - 34: x value, must be a member of the secp256k1 group +* Bytes 35 - 66: chain code +* Bytes 67 - 79: reserved for future expansion, zero-filled unless otherwise noted + +====Base58 Serialization==== + +When a payment code is presented to the user, it SHOULD be presented encoded in Base58Check form. + +* The version byte is: 0x47 (produces a "P" as the first character of the serialized form) +* The payload is the binary serialization of the payment code + +===Protocol=== + +In the following examples, Alice and Bob are identities with a corresponding payment codes. Alice initiates a Bitcoin transaction, and Bob is the recipient of the transaction. + +It is assumed that Alice can easily obtain Bob's payment code via a suitable method outside the scope of the payment code protocol. + +====Definitions==== + +* Payment code: an extended public key which is associated with a particular identity +* Notification address: the P2PKH address associated with the 0<sup>th</sup> public key derived from a payment code +* Notification transaction: a transaction which sends an output to a notification address which includes an embedded payment code + +====Notification Transaction==== + +Prior to the first time Alice initiates a transaction to Bob, Alice MUST inform Bob of her payment code via the following procedure: + +# Alice constructs a transaction which sends a small quantity of bitcoins to Bob's notification address (notification transaction) +## The inputs selected for this transaction MUST NOT be easily associated with Alice's notification address +# Alice derives a unique shared secret using ECDH: +## Alice selects the private key corresponding to the first exposed public key, of the first pubkey-exposing input, of the transaction: <pre>a</pre> +## Alice selects the public key associated with Bob's notification address: <pre>B, where B = bG</pre> +## Alice calculates a secret point: <pre>S = aB</pre> +## Alice calculates a 64 byte blinding factor: <pre>s = HMAC-SHA512(x, o)</pre> +### "x" is the x value of the secret point +### "o" is the outpoint being spent by the first pubkey-exposing input of the transaction. +# Alice serializes her payment code in binary form. +# Alice renders her payment code (P) unreadable to anyone except Bob: +## Replace the x value with x': <pre>x' = x XOR (first 32 bytes of s)</pre> +## Replace the chain code with c': <pre>c' = c XOR (last 32 bytes of s)</pre> +# Alice adds an OP_RETURN output to her transaction which consists of P. +<img src="bip-0047/reusable_payment_codes-01.png" /> + +# Bob watches for any transactions which create an output at his notification address. +# When a transaction is received, the client examines it to determine if it contains a standard OP_RETURN output with an 80 byte payload (notification transactions). +# If the first byte of the payload in a notification transaction is 0x01: +## Bob selects the first exposed public key, of the first pubkey-exposing input, of the transaction: <pre>A, where A = aG</pre> +## Bob selects the private key associated with his notification address: <pre>b</pre> +## Bob calculates a secret point: <pre>S = bA</pre> +## Bob calculates the binding factor: <pre>s = HMAC-SHA512(x, o)</pre> +### "x" is the x value of the secret point +### "o" is the outpoint being spent by the first pubkey-exposing input of the transaction. +## Bob interprets the 80 byte payload as a payment code, except: +### Replace the x value with x': <pre>x' = x XOR (first 32 bytes of s)</pre> +### Replace the chain code with c': <pre>c' = c XOR (last 32 bytes of s)</pre> +## If the updated x value is a member of the secp256k1 group, the payment code is valid. +## If the updated x value is not a member of the secp256k1 group, the payment code is ignored. + +Now that Bob's client has received Alice's payment code, it is possible for Alice to send payments (up to 2<sup>32</sup> payments) to Bob. + +Alice will never again need to send a notification transaction to Bob. + +Bitcoins received via notification transactions require special handling in order to avoid privacy leaks: + +# The value of outputs received to notification addresses MUST NOT be displayed to the user as part of their spendable balance. +# Outputs received to notification addresses MUST NOT be used as inputs for any transaction that involve ECDH calculations using any of the user's payment codes. +# Outputs received to notification addresses MAY be passed through a mixing service before being added to the user's spendable balance. +# Outputs received to notification addresses MAY be donated to miners using dust-b-gone or an equivalent procedure. + +====Sending==== + +# Each time Alice wants to initiate a transaction to Bob, Alice derives a unique P2PKH address for the transaction using ECDH follows: +## Alice selects the 0th private key derived from her payment code: <pre>a</pre> +## Alice selects the next unused public key derived from Bob's payment code, starting from zero: <pre>B, where B = bG</pre> +### The "next unused" public key is based on an index specific to the Alice-Bob context, not global to either Alice or Bob +## Alice calculates a secret point: <pre>S = aB</pre> +## Alice calculates a scalar shared secret using the x value of S: <pre>s = SHA256(Sx)</pre> +### If the value of s is not in the secp256k1 group, Alice MUST increment the index used to derive Bob's public key and try again. +## Alice uses the scalar shared secret to calculate the ephemeral public key used to generate the P2PKH address for this transaction: <pre>B' = B + sG</pre> +<img src="bip-0047/reusable_payment_codes-04.png" /> +<img src="bip-0047/reusable_payment_codes-05.png" /> +# Bob is watching for incoming payments on B' ever since he received the notification transaction from Alice. +## Bob calculates n shared secrets with Alice, using the 0<sup>th</sup> public key derived Alice's payment code, and private keys 0 - n derived from Bob's payment code, where n is his desired lookahead window. +## Bob calculates the ephemeral deposit addresses using the same procedure as Alice: <pre>B' = B + sG</pre> +## Bob calculate the private key for each ephemeral address as: <pre>b' = b + s</pre> +<img src="bip-0047/reusable_payment_codes-02.png" /> +<img src="bip-0047/reusable_payment_codes-03.png" /> + +====Refunds==== + +Because Bob learns Alice's payment code as part of the process of receiving a payment, Bob has all the information he needs in order to send a refund to Alice. + +A refund transaction is identical to a payment transactions, with only the roles of the participants switches. + +Bob MUST send a notification transaction to Alice prior to the first time he sends funds to Alice, even if he has received transactions from her in the past. + +<img src="bip-0047/reusable_payment_codes-06.png" /> + +====Anonymous Payments==== + +If Alice does not want her payment to Bob to be associated with her identity, she generates an ephemeral payment code to use for the transaction. + +* Ephemeral payment codes are the hardened children of a payment code, starting from an index of zero. +* An ephemeral payment code SHOULD only be used for a single outgoing payment. +* The notification address of an ephemeral payment code MUST be monitored for notification transactions in order to detect incoming refund payments +* The correspondence between BIP44 accounts and ephemeral payment codes is 1:many + +====Cold Storage==== + +* Unlike traditional watching-only wallets, those associated with payment codes help in cold storage can not detect incoming payments immediately. +* When the watching-only wallet detects an incoming notification transaction, it packages the transaction in an implementation-specific format suitable for transfer to the offline device. +* The offline device recovers the payment code, then pre-generates a large number of relevant keypairs (example: 10000) in order to minimize the need for air gap round trips. +* The offline device then packages the relevant public keys in an implementation-specific format suitable for transfer to the online device. +* The online device can then watch for incoming payments using a suitable lookahead window. +* If the lookahead window reaches the end of the pre-generated public keys, the user must generate more keys on the offline device and transfer them to the online device. + +====Wallet Recovery==== + +Normal operation of a payment code-enabled wallet can be performed by an SPV client and does not require access to a complete copy of the blockchain. + +Recovering a wallet from a seed, however, does require access to a fully-indexed blockchain. + +The required data may be obtained from copy of the blockchain under the control of the user, or via a publicly-queriable blockchain explorer. + +When querying a public blockchain explorer, wallets SHOULD connect to the explorer through Tor (or equivalent) and SHOULD avoid grouping queries in a manner that associates ephemeral addresses with each other. + +Previously-spendable funds will generally not be lost or become inaccessible after a recovery from a seed, but all information regarding previous outgoing payments will be lost. + +The metadata which a wallet must store regarding the state an identity consists of: + +# A list of every payment code to which the identity has sent a notification transaction. +## This list is lost if a wallet must be recovered from a seed. +## The recovered wallet MUST send notification transactions as if it was a newly-created wallet +# The index value corresponding to the next unused pubkey for each payment code on the previous list +## This value can be recovered by checking each ephemeral deposit address in sequence for transactions. +## Wallets MAY use a lookahead window capable of detecting gaps in the address sequence during this recovery operation. +# The index value of the next unused ephemeral payment code. +## Recovering all incoming funds associated with ephemeral payment codes with 100% certainty requires exhausting the entire 2<sup>32</sup> address space of potential ephemeral payment codes. +### In most cases, less than 100% certainty is acceptable as long as a fallback "deep scan" is available as an option to the user. +## The wallet checks the notification address for each ephemeral payment code for notification transactions in order to recover associated funds. +## Since most ephemeral payment codes will not receive a refund transaction wallets SHOULD use a large lookahead window for this recovery operation. +## The recovered value MUST be chosen as a number higher than any ephemeral payment code which has received a notification transaction. + +===Wallet Sharing=== + +Wallets using payment codes generally should not be shared across multiple devices, given the need to synchronize metadata between each instance. + +If wallets are shared between devices without a synchronization mechanism, undesirable address reuse can occur. + +Wallets may perform an OPTIONAL check for existing transactions to an ephemeral deposit addresses prior to sending a transaction by checking a local copy of the blockchain or querying a public blockchain explorer via Tor or equivalent. + +===Alternate Notification Methods=== + +In order to ensure that no funds will be lost in the event the recipient must recover their wallet from a seed, the sender MUST send a notification transaction the first time the sender interacts with a particular recipient. + +A recipient MAY choose to designate alternate notification methods which the sender may use in addition to a notification transaction. + +If the recipient specifies an alternate notification method, a compliant implementation MAY refrain from continually monitoring the notification address and SHOULD check the notification address periodically to detect payments sent by users who can not employ the alternate method. + +A recipient specifies their preference for alternate notification by setting the appropriate bits in the feature byte of their payment code. + +===Bitmessage Notification=== + +A recipient prefers to receive notifications via Bitmessage indiates this preference by: + +* Setting bit 0 of the features byte to 1 +* Setting byte 67 of the serialized payment code to the desired Bitmessage address version +* Setting byte 67 of the serialized payment code to the desired Bitmessage stream number + +The sender uses this information to construct a valid notification Bitmessage address: + +# Derive a Bitmessage signing key as: <pre>B = payment code / 0 / 0</pre> +# Initialize a counter at 1: <pre>n</pre> +# Derive a candidate encryption key as: <pre>B' = payment code / 0 / n</pre> +# If the combination of B and B` do not form a valid Bitmessage address, increment n by one and try again +# Use the address version, signing key, encryption key, and stream number to construct a Bitmessage address per the Bitmessage protocol + +The sender transmits their payment code in base58 form to the calculated Bitmessage address. + +In order to use Bitmessage notification, the recipient must have a Bitmessage client which listens at the address which the senders will derive and is capable of relaying received payment codes to the Bitcoin wallet. + +==Reference== + +* [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] +* [[bip-0043.mediawiki|BIP43 - Purpose Field for Deterministic Wallets]] +* [[bip-0044.mediawiki|BIP44 - Multi-Account Hierarchy for Deterministic Wallets]] +* [[https://bitcoin.org/en/glossary/outpoint|Outpoint]] +* [[https://github.com/petertodd/dust-b-gone|dust-b-gone]] +* [[https://en.bitcoin.it/wiki/Base58Check_encoding|Base58Check encoding]] +* [[https://bitmessage.org/bitmessage.pdf|Bitmessage]] +* [[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-April/007812.html|Mailing list discussion]] diff --git a/bip-0047/reusable_payment_codes-01.png b/bip-0047/reusable_payment_codes-01.png Binary files differnew file mode 100644 index 0000000..30a003f --- /dev/null +++ b/bip-0047/reusable_payment_codes-01.png diff --git a/bip-0047/reusable_payment_codes-02.png b/bip-0047/reusable_payment_codes-02.png Binary files differnew file mode 100644 index 0000000..da81d63 --- /dev/null +++ b/bip-0047/reusable_payment_codes-02.png diff --git a/bip-0047/reusable_payment_codes-03.png b/bip-0047/reusable_payment_codes-03.png Binary files differnew file mode 100644 index 0000000..3087293 --- /dev/null +++ b/bip-0047/reusable_payment_codes-03.png diff --git a/bip-0047/reusable_payment_codes-04.png b/bip-0047/reusable_payment_codes-04.png Binary files differnew file mode 100644 index 0000000..9738ca2 --- /dev/null +++ b/bip-0047/reusable_payment_codes-04.png diff --git a/bip-0047/reusable_payment_codes-05.png b/bip-0047/reusable_payment_codes-05.png Binary files differnew file mode 100644 index 0000000..5e93559 --- /dev/null +++ b/bip-0047/reusable_payment_codes-05.png diff --git a/bip-0047/reusable_payment_codes-06.png b/bip-0047/reusable_payment_codes-06.png Binary files differnew file mode 100644 index 0000000..c5619da --- /dev/null +++ b/bip-0047/reusable_payment_codes-06.png diff --git a/bip-0061.mediawiki b/bip-0061.mediawiki index a18a4e6..aca329a 100644 --- a/bip-0061.mediawiki +++ b/bip-0061.mediawiki @@ -107,6 +107,8 @@ The following codes are used: |- | 0x10 || Transaction is invalid for some reason (invalid signature, output value greater than input, etc.) |- +| 0x12 || An input is already spent +|- | 0x40 || Not mined/relayed because it is "non-standard" (type or version unknown by the server) |- | 0x41 || One or more output amounts are below the 'dust' threshold diff --git a/bip-0062.mediawiki b/bip-0062.mediawiki index 4846abf..5d46b7c 100644 --- a/bip-0062.mediawiki +++ b/bip-0062.mediawiki @@ -1,3 +1,5 @@ +'''NOTICE: This document is a work in progress and is not complete, implemented, or otherwise suitable for deployment.''' + <pre> BIP: 62 Title: Dealing with malleability @@ -38,7 +40,7 @@ The first six and part of the seventh can be fixed by extra consensus rules, but ===New rules=== Seven extra rules are introduced, to combat exactly the seven first sources of malleability listed above: -# '''Canonically encoded ECDSA signatures''' An ECDSA signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG or OP_CHECKMULTISIGVERIFY must be encoded using strict DER encoding. To provide a compact way to delibrately create an invalid signature for with OP_CHECKSIG and OP_CHECKMULTISIG the empty byte array (the result of OP_0) is also allowed. Doing a verification with a non-DER signature makes the entire script evaluate to False (not just the signature verification). See reference: [[#der-encoding|DER encoding]]. +# '''Canonically encoded ECDSA signatures''' An ECDSA signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG or OP_CHECKMULTISIGVERIFY must be encoded using strict DER encoding. To provide a compact way to deliberately create an invalid signature for OP_CHECKSIG and OP_CHECKMULTISIG, an empty byte array (i.e., the result of OP_0) is also allowed. Doing a verification with a non-DER signature makes the entire script evaluate to False (not just the signature verification). See reference: [[#der-encoding|DER encoding]]. # '''Non-push operations in scriptSig''' Only data pushes are allowed in scriptSig. Evaluating any other operation makes the script evaluate to false. See reference: [[#push-operators|Push operators]]. # '''Push operations in scriptSig of non-standard size type''' The smallest possible push operation must be used when possible. Pushing data using an operation that could be encoded in a shorter way makes the script evaluate to false. See reference: [[#push-operators|Push operators]]. # '''Zero-padded number pushes''' Any time a script opcode consumes a stack value that is interpreted as a number, it must be encoded in its shortest possible form. 'Negative zero' is not allowed. See reference: [[#numbers|Numbers]]. diff --git a/bip-0065.mediawiki b/bip-0065.mediawiki index 5549182..02de20b 100644 --- a/bip-0065.mediawiki +++ b/bip-0065.mediawiki @@ -40,7 +40,7 @@ An example where this technique is used is in micro-payment channels, where the nLockTime field proves that should the receiver vanish the sender is guaranteed to get all their escrowed funds back when the nLockTime is reached. -However the nLockTime field is insufficient if you wish to prove that +However, the nLockTime field is insufficient if you wish to prove that a transaction output ''cannot'' be spent until some time in the future, as there is no way to prove that the secret keys corresponding to the pubkeys controlling the funds have not been used to create a valid signature. @@ -60,7 +60,7 @@ either Alice or Bob to steal the funds illegitimately. Equally Lenny may prefer not to have immediate access to the funds to discourage bad actors from attempting to get the secret keys from him by force. -However with CHECKLOCKTIMEVERIFY the funds can be stored in scriptPubKeys of +However, with CHECKLOCKTIMEVERIFY the funds can be stored in scriptPubKeys of the form: IF @@ -74,24 +74,24 @@ the form: At any time the funds can be spent with the following scriptSig: - <Alice's signature> <Bob's signature> 0 + 0 <Alice's signature> <Bob's signature> 0 After 3 months have passed Lenny and one of either Alice or Bob can spend the funds with the following scriptSig: - <Alice/Bob's signature> <Lenny's signature> 1 + 0 <Alice/Bob's signature> <Lenny's signature> 1 ===Non-interactive time-locked refunds=== There exist a number of protocols where a transaction output is created that requires the co-operation of both parties to spend the output. To ensure the -failure of one party does not result in the funds becoming lost refund +failure of one party does not result in the funds becoming lost, refund transactions are setup in advance using nLockTime. These refund transactions need to be created interactively, and additionaly, are currently vulnerable to transaction mutability. CHECKLOCKTIMEVERIFY can be used in these protocols, replacing the interactive setup with a non-interactive setup, and additionally, -making transaction mutability a non-issue. +making transaction mutability (aka malleability) a non-issue. ====Two-factor wallets==== @@ -172,6 +172,17 @@ sufficiently far into the future that large miners profitably can't sell the sacrifices at a discount. +===Freezing Funds=== + +In addition to using cold storage, hardware wallets, and P2SH multisig outputs +to control funds, now funds can be frozen in UTXOs directly on the blockchain. +With the following scriptPubKey, nobody will be able to spend the encumbered +output until the provided expiry time. This ability to freeze funds reliably may +be useful in scenarios where reducing duress or confiscation risk is desired. + + <expiry time> CHECKLOCKTIMEVERIFY DROP DUP HASH160 <pubKeyHash> EQUALVERIFY CHECKSIG + + ===Replacing the nLockTime field entirely=== As an aside, note how if the SignatureHash() algorithm could optionally cover @@ -276,9 +287,21 @@ time. PayPub - https://github.com/unsystem/paypub -Jeremy Spilman Micropayment Channels - http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg02028.html +Jeremy Spilman Micropayment Channels - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html + + +==Implementations== + +Python / python-bitcoinlib + +- https://github.com/petertodd/checklocktimeverify-demos + +JavaScript / Node.js / bitcore + +- https://github.com/mruddy/bip65-demos ==Copyright== This document is placed in the public domain. + diff --git a/bip-0066.mediawiki b/bip-0066.mediawiki index 3fd1b85..1235afd 100644 --- a/bip-0066.mediawiki +++ b/bip-0066.mediawiki @@ -2,7 +2,7 @@ BIP: 66 Title: Strict DER signatures Author: Pieter Wuille <pieter.wuille@gmail.com> - Status: Draft + Status: Final Type: Standards Track Created: 2015-01-10 </pre> @@ -23,7 +23,7 @@ This document proposes to restrict valid signatures to exactly what is mandated Every signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied, must be encoded using strict DER encoding (see further). -These operators all perform ECDSA verifications on pubkey/signature pairs, iterating from the top of the stack backwards. For each such verifcation, if the signature does not pass the <code>IsValidSignatureEncoding</code> check below, the entire script evaluates to false immediately. If the signature is valid DER, but does not pass ECDSA verification, opcode execution continues as it used to, causing opcode execution to stop and push false on the stack (but not immediately fail the script) in some cases, which potentially skips further signatures (and thus does not subject them to <code>IsValidSignatureEncoding</code>). +These operators all perform ECDSA verifications on pubkey/signature pairs, iterating from the top of the stack backwards. For each such verification, if the signature does not pass the <code>IsValidSignatureEncoding</code> check below, the entire script evaluates to false immediately. If the signature is valid DER, but does not pass ECDSA verification, opcode execution continues as it used to, causing opcode execution to stop and push false on the stack (but not immediately fail the script) in some cases, which potentially skips further signatures (and thus does not subject them to <code>IsValidSignatureEncoding</code>). ===DER encoding reference=== diff --git a/bip-0067.mediawiki b/bip-0067.mediawiki index 9c4f3de..8be5c9b 100644 --- a/bip-0067.mediawiki +++ b/bip-0067.mediawiki @@ -4,8 +4,8 @@ Title: Deterministic Pay-to-script-hash multi-signature addresses through public key sorting Author: Thomas Kerin, Jean-Pierre Rupp, Ruben de Vries Status: Draft - Type: Standard - Created: 8 February 2015 + Type: Standards Track + Created: 2015-02-08 </pre> ==Abstract== diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki new file mode 100644 index 0000000..12b97c7 --- /dev/null +++ b/bip-0068.mediawiki @@ -0,0 +1,254 @@ +<pre> + BIP: 68 + Title: Consensus-enforced transaction replacement signaled via sequence numbers (relative lock-time) + Author: Mark Friedenbach <mark@friedenbach.org> + Status: Draft + Type: Standards Track + Created: 2015-05-28 +</pre> + +==Abstract== + +This BIP describes a modification to the consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding outpoint, for the purpose of supporting consensus-enforced transaction replacement features. + +==Motivation== + +Bitcoin has sequence number fields for each input of a transaction. The original idea appears to have been that the highest sequence number should dominate and miners should prefer it over lower sequence numbers. This was never really implemented, and the half-implemented code seemed to be making an assumption that miners would honestly prefer the higher sequence numbers, even if the lower ones were much much more profitable. That turns out to be a dangerous assumption, and so most technical people have assumed that kind of sequence number mediated replacement was useless because there was no way to enforce "honest" behavior, as even a few rational (profit maximizing) miners would break that completely. The change described by this BIP provides the missing piece that makes sequence numbers do something significant with respect to enforcing transaction replacement without assuming anything other than profit-maximizing behavior on the part of miners. + +==Specification== + +For transactions with an nVersion of 2 or greater, if the most significant bit (1 << 31) of a sequence number is clear, the remaining 31 bits are interpreted as an encoded relative lock-time. A sequence number with the most significant bit set is given no consensus meaning and can be included in any block, like normal, under all circumstances. + +If the second most significant bit (1 << 30) is clear, the next 16 bits are interpreted as a minimum block-height constraint over the input's age. The remaining 14 bits have no consensus-enforced meaning. A sequence number of zero indicates a relative lock-time of zero blocks (bits 31 and 30 clear) and can be included in any block. A sequence number of 1 << 14 can be included in the next block after the input it is spending, or any block thereafter, but cannot be included in the same block as its parent. A sequence number of 2 << 14 can't be included until at least two blocks later, and so on. + +Alternatively, if the second most significant bit (1 << 30) is set, the next 25 bits are interpreted as a minimum block-time constraint over the input's age. The remaining 5 bits have no consensus-enforced meaning. A sequence number with just that second most significant bit set (0x40000000) is interpreted as a relative lock-time of 0, measured in seconds, and can be included in the same block as the output being spent. Advancing that sequence number by 2^5 (0x40000020) constrains the transaction to be included in blocks with an nTime timestamp at least one second greater than the median time stamp of the 11 blocks prior to the block containing the coin being spent. Advancing the sequence number by an additional 2^5 (0x40000040) constrains the spend to be two seconds later, and so on. + +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: + +<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. */ + const uint32_t CTxIn::SEQUENCE_FINAL = 0xffffffff; + /* Threshold for CTxIn::nSequence: below this value it is interpreted + * as arelative lock-time, otherwise ignored. */ + const uint32_t CTxIn::SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31); + /* Threshold for CTxIn::nSequence when interpreted as a relative + * lock-time: below this value it has units of blocks, otherwise + * seconds. */ + const uint32_t CTxIn::SEQUENCE_UNITS_THRESHOLD = (1 << 30); + /* Number of reserved low-order bits (depending on units used) which + * are shifted out prior to relative lock-time constraint checking. */ + const int CTxIn::SEQUENCE_BLOCKS_OFFSET = 14; + const int CTxIn::SEQUENCE_SECONDS_OFFSET = 5; + + int64_t LockTime(const CTransaction &tx, + int flags, const CCoinsView* pCoinsView, + int nBlockHeight, int64_t nBlockTime) + { + CCoins coins; + + 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; + + BOOST_FOREACH(const CTxIn& txin, tx.vin) { + // Set a flag if we witness an input that isn't finalized. + if (CTxIn::SEQUENCE_FINAL == txin.nSequence) + continue; + else + fFinalized = false; + + // Do not enforce sequence numbers as a relative lock time + // unless we have been instructed to, and a view has been + // provided. + if (!(fEnforceBIP68 && pCoinsView)) + continue; + + // Sequence numbers equal to or above the locktime threshold + // are not treated as relative lock-times, nor are they given + // any consensus-enforced meaning at this point. + if (txin.nSequence >= CTxIn::SEQUENCE_LOCKTIME_THRESHOLD) + continue; + + // Fetch the UTXO corresponding to this input. + if (!pCoinsView->GetCoins(txin.prevout.hash, coins)) { + // It is fully expected that coinbases inputs are not + // found in the UTXO set. Proceed to the next intput... + if (txin.prevout.IsNull()) + continue; + // If a non-coinbase input cannot be found, we cannot + // be certain about whether lock-time constraints have + // been satisfied. Note that it should only ever be + // possible for this to happen with wallet transactions + // that have unknown inputs. + else + return std::numeric_limits<int64_t>::max(); + } + + // coins.nHeight is MEMPOOL_HEIGHT (an absurdly high value) + // if the parent transaction was from the mempool. We can't + // know what height it will have once confirmed, but we + // assume it makes it in the same block. + int nCoinHeight = std::min(coins.nHeight, nBlockHeight); + + if (txin.nSequence < CTxIn::SEQUENCE_UNITS_THRESHOLD) { + // 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_BLOCKS_OFFSET) - 1); + } else { + // In two locations that follow we make reference to + // chainActive.Tip(). To prevent a race condition, we + // store a reference to the current tip. + // + // Note that it is not guaranteed that indexBestBlock will + // be consistent with the passed in view. The proper thing + // to do is to have the view return time information about + // UTXOs. + const CBlockIndex& indexBestBlock = *chainActive.Tip(); + + // The only time the negative branch of this conditional + // is executed is when the prior output was taken from the + // mempool, in which case we assume it makes it into the + // same block (see above). + int64_t nCoinTime = (nCoinHeight <= (indexBestBlock.nHeight+1)) + ? indexBestBlock.GetAncestor(nCoinHeight-1)->GetMedianTimePast() + : nBlockTime; + + // 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. We subtract one for the same reason as + // above. + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)(( + txin.nSequence - CTxIn::SEQUENCE_UNITS_THRESHOLD) + >> CTxIn::SEQUENCE_SECONDS_OFFSET) - 1); + } + } + + // 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 >= nBlockHeight) + return nMinHeight; + if (nMinTime >= nBlockTime) + return nMinTime; + + return 0; + } + + int64_t CheckLockTime(const CTransaction &tx, int flags) + { + AssertLockHeld(cs_main); + + // By convention a negative value for flags indicates that the + // current network-enforced consensus rules should be used. + flags = std::max(flags, 0); + + // pcoinsTip contains the UTXO set for chainActive.Tip() + CCoinsViewMemPool viewMemPool(pcoinsTip, mempool); + const CCoinsView *pCoinsView = &viewMemPool; + + // CheckLockTime() uses chainActive.Height()+1 to evaluate + // nLockTime because when LockTime() 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 + // LockTime() with one more than chainActive.Height(). + const int nBlockHeight = chainActive.Height() + 1; + + // Timestamps on the other hand don't get any special treatment, + // because we can't know what timestamp the next block will have, + // and there aren't timestamp applications where it matters. + const int64_t nBlockTime = GetAdjustedTime(); + + return LockTime(tx, flags, pCoinsView, nBlockHeight, nBlockTime); + } +</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. + +==Rationale== + +Using sequence numbers for locking inputs makes sense, since no transaction can be in a block before its parent transactions. This means that a lower sequence number can always be included earlier than a higher one (even if the time the original coins being spent was unknown when the transaction was authored). Because of this, even rational miners should go along with the scheme: Take the lowest sequence number and collect the fees, or skip over it in the hopes that no one else takes a lower number before the next available higher number becomes spendable. And, of course, users are not constrained to make their sequence numbers go up only one at a time. So it's "take the most updated version, now, or gamble that no one in the next dozen blocks takes the most updated and that you manage to include the next to most when it finally becomes mineable." This is similar to how lock-time works. In fact, this scheme is precisely a per-input relative lock-time. + +==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 1btc 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.1btc. She does so by constructing a transaction spending the 1btc output and sending 0.1btc to Bob and 0.9btc 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.1btc, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2btc, then 0.3btc 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.25btc. He does so by constructing a transaction spending the 1btc output and sending 0.95btc (= 0.7btc + 0.25btc) to Alice and 0.05btc to himself. Since Bob will still have in his logs the transaction giving him 0.7btc 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 + +https://github.com/bitcoin/bitcoin/pull/6312 + +==Acknowledgments== + +Credit goes to Gregory Maxwell for providing a succinct and clear description of the behavior of this change, which became the basis of this BIP text. + +==Deployment== + +We reuse the double-threshold switch over mechanism from BIPs 34 and 66, with the same thresholds, but for nVersion = 4. The new rules are in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = 4. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = 4, nVersion = 3 blocks become invalid, and all further blocks enforce the new rules. + +It is recommended that this soft-fork deployment trigger include other related proposals for improving Bitcoin's lock-time capabilities, including [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY, [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY, and [https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113] Median time-past as endpoint for lock-time calculations. + +==Compatibility== + +The only use of sequence numbers by the Bitcoin Core reference client software is to disable checking the nLockTime constraints in a transaction. The semantics of that application are preserved by this BIP. + +There may be other uses for the sequence number field that are not commonplace or yet to be discovered. To allow for other uses of the sequence number field, it is only interpreted as a relative lock-time as described in this BIP if the most significant bit is clear. This allows up to 31 bits of the sequence number field to be used for other purposes in applications which don't simultaneously need a per-input relative lock-time. In addition, the unused low-order bits of the relative lock-time encoding are available for use by future soft-fork extensions. + +The most efficient way to calculate sequence number from relative lock-time is with bit masks and shifts: + +<pre> + // 0 <= nHeight < 65,535 blocks (1.25 years) + nSequence = nHeight << 14; + nHeight = nSequence >> 14; + + // 0 <= nTime < 33,554,431 seconds (1.06 years) + nSequence = 1<<30 | (nTime << 5); + nTime = (nSequence ^ 1<<30) >> 5; +</pre> + +==References== + +Bitcoin mailing list discussion: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html + +[https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki BIP 34]: Block v2, Height in Coinbase + +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY + +[https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP 66]: Strict DER signatures + +[https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY + +[https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113]: Median time-past as endpoint for lock-time calculations diff --git a/bip-0069.mediawiki b/bip-0069.mediawiki new file mode 100644 index 0000000..e23ff04 --- /dev/null +++ b/bip-0069.mediawiki @@ -0,0 +1,169 @@ +<pre> + BIP: BIP: 69 + Title: Lexicographical Indexing of Transaction Inputs and Outputs + Authors: Kristov Atlas <kristov@openbitcoinprivacyproject.org> + Editors: Daniel Cousens <bips@dcousens.com> + Status: Draft + Type: Informational + Created: 2015-06-12 +</pre> + +==Abstract== + +Currently there is no standard for bitcoin wallet clients when ordering transaction inputs and outputs. +As a result, wallet clients often have a discernible blockchain fingerprint, and can leak private information about their users. +By contrast, a standard for non-deterministic sorting could be difficult to audit. +This document proposes deterministic lexicographical sorting, using hashes of previous transactions and output indices to sort transaction inputs, as well as values and scriptPubKeys to sort transaction outputs. + +==Copyright== + +This BIP is in the public domain. + +==Motivation== + +Currently, there is no clear standard for how wallet clients ought to order transaction inputs and outputs. +Since wallet clients are left to their own devices to determine this ordering, they often leak information about their users’ finances. +For example, a wallet client might naively order inputs based on when addresses were added to a wallet by the user through importing or random generation. +Many wallets will place spending outputs first and change outputs second, leaking information about both the sender and receiver’s finances to passive blockchain observers. +Such information should remain private not only for the benefit of consumers, but in higher order financial systems must be kept secret to prevent fraud. +Currently, there is no clear standard for how wallet clients ought to order transaction inputs and outputs. +Since wallet clients are left to their own devices to determine this ordering, they often leak information about their users’ finances. +For example, a wallet client might naively order inputs based on when addresses were added to a wallet by the user through importing or random generation. +Many wallets will place spending outputs first and change outputs second, leaking information about both the sender and receiver’s finances to passive blockchain observers. +Such information should remain private not only for the benefit of consumers, but in higher order financial systems must be kept secret to prevent fraud. +A researcher recently demonstrated this principle when he detected that Bitstamp leaked information when creating exchange transactions, enabling potential espionage among traders. [1] + +One way to address these privacy weaknesses is by randomizing the order of inputs and outputs. [2] +After all, the order of inputs and outputs does not impact the function of the transaction they belong to, making random sorting viable. +Unfortunately, it can be difficult to prove that this sorting process is genuinely randomly sorted based on code or run-time analysis, especially if the software is closed source. +A malicious software developer can abuse the ordering of inputs and outputs as a side channel of leaking information. +For example, if an attacker can patch a victim’s HD wallet client to order inputs and outputs based on the bits of a master private key, then the attacker can eventually steal all of the victim’s funds by monitoring the blockchain. +Non-deterministic methods of sorting are difficult to audit because they are not repeatable. + +The lack of standardization between wallet clients when ordering inputs and outputs can yield predictable quirks that characterize particular wallet clients or services. +Such quirks create unique fingerprints that a privacy attacker can employ through simple passive blockchain observation. + +The solution is to create an algorithm for sorting transaction inputs and outputs that is deterministic. +Since it is deterministic, it should also be unambiguous — that is, given a particular transaction, the proper order of inputs and outputs should be obvious. +To make this standard as widely applicable as possible, it should rely on information that is downloaded by both full nodes (with or without typical efficiency techniques such as pruning) and SPV nodes. +In order to ensure that it does not leak confidential data, it must rely on information that is publicly accessible through the blockchain. +The use of public blockchain information also allows a transaction to be sorted even when it is a multi-party transaction, such as in the example of a CoinJoin. + +==Specification== + +===Applicability=== + +This BIP applies to any transaction for which the order of its inputs and outputs does not impact the transaction’s function. +Currently, this refers to any transaction that employs the SIGHASH_ALL signature hash type, in which signatures commit to the exact order of inputs and outputs. +Transactions that use SIGHASH_ANYONECANPAY and/or SIGHASH_NONE may include inputs and/or outputs that are not signed; however, compliant software should still emit transactions with lexicographically sorted inputs and outputs, even though they may later be modified by others. + +In the event that future protocol upgrades introduce new signature hash types, compliant software should apply the lexicographical ordering principle analogously. + +While out of scope of this BIP, protocols that do require a specified order of inputs/outputs (e.g. due to use of SIGHASH_SINGLE) should consider the goals of this BIP and how best to adapt them to the specific needs of those protocols. + +===Lexicographical Ordering=== + +Lexicographical ordering is an algorithm for comparison used to sort two sets based on their cartesian order within their common superset. +Lexicographic order is also often known as alphabetical order, or dictionary order. + +Common implementations include: + +* `std::lexicographical_compare` in C++ [5] +* `cmp` in Python 2.7 +* `memcmp` in C [6] +* `Buffer.compare` in Node.js [7] + +For more information, see the wikipedia entry on Lexicographical order. [8] + +N.B. All comparisons do not need to operate in constant time since they are not processing secret information. + +===Transaction Inputs=== + +Transaction inputs are defined by the hash of a previous transaction, the output index of of a UTXO from that previous transaction, the size of an unlocking script, the unlocking script, and a sequence number. [3] +For sorting inputs, the hash of the previous transaction and the output index within that transaction are sufficient for sorting purposes; each transaction hash has an extremely high probability of being unique in the blockchain — this is enforced for coinbase transactions by BIP30 — and output indices within a transaction are unique. +For the sake of efficiency, transaction hashes should be compared first before output indices, since output indices from different transactions are often equivalent, while all bytes of the transaction hash are effectively random variables. + +Previous transaction hashes (in reversed byte-order) are to be sorted in ascending order, lexicographically. +In the event of two matching transaction hashes, the respective previous output indices will be compared by their integer value, in ascending order. +If the previous output indices match, the inputs are considered equal. + +Transaction malleability will not negatively impact the correctness of this process. +Even if a wallet client follows this process using unconfirmed UTXOs as inputs and an attacker changes modifies the blockchain’s record of the hash of the previous transaction, the wallet client will include the invalidated previous transaction hash in its input data, and will still correctly sort with respect to that invalidated hash. + +===Transaction Outputs=== + +A transaction output is defined by its scriptPubKey and amount. [3] +For the sake of efficiency, amounts should be compared first for sorting, since they contain fewer bytes of information (8 bytes) compared to a standard P2PKH scriptPubKey (25 bytes). [4] + +Transaction output amounts (as 64-bit unsigned integers) are to be sorted in ascending order. +In the event of two matching output amounts, the respective output scriptPubKeys (as a byte-array) will be compared lexicographically, in ascending order. +If the scriptPubKeys match, the outputs are considered equal. + +===Examples=== + +Transaction 0a6a357e2f7796444e02638749d9611c008b253fb55f5dc88b739b230ed0c4c3: + +Inputs: + + <nowiki>0: 0e53ec5dfb2cb8a71fec32dc9a634a35b7e24799295ddd5278217822e0b31f57[0] + 1: 26aa6e6d8b9e49bb0630aac301db6757c02e3619feb4ee0eea81eb1672947024[1] + 2: 28e0fdd185542f2c6ea19030b0796051e7772b6026dd5ddccd7a2f93b73e6fc2[0] + 3: 381de9b9ae1a94d9c17f6a08ef9d341a5ce29e2e60c36a52d333ff6203e58d5d[1] + 4: 3b8b2f8efceb60ba78ca8bba206a137f14cb5ea4035e761ee204302d46b98de2[0] + 5: 402b2c02411720bf409eff60d05adad684f135838962823f3614cc657dd7bc0a[1] + 6: 54ffff182965ed0957dba1239c27164ace5a73c9b62a660c74b7b7f15ff61e7a[1] + 7: 643e5f4e66373a57251fb173151e838ccd27d279aca882997e005016bb53d5aa[0] + 8: 6c1d56f31b2de4bfc6aaea28396b333102b1f600da9c6d6149e96ca43f1102b1[1] + 9: 7a1de137cbafb5c70405455c49c5104ca3057a1f1243e6563bb9245c9c88c191[0] + 10: 7d037ceb2ee0dc03e82f17be7935d238b35d1deabf953a892a4507bfbeeb3ba4[1] + 11: a5e899dddb28776ea9ddac0a502316d53a4a3fca607c72f66c470e0412e34086[0] + 12: b4112b8f900a7ca0c8b0e7c4dfad35c6be5f6be46b3458974988e1cdb2fa61b8[0] + 13: bafd65e3c7f3f9fdfdc1ddb026131b278c3be1af90a4a6ffa78c4658f9ec0c85[0] + 14: de0411a1e97484a2804ff1dbde260ac19de841bebad1880c782941aca883b4e9[1] + 15: f0a130a84912d03c1d284974f563c5949ac13f8342b8112edff52971599e6a45[0] + 16: f320832a9d2e2452af63154bc687493484a0e7745ebd3aaf9ca19eb80834ad60[0]</nowiki> + +Outputs: + + <nowiki>0: 400057456 76a9144a5fba237213a062f6f57978f796390bdcf8d01588ac + 1: 40000000000 76a9145be32612930b8323add2212a4ec03c1562084f8488ac</nowiki> + +Transaction 28204cad1d7fc1d199e8ef4fa22f182de6258a3eaafe1bbe56ebdcacd3069a5f + +Inputs: + + <nowiki>0: 35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055[0] + 1: 35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055[1]</nowiki> + +Outputs: + + <nowiki>0: 100000000 41046a0765b5865641ce08dd39690aade26dfbf5511430ca428a3089261361cef170e3929a68aee3d8d4848b0c5111b0a37b82b86ad559fd2a745b44d8e8d9dfdc0cac + 1: 2400000000 41044a656f065871a353f216ca26cef8dde2f03e8c16202d2e8ad769f02032cb86a5eb5e56842e92e19141d60a01928f8dd2c875a390f67c1f6c94cfc617c0ea45afac</nowiki> + +==Discussion== + +* [[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-June/008484.html|<nowiki>[Bitcoin-development]</nowiki> Lexicographical Indexing of Transaction Inputs and Outputs]] +* [[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-June/008487.html|<nowiki>[Bitcoin-development] [RFC]</nowiki> Canonical input and output ordering in transactions]] + +==References== + +* [[https://bitcoinmagazine.com/20273/bitstamp-exchange-activity-trackable-due-multisig-wallet-implementation/|1: Bitstamp Info Leak]] +* [[https://github.com/OpenBitcoinPrivacyProject/wallet-ratings/blob/master/2015-1/criteria.md|2: OBPP Random Indexing as Countermeasure]] +* [[https://github.com/aantonop/bitcoinbook/blob/develop/ch05.asciidoc|3: Mastering Bitcoin]] +* [[https://en.bitcoin.it/wiki/Script|4: Bitcoin Wiki on Script]] +* [[http://www.cplusplus.com/reference/algorithm/lexicographical_compare|5: std::lexicographical_compare]] +* [[http://www.cplusplus.com/reference/cstring/memcmp|6: memcmp]] +* [[https://nodejs.org/api/buffer.html#buffer_class_method_buffer_compare_buf1_buf2|7: Buffer.compare]] +* [[https://en.wikipedia.org/wiki/Lexicographical_order|8: Lexicographical order]] + +==Implementations== + +* [[https://github.com/spesmilo/electrum/blob/2af670ea2b92e835919b745d94afcb8b4ec32fda/lib/transaction.py#L648|Electrum]] +* [[https://github.com/bitcoinjs/bip69/blob/master/index.js|BitcoinJS]] +* [[https://github.com/bitcoinjs/bip69/blob/master/test/fixtures.json|BitcoinJS Test Fixtures]] +* [[https://www.npmjs.com/package/bip69|NodeJS]] + +==Acknowledgements== + +Danno Ferrin <danno@numisight.com>, Sergio Demian Lerner <sergiolerner@certimix.com>, Justus Ranvier <justus@openbitcoinprivacyproject.org>, and Peter Todd <pete@petertodd.org> contributed to the design and motivations for this BIP. +A similar proposal was submitted to the Bitcoin-dev mailing list independently by Rusty Russell <rusty@rustcorp.com.au> diff --git a/bip-0069/bip-0069_examples.py b/bip-0069/bip-0069_examples.py new file mode 100644 index 0000000..e2f52ed --- /dev/null +++ b/bip-0069/bip-0069_examples.py @@ -0,0 +1,112 @@ +import binascii + +#returns -1 if barr1 is less, 1 if barr1 is greater, and 0 if equal +def bytearr_cmp(barr1, barr2): + pos = 0 + while (pos < len(barr1) and pos < len(barr2)): + if (barr1[pos] < barr2[pos]): + return -1; + elif (barr1[pos] > barr2[pos]): + return 1; + pos = pos + 1 + #the shorter array will be ordered first + if (len(barr1) < len(barr2)): + return -1 + elif (len(barr1) > len(barr2)): + return 1 + else: + return 0 + +#tuples: (prev_tx_hash_byte_arr_little_endian, prev_tx_output_index) +def input_cmp(input_tuple1, input_tuple2): + #test prev_tx_hash_byte_arr_little_endian first + prev_tx_hash_cmp = bytearr_cmp(input_tuple1[0], input_tuple2[0]) + if (prev_tx_hash_cmp != 0): + return prev_tx_hash_cmp + #tie-breaker: prev_tx_output_index + if (input_tuple1[1] < input_tuple2[1]): + return -1 + elif (input_tuple1[1] > input_tuple2[1]): + return 1 + else: + raise ValueError('Matching previous transaction hash and previous transaction output index for two disinct inputs. Invalid!') + +def sort_inputs(input_tuples): + return sorted(input_tuples, cmp=input_cmp) + +def print_inputs(ordered_input_tuples): + index = 0 + for prev_tx_hash_byte_arr_little_endian, prev_tx_output_index in ordered_input_tuples: + prev_tx_hash_hex = binascii.hexlify(bytearray(prev_tx_hash_byte_arr_little_endian)) + print("%d: %s[%d]" % (index, prev_tx_hash_hex, prev_tx_output_index)) + index = index + 1 + +#tuples: (amount, scriptPubKey_byte_arr) +def output_cmp(output_tuple1, output_tuple2): + #test amount first + if (output_tuple1[0] < output_tuple2[0]): + return -1 + elif (output_tuple1[0] > output_tuple2[0]): + return 1 + #tie-breaker: scriptPubKey_byte_arr + return bytearray_cmp(output_tuple1[1], output_tuple2[1]) + +def sort_outputs(output_tuples): + return sorted(output_tuples, cmp=output_cmp) + +def print_outputs(ordered_output_tuples): + index = 0 + for amount, scriptPubKey_byte_arr in ordered_output_tuples: + scriptPubKey_hex = binascii.hexlify(bytearray(scriptPubKey_byte_arr)) + print("%d:\t%d\t%s" % (index, amount, scriptPubKey_hex)) + index = index + 1 + +def main(): + #reference data: https://blockchain.info/rawtx/0a6a357e2f7796444e02638749d9611c008b253fb55f5dc88b739b230ed0c4c3 + tx_0a6a_input_tuples = [ + # (prev_tx_hash_byte_arr_little_endian, prev_tx_output_index) + ([0x64, 0x3e, 0x5f, 0x4e, 0x66, 0x37, 0x3a, 0x57, 0x25, 0x1f, 0xb1, 0x73, 0x15, 0x1e, 0x83, 0x8c, 0xcd, 0x27, 0xd2, 0x79, 0xac, 0xa8, 0x82, 0x99, 0x7e, 0x00, 0x50, 0x16, 0xbb, 0x53, 0xd5, 0xaa], 0), + ([0x28, 0xe0, 0xfd, 0xd1, 0x85, 0x54, 0x2f, 0x2c, 0x6e, 0xa1, 0x90, 0x30, 0xb0, 0x79, 0x60, 0x51, 0xe7, 0x77, 0x2b, 0x60, 0x26, 0xdd, 0x5d, 0xdc, 0xcd, 0x7a, 0x2f, 0x93, 0xb7, 0x3e, 0x6f, 0xc2], 0), + ([0xf0, 0xa1, 0x30, 0xa8, 0x49, 0x12, 0xd0, 0x3c, 0x1d, 0x28, 0x49, 0x74, 0xf5, 0x63, 0xc5, 0x94, 0x9a, 0xc1, 0x3f, 0x83, 0x42, 0xb8, 0x11, 0x2e, 0xdf, 0xf5, 0x29, 0x71, 0x59, 0x9e, 0x6a, 0x45], 0), + ([0x0e, 0x53, 0xec, 0x5d, 0xfb, 0x2c, 0xb8, 0xa7, 0x1f, 0xec, 0x32, 0xdc, 0x9a, 0x63, 0x4a, 0x35, 0xb7, 0xe2, 0x47, 0x99, 0x29, 0x5d, 0xdd, 0x52, 0x78, 0x21, 0x78, 0x22, 0xe0, 0xb3, 0x1f, 0x57], 0), + ([0x38, 0x1d, 0xe9, 0xb9, 0xae, 0x1a, 0x94, 0xd9, 0xc1, 0x7f, 0x6a, 0x08, 0xef, 0x9d, 0x34, 0x1a, 0x5c, 0xe2, 0x9e, 0x2e, 0x60, 0xc3, 0x6a, 0x52, 0xd3, 0x33, 0xff, 0x62, 0x03, 0xe5, 0x8d, 0x5d], 1), + ([0xf3, 0x20, 0x83, 0x2a, 0x9d, 0x2e, 0x24, 0x52, 0xaf, 0x63, 0x15, 0x4b, 0xc6, 0x87, 0x49, 0x34, 0x84, 0xa0, 0xe7, 0x74, 0x5e, 0xbd, 0x3a, 0xaf, 0x9c, 0xa1, 0x9e, 0xb8, 0x08, 0x34, 0xad, 0x60], 0), + ([0xde, 0x04, 0x11, 0xa1, 0xe9, 0x74, 0x84, 0xa2, 0x80, 0x4f, 0xf1, 0xdb, 0xde, 0x26, 0x0a, 0xc1, 0x9d, 0xe8, 0x41, 0xbe, 0xba, 0xd1, 0x88, 0x0c, 0x78, 0x29, 0x41, 0xac, 0xa8, 0x83, 0xb4, 0xe9], 1), + ([0x3b, 0x8b, 0x2f, 0x8e, 0xfc, 0xeb, 0x60, 0xba, 0x78, 0xca, 0x8b, 0xba, 0x20, 0x6a, 0x13, 0x7f, 0x14, 0xcb, 0x5e, 0xa4, 0x03, 0x5e, 0x76, 0x1e, 0xe2, 0x04, 0x30, 0x2d, 0x46, 0xb9, 0x8d, 0xe2], 0), + ([0x54, 0xff, 0xff, 0x18, 0x29, 0x65, 0xed, 0x09, 0x57, 0xdb, 0xa1, 0x23, 0x9c, 0x27, 0x16, 0x4a, 0xce, 0x5a, 0x73, 0xc9, 0xb6, 0x2a, 0x66, 0x0c, 0x74, 0xb7, 0xb7, 0xf1, 0x5f, 0xf6, 0x1e, 0x7a], 1), + ([0xba, 0xfd, 0x65, 0xe3, 0xc7, 0xf3, 0xf9, 0xfd, 0xfd, 0xc1, 0xdd, 0xb0, 0x26, 0x13, 0x1b, 0x27, 0x8c, 0x3b, 0xe1, 0xaf, 0x90, 0xa4, 0xa6, 0xff, 0xa7, 0x8c, 0x46, 0x58, 0xf9, 0xec, 0x0c, 0x85], 0), + ([0xa5, 0xe8, 0x99, 0xdd, 0xdb, 0x28, 0x77, 0x6e, 0xa9, 0xdd, 0xac, 0x0a, 0x50, 0x23, 0x16, 0xd5, 0x3a, 0x4a, 0x3f, 0xca, 0x60, 0x7c, 0x72, 0xf6, 0x6c, 0x47, 0x0e, 0x04, 0x12, 0xe3, 0x40, 0x86], 0), + ([0x7a, 0x1d, 0xe1, 0x37, 0xcb, 0xaf, 0xb5, 0xc7, 0x04, 0x05, 0x45, 0x5c, 0x49, 0xc5, 0x10, 0x4c, 0xa3, 0x05, 0x7a, 0x1f, 0x12, 0x43, 0xe6, 0x56, 0x3b, 0xb9, 0x24, 0x5c, 0x9c, 0x88, 0xc1, 0x91], 0), + ([0x26, 0xaa, 0x6e, 0x6d, 0x8b, 0x9e, 0x49, 0xbb, 0x06, 0x30, 0xaa, 0xc3, 0x01, 0xdb, 0x67, 0x57, 0xc0, 0x2e, 0x36, 0x19, 0xfe, 0xb4, 0xee, 0x0e, 0xea, 0x81, 0xeb, 0x16, 0x72, 0x94, 0x70, 0x24], 1), + ([0x40, 0x2b, 0x2c, 0x02, 0x41, 0x17, 0x20, 0xbf, 0x40, 0x9e, 0xff, 0x60, 0xd0, 0x5a, 0xda, 0xd6, 0x84, 0xf1, 0x35, 0x83, 0x89, 0x62, 0x82, 0x3f, 0x36, 0x14, 0xcc, 0x65, 0x7d, 0xd7, 0xbc, 0x0a], 1), + ([0x7d, 0x03, 0x7c, 0xeb, 0x2e, 0xe0, 0xdc, 0x03, 0xe8, 0x2f, 0x17, 0xbe, 0x79, 0x35, 0xd2, 0x38, 0xb3, 0x5d, 0x1d, 0xea, 0xbf, 0x95, 0x3a, 0x89, 0x2a, 0x45, 0x07, 0xbf, 0xbe, 0xeb, 0x3b, 0xa4], 1), + ([0x6c, 0x1d, 0x56, 0xf3, 0x1b, 0x2d, 0xe4, 0xbf, 0xc6, 0xaa, 0xea, 0x28, 0x39, 0x6b, 0x33, 0x31, 0x02, 0xb1, 0xf6, 0x00, 0xda, 0x9c, 0x6d, 0x61, 0x49, 0xe9, 0x6c, 0xa4, 0x3f, 0x11, 0x02, 0xb1], 1), + ([0xb4, 0x11, 0x2b, 0x8f, 0x90, 0x0a, 0x7c, 0xa0, 0xc8, 0xb0, 0xe7, 0xc4, 0xdf, 0xad, 0x35, 0xc6, 0xbe, 0x5f, 0x6b, 0xe4, 0x6b, 0x34, 0x58, 0x97, 0x49, 0x88, 0xe1, 0xcd, 0xb2, 0xfa, 0x61, 0xb8], 0)] + tx_0a6a_sorted_input_tuples = sort_inputs(tx_0a6a_input_tuples) + print_inputs(tx_0a6a_sorted_input_tuples) + + tx_0a6a_output_tuples = [ + # (amount, scriptPubKey_byte_arr) + (400057456, [0x76, 0xa9, 0x14, 0x4a, 0x5f, 0xba, 0x23, 0x72, 0x13, 0xa0, 0x62, 0xf6, 0xf5, 0x79, 0x78, 0xf7, 0x96, 0x39, 0x0b, 0xdc, 0xf8, 0xd0, 0x15, 0x88, 0xac]), + (40000000000, [0x76, 0xa9, 0x14, 0x5b, 0xe3, 0x26, 0x12, 0x93, 0x0b, 0x83, 0x23, 0xad, 0xd2, 0x21, 0x2a, 0x4e, 0xc0, 0x3c, 0x15, 0x62, 0x08, 0x4f, 0x84, 0x88, 0xac])] + tx_0a6a_sorted_output_tuples = sort_outputs(tx_0a6a_output_tuples) + print_outputs(tx_0a6a_sorted_output_tuples) + + #reference data: https://blockchain.info/rawtx/28204cad1d7fc1d199e8ef4fa22f182de6258a3eaafe1bbe56ebdcacd3069a5f thanks @quantabytes! + tx_2820_input_tuples = [ + # (prev_tx_hash, prev_tx_output_index) + ("35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055", 0), + ("35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055", 1)] #duplicate prev_tx_hash + + tx_2820_sorted_input_tuples = sort_inputs(tx_2820_input_tuples) + print_inputs(tx_2820_sorted_input_tuples) + + tx_2820_output_tuples = [ + # (amount, scriptPubKey_byte_arr) + (100000000, [0x41, 0x04, 0x6a, 0x07, 0x65, 0xb5, 0x86, 0x56, 0x41, 0xce, 0x08, 0xdd, 0x39, 0x69, 0x0a, 0xad, 0xe2, 0x6d, 0xfb, 0xf5, 0x51, 0x14, 0x30, 0xca, 0x42, 0x8a, 0x30, 0x89, 0x26, 0x13, 0x61, 0xce, 0xf1, 0x70, 0xe3, 0x92, 0x9a, 0x68, 0xae, 0xe3, 0xd8, 0xd4, 0x84, 0x8b, 0x0c, 0x51, 0x11, 0xb0, 0xa3, 0x7b, 0x82, 0xb8, 0x6a, 0xd5, 0x59, 0xfd, 0x2a, 0x74, 0x5b, 0x44, 0xd8, 0xe8, 0xd9, 0xdf, 0xdc, 0x0c, 0xac]), + (2400000000, [0x41, 0x04, 0x4a, 0x65, 0x6f, 0x06, 0x58, 0x71, 0xa3, 0x53, 0xf2, 0x16, 0xca, 0x26, 0xce, 0xf8, 0xdd, 0xe2, 0xf0, 0x3e, 0x8c, 0x16, 0x20, 0x2d, 0x2e, 0x8a, 0xd7, 0x69, 0xf0, 0x20, 0x32, 0xcb, 0x86, 0xa5, 0xeb, 0x5e, 0x56, 0x84, 0x2e, 0x92, 0xe1, 0x91, 0x41, 0xd6, 0x0a, 0x01, 0x92, 0x8f, 0x8d, 0xd2, 0xc8, 0x75, 0xa3, 0x90, 0xf6, 0x7c, 0x1f, 0x6c, 0x94, 0xcf, 0xc6, 0x17, 0xc0, 0xea, 0x45, 0xaf, 0xac])] + tx_2820_sorted_output_tuples = sort_outputs(tx_2820_output_tuples) + print_outputs(tx_2820_output_tuples) + +if __name__ == "__main__": + main() diff --git a/bip-0070/paymentrequest.proto b/bip-0070/paymentrequest.proto index 6680810..717946e 100644 --- a/bip-0070/paymentrequest.proto +++ b/bip-0070/paymentrequest.proto @@ -3,7 +3,7 @@ // // Use fields 1000+ for extensions; // to avoid conflicts, register extensions via pull-req at -// https://github.com/bitcoin/bips/bip-0070/extensions.mediawiki +// https://github.com/bitcoin/bips/blob/master/bip-0070/extensions.mediawiki // package payments; diff --git a/bip-0101.mediawiki b/bip-0101.mediawiki new file mode 100644 index 0000000..a76db0f --- /dev/null +++ b/bip-0101.mediawiki @@ -0,0 +1,126 @@ +<pre> + BIP: 101 + Title: Increase maximum block size + Author: Gavin Andresen <gavinandresen@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-06-22 +</pre> + +==Abstract== + +This BIP proposes replacing the fixed one megabyte maximum block size with a maximum size that grows over time at a predictable rate. + +==Motivation== + +Transaction volume on the Bitcoin network has been growing, and will soon reach the one-megabyte-every-ten-minutes limit imposed by the one megabyte maximum block size. Increasing the maximum size reduces the impact of that limit on Bitcoin adoption and growth. + +==Specification== + +After deployment (see the Deployment section for details), the maximum allowed size of a block on the main network shall be calculated based on the timestamp in the block header. + +The maximum size shall be 8,000,000 bytes at a timestamp of 2016-01-11 00:00:00 UTC (timestamp 1452470400), and shall double every 63,072,000 seconds (two years, ignoring leap years), until 2036-01-06 00:00:00 UTC (timestamp 2083190400). The maximum size of blocks in between doublings will increase linearly based on the block's timestamp. The maximum size of blocks after 2036-01-06 00:00:00 UTC shall be 8,192,000,000 bytes. + +Expressed in pseudo-code, using integer math, assuming that block_timestamp is after the activation time (as described in the Deployment section below): + + function max_block_size(block_timestamp): + + time_start = 1452470400 + time_double = 60*60*24*365*2 + size_start = 8000000 + if block_timestamp >= time_start+time_double*10 + return size_start * 2^10 + + // Piecewise-linear-between-doublings growth: + time_delta = block_timestamp - time_start + doublings = time_delta / time_double + remainder = time_delta % time_double + interpolate = (size_start * 2^doublings * remainder) / time_double + max_size = size_start * 2^doublings + interpolate + + return max_size + +==Deployment== + +Deployment shall be controlled by hash-power supermajority vote (similar to the technique used in BIP34), but the earliest possible activation time is 2016-01-11 00:00:00 UTC. + +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. If a supermajority is achieved more than two weeks before 2016-01-11 00:00:00 UTC, the activation time will be 2016-01-11 00:00:00 UTC. + +Block version numbers are used only for activation; once activation is achieved, the maximum block size shall be as described in the specification section, regardless of the version number of the block. + +==Test network== + +Test network parameters are the same as the main network, except starting earlier with easier supermajority conditions and a shorter grace period: + + starting time: 1 Aug 2015 (timestamp 1438387200) + activation condition: 75 of 100 blocks + grace period: 24 hours + +==Rationale== + +The initial size of 8,000,000 bytes was chosen after testing the current reference implementation code with larger block sizes and receiving feedback from miners on bandwidth-constrained networks (in particular, Chinese miners behind the Great Firewall of China). + +The doubling interval was chosen based on long-term growth trends for CPU power, storage, and Internet bandwidth. The 20-year limit was chosen because exponential growth cannot continue forever. If long-term trends do not continue, maximum block sizes can be reduced by miner consensus (a soft-fork). + +Calculations are based on timestamps and not blockchain height because a timestamp is part of every block's header. This allows implementations to know a block's maximum size after they have downloaded it's header, but before downloading any transactions. + +The deployment plan is taken from Jeff Garzik's proposed BIP100 block size increase, and is designed to give miners, merchants, and full-node-running-end-users sufficient time to upgrade to software that supports bigger blocks. A 75% supermajority was chosen so that one large mining pool does not have effective veto power over a blocksize increase. The version number scheme is designed to be compatible with Pieter's Wuille's proposed "Version bits" BIP, and to not interfere with any other consensus rule changes in the process of being rolled out. + +==Objections to this proposal== + +Raising the 1MB block size has been [https://www.google.com/webhp?#q=1mb+limit+site%3Abitcointalk.org discussed and debated for years]. + +===Centralization of full nodes=== + +The number of fully-validating nodes reachable on the network has been steadily declining. Increasing the capacity of the network to handle transactions by increasing the maximum block size may accelerate that decline, meaning a less distributed network that is more vulnerable to disruption. The size of this effect is debatable; the author of this BIP believes that the decline in fully validating nodes on the network is largely due to the availability of convenient, attractive, secure, lightweight wallet software and the general trend away from computing on desktop computers to mobile phones and tablets. + +Increasing the capacity of the network to handle transactions should enable increased adoption by users and businesses, especially in areas of the world where existing financial infrastructure is weak. That could lead to a more robust network with nodes running in more political jurisdictions. + +===Centralization of mining: costs=== + +Miners benefit from low-latency, high-bandwidth connections because they increase their chances of winning a "block race" (two or more blocks found at approximately the same time). With the current peer-to-peer networking protocol, announcing larger blocks requires more bandwidth. If the costs grow high enough, the result will be a very small number of very large miners. + +The limits proposed by this BIP are designed so that running a fully validating node has very modest costs, which, if current trends in the cost of technology continue, will become even less expensive over time. + +===Centralization of mining: big-block attacks=== + +[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-June/008820.html Simulations show] that with the current peer-to-peer protocol, miners behind high-latency or low-bandwidth links are at a disadvantage compared to miners connected to a majority of hashpower via low-latency, high-bandwidth links. Larger blocks increase the advantage of miners with high-bandwidth connections, although that advantage can be minimized with changes to the way new blocks are announced (e.g. http://bitcoinrelaynetwork.org/ ). + +If latency and bandwidth to other miners were the only variable that affected the profitability of mining, and miners were driven purely by profit, the end result would be one miner running on one machine, where latency was zero and bandwidth was essentially infinite. + +However, many other factors influence miner profitability, including cost of electricity and labor and real estate, ability to use waste heat productively, access to capital to invest in mining equipment, etc. Increasing the influence of bandwidth in the mining profitability equation will not necessarily lead to more centralization. + +===Unspent Transaction Output Growth=== + +This BIP makes no attempt to restrict the approximately 100% per-year growth in unspent transaction outputs (see http://gavinandresen.ninja/utxo-uhoh for details), because the author believe that problem should be solved by a further restriction on blocks described in a separate BIP (perhaps an additional limit on how much the transactions in any block may increase the UTXO set size). + +==Long-term fee incentives== + +http://gavinandresen.ninja/block-size-and-miner-fees-again + +==Other solutions considered== + +There have been dozens of proposals for increasing the block size over the years. Some notable ideas: + +===One-time increase=== + +A small, quick one-time increase to, for example, 2MB blocks, would be the most conservative option. + +However, a one-time increase requires just as much care in testing and deployment as a longer-term fix. And the entire debate over how large or small a limit is appropriate would be repeated as soon as the new limit was reached. + +===Dynamic limit proposals=== + +BIP 100 proposes a dynamic limit determined by miner preferences expressed in coinbase transactions, with limits on the rate of growth. It gives miners more direct control over the maximum block size, which some people see as an advantage over this proposal and some see as a disadvantage. It is more complex to implement, because the maximum allowed size for a block depends on information contained in coinbase transactions from previous blocks (which may not be immediately known if block contents are being fetched out-of-order in a 'headers-first' mode). + +[https://bitcointalk.org/index.php?topic=1078521.0 Meni Rosenfeld has proposed] that miners sacrifice mining reward to "pay for" bigger blocks, so there is an incentive to create bigger blocks only if transaction fees cover the cost of creating a larger block. This proposal is significantly more complex to implement, and it is not clear if a set of parameters for setting the cost of making a block bigger can be found that is not equivalent to a centrally-controlled network-wide minimum transaction fee. + +==Compatibility== + +This is a hard-forking change to the Bitcoin protocol; anybody running code that fully validates blocks must upgrade before the activation time or they will risk rejecting a chain containing larger-than-one-megabyte blocks. + +Simplified Payment Verification software is not affected, unless it makes assumptions about the maximum depth of a transaction's merkle branch based on the minimum size of a transaction and the maximum block size. + +==Implementation== + +https://github.com/bitcoin/bitcoin/pull/6341 + diff --git a/bip-0105.mediawiki b/bip-0105.mediawiki new file mode 100644 index 0000000..cbd309d --- /dev/null +++ b/bip-0105.mediawiki @@ -0,0 +1,106 @@ +<pre> + BIP: 105 + Title: Consensus based block size retargeting algorithm + Author: BtcDrak <btcdrak@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-08-21 +</pre> + +==Abstract== + +A method of altering the maximum allowed block size of the Bitcoin protocol +using a consensus based approach. + +==Motivation== + +There is a belief that Bitcoin cannot easily respond to raising the +blocksize limit if popularity was to suddenly increase due to a mass adoption +curve, because co-ordinating a hard fork takes considerable time, and being +unable to respond in a timely manner would irreparably harm the credibility of +bitcoin. + +Additionally, predetermined block size increases are problematic because they +attempt to predict the future, and if too large could have unintended +consequences like damaging the possibility for a fee market to develop +as block subsidy decreases substantially over the next 9 years; introducing +or exacerbating mining attack vectors; or somehow affect the network in unknown +or unpredicted ways. Since fixed changes are hard to deploy, the damage could be +extensive. + +Dynamic block size adjustments also suffer from the potential to be gamed by the +larger hash power. + +Free voting as suggested by BIP100 allows miners to sell their votes out of band +at no risk, and enable the sponsor the ability to manipulate the blocksize. +It also provides a cost free method or the larger pools to vote in ways to +manipulate the blocksize such to disadvantage or attack smaller pools. + + +==Rationale== + +By introducing a cost to increase the block size ensures the mining community +will collude to increase it only when there is a clear necessity, and reduce it +when it is unnecessary. Larger miners cannot force their wishes so easily +because not only will they have to pay extra a difficulty target, then can be +downvoted at no cost by the objecting hash power. + +Using difficulty as a penalty is better than a fixed cost in bitcoins because it +is less predictable. + +In order to prevent miners having complete control over blocksize, an upper +limit is required at protocol level. This feature ensures full nodes retain +control over consensus, remembering full nodes are the mechanism to keep miners +honest. + + +==Specification== + +The initial block size limit shall be 1MB. + +Each time a miner creates a block, they may vote to increase or decrease the +blocksize by a maximum of 10% of the current block size limit. These votes will +be used to recalculate the new block size limit every 2016 blocks. + +Votes are cast using the block's coinbase transaction scriptSig. + +As per BIP34, the coinbase transaction scriptSig starts with a push of the block +height. The next push is a little-endian number representing the preferred block +size in bytes. For example, 0x4c(OP_PUSHDATA1) 0x03(size of constant) 0x80 0x84 0x1e(2MB) +or 0x4c(OP_PUSHDATA1) 0x04(size of constant) 0x80 0x96 0x98 0x00(10MB). + +If a miner votes for an increase, the block hash must meet a difficulty target +which is proportionally larger than the standard difficulty target based on the +percentage increase they voted for. + +Votes proposing decreasing the block size limit do not need to meet a higher +difficulty target. + +Miners can vote for no change by voting for the current block size. + +For blocks to be valid the blockhash must meet the required difficulty target +for the vote otherwise the block is invalid and will be rejected. + +Every 2016 blocks, the block size limit will be recalculated by the median of +all votes in the last 2016 blocks. This will redefine the block size limit for +the next 2016 blocks. + +Blocks that are larger than the calculated base block size limit are invalid and +will be rejected. + +The base block size limit may not reduce below 1MB or increase above 8MB. + + +==Acknowledgements== + +This proposal is based on ideas and concepts derived from the writings of +Meni Rosenfeld and Gregory Maxwell. + + +==References== + +[[bip-0034.mediawiki|BIP34]] + +==Copyright== + +This work is placed in the public domain. diff --git a/bip-0106.mediawiki b/bip-0106.mediawiki new file mode 100644 index 0000000..e9018fa --- /dev/null +++ b/bip-0106.mediawiki @@ -0,0 +1,80 @@ +<pre> + BIP: 106 + Title: Dynamically Controlled Bitcoin Block Size Max Cap + Author: Upal Chakraborty <bitcoin@upalc.com> + Status: Draft + Type: Standards Track + Created: 2015-08-24 +</pre> + +==Abstract== + +This BIP proposes replacing the fixed one megabyte maximum block size with a dynamically controlled maximum block size that may increase or decrease with difficulty change depending on various network factors. I have two proposals regarding this... + +i. Depending only on previous block size calculation. + +ii. Depending on previous block size calculation and previous Tx fee collected by miners. + +==Motivation== + +With increased adoption, transaction volume on bitcoin network is bound to grow. If the one megabyte max cap is not changed to a flexible one which changes itself with changing network demand, then adoption will hamper and bitcoin's growth may choke up. Following graph shows the change in average block size since inception... + +https://blockchain.info/charts/avg-block-size?timespan=all&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address= + +==Specification== + +===Proposal 1 : Depending only on previous block size calculation=== + + If more than 50% of block's size, found in the first 2000 of the last difficulty period, is more than 90% MaxBlockSize + Double MaxBlockSize + Else if more than 90% of block's size, found in the first 2000 of the last difficulty period, is less than 50% MaxBlockSize + Half MaxBlockSize + Else + Keep the same MaxBlockSize + +===Proposal 2 : Depending on previous block size calculation and previous Tx fee collected by miners=== + + TotalBlockSizeInLastButOneDifficulty = Sum of all Block size of first 2008 blocks in last 2 difficulty period + TotalBlockSizeInLastDifficulty = Sum of all Block size of second 2008 blocks in last 2 difficulty period (This actually includes 8 blocks from last but one difficulty) + + TotalTxFeeInLastButOneDifficulty = Sum of all Tx fees of first 2008 blocks in last 2 difficulty period + TotalTxFeeInLastDifficulty = Sum of all Tx fees of second 2008 blocks in last 2 difficulty period (This actually includes 8 blocks from last but one difficulty) + + If ( ( (Sum of first 4016 block size in last 2 difficulty period)/4016 > 50% MaxBlockSize) AND (TotalTxFeeInLastDifficulty > TotalTxFeeInLastButOneDifficulty) AND (TotalBlockSizeInLastDifficulty > TotalBlockSizeInLastButOneDifficulty) ) + MaxBlockSize = TotalBlockSizeInLastDifficulty * MaxBlockSize / TotalBlockSizeInLastButOneDifficulty + Else If ( ( (Sum of first 4016 block size in last 2 difficulty period)/4016 < 50% MaxBlockSize) AND (TotalTxFeeInLastDifficulty < TotalTxFeeInLastButOneDifficulty) AND (TotalBlockSizeInLastDifficulty < TotalBlockSizeInLastButOneDifficulty) ) + MaxBlockSize = TotalBlockSizeInLastDifficulty * MaxBlockSize / TotalBlockSizeInLastButOneDifficulty + Else + Keep the same MaxBlockSize + +==Rationale== + +These two proposals have been derived after discussion on [https://bitcointalk.org/index.php?topic=1154536.0 BitcoinTalk] and [http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010285.html bitcoin-dev mailing list]. The original idea and its evolution in the light of various arguements can be found [http://upalc.com/maxblocksize.php here]. + +===Proposal 1 : Depending only on previous block size calculation=== + +This solution is derived directly from the indication of the problem. If transaction volume increases, then we will naturally see bigger blocks. On the contrary, if there are not enough transaction volume, but maximum block size is high, then only few blocks may sweep the mempool. Hence, if block size is itself taken into consideration, then maximum block size can most rationally be derived. Moreover, this solution not only increases, but also decreases the maximum block size, just like difficulty. + +===Proposal 2 : Depending on previous block size calculation and previous Tx fee collected by miners=== + +This solution takes care of stable mining subsidy. It will not increase maximum block size, if Tx fee collection is not increasing and thereby creating a Tx fee pressure on the market. On the other hand, though the block size max cap is dynamically controlled, it is very difficult to game by any party because the increase or decrease of block size max cap will take place in the same ratio of average block size increase or decrease. + +==Compatibility== + +This is a hard-forking change to the Bitcoin protocol; anybody running code that fully validates blocks must upgrade before the activation time or they will risk rejecting a chain containing larger-than-one-megabyte blocks. + +==Other solutions considered== + +[http://gtf.org/garzik/bitcoin/BIP100-blocksizechangeproposal.pdf Making Decentralized Economic Policy] - by Jeff Garzik + +[https://bitcointalk.org/index.php?topic=1078521.0 Elastic block cap with rollover penalties] - by Meni Rosenfeld + +[https://github.com/bitcoin/bips/blob/master/bip-0101.mediawiki Increase maximum block size] - by Gavin Andresen + +[https://gist.github.com/sipa/c65665fc360ca7a176a6 Block size following technological growth] - by Pieter Wuille + +[https://lightning.network/lightning-network-paper.pdf The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments] - by Joseph Poon & Thaddeus Dryja + +==Deployment== + +If consensus is achieved, deployment can be made at a future block number at which difficulty will change. diff --git a/bip-0111.mediawiki b/bip-0111.mediawiki new file mode 100644 index 0000000..d3bd630 --- /dev/null +++ b/bip-0111.mediawiki @@ -0,0 +1,85 @@ +<pre> + BIP: 111 + Title: NODE_BLOOM service bit + Author: Matt Corallo <bip@bluematt.me>, Peter Todd <pete@petertodd.org> + Status: Draft + Type: Standards Track + Created: 2015-08-20 +</pre> + +== Abstract == + +This BIP extends BIP 37, Connection Bloom filtering, by defining a +service bit to allow peers to advertise that they support bloom filters +explicitly. It also bumps the protocol version to allow peers to +identify old nodes which allow bloom filtering of the connection despite +lacking the new service bit. + + +== Motivation == + +BIP 37 did not specify a service bit for the bloom filter service, thus +implicitly assuming that all nodes that serve peers data support it. +However, the connection filtering algorithm proposed in BIP 37, and +implemented in several clients today, has been shown to provide little +to no privacy<ref>http://eprint.iacr.org/2014/763</ref>, as well as being a large DoS risk on some nodes<ref>[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-July/003044.html] is one example where the issues were found, though others independently discovered issues as well. Sample DoS exploit code available at https://github.com/petertodd/bloom-io-attack.</ref>. +Thus, allowing node operators to disable connection bloom filtering is a +much-needed feature. + + +== Specification == + +The following protocol bit is added: + +<pre> + NODE_BLOOM = (1 << 2) +</pre> + +Nodes which support bloom filters should set that protocol bit. +Otherwise it should remain unset. In addition the protocol version is +increased from 70002 to 70011 in the reference implementation. It is +often the case that nodes which have a protocol version smaller than +70011, but larger than 70000 support bloom filtered connections without +the NODE_BLOOM bit set, however clients which require bloom filtered +connections should avoid making this assumption. + +NODE_BLOOM is distinct from NODE_NETWORK, and it is legal to advertise +NODE_BLOOM but not NODE_NETWORK (though there is little reason to do +so now, some proposals may make this more useful in the future) + +If a node does not support bloom filters but receives a "filterload", +"filteradd", or "filterclear" message from a peer the node should +disconnect that peer immediately. For backwards compatibility, in +initial implementations, nodes may choose to only disconnect nodes which +have the new protocol version set and attempt to send a filter command. + +While outside the scope of this BIP it is suggested that DNS seeds and +other peer discovery mechanisms support the ability to specify the +services required; current implementations simply check only that +NODE_NETWORK is set. + + +== Design rational == + +A service bit was chosen as applying a bloom filter is a service. + +The increase in protocol version is for backwards compatibility. In +initial implementations, old nodes which are not yet aware of NODE_BLOOM +and use a protocol version < 70011 may still send filter messages to a +node without NODE_BLOOM. This feature may be removed after there are +sufficient NODE_BLOOM nodes available and SPV clients have upgraded, +allowing node operators to fully close the bloom-related DoS vectors. + + +== Reference Implementation == + +https://github.com/bitcoin/bitcoin/pull/6579 + + +== Copyright == + +This document is placed in the public domain. + + +== References == +<references> diff --git a/bip-0112.mediawiki b/bip-0112.mediawiki new file mode 100644 index 0000000..e1a186f --- /dev/null +++ b/bip-0112.mediawiki @@ -0,0 +1,399 @@ +<pre> + BIP: 112 + Title: CHECKSEQUENCEVERIFY + Authors: BtcDrak <btcdrak@gmail.com> + Mark Friedenbach <mark@friedenbach.org> + Eric Lombrozo <elombrozo@gmail.com> + Status: Draft + Type: Standards Track + Created: 2015-08-10 +</pre> + +==Abstract== + +This BIP describes a new opcode (CHECKSEQUENCEVERIFY) for the Bitcoin +scripting system that in combination with BIP 68 allows execution +pathways of a script to be restricted based on the age of the output +being spent. + + +==Summary== + +CHECKSEQUENCEVERIFY redefines the existing NOP3 opcode. +When executed, the script interpreter continues as if a NOP was executed +so long as one of the following conditions is met: + + * the transaction's nVersion field is 0 or 1; + * the top item on the stack is a value greater than or equal to (1 << 31); or + * the top item on the stack and the transaction input's sequence number are both relative lock-times of the same units, and the relative lock-time represented by the sequence number is greater than or equal to the relative lock-time represented by the top item on the stack. + +Otherwise, script execution terminates with an error. + +BIP 68's redefinition of nSequence prevents a non-final transaction +from being selected for inclusion in a block until the corresponding +input has reached the specified age, as measured in block height or +block time. By comparing the argument to CHECKSEQUENCEVERIFY against +the nSequence field, we indirectly verify a desired minimum age of the +the output being spent; until that relative age has been reached any +script execution pathway including the CHECKSEQUENCEVERIFY will fail +to validate, causing the transaction not to be selected for inclusion +in a block. + + +==Motivation== + +BIP 68 repurposes the transaction nSequence field meaning by giving +sequence numbers new consensus-enforced semantics as a relative +lock-time. However, there is no way to build Bitcoin scripts to make +decisions based on this field. + +By making the nSequence field accessible to script, it becomes +possible to construct code pathways that only become accessible some +minimum time after proof-of-publication. This enables a wide variety +of applications in phased protocols such as escrow, payment channels, +or bidirectional pegs. + + +===Contracts With Expiration Deadlines=== + +====Escrow with Timeout==== + +An escrow that times out automatically 30 days after being funded can be +established in the following way. Alice, Bob and Escrow create a 2-of-3 +address with the following redeemscript. + + IF + 2 <Alice's pubkey> <Bob's pubkey> <Escrow's pubkey> 3 CHECKMULTISIGVERIFY + ELSE + "30d" CHECKSEQUENCEVERIFY DROP + <Alice's pubkey> CHECKSIGVERIFY + ENDIF + +At any time funds can be spent using signatures from any two of Alice, +Bob or the Escrow. + +After 30 days Alice can sign alone. + +The clock does not start ticking until the payment to the escrow address +confirms. + + +===Retroactive Invalidation=== + +In many instances, we would like to create contracts that can be revoked in case +of some future event. However, given the immutable nature of the blockchain, it +is practically impossible to retroactively invalidate a previous commitment that +has already confirmed. The only mechanism we really have for retroactive +invalidation is blockchain reorganization which, for fundamental security +reasons, is designed to be very hard and very expensive to deliberately pull off. + +Despite this limitation, we do have a way to provide something functionally similar +using CHECKSEQUENCEVERIFY. By constructing scripts with multiple branches of +execution where one or more of the branches are delayed we provide +a time window in which someone can supply an invalidation condition that allows the +output to be spent, effectively invalidating the would-be delayed branch and potentially discouraging +another party from broadcasting the transaction in the first place. If the invalidation +condition does not occur before the timeout, the delayed branch becomes spendable, +honoring the original contract. + +Some more specific applications of this idea: + +====Hash Time-Locked Contracts==== + +Hash Time-Locked Contracts (HTLCs) provide a general mechanism for offchain contract negotiation. An execution pathway can be made to require knowledge of a secret (a hash preimage) that can be presented within an invalidation time window. By sharing the secret it is possible to guarantee to the counterparty that the transaction will never be broadcast since this would allow the counterparty to claim the output immediately while one would have to wait for the time window to pass. If the secret has not been shared, the counterparty will be unable to use the instant pathway and the delayed pathway must be used instead. + +====Bidirectional Payment Channels==== + +Scriptable relative locktime provides a predictable amount of time to respond in +the event a counterparty broadcasts a revoked transaction: Absolute locktime +necessitates closing the channel and reopen it when getting close to the timeout, +whereas with relative locktime, the clock starts ticking the moment the +transactions confirms in a block. It also provides a means to know exactly how +long to wait (in number of blocks) before funds can be pulled out of the channel +in the event of a noncooperative counterparty. + + +====Lightning Network==== + +The lightning network extends the bidirectional payment channel idea to allow for payments to be routed over multiple bidirectional payment channel hops. + +These channels are based on an anchor transaction that requires a 2-of-2 +multisig from Alice and Bob, and a series of revocable commitment +transactions that spend the anchor transaction. The commitment +transaction splits the funds from the anchor between Alice and Bob and +the latest commitment transaction may be published by either party at +any time, finalising the channel. + +Ideally then, a revoked commitment transaction would never be able to +be successfully spent; and the latest commitment transaction would be +able to be spent very quickly. + +To allow a commitment transaction to be effectively revoked, Alice +and Bob have slightly different versions of the latest commitment +transaction. In Alice's version, any outputs in the commitment +transaction that pay Alice also include a forced delay, and an +alternative branch that allows Bob to spend the output if he knows that +transaction's revocation code. In Bob's version, payments to Bob are +similarly encumbered. When Alice and Bob negotiate new balances and +new commitment transactions, they also reveal the old revocation code, +thus committing to not relaying the old transaction. + +A simple output, paying to Alice might then look like: + + HASH160 <revokehash> EQUAL + IF + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + "24h" CHECKSEQUENCEVERIFY + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ENDIF + +This allows Alice to publish the latest commitment transaction at any +time and spend the funds after 24 hours, but also ensures that if Alice +relays a revoked transaction, that Bob has 24 hours to claim the funds. + +With CHECKLOCKTIMEVERIFY, this would look like: + + HASH160 <revokehash> EQUAL + IF + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + "2015/12/15" CHECKLOCKTIMEVERIFY + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ENDIF + +This form of transaction would mean that if the anchor is unspent on +2015/12/16, Alice can use this commitment even if it has been revoked, +simply by spending it immediately, giving no time for Bob to claim it. + +Ths means that the channel has a deadline that cannot be pushed +back without hitting the blockchain; and also that funds may not be +available until the deadline is hit. CHECKSEQUENCEVERIFY allows you +to avoid making such a tradeoff. + +Hashed Time-Lock Contracts (HTLCs) make this slightly more complicated, +since in principle they may pay either Alice or Bob, depending on whether +Alice discovers a secret R, or a timeout is reached, but the same principle +applies -- the branch paying Alice in Alice's commitment transaction gets a +delay, and the entire output can be claimed by the other party if the +revocation secret is known. With CHECKSEQUENCEVERIFY, a HTLC payable to +Alice might look like the following in Alice's commitment transaction: + + HASH160 DUP <revokehash> EQUAL + IF + DROP DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ELSE + <R hash> EQUAL + IF + "24h" CHECKSEQUENCEVERIFY DROP + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ENDIF + ENDIF + +and correspondingly in Bob's commitment transaction: + + HASH160 DUP <revokehash> EQUAL + IF + DROP DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + <R hash> EQUAL + IF + DUP HASH160 <Alice key hash> CHECKSIGVERIFY + ELSE + "24h" CHECKSEQUENCEVERIFY DROP + "2015/10/20 10:33" CHECKLOCKTIMEVERIFY DROP + DUP HASH160 <Bob key hash> CHECKSIGVERIFY + ENDIF + ENDIF + +Note that both CHECKSEQUENCEVERIFY and CHECKLOCKTIMEVERIFY are used in the +final branch of above to ensure Bob cannot spend the output until after both +the timeout is complete and Alice has had time to reveal the revocation +secret. + +See the [https://github.com/ElementsProject/lightning/blob/master/doc/deployable-lightning.pdf Deployable Lightning] paper. + + +====2-Way Pegged Sidechains==== + +The 2-way pegged sidechain requires a new REORGPROOFVERIFY opcode, the semantics of which are outside the scope of this BIP. CHECKSEQUENCEVERIFY is used to make sure that sufficient time has passed since the return peg was posted to publish a reorg proof: + + IF + lockTxHeight <lockTxHash> nlocktxOut [<workAmount>] reorgBounty Hash160(<...>) <genesisHash> REORGPROOFVERIFY + ELSE + withdrawLockTime CHECKSEQUENCEVERIFY DROP HASH160 p2shWithdrawDest EQUAL + ENDIF + + +==Specification== + +Refer to the reference implementation, reproduced below, for the precise +semantics and detailed rationale for those semantics. + + + /* Threshold for nSequence: below this value it is interpreted + * as a relative lock-time, otherwise ignored. */ + static const uint32_t SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31); + + /* Threshold for nSequence when interpreted as a relative + * lock-time: below this value it has units of blocks, otherwise + * seconds. */ + static const uint32_t SEQUENCE_UNITS_THRESHOLD = (1 << 30); + + case OP_NOP3: + { + if (!(flags & SCRIPT_VERIFY_CHECKSEQUENCEVERIFY)) { + // not enabled; treat as a NOP3 + if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS) { + return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS); + } + break; + } + + if (stack.size() < 1) + return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); + + // Note that elsewhere numeric opcodes are limited to + // operands in the range -2**31+1 to 2**31-1, however it is + // legal for opcodes to produce results exceeding that + // range. This limitation is implemented by CScriptNum's + // default 4-byte limit. + // + // Thus as a special case we tell CScriptNum to accept up + // to 5-byte bignums, which are good until 2**39-1, well + // beyond the 2**32-1 limit of the nSequence field itself. + const CScriptNum nSequence(stacktop(-1), fRequireMinimal, 5); + + // In the rare event that the argument may be < 0 due to + // some arithmetic being done first, you can always use + // 0 MAX CHECKSEQUENCEVERIFY. + if (nSequence < 0) + return set_error(serror, SCRIPT_ERR_NEGATIVE_LOCKTIME); + + // To provide for future soft-fork extensibility, if the + // operand is too large to be treated as a relative lock- + // time, CHECKSEQUENCEVERIFY behaves as a NOP. + if (nSequence >= SEQUENCE_LOCKTIME_THRESHOLD) + break; + + // Actually compare the specified sequence number with the input. + if (!checker.CheckSequence(nSequence)) + return set_error(serror, SCRIPT_ERR_UNSATISFIED_LOCKTIME); + + break; + } + + bool TransactionSignatureChecker::CheckSequence(const CScriptNum& nSequence) const + { + // Relative lock times are supported by comparing the passed + // in operand to the sequence number of the input. + const int64_t txToSequence = (int64_t)txTo->vin[nIn].nSequence; + + // Fail if the transaction's version number is not set high + // enough to trigger BIP 68 rules. + if (static_cast<uint32_t>(txTo->nVersion) < 2) + return false; + + // Sequence numbers above SEQUENCE_LOCKTIME_THRESHOLD + // are not consensus constrained. Testing that the transaction's + // sequence number is not above this threshold prevents + // using this property to get around a CHECKSEQUENCEVERIFY + // check. + if (txToSequence >= SEQUENCE_LOCKTIME_THRESHOLD) + return false; + + // There are two kinds of nSequence: lock-by-blockheight + // and lock-by-blocktime, distinguished by whether + // nSequence < SEQUENCE_UNITS_THRESHOLD. + // + // We want to compare apples to apples, so fail the script + // unless the type of nSequence being tested is the same as + // the nSequence in the transaction. + if (!( + (txToSequence < SEQUENCE_UNITS_THRESHOLD && nSequence < SEQUENCE_UNITS_THRESHOLD) || + (txToSequence >= SEQUENCE_UNITS_THRESHOLD && nSequence >= SEQUENCE_UNITS_THRESHOLD) + )) + return false; + + // Now that we know we're comparing apples-to-apples, the + // comparison is a simple numeric one. + if (txTo->vin[nIn].nSequence > txToSequence) + return false; + + return true; + } + + +==Reference Implementation== + +A reference implementation is provided by the following pull request: + +https://github.com/bitcoin/bitcoin/pull/6564 + + +==Deployment== + +We reuse the double-threshold switchover mechanism from BIPs 34 and +66, with the same thresholds, but for nVersion = 4. The new rules are +in effect for every block (at height H) with nVersion = 4 and at least +750 out of 1000 blocks preceding it (with heights H-1000..H-1) also +have nVersion = 4. Furthermore, when 950 out of the 1000 blocks +preceding a block do have nVersion = 4, nVersion = 3 blocks become +invalid, and all further blocks enforce the new rules. + +It is recommended that this soft-fork deployment trigger include other +related proposals for improving Bitcoin's lock-time capabilities, including: + +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: +OP_CHECKLOCKTIMEVERIFY, + +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68]: +Consensus-enforced transaction replacement signalled via sequence numbers, + +and [https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113]: +Median-Past-Time-Lock. + +==Credits== + +Mark Friedenbach invented the application of sequence numbers to +achieve relative lock-time, and wrote the reference implementation of +CHECKSEQUENCEVERIFY. + +The reference implementation and this BIP was based heavily on work +done by Peter Todd for the closely related BIP 65. + +BtcDrak authored this BIP document. + +Thanks to Eric Lombrozo and Anthony Towns for contributing example usecases. + + +==References== + +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68] Consensus-enforced transaction replacement signalled via sequence numbers + +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65] OP_CHECKLOCKTIMEVERIFY + +[https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113] Median past block time for time-lock constraints + +[http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-July/000021.html HTLCs using OP_CHECKSEQUENCEVERIFY/OP_LOCKTIMEVERIFY and revocation hashes] + +[http://lightning.network/lightning-network-paper.pdf Lightning Network] + +[https://github.com/ElementsProject/lightning/blob/master/doc/deployable-lightning.pdf Deployable Lightning] + +[http://diyhpl.us/diyhpluswiki/transcripts/sf-bitcoin-meetup/2015-02-23-scaling-bitcoin-to-billions-of-transactions-per-day/ Scaling Bitcoin to Billions of Transactions Per Day] + +[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010396.html Softfork deployment considerations] + +[https://gist.github.com/sipa/bf69659f43e763540550 Version bits] + +[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html Jeremy Spilman Micropayment Channels] + + +==Copyright== + +This document is placed in the public domain. + diff --git a/bip-0113.mediawiki b/bip-0113.mediawiki new file mode 100644 index 0000000..190fb4c --- /dev/null +++ b/bip-0113.mediawiki @@ -0,0 +1,137 @@ +<pre> + BIP: 113 + Title: Median time-past as endpoint for lock-time calculations + Author: Thomas Kerin <me@thomaskerin.io> + Mark Friedenbach <mark@friedenbach.org> + Status: Draft + Type: Standards Track + Created: 2015-08-10 +</pre> + + +==Abstract== + +This BIP is a proposal to redefine the semantics used in determining a +time-locked transaction's eligibility for inclusion in a block. The +median of the last 11 blocks is used instead of the block's timestamp, +ensuring that it increases monotonically with each block. + + +==Motivation== + +At present, transactions are excluded from inclusion in a block if the +present time or block height is less than or equal to that specified +in the locktime. Since the consensus rules do not mandate strict +ordering of block timestamps, this has the unfortunate outcome of +creating a perverse incentive for miners to lie about the time of +their blocks in order to collect more fees by including transactions +that by wall clock determination have not yet matured. + +This BIP proposes comparing the locktime against the median of the +past 11 block's timestamps, rather than the timestamp of the block +including the transaction. Existing consensus rules guarantee this +value to monotonically advance, thereby removing the capability for +miners to claim more transaction fees by lying about the timestamps of +their block. + +This proposal seeks to ensure reliable behaviour in locktime calculations as +required by BIP65 (CHECKLOCKTIMEVERIFY), BIP68 (sequence numbers), and BIP112 (CHECKSEQUENCEVERIFY). + + +==Specification== + +The values for transaction locktime remain unchanged. The difference is only in +the calculation determining whether a transaction can be included. Instead of +an unreliable timestamp, the following function is used to determine the current +block time for the purpose of checking lock-time constraints: + + enum { nMedianTimeSpan=11 }; + + int64_t GetMedianTimePast(const CBlockIndex* pindex) + { + int64_t pmedian[nMedianTimeSpan]; + int64_t* pbegin = &pmedian[nMedianTimeSpan]; + int64_t* pend = &pmedian[nMedianTimeSpan]; + for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) + *(--pbegin) = pindex->GetBlockTime(); + std::sort(pbegin, pend); + return pbegin[(pend - pbegin)/2]; + } + +Lock-time constraints are checked by the consensus method IsFinalTx(), +or LockTime() under BIP68. These methods take the block time as one +parameter. This BIP proposes that after activation calls to +IsFinalTx() or LockTime() within consensus code use the return value +of `GetMedianTimePast(pindexPrev)` instead. + +A reference implementation of this proposal is provided by the +following pull request: + +https://github.com/bitcoin/bitcoin/pull/6566 + + +==Deployment== + +We reuse the double-threshold switchover mechanism from BIPs 34 and +66, with the same thresholds, but for nVersion = 8. The new rules are +in effect for every block (at height H) with nVersion = 8 and at least +750 out of 1000 blocks preceding it (with heights H-1000..H-1) also +have nVersion = 8. Furthermore, when 950 out of the 1000 blocks +preceding a block do have nVersion = 8, nVersion = 3 blocks become +invalid, and all further blocks enforce the new rules. + +When assessing the block version as mask of ~0x20000007 must be applied +to work around the complications caused by +[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010396.html BIP101's premature use] +of the [https://gist.github.com/sipa/bf69659f43e763540550 undecided version bits proposal]. + +By applying ~0x20000007 with nVersion = 8, the thresholds should be tested +comparing block nVersion >= 4 as this will save a bit for future use. + +It is recommended that this soft-fork deployment trigger include other related +proposals for improving Bitcoin's lock-time capabilities, including: + +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: +CHECKLOCKTIMEVERIFY, + +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP 68]: +Consensus-enforced transaction replacement signalled via sequence numbers, + +and [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: +CHECKSEQUENCEVERIFY. + + +==Acknowledgements== + +Mark Friedenbach for designing and authoring the reference +implementation of this BIP. + +Thanks go to Gregory Maxwell who came up with the original idea, +in #bitcoin-wizards on 2013-07-16. + +Thomas Kerin authored this BIP document. + + +==Compatibility== + +Transactions generated using time-based lock-time will take +approximately an hour longer to confirm than would be expected under +the old rules. This is not known to introduce any compatibility +concerns with existing protocols. + + +==References== +[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP65: OP_CHECKLOCKTIMEVERIFY] + +[https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP68: Consensus-enforced transaction replacement signaled via sequence numbers] + +[https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP112: CHECKSEQUENCEVERIFY] + +[http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-August/010396.html Softfork deployment considerations] + +[https://gist.github.com/sipa/bf69659f43e763540550 Version bits] + + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-0120.mediawiki b/bip-0120.mediawiki new file mode 100644 index 0000000..1602c65 --- /dev/null +++ b/bip-0120.mediawiki @@ -0,0 +1,152 @@ +<pre> + BIP: 120 + Title: Proof of Payment + Author: Kalle Rosenbaum <kalle@rosenbaum.se> + Status: Draft + Type: Standards Track + Created: 2015-07-28 +</pre> + +== Abstract == + +This BIP describes a system called Proof of Payment, PoP. It is used to prove that a wallet has the credentials that were used to sign a previously generated transaction. Or simply put, it lets you prove that you have made a payment. + +== Motivation == + +There are several scenarios in which it would be useful to prove that you have paid for something. For example: + +* A pre-paid hotel room where your PoP functions as a key to the door. +* An online video rental service where you pay for a video and watch it on any device. +* An ad-sign where you pay in advance for e.g. 2 weeks exclusivity. During this period you can upload new content to the sign whenever you like using PoP. +* Log in to a pay site using a PoP. +* A parking lot you pay for monthly and the car authenticates itself using PoP. +* A lottery where all participants pay to the same address, and the winner is selected among the transactions to that address. You exchange the prize for a PoP for the winning transaction. + +With Proof of Payment, these use cases can be achieved without any personal information (user name, password, e-mail address, etc) being involved. + +== Rationale == + +Desirable properties: + +# A PoP should be generated on demand. +# It should only be usable once to avoid issues due to theft. +# It should be able to create a PoP for any payment, regardless of script type (P2SH, P2PKH, etc.). +# It should prove that you have enough credentials to unlock all the inputs of the proven transaction. +# It should be easy to implement by wallets and servers to ease adoption. + +Current methods of proving a payment: + +* In BIP0070, the PaymentRequest together with the transactions fulfilling the request makes some sort of proof. However, it does not meet 1, 2 or 4 and it obviously only meets 3 if the payment is made through BIP0070. Also, there's no standard way to request/provide the proof. If standardized it would probably meet 5. +* Signing messages, chosen by the server, with the private keys used to sign the transaction. This could meet 1 and 2 but probably not 3. This is not standardized either. 4 Could be met if designed so. + +If an input script type is P2SH, any satisfying script should do, just as if it was a payment. For M-of-N multisig scripts, that would mean that any set of M keys should be sufficient, not necessarily the same set of M keys that signed the transaction. This is important because strictly demanding the same set of M keys would defeat the purpose of a multisig address. + +== Specification == + +=== Data structure === + +A proof of payment for a transaction T, here called PoP(T), is used to prove that one has ownership of the credentials needed to unlock all the inputs of T. It has the exact same structure as a bitcoin transaction with the same inputs as T and in the same order as in T, but with each sequence number set to 0. There is exactly one output, here called the pop output, with value 0. The pop output must have the following format: + + OP_RETURN <version> <txid> <nonce> + +{| +! Field !! Size [B] !! Description +|- +| <version> || 2 || Version, little endian, currently 0x01 0x00 +|- +| <txid> || 32 || The transaction to prove +|- +| <nonce> || 6 || Random data +|} + +The lock_time of the PoP must be set to 499999999 to prevent the PoP from being included in a block, should it appear on the bitcoin p2p network. This is also the reason for setting the sequence numbers to 0, since sequence number of ffffffff would make lock_time ineffective. This specification demands that all input sequence numbers are 0, not just one of them, which would be sufficient to make lock_time effective. This is for simplicity reasons. + +An illustration of the PoP data structure and its original payment is shown below. + +<pre> + T + +------------------------------------------------+ + |inputs | outputs | + | Value,Sequence | Value,Script | + +------------------------------------------------+ + |input0 1,ffffffff | 0,pay to A | + |input1 3,ffffffff | 2,OP_RETURN <some data> | + |input2 4,ffffffff | 1,pay to B | + | | 4,pay to C | + +------------------------------------------------+ + + PoP(T) + +-------------------------------------------------------------+ + | inputs | outputs | + | Value,Sequence | Value,Script | + +-------------------------------------------------------------+ + |input0 1,00000000 | 0,OP_RETURN <version> <txid> <nonce> | + |input1 3,00000000 | | + |input2 4,00000000 | | + +-------------------------------------------------------------+ + | lock_time=499999999 | + +-------------------------------------------------------------+ +</pre> + +The PoP is signed using the same signing process that is used for bitcoin transactions. + +The purpose of the nonce is to make it harder to use a stolen PoP; Once the PoP has reached the server, that PoP is useless since the server will generate a new nonce for every PoP request. + +=== Process === + +# A proof of payment request is sent from the server to the wallet. The PoP request contains: +## a random nonce +## a destination where to send the PoP, for example a https URL +## data hinting the wallet which transaction to create a proof for. For example: +##* txid, if known by the server +##* PaymentRequest.PaymentDetails.merchant_data (in case of a BIP0070 payment) +##* amount, label, message or other information from a BIP0021 URI +# The wallet identifies a transaction T, if possible. Otherwise it asks the user to select among the ones that match the hints in 1.iii. +# The wallet creates an unsigned PoP (UPoP) for T, and asks the user to sign it. +# The user confirms +# The UPoP(T) is signed by the wallet, creating PoP(T). +# The PoP is sent to the destination in 1.ii. +# The server receiving the PoP validates it and responds with “valid” or “invalid”. +# The wallet displays the response in some way to the user. + +'''Remarks:''' + +* The method of transferring the PoP request at step 1 is not specified here. Instead that is specified in separate specifications, see BIP0121. +* The nonce must be randomly generated by the server for every new PoP request. + +=== Validating a PoP === + +The server needs to validate the PoP and reply with "valid" or "invalid". That process is outlined below. If any step fails, the validation is aborted and "invalid" is returned: + +# Check the format of the PoP. It must pass normal transaction checks, except that the inputs may already be spent. +# Check that lock_time is 499999999. +# Check that there is exactly one output. This output must have value 0 and conform to the OP_RETURN output format outlined above. +# Check that the nonce is the same as the one requested. +# Check that the inputs of the PoP are exactly the same as in transaction T, except that the sequence numbers must all be 0. The ordering of the inputs must also be the same as in T. +# Run the scripts of all the inputs. All scripts must return true. +# Check that the txid in the PoP output is the transaction you actually want proof for. If you don’t know exactly what transaction you want proof for, check that the transaction actually pays for the product/service you deliver. +# Return "valid". + +== Security considerations == + +* Someone can intercept the PoP-request and change any parameter in it. These can be mitigated by using secure connections. Examples of tampered parameters: +** Pop destination - Stealing your PoP. +** label - Trick you to sign an unintended pop or set a label that your wallet doesn't have any record for, resulting in a broken service. Always check the PoP before signing. +** nonce - Your pop will not validate on server. +* Someone can steal a PoP, for example by tampering with the PoP request, and try to use the service hoping to get a matching nonce. Probability per try: 1/(2^48). The server should have a mechanism for detecting a brute force attack of this kind, or at least slow down the process by delaying the PoP request by some 100 ms or so. +* Even if a wallet has no funds it might still be valuable as a generator for PoPs. This makes it important to keep the security of the wallet after it has been emptied. +* Transaction malleability may cause the server to have a different transaction id for a payment than the client's wallet. In that case the wallet will not be able to prove the transaction to the server. Wallets should not rely on the transaction id of the outgoing transaction. Instead it should listen for the transaction on the network and put that in its list of transactions. + +== Reference implementation == + +[https://github.com/kallerosenbaum/poppoc PoP Demo server on GitHub] + +[https://github.com/kallerosenbaum/wallet PoP-enabled Mycelium fork on GitHub] + +== References == + +[https://github.com/bitcoin/bips/blob/master/bip-0021.mediawiki BIP0021]: URI Scheme + +[https://github.com/bitcoin/bips/blob/master/bip-0070.mediawiki BIP0070]: Payment Protocol + +[https://github.com/bitcoin/bips/blob/master/bip-0121.mediawiki BIP0121]: Proof of Payment URI scheme diff --git a/bip-0121.mediawiki b/bip-0121.mediawiki new file mode 100644 index 0000000..716f3c9 --- /dev/null +++ b/bip-0121.mediawiki @@ -0,0 +1,145 @@ +<pre> + BIP: 121 + Title: Proof of Payment URI scheme + Author: Kalle Rosenbaum <kalle@rosenbaum.se> + Status: Draft + Type: Standards Track + Created: 2015-07-27 +</pre> + +== Abstract == + +This is a proposal for a URI scheme to be used in the Proof of Payment +process. + +== Motivation == + +To make a Proof of Payment, the party that wants the proof needs to +transfer a Proof of Payment request to the wallet software of the +other party. To facilitate that transfer, a new URI scheme +representing the PoP request is proposed. This URI can then be encoded +in QR images or be sent over NFC in order to transfer it to the wallet. + +== Specification == + +The specification is the same as BIP0021, with the following +differences: + +* The URI scheme is <tt>btcpop</tt> instead of <tt>bitcoin</tt> +* The path component, i.e. the address part, is always empty. +* A mandatory <tt>p</tt> parameter whose value contains the destination for the PoP. This could for example be a <tt>https:</tt> URL or a <tt>mailto:</tt> URI. +* A mandatory <tt>n</tt> parameter representing the nonce, base58 encoded. +* An optional <tt>txid</tt> parameter containing the Base58 encoded hash of the transaction to prove. + +Just as in BIP0021, elements of the query component may contain +characters outside the valid range. These must first be encoded +according to UTF-8, and then each octet of the corresponding UTF-8 +sequence must be percent-encoded as described in RFC 3986. + +All parameters except <tt>p</tt> and <tt>n</tt> are hints to the +wallet on which transaction to create a PoP for. + +The extensibility of BIP0021 applies to this scheme as well. For +example, a <tt>date</tt> parameter or a <tt>toaddr</tt> parameter +might be useful. <tt>req-*</tt> parameters are also allowed and obey +the same rules as in BIP0021, clients not supporting a <tt>req-*</tt> +parameter must consider the URI invalid. + +=== Keep URIs short === + +Implementations should keep the URIs as short as possible. This is +because it makes QR decoding more stable. A camera with a scratched +lens or low resolution may run into problems scanning huge QR +codes. This is why the <tt>txid</tt> parameter is encoded in Base58 +instead of the classic hex encoded string. We get away with 44 +characters instead of 64. Also, the <tt>nonce</tt> parameter is Base58 +encoded for the same reason. + +== Interpretation == + +=== Transaction hints === + +The wallet processing the URI must use the hints in the PoP request to +filter its transaction set. The <tt>label</tt>, <tt>amount</tt> and +<tt>message</tt> parameters must, if present in the URI, exactly match +the data associated with the original payment according to the +following table: + +{| +| <tt>btcpop:</tt> URI parameter || <tt>bitcoin:</tt> URI parameter || BIP70 PaymentDetails data +|- +| <tt>label</tt> || <tt>label</tt> || <tt>merchant_data</tt> +|- +| <tt>amount</tt> || <tt>amount</tt> || <tt>sum of outputs.amount</tt> +|- +| <tt>message</tt> || <tt>message</tt> || <tt>memo</tt> +|} + +The <tt>txid</tt> parameter value must match the transaction hash of +the payment. + +After filtering, the resulting transaction set is displayed to the +user who selects one of them to prove. An implementation could also +automatically select a transaction in the filtered set, but +there must still be a way for the user to select freely among the +matching transactions. If the filtered set is empty, no transaction +fits the hints and a message about that is presented to the user. If +the filtered set contains exactly one transaction, which is +preferable, that transaction can be automatically selected. + +As a fallback, there must also be a way for the user to select any +transaction from the wallet regardless of the transaction hints. This +can be useful if the metadata of the wallet is lost, possibly due to a +restore from backup. + +=== PoP destination <tt>p</tt> === + +The <tt>p</tt> parameter value is the destination where to send the +PoP to. This destination is typically a <tt>https:</tt> URL or a +<tt>http:</tt> URL, but it could be any type of URI, for example +<tt>mailto:</tt>. To keep <tt>btcpop:</tt> URIs short, users should +not make their <tt>p</tt> parameter unnecessarily long. + +==== <tt>http:</tt> and <tt>https:</tt> URLs ==== + +Wallet implementations must support the <tt>http:</tt> and +<tt>https:</tt> schemes in which case <tt>POST</tt> method must be +used. The content type of the POST request must be set to + + application/bitcoin-pop + +== Examples == + +Send PoP for a transaction with label "video 42923" to +<nowiki>https://www.example.com/pop/352</nowiki>, using nonce +<tt>0x73 0xd5 0x1a 0xbb 0xd8 0x9c</tt>: +<pre> + btcpop:?p=https://www.example.com/pop/352&n=zgWTm8yH&label=video%2042923 +</pre> +Send PoP through mail using +<nowiki>mailto:pop@example.com?subject=pop444</nowiki>, amount +is 13370000 satoshis, nonce is <tt>0x6f 0xe 0xfb 0x68 0x92 0xf9</tt>. +Note that the <tt>?</tt> before <tt>subject</tt> is OK according to RFC3986, +since the query part starts from the first <tt>?</tt>: +<pre> + btcpop:?p=mailto:pop@example.com?subject%3Dpop444&n=xJdKmEbr&amount=0.1337 +</pre> +Send PoP for transaction with id +<tt>cca7507897abc89628f450e8b1e0c6fca4ec3f7b34cccf55f3f531c659ff4d79</tt> +to pizza place at <nowiki>http://pizza.example.com/pop/laszlo111</nowiki> using nonce <tt>0xfc 0xcc 0x2c 0x35 0xf0 0xb8</tt> +<pre> + btcpop:?p=http://pizza.example.com/pop/laszlo111&n=3AtNpVrPh&txid=Emt9MPvt1joznqHy5eEHkNtcuQuYWXzYJBQZN6BJm6NL +</pre> +== Reference implementation == + +[https://github.com/kallerosenbaum/poppoc PoP Demo server on GitHub] + +[https://github.com/kallerosenbaum/wallet PoP-enabled Mycelium fork on GitHub] + +== References == + +[https://github.com/bitcoin/bips/blob/master/bip-0021.mediawiki BIP0021]: URI Scheme + +[https://github.com/bitcoin/bips/blob/master/bip-0120.mediawiki BIP0120]: Proof of Payment + +[https://www.ietf.org/rfc/rfc3986.txt RFC3986]: Uniform Resource Identifier (URI): Generic Syntax |
