It’s well-known that Bitcoin has a more constrained scripting system than other
blockchains like Ethereum or Solana, which more directly support running smart
contracts. Despite this, many people want build systems that interoperate with
Bitcoin, in part due to it being the oldest, longest lasting blockchain. To
overcome Bitcoin’s constraints, people combine its scripting capabilities with
properties of its supported signature schemes in order to enforce higher-level
properties with a mix of on-chain and off-chain logic.

In this post, we’ll take a glance at how Bitcoin’s scripting system works —
including its supported signature schemes and the system’s evolution — as
well as how several projects make use of them to build functionality not
directly expressible in Bitcoin.

Overview of Selected Features of Bitcoin​

Let’s first take a look at some of the key elements of Bitcoin’s system,
including BIP-340 Schnorr signatures, Bitcoin’s Script VM, common script types
like pay-to-pubkey hash and pay-to-script hash, extensions to the script system
like SegWit version 0, Taproot scripts, covenants, and an extension to the signature
scheme, FROST signatures.

BIP-340 Schnorr Signatures​

Bitcoin uses digital signatures to authorize transactions (or more
strictly, makes verification of signatures available as a primitive
condition that can be used as part of a script that authorizes
transactions).

Prior to the Taproot upgrade, Bitcoin exclusively used Elliptic Curve
Digital Signature Algorithm (ECDSA) signatures.

Since Taproot, it additionally uses Schnorr signatures in some contexts.

Both signature schemes use the Secp256k1 elliptic curve, whose elements
are 256 bits (32 bytes); both use a uniformly random (over the group
order) scalar d as a private key and multiply it by a fixed
generator G to generate a public key P; and both require a
unique, uniformly random, secret nonce value k per message m
signed, but their implementations of signing and verification differ.

In the below pseudocode, n denotes the group order and H denotes
a hash function, and type conversions between byte strings, integers
modulo n, and group elements are elided, as are various
well-formedness and parity checks; for full details, see Bitcoin’s ECDSA implementation↗
and Bitcoin’s Schnorr implementation↗.

Here are the ECDSA signatures:

def sign_ecdsa(d, m, k):
    e = H(m)
    R = k*G
    r = R.x
    s = pow(k, -1, n)*(e + r * d)
    return (r, s)

def verify_ecdsa(P, m, sig):
    (r, s) = sig
    e = H(m)
    u1 = e*pow(s, -1, n)
    u2 = r*pow(s, -1, n)
    R = u1 * G + u2 * P
    return R.x == r

Here are the Schnorr signatures:

def sign_schnorr(d, m, k):
    P = d * G
    R = k * G
    e = H(R.x || P.x || m)
    s = k + e * d
    return (R.x, s)

def verify_schnorr(P, m, sig):
    (r, s) = sig
    e = H(r || P.x || m)
    R = s * G - e * P
    return R.x == r

The idea of both is that the R point is a commitment to k
that’s binding (since R is uniquely determined by k, since
G is fixed) and hiding (due to the discrete logarithm hardness
assumption). The message is committed to by being hashed to e and
then turned into s with an equation over the scalar field of the
elliptic curve such that it can be checked that e is a unique
solution to an equation determined by k and d with only the
commitments R and P, without knowing k and d (the
discrete logarithms of R and P with respect to G, which only
the signer knows). With Schnorr, this equation is linear; with ECDSA, it
is not.

Both ECDSA and Schnorr signatures allow recovering the private key d
given a pair of signatures (sig1, sig2) on distinct messages (m1, m2) that use the same nonce k:

def recover_ecdsa(sig1, sig2, m1, m2):
    r1, s1 = sig1
    r2, s2 = sig2
    assert r1 == r2 # since k was reused
    e1, e2 = H(m1), H(m2)
    k = (e2 - e1) * pow(s2 - s1, -1, n)
    d = (s1 * k - e1) * pow(r, -1, n)
    return d

def recover_schnorr(P, sig1, sig2, m1, m2):
    r1, s1 = sig1
    r2, s2 = sig2
    assert r1 == r2 # since k was reused
    e1, e2 = H(r1 || P.x || m1), H(r2 || P.x || m2)
    d = pow(e2 - e1, -1, n) * (s2 - s1)
    return d

Additionally, if ECDSA and Schnorr signatures are generated for the same key
with the same nonce, that also allows recovering the private key, regardless of
whether or not the messages are distinct:

