diff options
| -rw-r--r-- | README.mediawiki | 20 | ||||
| -rw-r--r-- | bip-0008.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0019.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0033.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0036.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0039.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0119.mediawiki | 18 | ||||
| -rw-r--r-- | bip-0152.mediawiki | 2 | ||||
| -rw-r--r-- | bip-0322.mediawiki | 69 | ||||
| -rw-r--r-- | bip-0325.mediawiki | 20 | ||||
| -rw-r--r-- | bip-0340.mediawiki | 6 | ||||
| -rw-r--r-- | bip-0341.mediawiki | 4 | ||||
| -rw-r--r-- | bip-0342.mediawiki | 2 |
13 files changed, 66 insertions, 85 deletions
diff --git a/README.mediawiki b/README.mediawiki index 6b5eb5d..9003cce 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 | Informational -| Draft +| Rejected |- style="background-color: #cfffcf" | [[bip-0009.mediawiki|9]] | @@ -104,13 +104,13 @@ Those proposing changes should consider that ultimately consent may rest with th | Luke Dashjr | Standard | Proposed -|- +|- style="background-color: #ffcfcf" | [[bip-0019.mediawiki|19]] | Applications | M-of-N Standard Transactions (Low SigOp) | Luke Dashjr | Standard -| Draft +| Rejected |- style="background-color: #ffcfcf" | [[bip-0020.mediawiki|20]] | Applications @@ -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 @@ -770,13 +770,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 diff --git a/bip-0008.mediawiki b/bip-0008.mediawiki index 9840bed..f09f8a7 100644 --- a/bip-0008.mediawiki +++ b/bip-0008.mediawiki @@ -4,7 +4,7 @@ Author: Shaolin Fry <shaolinfry@protonmail.ch> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0008 - Status: Draft + Status: Rejected Type: Informational Created: 2017-02-01 License: BSD-3-Clause diff --git a/bip-0019.mediawiki b/bip-0019.mediawiki index 744b97a..32179ea 100644 --- a/bip-0019.mediawiki +++ b/bip-0019.mediawiki @@ -5,7 +5,7 @@ Author: Luke Dashjr <luke+bip17@dashjr.org> Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0019 - Status: Draft + Status: Rejected Type: Standards Track Created: 2012-01-30 License: BSD-2-Clause 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 af76d59..cd0115c 100644 --- a/bip-0039.mediawiki +++ b/bip-0039.mediawiki @@ -138,7 +138,7 @@ Go: * https://github.com/tyler-smith/go-bip39 Elixir: -* https://github.com/izelnakri/mnemonic +* https://github.com/aerosol/mnemo Objective-C: * https://github.com/nybex/NYMnemonic diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index 11a90bb..7a87b24 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -100,7 +100,7 @@ In BOLT #2, this maximum number of HTLCs in a channel is hard limited to 483 as size to prevent the transaction from being too large to be valid. In common software implementations such as LND, this limit is set much lower to 12 HTLCS. This is because accepting a larger number of HTLCS makes it more difficult for transactions to confirm during congested periods as they must pay -hire fees. +higher fees. Therefore, similarly to how congestion control is handled for normal transaction, lightning channel updates can be done across an CHECKTEMPLATEVERIFY tree, allowing nodes to safely use many more HTLCS. @@ -536,14 +536,14 @@ for older node versions that can be patched but not upgraded to a newer major re == References == -*[[https://utxos.org|utxos.org informational site]] -*[[https://youtu.be/YxsjdIl0034?t=2451|Scaling Bitcoin Presentation]] -*[[https://bitcoinops.org/en/newsletters/2019/05/29/|Optech Newsletter Covering OP_CHECKOUTPUTSHASHVERIFY]] -*[[https://cyber.stanford.edu/sites/g/files/sbiybj9936/f/jeremyrubin.pdf|Structuring Multi Transaction Contracts in Bitcoin]] -*[[https://github.com/jeremyrubin/lazuli]|Lazuli Notes (ECDSA based N-of-N Signatures for Certified Post-Dated UTXOs)]] -*[[https://fc16.ifca.ai/bitcoin/papers/MES16.pdf|Bitcoin Covenants]] -*[[https://bitcointalk.org/index.php?topic=278122.0|CoinCovenants using SCIP signatures, an amusingly bad idea.]] -*[[https://fc17.ifca.ai/bitcoin/papers/bitcoin17-final28.pdf|Enhancing Bitcoin Transactions with Covenants]] +*[https://utxos.org utxos.org informational site] +*[https://www.youtube.com/watch?v=YxsjdIl0034&t=2451 Scaling Bitcoin Presentation] +*[https://bitcoinops.org/en/newsletters/2019/05/29/ Optech Newsletter Covering OP_CHECKOUTPUTSHASHVERIFY] +*[https://cyber.stanford.edu/sites/g/files/sbiybj9936/f/jeremyrubin.pdf Structuring Multi Transaction Contracts in Bitcoin] +*[https://github.com/jeremyrubin/lazuli Lazuli Notes (ECDSA based N-of-N Signatures for Certified Post-Dated UTXOs)] +*[https://fc16.ifca.ai/bitcoin/papers/MES16.pdf Bitcoin Covenants] +*[https://bitcointalk.org/index.php?topic=278122.0 CoinCovenants using SCIP signatures, an amusingly bad idea.] +*[https://fc17.ifca.ai/bitcoin/papers/bitcoin17-final28.pdf Enhancing Bitcoin Transactions with Covenants] ===Note on Similar Alternatives=== 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-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..c0db46d 100644 --- a/bip-0325.mediawiki +++ b/bip-0325.mediawiki @@ -57,6 +57,26 @@ The <code>modifiedMerkleRoot</code> hash is obtained by generating the merkle ro 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. +== 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 == This specification is backwards compatible in the sense that existing software can use Signet out of the box. diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 9e0a73e..d2f92db 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -55,7 +55,7 @@ encodings and operations. === Design === '''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and the base point ''G'' which satisfy ''e = hash(R || m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'': -# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P || m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intent to sign. +# Signatures are pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P || m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign. # Signatures are pairs ''(R, s)'' that satisfy ''s⋅G = R + hash(R || m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups. [[File:bip-0340/speedup-batch.png|center|frame|This graph shows the ratio between the time it takes to verify ''n'' signatures individually and to verify a batch of ''n'' signatures. This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify ''n'' signatures grows with ''O(n / log n)''.]] @@ -166,7 +166,9 @@ The algorithm ''Sign(sk, m)'' is defined as: 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. Adding RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks], and it is safe to add the output of a low-entropy RNG. +'''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. + +'''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.''' '''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. diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index 8f27c35..ec11f6a 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -31,7 +31,7 @@ This proposal aims to improve privacy, efficiency, and flexibility of Bitcoin's ==Design== -A number of related ideas for improving Bitcoin's scripting capabilities have been previously proposed: Schnorr signatures ([[bip-0340|BIP340]]), Merkle branches ("MAST", [[bip-0114|BIP114]], [[bip-0117|BIP117]]), new sighash modes ([[bip-0118|BIP118]]), new opcodes like CHECKSIGFROMSTACK, [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html Taproot], [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html Graftroot], [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html G'root], and [https://bitcointalk.org/index.php?topic=1377298.0 cross-input aggregation]. +A number of related ideas for improving Bitcoin's scripting capabilities have been previously proposed: Schnorr signatures ([[bip-0340.mediawiki|BIP340]]), Merkle branches ("MAST", [[bip-0114.mediawiki|BIP114]], [[bip-0117.mediawiki|BIP117]]), new sighash modes ([[bip-0118.mediawiki|BIP118]]), new opcodes like CHECKSIGFROMSTACK, [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html Taproot], [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html Graftroot], [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html G'root], and [https://bitcointalk.org/index.php?topic=1377298.0 cross-input aggregation]. Combining all these ideas in a single proposal would be an extensive change, be hard to review, and likely miss new discoveries that otherwise could have been made along the way. Not all are equally mature as well. For example, cross-input aggregation [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html interacts] in complex ways with upgrade mechanisms, and solutions to that are still [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016461.html in flux]. On the other hand, separating them all into independent upgrades would reduce the efficiency and privacy gains to be had, and wallet and service providers may not be inclined to go through many incremental updates. Therefore, we're faced with a tradeoff between functionality and scope creep. In this design we strike a balance by focusing on the structural script improvements offered by Taproot and Merkle branches, as well as changes necessary to make them usable and efficient. For things like sighashes and opcodes we include fixes for known problems, but exclude new features that can be added independently with no downsides. @@ -65,7 +65,7 @@ The following rules only apply when such an output is being spent. Any other out * 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 = point(p)'' where ''point'' 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]'': diff --git a/bip-0342.mediawiki b/bip-0342.mediawiki index 3da9904..c4af38a 100644 --- a/bip-0342.mediawiki +++ b/bip-0342.mediawiki @@ -76,7 +76,7 @@ The execution rules for tapscript are based on those for P2WSH according to BIP1 * '''OP_SUCCESSx opcodes''' As listed above, some opcodes are renamed to <code>OP_SUCCESSx</code>, and make the script unconditionally valid. * '''Signature opcodes'''. The <code>OP_CHECKSIG</code> and <code>OP_CHECKSIGVERIFY</code> are modified to operate on Schnorr public keys and signatures (see [[bip-0340.mediawiki|BIP340]]) instead of ECDSA, and a new opcode <code>OP_CHECKSIGADD</code> is added. ** The opcode 186 (<code>0xba</code>) is named as <code>OP_CHECKSIGADD</code>. <ref>'''<code>OP_CHECKSIGADD</code>''' This opcode is added to compensate for the loss of <code>OP_CHECKMULTISIG</code>-like opcodes, which are incompatible with batch verification. <code>OP_CHECKSIGADD</code> is functionally equivalent to <code>OP_ROT OP_SWAP OP_CHECKSIG OP_ADD</code>, but only takes 1 byte. All <code>CScriptNum</code>-related behaviours of <code>OP_ADD</code> are also applicable to <code>OP_CHECKSIGADD</code>.</ref><ref>'''Alternatives to <code>CHECKMULTISIG</code>''' There are multiple ways of implementing a threshold ''k''-of-''n'' policy using Taproot and Tapscript: -* '''Using a single <code>OP_CHECKSIGADD</code>-based script''' A <code>CHECKMULTISIG</code> script <code>m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG</code> with witness <code>0 <signature_1> ... <signature_m></code> can be rewritten as script <code><pubkey_1> CHECKSIG ... <pubkey_n> CHECKSIGADD m NUMEQUAL</code> with witness <code><w_1> ... <w_n></code>. Every witness element <code>w_i</code> is either a signature corresponding to <code>pubkey_i</code> or an empty vector. A similar <code>CHECKMULTISIGVERIFY</code> script can be translated to BIP342 by replacing <code>NUMEQUAL</code> with <code>NUMEQUALVERIFY</code>. This approach has very similar characteristics to the existing <code>OP_CHECKMULTISIG</code>-based scripts. +* '''Using a single <code>OP_CHECKSIGADD</code>-based script''' A <code>CHECKMULTISIG</code> script <code>m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG</code> with witness <code>0 <signature_1> ... <signature_m></code> can be rewritten as script <code><pubkey_1> CHECKSIG <pubkey_2> CHECKSIGADD ... <pubkey_n> CHECKSIGADD m NUMEQUAL</code> with witness <code><w_n> ... <w_1></code>. Every witness element <code>w_i</code> is either a signature corresponding to <code>pubkey_i</code> or an empty vector. A similar <code>CHECKMULTISIGVERIFY</code> script can be translated to BIP342 by replacing <code>NUMEQUAL</code> with <code>NUMEQUALVERIFY</code>. This approach has very similar characteristics to the existing <code>OP_CHECKMULTISIG</code>-based scripts. * '''Using a ''k''-of-''k'' script for every combination''' A ''k''-of-''n'' policy can be implemented by splitting the script into several leaves of the Merkle tree, each implementing a ''k''-of-''k'' policy using <code><pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG</code>. This may be preferable for privacy reasons over the previous approach, as it only exposes the participating public keys, but it is only more cost effective for small values of ''k'' (1-of-''n'' for any ''n'', 2-of-''n'' for ''n ≥ 6'', 3-of-''n'' for ''n ≥ 9'', ...). Furthermore, the signatures here commit to the branch used, which means signers need to be aware of which other signers will be participating, or produce signatures for each of the tree leaves. * '''Using an aggregated public key for every combination''' Instead of building a tree where every leaf consists of ''k'' public keys, it is possible instead build a tree where every leaf contains a single ''aggregate'' of those ''k'' keys using [https://eprint.iacr.org/2018/068 MuSig]. This approach is far more efficient, but does require a 3-round interactive signing protocol to jointly produce the (single) signature. * '''Native Schnorr threshold signatures''' Multisig policies can also be realized with [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps threshold signatures] using verifiable secret sharing. This results in outputs and inputs that are indistinguishable from single-key payments, but at the cost of needing an interactive protocol (and associated backup procedures) before determining the address to send to.</ref> |