BIP 442: OP_PAIRCOMMIT

  BIP: 442
  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

Abstract

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.

Summary

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.

Specification

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.

The number of SHA256 blocks is minimized in typical use cases. The tag can be precomputed as a SHA256 mid-state, requiring only two hash cycles for two 32-byte items, or one for two smaller items.

Motivation

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.

Key laddering involves a sequence of keys signing tuples of items and keys, which is costly in bytes and sigops. See key laddering post for details.

Examples

Committing to more than 2 elements

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                         #
# ...

Use in Lightning Symmetry

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.

The required data is a full CTV hash of the settlement transaction when there are open HTLCs, or merely the difference in balance between the channel partners in other cases. Whether the latter optimization would be used is an implementation detail not further discussed here.

# 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 }

Example channel script (pseudo-code)

# 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>

Channel update script (pseudo-code) for m > n

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. ⁴ ⁵

⁴

state-n-hash commits to a specific nLockTime value for the transaction through OP_CHECKTEMPLATEVERIFY; OP_CHECKLOCKTIMEVERIFY ensures that the state progression can only go forward (the transaction needs to have greater nLockTime value than the intermediate state ⁵: OP_0NOTEQUAL can be omitted (any non-zero value left on the stack would be accepted by the script interpreter).

In MATT

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

⁶

Naive use of OP_CAT is vulnerable to byte shifting attacks. E.g. 0x0102 || 0x03 equals 0x01 || 0x0203. Mitigation requires length checking or hashing.

Alternative approaches

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⁹

⁸

Committing to the taproot annex allows one additional item, but it is not accessible to script. ⁹: OP_RETURN can commit to additional data, but is costly and not accessible to script. ⁷: OP_PAIRCOMMIT enables useful scripts without the risks of OP_CAT (see CAT-tricks-I, CAT-tricks-II).

Reference Implementation

Code

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();
}

Pull Request

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

Rationale

Cost comparison of Lightning Symmetry constructions

Method	Channel Script	Update Script	Update Witness¹	Force Close²	Contest	Settlement Mechanism
APO-Annex	8 WU	113 WU	100 WU	1221 WU	627 WU	SigOp
APO-Return	8 WU	113 WU	66 WU	1359 WU	765 WU	SigOp
CTV+CSFS	43 WU	81 WU	98 WU	1394 WU	765 WU	HashEq
CTV+CSFS+IKEY	10 WU	48 WU	98 WU	1328 WU	732 WU	HashEq
CTV+CSFS+IKEY+PC	11 WU	49 WU	131 WU	1191 WU	594 WU	HashEq
THIKCS-Annex	10 WU	49 WU	98 WU	1160 WU	563 WU	HashEq
THIKCS-Return	10 WU	49 WU	66 WU	1329 WU	733 WU	HashEq

¹ 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

Proving general computation using trees

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.

Backward Compatibility

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

Deployment

TBD

Credits

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

Copyright

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

References

LNhance bitcoin repository: lnhance
Lightning Symmetry: eltoo
OP_CAT: BIP-347, BIN-2024-0001
OP_CHECKTEMPLATEVERIFY: BIP-119
OP_CHECKSIGFROMSTACK: BIP-348, BIN-2024-0003
OP_CHECKCONTRACTVERIFY: BIP-443
OP_INTERNALKEY: BIP-349, BIN-2024-0004
OP_TEMPLATEHASH: BIP-446
Tagged hash: BIP-340
MuSig2: BIP-327