Computer Systems Science & Engineering DOI:10.32604/csse.2021.017507
BlockChain Technology

A Novel PoW Scheme Implemented by Probabilistic Signature for Blockchain

Bo Mi1, Yuan Weng1, Darong Huang1,*, Yang Liu1 and Yuqing Gan2

1Institute of Information Science and Engineering, Chongqing Jiaotong University, Chongqing, 400074, China
2Electrical and Electronics Engineering Department, The University of Sheffield, Sheffield, S102TT, United Kingdom
*Corresponding Author: Darong Huang. Email: drhuang@cqjtu.edu.com
Received: 01 February 2021; Accepted: 16 March 2021

Abstract: PoW (Proof of Work) plays a significant role in most blockchain systems to grant an accounting right over decentralized participants and ensure tamper resistance. Though hash functions are generally exploited for PoW due to their merits on summering, anti-collision, and irreversibility, they cannot certify that the bookkeeper is exactly the worker. Thereafter, such insistence may lead to abuse or even embezzlement of computing power for the benefit of malicious miners. To preserve the functionality of PoW but also bind the miners’ signing keys with their works, we build a post-quantum PoW scheme by changing the approximate closest vector norm for probabilistic NTRUSign. Different from the schemes based on hash functions, our scheme takes signing as the proof of work where signature verification is just the evidence of block reward. We also presented a method to adjust the difficulty of signing by modifying the probability of generating a correct signature. The performance of our scheme is also analyzed theoretically and experimentally, which implies its practicability and advantages.

Keywords: Proof of work; NTRUSign; Burr distribution; blockchain

1  Introduction

Blockchain is now an important carrier of electronic money due to its advantage of tamper resistance. In addition to the field of electronic cash [1], academia [2–5] also suggests using blockchain to combat cybercrime, curb network rumors, or make the IoT (Internet of Things) more credible. Thanks to the difficulty of a hash collision, hash function-based PoW schemes are generally deemed secure and reliable for digital currencies [6]. However, Wang’s team [7] has already realized a rapid collision for MD5 (Message-Digest Algorithm 5) and SHA-1 in 2004 and 2005, which implies the vulnerabilities of other hash functions and also the fragility of most PoW. Moreover, with the advent of the quantum era, the consensus mechanism originally used in the blockchain is now facing more challenges. As explored by Zhang et al. [8], Gao et al. [9], Fernández-Caramès et al. [10], and Li et al. [11], there is a great gap between the development of blockchain and its resistance against quantum machines.

As for space occupation, the size of each block is quite limited within blockchains. Taking BTC (bitcoin) for example, a block can only be generated smaller than 1 M bytes to ensure the efficiency and security of the chain. When exploiting the hash function to achieve PoW, the node who wins the right to generate a block must write a nonce together with his reward in it. These data will inevitably cause waste of storage if the block is small. To address such issue, Xiao et al. [12] suggested replacing the hash puzzle (generating a specific hash value by changing the nonce) by solving the SAT (Propositional Satisfiability) problem as a competition, Liu et al. [13] presented a PoW scheme based on ECDLP (Elliptic Curve Discrete Logarithm Problem), while Shahriar et al. [14] exploited parallel mining instead of solo mining for PoW which also accelerated the rate of block generation.

In consideration of the aforementioned problems, we base the security of PoW on a well-studied problem named appr-CVP (approximate Nearest Vector Problem) [15] over lattice for block generation. Such a problem is provided with the merit of anti-quantum whose difficulty can also be adjusted by changing the precision of approximation. Thanks to the reduction between NTRUSign (Signature Protocol of Number Theory Research Unit) and appr-CVP, we take signing as the proof of work to testify the right of block generation. Combing the processes of signing with mining also brings about a significant property that the bookkeeper cannot usurp unauthorized computing powers unless exposing his secret key. To mimic the capacity of dynamic block generation rate as in bitcoin, our scheme is capable of controlling the probability of signing success for NTRUSign [16]. The core concept of our scheme is to carry out signing and mining at the same time, implying that the miners’ signing keys are bounded with their works and their reward records can be omitted in blocks. Besides, the signatures can be verified in batches, thus the authenticity of the block can also be quickly verified without tracing the sources along with the hash values block by block.

