# Research on a New Signature Scheme on Blockchain

Authors: Chao Yuan; Mi-xue Xu; Xue-ming Si
Journal: Security and Communication Networks
 (2017)

---

## Abstract

With the rise of Bitcoin, blockchain which is the core technology of Bitcoin has received increasing attention. Privacy preserving and performance on blockchain are two research points in academia and business, but there are still some unresolved issues in both respects. An aggregate signature scheme is a digital signature that supports making signatures on many different messages generated by many different users. Using aggregate signature, the size of the signature could be shortened by compressing multiple signatures into a single signature. In this paper, a new signature scheme for transactions on blockchain based on the aggregate signature was proposed. It was worth noting that elliptic curve discrete logarithm problem and bilinear maps played major roles in our signature scheme. And the security properties of our signature scheme were proved. In our signature scheme, the amount will be hidden especially in the transactions which contain multiple inputs and outputs. Additionally, the size of the signature on transaction is constant regardless of the number of inputs and outputs that the transaction contains, which can improve the performance of signature. Finally, we gave an application scenario for our signature scheme which aims to achieve the transactions of big data on blockchain.


---

## Body

## 1. Introduction

Since the emergence of Bitcoin [1], blockchain as the core technology of Bitcoin has attracted more and more attention. As a combination of a variety of technologies such as distributed data storage, peer-to-peer network, consensus mechanism, and cryptographic algorithm, blockchain has broad prospects of application.There are still some flaws on blockchain where privacy preserving and performance are two important aspects. When achieving the characteristics of blockchain, preserving the privacy is the focus of academic research. In this field, Monero and Zcach are representative projects where ring signature, zero-knowledge proof, and other cryptographic technologies play important roles. In addition, achieving rapid trading to meet realistic demands is another challenge that blockchain faces. In this field, lightning network is widely recognized, but there are also some flaws in its theories and implement.Meanwhile, we know big data has been used in many fields. However, there are still many flaws in the storage, transmission, transaction, and privacy preserving of big data. And blockchain was considered to be an ideal technology for solving these flaws. Thus, we applied our new signature scheme to the transactions of big data on blockchain.Our Contributions.In this work, we make three contributions in view of the privacy preserving and performance on blockchain.(1) We introduce some existing contributions to the privacy preserving on blockchain, including CoinJoin in Dash, ring signature in Monero, and zero-knowledge proof in Zcash.(2) We introduce some cryptographic technologies which are favorable for privacy preserving and performance on blockchain, including elliptic curve cryptography (ECC), bilinear maps, and aggregation signature. And then we propose a new signature scheme for the transaction on blockchain in which the amount will be hidden especially in the transactions which include multiple inputs and outputs. Additionally, the size of the signature on transaction is constant regardless of the number of inputs and outputs that the transaction contains, which can improve the performance of the signature. And we give the security analysis of our new signature scheme.(3) We propose an application scenario for our signature scheme which aims to achieve the transaction of big data on blockchain.Paper Organization. The rest of the paper is organized as follows. Section 2 introduces some projects which aimed at the privacy preserving on blockchain. And the basic building blocks that will be used in our signature scheme are also introduced. In Section 3, the core of our new signature scheme which aimed at hiding the amount of transactions is introduced. The main contribution of this paper is the new signature scheme on blockchain based on aggregate signature that will be described in Section 4, and a formal security analysis for our proposed scheme will also be presented. In Section 5, a simple application of our signature scheme is introduced with respect to transactions of big data. Finally, Section 6 concludes the paper.


## 2. Preliminaries

### 2.1. Privacy Preserving on Blockchain

Dash. Dash uses a technique known as CoinJoin. In a nutshell, the CoinJoin mixes multiple transactions of multiple users to a single transaction through some master nodes. In Dash, each user picks an address and then sends it to the master node to mix with other addresses. Transactions can only be made with amount of 0.1, 1, 10, and 100 which increases the difficulty for the attackers to guess the relevance of transactions from the amount of transactions. At the same time, the master nodes are required to ensure out-of-order output. As shown in Figure 1, different lines represent different users and every amount is 10 DASH. DASH is the currency unit in this system. By mixing, the user who is represented by the vertical line makes a transaction of 10 DASH to the user who is represented by the line from top left to bottom right, while it is hard for others to find this transaction from the confused transactions.Figure 1
CoinJoin technique.Monero. In Dash, there is still the risk that the master nodes are controlled by malicious attackers, which may lead to the disclosure privacy of the users. In order to solve this problem, a hybrid cryptographic scheme that does not depend on the central nodes was proposed in Monero. There are two technologies in Monroe: one is calledstealth address and the other is calledring signature [2, 3].Stealth addressis to solve the problem of relevance of input addresses and output addresses. Each time the sender makes a transaction, a one-time public key using the elliptic curve via the receiver’s address will be computed. The sender then sends out this public key along with an additional message on blockchain. And the receivers can detect each transaction based on its own private key to determine whether the sender has already sent out the transaction. When the receiver wants to use the transaction, it can calculate a private key of signature based on their own private key and transaction information. Then the transaction is signed by the private key of signature.In addition, Monroe proposed aring signature scheme. Whenever the sender wants to make a transaction, the transaction will be signed by the sender’s private key and the public keys of other users randomly selected. When verifying a signature, the public keys of the other users and the parameters in the signature are needed.Zcash. A new scheme with zero-knowledge proof was proposed in Zcash, which allows users to hide transaction information only by interacting with the cryptographic algorithm itself, so that all transactions are created equally [4].In Zcash, a noninteractive zero-knowledge proof [5, 6] was used, which is called zk-SNARK. Here we do not go into the details of zk-SNARK but generally describe how to use this technology in Zcash. Let us discuss the simplest case, assuming that the amount in Zcash is fixed, such as 1BTC. Then the process of coinage is equivalent to the fact that the user pours 1BTC into an escrow pool and then writes a commitment which can be calculated by the serial number and user’s private key to a list. When the user wants to spend the money, two steps need to be done:(1)
Give the serial number.(2)
Use zk-SNARK to prove that it holds the user’s private key to generate this commitment.


