Confidential Transaction Balance Verification by the Net Using Non-Interactive Zero-Knowledge Proofs

1Introduction

The global trends, current tendencies, and frontiers of blockchain technology have been reported in Boakye et al. (2022) where it is noted that blockchain technology research in finance has become dominated by studies on crowdfunding, entrepreneurial finance, bitcoin, entrepreneurship, fintech, and venture capital. Their overview covers 157 articles. However, the interaction between financial activity and the tax collection system is not sufficiently outlined in this and other studies.

This paper is a continuation of our previous research based on a tax declaration scheme using blockchain confidential transactions (Sakalauskas et al., 2023), based on the Unspent Transaction Output (UTxO) paradigm. This scheme includes the main blockchain actors: Senders, the Receiver, the Audit Authority (AA), and the Net, and provides confidentiality of transactions while at the same time ensuring their verifiability for the Net. Any sum Received by the Receiver is denoted by income i, and any sum spent by the Receiver is denoted by expense e. The honesty of a transaction is based on the balance between the total sums of income and expense, which we denote by In and Ex. This means that, to ensure the honesty of transaction, the balance equation In=Ex must hold. Privacy in a private blockchain must be achieved through the encryption of actual transaction values. But at the same time, all the Net must be able to verify the validity of the transaction balance equation, which is impossible for probabilistically encrypted data.

So far, ciphertext equivalency proofs have been broadly used in cloud computing.

Guomin et al. (2010) present a probabilistic public key encryption scheme based on a bilinear group where anyone can verify whether two ciphertexts are encryptions of the same message. The applications of this include searchable encryption and the partitioning of encrypted data. In their scheme, verifying the equivalency of ciphertexts requires bilinear map operations. Such operations require more computational power than exponential operations in ElGamal encryption. Their presented solution does not support encryptor authorization, which is an important part of our application.

The issue of searching among encrypted data is discussed in Canard et al. (2012) with an approach based on the ElGamal system, using bilinear maps. This approach extends public-key encryption by having the following functionality: given a plaintext, a ciphertext, and a public key, it is universally possible to check whether the ciphertext encrypts the plaintext under the key. This approach, like the previous one, lacks authorization. This capacity could be valuable when storing encrypted transaction balances, and utilizing the technique outlined in our paper, in the cloud.

In Hongbo et al. (2019), the problem of protecting data privacy using cloud storage is considered. The most effective solution is to encrypt data before uploading it to the cloud. The authors introduced a new notion of identity-based encryption with an equivalency test which supported flexible authorization using bilinear pairings. The experimental results presented by the authors show that their scheme is efficient and can satisfy various types of searches of encrypted data.

The problem of plaintext equality, which consists in determining whether ciphertexts hold the same value, is considered in Blazy et al. (2021). Their approach generates two ciphertexts using a probabilistic public-key encryption scheme by the same prover. For a proof of plaintext equality, the authors proposed sigma protocols that led to non-interactive zero-knowledge proofs.

In Zhao et al. (2022), a public key encryption scheme is proposed which supports authorized equality tests on ciphertexts in the dual server model. In this scheme, the primary server and secondary server must get authorization from users before performing a sequential equality test on ciphertexts. This scheme provides security against keyword guessing attacks and is a further improvement on the schemes proposed before.

In Dong et al. (2023), it is pointed out that existing encryption schemes can potentially suffer from information leakage when dealing with multiple ciphertexts due to the need for pairwise equality tests. In this paper, encryption is supported by a multi-ciphertext equality test with proxy-assisted authorization. The proposed scheme incorporates the functionality of the multi-ciphertext equality test into the encryption schemes outlined above. It allows a single equality test to be performed on multiple ciphertexts to determine whether the underlying plaintexts are equal.

