A Flexible $n/2$ Adversary Node Resistant and Halting Recoverable Blockchain Sharding Protocol

If people are inside of a forest recording the time when trees fall to the ground, there is no need for everyone in the forest to hear and record every fall to maintain the fairness and integrity of the record. The fact that a tree falls and the time when a tree falls is correct when it is recognised by most people around the tree, assuming these people have not colluded. With a sufficient number of people, if they are assigned randomly and distributed to subareas in the forest and are relocated time by time to avoid the accumulation of adversary power, collusion is hard to happen (expected to occur in hundreds of years).

In particular, this proposal is secure when (1) only people assigned to a subarea of the forest can record the information about this subarea. (2) No person can control or predict which subarea they will be assigned to. (3) The assignment follows a globally recognised rule, not by the arbitrary willing of some specific group of superior people. (4) People are periodically reassigned. (5) The number of people in every shard is a sufficient size.

When people assume there is a sufficient number of people acting honestly; people would only need to check what is the typically recognised time of falling for a tree of their interest from the subarea where this tree belongs. It is not necessary for themselves to hear the falling. In this regard, people do not need to have excellent hearing ability when the forest is dense. Instead, they only need to focus on monitoring the subarea in which they are assigned to.

The challenges in this model are as follows: (1) How to distribute people to subareas in a decentralised and unpredictable way? (2) How can people determine if a record of a subarea is made by people assigned to that area? (3) Without monitoring what happened in a subarea, how can people outside know if the majority of the population in that area support a record or not? (4) How large is a population and how many subareas does the forest need to make a "collusion" unlikely to happen?

Assuming there exist methods to solve all or some of these challenges above, we calculate the probability of a "collusion" to happen. The probability of obtaining no less than X adversary nodes when randomly picking a shard sized m (m is the number of nodes inside the shard) can be calculated by the cumulative hypergeometric distribution function without replacement from a population of n nodes. Let X denote the random variable corresponding to the number of adversary nodes in the sampled shard. The failure probability for one shard is at most:

$$Pr[X>[m/2]]=\sum^{m}_{X=[m/2]}\frac{(^{t}_{X})(^{n-t}_{m-X})}{(^{n}_{m})}$$

(1)

which calculates the probability that no less than X nodes are adversary in a shard sized m and the adversary has t number of nodes globally in a system of n nodes. Rapidchain ²¹ is designed with this failure probability.

Figure 1 shows the maximum probability to fail with $n=2000$ and $m=n/s$ where s is the number of shards.

As can be seen from the result, the system has a very high failure chance when the adversary taken $n/2$ of nodes. The high failure probability is the main reason why most Blockchain sharding approaches can only withstand up to $n/3$ of nodes being evil, and the shard size must be enormous.

We proposed a $n/2$ adversary node resistant Blockchain sharding approach ²³ using a different Hypothesis to build the model. In this hypothesis, nodes are juries inside the courtrooms, and a sentence is made when more than a pre-defined T number of people inside the jury sized m reached a consensus, $T>\frac{m}{2}$. In order to make the sentences convincing, people inside the jury come from different occupations; united they represent the whole of society. Assuming the rule says a jury should have five people, a teacher, a social worker, a doctor, a businessman, and a police officer. There are five teachers, five social workers, five doctors, five business-people and five police officers for five juries to run in parallel. The Jury hypothesis is different from the Forest hypothesis because if the adversary controls two doctors, they cannot live inside the same jury. However, they can be inside the same sub-area of the forest when recording the time of the tree falling.

The challenge of the Jury hypothesis is (1) How to give every node a different occupation; and (2) How to make the nodes equally divided into different occupations.

Let there be a shard acting as the court office which in charge of Jury schedule arrangement. We refer a pending person as the person who reported to the court office but has not been assigned to a court. Pending people can claim their occupations when reporting to the court office, and they cannot change the occupations once they are assigned into a court. The court office periodically publishes the number of pending people in every occupation. Line up the number of pending people in every occupation in ascending order of the time when they claimed an occupation. Every time there comes F pending people in every occupation, the front F people in every occupation is added to the courts. In the meantime, F more courts are formed, and all the jurors are reassigned into different courts. When assigning people, the court office can also be seen as a court. Namely, every time the juror membership is adjusted, the people inside the court office is also reassigned to other courts. If a pending person changes its occupation, it will go to the tail of the other pending queue, losing the position in the original pending queue. Thus, we expect new participants to check the pending queue of every occupation and choose an unpopular occupation to get into the courts quicker. Otherwise, they will be kept in pending status longer until other people fill in unpopular occupations. As new participants line in the shorter queues, the number of people in every occupation is automatically close to each other (tend to be equal in the long run). The person, regardless if they are inside a court or in the waiting queue, should work (generate PoWs in the case of blockchain) in every fixed time window so that the adversary who has half of the overall energy can only have half of the people in the system.

