Commit Twin

Create a zero-knowledge equality proof from two commitments.

This project demonstrates how to create a zero-knowledge proof that two commitments hide the same secret using elliptic curves.

This project has two implementations: golang and rust.

Primitives

The protocol uses any elliptic curve.

The curve parameters are denoted as

• : The security parameter in bits.
• : The field modulus
• : The subgroup order
• : A hash function which outputs bytes less than .
• : Points in the cyclic group of order
• : The base point in
• : A point in whose discrete log is not known or relative to
• : A point in whose discrete log is not known or relative to
• : The point at infinity

Scalars operate in and are denoted as lower case letters.

Points operating in are denoted as capital letters.

A common approach is to use SHA256 to hash to byte sequence then reduce modulo . However, this results in a biased result that isn't uniform. Instead more bytes should be generated then reduced modulo . The number of bytes is calculated with L = ceil((ceil(log2(p)) + k) / 8).

Consider this when choosing , from Appendix A "The problem of mapping arbitrary bit strings to elliptic curve points has been the subject of both practical and theoretical research. This section briefly describes the background and research results that underly the recommendations in this document. A naive but generally insecure method of mapping a string msg to a point on an elliptic curve having points is to first fix a point that generates the elliptic curve group, and a hash function Hp from bit strings to integers less than ; then compute , where the operator represents scalar multiplication. The reason this approach is insecure is that the resulting point has a known discrete log relationship to . Thus, except in cases where this method is specified by the protocol, it must not be used; doing so risks catastrophic security failures."

Also, , should not be generated by randomly choosing a scalar and computing . The best method to choose , is to pick a nothing up my sleeve value and compute the hash to curve of the bit string.

If using pairing friendly curves this same protocol can be used to compare commitments in and .

Setup

Alice secretly holds and randomly chooses in order to compute two commitments and .

Bob knows but doesn't know .

Protocol

• Bob sends nonce to Alice
• Alice picks random .
• She computes and .
• She computes
• She computes all in
• Alice sends to Bob.
• Bob computes
• Bob checks that

Note

The commitment doesn't have to use but could be another point like . The protocol will still work.

can also be a nothing up my sleeve value chosen by Alice as long as its not used more than once like a timestamp in milliseconds in which case Bob doesn't need to send it Alice. The security concern is that Alice should not be able to pick a value that allows her to cheat in the proof by biasing the result.

If Bob knows but not , then could also be part of the proof and sent.