def recover_mixed(P, sig_ecdsa, sig_schnorr, m_ecdsa, m_schnorr):
    r_ecdsa, s_ecdsa = sig_ecdsa
    r_schnorr, s_schnorr = sig_schnorr
    assert r_ecdsa == r_schnorr # since k was reused
    r = r_ecdsa
    r_inv = pow(r, -1, n)
    e_ecdsa, e_schnorr = H(m_ecdsa), H(r_schnorr || P.x || m_schnorr)
    k = (s_schnorr + e_schnorr * e_ecdsa * r_inv) * pow(1 + e_schnorr * s_ecdsa * r_inv, -1, n)
    d = (k * s_ecdsa - e_ecdsa) * r_inv
    return d

Schnorr signatures permit signatures to be efficiently generated for an
aggregate key as if it was an individual key by summing partial signatures
produced with knowledge of the aggregate public key and the individual private
keys, without a single party holding the private keys that make up the
aggregate. If (d1, d2) are private keys, then sig = sign_schnorr(d1+d2, m, k1+k2) is a valid signature with public key (d1+d2)*G according to
verify_schnorr((d1+d2)*G, m, sig).

This can be produced by parties holding d1 and d2 separately
producing the r values independently as r1 = k1*G, r2 = k2*G, summing them to produce r, summing their public keys to
produce the aggregate public key (d1+d2)*G, computing a shared e = H(r || ((d1+d2)*G).x || m), generating individual s values
s1 = k1 + e * d1 and s2 = k2 + e*d2, and summing them to
produce the aggregate signature’s s = s1 + s2. Threshold signature
schemes like FROST specify more details of this process, such as exactly
what values to send and when, how to handle more than two signers, and
how to detect signers submitting incorrect values, since if intermediate values
are exchanged naively without additional validation, one party can cause the
other parties’ keys to be revealed.

Protocols for producing aggregate ECDSA signatures require more rounds than
those for producing aggregate Schnorr signatures, see A Survey of ECDSA
Threshold Signing↗ for details.

Unlike BLS signatures, Schnorr signatures cannot be aggregated after they are
created with individual public keys, since if (r1, s1) = sign_schnorr(d1, m, k1) and (r2, s2) = sign_schnorr(d2, m, k2), the intermediate values e1 = H(r1 || (d1*G).x || m) and e2 = H(r2 || (d2*G).x || m) used to compute s1
and s2 contain hashes of the individual public keys, which won’t match the
aggregated public key (d1+d2)*G.

Script VM​

Bitcoin scripts are programs for a stack-based virtual machine,
consisting of opcodes that operate on data at and near the top of the
stack. The stack elements are variable-sized strings of bytes, with a
limit of 520 bytes per stack element. Stack-based programs can be
composed by concatenating them, causing the second program to operate on
stack data produced by the first program as its input.

Each Bitcoin transaction output contains a script called its
scriptPubKey, which specifies the conditions under which the output
can be spent.

A subsequent transaction input, in order to spend a previous
transaction’s output, provides a script called its scriptSig that
provides an input stack for the output’s scriptPubKey. For an
input-output pair to be valid, the execution of the concatenated
scriptSig and scriptPubKey must halt without errors and with a
nonzero stack element at the top of the stack.

In summary:

• scriptPubKey is part of the output, and is a string of VM opcodes that checks whether the output’s spend conditions are satisfied.
• scriptSig is part of the input, and is what “unlocks” the scriptPubKey. It is also a string of VM opcodes, and it is prepended to scriptPubKey, and the combined bytecode is executed in the VM.

Pay-to-Pubkey Hash​

The most common scriptPubKey script, called pay-to-pubkey hash
(P2PKH), allows the output to be spent by a specific key pair by
requiring the entire transaction to be signed by that key pair.

It consists of OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG, which enforces that the corresponding scriptSig is of
the form <sig> <pubkey>, where <data> denotes an
instruction to push literal data.

In the combined script, <pubkey> OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY enforces that the top element of
the stack is the specified hash, leaving it on the stack (due to the
OP_DUP), and aborting (causing the transaction to be invalid) if the
hash doesn’t match or if the stack has too few elements.

After this, the remaining execution state <sig> <pubkey> OP_CHECKSIG verifies that sig is an ECDSA signature of the entire
transaction (with the exception of the script — to avoid circularity
that would require finding a fixed point of the hash function) signed by
pubkey.

Pay-to-Script Hash​

The Bitcoin Improvement Proposal
BIP-16↗
introduced the capability for a transaction output to specify its
spending condition as a fixed-sized hash as a commitment to the script,
instead of including the variable-sized script directly, deferring the
cost of storing the script until the transaction that spends it.

