path: root/7e/25d94aa636058373d6e348fa417e9ec31263ed

Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 1E7981318
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 14 Mar 2018 00:38:04 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149084.authsmtp.net (outmail149084.authsmtp.net
	[62.13.149.84])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A8C96576
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 14 Mar 2018 00:38:02 +0000 (UTC)
Received: from mail-c245.authsmtp.com (mail-c245.authsmtp.com [62.13.128.245])
	by punt21.authsmtp.com. (8.15.2/8.15.2) with ESMTP id w2E0bxFG056161;
	Wed, 14 Mar 2018 00:37:59 GMT (envelope-from pete@petertodd.org)
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
	[52.5.185.120]) (authenticated bits=0)
	by mail.authsmtp.com (8.15.2/8.15.2) with ESMTPSA id w2E0bvAk074166
	(version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); 
	Wed, 14 Mar 2018 00:37:58 GMT (envelope-from pete@petertodd.org)
Received: from [127.0.0.1] (localhost [127.0.0.1])
	by petertodd.org (Postfix) with ESMTPSA id EEB1840118;
	Wed, 14 Mar 2018 00:37:56 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
	id 0780320065; Tue, 13 Mar 2018 20:37:53 -0400 (EDT)
Date: Tue, 13 Mar 2018 20:37:52 -0400
From: Peter Todd <pete@petertodd.org>
To: Daniel Robinson <danrobinson010@gmail.com>
Message-ID: <20180314003752.GA3853@fedora-23-dvm>
References: <CAD438Ht8ewJDyGbcqjkZdRWn6Yy2sRH9H_3jg2gWSgoJkrAHVA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="17pEHd4RhPHOinZp"
Content-Disposition: inline
In-Reply-To: <CAD438Ht8ewJDyGbcqjkZdRWn6Yy2sRH9H_3jg2gWSgoJkrAHVA@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: f1a8a1ad-271f-11e8-9f3c-9cb654bb2504
X-AuthReport-Spam: If SPAM / abuse - report it at:
	http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
	aAdMdwYUFVQGAgsB Am4bW1ReU1p7XGs7 bghPaBtcak9QXgdq
	T0pMXVMcUwcdAU5H d0UeVR1zcQMIeXh3 bUIsCHEKVBV7JBJg
	QElVQ3AHZDJodWlJ UxNFflAGdgZOLE1H b1B7GhFYa3VzNz4x
	VxQvJS06IShFJWxb RRtFIFwcQE0KEzgg DwgYGjIhBgUCSW01
	KBpjK1gXGFsKM0I0 WQAA
X-Authentic-SMTP: 61633532353630.1039:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
	anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
	autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] Data structure for efficient proofs of
	non-inclusion
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: Wed, 14 Mar 2018 00:38:04 -0000


--17pEHd4RhPHOinZp
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Wed, Feb 14, 2018 at 09:09:18PM +0000, Daniel Robinson wrote:
> Hi Peter,
>=20
> Thanks for the mind-expanding presentation on client-side validation at
> Chaincode last week.
>=20

CCing bitcoin-dev because this is of general interest...

For background, Daniel is asking about my client-side verified single-use-s=
eals
via proof-of-publication model, previously published here=B9, which creates=
 an
anti-double-spend primitive via a proof-of-publication, and many
proofs-of-non-publication.

tl;dr: A seal is closed by publishing a valid signature for the seal to a
ledger. The first signature is the valid one, so if Alice want to convince =
Bob
you she closed a seal correctly (e.g. to pay Bob), she has to supply Bob wi=
th a
proof that the signature _was_ published - a proof-of-publication - as well=
 as
proof that prior to being published, no valid signature was previously
published - a proof-of-non-publication.

It's the proofs-of-non-publication that take up the most space.

> I'm trying to sketch out a system that would use some of those ideas, and
> am looking at what Merkle-tree-like structure for the "transaction root"
> would best allow efficient proofs of non-inclusion in a block. The simple=
st
> solution seems to just be a Merkle tree with the transactions sorted by
> public key, but it seems like having intermediate information about ranges
> higher up in the branches might help make non-inclusion proofs more
> compact. Other solutions I've seen like Patricia trees and sparse Merkle
> trees seem to be optimizing for easy recomputation on update, which doesn=
't
> seem to be necessary for at least this version of the idea.
>
> Are there any verifiable data structures you've found that improve on
> sorted Merkle trees with respect to proofs of non-inclusion?

So remember that the system I proposed=B9 used sorted merkle trees only wit=
hin a
block; for blocks themselves you mostly can't do any better than a linear l=
ist.
Though I think there may be some exceptions which deserves another email. :)

As you know, asymptotically merkle trees have excellent log2(n) proof size
growth. But as you correctly suggest, their high overhead in the small-n ca=
se
suggests that we can do better. In fact, Bram Cohen previously proposed=B2 =
a "TXO
Bitfield" for the somewhat similar use-case of committing to the spentness =
of
outputs efficiently.


# Naive Analysis

