From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 91173B78 for ; 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 ; Mon, 11 Dec 2017 22:23:33 +0000 (UTC) Received: by mail-wm0-f45.google.com with SMTP id g75so17425909wme.0 for ; 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 Date: Mon, 11 Dec 2017 22:23:21 +0000 Message-ID: To: Bitcoin Protocol Discussion , Peter Todd 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
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't a second decentralized network be able to perform the func= tions 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@l= ists.linuxfoundation.org> wrote:
I recently wrote this up for a client, and although the material has b= een
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 fles= hed 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 t= o
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 transfe= r
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:

=C2=A0 =C2=A0 Close(l,m) -> w_l
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Close seal l over message m, producing a witnes= s w_l

=C2=A0 =C2=A0 Verify(l,w_l,m) -> bool
=C2=A0 =C2=A0 =C2=A0 =C2=A0 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<= br> 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:

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

=C2=A0 =C2=A0 Close(l,m,s) -> w_l
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Close seal l over message m, authenticated by s= ignature 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<= br> 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<= br> 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 =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})
=C2=A0 =C2=A0returns 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 b= e
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
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 m= ore
inputs are combined in a single transaction, then split amongst zero or mor= e
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, whos= e
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
=C2=A0 =C2=A0set closed over the message (D,V) (the spend and split).

As with the indivisible asset transfer, a recipient can verify that an asse= t
has been securely transferred to them by generating a fresh seal, asking th= e
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<= br> 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 bein= g
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 i= s
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 i= n
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<= br> 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 simil= ar). 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
=C2=A0 =C2=A0valid 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<= br> 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<= br> 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 pubk= ey 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 t= o
censorship: the ledger maintainer can prevent the publication of a signatur= e
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:

=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
=C2=A0 =C2=A0 merkle path down k/v tree: 32 levels * 32bytes/level =3D=C2= =A0 1KB
=C2=A0 =C2=A0 key/value: 32 bytes predicate hash + 1KB script sig=C2=A0 =3D= ~1KB
=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

=C2=A0 =C2=A0 =C2=A0 =C2=A0 * 356 days/year * 12 updates/day =3D 13MB/year<= br>
Now, those are *absolute worst case* numbers, and there's a number of w= ays that
they can be substantially reduced such as only publishing valid signatures,= or
just assuming you're not being attacked constantly... Also, note how fo= r 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 i= s
just 1KB/ledger update, 4.4MB/year.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--001a114ca7fa00fa50056017fcb8--