It does this by performing additional validation for transactions
spending an output whose scriptPubKey matches the form OP_HASH160 <data-of-length-20> OP_EQUAL, called a pay-to-script hash (P2SH)
transaction. Prior to BIP-16, Bitcoin implementations would interpret
this scriptPubKey as is, only requiring the top element of the stack
after the execution of the combined input scriptSig and output
scriptPubKey to have the specified hash.

Implementations that incorporate BIP-16 add additional validation requirements.
They treat the value that is hashed (innerScriptPubKey in the diagram) in the output’s scriptPubKey as a serialized script.
This serialized script functions as a new scriptPubKey.
During validation, the outer execution pushes the inner scriptSig onto the stack.
Then, this inner scriptSig is executed against the new scriptPubKey in an additional execution of the script VM.
This second script execution must also succeed for the transaction to be considered valid.
In essence, the outer execution verifies that the provided script matches the hash committed in the output, while the inner execution actually runs the spending conditions encoded in that script—the “script” part of “pay to script hash.”

SegWit Version 0​

Prior to
BIP-141↗,
SegWit scripts were included directly in transactions within blocks,
requiring them to be replicated to any entity that processes blocks at
all, even ones that don’t verify script executions. SegWit allows
transactions to opt in to storing their scripts in a separate witness
tree whose root hash is committed to as part of the main block and
whose bytes are considered to be one third as expensive as bytes in the
main block for the purposes of fee calculations. SegWit transaction outputs use
a small scriptPubKey consisting of metadata indicating what data to expect as
part of the witness (this metadata would fail to be a valid transaction prior
to the adoption of BIP-141, ensuring that only nodes that adopt BIP-141
consider spends of SegWit transaction outputs valid). The metadata includes a
version byte, for which BIP-141 only defines spending rules for version 0,
leaving other versions to be interpreted in a forward-compatible way by future
proposals. The scriptWitness field of a transaction input that spends a
SegWit output is not included in regular blocks, but is included in witness
blocks. A witness block can be verified against a regular block by hashing the
witnesses of transaction inputs and checking that it matches the root hash
committed to in the corresponding regular block.

SegWit V0 scriptPubKeys must be either a pay-to-witness pubkey hash (P2WPH) or
pay-to-witness script hash (P2WSH). A P2WPH script is a 20-byte
HASH160 hash of a public key, and it requires that the witness
script consists of a signature and a public key, which are verified as
if by a P2PKH script. A P2WPH script is three bytes shorter than a P2PKH
script, due to having the SegWit version byte instead of the four
opcodes in the P2PKH script. A P2WSH script is a 32-byte SHA-256 hash of
a script to be deserialized from the last element of the witness script,
verified against the script hash, and then concatenated with the
remainder of the witness script. This allows arbitrary scripts to be
used with SegWit, taking up a constant amount of block space in the size
of the script (instead of linear). P2WSH shares the advantage of P2SH of
not revealing the script until the output is spent, and it additionally
saves on costs by moving the reveal of the script from the block to the
witness.

Taproot scripts​

BIP-341↗’s
Taproot defines version 1 SegWit transaction outputs to contain a point
Q = P + H(P || m)*G and to be redeemable by either providing a
Schnorr signature of the transaction data with Q as a public key or
by providing P, a script s, and a proof that s is included
in the Merkle root m. (The inclusion proof is used to compute m,
which is then used to recompute Q and check that it matches the
Q in the SegWit metadata.) Similarly to P2WSH, scripts are not
revealed until they are present as a witness input in a transaction that
spends them.

