# Privacy-Oriented Transaction for Public Blockchain via Secret Sharing

Authors: Bo Mi; Bingqing Wu; Darong Huang; Yang Liu; Lu Chen; Shaohua Wan
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Immutability and traceability are the main reasons for the popularity of blockchain. Nevertheless, its transparency also makes the transactions visible to all participants, which seriously violates the privacy of some dealers. In order to transfer accounts over blockchain, all verifiers should be empowered with the ability to confirm the transactions, leading to the conflict between extensive consensus and individual privacy. Orienting to privacy issues of UTXO (Unspent Transaction Output), this paper exploited the unconditional security of Shamir’s secret sharing to construct a logic-physical map for public chain, which enabled noninteractive transaction verification without privacy infringement. A comprehensive analysis indicated that the proposed scheme is secure under UC (Universal Composability) framework with practical computation and communication overheads.


---

## Body

## 1. Introduction

As the most popular distributed platform, blockchain is provided with the merits of traceability and immutability, attracting more and more users to adopt it for accounting and trading [1–3]. However, the transparency of blockchain makes records visible to all participants, even for those in consortium and private blockchain, which brings about severe threats to sensitive information such as business secrets or personal privacy. Nevertheless, the property of openness is inevitable for blockchain due to tampering-resistant and verification purposes. Therefore, the conflict between the availability and confidentiality of blockchain has become a significant obstacle to its extensive application.The first showcase of privacy infringement for blockchain was presented in literature [4], taking Bitcoin as an illustrative example. It is pointed out that, due to the open nature of blockchain, attackers can statically analyse the distributed database and actively monitor the network flow, thus revealing the trading graph or transaction pattern of the Bitcoin system. Thereafter, Bitcoin is no longer anonymous as the inventor claims, not mentioning the confidentiality of ledgers. Accordingly, literature [4] also suggested two rudimentary tools that can be used to preserve the privacy of blockchain, namely, NIZK (Noninteractive Zero-Knowledge Proof) and HE (Homomorphic Encryption). Zero-Knowledge Proof allows the prover to convince the verifier that a certain assertion is correct without providing any useful information. Noninteractive Zero-Knowledge Proof does not require an interactive process and only needs to provide proof to the verifier to prove that he is correct, avoiding the possibility of collusion, but additional machines and procedures may be required to determine the order of experiments. In the blockchain, addresses are used to represent the parties to a transaction, thereby achieving anonymity. However, although the information on the chain is anonymous, the information in the real world is bound by the information on the chain. For example, many transactions are bound with the address on the chain and the bank account in the real world, which makes it convenient to trace the transaction parties in the real world and weakens anonymity. Homomorphic Encryption allows ciphertext to be processed directly, and the result is still ciphertext. That is, direct processing of ciphertext is the same as processing and then encrypting the plaintext. Noninteractive Zero-Knowledge Proofs and Homomorphic Encryption can ensure a valid transaction while hiding other details such as sender, receiver, and transaction amount. However, while NIZK eliminates the need for multiple interactions, its biggest disadvantage is that the generation of proof is very slow. Zcash [5], for example, takes 30 seconds, while the popular Filecoin [6] takes an hour. Similarly, for homomorphic computation, its computational efficiency is also a factor that seriously restricts the block generation speed. By introducing extra security mechanisms into the blockchain, the overall impact of privacy threats can be further reduced with remarkable efficiency and reliability improvements. Since Critical Energy Infrastructure (CEI) systems are vulnerable to cyberattack and data privacy leakage when deep learning training, Lu [7] designed the fairness-aware and time-sensitive task allocation mechanisms in asynchronous federated learning for CEI.The most intuitive way to preserve privacy is to upload encrypted information to the blockchain that no node can decrypt except the one who holds the secret key. However, this solution contradicts the basic principle of blockchain to some extent since it is a distributed database whose blocks must be commonly approved and maintained. Therefore, an open problem in such a research direction is how to make ciphertexts verifiable and computable, especially when they are encrypted by distinct keys. A promising way to conceal sensitive data in blockchain draws support from Attribute-Based Encryption. Since the keys are not directly related to each user but only their attributes, the participants provided with similar properties can hierarchically form a group. That is to say, they can share and process their collective data together, while any specific identity is concealed. Howbeit, considering that once a group member is corrupted, all of his keys would be exposed to the attacker. That is to say, such a solution is not fair enough, even if just a passive attack occurs.Considering that blockchain is essentially a distributed data structure, many scholars have studied the privacy issues in distributed systems [8–11]. Wu et al. [12] propose an efficient identity-based equal test encryption scheme with bilinear pairings to solve the problem of efficiently searching encrypted data outsourced to the cloud. For distributed secure computing, they also propose an efficient and secure searchable encryption protocol using trap door substitution functions that can be deployed over the cloud-based Internet of Things [13]. Due to the decentralized nature of blockchain, some researchers attempt to draw support from secret sharing (SS) for privacy-preserving. Zyskind and Nathan [14] implement a protocol that transforms the blockchain into an automatic access control manager that does not require third-party trust. In [15], it says the best way to protect private data is never to let the service see the raw data but to allow it to run calculations directly on the network and get the final result. If we split the data into shares rather than encryption, we can securely evaluate any function using secure multiparty computation. Raman and Varshney [16]combine distributed storage, private key encryption, and Shamir’s secret sharing scheme to distribute transaction data to ensure data integrity. In this scheme, hash and Merkle root are divided into secret shares, and each node only holds the corresponding share, which means each node only holds a part of the chain but can recover the whole chain, thus reducing the storage cost. Bartolucci et al. [17] construct a secret shared voting protocol based on blockchain; they use Shamir’s secret sharing for on-chain vote submission and winning candidate determination. The dealer divides the private keys of the two candidates into secret shares and distributes them. Only when a sufficient number of shares were collected could the private keys of the two candidates be recovered and the winner of the voting be determined at the same time. And the protocol is combined with a shuffling technique to delink voters from their submissions. Such innovation is inspired by the fact that sensitive information can be separately allocated to distinct participants in the blockchain. Thus, it cannot be revealed or processed unless multiparties collaborate. Since the basic principle of secret sharing is similar to the consensus protocol in distributed systems, it is more natural and feasible to be combined with blockchain. Following this research direction, Zheng et al. [18] proposed a credible data sharing scheme, which takes advantage of the consistency and availability of blockchain to prevent shared data from tampering or modification. It exploits the Paillier cipher system to achieve the confidentiality of shared data. Specifically, this scheme stores encrypted data in blockchain and divides secret keys as distributed shares for security purposes. However, it requires a trusted third party to distribute the secret keys, which is an inevitable bottleneck with respect to both efficiency and security. Moreover, due to the limitations of the Paillier algorithm, it only realizes the operation of homomorphic addition rather than multiplication and Boolean calculations. To eliminate the necessity of a key server, Kim et al. [19] assembled Shamir’s secret sharing scheme, private key encryption, and information diffusion algorithm to construct a distributed secret sharing blockchain. By secretly sharing private keys and hash values on diverse nodes, the purpose of cooperative decryption is achieved. Nevertheless, how to directly calculate between encrypted data remain unaddressed, which severely hinders the practicality of their scheme. Similarly, Fukumitsu et al. [20] presented a secure online storage system that divides user data into parts and distributes them over a P2P network through anonymous communication. Though achieved better performance, the data stored in the blockchain are fragments containing more or less semantic information of their primitives. Moreover, this scheme is still incapable of processing the encrypted data, which introduces more challenges to authentication, consensus, and operation of blockchain.To not only narrow the gap between security and maneuverability but also fit the distributed structure of blockchain, a practical privacy-preserving scheme will be presented in this paper. We exploit Shamir’s secret sharing (SSS) to retain sensitive data on a logic blockchain which is physically composed of multiple share-piece chains. That is to say, the data are stored in the form of secret shares to ensure their confidentiality. Thanks to the Q2 structure of Shamir’s secret sharing, the secret cannot be recovered unless at leastt pieces of shares are collected, where t stands for a predefined threshold. To make sure that the shares can be efficiently processed, we also presented a noninteractive homomorphic multiplication method followed by nonlinear operations such as logic calculation and comparison. Thereafter, transactions can be carried out without exposing any sensitive information within in chain. In this way, blockchain will not just be simple cloud storage but a secure platform with homomorphic function.Briefly, the contributions of this paper are as the following:(1)
We proposed a homomorphic multiplication method based on Shamir’s secret sharing, which eliminated the bottleneck of interactions among participants. Based on it, the concealed data can be processed in terms of nonlinear functions without communication delay.(2)
Combining SSS with the raft algorithm, a secure data computation model is presented, which not only ensures the confidentiality of data on blockchain but also guarantees that the computational result is recoverable when necessary. It means that the basic functions of blockchain can be normally and securely executed, including consensus, audit, and transaction.(3)
By actualizing basic operations such as unbounded fan-in addition and numerical comparison, a complete framework for secure UTXO (Unspent Transaction Outputs) is presented as an instance of our SSS-based blockchain scheme. Within such a framework, the mechanism of UTXO can be accurately and efficiently realized without infringement. We can also conclude that our scheme is practical for more complex blockchain since it is flexible and naturally consistent with decentralized systems.


## 2. Noninteractive Multiplication Based on Shamir’s Secret Sharing

### 2.1. Preliminaries

We assume that a distributed network hasn parties P1,P2,P3…Pn connected, and the index i of each party Pi is public. We continue to use the symbolic representation in [21]. Let ap represent a polynomial sharing of a secret a as in [22]. That means a is shared by a random polynomial fax=a+a1x+a2x+a3x+⋯at−1xt−1modp and ai,1≤i≤t−1,t−1<n/2 is randomly chosen from Zp. Among them, p is an odd prime, Zp is a prime field, and a∈Zp donates a∈0,…p−1. Each party can get a secret share fai calculated by its own index number.In this work, it involves a Boolean comparison operation. We useCp to represent a polynomial sharing of a Boolean operation result, and C∈0,1 is a Boolean test. For example, when a<b is true, then a<bp=1p.Shamir’s secret sharing scheme has some very convenient properties. When we writeap+bp, it means that the secret a+b can be revealed by calculating fai+fbi independently of each party where a and b are both secrets. In the same way, each party can compute c+fai, cfai without interaction. And c+a, ca can be revealed by gathering t parties’ shares where c is a constant. Calculating the multiplication of the two secrets ab by ap×bp is more complicated. In [23], an interactive multiplication has been proposed, and it requires each party to communicate interactively, which would result in a severe increase in computational complexity and time. To solve this problem, this paper proposes a noninteractive multiplication in which nodes can be computed locally.


### 2.2. Interactive Multiplication

Forap×bp , in simple terms, the original version of multiplication is to distribute the secret shares that have already been allocated by a new random polynomial. However, this will lead to a significant increase in secret shares, and the number of nodes involved in decryption will increase accordingly. Next, we will briefly introduce interactive multiplication.For the following two random polynomials, wherea and b are two secrets and the secret shares assigned to each node are represented by ap and bp, we need to get from ap and bp to abp.(1)fax=a+a1x+a2x2+⋯+at−1xt−1,fbx=b+b1x+b2x2⋯+bt−1xt−1.Each node getsfaxi and fbxi, so fabxi is available:(2)fabx=ab+r1x+r2x2⋯+r2t−2x2t−2.By using the Lagrange interpolation formula, we know that(3)fab0=∑j=02t−2fabxjlj0=ab,lj0=∏0≤m≤2t−m≠j−xmxj−xm.Since the order is 2t − 2, it needs to be distributed again to reduce its order to t − 1 so that shares can be computed directly. Then we need to construct 2t − 1 new random polynomials:(4)2t−1hx1x=fabx1+a1′x+a2′x2+⋯+at−1′xt−1,hx2x=fabx2+a1″x+a2″x2+⋯+at−1″xt−1,⋮,hx2t−1x=fabx2t−1+a12t−1x+a22t−1x2+⋯+at−12t−1xt−1.For one of the nodesxi,(5)hxix=fabxi+a1ix+a2ix2+⋯+at−1ixt−1=faxi⋅fbxi+a1ix+a2ix2+⋯+at−1ixt−1.xi uses the above polynomial to calculate the corresponding shares of other nodes and sends hxjxj. Let(6)Hx=∑j=02t−2lj0hxjx.(7)H0=l00fabx0+l10fabx1+⋯+l2t−20fabx2t=ab,where Hx is the shared random polynomial of ab. After each node receives allhxixj, calculateHj=∑xi=02t−2lixhxixjand then obtainabp.It can be seen from the above process that, in the interaction process, additional random polynomialshxix need to be constructed, and the corresponding secret shares will increase by 2t−1n. However, in blockchain, this will significantly reduce the efficiency of consensus, making it unable to meet the needs of transactions. Therefore, we design a noninteractive multiplication to eliminate the unnecessary extra traffic.


### 2.3. Noninteractive Multiplication

Besides homomorphic addition, efficient multiplication is also needed in the trading calculation. However, the multiplication of secret shares mentioned in Section2.2 essentially shares the product of two shares again as a new secret. And this requires interaction between nodes. To realize the goal that nodes can complete all secret shares locally, we designed a multiplication secret sharing without interaction.The form of direct multiplication of two secret sharesfaxi and fbxi is(8)faxifbxi=ab+r1x+r2x2+⋯r2t−2xi2t−2.Convert polynomials into vector multiplication, and the two random polynomials are shown as follows:(9)faxi=a,a1,a2,…,at−1xi0,xi1,xi2,…,x1t−1T.And(10)fbxi=b,b1,b2,…,bt−1xi0,xi1,xi2,…,x1t−1T.Thenfaxifbxi=α+β, where(11)α=ab,ab1+ba1,…,∑σ+τ=μaσbτ,…,∑σ+τ=t−1aσbτmodp⋅xi0,xi1,…xiμ,…,xit−1T,β=∑σ+τ=μaσbτ,…,∑σ+τ=ωaσbτ,…,at−2bt−1+at−1bt−2,at−1bt−1modp⋅xit−1xi1,…,xiω=t+1,…,xit−2,xit−1T.From the above formulas, we can see that the order ofα is precisely the order t−1 we need, and its leading coefficient is ab. So the secret share of ab belonging to node i can be obtained by subtracting faxifbxi from β, which is α.Based on the above observations, first, construct a random polynomial as follows:(12)fsx=s+a1x+a2x2+a3x3+⋯at−1xt−1modxit−1,wheres is secret and fsxi is a secret share distributed to i, where p<xi<q. Because the node i owns all the information of faxi, fbxi, and xi, node i can obtain the secret share of ab by calculating(13)fabxi=faxifbxi−xi−t−1−1faxifbximodxit−1−faxifbximodxit−1.Through the above operation, even if multiplication is needed in the transaction, the node can complete the secret share calculation locally without interacting.


