15 juni 2021

The increased adoption of financial blockchains has fueled a lot of cryptography research in recent years. One area of high interest is transaction confidentiality which requires hiding investors’ account balances and transaction amounts, while enforcing compliance rules and performing validity checks on all activities.

This blog post will look at the Zether [2] protocol, which uses ElGamal public key encryption to hide transaction amounts and utilizes zero-knowledge proofs to demonstrates the validity of a transaction to stakeholders, namely network validators, investors, and auditors.

At a high level, with this formulation, Alice (sender) transfers x assets to Bob (receiver), by encrypting x with her own and Bob’s public keys, and including Ciphertext_Alice(x) and Ciphertext_Bob(x) in the transaction. She then, without revealing x, cryptographically proves that Ciphertext_Alice(x) encrypts a value less than or equal to her account balance. She also proves that Ciphertext_Alice(x) and Ciphertext_Bob(x) encrypt the same value. When the network validators receive the transaction, they verify the zero-knowledge proofs, and if successful, subtract Ciphertext_Alice(x) from Alice’s balance and add Ciphertext_Bob(x) to Bob’s balance.

Cryptographic Building Blocks

Let’s take a look at the cryptographic components before we discuss the implementation details. We first explain Pedersen Commitment and its role in ElGamal encryption. We then briefly examine relevant zero-knowledge proofs.

Pedersen Commitment

In cryptographic protocols there is often a need for a party to prove the knowledge of a privately chosen value, without initially revealing it or being able to change it at a later stage. More specifically, commitment schemes must hide the value, and bind to it such that the committer cannot change the value without changing the commitment.

Let mathbb{G} be a cyclic group of prime order p ( $mathbb{Z}_p$ ), for which the decisional Diffie-Hellman (DDH) assumption holds, and let g and h be generators of group . The DDH assumption states that for $a, b, c in mathbb{Z}_p$ , the tuple (g, g^a, g^b, g^a.b) is indistinguishable from (g, g^a, g^b, g^c), given that the discrete logarithm is a hard problem.

To commit to the value v in $mathbb{Z}_p$ , the committer uniformly samples a random number, r in $mathbb{Z}_p$ , and publishes commitment(v, r) = g^vh^r. This commitment is binding under the DDH assumption since the probability that the committer can compute a (v’, r’) != (v, r) such that commitment(v, r) = commitment(v’, r’) is low. It is also hiding meaning that it is computationally infeasible to calculate v from the commitment, since (with equal probability) it could be any member of $mathbb{Z}_p$ .

A key property of this definition is that multiplying commitments to 2 values, (v₁, r₁) and (v₂, r₂), results in a commitment to the sum of those values.

$commitment(v_1, r_1) circ commitment(v_2, r_2) = g^{v_1} h^{r_1} g^{v_2} h^{r_2} = g^{v_1 + v_2} h^{r_1 + r_2} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~= commitment(v_1 + v_2, r_1 + r_2)$

This property is referred to as additive homomorphism. It means that without knowledge of the 2 values, (v₁, r₁) and (v₂, r₂), one can multiply their corresponding commitments to calculate a commitment to their sum, (v₁+v₂, r₁+r₂).

ElGamal Encryption with Message in the Exponent

Considering the same group mathbb{G} , we can define the ElGamal encryption scheme as follows:

Key Generation: A secret key (x) is randomly sampled from $mathbb{Z}_p$ , and the public key (y) is derived as:

y = g^x

Encryption: Knowing the public key (y), anyone can randomly choose a blinding factor (r) and encrypt the value b for the secret key owner:

Ciphertext = (X, Y) = (y^r, h^b g^r)

Decryption: Knowing the secret key, first h^b can be recovered as:

$X/Y^{x^{-1}} = h^b g^r / (y^r)^{x^{-1}} = h^b$

Since discrete logarithm is assumed to be hard on a classical computer, there is no solution to calculate b from h^b efficiently. Therefore, b is computed by brute-forcing every possible value in h^value to find the one that matches with h^b. This variation of ElGamal encryption scheme is sometimes referred to as the twisted ElGamal encryption [1] or message in the exponent ElGamal encryption.

If you look closely at the second term of the ciphertext (Y), it is a Pedersen commitment to the plaintext and the blinding factor:

Ciphertext = (X, Y) = (y^r, commitment(b, r))

As a result one can show that ElGamal encryption is additively homomorphic, meaning that if Ciphertext₁ encrypts b₁and Ciphertext₂ encrypts b₂, to the public key y, Ciphertext_1 circ Ciphertext_2 encrypts b₁ + b₂.

Homomorphic encryption has been used to preserve users’ privacy in many applications. Besides its’ use in confidential financial blockchains, it has also been used in collecting medical data to encrypt patients’ biometrics and hide their identity, while keeping the dataset searchable [11].

Another advantage of this property of the ElGamal ciphertexts is that we now can leverage the zero-knowledge proofs that are developed for Pedersen commitments to prove properties of the encrypted value.

Zero-Knowledge Proofs

In cryptographic applications there is often a need to prove knowledge of a secret, or some property about it, to a verifier without leaking any additional information. This method is called a zero-knowledge proof. It must be complete, sound, and reveal no information (zero knowledge) about the secret, meaning that an honest verifier will be convinced that the prover has the knowledge of the secret (completeness), and a dishonest prover cannot mislead an honest verifier to believe, with non-negligible probability, that they know the secret (soundness).

