Skip to content

Latest commit

 

History

History
251 lines (189 loc) · 8.95 KB

bip-0442.md

File metadata and controls

251 lines (189 loc) · 8.95 KB
  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

Abstract

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,
  • pushes the resulting commitment on the top of the stack.

Motivation

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 number of SHA256 iterations is minimized in the primary use case we can optimize for, which is LN-Symmetry. 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.

Specification

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

Implementation

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

Use in script

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

Use in LN-Symmetry

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

Use with future updates

Detailed introspection opcodes would also need vector commitments when used with OP_CHECKSIGFROMSTACK.

OP_CHECKCONTRACTVERIFY would also need a way to carry complex data.

Reference Implementation

A reference implementation is provided here:

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

Rationale

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.

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.

Behaviors LNhance tries to avoid introducing

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

Alternative approaches

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

Cost comparison of LN-Symmetry constructions

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
rekey 7.25 vB 16.75 vB 73.75 vB 347.25 vB 541 vB

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 they need to be iterated over and hashed into a merkle root.

MAST trees can currently 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 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.

Backward Compatibility

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.

Deployment

TBD

Credits

Jeremy Rubin, Brandon Black, Salvatore Ingala, Anthony Towns, Ademan555

Copyright

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

References

  1. LNhance bitcoin repository: lnhance
  2. LN-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_INTERNALKEY: BIP-349, BIN-2024-0004
  7. Tagged hash: BIP-340