#### 2.3.1. Proof of Correctness

For the above scheme, we will prove its correctness:(14)fax=a0+a1x+a2x2+⋯+at−1xt−1,fbx=b0+b1x+b2x2+⋯+bt−1xt−1.And then(15)fabx=fax⋅fbx=ab+c1x+c2x2+⋯+c2t−2x2t−2,fabxmodxt−1=ab+c1x+⋯+ct−1xt−1+tct+⋯+ct−2xt−2modxt−1.Andxtmodxt−1=1. Let(16)ab+c1x+c2x2+⋯ct−1xt−1=k1,ct+ct+1x+⋯+c2t−2xt−2=k2.The above formula can be converted to(17)fabxmodxt−1=k1+k2modxt−1fabx=k1+xtk2.And(18)fabxmodxt−1−fabx=−xt−1⋅k2⋅xt−1−1⋅fabxmodxt−1−fabx=−k2.So(19)fabx+xt−1−1fabxmodxt−1−fabxmodxt−1=k1+k2xt−k2modxt−1=k1+xt−1k2modxt−1=k1=ab+c1x+c2x2+⋯ct−1xt−1.


#### 2.3.2. Proof of Security

Next, we will conduct a simple analysis of its security.Lemma 1.
As long as no more thant participants collude, the Shamirt,n threshold secret sharing scheme is unconditionally secure.Obviously, in the noninteractive multiplication scheme proposed in this paper, when participants multiply the sharesfaxi,fbxi of two secret shares, there is no need for information interaction between participants. Therefore, according to Lemma 1, the noninteractive multiplication based on secret sharing proposed in this paper is unconditionally secure.


## 2.1. Preliminaries

We assume that a distributed network hasn parties P1,P2,P3…Pn connected, and the index i of each party Pi is public. We continue to use the symbolic representation in [21]. Let ap represent a polynomial sharing of a secret a as in [22]. That means a is shared by a random polynomial fax=a+a1x+a2x+a3x+⋯at−1xt−1modp and ai,1≤i≤t−1,t−1<n/2 is randomly chosen from Zp. Among them, p is an odd prime, Zp is a prime field, and a∈Zp donates a∈0,…p−1. Each party can get a secret share fai calculated by its own index number.In this work, it involves a Boolean comparison operation. We useCp to represent a polynomial sharing of a Boolean operation result, and C∈0,1 is a Boolean test. For example, when a<b is true, then a<bp=1p.Shamir’s secret sharing scheme has some very convenient properties. When we writeap+bp, it means that the secret a+b can be revealed by calculating fai+fbi independently of each party where a and b are both secrets. In the same way, each party can compute c+fai, cfai without interaction. And c+a, ca can be revealed by gathering t parties’ shares where c is a constant. Calculating the multiplication of the two secrets ab by ap×bp is more complicated. In [23], an interactive multiplication has been proposed, and it requires each party to communicate interactively, which would result in a severe increase in computational complexity and time. To solve this problem, this paper proposes a noninteractive multiplication in which nodes can be computed locally.


## 2.2. Interactive Multiplication

Forap×bp , in simple terms, the original version of multiplication is to distribute the secret shares that have already been allocated by a new random polynomial. However, this will lead to a significant increase in secret shares, and the number of nodes involved in decryption will increase accordingly. Next, we will briefly introduce interactive multiplication.For the following two random polynomials, wherea and b are two secrets and the secret shares assigned to each node are represented by ap and bp, we need to get from ap and bp to abp.(1)fax=a+a1x+a2x2+⋯+at−1xt−1,fbx=b+b1x+b2x2⋯+bt−1xt−1.Each node getsfaxi and fbxi, so fabxi is available:(2)fabx=ab+r1x+r2x2⋯+r2t−2x2t−2.By using the Lagrange interpolation formula, we know that(3)fab0=∑j=02t−2fabxjlj0=ab,lj0=∏0≤m≤2t−m≠j−xmxj−xm.Since the order is 2t − 2, it needs to be distributed again to reduce its order to t − 1 so that shares can be computed directly. Then we need to construct 2t − 1 new random polynomials:(4)2t−1hx1x=fabx1+a1′x+a2′x2+⋯+at−1′xt−1,hx2x=fabx2+a1″x+a2″x2+⋯+at−1″xt−1,⋮,hx2t−1x=fabx2t−1+a12t−1x+a22t−1x2+⋯+at−12t−1xt−1.For one of the nodesxi,(5)hxix=fabxi+a1ix+a2ix2+⋯+at−1ixt−1=faxi⋅fbxi+a1ix+a2ix2+⋯+at−1ixt−1.xi uses the above polynomial to calculate the corresponding shares of other nodes and sends hxjxj. Let(6)Hx=∑j=02t−2lj0hxjx.(7)H0=l00fabx0+l10fabx1+⋯+l2t−20fabx2t=ab,where Hx is the shared random polynomial of ab. After each node receives allhxixj, calculateHj=∑xi=02t−2lixhxixjand then obtainabp.It can be seen from the above process that, in the interaction process, additional random polynomialshxix need to be constructed, and the corresponding secret shares will increase by 2t−1n. However, in blockchain, this will significantly reduce the efficiency of consensus, making it unable to meet the needs of transactions. Therefore, we design a noninteractive multiplication to eliminate the unnecessary extra traffic.


## 2.3. Noninteractive Multiplication

Besides homomorphic addition, efficient multiplication is also needed in the trading calculation. However, the multiplication of secret shares mentioned in Section2.2 essentially shares the product of two shares again as a new secret. And this requires interaction between nodes. To realize the goal that nodes can complete all secret shares locally, we designed a multiplication secret sharing without interaction.The form of direct multiplication of two secret sharesfaxi and fbxi is(8)faxifbxi=ab+r1x+r2x2+⋯r2t−2xi2t−2.Convert polynomials into vector multiplication, and the two random polynomials are shown as follows:(9)faxi=a,a1,a2,…,at−1xi0,xi1,xi2,…,x1t−1T.And(10)fbxi=b,b1,b2,…,bt−1xi0,xi1,xi2,…,x1t−1T.Thenfaxifbxi=α+β, where(11)α=ab,ab1+ba1,…,∑σ+τ=μaσbτ,…,∑σ+τ=t−1aσbτmodp⋅xi0,xi1,…xiμ,…,xit−1T,β=∑σ+τ=μaσbτ,…,∑σ+τ=ωaσbτ,…,at−2bt−1+at−1bt−2,at−1bt−1modp⋅xit−1xi1,…,xiω=t+1,…,xit−2,xit−1T.From the above formulas, we can see that the order ofα is precisely the order t−1 we need, and its leading coefficient is ab. So the secret share of ab belonging to node i can be obtained by subtracting faxifbxi from β, which is α.Based on the above observations, first, construct a random polynomial as follows:(12)fsx=s+a1x+a2x2+a3x3+⋯at−1xt−1modxit−1,wheres is secret and fsxi is a secret share distributed to i, where p<xi<q. Because the node i owns all the information of faxi, fbxi, and xi, node i can obtain the secret share of ab by calculating(13)fabxi=faxifbxi−xi−t−1−1faxifbximodxit−1−faxifbximodxit−1.Through the above operation, even if multiplication is needed in the transaction, the node can complete the secret share calculation locally without interacting.


### 2.3.1. Proof of Correctness

For the above scheme, we will prove its correctness:(14)fax=a0+a1x+a2x2+⋯+at−1xt−1,fbx=b0+b1x+b2x2+⋯+bt−1xt−1.And then(15)fabx=fax⋅fbx=ab+c1x+c2x2+⋯+c2t−2x2t−2,fabxmodxt−1=ab+c1x+⋯+ct−1xt−1+tct+⋯+ct−2xt−2modxt−1.Andxtmodxt−1=1. Let(16)ab+c1x+c2x2+⋯ct−1xt−1=k1,ct+ct+1x+⋯+c2t−2xt−2=k2.The above formula can be converted to(17)fabxmodxt−1=k1+k2modxt−1fabx=k1+xtk2.And(18)fabxmodxt−1−fabx=−xt−1⋅k2⋅xt−1−1⋅fabxmodxt−1−fabx=−k2.So(19)fabx+xt−1−1fabxmodxt−1−fabxmodxt−1=k1+k2xt−k2modxt−1=k1+xt−1k2modxt−1=k1=ab+c1x+c2x2+⋯ct−1xt−1.


### 2.3.2. Proof of Security

Next, we will conduct a simple analysis of its security.Lemma 1.
As long as no more thant participants collude, the Shamirt,n threshold secret sharing scheme is unconditionally secure.Obviously, in the noninteractive multiplication scheme proposed in this paper, when participants multiply the sharesfaxi,fbxi of two secret shares, there is no need for information interaction between participants. Therefore, according to Lemma 1, the noninteractive multiplication based on secret sharing proposed in this paper is unconditionally secure.


## 2.3.1. Proof of Correctness

For the above scheme, we will prove its correctness:(14)fax=a0+a1x+a2x2+⋯+at−1xt−1,fbx=b0+b1x+b2x2+⋯+bt−1xt−1.And then(15)fabx=fax⋅fbx=ab+c1x+c2x2+⋯+c2t−2x2t−2,fabxmodxt−1=ab+c1x+⋯+ct−1xt−1+tct+⋯+ct−2xt−2modxt−1.Andxtmodxt−1=1. Let(16)ab+c1x+c2x2+⋯ct−1xt−1=k1,ct+ct+1x+⋯+c2t−2xt−2=k2.The above formula can be converted to(17)fabxmodxt−1=k1+k2modxt−1fabx=k1+xtk2.And(18)fabxmodxt−1−fabx=−xt−1⋅k2⋅xt−1−1⋅fabxmodxt−1−fabx=−k2.So(19)fabx+xt−1−1fabxmodxt−1−fabxmodxt−1=k1+k2xt−k2modxt−1=k1+xt−1k2modxt−1=k1=ab+c1x+c2x2+⋯ct−1xt−1.


## 2.3.2. Proof of Security

Next, we will conduct a simple analysis of its security.Lemma 1.
As long as no more thant participants collude, the Shamirt,n threshold secret sharing scheme is unconditionally secure.Obviously, in the noninteractive multiplication scheme proposed in this paper, when participants multiply the sharesfaxi,fbxi of two secret shares, there is no need for information interaction between participants. Therefore, according to Lemma 1, the noninteractive multiplication based on secret sharing proposed in this paper is unconditionally secure.


## 3. The Secure Data Comparison Model

### 3.1. Raft Protocol

As the core of the blockchain system, the consensus mechanism helps to maintain the consistency of nodes. Various mainstream consensus protocols are analysed in [24]. By measuring the performance of these consensus algorithms and combining with the characteristics required by our scheme, we decided to adopt the raft consensus protocol. The raft protocol can elect a temporary leader to make the system consists in a term. In a nutshell, the raft protocol breaks the consistency problem into three relatively independent subproblems: leader election, log replication, and safety.Since the blockchain in this paper is a logic-physical mapping structure, there are some differences in the logical and physical consensus process, among which the logical consensus process is as follows. Figure1 shows the consensus process on a logical chain.Figure 1
The consensus process on a logical chain. Ultimately, each node writes different secret shares to the local log.


#### 3.1.1. Leader Election

Nodes in the system have three states: follower, candidate, and leader. All nodes are started as followers, and their terms are initialized to 0. When the election starts, all nodes set the timeout at the same time. When a timeout occurs, the node becomes a candidate and sends the vote requests to the other nodes immediately. The timeout node only votes for itself, and its term automatically increases by 1. If it gets a majority of the votes in the system, it will become the leader.Since each node has a random timeout between 100 and 500 milliseconds, all the followers cannot become candidates and send the vote requests at the same time. In other words, the node that becomes a candidate first and sends the vote requests has the “first-mover advantage” of becoming the leader. But if two nodes happen to be candidates at the same time and split votes or the candidate does not receive more than half of the votes, then they will reset the timer and restart the election.


#### 3.1.2. Log Replication

When there is a leader, the system enters the work period. The client sends all the requests to the leader, and the leader schedules the order of concurrent requests to ensure the consistency of its state with the followers. Raft does this by informing followers of these requests and the order in which they are executed. The leader and followers execute these requests in the same order to ensure a consistent state.First, when a request is received, the leader writes it to the local log as an entry. Note that the entry’s status is uncommitted at this time, and the leader will not update the local data, so it will not be readable. When a leader is in the system, the leader will send a heartbeat to the followers at regular intervals. These heartbeats serve two purposes. First, they inform followers that the leader is online. Second, they can be used to send entry. Since the leader sending heartbeats is periodic, in one period, the leader may receive more than one entry from the client. Leader records the entry sent by the client to the local log and constantly AppendEntries until the next period, and these entries will be sent to the followers in parallel.When an AppendEntries is sent, the leader will add the new log entry’s index position (prevLogIndex) and Leader Term number (TERM) in it. The nodes verify consistency through the index inside the entries. If most nodes write it to the local log and return success, the entry written in the leader’s log will be marked as committed. When the leader responds to the client, the result will be informed to the followers with the next heartbeat. Upon receiving the heartbeat, the followers will also mark the entry as committed. This means that more than half of the nodes in the system are consistent.If the follower does not find the same index position and term number in its log, it will refuse to receive the new entry. To solve the problem that the follower’s logs are not consistent with the leader. The leader must find the position where the last log was not consistent, delete all the log entries from that position onwards, and send its logs to the follower.


#### 3.1.3. Safety

However, the log replication phase does not sufficiently guarantee that each follower will execute the same instructions in the same order. For example, a follower may be unavailable while the leader has sent some log entries and when the follower is online and the leader is unavailable. The problem will arise if the follower is elected as the leader and others’ log entries are rolled back.To solve the above problem, the leader must store all the log entries that have been committed. The candidate must contact most nodes to win an election. This means that every log entry that has been committed must exist on at least one node. If the candidate’s log is as new as most of the nodes, it must hold all the log entries that have been committed. Therefore, the raft protocol requires that the request must contain the candidate’s log, and the voting nodes will reject the requests whose logs are not fresh enough. Determine whose logs are newer by comparing the term and the index of the last log in the two candidates’ logs. If the last entry of the two logs has a different term, then the logs with a larger term number are newer. If the last entry in both logs has the same term, then the one with the longer log is newer.If a leader crashes before committing a log entry, the subsequent leader will continue to try to duplicate the log. However, a leader cannot determine that a log entry from a previous term that is saved to the major of followers has been committed. This is obvious from the process of log replication. The raft protocol does not commit a log entry from a previous term by counting the number of replicas. Only the log entries for the current term of the leader can be committed by counting the number of replicas. Once the current term log entry is committed in this way, previous log entries will also be committed indirectly due to the log matching feature.In fact, the public chain operates depending on the different physical chains stored by each node. As described above, in the early stage, each node votes for a leader node according to the leader election. Then, the leader will call the Comparison Protocol and Equality Test Protocol described in Sections3.2 and 3.3 to determine whether the transaction meets the requirements. If so, the leader will inform each node to update data. The entire election and consensus process for the physical chain is shown in Figure 2.Figure 2
The consensus process on a physical chain. Each node computes on a local physical chain.Different from the consensus process on the logical chain, each follower receives a different secret share, and the leader is responsible for calling the protocol for verification. Only when the leader runs the protocols to send message 1 to the followers will each follower perform the calculation and update on the local chain.


