Explored: Zero-Knowledge Proofs, Part II

A series of in-depth articles overviewing the technologies utilized by the Dusk Network protocol.

We’re back after a short break! The second part of our inaugural topic of the series will encompass the fundamentals of commitment schemes and sigma protocols followed by a dive into the elliptic curve pairings and zero-knowledge arguments of knowledge (i.e. zk-SNARKs) in Part III before discussing the inner product proofs and Bulletproofs in the finale (Part IV) of the first iteration of the aforementioned series.

A pseudo-code outline of an imaginary zero-knowledge proof scheme.

Short Recap

Part I got the reader acquainted with the general idea behind zero-knowledge proofs and the requirements for a secure zero-knowledge proof scheme. The reader has also been introduced to Turing machines and the role of computational complexity theory in proof constructions. Lastly, Part I has glanced over the elliptic curve theory (a more thorough examination of elliptic curves will be offered in “Explored: Elliptic Curves” iteration of the series).

Commitment Schemes

A simple commitment scheme

Commitment schemes are cryptographic primitives allowing a user to commit to a value while obfuscating the value.

Commitment schemes have to satisfy the following two criteria:
1. Be hiding and
2. Be computationally binding

The hiding criterium is satisfied when a commitment does not reveal the value the user has committed to and the binding criterium is satisfied when the user is only able to probabilistically reveal the real value corresponding to the commitment at a later phase.

A commitment scheme requires the use of one-way functions (functions that are easy to compute, but nearly impossible to find the reverse) which would suggest that using hash functions should do the trick. While hashing the value satisfies the binding property, it does not satisfy the blinding property, as it would be relatively easy to brute-force the original value. A solution would be to append a random number (otherwise known as a blinder) to the value before hashing the resulting blinded value.

A homomorphic commitment scheme

Unfortunately, our simple commitment scheme design lacks an important feature required for the zero-knowledge proofs to work — homomorphism. Homomorphic encryption enables us to perform operations on the encrypted values which result in outcomes indistinguishable from the outcomes of operations performed on the decrypted values. Specifically, we are interested in additive homomorphism, which allows us to perform addition on the encrypted values.

Pedersen Commitment Scheme

Pedersen Commitment scheme

Pedersen commitment scheme satisfies both of the criteria highlighted in the previous section as well as being additively homomorphic. The scheme works by multiplying the value and the blinder by two elliptic curve points - G and H, where G is a publically pre-agreed point on an elliptic curve, known as a generator and H is a point derived from a G. H is a NUMS (nothing up my sleeve) point, implying that the relationship between G and H is unknown. The usual approach is to hash the encoded point G before converting the scalar obtained from the hash function into a point on a curve.

Addition of two Pedersen Commitments

Vector Pedersen Commitment Scheme

Vector Pedersen Commitment scheme

Vector Pedersen Commitment scheme is an extension of the scheme outlined in the previous section. The difference is in the fact that the latter scheme commits to a vector instead of a scalar.

A vector

The elliptic curve points for each value in a vector are generated with the process described in a previous section.

Dusk Network utilizes Pedersen Commitment scheme to obfuscate the values being transferred and Vector Pedersen Commitment scheme as a building block for Bulletproofs.

Sigma Protocol

Sigma protocol

A sigma protocol is an interactive proof scheme with a three-stage communication process between the Prover (P) and the Verifier (V). After making the commitments to the values public, the Prover issues a commitment to a random value (C_0) to the Verifier, who in turn returns a challenge value e to the Prover. The Prover computes the proof in form of vector z and scalar s and makes both public. The Verifier is now able to verify the original commitments against the commitment to the random value, the challenge value and the proof without the values behind the original commitments being leaked.

The proof values

The sigma protocol gets the name from the similarity between the Greek letter Sigma and the communication pattern between the Prover and the Verifier.

The protocol can be converted into a non-interactive scheme via Fiat-Shamir heuristic, which will be outlined in Part III.

How to learn more about Dusk Network

Dusk’s technology disintermediates regulated (financial) markets. Our infrastructure tackles the challenge at the deepest layer. With Dusk you are in charge of your securities from start to finish. You can issue, register, and trade digital securities while complying with all regulatory requirements.

Please consider joining us at the following media:

Website: https://www.dusk.network
FAQ: https://www.dusk.network/faq
Telegram: https://t.me/dusknetwork
Twitter: https://twitter.com/duskfoundation