Emulating CTV with a trust-minimized deleted-key covenant

emulate-ctv.md

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

<next_tx> CHECKTEMPLATEVERIFY

with a deleted-key covenant having a one-time key

<next_tx_key> CHECKSIGVERIFY

so the functionary creates a <next_tx_signature> for a transaction, which matches the <next_tx> template, and then they delete the secret of <next_tx_key>. This way the covenant is unbreakable.

Problem

• What if the functionary does not delete the secret of <next_tx_key>?

Naive Deleted-Key Covenant using Multiple Co-Signers

We can run the same protocol with n functionaries. E.g., we can use MuSig for a n-of-n multi-signature. If only 1-of-n functionaries is honest and deletes their key, then the covenant is unbreakable.

Problems:

• Why should we trust these n functionaries?
• What if a functionary is offline or refuses to sign?

Deleted-Key Covenant using a Committee

The high-level idea is to design a censorship-resistant and trust-minimized CTV emulator by using a committee of Bitcoin holders which communicates on-chain.

Step 1: Initial Setup

Every Bitcoin holder can join the committee by staking BTC in a staking contract. For example, in a most simple time-locked contract, e.g., at least 0.01 BTC, locked for 1 year.

There is no slashing required because the time value of BTC is sufficient to prevent sybil attacks.

Step 2: Emulate CTV

Scenario: A particular user, Alice, wants to emulate CTV for a particular transaction myTx. Alice requests a signature from the committee.

Protocol:

1. Alice makes an onchain request to sign myTx
2. Each registered functionary publishes a signature onchain for myTx
3. Alice combines all n signatures to complete the covenant
4. Timeout: If there are signatures still missing after T blocks, then those functionaries are excluded from the committee and the signing protocol is restarted with the remaining stakers.

Advantages and Optimizations:

• Since joining the committee is permissionless, every user can make a covenant trustless for themselves by participating as a functionary and then deleting their own key.
• A single request can batch many covenants (many messages) to be signed using the same one-time key. For example, all stakers could be required to sign once a week all requests that occured in the chain during the last week.

Problems:

• Onchain is slow
• Each emulation requires at least n onchain commitments

Optimistic Deleted-Key Covenant using a Committee

Honest functionaries can send their signatures to Alice offchain. That means no onchain transactions are required. Only if a functionary is refusing to sign then Alice can force them to reveal their signature onchain or leave the committee.

Advantages and Optimizations:

• In the collaborative case, CTV emulation costs no onchain fees and is basically instant.
• Alice can buy a signature from a functionary by using an adapter signature and a PTLC.

Problems:

• How to prevent Alice from forcing all functionaries onchain?
  • Can a functionary prove that they revealed their signature to Alice?
  • Maybe Alice has to publish an adaptor signature to pay each functionary she blamed, if they publish a correct signature
• How to facilitate the offchain communication?
  • Each functionary runs a web server?
• How to prevent the committee from getting too large?
  • Maybe adjust the minimum required staking amount dynamically?
  • Sample smaller subsets using randomness, e.g., from block headers?
• In the worst case, it might take a long while to kick all the malicious functionaries, one by one

Implementation Details

Implementation Details

Non-interactive MuSig with One-time Keys

In the following, we discuss how stakers commit to their set of one-time keys to sign deleted-key covenants non-interactively.

1. Each signer publishes in their staking TX a set of l keys and nonces for signing. This allows them to sign l different covenants, until they have to publish more keys.
2. MuSig signing can be non-interactive, because for the i-th covenant, everybody can compute the corresponding i-th shared key and nonces from public data in the chain.
3. The i-th onchain transaction requesting a covenant has to contain the desired message to sign. Since also nonces are pre-committed, all signatures are deterministic in this scheme.

Simplification: We can use the ROAST mechanism. Each functionary inscribes with each signature a next pubkey and a next nonce. This allows to use an unlimted number of pubkeys and requires to store only one at at time.

Problems:

• This requires 3 * 64 = 196 vBytes per functionary per CTV call

Compact Embedded Consensus Protocols

A general problem of embedded consensus protocols is that users have to scan the entire bitcoin blockchain for relevant data.

A solution is to filter out most of the irrelevant data by using markers in the TXIDs. For example, we can define a TX to be valid for our protocol only if its TXID starts with a zero byte. Thus, the sender will be required to "mine" a valid TXID. That can be considered negligble effort, because a modern CPU can mine at about 65000 hashes per second, which already allows for a 2-byte marker. GPUs are about 100 - 1000x faster.

This reduces blocks to its TXIDs, which we can verify against the Merkle root in the block header. There are on average about 3500 TXs per block and a TXID has 32 bytes. This results in about 120 kBytes per block. In contrast, a full block, including witness data, is about 4 MB. That's a 30x reduction in data.

More Ideas for Improvements

• The timeout until publication, T, can be adjusted dynamically based on the recent average fee rate. We can derive the fee rate from the latest k blocks
• MuSig allows to compress the optimistic case. The joined signature proves that everyone agreed. However, for a message to be complete, they all have to publish their next nonce though.
• Is it maybe possible to build a tree of nested 2-of-2 MuSigs, which exposes in log(n), who's signtatures are missing?

Incentivizing the Committee

The following might be a solution to incentivize bitcoin holders to become a functionary and co-sign covenants.

Alice pays a fee to the committee. The fee is distributed fairly amongst all committee members by making it a lottery.

The onchain procedure to sign the covenant is altered only slightly:

1. Draw a lucky committee member. Derive publicly deterministic randomness. E.g. from the hash of the block, which completes the previous signature from the committee.
2. Make an onchain request for the committee to co-sign your staking covenant. In your request transaction, send your fee to the lucky committee member.
3. Collect the signatures from all committee members to complete your covenant.

(Alternatively, the fee could be distributed perfectly evenly, to one member after another.)

Hi Robin, great stuff! This is Fisher from Babylon.
Two quick questions:

1. by "If only 1-of-n functionaries is honest and deletes their key, then the covenant is unbreakable", does this honest functionaries have to delete the key, or it is sufficient to ask it not to sign a conflicting tx? I am asking because if it deletes its key, then 1) may it not be able to withdraw its own stake? 2) can each functionary only serve one tx that needs CTV emulation?
2. when Alice requests the committee member to sign tx, does she need to supply the tx to each member, or just supply a hash and say "hey sign this hash please". I guess the answer is the former because otherwise the committee member does not know what they are signing - t could even be transfer txs for their own bitcoins.