### 3.2. Comparison Protocol

In the process of transaction verification, it is necessary to verify whether the payer’s balance is enough to pay, which requires a comparison operation based on secret sharing. To implement the Comparison Protocol, Bitwise Sharing and LSB Protocol using wraparound should be implemented first. The specific call relationship is shown in Figure3.Figure 3
The call relationship of Comparison Protocol. Bitwise Sharing and LSB Protocol using wraparound are called subprotocols.


#### 3.2.1. Bitwise Sharing

Bitwise Sharing is sharing a secret by sharing each bit. In a nutshell, each participant shares a secreta∈Zp in the form of al−1p,…,a0p, ai∈0,1, where a=∑i=0l−12iai. For simplicity of notation, use aB for Bitwise Sharing al−1p,…,a0p.


#### 3.2.2. LSB Protocol Using Wraparound

To implement the Comparison Protocol, we first use the feature of wraparound under modulusp to estimate the size of the secret. We notice that, under the modulus p, the numbers less than p retain their properties, and the numbers greater than p wrap around. That means, if a∈0,1,2…p−1/2, then 2amodp0=0. If a∈p−1/2+1,…,p−1, then 2amodp0=1. Because when a<p/2, 2amodp is even and when a>p/2, wraparound occurs, 2amodp is odd. Thus, we can tell the magnitude of the secret a and p/2 by whether the lowest order after modulating p is 0 or 1.We want to computea0p from ap without exposing a, and we just randomize the secret a to hide with a random number r and then calculate by bit with the random value obtained. Since we have r, we can get a0p that we need. The whole calculation process is as follows:Parties generate a Bitwise SharingrB and get rp.Parties computecp=ap+rp and reveal c.Ifa<p/2 and no wraparound occurs, then a0p=c0⊕r0p.Ifa>p/2 and wraparound occurs, then a0p=1−c0⊕r0p.To see if there is a wraparound, we can comparer with c. If r<c, no wraparound occurs. And if r>c, wraparound occurs for c=a+r−p.To sum up,(20)a0p=1−c0⊕r0p×c<Brp+c0⊕r0p×1−c<Brp,wherec<Brp represents that c is less than r in bits, and the details are presented in [15]. In the actual calculation, the comparison result can be easily calculated by c<Brp, because all the parties that hold the bitwise shares of r and c are revealed. Therefore, we only need to calculate the result of c0⊕r0p. Since the parties have revealed c, they can easily obtain c0, and the value of c0 can be used to determine the value of c0⊕r0p. The specific calculation method is as follows:(21)c0⊕r0p=r0pifc0=0,1−r0pifc0=1.From the previous steps, we can obtaina0p from ap. And they can tell if a is greater than p/2 by 2a0p, where a<p/2p=1−2a0p.Through the above protocol, we can effectively calculate the size relation betweena and p/2 by using wraparound, laying a foundation for further comparison in the follow-up work.


#### 3.2.3. Comparison

When Bitwise Sharing and LSB Protocol using wraparound are implemented in sequence, each participant can determine whether a secreta is less than p/2. Then, it can determine whether a is less than b through the different situations of the two secrets in the interval 0,p/2. For the two secrets a and b that need to be compared, let w=a<p/2, x=b<p/2, y=a−bmodp<p/2, and z=a<b. The truth relation is shown in Table 1.Table 1
The truth case of different comparisons in the Comparison Protocol.
wxyz10∗101∗00001001011011110According to the truth table above, the expression forz=a<b is(22)z=wx¯∨w¯x¯y¯∨wxy¯=w1−x+1−w1−x1−y+wx1−y=wx+y−2xy+1−y−x+xy.


### 3.3. Equality Test Protocol

When participants need to compare whether two secrets are equal, they need to implement Equality Test Protocol, which contains a relatively large number of subprotocols. Since we creatively propose noninteractive multiplication as the underlying module of Equality Test Protocol, the delay caused by asynchronous communication can be greatly reduced. In addition, as described in Figure4, Unbounded Fan-In Or, Prefix-Or, Bitwise Less-Than, Joint Random Number Sharing, and so on are also called submodules.Figure 4
The call relationship of Equality Test Protocol. Subprotocols such as noninteractive multiplication are called.Since there are many protocols nested in Equality Test Protocol, this section mainly describes the two protocols at the top of the call relationship. For details of other submodules, see [21]. Similarly, we give the symbolic representation of each subprotocol so as not to cause confusion when building subsequent protocols, as shown in Table 2.Table 2
Symbolic representation of protocols.
Protocol nameSymbolic representationUnbounded Fan-In Or∨i=0l−1aip, ai∈0,1Prefix-Orb1p,…,blp, bi=∨j=1iajBitwise Less-Thana<BbpJoint Random Number Bitwise Sharinga∈R0,1pJoint Random Number Sharingr∈RZppUnbounded Fan-In And∨i=0l−1aip, ai∈0,1


#### 3.3.1. Joint Random Number Bitwise Sharing

To generate a shared random number, according to Bitwise Sharing, participants need to generate Bitwise Sharing for each bit ofri and calculate 0≤r=∑i=0l−12iri<p. Then, participants generate l bits ri∈R0,1p,0≤r≤l−1 according to the Joint Random Bit Sharing. Finally, participants calculate r<Bpp by Bitwise Less-Than and recover the comparison result of r<p. If the recovered comparison result is 1, the generation of bitwise shared random number succeeds. If the result is 0, the protocol is executed again.


#### 3.3.2. Unbounded Fan-In And

In the subsequent Equality Test Protocol, the Unbounded Fan-In And is necessary, which computes∨i=0l−1aip, where al−1p,…,a0p and ai∈0,1. As in [25], Damgård et al. proposed a symmetric Boolean function which only depends on the number of 1’s in its input. With this framework, it can be concretized into Unbounded Fan-In And.Giveal−1p,…,a0p, where ai∈0,1. Assume A=1+∑i=0i=l−1ai, and parties compute Ap=1+∑i=0i=l−1aip; that means A is the number of 1 in ai plus 1. Then, parties can construct a l-degree polynomial flx by fl1=0,fl2=0,…,fll=0,fll+1=1. It is obvious that flA=∧i=0l−1ai, and we convert computing ∧i=0l−1aip to flAp.We know thatflx can be written as flx=α0+α1x+α2x2+⋯αlxlmodp, and thanks to the properties of shared secrets, flxp=α0+α1x+α2x2+⋯αlxlmodpp can be simplified to flxp=α0+∑i=1i=lαixip. To obtain flAp, parties only need to compute Aip,1≤i≤l for they have already got αi,0≤i≤l by using Lagrange interpolation.For1≤i≤l, parties generate two shared random numbers bi∈RZpp and bi′∈RZpp; see the detailed generation method in [26]. Then they compute Bip=bip×bi′p and reveal Bi:(23)bi−1pbip=BipBi−1p,bi−1pbip=bipbi′pBi−1p,bi−1p=bi′pBi−1.First, each party computesci′p,1≤i≤l:(24)c1p=Ap×b1−1p,c2p=Ap×b1p×b2−1p,c3p=Ap×b3p×b3−1p,⋮,clp=Ap×bl−1p×bl−1p.Then, they revealci′. The parties can compute Aip=∏k=1ickbip,1≤i≤l in parallel. The reason why A=1+∑i=0i=l−1ai is to hide the case when the number of 1 in ai is zero.The framework proposed by Damgård is suitable for many similar subprotocols, such as Unbounded Fan-In OR and Unbounded Fan-In XOR.


### 3.4. Secure UTXO Based on Secret Sharing

The challenge of the scheme is to support the privacy of the transaction; the other nodes should not know the value of the transaction except the two parties to the transaction. The transaction can be completed and verified without exposing the balance and the transaction value. Figure5 shows a general overview of the scheme. When a transaction is initiated, the other nodes on the blockchain only need to receive the secret shares sent by both parties of the transaction, use Comparison Protocol to calculate whether the balance of A is greater than the transaction value, and use Equality Test Protocol to calculate whether the two distributed transaction values are equal. The rest of this section will describe the calculation of the entire transaction process and the changes in the secret shares held at each node before and after the transaction.Figure 5
Transaction process. In the whole transaction process, no information about the value will be exposed, and only the comparison result 0 or 1 will be recovered.


## 3.1. Raft Protocol

As the core of the blockchain system, the consensus mechanism helps to maintain the consistency of nodes. Various mainstream consensus protocols are analysed in [24]. By measuring the performance of these consensus algorithms and combining with the characteristics required by our scheme, we decided to adopt the raft consensus protocol. The raft protocol can elect a temporary leader to make the system consists in a term. In a nutshell, the raft protocol breaks the consistency problem into three relatively independent subproblems: leader election, log replication, and safety.Since the blockchain in this paper is a logic-physical mapping structure, there are some differences in the logical and physical consensus process, among which the logical consensus process is as follows. Figure1 shows the consensus process on a logical chain.Figure 1
The consensus process on a logical chain. Ultimately, each node writes different secret shares to the local log.


### 3.1.1. Leader Election

Nodes in the system have three states: follower, candidate, and leader. All nodes are started as followers, and their terms are initialized to 0. When the election starts, all nodes set the timeout at the same time. When a timeout occurs, the node becomes a candidate and sends the vote requests to the other nodes immediately. The timeout node only votes for itself, and its term automatically increases by 1. If it gets a majority of the votes in the system, it will become the leader.Since each node has a random timeout between 100 and 500 milliseconds, all the followers cannot become candidates and send the vote requests at the same time. In other words, the node that becomes a candidate first and sends the vote requests has the “first-mover advantage” of becoming the leader. But if two nodes happen to be candidates at the same time and split votes or the candidate does not receive more than half of the votes, then they will reset the timer and restart the election.


### 3.1.2. Log Replication

When there is a leader, the system enters the work period. The client sends all the requests to the leader, and the leader schedules the order of concurrent requests to ensure the consistency of its state with the followers. Raft does this by informing followers of these requests and the order in which they are executed. The leader and followers execute these requests in the same order to ensure a consistent state.First, when a request is received, the leader writes it to the local log as an entry. Note that the entry’s status is uncommitted at this time, and the leader will not update the local data, so it will not be readable. When a leader is in the system, the leader will send a heartbeat to the followers at regular intervals. These heartbeats serve two purposes. First, they inform followers that the leader is online. Second, they can be used to send entry. Since the leader sending heartbeats is periodic, in one period, the leader may receive more than one entry from the client. Leader records the entry sent by the client to the local log and constantly AppendEntries until the next period, and these entries will be sent to the followers in parallel.When an AppendEntries is sent, the leader will add the new log entry’s index position (prevLogIndex) and Leader Term number (TERM) in it. The nodes verify consistency through the index inside the entries. If most nodes write it to the local log and return success, the entry written in the leader’s log will be marked as committed. When the leader responds to the client, the result will be informed to the followers with the next heartbeat. Upon receiving the heartbeat, the followers will also mark the entry as committed. This means that more than half of the nodes in the system are consistent.If the follower does not find the same index position and term number in its log, it will refuse to receive the new entry. To solve the problem that the follower’s logs are not consistent with the leader. The leader must find the position where the last log was not consistent, delete all the log entries from that position onwards, and send its logs to the follower.


### 3.1.3. Safety

However, the log replication phase does not sufficiently guarantee that each follower will execute the same instructions in the same order. For example, a follower may be unavailable while the leader has sent some log entries and when the follower is online and the leader is unavailable. The problem will arise if the follower is elected as the leader and others’ log entries are rolled back.To solve the above problem, the leader must store all the log entries that have been committed. The candidate must contact most nodes to win an election. This means that every log entry that has been committed must exist on at least one node. If the candidate’s log is as new as most of the nodes, it must hold all the log entries that have been committed. Therefore, the raft protocol requires that the request must contain the candidate’s log, and the voting nodes will reject the requests whose logs are not fresh enough. Determine whose logs are newer by comparing the term and the index of the last log in the two candidates’ logs. If the last entry of the two logs has a different term, then the logs with a larger term number are newer. If the last entry in both logs has the same term, then the one with the longer log is newer.If a leader crashes before committing a log entry, the subsequent leader will continue to try to duplicate the log. However, a leader cannot determine that a log entry from a previous term that is saved to the major of followers has been committed. This is obvious from the process of log replication. The raft protocol does not commit a log entry from a previous term by counting the number of replicas. Only the log entries for the current term of the leader can be committed by counting the number of replicas. Once the current term log entry is committed in this way, previous log entries will also be committed indirectly due to the log matching feature.In fact, the public chain operates depending on the different physical chains stored by each node. As described above, in the early stage, each node votes for a leader node according to the leader election. Then, the leader will call the Comparison Protocol and Equality Test Protocol described in Sections3.2 and 3.3 to determine whether the transaction meets the requirements. If so, the leader will inform each node to update data. The entire election and consensus process for the physical chain is shown in Figure 2.Figure 2
The consensus process on a physical chain. Each node computes on a local physical chain.Different from the consensus process on the logical chain, each follower receives a different secret share, and the leader is responsible for calling the protocol for verification. Only when the leader runs the protocols to send message 1 to the followers will each follower perform the calculation and update on the local chain.


## 3.1.1. Leader Election

Nodes in the system have three states: follower, candidate, and leader. All nodes are started as followers, and their terms are initialized to 0. When the election starts, all nodes set the timeout at the same time. When a timeout occurs, the node becomes a candidate and sends the vote requests to the other nodes immediately. The timeout node only votes for itself, and its term automatically increases by 1. If it gets a majority of the votes in the system, it will become the leader.Since each node has a random timeout between 100 and 500 milliseconds, all the followers cannot become candidates and send the vote requests at the same time. In other words, the node that becomes a candidate first and sends the vote requests has the “first-mover advantage” of becoming the leader. But if two nodes happen to be candidates at the same time and split votes or the candidate does not receive more than half of the votes, then they will reset the timer and restart the election.


