diff options
48 files changed, 1627 insertions, 436 deletions
diff --git a/README.mediawiki b/README.mediawiki index b270383..ca28339 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -27,13 +27,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Luke Dashjr | Process | Active -|- style="background-color: #ffcfcf" +|- | [[bip-0008.mediawiki|8]] | | Version bits with lock-in by height -| Shaolin Fry +| Shaolin Fry, Luke Dashjr | Informational -| Rejected +| Draft |- style="background-color: #cfffcf" | [[bip-0009.mediawiki|9]] | @@ -160,13 +160,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Pieter Wuille | Informational | Final -|- +|- style="background-color: #ffcfcf" | [[bip-0033.mediawiki|33]] | Peer Services | Stratized Nodes | Amir Taaki | Standard -| Draft +| Rejected |- style="background-color: #cfffcf" | [[bip-0034.mediawiki|34]] | Consensus (soft fork) @@ -181,13 +181,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Jeff Garzik | Standard | Final -|- +|- style="background-color: #ffcfcf" | [[bip-0036.mediawiki|36]] | Peer Services | Custom Services | Stefan Thomas | Standard -| Draft +| Rejected |- style="background-color: #cfffcf" | [[bip-0037.mediawiki|37]] | Peer Services @@ -230,13 +230,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Pieter Wuille | Standard | Final -|- +|- style="background-color: #cfffcf" | [[bip-0043.mediawiki|43]] | Applications | Purpose Field for Deterministic Wallets | Marek Palatinus, Pavol Rusnak | Informational -| Draft +| Final |- style="background-color: #ffffcf" | [[bip-0044.mediawiki|44]] | Applications @@ -301,13 +301,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Peter Todd | Standard | BIP number allocated -|- +|- style="background-color: #ffcfcf" | [[bip-0064.mediawiki|64]] | Peer Services | getutxo message | Mike Hearn | Standard -| Draft +| Obsolete |- style="background-color: #cfffcf" | [[bip-0065.mediawiki|65]] | Consensus (soft fork) @@ -385,6 +385,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Justin Newton, Matt David, Aaron Voisine, James MacWhyte | Standard | Final +|- +| [[bip-0078.mediawiki|78]] +| Applications +| A Simple Payjoin Proposal +| Nicolas Dorier +| Standard +| Draft |- style="background-color: #ffffcf" | [[bip-0079.mediawiki|79]] | Applications @@ -406,13 +413,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Justus Ranvier, Jimmy Song | Informational | Deferred -|- +|- style="background-color: #ffcfcf" | [[bip-0083.mediawiki|83]] | Applications | Dynamic Hierarchical Deterministic Key Trees | Eric Lombrozo | Standard -| Draft +| Rejected |- | [[bip-0084.mediawiki|84]] | Applications @@ -421,12 +428,19 @@ Those proposing changes should consider that ultimately consent may rest with th | Informational | Draft |- +| [[bip-0085.mediawiki|85]] +| Applications +| Deterministic Entropy From BIP32 Keychains +| Ethan Kosakovsky +| Informational +| Draft +|- style="background-color: #cfffcf" | [[bip-0090.mediawiki|90]] | | Buried Deployments | Suhas Daftuar | Informational -| Draft +| Final |- style="background-color: #cfffcf" | [[bip-0091.mediawiki|91]] | Consensus (soft fork) @@ -441,13 +455,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Mark Friedenbach, Kalle Alm, BtcDrak | Standard | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0099.mediawiki|99]] | | Motivation and deployment of consensus rule changes ([soft/hard]forks) | Jorge Timón | Informational -| Draft +| Rejected |- style="background-color: #ffcfcf" | [[bip-0100.mediawiki|100]] | Consensus (hard fork) @@ -476,34 +490,34 @@ Those proposing changes should consider that ultimately consent may rest with th | Pieter Wuille | Standard | Withdrawn -|- +|- style="background-color: #ffcfcf" | [[bip-0104.mediawiki|104]] | Consensus (hard fork) | 'Block75' - Max block size like difficulty | t.khan | Standard -| Draft -|- +| Rejected +|- style="background-color: #ffcfcf" | [[bip-0105.mediawiki|105]] | Consensus (hard fork) | Consensus based block size retargeting algorithm | BtcDrak | Standard -| Draft -|- +| Rejected +|- style="background-color: #ffcfcf" | [[bip-0106.mediawiki|106]] | Consensus (hard fork) | Dynamically Controlled Bitcoin Block Size Max Cap | Upal Chakraborty | Standard -| Draft -|- +| Rejected +|- style="background-color: #ffcfcf" | [[bip-0107.mediawiki|107]] | Consensus (hard fork) | Dynamic limit on the block size | Washington Y. Sanchez | Standard -| Draft +| Rejected |- style="background-color: #ffcfcf" | [[bip-0109.mediawiki|109]] | Consensus (hard fork) @@ -539,13 +553,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Johnson Lau | Standard | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0115.mediawiki|115]] | Consensus (soft fork) | Generic anti-replay protection using Script | Luke Dashjr | Standard -| Draft +| Rejected |- | [[bip-0116.mediawiki|116]] | Consensus (soft fork) @@ -637,13 +651,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Suhas Daftuar | Standard | Proposed -|- +|- style="background-color: #ffcfcf" | [[bip-0131.mediawiki|131]] | Consensus (hard fork) | "Coalescing Transaction" Specification (wildcard inputs) | Chris Priest | Standard -| Draft +| Rejected |- style="background-color: #ffcfcf" | [[bip-0132.mediawiki|132]] | @@ -658,13 +672,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Alex Morcos | Standard | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0134.mediawiki|134]] | Consensus (hard fork) | Flexible Transactions | Tom Zander | Standard -| Draft +| Rejected |- | [[bip-0135.mediawiki|135]] | @@ -686,13 +700,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Christopher Gilliard | Standard | Final -|- +|- style="background-color: #ffcfcf" | [[bip-0140.mediawiki|140]] | Consensus (soft fork) | Normalized TXID | Christian Decker | Standard -| Draft +| Rejected |- style="background-color: #cfffcf" | [[bip-0141.mediawiki|141]] | Consensus (soft fork) @@ -728,13 +742,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Luke Dashjr | Standard | Final -|- +|- style="background-color: #ffcfcf" | [[bip-0146.mediawiki|146]] | Consensus (soft fork) | Dealing with signature encoding malleability | Johnson Lau, Pieter Wuille | Standard -| Draft +| Withdrawn |- style="background-color: #cfffcf" | [[bip-0147.mediawiki|147]] | Consensus (soft fork) @@ -770,13 +784,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Jonas Schnelli | Standard | Withdrawn -|- +|- style="background-color: #cfffcf" | [[bip-0152.mediawiki|152]] | Peer Services | Compact Block Relay | Matt Corallo | Standard -| Draft +| Final |- style="background-color: #ffcfcf" | [[bip-0154.mediawiki|154]] | Peer Services @@ -791,13 +805,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Wladimir J. van der Laan | Standard | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0156.mediawiki|156]] | Peer Services | Dandelion - Privacy Enhancing Routing | Brad Denby, Andrew Miller, Giulia Fanti, Surya Bakshi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath | Standard -| Draft +| Rejected |- | [[bip-0157.mediawiki|157]] | Peer Services @@ -819,13 +833,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Jonas Schnelli | Standard | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0171.mediawiki|171]] | Applications | Currency/exchange rate information API | Luke Dashjr | Standard -| Draft +| Rejected |- style="background-color: #cfffcf" | [[bip-0173.mediawiki|173]] | Applications @@ -868,13 +882,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Emil Engler, MarcoFalke, Luke Dashjr | Informational | Draft -|- +|- style="background-color: #ffcfcf" | [[bip-0180.mediawiki|180]] | Peer Services | Block size/weight fraud proof | Luke Dashjr | Standard -| Draft +| Rejected |- | [[bip-0197.mediawiki|197]] | Applications @@ -939,6 +953,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0339.mediawiki|339]] +| Peer Services +| WTXID-based transaction relay +| Suhas Daftuar +| Standard +| Draft +|- | [[bip-0340.mediawiki|340]] | | Schnorr Signatures for secp256k1 diff --git a/bip-0001.mediawiki b/bip-0001.mediawiki index b1947ea..7067f64 100644 --- a/bip-0001.mediawiki +++ b/bip-0001.mediawiki @@ -6,7 +6,7 @@ Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0001 Status: Replaced Type: Process - Created: 2011-08-19 + Created: 2011-09-19 Superseded-By: 2 </pre> diff --git a/bip-0008.mediawiki b/bip-0008.mediawiki index f09f8a7..6fa8cea 100644 --- a/bip-0008.mediawiki +++ b/bip-0008.mediawiki @@ -2,9 +2,10 @@ BIP: 8 Title: Version bits with lock-in by height Author: Shaolin Fry <shaolinfry@protonmail.ch> + Luke Dashjr <luke+bip@dashjr.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0008 - Status: Rejected + Status: Draft Type: Informational Created: 2017-02-01 License: BSD-3-Clause @@ -13,7 +14,9 @@ ==Abstract== -This document specifies an alteration to [[bip-0009.mediawiki|BIP9]] that replaces time based activation with block height, as well as guaranteed activation of backward-compatible changes (further called "soft forks"). +This document specifies an alternative to [[bip-0009.mediawiki|BIP9]] that corrects for a number of perceived mistakes. +Block heights are used for start and timeout rather than POSIX timestamps. +It additionally introduces an additional activation parameter to guarantee activation of backward-compatible changes (further called "soft forks"). 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. @@ -21,24 +24,21 @@ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "S BIP9 introduced a mechanism for doing parallel soft forking deployments based on repurposing the block nVersion field. Activation is dependent on near unanimous hashrate signalling which may be impractical and result in veto by a small minority of non-signalling hashrate. Super majority hashrate based activation triggers allow for accelerated activation where the majority hash power enforces the new rules in lieu of full nodes upgrading. Since all consensus rules are ultimately enforced by full nodes, eventually any new soft fork will be enforced by the economy. This proposal combines these two aspects to provide eventual flag day activation after a reasonable time (recommended a year), as well as for accelerated activation by majority of hash rate before the flag date. +Due to using timestamps rather than block heights, it was found to be a risk that a sudden loss of significant hashrate could interfere with a late activation. + Block time is somewhat unreliable and may be intentionally or unintentionally inaccurate, so thresholds based on block time are not ideal. Secondly, BIP9 specified triggers based on the first retarget after a given time, which is non-intuitive. Since each new block must increase the height by one, thresholds based on block height are much more reliable and intuitive and can be calculated exactly for difficulty retarget. ==Specification== -===Summary=== - -This specification is the same as [[bip-0009.mediawiki|BIP9]] except that MTP time based threshold are replaced with block height, and the state machine has no FAILED condition. The state transition from '''STARTED''' to '''LOCKED_IN''' will occur under two condition: - -The first is when the threshold of blocks signalling is reached as per BIP9, before '''LOCKED_IN''' state has been reached. The second condition is when the block height reaches the timeout block height while still being in the '''STARTED''' state. - ===Parameters=== Each soft fork deployment is specified by the following per-chain parameters (further elaborated below): # The '''name''' specifies a very brief description of the soft fork, reasonable for use as an identifier. For deployments described in a single BIP, it is recommended to use the name "bipN" where N is the appropriate BIP number. # The '''bit''' determines which bit in the nVersion field of the block is to be used to signal the soft fork lock-in and activation. It is chosen from the set {0,1,2,...,28}. -# The '''startheight''' specifies a minimum block height at which a block at which the bit gains its meaning. -# The '''timeoutheight''' specifies a block height at which the deployment should lock-in if not already locked in or activated. +# The '''startheight''' specifies the height of the first block at which the bit gains its meaning. +# The '''timeoutheight''' specifies a block height at which the miner signalling ends. Once this height has been reached, if the soft fork has not yet locked in (excluding this block's bit state), the deployment is either considered failed on all descendants of the block (but see the exception during '''FAILING''' state), or, if '''lockinontimeout'' is true, transitions to the '''LOCKED_IN''' state. +# The '''lockinontimeout''' boolean if set to true, will transition state to '''LOCKED_IN''' at timeoutheight if not already '''LOCKED_IN''' or '''ACTIVE'''. ===Selection guidelines=== @@ -46,30 +46,40 @@ The following guidelines are suggested for selecting these parameters for a soft # '''name''' should be selected such that no two softforks, concurrent or otherwise, ever use the same name. # '''bit''' should be selected such that no two concurrent softforks use the same bit. -# '''startheight''' should be set to some block height in the future, approximately 30 days (or 4320 blocks) after a software release date including the soft fork. This allows for some release delays, while preventing triggers as a result of parties running pre-release software. The startheight should be a retarget block height for simplicity. +# '''startheight''' should be set to some block height in the future, approximately 30 days (or 4320 blocks) after a software release date including the soft fork. This allows for some release delays, while preventing triggers as a result of parties running pre-release software, and ensures a reasonable number of full nodes have upgraded prior to activation. It should be rounded up to the next height which begins a retarget period for simplicity. # '''timeoutheight''' should be 1 year, or 52416 blocks (26 retarget intervals) after '''startheight'''. +# '''lockinontimeout''' should be set to true for any softfork that is expected or found to have political opposition from a non-negligible percent of miners. (It can be set after the initial deployment, but cannot be cleared once set.) -A later deployment using the same bit is possible as long as the startheight is after the previous one's timeoutheight or activation, but it is discouraged until necessary, and even then recommended to have a pause in between to detect buggy software. +A later deployment using the same bit is possible as long as the startheight is after the previous one's +timeoutheight or activation, but it is discouraged until necessary, and even then recommended to have a pause in between to detect buggy software. ===States=== With each block and soft fork, we associate a deployment state. The possible states are: # '''DEFINED''' is the first state that each soft fork starts out as. The genesis block is by definition in this state for each deployment. -# '''STARTED''' for blocks past the startheight. -# '''LOCKED_IN''' for one retarget period after the first retarget period with STARTED blocks of which at least threshold have the associated bit set in nVersion. +# '''STARTED''' for blocks at or beyond the startheight. +# '''LOCKED_IN''' for one retarget period after the first retarget period with STARTED blocks of which at least threshold have the associated bit set in nVersion, or for one retarget period after the timeout when '''lockinontimeout''' is true. # '''ACTIVE''' for all blocks after the LOCKED_IN retarget period. -# '''FAILED''' if block height is greater than or equal to timeoutheight during the DEFINED state. +# '''FAILING''' for one retarget period after the timeout, if LOCKED_IN was not reached and '''lockinontimeout''' is false. +# '''FAILED''' for all blocks after the FAILING retarget period. ===Bit flags=== The nVersion block header field is to be interpreted as a 32-bit little-endian integer (as present), and bits are selected within this integer as values (1 << N) where N is the bit number. -Blocks in the STARTED state get an nVersion whose bit position bit is set to 1. The top 3 bits of such blocks must be 001, so the range of actually possible nVersion values is [0x20000000...0x3FFFFFFF], inclusive. +Blocks in the STARTED state get an nVersion whose bit position bit is set to 1. The top 3 bits of such blocks must be +001, so the range of actually possible nVersion values is [0x20000000...0x3FFFFFFF], inclusive. -Due to the constraints set by BIP 34, BIP 66 and BIP 65, we only have 0x7FFFFFFB possible nVersion values available. This restricts us to at most 30 independent deployments. By restricting the top 3 bits to 001 we get 29 out of those for the purposes of this proposal, and support two future upgrades for different mechanisms (top bits 010 and 011). When a block nVersion does not have top bits 001, it is treated as if all bits are 0 for the purposes of deployments. +Due to the constraints set by BIP 34, BIP 66 and BIP 65, we only have 0x7FFFFFFB possible nVersion values available. +This restricts us to at most 30 independent deployments. By restricting the top 3 bits to 001 we get 29 out of those +for the purposes of this proposal, and support two future upgrades for different mechanisms (top bits 010 and 011). +When a block nVersion does not have top bits 001, it is treated as if all +bits are 0 for the purposes of deployments. -Miners should continue setting the bit in LOCKED_IN phase so uptake is visible, though this has no effect on consensus rules. +Miners must continue setting the bit in LOCKED_IN phase so uptake is visible and acknowledged. +Blocks without the applicable bit set are invalid during this period. +For flexibility, this rule does NOT require the top 3 bits to be set any particular way. ===New consensus rules=== @@ -79,6 +89,8 @@ The new consensus rules for each soft fork are enforced for each block that has <img src="bip-0008/states.png" align="middle"></img> +During the STARTED state if the '''lockinontimeout''' is set to true, the state will transition to LOCKED_IN when '''timeoutheight''' is reached. + The genesis block has state DEFINED for each deployment, by definition. State GetStateForBlock(block) { @@ -86,7 +98,9 @@ The genesis block has state DEFINED for each deployment, by definition. return DEFINED; } -All blocks within a retarget period have the same state. This means that if floor(block1.height / 2016) = floor(block2.height / 2016), they are guaranteed to have the same state for every deployment. +All blocks within a retarget period have the same state. This means that if +floor(block1.height / 2016) = floor(block2.height / 2016), they are guaranteed to have the same state for every +deployment. if ((block.height % 2016) != 0) { return GetStateForBlock(block.parent); @@ -94,32 +108,24 @@ All blocks within a retarget period have the same state. This means that if floo Otherwise, the next state depends on the previous state: - switch (GetStateForBlock(GetAncestorAtHeight(block, block.height - 2016))) { + switch (GetStateForBlock(GetAncestorAtHeight(block, block.height - 2016))) { -We remain in the initial state until either we pass the start block height or the timeout height. +We remain in the initial state until we reach the start block height. case DEFINED: - if (block.height >= timeoutheight) { - return FAILED; - } if (block.height >= startheight) { return STARTED; } return DEFINED; -After a period in the STARTED state, if we're past the timeout, we switch to LOCKED_IN. If not, we tally the bits set, +After a period in the STARTED state, we tally the bits set, and transition to LOCKED_IN if a sufficient number of blocks in the past period set the deployment bit in their version numbers. The threshold is ≥1916 blocks (95% of 2016), or ≥1512 for testnet (75% of 2016). - -There could be two non-overlapping deployments on the same bit, where the first one transitions to LOCKED_IN while the -other one simultaneously transitions to STARTED, which would mean both would demand setting the bit. +If the threshold hasn't been met, and we reach the timeout, then we either transition to LOCKED_IN state anyway (if lockinontimeout is true), or we transition to FAILING. Note that a block's state never depends on its own nVersion; only on that of its ancestors. case STARTED: - if (block.height >= timeoutheight) - return LOCKED_IN; - int count = 0; walk = block; for (i = 0; i < 2016; i++) { @@ -130,24 +136,47 @@ Note that a block's state never depends on its own nVersion; only on that of its } if (count >= threshold) { return LOCKED_IN; + } else if (block.height >= timeoutheight) { + return (lockinontimeout == true) ? LOCKED_IN : FAILING; } return STARTED; +If the deployment is not LOCKED_IN by the timeout (or '''lockinontimeout'''), it has a single retarget period during which it may still become active, only by unanimous signalling in every block. +This state exists such that if '''lockinontimeout''' is set to true later, it remains compatible with the original deployment. + + case FAILING: + walk = block; + for (i = 0; i < 2016; i++) { + walk = walk.parent; + if (walk.nVersion & 0xE0000000 == 0x20000000 && ((walk.nVersion >> bit) & 1) != 1) { + return FAILED; + } + } + return ACTIVE; + After a retarget period of LOCKED_IN, we automatically transition to ACTIVE. case LOCKED_IN: return ACTIVE; -And ACTIVE is terminal a state, which a deployment stays in once reached. +And ACTIVE and FAILED are terminal states, which a deployment stays in once they're reached. case ACTIVE: return ACTIVE; + + case FAILED: + return FAILED; + } } '''Implementation''' -It should be noted that the states are maintained along block chain branches, but may need recomputation when a reorganization happens. +It should be noted that the states are maintained along block chain +branches, but may need recomputation when a reorganization happens. -Given that the state for a specific block/deployment combination is completely determined by its ancestry before the current retarget period (i.e. up to and including its ancestor with height block.height - 1 - (block.height % 2016)), it is possible to implement the mechanism above efficiently and safely by caching the resulting state of every multiple-of-2016 block, indexed by its parent. +Given that the state for a specific block/deployment combination is completely determined by its ancestry before the +current retarget period (i.e. up to and including its ancestor with height block.height - 1 - (block.height % 2016)), +it is possible to implement the mechanism above efficiently and safely by caching the resulting state of every multiple-of-2016 +block, indexed by its parent. ===Warning mechanism=== @@ -182,6 +211,7 @@ The template Object is also extended: The "version" key of the template is retained, and used to indicate the server's preference of deployments. If versionbits is being used, "version" MUST be within the versionbits range of [0x20000000...0x3FFFFFFF]. Miners MAY clear or set bits in the block version WITHOUT any special "mutable" key, provided they are listed among the template's "vbavailable" and (when clearing is desired) NOT included as a bit in "vbrequired". +Servers MUST set bits in "vbrequired" for deployments in LOCKED_IN state, to ensure blocks produced are valid. Softfork deployment names listed in "rules" or as keys in "vbavailable" may be prefixed by a '!' character. Without this prefix, GBT clients may assume the rule will not impact usage of the template as-is; typical examples of this would be when previously valid transactions cease to be valid, such as BIPs 16, 65, 66, 68, 112, and 113. @@ -191,11 +221,17 @@ A client that does not understand a rule prefixed by '!' must not attempt to pro === Reference implementation === -https://github.com/bitcoin/bitcoin/compare/master...shaolinfry:bip8-height +https://github.com/bitcoin/bitcoin/compare/master...luke-jr:bip8 + +==Contrasted with BIP 9== + +* The '''lockinontimeout''' flag is added. BIP 9 would only transition to the FAILED state when timeout was reached. +* Block heights are used for the deployment monotonic clock, rather than median-time-past. +* The last-ditch effort during a new FAILING state is added to allow '''lockinontimeout''' to be safely set after the initial deployment. ==Backwards compatibility== -BIP8 and BIP9 deployments should not share concurrent active deployment bits. Nodes that only implement BIP9 will not activate a BIP8 soft fork if hashpower threshold is not reached by '''timeout''', however, those nodes will still accept the blocks generated by activated nodes. +BIP8 and BIP9 deployments should not share concurrent active deployment bits. Nodes that only implement BIP9 will not activate a BIP8 soft fork if hashpower threshold is not reached by '''timeoutheight''', however, those nodes will still accept the blocks generated by activated nodes. ==Deployments== diff --git a/bip-0008/states.png b/bip-0008/states.png Binary files differindex 13fae23..76f6cb7 100644 --- a/bip-0008/states.png +++ b/bip-0008/states.png diff --git a/bip-0008/states.svg b/bip-0008/states.svg new file mode 100644 index 0000000..f2e4b34 --- /dev/null +++ b/bip-0008/states.svg @@ -0,0 +1,55 @@ +<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 848 464" width="905" height="495"> + <defs> + <style type="text/css"><![CDATA[ + rect { + fill: white; + stroke: black; + stroke-width: 1; + } + text { + fill: black; + } + svg>path { + stroke: black; + stroke-width: 2; + fill: none; + marker-end: url(#arrow); + } + ]]></style> + <marker id="arrow" markerWidth="13" markerHeight="13" refX="8" refY="6" orient="auto"> + <path d="M0,2 L0,11 L8,6 L0,2" style="fill: black;" /> + </marker> + </defs> + + <rect x="112" y="48" width="128" height="32"/> + <text x="176" y="72" font-size="20" text-anchor="middle">DEFINED</text> + <path d="M 128 80 a 24 32 0 1 1 0 -32"/><!-- loop --> + <path d="M 176 80 l 0 96"/> + <text x="182" y="128" font-size="12" text-anchor="start">startheight <= height</text> + <rect x="112" y="176" width="128" height="32"/> + <text x="176" y="200" font-size="20" text-anchor="middle">STARTED</text> + <path d="M 128 208 a 24 32 0 1 1 0 -32"/><!-- loop --> + <path d="M 176 208 l 0 96"/> + <text x="182" y="232" font-size="12" text-anchor="start">(lockinontimeout == false) AND (height < timeoutheight) AND (threshold reached)</text> + <text x="304" y="256" font-size="12" text-anchor="start">OR</text> + <text x="182" y="280" font-size="12" text-anchor="start">(lockinontimeout == true) AND ((height >= timeoutheight) OR (threshold reached))</text> + <rect x="112" y="304" width="128" height="32"/> + <text x="176" y="328" font-size="20" text-anchor="middle">LOCKED_IN</text> + <path d="M 176 336 l 0 48"/> + <text x="182" y="360" font-size="12" text-anchor="start">Always</text> + <rect x="112" y="384" width="128" height="32"/> + <text x="176" y="408" font-size="20" text-anchor="middle">ACTIVE</text> + <path d="M 128 416 a 24 32 0 1 1 0 -32"/><!-- loop --> + + <rect x="640" y="176" width="128" height="32"/> + <text x="704" y="200" font-size="20" text-anchor="middle">FAILING</text> + <path d="M 240 192 l 400 0"/> + <text x="408" y="184" font-size="12" text-anchor="middle">(lockinontimeout == false) AND (timeoutheight <= height)</text> + <path d="M 704 208 l 0 176"/> + <text x="720" y="296" font-size="12" text-anchor="start">NOT all blocks signal</text> + <path d="M 656 208 c 0 196 -416 176 -416 176"/> + <text x="544" y="352" font-size="12" text-anchor="start">all blocks signal</text> + <rect x="640" y="384" width="128" height="32"/> + <text x="704" y="408" font-size="20" text-anchor="middle">FAILED</text> + <path d="M 756 416 a 24 32 0 1 0 0 -32"/><!-- loop --> +</svg> diff --git a/bip-0011.mediawiki b/bip-0011.mediawiki index e5052eb..8375f55 100644 --- a/bip-0011.mediawiki +++ b/bip-0011.mediawiki @@ -23,7 +23,7 @@ A couple of motivating use cases: * A wallet secured by a "wallet protection service" (WPS). 2-of-2 signatures required transactions will be used, with one signature coming from the (possibly compromised) computer with the wallet and the second signature coming from the WPS. When sending protected bitcoins, the user's bitcoin client will contact the WPS with the proposed transaction and it can then contact the user for confirmation that they initiated the transaction and that the transaction details are correct. Details for how clients and WPS's communicate are outside the scope of this BIP. Side note: customers should insist that their wallet protection service provide them with copies of the private key(s) used to secure their wallets that they can safely store off-line, so that their coins can be spent even if the WPS goes out of business. -* Three-party escrow (buyer, seller and trusted dispute agent). 2-of-3 signatures required transactions will be used. The buyer and seller and agent will each provide a public key, and the buyer will then send coins into a 2-of-3 CHECKMULTISIG transaction and send the seller and the agent the transaction id. The seller will fulfill their obligation and then ask the buyer to co-sign a transaction ( already signed by seller ) that sends the tied-up coins to him (seller).<br />If the buyer and seller cannot agree, then the agent can, with the cooperation of either buyer or seller, decide what happens to the tied-up coins. Details of how buyer, seller, and agent communicate to gather signatures or public keys are outside the scope of this BIP. +* Three-party escrow (buyer, seller, and trusted dispute agent). 2-of-3 signatures required transactions will be used. The buyer and seller and agent will each provide a public key, and the buyer will then send coins into a 2-of-3 CHECKMULTISIG transaction and send the seller and the agent the transaction id. The seller will fulfill their obligation and then ask the buyer to co-sign a transaction ( already signed by seller ) that sends the tied-up coins to him (seller).<br />If the buyer and seller cannot agree, then the agent can, with the cooperation of either buyer or seller, decide what happens to the tied-up coins. Details of how buyer, seller, and agent communicate to gather signatures or public keys are outside the scope of this BIP. ==Specification== diff --git a/bip-0032.mediawiki b/bip-0032.mediawiki index 9339307..f2f1e48 100644 --- a/bip-0032.mediawiki +++ b/bip-0032.mediawiki @@ -272,31 +272,6 @@ Seed (hex): 4b381541583be4423346c643850da4b320e46a87ae3d2a4e6da11eba819cd4acba45 ** ext pub: xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y ** ext prv: xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L -==Implementations== - -Two Python implementations exist: - -PyCoin (https://github.com/richardkiss/pycoin) is a suite of utilities for dealing with Bitcoin that includes BIP0032 wallet features. BIP32Utils (https://pypi.org/project/bip32utils/) is a library and command line interface specifically focused on BIP0032 wallets and scripting. - -2 Java implementations exist: https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java and https://github.com/bushidowallet/bushido-java-core/tree/master/src/main/java/com/bushidowallet/core/bitcoin/bip32 - -A C++ implementation is available at https://github.com/ciphrex/mSIGNA/blob/master/deps/CoinCore/src/hdkeys.h - -An Objective-C implementation is available at https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCKeychain.h - -A Ruby implementation is available at https://github.com/GemHQ/money-tree - -Two Go implementations exist: - -hdkeychain (https://github.com/conformal/btcutil/tree/master/hdkeychain) provides an API for bitcoin hierarchical deterministic extended keys (BIP0032). Go HD Wallet (https://github.com/WeMeetAgain/go-hdwallet). - -Two JavaScript implementations exist: available at https://github.com/sarchar/brainwallet.github.com/tree/bip32 and https://github.com/bitpay/bitcore - -A PHP implementation is available at https://github.com/Bit-Wasp/bitcoin-lib-php - -A C# implementation is available at https://github.com/MetacoSA/NBitcoin (ExtKey, ExtPubKey) - -A Haskell implementation is available at https://github.com/haskoin/haskoin together with a CLI interface at https://github.com/np/hx ==Acknowledgements== diff --git a/bip-0033.mediawiki b/bip-0033.mediawiki index d95357d..2c1a86f 100644 --- a/bip-0033.mediawiki +++ b/bip-0033.mediawiki @@ -5,7 +5,7 @@ Author: Amir Taaki <genjix@riseup.net> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0033 - Status: Draft + Status: Rejected Type: Standards Track Created: 2012-05-15 </pre> diff --git a/bip-0036.mediawiki b/bip-0036.mediawiki index d3e36f4..b3393b0 100644 --- a/bip-0036.mediawiki +++ b/bip-0036.mediawiki @@ -5,7 +5,7 @@ Author: Stefan Thomas <justmoon@members.fsf.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0036 - Status: Draft + Status: Rejected Type: Standards Track Created: 2012-08-03 License: PD diff --git a/bip-0039.mediawiki b/bip-0039.mediawiki index cd0115c..2b95c51 100644 --- a/bip-0039.mediawiki +++ b/bip-0039.mediawiki @@ -156,15 +156,19 @@ JavaScript: * https://github.com/bitpay/bitcore-mnemonic * https://github.com/bitcoinjs/bip39 (used by [[https://github.com/blockchain/My-Wallet-V3/blob/v3.8.0/src/hd-wallet.js#L121-L146|blockchain.info]]) +Java: +* https://github.com/bitcoinj/bitcoinj/blob/master/core/src/main/java/org/bitcoinj/crypto/MnemonicCode.java + Ruby: * https://github.com/sreekanthgs/bip_mnemonic Rust: -* https://github.com/infincia/bip39-rs +* https://github.com/maciejhirsz/tiny-bip39/ Swift: * https://github.com/CikeQiu/CKMnemonic * https://github.com/yuzushioh/WalletKit +* https://github.com/matter-labs/web3swift/blob/develop/Sources/web3swift/KeystoreManager/BIP39.swift C++: * https://github.com/libbitcoin/libbitcoin-system/blob/master/include/bitcoin/system/wallet/mnemonic.hpp diff --git a/bip-0043.mediawiki b/bip-0043.mediawiki index 85578d8..67b799d 100644 --- a/bip-0043.mediawiki +++ b/bip-0043.mediawiki @@ -6,7 +6,7 @@ Pavol Rusnak <stick@satoshilabs.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0043 - Status: Draft + Status: Final Type: Informational Created: 2014-04-24 </pre> diff --git a/bip-0064.mediawiki b/bip-0064.mediawiki index 22e56ba..82a6cfd 100644 --- a/bip-0064.mediawiki +++ b/bip-0064.mediawiki @@ -5,7 +5,7 @@ Author: Mike Hearn <hearn@vinumeris.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0064 - Status: Draft + Status: Obsolete Type: Standards Track Created: 2014-06-10 </pre> diff --git a/bip-0067.mediawiki b/bip-0067.mediawiki index 9baf6c0..b164289 100644 --- a/bip-0067.mediawiki +++ b/bip-0067.mediawiki @@ -46,7 +46,7 @@ Sort them lexicographically according to their binary representation: ..before using the resulting list of keys in a standard multisig redeem script: - OP_2 021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18 022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da 03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9 OP_3 OP_CHECKSIG + OP_2 021f2f6e1e50cb6a953935c3601284925decd3fd21bc445712576873fb8c6ebc18 022df8750480ad5b26950b25c7ba79d3e37d75f640f8e5d9bcd5b150a0f85014da 03e3818b65bcc73a7d64064106a859cc1a5a728c4345ff0b641209fba0d90de6e9 OP_3 OP_CHECKMULTISIG Hash the redeem script according to BIP-0016 to get the P2SH address. diff --git a/bip-0078.mediawiki b/bip-0078.mediawiki new file mode 100644 index 0000000..c795343 --- /dev/null +++ b/bip-0078.mediawiki @@ -0,0 +1,675 @@ +<pre> + BIP: 78 + Layer: Applications + Title: A Simple Payjoin Proposal + Author: Nicolas Dorier <nicolas.dorier@gmail.com> + Replaces: 79 + Comments-Summary: No comments yet. + Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0078 + Status: Draft + Type: Standards Track + Created: 2019-05-01 + License: BSD-2-Clause +</pre> + +==Introduction== + +===Abstract=== + +This document proposes a protocol for two parties +to negotiate a coinjoin transaction during a payment between them. + +===Copyright=== + +This BIP is licensed under the 2-clause BSD license. + +===Motivation=== + +When two parties (later referred to as sender and receiver) want to transact, +most of the time, the sender creates a transaction spending their own Unspent Transaction Outputs (UTXOs), signs +it and broadcasts it on the network. + +This simple model gave birth to several heuristics impacting the privacy of the parties and of the network as a whole. + +* Common input ownership heuristic: In most transactions, all the inputs belong to the same party. +* Change identification from scriptPubKey type: If all inputs are spending UTXOs of a certain scriptPubKey type, then the change output is likely to have the same scriptPubKey type, too. +* Change identification from round amount: If an output in the transaction has a round amount, it is likely an output belonging to the receiver. + +We will designate these three heuristics as <code>common-input</code>, <code>change-scriptpubkey</code>, <code>change-round-amount</code>. + +The problems we aim to solve are: +* For the receiver, there is a missed opportunity to consolidate their own UTXOs or making payment in the sender's transaction. +* For the sender, there are privacy leaks regarding their wallet that happen when someone applies the heuristics detailed above to their transaction. + +Our proposal gives an opportunity for the receiver to consolidate their UTXOs while also batching their own payments, without creating a new transaction. (Saving fees in the process) +For the sender, it allows them to invalidate the three heuristics above. With the receiver's involvement, the heuristics can even be poisoned. (ie, using the heuristics to intentionally mislead blockchain analysis) + +Note that the existence of this proposal is also improving the privacy of parties who are not using it by making the three heuristics unreliable to the network as a whole. + +=== Relation to BIP79 (Bustapay) === + +Another implementation proposal has been written: [[https://github.com/bitcoin/bips/blob/master/bip-0079.mediawiki|BIP79 Bustapay]]. + +We decided to deviate from it for several reasons: +* It was not using PSBT, so if the receiver wanted to bump the fee, they would need the full UTXO set. +* Inability to change the payment output to match scriptPubKey type. +* Lack of basic versioning negotiation if the protocol evolves. +* No standardization of error condition for proper feedback to the sender. + +Other than that, our proposal is very similar. + +==Specification== + +===Protocol=== + +In a payjoin payment, the following steps happen: + +* The receiver of the payment, presents a [[bip-0021.mediawiki|BIP 21 URI]] to the sender with a parameter <code>pj=</code> describing a payjoin endpoint. +* The sender creates a signed, finalized PSBT with witness UTXO or previous transactions of the inputs. We call this PSBT the <code>original</code>. +* The receiver replies back with a signed PSBT containing his own signed inputs/outputs and those of the sender. We call this PSBT <code>Payjoin proposal</code>. +* The sender verifies the proposal, re-signs his inputs and broadcasts the transaction to the Bitcoin network. We call this transaction <code>Payjoin transaction</code>. +<pre> ++----------+ +--------+ +-----------------+ +| Receiver | | Sender | | Bitcoin Network | ++----+-----+ +---+----+ +-------+---------+ + | +-----------------+ | | + +-------+ BIP21 with ?pj= +------->+ | + | +-----------------+ | | + | | | + | +---------------+ | | + +<-------+ Original PSBT +---------+ | + | +---------------+ | | + | | | + | +------------------+ | | + | | Payjoin Proposal | | | + +-------+ PSBT +------>+ | + | +------------------+ | | + | | +--------------+ | + | |---+ Payjoin | | + | | | transaction +-->+ + | | +--------------+ | + + + + +</pre> +The original PSBT is sent in the HTTP POST request body, base64 serialized, with <code>text/plain</code> in the <code>Content-Type</code> HTTP header and <code>Content-Length</code> set correctly. +The payjoin proposal PSBT is sent in the HTTP response body, base64 serialized with HTTP code 200. + +To ensure compatibility with web-wallets and browser-based-tools, all responses (including errors) must contain the HTTP header <code>Access-Control-Allow-Origin: *</code>. + +The sender must ensure that the url refers to a scheme or protocol using authenticated encryption, for example TLS with certificate validation, or a .onion link to a hidden service whose public key identifier has already been communicated via a TLS connection. Senders SHOULD NOT accept a url representing an unencrypted or unauthenticated connection. + +The original PSBT MUST: +* Have all the <code>witnessUTXO</code> or <code>nonWitnessUTXO</code> information filled in. +* Be finalized. +* Not include fields unneeded for the receiver such as global xpubs or keypath information. +* Be broadcastable. + +The original PSBT MAY: +* Have outputs unrelated to the payment for batching purpose. + +The payjoin proposal MUST: +* Use all the inputs from the original PSBT. +* Use all the outputs which do not belongs to the receiver from the original PSBT. +* Only finalize the inputs added by the receiver. (Referred later as <code>additional inputs</code>) +* Only fill the <code>witnessUTXO</code> or <code>nonWitnessUTXO</code> for the additional inputs. + +The payjoin proposal MAY: +* Add, remove or modify the outputs belonging to the receiver. + +The payjoin proposal MUST NOT: +* Shuffle the order of inputs or outputs, the additional outputs or additional inputs must be inserted at a random index. +* Decrease the absolute fee of the original transaction. + +===BIP21 payjoin parameters=== + +This proposal is defining the following new [[bip-0021.mediawiki|BIP 21 URI]] parameters: +* <code>pj=</code>: Represents an http(s) endpoint which the sender can POST the original PSBT. +* <code>pjos=0</code>: Signal to the sender that they MUST disallow [[#output-substitution|payment output substitution]]. (See [[#unsecured-payjoin|Unsecured payjoin server]]) + +===<span id="optional-params"></span>Optional parameters=== + +When the payjoin sender posts the original PSBT to the receiver, he can optionally specify the following HTTP query string parameters: + +* <code>v=</code>, the version number of the payjoin protocol that the sender is using. The current version is <code>1</code>. + +This can be used in the future so the receiver can reject a payjoin if the sender is using a version which is not supported via an error HTTP 400, <code>version-unsupported</code>. +If not specified, the receiver will assume the sender is <code>v=1</code>. + +If the receiver does not support the version of the sender, they should send an error with the list of supported versions: +<pre> +{ + "errorCode": "version-unsupported", + "supported" : [ 2, 3, 4 ], + "message": "The version is not supported anymore" +} +</pre> + +* <code>additionalfeeoutputindex=</code>, if the sender is willing to pay for increased fee, this indicate output can have its value substracted to pay for it. + +If the <code>additionalfeeoutputindex</code> is out of bounds or pointing to the payment output meant for the receiver, the receiver should ignore the parameter. See [[#fee-output|fee output]] for more information. + +* <code>maxadditionalfeecontribution=</code>, if the sender is willing to pay for increased fee, an integer defining the maximum amount in satoshis that the sender is willing to contribute towards fees for the additional inputs. <code>maxadditionalfeecontribution</code> must be ignored if set to less than zero. See [[#fee-output|fee output]] for more information. + +Note that both <code>maxadditionalfeecontribution=</code> and <code>additionalfeeoutputindex=</code> must be specified and valid for the receiver to be allowed to decrease an output belonging to the sender. +This fee contribution can't be used to pay for anything else than additional input's weight. + +* <code>minfeerate=</code>, a decimal in satoshi per vbyte that the sender can use to constraint the receiver to not drop the minimum fee rate too much. + +* <code>disableoutputsubstitution=</code>, a boolean indicating if the sender forbids the receiver to substitute the receiver's output, see [[#output-substitution|payment output substitution]]. (default to <code>false</code>) + +===Receiver's well known errors=== + +If for some reason the receiver is unable to create a payjoin proposal, it will reply with a HTTP code different than 200. +The receiver is not constrained to specific set of errors, some are specified in this proposal. + +The errors have the following format: +<pre> +{ + "errorCode": "leaking-data", + "message": "Key path information or GlobalXPubs should not be included in the original PSBT." +} +</pre> + +The well-known error codes are: +{| class="wikitable" +!Error code +!Meaning +|- +|unavailable +|The payjoin endpoint is not available for now. +|- +|not-enough-money +|The receiver added some inputs but could not bump the fee of the payjoin proposal. +|- +|version-unsupported +|This version of payjoin is not supported. +|- +|original-psbt-rejected +|The receiver rejected the original PSBT. +|} + +The receiver is allowed to return implementation specific errors which may assist the sender to diagnose any issue. + +However, it is important that error codes that are not well-known and that the message do not appear on the sender's software user interface. +Such error codes or messages could be used maliciously to phish a non technical user. +Instead those errors or messages can only appear in debug logs. + +It is advised to hard code the description of the well known error codes into the sender's software. + +===<span id="fee-output"></span>Fee output=== + +In some situation, the sender might want to pay some additional fee in the payjoin proposal. +If such is the case, the sender must use both [[#optional-params|optional parameters]] <code>additionalfeeoutputindex=</code> and <code>maxadditionalfeecontribution=</code> to indicate which output and how much the receiver can substract fee. + +There is several cases where a fee output is useful: + +* The sender's original transaction's fee rate is at the minimum accepted by the network, aka <code>minimum relay transaction fee rate</code>, which is typically 1 satoshi per vbyte. + +In such case, the receiver will need to increase the fee of the transaction after adding his own inputs to not drop below the minimum relay transaction fee rate. + +* The sender's wallet software is using round fee rate. + +If the sender's fee rate is always round, then a blockchain analyst can easily spot the transactions of the sender involving payjoin by checking if, when removing a single input to the suspected payjoin transaction, the resulting fee rate is round. +To prevent this, the sender can agree to pay more more fee so the receiver make sure that the payjoin transaction fee is also round. + +* The sender's transaction is time sensitive. + +When a sender pick a specific fee rate, the sender expects the transaction to be confirmed after a specific amount of time. But if the receiver adds an input without bumping the fee of the transaction, the payjoin transaction fee rate will be lower, and thus, longer to confirm. + +Our recommendation for <code>maxadditionalfeecontribution=</code> is <code>originalPSBTFeeRate * vsize(sender_input_type)</code>. + +{| class="wikitable" +!sender_input_type +!vsize(sender_input_type) +|- +|P2WPKH +|68 +|- +|P2PKH +|148 +|- +|P2SH-P2WPKH +|91 +|} + + + +===Receiver's original PSBT checklist=== + +The receiver needs to do some check on the original PSBT before proceeding: + +* Non-interactive receivers (like a payment processor) need to check that the original PSBT is broadcastable. <code>*</code> +* If the sender included inputs in the original PSBT owned by the receiver, the receiver must either return error <code>original-psbt-rejected</code> or make sure they do not sign those inputs in the payjoin proposal. +* If the sender's inputs are all from the same scriptPubKey type, the receiver must match the same type. If the receiver can't match the type, they must return error <code>unavailable</code>. +* Make sure that the inputs included in the original transaction have never been seen before. +** This prevent [[#probing-attack|probing attacks]]. +** This prevent reentrant payjoin, where a sender attempts to use payjoin transaction as a new original transaction for a new payjoin. + +<code>*</code>: Interactive receivers are not required to validate the original PSBT because they are not exposed to [[#probing-attack|probing attacks]]. + +===Sender's payjoin proposal checklist=== + +The sender should check the payjoin proposal before signing it to prevent a malicious receiver from stealing money. + +* Verify that the absolute fee of the payjoin proposal is equals or higher than the original PSBT. +* If the receiver's BIP21 signalled <code>pjos=0</code>, disable payment output substitution. +* Verify that the transaction version, and the nLockTime are unchanged. +* Check that the sender's inputs' sequence numbers are unchanged. +* For each inputs in the proposal: +** Verify that no keypaths is in the PSBT input +** Verify that no partial signature has been filled +** If it is one of the sender's input +*** Verify that input's sequence is unchanged. +*** Verify the PSBT input is not finalized +*** Verify that <code>non_witness_utxo</code> and <code>witness_utxo</code> are not specified. +** If it is one of the receiver's input +*** Verify the PSBT input is finalized +*** Verify that <code>non_witness_utxo</code> or <code>witness_utxo</code> are filled in. +** Verify that the payjoin proposal did not introduced mixed input's sequence. +** Verify that the payjoin proposal did not introduced mixed input's type. +** Verify that all of sender's inputs from the original PSBT are in the proposal. +* For each outputs in the proposal: +** Verify that no keypaths is in the PSBT output +** If the output is the [[#fee-output|fee output]]: +*** The amount that was substracted from the output's value is less than or equal to <code>maxadditionalfeecontribution</code>. Let's call this amount <code>actual contribution</code>. +*** Make sure the actual contribution is only paying fee: The <code>actual contribution</code> is less than or equals to the difference of absolute fee between the payjoin proposal and the original PSBT. +*** Make sure the actual contribution is only paying for fee incurred by additional inputs: <code>actual contribution</code> is less than or equals to <code>originalPSBTFeeRate * vsize(sender_input_type) * (count(original_psbt_inputs) - count(payjoin_proposal_inputs))</code>. (see [[#fee-output|Fee output]] section) +** If the output is the payment output and payment output substitution is allowed. +*** Do not make any check +** Else +*** Make sure the output's value did not decrease. +** Verify that all sender's outputs (ie, all outputs except the output actually paid to the receiver) from the original PSBT are in the proposal. +* Once the proposal is signed, if <code>minfeerate</code> was specified, check that the fee rate of the payjoin transaction is not less than this value. + +The sender must be careful to only sign the inputs that were present in the original PSBT and nothing else. + +Note: +* The sender must allow the receiver to add/remove or modify the receiver's own outputs. (if payment output substitution is disabled, the receiver's outputs must not be removed or decreased in value) +* The sender should allow the receiver to not add any inputs. This is useful for the receiver to change the paymout output scriptPubKey type. +* If no input have been added, the sender's wallet implementation should accept the payjoin proposal, but not mark the transaction as an actual payjoin in the user interface. + +Our method of checking the fee allows the receiver and the sender to batch payments in the payjoin transaction. +It also allows the receiver to pay the fee for batching adding his own outputs. + +==Rationale== + +There is several consequences of our proposal: + +* The receiver can bump the fee of the original transaction. +* The receiver can modify the outputs of the original PSBT. +* The sender must provide the UTXO information (Witness or previous transaction) in the PSBT. + +===Respecting the minimum relay fee policy=== + +To be properly relayed, a Bitcoin transaction needs to pay at least 1 satoshi per virtual byte. +When blocks are not full, the original transaction might already at the minimum relay fee rate (currently 1 satoshi per virtual byte), so if the receiver adds their own input, they need to make sure the fee is increased such that the rate does not drop below the minimum relay fee rate. +In such case, the sender must set both <code>maxadditionalfeecontribution=</code> and <code>additionalfeeoutputindex=</code>. + +See the [[#fee-output|Fee output]] section for more information. + +We also recommend the sender to set <code>minfeerate=</code>, as the sender's node policy might be different from the receiver's policy. + +===Defeating heuristics based on the fee calculation=== + +Most wallets are creating a round fee rate (like 2 sat/b). +If the payjoin transaction's fee was not increased by the added size, then those payjoin transactions could easily be identifiable on the blockchain. + +Not only would those transactions stand out by not having a round fee (like 1.87 sat/b), but any suspicion of payjoin could be confirmed by checking if removing one input would create a round fee rate. +In such case, the sender must set both <code>maxadditionalfeecontribution=</code> and <code>additionalfeeoutputindex=</code>. + +The recommended value <code>maxadditionalfeecontribution=</code> is explained in the [[#fee-output|Fee output]] section. +We also recommend the sender to set <code>minfeerate=</code>, as the sender's node policy might be different from the receiver's policy. + +===Receiver does not need to be a full node=== + +Because the receiver needs to bump the fee to keep the same fee rate as the original PSBT, it needs the input's UTXO information to know what is the original fee rate. Without PSBT, light wallets like Wasabi Wallet would not be able to receive a payjoin transaction. + +The validation (policy and consensus) of the original transaction is optional: a receiver without a full node can decide to create the payjoin transaction and automatically broadcast the original transaction after a timeout of 1 minute, and only verify that it has been propagated in the network. + +However, non-interactive receivers (like a payment processor) need to verify the transaction to prevent UTXO probing attacks. + +This is not a concern for interactive receivers like Wasabi Wallet, because those receivers can just limit the number of original PSBT proposals of a specific address to one. With such wallets, the attacker has no way to generate new deposit addresses to probe the UTXOs. + +===<span id="spare-change"></span>Spare change donation=== + +Small change inside wallets are detrimental to privacy. Mixers like Wasabi wallet, because of its protocol, eventually generate such [[https://docs.wasabiwallet.io/using-wasabi/ChangeCoins.html#first-round-coinjoin-change|small change]]. + +A common way to protect your privacy is to donate those spare changes, to deposit them in an exchange or on your favorite merchant's store account. Those kind of transactions can easily be spotted on the blockchain: There is only one output. + +However, if you donate via payjoin, it will look like a normal transaction. + +On top of this the receiver can poison analysis by randomly faking a round amount of satoshi for the additional output. + +===<span id="output-substitution"></span>Payment output substitution=== + +Unless disallowed by sender explicitely via `disableoutputsubstitution=true` or by the BIP21 url via query parameter the `pjos=0`, the receiver is free to decrease the amount, remove, or change the scriptPubKey output paying to himself. +Note that if payment output substitution is disallowed, the reveiver can still increase the amount of the output. (See [[#reference-impl|the reference implementation]]) + +For example, if the sender's scriptPubKey type is P2WPKH while the receiver's payment output in the original PSBT is P2SH, then the receiver can substitute the payment output to be P2WPKH to match the sender's scriptPubKey type. + +===<span id="unsecured-payjoin"></span>Unsecured payjoin server=== + +A receiver might run the payment server (generating the BIP21 invoice) on a different server than the payjoin server, which could be less trusted than the payment server. + +In such case, the payment server can signal to the sender, via the BIP21 parameter <code>pjos=0</code>, that they MUST disallow [[#output-substitution|payment output substitution]]. +A compromised payjoin server could steal the hot wallet outputs of the receiver, but would not be able to re-route payment to himself. + +===Impacted heuristics=== + +Our proposal of payjoin is breaking the following blockchain heuristics: + +* Common inputs heuristics. + +Because payjoin is mixing the inputs of the sender and receiver, this heuristic becomes unreliable. + +* Change identification from scriptPubKey type heuristics + +When Alice pays Bob, if Alice is using P2SH but Bob's deposit address is P2WPKH, the heuristic would assume that the P2SH output is the change address of Alice. +This is now however a broken assumption, as the payjoin receiver has the freedom to mislead analytics by purposefully changing the invoice's address in the payjoin transaction. + +See [[#output-substitution|payment output substitution]]. + +* Change identification from round change amount + +If Alice pays Bob, she might be tempted to pay him a round amount, like <code>1.23000000 BTC</code>. When this happens, blockchain analysis often identifies the output without the round amount as the change of the transaction. + +For this reason, during a [[#spare-change|spare change]] case, the receiver may add an output with a rounded amount randomly. + +==Attack vectors== + +===<span id="probing-attack"></span>On the receiver side: UTXO probing attack=== + +When the receiver creates a payjoin proposal, they expose one or more inputs belonging to them. + +An attacker could create multiple original transactions in order to learn the UTXOs of the receiver, while not broadcasting the payjoin proposal. + +While we cannot prevent this type of attack entirely, we implemented the following mitigations: + +* When the receiver detects an original transaction being broadcast, or if the receiver detects that the original transaction has been double spent, then they will reuse the UTXO that was exposed for the next payjoin. +* While the exposed UTXO will be reused in priority to not leak other UTXOs, there is no strong guarantee about it. This prevents the attacker from detecting with certainty the next payjoin of the merchant to another peer. + +Note that probing attacks are only a problem for automated payment systems such as BTCPay Server. End-user wallets with payjoin capabilities are not affected, as the attacker can't create multiple invoices to force the receiver to expose their UTXOs. + +===On the sender side: Double payment risk for hardware wallets=== + +For a successful payjoin to happen, the sender needs to sign two transactions double spending each other: The original transaction and the payjoin proposal. + +The sender's software wallet can verify that the payjoin proposal is legitimate by the sender's checklist. + +However, a hardware wallet can't verify that this is indeed the case. This means that the security guarantee of the hardware wallet is decreased. If the sender's software is compromised, the hardware wallet would sign two valid transactions, thus sending two payments. + +Without payjoin, the maximum amount of money that could be lost by a compromised software is equal to one payment (via [[#output-substitution|payment output substitution]]). +Note that the sender can disallow [[#output-substitution|payment output substitution]] by using the optional parameter <code>disableoutputsubstitution=true</code>. + +With payjoin, the maximum amount of money that can be lost is equal to two payments. + +==<span id="reference-impl"></span>Reference sender's implementation== + +Here is pseudo code of a sender implementation. +<code>RequestPayjoin</code> takes the bip21 URI of the payment, the wallet and the <code>signedPSBT</code>. + +The <code>signedPSBT</code> represents a PSBT which has been fully signed, but not yet finalized. +We then prepare <code>originalPSBT</code> from the <code>signedPSBT</code> via the <code>CreateOriginalPSBT</code> function and get back the <code>proposal</code>. + +While we verify the <code>proposal</code>, we also import into it informations about our own inputs and outputs from the <code>signedPSBT</code>. +At the end of this <code>RequestPayjoin</code>, the proposal is verified and ready to be signed. + +We logged the different PSBT involved, and show the result in our [[#test-vectors|test vectors]]. +<pre> +public async Task<PSBT> RequestPayjoin( + BIP21Uri bip21, + Wallet wallet, + PSBT signedPSBT, + PayjoinClientParameters optionalParameters) +{ + Log("Unfinalized signed PSBT" + signedPSBT); + // Extracting the pj link. + var endpoint = bip21.ExtractPayjointEndpoint(); + if (signedPSBT.IsAllFinalized()) + throw new InvalidOperationException("The original PSBT should not be finalized."); + ScriptPubKeyType inputScriptType = wallet.ScriptPubKeyType(); + PSBTOutput feePSBTOutput = null; + + bool allowOutputSubstitution = !optionalParameters.DisableOutputSubstitution; + if (bip21.Parameters.Contains("pjos") && bip21.Parameters["pjos"] == "0") + allowOutputSubstitution = false; + + if (optionalParameters.AdditionalFeeOutputIndex != null && optionalParameters.MaxAdditionalFeeContribution != null) + feePSBTOutput = signedPSBT.Outputs[optionalParameters.AdditionalFeeOutputIndex]; + Script paymentScriptPubKey = bip21.Address == null ? null : bip21.Address.ScriptPubKey; + decimal originalFee = signedPSBT.GetFee(); + PSBT originalPSBT = CreateOriginalPSBT(signedPSBT); + Transaction originalGlobalTx = signedPSBT.GetGlobalTransaction(); + TxOut feeOutput = feePSBTOutput == null ? null : originalGlobalTx.Outputs[feePSBTOutput.Index]; + var originalInputs = new Queue<(TxIn OriginalTxIn, PSBTInput SignedPSBTInput)>(); + for (int i = 0; i < originalGlobalTx.Inputs.Count; i++) + { + originalInputs.Enqueue((originalGlobalTx.Inputs[i], signedPSBT.Inputs[i])); + } + var originalOutputs = new Queue<(TxOut OriginalTxOut, PSBTOutput SignedPSBTOutput)>(); + for (int i = 0; i < originalGlobalTx.Outputs.Count; i++) + { + originalOutputs.Enqueue((originalGlobalTx.Outputs[i], signedPSBT.Outputs[i])); + } + // Add the client side query string parameters + endpoint = ApplyOptionalParameters(endpoint, optionalParameters); + Log("original PSBT" + originalPSBT); + PSBT proposal = await SendOriginalTransaction(endpoint, originalPSBT, cancellationToken); + Log("payjoin proposal" + proposal); + // Checking that the PSBT of the receiver is clean + if (proposal.GlobalXPubs.Any()) + { + throw new PayjoinSenderException("GlobalXPubs should not be included in the receiver's PSBT"); + } + //////////// + + if (proposal.CheckSanity() is List<PSBTError> errors && errors.Count > 0) + throw new PayjoinSenderException($"The proposal PSBT is not sane ({errors[0]})"); + + var proposalGlobalTx = proposal.GetGlobalTransaction(); + // Verify that the transaction version, and nLockTime are unchanged. + if (proposalGlobalTx.Version != originalGlobalTx.Version) + throw new PayjoinSenderException($"The proposal PSBT changed the transaction version"); + if (proposalGlobalTx.LockTime != originalGlobalTx.LockTime) + throw new PayjoinSenderException($"The proposal PSBT changed the nLocktime"); + + HashSet<Sequence> sequences = new HashSet<Sequence>(); + // For each inputs in the proposal: + foreach (PSBTInput proposedPSBTInput in proposal.Inputs) + { + if (proposedPSBTInput.HDKeyPaths.Count != 0) + throw new PayjoinSenderException("The receiver added keypaths to an input"); + if (proposedPSBTInput.PartialSigs.Count != 0) + throw new PayjoinSenderException("The receiver added partial signatures to an input"); + PSBTInput proposedTxIn = proposalGlobalTx.Inputs.FindIndexedInput(proposedPSBTInput.PrevOut).TxIn; + bool isOurInput = originalInputs.Count > 0 && originalInputs.Peek().OriginalTxIn.PrevOut == proposedPSBTInput.PrevOut; + // If it is one of our input + if (isOurInput) + { + OutPoint inputPrevout = ourPrevouts.Dequeue(); + TxIn originalTxin = originalGlobalTx.Inputs.FromOutpoint(inputPrevout); + PSBTInput originalPSBTInput = originalPSBT.Inputs.FromOutpoint(inputPrevout); + // Verify that sequence is unchanged. + if (input.OriginalTxIn.Sequence != proposedTxIn.Sequence) + throw new PayjoinSenderException("The proposedTxIn modified the sequence of one of our inputs") + // Verify the PSBT input is not finalized + if (proposedPSBTInput.IsFinalized()) + throw new PayjoinSenderException("The receiver finalized one of our inputs"); + // Verify that <code>non_witness_utxo</code> and <code>witness_utxo</code> are not specified. + if (proposedPSBTInput.NonWitnessUtxo != null || proposedPSBTInput.WitnessUtxo != null) + throw new PayjoinSenderException("The receiver added non_witness_utxo or witness_utxo to one of our inputs"); + sequences.Add(proposedTxIn.Sequence); + + // Fill up the info from the original PSBT input so we can sign and get fees. + proposedPSBTInput.NonWitnessUtxo = input.SignedPSBTInput.NonWitnessUtxo; + proposedPSBTInput.WitnessUtxo = input.SignedPSBTInput.WitnessUtxo; + // We fill up information we had on the signed PSBT, so we can sign it. + foreach (var hdKey in input.SignedPSBTInput.HDKeyPaths) + proposedPSBTInput.HDKeyPaths.Add(hdKey.Key, hdKey.Value); + proposedPSBTInput.RedeemScript = signedPSBTInput.RedeemScript; + proposedPSBTInput.RedeemScript = input.SignedPSBTInput.RedeemScript; + } + else + { + // Verify the PSBT input is finalized + if (!proposedPSBTInput.IsFinalized()) + throw new PayjoinSenderException("The receiver did not finalized one of their input"); + // Verify that non_witness_utxo or witness_utxo are filled in. + if (proposedPSBTInput.NonWitnessUtxo == null && proposedPSBTInput.WitnessUtxo == null) + throw new PayjoinSenderException("The receiver did not specify non_witness_utxo or witness_utxo for one of their inputs"); + sequences.Add(proposedTxIn.Sequence); + // Verify that the payjoin proposal did not introduced mixed inputs' type. + if (inputScriptType != proposedPSBTInput.GetInputScriptPubKeyType()) + throw new PayjoinSenderException("Mixed input type detected in the proposal"); + } + } + + // Verify that all of sender's inputs from the original PSBT are in the proposal. + if (originalInputs.Count != 0) + throw new PayjoinSenderException("Some of our inputs are not included in the proposal"); + + // Verify that the payjoin proposal did not introduced mixed inputs' sequence. + if (sequences.Count != 1) + throw new PayjoinSenderException("Mixed sequence detected in the proposal"); + + decimal newFee = proposal.GetFee(); + decimal additionalFee = newFee - originalFee; + if (additionalFee < 0) + throw new PayjoinSenderException("The receiver decreased absolute fee"); + // For each outputs in the proposal: + foreach (PSBTOutput proposedPSBTOutput in proposal.Outputs) + { + // Verify that no keypaths is in the PSBT output + if (proposedPSBTOutput.HDKeyPaths.Count != 0) + throw new PayjoinSenderException("The receiver added keypaths to an output"); + bool isOriginalOutput = originalOutputs.Count > 0 && originalOutputs.Peek().OriginalTxOut.ScriptPubKey == proposedPSBTOutput.ScriptPubKey; + if (isOriginalOutput) + { + var originalOutput = originalOutputs.Dequeue(); + if (output.OriginalTxOut == feeOutput) + { + var actualContribution = feeOutput.Value - proposedPSBTOutput.Value; + // The amount that was substracted from the output's value is less than or equal to maxadditionalfeecontribution + if (actualContribution > optionalParameters.MaxAdditionalFeeContribution) + throw new PayjoinSenderException("The actual contribution is more than maxadditionalfeecontribution"); + // Make sure the actual contribution is only paying fee + if (actualContribution > additionalFee) + throw new PayjoinSenderException("The actual contribution is not only paying fee"); + // Make sure the actual contribution is only paying for fee incurred by additional inputs + int additionalInputsCount = proposalGlobalTx.Inputs.Count - originalGlobalTx.Inputs.Count; + if (actualContribution > originalFeeRate * GetVirtualSize(inputScriptType) * additionalInputsCount) + throw new PayjoinSenderException("The actual contribution is not only paying for additional inputs"); + } + else if (allowOutputSubstitution && output.OriginalTxOut.ScriptPubKey == paymentScriptPubKey) + { + // That's the payment output, the receiver may have changed it. + } + else + { + if (originalOutput.OriginalTxOut.Value > proposedPSBTOutput.Value) + throw new PayjoinSenderException("The receiver decreased the value of one of the outputs"); + } + // We fill up information we had on the signed PSBT, so we can sign it. + foreach (var hdKey in output.SignedPSBTOutput.HDKeyPaths) + proposedPSBTOutput.HDKeyPaths.Add(hdKey.Key, hdKey.Value); + proposedPSBTOutput.RedeemScript = output.SignedPSBTOutput.RedeemScript; + } + } + // Verify that all of sender's outputs from the original PSBT are in the proposal. + if (originalOutputs.Count != 0) + { + // The payment output may have been substituted + if (!allowOutputSubstitution || + originalOutputs.Count != 1 || + originalOutputs.Dequeue().OriginalTxOut.ScriptPubKey != paymentScriptPubKey) + { + throw new PayjoinSenderException("Some of our outputs are not included in the proposal"); + } + } + + // After signing this proposal, we should check if minfeerate is respected. + Log("payjoin proposal filled with sender's information" + proposal); + return proposal; +} + +int GetVirtualSize(ScriptPubKeyType? scriptPubKeyType) +{ + switch (scriptPubKeyType) + { + case ScriptPubKeyType.Legacy: + return 148; + case ScriptPubKeyType.Segwit: + return 68; + case ScriptPubKeyType.SegwitP2SH: + return 91; + default: + return 110; + } +} + +// Finalize the signedPSBT and remove confidential information +PSBT CreateOriginalPSBT(PSBT signedPSBT) +{ + var original = signedPSBT.Clone(); + original = original.Finalize(); + foreach (var input in original.Inputs) + { + input.HDKeyPaths.Clear(); + input.PartialSigs.Clear(); + input.Unknown.Clear(); + } + foreach (var output in original.Outputs) + { + output.Unknown.Clear(); + output.HDKeyPaths.Clear(); + } + original.GlobalXPubs.Clear(); + return original; +} +</pre> + +==<span id="test-vectors"></span>Test vectors== + +A successful exchange with: + +{| class="wikitable" +!InputScriptType +!Orginal PSBT Fee rate +!maxadditionalfeecontribution +!additionalfeeoutputindex +|- +|P2SH-P2WSH +|2 sat/vbyte +|0.00000182 +|0 +|} + +<code>Unfinalized signed PSBT</code> +<pre>cHNidP8BAHMCAAAAAY8nutGgJdyYGXWiBEb45Hoe9lWGbkxh/6bNiOJdCDuDAAAAAAD+////AtyVuAUAAAAAF6kUHehJ8GnSdBUOOv6ujXLrWmsJRDCHgIQeAAAAAAAXqRR3QJbbz0hnQ8IvQ0fptGn+votneofTAAAAAAEBIKgb1wUAAAAAF6kU3k4ekGHKWRNbA1rV5tR5kEVDVNCHAQQWABTHikVyU1WCjVZYB03VJg1fy2mFMCICAxWawBqg1YdUxLTYt9NJ7R7fzws2K09rVRBnI6KFj4UWRzBEAiB8Q+A6dep+Rz92vhy26lT0AjZn4PRLi8Bf9qoB/CMk0wIgP/Rj2PWZ3gEjUkTlhDRNAQ0gXwTO7t9n+V14pZ6oljUBIgYDFZrAGqDVh1TEtNi300ntHt/PCzYrT2tVEGcjooWPhRYYSFzWUDEAAIABAACAAAAAgAEAAAAAAAAAAAEAFgAURvYaK7pzgo7lhbSl/DeUan2MxRQiAgLKC8FYHmmul/HrXLUcMDCjfuRg/dhEkG8CO26cEC6vfBhIXNZQMQAAgAEAAIAAAACAAQAAAAEAAAAAAA==</pre> + +<code>Original PSBT</code> +<pre>cHNidP8BAHMCAAAAAY8nutGgJdyYGXWiBEb45Hoe9lWGbkxh/6bNiOJdCDuDAAAAAAD+////AtyVuAUAAAAAF6kUHehJ8GnSdBUOOv6ujXLrWmsJRDCHgIQeAAAAAAAXqRR3QJbbz0hnQ8IvQ0fptGn+votneofTAAAAAAEBIKgb1wUAAAAAF6kU3k4ekGHKWRNbA1rV5tR5kEVDVNCHAQcXFgAUx4pFclNVgo1WWAdN1SYNX8tphTABCGsCRzBEAiB8Q+A6dep+Rz92vhy26lT0AjZn4PRLi8Bf9qoB/CMk0wIgP/Rj2PWZ3gEjUkTlhDRNAQ0gXwTO7t9n+V14pZ6oljUBIQMVmsAaoNWHVMS02LfTSe0e388LNitPa1UQZyOihY+FFgABABYAFEb2Giu6c4KO5YW0pfw3lGp9jMUUAAA=</pre> + +<code>payjoin proposal</code> +<pre>cHNidP8BAJwCAAAAAo8nutGgJdyYGXWiBEb45Hoe9lWGbkxh/6bNiOJdCDuDAAAAAAD+////jye60aAl3JgZdaIERvjkeh72VYZuTGH/ps2I4l0IO4MBAAAAAP7///8CJpW4BQAAAAAXqRQd6EnwadJ0FQ46/q6NcutaawlEMIcACT0AAAAAABepFHdAltvPSGdDwi9DR+m0af6+i2d6h9MAAAAAAAEBIICEHgAAAAAAF6kUyPLL+cphRyyI5GTUazV0hF2R2NWHAQcXFgAUX4BmVeWSTJIEwtUb5TlPS/ntohABCGsCRzBEAiBnu3tA3yWlT0WBClsXXS9j69Bt+waCs9JcjWtNjtv7VgIge2VYAaBeLPDB6HGFlpqOENXMldsJezF9Gs5amvDQRDQBIQJl1jz1tBt8hNx2owTm+4Du4isx0pmdKNMNIjjaMHFfrQAAAA==</pre> + +<code>payjoin proposal filled with sender's information</code> +<pre>cHNidP8BAJwCAAAAAo8nutGgJdyYGXWiBEb45Hoe9lWGbkxh/6bNiOJdCDuDAAAAAAD+////jye60aAl3JgZdaIERvjkeh72VYZuTGH/ps2I4l0IO4MBAAAAAP7///8CJpW4BQAAAAAXqRQd6EnwadJ0FQ46/q6NcutaawlEMIcACT0AAAAAABepFHdAltvPSGdDwi9DR+m0af6+i2d6h9MAAAAAAQEgqBvXBQAAAAAXqRTeTh6QYcpZE1sDWtXm1HmQRUNU0IcBBBYAFMeKRXJTVYKNVlgHTdUmDV/LaYUwIgYDFZrAGqDVh1TEtNi300ntHt/PCzYrT2tVEGcjooWPhRYYSFzWUDEAAIABAACAAAAAgAEAAAAAAAAAAAEBIICEHgAAAAAAF6kUyPLL+cphRyyI5GTUazV0hF2R2NWHAQcXFgAUX4BmVeWSTJIEwtUb5TlPS/ntohABCGsCRzBEAiBnu3tA3yWlT0WBClsXXS9j69Bt+waCs9JcjWtNjtv7VgIge2VYAaBeLPDB6HGFlpqOENXMldsJezF9Gs5amvDQRDQBIQJl1jz1tBt8hNx2owTm+4Du4isx0pmdKNMNIjjaMHFfrQABABYAFEb2Giu6c4KO5YW0pfw3lGp9jMUUIgICygvBWB5prpfx61y1HDAwo37kYP3YRJBvAjtunBAur3wYSFzWUDEAAIABAACAAAAAgAEAAAABAAAAAAA=</pre> + +==Implementations== + +* [[https://github.com/BlueWallet/BlueWallet|BlueWallet]] is in the process of implementing the protocol. +* [[https://github.com/btcpayserver/btcpayserver|BTCPay Server]] has implemented sender and receiver side of this protocol. +* [[https://github.com/zkSNACKs/WalletWasabi/|Wasabi Wallet]] has merged sender's support. +* [[https://github.com/JoinMarket-Org/joinmarket-clientserver|Join Market]] is in the process of implementing the protocol. +* [[https://github.com/bitcoinjs/payjoin-client|JavaScript sender implementation]]. + +==Backward compatibility== + +The receivers are advertising payjoin capabilities through [[bip-0021.mediawiki|BIP21's URI Scheme]]. + +Senders not supporting payjoin will just ignore the <code>pj</code> variable and thus, will proceed to normal payment. + +==Special thanks== + +Special thanks to Kukks for developing the initial support to BTCPay Server, to junderw, AdamISZ, lukechilds, ncoelho, nopara73, lontivero, yahiheb, SomberNight, andrewkozlik, instagibbs, RHavar for all the feedback we received since our first implementation. +Thanks again to RHavar who wrote the [[bip-0079.mediawiki|BIP79 Bustapay]] proposal, this gave a good starting point for our proposal. diff --git a/bip-0079.mediawiki b/bip-0079.mediawiki index 99430d9..c8f2104 100644 --- a/bip-0079.mediawiki +++ b/bip-0079.mediawiki @@ -5,10 +5,11 @@ Author: Ryan Havar <rhavar@protonmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0079 - Status: Proposed + Status: Replaced Type: Informational Created: 2018-10-05 License: CC0-1.0 + Superseded-By: 78 </pre> diff --git a/bip-0083.mediawiki b/bip-0083.mediawiki index a0b1e5e..d7bbe8e 100644 --- a/bip-0083.mediawiki +++ b/bip-0083.mediawiki @@ -5,7 +5,7 @@ Author: Eric Lombrozo <eric@ciphrex.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0083 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-11-16 License: PD diff --git a/bip-0085.mediawiki b/bip-0085.mediawiki new file mode 100644 index 0000000..7c4cbca --- /dev/null +++ b/bip-0085.mediawiki @@ -0,0 +1,261 @@ +<pre> + BIP: 85 + Layer: Applications + Title: Deterministic Entropy From BIP32 Keychains + Author: Ethan Kosakovsky <ethankosakovsky@protonmail.com> + Comments-Summary: No comments yet. + Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0085 + Status: Draft + Type: Informational + Created: 2020-03-20 + License: BSD-2-Clause + OPL +</pre> + +==Abstract== + +''"One Seed to rule them all,'' +''One Key to find them,'' +''One Path to bring them all,'' +''And in cryptography bind them."'' + +It is not possible to maintain one single (mnemonic) seed backup for all keychains used across various wallets because there are a variety of incompatible standards. Sharing of seeds across multiple wallets is not desirable for security reasons. Physical storage of multiple seeds is difficult depending on the security and redundancy required. + +As HD keychains are essentially derived from initial entropy, this proposal provides a way to derive entropy from the keychain which can be fed into whatever method a wallet uses to derive the initial mnemonic seed or root key. + +==Definitions== + +The terminology related to keychains used in the wild varies widely, for example `seed` has various different meanings. In this document we define the terms + +# '''BIP32 root key''' is the root extended private key that is represented as the top root of the keychain in BIP32. +# '''BIP39 mnemonic''' is the mnemonic phrase that is calculated from the entropy used before hashing of the mnemonic in BIP39. +# '''BIP39 seed''' is the result of hashing the BIP39 mnemonic seed. + +==Motivation== + +Most wallets implement BIP32 which defines how a BIP32 root key can be used to derive keychains. As a consequence, a backup of just the BIP32 root key is sufficient to include all keys derived from it. BIP32 does not have a human friendly serialization of the BIP32 root key (or BIP32 extended keys in general) which makes paper backups or manually restoring the key more error-prone. BIP39 was designed solve this problem but rather than serialize the BIP32 root key, it takes some entropy, encoded to a "seed mnemonic", which is then hashed to derive the BIP39 seed which can be turned into the BIP32 root key. Saving the BIP39 mnemonic is enough to reconstruct the entire BIP32 keychain, but a BIP32 root key cannot be reversed back to the BIP39 mnemonic. + +Most wallets implement BIP39, so on initialization or restoration, the user must interact with a BIP39 mnemonic. Most wallets do not support of BIP32 extended private keys so each wallet must either share the same BIP39 mnemonic, or have a separate BIP39 mnemonic entirely. Neither scenarios are particularly satisfactory for security reasons. For example, some wallets may be inherently less secure like hot wallets on smartphones, Join Market servers, Lightning Network nodes. Having multiple seeds is far from desirable especially for those who rely on split key or redundancy backups in different geological locations. Adding is necessarily difficult and may result in users being more lazy with subsequent keys, such that compromises security or leads to key loss. + +There is added complication with wallets that implement other standards, or no standards at all. Bitcoin Core wallet uses a WIF as the ''hdseed'', and yet other wallets use different mnemonic schemes like Electrum to derive the BIP32 root key. Other cryptocurrencies like Monero also use a different mnemonic scheme entirely. + +Ultimately, all of the mnemonic/seed schemes start with some "initial entropy" to derive a mnemonic/seed, and then process the mnemonic into a BIP32 key, or private key. We can use BIP32 itself to derive the "initial entropy" to then recreate the same mnemonic or seed according the specific application standard of the target wallet. We can use a BIP44 like categorization to ensure unitform derivation according to the target application type. + +==Specification== + +We assume a single BIP32 master root key. This specification is not concerned with how this was derived (e.g. directly or via a mnemonic scheme such as BIP39). + +For each application that requires its own wallet, a unique private key is derived from the BIP32 master root key using fully hardened derivation path. The resulting private key (k) is then processed with HMAC-SHA512, where the key is "bip-entropy-from-k", and the message payload is the private key k: <code>HMAC-SHA512(key="bip-entropy-from-k", msg=k)</code>. The result produces 512 bits of entropy. Each application SHOULD use up to the required number of bits necessary for their operation truncating the rest + +The HMAC-SHA512 function is specified in [http://tools.ietf.org/html/rfc4231 RFC 4231]. + +===Test vectors=== + +====Test case 1==== +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/0'/0' + +OUTPUT: +* DERIVED KEY=cca20ccb0e9a90feb0912870c3323b24874b0ca3d8018c4b96d0b97c0e82ded0 +* DERIVED ENTROPY=efecfbccffea313214232d29e71563d941229afb4338c21f9517c41aaa0d16f00b83d2a09ef747e7a64e8e2bd5a14869e693da66ce94ac2da570ab7ee48618f7 + +====Test case 2==== +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +*PATH: m/83696968'/0'/1' + +OUTPUT +* DERIVED KEY=503776919131758bb7de7beb6c0ae24894f4ec042c26032890c29359216e21ba +* DERIVED ENTROPY=70c6e3e8ebee8dc4c0dbba66076819bb8c09672527c4277ca8729532ad711872218f826919f6b67218adde99018a6df9095ab2b58d803b5b93ec9802085a690e + +==Reference Implementation== + +Python library implementation: [https://github.com/ethankosakovsky/bipentropy python-bipentropy] + +===Other Implementations=== + +Coldcard Firmware: [https://github.com/Coldcard/firmware/pull/39] + +==Applications== + +Application number define how entropy will be used post processing. Some basic examples follow: + +Derivation path uses the format <code>m/83696968/' + /app_no' + /index'</code> where ''app_no'' path for the application, and `index` in the index. + +===BIP39=== +Application number: 39' + +Truncate trailing (least significant) bytes of the entropy to the number of bits required to map to the relevant word length 128 bits for 12 words, 256 bits for 24 words. + +The derivation path format is: <code>m/83696968'/39'/{language}'/{words}'/{index}'</code> + +Example a BIP39 mnemonic with 12 English words (first index) would have the path <code>m/83696968'/39'/0'/12'/0'</code> the next key would be <code>m/83696968'/39'/0'/12'/1'</code> etc. + +Language Table + +{| +!Wordlist +!Code +|- +| English +| 0' +|- +| Japanese +| 1' +|- +| Korean +| 2' +|- +| Spanish +| 3' +|- +| Chinese (Simplified) +| 4' +|- +| Chinese (Traditional) +| 5' +|- +| French +| 6' +|- +| Italian +| 7' +|- +| Czech +| 8' +|} + +Words Table + +{| +!Words +!Entropy +!Code +|- +| 12 words +| 128 bits +| 12' +|- +| 18 words +| 192 bits +| 18' +|- +| 24 words +| 256 bits +| 24' +|} + +====12 English words==== +BIP39 English 12 word mnemonic seed + +128 bits of entropy as input to BIP39 to derive 12 word mnemonic + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/39'/0'/12'/0' + +OUTPUT: +* DERIVED ENTROPY=6250b68daf746d12a24d58b4787a714b +* DERIVED BIP39 MNEMONIC=girl mad pet galaxy egg matter matrix prison refuse sense ordinary nose + +====18 English words==== +BIP39 English 18 word mnemonic seed + +196 bits of entropy as input to BIP39 to derive 18 word mnemonic + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/39'/0'/18'/0' + +OUTPUT: +* DERIVED ENTROPY=938033ed8b12698449d4bbca3c853c66b293ea1b1ce9d9dc +* DERIVED BIP39 MNEMONIC=near account window bike charge season chef number sketch tomorrow excuse sniff circle vital hockey outdoor supply token + +====24 English words==== +Derives 24 word BIP39 mnemonic seed + +256 bits of entropy as input to BIP39 to derive 24 word mnemonic + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/39'/0'/24'/0' + +OUTPUT: +* DERIVED ENTROPY=ae131e2312cdc61331542efe0d1077bac5ea803adf24b313a4f0e48e9c51f37f +* DERIVED BIP39 MNEMONIC=puppy ocean match cereal symbol another shed magic wrap hammer bulb intact gadget divorce twin tonight reason outdoor destroy simple truth cigar social volcano + +===HD-Seed WIF=== +Application number: 2' + +Uses 256 bits[1] of entropy as the secret exponent to derive a private key and encode as a compressed WIF which will be used as the hdseed for Bitcoin Core wallets. + +Path format is <code>m/83696968'/2'/{index}'</code> + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/2'/0' + +OUTPUT +* DERIVED ENTROPY=7040bb53104f27367f317558e78a994ada7296c6fde36a364e5baf206e502bb1 +* DERIVED WIF=Kzyv4uF39d4Jrw2W7UryTHwZr1zQVNk4dAFyqE6BuMrMh1Za7uhp + +===XPRV=== +Application number: 32' + +Taking 64 bytes of the HMAC digest, the first 32 bytes are the chain code, and second 32 bytes[1] are the private key for BIP32 XPRV value. Child number, depth, and parent fingerprint are forced to zero. + +Path format is <code>m/83696968'/32'/{index}'</code> + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/32'/0' + +OUTPUT +* DERIVED ENTROPY=ead0b33988a616cf6a497f1c169d9e92562604e38305ccd3fc96f2252c177682 +* DERIVED WIF=xprv9s21ZrQH143K2srSbCSg4m4kLvPMzcWydgmKEnMmoZUurYuBuYG46c6P71UGXMzmriLzCCBvKQWBUv3vPB3m1SATMhp3uEjXHJ42jFg7myX + +===HEX=== +Application number: 128169' + +The derivation path format is: <code>m/83696968'/128169'/{num_bytes}'/{index}'</code> + +`16 <= num_bytes <= 64` + +Truncate trailing (least significant) bytes of the entropy after `num_bytes`. + +INPUT: +* MASTER BIP32 ROOT KEY: xprv9s21ZrQH143K2LBWUUQRFXhucrQqBpKdRRxNVq2zBqsx8HVqFk2uYo8kmbaLLHRdqtQpUm98uKfu3vca1LqdGhUtyoFnCNkfmXRyPXLjbKb +* PATH: m/83696968'/128169'/64'/0' + +OUTPUT +* DERIVED ENTROPY=492db4698cf3b73a5a24998aa3e9d7fa96275d85724a91e71aa2d645442f878555d078fd1f1f67e368976f04137b1f7a0d19232136ca50c44614af72b5582a5c + +==Backwards Compatibility== + +This specification is not backwards compatible with any other existing specification. + +This specification relies on BIP32 but is agnostic to how the BIP32 root key is derived, as such this standard is allows it to derive wallets with initialization schemes like BIP39 or Electrum wallet style mnemonics. + +==Discussion== + +The reason for running the derived key through HMAC-SHA512 and truncating the result as necessary is to prevent leakage of the parent tree should the derived key (k) be compromized. While the specification requires the use of hardended key derivation which would prevent this, we cannot enforce hardened derivation, so this method ensures the derived entropy is hardened. Also from a semantic point of view, since the purpose is to derive entropy and not a private key, we are required to transform the child key. This acts in an abundance of caution to ward off unwanted side effects should k be used for a dual purpose, including as a nonce hash(k), where undesirable and unforeseen interactions could occur. + +==Acknowledgements== + +Many thanks to Peter Gray and Christopher Allen for their input, and to Peter for suggesting extra application use cases. + +==References== + +BIP32, BIP39 + +==Footnotes== + +[1] There is a very small chance that you'll make an invalid key that is zero or bigger than the order of the curve. If this occurs, software should hard fail (forcing users should iterate to the next index). + +From BIP32: +> In case parse<sub>256</sub>(I<sub>L</sub>) is 0 or ≥ n, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has probability lower than 1 in 2<sup>127</sup>.) + +==Copyright== + +This BIP is dual-licensed under the Open Publication License and BSD 2-clause license. diff --git a/bip-0090.mediawiki b/bip-0090.mediawiki index 8cf3d6d..4c96698 100644 --- a/bip-0090.mediawiki +++ b/bip-0090.mediawiki @@ -4,7 +4,7 @@ Author: Suhas Daftuar <sdaftuar@chaincode.com> Comments-Summary: Mostly Recommended for implementation, with some Discouragement Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0090 - Status: Draft + Status: Final Type: Informational Created: 2016-11-08 License: PD diff --git a/bip-0099.mediawiki b/bip-0099.mediawiki index 1496557..8882e00 100644 --- a/bip-0099.mediawiki +++ b/bip-0099.mediawiki @@ -4,7 +4,7 @@ Author: Jorge Timón <jtimon@jtimon.cc> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0099 - Status: Draft + Status: Rejected Type: Informational Created: 2015-06-20 License: PD diff --git a/bip-0104.mediawiki b/bip-0104.mediawiki index 00db9a3..1244b3e 100644 --- a/bip-0104.mediawiki +++ b/bip-0104.mediawiki @@ -5,7 +5,7 @@ Author: t.khan <teekhan42@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0104 - Status: Draft + Status: Rejected Type: Standards Track Created: 2017-01-13 License: BSD-2-Clause diff --git a/bip-0105.mediawiki b/bip-0105.mediawiki index 125d852..3643562 100644 --- a/bip-0105.mediawiki +++ b/bip-0105.mediawiki @@ -5,7 +5,7 @@ Author: BtcDrak <btcdrak@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0105 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-08-21 License: PD diff --git a/bip-0106.mediawiki b/bip-0106.mediawiki index f622907..193d4cd 100644 --- a/bip-0106.mediawiki +++ b/bip-0106.mediawiki @@ -5,7 +5,7 @@ Author: Upal Chakraborty <bitcoin@upalc.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0106 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-08-24 </pre> diff --git a/bip-0107.mediawiki b/bip-0107.mediawiki index 84cd6a6..b82db61 100644 --- a/bip-0107.mediawiki +++ b/bip-0107.mediawiki @@ -5,7 +5,7 @@ Author: Washington Y. Sanchez <washington.sanchez@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0107 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-09-11 License: PD diff --git a/bip-0115.mediawiki b/bip-0115.mediawiki index 9432f5c..8bc90f6 100644 --- a/bip-0115.mediawiki +++ b/bip-0115.mediawiki @@ -5,7 +5,7 @@ Author: Luke Dashjr <luke+bip@dashjr.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0115 - Status: Draft + Status: Rejected Type: Standards Track Created: 2016-09-23 License: BSD-2-Clause diff --git a/bip-0119/fifty.png b/bip-0119/fifty.png Binary files differindex 6917937..1f90c01 100644 --- a/bip-0119/fifty.png +++ b/bip-0119/fifty.png diff --git a/bip-0119/five.png b/bip-0119/five.png Binary files differindex 5cf741a..7baa568 100644 --- a/bip-0119/five.png +++ b/bip-0119/five.png diff --git a/bip-0119/simulation.py b/bip-0119/simulation.py index ee06fee..e40d61e 100755 --- a/bip-0119/simulation.py +++ b/bip-0119/simulation.py @@ -24,6 +24,7 @@ def get_rate(phase): return 1.25**(phase)*TXNS_PER_SEC def normal(): + np.random.seed(0) print("Max Txns Per Sec %f"%TXNS_PER_SEC) backlog = 0 results_unconfirmed = [0]*SAMPLES @@ -43,6 +44,7 @@ def normal(): results_unconfirmed[i] = backlog/AVG_TX return results_unconfirmed, np.cumsum(total_time)/(60*60*24.0) def compressed(rate_multiplier = 1): + np.random.seed(0) print("Max Txns Per Sec %f"%TXNS_PER_SEC) backlog = 0 secondary_backlog = 0 @@ -54,7 +56,7 @@ def compressed(rate_multiplier = 1): total_time = [0]*(SAMPLES) for phase in range(PHASES): for i in range(PHASE_LENGTH*phase, PHASE_LENGTH*(1+phase)): - block_time = np.random.poisson(AVG_INTERVAL) + block_time = np.random.exponential(AVG_INTERVAL) total_time[i] = block_time txns = np.random.poisson(rate_multiplier*get_rate(phase)*block_time) postponed = txns * COMPRESSABLE diff --git a/bip-0131.mediawiki b/bip-0131.mediawiki index 5938138..25ba3a7 100644 --- a/bip-0131.mediawiki +++ b/bip-0131.mediawiki @@ -5,7 +5,7 @@ Author: Chris Priest <cp368202@ohiou.edu> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0131 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-11-30 License: PD diff --git a/bip-0134.mediawiki b/bip-0134.mediawiki index 74f6302..b7c33cf 100644 --- a/bip-0134.mediawiki +++ b/bip-0134.mediawiki @@ -5,7 +5,7 @@ Author: Tom Zander <tomz@freedommail.ch> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0134 - Status: Draft + Status: Rejected Type: Standards Track Created: 2016-07-27 License: CC-BY-SA-4.0 diff --git a/bip-0137.mediawiki b/bip-0137.mediawiki index 7ef89f4..19dd536 100644 --- a/bip-0137.mediawiki +++ b/bip-0137.mediawiki @@ -52,11 +52,11 @@ The header byte has a few components to it. First, it stores something known as ===Procedure for signing/verifying a signature=== -As noted above the signature is composed of three components, the header, r and s values. r/s can be computed with standard ECDSA library functions. Part of the header includes something called a recId. This is part of every ECDSA signature and should be generated by the ECDSA library. The recId is a number between 0 and 3 inclusive. The header is the recId plus a constant which indicates what time of Bitcoin private key this is. For P2PKH uncompressed keys, this value is 27. For P2PKH compressed keys, this value is 31. For P2SH Segwit keys, this value is 35 and for bech32 keys, this value is 35. So, you have the following ranges: -27-30: P2PKH uncompressed -31-34: P2PKH compressed -35-38: Segwit P2SH -39-42: Segwit Bech32 +As noted above the signature is composed of three components, the header, r and s values. r/s can be computed with standard ECDSA library functions. Part of the header includes something called a recId. This is part of every ECDSA signature and should be generated by the ECDSA library. The recId is a number between 0 and 3 inclusive. The header is the recId plus a constant which indicates what type of Bitcoin address this is. For P2PKH address using an uncompressed public key this value is 27. For P2PKH address using compressed public key this value is 31. For P2SH-P2WPKH this value is 35 and for P2WPKH (version 0 witness) address this value is 39. So, you have the following ranges: +* 27-30: P2PKH uncompressed +* 31-34: P2PKH compressed +* 35-38: Segwit P2SH +* 39-42: Segwit Bech32 To verify a signature, the recId is obtained by subtracting this constant from the header value. diff --git a/bip-0140.mediawiki b/bip-0140.mediawiki index 9fb52b4..88131f4 100644 --- a/bip-0140.mediawiki +++ b/bip-0140.mediawiki @@ -5,7 +5,7 @@ Author: Christian Decker <decker.christian@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0140 - Status: Draft + Status: Rejected Type: Standards Track Created: 2015-10-14 License: PD diff --git a/bip-0146.mediawiki b/bip-0146.mediawiki index 240f82a..f4a18a1 100644 --- a/bip-0146.mediawiki +++ b/bip-0146.mediawiki @@ -6,7 +6,7 @@ Pieter Wuille <pieter.wuille@gmail.com> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0146 - Status: Draft + Status: Withdrawn Type: Standards Track Created: 2016-08-16 License: PD diff --git a/bip-0152.mediawiki b/bip-0152.mediawiki index e6a3969..8200714 100644 --- a/bip-0152.mediawiki +++ b/bip-0152.mediawiki @@ -5,7 +5,7 @@ Author: Matt Corallo <bip152@bluematt.me> Comments-Summary: Unanimously Recommended for implementation Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0152 - Status: Draft + Status: Final Type: Standards Track Created: 2016-04-27 License: PD diff --git a/bip-0155.mediawiki b/bip-0155.mediawiki index 6f538d4..f437043 100644 --- a/bip-0155.mediawiki +++ b/bip-0155.mediawiki @@ -78,8 +78,8 @@ This means that the message contains a serialized <code>std::vector</code> of th One message can contain up to 1,000 addresses. Clients SHOULD reject messages with more addresses. -Field <code>addr</code> has a variable length, with a maximum of 32 bytes (256 bits). Clients SHOULD reject -longer addresses. +Field <code>addr</code> has a variable length, with a maximum of 512 bytes (4096 bits). +Clients SHOULD reject messages with longer addresses, irrespective of the network ID. The list of reserved network IDs is as follows: @@ -120,21 +120,23 @@ The list of reserved network IDs is as follows: | Cjdns overlay network address |} -To allow for future extensibility, clients MUST ignore address types that they do not know about. -Client MAY store and gossip address formats that they do not know about. Further network ID numbers MUST be reserved in a new BIP document. +Clients are RECOMMENDED to gossip addresses from all known networks even if they are currently not connected to some of them. That could help multi-homed nodes and make it more difficult for an observer to tell which networks a node is connected to. -Clients SHOULD reject addresses that have a different length than specified in this table for a specific address ID, as these are meaningless. +Clients SHOULD NOT gossip addresses from unknown networks because they have no means to validate those addresses and so can be tricked to gossip invalid addresses. + +Further network ID numbers MUST be reserved in a new BIP document. + +Clients SHOULD reject messages that contain addresses that have a different length than specified in this table for a specific network ID, as these are meaningless. See the appendices for the address encodings to be used for the various networks. -==Compatibility== +==Signaling support and compatibility== + +Introduce a new message type <code>sendaddrv2</code>. Sending such a message indicates that a node can understand and prefers to receive <code>addrv2</code> messages instead of <code>addr</code> messages. I.e. "Send me addrv2". + +<code>sendaddrv2</code> SHOULD be sent after receiving the <code>verack</code> message from the peer. -Send <code>addrv2</code> messages only, and exclusively, when the peer has a certain protocol version (or higher): -<source lang="c++"> -//! gossiping using `addrv2` messages starts with this version -static const int GOSSIP_ADDRV2_VERSION = 70016; -</source> -For older peers keep sending the legacy <code>addr</code> message, ignoring addresses with the newly introduced address types. +For older peers, that did not emit <code>sendaddrv2</code>, keep sending the legacy <code>addr</code> message, ignoring addresses with the newly introduced address types. ==Reference implementation== diff --git a/bip-0156.mediawiki b/bip-0156.mediawiki index dde928a..dcfed1f 100644 --- a/bip-0156.mediawiki +++ b/bip-0156.mediawiki @@ -9,7 +9,7 @@ Shaileshh Bojja Venkatakrishnan <shaileshh.bv@gmail.com> Pramod Viswanath <pramodv@illinois.edu> Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0156 - Status: Draft + Status: Rejected Type: Standards Track Created: 2017-06-09 License: CC0-1.0 diff --git a/bip-0171.mediawiki b/bip-0171.mediawiki index 11eb109..c4a8414 100644 --- a/bip-0171.mediawiki +++ b/bip-0171.mediawiki @@ -5,7 +5,7 @@ Author: Luke Dashjr <luke+bip@dashjr.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0171 - Status: Draft + Status: Rejected Type: Standards Track Created: 2017-03-04 License: BSD-2-Clause diff --git a/bip-0174.mediawiki b/bip-0174.mediawiki index df7d658..65fa9a9 100644 --- a/bip-0174.mediawiki +++ b/bip-0174.mediawiki @@ -143,13 +143,13 @@ The currently defined per-input types are defined as follows: * Type: Non-Witness UTXO <tt>PSBT_IN_NON_WITNESS_UTXO = 0x00</tt> ** Key: None. The key must only contain the 1 byte type. ***<tt>{0x00}</tt> -** Value: The transaction in network serialization format the current input spends from. This should only be present for inputs which spend non-segwit outputs. However, if it is unknown whether an input spends a segwit output, this type should be used. +** Value: The transaction in network serialization format the current input spends from. This should be present for inputs that spend non-segwit outputs and can be present for inputs that spend segwit outputs. An input can have both <tt>PSBT_IN_NON_WITNESS_UTXO</tt> and <tt>PSBT_IN_WITNESS_UTXO</tt>. <ref>'''Why can both UTXO types be provided?''' Many wallets began requiring the full previous transaction (i.e. <tt>PSBT_IN_NON_WITNESS_UTXO</tt>) for segwit inputs when PSBT was already in use. In order to be compatible with software which were expecting <tt>PSBT_IN_WITNESS_UTXO</tt>, both UTXO types must be allowed.</ref> *** <tt>{transaction}</tt> * Type: Witness UTXO <tt>PSBT_IN_WITNESS_UTXO = 0x01</tt> ** Key: None. The key must only contain the 1 byte type. *** <tt>{0x01}</tt> -** Value: The entire transaction output in network serialization which the current input spends from. This should only be present for inputs which spend segwit outputs, including P2SH embedded ones. +** Value: The entire transaction output in network serialization which the current input spends from. This should only be present for inputs which spend segwit outputs, including P2SH embedded ones. An input can have both <tt>PSBT_IN_NON_WITNESS_UTXO</tt> and <tt>PSBT_IN_WITNESS_UTXO</tt> *** <tt>{serialized transaction output({output value}|<scriptPubKey>)}</tt> * Type: Partial Signature <tt>PSBT_IN_PARTIAL_SIG = 0x02</tt> @@ -200,6 +200,30 @@ The currently defined per-input types are defined as follows: ** Value: The UTF-8 encoded commitment message string for the proof-of-reserves. See [[bip-0127.mediawiki|BIP 127]] for more information. *** <tt>{porCommitment}</tt> +* Type: RIPEMD160 preimage <tt>PSBT_RIPEMD160 = 0x0a</tt> +** Key: The resulting hash of the preimage +*** <tt>{0x0a}|{20-byte hash}</tt> +** Value: The hash preimage, encoded as a byte vector, which must equal the key when run through the `RIPEMD160` algorithm +*** <tt>{preimage}</tt> + +* Type: SHA256 preimage <tt>PSBT_SHA256 = 0x0b</tt> +** Key: The resulting hash of the preimage +*** <tt>{0x0b}|{32-byte hash}</tt> +** Value: The hash preimage, encoded as a byte vector, which must equal the key when run through the `SHA256` algorithm +*** <tt>{preimage}</tt> + +* Type: HASH160 preimage <tt>PSBT_HASH160 = 0x0c</tt> +** Key: The resulting hash of the preimage +*** <tt>{0x0c}|{20-byte hash}</tt> +** Value: The hash preimage, encoded as a byte vector, which must equal the key when run through the `SHA256` algorithm followed by the `RIPEMD160` algorithm +*** <tt>{preimage}</tt> + +* Type: HASH256 preimage <tt>PSBT_HASH256 = 0x0d</tt> +** Key: The resulting hash of the preimage +*** <tt>{0x0d}|{32-byte hash}</tt> +** Value: The hash preimage, encoded as a byte vector, which must equal the key when run through the `SHA256` algorithm twice +*** <tt>{preimage}</tt> + * Type: Proprietary Use Type <tt>PSBT_IN_PROPRIETARY = 0xFC</tt> ** Key: Variable length identifier prefix, followed by a subtype, followed by the key data itself. *** <tt>{0xFC}|<prefix>|{subtype}|{key data}</tt> @@ -349,6 +373,7 @@ The Signer must only accept a PSBT. The Signer must only use the UTXOs provided in the PSBT to produce signatures for inputs. Before signing a non-witness input, the Signer must verify that the TXID of the non-witness UTXO matches the TXID specified in the unsigned transaction. Before signing a witness input, the Signer must verify that the witnessScript (if provided) matches the hash specified in the UTXO or the redeemScript, and the redeemScript (if provided) matches the hash in the UTXO. +The Signer may choose to fail to sign a segwit input if a non-witness UTXO is not provided. <ref>'''Why would non-witness UTXOs be provided for segwit inputs?''' The sighash algorithm for Segwit specified in BIP 173 is known to have an issue where an attacker could trick a user to sending Bitcoin to fees if they are able to convince the user to sign a malicious transaction multiple times. This is possible because the amounts in <tt>PSBT_IN_WITNESS_UTXO<tt> of other segwit inputs can be modified without effecting the signature for a particular input. In order to prevent this kind of attack, many wallets are requiring that the full previous transaction (i.e. <tt>PSBT_IN_NON_WITNESS_UTXO</tt>) be provided to ensure that the amounts of other inputs are not being tampered with.</ref> The Signer should not need any additional data sources, as all necessary information is provided in the PSBT format. The Signer must only add data to a PSBT. Any signatures created by the Signer must be added as a "Partial Signature" key-value pair for the respective input it relates to. @@ -447,7 +472,7 @@ Or, for participants performing fA(psbt) and fB(psbt): Combine(fA(psbt), fB(psbt ===Input Finalizer=== The Input Finalizer must only accept a PSBT. -For each input, the Input Finalizer determines if the input has enough data to pass validation. If it does, it must construct the scriptSig and scriptWitness and place them into the input key-value map. +For each input, the Input Finalizer determines if the input has enough data to pass validation. If it does, it must construct the <tt>0x07</tt> Finalized scriptSig and <tt>0x08</tt> Finalized scriptWitness and place them into the input key-value map. All other data except the UTXO and unknown fields in the input key-value map should be cleared from the PSBT. The UTXO should be kept to allow Transaction Extractors to verify the final network serialized transaction. ===Transaction Extractor=== diff --git a/bip-0180.mediawiki b/bip-0180.mediawiki index 9f6bd18..721b0b7 100644 --- a/bip-0180.mediawiki +++ b/bip-0180.mediawiki @@ -5,7 +5,7 @@ Author: Luke Dashjr <luke+bip@dashjr.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0180 - Status: Draft + Status: Rejected Type: Standards Track Created: 2017-03-17 License: BSD-2-Clause diff --git a/bip-0322.mediawiki b/bip-0322.mediawiki index aaf5496..95991e6 100644 --- a/bip-0322.mediawiki +++ b/bip-0322.mediawiki @@ -34,8 +34,6 @@ The current message signing standard only works for P2PKH (1...) addresses. By e A new structure <code>SignatureProof</code> is added, which is a simple serializable scriptSig & witness container. -Two actions "Sign" and "Verify" are defined along with one ''purpose'', "SignMessage", with the ability to expand in the future to add a potential "ProveFunds" purpose. - === SignatureProof container === {|class="wikitable" style="text-align: center;" @@ -45,20 +43,6 @@ Two actions "Sign" and "Verify" are defined along with one ''purpose'', "SignMes !Name !Comment |- -|Uint32||4||version||BIP322 version format; must be equal to 1; if > 1, verifier must abort the verification process -|- -|Uint8||1||entries||number of proof entries<ref><strong>Why support multiple proofs?</strong> It is non-trivial to check a large number of individual proofs for duplicates. Software could be written to do so, but it seems more efficient to build this check into the specification itself.</ref> -|} - -The above is followed by [entries] number of signature entries: - -{|class="wikitable" style="text-align: center;" -|- -!Type -!Length -!Name -!Comment -|- |VarInt||1-8||scriptsiglen||Number of bytes in scriptSig data |- |Uint8*||[scriptsiglen]||scriptsig||ScriptSig data @@ -79,74 +63,51 @@ A verification call will return a result code according to the table below. !Code !Description |- -|INCOMPLETE||One or several of the given challenges had an empty proof. The prover may need some other entity to complete the proof. +|INCOMPLETE||Empty proof. |- -|INCONCLUSIVE||One or several of the given proofs was consensus-valid but policy-invalid. +|INCONCLUSIVE||The given proof was consensus-valid but policy-invalid. |- -|VALID||All proofs were deemed valid. +|VALID||The proof was valid. |- -|INVALID||One or more of the given proofs were invalid +|INVALID||The proof was invalid |- |ERROR||An error was encountered |} == Signing and Verifying == -If the challenge consists of a single address and the address is in the P2PKH (legacy) format, sign using the legacy format (further information below). Otherwise continue as stated below. +If the challenge consists of an address is in the P2PKH (legacy) format, sign using the legacy format (further information below). Otherwise continue as stated below. -Let there be an empty set <code>inputs</code> which is populated and tested at each call to one of the actions below. +For both cases, generate a sighash based on the given scriptPubKey and message as follows: -=== Purpose: SignMessage === - -The "SignMessage" purpose generates a sighash based on a scriptPubKey and a message. It emits a VALID verification result code unless otherwise stated. - -# Return INVALID if scriptPubKey already exists in <code>inputs</code> set, otherwise insert it<ref><strong>Why track duplicates?</strong> Because a 3-entry proof is not proving 3 entries unless they are all distinct</ref> # Define the message pre-image as the sequence "Bitcoin Signed Message:\n" concatenated with the message, encoded in UTF-8 using Normalization Form Compatibility Decomposition (NFKD) # Let sighash = sha256(sha256(scriptPubKey || pre-image)) A private key may be used directly to sign a message. In this case, its P2WPKH bech32 address shall be derived, and used as the input. -=== Action: Sign === +=== Signing === -The "Sign" action takes as input a purpose. It returns a signature or fails. +The signature is generated as follows: -# Obtain the sighash and scriptPubKey from the purpose; FAIL if not VALID # Derive the private key privkey for the scriptPubKey; FAIL if not VALID # Generate and return a signature sig with privkey=privkey, sighash=sighash -The resulting signature proof should be encoded using base64 encoding. - -=== Action: Verify === +=== Verifying === -The "Verify" action takes as input a standard flags value, a script sig, an optional witness, and a purpose. -It emits one of INCONCLUSIVE, VALID, INVALID, or ERROR. +Verify a proof, given a standard flags value, a script sig, an optional witness, and a derived sighash as described above. While omitted below, ERROR is returned if an unforeseen error occurs at any point in the process. A concrete example of this is if a legacy proof is given as input to a non-legacy address; the deserialization of the proof will fail in this case, and this should result in an ERROR result. -# Obtain the sighash and scriptPubKey from the purpose; pass on result code if not VALID # Verify Script with flags=consensus flags (currently P2SH, DERSIG, NULLDUMMY, CLTV, CSV, WITNESS), scriptSig=script sig, scriptPubKey=scriptPubKey, witness=witness, and sighash=sighash # Return INVALID if verification fails # Verify Script with flags=standard flags (above plus STRICTENC, MINIMALDATA, etc.), scriptSig=script sig, scriptPubKey=scriptPubKey, witness=witness, and sighash=sighash # Return VALID if verification succeeds, otherwise return INCONCLUSIVE -=== Multiple Proofs === - -When more than one proof is created or verified, repeat the operation for each proof, retaining the inputs set. As noted, if the same input appears more than once, the operation must fail accordingly. - -Note that the order of the entries in the proof must match the order of the entries given by the verifier. - -* If any of the proofs are empty during a verification process, skip the verification and set the INCOMPLETE flag -* If a verification call returns ERROR or INVALID, return ERROR or INVALID immediately, ignoring as yet unverified entries -* After all verifications complete, -** return INCONCLUSIVE if any verification call returned INCONCLUSIVE -** return INCOMPLETE if the INCOMPLETE flag is set -** return VALID - == Legacy format == -The legacy format is restricted to the legacy P2PKH address format, and restricted to one single challenge (address). +The legacy format is restricted to the legacy P2PKH address format. -Any other input (e.g. multiple addresses, or non-P2PKH address format(s)) must be signed using the new format described above. +Any other input (i.e. non-P2PKH address format) must be signed using the new format described above. === Signing === @@ -174,10 +135,6 @@ Given the P2PKH address <code>a</code>, the message <code>m</code>, the compact This specification is backwards compatible with the legacy signmessage/verifymessage specification through the special case as described above. -== Rationale == - -<references/> - == Reference implementation == # Pull request to Bitcoin Core: https://github.com/bitcoin/bitcoin/pull/16440 @@ -228,6 +185,8 @@ All of the above, plus (subject to change): == Test vectors == +(TODO: update test vectors, which are based on previous iteration where signature proofs contained additional data) + == Native segwit test vector == <pre> diff --git a/bip-0325.mediawiki b/bip-0325.mediawiki index 51ec634..4b45030 100644 --- a/bip-0325.mediawiki +++ b/bip-0325.mediawiki @@ -26,36 +26,70 @@ A new type of test network would be more suitable for integration testing by org A new type of network ("signet"), which takes an additional consensus parameter called the challenge (scriptPubKey). The challenge can be a simple pubkey (P2PKH style), or a k-of-n multisig, or any other script you would want. -The witness commitment of the coinbase transaction is extended to include a secondary commitment (the signature/solution): +The witness commitment of the coinbase transaction is extended to include a secondary commitment (the signature/solution) of either: - 1-4 bytes - Push the following (x + 4) bytes + 1-5 bytes - Push the following (4 + x + y) bytes 4 bytes - Signet header (0xecc7daa2) - x bytes - Solution (sigScript) + x bytes - scriptSig + y bytes - scriptWitness -Any push operations that do not start with the 4 byte signet header are ignored. Multiple push operations with the 4 byte signet header are ignored except for the first entry. +The scriptSig is serialized by first encoding its length as CompactSize. If the scriptWitness is empty, it is encoded as 0 bytes, otherwise it is encoded in the usual way (see BIP 141 "witness" encoding). -Any signature operations contained within the challenge use SHA256d(modifiedBlockHash), i.e. the double-SHA256 digest of the following data as the sighash: +Any push operations that do not start with the 4 byte Signet header are ignored. Multiple push operations with the 4 byte Signet header are ignored except for the first instance of the header. -{|class="wikitable" style="text-align: center;" -|- -!Type -!Size -!Name -|- -|Int32||4||nVersion -|- -|Uint256||32||hashPrevBlock -|- -|Uint256||32||modifiedMerkleRoot -|- -|Uint32||4||nTime -|- -|Uint32||4||nBits -|} +To sign the block or verify a block signature, two virtual transactions, each with a single input and output are constructed from the block as follows. -The <code>modifiedMerkleRoot</code> hash is obtained by generating the merkle root of the block transactions, with the coinbase witness commitment as is, without the signet extension. This means the merkle root of the block is different from the merkle root in the signet commitment. This is needed, because the signature can never be included in the very message (in this case, a block) that is being signed. Apart from the signature, to facilitate block generation (mining), the block nonce value is the only other component of the block that the signet signature does not commit to. When grinding proof of work, the extended nonce cannot be used as it would invalidate the signature. Instead, simply resigning the same (or an updated) block will give a new search space. +The "to_spend" transaction is: -A block is considered fully validated if the above commitment is found, and its solution is valid. It is recommended that this verification is done directly before or after the witness commitment verification, as the data required to do both is approximately the same. + nVersion = 0 + nLockTime = 0 + vin[0].prevout.hash = 0000...000 + vin[0].prevout.n = 0xFFFFFFFF + vin[0].nSequence = 0 + vin[0].scriptSig = OP_0 PUSH72[ block_data ] + vin[0].scriptWitness = [] + vout[0].nValue = 0 + vout[0].scriptPubKey = signet_challenge + +where block_data is the serialization of the block's nVersion, hashPrevBlock, signet_merkle_root, and nTime. The <code>signet_merkle_root</code> is obtained by generating the merkle root of the block transactions, after modifying the coinbase witness commitment by replacing the signet solution with an empty solution (that is, the witness commitment includes a four byte push of the Signet header with no additional solution data, and no prior pushes beginning with the Signet header). This means the merkle root of the block is different from the merkle root in the signet commitment. This is needed, because the signature can never be included in the very message (in this case, a block) that is being signed. + +The "to_sign" transaction is: + + nVersion = 0 + nLockTime = 0 + vin[0].prevout.hash = to_spend.txid + vin[0].prevout.n = 0 + vin[0].nSequence = 0 + vout[0].nValue = 0 + vout[0].scriptPubKey = signet_challenge + +The scriptSig and/or scriptWitness for <code>vin[0]</code> are filled in from the Signet header push above. + +To simplify block generation (mining), the signature also does not commit to the block nonce value, so that rolling the nonce to generate proof-of-work does not also require regenerating signatures. When grinding proof of work, the extended nonce cannot be used as it would invalidate the signature. Instead, simply resigning the same (or an updated) block will give a new search space. + +A block is considered fully validated only if the to_sign transaction is a valid spend of the to_spend transaction. It is recommended that this verification is done directly before or after the witness commitment verification, as the data required to do both is approximately the same. + +There is one other acceptable special case: if a block's challenge is e.g. `OP_TRUE` (`0x51`), where an empty solution would result in success, the block is also considered valid if the signet commitment is absent. + +== Genesis Block and Message Start == + +The genesis block is the same for all signet networks, whereas the message start is defined as the first four bytes of the sha256d of the challenge script as a single data push (see below). + +=== Genesis Block === + +* Time stamp: 1534313275 +* Nonce: 100123 +* Difficulty: 1e2adc28 + +The resulting genesis block hash is 0000032d7f67af9ec7b7152aea0fe7c95b9804ff973265e252f245e0ae61799d, and the block hex is 0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a3bc3735b28dc2a1e1b8701000101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000. + +=== Message Start === + +The message start is defined as the first four bytes of the sha256d of the challenge script, as a single push (i.e. prefixed with the challenge script length). Example: + +* Challenge script = 512103ad5e0edad18cb1f0fc0d28a3d4f1f3e445640337489abb10404f2d1e086be43051ae +* Sha256d(len || challenge script) = sha256d(25512103ad...51ae) = 7ec653a59b1912f9db10da2c461ed827d48f9404d5ef0346a6c94aadd4203646 +* First four bytes = the message start = 7ec653a5 == Compatibility == @@ -69,7 +103,7 @@ Other software need not add block signature validation code that they will not u == Reference implementation == -Pull request at https://github.com/bitcoin/bitcoin/pull/16411 +Pull request at https://github.com/bitcoin/bitcoin/pull/18267 == Acknowledgements == diff --git a/bip-0339.mediawiki b/bip-0339.mediawiki new file mode 100644 index 0000000..806ba1c --- /dev/null +++ b/bip-0339.mediawiki @@ -0,0 +1,59 @@ +<pre> + BIP: 339 + Layer: Peer Services + Title: WTXID-based transaction relay + Author: Suhas Daftuar <sdaftuar@chaincode.com> + Comments-Summary: No comments yet. + Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0339 + Status: Draft + Type: Standards Track + Created: 2020-02-03 + License: BSD-2-Clause +</pre> + +==Abstract== + +This BIP describes two changes to the p2p protocol to support transaction relay +based on the BIP 141 wtxid of a transaction, rather than its txid. + +==Motivation== + +Historically, the inv messages sent on the Bitcoin peer-to-peer network to +announce transactions refer to transactions by their txid, which is a hash of +the transaction that does not include the witness (see BIP 141). This has been +the case even since Segregated Witness (BIP 141/143/144) has been adopted by +the network. + +Not committing to the witness in transaction announcements creates +inefficiencies: because a transaction's witness can be malleated without +altering the txid, a node in receipt of a witness transaction that the node +does not accept will generally still download that same transaction when +announced by other peers. This is because the alternative -- of not downloading +a given txid after rejecting a transaction with that txid -- would allow a +third party to interfere with transaction relay by malleating a transaction's +witness and announcing the resulting invalid transaction to nodes, preventing +relay of the valid version of the transaction as well. + +We can eliminate this concern by using the wtxid in place of the txid when +announcing and fetching transactions. + +==Specification== + +# A new wtxidrelay message is added, which is defined as an empty message where pchCommand == "wtxidrelay". +# The protocol version of nodes implementing this BIP must be set to 70016 or higher. +# The wtxidrelay message MUST be sent in response to a version message from a peer whose protocol version is >= 70016 and prior to sending a verack. A wtxidrelay message received after a verack message MUST be ignored or treated as invalid. +# A new inv type MSG_WTX (0x00000005) is added, for use in both inv messages and getdata requests, indicating that the hash being referenced is a transaction's wtxid. In the case of getdata requests, MSG_WTX implies that the transaction being requested should be serialized with witness as well, as described in BIP 144. +# After a node has received a wtxidrelay message from a peer, the node MUST use the MSG_WTX inv type when announcing transactions to that peer. +# After a node has received a wtxidrelay message from a peer, the node SHOULD use a MSG_WTX getdata message to request any announced transactions. A node MAY still request transactions from that peer using MSG_TX getdata messages, such as for transactions not recently announced by that peer (like the parents of recently announced transactions). + +==Backward compatibility== + +As wtxid-based transaction relay is only enabled between peers that both support it, older clients remain fully compatible and interoperable after this change. + +==Implementation== + +https://github.com/bitcoin/bitcoin/pull/18044 + +==Copyright== + +This BIP is licensed under the 2-clause BSD license. diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index d2f92db..9502a69 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -2,7 +2,7 @@ BIP: 340 Title: Schnorr Signatures for secp256k1 Author: Pieter Wuille <pieter.wuille@gmail.com> - Jonas Nick <Jonas Nick <jonasd.nick@gmail.com> + Jonas Nick <jonasd.nick@gmail.com> Tim Ruffing <crypto@timruffing.de> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340 @@ -40,7 +40,7 @@ propose a new standard, a number of improvements not specific to Schnorr signatu made: * '''Signature encoding''': Instead of using [https://en.wikipedia.org/wiki/X.690#DER_encoding DER]-encoding for signatures (which are variable size, and up to 72 bytes), we can use a simple fixed 64-byte format. -* '''Public key encoding''': Instead of using ''compressed'' 33-byte encodings of elliptic curve points which are common in Bitcoin today, public keys in this proposal are encoded as 32 bytes. +* '''Public key encoding''': Instead of using [https://www.secg.org/sec1-v2.pdf ''compressed''] 33-byte encodings of elliptic curve points which are common in Bitcoin today, public keys in this proposal are encoded as 32 bytes. * '''Batch verification''': The specific formulation of ECDSA signatures that is standardized cannot be verified more efficiently in batch compared to individually, unless additional witness data is added. Changing the signature scheme offers an opportunity to address this. * '''Completely specified''': To be safe for usage in consensus systems, the verification algorithm must be completely specified at the byte level. This guarantees that nobody can construct a signature that is valid to some verifiers but not all. This is traditionally not a requirement for digital signature schemes, and the lack of exact specification for the DER parsing of ECDSA signatures has caused problems for Bitcoin [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-July/009697.html in the past], needing [[bip-0066.mediawiki|BIP66]] to address it. In this document we aim to meet this property by design. For batch verification, which is inherently non-deterministic as the verifier can choose their batches, this property implies that the outcome of verification may only differ from individual verifications with negligible probability, even to an attacker who intentionally tries to make batch- and non-batch verification differ. @@ -64,7 +64,7 @@ Since we would like to avoid the fragility that comes with short hashes, the ''e '''Key prefixing''' Using the verification rule above directly makes Schnorr signatures vulnerable to "related-key attacks" in which a third party can convert a signature ''(R, s)'' for public key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for public key ''P + a⋅G'' and the same message ''m'', for any given additive tweak ''a'' to the signing key. This would render signatures insecure when keys are generated using [[bip-0032.mediawiki#public-parent-key--public-child-key|BIP32's unhardened derivation]] and other methods that rely on additive tweaks to existing keys such as Taproot. -To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures; changing the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig multisignature scheme secure (see Applications below). +To protect against these attacks, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures which means that the public key is prefixed to the message in the challenge hash input. This changes the equation to ''s⋅G = R + hash(R || P || m)⋅P''. [https://eprint.iacr.org/2015/1135.pdf It can be shown] that key prefixing protects against related-key attacks with additive tweaks. In general, key prefixing increases robustness in multi-user settings, e.g., it seems to be a requirement for proving the MuSig multisignature scheme secure (see Applications below). We note that key prefixing is not strictly necessary for transaction signatures as used in Bitcoin currently, because signed transactions indirectly commit to the public keys already, i.e., ''m'' contains a commitment to ''pk''. However, this indirect commitment should not be relied upon because it may change with proposals such as SIGHASH_NOINPUT ([[bip-0118.mediawiki|BIP118]]), and would render the signature scheme unsuitable for other purposes than signing transactions, e.g., [https://bitcoin.org/en/developer-reference#signmessage signing ordinary messages]. @@ -78,16 +78,11 @@ Using the first option would be slightly more efficient for verification (around '''Implicit Y coordinates''' In order to support efficient verification and batch verification, the Y coordinate of ''P'' and of ''R'' cannot be ambiguous (every valid X coordinate has two possible Y coordinates). We have a choice between several options for symmetry breaking: # Implicitly choosing the Y coordinate that is in the lower half. # Implicitly choosing the Y coordinate that is even<ref>Since ''p'' is odd, negation modulo ''p'' will map even numbers to odd numbers and the other way around. This means that for a valid X coordinate, one of the corresponding Y coordinates will be even, and the other will be odd.</ref>. -# Implicitly choosing the Y coordinate that is a quadratic residue (has a square root modulo the field size, or "is a square" for short)<ref>A product of two numbers is a square when either both or none of the factors are squares. As ''-1'' is not a square modulo secp256k1's field size ''p'', and the two Y coordinates corresponding to a given X coordinate are each other's negation, this means exactly one of the two must be a square.</ref>. +# Implicitly choosing the Y coordinate that is a quadratic residue (i.e. has a square root modulo ''p''). -In the case of ''R'' the third option is slower at signing time but a bit faster to verify, as it is possible to directly compute whether the Y coordinate is a square when the points are represented in -[https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates Jacobian coordinates] (a common optimization to avoid modular inverses -for elliptic curve operations). The two other options require a possibly -expensive conversion to affine coordinates first. This would even be the case if the sign or oddness were explicitly coded (option 2 in the list above). We therefore choose option 3. +The second option offers the greatest compatibility with existing key generation systems, where the standard 33-byte compressed public key format consists of a byte indicating the oddness of the Y coordinate, plus the full X coordinate. To avoid gratuitous incompatibilities, we pick that option for ''P'', and thus our X-only public keys become equivalent to a compressed public key that is the X-only key prefixed by the byte 0x02. For consistency, the same is done for ''R''<ref>An earlier version of this draft used the third option instead, based on a belief that this would in general trade signing efficiency for verification efficiency. When using Jacobian coordinates, a common optimization in ECC implementations, it is possible to determine if a Y coordinate is a quadratic residue by computing the Legendre symbol, without converting to affine coordinates first (which needs a modular inversion). As modular inverses and Legendre symbols have similar [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-August/018081.html performance] in practice, this trade-off is not worth it.</ref>. -For ''P'' the speed of signing and verification does not significantly differ between any of the three options because affine coordinates of the point have to be computed anyway. For consistency reasons we choose the same option as for ''R''. The signing algorithm ensures that the signature is valid under the correct public key by negating the secret key if necessary. - -Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is a square by negating the point if necessary. This is just a subtraction of field elements and not an elliptic curve operation<ref>This can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is not a square. A proof sketch can be found [https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 here].</ref>. +Despite halving the size of the set of valid public keys, implicit Y coordinates are not a reduction in security. Informally, if a fast algorithm existed to compute the discrete logarithm of an X-only public key, then it could also be used to compute the discrete logarithm of a full public key: apply it to the X coordinate, and then optionally negate the result. This shows that breaking an X-only public key can be at most a small constant term faster than breaking a full one.<ref>This can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is odd. A proof sketch can be found [https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 here].</ref>. '''Tagged Hashes''' Cryptographic hash functions are used for multiple purposes in the specification below and in Bitcoin in general. To make sure hashes used in one context can't be reinterpreted in another one, hash functions can be tweaked with a context-dependent tag name, in such a way that collisions across contexts can be assumed to be infeasible. Such collisions obviously can not be ruled out completely, but only for schemes using tagging with a unique name. As for other schemes collisions are at least less likely with tagging than without. @@ -95,11 +90,11 @@ For example, without tagged hashing a BIP340 signature could also be valid for a This proposal suggests to include the tag by prefixing the hashed data with ''SHA256(tag) || SHA256(tag)''. Because this is a 64-byte long context-specific constant and the ''SHA256'' block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization. -'''Final scheme''' As a result, our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is a square and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is a square. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''. +'''Final scheme''' As a result, our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is even and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is even. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''. === Specification === -The following conventions are used, with constants as defined for [https://www.secg.org/sec2-v2.pdf secp256k1]: +The following conventions are used, with constants as defined for [https://www.secg.org/sec2-v2.pdf secp256k1]. We note that adapting this specification to other elliptic curves is not straightforward and can result in an insecure scheme<ref>Among other pitfalls, using the specification with a curve whose order is not close to the size of the range of the nonce derivation function is insecure.</ref>. * Lowercase variables represent integers or byte arrays. ** The constant ''p'' refers to the field size, ''0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F''. ** The constant ''n'' refers to the curve order, ''0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141''. @@ -111,36 +106,33 @@ The following conventions are used, with constants as defined for [https://www.s ** [https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication Multiplication (⋅) of an integer and a point] refers to the repeated application of the group operation. * Functions and operations: ** ''||'' refers to byte array concatenation. -** The function ''x[i:j]'', where ''x'' is a byte array, returns a ''(j - i)''-byte array with a copy of the ''i''-th byte (inclusive) to the ''j''-th byte (exclusive) of ''x''. +** The function ''x[i:j]'', where ''x'' is a byte array and ''i, j ≥ 0'', returns a ''(j - i)''-byte array with a copy of the ''i''-th byte (inclusive) to the ''j''-th byte (exclusive) of ''x''. ** The function ''bytes(x)'', where ''x'' is an integer, returns the 32-byte encoding of ''x'', most significant byte first. ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))''. ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''. -** The function ''is_square(x)'', where ''x'' is an integer, returns whether or not ''x'' is a quadratic residue modulo ''p''. Since ''p'' is prime, it is equivalent to the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(x / p) = x<sup>(p-1)/2</sup> mod p'' being equal to ''1''<ref>For points ''P'' on the secp256k1 curve it holds that ''y(P)<sup>(p-1)/2</sup> ≠ 0 mod p''.</ref>. -** The function ''has_square_y(P)'', where ''P'' is a point, is defined as ''not is_infinite(P) and is_square(y(P))''<ref>For points ''P'' on the secp256k1 curve it holds that ''has_square_y(P) = not has_square_y(-P)''.</ref>. +** The function ''has_even_y(P)'', where ''P'' is a point, returns ''y(P) mod 2 = 0''. ** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x''<ref> - Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''. -</ref> and ''has_square_y(P)''<ref> - If ''P := lift_x(x)'' does not fail, then ''y := y(P) = c<sup>(p+1)/4</sup> mod p'' is square. Proof: If ''lift_x'' does not fail, ''y'' is a square root of ''c'' and therefore the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(c / p)'' is ''c<sup>(p-1)/2</sup> = 1 mod p''. Because the Legendre symbol ''(y / p)'' is ''y<sup>(p-1)/2</sup> mod p = c<sup>((p+1)/4)((p-1)/2)</sup> mod p = 1<sup>((p+1)/4)</sup> mod p = 1 mod p'', ''y'' is square. -</ref>, or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: + Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: *** Let ''c = x<sup>3</sup> + 7 mod p''. *** Let ''y = c<sup>(p+1)/4</sup> mod p''. *** Fail if ''c ≠ y<sup>2</sup> mod p''. -*** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'', or fail if no such point exists. -** The function ''point(x)'', where ''x'' is a 32-byte array, returns the point ''P = lift_x(int(x))''. +*** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'' if ''y mod 2 = 0'' or ''y(P) = p-y'' otherwise. ** The function ''hash<sub>tag</sub>(x)'' where ''tag'' is a UTF-8 encoded tag name and ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)''. ==== Public Key Generation ==== Input: -* The secret key ''sk'': a 32-byte array, generated uniformly at random +* The secret key ''sk'': a 32-byte array, freshly generated uniformly at random The algorithm ''PubKey(sk)'' is defined as: -* Let ''d = int(sk)''. -* Fail if ''d = 0'' or ''d ≥ n''. -* Return ''bytes(d⋅G)''. +* Let ''d' = int(sk)''. +* Fail if ''d' = 0'' or ''d' ≥ n''. +* Return ''bytes(d'⋅G)''. Note that we use a very different public key format (32 bytes) than the ones used by existing systems (which typically use elliptic curve points as public keys, or 33-byte or 65-byte encodings of them). A side effect is that ''PubKey(sk) = PubKey(bytes(n - int(sk))'', so every public key has two corresponding secret keys. +==== Public Key Conversion ==== + As an alternative to generating keys randomly, it is also possible and safe to repurpose existing key generation algorithms for ECDSA in a compatible way. The secret keys constructed by such an algorithm can be used as ''sk'' directly. The public keys constructed by such an algorithm (assuming they use the 33-byte compressed encoding) need to be converted by dropping the first byte. Specifically, [[bip-0032.mediawiki|BIP32]] and schemes built on top of it remain usable. ==== Default Signing ==== @@ -148,33 +140,37 @@ As an alternative to generating keys randomly, it is also possible and safe to r Input: * The secret key ''sk'': a 32-byte array * The message ''m'': a 32-byte array +* Auxiliary random data ''a'': a 32-byte array The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' -* Let ''d = d' '' if ''has_square_y(P)'', otherwise let ''d = n - d' ''. -* Let ''rand = hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m)''. +* Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. +* Let ''t'' be the byte-wise xor of ''bytes(d)'' and ''hash<sub>BIP0340/aux</sub>(a)''<ref>The auxiliary random data is hashed (with a unique tag) as a precaution against situations where the randomness may be correlated with the private key itself. It is xored with the private key (rather than combined with it in a hash) to reduce the number of operations exposed to the actual secret key.</ref>. +* Let ''rand = hash<sub>BIP0340/nonce</sub>(t || bytes(P) || m)''<ref>Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons.</ref>. * Let ''k' = int(rand) mod n''<ref>Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2<sup>256</sup>'' that this bias is not observable (''1 - n / 2<sup>256</sup>'' is around ''1.27 * 2<sup>-128</sup>'').</ref>. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. -* Let ''k = k' '' if ''has_square_y(R)'', otherwise let ''k = n - k' ''. -* Let ''e = int(hash<sub>BIPSchnorr</sub>(bytes(R) || bytes(P) || m)) mod n''. -* Return the signature ''bytes(R) || bytes((k + ed) mod n)''. +* Let ''k = k' '' if ''has_even_y(R)'', otherwise let ''k = n - k' ''. +* Let ''e = int(hash<sub>BIP0340/challenge</sub>(bytes(R) || bytes(P) || m)) mod n''. +* Let ''sig = bytes(R) || bytes((k + ed) mod n)''. +* If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abort<ref>Verifying the signature before leaving the signer prevents random or attacker provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended, but can be omitted if the computation cost is prohibitive.</ref>. +* Return the signature ''sig''. -==== Alternative Signing ==== +The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. Using 32 bytes of randomness is optimal. If obtaining randomness is expensive, 16 random bytes can be padded with 16 null bytes to obtain a 32-byte array. If randomness is not available at all at signing time, a simple counter wide enough to not repeat in practice (e.g., 64 bits or wider) and padded with null bytes to a 32 byte-array can be used, or even the constant array with 32 null bytes. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. -It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' - -'''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hash<sub>BIPSchnorrDerive</sub>''. This will change the corresponding line in the signing algorithm to ''rand = hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. +==== Alternative Signing ==== -'''Verifying the signing output''' To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. '''If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.''' +It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' For nonces without randomness this implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. '''Nonce exfiltration protection''' It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection. '''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2018/068 MuSig], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below). '''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).''' +'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key corresponding to the secret key may already be known, making it easy to evaluate ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than recalculating the public key from the secret key. However, if this optimization is used and additionally the signature verification at the end of the signing algorithm is dropped for increased efficiency, signers must ensure the public key is correctly calculated and not taken from untrusted sources. + ==== Verification ==== Input: @@ -183,17 +179,17 @@ Input: * A signature ''sig'': a 64-byte array The algorithm ''Verify(pk, m, sig)'' is defined as: -* Let ''P = point(pk)''; fail if ''point(pk)'' fails. +* Let ''P = lift_x(int(pk))''; fail if that fails. * Let ''r = int(sig[0:32])''; fail if ''r ≥ p''. * Let ''s = int(sig[32:64])''; fail if ''s ≥ n''. -* Let ''e = int(hash<sub>BIPSchnorr</sub>(bytes(r) || bytes(P) || m)) mod n''. +* Let ''e = int(hash<sub>BIP0340/challenge</sub>(bytes(r) || bytes(P) || m)) mod n''. * Let ''R = s⋅G - e⋅P''. -* Fail if ''not has_square_y(R)'' or ''x(R) ≠ r''. +* Fail if ''not has_even_y(R)'' or ''x(R) ≠ r''. * Return success iff no failure occurred before reaching this point. For every valid secret key ''sk'' and message ''m'', ''Verify(PubKey(sk),m,Sign(sk,m))'' will succeed. -Note that the correctness of verification relies on the fact that ''point(pk)'' always returns a point with a square Y coordinate. A hypothetical verification algorithm that treats points as public keys, and takes the point ''P'' directly as input would fail any time a point with non-square Y is used. While it is possible to correct for this by negating points with non-square Y coordinate before further processing, this would result in a scheme where every (message, signature) pair is valid for two public keys (a type of malleability that exists for ECDSA as well, but we don't wish to retain). We avoid these problems by treating just the X coordinate as public key. +Note that the correctness of verification relies on the fact that ''lift_x'' always returns a point with an even Y coordinate. A hypothetical verification algorithm that treats points as public keys, and takes the point ''P'' directly as input would fail any time a point with odd Y is used. While it is possible to correct for this by negating points with odd Y coordinate before further processing, this would result in a scheme where every (message, signature) pair is valid for two public keys (a type of malleability that exists for ECDSA as well, but we don't wish to retain). We avoid these problems by treating just the X coordinate as public key. ==== Batch Verification ==== @@ -206,26 +202,16 @@ Input: The algorithm ''BatchVerify(pk<sub>1..u</sub>, m<sub>1..u</sub>, sig<sub>1..u</sub>)'' is defined as: * Generate ''u-1'' random integers ''a<sub>2...u</sub>'' in the range ''1...n-1''. They are generated deterministically using a [https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator CSPRNG] seeded by a cryptographic hash of all inputs of the algorithm, i.e. ''seed = seed_hash(pk<sub>1</sub>..pk<sub>u</sub> || m<sub>1</sub>..m<sub>u</sub> || sig<sub>1</sub>..sig<sub>u</sub> )''. A safe choice is to instantiate ''seed_hash'' with SHA256 and use [https://tools.ietf.org/html/rfc8439 ChaCha20] with key ''seed'' as a CSPRNG to generate 256-bit integers, skipping integers not in the range ''1...n-1''. * For ''i = 1 .. u'': -** Let ''P<sub>i</sub> = point(pk<sub>i</sub>)''; fail if ''point(pk<sub>i</sub>)'' fails. +** Let ''P<sub>i</sub> = lift_x(int(pk<sub>i</sub>))''; fail if it fails. ** Let ''r<sub>i</sub> = int(sig<sub>i</sub>[0:32])''; fail if ''r<sub>i</sub> ≥ p''. ** Let ''s<sub>i</sub> = int(sig<sub>i</sub>[32:64])''; fail if ''s<sub>i</sub> ≥ n''. -** Let ''e<sub>i</sub> = int(hash<sub>BIPSchnorr</sub>(bytes(r<sub>i</sub>) || bytes(P<sub>i</sub>) || m<sub>i</sub>)) mod n''. +** Let ''e<sub>i</sub> = int(hash<sub>BIP0340/challenge</sub>(bytes(r<sub>i</sub>) || bytes(P<sub>i</sub>) || m<sub>i</sub>)) mod n''. ** Let ''R<sub>i</sub> = lift_x(r<sub>i</sub>)''; fail if ''lift_x(r<sub>i</sub>)'' fails. * Fail if ''(s<sub>1</sub> + a<sub>2</sub>s<sub>2</sub> + ... + a<sub>u</sub>s<sub>u</sub>)⋅G ≠ R<sub>1</sub> + a<sub>2</sub>⋅R<sub>2</sub> + ... + a<sub>u</sub>⋅R<sub>u</sub> + e<sub>1</sub>⋅P<sub>1</sub> + (a<sub>2</sub>e<sub>2</sub>)⋅P<sub>2</sub> + ... + (a<sub>u</sub>e<sub>u</sub>)⋅P<sub>u</sub>''. * Return success iff no failure occurred before reaching this point. If all individual signatures are valid (i.e., ''Verify'' would return success for them), ''BatchVerify'' will always return success. If at least one signature is invalid, ''BatchVerify'' will return success with at most a negligible probability. -=== Optimizations === - -Many techniques are known for optimizing elliptic curve implementations. Several of them apply here, but are out of scope for this document. Two are listed below however, as they are relevant to the design decisions: - -'''Squareness testing''' The function ''is_square(x)'' is defined as above, but can be computed more efficiently using an [https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol extended GCD algorithm]. - -'''Jacobian coordinates''' Elliptic Curve operations can be implemented more efficiently by using [https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates Jacobian coordinates]. Elliptic Curve operations implemented this way avoid many intermediate modular inverses (which are computationally expensive), and the scheme proposed in this document is in fact designed to not need any inversions at all for verification. When operating on a point ''P'' with Jacobian coordinates ''(x,y,z)'' which is not the point at infinity and for which ''x(P)'' is defined as ''x / z<sup>2</sup>'' and ''y(P)'' is defined as ''y / z<sup>3</sup>'': -* ''has_square_y(P)'' can be implemented as ''is_square(yz mod p)''. -* ''x(P) ≠ r'' can be implemented as ''(0 ≤ r < p) and (x ≠ z<sup>2</sup>r mod p)''. - == Applications == There are several interesting applications beyond simple signatures. @@ -235,7 +221,7 @@ While recent academic papers claim that they are also possible with ECDSA, conse By means of an interactive scheme such as [https://eprint.iacr.org/2018/068 MuSig], participants can aggregate their public keys into a single public key which they can jointly sign for. This allows ''n''-of-''n'' multisignatures which, from a verifier's perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus ''CHECKMULTISIG'' or other means. -Moreover, Schnorr signatures are compatible with [https://web.archive.org/web/20031003232851/http://www.research.ibm.com/security/dkg.ps distributed key generation], which enables interactive threshold signatures schemes, e.g., the schemes described by [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps Stinson and Strobl (2001)] or [https://web.archive.org/web/20060911151529/http://theory.lcs.mit.edu/~stasio/Papers/gjkr03.pdf Genaro, Jarecki and Krawczyk (2003)]. These protocols make it possible to realize ''k''-of-''n'' threshold signatures, which ensure that any subset of size ''k'' of the set of ''n'' signers can sign but no subset of size less than ''k'' can produce a valid Schnorr signature. However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case ''k-1 < n/2'', are not secure when used concurrently in multiple sessions, or require a reliable broadcast mechanism to be secure. Further research is necessary to improve this situation. +Moreover, Schnorr signatures are compatible with [https://web.archive.org/web/20031003232851/http://www.research.ibm.com/security/dkg.ps distributed key generation], which enables interactive threshold signatures schemes, e.g., the schemes described by [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps Stinson and Strobl (2001)] or [https://web.archive.org/web/20060911151529/http://theory.lcs.mit.edu/~stasio/Papers/gjkr03.pdf Gennaro, Jarecki and Krawczyk (2003)]. These protocols make it possible to realize ''k''-of-''n'' threshold signatures, which ensure that any subset of size ''k'' of the set of ''n'' signers can sign but no subset of size less than ''k'' can produce a valid Schnorr signature. However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case ''k-1 < n/2'', are not secure when used concurrently in multiple sessions, or require a reliable broadcast mechanism to be secure. Further research is necessary to improve this situation. === Adaptor Signatures === diff --git a/bip-0340/reference.py b/bip-0340/reference.py index f2a944f..5d17db5 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -1,6 +1,16 @@ +from typing import Tuple, Optional, Any import hashlib import binascii +# Set DEBUG to True to get a detailed debug output including +# intermediate values during key generation, signing, and +# verification. This is implemented via calls to the +# debug_print_vars() function. +# +# If you want to print values on an individual basis, use +# the pretty() function, e.g., print(pretty(foo)). +DEBUG = False + p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 @@ -8,50 +18,55 @@ n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # represented by the None keyword. G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) +Point = Tuple[int, int] + # This implementation can be sped up by storing the midstate after hashing # tag_hash instead of rehashing it all the time. -def tagged_hash(tag, msg): +def tagged_hash(tag: str, msg: bytes) -> bytes: tag_hash = hashlib.sha256(tag.encode()).digest() return hashlib.sha256(tag_hash + tag_hash + msg).digest() -def is_infinity(P): +def is_infinity(P: Optional[Point]) -> bool: return P is None -def x(P): +def x(P: Point) -> int: return P[0] -def y(P): +def y(P: Point) -> int: return P[1] -def point_add(P1, P2): - if (P1 is None): +def point_add(P1: Optional[Point], P2: Optional[Point]) -> Optional[Point]: + if P1 is None: return P2 - if (P2 is None): + if P2 is None: return P1 - if (x(P1) == x(P2) and y(P1) != y(P2)): + if (x(P1) == x(P2)) and (y(P1) != y(P2)): return None - if (P1 == P2): + if P1 == P2: lam = (3 * x(P1) * x(P1) * pow(2 * y(P1), p - 2, p)) % p else: lam = ((y(P2) - y(P1)) * pow(x(P2) - x(P1), p - 2, p)) % p x3 = (lam * lam - x(P1) - x(P2)) % p return (x3, (lam * (x(P1) - x3) - y(P1)) % p) -def point_mul(P, n): +def point_mul(P: Optional[Point], n: int) -> Optional[Point]: R = None for i in range(256): - if ((n >> i) & 1): + if (n >> i) & 1: R = point_add(R, P) P = point_add(P, P) return R -def bytes_from_int(x): +def bytes_from_int(x: int) -> bytes: return x.to_bytes(32, byteorder="big") -def bytes_from_point(P): +def bytes_from_point(P: Point) -> bytes: return bytes_from_int(x(P)) -def point_from_bytes(b): +def xor_bytes(b0: bytes, b1: bytes) -> bytes: + return bytes(x ^ y for (x, y) in zip(b0, b1)) + +def lift_x(b: bytes) -> Optional[Point]: x = int_from_bytes(b) if x >= p: return None @@ -59,94 +74,109 @@ def point_from_bytes(b): y = pow(y_sq, (p + 1) // 4, p) if pow(y, 2, p) != y_sq: return None - return [x, y] + return (x, y if y & 1 == 0 else p-y) -def int_from_bytes(b): +def int_from_bytes(b: bytes) -> int: return int.from_bytes(b, byteorder="big") -def hash_sha256(b): +def hash_sha256(b: bytes) -> bytes: return hashlib.sha256(b).digest() -def is_square(x): - return pow(x, (p - 1) // 2, p) == 1 - -def has_square_y(P): - return not is_infinity(P) and is_square(y(P)) +def has_even_y(P: Point) -> bool: + return y(P) % 2 == 0 -def pubkey_gen(seckey): - x = int_from_bytes(seckey) - if not (1 <= x <= n - 1): +def pubkey_gen(seckey: bytes) -> bytes: + d0 = int_from_bytes(seckey) + if not (1 <= d0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') - P = point_mul(G, x) + P = point_mul(G, d0) + assert P is not None return bytes_from_point(P) -def schnorr_sign(msg, seckey0): +def schnorr_sign(msg: bytes, seckey: bytes, aux_rand: bytes) -> bytes: if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') - seckey0 = int_from_bytes(seckey0) - if not (1 <= seckey0 <= n - 1): + d0 = int_from_bytes(seckey) + if not (1 <= d0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') - P = point_mul(G, seckey0) - seckey = seckey0 if has_square_y(P) else n - seckey0 - k0 = int_from_bytes(tagged_hash("BIPSchnorrDerive", bytes_from_int(seckey) + msg)) % n + if len(aux_rand) != 32: + raise ValueError('aux_rand must be 32 bytes instead of %i.' % len(aux_rand)) + P = point_mul(G, d0) + assert P is not None + d = d0 if has_even_y(P) else n - d0 + t = xor_bytes(bytes_from_int(d), tagged_hash("BIP0340/aux", aux_rand)) + k0 = int_from_bytes(tagged_hash("BIP0340/nonce", t + bytes_from_point(P) + msg)) % n if k0 == 0: raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) - k = n - k0 if not has_square_y(R) else k0 - e = int_from_bytes(tagged_hash("BIPSchnorr", bytes_from_point(R) + bytes_from_point(P) + msg)) % n - return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) - -def schnorr_verify(msg, pubkey, sig): + assert R is not None + k = n - k0 if not has_even_y(R) else k0 + e = int_from_bytes(tagged_hash("BIP0340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n + sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n) + debug_print_vars() + if not schnorr_verify(msg, bytes_from_point(P), sig): + raise RuntimeError('The created signature does not pass verification.') + return sig + +def schnorr_verify(msg: bytes, pubkey: bytes, sig: bytes) -> bool: if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') if len(pubkey) != 32: raise ValueError('The public key must be a 32-byte array.') if len(sig) != 64: raise ValueError('The signature must be a 64-byte array.') - P = point_from_bytes(pubkey) - if (P is None): - return False + P = lift_x(pubkey) r = int_from_bytes(sig[0:32]) s = int_from_bytes(sig[32:64]) - if (r >= p or s >= n): + if (P is None) or (r >= p) or (s >= n): + debug_print_vars() return False - e = int_from_bytes(tagged_hash("BIPSchnorr", sig[0:32] + pubkey + msg)) % n + e = int_from_bytes(tagged_hash("BIP0340/challenge", sig[0:32] + pubkey + msg)) % n R = point_add(point_mul(G, s), point_mul(P, n - e)) - if R is None or not has_square_y(R) or x(R) != r: + if (R is None) or (not has_even_y(R)) or (x(R) != r): + debug_print_vars() return False + debug_print_vars() return True # # The following code is only used to verify the test vectors. # import csv +import os +import sys -def test_vectors(): +def test_vectors() -> bool: all_passed = True - with open('test-vectors.csv', newline='') as csvfile: + with open(os.path.join(sys.path[0], 'test-vectors.csv'), newline='') as csvfile: reader = csv.reader(csvfile) reader.__next__() for row in reader: - (index, seckey, pubkey, msg, sig, result, comment) = row - pubkey = bytes.fromhex(pubkey) - msg = bytes.fromhex(msg) - sig = bytes.fromhex(sig) - result = result == 'TRUE' - print('\nTest vector #%-3i: ' % int(index)) - if seckey != '': - seckey = bytes.fromhex(seckey) + (index, seckey_hex, pubkey_hex, aux_rand_hex, msg_hex, sig_hex, result_str, comment) = row + pubkey = bytes.fromhex(pubkey_hex) + msg = bytes.fromhex(msg_hex) + sig = bytes.fromhex(sig_hex) + result = result_str == 'TRUE' + print('\nTest vector', ('#' + index).rjust(3, ' ') + ':') + if seckey_hex != '': + seckey = bytes.fromhex(seckey_hex) pubkey_actual = pubkey_gen(seckey) if pubkey != pubkey_actual: print(' * Failed key generation.') print(' Expected key:', pubkey.hex().upper()) print(' Actual key:', pubkey_actual.hex().upper()) - sig_actual = schnorr_sign(msg, seckey) - if sig == sig_actual: - print(' * Passed signing test.') - else: - print(' * Failed signing test.') - print(' Expected signature:', sig.hex().upper()) - print(' Actual signature:', sig_actual.hex().upper()) + aux_rand = bytes.fromhex(aux_rand_hex) + try: + sig_actual = schnorr_sign(msg, seckey, aux_rand) + if sig == sig_actual: + print(' * Passed signing test.') + else: + print(' * Failed signing test.') + print(' Expected signature:', sig.hex().upper()) + print(' Actual signature:', sig_actual.hex().upper()) + all_passed = False + except RuntimeError as e: + print(' * Signing test raised exception:', e) all_passed = False result_actual = schnorr_verify(msg, pubkey, sig) if result == result_actual: @@ -165,5 +195,29 @@ def test_vectors(): print('Some test vectors failed.') return all_passed +# +# The following code is only used for debugging +# +import inspect + +def pretty(v: Any) -> Any: + if isinstance(v, bytes): + return '0x' + v.hex() + if isinstance(v, int): + return pretty(bytes_from_int(v)) + if isinstance(v, tuple): + return tuple(map(pretty, v)) + return v + +def debug_print_vars() -> None: + if DEBUG: + current_frame = inspect.currentframe() + assert current_frame is not None + frame = current_frame.f_back + assert frame is not None + print(' Variables in function ', frame.f_code.co_name, ' at line ', frame.f_lineno, ':', sep='') + for var_name, var_val in frame.f_locals.items(): + print(' ' + var_name.rjust(11, ' '), '==', pretty(var_val)) + if __name__ == '__main__': test_vectors() diff --git a/bip-0340/test-vectors.csv b/bip-0340/test-vectors.csv index 3970803..a1a63e1 100644 --- a/bip-0340/test-vectors.csv +++ b/bip-0340/test-vectors.csv @@ -1,16 +1,16 @@ -index,secret key,public key,message,signature,verification result,comment
-0,0000000000000000000000000000000000000000000000000000000000000001,79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0000000000000000000000000000000000000000000000000000000000000000,528F745793E8472C0329742A463F59E58F3A3F1A4AC09C28F6F8514D4D0322A258BD08398F82CF67B812AB2C7717CE566F877C2F8795C846146978E8F04782AE,TRUE,
-1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,TRUE,
-2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,2D941B38E32624BF0AC7669C0971B990994AF6F9B18426BF4F4E7EC10E6CDF386CF646C6DDAFCFA7F1993EEB2E4D66416AEAD1DDAE2F22D63CAD901412D116C6,TRUE,
-3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,8BD2C11604B0A87A443FCC2E5D90E5328F934161B18864FB48CE10CB59B45FB9B5B2A0F129BD88F5BDC05D5C21E5C57176B913002335784F9777A24BD317CD36,TRUE,test fails if msg is reduced modulo p or n
-4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63EE374AC7FAE927D334CCB190F6FB8FD27A2DDC639CCEE46D43F113A4035A2C7F,TRUE,
-5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,public key not on the curve
-6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9935554D1AA5F0374E5CDAACB3925035C7C169B27C4426DF0A6B19AF3BAEAB138,FALSE,has_square_y(R) is false
-7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,10AC49A6A2EBF604189C5F40FC75AF2D42D77DE9A2782709B1EB4EAF1CFE9108D7003B703A3499D5E29529D39BA040A44955127140F81A8A89A96F992AC0FE79,FALSE,negated message
-8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E84BE9F4303C0B9913470532E6521A827951D39F5C631CFD98CE39AC4D7A5A83BA9,FALSE,negated s value
-9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,000000000000000000000000000000000000000000000000000000000000000099D2F0EBC2996808208633CD9926BF7EC3DAB73DAAD36E85B3040A698E6D1CE0,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0
-10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,000000000000000000000000000000000000000000000000000000000000000124E81D89F01304695CE943F7D5EBD00EF726A0864B4FF33895B4E86BEADC5456,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1
-11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D4160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,sig[0:32] is not an X coordinate on the curve
-12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F4160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,sig[0:32] is equal to field size
-13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E84FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order
-14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,public key is not a valid X coordinate because it exceeds the field size
+index,secret key,public key,aux_rand,message,signature,verification result,comment
+0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,0000000000000000000000000000000000000000000000000000000000000000,E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA821525F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0,TRUE,
+1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,0000000000000000000000000000000000000000000000000000000000000001,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE33418906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A,TRUE,
+2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,C87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,5831AAEED7B44BB74E5EAB94BA9D4294C49BCF2A60728D8B4C200F50DD313C1BAB745879A5AD954A72C45A91C3A51D3C7ADEA98D82F8481E0E1E03674A6F3FB7,TRUE,
+3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,7EB0509757E246F19449885651611CB965ECC1A187DD51B64FDA1EDC9637D5EC97582B9CB13DB3933705B32BA982AF5AF25FD78881EBB32771FC5922EFC66EA3,TRUE,test fails if msg is reduced modulo p or n
+4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C6376AFB1548AF603B3EB45C9F8207DEE1060CB71C04E80F593060B07D28308D7F4,TRUE,
+5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key not on the curve
+6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A14602975563CC27944640AC607CD107AE10923D9EF7A73C643E166BE5EBEAFA34B1AC553E2,FALSE,has_even_y(R) is false
+7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,1FA62E331EDBC21C394792D2AB1100A7B432B013DF3F6FF4F99FCB33E0E1515F28890B3EDB6E7189B630448B515CE4F8622A954CFE545735AAEA5134FCCDB2BD,FALSE,negated message
+8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769961764B3AA9B2FFCB6EF947B6887A226E8D7C93E00C5ED0C1834FF0D0C2E6DA6,FALSE,negated s value
+9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000000123DDA8328AF9C23A94C1FEECFD123BA4FB73476F0D594DCB65C6425BD186051,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0
+10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000017615FBAF5AE28864013C099742DEADB4DBA87F11AC6754F93780D5A1837CF197,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1
+11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is not an X coordinate on the curve
+12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is equal to field size
+13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order
+14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key is not a valid X coordinate because it exceeds the field size
diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index 195b61b..e5b8847 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -1,51 +1,92 @@ import sys from reference import * +def is_square(x): + return int(pow(x, (p - 1) // 2, p)) == 1 + +def has_square_y(P): + """Determine if P has a square Y coordinate. Used in an earlier draft of BIP340.""" + assert not is_infinity(P) + return is_square(P[1]) + def vector0(): - seckey = bytes_from_int(1) + seckey = bytes_from_int(3) msg = bytes_from_int(0) - sig = schnorr_sign(msg, seckey) + aux_rand = bytes_from_int(0) + sig = schnorr_sign(msg, seckey, aux_rand) pubkey = pubkey_gen(seckey) - # The point reconstructed from the public key has an even Y coordinate. - pubkey_point = point_from_bytes(pubkey) - assert(pubkey_point[1] & 1 == 0) + # We should have at least one test vector where the seckey needs to be + # negated and one where it doesn't. In this one the seckey doesn't need to + # be negated. + x = int_from_bytes(seckey) + P = point_mul(G, x) + assert(y(P) % 2 == 0) + + # For historical reasons (pubkey tiebreaker was squareness and not evenness) + # we should have at least one test vector where the the point reconstructed + # from the public key has a square and one where it has a non-square Y + # coordinate. In this one Y is non-square. + pubkey_point = lift_x(pubkey) + assert(not has_square_y(pubkey_point)) + + # For historical reasons (R tiebreaker was squareness and not evenness) + # we should have at least one test vector where the the point reconstructed + # from the R.x coordinate has a square and one where it has a non-square Y + # coordinate. In this one Y is non-square. + R = lift_x(sig[0:32]) + assert(not has_square_y(R)) - return (seckey, pubkey, msg, sig, "TRUE", None) + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) def vector1(): seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF) msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89) - sig = schnorr_sign(msg, seckey) - pubkey = pubkey_gen(seckey) + aux_rand = bytes_from_int(1) + + sig = schnorr_sign(msg, seckey, aux_rand) - # The point reconstructed from the public key has an odd Y coordinate. - pubkey_point = point_from_bytes(pubkey) - assert(pubkey_point[1] & 1 == 1) + # The point reconstructed from the R.x coordinate has a square Y coordinate. + R = lift_x(sig[0:32]) + assert(has_square_y(R)) - return (seckey, pubkey, msg, sig, "TRUE", None) + return (seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", None) def vector2(): seckey = bytes_from_int(0xC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9) - msg = bytes_from_int(0x5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C) - sig = schnorr_sign(msg, seckey) + msg = bytes_from_int(0x7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C) + aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906) + sig = schnorr_sign(msg, seckey, aux_rand) + + # The point reconstructed from the public key has a square Y coordinate. + pubkey = pubkey_gen(seckey) + pubkey_point = lift_x(pubkey) + assert(has_square_y(pubkey_point)) # This signature vector would not verify if the implementer checked the - # squareness of the X coordinate of R instead of the Y coordinate. - R = point_from_bytes(sig[0:32]) - assert(not is_square(R[0])) + # evenness of the X coordinate of R instead of the Y coordinate. + R = lift_x(sig[0:32]) + assert(R[0] % 2 == 1) - return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", None) + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) def vector3(): seckey = bytes_from_int(0x0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710) + + # Need to negate this seckey before signing + x = int_from_bytes(seckey) + P = point_mul(G, x) + assert(y(P) % 2 != 0) + msg = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) - sig = schnorr_sign(msg, seckey) - return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", "test fails if msg is reduced modulo p or n") + aux_rand = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + + sig = schnorr_sign(msg, seckey, aux_rand) + return (seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", "test fails if msg is reduced modulo p or n") # Signs with a given nonce. This can be INSECURE and is only INTENDED FOR # GENERATING TEST VECTORS. Results in an invalid signature if y(kG) is not -# square. +# even. def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k): if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') @@ -53,21 +94,22 @@ def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k): if not (1 <= seckey0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') P = point_mul(G, seckey0) - seckey = seckey0 if has_square_y(P) else n - seckey0 + seckey = seckey0 if has_even_y(P) else n - seckey0 R = point_mul(G, k) - e = int_from_bytes(tagged_hash("BIPSchnorr", bytes_from_point(R) + bytes_from_point(P) + msg)) % n + e = int_from_bytes(tagged_hash("BIP0340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) -# Creates a singature with a small x(R) by using k = 1/2 +# Creates a singature with a small x(R) by using k = -1/2 def vector4(): - one_half = 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 + one_half = n - 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 seckey = bytes_from_int(0x763758E5CBEEDEE4F7D3FC86F531C36578933228998226672F13C4F0EBE855EB) msg = bytes_from_int(0x4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703) sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, one_half) - return (None, pubkey_gen(seckey), msg, sig, "TRUE", None) + return (None, pubkey_gen(seckey), None, msg, sig, "TRUE", None) default_seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF) default_msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89) +default_aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906) # Public key is not on the curve def vector5(): @@ -75,38 +117,38 @@ def vector5(): # public key. seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey = bytes_from_int(0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34) - assert(point_from_bytes(pubkey) is None) + assert(lift_x(pubkey) is None) - return (None, pubkey, msg, sig, "FALSE", "public key not on the curve") + return (None, pubkey, None, msg, sig, "FALSE", "public key not on the curve") def vector6(): seckey = default_seckey msg = default_msg - k = 3 + k = 6 sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) - # Y coordinate of R is not a square + # Y coordinate of R is not even R = point_mul(G, k) - assert(not has_square_y(R)) + assert(not has_even_y(R)) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "has_square_y(R) is false") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "has_even_y(R) is false") def vector7(): seckey = default_seckey msg = int_from_bytes(default_msg) neg_msg = bytes_from_int(n - msg) - sig = schnorr_sign(neg_msg, seckey) - return (None, pubkey_gen(seckey), bytes_from_int(msg), sig, "FALSE", "negated message") + sig = schnorr_sign(neg_msg, seckey, default_aux_rand) + return (None, pubkey_gen(seckey), None, bytes_from_int(msg), sig, "FALSE", "negated message") def vector8(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) sig = sig[0:32] + bytes_from_int(n - int_from_bytes(sig[32:64])) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "negated s value") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "negated s value") def bytes_from_point_inf0(P): if P == None: @@ -125,7 +167,7 @@ def vector9(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0") def bytes_from_point_inf1(P): if P == None: @@ -144,7 +186,7 @@ def vector10(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[0:32] is an X @@ -152,14 +194,14 @@ def vector10(): def vector11(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace R's X coordinate with an X coordinate that's not on the curve x_not_on_curve = bytes_from_int(0x4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D) - assert(point_from_bytes(x_not_on_curve) is None) + assert(lift_x(x_not_on_curve) is None) sig = x_not_on_curve + sig[32:64] - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[0:32] is smaller @@ -167,12 +209,12 @@ def vector11(): def vector12(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace R's X coordinate with an X coordinate that's equal to field size sig = bytes_from_int(p) + sig[32:64] - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[0:32] is equal to field size") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is equal to field size") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[32:64] is smaller @@ -180,12 +222,12 @@ def vector12(): def vector13(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace s with a number that's equal to the curve order sig = sig[0:32] + bytes_from_int(n) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[32:64] is equal to curve order") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[32:64] is equal to curve order") # Test out of range pubkey # It's cryptographically impossible to create a test vector that fails if run @@ -197,16 +239,15 @@ def vector14(): # public key. seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) - + sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey_int = p + 1 pubkey = bytes_from_int(pubkey_int) - assert(point_from_bytes(pubkey) is None) + assert(lift_x(pubkey) is None) # If an implementation would reduce a given public key modulo p then the # pubkey would be valid - assert(point_from_bytes(bytes_from_int(pubkey_int % p)) is not None) + assert(lift_x(bytes_from_int(pubkey_int % p)) is not None) - return (None, pubkey, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") + return (None, pubkey, None, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") vectors = [ vector0(), @@ -227,14 +268,14 @@ vectors = [ ] # Converts the byte strings of a test vector into hex strings -def bytes_to_hex(seckey, pubkey, msg, sig, result, comment): - return (seckey.hex().upper() if seckey is not None else None, pubkey.hex().upper(), msg.hex().upper(), sig.hex().upper(), result, comment) +def bytes_to_hex(seckey, pubkey, aux_rand, msg, sig, result, comment): + return (seckey.hex().upper() if seckey is not None else None, pubkey.hex().upper(), aux_rand.hex().upper() if aux_rand is not None else None, msg.hex().upper(), sig.hex().upper(), result, comment) -vectors = list(map(lambda vector: bytes_to_hex(vector[0], vector[1], vector[2], vector[3], vector[4], vector[5]), vectors)) +vectors = list(map(lambda vector: bytes_to_hex(vector[0], vector[1], vector[2], vector[3], vector[4], vector[5], vector[6]), vectors)) def print_csv(vectors): writer = csv.writer(sys.stdout) - writer.writerow(("index", "secret key", "public key", "message", "signature", "verification result", "comment")) + writer.writerow(("index", "secret key", "public key", "aux_rand", "message", "signature", "verification result", "comment")) for (i,v) in enumerate(vectors): writer.writerow((i,)+v) diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index ec11f6a..7ac5bf8 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -13,6 +13,7 @@ License: BSD-3-Clause Requires: 340 Post-History: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal + 2019-10-09: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017378.html [bitcoin-dev] Taproot updates </pre> ==Introduction== @@ -59,13 +60,13 @@ The following rules only apply when such an output is being spent. Any other out * Let ''q'' be the 32-byte array containing the witness program (the second push in the scriptPubKey) which represents a public key according to [[bip-0340.mediawiki#design|BIP340]]. * Fail if the witness stack has 0 elements. -* If there are at least two witness elements, and the first byte of the last element is 0x50<ref>'''Why is the first byte of the annex <code>0x50</code>?''' The <code>0x50</code> is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y squareness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like <code>0x50</code>. This choice maximizes the available options for future script versions.</ref>, this last element is called ''annex'' ''a''<ref>'''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include <code>annex</code> in transactions, or it may lead to PERMANENT FUND LOSS.</ref> and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. +* If there are at least two witness elements, and the first byte of the last element is 0x50<ref>'''Why is the first byte of the annex <code>0x50</code>?''' The <code>0x50</code> is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the parity of the public key's Y coordinate, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like <code>0x50</code>. This choice maximizes the available options for future script versions.</ref>, this last element is called ''annex'' ''a''<ref>'''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include <code>annex</code> in transactions, or it may lead to PERMANENT FUND LOSS.</ref> and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. * If there is exactly one element left in the witness stack, key path spending is used: ** The single witness stack element is interpreted as the signature and must be valid (see the next section) for the public key ''q'' (see the next subsection). * If there are at least two witness elements left, script path spending is used: ** Call the second-to-last stack element ''s'', the script. ** The last stack element is called the control block ''c'', and must have length ''33 + 32m'', for a value of ''m'' that is an integer between 0 and 128<ref>'''Why is the Merkle path length limited to 128?''' The optimally space-efficient Merkle tree can be constructed based on the probabilities of the scripts in the leaves, using the Huffman algorithm. This algorithm will construct branches with lengths approximately equal to ''log<sub>2</sub>(1/probability)'', but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in ''2<sup>128</sup>''. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely.</ref>, inclusive. Fail if it does not have such a length. -** Let ''p = c[1:33]'' and let ''P = point(p)'' where ''point'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. +** Let ''p = c[1:33]'' and let ''P = lift_x(int(p))'' where ''lift_x'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. ** Let ''v = c[0] & 0xfe'' and call it the ''leaf version''<ref>'''What constraints are there on the leaf version?''' First, the leaf version cannot be odd as ''c[0] & 0xfe'' will always be even, and cannot be ''0x50'' as that would result in ambiguity with the annex. In addition, in order to support some forms of static analysis that rely on being able to identify script spends without access to the output being spent, it is recommended to avoid using any leaf versions that would conflict with a valid first byte of either a valid P2WPKH pubkey or a valid P2WSH script (that is, both ''v'' and ''v | 1'' should be an undefined, invalid or disabled opcode or an opcode that is not valid as the first opcode). The values that comply to this rule are the 32 even values between ''0xc0'' and ''0xfe'' and also ''0x66'', ''0x7e'', ''0x80'', ''0x84'', ''0x96'', ''0x98'', ''0xba'', ''0xbc'', ''0xbe''. Note also that this constraint implies that leaf versions should be shared amongst different witness versions, as knowing the witness version requires access to the output being spent.</ref>. ** Let ''k<sub>0</sub> = hash<sub>TapLeaf</sub>(v || compact_size(size of s) || s)''; also call it the ''tapleaf hash''. ** For ''j'' in ''[0,1,...,m-1]'': @@ -75,8 +76,8 @@ The following rules only apply when such an output is being spent. Any other out **** If ''k<sub>j</sub> ≥ e<sub>j</sub>'': ''k<sub>j+1</sub> = hash<sub>TapBranch</sub>(e<sub>j</sub> || k<sub>j</sub>)''. ** Let ''t = hash<sub>TapTweak</sub>(p || k<sub>m</sub>)''. ** If ''t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'' (order of secp256k1), fail. -** Let ''Q = point(q) if (c[0] & 1) = 1 and -point(q) otherwise''<ref>'''Why is it necessary to reveal a bit to indicate if the point represented by the output public key is negated in a script path spend?''' The ''point'' function (defined in [[bip-0340.mediawiki#design|BIP340]]) always constructs a point with a square Y coordinate, but because ''Q'' is constructed by adding the taproot tweak to the internal public key ''P'', it cannot easily be guaranteed that ''Q'' in fact has such a Y coordinate. Therefore, before verifying the taproot tweak the original point is restored by negating if necessary. We can not ignore the Y coordinate because it would prevent batch verification. Trying out multiple internal keys until there's such a ''Q'' is possible but undesirable and unnecessary since this information about the Y coordinate only consumes an unused bit.</ref>. Fail if this point is not on the curve. -** If ''Q ≠ P + int(t)G'', fail. +** Let ''Q = P + int(t)G''. +** If ''q ≠ x(Q)'' or ''c[0] & 1 ≠ y(Q) mod 2'', fail<ref>'''Why is it necessary to reveal a bit in a script path spend and check that it matches the parity of the Y coordinate of ''Q''?''' The parity of the Y coordinate is necessary to lift the X coordinate ''q'' to a unique point. While this is not strictly necessary for verifying the taproot commitment as described above, it is necessary to allow batch verification. Alternatively, ''Q'' could be forced to have an even Y coordinate, but that would require retrying with different internal public keys (or different messages) until ''Q'' has that property. There is no downside to adding the parity bit because otherwise the control block bit would be unused.</ref>. ** Execute the script, according to the applicable script rules<ref>'''What are the applicable script rules in script path spends?''' [[bip-0342.mediawiki|BIP342]] specifies validity rules that apply for leaf version 0xc0, but future proposals can introduce rules for other leaf versions.</ref>, using the witness stack elements excluding the script ''s'', the control block ''c'', and the annex ''a'' if present, as initial stack. ''q'' is referred to as ''taproot output key'' and ''p'' as ''taproot internal key''. @@ -87,7 +88,7 @@ We first define a reusable common signature message calculation function, follow ==== Common signature message ==== -The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. +The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. The parameter ''hash_type'' is an 8-bit unsigned value. The <code>SIGHASH</code> encodings from the legacy script system are reused, including <code>SIGHASH_ALL</code>, <code>SIGHASH_NONE</code>, <code>SIGHASH_SINGLE</code>, and <code>SIGHASH_ANYONECANPAY</code>, plus the default ''hash_type'' value ''0x00'' which results in signing over the whole transaction just as for <code>SIGHASH_ALL</code>. The following restrictions apply, which cause validation failure if violated: * Using any undefined ''hash_type'' (not ''0x00'', ''0x01'', ''0x02'', ''0x03'', ''0x81'', ''0x82'', or ''0x83''<ref>'''Why reject unknown ''hash_type'' values?''' By doing so, it is easier to reason about the worst case amount of signature hashing an implementation with adequate caching must perform.</ref>). @@ -95,7 +96,7 @@ The parameter ''hash_type'' is an 8-bit unsigned value. The <code>SIGHASH</code> The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating (in the message) that extensions are added at the end of the message<ref>'''What extensions use the ''ext_flag'' mechanism?''' [[bip-0342.mediawiki|BIP342]] reuses the same common signature message algorithm, but adds BIP342-specific data at the end, which is indicated using ''ext_flag = 1''.</ref>. -If the parameters take acceptable values, the message is the concatenation of the following data, in order(with byte size of each item listed in parentheses). Numerical values in 2, 4, or 8-byte are encoded in little-endian. +If the parameters take acceptable values, the message is the concatenation of the following data, in order (with byte size of each item listed in parentheses). Numerical values in 2, 4, or 8-byte are encoded in little-endian. * Control: ** ''hash_type'' (1). @@ -104,16 +105,17 @@ If the parameters take acceptable values, the message is the concatenation of th ** ''nLockTime'' (4): the ''nLockTime'' of the transaction. ** If the ''hash_type & 0x80'' does not equal <code>SIGHASH_ANYONECANPAY</code>: *** ''sha_prevouts'' (32): the SHA256 of the serialization of all input outpoints. -*** ''sha_amounts'' (32): the SHA256 of the serialization of all input amounts. +*** ''sha_amounts'' (32): the SHA256 of the serialization of all spent output amounts. +*** ''sha_scriptpubkeys'' (32): the SHA256 of the serialization of all spent output ''scriptPubKey''s. *** ''sha_sequences'' (32): the SHA256 of the serialization of all input ''nSequence''. ** If ''hash_type & 3'' does not equal <code>SIGHASH_NONE</code> or <code>SIGHASH_SINGLE</code>: *** ''sha_outputs'' (32): the SHA256 of the serialization of all outputs in <code>CTxOut</code> format. * Data about this input: ** ''spend_type'' (1): equal to ''(ext_flag * 2) + annex_present'', where ''annex_present'' is 0 if no annex is present, or 1 otherwise (the original witness stack has two or more witness elements, and the first byte of the last element is ''0x50'') -** ''scriptPubKey'' (35): ''scriptPubKey'' of the previous output spent by this input, serialized as script inside <code>CTxOut</code>. Its size is always 35 bytes. ** If ''hash_type & 0x80'' equals <code>SIGHASH_ANYONECANPAY</code>: *** ''outpoint'' (36): the <code>COutPoint</code> of this input (32-byte hash + 4-byte little-endian). *** ''amount'' (8): value of the previous output spent by this input. +*** ''scriptPubKey'' (35): ''scriptPubKey'' of the previous output spent by this input, serialized as script inside <code>CTxOut</code>. Its size is always 35 bytes. *** ''nSequence'' (4): ''nSequence'' of this input. ** If ''hash_type & 0x80'' does not equal <code>SIGHASH_ANYONECANPAY</code>: *** ''input_index'' (4): index of this input in the transaction input vector. Index of the first input is 0. @@ -123,11 +125,11 @@ If the parameters take acceptable values, the message is the concatenation of th ** If ''hash_type & 3'' equals <code>SIGHASH_SINGLE</code>: *** ''sha_single_output'' (32): the SHA256 of the corresponding output in <code>CTxOut</code> format. -The total length of ''SigMsg()'' is at most ''209'' bytes<ref>'''What is the output length of ''SigMsg()''?''' The total length of ''SigMsg()'' can be computed using the following formula: ''177 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32''.</ref>. Note that this does not include the size of sub-hashes such as ''sha_prevouts'', which may be cached across signatures of the same transaction. +The total length of ''SigMsg()'' is at most ''206'' bytes<ref>'''What is the output length of ''SigMsg()''?''' The total length of ''SigMsg()'' can be computed using the following formula: ''174 - is_anyonecanpay * 49 - is_none * 32 + has_annex * 32''.</ref>. Note that this does not include the size of sub-hashes such as ''sha_prevouts'', which may be cached across signatures of the same transaction. In summary, the semantics of the [[bip-0143.mediawiki|BIP143]] sighash types remain unchanged, except the following: # The way and order of serialization is changed.<ref>'''Why is the serialization in the signature message changed?''' Hashes that go into the signature message and the message itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for signature messages because there is no secret data. Therefore doubling SHA256 is a waste of resources. The message computation now follows a logical order with transaction level data first, then input data and output data. This allows to efficiently cache the transaction part of the message across different inputs using the SHA256 midstate. Additionally, sub-hashes can be skipped when calculating the message (for example `sha_prevouts` if <code>SIGHASH_ANYONECANPAY</code> is set) instead of setting them to zero and then hashing them as in BIP143. Despite that, collisions are made impossible by committing to the length of the data (implicit in ''hash_type'' and ''spend_type'') before the variable length data.</ref> -# The signature message commits to the ''scriptPubKey''<ref>'''Why does the signature message commit to the ''scriptPubKey''?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (''scriptCode'' in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed.</ref>. +# The signature message commits to the ''scriptPubKey'' of the spent output and if the <code>SIGHASH_ANYONECANPAY</code> flag is not set, the message commits to the ''scriptPubKey''s of ''all'' outputs spent by the transaction. <ref>'''Why does the signature message commit to the ''scriptPubKey''?''' This prevents lying to offline signing devices about output being spent, even when the actually executed script (''scriptCode'' in BIP143) is correct. This means it's possible to compactly prove to a hardware wallet what (unused) execution paths existed. Moreover, committing to all spent ''scriptPubKey''s helps offline signing devices to determine the subset that belong to its own wallet. This is useful in [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-April/017801.html automated coinjoins].</ref>. # If the <code>SIGHASH_ANYONECANPAY</code> flag is not set, the message commits to the amounts of ''all'' transaction inputs.<ref>'''Why does the signature message commit to the amounts of all transaction inputs?''' This eliminates the possibility to lie to offline signing devices about the fee of a transaction.</ref> # The signature message commits to all input ''nSequence'' if <code>SIGHASH_NONE</code> or <code>SIGHASH_SINGLE</code> are set (unless <code>SIGHASH_ANYONECANPAY</code> is set as well).<ref>'''Why does the signature message commit to all input ''nSequence'' if <code>SIGHASH_SINGLE</code> or <code>SIGHASH_NONE</code> are set?''' Because setting them already makes the message commit to the <code>prevouts</code> part of all transaction inputs, it is not useful to treat the ''nSequence'' any different. Moreover, this change makes ''nSequence'' consistent with the view that <code>SIGHASH_SINGLE</code> and <code>SIGHASH_NONE</code> only modify the signature message with respect to transaction outputs and not inputs.</ref> # The signature message includes commitments to the taproot-specific data ''spend_type'' and ''annex'' (if present). @@ -135,7 +137,7 @@ In summary, the semantics of the [[bip-0143.mediawiki|BIP143]] sighash types rem ==== Taproot key path spending signature validation ==== To validate a signature ''sig'' with public key ''q'': -* If the ''sig'' is 64 bytes long, return ''Verify(q, hash<sub>TapSigHash</sub>(0x00 || SigMsg(0x00, 0)), sig)''<ref>'''Why is the input to ''hash<sub>TapSigHash</sub>'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hash<sub>TapSigHash</sub>'' tagged hash in future signature algorithms that make invasive changes to how hashing is performed (as opposed to the ''ext_flag'' mechanism that is used for incremental extensions). An alternative is having them use a different tag, but supporting a growing number of tags may become undesirable.</ref>, where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. +* If the ''sig'' is 64 bytes long, return ''Verify(q, hash<sub>TapSighash</sub>(0x00 || SigMsg(0x00, 0)), sig)''<ref>'''Why is the input to ''hash<sub>TapSighash</sub>'' prefixed with 0x00?''' This prefix is called the sighash epoch, and allows reusing the ''hash<sub>TapSighash</sub>'' tagged hash in future signature algorithms that make invasive changes to how hashing is performed (as opposed to the ''ext_flag'' mechanism that is used for incremental extensions). An alternative is having them use a different tag, but supporting a growing number of tags may become undesirable.</ref>, where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. * If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00<ref>'''Why can the <code>hash_type</code> not be <code>0x00</code> in 65-byte signatures?''' Permitting that would enable malleating (by third parties, including miners) 64-byte signatures into 65-byte ones, resulting in a different `wtxid` and a different fee rate than the creator intended</ref> and Verify(q, hash<sub>TapSighash</sub>(0x00 || SigMsg(sig[64], 0)), sig[0:64])''. * Otherwise, fail<ref>'''Why permit two signature lengths?''' By making the most common type of <code>hash_type</code> implicit, a byte can often be saved.</ref>. @@ -150,7 +152,7 @@ Satisfying any of these conditions is sufficient to spend the output. '''Initial steps''' The first step is determining what the internal key and the organization of the rest of the scripts should be. The specifics are likely application dependent, but here are some general guidelines: * When deciding between scripts with conditionals (<code>OP_IF</code> etc.) and splitting them up into multiple scripts (each corresponding to one execution path through the original script), it is generally preferable to pick the latter. * When a single condition requires signatures with multiple keys, key aggregation techniques like MuSig can be used to combine them into a single key. The details are out of scope for this document, but note that this may complicate the signing procedure. -* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. +* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. * If the spending conditions do not require a script path, the output key should commit to an unspendable script path instead of having no script path. This can be achieved by computing the output key point as ''Q = P + int(hash<sub>TapTweak</sub>(bytes(P)))G''. <ref>'''Why should the output key always have a taproot commitment, even if there is no script path?''' If the taproot output key is an aggregate of keys, there is the possibility for a malicious party to add a script path without being noticed by the other parties. This allows to bypass the multiparty policy and to steal the coin. @@ -168,8 +170,8 @@ Alice will not be able to notice the script path, but Mallory can unilaterally s '''Computing the output script''' Once the spending conditions are split into an internal key <code>internal_pubkey</code> and a binary tree whose leaves are (leaf_version, script) tuples, the output script can be computed using the Python3 algorithms below. These algorithms take advantage of helper functions from the [bip-0340/referency.py BIP340 reference code] for integer conversion, point multiplication, and tagged hashes. First, we define <code>taproot_tweak_pubkey</code> for 32-byte [[bip-0340.mediawiki|BIP340]] public key arrays. -In addition to the tweaked public key byte array, the function returns a boolean indicating whether the public key represents the tweaked point or its negation. -This will be required for spending the output with a script path. +The function returns a bit indicating the tweaked public key's Y coordinate as well as the public key byte array. +The parity bit will be required for spending the output with a script path. In order to allow spending with the key path, we define <code>taproot_tweak_seckey</code> to compute the secret key for a tweaked public key. For any byte string <code>h</code> it holds that <code>taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h))</code>. @@ -178,13 +180,12 @@ def taproot_tweak_pubkey(pubkey, h): t = int_from_bytes(tagged_hash("TapTweak", pubkey + h)) if t >= SECP256K1_ORDER: raise ValueError - Q = point_add(point(pubkey), point_mul(G, t)) - is_negated = not has_square_y(Q) - return bytes_from_int(x(Q)), is_negated + Q = point_add(lift_x(int_from_bytes(pubkey)), point_mul(G, t)) + return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q)) def taproot_tweak_seckey(seckey0, h): P = point_mul(G, int_from_bytes(seckey0)) - seckey = SECP256K1_ORDER - seckey0 if not has_square_y(P) else seckey + seckey = seckey0 if has_even_y(P) else SECP256K1_ORDER - seckey0 t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h)) if t >= SECP256K1_ORDER: raise ValueError @@ -226,7 +227,7 @@ def taproot_output_script(internal_pubkey, script_tree): To spend this output using script ''D'', the control block would contain the following data in this order: - <control byte with leaf version and negation bit> <internal key p> <C> <E> <AB> + <control byte with leaf version and parity bit> <internal key p> <C> <E> <AB> The TapTweak would then be computed as described [[bip-0341.mediawiki#script-validation-rules|above]] like so: @@ -258,9 +259,8 @@ This function returns the witness stack necessary and a <code>sighash</code> fun def taproot_sign_script(internal_pubkey, script_tree, script_num, inputs): info, h = taproot_tree_helper(script_tree) (leaf_version, script), path = info[script_num] - _, is_negated = taproot_tweak_pubkey(internal_pubkey, h) - output_pubkey_tag = 0 if is_negated else 1 - pubkey_data = bytes([output_pubkey_tag + leaf_version]) + internal_pubkey + output_pubkey_y_parity, _ = taproot_tweak_pubkey(internal_pubkey, h) + pubkey_data = bytes([output_pubkey_y_parity + leaf_version]) + internal_pubkey return inputs + [script, pubkey_data + path] </source> diff --git a/bip-0342.mediawiki b/bip-0342.mediawiki index c4af38a..3cf87a3 100644 --- a/bip-0342.mediawiki +++ b/bip-0342.mediawiki @@ -110,8 +110,8 @@ To validate a signature ''sig'' with public key ''p'': * Compute the tapscript message extension ''ext'', consisting of the concatenation of: ** ''tapleaf_hash'' (32): the tapleaf hash as defined in [[bip-0341.mediawiki#design|BIP341]] ** ''key_version'' (1): a constant value ''0x00'' representing the current version of public keys in the tapscript signature opcode execution. -** ''codesep_pos'' (4): the opcode position of the last executed <code>OP_CODESEPARATOR</code> before the currently executed signature opcode, with the value in little endian (or ''0xffffffff'' if none executed). The first opcode in a script has a position of 0. A multi-byte push opcode is counted as one opcode, regardless of the size of data being pushed. -* If the ''sig'' is 64 bytes long, return ''Verify(p, hash<sub>TapSigHash</sub>(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. +** ''codesep_pos'' (4): the opcode position of the last executed <code>OP_CODESEPARATOR</code> before the currently executed signature opcode, with the value in little endian (or ''0xffffffff'' if none executed). The first opcode in a script has a position of 0. A multi-byte push opcode is counted as one opcode, regardless of the size of data being pushed. Opcodes in parsed but unexecuted branches count towards this value as well. +* If the ''sig'' is 64 bytes long, return ''Verify(p, hash<sub>TapSighash</sub>(0x00 || SigMsg(0x00, 1) || ext), sig)'', where ''Verify'' is defined in [[bip-0340.mediawiki#design|BIP340]]. * If the ''sig'' is 65 bytes long, return ''sig[64] ≠ 0x00 and Verify(p, hash<sub>TapSighash</sub>(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64])''. * Otherwise, fail. diff --git a/scripts/buildtable.pl b/scripts/buildtable.pl index 75ace26..1edd8c0 100755 --- a/scripts/buildtable.pl +++ b/scripts/buildtable.pl @@ -54,6 +54,7 @@ my %ValidStatus = ( Final => "background-color: #cfffcf", Active => "background-color: #cfffcf", Replaced => "background-color: #ffcfcf", + Obsolete => "background-color: #ffcfcf", ); my %ValidType = ( 'Standards Track' => 'Standard', |
