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

[Mike Hamburg]

Hi Gregory,

OK, so I think I might have an interesting variant on the Borromean 
paper, but only for the case where everyone is using the same group 
(Elliptic curve, or whatever).  Stop me if you've seen it.  I haven't 
read the commitments part yet, but it might come in handy.

Let M be a matrix of group elements.  You can multiply it by a vector of 
scalars, and get a vector of group elements.  Here's a ZKP of knowledge 
of an element of ker M, with nonzero first element. (You can prove 
knowledge of just any vector, but nonzero first element is fine here.)

Alice sends to Bob: Mr, for a random vector r.
Bob responds with a challenge c (= hash(M,Mr,message) in the sig case)
Alice responds with r', where Mr = Mr' and the first element of r' is c.

For the signature version, the signature is r'.  Mr = Mr' is the input 
to the hash (along with the message and pubkey), and the output is c 
which you check against the message.

This is honest verifier zero knowledge because you can just choose r' 
upfront, and the Fiat-Shamir trick clearly applies.  It's a 
generalization of Schnorr: in Schnorr, the matrix is (G,pubkey). For a 
ring signature, it's (G,pub1,pub2,...,pubN).  [[ Technically what this 
proves is knowledge of some linear combination of the secret keys, which 
might be a problem somehow, but I'm not sure how. ]]

You can also prove knowledge of at least k kernel vectors.  Here instead 
of matching the first element of r' against the challenge, you have to 
match the first k elements of r'.

You can also construct complex relations using monotone span programs.  
A monotone span program is a target t and vectors v_i (i = 1..n), in 
some vector space.  It is satisfied by a subset S of 1..n if t is in the 
span of {v_i | i in S}.

In this case, let M be the matrix [ Gt, Pub1 v1, Pub2 v2, ...] where 
Pub1 v1 denotes a column of group elements, which are the entries of v1 
times Pub1.  A vector [-1,w1,w2,...] is in the kernel of M if

t = (w1 sec1) v1 + (w2 sec2) v2 + ...

If you don't know, say, sec_i (or maybe some linear combination of it 
and the other secret keys) then you'll probably be forced to set w_i = 
0.  For the ones you do know, you can set w_i = s_i / sec_i, where t = 
sum s_i v_i is a solution to the span program.  So probably you can find 
an element of ker M iff you can solve the span program.

Span programs are fairly powerful.  For example, you can clearly get a 
k-of-n threshold system: just choose n general vectors in k-dimensional 
space (probably actually in some nice pattern for efficiency).  Any k of 
them span, and any k-1 do not.

Also, we ought to have something more powerful than span programs here, 
especially since we can get thresholds in a different way be showing 
multiple kernel vectors.

To think about tomorrow: how to go beyond span programs, and how to 
match the efficiency of the Borromean signature scheme, and how to apply 
to your proof system, and how to prove security.

Cheers,
-- Mike



On 06/17/2015 04:52 PM, Gregory Maxwell wrote:
> 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.
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves