Proving Service for Bitcoin Native Tokens and 1Sat Ordinals

Abstract

A Bitcoin Native Token (BNT) recipient checks the token's history back to its deploy, and that history grows with every trade. A step proof of draft BRC-252 (#321) §4 is a trustless checkpoint. It stands in for the history behind a transaction, and the recipient checks it itself. Wallets pass step proofs to each other in the token package, and a recipient may refuse a transfer whose walk back to the newest proof is longer than its limit. Step proofs are for histories longer than that limit. A wallet checks a short history itself in milliseconds (11 ms for three hops on a laptop). Proving one transaction alone took about four minutes and 19 GB of memory on a laptop, so wallets check proofs and do not make them. A service proves many transactions in one batch, about 5 s each in a batch of 100. Checking a proof stays cheap at any depth.

A proving service is an overlay node that makes step proofs and serves them by txid. A sender uses one when it must pass on a proof it does not hold, because a recipient's walk limit needs a newer proof than the sender has or the sender lost one. The service is not trusted. Wallets check every proof themselves, so it can refuse or delay but cannot make a false claim count. Below a recipient's limit, the sender can send the history instead, as draft BRC-255 (#335) §6 says.

A service MAY also prove 1Sat ordinals of BRC-159. Their id is an origin that a recipient finds by walking back one transfer at a time, and that walk grows with every transfer. They have their own names, claim and step program (§9) and use the same submission, lookup and wallet duties. No step program for them is built yet.

A service MAY also audit Issuer-Permissioned Tokens (IPT) of draft BRC-253 (#333). An IPT recipient checks one transaction and trusts the issuer for the history behind it, so an audit is how anyone holds the issuer to its supply. An audit is a walk, not a step proof. Evidence of fraud proves itself, while a clean result is the service's word, which anyone can redo. No step program for IPT is defined yet.

The service uses the standard overlay interfaces: submission under BRC-22, lookup under BRC-24, names under BRC-87 and discovery under BRC-88.

Relationship to other documents

MUST, MUST NOT, SHOULD and MAY are requirements on a proving service or on a wallet that uses one, as each rule says.

Specification

1. Names and discovery

A proving service hosts topic manager tm_bnt_step and lookup service ls_bnt_step, and advertises them with SHIP and SLAP (BRC-88). A wallet finds services through SLAP.

2. Submitting

A wallet submits a transaction T to /submit with X-Topics: ["tm_bnt_step"] and BEEF holding T and every transaction T spends. The topic manager admits each output of T that reads as a BNT locking script under BRC-255 §1. Admission means the service will try to prove T. It does not mean T is valid.

A sender SHOULD submit each transfer it broadcasts, so a proof exists before the next holder needs it. A recipient MAY submit a transfer it accepts. A service treats a repeat submission of T as one.

3. Proving

The service proves T with the step program of BRC-252 §4 once both hold:

1. Each parent of T that carries an asset has a proof at the service, or is a deploy.
2. Miners have accepted T. A service that proves earlier risks proving a transaction that loses a double spend.

A service that lacks a parent's proof proves that parent first. When it does not hold the parent's own history, it answers that parent as unknown (§4), and a wallet MAY submit the walk's transactions oldest first, starting after the deploy.

A service MAY wait and prove several admitted transactions in one batch (BRC-252 §4), oldest first, which costs far less per transaction (see Cost). The batch's proof serves every member whose claim it commits. A member whose asset outputs are all spent by later members gets no claim. No wallet needs one, since the spenders' claims cover it.

A service MAY keep each proof in a form that is cheaper to check inside the step program, and convert it to a registered type when a wallet first looks it up. Only a type registered in BRC-252 §4 leaves the service.

4. Looking up

A wallet sends /lookup with service ls_bnt_step and query { "txids": ["<hex>", ...] }, naming every transaction whose proof it needs in one request. A service MAY cap the list and answer the first entries it accepts.

The answer is an output-list with at most one entry per named transaction: its lowest-index BNT output. The proof covers the whole transaction, so the other outputs add nothing. Transactions proved in one batch share its proof. The entry's beef holds the transaction, with its Merkle path once mined. The entry's context holds the proof:

context:  type length (u8) ‖ type (ASCII, e.g. "bnt-step-1") ‖ proof (encoded as BRC-252 §4 registers the type)

A service SHOULD answer in the application/octet-stream form of BRC-24, which shares one BEEF across entries.

5. Keeping proofs

A proof stays useful after the outputs it covers are spent, because the holder of a transfer that spends them attaches it for the recipient. A service SHOULD keep serving a proof at least until every transaction that spends the proven outputs is mined, and answers it whether or not those outputs are spent.

6. Policy

A service MAY charge, limit the rate of requests, or prove only the assets it chooses. Payment and authentication are layered on /submit and /lookup as BRC-22 and BRC-24 allow, for example with the paid lookup of BRC-195. An issuer MAY run a service for its own asset, and a market for the assets it lists.

7. Wallet duties

A wallet:

1. MUST check each proof under BRC-252 §4, whatever service served it.
2. Passes on the steps it holds under BRC-252 §4. When a recipient's walk limit needs a step it does not hold, or it lost one, it looks up the proofs of the transactions it spends before it sends the transfer, and attaches them under steps.
3. SHOULD ask more than one service it found through SLAP.
4. Refused by one service above a recipient's walk limit, asks another, or the asset's issuer. Without a proof from any of them, sends the history as BRC-255 §6 says, which the recipient MAY refuse.

A wallet is never required to prove.

8. Auditing IPT issuers

A service MAY audit IPT assets. It hosts topic manager tm_ipt_audit and lookup service ls_ipt_audit, advertised as in §1. A wallet submits an IPT transaction to /submit with X-Topics: ["tm_ipt_audit"] as in §2, and the topic manager admits each output that reads as an IPT locking script under BRC-253 §1.

The service audits each admitted transaction as BRC-253 §11 says. It resolves the transaction by steps 1 to 3 and walks its inputs back until every path reaches the deploy or a transaction it has already audited. When it lacks a parent, it answers that asset as not audited, and a wallet MAY submit the missing transactions oldest first.

A wallet sends /lookup with service ls_ipt_audit and query { "asset": "<asset id>" }. The context of the answer's entry is fail or clean:

A wallet SHOULD ask more than one service, SHOULD warn its user about an asset with checked evidence against the issuer, and MUST NOT refuse a transfer only because no audit has run.

9. Proving 1Sat ordinals

A service MAY prove 1Sat ordinals (BRC-159). It hosts topic manager tm_1sat_step and lookup service ls_1sat_step, advertised as in §1. The topic manager admits each output of a submitted transaction that holds exactly 1 satoshi. Submitting, proving, looking up and keeping proofs follow §2 to §5 under these names, with the 1Sat step program in place of BRC-252 §4's, and a lookup entry is the transaction's lowest-index 1-satoshi output.

Claim. The claim of a transaction P names P and the origin of each of its 1-satoshi outputs:

claim:  txid (32 bytes, internal order) ‖ count (u16 LE) ‖ link*
link:   vout (u32 LE) ‖ origin txid (32 bytes, internal order) ‖ origin vout (u32 LE)

Links are in ascending vout order, one for every 1-satoshi output of P, so a claim has one encoding. An output that starts a chain names itself as its origin.

Step program. The 1Sat step program proves a batch as BRC-252 §4's does: one or more transactions, each after the members it spends, with a step proof for each transaction they spend outside the batch whose claim they need. For each 1-satoshi output of a member it applies the transfer rule of BRC-159 ("Sat ordering and transfer"): when the input that holds the output's satoshi is a 1-satoshi output at the same offset, the output takes that input's origin from its transaction's claim. Otherwise the output is its own origin. An input's satoshis are 1 when its transaction's claim lists the output. Otherwise the program reads that transaction and hashes it to the input's txid. When the input that holds the satoshi is a 1-satoshi output whose transaction has no claim from a verified proof or an earlier member, the program fails rather than guess. The program commits its verifying key digest followed by the claims of the members with a 1-satoshi output that no later member spends, and accepts a parent's proof only when that proof committed the same digest. It checks no scripts, for the reason BRC-252 §4 gives.

Accepting a step. A recipient MAY stop its BRC-159 origin walk at output v of transaction P when all of these hold:

1. The proof verifies under the pinned verifying key of 1sat-step-1, and its public values begin with that key's digest.
2. A claim the proof commits has txid P and a link for v.
3. The recipient holds P and sees that output v holds 1 satoshi.
4. P is mined, or miners have accepted the transaction that spends it, as BRC-252 §4 requires.

The link's origin is then the token's origin. The recipient fetches the origin transaction by its txid and reads any inscription itself under BRC-160. A sender MAY pass a step with the transfer, in the steps form of BRC-252 §4. A recipient that gets none looks one up.

Proof type. This document registers 1sat-step-1: an SP1 Groth16 proof over BN254 of the 1Sat step program, encoded as BRC-252 §4 encodes bnt-step-1. 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.

Wallet duties are those of §7, with this section in place of BRC-252 §4.

Cost

A service proves every BNT transaction it serves once, oldest first, because a step proof needs its parents' proofs (§3). Its cost grows with the asset's transactions, not with how often wallets look proofs up. Proving many transactions in one batch (§3) cuts that cost, because most of a proof's time is a fixed cost that the batch shares. All runs below used SP1 v6.1.0 on the CPU of an 8 GB Apple M2 (bnt-proof, proofs/*.log), and every proof is 1,272,656 bytes whatever the batch holds.

The first three columns are measured. The estimates fit a line through the two batch runs: about 147 s fixed per proof plus about 3.4 s per transfer, which matches the program's flat cost of about 50,000 cycles per transfer in chains of 10 to 1,000 (proofs/cycles.log). At that rate one M2 keeps up with about 1,000 transactions an hour, or 24,000 a day. A batch needed about 15 GB of memory, which macOS supplied on the 8 GB M2 by compressing memory. The batch of 100 ran with one shard at a time (script/prove-small.sh), because SP1's default workers passed 24 GB. For comparison, a recipient walks 1,000 transactions in about 4 s (measured, 11.3 ms for three hops; BRC-252 §4), so proving pays for histories past a recipient's walk limit, not for those below it. Not measured: a batch of 1,000, a machine with enough memory, GPU proving, and the wrap into a small proof for delivery (16 GB of memory or more). The 1Sat step program (§9) is not built, so its cost is not measured.

Security considerations

• A service can refuse, delay, or answer that a proof is pending. It cannot make a false claim verify. The wallet asks another service or sends the history.
• A service can serve a proof for the wrong transaction or under the wrong key. The recipient's checks under BRC-252 §4 reject it.
• A submission shows the service the transaction and the address it came from. A wallet that wants to keep its activity private submits through a relay, or does not submit and sends the history.
• A service that proves before miners accept a transaction may prove one that is never mined. That costs the service, not the recipient, who uses a step only behind a mined or accepted transaction.
• A 1Sat service cannot give an output a false origin, because its step program applies BRC-159 and every claim names its own txid. It can refuse to prove, and the recipient walks to the origin itself.
• An audit service can hide fraud by answering clean, but cannot fake evidence, which every wallet checks itself. A wallet that asks several services is fooled only if all of them hide it.

Implementations

None yet. The step program agrees with HandCash Desktop's BRC-255 rules on its test vectors. It 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 SP1 proof, made in 155 s and 351 s on an 8 GB Apple M2 with a peak memory footprint of 19 GB. Chains of 10 and 100 transfers have each been proved in one batch, in 181 s and 483 s, with proofs of the same size. The proofs, the runs' logs and the experiment that checks each figure are published with draft BRC-252 (bnt-proof). These proofs are not yet wrapped into a small proof for delivery, and the verifying key of bnt-step-1 is not pinned, so no service can serve a checkable proof until it is. A transfer costs the program 83,776 cycles alone and about 50,000 in a batch, and a merge of 16 branches about 3.3 million.

No 1Sat step program or service exists yet.

No service audits IPT yet. The audit walk is tested in the test script of BRC-253, which catches a transfer of counterfeit units that the one-transaction check accepts.

References

1. Draft BRC-251 (#320) — Bitcoin Native Tokens (BNT): Definition and Wallet Duties
2. Draft BRC-252 (#321) — Short Proofs for Bitcoin Native Tokens
3. Draft BRC-255 (#335) — Bitcoin Native Tokens (BNT): Compact Format
4. BRC-22 — Overlay Network Data Synchronization
5. BRC-24 — Overlay Network Lookup Services
6. BRC-62 — Background Evaluation Extended Format (BEEF) Transactions
7. BRC-87 — Standardized Naming Conventions for BRC-22 Topic Managers and BRC-24 Lookup Services
8. BRC-88 — Overlay Services Synchronization Architecture
9. BRC-195 — Private Overlay Data and Recoverable Paid Lookup
10. BRC-159 — 1Sat Ordinals — Single-Satoshi Tokens and Origin Tracking
11. BRC-160 — 1Sat Ordinals — Inscription Envelopes