Pay-to-Merkle-Root (P2MR)

  BIP: 360
  Layer: Consensus (soft fork)
  Title: Pay-to-Merkle-Root (P2MR)
  Authors: Hunter Beast 
           Ethan Heilman 
           Isabel Foxen Duke 
  Status: Draft
  Type: Specification
  Assigned: 2024-12-18
  License: BSD-3-Clause
  Version: 0.11.0
  Requires: 340, 341, 342

Introduction

Abstract

This document proposes a new output type: Pay-to-Merkle-Root (P2MR), via a soft fork. P2MR outputs operate with nearly the same functionality as P2TR (Pay-to-Taproot) outputs, but with the key path spend removed.

Through this modification, P2MR outputs allow developers to use script trees and tapscript in a manner that is:

# resistant to long exposure attacks by Cryptographically Relevant Quantum Computers (CRQCs), and # resistant to future cryptanalytic approaches that may compromise the elliptic curve cryptography (ECC) used by Bitcoin.

It is worth noting that proposed P2MR outputs are only resistant to "long exposure attacks" on elliptic curve cryptography; that is, attacks on keys exposed for time periods longer than needed to confirm a spending transaction.

Protection against more sophisticated quantum attacks, including protection against private key recovery from public keys exposed in the mempool while a transaction is waiting to be confirmed (a.k.a. "short exposure attacks"), may require the introduction of post-quantum signatures in Bitcoin. We believe it's worth considering this path in the future and intend to offer a separate proposal for this purpose upon further research.

This document additionally defines "long exposure" and "short exposure" attacks, and other new terminology in the Glossary.

Copyright

This document is licensed under the 3-clause BSD license.

Motivation

The primary threat to Bitcoin from Cryptographically Relevant Quantum Computers (CRQCs) is their potential to break the key cryptographic assumption which secures the digital signatures used in Bitcoin. More specifically, Shor's algorithm enables a CRQC to solve the Discrete Logarithm Problem (DLP) exponentially faster than classical methods. This allows the derivation of private keys from public keys — a process referred to here as quantum key recovery. While it is unclear when or if CRQCs will become viable in the future, we propose the addition of a quantum-resistant, script tree output type for those interested in this level of protection.

While some may balk at the potential threat of quantum computers to Bitcoin given their limited functionality to date, some others — including governments, corporations and some existing and potential Bitcoin users — are concerned about their potential for advancement. The Commercial National Security Algorithm Suite (CNSA) 2.0, for instance, has mandated software and networking equipment to be upgraded to post-quantum schemes by 2030, with browsers and operating systems fully upgraded by 2033. Additionally, according to NIST IR 8547, Elliptic Curve Cryptography (ECC) is planned to be disallowed within the US federal government after 2035 (with an exception made for hybrid cryptography, or the use of ECC and post-quantum algorithms together). These kinds of mandates have triggered concern by some ECC users, including some Bitcoin users who prefer to be prepared out of an abundance of caution.

In the most optimistic case, wherein quantum computers never pose a significant risk to ECC, we understand that the possibility of quantum advancement alone may be influencing adoption and broad confidence in the Bitcoin network. In other words, we believe users' fear of quantum computers may be worth addressing regardless of CRQC viability. Given these concerns, we think it's worth considering simple low risk changes that create options for using Bitcoin in a quantum-resistant way.

As a conservative first step in this effort, we propose Pay-to-Merkle-Root (P2MR), a script tree output that can be used in a quantum resistant manner.

Long Exposure vs Short Exposure Attacks

For clarity, this proposal specifically mitigates the risk of long exposure attacks on outputs that support tapscript and script trees. While some other Bitcoin output types, such as P2SH, are safe against long exposure attacks, taproot is not and taproot is the only currently activated output type that supports tapscript and script trees.

A long exposure attack is an attack performed on exposed blockchain data, such as exposed public keys, or the scripts of spent outputs. These are likely to be the earliest quantum attacks made possible on Bitcoin, because attackers will have ample time — as much time as vulnerable keys are exposed — to carry out quantum key recovery.

Short exposure attacks, however, require faster quantum computers, because they must occur within the relatively short time that a transaction is unconfirmed in the mempool.

