path: root/1f/2d4f4cfd636456a32af8f1709a2018a8c32eba

Return-Path: <pulat@yunusov.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 91173B78
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 11 Dec 2017 22:23:35 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f45.google.com (mail-wm0-f45.google.com [74.125.82.45])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9750F4FF
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 11 Dec 2017 22:23:33 +0000 (UTC)
Received: by mail-wm0-f45.google.com with SMTP id g75so17425909wme.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 11 Dec 2017 14:23:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=yunusov-org.20150623.gappssmtp.com; s=20150623;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to; 
	bh=uot4iAoS522N3638jyM9lpNmveTGx2jJUsNiHrTh3Wc=;
	b=oIZhnRQmPAJcXZQWY/tsCMtCyWdbNXJsq7Xei+Q1+Wsi7f36b0ilLKiNWn110w8MB8
	220ANISvFBCIazmsW5PAr6qIh5MEbxWyaMlaa2Ka6oeWzg3Ffd0Yq4Jj6Jdjre0iX392
	yqI4fV40aYSmCyVCCUki4E9G8MAfMnb+PUEegMBIfUqwhg2My5f1yvhMrtAZC0oUmfiH
	5iiBhjDtSzELgo4p89ImrQQhOzC3+2a9yCsaLLo05QQtVqg6siUI4wxjwVfhpoq25stv
	6IZPn3in1355nm896rLIbjIhhSwiW0ebBb9hET18LlWfogPn1tA7FnGF7CYDzmfdGSci
	AiAw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:references:in-reply-to:from:date
	:message-id:subject:to;
	bh=uot4iAoS522N3638jyM9lpNmveTGx2jJUsNiHrTh3Wc=;
	b=LwBn3GqUCRuW/ThiiH4if2anRueF0CTQJBA2OxN1RBhflV1h765y5zKFmpP7Xog/PV
	lEKSeqSNTT6Nk+HfhynFd4A9KPbDyTl09+vbtw+e3C6I5/TYcNU/PCcqVXHDPndSzwXt
	JfBqnajz3e3BZtaiT/AdcIUz1M1MqOaHcsGM43cEbTtdPEtvNo/IcIM4kjqQHiABr/hH
	QW/6Wcw7ah97qywcybX6wtGEjpAt5tbMlWSAyX1oiEDAOzAzH/wrrOjDevZA8oOlz4J+
	xOZKyA49SCd/wreuwv/k+UH7dFrquN6rHdRYTZJuLpcHQsU4SnqaOTu8xrU4v+5VB7tt
	+Wew==
X-Gm-Message-State: AKGB3mI5TqiwNgVct8w5zLp/Tv++Pb6j3F4vfkK8z/Gihf5xcwx246uM
	4IrjbDJD0zmXYH03vzur3pqX6DSe4hvRWFAob+E4X6+P
X-Google-Smtp-Source: ACJfBotLhTgrN3qeHVoPjhu6gM8J2ZDUS4fNpxg2cmSLJfS+qV72dv7VuipTT1ygpsdK8Lec6aTKK8DMAE0q6hnMask=
X-Received: by 10.28.26.6 with SMTP id a6mr2181405wma.8.1513031011983; Mon, 11
	Dec 2017 14:23:31 -0800 (PST)
MIME-Version: 1.0
References: <20171205101551.GA10265@fedora-23-dvm>
In-Reply-To: <20171205101551.GA10265@fedora-23-dvm>
From: Pulat Yunusov <pulat@yunusov.org>
Date: Mon, 11 Dec 2017 22:23:21 +0000
Message-ID: <CAC08FKvbbOsYWLieS+kgsdZByFiFXuQbBs1trvHuDAdG35HXkA@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary="001a114ca7fa00fa50056017fcb8"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Mon, 11 Dec 2017 22:24:18 +0000
Subject: Re: [bitcoin-dev] Scalable Semi-Trustless Asset Transfer via
 Single-Use-Seals and Proof-of-Publication
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 11 Dec 2017 22:23:35 -0000

--001a114ca7fa00fa50056017fcb8
Content-Type: text/plain; charset="UTF-8"

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
>

--001a114ca7fa00fa50056017fcb8
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div><span style=3D"color:rgb(49,49,49);word-spacing:1px;background-color:r=
gb(255,255,255)">Thank you for your post, Peter. Why is it necessary to cen=
tralize the p-o-p sidechain and have a maintainer? It seems the Bitcoin net=
work will secure the most critical element, which is the witness authentici=
ty. Wouldn&#39;t a second decentralized network be able to perform the func=
tions of the maintainer so the entire system is trustless?</span></div><div=
 dir=3D"auto"><font color=3D"#313131"><span style=3D"word-spacing:1px;backg=