### 2.2. Bilinear Pairings

There,G1 and G2 are two multiplicative cyclic groups of prime order p, g1 is a generator of G1, and g2 is a generator of G2. ψ is a computable isomorphism from G2 to G1, with ψ(g2) = g1. A bilinear pairing is defined to be G=(n,G1,G2,GT,e,g1,g2),where G1=g1,G2=g2, and GT are multiplicative groups of order n. Let e:G1×G2→GT be a map with the following properties [7, 8]:(i)
Bilinear:∀u∈G1,v∈G2 and a,b∈Zn:eua,vb=eu,vab.(ii)
Nondegenerate: there existsu∈G1, v∈G2 such that e(u,v)≠O, where O means the identity of GT.(iii)
Computability: there is an efficient algorithm to computee(u,v) for all u∈G1, v∈G2.


### 2.3. Aggregate Signature

There,U means a set of users, each user u∈U has a signature key pair (PKu,SKu), and U1⊆U means the users whose signatures will be aggregated. Each user u∈U1 generates a signature σu for the message Mu they select, and then these signatures are grouped into a single signature by an aggregate community, which cannot be in the set U or can be distrusted by the user in the collection U, who has access to the user’s public key, message, and their home signature but cannot access any private key.The result of the aggregate signature isσ whose length is the same as any single signature. Aggregate signatures have the property that a verifier can make sure that each user signs their own messages [7, 8] when σ and each message are obtained.


### 2.4. Elliptic Curve

Assume thatFq has characteristic greater than 3. An elliptic curve E over Fq is the set of all solutions x,y∈Fq×Fq to an equation y2=x3+ax+b, where a,b∈Fq, and 4a2+27b2≠0, together with a special point ∞ called the point at infinity. It is well known that E is an abelian group with the point ∞ serving as its identity element. The rules for group addition are summarized below [9].(1) Let P=x1,y1∈E; then -P=x1,-y1. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where x3=λ2-x1-x2 and y3=λx1-x3-y1(1)λ=y2-y1x2-x1,ifP≠Q3x12+a2y1,ifP=Q.IfFq is a field of characteristic 2, an elliptic curve E of zero j-invariant over Fq is the set of all solutions x,y∈F¯q×F¯q to an equation y2+cy=x3+ax+b, where a,b,c∈Fq, c≠0, together with the point at infinity ∞. The rules for group addition are summarized below.(2) Let P=x1,y1∈E; then -P=x1,y1+c. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where(2)x3=y1+y2x1+x22+x1+x2ifP≠Qx14+a2c2ifP=Q,y3=y1+y2x1+x2x1+x3+y1+cifP≠Qx12+acx1+x3+y1+cifP=Q.IfFq is a field of characteristic 2, an elliptic curve E ofnonzero j-invariant over Fq is the set of all solutions x,y∈F¯q×F¯q to an equation y2+xy=x3+ax2+b, where a,b∈Fq,b≠0, together with the point at infinity ∞. The rules for group addition are summarized below.(3) Let P=x1,y1∈E; then -P=x1,y1+x1. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where(3)x3=y1+y2x1+x22+y1+y2x1+x2+x1+x2+aifP≠Qx12+bx12ifP=Q,y3=y1+y2x1+x2x1+x3+x3+y1ifP≠Qx12+x1+y1x1x3+x3ifP=Q.


## 2.1. Privacy Preserving on Blockchain

Dash. Dash uses a technique known as CoinJoin. In a nutshell, the CoinJoin mixes multiple transactions of multiple users to a single transaction through some master nodes. In Dash, each user picks an address and then sends it to the master node to mix with other addresses. Transactions can only be made with amount of 0.1, 1, 10, and 100 which increases the difficulty for the attackers to guess the relevance of transactions from the amount of transactions. At the same time, the master nodes are required to ensure out-of-order output. As shown in Figure 1, different lines represent different users and every amount is 10 DASH. DASH is the currency unit in this system. By mixing, the user who is represented by the vertical line makes a transaction of 10 DASH to the user who is represented by the line from top left to bottom right, while it is hard for others to find this transaction from the confused transactions.Figure 1
CoinJoin technique.Monero. In Dash, there is still the risk that the master nodes are controlled by malicious attackers, which may lead to the disclosure privacy of the users. In order to solve this problem, a hybrid cryptographic scheme that does not depend on the central nodes was proposed in Monero. There are two technologies in Monroe: one is calledstealth address and the other is calledring signature [2, 3].Stealth addressis to solve the problem of relevance of input addresses and output addresses. Each time the sender makes a transaction, a one-time public key using the elliptic curve via the receiver’s address will be computed. The sender then sends out this public key along with an additional message on blockchain. And the receivers can detect each transaction based on its own private key to determine whether the sender has already sent out the transaction. When the receiver wants to use the transaction, it can calculate a private key of signature based on their own private key and transaction information. Then the transaction is signed by the private key of signature.In addition, Monroe proposed aring signature scheme. Whenever the sender wants to make a transaction, the transaction will be signed by the sender’s private key and the public keys of other users randomly selected. When verifying a signature, the public keys of the other users and the parameters in the signature are needed.Zcash. A new scheme with zero-knowledge proof was proposed in Zcash, which allows users to hide transaction information only by interacting with the cryptographic algorithm itself, so that all transactions are created equally [4].In Zcash, a noninteractive zero-knowledge proof [5, 6] was used, which is called zk-SNARK. Here we do not go into the details of zk-SNARK but generally describe how to use this technology in Zcash. Let us discuss the simplest case, assuming that the amount in Zcash is fixed, such as 1BTC. Then the process of coinage is equivalent to the fact that the user pours 1BTC into an escrow pool and then writes a commitment which can be calculated by the serial number and user’s private key to a list. When the user wants to spend the money, two steps need to be done:(1)
Give the serial number.(2)
Use zk-SNARK to prove that it holds the user’s private key to generate this commitment.