So suppose at an intermediate node you commit to a simple bitfield where ea=
ch
possible value under that node is represented by a single bit. Thus for m
values under that point in the tree, the marginal size of the non-inclusion
proof is m bits. By comparison a naive merkle tree built from a hash functi=
on
with k bits takes approximately k*log2(m) bits to prove non-inclusion. For =
an
rough, unsophisticated, analysis just solve:

    m =3D k * log2(m)

Apparently you can do this analytically, but as this analysis is only
approximate a much better idea is to just plot it on a graph: for k=3D256bi=
ts the
crossover point is roughly m=3D3000.


# Merkle Tree Structure

But what is the bitfield competing against exactly? Just saying "merkle tre=
e"
isn't very precise. Most designs along these lines use something like a
merkelized patricia tree, where each bit of the key is compared individually
and each node is a two-way (left vs right) branch. Better yet is the radix
tree, where each inner node that has only one child is merged with its pare=
nt.

Regardless, the logic of these kinds of trees can be thought of a recursive
query, where each type of node has a `get(key)` operation that returns eith=
er a
value or None.

So let's define a new type of inner node that commits to a
merkle-mountain-range (MMR) tip and a 2^j element bitfield. `get(key)` is t=
hen
this pseudo-rust:

    fn get(self, prefix) -> Option<Value> {
        let idx =3D Int::from(prefix[0 .. j]);
        if self.bitfield[idx] {
            let mmr_idx =3D node.bitfield[0 .. idx].count_ones() - 1;
            Some(node.mmr[mmr_idx].get(prefix)
        } else {
            None
        }
    }

The hard part with this is choosing when to use a bitfield-based inner node
instead of a standard one. Assuming keys are randomly distributed, it makes
sense to do so when the bitfield table is partially empty, but how empty? I=
t's
a trade-off between multiple parameters, including the size of
proofs-of-publication - although the latter may be OK to ignore as the numb=
er
of proof-of-non-publication needed should usually greatly outnumber
proofs-of-publication.

Question: is it OK for this choice to not be part of the deterministic
consensus? Is that even possible to enforce?


# Security

For a proof-of-publication to be secure, it must ensure that any attempt to
construct a false proof-of-non-publication will fail. In the pruning model,
that means that a proof-of-publication is simply the data necessary for the
proof-of-non-publication verifier to return false. Concretely:

    fn verify_pop(tree, key) -> bool {
        !verify_non_pop(tree, key)
    }

However note the subtle difference in trust model with respect to censorship
between the following two possible non-pop verifiers:

    fn verify_non_pop(tree, key) -> bool {
        !tree.exists(key)
    }

    fn verify_non_pop(tree, key) -> bool {
        match tree.get(key) {
            Some(value) =3D> !verify_signature(value),
            None =3D> true,
        }
    }


## False Positives

Note how if we use the second `verify_non_pop()` function shown above we can
also use probabilistic data structures such as bloom filters in place of a
bitfield. This works because a false-positive is acceptable, as it will sti=
ll
fail signature verification (or sooner if the key is committed in the leaf
node).

For example, it's plausible that a compressed bloom filter would be more sp=
ace
efficient than a bitfield, as the multiple hashing steps might use the bits=
 in
the filter more efficiently. Investigating this further would be a good
research topic.


# References

1) "[bitcoin-dev] Scalable Semi-Trustless Asset Transfer via Single-Use-Sea=
ls and Proof-of-Publication",
   Peter Todd, Dec 5th 2017, https://lists.linuxfoundation.org/pipermail/bi=
tcoin-dev/2017-December/015350.html

2) "[bitcoin-dev] The TXO bitfield",
   Bram Cohen, Mar 31st 2017, https://lists.linuxfoundation.org/pipermail/b=
itcoin-dev/2017-March/013928.html

3) "Bloom filters",
    Wikipedia, Jan 27th 2018, https://en.wikipedia.org/w/index.php?title=3D=
Bloom_filter&oldid=3D822632093

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

--17pEHd4RhPHOinZp
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

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

iQGSBAEBCAB8FiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAlqobt5eFIAAAAAAFQBA
YmxvY2toYXNoQGJpdGNvaW4ub3JnMDAwMDAwMDAwMDAwMDAwMDAwMzFmOTYxY2Ri
YjQ3MjliNjcxMGVmOTg5MWY4M2QxMDljODA0ODg5NTllMDFjYwAKCRAkgUA9pfCR
+wL2B/4svFyIc4JdPpLonz2KVwM+YM5MiWxnf7xQnaVE4QnN2eoShUQ2YWIdcqaf
NbIEgX+z5F5G8WYGZsymiaYqkSRHVDdg3FeXG/b/DKvdo4JcsvAWI7AegxRiPgUy
rxIDbWZ+pjcsvMwKBonXry7EknNSqRq5iP8lEoZE6K5jh85o5mDzM/fsIYznB8gp
hEkuQyuc4SfjDJpy4hNHGaJ6YkA901wBvMNLHm5wzCHJEAl23L2VSvi2nfpAUKcb
u7hGckNddVCyMIXBEWCC6UXusf6ttfMnj3onTRGC7cb0aMY2nRyVnTn1N+pdT8bg
6LO/zgroGxCMG9IRe2prQFeLxfQQ
=985T
-----END PGP SIGNATURE-----

--17pEHd4RhPHOinZp--