Before we present a security analysis for PoAS, there are some specific security threats for distributed algorithms, such as anonymity and double spending attack, are worthy of consideration.
Anonymity is related to whether the privacy of users of blockchain network can be protected under the application scenario without access restrictions. Double spending attack is one of the most troublesome challenge that digital currency needs to solve. 6.1 will give the anonymity analysis with signature matrix. 6.2 will give the double spending analysis with some comparison. 6.3 gives some explanations about performance. In particular, in blockchain systems, security analysis and throughput are always tied together and cannot be analyzed separately. Therefore, in section 6.3, we introduced the interaction between security and throughput, and did some quantitative analysis on them to prove that PoAS has an excellent performance in balancing security and throughput.
6.1 Anonymity
For our candidates were determined by signature matrix, the coalition between public key and coin-base, it is necessary to make a discussion about the security guarantee of signature matrix against malicious nodes transferring the drifting fund. To keep a safety ID-based cryptosystem, we inherit the fundamental concept of ID-based homomorphic signature model [18][19][20] to avoid private key to confront with economic threats, such as disclosed in the signing and tracing process.
Here are some processes description of security assurance with key pair. \({f}_{i}\)(i = 0,1,2,3,4,5) are viewed as some random oracles. The relationship between the processes is shown in Fig. 5.
1)Public key generation
\({{f}}_{1}\) : {address_id,address_amount}->{pk}
In this process, we chooses representative parameters of coin-base as input to distinguish the unique identity, and generate public key later used in the Trace、Sign and private key generation 2)Private key generation
\({{f}}_{2}\) : {pk,λ}->{sk}
In this process, λ was a security parameter determined by local management, combined with public key to generate a private key which is irreplaceable in asset transferring. Even if you obtained the public key, you still can't get the private key without knowing λ.
3)Sign
\({{f}}_{3}\) : {pk,sk,tx}->{\({\mathbf{t}\mathbf{x}}_{{\sigma }}\)}
In this process, whenever we capture a transaction from propagation network, we can start the Sign process with public key and private key. Then forward the signed transaction back to propagation network in (tx,\({\mathbf{t}\mathbf{x}}_{{\sigma }}\),pk) format
4)Trace
\({{f}}_{4}\) : {PK}->{ADRESS_ID,ADRESS_AMOUNT}
This process was executed in candidate selection procedure. The purpose of establishing the connection between the address and the public key is to introduce the asset scale parameter into the publisher evaluation. With the available public key, nodes can voluntarily monitor the results of publisher evaluations.
5)Verify
\({{f}}_{5}\) : {px,tx,\({\mathbf{t}\mathbf{x}}_{{\sigma }}\)}->{1.0} if valid: 1;else༚0
This process is used to determine the signature’s validity. With the given public key, a local unsigned transaction and a signed transaction, this algorithm output 1 if\({\mathbf{t}\mathbf{x}}_{{\sigma }}\) is a valid signature for this transaction, else output 0.
In conclusion, except of the invisible λ and private key, other messages are accessible for nodes in the cryptocurrency network. The attachment between public key and asset amount provides a graceful method to convert publisher selection into Satoshi selection.
6.2 Double spending
Transactions grouped into blocks, and blocks inheritance form a tree. Each branch in the tree represents a version of the current transaction history. The double spending attack comes from inconsistent state, which is caused by tree fork. In this section. We present the typical steps of double spending attack under PoAS protocol and prove its safety from two aspects:1)conditions for a successful attack 2) the economic cost
A typical successful double-spending attack can be described as following steps:
Step1. Broadcast a paid transaction message to the network.
Step2. Secret mining a branch behind the latest block away from the main chain which contained a conflicting transaction contrary to the transaction in step 1.
Step3. Waiting a period until the target of the attack believes the transaction has received enough confirmation to deliver the product.
Step4. Continue to extend the secret branch until it is longer than the main chain, then the attack is successful.
It is worth noting that because of our candidates and publisher selection mechanism, the constitution of tree can be seen as double inheritance. First, the block header of the child block comes from the father block. Second, the public key of the publisher of the child block must be contained in the signature matrix of the father block. Therefore, it is impossible to launch a double spending attack in the PoAS just as in the single inheritance tree like bitcoin——the attacker dug a certain number of blocks secretly and published them all at once. These leads to the particularity of step4.
Figure 6 illustrate the outline of double spending attack in single inheritance tree. (a)indicate the blockchain state before the attack starts. (b) red and blue represents a pair of contradictory transactions blocks and dotted blue one indicates the secret block created by attacker. (c) the main chain is still the one that contains the valid block, which means the secret chain is shorter. (d) the secret chain catches up with the main chain and become the new valid state. We illustrate the attacker's behavior of releasing the secret block by the modification from the dotted line to the solid line in (c) and (d).
In PoAS protocol, we form a tree formed by double inheritance. In Fig. 7, The solid arrow represents the inheritance between public keys, and the dotted arrow represents the inheritance hashes. Bottom block represents the initial point of a fork. The key outside the key box is the creator of this block and also the winner of last publisher selection. We also use the red and blue block to imply a pair of contradictory transactions. Most importantly, this double inheritance relation prevents attackers from secretly creating blocks and publishing them all at once like (d) in Fig. 6.
From the initial block in the Fig. 7, the red key represents the attacker, the green key represents the winner of n round and the publisher of n + 1 round. The candidate failed to be elected will starts an unveracious transaction, contained in the green block, which will be scrapped eventually. The attacker would immediately create a branch, illustrated as red block, which contains a contradictory transaction against previous one so as to spend same money twice. For the remaining nodes in the system, they would update the local cryptocurrency stat, focus on the new end of chain, after receiving the publisher’s winning message. From the above discussion, we can draw a conclusion that under the PoAS protocol, an attacker needs to meet the following conditions to launch a successful double spending attack:
1) attacker should be a qualitied candidate in the initial block
2) attacker should be a qualitied candidate in every block in the secret branch
The first condition raised the threshold of launch a double spending attack. Which means the attacker must actively participate in propagating, and lucky enough to be a candidate before launch an attack. The second condition requires the attacker to maintain the public key inheritance relationship until the secret branch longer than the main chain, even if this will increase the risk of his exposure.
6.3 Security and throughput
Before we discuss about performance, let’s clarify the concept of security in blockchain applications at first. This section will analyze the performance of PoAS with the basis of the Satoshi’s explanation about blockchain security when bitcoin published. In bitcoin system, a node will broadcast his winning massage to the network after accomplishing the proof of work. Other nodes can promptly valid this winning massage when informed. When this validation is done by most nodes, the block will be added to the main chain in the end and miners will devote themselves into new round mining. But it’s still early for the merchant to take this block for unreversed (if malicious node generates a secret branch and make it longer than the main chain, the block recorded after the fork will be invalidated). Bitcoin set a confirmation time to ensure the safety, to be specific, to wait long enough to ensure that the probability of block being reversed is low enough. For example, if the malicious node owns 10% compute power among the whole network, there needs at least waiting for 6 blocks after the birth of the current block to ensure that it has a 99.99% probability of not being reversed. In other words, if the main chain exceeds 6 blocks of the secret branch, the chance of the secret branch catching up with main chain will be less than 0.02%.
With some presupposition of security of blockchain, we can then focus on the relationship between security and throughput. It’s can be known from the [3] and [10] that throughput is determined directly by only two parameters, one is the block size, another is the extension rate of main chain. Block size is the number of transactions contained in a block, and it’s obviously that the larger the block, the higher throughput of the system. However, overlarge block will cause greater propagation delay, which will induce forks occurring, and weaken the security of system ultimately. So far, we can regard security and throughput as two factors that interact with each other and should not be discussed separately. Figure 8 shows this relationship. In addition, it’s necessary to distinguish between two concepts, the extension rate of main chain and the creating rate of blocks. Extension of the main chain is the result of the system reaching the consistency, and blocks in the main chain is not easily being invalidated. The creating rate of block is only related to the collection and packing time. From this point of view, the extension rate of main chain mainly depends on the confirmation time, while creating rate of blocks is mainly determined by the way of mining.
Based on the above discussion, we used mathematical model to quantitatively analyze the relationship between throughput and security, and compared the performance of PoAS with PoW. Satoshi has given the probability model with confirmation time and successful double spending attack where p represents the probability that an honest node finds the next block and q presents the probability that attacker finds the next block(p + q = 1). The probability of the secret branch build by attacker can catch up with main chain from z blocks behind can be described as follow:
$${q}_{z}=\left\{\begin{array}{c}1 if p\le q\\ {\left(\frac{q}{p}\right)}^{z} if p>q\end{array}\right.$$
1
The attacker’s potential process should be a Poisson distribution with expected value:
$${\lambda }=\text{z}\frac{q}{p}$$
2
The probability distribution of attacker catching up with the main chain from z blocks behind is expressed as follow:
$$\sum _{k=0}^{z}\frac{{\lambda }^{k}{e}^{-\lambda }}{k!}(1-{\left(\frac{q}{p}\right)}^{(z-k)})$$
3
Therefore, the probability of system safety can be expressed as:
$$1-\sum _{k=0}^{z}\frac{{\lambda }^{k}{e}^{-\lambda }}{k!}(1-{\left(\frac{q}{p}\right)}^{(z-k)})$$
4
Since z represents the distance between main chain and secret branch, if we define T as the confirmation time and t as the average delay of main chain extension, then z can be replaced by T/t, so the safety probability can be replaced as:
$$1-\sum _{k=0}^{\frac{T}{t}}\frac{{\lambda }^{k}{e}^{-\lambda }}{k!}(1-{\left(\frac{q}{p}\right)}^{(\frac{T}{t}-k)})$$
5
For PoAS, since mining method does not affect the main chain extension rate as we mentioned in previous discussion, we can also donate p as the probability of honest node being publisher, q as the probability of attacker being publisher. So the safety probability can be expressed as formula (5) as well.
Because of the big difference of mining process between PoW and PoAS, the main factors affecting the extension rate of the main chain are also different. For PoW, the propagation delay is negligible compared to the hash calculation, so we only considerate the calculation time when analyze the extension rate of main chain. For PoAS, since the signature matrix is introduced to replace the time-consuming hash calculation, the block size scales up which prolong the propagation delay. Therefore, we only consider the propagation delay when discussing the extension rate of the main chain. Under this presupposition, we can analyze the relationship between security probability and confirmation time when attacker owns different proportions of resources.
(1) PoW
When the difficulty of hash calculation is set to t (min/block), the propagation delay is negligible compared with t, then confirmation time T = z*t, that is, z = T/t. the probability of safety can be described as formula (6)
$${Pr}_{pow}=1-\sum _{k=0}^{\frac{T}{t}}\frac{{\lambda }^{k}{e}^{-\lambda }}{k!}(1-{\left(\frac{q}{p}\right)}^{(\frac{T}{t}-k)})$$
6
(2) PoAS
Since the mining process abandons hash calculation, we use \({t}^{{\prime }}\)to represent the propagation delay, and the mining time is negligible compared with \({t}^{{\prime }}\). So the probability of safety can be described as formula (7)
$${Pr}_{poas}=1-\sum _{k=0}^{\frac{T}{{t}^{‘}}}\frac{{\lambda }^{k}{e}^{-\lambda }}{k!}(1-{\left(\frac{q}{p}\right)}^{(\frac{T}{{t}^{’}}-k)})$$
7
In order to make a more intuitive comparison between PoW and PoAS, we use t as the minimum unit of the X-axis, and obtained the following data through simulation:
Table 2. q=0.1 propagation delay is o.5t and 0.1t, the relationship between the probability of successful attack and confirmation time
Pr
T
|
\(1-{Pr}_{pow}\)
(\({t}^{\text{'}}\)=t)
|
\(1-{Pr}_{poas}\)
(\({t}^{\text{'}}\)=0.5t)
|
\({1-Pr}_{poas}\)(\({t}^{\text{'}}\)=0.1t)
|
t
|
0.2045873
|
0.0509779
|
0.0000012
|
2t
|
0.0509779
|
0.0034552
|
2.46314080243337e-12
|
3t
|
0.0131722
|
0.0002428
|
/
|
4t
|
0.0034552
|
0.0000173
|
/
|
5t
|
0.0009137
|
0.0000012
|
/
|
6t
|
0.0002428
|
8.94584136768017e-8
|
/
|
7t
|
0.0000647
|
/
|
/
|
8t
|
0.0000173
|
/
|
/
|
9t
|
0.0000046
|
/
|
/
|
10t
|
0.0000012
|
/
|
/
|
11t
|
0.0000003
|
/
|
/
|
Table 3. q=0.3 propagation delay is o.5t and 0.1t, the relationship between the probability of successful attack and confirmation time
Pr
T
|
\({1-Pr}_{pow}\)
(\({t}^{\text{'}}\)=t)
|
\({1-Pr}_{poas}\)(\({t}^{\text{'}}\)=0.5t)
|
\(1-{Pr}_{poas}\)(\({t}^{\text{'}}\)=0.1t)
|
t
|
0.6277491
|
0.4457170
|
0.0416604
|
2t
|
0.4457170
|
0.2391268
|
0.0024803
|
3t
|
0.3245841
|
0.1321111
|
0.0001522
|
4t
|
0.2391268
|
0.0739243
|
0.0000095
|
5t
|
0.1773523
|
0.0416605
|
0.0000006
|
10t
|
0.0416605
|
0.0024804
|
/
|
15t
|
0.0101008
|
0.0001522
|
/
|
20t
|
0.0024804
|
0.0000095
|
/
|
25t
|
0.0006132
|
0.0000006
|
/
|
30t
|
0.0001522
|
/
|
/
|
35t
|
0.0000379
|
/
|
/
|
40t
|
0.0000095
|
/
|
/
|
45t
|
0.0000024
|
/
|
/
|
50t
|
0.0000006
|
/
|
/
|
As can be clearly seen from the above tables and figures, if we regard the probability of being invalidated less than 0.000001 as the security threshold, when q = 0.1, the confirmation time PoW need will be 11t, the confirmation time PoAS(\({t}^{{\prime }}\)=0.5t) need will be 6t, the confirmation time PoAS(\({t}^{{\prime }}\)=0.1t) need will be 2t. When q = 0.3, the confirmation time PoW need will be 50t, the confirmation time PoAS(\({t}^{{\prime }}\)=0.5t) need will be 25t, the confirmation time PoAS(\({t}^{{\prime }}\)=0.1t) need will be 5t.
The above results clearly show that when the malicious nodes occupy the same proportion of resources, the throughput of PoAS is much higher than that of pow when the same security is required. The smaller ratio between propagation delay and the time need for hash computing, the bigger improvement with the throughput. In addition, the more resources the malicious node occupies, the more obvious in performance improvement.