Previously published on the bitcoin-dev mailing list.

tl;dr: We can do trustless with respect to validity, trusted with respect to censorship resistance, indivisible asset transfer with less than 5MB/year/token of proof data, assuming token ownership is updated every two hours, at a rate of ~500,000 transfers per second. The scalability of this scheme is linear with respect to update interval, and logarithmic with respect to overall transfer rate.

Single-Use-Seal Definition

Analogous to the real-world, physical, single-use-seals used to secure shipping containers, a single-use-seal primitive is a unique object that can be closed over a message exactly once. In short, a single-use-seal is an abstract mechanism to prevent double-spends.

A single-use-seal implementation supports two fundamental operations:

• \(\operatorname{Close}(l,m) \to w_l\) — Close seal \(l\) over message \(m\), producing a witness \(w_l\).
• \(\operatorname{Verify}(l,w_l,m) \to \operatorname{bool}\) — Verify that the seal \(l\) was closed over message \(m\).

A single-use-seal implementation is secure if it is impossible for an attacker to cause the Verify function to return true for two distinct messages \(m_1\), \(m_2\), when applied to the same seal (it is acceptable, although non-ideal, for there to exist multiple witnesses for the same seal/message pair).

Practical single-use-seal implementations will also obviously require some way of generating new single-use-seals. Secondly, authentication is generally useful. Thus we have:

• \(\operatorname{Gen}(p) \to l\) — Generate a new seal bound to pubkey \(p\).
• \(\operatorname{Close}(l,m,s) \to w_l\) — Close seal \(l\) over message \(m\), authenticated by signature \(s\) valid for pubkey \(p\).

Obviously, in the above, pubkey can be replaced by any cryptographic identity scheme, such as a Bitcoin-style predicate script, zero-knowledge proof, etc.

Finally, some single-use-seal implementations may support the ability to prove that a seal is open, e.g. as of a given block height or point in time. This however is optional, and as it can be difficult to implement, it is suggested that seal-using protocols avoid depending on this functionality existing.

Indivisible Token Transfer

With a secure single-use-seal primitive we can build a indivisible token transfer system, allowing the secure transfer of a token from one party to another, with the seals preventing double-spends of that indivisible token.

Each token is identified by its genesis seal \(l_0\). To transfer a token, the most recent seal \(l_n\) is closed over a message committing to a new seal, \(l_{n+1}\), producing a witness \(w_{l_n}\) attesting to that transfer. This allows a recipient to securely verify that they have received the desired token as follows:

1. Generate a fresh, open, seal \(l_{n+1}\) that only they can close.
2. Ask the sender to close their seal, \(l_n\), over the seal \(l_{n+1}\)
3. Verify that there exist a set of valid witnesses \(w_0 .. w_n\), and seals \(l_0 .. l_n\), such that for each seal \(l_i\) in \(i = 0 .. n\), \(\operatorname{Verify}(l_i, w_i, l_{i+1})\) returns true.

Since a secure single-use-seal protocol prohibits the closure of a single seal over multiple messages, the above protocol ensures that the token can not be double-spent. Secondly, by ensuring that seal \(l_{n+1}\) can be closed by the recipient and only the recipient, the receipient of the token knows that they and they alone have the ability to send that token to the next owner.

Divisible Asset Transfer

In the case of a divisible asset, rather than transferring a single, unique, token we want to transfer a quantity of an asset. We can accomplish this in a manner similar how Bitcoin’s UTXO-based transactions, in which one or more inputs are combined in a single transaction, then split amongst zero or more outputs.

We define the concept of an output. Each output \(x\) is associated with a seal \(l\) and value \(v\). For each asset we define a set of genesis outputs, \(X_G\), whose validity is assumed.

To transfer divisible assets we further define the concepts of a spend and a split. A spend, \(D\), is a commitment to a set of outputs \(x_i .. x_j\); the value of a spend is simply the sum of the values of all outputs in the spend. A split commitments to a set of zero or seal/value, \((l_i,v_i)\), tuples, with the sum value of the split being the sum of a values in the split.

Spends and splits are used to define a split output. While a genesis output is simply assumed valid, a split output \(x\) is then the tuple \((D,V,i)\), committing to a spend \(D\), split \(V\), and within that split, a particular output \(i\).

A split output is valid if:

1. Each output in the spend set \(D\) is a valid output.
2. The sum value of the spend set \(D\) is \(\ge\) the sum value of the split \(V\).
3. \(i\) corresponds to a valid output in the split.
4. There exists a set of witnesses \(w_i .. w_j\), such that each seal in the spend set closed over the message \((D,V)\) (the spend and split).

As with the indivisible asset transfer, a recipient can verify that an asset has been securely transferred to them by generating a fresh seal, asking the sender to create a new split output for that seal and requested output amount, and verifying that the newly created split output is in fact valid. As with Bitcoin transactions, in most transfers will also result in a change output.