In the reviewed papers, different techniques are considered, but the proposed solutions do not cover the problem we are examining in this paper. Ensuring privacy in the realization of transactions requires that the inputs and outputs of such transactions are encrypted with different public keys, and that these encryptions are performed by different actors. All Senders encrypt their transactions with the Receiver’s public key, and the Receiver declares her expenses to the AA by encrypting them with the AA’s public key. To validate the balance, additively-multiplicative homomorphic encryption must be integrated into the system. We are using the well-known probabilistic ElGamal encryption paradigm, transformed to become additively-homomorphic, using also an established technique. This issue has not been considered in our reviewed literature.

As outlined in the literature, the problem of deciding whether several ciphertexts are computed from the same plaintext is called the ciphertext equivalency problem. Thus, the integrity of the transaction can be verified by providing a ciphertext equivalency proof for the total In and Ex values, which are encrypted. In the case of an honest transaction, In=Ex, and the Receiver must prove that multiple ciphertexts of the (encrypted) total In and Ex values are the same. This eventuality is also not considered in the outlined literature, since it arises when encrypted In and Ex values are made by different actors and with different public keys.

In the reviewed techniques, no homomorphic property is required for balance verification, is realized. Such techniques can be used in a further step to store confidential data in the cloud. It is also known that encryption based on the bilinear pairing approach requires more computation power than the ElGamal encryption-based approach. Given the large number of transactions in the blockchain, optimizing the effectiveness of the ciphertext equivalency proof on the user side is desirable.

In this paper, we propose a more efficient method for the verification of balances by the Net in confidential transactions, compared to our previous publication (Sakalauskas et al., 2023). The background of our approach is the application of modified, probabilistic, additively-multiplicative homomorphic ElGamal encryption together with a modified Schnorr identification method (Freeman, 2011; Boneh and Shoup, 2023). The benefit of this approach is that the public parameters for both cryptographic methods are the same. The modification of ElGamal encryption involves transforming it into an additively-multiplicative homomorphic encryption, as proposed by Bunz et al. (2018).

The innovation in our realization is based on the integration of modified, probabilistic and additively-multiplicative homomorphic ElGamal encryption with our proposed construction of a modified Schnorr identification. This construction is extended to a non-interactive zero-knowledge proof (NIZKP) using a cryptographically secure h-function (Boneh and Shoup, 2023). By introducing an AA as a structural element in blockchain system based on UTxO, the verification of encrypted transaction data for the Net can be dealt with effectively.

This is achieved when the proposed NIZKP construction proves the equivalency of two ciphertexts encrypted with two different public keys. This equivalency shows that two ciphertexts correspond to encryption of the same plaintext, either In or Ex when In=Ex.

Efficiency is assured by using NIZKP, thereby reducing twofold the number of encryptions required for Senders and the number of decryptions realized by the Receiver, compared with our previous publication (Sakalauskas et al., 2023). This is achieved by omitting the encryption of random parameters sent by Senders to the Receiver and, hence, avoiding the decryption of these parameters for the Receiver. For example, if a transaction has M inputs, then the validity verification requires M encryptions and M decryptions, respectively. All encryption and decryption methods require at least two modular exponentiations. In this paper, we are using NIZKP which requires only four modular exponentiations instead of 2M encryptions/decryptions of random parameters.

The approach presented here is compatible with mobile e-wallets, and has the capacity to realize transactions offline. The realization of e-wallet transactions in the presence of observers is treated in Sakalauskas et al. (2017, 2018), and Muleravičius et al. (2019). In this case, a digital currency for money transfers can be installed in the customer’s e-wallet.

The main contributions of this paper are:

The innovation of our realization is based on the integration of probabilistic, additively-multiplicative homomorphic ElGamal encryption with our proposed modification of a Non-Interactive Zero-Knowledge Proof (NIZKP) based on Schnorr identification, and on the introduction of an AA as a structural element in a UTxO-based blockchain, thus facilitating a more effective verification of encrypted transaction data by the Net. This integration allows all users on the Net to check the balance equation for UTxO-based transactions from encrypted data.

