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?
I meant that these explanations should be part of the BIP, not just part of the conversation here in the pull request comments.
While BIP-2 recommends that a single BIP contain a single key proposal or new idea. The more focused the BIP, the more successful it tends to be. If in doubt, split your BIP into several well-focused ones, I agree that background context like #1699 (review) ought to be here in the open source BIP, and not only as GitHub meta-data (review comments) or an entry in Delving.
PairCommit is generically useful as a concept, and I think that having things like this spec’d, implemented, and deployable is a positive good towards improving bitcoin.
Further, new things that synergize with exisiting older concepts having to go together into the same PR would create a disincentive for people to share and work on new ideas, since it would make them “less mature” as a package. For example, when I published the CTV V2 Hashing Spec WIP BIP, it would have made ZERO sense for that to go into the CTV BIP (or CTV PR, were it not merged), since it’s a standalone concept. A concept that now, thanks to me writing it up, can be discussed against PairCommit as an alternative.
wholeheartedly support this being a standalone BIP and PR.
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.
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.
11+ License: BSD-3-CLAUSE
12+</pre>
13+
14+## Abstract
15+
16+This BIP describes a new tapscript opcode `OP_PAIRCOMMIT` which
Needs a comma before “which” here.
0This BIP describes a new tapscript opcode `OP_PAIRCOMMIT`, which
83+}
84+```
85+### Use in script
86+
87+`OP_PAIRCOMMIT` can be used to commit to a vector of stack elements in a way
88+that is not vulnerable to various forms of witness malleability. It is however,
0that is not vulnerable to various forms of witness malleability. It is, however,
95+```
96+
97+### Use in LN-Symmetry
98+
99+The following assembly-like pseudo-code shows a possible LN-Symmetry channel
100+construction, that provides data availability to spend to the latest state from
0construction that provides data availability to spend to the latest state from
104+```text
105+# S = 500000000
106+# IK -> A+B
107+<sig> <state-n-recovery-data> <state-n-hash> | CTV PC IK CSFS <S+1> CLTV DROP
108+```
109+before funding sign first state template:
(If I understand what is meant here)
0before funding, first sign the state template:
133+
134+https://github.com/lnhance/bitcoin/pull/6/files
135+
136+## Rationale
137+
138+If `OP_CAT` was available, it could be used to combine multiple stack elements,
0If `OP_CAT` was available, it could be used to combine multiple stack elements
139+that get verified with `OP_CHECKSIGFROMSTACK` as a valid state update.
140+
141+`OP_PAIRCOMMIT` solves this specific problem without introducing a wide range
142+of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
143+
144+`OP_RETURN` could also be used for ensuring the availability of the state
0Alternatively, `OP_RETURN` could be used to ensure the availability of the state
140+
141+`OP_PAIRCOMMIT` solves this specific problem without introducing a wide range
142+of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
143+
144+`OP_RETURN` could also be used for ensuring the availability of the state
145+recovery data as `OP_CHECKTEMPLATEVERIFY` naturally commits to all outputs.
0recovery data, as `OP_CHECKTEMPLATEVERIFY` naturally commits to all outputs.
141+`OP_PAIRCOMMIT` solves this specific problem without introducing a wide range
142+of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
143+
144+`OP_RETURN` could also be used for ensuring the availability of the state
145+recovery data as `OP_CHECKTEMPLATEVERIFY` naturally commits to all outputs.
146+However the cost of that would be over 4 times higher in weight units.
0However, its cost in weight units would be over 4 times higher than that of using OP_PAIRCOMMIT`.
145+recovery data as `OP_CHECKTEMPLATEVERIFY` naturally commits to all outputs.
146+However the cost of that would be over 4 times higher in weight units.
147+
148+One way to think about the 3 opcodes (`OP_CHECKSIGFROMSTACK`, `OP_INTERNALKEY`,
149+`OP_PAIRCOMMIT`) is we decompose a `OP_CHECKSIGFROMSTACK` variant that can use
150+1 byte `OP_TRUE` public key (substitute for the *taproot internal key*) and can
0a 1-byte `OP_TRUE` public key (substituting for the *taproot internal key*) and can
146+However the cost of that would be over 4 times higher in weight units.
147+
148+One way to think about the 3 opcodes (`OP_CHECKSIGFROMSTACK`, `OP_INTERNALKEY`,
149+`OP_PAIRCOMMIT`) is we decompose a `OP_CHECKSIGFROMSTACK` variant that can use
150+1 byte `OP_TRUE` public key (substitute for the *taproot internal key*) and can
151+commit to a number of stack elements as message.
0commit to a number of stack elements as a message.
148+One way to think about the 3 opcodes (`OP_CHECKSIGFROMSTACK`, `OP_INTERNALKEY`,
149+`OP_PAIRCOMMIT`) is we decompose a `OP_CHECKSIGFROMSTACK` variant that can use
150+1 byte `OP_TRUE` public key (substitute for the *taproot internal key*) and can
151+commit to a number of stack elements as message.
152+
153+### Behaviours LNhance tries to avoid introducing
Per your spelling of the word in the next sentence after.
0### Behaviors LNhance tries to avoid introducing
153+### Behaviours LNhance tries to avoid introducing
154+
155+The following behaviors are out of scope for LNhance and should not be enabled
156+as a side effect without explicit consensus:
157+
158+* Fine grained introspection
0* Fine-grained introspection
154+
155+The following behaviors are out of scope for LNhance and should not be enabled
156+as a side effect without explicit consensus:
157+
158+* Fine grained introspection
159+* State carrying covenants
0* State-carrying covenants
186+
187+### Proving general computation
188+
189+Merkle trees can be used to prove out computation where the root of the tree
190+represents the *function* and the leaves represent the *inputs* and *output*.
191+There are practical limits to the entropy space for the *inputs* as it needs
0There are practical limits to the entropy space for the *inputs*, as they need
187+### Proving general computation
188+
189+Merkle trees can be used to prove out computation where the root of the tree
190+represents the *function* and the leaves represent the *inputs* and *output*.
191+There are practical limits to the entropy space for the *inputs* as it needs
192+to be iterated over and hashed up.
0to be iterated over and hashed.
189+Merkle trees can be used to prove out computation where the root of the tree
190+represents the *function* and the leaves represent the *inputs* and *output*.
191+There are practical limits to the entropy space for the *inputs* as it needs
192+to be iterated over and hashed up.
193+
194+Currently MAST trees can cover 128 bits of entropy space, which is well over
0MAST trees can currently cover 128 bits of entropy space, which is well over
190+represents the *function* and the leaves represent the *inputs* and *output*.
191+There are practical limits to the entropy space for the *inputs* as it needs
192+to be iterated over and hashed up.
193+
194+Currently MAST trees can cover 128 bits of entropy space, which is well over
195+the practical limits to iterate over and merklize. Therefore we assume this
0the practical limits to iterate over and merklize. Therefore, we assume this
192+to be iterated over and hashed up.
193+
194+Currently MAST trees can cover 128 bits of entropy space, which is well over
195+the practical limits to iterate over and merklize. Therefore we assume this
196+capability does not materially extend what computations are possible to prove
197+out in bitcoin script. While `OP_PAIRCOMMIT` is not limited to a height of 128,
0in bitcoin script. While `OP_PAIRCOMMIT` is not limited to a height of 128,
195+the practical limits to iterate over and merklize. Therefore we assume this
196+capability does not materially extend what computations are possible to prove
197+out in bitcoin script. While `OP_PAIRCOMMIT` is not limited to a height of 128,
198+that should not be practically feasible to utilize.
199+
200+There is a way to reduce the size of the witness for proving out computation,
0There is a way to reduce the size of the witness for proving computation
What date should go to the header?
The Created header records the date that the BIP was assigned a number (see BIP-2).
A few edit suggestions on first read.
I think this can potentially be assigned a number once the BIP-2 criteria are met. A non-exhaustive list:
“When the BIP draft is complete, a BIP editor will assign the BIP a number, label it as Standards Track, Informational, or Process, and merge the pull request to the BIPs git repository. “The BIP editors will not unreasonably reject a BIP. “Reasons for rejecting BIPs include duplication of effort, disregard for formatting rules, being too unfocused or too broad, being technically unsound, not providing proper motivation or addressing backwards compatibility, or not in keeping with the Bitcoin philosophy. “For a BIP to be accepted it must meet certain minimum criteria. “It must be a clear and complete description of the proposed enhancement. “The enhancement must represent a net improvement. “The proposed implementation, if applicable, must be solid and must not complicate the protocol unduly.”
174+* OP_CHECKSIGFROMSTACK on n elements as message
175+* OP_VECTORCOMMIT: generalized form for n > 2 elements
176+
177+### Cost comparison of LN-Symmetry constructions
178+
179+| Method | ChannelS | UpdateSc | UpdateWi | 1-Update | 2-Update |
0@@ -0,0 +1,252 @@
1+<pre>
2+ BIP: ?
0 BIP: 442
5+ Author: moonsettler <moonsettler@protonmail.com>
6+ Comments-Summary: No comments yet.
7+ Comments-URI: <links to wiki page for comments>
8+ Status: Draft
9+ Type: Standards Track
10+ Created: 2024-11-08
0 Created: 2024-12-09
0@@ -0,0 +1,252 @@
1+<pre>
2+ BIP: ?
3+ Layer: Consensus (soft fork)
4+ Title: OP_PAIRCOMMIT
5+ Author: moonsettler <moonsettler@protonmail.com>
6+ Comments-Summary: No comments yet.
The Comments-Summary header is optional, and the comment system has fallen out of use. (And will hopefully be sunset in the near future.)
1273@@ -1274,6 +1274,13 @@ Those proposing changes should consider that ultimately consent may rest with th
1274 | Gloria Zhao
1275 | Informational
1276 | Draft
1277+|-
1278+| [[bip-PC.md|PC]]
0| [[bip-0442.md|442]
Please also move the bip-PC.md file to bip-0442.md.
16+provides limited vector commitment functionality in tapscript.
17+
18+When evaluated, the `OP_PAIRCOMMIT` instruction:
19+* Pops the top two values off the stack,
20+* takes the "PairCommit" tagged SHA256 hash of the stack elements,
21+* pushes the resulting commitment on the top of the stack.
0* takes the "PairCommit" tagged SHA256 hash of the stack elements' lengths and values,
1* pushes the resulting 32-byte hash to the top of the stack.
21+* pushes the resulting commitment on the top of the stack.
22+
23+## Motivation
24+
25+To do [LN-Symmetry] contracts that don't require the nodes to keep old states,
26+we need to solve the data availability problem presented by unilateral closes.
While this was the original motivation for developing PAIRCOMMIT, I don’t think it’s the current motivation for introducing it standalone, or including it in LNHANCE.
Perhaps something more like:
When building scripts using
OP_CHECKSIGFROMSTACK, it is common to require a commitment to multiple items in a specific sequence and without malleability.OP_PAIRCOMMITenables efficient commitments of this type. Alternative methods for achieving these multiple commitments require an additional signature checking operation for each additional unordered commitment or 2 additional signature checks for each additional ordered commitment.One example of such a construction is [LN-Symmetry] which requires a single signature to commit both to the update CTV hash and the settlement CTV hash to ensure O(1) data storage requirements for each channel partner. Another is a complex delegation (delegating to various pubkeys after matching locktimes). Either of these contracts can be achieved without
OP_PAIRCOMMITbut they would require the use of a costlyOP_RETURNor 2 additional signature checks respectively.
Then (as we discussed) move the remaining symmetry discussion to its own section.
48+
49+`OP_PAIRCOMMIT` will push `SHA256(tagPC|cs(x1)|x1|cs(x2)|x2)` onto the stack.
50+
51+Where `|` denotes concatenation and `tagPC` is calculated according to
52+[BIP-340] tagged hash as `SHA256("PairCommit")|SHA256("PairCommit")` and
53+`cs(x)` means `CompactSize(x)`.
CompactSize defined?
133+https://github.com/lnhance/bitcoin/pull/6/files
134+
135+## Rationale
136+
137+If `OP_CAT` was available, it could be used to combine multiple stack elements
138+that get verified with `OP_CHECKSIGFROMSTACK` as a valid state update.
Add
Using
OP_CATfor this purpose requires additional opcodes to prevent malleability (e.g.0x0102 0x03 CATis identical to0x01 0x0203 CAT).
or similar.
136+
137+If `OP_CAT` was available, it could be used to combine multiple stack elements
138+that get verified with `OP_CHECKSIGFROMSTACK` as a valid state update.
139+
140+`OP_PAIRCOMMIT` solves this specific problem without introducing a wide range
141+of potentially controversial new behaviors, such as novel 2-way peg mechanisms.
0`OP_PAIRCOMMIT` solves this specific problem without introducing granular introspection
1via Andrew Poelstra's CAT and Schnorr Tricks.
142+
143+Alternatively `OP_RETURN` could be used to ensure the availability of the state
144+recovery data, as `OP_CHECKTEMPLATEVERIFY` naturally commits to all outputs.
145+However, its cost in weight units would be over 4 times higher than that of
146+using `OP_PAIRCOMMIT`.
147+
Multiple data commitments can also be achieved using ephemeral key delegation to bind the data items.
0witness: <asig> <a> <bsig> <b> <dsig> <dkey>
1script: TUCK DUP TOALT TOALT <key> CHECKSIGFROMSTACK VERIFY \
2 TUCK [check and consume b] FROMALT CHECKSIGFROMSTACK VERIFY \
3 TUCK [check and consume a] FROMALT CHECKSIGFROMSTACK
148+One way to think about the 3 opcodes (`OP_CHECKSIGFROMSTACK`, `OP_INTERNALKEY`,
149+`OP_PAIRCOMMIT`) is we decompose a `OP_CHECKSIGFROMSTACK` variant that can use
150+a 1-byte `OP_TRUE` public key (substituting for the *taproot internal key*) and
151+can commit to a number of stack elements as a message.
152+
153+### Behaviors LNhance tries to avoid introducing
191+Merkle trees can be used to prove computation where the root of the tree
192+represents the *function* and the leaves represent the *inputs* and *output*.
193+There are practical limits to the entropy space for the *inputs* as they need
194+to be iterated over and hashed into a merkle root.
195+
196+MAST trees can currently cover 128 bits of entropy space, which is well over
192+represents the *function* and the leaves represent the *inputs* and *output*.
193+There are practical limits to the entropy space for the *inputs* as they need
194+to be iterated over and hashed into a merkle root.
195+
196+MAST trees can currently cover 128 bits of entropy space, which is well over
197+the practical limits to iterate over and merklize. Therefore, we assume this
195+
196+MAST trees can currently cover 128 bits of entropy space, which is well over
197+the practical limits to iterate over and merklize. Therefore, we assume this
198+capability does not materially extend what computations are possible to prove
199+in bitcoin script. While `OP_PAIRCOMMIT` is not limited to a height of 128,
200+that should not be practically feasible to utilize.
should not be -> is
as in, it is practical to utilize deeper trees? (for this technique)
Did I miss a discovery?
I suppose a sparse tree could be deeper but that’s logically equivalent to reducing the bit size of the inputs afaict.
197+the practical limits to iterate over and merklize. Therefore, we assume this
198+capability does not materially extend what computations are possible to prove
199+in bitcoin script. While `OP_PAIRCOMMIT` is not limited to a height of 128,
200+that should not be practically feasible to utilize.
201+
202+There is a way to reduce the size of the witness for proving computation,
PAIRCOMMIT continues to grow on me.
Getting the primary benefits of OP_CAT without introducing ugly introspection seems like a clear win for bitcoin.
Better introspection should also be added in follow-up forks. Thanks for your work on this!
I get that there is a goal here to avoid introspection…
but it seems that it’d be more generically useful if the function were e.g., a TapBranch function, so then it could be used in the future with some other taproot editing opcodes.
e.g., if OP_TAPBRANCHCOMMIT were to lexicographic sort, then cat, then commit, you could do paircommit like functionality by doing:
<a> <b> TUCK OP_TAPBRANCHCOMMIT OP_TAPBRANCHCOMMIT
this works because while the first commit commits to either a||b or b||a, and also has sliceable errors (e.g., (a||b)[:i] and (a||b)[i:]), the second commit re-commits to <b> and it’s length which uniquely determines order and prevents sliceable errors.
One concern: OP_TAPBRANCHCOMMIT is witness “malleable”, in that items could show up in the witness stack in either order and get the same result. It’d still be possible to make non-malleable witnesses by requiring the stack elements to be in order with a OP_LEXSORT or equivalent functionality.
If we did OP_TAPBRANCHCOMMIT then with OP_CHECKCONTRACTVERIFY I believe you get TLUV behavior?
You can verify a tapleaf on the input and can also replace it with an other on the output?
To be honest the OP_PAIRCOMMIT domain separation was aimed to prevent the possibility of such uses as potentially being more controversial.
I think it’s actually less controversial, because if you do OP_TAPBRANCHCOMMIT you’re doing something that even once you have OP_CAT, is really handy to have (because sorting two strings is actually still pretty hard with CAT).
Whereas now you’re getting a lot of people thinking that paircommit is not so useful if CAT gets in eventually.
<a> <1> <b> OP_TAPBRANCHCOMMIT OP_TAPBRANCHCOMMIT
or maybe:
<a> <b> OP_SHA256 OP_TAPBRANCHCOMMIT
instead of:
<a> <b> OP_PAIRCOMMIT
So if I wanted to support both of these functionalities I would probably end up with 2 separate opcodes for them.
Maybe this is obvious to everyone else and I’m a slowpoke here, but PC+CSFS+CTV enables a kind of “multi-transaction-signature”. You sign a merkle root that commits to a bunch of CTV transaction templates, and you can provide an inclusion proof with PC with the signature.
I’ve been spitballing with someone about a multiparty eltoo scheme and came up with a way to bound the state resolution but without state carrying covenants it requires a possible field of ~2^N transactions (of which, at most N will end up on-chain), and every party shares N*(N+1)/2 signatures.
With PC+CSFS+CTV it still requires ~2^N transactions, but each party only needs to share their 1 signature over the merkle root.
EDIT: Not 100% sure it works for my mutliparty eltoo scheme just yet, but I’m still >50% confident it does… EDIT EDIT: More confident it works, but it looks like the number of transactions is exponential rather than polynomial… and so my estimate for how many signatures would need to be shared without the “multi-transaction-signature” commitment is probably way low. EDIT EDIT EDIT: I genuinely have no idea how I decided “multi-signature” was an acceptable term considering it already has a different meaning in Bitcoin… s/“multi-signature”/“multi-transaction-signature”/g
88+# pc-hash = PC(a, PC(b, c))
89+
90+<a> <b> <c> | PC PC <pc-hash> OP_EQUALVERIFY
91+```
92+
93+### Use in LN-Symmetry
123+ELSE
124+ <settlement-n-hash> CTV
125+ENDIF
126+```
127+
128+### Use with future updates
## instead of ### for this section and for “Use in LN-Symmetry” might suffice (e.g. moving them out of the Specification section).
194+| CTV+CSFS+IKEY | 10 WU | 48 WU | 98 WU | 1328 WU | 732 WU | CTV |
195+| CTV+CSFS | 43 WU | 81 WU | 98 WU | 1394 WU | 765 WU | CTV |
196+| LNhance | 11 WU | 49 WU | 131 WU | 1191 WU | 594 WU | CTV |
197+
198+*ChannelSc: channel script, UpdateSc: update script, UpdateW: witness is the
199+same size for both Force Close and Contest in LN-Symmetry, ForceC: total cost of unilateral close transactions*
Some of these abbreviations are just a few characters shorter than the actual term. How about something along the lines of:
0| Method | Channel Script | Update Script | Update Witness¹ | Force Close² | Contest | Settlement Mechanism |
1| :------------ | --------: | -------: | ------: | ------: | ------: | :----: |
2| APO-Annex | 8 WU | 113 WU | 100 WU | 1221 WU | 627 WU | SigOp |
3| APO-Return | 8 WU | 113 WU | 66 WU | 1359 WU | 765 WU | SigOp |
4| CTV+CSFS+IKEY | 10 WU | 48 WU | 98 WU | 1328 WU | 732 WU | CTV |
5| CTV+CSFS | 43 WU | 81 WU | 98 WU | 1394 WU | 765 WU | CTV |
6| LNhance | 11 WU | 49 WU | 131 WU | 1191 WU | 594 WU | CTV |
7
8¹ *witness is the same weight for both Force Close and Contest in LN-Symmetry*
9² *total cost of unilateral close transactions*
183+* OP_CHECKTEMPLATEVERIFY committing to the taproot annex in tapscript
184+* OP_CHECKSIGFROMSTACK on n elements as message
185+* OP_VECTORCOMMIT: generalized form for n > 2 elements
186+* ReKey: key delegation and multiple use of OP_CHECKSIGFROMSTACK
187+
188+### Cost comparison of LN-Symmetry constructions
0### Weight comparison of LN-Symmetry constructions
161+a 1-byte `OP_TRUE` public key (substituting for the *taproot internal key*) and
162+can commit to a number of stack elements as a message.
163+
164+### Behaviors LNhance tries to avoid introducing
165+
166+The following behaviors are out of scope for LNhance and should not be enabled
203+Merkle trees can be used to prove computation where the root of the tree
204+represents the *function* and the leaves represent the *inputs* and *output*.
205+There are practical limits to the entropy space for the *inputs* as they need
206+to be iterated over and hashed into a Merkle root.
207+
208+Taproot MAST trees can currently cover 128 bits of entropy space, which is over
What are “Taproot MAST trees”? The taproot BIPs speaks of “Script Trees” and MAST would be understood as “Merklized Alternative Script Trees” in the context of Taproot. On the other hand, MAST as described in BIP 114 and BIP 117 speaks of Merklized Abstract Syntax Trees where multiple leaves are used in combination.
You mention MAST here in the context taproot, where only a single leaf is ever used at once, but it seems to me that you might be thinking of Abstract Syntax Trees. Either way, it is not clear to me what you are referring to here, when you speak of the “entropy space covered by Taproot MAST trees” while treating leaves as “inputs and outputs”.
This section is jumping right in the middle of something. I’m not sure that the scenario is described sufficiently to understand what the supposed concern is, let alone why the supposed concern is not a concern. If this section is relevant to this BIP, I reckon that more context is necessary for the reader to understand why and how, e.g., add aa link to a description of this scheme, or provide a bit more explanation what this section is talking about.
IMO this is a problem in the taproot BIP series, where various individuals decided it pertinent to change a well understood acronym (MAST) to suit taproot, rather than resepcting an existing body of literature including other BIPs.
I’d rather the taproot BIPs get updated to reflect the terminology Merklized Abstract Syntax Trees (or Tap Script Merkle Commitments, TSMC, if we’re fond of confusing backronyming but should be less ambiguous in context) rather than Merklized Alternative Script Trees, which was a backronym.
22+* pushes the resulting 32-byte hash to the top of stack.
23+
24+## Motivation
25+
26+Currently, bitcoin lacks a way to hash multiple stack elements together. Which
27+means building Merkle trees or verifying inclusion in a tree is not supported.
0Currently, bitcoin lacks a way to commit to multiple stack elements together. It is common practice to hash a single item as part of a bitcoin script, either in hash/time locked contracts, or in pay-to-pubkey-hash (P2PKH) scripts, but there is no way to commit to multiple items with a single hash.
1
2In a contrived but demonstrative example, if PAIRCOMMIT existed in legacy script, P2PKH could be extended to pay-to-pubkey-time-hash with scriptPubKey `2DUP PAIRCOMMIT RIPEMD160 <hash> EQUALVERIFY CHECKLOCKTIMEVERIFY DROP CHECKSIG`. This script format for single signature, time-locked bitcoin could be transformed into an address format.
3
4With the ability to commit to pairs of elements, PAIRCOMMIT can be generalized Merklized commitments to a tree of elements with a single hash. On its own, this could enable a hash lock contract where the holder of any pre-image in a Merkle tree can unlock the spend, for example.
5
6If `OP_CHECKSIGFROMSTACK` is combined with PAIRCOMMIT, the ability to sign commitments to multiple items enables both of the above but as a form of delegation. In cases where any single item can be used to unlock an output, additional off chain signatures be simply can be used as an alternative to PAIRCOMMIT. However in cases where multiple items must be used for spending together, PAIRCOMMIT removes the need for complex laddering schemes to ensure that all items were authorized together.
29+`OP_PAIRCOMMIT` is a simple and efficient tool to commit to two stack elements,
30+in a way that makes length redistribution attacks infeasible.
31+
32+The number of SHA256 iterations is minimized in the typical use cases we can
33+optimize for. Since the Tag can be pre-computed as mid-state, it would only
34+take 1 or 2 hash cycles in validation for the unilateral close scenario.
28+
29+`OP_PAIRCOMMIT` is a simple and efficient tool to commit to two stack elements,
30+in a way that makes length redistribution attacks infeasible.
31+
32+The number of SHA256 iterations is minimized in the typical use cases we can
33+optimize for. Since the Tag can be pre-computed as mid-state, it would only
Does “Tag” here refer to this, as you are writing elsewhere in this draft?
0optimize for. Since the tagged SHA256 hash can be pre-computed mid-state, it would only
126+```
127+
128+### Use with future updates
129+
130+Detailed introspection opcodes would also need vector commitments when used
131+with `OP_CHECKSIGFROMSTACK`.
128+### Use with future updates
129+
130+Detailed introspection opcodes would also need vector commitments when used
131+with `OP_CHECKSIGFROMSTACK`.
132+
133+`OP_CHECKCONTRACTVERIFY` would also need a way to carry complex data.
136+
137+A reference implementation is provided here:
138+
139+https://github.com/lnhance/bitcoin/pull/6/files
140+
141+## Rationale
174+### Alternative approaches
175+
176+The following list of alternative approaches were discussed and rejected for
177+various reasons, either for expanding the scope or for unnecessary complexity:
178+
179+* OP_CAT
138+
139+https://github.com/lnhance/bitcoin/pull/6/files
140+
141+## Rationale
142+
143+If `OP_CAT` was available, it could be used to combine multiple stack elements
179+* OP_CAT
180+* SHA256 streaming opcodes
181+* Merkle operation opcodes
182+* 'Kitty' CAT: result or inputs arbitrarily limited in size
183+* OP_CHECKTEMPLATEVERIFY committing to the taproot annex in tapscript
184+* OP_CHECKSIGFROMSTACK on n elements as message
178+
179+* OP_CAT
180+* SHA256 streaming opcodes
181+* Merkle operation opcodes
182+* 'Kitty' CAT: result or inputs arbitrarily limited in size
183+* OP_CHECKTEMPLATEVERIFY committing to the taproot annex in tapscript
95+To do LN-Symmetry contracts that don't require the nodes to keep old states,
96+we need to solve the data availability problem presented by unilateral closes.
97+Channel peers must be able to reconstruct the script that spends an
98+intermediate state.
99+
100+Using in sequence `OP_CHECKTEMPLATEVERIFY`, `OP_PAIRCOMMIT`, `OP_INTERNALKEY`
The pseudocode below might be clearer if the acronyms are defined beforehand
0Using in sequence `OP_CHECKTEMPLATEVERIFY` (`CTV`), `OP_PAIRCOMMIT` (`PC`), `OP_INTERNALKEY` (`IK`)
(idem for CSFS on the next line)