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.
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 \cdot P)
, 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 
.
Alice secretly holds 
and randomly chooses 
in order to compute two commitments 
and 
.
Bob knows 
but doesn't know 
.
- 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
)
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.