Short Proofs for Bitcoin Native Tokens

Abstract

A Bitcoin Native Token (BNT) recipient checks every hop back to the deploy (draft BRC-251, #320, test 2). Draft BRC-255 (#335) defines that walk and the proof package that carries it. The package grows with every trade. This document keeps it short however long an asset trades. The recipient still decides validity itself, from transactions named by txid and proofs it checks.

The main rule is the step proof (§4), a trustless checkpoint. It proves that a transaction follows the BRC-255 rules back to a deploy, the recipient checks it, and the walk stops there. Whoever made the proof is not trusted, since a false one fails the check. Wallets pass step proofs to each other in the package, and a recipient may refuse a transfer whose walk back to the newest proof is longer than its limit. Three smaller rules cut what is sent, with or without proofs. Any party may serve a transaction by txid. A sender may leave out history its recipient has probably validated. A sender chooses the inputs that leave the least history to send. Draft BRC-257 (#343) defines a proving service. A sender gets a proof there when it must pass one on and does not hold it, so wallets check proofs and never have to make them.

The same rules apply to the walk of a released Issuer-Permissioned Token (IPT) under draft BRC-253 (#333) §11, which uses the same package and also stops at accepted transactions.

Relationship to other documents

MUST, MUST NOT, SHOULD and MAY are requirements on a wallet that implements this document.

Specification

1. A transaction is named by its txid

Any party MAY store or serve a transaction of an asset's history: the wallet, another device of the same vault, the counterparty, or a public host. The recipient MUST accept a served transaction only when it hashes to the txid it asked for. A host that refuses a txid delays the walk. It cannot put a different transaction in its place.

A served transaction is still validated under BRC-255 §7, including the check of each input's claimed script and satoshis against the transaction behind it (BRC-255 §6). A wallet MAY keep one cache of transactions, shared across assets, payments and its own devices. Copying a transaction to another device copies bytes. That device still hashes and validates it.

2. Leave out history the recipient has probably validated

A wallet's frontier for an asset is the set of transactions of that asset it validated and recorded (BRC-255 §7).

A sender cannot see a recipient's frontier. A BRC-33 acknowledgement deletes the message from the recipient's box and tells the sender nothing. The sender does see its own delivery: the recipient's box accepted the BRC-255 §8 delivery and the package it carried.

When the recipient's box accepts a delivery, the sender MAY record that recipient as probably holding every transaction of that package. The record is only a guess about what a later package may omit. The recipient may not have read the message yet, may have refused it, or may have lost its records since. The record is not a validation for the sender, and the recipient cannot use it as its own. A wrong guess costs the recipient a fetch, never a wrong verdict.

To build a package for a recipient, the sender walks the asset's inputs back from the subject, as BRC-255 §7 step 3 does. It includes each transaction until every branch reaches the deploy, a transaction it has recorded for that recipient, or, for an IPT, an accepted transaction (BRC-253 §11). It omits everything behind those points. With no record for the recipient, the package carries the full walk.

The recipient walks as BRC-255 §7 says. When it reaches an input whose transaction is neither in the package nor recorded, it takes it from its cache, asks the sender with { "t": "need", "txids": [...] } (BRC-255 §6), or fetches it by txid, and validates it. A fetch that fails leaves the output uncredited. Omitting a transaction never makes an output valid.

The sender records on delivery, not on validation, so a later delivery can arrive while the one it relies on is still unread. A recipient SHOULD process queued deliveries in the order its box returns them, and MAY take a missing transaction from any other message it holds, under §1.

3. Spend the inputs that leave the least history

When more than one set of resolved inputs covers the amount, the sender SHOULD choose the set that minimizes the transactions §2 includes for that recipient. Ties SHOULD go to the inputs this wallet validated most recently.

The choice does not change validity. A payment that spends an older branch is still valid, and the recipient walks whatever arrives.

4. Step proofs

A step proof is a trustless checkpoint. It lets a recipient stop the walk at a transaction without the history behind it. The recipient trusts no one for it, because it checks the proof itself. Its size and its check stay the same however long that history is.

Claim. The claim of a transaction P names P and every asset whose outputs in P are valid under BRC-255 §4 and §7, with the deploy rules a spender needs:

claim:  txid (32 bytes, internal order) ‖ count (u16 LE) ‖ asset*
asset:  asset id (20) ‖ flags (u8) ‖ [max (u64 LE)] ‖ [size (u64 LE)]
flags:  1 item, 2 auth, 4 max follows, 8 size follows

Assets are in ascending id order, so a claim has one encoding.

Step program. The step program proves a batch: one or more transactions, each after the members it spends. It reads the batch, every transaction a member spends that is not in the batch, and a step proof for each of those that carries an asset. It verifies those proofs, then applies BRC-255 §4, member by member, to every asset the member spends or writes. An input that spends a deploy output counts that deploy's supply and rules. Any other input of an asset counts only when its transaction's claim, from a verified proof or an earlier member, names the asset. The program commits its own verifying key digest followed by the claims of the members that have an asset output no later member spends, in batch order. A batch of one transaction commits that transaction's claim, and a chain of transfers commits only the last one's. The program accepts a parent's proof only when that proof committed the same digest, so one pinned key covers every proof in a chain.

The program checks neither scripts nor deploys. Bitcoin checks scripts. A transaction is mined only when every input unlocks, so every ancestor of a mined transaction passed script validation. The recipient checks each deploy itself under BRC-255 §2 and §3, since it already holds each one.

Accepting a step. A recipient MAY stop the walk at transaction P for asset A when all of these hold:

1. The proof verifies under the pinned verifying key, and its public values begin with that key's digest.
2. A claim the proof commits has txid P and names A.
3. The recipient holds P itself, from the package or its cache, and checks each claimed script and satoshis against it (BRC-255 §6).
4. P is mined, shown by a BRC-67 Merkle path against the recipient's headers, or miners have accepted the transaction that spends it.
5. The recipient holds A's deploy, and it reads as an asset under BRC-255 §2 and §3.

The transfer that spends P is still validated under BRC-255 §7, scripts included. The step stands in only for the history behind P.

Delivery. A package (BRC-255 §6) MAY carry "steps": { "<txid>": { "type": "<proof type>", "proof": "<hex>" } }. With a step for P, the sender includes P in txs and omits what lies behind it. A wallet that does not read steps asks for the missing history with need (BRC-255 §6) and walks as before.

Walk limit. A recipient MAY refuse a transfer whose walk, from the transfer back to the newest accepted step or the deploy, is longer than the recipient's limit. A recipient SHOULD set its limit at 1,000 transactions or more, so a short history needs no proof. A walk takes about 4 ms per transaction (measured: 11.3 ms for three hops, with SPV and every input script), so 1,000 transactions take about 4 s and a million about an hour, before fetching them. A prover serving a busy token SHOULD keep its newest step within a few thousand transactions of the token's newest transfers, not a million behind. To transfer past a recipient's limit, the sender MUST attach a step for a transaction within that limit. A sender that holds no such step gets one from a prover.

Proving. Anyone may make a step proof: the sender, the issuer, or a proving service (draft BRC-257). A prover cannot make the program accept a false claim. It can only refuse to prove, in which case the recipient walks, up to its limit. Each transaction is proven once, and every later holder passes its proof on with the transfer. A prover MAY prove many transactions in one batch. That costs far less per transaction than proving each alone, and gives a proof of the same size (measured: 100 transfers in one batch took 483 s, about 5 s each, against about 4 minutes for a transaction proved alone). A wallet is not required to prove.

Proof type. This document registers bnt-step-1: an SP1 Groth16 proof over BN254 of the step program, encoded as public values length (u16 LE) ‖ public values ‖ the proof bytes SP1 writes for it. The program and its verifying key are pinned in a revision of this document when the program is frozen. Until then no proof of this type skips a walk.

A wallet MUST ignore a proof of an unregistered type, or one its verifier rejects, and walk the transactions instead.

Security considerations

• A sender can omit a transaction the recipient still needs. The recipient fetches it, or the output stays uncredited.
• A host can refuse a txid. It cannot substitute a transaction, because the hash would fail.
• The sender's record is a guess from delivery, not knowledge of the recipient's frontier. A delivery to one recipient says nothing about another, nor about a recipient that refused the transfer or reinstalled and lost its records. That wallet fetches what it does not hold.
• A step proof's claim names its own txid, so it cannot stand for another transaction. A prover can refuse to prove, but cannot make a false claim verify.
• A step proof leaves script validation to Bitcoin, so a recipient uses one only behind a mined transaction or one miners accepted (§4).
• Until the step program's key is pinned, no proof skips a walk.
• Spending an older branch changes the size of a package, not the result of the walk.
• An output whose transaction is not yet mined is still unconfirmed, as BRC-255 §7 says.

Implementations

• HandCash Desktop and Mobile implemented §1 to §3 for the earlier token encoding from version 1.3.555. They record validations, fetch a missing ancestor by txid, omit ancestors behind a recipient's accepted deliveries, and spend the inputs whose remaining walk is shortest. They ignore step proofs until the key is pinned. The BRC-255 port is in progress, and the step program is checked against HandCash Desktop's BRC-255 rules.
• Step program (SP1) has proved the split and the merge of a mainnet test token, with the merge's proof checking the split's proof inside it. Each is a 1,272,656-byte compressed proof, made in 155 s and 351 s on an 8 GB Apple M2. Chains of 10 and 100 synthetic transfers have each been proved in one batch, in 181 s and 483 s, with proofs of the same size. Neither is wrapped as bnt-step-1 (Groth16) yet, and the key is not pinned. The proofs, the program and its source, the runs' logs and the pinned mainnet transactions are in media/0252/bnt-proof. Its README lists each claim with the command that checks it, and cargo run --release --bin verify in its script directory checks the proofs.

References

1. Draft BRC-251 (#320) — Bitcoin Native Tokens (BNT): Definition and Wallet Duties
2. Draft BRC-255 (#335) — Bitcoin Native Tokens (BNT): Compact Format
3. Draft BRC-253 (#333) — Issuer-Permissioned Tokens (IPT): Countersigned Tokens and Items
4. BRC-30 — Transaction Extended Format (EF)
5. BRC-33 — PeerServ Message Relay Interface
6. BRC-67 — Simplified Payment Verification
7. Draft BRC-257 (#343) — Proving Service for Bitcoin Native Tokens