round-color:rgb(255,255,255)"><br></span></font><div class=3D"gmail_quote" =
dir=3D"auto"><div>On Tue, Dec 5, 2017 at 5:16 AM Peter Todd via bitcoin-dev=
 &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l=
ists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail=
_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:=
1ex">I recently wrote this up for a client, and although the material has b=
een<br>
covered elsewhere, I thought being a worked example it might be of interest=
,<br>
particularly while sidechains are being discussed again.<br>
<br>
As per (1) I&#39;ve perhaps foolishly committed to making an even more fles=
hed out<br>
example, so peer review here before it gets to an even wider audience would=
 be<br>
appreciated. :)<br>
<br>
1) <a href=3D"https://twitter.com/petertoddbtc/status/937401676042039296" r=
el=3D"noreferrer" target=3D"_blank">https://twitter.com/petertoddbtc/status=
/937401676042039296</a><br>
<br>
<br>
tl;dr: We can do trustless with respect to validity, trusted with respect t=
o<br>
censorship resistance, indivisible asset transfer with less than 5MB/year/t=
oken<br>
of proof data, assuming token ownership is updated every two hours, at a ra=
te<br>
of ~500,000 transfers per second. The scalability of this scheme is linear =
with<br>
respect to update interval, and logarithmic with respect to overall transfe=
r<br>
rate.<br>
<br>
<br>
## Single-Use-Seal Definition<br>
<br>
Analogous to the real-world, physical, single-use-seals used to secure ship=
ping<br>
containers, a single-use-seal primitive is a unique object that can be clos=
ed<br>
over a message exactly once. In short, a single-use-seal is an abstract<br>
mechanism to prevent double-spends.<br>
<br>
A single-use-seal implementation supports two fundamental operations:<br>
<br>
=C2=A0 =C2=A0 Close(l,m) -&gt; w_l<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Close seal l over message m, producing a witnes=
s w_l<br>
<br>
=C2=A0 =C2=A0 Verify(l,w_l,m) -&gt; bool<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Verify that the seal l was closed over message =
m<br>
<br>
A single-use-seal implementation is secure if it is impossible for an attac=
ker<br>
to cause the Verify function to return true for two distinct messages m_1, =
m_2,<br>
when applied to the same seal (it _is_ acceptable, although non-ideal, for<=
br>
there to exist multiple witnesses for the same seal/message pair).<br>
<br>
Practical single-use-seal implementations will also obviously require some =
way<br>
of generating new single-use-seals. Secondly, authentication is generally<b=
r>
useful. Thus we have:<br>
<br>
=C2=A0 =C2=A0 Gen(p) -&gt; l<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Generate a new seal bound to pubkey p<br>
<br>
=C2=A0 =C2=A0 Close(l,m,s) -&gt; w_l<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Close seal l over message m, authenticated by s=
ignature s valid for pubkey p<br>
<br>
Obviously, in the above, pubkey can be replaced by any cryptographic identi=
ty<br>
scheme, such as a Bitcoin-style predicate script, zero-knowledge proof, etc=
.<br>
<br>
Finally, _some_ single-use-seal implementations may support the ability to<=
br>
prove that a seal is _open_, e.g. as of a given block height or point in ti=
me.<br>
This however is optional, and as it can be difficult to implement, it is<br=
>
suggested that seal-using protocols avoid depending on this functionality<b=
r>
existing.<br>
<br>
<br>
## Indivisible Token Transfer<br>
<br>
With a secure single-use-seal primitive we can build a indivisible token<br=
>
transfer system, allowing the secure transfer of a token from one party to<=
br>
another, with the seals preventing double-spends of that indivisible token.=
<br>
<br>
Each token is identified by its genesis seal l_0. To transfer a token, the =
most<br>
recent seal l_n is closed over a message committing to a new seal, l_{n+1},=
<br>
producing a witness w_{l_n} attesting to that transfer. This allows a recip=
ient<br>
to securely verify that they have received the desired token as follows:<br=
>
<br>
1. Generate a fresh, open, seal l_{n+1} that only they can close.<br>
2. Ask the sender to close their seal, l_n, over the seal l_{n+1}<br>
3. Verify that there exist a set of valid witnesses w_0 .. w_n, and seals<b=
r>
=C2=A0 =C2=A0l_0 .. l_n, such that for each seal l_i in i =3D 0 .. n, Verif=
y(l_i, w_i, l_{i+1})<br>
=C2=A0 =C2=A0returns true.<br>
<br>
Since a secure single-use-seal protocol prohibits the closure of a single s=
eal<br>
over multiple messages, the above protocol ensures that the token can not b=
e<br>
double-spent. Secondly, by ensuring that seal l_{n+1} can be closed by the<=
br>
recipient and only the recipient, the receipient of the token knows that th=
ey<br>
and they alone have the ability to send that token to the next owner.<br>
<br>
<br>
## Divisible Asset Transfer<br>
<br>
In the case of a divisible asset, rather than transferring a single, unique=
,<br>
token we want to transfer a _quantity_ of an asset. We can accomplish this =
in a<br>
manner similar how Bitcoin&#39;s UTXO-based transactions, in which one or m=
ore<br>
inputs are combined in a single transaction, then split amongst zero or mor=
e<br>
outputs.<br>
<br>
We define the concept of an _output_. Each output x is associated with a se=
al l<br>
and value v. For each asset we define a set of _genesis outputs_, X_G, whos=
e<br>
validity is assumed.<br>
<br>
To transfer divisible assets we further define the concepts of a _spend_ an=
d a<br>
_split_. A spend, D, is a commitment to a set of outputs x_i .. x_j; the va=
lue<br>
of a spend is simply the sum of the values of all outputs in the spend. A s=
plit<br>
commitments to a set of zero or seal/value, (l_i,v_i), tuples, with the sum=
<br>
value of the split being the sum of a values in the split.<br>
<br>
Spends and splits are used to define a _split output_. While a genesis outp=
ut<br>
is simply assumed valid, a split output x is then the tuple (D,V,i), commit=
ting<br>
to a spend D, split V, and within that split, a particular output i.<br>
<br>
A split output is valid if:<br>
<br>
1. Each output in the spend set D is a valid output.<br>
2. The sum value of the spend set D is &gt;=3D the sum value of the split V=
.<br>
3. i corresponds to a valid output in the split.<br>
4. There exists a set of witnesses w_i .. w_j, such that each seal in the s=
pend<br>
=C2=A0 =C2=A0set closed over the message (D,V) (the spend and split).<br>
<br>
As with the indivisible asset transfer, a recipient can verify that an asse=
t<br>
has been securely transferred to them by generating a fresh seal, asking th=
e<br>
sender to create a new split output for that seal and requested output amou=
nt,<br>
and verifying that the newly created split output is in fact valid. As with=
<br>
Bitcoin transactions, in most transfers will also result in a change output=
.<br>
<br>
Note how an actual implementation can usefully use a merkle-sum-tree to com=
mit<br>
to the split set, allowing outputs to be proven to the recipient by giving =
only<br>
a single branch of the tree, with other outputs pruned. This can have both<=
br>
efficiency and privacy advantages.<br>
<br>
<br>
<br>
## Single-Use-Seal Implementation<br>
<br>
An obvious single-use-seal implementation is to simply have a trusted notar=
y,<br>
with each seal committing to that notary&#39;s identity, and witnesses bein=
g<br>
cryptographic signatures produced by that notary. A further obvious refinem=
ent<br>
is to use disposable keys, with a unique private key being generated by the=
<br>
notary for each seal, and the private key being securely destroyed when the=
<br>
seal is closed.<br>
<br>
Secondly Bitcoin (or similar) transaction outputs can implement<br>
single-use-seals, with each seal being uniquely identified by outpoint<br>
(txid:n), and witnesses being transactions spending that outpoint in a<br>
specified way (e.g. the first output being an OP_RETURN committing to the<b=
r>
message).<br>
<br>
<br>
### Proof-of-Publication Ledger<br>
<br>
For a scalable, trust-minimized, single-use-seal implementation we can use =
a<br>
proof-of-publication ledger, where consensus over the state of the ledger i=
s<br>
achieved with a second single-use-seal implementation (e.g. Bitcoin).<br>
<br>
Such a ledger is associated with a genesis seal, L_0, with each entry M_i i=
n<br>
the ledger being committed by closing the most recent seal over that entry,=
<br>
producing W_i such that Verify(L_i, (L_{i+1}, M_i), W_i) returns true.<br>
Thus we achieve consensus over the state of the ledger as we can prove the<=
br>
contents of the ledger.<br>
<br>
Specifically, given starting point L_i we can prove that the subsequent led=
ger<br>
entries M_i .. M_j are valid with witnesses W_i .. W_j and seals L_{i+1} ..=
 L_{j+1}.<br>