Bitcoin outputs are generally vulnerable to short exposure attacks, as most Bitcoin transactions require revealing the associated public key when spending. Full protection of outputs from short exposure attacks may require the use of post-quantum signature schemes.

Since long exposure attacks on public keys are likely to be the first quantum-enabled threat to Bitcoin, we propose a script tree output that is resistant to long exposure attacks as a first step in hardening Bitcoin against the potential threat of quantum computers.

The following list of output types describes their long exposure attack vulnerability:

Type	Vulnerable	Prefix	Example
P2PK	Yes	Varies	02103203b768951584fe9af6d9d9e6ff26a5f76e453212f19ba163774182ab8057f3eac
P2PKH	No*	1	1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
P2MS	Yes	Varies	52410496ec45f878b62c46c4be8e336dff7cc58df9b502178cc240e...
P2SH	No*	3	3FkhZo7sGNue153xhgqPBcUaBsYvJW6tTx
P2WPKH	No*	bc1q	bc1qsnh5ktku9ztqeqfr89yrqjd05eh58nah884mku
P2WSH	No*	bc1q	bc1qvhu3557twysq2ldn6dut6rmaj3qk04p60h9l79wk4lzgy0ca8mfsnffz65
P2TR	Yes	bc1p	bc1p92aslsnseq786wxfk3ekra90ds9ku47qttupfjsqmmj4z82xdq4q3rr58u
P2MR	No*	bc1z	bc1zzmv50jjgxxhww6ve4g5zpewrkjqhr06fyujpm20tuezdlxmfphcqfc80ve

The following output types are fundamentally vulnerable to long exposure attacks:

• P2PK outputs (e.g. Satoshi's coins, CPU miners)
• Reused outputs*
• Taproot outputs (starts with bc1p)

* Funds in P2PKH, P2SH, P2WPKH, P2WSH, and P2MR outputs can become vulnerable to long exposure quantum attacks anytime their script reveals a public key.

Note: Extended public keys, commonly known as "xpubs," and wallet descriptors also reveal quantum vulnerable public key information. For further clarification on quantum attack vectors, please refer to the Glossary of Terms.

Design

Pay-to-Merkle-Root (P2MR) is a proposed new output type that commits to the root of a script tree. It operates with nearly the same functionality as P2TR (Pay-to-Taproot) outputs, but with the quantum vulnerable key path spend removed.

In other words, P2MR outputs commit to the Merkle root of a script tree without committing to an internal key. The script(s) being committed to, however, may contain a key or key-hash.

This output type is designed to offer users protection against long exposure quantum attacks as well as a practical output type with which post-quantum signatures may be used if such signatures are adopted in the future.

Since P2MR outputs have no key path spend, they omit the Taproot internal key. Instead, a P2MR output includes the 32-byte root of the script tree as defined in BIP 341 hashed with the tag "TapBranch" as shown below.

thumb|Construction of P2MR script tree root, scriptPubkey, and Witness

To construct a P2MR output, we follow the process outlined in BIP 341 to compute the final tapbranch hash, which is the merkle root of the script leaves; however, instead of tweaking the internal key with the root of the Merkle tree (as is the case with P2TR outputs), P2MR outputs commit only to final tapbranch hash, which is tagged, "TapBranch".

D = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
CD = tagged_hash("TapBranch", C + D)
CDE = tagged_hash("TapBranch", CD + E)
ABCDE = tagged_hash("TapBranch", AB + CDE)

A P2MR input witness provides the following:

initial stack element 0,
...,
initial stack element N,
leaf script,
control block = [control byte, 32*m byte Merkle path] # m is the depth of the script in the Merkle tree

The initial stack elements of P2MR follow the same rules as P2TR script path spends. That is, they place elements on the stack to be evaluated by the leaf script.

The control block is a 1 + 32 * m byte array, where the first byte is the control byte and the next 32 * m bytes are the Merkle path to the leaf script. The control byte is the same as the control byte in a P2TR control block, including the 7 bits which are used to specify the leaf version. The parity bit of the control byte is always 1, since P2MR does not have a key path spend. Unlike P2TR, we omit the public key from the control block as it is not needed in P2MR. We maintain support for the optional annex in the witness (see Specification section below for more details).

Rationale

Design of the P2MR output type is guided by the following intentions:

1. Minimize changes to the network. We should reuse existing Bitcoin code and preserve existing software behavior, workflows, user expectations and compatibility whenever possible.

P2MR leverages the battle tested P2TR, tapleaf and tapscript code already in Bitcoin, reducing the implementation burden on wallets, exchanges, and libraries that can reuse code they already have. This approach reduces complexity and minimizes implementation risks.

2. Create the safest possible path for the addition of post-quantum signature integrations, in the event that they are used in the future.

Importantly, we are proposing a script tree output, i.e. an output type that supports tapscript, that is resistant to long exposure attacks. While some existing output types are already resistant to long exposure attacks (e.g. P2WSH), no such output type supports tapscript — a feature that may be required for practical implementation of post-quantum signature opcodes.

P2WSH, for instance, does not support tapscript and as such does not support the OP_SUCCESSx opcode update path that will be critical for the integration of post-quantum OP_CHECKSIG opcodes into Bitcoin.

3. Facilitate gradual integration of quantum resistant features that can be carried out iteratively as quantum computers evolve. This approach encourages responsiveness to the current threat-level, while avoiding heavy-handedness in our reactions to a potential threat.

We designed P2MR with an eye towards integrating post-quantum signatures in the future, without proposing more complex changes while CRQCs are still in their infancy.

P2MR Trade-Offs

While P2TR outputs (and the use of key path spend) will remain an option for folks wishing to use them, we aim to be clear about the tradeoffs of using P2MR outputs, which disable the key path spend for the benefit of quantum resistance.

The witness to a P2MR spend is always larger than the witness to a P2TR key path spend. This is because a P2TR key path spend requires only a Schnorr signature in the witness. For P2MR, the witness must include the chosen leaf script, the initial stack, and a control block consisting of the control byte and Merkle path (if any).

That said, the witness to a P2MR spend will always be smaller than the witness to an equivalent P2TR script path spend, because there is no longer any internal key in P2MR that must be revealed in the control block. For a more complete comparison of output type transaction sizes, the "Transaction Size and Fees" section may be reviewed later in this proposal.

Additionally, there is a privacy tradeoff when comparing P2MR and P2TR, which is that users reveal they are spending to a script tree whenever they are using P2MR outputs, since P2MR outputs can only be spent via script path spend. In P2TR when you spend an output as a key path spend, you don't reveal if you have any script path spends. This trade-off only exists when comparing P2TR key path spends to P2MR script path spends; P2TR and P2MR provide the same level of privacy when both are script path spends.

Note: P2MR and P2TR both provide greater script privacy than P2SH BIP 16 because unused script paths are not revealed.

Specification

We define the Pay-to-Merkle-Root (P2MR) output structure as follows:

A P2MR output is similar to a P2TR output (as defined in BIP 341); however, unlike P2TR outputs, we disable the key path spend for the benefit of quantum resistance by omitting the internal key and the tap tweak step. A P2MR output is then a SegWit version 2 byte followed by the Merkle root of the script tree as the witness program.

Address Format

P2MR outputs use SegWit version 2, resulting in mainnet addresses that start with bc1z, following BIP 173. Bech32m encoding maps version 2 to the prefix z.

Example P2MR address:

bc1zzmv50jjgxxhww6ve4g5zpewrkjqhr06fyujpm20tuezdlxmfphcqfc80ve

This commits to a 32-byte script tree Merkle root.

ScriptPubKey

The scriptPubKey for a P2MR output is:

OP_2 OP_PUSHBYTES_32 

Where:

• OP_2 indicates SegWit version 2.
• is the 32-byte Merkle root of the script tree.

Script Validation

A P2MR output is a native SegWit output (see BIP 141) with version 2 and a 32-byte witness program. For the sake of comparison, we have — as much as possible — copied the language verbatim from the script validation section of BIP 341.

• Let q be the 32-byte array containing the witness program (the second push in the scriptPubK