In Section 2, an overall description of the proposed scheme is presented. In Section 3, an introduction to ElGamal encryption is given, and the construction of additively-multiplicative homomorphic encryption is presented. The construction of a confidential transaction is presented in Sections 4 and 5 using our proposed modification of Schnorr identification. In Section 6, security and efficiency analyses are provided. Section 7 gives conclusions, and at the end, a list of references is presented.

2Overall Description of the Transaction Scheme

To be self-contained, we present here some material from Sakalauskas et al. (2023). We consider multiple-input and multiple-output blockchain transactions based on the UTxO paradigm, which is the fundamental building block of cryptocurrency transactions in blockchain systems. Transactions based on a UTxO have certain inputs and outputs (Pinna et al., 2018).

Our scheme defines the following actors: the transaction creator, Alice; the Audit Authority (AA); and the network of users, denoted as the Net. The Net is divided into three parts: the Bobs, B₁, B₂, …, B_M transferring money to Alice and providing her with income; the Larries L₁, L₂, …, L_N receiving money from Alice and thus representing Alice’s expenses; and other Net nodes verifying the transaction’s validity, composing and validating blocks, etc.

The present solution is an integration of several approaches. It is known that the trustworthiness of transactions relies on the balance between income (inputs) and expenses (outputs). Bunz et al. (2018) present a method to assure the Net of the confidentiality and verifiability of transactions using a modification of ElGamal encryption (ElGamal, 1985). This technique transforms multiplicatively homomorphic ElGamal encryption into additively homomorphic encryption. We will use this technique to create confidential and verifiable transactions for the Net. According to the UTxO paradigm, a valid transaction requires that the sum of all inputs be equal to the sum of all outputs. Change leftover after expenses is sent to the transaction creator as one of the outputs.

For business processes, it is important to ensure the confidentiality of transaction amounts. Confidentiality means that transaction data must be encrypted using a secure probabilistic encryption method. The challenge here lies in ensuring the honesty of transactions with encrypted incomes and expenses. Even when these values are equal, their ciphertexts may differ due to probabilistic encryption. As a result, detecting balance violations becomes problematic. Let us consider a transaction, created by Alice, consisting of income and expenses. Let us assume that Alice received incomes i1, i2, …, iM from several Bobs B₁, B₂, …, and B_M, respectively. Then the total income is i=i1+i2+⋯+iM. Alice transfers part of her total income i to several Larries L₁, L₂, …, L_N by disbursing expenses e1,e2,…,eN, respectively. If the sum of expenses e′=e1+e2+⋯+eN is less than the total income, then she transfers the change value, which we denote by eN+1, to herself. If the transaction is honest, then the following balance equation must hold

In an open blockchain, i.e. in an open distributed ledger, all nodes in the Net can verify the balance of the transaction. If this balance holds good, the transaction is assumed valid. However, in private blockchain transactions, data should be confidential. In these cases, the Net cannot directly verify the validity of a transaction.

In this study, we will use the following notation for the private key PrK and public key PuK of two actors. For Alice: PrKA=x, PuKA=a and for the AA: PrKAA=z, PukAA=β.

We assume that the AA is a Trusted Third Party (TTP) for all the Net providing tax accountancy services. All actors must declare to the AA all actual transaction data by encrypting it with the AA’s PukAA=β to ensure the confidentiality of their business activity. In addition, in our example, it means that all Bobs must encrypt their expenses by Alice’s PuKA=a. Then only Alice can decrypt her received income and verify their correctness. When Alice is transferring her expenses to her Larries, and the leftover change to herself, she encrypts them with corresponding Larries’ public keys. We do not consider this stage in this paper.

We will deal with Alice’s encrypted income values im, m=1,2,…,M, encrypted by her PuKA=a and ciphertexts ca,im, respectively. All Alice’s expenses en, n=1,2,…,N are declared to the AA by encrypting them with PukAA=β represented by ciphertexts cβ,en, respectively.

