# A Blockchain Network Communication Architecture Based on Information-Centric Networking
## 5 Method Analysis
### Domain Gateway Node Selection Algorithm
#### 5.2.1 Time Complexity Analysis  
We evaluated the communication overhead of the domain gateway node selection algorithm for different types of actual network topologies, which is also reflected in the time complexity of the algorithm. The communication overhead of the algorithm mainly comes from the upstream and downstream message information between nodes (gateway request messages and proxy confirmation messages), as well as the communication overhead of the PBFT algorithm. Assuming there are \(n\) nodes in the domain network, for the PBFT algorithm, each node needs to send \(n-1\) messages to other nodes. In the absence of Byzantine faults, the algorithm's time complexity of PBFT is \(O(n^{2})\). Based on the support of ICN multicast technology among intra-domain ICN nodes, unicast between nodes can be optimized through multicast, reducing communication overhead and making the time complexity \(O(n)\). For star-shaped network topology, there is only one core layer node, and the communication cost for upstream and downstream message exchange is \(2(n-1)\). The time complexity is \(O(1)\). Adding the time complexity of the PBFT algorithm, the total time complexity is \(O(n)\). For a tree-shaped network topology, assuming the height of the tree is \(H\) and the width of each layer of the tree is \(W_{h}\), where \(h=1,2,\ldots,H\), the relationship with the number of network nodes \(n\) is \(n=1+\sum_{h=1}^{H-1}W_{h}\). For convenience, we assume that the width of the tree under a specific height \(h\) is the same, denoted as \(W_{h}\). The total number of upstream and downstream message exchanges that each layer of nodes needs to send to the downstream nodes is as follows:  
\[\text{Layer }0:MSG_{0}=n-1\]  
\[\text{Layer }1:MSG_{1} =w_{1}\cdot\frac{n-1-w_{1}}{w_{1}}\] \[=n-1-w_{1}\] \[\vdots\]  
\[\text{Layer }h:MSG_{h} =n-1-w_{1}-w_{2}-\ldots-w_{h}\] \[=n-1-\sum_{h=1}^{H-1}w_{h}\]  
Therefore, the total communication cost for upstream and downstream messages is  
\[MSG_{\text{all}} =MSG_{0}+MSG_{1}+\ldots+MSG_{H-1}\] \[=(n-1)+\sum_{h=1}^{H-1}(n-1-\sum_{h=1}^{H-1}w_{h})\] \[=H\cdot(n-1)-\sum_{h=1}^{H-1}(\sum_{h=1}^{H-1}w_{h})\]  
furthermore,  
\[H\cdot(n-1)-\sum_{h=1}^{H-1}(\sum_{h=1}^{H-1}w_{h})\leq H\cdot(n-1)\leq H\cdot n\]  
Therefore, the communication cost between intra-domain ICN nodes does not exceed \(2H\cdot n\). Since \(H\) represents the maximum depth of the tree-like network, and the depth of tree-like networks in real networks is generally small, the time complexity of the local betweenness centrality evaluation algorithm for domain gateway nodes is \(O(n)\). The overall time complexity is \(O(n*m)\), which is \(O(N)\), where \(m\) is the number of partitions in the network and \(N\) is the total number of nodes in the network. Compared to the \(O(N^{2})\) time complexity of the BCBPT algorithm [37] for partition selection in other blockchain networks and the \(O(K\cdot N)\) time complexity of the GPSC algorithm [36] improved by K-means, the time complexity of the domain gateway node election algorithm is lower, requiring smaller communication costs. Although the algorithm has a lower time complexity and communication overhead, it is more suitable for layered network topologies such as star and tree topologies. In the case of a ring network topology, there may be a situation where domain gateway nodes cannot be selected in the early stage, because voting based on the PBFT algorithm provides a fault tolerance of \((n-1)/3\). The relationship between the total number of nodes \(n\) and the number of malicious nodes \(f\) is \(n>3f\), so more than \(2f+1\) nodes are required to vote, in order to select a domain gateway node. This means that if the number of downstream nodes of a candidate node does not exceed \(2f+1\), a consensus cannot be reached to select a domain gateway node.