If the signer knows the private key corresponding to the internal key
P (i.e., a scalar d such that P = d*G, they also know the
private key corresponding to the output key Q, since Q = P + H(P || m)*G = d*G + H(P || m)*G = (d + H(P || m)*G.

Several special cases of Taproot are significant:

• If m is a commitment to an empty Merkle tree, this provides a
  Schnorr variant of pay to pubkey, which allows for cheaper multi-sig
  transactions through key aggregation. This usage is similar to P2PKH.

• If P is constructed to have no known discrete log with respect to
  G, this provides a variant of P2SH that pays to a disjunction of
  scripts, but only the script that is executed costs witness space.

• The P key can be constructed to have no known discrete log in a
  deterministic way, P = H = lift_x(sha256(\"\\x04\"||G.x||G.y))
  (where lift_x produces the unique point on the curve with the
  specified x-coordinate and an even y-coordinate), which allows anyone to
  verify that a Taproot output is a commitment to a specific set of
  scripts, if they know which scripts.

• The P key can be constructed to have no known discrete log in a
  nondeterministic way, P = H + rG with a random r, which makes
  the Taproot output indistinguishable from one with an arbitrary pubkey
  but permits a proof that that the output’s creator does not know a
  discrete log for P by revealing r to the verifier (or by
  providing a zero-knowledge proof that r exists such that P was
  computed correctly).

Additionally, state machines with edge conditions verifiable in Bitcoin
script can be represented using Taproot by making use of transactions
that both consume and produce Taproot outputs (though covenants are
additionally required to constrain the output). BitVM and Babylon both encode
state machines this way, the former encoding a state machine for performing a
fraud proof of execution of a circuit and the latter encoding a state machine
for bonding and unbonding Bitcoin as stake.

Covenants and Covenant Emulation Committees​

A transaction’s output’s script cannot currently depend on arbitrary fields of
the transaction spending the output. If a script could depend on the outputs of
the transaction spending it, it could require that output’s script to have a
particular value. Making chains of these constraints to a fixed depth allows
encoding state machines: an output A could require one of the outputs of the
transaction spending it to be a script B with some minimum value, which can in
turn require an output with script C in the next transaction.

General covenants, with the OP_CAT opcode (which concatenates two stack
elements, are proposed to be re-enabled in
BIP-347↗)
and the OP_CHECKSIGFROMSTACK opcode (which would check a Schnorr signature of
arbitrary data, specified in
BIP-348↗).
They would allow scripts to depend on any field that was included in the
transaction’s hash, by including the fields of the transaction separately
(duplicating them as needed to perform additional checks), concatenating them
with OP_CAT, calculating the transaction hash and checking that it has a
valid signature with OP_CHECKSIGFROMSTACK, and checking that the
signature is also valid for the transaction itself with OP_CHECKSIG, which
ensures that the fields provided in the scriptSig are actually the fields
that the transaction consists of.

Template covenants, with the OP_CHECKTEMPLATEVERIFY opcode (specified in
BIP-119↗)
allow depending on a specific subset of the transaction’s fields, and they are
intended to make it infeasible to create self-propagating covenants (where a
script A requires that a copy of A be present in the next output’s script),
which are possible with covenants that make use of both OP_CAT and
OP_CHECKSIGFROMSTACK.

Since none of these opcodes are currently available in Bitcoin script,
protocols that would otherwise make use of covenants instead use a Covenant
Emulation Committee, which signs transactions that satisfy the constraints the
covenant would have enforced. Wherever the transactions’ scripts would enforce
the covenant, they instead check that at least some threshold of that
protocol’s Covenant Emulation Committee has signed the transaction. For sets of
transactions that enforce a state machine, the Covenant Emulation Committee
pre-signs the entire set of transactions at once. Since the transactions
require additional signatures to be submitted to Bitcoin (e.g., require a
signature from the user submitting the initial transaction to provide funds or
require signatures from other parties based on which actions they want to take)
the Covenant Emulation Committee is not in a position to submit the
transactions it’s cosigning early, and the user can choose to avoid entering
the state machine if the committee only signs a subset of them.

FROST Signatures​

Flexible round-optimized Schnorr threshold
signatures↗ (FROST Signatures for
short) is a protocol for distributed generation of a standard Schnorr
public key by n participants such that any t of them can produce
signatures for that message (i.e., t-of-n threshold signatures).
Unlike direct use of Shamir shares of the key, the corresponding private
key isn’t explicitly reconstructed during signing operations.

FROST-distributed key generation takes two rounds and produces a
long-term key that can be used to sign messages with the same set of
signers. In it, each participant generates random degree t - 1
polynomials, commits to the coefficients with a discrete-log commitment
scheme, produces proofs of knowledge of the constant coefficient (by
producing a Schnorr signature of a message containing the participant
index and the step in the protocol using the constant coefficient as a
signing key), broadcasts these commitments and proofs (so that each
participant can verify that each other participant is using their polynomial
consistently across messages), and sends per-participant shares of their
polynomial encrypted to each other participant. Each participant, as a
recipient, verifies each sender’s proof of knowledge and shares against the
sender’s commitments, and if there are no discrepancies, interpolates all the
senders’ shares to generate that recipient’s share of the signing key. If a
sender deviated from the protocol by sending shares inconsistent with their
commitments, this can be detected and key generation can be restarted with that
sender excluded.

FROST signing can either take two rounds (if one message is signed at a
time) or one round (if a batch of nonces is precomputed). Nonces are
generated using additive shares (with commitments to prevent an
individual malicious participant from canceling out the sum of the
randomness of the shares seen so far) and then converted to Shamir
shares, which are used together with the long-term signing shares to
compute signatures.

The non–batch-signing protocol, in addition to being described by the
aforementioned paper, is additionally specified in IETF
RFC-9591↗.

The frost_secp256k1_tr↗
crate is an implementation of FROST that produces signatures compatible
with BIP-340, and it is used by
zkBitcoin↗
and
Nomic↗.
Penumbra has the
decaf377-frost↗
implementation, which shares the frost-core implementation with
frost-secp256k1-tr but uses the decaf377 elliptic curve instead of
Secp256k1.

Previewing the Projects​

Now we’ll take a look at how a few projects use these elements in their own
software.

BitVM​

BitVM↗ makes use of Taproot scripts to
allow two parties (a prover and a verifier) to commit to a circuit,
creating a UTXO that is spendable by a party determined by the output of
the circuit if the prover provides inputs to evaluate the circuit or
that can be spent by the verifier if the prover evaluates the circuit
incorrectly or fails to provide inputs. Simply directly executing the
circuit in Bitcoin script would take linear script size in the number of
gates of the circuit, which would be impractical for larger circuits.
BitVM’s best case is a single transaction, with a 2-of-2 multi-sig on
the success path where the prover and verifier agree about the execution
of the circuit off chain. The fallback is an interactive fraud proof
that takes time proportional to the depth of the circuit (which is
typically logarithmic in the number of gates of the circuit), where
whichever party was incorrect about the circuit execution forfeits their
deposit to the correct party.

For the proof that this is universal, it suffices to compile boolean
circuits to only bit commitments and NAND gates, but for efficiency,
this can also be done with arithmetic circuits.

For each bit in the circuit, the prover creates preimages (similar to
wire labels in garbled circuits) w_0 and w_1, with a
corresponding bit-commitment script fragment OP_IF OP_HASH_160 <H(w_0)> OP_EQUALVERIFY <0> OP_ELSE OP_HASH_160 <H(w_1)> OP_EQUALVERIFY <1> OP_ENDIF. If w_i is published, this script
can be satisfied with <w_i> <i>, which results in the commitment
script succeeding, pushing value <i> to the stack. Someone knowing
neither preimage cannot satisfy the bit-commitment script. The prover
can set inputs to the circuit off chain by sending the preimages to the
verifier.

Each NAND gate of the circuit can be encoded as a script that takes
preimages a_i and b_j for the inputs and preimage c_k for
the output, uses the bit-commitment scripts for bits a and b to
push i and j onto the stack to compute i NAND j, uses the
bit-commitment script for c to push k onto the stack, and
verifies that k = i NAND j. For each gate in the circuit, and for
each round of the fraud proof protocol, the verifier constructs a
hashlock of a request for the prover to evaluate that gate by choosing a
preimage whose hash is required before executing the Taproot leaf
corresponding to the execution of that gate.

For the fraud proof, starting with the verifier, the prover and verifier
take alternate turns submitting transactions that progress the BitVM
state machine (which they pre-sign as if they were a covenant emulation
committee, in the absence of covenants). Edges that require it to be someone’s
turn have a check for that party’s signature in that edge’s leaf script. The
internal Taproot key is the aggregate of keys held by the prover and verifier,
which allows the 2-of-2 multi-sig to be used for a fast success path. Each
state also has a timelock path spendable by the counterparty to prevent the
party whose current turn it is from delaying indefinitely to prevent a loss.

To ensure that the prover does not evaluate the circuit inconsistently
(e.g., using c_0 for one equation as an output and then c_1 for
a different equation as an input or committing to different inputs on
chain and off chain), on verifier turns, the verifier immediately claims
the deposit if they have both preimages for the same gate (accomplished
by, for each gate, adding a Taproot leaf that requires both preimages
for that gate).

On the verifier’s turn, they can choose which gate for the prover to
evaluate next by publishing the preimage for the corresponding hashlock.
The prover then must provide the preimages for the inputs and output of
the chosen gate (by executing the leaf corresponding to that hashlock
and gate equation).

Since, by invoking the fraud proof, an honest verifier disagrees with
the prover about the circuit output, the first gate evaluation they
request will be for the overall output gate of the circuit. By providing
inputs to the final gate of the circuit, the prover reveals which
subtree their input disagrees with the verifier’s input on (since the
verifier can compute forward from their inputs off chain). Working
backwards, the verifier can reach inputs to the circuit in as many
rounds as the depth of the circuit, at which point they are in
possession of an input preimage they were given off chain that does not
match the prover’s on-chain input preimage, allowing them to claim the
deposit due to knowing both preimages for that input.

If the verifier is not able to prove an inconsistency in the prover’s
chosen inputs after the specified number of rounds, the prover evaluated
the circuit consistently with the inputs they gave the verifier and
claims the deposit.

Note that unlike garbled circuits or zero-knowledge proofs, neither
party’s inputs are private. The prover’s inputs are revealed directly
both on chain and to the verifier, and if the verifier were to obtain
their input commitments in a manner similar to garbled circuits off
chain, by using oblivious transfer with the prover to receive the
commitments corresponding to their input bits without revealing those
bits to the prover, the verifier would be able to issue spurious fraud
proofs, as the prover would not know which way to evaluate the circuit
for the verifier’s inputs. However, the circuit itself can be a verifier
for an inner zero-knowledge proof algorithm, which is done by
BitVM Bridge↗.

BitVM2​

BitVM2↗ provides a similar primitive to
BitVM, improving its flexibility and efficiency. Its program representation
differs from BitVM’s in that the prover commits to a Bitcoin script of
arbitrary length (which is split into chunks that individually do not exceed
the maximum supported size of a natively executed Bitcoin script) instead of a
boolean circuit. This representation allows more efficient fraud proofs, taking
a constant number of rounds independently of the number of chunks (in contrast
to BitVM’s logarithmic number of rounds in the number of gates of the circuit).
BitVM2’s fraud proofs are more flexible than BitVM’s by allowing any Bitcoin
user to participate as the verifier role if the prover claims an execution of
the program inconsistent with their input, rather than requiring setup for each
prover-verifier pair.

For each instance of the protocol, the prover creates a Lamport keypair for
each chunk of the program. The Lamport keypair generalizes the bit commitments
used in BitVM to fixed-length bitstrings. Unlike in BitVM, the Lamport
signatures aren’t directly used for fraud proofs by revealing part of the key
if multiple messages were signed (note that for 1-bit Lamport signatures, the
keys are equal to the signatures); they’re used instead as a signature scheme
that’s verifiable on data provided within a Bitcoin script (OP_CHECKSIG only
supports checking signatures on the transaction, and
OP_CHECKSIGFROMSTACK↗,
which would support this, isn’t part of Bitcoin yet). The prover uses these to
sign the stack that results from executing each chunk so that if their claimed
output for the entire program is incorrect, a verifier can execute the program
chunk-by-chunk off chain to find the first chunk whose execution mismatches the
input, at which point they have signatures on an input and output pair for a
chunk that can be verified to be inconsistent with the execution on chain.

The BitVM2 protocol makes use of a Covenant Emulation Committee, a committee of
signers that enforce that the prover’s transactions match what the protocol
requires by signing transactions that have the required structure with n-of-n
multi-signatures.

To commit to a program to be executed, the prover creates a set of six linked
transactions that enable the prover to later evaluate the program on an input
then either receive their deposit after a timelock if their output is
correct for that input or, for any verifier that notices that the claimed
output is incorrect, submit a fraud proof and receive the deposit instead.

These transactions are as follows:

• The Claim transaction takes a funding input (which can allow someone other
  than the prover to fund the use of this protocol) and specifies the initial
  stack value that the program to be verified will execute on. Its first output
  is a Taproot output with a timelock leaf for the PayoutOptimistic path and a
  leaf for the Assert path, which checks Lamport signatures for the claimed
  intermediate states to commit to them on chain. Its second output is a
  zero-value connector output that is used as an input to the PayoutOptimistic
  and Challenge transactions to ensure that they are mutually exclusive.
• The PayoutOptimistic transaction’s inputs are the timelock path of the
  Claim transaction’s Taproot output as well as its connector output, and its
  output is spendable by the prover. This is used to avoid posting the
  commitments to the intermediate states on chain if no challenge is issued
  during the timelock period.
• The Challenge transaction takes the Claim transaction’s connector input as
  well as a funding input that a verifier pays as a fee. Its output is spendable
  by the prover. This fee discourages verifiers from issuing spurious challenges,
  and covers the prover’s transaction costs for publishing the Assert
  transaction.
• The Assert transaction executes the Claim transaction’s output with the
  Assert path, which commits to the intermediate stack values and the Lamport
  keys on chain. Its Taproot output contains a leaf for challenging each chunk of
  the program to be verified (each of which checks the provided input and output
  signatures, runs the chunk, and checks that the output does not match the
  signed output) as well as a success-path leaf that allows the prover to spend
  the output with their public key after a timelock.
• The Disprove transaction for a chunk takes the Assert transaction’s Taproot
  output as its input, executing the leaf that shows incorrect execution of that
  chunk. It has two outputs, one of which must render a specified amount of the
  deposit unspendable; the other allows the remainder to be spent by the verifier.
• The Payout transaction takes the Assert transaction’s Taproot output as its
  input and executes the timelock path, allowing the prover to spend the deposit.

BitVM Bridge makes use of BitVM2 to allow bridging BTC to other
blockchains. It requires that the counterparty blockchain have a Bitcoin light
client and that the counterparty blockchain posts its state to Bitcoin. Users
send BTC to the counterparty blockchain by submitting a transaction to the
Bitcoin network that the counterparty recognizes, minting bridged BTC on the
counterparty. Users on the counterparty blockchain can send BTC back to Bitcoin
by burning the bridged BTC and producing a Groth16 proof that the bridged BTC
was burned, which is verified by BitVM2 instances on Bitcoin.

zkBitcoin​

zkBitcoin↗ allows the
creation of Bitcoin outputs whose spend conditions are given by
zero-knowledge circuits, called zkApps.

Unlike BitVM, it doesn’t verify the proofs directly on chain; it has a
committee of FROST participants that manage a threshold signature
wallet, which verifies zero-knowledge proofs that are sent to it and
signs the corresponding transactions.

The implementation uses PLONK as the proof system, which has universal
setup, allowing the committee to use the same setup for multiple
circuits. Creator of zkApps specify them as Circom programs, which
zkBitcoin’s tooling deploys to the Bitcoin network.

Stateless zkApps are created by Bitcoin transactions with two outputs
that are recognized by the zkBitcoin committee: one sends the value to
be managed by the zkApp to the committee’s address, and the other
commits to a hash of a circuit’s verification key by including it as an
immediate argument of an OP_RETURN (the latter output is unspendable).
The committee signs transactions that take a zkApp’s output as input
and include a fee to the committee if their submitter provides a
verification key that matches the zkApp’s verification-key hash and a
proof that verifies with that verification key and the transaction hash
as a public input. This allows the circuit to enforce additional
constraints on the structure of the transaction by deriving a
transaction hash within the circuit from private inputs and constraining
it equal to the public input.

Stateful zkApps are similar and additionally include an initial state
with the verification key in the transaction that creates them. In
addition to the transaction hash, the public inputs include an old and
new state and a withdraw and deposit amount. This allows the circuit to
enforce the computation of a new state from the old state and to enforce
state-dependent conditions on the withdraw and deposit amounts. The
committee enforces outside the circuit the withdraw and deposit amounts,
the stateful zkApp’s balance, and the transaction’s inputs and
outputs’ balance.

The zkBitcoin wallet is an ordinary wallet from Bitcoin’s perspective;
the outputs it can spend are Taproot outputs with no script paths, to
support the use of BIP-340 Schnorr signatures with FROST. As such, the
security of zkBitcoin depends on the members of the committee not having
their key material aggregated outside of the protocol, whether by
collusion or hacks, to reconstruct a private key that can spend the
zkBitcoin wallet’s funds with no constraints.

Babylon​

Babylon↗ is a proof-of-stake chain secured
by Bitcoin stake. Stakers delegate to finality providers, which sign
blocks on the Babylon chain to provide consensus. A finality provider’s
vote weight for consensus is proportional to the BTC delegated to them,
and stakers are issued BBN proportionally to the amount that they stake.
If a finality provider attempts a double-spend by signing two different
blocks for the same height, their delegators are slashed: 10% of their
stake is sent to an unspendable burn address, and the remaining 90% is
returned to the staker. In the absence of malicious finality-provider
behavior, stakers can unbond to receive their staked BTC in 101 Bitcoin
blocks (approximately 17 hours), a delay period in which slashing can
still occur.

Babylon uses Taproot scripts to ensure that the staked funds are only
usable according to this state machine. A staking transaction contains a
commitment to the staking output, a Taproot output consisting of three
scripts, with a deterministic unspendable internal key allowing the
staking transaction to be recognized by reconstructing it from a
delegation’s data.

The staking output’s first script is the timelock path, which requires
the Staker’s signature and a
BIP-112↗
OP_CHECKSEQUENCEVERIFY timelock based on the intended duration of
the delegation in the absence of unbonding. The second script is the
unbonding path, requiring the staker’s signature and a threshold of
Covenant Emulation Committee member signatures, which enforce
the structure of the unbonding transaction. The third script is the
slashing script, which requires the staker’s signature; a threshold of
Covenant Emulation Committee member signatures, which enforce the
structure of the slashing transaction; and the signature of the finality
provider being delegated to, whose key is revealed through the structure
of the signatures used for signing blocks if multiple blocks are signed
for the same height.

The unbonding transaction is presigned by the Covenant Emulation
Committee, consumes the staking output through the second path, and has
an unbonding output with two paths: a timelock path, which requires the
staker’s signature and the 101-block OP_CHECKSEQUENCEVERIFY
timelock, and a slashing path with the same requirements as the staking
output’s slashing path. The unbonding path of the staking script
requires the Covenant Emulation Committee member signatures in order to
ensure that it is only exercised with this delay period.

The slashing transactions (one each for the staking and unbonding
output) must be signed by the staker in order for their delegation to
become active. The Covenant Emulation Committee enforces that the
slashing transactions burn 10% of the delegation’s stake. The finality
providers sign proof-of-stake blocks with extractable one-time
signatures — a variant of Schnorr signatures that derive the nonce as
a function of the height for the block being signed — and the finality
provider’s key, submitting the R value to the Babylon chain before
the s value (similar to what discreet log contracts call committed
R-point signatures). This ensures that if they attempt to submit two
different s values for the same height, sufficient information is
present to recover the finality provider’s key via recover_schnorr,
which allows anyone observing a double-sign attempt to submit the
slashing transaction to the Bitcoin network. If a finality provider acts
honestly, signing at most one block per height, they’re using
unpredictable nonces, which does not reveal their private key.

Discreet Log Contracts​

Discreet log contracts↗ provide a
mechanism by which oracles can publish data external to the blockchain
(e.g., price feeds) in a way that allows a pair of parties to pre-sign
transactions, one of which can be spent based on the revealed price
(e.g., to effect a foreign-currency swap based on the price feed),
without the oracle having to receive any input from the parties (or even
being able to detect that its output is being used by any particular
transaction).

The oracle uses committed R-point signatures, a variant of Schnorr
signatures in which the nonce k is sampled and R = kG is
published before the message or s value of the signature are known.
For price feeds, the oracle commits to a different R point per asset and
per time window. When a price-feed entry is to be published, the oracle
signs the price as the message with the R-point associated with its time
window.

To perform a swap based on a future price from a price feed, two parties
fund a multi-signature output and pre-sign one transaction for each
possible message that spends that output. The transactions have outputs
with message-dependent values, with one output sending directly to the
counterparty as a P2PKH output and the other with a spend condition
(P2SH in the paper, but P2WSH/Taproot would also work) that allows it to
be spent immediately by one party with a tweaked public key that
incorporates sG for the corresponding message (which is computable
from the oracle’s public key, R, and the message) or after a timelock
by the counterparty.

The oracle’s signature s for a message allows the party with public
key A = aG to spend the P2SH output requiring pubkey A+sG, since
they know the corresponding private key a+s, allowing them to
immediately claim their own output from the swap from the P2SH output
and their counterparty to claim the P2PKH output. If a party publishes a
transaction for the wrong message, with public key A+s1G (consuming
the multi-signature output), the timelock path allows the counterparty
to claim the P2SH output, since the first party won’t know s1,
since the oracle will have published a distinct signature s2.

If an oracle signs multiple messages for the same R (e.g., multiple
prices for the same timeslot), they reveal their long-term private key
through nonce reuse. To handle the case where an oracle fails to provide
any output, the parties can pre-sign a transaction that refunds them both
from the multi-signature output with a timelock. To handle the case
where an oracle misreports a price without signing multiple messages, a
conjunction of oracles can be used, where a transaction is valid for a
price if all the oracles agree and the timelock refund path is used to
handle mismatches.

About Us​

Zellic specializes in securing emerging technologies. Our security
researchers have uncovered vulnerabilities in the most valuable targets,
from Fortune 500s to DeFi giants.

Developers, founders, and investors trust our security assessments to
ship quickly, confidently, and without critical vulnerabilities. With
our background in real-world offensive security research, we find what
others miss.

Contact us↗ for an audit that’s better
than the rest. Real audits, not rubber stamps.

*** This is a Security Bloggers Network syndicated blog from Zellic — Research Blog authored by Zellic — Research Blog. Read the original post at: https://www.zellic.io/blog/building-with-bitcoin