3Additively-Multiplicative Homomorphic ElGamal Encryption

Our solution relies on probabilistic asymmetric ElGamal encryption by transforming it into additively-multiplicative homomorphic encryption (Bunz et al., 2018). To realize ElGamal encryption/decryption, public parameters must be shared on the Net. Probabilistic encryption is performed by the Sender using the Receiver’s public key and a randomly generated number, thus providing different ciphertexts even for the encryption of the same plaintext. The ciphertext is sent to the Receiver who can decrypt it using the same shared public parameters and his/her private key to obtain the corresponding plaintext. ElGamal encryption has so-called multiplicatively homomorphic properties: the encrypted product of plaintexts is equal to the product of corresponding ciphertexts.

Let Zp∗={1,2,3,…,p−1} be a multiplicative cyclic group of order p−1, where p is prime, and multiplication is performed mod p. Then let there be a cyclic subgroup Gq of order q where q is prime and any generator of this group we denote by g. Let Mes be a message to be encrypted and m – the image of a reversible 1-to-1 function, transforming Mes to m in Zp∗. We denote public parameters in ElGamal encryption by

The ElGamal encryption system uses the discrete exponential function (DEF) defined by the generator g in Gq and provides the following isomorphic mapping DEFg: Zq→Gq, where Zq={0,1,2,…,q−1} is a ring with addition, subtraction, and multiplication operations mod q. For any integer i∈ Zq:

Further, we omit the notation mod p, except in some special cases. A private-public key pair (PrK, PuK) is computed using public parameters PP in (2) and DEF. Encryption is performed using the Receiver’s PuK, and decryption, correspondingly, with the Receiver’s PrK. Let Alice’s private-public key pair be (PrKA=x, PuK=a) and the AA’s private-public key pair be (PrKAA=z, PuK=β). Key generation for both actors, Alice and the AA, is performed in the following way:

Let Alice be a Sender and encrypt transaction data d corresponding to a single income or expense with the AA’s PuKAA=β. Then ciphertext cβ=(εβ,δβ) is obtained by the following two steps:

We denote encryption and decryption functions by Enc( ) and Dec( ), respectively. Then, formally, encryption and decryption operations are expressed in the following way:

ElGamal encryption has the following multiplicative isomorphic property. Let d1,d2∈Zq. Then, for the encryption of two plaintexts d1 and d2, two random numbers k, l are generated, yielding two ciphertexts cβ,1 and cβ,2:

The encryption of a product d=d1·d2 with the random parameter j=k+l mod q yields a ciphertext cβ,12 , equal to the product of two ciphertexts cβ,1 and cβ,2 in Zp∗, i.e.

According to (10) and (11), this encryption is a multiplicative homomorphism of plaintexts. The value of the multiplied ciphertexts is equal to multiplied value of the underlying transactions.

To verify the validity of the transaction based on balance equation (1), we need to obtain the additively-multiplicative homomorphic encryption by transforming transaction data in the following way:

Then (10) can be rewritten in a form denoting the ciphertexts of encrypted transformed data in capital letters C

The last step allows us to verify transaction balance in (1) by verifying the multiplied encrypted income and expenses with different public keys and proving that these ciphertexts are equivalent using NIZKP.

To create Alice’s confidential and verifiable transaction, all her actual incomes i1,i2,…,iM must be transformed to the numbers I1,I2,…,IM using (12) and expenses e1,e2,…,eN+1, to the numbers E1,E2,…,EN+1, respectively.

The total transformed income is denoted by I, and the total transformed expenses, by E. Then, referencing homomorphic equation (14), we obtain

The balance equation (1) can then be rewritten as

4Creation of Confidential and Auditable Transactions

In the proposed solution, all the information about actual transaction data is available to Alice as a transaction creator and to the AA.