## 3.1.2. Log Replication

When there is a leader, the system enters the work period. The client sends all the requests to the leader, and the leader schedules the order of concurrent requests to ensure the consistency of its state with the followers. Raft does this by informing followers of these requests and the order in which they are executed. The leader and followers execute these requests in the same order to ensure a consistent state.First, when a request is received, the leader writes it to the local log as an entry. Note that the entry’s status is uncommitted at this time, and the leader will not update the local data, so it will not be readable. When a leader is in the system, the leader will send a heartbeat to the followers at regular intervals. These heartbeats serve two purposes. First, they inform followers that the leader is online. Second, they can be used to send entry. Since the leader sending heartbeats is periodic, in one period, the leader may receive more than one entry from the client. Leader records the entry sent by the client to the local log and constantly AppendEntries until the next period, and these entries will be sent to the followers in parallel.When an AppendEntries is sent, the leader will add the new log entry’s index position (prevLogIndex) and Leader Term number (TERM) in it. The nodes verify consistency through the index inside the entries. If most nodes write it to the local log and return success, the entry written in the leader’s log will be marked as committed. When the leader responds to the client, the result will be informed to the followers with the next heartbeat. Upon receiving the heartbeat, the followers will also mark the entry as committed. This means that more than half of the nodes in the system are consistent.If the follower does not find the same index position and term number in its log, it will refuse to receive the new entry. To solve the problem that the follower’s logs are not consistent with the leader. The leader must find the position where the last log was not consistent, delete all the log entries from that position onwards, and send its logs to the follower.


## 3.1.3. Safety

However, the log replication phase does not sufficiently guarantee that each follower will execute the same instructions in the same order. For example, a follower may be unavailable while the leader has sent some log entries and when the follower is online and the leader is unavailable. The problem will arise if the follower is elected as the leader and others’ log entries are rolled back.To solve the above problem, the leader must store all the log entries that have been committed. The candidate must contact most nodes to win an election. This means that every log entry that has been committed must exist on at least one node. If the candidate’s log is as new as most of the nodes, it must hold all the log entries that have been committed. Therefore, the raft protocol requires that the request must contain the candidate’s log, and the voting nodes will reject the requests whose logs are not fresh enough. Determine whose logs are newer by comparing the term and the index of the last log in the two candidates’ logs. If the last entry of the two logs has a different term, then the logs with a larger term number are newer. If the last entry in both logs has the same term, then the one with the longer log is newer.If a leader crashes before committing a log entry, the subsequent leader will continue to try to duplicate the log. However, a leader cannot determine that a log entry from a previous term that is saved to the major of followers has been committed. This is obvious from the process of log replication. The raft protocol does not commit a log entry from a previous term by counting the number of replicas. Only the log entries for the current term of the leader can be committed by counting the number of replicas. Once the current term log entry is committed in this way, previous log entries will also be committed indirectly due to the log matching feature.In fact, the public chain operates depending on the different physical chains stored by each node. As described above, in the early stage, each node votes for a leader node according to the leader election. Then, the leader will call the Comparison Protocol and Equality Test Protocol described in Sections3.2 and 3.3 to determine whether the transaction meets the requirements. If so, the leader will inform each node to update data. The entire election and consensus process for the physical chain is shown in Figure 2.Figure 2
The consensus process on a physical chain. Each node computes on a local physical chain.Different from the consensus process on the logical chain, each follower receives a different secret share, and the leader is responsible for calling the protocol for verification. Only when the leader runs the protocols to send message 1 to the followers will each follower perform the calculation and update on the local chain.


## 3.2. Comparison Protocol

In the process of transaction verification, it is necessary to verify whether the payer’s balance is enough to pay, which requires a comparison operation based on secret sharing. To implement the Comparison Protocol, Bitwise Sharing and LSB Protocol using wraparound should be implemented first. The specific call relationship is shown in Figure3.Figure 3
The call relationship of Comparison Protocol. Bitwise Sharing and LSB Protocol using wraparound are called subprotocols.


### 3.2.1. Bitwise Sharing

Bitwise Sharing is sharing a secret by sharing each bit. In a nutshell, each participant shares a secreta∈Zp in the form of al−1p,…,a0p, ai∈0,1, where a=∑i=0l−12iai. For simplicity of notation, use aB for Bitwise Sharing al−1p,…,a0p.


### 3.2.2. LSB Protocol Using Wraparound

To implement the Comparison Protocol, we first use the feature of wraparound under modulusp to estimate the size of the secret. We notice that, under the modulus p, the numbers less than p retain their properties, and the numbers greater than p wrap around. That means, if a∈0,1,2…p−1/2, then 2amodp0=0. If a∈p−1/2+1,…,p−1, then 2amodp0=1. Because when a<p/2, 2amodp is even and when a>p/2, wraparound occurs, 2amodp is odd. Thus, we can tell the magnitude of the secret a and p/2 by whether the lowest order after modulating p is 0 or 1.We want to computea0p from ap without exposing a, and we just randomize the secret a to hide with a random number r and then calculate by bit with the random value obtained. Since we have r, we can get a0p that we need. The whole calculation process is as follows:Parties generate a Bitwise SharingrB and get rp.Parties computecp=ap+rp and reveal c.Ifa<p/2 and no wraparound occurs, then a0p=c0⊕r0p.Ifa>p/2 and wraparound occurs, then a0p=1−c0⊕r0p.To see if there is a wraparound, we can comparer with c. If r<c, no wraparound occurs. And if r>c, wraparound occurs for c=a+r−p.To sum up,(20)a0p=1−c0⊕r0p×c<Brp+c0⊕r0p×1−c<Brp,wherec<Brp represents that c is less than r in bits, and the details are presented in [15]. In the actual calculation, the comparison result can be easily calculated by c<Brp, because all the parties that hold the bitwise shares of r and c are revealed. Therefore, we only need to calculate the result of c0⊕r0p. Since the parties have revealed c, they can easily obtain c0, and the value of c0 can be used to determine the value of c0⊕r0p. The specific calculation method is as follows:(21)c0⊕r0p=r0pifc0=0,1−r0pifc0=1.From the previous steps, we can obtaina0p from ap. And they can tell if a is greater than p/2 by 2a0p, where a<p/2p=1−2a0p.Through the above protocol, we can effectively calculate the size relation betweena and p/2 by using wraparound, laying a foundation for further comparison in the follow-up work.


### 3.2.3. Comparison

When Bitwise Sharing and LSB Protocol using wraparound are implemented in sequence, each participant can determine whether a secreta is less than p/2. Then, it can determine whether a is less than b through the different situations of the two secrets in the interval 0,p/2. For the two secrets a and b that need to be compared, let w=a<p/2, x=b<p/2, y=a−bmodp<p/2, and z=a<b. The truth relation is shown in Table 1.Table 1
The truth case of different comparisons in the Comparison Protocol.
wxyz10∗101∗00001001011011110According to the truth table above, the expression forz=a<b is(22)z=wx¯∨w¯x¯y¯∨wxy¯=w1−x+1−w1−x1−y+wx1−y=wx+y−2xy+1−y−x+xy.


## 3.2.1. Bitwise Sharing

Bitwise Sharing is sharing a secret by sharing each bit. In a nutshell, each participant shares a secreta∈Zp in the form of al−1p,…,a0p, ai∈0,1, where a=∑i=0l−12iai. For simplicity of notation, use aB for Bitwise Sharing al−1p,…,a0p.


## 3.2.2. LSB Protocol Using Wraparound

To implement the Comparison Protocol, we first use the feature of wraparound under modulusp to estimate the size of the secret. We notice that, under the modulus p, the numbers less than p retain their properties, and the numbers greater than p wrap around. That means, if a∈0,1,2…p−1/2, then 2amodp0=0. If a∈p−1/2+1,…,p−1, then 2amodp0=1. Because when a<p/2, 2amodp is even and when a>p/2, wraparound occurs, 2amodp is odd. Thus, we can tell the magnitude of the secret a and p/2 by whether the lowest order after modulating p is 0 or 1.We want to computea0p from ap without exposing a, and we just randomize the secret a to hide with a random number r and then calculate by bit with the random value obtained. Since we have r, we can get a0p that we need. The whole calculation process is as follows:Parties generate a Bitwise SharingrB and get rp.Parties computecp=ap+rp and reveal c.Ifa<p/2 and no wraparound occurs, then a0p=c0⊕r0p.Ifa>p/2 and wraparound occurs, then a0p=1−c0⊕r0p.To see if there is a wraparound, we can comparer with c. If r<c, no wraparound occurs. And if r>c, wraparound occurs for c=a+r−p.To sum up,(20)a0p=1−c0⊕r0p×c<Brp+c0⊕r0p×1−c<Brp,wherec<Brp represents that c is less than r in bits, and the details are presented in [15]. In the actual calculation, the comparison result can be easily calculated by c<Brp, because all the parties that hold the bitwise shares of r and c are revealed. Therefore, we only need to calculate the result of c0⊕r0p. Since the parties have revealed c, they can easily obtain c0, and the value of c0 can be used to determine the value of c0⊕r0p. The specific calculation method is as follows:(21)c0⊕r0p=r0pifc0=0,1−r0pifc0=1.From the previous steps, we can obtaina0p from ap. And they can tell if a is greater than p/2 by 2a0p, where a<p/2p=1−2a0p.Through the above protocol, we can effectively calculate the size relation betweena and p/2 by using wraparound, laying a foundation for further comparison in the follow-up work.


## 3.2.3. Comparison

When Bitwise Sharing and LSB Protocol using wraparound are implemented in sequence, each participant can determine whether a secreta is less than p/2. Then, it can determine whether a is less than b through the different situations of the two secrets in the interval 0,p/2. For the two secrets a and b that need to be compared, let w=a<p/2, x=b<p/2, y=a−bmodp<p/2, and z=a<b. The truth relation is shown in Table 1.Table 1
The truth case of different comparisons in the Comparison Protocol.
wxyz10∗101∗00001001011011110According to the truth table above, the expression forz=a<b is(22)z=wx¯∨w¯x¯y¯∨wxy¯=w1−x+1−w1−x1−y+wx1−y=wx+y−2xy+1−y−x+xy.


## 3.3. Equality Test Protocol

When participants need to compare whether two secrets are equal, they need to implement Equality Test Protocol, which contains a relatively large number of subprotocols. Since we creatively propose noninteractive multiplication as the underlying module of Equality Test Protocol, the delay caused by asynchronous communication can be greatly reduced. In addition, as described in Figure4, Unbounded Fan-In Or, Prefix-Or, Bitwise Less-Than, Joint Random Number Sharing, and so on are also called submodules.Figure 4
The call relationship of Equality Test Protocol. Subprotocols such as noninteractive multiplication are called.Since there are many protocols nested in Equality Test Protocol, this section mainly describes the two protocols at the top of the call relationship. For details of other submodules, see [21]. Similarly, we give the symbolic representation of each subprotocol so as not to cause confusion when building subsequent protocols, as shown in Table 2.Table 2
Symbolic representation of protocols.
Protocol nameSymbolic representationUnbounded Fan-In Or∨i=0l−1aip, ai∈0,1Prefix-Orb1p,…,blp, bi=∨j=1iajBitwise Less-Thana<BbpJoint Random Number Bitwise Sharinga∈R0,1pJoint Random Number Sharingr∈RZppUnbounded Fan-In And∨i=0l−1aip, ai∈0,1


### 3.3.1. Joint Random Number Bitwise Sharing

To generate a shared random number, according to Bitwise Sharing, participants need to generate Bitwise Sharing for each bit ofri and calculate 0≤r=∑i=0l−12iri<p. Then, participants generate l bits ri∈R0,1p,0≤r≤l−1 according to the Joint Random Bit Sharing. Finally, participants calculate r<Bpp by Bitwise Less-Than and recover the comparison result of r<p. If the recovered comparison result is 1, the generation of bitwise shared random number succeeds. If the result is 0, the protocol is executed again.


### 3.3.2. Unbounded Fan-In And

In the subsequent Equality Test Protocol, the Unbounded Fan-In And is necessary, which computes∨i=0l−1aip, where al−1p,…,a0p and ai∈0,1. As in [25], Damgård et al. proposed a symmetric Boolean function which only depends on the number of 1’s in its input. With this framework, it can be concretized into Unbounded Fan-In And.Giveal−1p,…,a0p, where ai∈0,1. Assume A=1+∑i=0i=l−1ai, and parties compute Ap=1+∑i=0i=l−1aip; that means A is the number of 1 in ai plus 1. Then, parties can construct a l-degree polynomial flx by fl1=0,fl2=0,…,fll=0,fll+1=1. It is obvious that flA=∧i=0l−1ai, and we convert computing ∧i=0l−1aip to flAp.We know thatflx can be written as flx=α0+α1x+α2x2+⋯αlxlmodp, and thanks to the properties of shared secrets, flxp=α0+α1x+α2x2+⋯αlxlmodpp can be simplified to flxp=α0+∑i=1i=lαixip. To obtain flAp, parties only need to compute Aip,1≤i≤l for they have already got αi,0≤i≤l by using Lagrange interpolation.For1≤i≤l, parties generate two shared random numbers bi∈RZpp and bi′∈RZpp; see the detailed generation method in [26]. Then they compute Bip=bip×bi′p and reveal Bi:(23)bi−1pbip=BipBi−1p,bi−1pbip=bipbi′pBi−1p,bi−1p=bi′pBi−1.First, each party computesci′p,1≤i≤l:(24)c1p=Ap×b1−1p,c2p=Ap×b1p×b2−1p,c3p=Ap×b3p×b3−1p,⋮,clp=Ap×bl−1p×bl−1p.Then, they revealci′. The parties can compute Aip=∏k=1ickbip,1≤i≤l in parallel. The reason why A=1+∑i=0i=l−1ai is to hide the case when the number of 1 in ai is zero.The framework proposed by Damgård is suitable for many similar subprotocols, such as Unbounded Fan-In OR and Unbounded Fan-In XOR.


## 3.3.1. Joint Random Number Bitwise Sharing

To generate a shared random number, according to Bitwise Sharing, participants need to generate Bitwise Sharing for each bit ofri and calculate 0≤r=∑i=0l−12iri<p. Then, participants generate l bits ri∈R0,1p,0≤r≤l−1 according to the Joint Random Bit Sharing. Finally, participants calculate r<Bpp by Bitwise Less-Than and recover the comparison result of r<p. If the recovered comparison result is 1, the generation of bitwise shared random number succeeds. If the result is 0, the protocol is executed again.


## 3.3.2. Unbounded Fan-In And