Note how an actual implementation can usefully use a merkle-sum-tree to commit to the split set, allowing outputs to be proven to the recipient by giving only a single branch of the tree, with other outputs pruned. This can have both efficiency and privacy advantages.

Single-Use-Seal Implementation

An obvious single-use-seal implementation is to simply have a trusted notary, with each seal committing to that notary’s identity, and witnesses being cryptographic signatures produced by that notary. A further obvious refinement is to use disposable keys, with a unique private key being generated by the notary for each seal, and the private key being securely destroyed when the seal is closed.

Secondly Bitcoin (or similar) transaction outputs can implement single-use-seals, with each seal being uniquely identified by outpoint (txid:n), and witnesses being transactions spending that outpoint in a specified way (e.g. the first output being an OP_RETURN committing to the message).

Proof-of-Publication Ledger

For a scalable, trust-minimized, single-use-seal implementation we can use a proof-of-publication ledger, where consensus over the state of the ledger is achieved with a second single-use-seal implementation (e.g. Bitcoin).

Such a ledger is associated with a genesis seal, \(L_0\), with each entry \(M_i\) in the ledger being committed by closing the most recent seal over that entry, producing \(W_i\) such that \(\operatorname{Verify}(L_i, (L_{i+1}, M_i), W_i)\) returns true. Thus we achieve consensus over the state of the ledger as we can prove the contents of the ledger.

Specifically, given starting point \(L_i\) we can prove that the subsequent ledger entries \(M_i .. M_j\) are valid with witnesses \(W_i .. W_j\) and seals \(L_{i+1} .. L_{j+1}\).

A proof-of-publication-based seal can then be constructed via the tuple \((L_i, p)\), where \(L_i\) is one of the ledger’s seals, and \(p\) is a pubkey (or similar). To close a proof-of-publication ledger seal a valid signature for that pubkey and message m is published in the ledger in entry \(M_j\).

Thus the seal witness is proof that:

1. Entry \(M_j\) contained a valid signature by pubkey \(p\), for message m.
2. All prior entries \(M_i .. M_{j-1}\) (possibly an empty set) did not contain valid signatures.

Finally, for the purpose of scalability, instead of each ledger entry \(M_i\) consisting of a unstructured message, we can instead commit to a merkelized key:value tree, with each key being a pubkey \(p\), and each value being an alleged signature (possibly invalid). Now the non-publication condition is proven by showing that either:

1. Tree \(M_i\) does not contain key \(p\).
2. Tree \(M_i\) does contain key \(p\), but alleged signature \(s\) is invalid.

The publication condition is proven by showing that tree \(M_j\) does contain key \(p\), and that key is associated with valid signature \(s\).

A merkelized key:value tree can prove both statements with a \(\log_2(n)\) sized proof, and thus we achieve \(\log_2(n)\) size scalability, with the constant factor growing by the age of the seals, the ledger update frequency, the rate at which seals are closed, and the maximum size allowed for signatures.

Note how a number of simple optimizations are possible, such as preventing the creation of “spam” invalid signatures by blinding the actual pubkey with a nonce, ensuring only valid signatures are published, etc. Also note how it is not necessary to validate all entries in the ledger form a chain: the single-use-seals guarantees that a particular range of ledger entries will be unique, regardless of whether all ledger history was unique.

Proof-of-Publication ledgers are trustless with regard to false seal witnesses: the ledger maintainer(s) are unable to falsify a witness because they are unable to produce a valid signature. They are however trusted with regard to censorship: the ledger maintainer can prevent the publication of a signature and/or or withhold data necessary to prove the state of the seal.

Performance Figures

Assume a indivisible token transfer via a PoP ledger using Bitcoin-based single-use-seals, with the ledger updated 12 times a day (every two hours). Assume each ledger update corresponds to \(2^{32}\), 4 billion, transfers.

The data required to prove publication/non-publication for a given ledger update is less than:

lite-client BTC tx proof:                            = ~1KB
merkle path down k/v tree: 32 levels * 32bytes/level =  1KB
key/value: 32 bytes predicate hash + 1KB script sig  = ~1KB
                                               Total = ~3KB/ledger update

    * 356 days/year * 12 updates/day = 13MB/year

Now, those are absolute worst case numbers, and there’s a number of ways that they can be substantially reduced such as only publishing valid signatures, or just assuming you’re not being attacked constantly… Also, note how for a client with multiple tokens, much of the data can be shared amongst each token. But even then, being able to prove the ownership status of a token, in a trustless fashion, with just 13MB/year of data is an excellent result for many use-cases.

With these optimizations, the marginal cost per token after the first one is just 1KB/ledger update, 4.4MB/year.