It is worth mentioning that our scheme is not a trivial combination between PoW and NTRUSign. In the original NTRUSign scheme, the author only estimated the success rate of signing, without any detailed analysis of the range probability for correct signature. Based on NTRUSign, we carefully analyzed the distribution of the signing success and exploit such distribution to construct our scheme which replaces the hash puzzle. During the process of derivation, we used the joint distribution of multiple independent exponential distributions to manipulate the distribution parameters after signing, thus the parameters can be well-fitted via burr distribution [17] in the gamma function family. We also programmed the entire signing process in C language to verify the reliability of such distribution. Based on mathematical analysis, the cumulative probability function of the burr distribution [18,19] was practically used to select the parameters which coordinate with an expected workload, as verified in our experiment.

For clarity, we will first take BTC as an instance to present related concepts of PoW as well as the construction of NTRUSign.

PoW:The PoW technology used in Bitcoin was proposed by Satoshi Nakamoto to ensure that the distributed system can achieve even unification in an untrusted environment. Within each Bitcoin block, the hash value of all transactions needs to be included as the root of a Merkle tree [20] together with a nonce, the hash value of its parent block, and some parameters such as timestamps.

To pack a block according to the protocol, each node should calculate the hash value of the block header appended with a nonce. When the generated hash value is smaller than a certain value, the packaging will succeed. During the packing process, a specific threshold can be designated to ensure the difficulty of packing, which is related to blocking speed due to the uniform distribution of output hashes.

The primary reason for choosing the hash puzzle as the way of block generation is because the hash function is irreversible and collision-resistant while summarizing the data. The anti-collision feature can mainly be described as: for a message A , the hash operation H returns a←H(A) , while the probability of finding another message B with the same value is bounded by P(H(A)=H(B)|A≠B)<1/2256 . Therefore, to construct a valid hash value, the adversary can only resort to exhaustive enumeration. In BTC, the problem of scrambling for accounting rights is solved by the above characteristic of the hash puzzle. Suppose that we use SHA-256 to generate a hash value with n prefixed 0 bits, then each participant can only exhaust the random nonces to achieve a valid hash value since the probability is just 1/2n , it can be seen that it is almost impossible for two participants to complete the puzzle at the same time while completing for accounting right.

NTRUSign: The scheme of NTRUSign was proposed by Hoffstein, based on the approximate nearest vector problem over a lattice. It maps a message digest to a random point in a 2N -dimensional space and solves the appr-CVP problem by finding its nearest lattice point. Thus, lattice point can be used as the signature. The authenticity of the signature can be verified by estimating the distance between the coded message and the signature.

In Hoffstein’s scheme, the signer can use the shortest vector basis as his private key and easily find the nearest lattice point via this basis [21]. The public base is an inferior base with a Hadamard ratio of less than 0.1 after elementary transformation, which is can be deemed as the verifying key. It is NP-hard to solve appr-CVP under the inferior base that the verifier cannot forge the signature but quickly verify it. The security of NTRUSign was also proofed in different situations in Hoffstein’s paper.

To generate the signature, we use rounding to map the message digest on the rational field to obtain an approximate lattice point. The error of the rounding is the distance to detect whether the signature is valid. Using the Euclidean center norm for expression, we found that though the discarded signatures obey gamma distribution as a whole, specific distributions are still different. In the next chapter, we will introduce the mathematical background and solve the above problem of distribution in Chapter 3, then use gamma distribution to achieve controllable probabilistic signatures.

2  Mathematical Background

The protocol suite of NTRU works over the quotient ring R/qR , for R=Z[X]/(XN−1) . There are two polynomials f∈R,g∈R whose orders are N−1 and can be mulitiplied via

f∗g=∑k=0N−1(f⊙g)kXK∈R, (1)

where (f⊙g)k=∑i+j≡k(modN)fi⋅gj(0≤k≤N) .

For each q∈Z and h∈R , the set Mh,q={(u,v)∈R2|v≡u∗h(modq)} is an R -module of rank 2 ( Mh,q is also a lattice of 2N -dimensions) while all elements of R can be represented as f=∑i=0N−1riXi . Therefore, the length of f is naturally measure as the centered Euclidean norm of its coefficient vector that ||f||=∑i=0N−1ri2−(1N)(∑i=0N−1ri)2 . The norm imposed between two elements on Mh,q , or more generally on (u,v)∈R2 , is thus the component-wise Euclidean norm ||(u,v)||2=||u||2+||v||2 . Also, it is obvious that ||f||=1N∑i<j(fi−fj)2 .

Noting that df numbers of the coefficients in f should be set to 1 while the rest coefficients are 0. Then, the norm of it is ||f||=df(1−df/N) .

Definition 1: The real-valued function of Rn||⋅|| is a vector norm, which satisfies:

(1) Positive definiteness: ||x||≥0, and ||x||=0 only when x=0 .

(2) Homogeneity: ||kx||=|k|⋅||x|| for any k∈R .

(3) Triangle inequality: ||x+y||≤||x||+||y|| .

In our research, we will use some basic probability distributions to analyze the Euclidean center norm of the approximate shortest vector. That is to say X∼Exponential(λ) for ∑i=1NXi∼gamma(c,k) , and the probability density function of the burr distribution over the generalized gamma burr distribution is defined as

f(x;c,k)=ckxc−1(1+xc)k+1. (2)

Then we change the scale of the burr to λ to get

f(x;c,k,λ)=ckλ(xλ)c−1[1+(xλ)2]−k−1. (3)

Correspondingly, the corresponding cumulative distribution function is

F(x;v,k,λ)=1−[1+(xλ)c]−k (4)

From the next chapter, we will begin to construct the overall algorithmic inference process.

3  Algorithm Design

In this chapter, we will introduce the construction of NTRUSign in detail and analyze its probability distribution. NTRUSign’s basic operations are addition and multiplication over a polynomial ring, so the algorithm is very efficient. Meanwhile, the signature is quantum-resistant because it is based on a lattice puzzle. Therefore, the scheme is more secure than the hash puzzle in the blockchain.

3.1 The Proposed PoW Scheme Combined with Signing

Firstly, the message should also be rounded to its nearest integer. For any message a∈Q , denote [a] as the rounding of a , where [a]=a−{a} for {a}≤0.5 . Similarly, as for polynomial f , [f] and {f} are respectively obtained by carry out the the same operation on its coefficients.

The algorithm can be mainly divided into three steps, that

1) KeyGeneration : (Pk,Sk)←KeyGen(N,q,df,fg,S,t)

1. Input initial integers N,q,df,dg,S≥0 as security parameters and a state t= “standard” or “transpose”.

2. Generate S private lattice bases and one public lattice basis to execute the following process.

Let i=S , and i≥0 , then

(a) randomly select f and g∈R , where the number of 1 in those polynomials are df and dg respectively;

(b) find a pair of polynomials F,G∈R with small coefficients, satisfying f∗G−F∗g=q ;

(c) when t= "standard", set fi=f,fi′=F , while when t= "transpose", let fi=f,fi′=g , Then compute hi≡fi∗fi′(modq) ;

(d) let i=i−1 unless i=0 .

3. Release the public key Pk : h=h0≡f0′∗f0−1modq .

4. Secretly keep the private key Sk : {fi,fi′,hi},i=0,…,S.

2) Signing : (D,s)←Sign(Sk,Pk,D,U)

1. Let s=0,i=S and m=D.

2. Use the private key Sk to sign as below.

