Date: Tue, 5 Dec 2017 05:15:51 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20171205101551.GA10265@fedora-23-dvm>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="GvXjxJ+pjyke8COw"
Content-Disposition: inline
User-Agent: Mutt/1.5.23 (2014-03-12)
Subject: [bitcoin-dev] Scalable Semi-Trustless Asset Transfer via
 Single-Use-Seals and Proof-of-Publication
Precedence: list


--GvXjxJ+pjyke8COw
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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/t=
oken
of proof data, assuming token ownership is updated every two hours, at a ra=
te
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 ship=
ping
containers, a single-use-seal primitive is a unique object that can be clos=
ed
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 attac=
ker
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 identi=
ty
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 ti=
me.
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 recip=
ient
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 =3D 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 s=
eal
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 th=
ey
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 se=
al 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_ an=
d a
_split_. A spend, D, is a commitment to a set of outputs x_i .. x_j; the va=
lue
of a spend is simply the sum of the values of all outputs in the spend. A s=
plit
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 outp=
ut
is simply assumed valid, a split output x is then the tuple (D,V,i), commit=
ting
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 >=3D 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 s=
pend
   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 amou=
nt,
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 com=
mit
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 notar=
y,
with each seal committing to that notary's identity, and witnesses being
cryptographic signatures produced by that notary. A further obvious refinem=
ent
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 led=
ger
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_ conta=
in
   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 k=
ey
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 fact=
or
growing by the age of the seals, the ledger update frequency, the rate at w=
hich
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 witnes=
ses:
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:                            =3D ~1KB
    merkle path down k/v tree: 32 levels * 32bytes/level =3D  1KB
    key/value: 32 bytes predicate hash + 1KB script sig  =3D ~1KB
                                                   Total =3D ~3KB/ledger up=
date

        * 356 days/year * 12 updates/day =3D 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 to=
ken.
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 m=
any
use-cases.

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

--=20
https://petertodd.org 'peter'[:-1]@petertodd.org

--GvXjxJ+pjyke8COw
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQEzBAEBCAAdFiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAlomcdcACgkQJIFAPaXw
kftSBwf+LzqUX145L2IFavZGUckFeYH5s1GdzsvSqzkVj+Mep0VzBs5NlbsZ5Qut
UN9oOCPgUhUTF1VISPxLqJ6r3q6fGES98PIZ59PGYMioWTZzztrwXIxql4VLtl1k
tzmgu/sQ6pCirgjHFZKgUMcfhUgGDr0ISeJUM2WQr6CX1xcvM45dwWW1T40WrziI
Z9IJtU8h1TDVFpYEjNeUN+usnsh8AW9mU5om68ALDZBE7NDwqD/2rkRvPjOmpaEF
cNJoV3m3UNmLagA0Dxku/iNcR0fL97QQvR4eQPZXe6PDRKGj/6CTNPC6N46vFxPW
IZA9fdfHvGlq6mPD3HKcV23dyfKNog==
=cVem
-----END PGP SIGNATURE-----

--GvXjxJ+pjyke8COw--