[bitcoin-dev] Scalable Semi-Trustless Asset Transfer via Single-Use-Seals and Proof-of-Publication

[Pulat Yunusov]

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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20171211/8d130370/attachment.html>