OP_PAIRCOMMIT is the newest member of the LNhance family of opcodes. It provides limited vector commitment functionality in tapscript.
When evaluated, the OP_PAIRCOMMIT instruction:
Discussion: https://delvingbitcoin.org/t/op-paircommit-as-a-candidate-for-addition-to-lnhance/1216/12
This document has a few formatting issues, please make sure that the preamble matches the BIP 2 requirements and take a look at the rich diff to see whether it looks the way you intend.
Please note that the BIPs repository also accepts markdown files.
Added a discussion link to the PR description.
The original create date of OP_PAIRCOMMIT is 2024-03-15 this is the latest revision based on feedback from Anthony Towns. gist.github.com/moonsettler/d7f1fb88e3e54ee7ecb6d69ff126433b/revisions What date should go to the header?
Perhaps add a changelog with the revision based on Anthony Towns’ feedback followed by the initial version. Or use the date of the current draft revision as your starting point.
According to BIP 2:
The Created header records the date that the BIP was assigned a number, […]
Has this proposal been sent to the mailing list?
Not yet. Wanted to get it into an acceptable shape before I post it there.
Proposed to the mailing list, waiting for feedback.
1266@@ -1267,6 +1267,13 @@ Those proposing changes should consider that ultimately consent may rest with th
1267 | Gloria Zhao
1268 | Informational
1269 | Draft
1270+|- style="background-color: #cfffcf"
For Draft status PRs the background color is not specified
0|-
1266@@ -1267,6 +1267,13 @@ Those proposing changes should consider that ultimately consent may rest with th
1267 | Gloria Zhao
1268 | Informational
1269 | Draft
1270+|- style="background-color: #cfffcf"
1271+| [[bip-PC.md|PC]]
1272+| Consensus (soft fork)
1273+| PAIRCOMMIT
This has to match the title header in the preamble:
0| OP_PAIRCOMMIT
34+
35+If `OP_CAT` was available, it could be used to combine multiple stack elements,
36+that get verified with `OP_CHECKSIGFROMSTACK` as a valid state update.
37+
38+`OP_PAIRCOMMIT` solves this specific problem without introducing a wide range
39+of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
Alternatives we discussed:
Finally after weighing everything OP_PAIRCOMMIT was the simplest addition that got what we needed exactly in the most efficient way. It’s a minimal code change, very easy to reason about. Therefore we expect it to be the least controversial option.
Sadly a lot of the discussion is all over the place and on unsearchable mediums.
OP_PAIRCOMMIT on delvingbitcoin.
129+## Reference Implementation
130+
131+A reference implementation is provided here:
132+
133+https://github.com/lnhance/bitcoin/pull/6/files
134+
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.
OP_PAIRCOMMIT solves this specific problem without introducing a wide range
of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
OP_CAT allows for fine grained introspection possibly bigint operations and
extending the arithmetic capabilities of bitcoin script using lookup tables.
These would predictably allow for the same functionality as OP_CAT for
introspection purposes, since verification of a computation is largely
equivalent with carrying it out. Bigint and new arithmetic operations would
be hard or even impossible.
These would be of very limited general use and hard to rationalize without OP_CAT. Their complexity and resource cost is hard to justified for vector commitments only. Compatibility considerations with taproot MAST were also hard to resolve without knowing what other opcodes may be activated in the future.
The original idea would have limited the maximum size of OP_CAT output to a
size that is smaller than the smallest sighash preimage, thus disabling the
introspection capabilities and trivial ways to extend the arithmetic repertoir
of bitcoin script. This turned out to be an awkward, arbitrary and offering
weak .
A CTV template can be considered a sighash, however relaxing the relay policy to take advantage of this change would make various endogenous asset protocols more efficient, and therefore be controversial. There is also no consensus on how to use or how to structure the annex.
This was previosuly discussed and also implemented, it complicates the code and is a pretty arbitrary coupling of behaviors.
The obvious generalized solution for committing to n stack elements, however it involves looping and hard to argue about setting the proper limits to it.
12+</pre>
13+
14+## Abstract
15+
16+This BIP describes a new tapscript opcode `OP_PAIRCOMMIT` which
17+provide limited vector commitment functionality in tapscript.
0provides limited vector commitment functionality in tapscript.
28+Channel peers must be able to reconstruct the script that spends an
29+intermediate state.
30+
31+Using in sequence `OP_CHECKTEMPLATEVERIFY`, `OP_PAIRCOMMIT`, `OP_INTERNALKEY`
32+and `OP_CHECKSIGFROMSTACK` we can construct a rebindable channel that is also
33+optimal.
OP_PAIRCOMMIT proposal would be especially useful in combination with these other opcodes. Could you perhaps clarify whether and how OP_PAIRCOMMIT is useful by itself in absence of the other three opcodes you mention here?
LNhance at it’s core is CTV + CSFS. They together provide the core utility. IKEY is an optimization for not having to pay for the pubkey twice when the internal key can be used. PC is an optimization when CSFS has to commit to additional data required to recreate a spend script from an intermediate state, because OP_RETURN (to which CTV naturally commits to) is 4x more expensive in weight units for data availability.
PC could also be used by CHECKCONTRACTVERIFY to carry a complex state in the absence of CAT.
I don’t think anyone would find PC useful enough to activate in isolation without the aforementioned other opcodes.
It can do general merkle tree style commitments that are not compatible with other merkle tree structures in bitcoin.
We probably will make a new BIP for LNhance that has these other BIPs as “Relies on”.
Really leaning towards making a head BIP for LNhance and keeping the individual BIPs strictly limited to describing functionality without a lot of speculation on applications. (Which we would do after finalizing the individual ops.)
Is there a problem with this approach?
16+This BIP describes a new tapscript opcode `OP_PAIRCOMMIT` which
17+provides limited vector commitment functionality in tapscript.
18+
19+When evaluated, the `OP_PAIRCOMMIT` instruction:
20+* Pops the top two values off the stack,
21+* takes the "PairCommit" tagged SHA256 hash of the stack elements,
24+## Motivation
25+
26+To do LN-Symmetry contracts that don't require the nodes to keep old states,
27+we need to solve the data availability problem presented by unilateral closes.
28+Channel peers must be able to reconstruct the script that spends an
29+intermediate state.
The data that needs to be available for state n is:
0state-n-recovery-data { settlement-n-hash or state-n-balance }
This is needed to reconstruct the whole script for the nth state address that the funds move to by the channel peer that only holds the latest state, so he can spend to the latest state.
edit: Instead of an IF statement we could use different tap leaves (less optimal actually) and then merkle inclusion proof with sibling hashes would have to be known.
Is this mechanism useful for things outside of LN-Symmetry?
It was obviously our primary motivation, but I would not be surprised if other applications that use CSFS find a similar use for it.
One way to think about the 3 opcodes (CSFS, IKEY, PC) is we decompose a CSFS variant that can use 1 byte pubkey (internal key) and can commit to a vector of stack elements as message. They thus become more generally useful, but to a limited degree without additional opcodes.
Detailed introspection opcodes would also need vector commitments with CSFS, and as mentioned it would also be useful for CCV.
It looks like we gonna have to amend the PAIRCOMMIT BIP with some new use cases.
Turns out within certain practical limitations any computational function can be proven out in the form of a merkle tree.
The root hash of the merkle tree represents the function the leaves represent the inputs and output.
Any 32 bit arithmetic function can certainly be proven out with this method.
CAT itself with a limited set of inputs or limited input sizes can be proven out.
At this point it’s an open question if this enables new behaviors not enabled by taproot MAST itself?
Special thanks to: @JeremyRubin @Ademan @bigspider
edit:
Alternatively could consider imposing specific script limits that make PAIRCOMMIT explicitly less capable than MAST itself.
ACK on the current content.
Might want to consider mentioning the deleted key function verification scheme we learned from @bigspider?
I think I’ve changed my mind a bit. We were talking about computing a merkle tree for f(u32,u32) as if it was trivial but after a quick experiment it seems like that would take hundreds of years to compute (am I being dumb here?) Instead, you can compute mul(u32,u32) -> u32 using 3 mul(u16,u16)s which is feasible to compute. The witness size is worse, ~32 * 32 * 3 = 3072 instead of 32 * 64 * 1 = 2048, but computing the tree for mul(u16,u16) is feasible using a naive algorithm on commodity hardware.
The implication of this is that where a function can be decomposed into operations on smaller inputs, PAIRCOMMIT is massively more feasible to use than encoding things into a tap tree.
I think I’ve changed my mind a bit. We were talking about computing a merkle tree for
f(u32,u32)as if it was trivial but after a quick experiment it seems like that would take hundreds of years to compute (am I being dumb here?) Instead, you can computemul(u32,u32) -> u32using 3mul(u16,u16)s which is feasible to compute. The witness size is worse, ~32 * 32 * 3 = 3072instead of32 * 64 * 1 = 2048, but computing the tree formul(u16,u16)is feasible using a naive algorithm on commodity hardware.
Arithmetic and bitwise operations where inputs & outputs are small enough, can already be done in Script in cheaper ways. Merkle trees as lookup tables are only interesting for functions that are either extremely complex, or where preimages/images are larger than what Script can work with. Note that you can already do small indexed lookup tables more efficiently by just hard-coding them in Script (that is: push the table on the stack and use OP_PICK to read its entries), and these techniques are widely used (e.g. in BitVM).
The implication of this is that where a function can be decomposed into operations on smaller inputs, PAIRCOMMIT is massively more feasible to use than encoding things into a tap tree.
I think the only substantial difference is that in a Script where you need several lookups, you can do it with Merkle trees, while you can only do a single lookup with a precomputed taptree.
Proving general computation
Merkle trees can be used to prove out 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 it needs to be iterated over and hashed up.
Currently MAST trees can cover 128 bits of entropy space, which is well over the practical limits to iterate over and merklize. Therefore we assume this capability does not materially extend what computations are possible to prove out in bitcoin script. While
OP_PAIRCOMMITis 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 out computation, by eliminating the merkle path inclusion proofs, using
OP_CHECKSIGFROMSTACKtogether withOP_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.
Is this correct? Any suggestions? @Ademan @bigspider
The implication of this is that where a function can be decomposed into operations on smaller inputs, PAIRCOMMIT is massively more feasible to use than encoding things into a tap tree.
This is the main open question I believe. does it or does it not practically expand what we can already do? For example using PC to emulate smolCAT and using traditional methods with lookup tables could make 32 bit or even 64 bit arithmetics more feasible?
edit:
Within the 32 bit realm we can already use OP_ADD, I see little practical diff between <0x1234> <0x5678> CAT and <0x12340000> <0x5678> ADD.
And it sounds like 64 bit smolCAT would be way too expensive to generate (and also to interact with trustlessly).
(actually the above examples are wrong, because internally bitcoin script uses little endian, but should convey the point)
…
Arithmetic and bitwise operations where inputs & outputs are small enough, can already be done in Script in cheaper ways. Merkle trees as lookup tables are only interesting for functions that are either extremely complex, or where preimages/images are larger than what Script can work with. Note that you can already do small indexed lookup tables more efficiently by just hard-coding them in Script (that is: push the table on the stack and use OP_PICK to read its entries), and these techniques are widely used (e.g. in BitVM).
Even u16,u16 is quite a bit larger than I think is practical as a lookup table, but the efficiency for repeated operations is constant, obviously. The lookup table is less efficient for small numbers of operations (a u8,u8 table is 16k vs 1 u8,u8 proof is 0.4k) but the merkle tree loses quickly when those operations are repeated.
The implication of this is that where a function can be decomposed into operations on smaller inputs, PAIRCOMMIT is massively more feasible to use than encoding things into a tap tree.
I think the only substantial difference is that in a Script where you need several lookups, you can do it with Merkle trees, while you can only do a single lookup with a precomputed taptree.
Right, and the key point is these merkle trees and lookup tables rapidly become infeasible to compute as the input size grows, so multiple smaller lookups is significantly more useful.
EDIT: But your point is well taken that for smaller operations they can already be better accomplished by lookup tables.
… edit: Within the 32 bit realm we can already use OP_ADD, I see little practical diff between
<0x1234> <0x5678> CATand<0x12340000> <0x5678> ADD. And it sounds like 64 bit smolCAT would be way too expensive to generate (and also to interact with trustlessly).(actually the above examples are wrong, because internally bitcoin script uses little endian, but should convey the point)
Yeah for arbitrary 8 byte strings smolCAT seems infeasible to compute the table or merkle tree for. After a bit of conversation on IRC it could probably be feasible for arbitrary f(b[4],b[4]) -> b[8] with a custom ASIC¹ or maybe a cluster of FPGAs in a span of ~a few years but that would not be very useful for the average person.
Bit shifts over 32 bit integers seems pretty feasible though, that’s f(u32,u6)->u32 (maybe save some space by special casing shift = 0). it seems like my incredibly naive, unoptimized, single-core experiment could calculate that merkle tree in ~96 hours. Of course the proof is ~1.2k and users would likely need multiple, but the lookup table for that wouldn’t fit in a block anyway so maybe something new is possible?
You can also separate positive and negative shifts, and maybe break it down into multiple rounds of shifts 1-3 or something (or 1k for a proof for a constant shift)
[1]: afaik existing ASICs operate on block headers so couldn’t help
I think this BIP is already way more verbose than it was supposed to be.
It would be useful if we could reference it by a number. Can we get a BIP number assigned? Not asking for a merge yet.
popstack() has a redundant check @Psifour
Should we add this table to this BIP? And it’s not just vBytes but also the number of sigops to consider, which is a cost all nodes on the p2p network have to bear.
edit: I think it looks like this:
| Method | ChannelS | UpdateSc | UpdateWi | 1-Update | 2-Update |
|---|---|---|---|---|---|
| APO-annex | 2.25 vB | 28.25 vB | 25 vB | 305 vB | 461.5 vB |
| APO-return | 2.25 vB | 28.25 vB | 16.5 vB | 338.5 vB | 528.5 vB |
| CTV+CSFS+IKEY | 2.75 vB | 12.25 vB | 24.5 vB | 331 vB | 513 vB |
| CTV+CSFS | 11 vB | 20.5 vB | 24.5 vB | 347.5 vB | 537.75 vB |
| LNhance | 3 vB | 12.5 vB | 32.75 vB | 297.75 vB | 446.25 vB |
| CTV+CSFS+VAULT | 18.75 vB | 30 vB | 35 vB | 333.75 vB | 502.25 vB |
| rekey | 7.25 vB | 16.75 vB | 73.75 vB | 347.25 vB | 541 vB |
| Method | ForceC | Update | Settle | OP_RETURN |
|---|---|---|---|---|
| APO-annex | 1 SigOp | 1 SigOp | 1 SigOp | |
| APO-return | 1 SigOp | 1 SigOp | 1 SigOp | X |
| CTV+CSFS+IKEY | 1 SigOp | 1 SigOp | CTV | X |
| CTV+CSFS | 1 SigOp | 1 SigOp | CTV | X |
| LNhance | 1 SigOp | 1 SigOp | CTV | |
| CTV+CSFS+VAULT | 2* SigOp | 2* SigOp | CTV | |
| rekey | 3 SigOp | 3 SigOp | CTV |
* VAULT is not exactly a SigOp, but close enough. Has a budget cost of 1.2 SigOps.
It would be useful if we could reference it by a number. Can we get a BIP number assigned? Not asking for a merge yet.
Looking at the Motivation section, it seems to me that the main application for this proposal would be a construction that depends on three other undeployed proposals some of which are themselves draft stage or pre-draft. This proposal feels a bit hypothetical at this point. I’ll get back to you next week.
This proposal feels a bit hypothetical at this point.
While PAIRCOMMIT would only be truly useful with certain other future upgrades, it is proposed to activate in a bundle with said updates. We are in the process of trying to reach consensus on said package.
It’s unlikely I would withdraw OP_PAIRCOMMIT, unless OP_CAT got activated first.