<br>
A proof-of-publication-based seal can then be constructed via the tuple (L_=
i,<br>
p), where L_i is one of the ledger&#39;s seals, and p is a pubkey (or simil=
ar). To<br>
close a proof-of-publication ledger seal a valid signature for that pubkey =
and<br>
message m is published in the ledger in entry M_j.<br>
<br>
Thus the seal witness is proof that:<br>
<br>
1. Entry M_j contained a valid signature by pubkey p, for message m.<br>
2. All prior entries M_i .. M_{j-1} (possibly an empty set) did _not_ conta=
in<br>
=C2=A0 =C2=A0valid signatures.<br>
<br>
Finally, for the purpose of scalability, instead of each ledger entry M_i<b=
r>
consisting of a unstructured message, we can instead commit to a merkelized=
<br>
key:value tree, with each key being a pubkey p, and each value being an<br>
alleged signature (possibly invalid). Now the non-publication condition is<=
br>
proven by showing that either:<br>
<br>
1. Tree M_i does not contain key p.<br>
2. Tree M_i does contain key p, but alleged signature s is invalid.<br>
<br>
The publication condition is proven by showing that tree M_j does contain k=
ey<br>
p, and that key is associated with valid signature s.<br>
<br>
A merkelized key:value tree can prove both statements with a log2(n) sized<=
br>
proof, and thus we achieve log2(n) size scalability, with the constant fact=
or<br>
growing by the age of the seals, the ledger update frequency, the rate at w=
hich<br>
seals are closed, and the maximum size allowed for signatures.<br>
<br>
Note how a number of simple optimizations are possible, such as preventing =
the<br>
creation of &quot;spam&quot; invalid signatures by blinding the actual pubk=
ey with a<br>
nonce, ensuring only valid signatures are published, etc. Also note how it =
is<br>
_not_ necessary to validate all entries in the ledger form a chain: the<br>
single-use-seals guarantees that a particular range of ledger entries will =
be<br>
unique, regardless of whether all ledger history was unique.<br>
<br>
Proof-of-Publication ledgers are trustless with regard to false seal witnes=
ses:<br>
the ledger maintainer(s) are unable to falsify a witness because they are<b=
r>
unable to produce a valid signature. They are however trusted with regard t=
o<br>
censorship: the ledger maintainer can prevent the publication of a signatur=
e<br>
and/or or withhold data necessary to prove the state of the seal.<br>
<br>
<br>
# Performance Figures<br>
<br>
Assume a indivisible token transfer via a PoP ledger using Bitcoin-based<br=
>
single-use-seals, with the ledger updated 12 times a day (every two hours).=
<br>
Assume each ledger update corresponds to 2^32, 4 billion, transfers.<br>
<br>
The data required to prove publication/non-publication for a given ledger<b=
r>
update is less than:<br>
<br>
=C2=A0 =C2=A0 lite-client BTC tx proof:=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =3D ~1KB<br>
=C2=A0 =C2=A0 merkle path down k/v tree: 32 levels * 32bytes/level =3D=C2=
=A0 1KB<br>
=C2=A0 =C2=A0 key/value: 32 bytes predicate hash + 1KB script sig=C2=A0 =3D=
 ~1KB<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Total =3D ~3KB/ledger update<br>
<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 * 356 days/year * 12 updates/day =3D 13MB/year<=
br>
<br>
Now, those are *absolute worst case* numbers, and there&#39;s a number of w=
ays that<br>
they can be substantially reduced such as only publishing valid signatures,=
 or<br>
just assuming you&#39;re not being attacked constantly... Also, note how fo=
r a<br>
client with multiple tokens, much of the data can be shared amongst each to=
ken.<br>
But even then, being able to prove the ownership status of a token, in a<br=
>
trustless fashion, with just 13MB/year of data is an excellent result for m=
any<br>
use-cases.<br>
<br>
With these optimizations, the marginal cost per token after the first one i=
s<br>
just 1KB/ledger update, 4.4MB/year.<br>
<br>
--<br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> &#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org"=
 rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>

--001a114ca7fa00fa50056017fcb8--