Table 1,2,3,4 and 5 show the procedure of adding people into the system. In this procedure, we rule that whenever there are at least four pending people in every occupation, the adding starts ($F=4$). Table 1 shows the pending queue published by the court office in moment one. Table 2 shows the pending queue when the adding conditions are met after moment one and before moment two. Table 3 shows the pending queue in moment two. Table 4 shows the people in the court system at in moment one. Table 5 shows the people in the court system at the moment two where some new people are added.

As can be seen from the adding procedure, if the adversary is not in a very long pending queue, there is no gain for the adversary to change the occupation once it reports to the court office. If it does so, it goes to the tail of another queue, leaving its original place to others. With a sufficient number of participants, only an insignificant number of people will be left outside the system eventually.

Table 6 shows a court schedule table for five courts run in parallel with the jury sized five (five people in different occupations). A refers to an adversary person. H refers to an honest person.

For a s number of courts to be held in parallel, there is an s number of people in each occupation. To manipulate a sentence in of a court, the adversary must gain control of at least T people inside this court. Because the adversary not having more than $\frac{n}{2}$ of people globally and $T>\frac{m}{2}$, so

$$T\times s>t$$

(2)

where t is the number of adversary persons. If the adversary has $A_{i}$ number of the person in occupation i; then the chance for the adversary to secure a manipulated sentence is (assuming it place all the adversary person in the front T occupations):

$$Pr[T]=\prod_{i=1}^{T}\frac{A_{i}}{s}$$

(3)

To derive the maximised value of $Pr[T]$, we want $\prod_{i=1}^{T}A_{i}$ to be maximised because s is the same number (every occupation has s people inside the system). If the adversary has t number of people inside the system (Court Jury Schedule), then

$$t=\sum_{i=1}^{m}A_{i}$$

(4)

To let the value of $\prod_{i=1}^{T}A_{i}$ maximised, we consider

	$\displaystyle A_{i}$	$\displaystyle=\lceil(t/T)\rceil,\quad i\in[1,t\bmod T]$		(5)
	$\displaystyle A_{i}$	$\displaystyle=\lfloor(t/T)\rfloor,\quad i\in(t\bmod T,T]$		(6)

This scenario is maximised because given any positive Integer $X$,

$$X\times X>(X-1)\times(X+1)=X\times X-1$$

(7)

Thus,

$$Pr[T]_{max}\approx(\frac{t}{T\times s})^{T}$$

(8)

Though the adversary cannot manipulate a sentence when it does not have T people inside a shard, it can halt a sentence to be reached when it has m-T+1 number of the nodes in a shard. This sentence cannot then be made until the next court (the group of juries is re-selected). Thus, to make the system function more smoothly, we want $T\approx[m/2]$ whilst meeting the security threshold (e.g., $10^{-6}$ failure chance). Figure 2 shows the maximum failure chance with different s,$n=s\times m=2000$, $T=0.7\times m$ and $t=1000$ ($1/2$ fraction of the overall population).

Comparing Figure 1 and Figure 2, the $Jury$ hypothesis largely outperforming the $forest$ hypothesis even when there are $n/2$ of evil nodes in the $Jury$ hypothesis and only $n/3$ of evil nodes in the $forest$ hypothesis. When $n=2000$, if maintaining a $10^{-6}$ failure chance, $Jury$ ($n/2$ evil nodes) can have 33 shards at the same time, while $forest$ ($n/3$ evil nodes) can only have 10 shards.

The system as a whole is halted when the adversary took $s\times(m-T+1)$ of nodes, and it places all of these nodes into the same $m-T+1$ occupations. In this scenario, it is guaranteed that the adversary has $m-T+1$ of nodes inside every shard. Table 7 shows a example of a system halting, where $m=5$ and $T=4$, the adversary took $m-T+1$ number of nodes in every shard.

Because the court office (the shard which deals with the node membership) is also stopped from generating further blocks that can be approved by $T$ people inside it, the pending nodes cannot be added to the system. Thus, though the $n/2$ Blockchain sharding method secured the system from tampering when the adversary is below $n/2$, the system can stop functioning anymore when $s\times(m-T+1)$ of nodes are evil.

