[curves] Confidential Transactions and "Borromean" ring signatures-- ZK proof applications of ECC

[Gregory Maxwell]

A couple weeks ago I made available a short draft write-up describing
a simple generalization of the AOS ring signature, which allows it to
efficiently prove acceptance of an AND of ORs access policy, rather
than OR you get from a basic AOS signature:

https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_8c3f9e7.pdf

In the write-up Andrew Poelstra and I also describe an alternative
framework for thinking about Schnorr signatures (especially when
expressed as {e,s}) as an application of chameleon hashes. This
description is helpful for understanding this particular construction
but may also be useful for gaining other insights into other
protocols.

I used this primitive to construct a protocol which proves that a
blinded value (pedersen commitment) is within a specified range (my
upper bounds are only powers of 2 because thats all that I needed.),
through an approach isomorphic to the binary decomposition range
proofs of Bellare and Goldwasser. Due to the use of the generalized
AOS signature and a number of other optimizations my construction
requires 2.5 elements per bit proven, which is more efficient than
general scheme I could find in the literature using only ECDL+RO
assumptions, at least for the number sizes I care about.  My
implementation also has a number of other cute tricks, like allowing a
non-private base-10 exponent. It is also able to use 80% of the
proof's size to communicate a private message to a designated receiver
(for whom the committed value is not secret).

I created a very informal description pedersen commitments, binary
decomposition range proofs, and some information about how this scheme
is used to construct a cryptocurrency system where the amounts
transmitted are private:

https://people.xiph.org/~greg/confidential_values.txt

I apologize for the informality (and lack of citations) and
incompleteness, my primary intended audience is technical persons in
the cryptocurrency space whom have strong CS fundamentals but may not
know anything about zero-knowledge proof systems. I've received many
positive reports about it, so if any of you are only familiar with
ECDH and signatures and would like an intuitive and informal overview
of range proofs, I'd suggest it as well-- and comments and questions
are welcome!  I think an essential part of advancing the art and
science of cryptography is elevating people's working understanding: I
think systems which are pure black boxes to all but a few are unlikely
to ever become highly secure.


I plan on documenting the system more formally-- along with all
details like the use of base-4 encoding-- in the future, certainly
before putting it into any production use. (beyond time constraints
and the system not being final, I find that more formal descriptions
sometimes scare people off, so it's useful to have both).

There is an experimental implementation of both the ring-signature and
range-proof available at:

https://github.com/ElementsProject/secp256k1-zkp

This implementation is on top of an also-experimental EC library
libsecp256k1-- where I am also a contributor. As the name suggests, it
implements secp256k1-- the 256-bit prime order, prime field, SECG
specified curve designed to have an efficient endomophism, which is
used by Bitcoin. Libsecp256k1 implements many interesting
optimizations, including ones not implemented or described elsewhere
(e.g. techniques which allow completely inversion free signature
verification, or jacobian plus jacobian as fast as jacobian plus
affine, under certain conditions). Optimizations where we are aware of
heightened potential for patent complications are disabled by default.
Currently we view this implementation as a test bed for exploring the
limits of performance on top of this curve, as well as s test bed for
software quality and verification techniques for use in cryptographic
and consensus systems. There are other forks of this library that
implement things like batch verified Schnorr signatures, and such.

Finally,

The range-proof powered private value system is integrated into a
cryptocurrency test-bed called Elements Alpha (
https://blockstream.com/developers/  /
https://github.com/ElementsProject/elements ). Rather than being a
separate cryptocurrency the alpha network is a "pegged side-chain"
against Bitcoin testnet, which uses the mechanisms/protocols described
in the sidechains whitepaper ( https://blockstream.com/sidechains.pdf
) to allow users to transfer testnet bitcoins into alpha, trade them
around, and then transfer them back to Bitcoin testnet.  The
motivation of this approach is being able to experiment with new
constructions and techniques without rebooting the cryptocurrency
adoption network effect by creating a separate competing system. So
beyond all this being a fun cryptography novelty it can be used right
now (though currently only with testnet bitcoin. :) )


I hope some here find some of this of interest.