## 2.2. Bilinear Pairings

There,G1 and G2 are two multiplicative cyclic groups of prime order p, g1 is a generator of G1, and g2 is a generator of G2. ψ is a computable isomorphism from G2 to G1, with ψ(g2) = g1. A bilinear pairing is defined to be G=(n,G1,G2,GT,e,g1,g2),where G1=g1,G2=g2, and GT are multiplicative groups of order n. Let e:G1×G2→GT be a map with the following properties [7, 8]:(i)
Bilinear:∀u∈G1,v∈G2 and a,b∈Zn:eua,vb=eu,vab.(ii)
Nondegenerate: there existsu∈G1, v∈G2 such that e(u,v)≠O, where O means the identity of GT.(iii)
Computability: there is an efficient algorithm to computee(u,v) for all u∈G1, v∈G2.


## 2.3. Aggregate Signature

There,U means a set of users, each user u∈U has a signature key pair (PKu,SKu), and U1⊆U means the users whose signatures will be aggregated. Each user u∈U1 generates a signature σu for the message Mu they select, and then these signatures are grouped into a single signature by an aggregate community, which cannot be in the set U or can be distrusted by the user in the collection U, who has access to the user’s public key, message, and their home signature but cannot access any private key.The result of the aggregate signature isσ whose length is the same as any single signature. Aggregate signatures have the property that a verifier can make sure that each user signs their own messages [7, 8] when σ and each message are obtained.


## 2.4. Elliptic Curve

Assume thatFq has characteristic greater than 3. An elliptic curve E over Fq is the set of all solutions x,y∈Fq×Fq to an equation y2=x3+ax+b, where a,b∈Fq, and 4a2+27b2≠0, together with a special point ∞ called the point at infinity. It is well known that E is an abelian group with the point ∞ serving as its identity element. The rules for group addition are summarized below [9].(1) Let P=x1,y1∈E; then -P=x1,-y1. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where x3=λ2-x1-x2 and y3=λx1-x3-y1(1)λ=y2-y1x2-x1,ifP≠Q3x12+a2y1,ifP=Q.IfFq is a field of characteristic 2, an elliptic curve E of zero j-invariant over Fq is the set of all solutions x,y∈F¯q×F¯q to an equation y2+cy=x3+ax+b, where a,b,c∈Fq, c≠0, together with the point at infinity ∞. The rules for group addition are summarized below.(2) Let P=x1,y1∈E; then -P=x1,y1+c. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where(2)x3=y1+y2x1+x22+x1+x2ifP≠Qx14+a2c2ifP=Q,y3=y1+y2x1+x2x1+x3+y1+cifP≠Qx12+acx1+x3+y1+cifP=Q.IfFq is a field of characteristic 2, an elliptic curve E ofnonzero j-invariant over Fq is the set of all solutions x,y∈F¯q×F¯q to an equation y2+xy=x3+ax2+b, where a,b∈Fq,b≠0, together with the point at infinity ∞. The rules for group addition are summarized below.(3) Let P=x1,y1∈E; then -P=x1,y1+x1. If Q=x2,y2∈E,Q≠-P, then P+Q=x3,y3, where(3)x3=y1+y2x1+x22+y1+y2x1+x2+x1+x2+aifP≠Qx12+bx12ifP=Q,y3=y1+y2x1+x2x1+x3+x3+y1ifP≠Qx12+x1+y1x1x3+x3ifP=Q.


## 3. Core of the New Signature Scheme

When transactions are generated on blockchain, cryptographic signatures are used to judge the legality of the transactions and the identities of the senders [10]. Furthermore, the signature algorithms are aimed at privacy preserving of the transactions, including the addresses of both sides and transaction amount. For example, in Bitcoin, ECDSA [11, 12], RIPEMD [13, 14], and SHA256 [15, 16] are used to make signatures for the transactions. In Section 3.1, we will design a scheme which is the core of our new signature scheme. The amount of transactions which include multiple inputs and outputs can be hidden using this scheme.


### 3.1. Basic Scheme

