Robin Linus RobinLinus

Optimizing On-Chain Costs for Publishing Proofs in BitVM-Style Bridges

Liam Eagen came up with a clever optimization for publishing proof data in BitVM-style bridges. Instead of Lamport/Winternitz signatures, it uses adaptor signatures. The message is split into chunks (e.g., 8- or 11-bit digits), and for each digit a Schnorr signature is provided.

Naively, the unlocking script would require a separate public key for each digit. The following construction shows how to use OP_CODESEPARATOR to instead require just a single public key, regardless of the number of digits. The key idea is to use OP_CODESEPARATOR to modify the sighash so that each adaptor signature is tied to a specific digit.

OP_CAT Enables Scalar Multiplication for EC Points

CAT can reduce curve point scalar multiplication to a subtraction in the scalar field.

Subtraction of field elements can probably be emulated in less than 250 (?) opcodes. For now, let's assume we had an (emulated) opcode, op_scalar_sub, for subtracting two elements of the scalar field of secp256k1.

Given secp's generator G, we want to compute for some scalar r the point R = rG

That is possible by hacking it into a Schnorr signature (R,s) for the key P = xG = 1G = G

Commit to a Bit Value using a Schnorr Signature

This is a bit commitment (e.g. for BitVM) which allows you to commit to the value of a 1-bit variable across two different UTXOs via Schnorr signatures. If Paul equivocates on the bit's value then he leaks his private key.

Surprisingly, the commitment script doesn't need to commit to anything specific. All semantics arise from the nonces in the partial signatures. That allows you to reprogram gates after compile time.

Commitment Script

The commitment script uses OP_CODESEPARATOR such that public key P can sign off on one of two execution branches in the script. Depending on which branch is signed, the script leaves 0 or 1 on the stack.

31-bit Commitment

This is a 31-bit commitment in Bitcoin Script.

OP_DUP
OP_TOALTSTACK

OP_DUP
<1073741824>

Covenants with CAT and ECDSA

In his article, CAT and Schnorr Tricks I, Andrew Poelstra showed how to emulate OP_CHECKSIGFROMSTACK-like covenants using only OP_CATand Schnorr signatures.

Here, we show that a similar trick is possible to emulate covenants using only OP_CAT and ECDSA signatures.

The High-Level Idea

Recall the ECDSA Signature Equation

Emulating CTV with a Trust-minimized Committee

The following describes a trust-minimized scheme to emulate op_checktemplateverify. The high-level idea is to run a everyone-can-join multi-party computation in a publicly verifiable way, by inscribing every message of the protocol into the Bitcoin blockchain.

A committee of Bitcoin stakers combined with onchain proofs of publication prevent censorship and guarantee liveness. The protocol is secure, that means the covenant is unbreakable, if there is at least one honest staker.

Naive Deleted-Key Covenant using a Single Co-Signer

Firstly, we discuss some "naive", oversimplified solutions, which do not work in practice. That helps to understand our final solution.

We want to emulate op_checktemplateverify scripts like

Some Day Peg

A two-way peg bridging BTC to other chains. It works similar to a perpetual one-way peg; however, instead of burning the BTC they are locked up until a particular time in 20 years. Until then, the community has to figure out how to do peg-outs with, e.g., some sort of OP_ZKP_VERIFY or Simplicity.

We simply pretend that OP_NOP10 is OP_ZKP_VERIFY and let users lock BTC in the following script:

<program_hash> OP_NOP10
 OP_CLTV OP_2DROP

	<main>
	<h1>Seed Splitting</h1>
	<h3>Split your BIP39 seed phrase into two of three shards.</h3>
	<div class="row-reverse">
	<a onclick="example()">Example</a>
	</div>
	<textarea id="$seedphrase" placeholder="Enter 24 word seed phrase"></textarea>
	<div class="row-reverse">
	<button onclick="splitSeed()">Split</button>
	</div>

	#
	# This is a scheme to encrypt a backup of a t-of-n Multisig spending script
	# such that any combination of t-of-n xpubkeys can recover the missing (n-t) xpubkeys.
	#
	#
	# In this example, we encrypt the 5 xpubkeys of a 3-of-5 Multisig
	# and demonstrate how to recover from any 3 xpubkeys the other 2 missing xpubkeys.
	#
	# The scheme is a simple variation of Shamir's secret sharing.
	# It is nicely compact. The encrypted payload is only the size of 2 xpubkeys.

	#
	# A variation of Shamir's t-of-n Secret Sharing scheme,
	# which allows to use any `n` values as secret shares
	# at the expense of having to store `(n-t)` many public shares.
	# This overcomes a drawback of the orginal scheme,
	# which requires to use the secret shares resulting from the scheme.
	#
	# For example, for a 3-of-5 this requires to store 2 public points.
	#