In the subsequent Equality Test Protocol, the Unbounded Fan-In And is necessary, which computes∨i=0l−1aip, where al−1p,…,a0p and ai∈0,1. As in [25], Damgård et al. proposed a symmetric Boolean function which only depends on the number of 1’s in its input. With this framework, it can be concretized into Unbounded Fan-In And.Giveal−1p,…,a0p, where ai∈0,1. Assume A=1+∑i=0i=l−1ai, and parties compute Ap=1+∑i=0i=l−1aip; that means A is the number of 1 in ai plus 1. Then, parties can construct a l-degree polynomial flx by fl1=0,fl2=0,…,fll=0,fll+1=1. It is obvious that flA=∧i=0l−1ai, and we convert computing ∧i=0l−1aip to flAp.We know thatflx can be written as flx=α0+α1x+α2x2+⋯αlxlmodp, and thanks to the properties of shared secrets, flxp=α0+α1x+α2x2+⋯αlxlmodpp can be simplified to flxp=α0+∑i=1i=lαixip. To obtain flAp, parties only need to compute Aip,1≤i≤l for they have already got αi,0≤i≤l by using Lagrange interpolation.For1≤i≤l, parties generate two shared random numbers bi∈RZpp and bi′∈RZpp; see the detailed generation method in [26]. Then they compute Bip=bip×bi′p and reveal Bi:(23)bi−1pbip=BipBi−1p,bi−1pbip=bipbi′pBi−1p,bi−1p=bi′pBi−1.First, each party computesci′p,1≤i≤l:(24)c1p=Ap×b1−1p,c2p=Ap×b1p×b2−1p,c3p=Ap×b3p×b3−1p,⋮,clp=Ap×bl−1p×bl−1p.Then, they revealci′. The parties can compute Aip=∏k=1ickbip,1≤i≤l in parallel. The reason why A=1+∑i=0i=l−1ai is to hide the case when the number of 1 in ai is zero.The framework proposed by Damgård is suitable for many similar subprotocols, such as Unbounded Fan-In OR and Unbounded Fan-In XOR.


## 3.4. Secure UTXO Based on Secret Sharing

The challenge of the scheme is to support the privacy of the transaction; the other nodes should not know the value of the transaction except the two parties to the transaction. The transaction can be completed and verified without exposing the balance and the transaction value. Figure5 shows a general overview of the scheme. When a transaction is initiated, the other nodes on the blockchain only need to receive the secret shares sent by both parties of the transaction, use Comparison Protocol to calculate whether the balance of A is greater than the transaction value, and use Equality Test Protocol to calculate whether the two distributed transaction values are equal. The rest of this section will describe the calculation of the entire transaction process and the changes in the secret shares held at each node before and after the transaction.Figure 5
Transaction process. In the whole transaction process, no information about the value will be exposed, and only the comparison result 0 or 1 will be recovered.


## 4. The Overview of Blockchain

To make the verification of balance relatively efficient in the transaction process, this scheme adopts the UTXO-based blockchain model. However, unlike the UTXO of the Bitcoin system, our UTXO holds secret shares. Since each node keeps different secret shares, so they keep different physical chains. Because different secret shares correspond to the same transaction, nodes keep the same logical chain. The corresponding relationship between physical chain and logical chain is shown in Figure6.Figure 6
Logical chain and physical chain. The nodes hold different physical chains that correspond to the same logical chain.


### 4.1. Transaction Process

This section describes in detail the calculations designed during the transaction. By combining Shamir’s secret sharing scheme, it realizes the confidentiality of balance and transaction value on the premise of ensuring the original properties of the blockchain.The payerA and the payee B initiate a transaction to the blockchain. Suppose the balances of the two accounts are TA and TB. The transaction value which A needs to distribute is w1, and the transaction value that B distributes is w2. The execution of a transaction is mainly divided into two stages: (1) verify that the balance is greater than the payment, and (2) verify that the payment is equal to the value received. The transaction process is as follows.


#### 4.1.1. Verify That the BalanceTA of A Is Greater Than the Payment w1

The balance ofA and B is stored in the form of secret shares and is expressed as fTAx and fTBx, where(25)fTAx=TA+a1x+a2x2+⋯+at−1xt−1modp,fTBx=TB+a1′x+a2′x2+⋯+at−1′xt−1modp.WhenA trades, A generates a random polynomial and takes w1 as the secret. Then A calculates the secret shares corresponding to each node and distributes them. Similarly, B also generates a random polynomial that distributes the transaction value w2 to other nodes. The random polynomial for w1 and w2 is as follows:(26)fw1x=w1+b1x+b2x2+⋯+bt−1xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp.After the above operation, each node holds the secret shares of the balance ofTA and TB and the transaction value of w1 and w2. We use w1p, w2p, TAp, and TBp to represent simplicity. To compare the size of w1 and TA, we need to use the LSB Protocol using wraparound mentioned earlier. We can calculate w1<p/2p, TA<p/2p, and TA−w1<p/2pmodpp very easily with LSB Protocol using wraparound. Then, we discuss all the cases of w1 and TA using P/2.Case 1.
IfTA<p/2p=1 and w1<p/2p=0, then TA<w1p=1.Case 2.
IfTA<p/2p=0 and w1<p/2p=1, then TA<w1p=0.Case 3.
IfTA<p/2p=0, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 4.
IfTA<p/2p=0, w1<p/2p=0, and TA−w1<p/2p=1, then TA<w1p=1.Case 5.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 6.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=1, then TA<w1p=0.
Whenw1<TAp=1, it means A has enough balance to initiate the transaction.


#### 4.1.2. Verify That the Paymentw1 is Equal to the Amount Received w2

When a transaction is initiated, the other parties must verify that the money spent byA is equal to the money received by B. Otherwise, some malicious nodes will use the imbalance to cheat money. For example, the transaction value A that distributes to other nodes is 5 BTC, while the transaction value that distributes by B is 3 BTC. If it is not verified, 2 BTC will be defrauded by malicious nodes.During the transaction,A and B distribute secret shares of w1 and w2 in parallel. We still use w1p and w2p for simplicity. Nodes can easily compute w1−w2p, and if they can verify a=w1−w2=0p, they can achieve their goals. The framework of the whole verification process is very clear. We randomize a by c=a+r firstly. Then, all we have to do is verify that c=r to determine a=0.First, nodes generate a bitwise shared random number byr∈RZpB and get rp=∑i=0i=l−12irip. Then, nodes compute cp=ap+rp and reveal c=a+rmodp. Nodes can easily obtain the binary of c for it is public. Then the parties compute ci′p, which shows if bits of c and r are equal.(27)ci′p=1−ripifci=0.ripifci=1,It is obvious thatci′=1 if ci=ri. Finally, parties obtain a=0p by computing the Unbounded Fan-In And ∧i=0i=l−1ci′p. Through the above steps, nodes can compute w1−w2=0p.After the above two steps, the nodes hold the secret shares ofw1−w2=0p and w1<TAp. As long as any t nodes send the secret shares to the current leader, the result can be revealed. If the verification result is true, each node calculates TA−wp and TB+wp locally, and the transaction is written to the blockchain. If the verification result is false, the transaction is ruled illegal.


### 4.2. Changes of Secret Shares

As we described earlier, each node stores secret shares of the balance of the other nodes. The secret shares held by each node before trading are shown on the left side of Figure7, and it is easy to see that the secret shares obtained by different nodes are different values of x calculated by the different random polynomials. After verifying the transaction, thanks to the properties of secret shares, each node can add and subtract the secret shares of the balance of A and B with the secret shares of the transaction value directly.Figure 7
The change of the secret shares. In the secret shares kept by each node, only the shares related to the transaction node will change.


### 4.3. The Data Structure

In this section, we will describe the major data structures and the main properties, including the basic unitTransaction, the Block on which transactions are recorded, the Log held locally by the nodes, and the UTXO. We still use the block structure, but unlike the public chain, we simply keep transactions on the logical chain, and there is no amount of money involved. The local log records secret shares of each node’s balance that is constantly updated. We made a slight change to the UTXO structure in Bitcoin, so instead of holding unspent Bitcoin, it is the shares of the node’s most recent balance.


#### 4.3.1. Block

Similar to the Bitcoin system, blocks are divided into head and body. The specific composition of the block is shown in Figure8. However, because of the different consensus algorithms, we do not need proof of work for mining, so there are no random numbers in the block header for proof of work. It simply contains the header of the previous block, the Merkle tree hash of the current block, and the timestamp.Figure 8
Block. Blocks do not contain difficulty values required for mining.


#### 4.3.2. Transaction

The transaction is the basic unit that makes up the block, and it consists of two main parts:Vin and Vout. Vin represents the input to the transaction, which points to the most recent unspent shares of the balance in UTXO. It is important to note that UTXO here holds the shares of the balance. Even if the balance of an account is insufficient to pay, the calculated secret shares are not necessarily zero, so UTXO does not reveal the balance of an account.As shown in Figure9, in the case of a coinbase transaction, initial balances can be assigned to each account, and this transaction corresponds to one input and multiple outputs. To_spent in Vin is a pointer to UTXO, and Vout contains the addresses of the output and the secret shares to allocate.Figure 9
Transaction.Vin and Vout are in the form of secret shares rather than specific values.


#### 4.3.3. Log

The log locally recorded by each node consists of the type, timestamp, and secret shares of the balance updated after the transaction. It can be seen from Figure10 that each node will hold many secret shares, which are the balances of different nodes. It should be noted that only the secret shares of balance after the transaction are kept here, and no data related to the transaction value is involved.Figure 10
Log. The local storage of each node involves only secret shares.


#### 4.3.4. UTXO

In a nutshell, updating UTXO is simply by packing theVout of each transaction. As shown in Figure 11, for a verified transaction, the input points to the latest unconsumed secret shares and the output secret shares are packaged as a UTXO unit and added to UTXO_SET. We have given an example of UTXO in Figure 12 to understand the properties of UTXO. It is important to note that since there are multiple outputs from a transaction, it is necessary to specify the output of the transaction when packaging as a UTXO unit.Figure 11
The process of UTXO packing. EachVout is packaged into UTXO_SET to be used as Vin for the next transaction.Figure 12
UTXO. A UTXO item contains a pointer to a transaction and itsVout.


## 4.1. Transaction Process

This section describes in detail the calculations designed during the transaction. By combining Shamir’s secret sharing scheme, it realizes the confidentiality of balance and transaction value on the premise of ensuring the original properties of the blockchain.The payerA and the payee B initiate a transaction to the blockchain. Suppose the balances of the two accounts are TA and TB. The transaction value which A needs to distribute is w1, and the transaction value that B distributes is w2. The execution of a transaction is mainly divided into two stages: (1) verify that the balance is greater than the payment, and (2) verify that the payment is equal to the value received. The transaction process is as follows.


### 4.1.1. Verify That the BalanceTA of A Is Greater Than the Payment w1

The balance ofA and B is stored in the form of secret shares and is expressed as fTAx and fTBx, where(25)fTAx=TA+a1x+a2x2+⋯+at−1xt−1modp,fTBx=TB+a1′x+a2′x2+⋯+at−1′xt−1modp.WhenA trades, A generates a random polynomial and takes w1 as the secret. Then A calculates the secret shares corresponding to each node and distributes them. Similarly, B also generates a random polynomial that distributes the transaction value w2 to other nodes. The random polynomial for w1 and w2 is as follows:(26)fw1x=w1+b1x+b2x2+⋯+bt−1xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp.After the above operation, each node holds the secret shares of the balance ofTA and TB and the transaction value of w1 and w2. We use w1p, w2p, TAp, and TBp to represent simplicity. To compare the size of w1 and TA, we need to use the LSB Protocol using wraparound mentioned earlier. We can calculate w1<p/2p, TA<p/2p, and TA−w1<p/2pmodpp very easily with LSB Protocol using wraparound. Then, we discuss all the cases of w1 and TA using P/2.Case 1.
IfTA<p/2p=1 and w1<p/2p=0, then TA<w1p=1.Case 2.
IfTA<p/2p=0 and w1<p/2p=1, then TA<w1p=0.Case 3.
IfTA<p/2p=0, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 4.
IfTA<p/2p=0, w1<p/2p=0, and TA−w1<p/2p=1, then TA<w1p=1.Case 5.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 6.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=1, then TA<w1p=0.
Whenw1<TAp=1, it means A has enough balance to initiate the transaction.


### 4.1.2. Verify That the Paymentw1 is Equal to the Amount Received w2

When a transaction is initiated, the other parties must verify that the money spent byA is equal to the money received by B. Otherwise, some malicious nodes will use the imbalance to cheat money. For example, the transaction value A that distributes to other nodes is 5 BTC, while the transaction value that distributes by B is 3 BTC. If it is not verified, 2 BTC will be defrauded by malicious nodes.During the transaction,A and B distribute secret shares of w1 and w2 in parallel. We still use w1p and w2p for simplicity. Nodes can easily compute w1−w2p, and if they can verify a=w1−w2=0p, they can achieve their goals. The framework of the whole verification process is very clear. We randomize a by c=a+r firstly. Then, all we have to do is verify that c=r to determine a=0.First, nodes generate a bitwise shared random number byr∈RZpB and get rp=∑i=0i=l−12irip. Then, nodes compute cp=ap+rp and reveal c=a+rmodp. Nodes can easily obtain the binary of c for it is public. Then the parties compute ci′p, which shows if bits of c and r are equal.(27)ci′p=1−ripifci=0.ripifci=1,It is obvious thatci′=1 if ci=ri. Finally, parties obtain a=0p by computing the Unbounded Fan-In And ∧i=0i=l−1ci′p. Through the above steps, nodes can compute w1−w2=0p.After the above two steps, the nodes hold the secret shares ofw1−w2=0p and w1<TAp. As long as any t nodes send the secret shares to the current leader, the result can be revealed. If the verification result is true, each node calculates TA−wp and TB+wp locally, and the transaction is written to the blockchain. If the verification result is false, the transaction is ruled illegal.


## 4.1.1. Verify That the BalanceTA of A Is Greater Than the Payment w1