The Bobs in the transaction transfer their expenses as Alice’s income i1,i2,…,iM, and using (15) computed values I1,I2,…,IM. Then the Bobs encrypt them using Alice PuKA=a with the randomly generated numbers k1,k2,…,kM, thus obtaining ciphertexts Ca,I1,Ca,I2,…,Ca,IM, respectively. All Bobs send (Ca,I1,Ca,I2,…,Ca,IM) to Alice.

Alice, after receiving ciphertexts Ca,I1,Ca,I2,…,Ca,IM from the Bobs, decrypts them using her PrK=x and obtains numbers I1,I2,…,IM corresponding to the actual income values i1,i2,…,iM transformed according to (15).

Let us consider that according to the agreement between parties, values i1,i2,…,iM are bounded to 232−1. The computation of i1,i2,…,iM does not, therefore, require us to solve a general discrete logarithm problem in Zq, which is assumed unfeasible given security requirements. It is enough to perform a search in the set with 232−1 values. Moreover, Alice can reduce the search area with preliminary knowledge about the expected sums to be received. For example, let Alice know that the sums received from her Bobs do not exceed 10.000. Then the search area can be bound by 216 instead of 232−1.

According to (10), Alice multiplies all ciphertexts (Ca,I1,Ca,I2,…,Ca,IM), thus obtaining the ciphertext

After this step, Alice defines expenses e1,e2,…,eN+1 and transforms them to E1,E2,…,EN+1 by applying (15).

We do not consider Alice’s tax declaration to the AA and her encrypted transfer of expenses to her Larries, since these were presented in the previous paper (Sakalauskas et al., 2023).

Alice multiplies all expenses (E1,E2,…,EN+1) mod p, computing the value

Then the secret random integer l←randi(Zq) is generated by Alice and used for E value encryption using the AA’s PuK=β. Thus, the following ciphertext is obtained:

Alice must prove to the Net that ciphertexts Ca,I, and Cβ,E encrypt the same value I=E using NIZKP, thus proving that the transaction is valid and honest.

5A Zero-Knowledge Proof – ZKP

A ZKP is based on our proposed modifications of the classical Schnorr identification protocol realized in the form of NIZKP (Boneh and Shoup, 2023).

To be self-contained we present the classical ZKP. Recall that the public parameter is a pair, PP=(p,g). Let Alice be a Prover intending to prove to any Verifier (say, the Net) that she knows her private key PrKA=x by declaring her public key PuKA=a. Then PuKA=a is called a statement (St), and PrKA=x is a witness for a. An interactive ZKP consists of three steps:

The Verifier verifies the following identity of terms to be convinced that Alice knows her PrKA=x.

This technique is generalized to allow NIZKP to convince the Net that two different ciphertexts Ca,I in (18) and Cβ,E in (21) are obtained by encryption of the same plaintext with different public keys, namely PuKA=a and PuKAA=β. We assume that the verifier Net is a so-called honest verifier, and the proof represents the so-called Honest Verifier ZKP.

Referring to Boneh and Shoup (2023), interactive ZKP can be transformed to non-interactive by replacing the random value h generated by the Verifier with the h-value computed by the Prover using a cryptographically secure h-function. This is the basis of the NIZKP scheme.

However, the scheme presented above is insufficient to realize a proof of ciphertext equivalency. We propose the modification of the existing NIZKP to realize two ciphertext equivalency proofs, namely Ca,I in (18), (19), and Cβ,E in (20), (21). Recall that Ca,I is a ciphertext of plaintext I encryption with Alice’s PuK=a and Cβ,E is a ciphertext of plaintext E encryption with the AA’s PuK=β. The statement St of our proposed NIZKP consists of the following:

Notice that k is not known to Alice and is included in (δa,I). If the transaction is honest, then the transaction balance (1) is satisfied and I=E since. Then Eh·I−h=1 mod p, and putting it all together, we obtain:

This is the proof to the Net that the balance equation (1) is valid.

6Security Considerations