We use a new hypothesis named colour Hypothesis. It is ruled that every node should claim a colour from the colour spectrum when joining in the system — every node inside a shard is categorised to its closet base colour. If there is a m number of nodes inside a shard, then there is a m number of base colours globally which together represent the colour spectrum as a whole. The same as the Jury Hypothesis, a consensus of a shard should be approved by at least a pre-defined T people (T must larger than $0.5\times m$) inside this shard. Figure 3 shows the example of the base colour. Every base colour should have the same number of nodes inside. This hypothesis is different from the jury Hypothesis, the jury Hypothesis requires a fixed number of occupations, however this hypothesis can regroup a colour to a different base colour base on the change of the number of base colours.

The challenge of colour Hypothesis is to make the number of nodes in every categorisation the same as each other, especially with the rapid changes of the number of base colour.

Assuming the adversary has a $t=\frac{n}{2}-1$ number of nodes. The chance for the adversary to take control of a shard in a system which has n nodes, $m$ base colours and $s$ number of shards ($s=n/m$) is:

$$Pr[T]_{Max}={(\frac{t}{T\times s})}^{T}={(\frac{t/T}{n/m})}^{T}\approx{(\frac{m}{2\times T})}^{T}$$

(9)

As can be seen from Figure 4, T can be adjusted by the number of m when maintaining a fixed threshold failure chance. When m is over $800$, $T/m$ is very close to $0.5$ (the adversary needs to take approximately $n/2$ of nodes to halt the system). We aim to dynamically adjust m to increase the difficulty for the adversary in deadlocking a shard.

We run a committee to deal with the membership issues (the same to the court office in Jury Hypothesis). The new nodes report to the committee and wait for the assignment by the committee. The committee’s block contains two sections.

• •

  Pending node section.The node information of nodes which reported to the committee before but have not yet assigned to a shard.

• •

  Member node section. The node information of nodes inside each shard.

When a node wants to join the system, the node will check the information in the Pending node section and the information in the Member node section. It then selects a colour code that is more likely to be added to the system. It then tells the committee the colour code it chooses and its public identity key. When a node’s information is added to the Pending node section, it needs to continuously send one PoW to the committee per iteration to maintain its spot in the section until it is assigned. After the node is assigned to a shard, it also needs to present one PoW per iteration. In this way, we prevented the node simulation problem: if the adversary has $50\%$ of the overall power, it can only simulate $n/2$ of nodes. The system will add the pending nodes to make the number of shards fulfilling the current workload. There is a number of pending transactions indicated in the block header of every shard. We pre-define a standard workload K which is also written in the block header of every shard. When the pending transaction of a shard exceeds 2K there should be one more shard added to the system. If the pending transaction is below $\frac{K}{2}$, then the system should cut this shard. In this way, a shard has at least K/2 workload and at most 2K workload.

Let there be $m=\frac{n}{s}$ colour categorisations (base colour) currently.

Let

$$mt=\frac{n+snp}{st}$$

(10)

where st is the ideal number of shards in the system based on the current workload, snp is the number of pending nodes that should be added to the system for the system to achieve st number of shards (snp can be zero) and mt is the number of colour categorisations corresponding to that situation. Find a snp number of nodes from the pending nodes that after adding these pending nodes, there can be st number of shards with each shard sized mt. If such snp number of nodes are found, then the shard number is adjusted to st, and the selected nodes are added. The deselected nodes remain in the pending section. If there is more than one snp possible, then it should select the largest snp.

If a node inside a shard did not show a PoW in an iteration, it is labelled as offline, and this information is written into the next block header of that shard. All the shards (including the committee) synchronise the block headers of the blocks in other shards, and these blocks should have at least T approvals in the relevant shards. Then, the committee updates its Member node section using such information. When a block of a shard is not approved by at least T people inside this shard in a fixed time frame (e.g., 10 minutes), the block is abandoned. The leader of the next block height will create a new block, and people will vote again for this new block. If the shard cannot reach a consensus in a longer fixed time frame, the shard is halted. All shards know if a shard has halted because they sync the qualified block headers of other shards and the block of the committee. If a shard is halted, the membership of all shards is rearranged (without adjusting the shard number).

