# A Robust Sharding-Enabled Blockchain with Efficient Hashgraph Mechanism for MANETs
## 5 Asynchronous Intra-Sharding and Inter-Sharding Consensus
### Work Process of a Dynamic Shard
```
0:\(cTx^{j}\), the graph in the involved shard
0:\(tx^{j}\) or False
1:if the signature of the requester is valid && there is a latest _cross-shard joined transaction_ before a latest _cross-shard exited transaction_ of the requester **then**
2: Get \(beS=\{be|be\in cTx^{j}.beSet\)&& \(be.jSld\) is the ID of the shard\}
3: Retrieve the set of requester's _cross-shard joined transactions_, \(jSet\), and set of requester's _cross-shard existed transactions_, \(eSet\), from local graph
4:if\(|beS|=|eSet|\)then
5:for each \(be\) in \(beS\)do
6: Get an element \(cTx^{e}\) which \(H=be.eH\) from \(eSet\)
7: Get an element \(cTx^{j}\) which \(H=cTx^{e}.preH\) from \(jSet\)
8:if\(cTx^{e}\) not exist \(|\mid cTx^{j}.preH\
eq be.preH\mid\mid cTx^{j}.ts\
eq be.jTs\mid\mid cTx^{e}.ts\
eq be.eTs\mid\mid be.nBl\) is wrong **then return** False
9: Generate \(tx^{j}=~{}<H,jH,ISId,sId,ts>\)
10:else return False
11:else return False
```  
**Algorithm 1**\(cTx^{j}\) is verified in an involved shard. Then, \(tx^{j}\) is added to an event, updated to the graph, and sent to other involved shards and _target shard_. In this way, a two-layer tree, \(tree^{ie}\), is constructed in these shards. For example, in Figure 4, \(tree^{ie}\) is composed of \(cTx^{j}\), \(tx^{j}_{2}\) and \(tx^{j}_{3}\). \(cTx^{j}\) is the root, and \(tx^{j}_{2}\) and \(tx^{j}_{3}\) are the first validation of \(cTx^{j}\). Step 3: 2 nd validation of the requestNodes in the _target shard_ check whether the reputation values of the requester are greater than a given threshold. In the _target shard_, when the unconfirmed transactions of the requester are used, the second verification of \(cTx^{j}\) is processed via the smart contract (see Algorithm 2). In line 8, the reputation value of a requester is calculated via a sigmoid function. \(\alpha\) is set to larger than 1 in order to make the weight of recent behaviors on reputation evaluation greater than that of the past. \(\lambda\) and \(\epsilon\) are preset values. If \(rep\) of the requester is more than threshold \(th1\), the requester becomes an accounting node of the _target shard_. Otherwise, if a given time is expired, a _cross-shard exited transaction_ named \(cTx^{e}\) is generated in line 11, where \(H\) is the hash value of \(cTx^{e}\), \(preH=cTx^{j}.H\), \(ts\) is the generation  
Figure 4: The structure of \(tree^{ie}\) and \(inChain\). time of \(cTx^{e}\), and \(HBlock=null\), which is discussed later. \(ctl\) is a list of the requester's generated transactions since \(cTx^{i}\) is submitted, which will be invalid. \(cTx^{e}\) is sent to involved shards. In addition, \(tx^{a}\) is generated in line 12 and added into the blacklist of the _target shard_. ```
0:\(tree^{ie}\)
0:\(True\), or \((cTx^{e},tx^{a})\)
1: Get the root of \(tree^{ie}\), \(cTx^{j}\)
2: Get children of \(cTx^{j}\) in \(tree^{ie}\), \(cSet\)
3: Retrieve IDs \(idSet\) of involved shards from \(cTx^{j}\).\(beSet\)
4:if\(\forall id\in idSet\)&& \(id=cSet.tx^{i}.ISId\)then
5: Sequence elements in \(cTx^{j}\).\(beSet\) according to \(be_{i}\).\(preH=be_{k}\).\(eH\) and \(be_{k}\) as the previous one of \(be_{i}\)
6:for Each be in \(cTx^{j}\).\(beSet\) in ascending order do
7:\(duration=be\).\(eTs-be\).\(jTs\)
8:\(rep=\alpha\cdot rep+\frac{(be,jTs+be\cdot Te)/2}{1+e^{-\lambda}(duration/ br\cdot nBL-e)}\)
9:if\(rep>th1\)thenreturn\(True\)
10:if a given time is expired then
11: Generate \(cTx^{e}=<H\), \(preH,ctl,ts,HBlock>\)
12: Generate \(tx^{a}\) with \(pk\) as the public key of the request & \(beH=cTx^{i}\).\(H\)&\(bType=FE\) according to (3)
```  
**Algorithm 2**\(cTx^{i}\) is verified in _target shard_. Red vertexes in Figure 4 present the tree structure of root \(cTx^{i}\) in inter-sharding consensus. After \(cTx^{i}\) is updated to the graph in shard A, it is sent to involved shards, i.e., shards B and C. Nodes in the involved shards verify the behavior records of the requester in parallel (see Algorithm 1). If the records are correct, involved shards send \(tx_{2}^{j}\) and \(tx_{3}^{j}\) to shard A, referring to \(cTx^{i}\).