Date: Tue, 16 Mar 2021 15:15:21 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Andrea <baro77@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <YFDLiR/w1IYiTURU@camus>
References: <202103152148.15477.luke@dashjr.org> <YE/p0u3gp4UYNS7R@camus>
 <3d6d308f-3d9f-588a-5b8f-3ab14560974c@gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
 protocol="application/pgp-signature"; boundary="7leejtRQM5NgM6WJ"
Content-Disposition: inline
In-Reply-To: <3d6d308f-3d9f-588a-5b8f-3ab14560974c@gmail.com>
Subject: Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum
 protections)
Precedence: list


--7leejtRQM5NgM6WJ
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, Mar 16, 2021 at 03:10:21PM +0100, Andrea via bitcoin-dev wrote:
>=20
> Hi! Sorry for the OT, could you provide some references to ring signatures
> over/for/via taproot (I mean the schema or something like that)? And what=
 is
> "Provisions" (the capital letter makes me think it's a product/technology=
)?
> I'm a rookie following this mailing since just a few months...
>

Thanks for posting such a positive message in an otherwise tense thread :)

Provisions is a scheme for providing proof of ownership of funds, developed
by Dagher et al in 2015 at https://eprint.iacr.org/2015/1008 . The way it
works is to collect all of the Bitcoin outputs which have exposed/known
public keys then associate to these keys a Pedersen commitment which commits
to the outputs' amounts in a homomorphic way.

Homomorphic means that even though the commitments hide what the original
amounts are, anyone can add them together (in some sense) to get a new
commitment to the sum of the original amounts.

So Provisions is essentially a zero-knowledge proof of the following statem=
ent

    1. I have a commitment to >100BTC (or whatever)...
    2. ...which is a sum of commitments of actual UTXO values...
    3. ...where these UTXOs come from the set of known-public-key UTXOs...
    4. ...and I am able to sign with the public keys associated to them.

which proves ownership of some amount of BTC, without revealing which speci=
fic
UTXOs were involved. This zero-knowledge proof can be done fairly efficient=
ly
by exploiting the structure of EC public keys and Pedersen commitments.


Unfortunately, most unspent Bitcoin outputs do not have known public keys,
which means that you can only do a Provisions proof using a small anonymity
set. However, all Taproot outputs, by virtue of having exposed public keys
(which is the point under contention in this thread), will be in the set of
exposed-public-key UTXOs, allowing people to do Provisions proofs where
their anonymity set consists of a large proportion of active coins.


BTW, even without Provisions, there are some similar and simpler things you
can do with Taproot keys along these lines. See for example
https://twitter.com/n1ckler/status/1334240709814136833


--=20
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


--7leejtRQM5NgM6WJ
Content-Type: application/pgp-signature; name="signature.asc"

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

iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmBQy4cACgkQxYjWPOQb
l8FRIgf+JVhhy/Xc8jhX9zPvOSv4WinJEDT6JfJ4doQnzUm6lQP0KfDDtB4mLAOc
viPNAslSrvT9vVtgt/ha3vkLHmhwDx25bbpaYOWO3IVx+X7K2NRXSz6w9JDQ6G1l
gWbBXG2fffRunvxd3G9XvrTBNCYsi5cS1FDjYhVz43U8DhEaOuHXp1ENeAfDEL5B
+tui7ss8uvclnTi5oak6zGiZkKOAO/2VXdcL4UD+IVLOoSxQHwHmuQYi70I+CH1A
hiNUejJetM8S0KZv9TDVg2KPpXK3QXKFATB9bfQWZuARxfEtAtHMC55O/R5DmPyZ
T79IFzawAcnSQlE1+NDvRGXvLvSELQ==
=HA/w
-----END PGP SIGNATURE-----

--7leejtRQM5NgM6WJ--