It is known that ElGamal encryption possesses semantic security and is secure against eavesdropping attacks. The modification of classical ElGamal encryption for the additively-multiplicative homomorphic encryption does not add or subtract security. It is furthermore proven that the classical Schnorr identification protocol is secure against eavesdropping attacks (Boneh and Shoup, 2023).

The present modification of the classical Schnorr identification scheme is based on two parallel proofs of knowledge, i.e. of PrKA=x in (4) and of a secret random parameter l in (21) used for probabilistic encryption. Therefore, these parallel proofs are also secure against eavesdropping attacks. The third proof is the combination of the two previous proofs proving the equivalency of two ciphertexts meaning that total transformed income I in (16) is encrypted by Alice’s public key a and the total transformed expense E in (16) is encrypted with the AA’s public key β, when, according to (17), I=E. This proof neither adds nor subtracts security. Therefore, the proposed scheme is also secure against eavesdropping attacks.

We refer to the following facts and the proof of statements presented below, as detailed in numerous publications (e.g. Boneh and Shoup, 2023), providing our security considerations.

The following known statements hold.

Now we can turn to the proof of security for a non-interactive zero-knowledge proof of ciphertext equivalency starting from the following clear lemma.

According to Lemma 1 and the Corollaries, the first two steps of the presented modification of NIZKP are based on two independent and parallel proofs of knowledge: one for PrKA=x in (4) and another for the secret random parameter l in (21) used for probabilistic encryption. These proofs use the classical Schnorr identification scheme. Therefore, these two parallel proofs are also secure against eavesdropping attacks.

The third proof is the combination of the two previous proofs, demonstrating the equivalence of two ciphertexts. Specifically, this means that the total transformed income I in (16) is encrypted with Alice’s public key a, and the total transformed expense E in (16) is encrypted with the AA’s public key β. According to (17), it means that I=E.

Let us consider the commitment t3 consisting of the two secret parameters u and v. According to Fact 1, all the elements of Gq, except 1, are generators. We can interpret the value δa,I as a the generator g1 and β−1 as the generator g2. Then (25) we can rewrite it in the following way:

The last equation indicates that t3 can be represented by generators g1 and g2 with two indices u and v, respectively. In other words, t3 has representation of generator-tuple of length 2, (2-tuples).

The security proof is based on the fact that the Honest Prover will always convince the Honest Verifier about the ciphertexts’ equivalency. It is called a completeness proof.

7Conclusions

A method for the confidential verification of transaction balances by the Net has been presented using the UTxO system, in a manner providing transparency and trustworthiness for blockchain transactions. The honesty of transactions can be verified by anyone on the Net without any knowledge about their actual values.

The proposed scheme provides a proof to the Net that encrypted transaction data satisfies the balance equation (1) without revealing any information about the actual transaction data. It is guaranteed by the semantic security of ElGamal encryption and, in this paper, by a proposed a non-interactive zero-knowledge proof (NIZKP) based on Schnorr identification. Proof of security against eavesdropping attacks for the proposed NIZKP is presented. In the literature, this problem is generally known as a ciphertext equivalency proof.

The novelty of this proposed solution lies in the integration of additively-multiplicative homomorphic ElGamal encryption with our constructed NIZKP and its application to blockchain technology based on a UTxO system. The difference from other known approaches is that our NIZKP is constructed for different actors making independent encryptions with two different public keys.

The security of the proposed NIZKP against an eavesdropping adversary is proved.

The proposed scheme uses NIZKP, which reduces the number of encryptions and the number of decryptions by a factor of two for income, as compared with the previous authors’ results.

We intend future research to focus on implementing a sigma identification protocol for the ciphertext equivalency proof that is secure against active adversary attacks. The other possible direction for the presented methodology is to create new NIZKP schemes based on the potential of the matrix power function to provide security against quantum cryptanalysis attacks. This could involve some contribution to the task of integrating post-quantum cryptography with blockchain technologies.