BIP: 442 source
  Layer: Consensus (soft fork)
  Title: OP_PAIRCOMMIT
  Authors: moonsettler <moonsettler@protonmail.com>
           Brandon Black <freedom@reardencode.com>
  Status: Draft
  Type: Specification
  Assigned: 2024-12-09
  License: BSD-3-Clause
  Discussion: https://delvingbitcoin.org/t/op-paircommit-as-a-candidate-for-addition-to-lnhance/1216
              https://groups.google.com/g/bitcoindev/c/si6ZNIkVfOw/m/29VY_YRrCgAJ

This BIP proposes a new tapscript opcode, OP_PAIRCOMMIT, which enables efficient and secure commitment to pairs of stack elements using a tagged hash construction. This opcode provides limited vector commitment functionality, facilitating more expressive contracts and improved data availability in Bitcoin scripts.

For taproot script spends with leaf version 0xc0 (see BIP-342), OP_PAIRCOMMIT replaces OP_SUCCESS205 (0xcd). When executed, OP_PAIRCOMMIT pops the top two stack elements, computes a PairCommit tagged SHA256 hash over their compact size and data, and pushes the resulting 32-byte hash onto the stack.

Notation follows BIP-340, including the tagged hash notation: hash_tag(x) = SHA256(SHA256(tag) || SHA256(tag) || x)

Stack operation:

• If fewer than 2 elements are present, script execution fails.
• Let the stack be [..., x1, x2] (top is rightmost).
• Compute: pc = hash_PairCommit(compact_size(len(x1)) || x1 || compact_size(len(x2)) || x2)¹
• Pop x2 and x1 from the stack.
• Push pc onto the stack.

Bitcoin scripts often commit to single data items (e.g., hash/time locks, P2PKH), but lack native support for committing to multiple items together. OP_PAIRCOMMIT enables Merklized commitments, allowing contracts to commit to trees of elements with a single hash. This supports use cases such as hash lock contracts where any pre-image in a Merkle tree can unlock a spend.

Combined with OP_CHECKSIGFROMSTACK, signing commitments to multiple items enables complex delegation (e.g., delegating to key1 after time t1 and key2 after time t2). Previously, such delegation required key laddering², which is more costly in validation. OP_PAIRCOMMIT enforces relationships between items efficiently.

OP_PAIRCOMMIT can commit to a vector of stack elements securely and efficiently.

# Commit to three elements: a, b, c
# pc-hash = PC(a, PC(b, c))

# Witness: <a> <b> <c>
OP_PAIRCOMMIT                          # <a>, PC(b, c)
OP_PAIRCOMMIT                          # PC(a, PC(b, c))
<pc-hash>                              # PC(a, PC(b, c)), <pc-hash>
OP_EQUALVERIFY                         #
# ...

Lightning Symmetry contracts require data availability for contested closes. ³ By forcing parties to include settlement transaction hashes in the witness, later updates can reconstruct scripts of intermediate states while only keeping the latest state.

# S:                                   500000000
# internal-key:                        BIP-327 aggregate key of channel participants
# state-n-hash:                        { nLockTime(S+n), out(contract, amount(A)+amount(B)) }
# settlement-n-hash:                   { nSequence(2w), out(A, amount(A)), out(B, amount(B)) }
# state-n-recovery-data:               { settlement-n-hash or state-n-balance }

# Witness: <sig> <state-n-recovery-data> <state-n-hash>
OP_CHECKTEMPLATEVERIFY                 # <sig>, <state-n-recovery-data>, <state-n-hash>
OP_PAIRCOMMIT                          # <sig>, PC(state-n-recovery-data, state-n-hash)
OP_INTERNALKEY                         # <sig>, PC(state-n-recovery-data, state-n-hash), <internal-key>
OP_CHECKSIGFROMSTACK                   # <1>
<S+1>                                  # <1>, <S+1>
OP_CHECKLOCKTIMEVERIFY                 # <1>, <S+1>
OP_DROP                                # <1>