Let’s first look at a class of zero-knowledge proofs called Sigma (Sigma) protocols [6], which consist of 3 rounds of interactions between the prover and the verifier: 1. commitment phase, 2. challenge phase, and 3. response phase. These proofs can be used to show the knowledge of a discrete logarithm, e.g. plaintext for a twisted ElGamal ciphertext.

For example, the following Sigma protocol proves that 2 ciphertexts encrypt the same value to 2 different public keys. This is useful in the context of transaction confidentiality as described in the introduction, where the transaction creator must prove that the number of withdrawn assets (v) from the sender’s account, with public key y₁, is equal to the deposited assets into receiver’s account, with public key y₂. So it essentially proves that Ciphertext₁ = (X₁, Y) = (y₁^r, h^vg^r) encrypts the same value as Ciphertext₂ = (X₂, Y) = (y₂^r, h^vg^r):

Prover randomly selects a and b in $mathbb{Z}_p$ , computes A₁ = y₁^a, A₂ = y₂^a, and B = h^bg^a, and sends them to Verifier.
Verifier randomly chooses a challenge, c in $mathbb{Z}_p$ and sends it to Prover.
Prover computes z₁ = a + c.r and z₂ = b + c.v and sends them to Verifier.
Verifier accepts the proof if and only if: y₁^z₁ == A₁ X₁^c, y₂^z₁ == A₂ X₂^c, g^z₁ h^z₂ = B Y^c.

For similar zero-knowledge proofs, regarding ElGamal ciphertexts, see reference [1].

Another class of useful proofs are Bulletproofs [3] which are non-interactive and are used to prove a ciphertext has a specific form, without requiring a trusted setup like zk-SNARKs do (references [7] and [10] give nice overviews of the trusted setup for zk-SNARKs). Bulletproofs’ range proof can be used to show that an ElGamal ciphertext encrypts a value that is within the range of positive numbers. We can utilize it to prove that the sender’s remaining balance is non-negative, and therefore they are not double spending. Although the initial proposal was not as efficient as zk-SNARKs, recently researchers have found ways to aggregate proofs in a transaction to make them smaller and the verification faster. Focusing on performance is key for adoption of zero-knowledge proofs in blockchain applications, as they need to process thousands of transactions per second in order to handle the traffic in real world financial applications. A popular implementation of Bulletproofs over Ristretto and curve-25519 is open-sourced by the Dalek project [4].

Implementation Considerations for Blockchain Applications

This approach to transaction confidentiality is at the core of a few blockchain protocols such as Zether [2], MERCAT [1], and PGC [5]. Its main advantage over zk-SNARKs [7] is that it does not require an initial setup phase to generate a master key [9]. It also has small ciphertexts and proof sizes. Proof validation is fast and researchers are actively looking into ways to aggregate Bulletproofs, so even faster batch verification might be possible. However, there are some challenges in using Zether in real-world applications. The following is a non-exhaustive list of important aspects that should be considered.

Privacy vs Confidentiality While hiding the transaction amount is one step towards offering privacy, the account-based model makes it easy to track investors’ accounts and learn about their actions. Zether proposes the use of one-out-of-many proofs to hide participants’ identities, yet leaves it as future work (see Appendix D in [2]). The Quorum blockchain project has used many-out-of-many proofs in addition to Zether to create Anonymous Zether [8]. Another caveat is that if at any point a confidential asset is exchanged with a non-confidential asset, the settlement will leak the confidential asset’s amount.
Front Running Problem Range proofs prove that the encrypted remaining balance of the sender is positive, which makes it dependent on the state of the account. As a result any change to the sender’s balance before the proof is verified will invalidate the proof. Thus, an account cannot participate in parallel settlements. Any solution will require locking the participating accounts until each transaction is settled, and ordering and processing them sequentially. This complicates real-world implementations.
Side-Channel Attacks ElGamal decryption with Message in the Exponent, as described above, requires brute-forcing all possible amounts to find the plaintext. This can be very slow and if not implemented carefully opens the application to side-channel attacks. Since decryption is only performed by the secret key owners, and not the network validators, this issue is not as critical to the blockchain’s performance. Nevertheless, it cannot be ignored for lightweight clients.
Forward Secrecy In financial systems, there is often a need to have support for offline transaction auditors that could peek at any given transaction out of band and verify it. One solution is to encrypt the transaction amounts with auditors’ ElGamal public keys, similar to how PGP distributes session keys among participants. But if any of the auditors are compromised, the attacker can decrypt all the transaction amounts that the auditor was auditing. Besides, since auditors are usually auditing a huge number of transactions, ElGamal decryption performance can become a bottleneck.
Integrated Signing and Encryption Since Schnorr signature and ElGamal encryption have the same key pair format, presumably a single key pair could be shared between the two schemes to facilitate key management on constrained wallets. However, if the signing key needs to be revoked or rotated, all the encrypted assets of an account need to be transferred to a new account. This is another trade-off that needs to be considered.

Conclusion

In this blog post we explored the possibility of utilizing ElGamal encryption and Zero-Knowledge proofs for transaction confidentiality. While homomorphic additivity properties of the ElGamal encryption make it possible for the network validators to maintain account states, it has some pitfalls that must be carefully considered in practice.