Veriable Data on Bitcoin:FlatMerkle Commitments, Refutable Proofs, and FlatChecks
Abstract
We give a method to publish data on Bitcoin and to verify properties of that data on Bitcoin itself, against a publisher who may lie. The data is a FlatMerkle le a structured byte string whose ordinary SHA-256 supports logarithmic inclusion proofs and logarithmic proofs of malformation placed in a transaction's annex or, at four times the cost but relayable by Bitcoin Core, in an output. We show that the publisher's ordinary Taproot signature, with a suitably chosen signature-hash type, binds the publisher to the published data in a form that a dispute can authenticate with a single SHA-256 compression plus the signature check, or with three compressions when no annex is used.
Claims about the data, and claims about such claims, are published as proof messages in two formats: a plain encoding, refuted by revealing it whole, and a traced encoding that stores the verier's output after each level, so that any false message is refuted by revealing at most ve of its elements. The format, chosen by a cost model that weighs challenge bytes against published bytes, is xed by public context so that no message can be read in two formats; chains of claims about claims settle at four logical elements. A dispute thus reduces to a few dozen SHA-256 compressions and one Schnorr verication per commitment too large for Bitcoin Script, but small enough to adjudicate with an interactive bisection game, a chunked script in the manner of BitVM2, or a garbled circuit.
The same technique veries any locally refutable verier, one whose every rejection is witnessed by a single check over a few words of a canonical trace. A FlatCheck commits that trace as a FlatMerkle le and adjudicates one check, with the accused bound to answer and the challenger holding her to the publication that was conrmed, under every signature hash type. Only the proof is published; the trace follows if and only if it is challenged, bound to the proof by the hash chain of its annex hash; and for a separable verier, whose groups each read a few of the proof's parts, the parts are published once each in independently authenticated annexes, a challenge forces the trace of one group and the parts it reads, and each check authenticates at most one of them. We give two examples: a toy L2 of signed transfers, whose 512-transfer batches cost 12,200 vbytes to claim, and a Bitcoin header-chain light client veried on Bitcoin itself, which claims a retarget period of 2,016 headers in 45,200 vbytes; a dispute over a local check costs about 37,500 and 49,200 vbytes, and one over a malformed trace about 77,100 and 99,800,independently of the number of groups. Verifying STARK proofs is another application.
Wealso remove FlatMerkle's restriction to power-of-two sizes without padding. All measurements are taken with an executable reference implementation, and the remaining gures are marked as estimates.
Read the full paper here:
