BIP: 442 Layer: Consensus (soft fork) Title: OP_PAIRCOMMIT Author: moonsettler Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0442 Status: Draft Type: Standards Track Created: 2024-12-09 License: BSD-3-Clause
This BIP describes a new tapscript opcode OP_PAIRCOMMIT, which
provides limited vector commitment functionality in tapscript.
When evaluated, the OP_PAIRCOMMIT instruction:
- Pops the top two values off the stack,
- takes the "PairCommit" tagged SHA256 hash of the stack elements with size commitments,
- pushes the resulting 32-byte hash to the top of stack.
Currently, bitcoin lacks a way to hash multiple stack elements together. Which means building Merkle trees or verifying inclusion in a tree is not supported.
OP_PAIRCOMMIT is a simple and efficient tool to commit to two stack elements,
in a way that makes length redistribution attacks infeasible.
The number of SHA256 iterations is minimized in the typical use cases we can optimize for. Since the Tag can be pre-computed as mid-state, it would only take 1 or 2 hash cycles in validation for the unilateral close scenario.
Repurpose opcode 205 (currently OP_SUCCESS) as follows:
OP_PAIRCOMMIT pops two elements off the stack, then concatenates them along
with their size commitments and takes the tagged SHA256 hash of that
concatenated string, then pushes the resulting hash back on the stack.
Given the stack [x1, x2], where x2 is at the top of the stack:
OP_PAIRCOMMIT will push SHA256(tagPC|cs(x1)|x1|cs(x2)|x2) onto the stack.
Where | denotes concatenation and tagPC is calculated according to
BIP-340 tagged hash as SHA256("PairCommit")|SHA256("PairCommit") and
cs(x) means CompactSize(x).
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();
}OP_PAIRCOMMIT can be used to commit to a vector of stack elements in a way
that is not vulnerable to various forms of witness malleability. It is, however,
highly optimized for just 2 stack elements.
# pc-hash = PC(a, PC(b, c))
<a> <b> <c> | PC PC <pc-hash> OP_EQUALVERIFY
To do LN-Symmetry contracts that don't require the nodes to keep old states, we need to solve the data availability problem presented by unilateral closes. Channel peers must be able to reconstruct the script that spends an intermediate state.
Using in sequence OP_CHECKTEMPLATEVERIFY, OP_PAIRCOMMIT, OP_INTERNALKEY
and OP_CHECKSIGFROMSTACK we can construct a rebindable channel that is also
optimal.
The following assembly-like pseudo-code shows a possible LN-Symmetry channel construction that provides data availability to spend to the latest state from an earlier state pushed on-chain with a forced close by channel partner.
# S = 500000000
# IK -> A+B
<sig> <state-n-recovery-data> <state-n-hash> | CTV PC IK CSFS <S+1> CLTV DROP
before funding, sign the first state:
# 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 }
# contract for state n < m
IF
<sig> <state-m-recovery-data> <state-m-hash> | CTV PC IK CSFS <S+n+1> CLTV DROP
ELSE
<settlement-n-hash> CTV
ENDIF
Detailed introspection opcodes would also need vector commitments when used
with OP_CHECKSIGFROMSTACK.
OP_CHECKCONTRACTVERIFY would also need a way to carry complex data.
A reference implementation is provided here:
https://github.com/lnhance/bitcoin/pull/6/files
If OP_CAT was available, it could be used to combine multiple stack elements
that get verified with OP_CHECKSIGFROMSTACK as a valid state update.
Using OP_CAT for this purpose requires additional opcodes to prevent witness
malleability (e.g. 0x0102 0x03 OP_CAT is identical to 0x01 0x0203 OP_CAT).
OP_PAIRCOMMIT solves this specific problem without introducing a wide range
of potentially controversial new behaviors like fully detailed introspection,
which includes the ability to inspect parent transactions and novel 2-way peg
mechanisms. (CAT-tricks-I and CAT-tricks-II by Andrew Poelstra)
Alternatively OP_RETURN could be used to ensure the availability of the state
recovery data, as OP_CHECKTEMPLATEVERIFY naturally commits to all outputs.
However, its cost in weight units would be over 4 times higher than that of
using OP_PAIRCOMMIT.
One way to think about the 3 opcodes (OP_CHECKSIGFROMSTACK, OP_INTERNALKEY,
OP_PAIRCOMMIT) is we decompose a OP_CHECKSIGFROMSTACK variant that can use
a 1-byte OP_TRUE public key (substituting for the taproot internal key) and
can commit to a number of stack elements as a message.
The following behaviors are out of scope for LNhance and should not be enabled as a side effect without explicit consensus:
- Fine-grained introspection
- State-carrying covenants
- Bigint operations
- New arithmetic capabilities using lookup tables
The following list of alternative approaches were discussed and rejected for various reasons, either for expanding the scope or for unnecessary complexity:
- OP_CAT
- SHA256 streaming opcodes
- Merkle operation opcodes
- 'Kitty' CAT: result or inputs arbitrarily limited in size
- OP_CHECKTEMPLATEVERIFY committing to the taproot annex in tapscript
- OP_CHECKSIGFROMSTACK on n elements as message
- OP_VECTORCOMMIT: generalized form for n > 2 elements
- ReKey: key delegation and multiple use of OP_CHECKSIGFROMSTACK
| Method | ChannelSc | UpdateSc | UpdateW | ForceC | Contest | Settle |
|---|---|---|---|---|---|---|
| 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+IKEY | 10 WU | 48 WU | 98 WU | 1328 WU | 732 WU | CTV |
| CTV+CSFS | 43 WU | 81 WU | 98 WU | 1394 WU | 765 WU | CTV |
| LNhance | 11 WU | 49 WU | 131 WU | 1191 WU | 594 WU | CTV |
ChannelSc: channel script, UpdateSc: update script, UpdateW: witness is the same size for both Force Close and Contest in LN-Symmetry, ForceC: total cost of unilateral close transactions
Merkle trees can be used to prove computation where the root of the tree represents the function and the leaves represent the inputs and output. There are practical limits to the entropy space for the inputs as they need to be iterated over and hashed into a Merkle root.
Taproot MAST trees can currently cover 128 bits of entropy space, which is over
the practical limits to iterate over and merklize. Therefore, we conclude this
capability does not materially extend what computations are possible to prove
in bitcoin script. While OP_PAIRCOMMIT is not limited to a height of 128,
that should not be practically feasible to utilize.
There is a way to reduce the size of the witness for proving computation,
by eliminating the Merkle path inclusion proofs, using OP_CHECKSIGFROMSTACK
together with OP_PAIRCOMMIT. This method involves deleted key assumptions,
most likely using MPC to create an enormous amount of signatures for the stack
elements representing the inputs and the output of the function.
By constraining the behavior of OP_SUCCESS opcodes, deployment of the BIP
can be done in a backwards-compatible, soft-fork manner. If anyone were to
rely on the OP_SUCCESS behavior of OP_SUCCESS205, OP_PAIRCOMMIT would
invalidate their spend.
TBD
Jeremy Rubin, Brandon Black, Salvatore Ingala, Anthony Towns, Ademan555, Psifour
This document is licensed under the 3-clause BSD license.
- LNhance bitcoin repository: lnhance
- LN-Symmetry: eltoo
- OP_CAT: BIP-347, BIN-2024-0001
- OP_CHECKTEMPLATEVERIFY: BIP-119
- OP_CHECKSIGFROMSTACK: BIP-348, BIN-2024-0003
- OP_INTERNALKEY: BIP-349, BIN-2024-0004
- Tagged hash: BIP-340