When i≥0,

(a) let x=[−(1q)m∗fi′],y=[(1q)m∗fi],si=x∗fi+y∗fi′ ;

(b) when i≥1 , let m=si∗(hi−hi−1)modq ;

(c) let s=s+si and i=i−1 until i=0 .

3. Verify the validity of the signature by computing b=||(s,s∗h−m(modq)||. If b≥U , then regenerate D to sign. And return (D,s) otherwise.

3) Verification : 1or0←Ver(D,s,Pk)

1. Compute m=D,b=||s,s∗h−m(modq)|| .

2. If b≤U , then the signature is valid and returns 1. Or else, returns 0.

According to the above signature process, it is clear that the success probability of signing is related to the Euclidean center norm of (s,s∗h−m(modq) . In the following, we will analyze the distribution of this norm.

3.2 Functional Analysis of NTRUSign’s Cumulative Probability

During the signing process, we intend to find a set of approximate vectors (x,y)∈R such that x∗(f,g)+y∗(F,G)≈(0,m) for m∈R/qR . Using the private base we can compute

(x′,y′)=(0,m)(fgFG)−1=1q(0,m)(G−g−Ff)=(−m∗Fq,m∗fq), (5)

Then, let x=[x′],y=[y′] , he has

s=[−(1q)∗m∗F]∗f+[(1q)m∗f]∗F≈(0,0) (6)

Theorem 1: If f∗G−g∗F=q and h=f−1∗g , then s∗(g,G)≡s∗h(modq) .

Proof : Since

Then, m≈s∗(g,G)≡s∗h(modq).

So, we have

||(0,m)−(s,s∗h(modq))||2=||{x}∗f+{y}∗F||2+||{x}∗g+{y}∗f−1∗G||2. (7)

To obtain the distribution of the Eq. (7), we can also assume that the distributions of X and Y are uniform distributions between (−B,B) , thus Eq. (7) can be approximately expressed as

||g||∗(∑t=1NXi2−1N(∑t=1NXi)2+∑t=1NYi2−1N(∑t=1NYi)2) (8)

According to Theorem 1, Eq. (11) can be expressed as (1/N)||a||∗∑i<jj<N(Xi−Xj)2 , for a is constant. We now know that X is a uniform distribution between (−B,B) . Let R=Xi−Xj, the probability distribution of R is

fR(r)={2(r+B)B2,−B<r<02(B−r)B2,0≤r<B. (9)

And the distribution Z=R2 can be obtained as

fz(Z)={22B−22zB2,0<z<B20,other (10)

Using the exponential distribution: f(x;22B)={22Be−22Bx,(x≥0)0,other to approximately represent the original R distribution, it can be observed that the difference between the two distributions is insignificant as in Fig. 1.

Figure 1: Z and R probability distribution(lift) and probability cumulative(right) function

Then we can approximate ||(0,m)−(s,s∗h(modq))||2 as the result of adding multiple independent exponential distributions (with different parameters). Obviously, the resulting distribution lay within the class of the gamma distribution family, so we can use the burr distribution to fit the distribution function.

According to simulation, the cumulative distribution function can be obtained as

F(U2)=1−[1+(U2/62000)22.4179]−0.0799. (11)

Therefore, when the success probability of the singing needs to be less than P , we only have to set P≤F(U2) and adjust U to control the probability of a successful signature.

3.3 Application in Blockchain

In this section, we will introduce how to control the success rate of singing by changing the threshold of U in NTRUSign’s. In summary, the probability distribution of the signature will be mainly explored.

If a participant wants to generate a legal block, he should use NTRUSign to generate a successful signature for the transaction ledger. In Fig. 2, it can be shown that if we use the NTRUSign scheme, reward records are no longer needed.

Figure 2: Block structure of hash puzzle-based scheme (left) versus Block structure of NTRUSign-based scheme (right)

In practice, the validity of the block signature should be verified before billing. Once the signature is valid, the reward record can be automatically reduced from the corresponding block (because the signing is computed by the rewarded participant), thus adding the consumption records together to generate a general ledger. The process of grabbing block generation rights is as below.

(1) Encode the data m′ and randomly generate an r by (M,r)←Encode(m′,r)

1. Divided m′ into 251 pieces that m′=m1′|m2′|…|m251′ , where | represents the cascade symbol.

2. Let mi=mi′|r and m=m1|m2|…|m251 .

3. After performing the SHA-160 operation over m , then map it to Zp to obtain the encoded data Mi′=H(mi)modp for M=∑i=0N−1Mi′Xi.

(2) Sign M as the proof of work via (m′,r,s)←SIGN(n,P,M,r)

1. Generate (Pk,Sk)←KeyGen(N,q,df,dg,S,t) .

2. According to 1/2n=P=1−[1+(U2/62000)22.4179]−0.0799 to adjust U .

3. Compute the signature as (M,s)←Sign(Sk,Pk,M,U) .

4. If the signing is successful, return (m′,r,s) , re-encode m′ or else.

For now, we have shown how to use NTRUSign to replace the hash puzzle with the same capacity of PoW. In the next chapter, we will analyze the above scheme to validate its security and corecctness.

4  Experiment and Analysis

To verify the reliability of our scheme, we should prove that the above probability function is very close to the actual experimental probability distribution.

We first employed the C language to program the signing algorithm of NTRUSign and set the security parameters as N=251,q=128,df=73,dg=71,S=0,t=″standard″ . Then, we signed 6 million sets of data and recorded the values of ||(0,m)−(s,s∗h(modq))||2 . Comparing with the burr distribution with the actual experimental data distribution we got their difference as in Fig. 3:

Figure 3: Comparison of burr distribution and experimental probability distribution

It can be seen that our predicted distribution is similar to the experimental result. When ||⋅|| is less than a certain value, their difference can be simply ignored.

To verify the accuracy of our experimental distribution, we signed 500,000 sets of data once again and counted the theoretical boundary of U according to Eq. (11) for P=1/2n . Meanwhile, the experimental results which are smaller than the boundary are also counted. As shown in Tab. 1.

The experimental results demonstrated that the theoretical success probability is slightly greater than that of actual probability. However, since the conversion rules of the two are the same, it is feasible and secure when designing the data.

5  Conclusions and Open Problems

A novel PoW scheme combind with probabilistic signing was proposed in this paper. Our scheme can not only replace the hash puzzle in blockchain but also achieved fast block verification. However, there are still some problems to be addressed in the future.

Firstly, the probability distribution of successful singing is based on a set of commonly used parameters, without considering any possible disturbance (e.g., S=0 ). Therefore, the relationship between the probability distribution and the secret key is not accurately obtained.

Secondly, this scheme has not implemented bathing signing to replace the PoW yet. With the advent quantum era, more and more probabilistic signing schemes will be based on lattices, so it is necessary to find a scheme that can perfectly fit parallel computing.

Thirdly, NTRUSign may expose the private lattice base [22] after multiple signings, which is considered the most significant flaw of it. Moreover, since the secret key of our scheme is only used to prove the workload, how to combine it with the function of transactions signing should be further studied.

Acknowledgement: We would like to express our very great appreciation to the reviewers for their detailed reviews and constructive comments. At the same time, we are also very grateful for the support of the fund project.

Funding Statement: This work was supported in part by the National Natural Science Foundation of P.R. China under Grants [61573076, 61703063, 61903053]; the Science and Technology Research Project of the Chongqing Municipal Education Commission of P.R. China under Grants [KJZD-K201800701, KJQN201900702, KJ1705121, KJ1705139]; the Program of Chongqing innovation and entrepreneurship for Returned Overseas Scholars of P.R. China under Grant cx2018110; and 2018 Team Building Project for Graduate Tutors in Chongqing under Grant JDDSTD2018001.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.