Without loss of generality, we deal with a single transaction, which is divided into inputs and outputs; the details are shown in Figure2.Figure 2
Model of single transaction.As shown in Figure2, the transaction contains n inputs and m outputs. Accessibly, we have ∑i=1nini=∑j=1moutj.For eachi and j,1≤i≤n,1≤j≤m; in order to hide ini and outj, this paper uses ECC to make an operation for them. We choose G as the generator of Fp, and the transfer forms of ini and outj are Ij=inj·G and Oj=outj·G. And according to the operation rules of the elliptic curve, the following equations are true [17]:(4)∑i=1nini·G=∑i=1nIi=∑i=1nini·G∑j=1moutj·G=∑j=1mOj=∑j=1moutj·G.According to (4), we can verify ∑i=1nini=∑j=1moutj by ∑i=1nIi=∑j=1mOj. Because the attackers cannot get ini and outj through Ii and Oj, the amount of transaction can be hidden by this scheme. The following introduces the homomorphic proof and the drawback of this scheme [18].Homomorphic Proof of the Signature Scheme. Homomorphic property is an important target to evaluate the security of an algorithm, especially considering that quantum computer gets rapid development. We can easily prove that our basic scheme satisfies additive homomorphism [19, 20].Proof.
For eachi,1≤i≤n, as defined in basic scheme, Ii=ini·G. According to the operation rules of the elliptic curve, the following equations are true:(5)∑i=1nini·G=∑i=1nini·G∑i=1nini·G=∑i=1nini·G.
We can obtain that(6)∑i=1nini·G=∑i=1nini·G.
The left side of (6) means the addition followed by an encryption operation; correspondingly the right side means the encryption operation followed by addition. So we can obtain that our basic scheme is additive homomorphic.The Drawback of the Basic Scheme. Our basic scheme can hide the amount of the transactions which contain multiple inputs and outputs. But there are also opportunities for the attackers to acquire the amount. On Bitcoin system, there has been mature attack algorithms, such as selfish mining attack [21, 22], eclipse attack [23], and stubborn mining attack [24]. There are similar drawbacks in our basic scheme.A malicious attacker impedesu inputs and v outputs, which satisfy the fact that ∑i=1uini′=∑j=1voutj′. And in the normal network, the sum of all the inputs is(7)Is=∑i=1nini-∑j=1uin′j.The sum of all the outputs is(8)Os=∑i=1mouti-∑j=1vout′j,where the elements of sets in′j1≤j≤u and out′j1≤j≤v are contained in sets ini1≤i≤n and outi1≤i≤m.Because we know that∑i=1uin′i=∑j=1vout′j and ∑i=1nini=∑j=1moutj, it can be obtained that Is=Os. So we can also verify that Is·G=Os·G.In order to modify our basic scheme, this paper combines aggregate signature with the basic scheme to obtain a modified scheme.


### 3.2. Modified Scheme

Recall that elliptic curve on the finite groupFp is specified by tuple p,a,b,G,n,G=gx,gy which is the generator of Fp,n·G=O. The modified scheme is performed as follows.(1) Compute Ii=ini·G,i=1,2,…,n, Oj=outj·G,j=1,2,…,m.(2) For each i,1≤i≤n, randomly select di∈Zp, and compute iRi=di·G, ihi=HiRi∥ini, and isi=di·ihi+ini. And randomly select tj∈Zp, and compute oRj=tj·G, ohj=HoRj∥outj, and osj=tj·ohj+outj; the transfer forms of inputs and outputs are ∑i=1nisi and ∑j=1mosj.Feasibility of the Modified Scheme. Given Ii,Oj1≤i≤n;1≤j≤m, iRi1≤i≤n, ihi1≤i≤n, oRj1≤j≤m, and ohj1≤j≤m and the transfer form ∑i=1nisi and ∑j=1mosj, we can obtain that (9)∑i=1nihi·iRi-∑i=1nisi·G=∑j=1mohj·oRj-∑j=1mosj·G.Proof of the feasibility of the modified scheme will be given in the Appendix.The modified scheme greatly avoids the drawback in the basic scheme. If a malicious attacker impedesu inputs and v inputs, which satisfy the fact that ∑i=1uini=∑j=1voutj, then ∑i=1nihi·iRi, ∑i=1nisi·G, ∑j=1mohj·oRj, and ∑j=1mosj·G will change as well. And we cannot get (10)∑i=1n-uih′i·iR′i-∑i=1n-uis′i·G=∑j=1m-voh′j·oR′j-∑j=1m-vos′j·G,where ih′i1≤i≤n-u′ is the set which is obtained from the set ihi1≤i≤n removing the elements impeded. The relationship also applies to iR′i1≤i≤n-u′ and iRi1≤i≤n, is′i1≤i≤n-u′ and isi1≤i≤n,oh′j1≤j≤m-v′ and ohj1≤j≤m, oR′j1≤j≤m-v′ and oRj1≤j≤m, os′j1≤j≤m-v′ and osj1≤j≤m. So it will not pass verification; then the attack will not be successful.


## 3.1. Basic Scheme

Without loss of generality, we deal with a single transaction, which is divided into inputs and outputs; the details are shown in Figure2.Figure 2
Model of single transaction.As shown in Figure2, the transaction contains n inputs and m outputs. Accessibly, we have ∑i=1nini=∑j=1moutj.For eachi and j,1≤i≤n,1≤j≤m; in order to hide ini and outj, this paper uses ECC to make an operation for them. We choose G as the generator of Fp, and the transfer forms of ini and outj are Ij=inj·G and Oj=outj·G. And according to the operation rules of the elliptic curve, the following equations are true [17]:(4)∑i=1nini·G=∑i=1nIi=∑i=1nini·G∑j=1moutj·G=∑j=1mOj=∑j=1moutj·G.According to (4), we can verify ∑i=1nini=∑j=1moutj by ∑i=1nIi=∑j=1mOj. Because the attackers cannot get ini and outj through Ii and Oj, the amount of transaction can be hidden by this scheme. The following introduces the homomorphic proof and the drawback of this scheme [18].Homomorphic Proof of the Signature Scheme. Homomorphic property is an important target to evaluate the security of an algorithm, especially considering that quantum computer gets rapid development. We can easily prove that our basic scheme satisfies additive homomorphism [19, 20].Proof.
For eachi,1≤i≤n, as defined in basic scheme, Ii=ini·G. According to the operation rules of the elliptic curve, the following equations are true:(5)∑i=1nini·G=∑i=1nini·G∑i=1nini·G=∑i=1nini·G.
We can obtain that(6)∑i=1nini·G=∑i=1nini·G.
The left side of (6) means the addition followed by an encryption operation; correspondingly the right side means the encryption operation followed by addition. So we can obtain that our basic scheme is additive homomorphic.The Drawback of the Basic Scheme. Our basic scheme can hide the amount of the transactions which contain multiple inputs and outputs. But there are also opportunities for the attackers to acquire the amount. On Bitcoin system, there has been mature attack algorithms, such as selfish mining attack [21, 22], eclipse attack [23], and stubborn mining attack [24]. There are similar drawbacks in our basic scheme.A malicious attacker impedesu inputs and v outputs, which satisfy the fact that ∑i=1uini′=∑j=1voutj′. And in the normal network, the sum of all the inputs is(7)Is=∑i=1nini-∑j=1uin′j.The sum of all the outputs is(8)Os=∑i=1mouti-∑j=1vout′j,where the elements of sets in′j1≤j≤u and out′j1≤j≤v are contained in sets ini1≤i≤n and outi1≤i≤m.Because we know that∑i=1uin′i=∑j=1vout′j and ∑i=1nini=∑j=1moutj, it can be obtained that Is=Os. So we can also verify that Is·G=Os·G.In order to modify our basic scheme, this paper combines aggregate signature with the basic scheme to obtain a modified scheme.