The balance ofA and B is stored in the form of secret shares and is expressed as fTAx and fTBx, where(25)fTAx=TA+a1x+a2x2+⋯+at−1xt−1modp,fTBx=TB+a1′x+a2′x2+⋯+at−1′xt−1modp.WhenA trades, A generates a random polynomial and takes w1 as the secret. Then A calculates the secret shares corresponding to each node and distributes them. Similarly, B also generates a random polynomial that distributes the transaction value w2 to other nodes. The random polynomial for w1 and w2 is as follows:(26)fw1x=w1+b1x+b2x2+⋯+bt−1xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp,fw2x=w2+b1′x+b2′x2+⋯+bt−1′xt−1modp.After the above operation, each node holds the secret shares of the balance ofTA and TB and the transaction value of w1 and w2. We use w1p, w2p, TAp, and TBp to represent simplicity. To compare the size of w1 and TA, we need to use the LSB Protocol using wraparound mentioned earlier. We can calculate w1<p/2p, TA<p/2p, and TA−w1<p/2pmodpp very easily with LSB Protocol using wraparound. Then, we discuss all the cases of w1 and TA using P/2.Case 1.
IfTA<p/2p=1 and w1<p/2p=0, then TA<w1p=1.Case 2.
IfTA<p/2p=0 and w1<p/2p=1, then TA<w1p=0.Case 3.
IfTA<p/2p=0, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 4.
IfTA<p/2p=0, w1<p/2p=0, and TA−w1<p/2p=1, then TA<w1p=1.Case 5.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=0, then TA<w1p=1.Case 6.
IfTA<p/2p=1, w1<p/2p=1, and TA−w1<p/2p=1, then TA<w1p=0.
Whenw1<TAp=1, it means A has enough balance to initiate the transaction.


## 4.1.2. Verify That the Paymentw1 is Equal to the Amount Received w2

When a transaction is initiated, the other parties must verify that the money spent byA is equal to the money received by B. Otherwise, some malicious nodes will use the imbalance to cheat money. For example, the transaction value A that distributes to other nodes is 5 BTC, while the transaction value that distributes by B is 3 BTC. If it is not verified, 2 BTC will be defrauded by malicious nodes.During the transaction,A and B distribute secret shares of w1 and w2 in parallel. We still use w1p and w2p for simplicity. Nodes can easily compute w1−w2p, and if they can verify a=w1−w2=0p, they can achieve their goals. The framework of the whole verification process is very clear. We randomize a by c=a+r firstly. Then, all we have to do is verify that c=r to determine a=0.First, nodes generate a bitwise shared random number byr∈RZpB and get rp=∑i=0i=l−12irip. Then, nodes compute cp=ap+rp and reveal c=a+rmodp. Nodes can easily obtain the binary of c for it is public. Then the parties compute ci′p, which shows if bits of c and r are equal.(27)ci′p=1−ripifci=0.ripifci=1,It is obvious thatci′=1 if ci=ri. Finally, parties obtain a=0p by computing the Unbounded Fan-In And ∧i=0i=l−1ci′p. Through the above steps, nodes can compute w1−w2=0p.After the above two steps, the nodes hold the secret shares ofw1−w2=0p and w1<TAp. As long as any t nodes send the secret shares to the current leader, the result can be revealed. If the verification result is true, each node calculates TA−wp and TB+wp locally, and the transaction is written to the blockchain. If the verification result is false, the transaction is ruled illegal.


## 4.2. Changes of Secret Shares

As we described earlier, each node stores secret shares of the balance of the other nodes. The secret shares held by each node before trading are shown on the left side of Figure7, and it is easy to see that the secret shares obtained by different nodes are different values of x calculated by the different random polynomials. After verifying the transaction, thanks to the properties of secret shares, each node can add and subtract the secret shares of the balance of A and B with the secret shares of the transaction value directly.Figure 7
The change of the secret shares. In the secret shares kept by each node, only the shares related to the transaction node will change.


## 4.3. The Data Structure

In this section, we will describe the major data structures and the main properties, including the basic unitTransaction, the Block on which transactions are recorded, the Log held locally by the nodes, and the UTXO. We still use the block structure, but unlike the public chain, we simply keep transactions on the logical chain, and there is no amount of money involved. The local log records secret shares of each node’s balance that is constantly updated. We made a slight change to the UTXO structure in Bitcoin, so instead of holding unspent Bitcoin, it is the shares of the node’s most recent balance.


### 4.3.1. Block

Similar to the Bitcoin system, blocks are divided into head and body. The specific composition of the block is shown in Figure8. However, because of the different consensus algorithms, we do not need proof of work for mining, so there are no random numbers in the block header for proof of work. It simply contains the header of the previous block, the Merkle tree hash of the current block, and the timestamp.Figure 8
Block. Blocks do not contain difficulty values required for mining.


### 4.3.2. Transaction

The transaction is the basic unit that makes up the block, and it consists of two main parts:Vin and Vout. Vin represents the input to the transaction, which points to the most recent unspent shares of the balance in UTXO. It is important to note that UTXO here holds the shares of the balance. Even if the balance of an account is insufficient to pay, the calculated secret shares are not necessarily zero, so UTXO does not reveal the balance of an account.As shown in Figure9, in the case of a coinbase transaction, initial balances can be assigned to each account, and this transaction corresponds to one input and multiple outputs. To_spent in Vin is a pointer to UTXO, and Vout contains the addresses of the output and the secret shares to allocate.Figure 9
Transaction.Vin and Vout are in the form of secret shares rather than specific values.


### 4.3.3. Log

The log locally recorded by each node consists of the type, timestamp, and secret shares of the balance updated after the transaction. It can be seen from Figure10 that each node will hold many secret shares, which are the balances of different nodes. It should be noted that only the secret shares of balance after the transaction are kept here, and no data related to the transaction value is involved.Figure 10
Log. The local storage of each node involves only secret shares.


### 4.3.4. UTXO

In a nutshell, updating UTXO is simply by packing theVout of each transaction. As shown in Figure 11, for a verified transaction, the input points to the latest unconsumed secret shares and the output secret shares are packaged as a UTXO unit and added to UTXO_SET. We have given an example of UTXO in Figure 12 to understand the properties of UTXO. It is important to note that since there are multiple outputs from a transaction, it is necessary to specify the output of the transaction when packaging as a UTXO unit.Figure 11
The process of UTXO packing. EachVout is packaged into UTXO_SET to be used as Vin for the next transaction.Figure 12
UTXO. A UTXO item contains a pointer to a transaction and itsVout.


## 4.3.1. Block

Similar to the Bitcoin system, blocks are divided into head and body. The specific composition of the block is shown in Figure8. However, because of the different consensus algorithms, we do not need proof of work for mining, so there are no random numbers in the block header for proof of work. It simply contains the header of the previous block, the Merkle tree hash of the current block, and the timestamp.Figure 8
Block. Blocks do not contain difficulty values required for mining.


## 4.3.2. Transaction

The transaction is the basic unit that makes up the block, and it consists of two main parts:Vin and Vout. Vin represents the input to the transaction, which points to the most recent unspent shares of the balance in UTXO. It is important to note that UTXO here holds the shares of the balance. Even if the balance of an account is insufficient to pay, the calculated secret shares are not necessarily zero, so UTXO does not reveal the balance of an account.As shown in Figure9, in the case of a coinbase transaction, initial balances can be assigned to each account, and this transaction corresponds to one input and multiple outputs. To_spent in Vin is a pointer to UTXO, and Vout contains the addresses of the output and the secret shares to allocate.Figure 9
Transaction.Vin and Vout are in the form of secret shares rather than specific values.


## 4.3.3. Log

The log locally recorded by each node consists of the type, timestamp, and secret shares of the balance updated after the transaction. It can be seen from Figure10 that each node will hold many secret shares, which are the balances of different nodes. It should be noted that only the secret shares of balance after the transaction are kept here, and no data related to the transaction value is involved.Figure 10
Log. The local storage of each node involves only secret shares.


## 4.3.4. UTXO

In a nutshell, updating UTXO is simply by packing theVout of each transaction. As shown in Figure 11, for a verified transaction, the input points to the latest unconsumed secret shares and the output secret shares are packaged as a UTXO unit and added to UTXO_SET. We have given an example of UTXO in Figure 12 to understand the properties of UTXO. It is important to note that since there are multiple outputs from a transaction, it is necessary to specify the output of the transaction when packaging as a UTXO unit.Figure 11
The process of UTXO packing. EachVout is packaged into UTXO_SET to be used as Vin for the next transaction.Figure 12
UTXO. A UTXO item contains a pointer to a transaction and itsVout.


## 5. Attack Model

In the attack model of our scheme, we assume that each node is semihonest. That is, each node will correctly execute the protocol, but it may be monitored by malicious attackers to obtain its input, output, and the information obtained in the protocol operation process. The attack model in our scheme contains the following assumptions:(1)
A malicious attacker can collect the secret shares (less thant) during the protocol execution of each node and try to recover its plaintext. According to Lagrange interpolation, the protocol is unconditionally secure when the attacker cannot collect more than t secret shares.(2)
An attacker can take some nodes offline to prevent them from participating in the resulting recovery of protocol execution. Due to the threshold nature of our scheme itself, even if some nodes cannot participate in decryption, when there aret nodes online, the smooth implementation of the protocol can be realized.(3)
An attacker can collect secret shares and try to gain any information about balance and trading value. Since balance and transaction value are distributed in the form of shares in the whole process, even when the nodes call the Comparison Protocol, they only share the truth value of the comparison result, so as long as the attacker collects less thant shares, the attack will be invalid.


## 6. Analysis

### 6.1. Performance Analysis

The complexity of our scheme mainly contains two aspects: (1) communication complexity of making consensus on the blockchain; (2) computational complexity when validating transactions. In the second case, we can see that verifying a transaction requires a Comparison Protocol and Equality Test Protocol. The two protocols are composed of several subprotocols, and the most complicated part is calculatingap×bp. We continue to use the same method of expressing complexity as in [13], thinking of ap×bp as an invocation. So the Comparison Protocol would require 15 rounds of interactions and 279l+5 (l is the bit length of the prime p) invocations, and the Equality Test Protocol requires 8 rounds and 81l invocations.We work on a 6 Core AMD Machine with 3600 3.9 GHz CPUs and 16 GB of RAM, running on 64-bit Windows 10. The number of nodes in the blockchain is 11, and according to the two aspects of complexity, we give two figures of experimental results to describe intuitively; Figures13 and 14 show the changes of rounds and the time of making consensus as the transaction increases, respectively. The number of interaction rounds is related to the number of transactions, and the rounds required for each transaction are reduced due to our optimization of multiplication. To simulate congestion in the real world, we set the client to sleep (2) for each round of messages sent. It can be seen from the experimental results that the time efficiency of reaching consensus is relatively high.Figure 13
Changes in the number of interactive rounds. As the number of rounds in the multiplication is reduced, the change is linear.Figure 14
Change of consensus time. To prevent information loss, the interval for sending information is controlled as sleep (2).For the consensus protocol without privacy protection, allocating secret shares for calculation will increase the storage of the node, but according to the privacy needs of the transaction, the increased storage is worthwhile. The comparison of the storage of our scheme with that of the nonprivacy scheme is shown in Figure15.Figure 15
Storage comparison. As the value is divided into multiple secret shares, the storage cost of nodes increases.Since we proposed the noninteractive multiplication, the communication cost of a single node also decreased significantly. For the interactive multiplication, the nodes need to multiply the shares received and distribute them again, resulting in the fact that the communication volume of a single node is2log2p+nlog2p; however, noninteractive multiplication reduces this to 2log2p.


### 6.2. Security Analysis

To formally analyse the security of multiparty computing protocols, Golderich et al. [27] introduced a realistic/ideal model security analysis method. The multiparty computational cryptographic protocol is secure if the view obtained by the PPT adversary attacking the actual protocol is indistinguishable from the view obtained by attacking the ideal model. In the ideal model, there is a trusted third party trusted by all participants. Participants do not interact directly with each other but interact with the trusted third party. The trusted third party calculates the ideal function using the input of participants and returns the results to participants. In the ideal model, the protocol is a security protocol, and the effect of the adversary attacking the ideal model is negligible. If an adversary cannot distinguish whether its attack is against the ideal model or the real model, it means that the effect of attacking the actual protocol is also negligible, so the protocol is secure.When security analysis is considered, it is usually for a single protocol in a specific environment, but the actual cryptographic protocols are often executed concurrently or in combination with each other. The external environment of protocol execution can be summarized as an independent model, concurrent model, general combinable model, and so on. Canetti proposed the UC framework [28]. The biggest feature of security in the UC framework is that a secure protocol is still secure when it is combined with any other protocol or as a component of a larger protocol.UC framework also applies the ideal/reality model, and the difference is that the UC framework analyses protocol security from the perspective of the environment.The framework abstracts the ideal protocolπ into a secure ideal function ℱ. The ideal world and the real world are in the same environment Z. Participants and attackers in the ideal world interact with the ideal function ℱ, and they cannot communicate directly with each other. The ideal function ℱ is essentially an unassailable trusted third party.Definition 1.
When any real adversaryA has a simulated adversary S in the ideal world, the probability that environment Z can distinguish between the real adversary A interacting with protocol π and the simulated adversary S interacting with the ideal function ℱ is negligible, and the protocol π is said to securely implement the ideal function ℱ.Theorem 1.
If the protocolρ securely implements the ideal function ℱ, π is the protocol under hybrid model ℱ− . Then, the combined protocol πρ/f replacing the ideal function ℱ in protocol π with protocol ρ is also UC security.
Our protocolπ is mainly composed of πequality, πcomparison, and πaddition. To prove that the protocol π is secure for UC, it is necessary to prove that πequality, πcomparison, and πaddition are secure for UC. That is, the three protocols securely implement the ideal functions ℱequality,ℱcomprison, and ℱaddition, respectively, and then prove that π is secure for UC under ℱequalityℱcomprisonℱaddition-hybrid model.


#### 6.2.1. Security Analysis ofπequality

Inπequality, each participant pi holds secret shares faIDi and fbIDi of secrets a and b. Participants calculate the secret shares of Boolean results fa=bIDi by the protocol to estimate whether a and b are equal and do not expose the comparison results of a and b. In the protocol, Unbounded Fan-In And is called πand. We first proved the security of πand.Claim 1.
The Unbounded Fan-In And protocol is hybrid-model security when the adversary corrupts no more thant participants.
We describe the ideal function ofπand as follows.


#### 6.2.2. Ideal Functionℱand

