Scalable Semi-Trustless Asset Transfer via Single-Use-Seals and Proof-of-Publication

I recently wrote this up for a client, and although the material has been covered elsewhere, I thought being a worked example it might be of interest, particularly while sidechains are being discussed again.

As per (1) I've perhaps foolishly committed to making an even more fleshed out example, so peer review here before it gets to an even wider audience would be appreciated. :)

1) https://twitter.com/petertoddbtc/status/937401676042039296

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:

    Close(l,m) -> w_l
        Close seal l over message m, producing a witness w_l

    Verify(l,w_l,m) -> 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:

    Gen(p) -> l
        Generate a new seal bound to pubkey p

    Close(l,m,s) -> 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, 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 >= 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 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 log2(n) sized proof, and thus we achieve log2(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.

Thank you for your post, Peter. Why is it necessary to centralize the p-o-p sidechain and have a maintainer? It seems the Bitcoin network will secure the most critical element, which is the witness authenticity. Wouldn't a second decentralized network be able to perform the functions of the maintainer so the entire system is trustless?

On Tue, Dec 5, 2017 at 5:16 AM Peter Todd via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:

> I recently wrote this up for a client, and although the material has been
> covered elsewhere, I thought being a worked example it might be of
> interest,
> particularly while sidechains are being discussed again.
>
> As per (1) I've perhaps foolishly committed to making an even more fleshed
> out
> example, so peer review here before it gets to an even wider audience
> would be
> appreciated. :)
>
> 1) https://twitter.com/petertoddbtc/status/937401676042039296
>
>
> 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:
>
>     Close(l,m) -> w_l
>         Close seal l over message m, producing a witness w_l
>
>     Verify(l,w_l,m) -> 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:
>
>     Gen(p) -> l
>         Generate a new seal bound to pubkey p
>
>     Close(l,m,s) -> 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, 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 >= 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 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 log2(n) sized
> proof, and thus we achieve log2(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.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

On Mon, Dec 11, 2017 at 10:23:21PM +0000, Pulat Yunusov wrote:

> Thank you for your post, Peter. Why is it necessary to centralize the p-o-p
> sidechain and have a maintainer? It seems the Bitcoin network will secure
> the most critical element, which is the witness authenticity. Wouldn't a
> second decentralized network be able to perform the functions of the
> maintainer so the entire system is trustless?

It's centralized in that writeup basically because centralizing it is *significantly* easier; it's not obvious how to maintain a proof-of-publication ledger in a decentralized, scalable, way.

In the centralized version it's obvious how to scale process by which the ledger is built via sharding: split the key range up as needed and assign each range to a separate server (be it an actual server, or a fault-tolerate cluster acting as a single server) that reports back to a master co-ordinator who builds the tree from the per-range sub-tips reported back by the shards. If required due to extreme scale, do this on multiple levels. Similarly, once the tree is built, storage and distribution can obviously be done via sharding.

In short, no matter how much the transaction rate on a PoP ledger grows, it's possible to meet demand by simply buying more hardware, and distributing the key space over a larger number of smaller shards.

But that simple architecture only works with trust: the coordinator is trusting the shards to build valid trees and distribute the results. Without trust, how do you ensure that actually happens? How do you pick who is assigned to what shard? How do you incentivise correct behavior?

That's not to say this is impossible - in fact my prior work on Treechains(1) is an attempt to do just this - but it's an orders of magnitude more difficult problem.

1) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004797.html,
   "[Bitcoin-development] Tree-chains preliminary summary", Mar 25th 2014,
   Peter Todd