Pedersen Commitment in Zecrey

We have already led readers into the world of Cryptographic Commitment Schemes in the last article. The latest and most widely-accepted commitment scheme in the blockchain field is a concrete type named Pedersen Commitment, which has already been adopted in several privacy-preserving blockchain projects, such as Monero and Zcash [1]. As we explained before, a commitment scheme is a cryptographic primitive that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party can not change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation. Pedersen Commitment is a specific kind of commitment scheme, which was proposed by Torben Pryds Pedersen in the article “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing” in 1992 [2]. At present, Pedersen Commitment is mainly used with elliptic curve cryptography [3]. In this article, we will give a detailed description on what Pedersen commitment is and what it is used for.

The Pedersen commitment scheme is an unconditional hiding and computational binding commitment scheme based on the discrete logarithm problem. The setup of the scheme is the same as in the Schnorr signature [4] and the Digital Signature Algorithm (DSA) [5]. We assume the interacting parties are Victor and Peggy. Now we first explain the setup procedures of Pedersen Commitment scheme. Notice that Victor generates the keys because the commitment scheme is unconditional hiding and computational binding. First Victor (or a trusted third party) chooses two prime numbers p and q such that p mod q = 1 (by first choosing q and then computing p = i⋅q+1 for i≥2 until p is a prime number) and a generator g of order q from the group ℤp*. If a generator g has order q, it means that g generates a subgroup G of ℤp* with q elements. Victor can easily find g by computing g = g_1^{(p−1)/q} mod p, where g_1 is a generator of the group ℤp.

Victor then chooses a secret key a between 1 and q−1 and computes the public key pk = h where h = g^a mod p which he sends to Peggy. Before Peggy makes a commitment to the value x, she verifies the received public key and only if it is correctly generated, she continues. Peggy first chooses a random integer r between 1 and q−1 and then she uses the received public key pk to compute the commitment c = commit_pk(x,r) = g^x⋅h^r mod p which she sends to Victor.

At some point later, Peggy opens the commitment by sending the values x and the random integer r to Victor who first computes the commitment by c′ = commit_pk(x,r) = g^x⋅h^r mod p and then verifies that c = c′. Only if this is true, he knows that the received x is the same value that Peggy made a commitment to earlier on.

In the following we will argue about why the scheme is unconditional hiding and computational binding (actually is Pedersen’s commitment scheme perfectly hiding) [6]. Perfect hiding means that the commitment c = commit_pk(x,r) = g^x⋅h^r mod p reveals no information whatsoever about the value x. The commitment c is a random element in the group G: g is an element in G (remember that g generates G and therefore it also belongs to the group) and the group G is closed under multiplication, so g^{x+a⋅r} is an element in G (think of g^{x+ar} as g multiplied with itself for x+a⋅r times). Because we multiply with the random integer r in the exponent we have that the commitment c is a totally random element in G and therefore the scheme is perfectly hiding.

In addition, we know that the discrete logarithm problem is computationally hard in the used group G (because G is a subgroup of ℤp* of order q). Therefore, because Peggy only can change her commitment by solving the discrete logarithm problem, which is computationally hard, it’s also computationally hard for Peggy to change the committed value.

Next, we will give an example of how Peggy sends a commitment to Victor based on Pedersen Commitment. Victor chooses the two prime numbers p = 1447, and q = 241 and the generator g_1 = 1252 of the group ℤ_1447. He then computes the generator g = g_1^{(p−1)/q} mod p = 1252^{(1447−1)/241} mod 1447 = 123 of order q = 241. Next he chooses the secret key a = 161 and computes the public key h = g^a mod p = 123¹⁶¹ mod 1447 = 944 which he sends to Peggy.

Peggy then chooses the random value r = 5 and makes a commitment to x = 52 by computing c = g^x⋅h^r mod p = 123⁵²⋅944⁵ mod 1447 = 325, which she sends to Victor. When she wants to open the commitment again, she sends x = 52 and r = 5 to Victor. Victor then computes the commitment c′ = g^x⋅h^r mod p = 123⁵²⋅944⁵ mod 1447 = 325 and checks that c′ = 325 is equal to c = 325. If the equation holds, it denotes that Peggy did not change the value x after committing to it.

Pedersen Commitment scheme can be applied to solve some valuable but intractable issues encountered in real-life scenarios. For example, in terms of auditing, in order to prevent the disclosure of the auditee’s secrets, the data is usually encrypted and then handed over to the auditing party for verification, but it is also supposed to be ensured that the audited party didn’t falsify raw data, which calls for a data verification strategy. This situation can be resolved through Pedersen Commitment. Besides, Pedersen Commitment can be used to hide specific information like other commitment schemes, and if it is determined that each other’s information is correct, Pedersen Commitment can also omit the unblinding process of the traditional commitment scheme [7]. This feature makes it more suitable for cryptocurrency scenarios that require anonymous transactions than common approaches. By only publishing the commitments of the input and output of a transaction, the private information such as transaction amounts is kept secret from irrelavant users and thus the overall security and system trust is greatly enhanced.

Although Pedersen Commitment presents the above strengths, it can not be directly employed without any improvement. Commitments alone can not meet privacy requirements. Specifically, projects such as Monero, Zcash, Grin, and Beam have adopted Pedersen Commitment to some extent. However, these projects have been improved more or less based on the original Pedersen Commitment. For example, Grin and Beam use the Mimblewimble protocol integrate Cut-through and Coin-join technologies with Pedersen commitment respectively. Zcash also uses Pedersen Hash and a large number of ZK-SNARKs-related technologies except Pedersen Commitment.

Resources

Zecrey official website: Zecrey

Welcome to join our communities and follow us on twitter:

Medium：https://medium.com/@zecrey

Twitter: https://twitter.com/zecreyprotocol

Telegram: https://t.me/zecrey

Discord: https://discord.com/invite/U98ghQsJE5

References

[1] https://medium.com/coinmonks/zero-knowledge-proofs-um-what-a092f0ee9f28
[2] Pedersen T P. Non-interactive and information-theoretic secure verifiable secret sharing[C]//Annual international cryptology conference. Springer, Berlin, Heidelberg, 1991: 129–140.
[3] https://zhuanlan.zhihu.com/p/127992011
[4] Choi C J, Kim Z, Kim K. Schnorr signature scheme with restricted signing capability[C]//CSS2003. 2003: 385–390.
[5] Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm (ECDSA)[J]. International journal of information security, 2001, 1(1): 36–63.
[6] Koshiba T, Odaira T. Non-interactive statistically-hiding quantum bit commitment from any quantum one-way function[J]. arXiv preprint arXiv:1102.3441, 2011.
[7]Groth J. Homomorphic Trapdoor Commitments to Group Elements[J]. IACR Cryptol. ePrint Arch., 2009, 2009: 7.