n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,al−1p,…,a0p from participant pi, it computes Ap=al−1p+⋯+a0p+1, uses Lagrange interpolation to determine a polynomial flx of order l which is satisfying fl2k=0,fl2k+1=1,k=0,1,2…, and sends Ap to participants.(2)
When it receivescompute,sid,pi,clp,…,c1p,bjp from participant pi, it first recovers c1,…,cl using Lagrange interpolation and then computes Ajp=∏k=1jckbjp. It substitutes Ajp,j∈1,l into flx to calculate flAp. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using Lagrange interpolation using y2i of all participants marked with corrupted. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, when the participantpi receives Ap in the interaction with the ideal function, it will interact with the environment machine Z, which needs to simulate inverse and multiplication protocols to calculate clp,…,c1p and generate bjp for the participant. From the definition of the UC framework, we know that this process is ideal and secure. Next, we prove the security of πAnd from the view of environment machine Z.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱand, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define Event. When n≤t, the value of y2i received from the ideal function ℱand is a bit 0 or 1, which is the recovered value of and.
According to Lemma1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Theorem 2.
When the adversaryA corrupts no more than t participants, the protocol πequality securely implements the ideal function ℱequality under the ℱand-hybrid model.The ideal function ofπequality is as follows:Ideal functionℱequality.n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,ap,bp,r∈RZpB,rp from participant pi, then it computes xp=ap−bp and cp=xp+rp. After receiving input from at least t participants, using the Lagrange interpolation to recover c, and calculating the bit form of cl−1,…,c0 and cj′p=rjpifrj=11−rjpifrj=0,j=0,1,2..., then it sends cj′p to participants.(2)
When it receivesinput,sid,pi,flAp from participant pi, the two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi, first it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi, y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send the y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, the participantpi first interacts with the environment machine Z to obtain r∈RZpB,rp, and when receiving cj′p from the ideal function, ℱequality, it interacts with the ideal function ℱand to compute the secret shares of and.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱequality, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value of y2i received from the ideal function ℱequality is a bit 0 or 1, which is the recovered value of and. According to Lemma 1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Define event 2: forinput,sid,pi,flAp where flAp is exactly equal to flA, when the adversary corrupts no more than t participants, according to Claim 1, the event cannot occur. So the two worlds are indistinguishable. Theorem 2 is proved.
(2) Security Analysis ofπcomparison. In πcomparison, each participant pi holds secret shares faIDi and fbIDi of a and b. The participants calculate the secret shares of the comparison result fa<bIDi and do not expose a and b themselves. a<p/2p, b<p/2p, and a−bmodp<p/2p are computed by calling the LSB Protocol, so we need to prove the security of πLSB.Claim 2.
The LSB Protocol is hybrid-model security when no more thant participants are corrupted.
To prove the above claim, we first describe the behavior of adversary, environment machines in the ideal world of the UC framework, and the ideal function of the LSB Protocol. Since the environment machineZ is used to simulate the external environment of protocol operation, we assume that the environment machine Z simulates the Joint Random Number Bitwise Sharing, Bitwise Less-Than, and noninteractive multiplication protocol that need to be called in the LSB Protocol.
The participants can communicate with the environment machineZ, and its specific behavior is as follows:Environment machineZ:(1)
Initialization phase: simulate Joint Random Number Bitwise Sharing to generater∈RZpB and rp for each participant pi.(2)
Interaction phase: when the inputcompute,sid,c,cp,c0⊕r0p is received from the participant pi, simulates the Bitwise Less-Than to produce an output c<Brp, and simulates the noninteractive multiplication protocol to produce an output 2c<Brp×c0⊕r0p, then send c<Brp,2c<Brp×c0⊕r0p to pi.
The behavior of the participantpi is described as follows:Participantpi:(1)
When the outputsr∈RZpB and rp are received from the environment machine Z, input,sid,pi,xp,r∈RZpB,rp is sent to the ideal function ℱLSB.(2)
When the outputc,cp,c0⊕r0p is received from the ideal function ℱLSB, compute,sid,c,cp,c0⊕r0p is sent to the environment machine Z.(3)
When the outputc<Brp,2c<Brp×c0⊕r0p is received from the environment machine Z, compute,sid,pi,c<Brp,2c<Brp×c0⊕r0p is sent to the ideal function ℱLSB.(4)
Send the outputoutput,sid,pi to the ideal function ℱLSB.
The ideal functionℱLSB is described as follows:Ideal functionℱLSB:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,xp,r∈RZpB,rp from the participant pi, it computes cp=xp+rp, and when it receives inputs from at least t participants, it recovers c using Lagrange interpolation and sends c,cp,c0⊕r0p to the participants.(2)
When it receivescompute,sid,pi,c<Brp,2c<Brp×c0⊕r0p from participant pi, compute x0p=c<Brp+c0⊕r0p−2c<Brp×c0⊕r0p. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=x0p.(3)
When it receives a requestoutput,sid,pi from participant pi, first, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and x0 is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=x0 of all corrupted participants and send y2i and x0 of the current participant to S; otherwise, only y2i of the current participant is sent.
The proof for Claim2 is similar to Claim 1.
The computation steps exceptπLSB in πcomparison are noninteractive; participants can complete them locally without any communications, so there is no adversary attack, and it is as secure as πLSB.
(3) Security Analysis ofπadditoin. Since πaddition itself is noninteractive, participants can complete without any communication in the local, and there is no adversary attack, so the protocol πaddition is unconditional security.
(4) Security Analysis of Our Scheme.Ideal functionℱ:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputsinput,sid,A,wA,Ta and input,sid,B,wb,Tb from transaction nodes A and B, it generates secret shares wAp,wBp,TAp,TBp for all nodes pi participating in the verification and sends corresponding secret shares to participants.(2)
When it receivesinput,sid,pi,wA=wBp,TA<wBp from participants pi with more than t, it uses Lagrange interpolation to recover the values of wA=wB and TA<wB. If TA<wB=0 and wA=wB=1, the values of wA=wB and TA<wB are sent to the leader, and the corresponding secret shares of each participant are used to calculate TA−wBp and TB+wAp, respectively. Otherwise, the values of wA=wB and TA<wB are sent to the leader, and the protocol process is terminated. Let yi=TA−wBp,TB+wAp, and xi is the set of all inputs for pi.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns yi; if so, it sets n+=1. If n>t, then it produces a delayed output yi to pi. When it receives corrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi is sent to S.(4)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted. TA−wB,TB+wA are recovered using yi of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let yi=TA−wB,TB+wA of all corrupted participants and send TA−wB,TB+wA to S; otherwise, only yi of the current participant is sent.Theorem 3.
Our protocolπ securely implements ideal function ℱ under ℱequality,ℱcomprison,ℱaddition-hybrid model.In an ideal world, the participantpi first interacts with ℱequality using wAp,wBp, gets its output as the value of wA=wBp, and interacts with ℱcomparison using wB,Ta to get its output as the value of TA<wBp.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,yi belonging to pi are received from ideal function ℱ, the simulated adversary gets xi,yi.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,yi to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value TA−wB,TB+wA can be received from the ideal function ℱ. According to Lemma 1, the event is impossible to occur.Define event 2: forinput,sid,pi,TA<wBp where the value of wA=wBp or TA<wBp is exactly a definite bit 0 or 1, when the adversary corrupts no more than t participants, according to Claim 1 and Claim 2, the event cannot occur. So the two worlds are indistinguishable. Theorem 3 is proved.


## 6.1. Performance Analysis

The complexity of our scheme mainly contains two aspects: (1) communication complexity of making consensus on the blockchain; (2) computational complexity when validating transactions. In the second case, we can see that verifying a transaction requires a Comparison Protocol and Equality Test Protocol. The two protocols are composed of several subprotocols, and the most complicated part is calculatingap×bp. We continue to use the same method of expressing complexity as in [13], thinking of ap×bp as an invocation. So the Comparison Protocol would require 15 rounds of interactions and 279l+5 (l is the bit length of the prime p) invocations, and the Equality Test Protocol requires 8 rounds and 81l invocations.We work on a 6 Core AMD Machine with 3600 3.9 GHz CPUs and 16 GB of RAM, running on 64-bit Windows 10. The number of nodes in the blockchain is 11, and according to the two aspects of complexity, we give two figures of experimental results to describe intuitively; Figures13 and 14 show the changes of rounds and the time of making consensus as the transaction increases, respectively. The number of interaction rounds is related to the number of transactions, and the rounds required for each transaction are reduced due to our optimization of multiplication. To simulate congestion in the real world, we set the client to sleep (2) for each round of messages sent. It can be seen from the experimental results that the time efficiency of reaching consensus is relatively high.Figure 13
Changes in the number of interactive rounds. As the number of rounds in the multiplication is reduced, the change is linear.Figure 14
Change of consensus time. To prevent information loss, the interval for sending information is controlled as sleep (2).For the consensus protocol without privacy protection, allocating secret shares for calculation will increase the storage of the node, but according to the privacy needs of the transaction, the increased storage is worthwhile. The comparison of the storage of our scheme with that of the nonprivacy scheme is shown in Figure15.Figure 15
Storage comparison. As the value is divided into multiple secret shares, the storage cost of nodes increases.Since we proposed the noninteractive multiplication, the communication cost of a single node also decreased significantly. For the interactive multiplication, the nodes need to multiply the shares received and distribute them again, resulting in the fact that the communication volume of a single node is2log2p+nlog2p; however, noninteractive multiplication reduces this to 2log2p.


## 6.2. Security Analysis

To formally analyse the security of multiparty computing protocols, Golderich et al. [27] introduced a realistic/ideal model security analysis method. The multiparty computational cryptographic protocol is secure if the view obtained by the PPT adversary attacking the actual protocol is indistinguishable from the view obtained by attacking the ideal model. In the ideal model, there is a trusted third party trusted by all participants. Participants do not interact directly with each other but interact with the trusted third party. The trusted third party calculates the ideal function using the input of participants and returns the results to participants. In the ideal model, the protocol is a security protocol, and the effect of the adversary attacking the ideal model is negligible. If an adversary cannot distinguish whether its attack is against the ideal model or the real model, it means that the effect of attacking the actual protocol is also negligible, so the protocol is secure.When security analysis is considered, it is usually for a single protocol in a specific environment, but the actual cryptographic protocols are often executed concurrently or in combination with each other. The external environment of protocol execution can be summarized as an independent model, concurrent model, general combinable model, and so on. Canetti proposed the UC framework [28]. The biggest feature of security in the UC framework is that a secure protocol is still secure when it is combined with any other protocol or as a component of a larger protocol.UC framework also applies the ideal/reality model, and the difference is that the UC framework analyses protocol security from the perspective of the environment.The framework abstracts the ideal protocolπ into a secure ideal function ℱ. The ideal world and the real world are in the same environment Z. Participants and attackers in the ideal world interact with the ideal function ℱ, and they cannot communicate directly with each other. The ideal function ℱ is essentially an unassailable trusted third party.Definition 1.
When any real adversaryA has a simulated adversary S in the ideal world, the probability that environment Z can distinguish between the real adversary A interacting with protocol π and the simulated adversary S interacting with the ideal function ℱ is negligible, and the protocol π is said to securely implement the ideal function ℱ.Theorem 1.
If the protocolρ securely implements the ideal function ℱ, π is the protocol under hybrid model ℱ− . Then, the combined protocol πρ/f replacing the ideal function ℱ in protocol π with protocol ρ is also UC security.
Our protocolπ is mainly composed of πequality, πcomparison, and πaddition. To prove that the protocol π is secure for UC, it is necessary to prove that πequality, πcomparison, and πaddition are secure for UC. That is, the three protocols securely implement the ideal functions ℱequality,ℱcomprison, and ℱaddition, respectively, and then prove that π is secure for UC under ℱequalityℱcomprisonℱaddition-hybrid model.


### 6.2.1. Security Analysis ofπequality

Inπequality, each participant pi holds secret shares faIDi and fbIDi of secrets a and b. Participants calculate the secret shares of Boolean results fa=bIDi by the protocol to estimate whether a and b are equal and do not expose the comparison results of a and b. In the protocol, Unbounded Fan-In And is called πand. We first proved the security of πand.Claim 1.
The Unbounded Fan-In And protocol is hybrid-model security when the adversary corrupts no more thant participants.
We describe the ideal function ofπand as follows.


### 6.2.2. Ideal Functionℱand