OP_IF
    # Witness: <sig> <state-m-recovery-data> <state-m-hash>
    OP_CHECKTEMPLATEVERIFY             # <sig>, <state-m-recovery-data>, <state-m-hash>
    OP_PAIRCOMMIT                      # <sig>, PC(state-m-recovery-data, state-m-hash)
    OP_INTERNALKEY                     # <sig>, PC(state-m-recovery-data, state-m-hash), <internal-key>
    OP_CHECKSIGFROMSTACK               # <1>
    <S+n+1>                            # <1>, <S+n+1>
    OP_CHECKLOCKTIMEVERIFY             # <1>, <S+n+1>
    OP_DROP                            # <1>
OP_ELSE
    # Empty witness stack
    <settlement-n-hash>                # <settlement-n-hash>
    OP_CHECKTEMPLATEVERIFY             # <settlement-n-hash>
    OP_0NOTEQUAL                       # <1>
OP_ENDIF

These constructions ensure both parties sign the same pair hash, requiring inclusion of both update and settlement hashes in the witness. ^{4 5}

The Merklize All The Things (MATT) framework uses OP_CAT to combine items for commitments. OP_PAIRCOMMIT provides a more ergonomic and secure alternative⁶.

Alternative approaches considered and rejected:

• OP_CAT⁶⁷
• SHA256 streaming opcodes⁷
• Merkle operation opcodes
• 'Kitty' CAT: OP_CAT with size limits
• OP_CHECKTEMPLATEVERIFY committing to the taproot annex⁸
• OP_CHECKSIGFROMSTACK on n elements
• OP_VECTORCOMMIT: generalized for n > 2 elements
• ReKey/Laddering²
• OP_RETURN⁹

case OP_PAIRCOMMIT: {
    // OP_PAIRCOMMIT is only available in Tapscript
    // ...
    // x1 x2 -- hash
    if (stack.size() < 2) {
        return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
    }
    const valtype& vch1 = stacktop(-2);
    const valtype& vch2 = stacktop(-1);

    uint256 hash = PairCommitHash(vch1, vch2);

    stack.pop_back();
    stack.pop_back();
    stack.emplace_back(hash.begin(), hash.end());
    break;
}

const HashWriter HASHER_PAIRCOMMIT{TaggedHash("PairCommit")};

uint256 PairCommitHash(const std::vector<unsigned char>& x1, const std::vector<unsigned char>& x2)
{
    return (HashWriter{HASHER_PAIRCOMMIT} << x1 << x2).GetSHA256();
}

https://github.com/lnhance/bitcoin/pull/6/files

¹ Witness is the same weight for both Force Close and Contest in LN-Symmetry
² Total cost of unilateral close transactions
³ THIKCS is short for TEMPLATEHASH+IKEY+CSFS

OP_PAIRCOMMIT enables Merkle tree commitments, which can represent functions where inputs and corresponding outputs are the leaves. Taproot trees can be 128 levels deep, therefore including up to 2¹²⁸ possible leaf scripts that can represent complex functions. This is already over the practical computational limits to enumerate and Merklize.

Constraining OP_SUCCESS opcodes allows deployment as a backwards-compatible soft fork. Reliance on OP_SUCCESS205 behavior will be invalidated by OP_PAIRCOMMIT.

TBD

Jeremy Rubin, Salvatore Ingala, Anthony Towns, Ademan555, Psifour

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

1. LNhance bitcoin repository: lnhance
2. Lightning Symmetry: eltoo
3. OP_CAT: BIP-347, BIN-2024-0001
4. OP_CHECKTEMPLATEVERIFY: BIP-119
5. OP_CHECKSIGFROMSTACK: BIP-348, BIN-2024-0003
6. OP_CHECKCONTRACTVERIFY: BIP-443
7. OP_INTERNALKEY: BIP-349, BIN-2024-0004
8. OP_TEMPLATEHASH: BIP-446
9. Tagged hash: BIP-340
10. MuSig2: BIP-327