## 3.2. Modified Scheme

Recall that elliptic curve on the finite groupFp is specified by tuple p,a,b,G,n,G=gx,gy which is the generator of Fp,n·G=O. The modified scheme is performed as follows.(1) Compute Ii=ini·G,i=1,2,…,n, Oj=outj·G,j=1,2,…,m.(2) For each i,1≤i≤n, randomly select di∈Zp, and compute iRi=di·G, ihi=HiRi∥ini, and isi=di·ihi+ini. And randomly select tj∈Zp, and compute oRj=tj·G, ohj=HoRj∥outj, and osj=tj·ohj+outj; the transfer forms of inputs and outputs are ∑i=1nisi and ∑j=1mosj.Feasibility of the Modified Scheme. Given Ii,Oj1≤i≤n;1≤j≤m, iRi1≤i≤n, ihi1≤i≤n, oRj1≤j≤m, and ohj1≤j≤m and the transfer form ∑i=1nisi and ∑j=1mosj, we can obtain that (9)∑i=1nihi·iRi-∑i=1nisi·G=∑j=1mohj·oRj-∑j=1mosj·G.Proof of the feasibility of the modified scheme will be given in the Appendix.The modified scheme greatly avoids the drawback in the basic scheme. If a malicious attacker impedesu inputs and v inputs, which satisfy the fact that ∑i=1uini=∑j=1voutj, then ∑i=1nihi·iRi, ∑i=1nisi·G, ∑j=1mohj·oRj, and ∑j=1mosj·G will change as well. And we cannot get (10)∑i=1n-uih′i·iR′i-∑i=1n-uis′i·G=∑j=1m-voh′j·oR′j-∑j=1m-vos′j·G,where ih′i1≤i≤n-u′ is the set which is obtained from the set ihi1≤i≤n removing the elements impeded. The relationship also applies to iR′i1≤i≤n-u′ and iRi1≤i≤n, is′i1≤i≤n-u′ and isi1≤i≤n,oh′j1≤j≤m-v′ and ohj1≤j≤m, oR′j1≤j≤m-v′ and oRj1≤j≤m, os′j1≤j≤m-v′ and osj1≤j≤m. So it will not pass verification; then the attack will not be successful.


## 4. New Signature Scheme on Blockchain

In Section3, we proposed a new scheme which aimed at hiding the amount of the transactions on blockchain which contain multiple inputs and outputs. Based on this, we designed a new signature scheme that can protect the amount of transactions and keep the size of signatures constant regardless of the number of inputs and outputs. Recall that elliptic curve E on the finite group Fp is specified by tuple p,a,b,G,n. The base groups are G1 and G2, their respective generators are g1 and g2, the computable isomorphism ψisfrom G2 to G1, and the bilinear map is e:G1×G2→GT with target group GT. Let Hs:{0,1}∗→Fq, Hp:EFq→EFq.


### 4.1. Basic Signature Scheme

Key Generation.A particular user picks random x←RZp, a∈E and computes v=g2x, A=aG. The user’s signature public key and signature private key are v∈G2 and x∈Zp. The user’s payment public key and payment private key are A∈E and a∈E.Signing. We suppose that the sender wants to send a payment to a particular receiver whose payment public key is B. The sender generates a random r∈[1,n-1] and computes a one-time public key P=HsrBG+A and then computes σ=Px. The signature is σ∈G1. R=r·G is also packed somewhere into the transaction.Verification. Given the sender’s payment public key v, and the signature σ, the receiver computes P′=Hsb·R·G+A and then accepts if eσ,g2=eP′,v holds.We know thatb·R=b·r·G=r·B; then P′=P. And through the rules of the bilinear maps, we obtain that eσ,g2=ePx,g2=P,g2x=P′,v. Figure 3 gives the structure of our basic signature scheme.Figure 3
Basic transaction structure.As shown in Figure3, we give the basic signature scheme [2, 25]. In order to achieve the purpose of improving the performance of the signature scheme, we combine the aggregate signature with our basic signature scheme and propose a modified signature scheme in Section 4.2.


### 4.2. Modified Signature Scheme

Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to k=U1.  Each user ui∈U1 picks random xi←RZp, ai∈E and computes vi=g2xi, Ai=ai·G. The signature public key and signature private key of ui are vi∈G2 and xi∈Zp. The payment public key and payment private key of ui are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transaction.Aggregation. Compute σ←∏i=1kσi; the aggregate signature is σ∈G1.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=Hsbi·Ri·G+Ai for 1≤i≤k and accept if eσ,g2=∏i=1kePi′,vi holds.Using the properties of the bilinear map, the left side of the verification equation expands:(11)eσ,g2=∏i=1ke∏i=1kσi,g2=∏i=1ke∏i=1kPixi,g2=∏i=1kePixi,g2=∏i=1kePi′,g2xi=∏i=1kePi′,vi.Figure4 gives the structure of our aggregate transaction structure.Figure 4
Aggregate transaction structure.As shown in Figure4, the signature is kept constant regardless of the number of inputs and outputs that the transaction contains. Then we combine the core of the new signature scheme proposed in Section 3.2 with the modified signature scheme to a new signature scheme which will be described in Section 4.3.