n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,al−1p,…,a0p from participant pi, it computes Ap=al−1p+⋯+a0p+1, uses Lagrange interpolation to determine a polynomial flx of order l which is satisfying fl2k=0,fl2k+1=1,k=0,1,2…, and sends Ap to participants.(2)
When it receivescompute,sid,pi,clp,…,c1p,bjp from participant pi, it first recovers c1,…,cl using Lagrange interpolation and then computes Ajp=∏k=1jckbjp. It substitutes Ajp,j∈1,l into flx to calculate flAp. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using Lagrange interpolation using y2i of all participants marked with corrupted. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, when the participantpi receives Ap in the interaction with the ideal function, it will interact with the environment machine Z, which needs to simulate inverse and multiplication protocols to calculate clp,…,c1p and generate bjp for the participant. From the definition of the UC framework, we know that this process is ideal and secure. Next, we prove the security of πAnd from the view of environment machine Z.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱand, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define Event. When n≤t, the value of y2i received from the ideal function ℱand is a bit 0 or 1, which is the recovered value of and.
According to Lemma1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Theorem 2.
When the adversaryA corrupts no more than t participants, the protocol πequality securely implements the ideal function ℱequality under the ℱand-hybrid model.The ideal function ofπequality is as follows:Ideal functionℱequality.n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,ap,bp,r∈RZpB,rp from participant pi, then it computes xp=ap−bp and cp=xp+rp. After receiving input from at least t participants, using the Lagrange interpolation to recover c, and calculating the bit form of cl−1,…,c0 and cj′p=rjpifrj=11−rjpifrj=0,j=0,1,2..., then it sends cj′p to participants.(2)
When it receivesinput,sid,pi,flAp from participant pi, the two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi, first it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi, y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send the y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, the participantpi first interacts with the environment machine Z to obtain r∈RZpB,rp, and when receiving cj′p from the ideal function, ℱequality, it interacts with the ideal function ℱand to compute the secret shares of and.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱequality, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value of y2i received from the ideal function ℱequality is a bit 0 or 1, which is the recovered value of and. According to Lemma 1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Define event 2: forinput,sid,pi,flAp where flAp is exactly equal to flA, when the adversary corrupts no more than t participants, according to Claim 1, the event cannot occur. So the two worlds are indistinguishable. Theorem 2 is proved.
(2) Security Analysis ofπcomparison. In πcomparison, each participant pi holds secret shares faIDi and fbIDi of a and b. The participants calculate the secret shares of the comparison result fa<bIDi and do not expose a and b themselves. a<p/2p, b<p/2p, and a−bmodp<p/2p are computed by calling the LSB Protocol, so we need to prove the security of πLSB.Claim 2.
The LSB Protocol is hybrid-model security when no more thant participants are corrupted.
To prove the above claim, we first describe the behavior of adversary, environment machines in the ideal world of the UC framework, and the ideal function of the LSB Protocol. Since the environment machineZ is used to simulate the external environment of protocol operation, we assume that the environment machine Z simulates the Joint Random Number Bitwise Sharing, Bitwise Less-Than, and noninteractive multiplication protocol that need to be called in the LSB Protocol.
The participants can communicate with the environment machineZ, and its specific behavior is as follows:Environment machineZ:(1)
Initialization phase: simulate Joint Random Number Bitwise Sharing to generater∈RZpB and rp for each participant pi.(2)
Interaction phase: when the inputcompute,sid,c,cp,c0⊕r0p is received from the participant pi, simulates the Bitwise Less-Than to produce an output c<Brp, and simulates the noninteractive multiplication protocol to produce an output 2c<Brp×c0⊕r0p, then send c<Brp,2c<Brp×c0⊕r0p to pi.
The behavior of the participantpi is described as follows:Participantpi:(1)
When the outputsr∈RZpB and rp are received from the environment machine Z, input,sid,pi,xp,r∈RZpB,rp is sent to the ideal function ℱLSB.(2)
When the outputc,cp,c0⊕r0p is received from the ideal function ℱLSB, compute,sid,c,cp,c0⊕r0p is sent to the environment machine Z.(3)
When the outputc<Brp,2c<Brp×c0⊕r0p is received from the environment machine Z, compute,sid,pi,c<Brp,2c<Brp×c0⊕r0p is sent to the ideal function ℱLSB.(4)
Send the outputoutput,sid,pi to the ideal function ℱLSB.
The ideal functionℱLSB is described as follows:Ideal functionℱLSB:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,xp,r∈RZpB,rp from the participant pi, it computes cp=xp+rp, and when it receives inputs from at least t participants, it recovers c using Lagrange interpolation and sends c,cp,c0⊕r0p to the participants.(2)
When it receivescompute,sid,pi,c<Brp,2c<Brp×c0⊕r0p from participant pi, compute x0p=c<Brp+c0⊕r0p−2c<Brp×c0⊕r0p. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=x0p.(3)
When it receives a requestoutput,sid,pi from participant pi, first, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and x0 is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=x0 of all corrupted participants and send y2i and x0 of the current participant to S; otherwise, only y2i of the current participant is sent.
The proof for Claim2 is similar to Claim 1.
The computation steps exceptπLSB in πcomparison are noninteractive; participants can complete them locally without any communications, so there is no adversary attack, and it is as secure as πLSB.
(3) Security Analysis ofπadditoin. Since πaddition itself is noninteractive, participants can complete without any communication in the local, and there is no adversary attack, so the protocol πaddition is unconditional security.
(4) Security Analysis of Our Scheme.Ideal functionℱ:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputsinput,sid,A,wA,Ta and input,sid,B,wb,Tb from transaction nodes A and B, it generates secret shares wAp,wBp,TAp,TBp for all nodes pi participating in the verification and sends corresponding secret shares to participants.(2)
When it receivesinput,sid,pi,wA=wBp,TA<wBp from participants pi with more than t, it uses Lagrange interpolation to recover the values of wA=wB and TA<wB. If TA<wB=0 and wA=wB=1, the values of wA=wB and TA<wB are sent to the leader, and the corresponding secret shares of each participant are used to calculate TA−wBp and TB+wAp, respectively. Otherwise, the values of wA=wB and TA<wB are sent to the leader, and the protocol process is terminated. Let yi=TA−wBp,TB+wAp, and xi is the set of all inputs for pi.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns yi; if so, it sets n+=1. If n>t, then it produces a delayed output yi to pi. When it receives corrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi is sent to S.(4)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted. TA−wB,TB+wA are recovered using yi of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let yi=TA−wB,TB+wA of all corrupted participants and send TA−wB,TB+wA to S; otherwise, only yi of the current participant is sent.Theorem 3.
Our protocolπ securely implements ideal function ℱ under ℱequality,ℱcomprison,ℱaddition-hybrid model.In an ideal world, the participantpi first interacts with ℱequality using wAp,wBp, gets its output as the value of wA=wBp, and interacts with ℱcomparison using wB,Ta to get its output as the value of TA<wBp.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,yi belonging to pi are received from ideal function ℱ, the simulated adversary gets xi,yi.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,yi to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value TA−wB,TB+wA can be received from the ideal function ℱ. According to Lemma 1, the event is impossible to occur.Define event 2: forinput,sid,pi,TA<wBp where the value of wA=wBp or TA<wBp is exactly a definite bit 0 or 1, when the adversary corrupts no more than t participants, according to Claim 1 and Claim 2, the event cannot occur. So the two worlds are indistinguishable. Theorem 3 is proved.


## 6.2.1. Security Analysis ofπequality

Inπequality, each participant pi holds secret shares faIDi and fbIDi of secrets a and b. Participants calculate the secret shares of Boolean results fa=bIDi by the protocol to estimate whether a and b are equal and do not expose the comparison results of a and b. In the protocol, Unbounded Fan-In And is called πand. We first proved the security of πand.Claim 1.
The Unbounded Fan-In And protocol is hybrid-model security when the adversary corrupts no more thant participants.
We describe the ideal function ofπand as follows.


## 6.2.2. Ideal Functionℱand

n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,al−1p,…,a0p from participant pi, it computes Ap=al−1p+⋯+a0p+1, uses Lagrange interpolation to determine a polynomial flx of order l which is satisfying fl2k=0,fl2k+1=1,k=0,1,2…, and sends Ap to participants.(2)
When it receivescompute,sid,pi,clp,…,c1p,bjp from participant pi, it first recovers c1,…,cl using Lagrange interpolation and then computes Ajp=∏k=1jckbjp. It substitutes Ajp,j∈1,l into flx to calculate flAp. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using Lagrange interpolation using y2i of all participants marked with corrupted. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, when the participantpi receives Ap in the interaction with the ideal function, it will interact with the environment machine Z, which needs to simulate inverse and multiplication protocols to calculate clp,…,c1p and generate bjp for the participant. From the definition of the UC framework, we know that this process is ideal and secure. Next, we prove the security of πAnd from the view of environment machine Z.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱand, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define Event. When n≤t, the value of y2i received from the ideal function ℱand is a bit 0 or 1, which is the recovered value of and.
According to Lemma1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Theorem 2.
When the adversaryA corrupts no more than t participants, the protocol πequality securely implements the ideal function ℱequality under the ℱand-hybrid model.The ideal function ofπequality is as follows:Ideal functionℱequality.n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,ap,bp,r∈RZpB,rp from participant pi, then it computes xp=ap−bp and cp=xp+rp. After receiving input from at least t participants, using the Lagrange interpolation to recover c, and calculating the bit form of cl−1,…,c0 and cj′p=rjpifrj=11−rjpifrj=0,j=0,1,2..., then it sends cj′p to participants.(2)
When it receivesinput,sid,pi,flAp from participant pi, the two inputs of pi are written as xi, and the output in (1) is y1i, y2i=flAp.(3)
When it receives a requestoutput,sid,pi from participant pi, first it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi, y1i are sent to S.(5)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted, and flA is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=flA of all corrupted participants and send the y2i and flA of the current participant to S; otherwise, only y2i of the current participant is sent.In an ideal world, the participantpi first interacts with the environment machine Z to obtain r∈RZpB,rp, and when receiving cj′p from the ideal function, ℱequality, it interacts with the ideal function ℱand to compute the secret shares of and.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,y1i,y2i belonging to pi are received from the ideal function ℱequality, the simulated adversary gets xi,y1i,y2i.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,y1i,y2i to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value of y2i received from the ideal function ℱequality is a bit 0 or 1, which is the recovered value of and. According to Lemma 1, the event is impossible to occur. So the two worlds are indistinguishable. Claim 1 is proved.Define event 2: forinput,sid,pi,flAp where flAp is exactly equal to flA, when the adversary corrupts no more than t participants, according to Claim 1, the event cannot occur. So the two worlds are indistinguishable. Theorem 2 is proved.
(2) Security Analysis ofπcomparison. In πcomparison, each participant pi holds secret shares faIDi and fbIDi of a and b. The participants calculate the secret shares of the comparison result fa<bIDi and do not expose a and b themselves. a<p/2p, b<p/2p, and a−bmodp<p/2p are computed by calling the LSB Protocol, so we need to prove the security of πLSB.Claim 2.
The LSB Protocol is hybrid-model security when no more thant participants are corrupted.
To prove the above claim, we first describe the behavior of adversary, environment machines in the ideal world of the UC framework, and the ideal function of the LSB Protocol. Since the environment machineZ is used to simulate the external environment of protocol operation, we assume that the environment machine Z simulates the Joint Random Number Bitwise Sharing, Bitwise Less-Than, and noninteractive multiplication protocol that need to be called in the LSB Protocol.
The participants can communicate with the environment machineZ, and its specific behavior is as follows:Environment machineZ:(1)
Initialization phase: simulate Joint Random Number Bitwise Sharing to generater∈RZpB and rp for each participant pi.(2)
Interaction phase: when the inputcompute,sid,c,cp,c0⊕r0p is received from the participant pi, simulates the Bitwise Less-Than to produce an output c<Brp, and simulates the noninteractive multiplication protocol to produce an output 2c<Brp×c0⊕r0p, then send c<Brp,2c<Brp×c0⊕r0p to pi.
The behavior of the participantpi is described as follows:Participantpi:(1)
When the outputsr∈RZpB and rp are received from the environment machine Z, input,sid,pi,xp,r∈RZpB,rp is sent to the ideal function ℱLSB.(2)
When the outputc,cp,c0⊕r0p is received from the ideal function ℱLSB, compute,sid,c,cp,c0⊕r0p is sent to the environment machine Z.(3)
When the outputc<Brp,2c<Brp×c0⊕r0p is received from the environment machine Z, compute,sid,pi,c<Brp,2c<Brp×c0⊕r0p is sent to the ideal function ℱLSB.(4)
Send the outputoutput,sid,pi to the ideal function ℱLSB.
The ideal functionℱLSB is described as follows:Ideal functionℱLSB:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputinput,sid,pi,xp,r∈RZpB,rp from the participant pi, it computes cp=xp+rp, and when it receives inputs from at least t participants, it recovers c using Lagrange interpolation and sends c,cp,c0⊕r0p to the participants.(2)
When it receivescompute,sid,pi,c<Brp,2c<Brp×c0⊕r0p from participant pi, compute x0p=c<Brp+c0⊕r0p−2c<Brp×c0⊕r0p. The two inputs of pi are written as xi, and the output in (1) is y1i, y2i=x0p.(3)
When it receives a requestoutput,sid,pi from participant pi, first, it determines whether pi is corrupted. If not, it returns y2i; if so, it sets n+=1. If n>t, then it produces a delayed output y2i to pi.(4)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi and y1i are sent to S.(5)
When it receivescorrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and x0 is recovered using y2i of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let y2i=x0 of all corrupted participants and send y2i and x0 of the current participant to S; otherwise, only y2i of the current participant is sent.
The proof for Claim2 is similar to Claim 1.
The computation steps exceptπLSB in πcomparison are noninteractive; participants can complete them locally without any communications, so there is no adversary attack, and it is as secure as πLSB.
(3) Security Analysis ofπadditoin. Since πaddition itself is noninteractive, participants can complete without any communication in the local, and there is no adversary attack, so the protocol πaddition is unconditional security.
(4) Security Analysis of Our Scheme.Ideal functionℱ:n=0, where n is used to record the number of participants corrupted by the adversary.(1)
When it receives the inputsinput,sid,A,wA,Ta and input,sid,B,wb,Tb from transaction nodes A and B, it generates secret shares wAp,wBp,TAp,TBp for all nodes pi participating in the verification and sends corresponding secret shares to participants.(2)
When it receivesinput,sid,pi,wA=wBp,TA<wBp from participants pi with more than t, it uses Lagrange interpolation to recover the values of wA=wB and TA<wB. If TA<wB=0 and wA=wB=1, the values of wA=wB and TA<wB are sent to the leader, and the corresponding secret shares of each participant are used to calculate TA−wBp and TB+wAp, respectively. Otherwise, the values of wA=wB and TA<wB are sent to the leader, and the protocol process is terminated. Let yi=TA−wBp,TB+wAp, and xi is the set of all inputs for pi.(3)
When it receives a requestoutput,sid,pi from participant pi. First, it determines whether pi is corrupted. If not, it returns yi; if so, it sets n+=1. If n>t, then it produces a delayed output yi to pi. When it receives corrupted_input,sid,pi from adversary S, the corresponding record of pi is corrupted, and xi is sent to S.(4)
When it receivescorrupted_output,sid,pi from adversary S, the corresponding record of pi is corrupted. TA−wB,TB+wA are recovered using yi of all participants marked with corrupted by Lagrange interpolation. If a valid solution can be successfully recovered, let yi=TA−wB,TB+wA of all corrupted participants and send TA−wB,TB+wA to S; otherwise, only yi of the current participant is sent.Theorem 3.
Our protocolπ securely implements ideal function ℱ under ℱequality,ℱcomprison,ℱaddition-hybrid model.In an ideal world, the participantpi first interacts with ℱequality using wAp,wBp, gets its output as the value of wA=wBp, and interacts with ℱcomparison using wB,Ta to get its output as the value of TA<wBp.Proof.
Given an adversary in the real world, construct an adversaryS in the ideal world such that the probability of any environmental machine Z distinguishing between the two worlds is negligible. The ideal adversary S forwards any input from the environment to A, and any output of A is regarded as the output of S. The specific operation of S is as follows:(1)
Simulation establishment.Whenxi,yi belonging to pi are received from ideal function ℱ, the simulated adversary gets xi,yi.(2)
Simulate corruption.When a real-world adversaryA corrupts pi, S corrupts pi by calling Corrupted_input or Corrupted_output and forwards xi,yi to A.(3)
Indistinguishability.Define event 1: whenn≤t, the value TA−wB,TB+wA can be received from the ideal function ℱ. According to Lemma 1, the event is impossible to occur.Define event 2: forinput,sid,pi,TA<wBp where the value of wA=wBp or TA<wBp is exactly a definite bit 0 or 1, when the adversary corrupts no more than t participants, according to Claim 1 and Claim 2, the event cannot occur. So the two worlds are indistinguishable. Theorem 3 is proved.


## 7. Conclusions

This paper proposes a private-oriented transaction scheme based on the blockchain via Shamir’s secret sharing. Taking advantage of the secret sharing feature, we creatively design a physical-logical chain; the characteristic is that each node maintains a physical chain locally, and physical chains map to the same logical chain. In this paper, we use the Equality Test Protocol, Comparison Protocol, and raft consensus algorithm to achieve legal transactions without disclosing any information about balance and trading value. And we propose noninteractive multiplication, which improves the efficiency of the whole scheme and reduces the risks brought by the interactive process.



---

*Source: 9946088-2022-11-19.xml*