## 3 Scalable Dynamic Multi-Agent Byzantine Consensus
### Process
#### 3.2.1 Process in Pre-Prepare Stage  
A basic feature of blockchain is that all consensus nodes participate in voting and jointly maintain the global characteristics. Therefore, in the pre-prepare stage, all nodes must receive the request message that is issued by the client. A client \(c\) requests the execution of state machine operation \(o\) by sending \(<REQUEST,o,t,c>_{\sigma c}\) to the first-layer agent. \(REQUEST\) is the message that the client sends, \(o\) is the detailed operation, \(c\) is the client and \(t\) is the timestamp. The timestamp is used to ensure exact semantics for the execution of client requests. The timestamp could be the value of the client's local clock when the request is issued. The PBFT algorithm employs the broadcast approach; however, in our system, we adopt the multicast method to pass the message to the next node. Our first change to the system is made when the client sends a message to the replicas. Instead of the client broadcasting to all the nodes, the client only sends the message to \(k\) nodes, where \(k\) is the number of clusters. We define the \(k\) nodes as agent nodes. If the total number of consensus nodes \(n\) of a blockchain system is less than or equal to \(k\), there is no need to look for agent nodes hierarchically and the blockchain system can use PBFT directly. Then, the algorithm is executed up to the pre-prepare stage. At this time, agent nodes look for \(k\) -- 1 peripheral nodes as an autonomous domain. In the autonomous domain, we call these nodes an area. An area has \(k\) nodes on which to execute the prepare stage and the commit stage of the PBFT algorithm. The agent nodes will send message \(<<pre-prepare,v,n,d>_{\sigma p},m,p>\) to the area, where \(v\) is the current view number, \(n\) is the sequence number, \(m\) is the client's request message, \(d\) is \(m\)'s digest, and \(p\) is the primary node. When replica \(i\) accepts the message, the agents will record the number of agreements with the primary. Figure 3 illustrates the execution of the SDMA-PBFT algorithm when \(k\) is 4. Another task of the agent is to send the pre-prepared message to the next layer and record the id of the agent node. All agent nodes perform the same operation until no consensus node exists. The agent nodes are dynamically selected while a multi-fork tree is generated. Each agent node acts as the primary node by broadcasting the message to its area and as an agent by transferring the request message to the next layer. According to the above concept, we put forward the SDMA-PBFT algorithm in the sending message and pre-prepare stages. The detailed algorithm is presented as Algorithm 1. According to the above algorithm, the choice and layer of the agent have an important impact on the system performance and implementation. At the same time, agents must recycle the voting results. We use an array agent [_layer_, _number_] to represent the agent set, where _layer_ is the number of layers in a blockchain system and _number_ is the total number. To achieve the goal of extension, we use the dynamic spanning tree algorithm and take the root node as the agent node. A schematic diagram of the spanning tree is shown in Figure 4.  
```
0: a client node, \(n\) consensus nodes, multicast algorithm, the size of the area \(k\)
0: agreement results
1:begin // layer processing
2:if\(k\geq n\)
3: run PBFT algorithm directly;
4:else client sent request message to \(k\) agent nodes;
5:for\(i=1\) to \(n\) do
6: set agent to be the set of all nodes that can execute at this layer;
7:while agent is not empty
8: do PBFT(area\({}_{i}\)) for all clusters in this layer;
9: agent sends Pre-prepare message to the next layer;
10:until agent is empty;
11:endwhile
12: load balance transaction using the method of decomposing clusters, which makes nodes maintain load balance;
13:endfor
14:end

Figure 3: Pre-preparation process of the scalable dynamic multi-agent hierarchical PBFT algorithm. Then, we present a multicast algorithm that meets the PBFT conditions in the multicast application.