### 4.3. New Signature Scheme

Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to k=U1. Each user ui∈U1, picks random xi←RZp, ai∈E, and computes vi=g2xi, Ai=ai·G. The user’s signature public key and signature private key are vi∈G2 and xi∈Zp. The user’s payment public key and payment private key are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transactions. And compute AIi=Iai·G, AOj=Oaj·G.Aggregation. Compute σ←∏i=1kσi; the aggregate signature is σ∈G1. For each i,1≤i≤k, randomly select di∈Zp and compute iRi=di·G, ihi=HiRi∥Iai, and isi=di·ihi+Iai; the transfer form of input is ∑i=1nisi.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=Hsbi·Ri·G+Ai for 1≤i≤k and accept if eσ,g2=∏i=1kePi′,vi holds. And randomly select tj∈Zp, compute oRj=tj·G, ohj=HoRj∥Oaj, and osj=tj·ohj+Oaj; the transfer form outputs are ∑j=1mosj. Figure 5 gives the structure of our new transaction structure.Figure 5
New transaction structure.


### 4.4. Security of the New Signature Scheme

It is easy to show that the security of our new signature scheme is equivalent to the traditional bilinear aggregate signature. As the aggregate chose-key security model which was proposed in [7], the security of aggregate signature schemes is equivalent to the nonexistence of an adversary capable of existentially forging an aggregate signature. Existential forgery here means that the adversary attempts to forge an aggregate signature on a subtransaction of his choice by other subtransactions in a particular transaction. The adversary A is given a single public key. His goal is the existential forgery of an aggregate signature. We give the adversary power to choose all public keys except the challenge public key. The adversary is also given access to a signing oracle on the challenge key. His advantage AdvAggSigA is defined to be his probability of success in the following game [7, 26].Setup. The aggregate forger A is provided with a public key PK1, generated at random.Queries. Proceeding adaptively, A requests signatures with PK1 on the subtransaction of his choice.Response. Finally, A outputs k-1 additional public keys PK2,…,PKk. These keys, along with the initial key PK1, will be included in A’s forged aggregate. A also outputs subtransaction T1,…,Tk, finally, an aggregate signature σ by the k users, each on his corresponding subtransaction.The forger wins if the aggregate signatureσ is a valid aggregate on subtransactions T1,…,Tk under keys PK1,…,PKk, and σ is nontrivial.Definition 1.
An aggregate forgerAt,qH,qs,N,ϵ-breaks an N-user aggregate signature scheme in the aggregate chosen-key model if the following conditions are met:(1)
A runs in time at most t.(2)
A makes at most qH queries to the hash function and at most qS queries to the signing oracle.(3)
AdvAggSigA is at least ϵ.(4)
Forged aggregate signature is by at mostN users.
An aggregate signature scheme ist,qH,qs,N,ϵ-secure. It is against existential forgery in the aggregate chosen-key model if no forger t,qH,qs,N,ϵ-breaks it. The next theorem shows that this simple constraint is sufficient for proving security in the chosen-key model.Theorem 2.
Let(G1,G2) be a t′,ϵ′-bilinear group pair for co-Diffie-Hellman, with each group of order p, with respective generators g1 and g2, with an isomorphism computable from G2 to G1, and with a bilinear map e:G1×G2→GT. Then the bilinear aggregate signature scheme on (G1,G2) is t,qH,qs,N,ϵ-secure against existential forgery in the aggregate chosen-key model for all t and ϵ satisfying ϵ≥eqs+N·ϵ′ and t≤t′-cG1qH+2qs+N+4-N-1, where e is the base of natural logarithms, and exponentiation and inversion on G1 take time cG1.Besides, the security of the scheme which is used to hide the amount of the transactions has been analyzed in Section3.2. So, we can get that our signature scheme satisfies unforgeability and other security properties.


## 4.1. Basic Signature Scheme

Key Generation.A particular user picks random x←RZp, a∈E and computes v=g2x, A=aG. The user’s signature public key and signature private key are v∈G2 and x∈Zp. The user’s payment public key and payment private key are A∈E and a∈E.Signing. We suppose that the sender wants to send a payment to a particular receiver whose payment public key is B. The sender generates a random r∈[1,n-1] and computes a one-time public key P=HsrBG+A and then computes σ=Px. The signature is σ∈G1. R=r·G is also packed somewhere into the transaction.Verification. Given the sender’s payment public key v, and the signature σ, the receiver computes P′=Hsb·R·G+A and then accepts if eσ,g2=eP′,v holds.We know thatb·R=b·r·G=r·B; then P′=P. And through the rules of the bilinear maps, we obtain that eσ,g2=ePx,g2=P,g2x=P′,v. Figure 3 gives the structure of our basic signature scheme.Figure 3
Basic transaction structure.As shown in Figure3, we give the basic signature scheme [2, 25]. In order to achieve the purpose of improving the performance of the signature scheme, we combine the aggregate signature with our basic signature scheme and propose a modified signature scheme in Section 4.2.