If the system is halted (every shard is halted for a fixed time, at the same time), then the nodes use the node information in the committee’s latest block to calculate a st<s that can make every base colour of a st number of base colours contains $mt$ number of nodes. If such snp is not found, then the shard size is directly reduced to one (all the nodes are inside the same shard). If there exists a snp (snp can be zero), then the system is rearranged to st number of shards. By adjusting the number of colour categorisations, we bring more nodes to shards, so that T is respectively reduced. At the extreme, when the shard size is one, the system can withstand the adversary that has a n/2-1 number of nodes. Especially if it is $s=1$, then there is no colour categorisation restriction (number of nodes inside every categorisation can be different). When the system recovers from the halting problem, the shard number can then be increased base on the data flow again. Figure 5 shows an illustration of the model.

We refer to the committee as Shard 0, and other shards also have their unique shard id. When assigning/rearranging nodes, let $C_{Hash}$ be the block header hash of the latest block (including the signatures of the nodes) that has been approved by at least T number of nodes in the Shard 0. Let ID[i][j] be the public identity key of the node in colour categorisation i in the j shard. Let ’hash’ be a hash function that returns a $2^{256}$ Integer, calculate a RID, where

$$RID[i][j]=C_{Hash}\ hash\ ID[i][j]$$

(11)

Rank every public key in ID[i] by the ascending order of RID[i] and then the new assignment will be completed.

Rank all the nodes in the Pending node section and nodes in the Member node section together into a list by the increasing order of their colour code. If node $x$ is originally from the Pending node section then $D(x)=1$, otherwise $D(x)=0$. Let $F[x][y]$ denote the node assignment scheme for grouping nodes which are selected from the front $x$ nodes in the ranked list; each group should have y people inside it.

$$F[x][y]=Max(F[i\in[y...x-y]][y],select(i,x,y))$$

(12)

where select is a function that takes y number of nodes from the node i to node x. The selection rule is: (1) if $D(x)=0$ then the node x must be selected. (2) Node x should be selected instead of node x1 if node x has been continuously written in the ’Pending node’ section longer than node x1. $Max(a,b)$ is a function that: (1) calculates the number of nodes from the pending node section in assignment scheme a and b; and (2) returns $a$ or $b$ which has a larger number in the step (1).

After the iterations, the assignment scheme in $Max(F[st..n][st])$ is the new node assignment scheme. If such an assignment scheme does not exist, we do not add the pending nodes into the system in that round of the mining game. If the system is halted, then the colour categorisation is automatically re-grouped to $Max(F[ss..n][ss])$, where ss is the largest one in ss<s that make a $F[ss..n][ss]$ exist. The system then automatically re-arranges people following the rule discussed in the model section. In this way, the system will eventually recover from the halt, at the extreme, when $ss=1$.

Let the block header hash of shard i in the block height BH be Blockhash[i][BH]. $L_{i}$ is the index number of the random leader of a shard i in BH+1

$$L_{i}=hash(Blockhash[i-5][BH],...,Blockhash[i+5][BH])\ mod\ m$$

(13)

Specially,

$$Blockhash[j][BH]=Blockhash[abs(NS-j)][BH],j\in[-4,0]\cup[NS+1,NS+4]$$

(14)

If the shard i did not reach a consensus on the block height $BH$ then

$$Blockhash[i][BH]=Blockhash[i][BH-1]$$

(15)

When the leader proposed a block Bob, all the nodes inside the shard will sync Bob and do the verification. If they approve Bob, they will sign Bob using their private identity key and attach a PoW which fulfils the difficulty they claimed before. If a node does not approve Bob, it will not send the signature, but it still needs to send the PoW. When a block receives a higher than T number of signature as well as the corresponding PoWs, then this block (Bob) is approved. If a node did not show the PoW, then this node is considered offline and its info is written to the block header of the next block. Later this node’s information will be synchronised by the committee, and this node is erased from the ’Member node’ section.

A detect then verify mechanism is used for the global synchronous. The nodes of a shard will inform other shards when more than T nodes approved a block of this shard. Then the nodes of the other shards will download the block header of this block. If a node in this shard is opposing this block, it will inform the other shards. When a conflict is detected, the honest nodes in this shard will send the signatures of this block to the other shards for verification. Other shards will accept this block if there are at least T number of signatures signed by different nodes in this shard. If there is no conflict reported within a given time frame, then other shards will recognise this block as a finally accepted block of this shard.

All shards can simply verify the signatures received to determine the genuine because all nodes sync the block of the committee; they know all the public keys of nodes. To prevent the adversaries from causing additional verification, the node which sends the global consensus information should sign the data using its private key. In this way, the dishonest node can be labelled as offline directly after the verification.