## 4.2. Modified Signature Scheme

Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to k=U1.  Each user ui∈U1 picks random xi←RZp, ai∈E and computes vi=g2xi, Ai=ai·G. The signature public key and signature private key of ui are vi∈G2 and xi∈Zp. The payment public key and payment private key of ui are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transaction.Aggregation. Compute σ←∏i=1kσi; the aggregate signature is σ∈G1.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=Hsbi·Ri·G+Ai for 1≤i≤k and accept if eσ,g2=∏i=1kePi′,vi holds.Using the properties of the bilinear map, the left side of the verification equation expands:(11)eσ,g2=∏i=1ke∏i=1kσi,g2=∏i=1ke∏i=1kPixi,g2=∏i=1kePixi,g2=∏i=1kePi′,g2xi=∏i=1kePi′,vi.Figure4 gives the structure of our aggregate transaction structure.Figure 4
Aggregate transaction structure.As shown in Figure4, the signature is kept constant regardless of the number of inputs and outputs that the transaction contains. Then we combine the core of the new signature scheme proposed in Section 3.2 with the modified signature scheme to a new signature scheme which will be described in Section 4.3.


## 4.3. New Signature Scheme

Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to k=U1. Each user ui∈U1, picks random xi←RZp, ai∈E, and computes vi=g2xi, Ai=ai·G. The user’s signature public key and signature private key are vi∈G2 and xi∈Zp. The user’s payment public key and payment private key are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transactions. And compute AIi=Iai·G, AOj=Oaj·G.Aggregation. Compute σ←∏i=1kσi; the aggregate signature is σ∈G1. For each i,1≤i≤k, randomly select di∈Zp and compute iRi=di·G, ihi=HiRi∥Iai, and isi=di·ihi+Iai; the transfer form of input is ∑i=1nisi.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=Hsbi·Ri·G+Ai for 1≤i≤k and accept if eσ,g2=∏i=1kePi′,vi holds. And randomly select tj∈Zp, compute oRj=tj·G, ohj=HoRj∥Oaj, and osj=tj·ohj+Oaj; the transfer form outputs are ∑j=1mosj. Figure 5 gives the structure of our new transaction structure.Figure 5
New transaction structure.


## 4.4. Security of the New Signature Scheme

It is easy to show that the security of our new signature scheme is equivalent to the traditional bilinear aggregate signature. As the aggregate chose-key security model which was proposed in [7], the security of aggregate signature schemes is equivalent to the nonexistence of an adversary capable of existentially forging an aggregate signature. Existential forgery here means that the adversary attempts to forge an aggregate signature on a subtransaction of his choice by other subtransactions in a particular transaction. The adversary A is given a single public key. His goal is the existential forgery of an aggregate signature. We give the adversary power to choose all public keys except the challenge public key. The adversary is also given access to a signing oracle on the challenge key. His advantage AdvAggSigA is defined to be his probability of success in the following game [7, 26].Setup. The aggregate forger A is provided with a public key PK1, generated at random.Queries. Proceeding adaptively, A requests signatures with PK1 on the subtransaction of his choice.Response. Finally, A outputs k-1 additional public keys PK2,…,PKk. These keys, along with the initial key PK1, will be included in A’s forged aggregate. A also outputs subtransaction T1,…,Tk, finally, an aggregate signature σ by the k users, each on his corresponding subtransaction.The forger wins if the aggregate signatureσ is a valid aggregate on subtransactions T1,…,Tk under keys PK1,…,PKk, and σ is nontrivial.Definition 1.
An aggregate forgerAt,qH,qs,N,ϵ-breaks an N-user aggregate signature scheme in the aggregate chosen-key model if the following conditions are met:(1)
A runs in time at most t.(2)
A makes at most qH queries to the hash function and at most qS queries to the signing oracle.(3)
AdvAggSigA is at least ϵ.(4)
Forged aggregate signature is by at mostN users.
An aggregate signature scheme ist,qH,qs,N,ϵ-secure. It is against existential forgery in the aggregate chosen-key model if no forger t,qH,qs,N,ϵ-breaks it. The next theorem shows that this simple constraint is sufficient for proving security in the chosen-key model.Theorem 2.
Let(G1,G2) be a t′,ϵ′-bilinear group pair for co-Diffie-Hellman, with each group of order p, with respective generators g1 and g2, with an isomorphism computable from G2 to G1, and with a bilinear map e:G1×G2→GT. Then the bilinear aggregate signature scheme on (G1,G2) is t,qH,qs,N,ϵ-secure against existential forgery in the aggregate chosen-key model for all t and ϵ satisfying ϵ≥eqs+N·ϵ′ and t≤t′-cG1qH+2qs+N+4-N-1, where e is the base of natural logarithms, and exponentiation and inversion on G1 take time cG1.Besides, the security of the scheme which is used to hide the amount of the transactions has been analyzed in Section3.2. So, we can get that our signature scheme satisfies unforgeability and other security properties.


## 5. Application of Signatures Scheme

Big data brings many benefits to our lives. At the same time, there are some drawbacks in big data. Firstly, the utilization of data is poor. Large amounts of data are in the idle state, occupying a lot of storage space. Secondly, there are a lot of drawbacks in the security and privacy of the data. The use of big data exposes personal privacy and other security problems, while big data may be used to do illegal activities by criminals. At the same time, there are some drawbacks in the transmission efficiency and transmission accuracy of data. Blockchain is considered to be an ideal solution to these problems. Based on this, we try to apply our signature scheme to the transactions of big data [27].


### 5.1. Infrastructure of Transaction of Big Data on Blockchain

Here, we consider the transactions of big data on blockchain. The infrastructure is based on the P2P network which is the network model of blockchain [28]. And we give the model of the infrastructure in Figure 6.Figure 6
Infrastructure of transaction of data.We consider the inputs and outputs of a particular transaction, which consists of data inputs, data outputs, and the corresponding amount of outputs and amount of inputs which are described in Figure7.Figure 7
Single transaction of data.Setup. Recall that elliptic curve on the finite group Fp is specified by tuple p,a,b,G,n.Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to n=U1.  Each user ui∈U1 picks random xi←RZp, ai∈E and computes vi=g2xi, Ai=ai·G. The signature public key and signature private key of ui are vi∈G2 and xi∈Zp. The payment public key and payment private key of ui are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBi∥OdiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transactions. And compute AIi=Iai·G, AOj=Oaj·G.Aggregation.Compute σ←∏i=1nσi; the aggregate signature is σ∈G1. For each i,1≤i≤n, randomly select di∈Zp and compute iRi=di·G, ihi=HiRi∥Iai, and isi=di·ihi+Iai; the transfer form of input is ∑i=1nisi.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=HsbiRi∥OdiG+Ai for 1≤i≤n and accept if eσ,g2=∏i=1nePi′,vi holds. And randomly select tj∈Zp, compute oRj=tj·G, ohj=HoRj∥Oaj, and osj=tj·ohj+Oaj; the transfer form outputs are ∑j=1mosj.


### 5.2. Performance of Signature Scheme on Transaction of Big Data

Aggregate Signing Time. In a single signature, one hash operation, one modular power multiplication, and one multiplication operation are implemented. Let σ be an aggregate of the n signatures σ1,…,σn. The time to verify the aggregate signature σ is linear in n. And one multiplication with aggregation is implemented [29].Aggregate Verification Time.In a single verification, k times hash operations and n+1 bilinear maps operations are implemented. Let σ be an aggregate of the n signatures σ1,…,σn. The time to verify the aggregate signature σ is linear in n.Signature Space. Let σ be an aggregate of the n signatures σ1,…,σn. The space of the signature will be 1/n of the normal signature.


## 5.1. Infrastructure of Transaction of Big Data on Blockchain

Here, we consider the transactions of big data on blockchain. The infrastructure is based on the P2P network which is the network model of blockchain [28]. And we give the model of the infrastructure in Figure 6.Figure 6
Infrastructure of transaction of data.We consider the inputs and outputs of a particular transaction, which consists of data inputs, data outputs, and the corresponding amount of outputs and amount of inputs which are described in Figure7.Figure 7
Single transaction of data.Setup. Recall that elliptic curve on the finite group Fp is specified by tuple p,a,b,G,n.Key Generation. For the aggregate subset of users U1⊆U, assign to each user an index i, ranging from 1 to n=U1.  Each user ui∈U1 picks random xi←RZp, ai∈E and computes vi=g2xi, Ai=ai·G. The signature public key and signature private key of ui are vi∈G2 and xi∈Zp. The payment public key and payment private key of ui are Ai∈E and ai∈E.Signing. For each i,1≤i≤k, we suppose that ui wants to send a payment to a particular receiver whose payment public key is Bi. And ui generates a random ri∈[1,n-1] and computes a one-time public key Pi=HsriBi∥OdiG+Ai and then computes σi=Pixi. The signature is σi∈G1. Ri=ri·G is also packed somewhere into the transactions. And compute AIi=Iai·G, AOj=Oaj·G.Aggregation.Compute σ←∏i=1nσi; the aggregate signature is σ∈G1. For each i,1≤i≤n, randomly select di∈Zp and compute iRi=di·G, ihi=HiRi∥Iai, and isi=di·ihi+Iai; the transfer form of input is ∑i=1nisi.Aggregate Verification. We are given an aggregate signature σ∈G1 for an aggregating subset U1⊆U indexed as before and are given the original Pi=Hsri·Bi·G+Ai and public keys vi∈G2 for all users ui∈U1. To verify the aggregate signature σ, compute Pi′=HsbiRi∥OdiG+Ai for 1≤i≤n and accept if eσ,g2=∏i=1nePi′,vi holds. And randomly select tj∈Zp, compute oRj=tj·G, ohj=HoRj∥Oaj, and osj=tj·ohj+Oaj; the transfer form outputs are ∑j=1mosj.


## 5.2. Performance of Signature Scheme on Transaction of Big Data

Aggregate Signing Time. In a single signature, one hash operation, one modular power multiplication, and one multiplication operation are implemented. Let σ be an aggregate of the n signatures σ1,…,σn. The time to verify the aggregate signature σ is linear in n. And one multiplication with aggregation is implemented [29].Aggregate Verification Time.In a single verification, k times hash operations and n+1 bilinear maps operations are implemented. Let σ be an aggregate of the n signatures σ1,…,σn. The time to verify the aggregate signature σ is linear in n.Signature Space. Let σ be an aggregate of the n signatures σ1,…,σn. The space of the signature will be 1/n of the normal signature.


## 6. Concluding

In this paper, we have proposed a new signature scheme for the transactions on blockchain based on aggregate signature and ECC. Through our new signature scheme, the amount will be hidden when the transactions contain multiple inputs and outputs [30]. Besides, the size of the signature for the transactions will keep constant regardless of the number of inputs and outputs that the transaction contains. We have shown the validity of our new signature scheme. More importantly, the security of our new signature scheme is analyzed. Currently there is no scheme which achieves both hiding the amount of the transactions and constant-size signature when the transaction contains multiple inputs and outputs. Furthermore, we have given an application scenario for our signature scheme which aimed at achieving the transaction of big data on blockchain. And the performance of the signature scheme in the application scenarios was analyzed.There are still many interesting problems to be solved. For example, it would be valuable to explore the possibility of achieving a signature scheme which combines our scheme with ring signature. Using our scheme to construct a practical complete application is also another interesting problem [31, 32].



---

*Source: 4746586-2017-08-21.xml*