# BlockREV: Blockchain-Enabled Multi-Controller Rule Enforcement Verification in SDN

Authors: Ping Li; Songtao Guo; Jiahui Wu; Quanjun Zhao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Compared with the classical structure with only one controller in software-defined networking (SDN), multi-controller topology structure in SDN provides a new type of cross-domain forwarding network architecture with multiple centralized controllers and distributed forwarding devices. However, when the network includes multiple domains, lack of trust among the controllers remains a challenge how to verify the correctness of cross-domain forwarding behaviors in different domains. In this paper, we propose a novel secure multi-controller rule enforcement verification (BlockREV) mechanism in SDN to guarantee the correctness of cross-domain forwarding. We first adopt blockchain technology to provide the immutability and privacy protection for forwarding behaviors. Furthermore, we present an address-based aggregate signature scheme with appropriate cryptographic primitives, which is provably secure in the random oracle model. Moreover, we design a verification algorithm based on hash values of forwarding paths to check the consistency of forwarding order. Finally, experimental results demonstrate that the proposed BlockREV mechanism is effective and suitable for multi-controller scenarios in SDN.


---

## Body

## 1. Introduction

Software-defined networking (SDN) is more agile by means of network programming [1]. With the development of edge computing and artificial intelligence (AI) technology, AI-enabled SDN provides users with a variety of applications [2]. Compared with the classical SDN network with only one controller, multi-controller framework can provide a new type of cross-domain forwarding network architecture with multiple centralized controllers and distributed forwarding devices and has more benefits of flexibility and scalability. It can overcome some drawbacks of classical SDN, such as weak computing power, limited scalability, and high load of the single controller. Clearly, it is very important to verify the correctness of cross-domain forwarding rule execution by using cryptology primitives or statistical knowledge, which is referred to as rule enforcement verification. It ensures the validity of cross-domain forwarding behaviors and maintains perfect network status, so as to offer better service-level agreements (SLAs) for clients and meet the needs of customized services.However, multi-controller rule enforcement verification technology still faces some security challenges. First, it lacks the trust among controllers. Forwarding verification in each domain is managed by its own controller. If the controller is compromised, the entire network will be subject to single-point failure attack. Adversaries can issue false messages to deceive the controllers in other domains [3]. Second, it has less privacy protection for entities on the forwarding path. For example, the public identities of switches are easy to be selected and determined as attack targets (e.g. middle-man attack). Lack of index value protection for a forwarding path can lead to the disclosure of the switches' forwarding order [4], and the path deviation attack [5]. Third, controllers need to collect outcomes of rule enforcement generated by switches in its domain and maintain traceability, which require more storage space [6]. These operations cause heavy load and high communication consumption to controllers [7]. Execution result of cross-domain forwarding functionality in SDN is a critical factor determining the quality of service (QoS), which motivates us to study multi-controller rule enforcement verification in SDN in this paper.Recently, some verification schemes in SDN have been proposed in [8–10]. These schemes mainly focused on the verification algorithms to verify dynamic flow policies and analyze service vulnerabilities. Every change of forwarding behaviors will be checked in the real-time verification process, which increases network computing overhead. Many cryptographic techniques are used in authentication schemes [3, 5, 11, 12], such as message authentication code, hash function, and Merkle hash tree. However, these schemes increase the relative latency of the network and the overhead between switches and controllers. Moreover, they are based on the assumption that the controller is trustworthy, which is not practical in the multi-controller network.Blockchain technology provides a decentralized and distributed network, in which nodes that do not trust each other can still interact successfully [13, 14]. Many schemes [15–17] have applied blockchain technology into SDN, such as Cochain-SC scheme adopting smart contract technology in multi-domain SDN to resist against DDoS attacks. Although the existing studies in [18–20] resorted to the blockchain technology to record all network events, the design of multi-controller rule enforcement verification models still has some challenges when we combine SDN with cryptography and blockchain technology: (i) how to improve the synergistic effect between centralization in SDN and decentralization on blockchain network to optimize network efficiency and security; (ii) how to design the verification scheme to be more efficient and accurate; and (iii) how to protect the privacy of entities and flows on the forwarding path.To address the above challenges, we propose a novel secure multi-controller rule enforcement verification (BlockREV) mechanism in SDN to guarantee the correctness of cross-domain forwarding. We first leverage blockchain technology to reduce controllers’ load and provide privacy protection for controllers and switches by broadcasting transactions with their addresses rather than real identities. Moreover, we use tags as flows’ pseudonyms so that the real information of flows can be hidden. A provably secure aggregate signature scheme is designed by cryptography primitive technology to guarantee the effective verification accuracy of multi-controller rule executions. Furthermore, we present a verification algorithm to ensure the correct index of forwarding nodes in each domain through checking the address sequence of switches. The nested hash method of forward paths is used to verify the correct order of operations among domains.The main contributions are summarized below.(i)
We propose a novel blockchain-enabled multi-controller rule enforcement verification mechanism in SDN, named BlockREV. We adopt the consortium blockchain technology to provide traceability and privacy protection for forwarding operations and solve the problem of mistrust among controllers.(ii)
We provide an address-based aggregate signature scheme on cryptography primitives which is provably secure in the random oracle model. Only designated verifiers can verify signatures signed by switches on the path, so as to provide protection of entities’ privacy and index privacy.(iii)
We present a verification algorithm based on forwarding path hash values to check the consistency of forwarding order by means of comparing index values of switches in actual path with that in the configured path.(iv)
The security analysis shows that BlockREV is secure and can resist many kinds of attacks. Performance evaluation demonstrates that our proposed scheme is effective and suitable for multi-controller scenarios in SDN.The rest of this paper is organized as follows. Section2 presents some related works on rrule enforcement verification schemes and aggregate signature algorithm. In Section 3, we describe the problem statement. The construction of BlockREV is shown in Section 4, and security analysis is given in Section 5. Section 6 provides the performance evaluation and result analysis. Section 7 concludes this paper.


## 2. Related Work

In this section, we review the related works, which can be summarized into the following three aspects: rule enforcement verification schemes in SDN, rule enforcement verification schemes on blockchain, and applications of aggregate signature algorithm.


### 2.1. Rule Enforcement Verification Schemes in SDN

Rule enforcement verification process is an important stage to confirm on the correctness of the rule execution and guarantee the quality of the forwarding service in SDN. Accordingly, there are many works on the rule enforcement verification. A forwarding path verification mechanism was proposed to flag forwarding path by the controller with a custom probe packet [12]. In [10], a validation scheme, named TrustTopo, was used to analyze service vulnerabilities. Furthermore, it adopted the technology of asynchronous rollback to verify a host location and the chaotic model for link verification. In [9], the layer design between controller and network devices, called VeriFlow, achieved the real-time verification of potential violation of key network invariants with a novel incremental algorithm to verify dynamic flow policies. In [3], a multi-controller architecture was proposed with distributed rule store for SDNs with Merkle hash tree to detect rule modifications. However, these schemes increase the relative latency and overhead of controllers. In particular, checking each change of forwarding behaviors in real time results in a large amount of network computation overhead.


### 2.2. Rule Enforcement Verification Schemes on Blockchain

Blockchain is a decentralized and distributed peer-to-peer network. There are some research studies which integrate blockchain technology and SDN. In [7], the authors introduced a distributed cloud architecture based on blockchain and SDN to provide secure and low-cost computing infrastructure in IoT, in which end-to-end delay is minimized between computing resources and IoT devices. In [21], a new authentication approach was proposed using blockchain and SDN techniques to remove unnecessary re-authentications in repeated handover which is appropriate for 5G network among heterogeneous cells. In [22], a new model, called SDIoBoT, was presented leveraging SDN architecture and the blockchain technology in 5G network, in which an elliptic curve digital signature algorithm was designed to ensure non-repudiation and integrity of the communications in the model. In [17], a blockchain-enabled architecture of controllers was proposed with an efficient authentication method to eliminate the overheads of the traditional blockchain, in which the cluster structure with a new routing protocol was designed to optimize energy consumption and enhance security in IoT. However, these existing research studies do not fully consider energy consumption issues; furthermore, the security proof of cryptographic primitive algorithms needs to be supplemented.


### 2.3. Applications of Aggregate Signature Algorithm

An aggregate signature scheme compacts a signature set into one short signature to reduce the overhead of verifiers. In [23], an aggregate signature scheme based on bilinear maps was proposed firstly to reduce the size of certificate chains and message size. In the literatures on the improvements of aggregate signature schemes, there are two types: certificate-based schemes [24–26] and certificateless schemes [27–30]. In [31], the authors proposed a certificate-based sequential aggregate signature scheme, in which each node aggregates the previous node’s signature and its own information to obtain a new signature. Aggregate signature is aggregated by signers in the specified order, and the order of signers is the key factor for validation. In [32], an aggregate signature scheme based on bilinear pairings with only one designated verifier was proposed to provide privacy protection for signers, which is a certificateless scheme that does not need certificate storage and public key verification. However, sequential aggregate signature scheme is not suitable for the scenario with multiple controllers because it will expose the information of all the previous forwarding nodes and the index value of the paths. Furthermore, we need more designated verifiers in the process of cross-domain forwarding.


## 2.1. Rule Enforcement Verification Schemes in SDN

Rule enforcement verification process is an important stage to confirm on the correctness of the rule execution and guarantee the quality of the forwarding service in SDN. Accordingly, there are many works on the rule enforcement verification. A forwarding path verification mechanism was proposed to flag forwarding path by the controller with a custom probe packet [12]. In [10], a validation scheme, named TrustTopo, was used to analyze service vulnerabilities. Furthermore, it adopted the technology of asynchronous rollback to verify a host location and the chaotic model for link verification. In [9], the layer design between controller and network devices, called VeriFlow, achieved the real-time verification of potential violation of key network invariants with a novel incremental algorithm to verify dynamic flow policies. In [3], a multi-controller architecture was proposed with distributed rule store for SDNs with Merkle hash tree to detect rule modifications. However, these schemes increase the relative latency and overhead of controllers. In particular, checking each change of forwarding behaviors in real time results in a large amount of network computation overhead.


## 2.2. Rule Enforcement Verification Schemes on Blockchain

Blockchain is a decentralized and distributed peer-to-peer network. There are some research studies which integrate blockchain technology and SDN. In [7], the authors introduced a distributed cloud architecture based on blockchain and SDN to provide secure and low-cost computing infrastructure in IoT, in which end-to-end delay is minimized between computing resources and IoT devices. In [21], a new authentication approach was proposed using blockchain and SDN techniques to remove unnecessary re-authentications in repeated handover which is appropriate for 5G network among heterogeneous cells. In [22], a new model, called SDIoBoT, was presented leveraging SDN architecture and the blockchain technology in 5G network, in which an elliptic curve digital signature algorithm was designed to ensure non-repudiation and integrity of the communications in the model. In [17], a blockchain-enabled architecture of controllers was proposed with an efficient authentication method to eliminate the overheads of the traditional blockchain, in which the cluster structure with a new routing protocol was designed to optimize energy consumption and enhance security in IoT. However, these existing research studies do not fully consider energy consumption issues; furthermore, the security proof of cryptographic primitive algorithms needs to be supplemented.


## 2.3. Applications of Aggregate Signature Algorithm

An aggregate signature scheme compacts a signature set into one short signature to reduce the overhead of verifiers. In [23], an aggregate signature scheme based on bilinear maps was proposed firstly to reduce the size of certificate chains and message size. In the literatures on the improvements of aggregate signature schemes, there are two types: certificate-based schemes [24–26] and certificateless schemes [27–30]. In [31], the authors proposed a certificate-based sequential aggregate signature scheme, in which each node aggregates the previous node’s signature and its own information to obtain a new signature. Aggregate signature is aggregated by signers in the specified order, and the order of signers is the key factor for validation. In [32], an aggregate signature scheme based on bilinear pairings with only one designated verifier was proposed to provide privacy protection for signers, which is a certificateless scheme that does not need certificate storage and public key verification. However, sequential aggregate signature scheme is not suitable for the scenario with multiple controllers because it will expose the information of all the previous forwarding nodes and the index value of the paths. Furthermore, we need more designated verifiers in the process of cross-domain forwarding.


## 3. Problem Statement

In this section, we outline the system model, adversary model, and security assumption. For convenience, some important notations used in the paper are summarized in Table1.Table 1
List of notations.
NotationDefinitionGACyclic additive groupGMCyclic multiplicative groupqPrime order ofGA and GMP^Generator ofGAeBilinear pairing:GA×GA⟶GMH1⋅,H2⋅Hash functions:0,1∗⟶GAH3Hash function:0,1∗⟶ℤq∗H4Hash function:0,1∗⟶0,1∗xMaster key of the systemYPublic key of the systemiDomain serial numberjIndex value in the domainDomiIDijIdentity of the switchsijTijRegistration timestamp of the switchsijBijPartial private key of the switchsijUijPublic key of the switchsijAddrijAddress of the switchsijTagftag value of flowfPathiForwarding rules in the domainDomitxijForwarding transaction published by the switchsijoutputAddrijOutput address intxijσijIndividual signature generated by the switchsijσ˜iAggregate signature generated by the controllerciMessage concatenation operation


### 3.1. System Model

Traditional cross-domain verification solutions may result in single-point failure, high-level overhead, and high maintenance cost. Our new verification model has the following characteristics: unforgeability (compromised entities cannot cheat others by means of blockchain technology), anonymity (entities publish transactions using pseudonymous address), security (the scheme is robust for various attacks), and efficiency (compared with related verification methods, it is more effective).In this paper, our proposed verification mechanism is inspired by Bitcoin system [33] and the aggregate signature scheme with only one specified verifier [32]. We consider that basic multi-controller architecture is flat, in which each domain decorates only one controller and some switches for its local network. Controllers in different domains intercommunicate through east-west interface, and they are managed by administrator which serves as the master controller. Our proposed decentralized verification system model consists of four parts which are divided into application plane, block-controller plane, data plane, and management layer, as illustrated in Figure 1. Participants involved in the model will be elaborated as follows.(i)
Switches: switches in the data plane are controlled only by the controller in its domain. They are lightweight nodes with finite computing power which are responsible for forwarding flows and publishing forwarding transactions with their signatures on the blockchain. Switches are semitrusted nodes, which may be compromised by adversaries to do malicious behaviors.(ii)
Controllers: distributed controllers in block-controller plane undertake the function of maintaining the local network in their own domains. They are the core of the architecture linking applications and network hardware equipment. Every controller manages switches by means of standard southbound APIs (e.g., OpenFlow [34]) and communicates with application layer through standard northbound APIs. They act as simplified payment verification (SPV) notes on the blockchain just like that in the Bitcoin network and validate transactions published by switches in their own domains without caring for that in others.(iii)
Administrator: administrator node in the management layer is the manager of the block-control plane. It can obtain global information of multi-controller network and customize cross-domain forwarding rules for flows. Administrator node also provides a service of registration for entities and flows in the blockchain network. In addition, it is responsible for verifying the correctness of cross-domain forwarding behaviors, which is the key factor to guarantee the QoS of multi-controller network.(iv)
Verichain: Verichain is a consortium blockchain network, which stores forwarding transaction information and verifies the correctness of the enforcement of forwarding rules. It has the following functions. Rule execution message storage—Verichain stores rule enforcement messages broadcasted by entity notes. It is responsible for recording and forwarding transactions generated by switches and confirming forwarding transactions generated by controllers and the administrator. Rule execution verification—administrator and controllers are qualified to verify the correctness of rule execution results on the basis of distributed ledgers. A special design of signature algorithm in this paper ensures the validity of the verification authority. Ledger update—Verichain expands its distributed ledger with blocks and reaches consensus to record the network status of SDN in real time. By updating the ledger to record the operation behaviors of entities, the execution of flow rules in the network can be monitored.Figure 1
The architecture of BlockREV.All entities in SDN are the nodes on Verichain. The administrator is a full node and keeps the whole blockchain information. Although controllers and switches are lightweight nodes, their functions are different. Controllers validate forwarding behavior information of switches in its domain, while switches only publish forwarding transactions and are not responsible for the validation.


### 3.2. Adversary Model

The adversaryA aims to destroy rule execution behaviors and pass the verification with attacks as follows.Type 1 (Single-Point Failure Attack). The controller is a key component of the centralized domain, the compromise of which will cause serious interference in forwarding activities and reduce the availability and reliability of services.Type 2 (Middle-Man Attack). Anonymity easily leads to a middle-man attack in which the adversary may pretend to be a legitimate controller or switch to perform malicious operations.Type 3 (Path Deviation Attack). Malicious behaviors of attackers make the flows unable to be forwarded according to forwarding rules in many ways, e.g. switch bypass, path detour, and out-of-order traversal [11].In this paper, we make the following assumptions:(i)
The communication channels among entities are secure, and hash functions are one-way and collision resistant.(ii)
Administrator is an honest node managing the entire network. Controllers and switches are relatively credible, which might be compromised in a minority. Additionally, no collusion exists between controllers and switchers.(iii)
AdversaryA cannot obtain the master key of the system but can replace the addresses of legal switches.


## 3.1. System Model

Traditional cross-domain verification solutions may result in single-point failure, high-level overhead, and high maintenance cost. Our new verification model has the following characteristics: unforgeability (compromised entities cannot cheat others by means of blockchain technology), anonymity (entities publish transactions using pseudonymous address), security (the scheme is robust for various attacks), and efficiency (compared with related verification methods, it is more effective).In this paper, our proposed verification mechanism is inspired by Bitcoin system [33] and the aggregate signature scheme with only one specified verifier [32]. We consider that basic multi-controller architecture is flat, in which each domain decorates only one controller and some switches for its local network. Controllers in different domains intercommunicate through east-west interface, and they are managed by administrator which serves as the master controller. Our proposed decentralized verification system model consists of four parts which are divided into application plane, block-controller plane, data plane, and management layer, as illustrated in Figure 1. Participants involved in the model will be elaborated as follows.(i)
Switches: switches in the data plane are controlled only by the controller in its domain. They are lightweight nodes with finite computing power which are responsible for forwarding flows and publishing forwarding transactions with their signatures on the blockchain. Switches are semitrusted nodes, which may be compromised by adversaries to do malicious behaviors.(ii)
Controllers: distributed controllers in block-controller plane undertake the function of maintaining the local network in their own domains. They are the core of the architecture linking applications and network hardware equipment. Every controller manages switches by means of standard southbound APIs (e.g., OpenFlow [34]) and communicates with application layer through standard northbound APIs. They act as simplified payment verification (SPV) notes on the blockchain just like that in the Bitcoin network and validate transactions published by switches in their own domains without caring for that in others.(iii)
Administrator: administrator node in the management layer is the manager of the block-control plane. It can obtain global information of multi-controller network and customize cross-domain forwarding rules for flows. Administrator node also provides a service of registration for entities and flows in the blockchain network. In addition, it is responsible for verifying the correctness of cross-domain forwarding behaviors, which is the key factor to guarantee the QoS of multi-controller network.(iv)
Verichain: Verichain is a consortium blockchain network, which stores forwarding transaction information and verifies the correctness of the enforcement of forwarding rules. It has the following functions. Rule execution message storage—Verichain stores rule enforcement messages broadcasted by entity notes. It is responsible for recording and forwarding transactions generated by switches and confirming forwarding transactions generated by controllers and the administrator. Rule execution verification—administrator and controllers are qualified to verify the correctness of rule execution results on the basis of distributed ledgers. A special design of signature algorithm in this paper ensures the validity of the verification authority. Ledger update—Verichain expands its distributed ledger with blocks and reaches consensus to record the network status of SDN in real time. By updating the ledger to record the operation behaviors of entities, the execution of flow rules in the network can be monitored.Figure 1
The architecture of BlockREV.All entities in SDN are the nodes on Verichain. The administrator is a full node and keeps the whole blockchain information. Although controllers and switches are lightweight nodes, their functions are different. Controllers validate forwarding behavior information of switches in its domain, while switches only publish forwarding transactions and are not responsible for the validation.


## 3.2. Adversary Model

The adversaryA aims to destroy rule execution behaviors and pass the verification with attacks as follows.Type 1 (Single-Point Failure Attack). The controller is a key component of the centralized domain, the compromise of which will cause serious interference in forwarding activities and reduce the availability and reliability of services.Type 2 (Middle-Man Attack). Anonymity easily leads to a middle-man attack in which the adversary may pretend to be a legitimate controller or switch to perform malicious operations.Type 3 (Path Deviation Attack). Malicious behaviors of attackers make the flows unable to be forwarded according to forwarding rules in many ways, e.g. switch bypass, path detour, and out-of-order traversal [11].In this paper, we make the following assumptions:(i)
The communication channels among entities are secure, and hash functions are one-way and collision resistant.(ii)
Administrator is an honest node managing the entire network. Controllers and switches are relatively credible, which might be compromised in a minority. Additionally, no collusion exists between controllers and switchers.(iii)
AdversaryA cannot obtain the master key of the system but can replace the addresses of legal switches.


## 4. Construction of BlockREV

In this section, we present the construction of BlockREV mechanism. We first briefly overview the designed mechanism. Then, we present system initialization stages and forwarding process in BlockREV, respectively. At last, based on the nested hash value method and aggregate signature theory, we design the verification scheme of cross-domain forwarding.


### 4.1. Overview

Controllers and switches register through administrator to gain authority for the admittance of consortium blockchain network. They obtain their addresses and partial private keys in the registration process. These entities communicate anonymously with each other using their addresses without revealing their real identity information on Verichain. This anonymous approach provides better privacy protection. After the system initialization phase is completed, flows are forwarded by the relevant switches in the domain. When the destination node receives these flows, it sends a request to the controller for forwarding out of the domain. Then, the controller confirms whether forwarding rules of flows have been executed correctly in its domain; if so, it submits the cross-domain forwarding request to the controller in the subsequent domain. After two controllers communicate with each other, they issue forwarding instructions to the related switches, and a new round of forwarding by switches begins in the subsequent domain. In order to ensure the correctness of forwarding behaviors, the controllers and the administrator are responsible for verifying the forwarding behaviors in the intra-domain and the cross-domain, respectively.In our system, we suppose that flows will be forwarded between two domainsDom1 and Dom2. Forwarding among more domains can be inferred in the same way. When the flow f proposes a cross-domain forwarding requirement, Admin customizes forwarding rules for f which will be sent to relative controllers and switches. Verichain network stores every forwarding message in the form of transaction, and the correct forwarding actions are guaranteed by verification schemes with cryptography technology.


### 4.2. System Initialization

The system initialization process in BlockREV comprises three stages: system parameter setting, entity registration, and flow registration.(i)
System Parameter Setting. The administrator node Admin generates system parameters. Let additive group GA and multiplicative group GM be two cyclic groups with the prime order q, and P^ is the generator of GA. The bilinear pairing is e:GA×GA⟶GM. The collision-resistant cryptographic hash functions are H1,H2:0,1∗⟶GA, H3:0,1∗⟶ℤq∗, and H4:0,1∗⟶0,1∗. Admin chooses a random number x∈ℤq∗, and let Y=xP^ be the public key and x denote the master key. The system parameter is Params=GA,GM,P^,q,e,Y,H1,H2,H3,H4.(ii)
Entity Registration. The SDN structure in this paper includes multiple domains, and the i-th domain Domi includes one controller ci and several switches sij, where i is the domain serial number and j is the index of the switch in the i-th domain. Entities including controllers and switches register on Verichain through administrator node Admin. They are configured with unique partial private key for signing. Specific steps of registration of a switch are shown in Algorithm 1, in which the function Addr⋅ is a wallet address generation algorithm which is the same used in Bitcoin network. After that, Admin sends the information IDij,Uij,Tij,i,j,Addrij,Bij to ci, where IDij is the identity of switch sij, Uij is the public key of sij, Tij is the registration timestamp of sij, Addrij is the address of sij on Verichain, and Bij is the partial private key of sij generated by Admin. Then, the controller ci stores and sends this information to switch sij. The registration process of ci is similar to that of switches, except for replacing ij with i0, and Admin saves IDi0,Ui0,Ti0,i,0,Addri0,Bi0 into its entity registration list ERList, where IDi0 is the identity of ci, Ui0 is the public key of ci, Ti0 is the registration timestamp of ci, Addri0 is the address of ci on Verichain, and Bi0 is the partial private key of ci generated by Admin.(iii)
Flow Registration. There are two types of flows, single flow and multiflow, which will be configured cross-domain forwarding rules by the administrator node after registering on Verichain. Suppose that source host sends the flow f to switch s11 in domain Dom1. Switch s11 searches its forwarding list and does not find the flow f’s forwarding rules; then, it sends a cross-domain forwarding requirement to controller c1. After controller c1 has received this requirement, it sends the information vector Vf=headerf,Addr10,Addr11,Tf, to the administrator node Admin, where Tf is the registration timestamp of f. After accepting Vf, administrator node Admin computes the hash value βf=H1Vf and gets the tag value Tagf=xβf and then saves Vf,Tagf in its flow registration list. According to the global network status, administrator node Admin formulates cross-domain forwarding rules with an ordered set of addresses Pathf=∪Pathi, where Pathi denotes the forwarding rule with an ordered set of switches’ addresses on the forwarding path in Domi.We assume that the forwarding rules ares11−s12−⋯−s1m in Dom1 and s21−s22−⋯−s2n in Dom2, and the corresponding set of addresses is Pathf=Path1∪Path2, where Path1=Addr11,…,Addr1m and Path2=Addr21,…,Addr2n, m,n∈ℤ+. s11 and s21 are source switches, and s1m and s2n are destination switches in their domains. Administrator node Admin computes hpath1=H4Path1, hpath2=H4Path2, and hpathf=H4hpath2,H4hpath1. It updates its forwarding list by Vf,Tagf,Pathf,hpath1,hpath2,hpathf. Finally, administrator node Admin sends Tagf,Path1,hpath1 to c1, and Tagf,Path2,hpath2 to c2, respectively. Controllers c1 and c2 then install flow rules at related switches in their own domains through a standard control channel.When there arel flows to be forwarded with the same forwarding rules at the same time, administrator node Admin will compress their tags into a single node Tagf˜=∑i=1lTagf in the registration process, and then multiple flows will be forwarded in batch processing.Algorithm 1: Registration of a switch.
Input: IDij: identity of sij;i: domain serial number, i∈ℤ+;j: index value of the switch in Domi, j∈ℤ+;x: master key of the system;Tij: registration timestamp of sij;ERList: entity registration list;Output: Bij: partial private key of sij;(1)
sij selects a random number aij∈ℝℤq∗ as a secret value and computes its public keyUij←aijP^ and address Addrij←AddrUij.(2)
sij sends IDij,Uij,Tij,i,j,Addrij to Admin;(3)
Admin checks(4)
ifIDij∈ERList or Uij∈ERList or Addrij∈ERListthen(5)
return fails;(6)
else(7)
Admin computes: Dij←H1Addrij; Bij←xDij; Admin saves IDij,Uij,Tij,i,j,Addrij,Bij into ERList.(8)
end if(9)
returnBij;


### 4.3. Forwarding Process in BlockREV

As shown in Figure2, the forwarding process in BlockREV includes three phases: intra-domain forwarding, cross-domain forwarding, and forwarding to destination host. Specific phases are described as follows.Figure 2
Forwarding process of BlockREV.


#### 4.3.1. Intra-Domain Forwarding

In this phase, the flowf will be forwarded from source switch s11 to destination switch s1m in domain Dom1 or from source switch s21 to destination switch s2n in domain Dom2. After forwarding rule configuration of the flow f by the controller, the related switches start forwarding. After completing the forwarding, switch sij generates a forwarding transaction txij with its signature and publishes it on Verichain. An illustration of block data structure and transaction information is shown in Figure 3. The specific verification algorithm of forwarding order and aggregate signature scheme will be described in Section 4.4. When the flow f reaches switch s1m, cross-domain forwarding phase will start. After the flow f reaches switch s2n, it will be forwarded to the destination host in the last phase.Figure 3
The structure of Verichain.


#### 4.3.2. Cross-Domain Forwarding

In this phase, the flowf will be forwarded in cross-domain manner from switch s1m to switch s21 between domain Dom1 and domain Dom2. When the flow f arrives at switch s1m in domain Dom1, switch s1m sends an out-domain forwarding request to controller c1. As a domain manager, controller c1 checks whether the flow f has been forwarded correctly in its domain or not. It firstly verifies whether the order of switches in Path1 is correct in Dom1 or not. Then, controller c1 checks the validity of signatures signed in forwarding transactions by switches on the forwarding path. The specific validation process will be explained later. If the verification is passed, controller c1 aggregates m signatures made by switches in Path1 into one signature and sends it to administrator node Admin for the whole path verification. The specific verification scheme will be described later. Controller c1 publishes a confirmed forwarding transaction tx10 on Verichain; after that, c1 sends the cross-domain forwarding request of the flow f to controller c2.When controllerc2 receives the request from controller c1, it searches its forwarding list to find forwarding rules of Tagf. If it makes, controller c2 checks transactions published by controller c1 on Verichain to confirm whether forwarding behaviors in domain Dom1 have been verified by controller c1. If the confirm information in tx10 is Yes, controller c2 gives an affirmative response to controller c1 with the address information of source note s21 and dispenses the forwarding instruction to s21. Otherwise, c2 rejects and communicates the situation to Admin. If c1 receives the affirmative response from c2, it responds to s1m that f should be forwarded to s21. Then, s21 receives f and begins a new round of forwarding. The specific cross-domain communication process is shown in Figure 4.Figure 4
Cross-domain communication process betweenc1 and c2.


#### 4.3.3. Forwarding to Destination Host

In this phase,f will be forwarded from s2n to the destination host. When f reaches s2n, s2n sends an out-domain forwarding request to c2. As a domain manager, c2 verifies rule enforcement just like c1 has done. After receiving the aggregate signatures sent by c1 and c2, Admin will verify whether the cross-domain forwarding rules have been implemented correctly or not. It first checks the correctness of the forwarding node order and then verifies the validity of two aggregate signatures, respectively, to guarantee the quality of forwarding service. The specific validation process is described later. After that, Admin publishes a confirmed forwarding transaction on Verichain. When the source host or the destination host wants to estimate the correctness of forwarding behaviors in SDN to ensure the security of f in the process of transmission, he may look up the confirmed forwarding transaction about Tagf published by Admin through any full node on Verichain.


### 4.4. Validation Process in BlockREV

In this section, we design appropriate forwarding verification schemes for controllers and administrator based on the nested hash value method and aggregate signature theory. The technology of cryptography and blockchain is combined with SDN to ensure the correctness and effectiveness of the verification scheme. We will describe the verification process in two scenarios: intra-domain verification and cross-domain verification.


#### 4.4.1. Intra-Domain Validation

In the intra-domain forwarding phase, controllerci traces forwarding transactions about Tagf on Verichain, which have been published by switches in its domain. First, ci verifies whether the forwarding order of switches is consistent with that in its memory. It calculates the hash value of the public key in the subsequent transaction in order to compare the result with the output address in the current transaction. If they are equal, it concatenates the output address into Pathi. After making sure that the order of switches in all adjacent transactions is correct, ci calculates the hash value H4Pathi. By comparing it with the hash value hpathi, ci can confirm whether the forwarding order of switches in its domain is correct or not. Specific steps are shown in Algorithm 2. Second, ci checks individual signatures signed by switches in Domi and then aggregates all signatures into a single one which will be sent to Admin for cross-domain validation. The specific steps of individual signatures verification will be explained in the aggregation signature scheme later.Algorithm 2: Verification of the order of switches in Domi.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;i,k: i=1,k=m or i=2,k=n;hpathi: hash value of Pathi;Output: valid, invalid;(1)
ci traces back all txij about Tagf published by switches in Domi;(2)
Pathi←Addri1;(3)
for each j∈1,k−1do(4)
ifAddri1==AddrUi1 and outputAddrij==AddrUij+1then(5)
j←j+1;(6)
Pathi←Pathi‖Addrij+1;(7)
end if(8)
end for(9)
ifhpathi==H4Pathithen(10)
return valid(11)
else(12)
return invalid(13)
end if


#### 4.4.2. Cross-Domain Validation

In the process of forwarding to destination host phase,Admin looks over the information on Verichain and obtains all forwarding transactions associated with Tagf published by switches in different domains. First, Admin judges whether the cross-domain forwarding order of switches is correct. It verifies the forwarding order in Dom1 and Dom2, respectively, and then it verifies whether the equation outputaddr1m=AddrU21 holds or not according to the information in tx1m and tx21. If it holds, Admin calculates the nested hash value H4hpath2,H4hpath1. By comparing it with the hash value hpathf, Admin can confirm whether the forwarding order of switches in multiple domains is correct or not. Specific steps are shown in Algorithm 3. Second, Admin verifies aggregate signatures from c1 and c2 to effectively ensure the validity of the multi-controller rule enforcement verification.Our proposed aggregation signature scheme is defined by six polynomial-time bounded algorithms: Setup, Key-Gen, Individual-Sign, Individual-Verify, Aggregate-Sign, and Aggregate-Verify. Specific steps are described as follows:(i)
Setup. Admin inputs the security parameter λ and outputs the system parameter Params=GA,GM,P^,q,e,Y,H1,H2,H3,H4, where Y=xP^ is the public key and x∈Rℤq∗ is the master key.(ii)
Key-Gen. In the entity registration process, sij obtains its partial secret key Bij, and ci obtains its partial secret key Bi0.(iii)
Individual-Sign. For txij, let mij=Uij,Tagf,Tijf. sij chooses a random number rij∈ℤq∗ and computes Rij=rijP^, Hij=H2aijUi0Y, hij=H3mij,Uij, and Wij=rij+aijHij+hijBij. Then sij’s individual signature is σij=Rij,Wij.(iv)
Individual-Verify. ci is responsible for verifying signatures in its domain. For k signatures σij=Rij,Wij, 1≤j≤k, k∈m,n, ci performs the following steps:(a)
Tracing on Verichain for all operating transactions associated withTagf in Domi and judging whether the order of addresses is the same with that in Pathi, as shown in Algorithm 2.(b)
Verifying the signature ofsij on Pathi. ci calculates Hij=H2ai0UijY, hij=H3mij,Uij, and Dij=H1Addrij. Checking whether the equation(1)eWij,P^=ehijDij,Y⋅eHij,Rij⋅eHij,Uijholds or not. If it holds,ci accepts σij.(v)
Aggregate-Sign. For k accepted individual signatures σij=Rij,Wij given by distinct switches on Pathi, where i=1,k=m or i=2,k=n, ci calculates W˜i=∑j=1kWij and generates the aggregate signature σ˜i=Ri1,Ri2,…,Rik,W˜i.(vi)
Aggregate-Verify. Admin completes the verification of aggregate signatures which are generated by c1 and c2, respectively. When Admin receives σ˜i=Ri1,Ri2,…,Rik,W˜i, it performs the following steps:(a)
Tracing all the operating transactions associated withTagf on Verichain and judging whether the order of transactions is the same with Pathf, in order to ensure that the sequence of forwarding nodes is correct. The trace process is similar to that in Individual-Verify step, except for the extra validations pubkeyhash1m=AddrU21 and hpathf=H4hpath2,H4hpath1 needed to be done, as shown in Algorithm 3.(b)
ComputingHij=H2xUijUi0, hij=H3mij,Uij and Dij=H1Addrij and checking whether the equation(2)eW˜i,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij∏j=1keHij,Uijholds or not. If it holds,Admin accepts the aggregate signatures σ˜i.Because of the properties of bilinear pairings, we can conclude that the aggregate signature scheme mentioned above is correct.(3)eW˜i,P^=e∑j=1kWij,P^=e∑j=1krij+aijHij+hijBij,P^=e∑j=1kxhijDij,P^⋅∏j=1kerijHij,P^⋅∏j=1keaijHij,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij⋅∏j=1keHij,Uij.If multiple flows are assigned with the same forwarding rules simultaneously, the batch verification technique is adopted to improve the efficiency of validation operations in our mechanism. The tag of batch flows isTagf˜, which will replace Tagf in the above scheme to perform batch verification.Algorithm 3: Verification of the cross-domain forwarding order of switches.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;hpathi: hash value of Pathi;hpathf: forwarding path hash value of f;Output: valid, invalid;(1)
Admin traces back all txij about Tagf;(2)
i←1;k←m;(3)
if the result of executing Algorithm 2 is “valid” then(4)
hpath1←H4Path1;(5)
end if(6)
i←2;k←n;(7)
if the result of executing Algorithm2 is “valid” then(8)
hpath2←H4Path2;(9)
end if(10)
ifoutputAddr1m==AddrU21 and hpathf==H4hpath2,H4hpath1then(11)
return valid(12)
else(13)
return invalid(14)
end if


## 4.1. Overview

Controllers and switches register through administrator to gain authority for the admittance of consortium blockchain network. They obtain their addresses and partial private keys in the registration process. These entities communicate anonymously with each other using their addresses without revealing their real identity information on Verichain. This anonymous approach provides better privacy protection. After the system initialization phase is completed, flows are forwarded by the relevant switches in the domain. When the destination node receives these flows, it sends a request to the controller for forwarding out of the domain. Then, the controller confirms whether forwarding rules of flows have been executed correctly in its domain; if so, it submits the cross-domain forwarding request to the controller in the subsequent domain. After two controllers communicate with each other, they issue forwarding instructions to the related switches, and a new round of forwarding by switches begins in the subsequent domain. In order to ensure the correctness of forwarding behaviors, the controllers and the administrator are responsible for verifying the forwarding behaviors in the intra-domain and the cross-domain, respectively.In our system, we suppose that flows will be forwarded between two domainsDom1 and Dom2. Forwarding among more domains can be inferred in the same way. When the flow f proposes a cross-domain forwarding requirement, Admin customizes forwarding rules for f which will be sent to relative controllers and switches. Verichain network stores every forwarding message in the form of transaction, and the correct forwarding actions are guaranteed by verification schemes with cryptography technology.


## 4.2. System Initialization

The system initialization process in BlockREV comprises three stages: system parameter setting, entity registration, and flow registration.(i)
System Parameter Setting. The administrator node Admin generates system parameters. Let additive group GA and multiplicative group GM be two cyclic groups with the prime order q, and P^ is the generator of GA. The bilinear pairing is e:GA×GA⟶GM. The collision-resistant cryptographic hash functions are H1,H2:0,1∗⟶GA, H3:0,1∗⟶ℤq∗, and H4:0,1∗⟶0,1∗. Admin chooses a random number x∈ℤq∗, and let Y=xP^ be the public key and x denote the master key. The system parameter is Params=GA,GM,P^,q,e,Y,H1,H2,H3,H4.(ii)
Entity Registration. The SDN structure in this paper includes multiple domains, and the i-th domain Domi includes one controller ci and several switches sij, where i is the domain serial number and j is the index of the switch in the i-th domain. Entities including controllers and switches register on Verichain through administrator node Admin. They are configured with unique partial private key for signing. Specific steps of registration of a switch are shown in Algorithm 1, in which the function Addr⋅ is a wallet address generation algorithm which is the same used in Bitcoin network. After that, Admin sends the information IDij,Uij,Tij,i,j,Addrij,Bij to ci, where IDij is the identity of switch sij, Uij is the public key of sij, Tij is the registration timestamp of sij, Addrij is the address of sij on Verichain, and Bij is the partial private key of sij generated by Admin. Then, the controller ci stores and sends this information to switch sij. The registration process of ci is similar to that of switches, except for replacing ij with i0, and Admin saves IDi0,Ui0,Ti0,i,0,Addri0,Bi0 into its entity registration list ERList, where IDi0 is the identity of ci, Ui0 is the public key of ci, Ti0 is the registration timestamp of ci, Addri0 is the address of ci on Verichain, and Bi0 is the partial private key of ci generated by Admin.(iii)
Flow Registration. There are two types of flows, single flow and multiflow, which will be configured cross-domain forwarding rules by the administrator node after registering on Verichain. Suppose that source host sends the flow f to switch s11 in domain Dom1. Switch s11 searches its forwarding list and does not find the flow f’s forwarding rules; then, it sends a cross-domain forwarding requirement to controller c1. After controller c1 has received this requirement, it sends the information vector Vf=headerf,Addr10,Addr11,Tf, to the administrator node Admin, where Tf is the registration timestamp of f. After accepting Vf, administrator node Admin computes the hash value βf=H1Vf and gets the tag value Tagf=xβf and then saves Vf,Tagf in its flow registration list. According to the global network status, administrator node Admin formulates cross-domain forwarding rules with an ordered set of addresses Pathf=∪Pathi, where Pathi denotes the forwarding rule with an ordered set of switches’ addresses on the forwarding path in Domi.We assume that the forwarding rules ares11−s12−⋯−s1m in Dom1 and s21−s22−⋯−s2n in Dom2, and the corresponding set of addresses is Pathf=Path1∪Path2, where Path1=Addr11,…,Addr1m and Path2=Addr21,…,Addr2n, m,n∈ℤ+. s11 and s21 are source switches, and s1m and s2n are destination switches in their domains. Administrator node Admin computes hpath1=H4Path1, hpath2=H4Path2, and hpathf=H4hpath2,H4hpath1. It updates its forwarding list by Vf,Tagf,Pathf,hpath1,hpath2,hpathf. Finally, administrator node Admin sends Tagf,Path1,hpath1 to c1, and Tagf,Path2,hpath2 to c2, respectively. Controllers c1 and c2 then install flow rules at related switches in their own domains through a standard control channel.When there arel flows to be forwarded with the same forwarding rules at the same time, administrator node Admin will compress their tags into a single node Tagf˜=∑i=1lTagf in the registration process, and then multiple flows will be forwarded in batch processing.Algorithm 1: Registration of a switch.
Input: IDij: identity of sij;i: domain serial number, i∈ℤ+;j: index value of the switch in Domi, j∈ℤ+;x: master key of the system;Tij: registration timestamp of sij;ERList: entity registration list;Output: Bij: partial private key of sij;(1)
sij selects a random number aij∈ℝℤq∗ as a secret value and computes its public keyUij←aijP^ and address Addrij←AddrUij.(2)
sij sends IDij,Uij,Tij,i,j,Addrij to Admin;(3)
Admin checks(4)
ifIDij∈ERList or Uij∈ERList or Addrij∈ERListthen(5)
return fails;(6)
else(7)
Admin computes: Dij←H1Addrij; Bij←xDij; Admin saves IDij,Uij,Tij,i,j,Addrij,Bij into ERList.(8)
end if(9)
returnBij;


## 4.3. Forwarding Process in BlockREV

As shown in Figure2, the forwarding process in BlockREV includes three phases: intra-domain forwarding, cross-domain forwarding, and forwarding to destination host. Specific phases are described as follows.Figure 2
Forwarding process of BlockREV.


### 4.3.1. Intra-Domain Forwarding

In this phase, the flowf will be forwarded from source switch s11 to destination switch s1m in domain Dom1 or from source switch s21 to destination switch s2n in domain Dom2. After forwarding rule configuration of the flow f by the controller, the related switches start forwarding. After completing the forwarding, switch sij generates a forwarding transaction txij with its signature and publishes it on Verichain. An illustration of block data structure and transaction information is shown in Figure 3. The specific verification algorithm of forwarding order and aggregate signature scheme will be described in Section 4.4. When the flow f reaches switch s1m, cross-domain forwarding phase will start. After the flow f reaches switch s2n, it will be forwarded to the destination host in the last phase.Figure 3
The structure of Verichain.


### 4.3.2. Cross-Domain Forwarding

In this phase, the flowf will be forwarded in cross-domain manner from switch s1m to switch s21 between domain Dom1 and domain Dom2. When the flow f arrives at switch s1m in domain Dom1, switch s1m sends an out-domain forwarding request to controller c1. As a domain manager, controller c1 checks whether the flow f has been forwarded correctly in its domain or not. It firstly verifies whether the order of switches in Path1 is correct in Dom1 or not. Then, controller c1 checks the validity of signatures signed in forwarding transactions by switches on the forwarding path. The specific validation process will be explained later. If the verification is passed, controller c1 aggregates m signatures made by switches in Path1 into one signature and sends it to administrator node Admin for the whole path verification. The specific verification scheme will be described later. Controller c1 publishes a confirmed forwarding transaction tx10 on Verichain; after that, c1 sends the cross-domain forwarding request of the flow f to controller c2.When controllerc2 receives the request from controller c1, it searches its forwarding list to find forwarding rules of Tagf. If it makes, controller c2 checks transactions published by controller c1 on Verichain to confirm whether forwarding behaviors in domain Dom1 have been verified by controller c1. If the confirm information in tx10 is Yes, controller c2 gives an affirmative response to controller c1 with the address information of source note s21 and dispenses the forwarding instruction to s21. Otherwise, c2 rejects and communicates the situation to Admin. If c1 receives the affirmative response from c2, it responds to s1m that f should be forwarded to s21. Then, s21 receives f and begins a new round of forwarding. The specific cross-domain communication process is shown in Figure 4.Figure 4
Cross-domain communication process betweenc1 and c2.


### 4.3.3. Forwarding to Destination Host

In this phase,f will be forwarded from s2n to the destination host. When f reaches s2n, s2n sends an out-domain forwarding request to c2. As a domain manager, c2 verifies rule enforcement just like c1 has done. After receiving the aggregate signatures sent by c1 and c2, Admin will verify whether the cross-domain forwarding rules have been implemented correctly or not. It first checks the correctness of the forwarding node order and then verifies the validity of two aggregate signatures, respectively, to guarantee the quality of forwarding service. The specific validation process is described later. After that, Admin publishes a confirmed forwarding transaction on Verichain. When the source host or the destination host wants to estimate the correctness of forwarding behaviors in SDN to ensure the security of f in the process of transmission, he may look up the confirmed forwarding transaction about Tagf published by Admin through any full node on Verichain.


## 4.3.1. Intra-Domain Forwarding

In this phase, the flowf will be forwarded from source switch s11 to destination switch s1m in domain Dom1 or from source switch s21 to destination switch s2n in domain Dom2. After forwarding rule configuration of the flow f by the controller, the related switches start forwarding. After completing the forwarding, switch sij generates a forwarding transaction txij with its signature and publishes it on Verichain. An illustration of block data structure and transaction information is shown in Figure 3. The specific verification algorithm of forwarding order and aggregate signature scheme will be described in Section 4.4. When the flow f reaches switch s1m, cross-domain forwarding phase will start. After the flow f reaches switch s2n, it will be forwarded to the destination host in the last phase.Figure 3
The structure of Verichain.


## 4.3.2. Cross-Domain Forwarding

In this phase, the flowf will be forwarded in cross-domain manner from switch s1m to switch s21 between domain Dom1 and domain Dom2. When the flow f arrives at switch s1m in domain Dom1, switch s1m sends an out-domain forwarding request to controller c1. As a domain manager, controller c1 checks whether the flow f has been forwarded correctly in its domain or not. It firstly verifies whether the order of switches in Path1 is correct in Dom1 or not. Then, controller c1 checks the validity of signatures signed in forwarding transactions by switches on the forwarding path. The specific validation process will be explained later. If the verification is passed, controller c1 aggregates m signatures made by switches in Path1 into one signature and sends it to administrator node Admin for the whole path verification. The specific verification scheme will be described later. Controller c1 publishes a confirmed forwarding transaction tx10 on Verichain; after that, c1 sends the cross-domain forwarding request of the flow f to controller c2.When controllerc2 receives the request from controller c1, it searches its forwarding list to find forwarding rules of Tagf. If it makes, controller c2 checks transactions published by controller c1 on Verichain to confirm whether forwarding behaviors in domain Dom1 have been verified by controller c1. If the confirm information in tx10 is Yes, controller c2 gives an affirmative response to controller c1 with the address information of source note s21 and dispenses the forwarding instruction to s21. Otherwise, c2 rejects and communicates the situation to Admin. If c1 receives the affirmative response from c2, it responds to s1m that f should be forwarded to s21. Then, s21 receives f and begins a new round of forwarding. The specific cross-domain communication process is shown in Figure 4.Figure 4
Cross-domain communication process betweenc1 and c2.


## 4.3.3. Forwarding to Destination Host

In this phase,f will be forwarded from s2n to the destination host. When f reaches s2n, s2n sends an out-domain forwarding request to c2. As a domain manager, c2 verifies rule enforcement just like c1 has done. After receiving the aggregate signatures sent by c1 and c2, Admin will verify whether the cross-domain forwarding rules have been implemented correctly or not. It first checks the correctness of the forwarding node order and then verifies the validity of two aggregate signatures, respectively, to guarantee the quality of forwarding service. The specific validation process is described later. After that, Admin publishes a confirmed forwarding transaction on Verichain. When the source host or the destination host wants to estimate the correctness of forwarding behaviors in SDN to ensure the security of f in the process of transmission, he may look up the confirmed forwarding transaction about Tagf published by Admin through any full node on Verichain.


## 4.4. Validation Process in BlockREV

In this section, we design appropriate forwarding verification schemes for controllers and administrator based on the nested hash value method and aggregate signature theory. The technology of cryptography and blockchain is combined with SDN to ensure the correctness and effectiveness of the verification scheme. We will describe the verification process in two scenarios: intra-domain verification and cross-domain verification.


### 4.4.1. Intra-Domain Validation

In the intra-domain forwarding phase, controllerci traces forwarding transactions about Tagf on Verichain, which have been published by switches in its domain. First, ci verifies whether the forwarding order of switches is consistent with that in its memory. It calculates the hash value of the public key in the subsequent transaction in order to compare the result with the output address in the current transaction. If they are equal, it concatenates the output address into Pathi. After making sure that the order of switches in all adjacent transactions is correct, ci calculates the hash value H4Pathi. By comparing it with the hash value hpathi, ci can confirm whether the forwarding order of switches in its domain is correct or not. Specific steps are shown in Algorithm 2. Second, ci checks individual signatures signed by switches in Domi and then aggregates all signatures into a single one which will be sent to Admin for cross-domain validation. The specific steps of individual signatures verification will be explained in the aggregation signature scheme later.Algorithm 2: Verification of the order of switches in Domi.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;i,k: i=1,k=m or i=2,k=n;hpathi: hash value of Pathi;Output: valid, invalid;(1)
ci traces back all txij about Tagf published by switches in Domi;(2)
Pathi←Addri1;(3)
for each j∈1,k−1do(4)
ifAddri1==AddrUi1 and outputAddrij==AddrUij+1then(5)
j←j+1;(6)
Pathi←Pathi‖Addrij+1;(7)
end if(8)
end for(9)
ifhpathi==H4Pathithen(10)
return valid(11)
else(12)
return invalid(13)
end if


### 4.4.2. Cross-Domain Validation

In the process of forwarding to destination host phase,Admin looks over the information on Verichain and obtains all forwarding transactions associated with Tagf published by switches in different domains. First, Admin judges whether the cross-domain forwarding order of switches is correct. It verifies the forwarding order in Dom1 and Dom2, respectively, and then it verifies whether the equation outputaddr1m=AddrU21 holds or not according to the information in tx1m and tx21. If it holds, Admin calculates the nested hash value H4hpath2,H4hpath1. By comparing it with the hash value hpathf, Admin can confirm whether the forwarding order of switches in multiple domains is correct or not. Specific steps are shown in Algorithm 3. Second, Admin verifies aggregate signatures from c1 and c2 to effectively ensure the validity of the multi-controller rule enforcement verification.Our proposed aggregation signature scheme is defined by six polynomial-time bounded algorithms: Setup, Key-Gen, Individual-Sign, Individual-Verify, Aggregate-Sign, and Aggregate-Verify. Specific steps are described as follows:(i)
Setup. Admin inputs the security parameter λ and outputs the system parameter Params=GA,GM,P^,q,e,Y,H1,H2,H3,H4, where Y=xP^ is the public key and x∈Rℤq∗ is the master key.(ii)
Key-Gen. In the entity registration process, sij obtains its partial secret key Bij, and ci obtains its partial secret key Bi0.(iii)
Individual-Sign. For txij, let mij=Uij,Tagf,Tijf. sij chooses a random number rij∈ℤq∗ and computes Rij=rijP^, Hij=H2aijUi0Y, hij=H3mij,Uij, and Wij=rij+aijHij+hijBij. Then sij’s individual signature is σij=Rij,Wij.(iv)
Individual-Verify. ci is responsible for verifying signatures in its domain. For k signatures σij=Rij,Wij, 1≤j≤k, k∈m,n, ci performs the following steps:(a)
Tracing on Verichain for all operating transactions associated withTagf in Domi and judging whether the order of addresses is the same with that in Pathi, as shown in Algorithm 2.(b)
Verifying the signature ofsij on Pathi. ci calculates Hij=H2ai0UijY, hij=H3mij,Uij, and Dij=H1Addrij. Checking whether the equation(1)eWij,P^=ehijDij,Y⋅eHij,Rij⋅eHij,Uijholds or not. If it holds,ci accepts σij.(v)
Aggregate-Sign. For k accepted individual signatures σij=Rij,Wij given by distinct switches on Pathi, where i=1,k=m or i=2,k=n, ci calculates W˜i=∑j=1kWij and generates the aggregate signature σ˜i=Ri1,Ri2,…,Rik,W˜i.(vi)
Aggregate-Verify. Admin completes the verification of aggregate signatures which are generated by c1 and c2, respectively. When Admin receives σ˜i=Ri1,Ri2,…,Rik,W˜i, it performs the following steps:(a)
Tracing all the operating transactions associated withTagf on Verichain and judging whether the order of transactions is the same with Pathf, in order to ensure that the sequence of forwarding nodes is correct. The trace process is similar to that in Individual-Verify step, except for the extra validations pubkeyhash1m=AddrU21 and hpathf=H4hpath2,H4hpath1 needed to be done, as shown in Algorithm 3.(b)
ComputingHij=H2xUijUi0, hij=H3mij,Uij and Dij=H1Addrij and checking whether the equation(2)eW˜i,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij∏j=1keHij,Uijholds or not. If it holds,Admin accepts the aggregate signatures σ˜i.Because of the properties of bilinear pairings, we can conclude that the aggregate signature scheme mentioned above is correct.(3)eW˜i,P^=e∑j=1kWij,P^=e∑j=1krij+aijHij+hijBij,P^=e∑j=1kxhijDij,P^⋅∏j=1kerijHij,P^⋅∏j=1keaijHij,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij⋅∏j=1keHij,Uij.If multiple flows are assigned with the same forwarding rules simultaneously, the batch verification technique is adopted to improve the efficiency of validation operations in our mechanism. The tag of batch flows isTagf˜, which will replace Tagf in the above scheme to perform batch verification.Algorithm 3: Verification of the cross-domain forwarding order of switches.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;hpathi: hash value of Pathi;hpathf: forwarding path hash value of f;Output: valid, invalid;(1)
Admin traces back all txij about Tagf;(2)
i←1;k←m;(3)
if the result of executing Algorithm 2 is “valid” then(4)
hpath1←H4Path1;(5)
end if(6)
i←2;k←n;(7)
if the result of executing Algorithm2 is “valid” then(8)
hpath2←H4Path2;(9)
end if(10)
ifoutputAddr1m==AddrU21 and hpathf==H4hpath2,H4hpath1then(11)
return valid(12)
else(13)
return invalid(14)
end if


## 4.4.1. Intra-Domain Validation

In the intra-domain forwarding phase, controllerci traces forwarding transactions about Tagf on Verichain, which have been published by switches in its domain. First, ci verifies whether the forwarding order of switches is consistent with that in its memory. It calculates the hash value of the public key in the subsequent transaction in order to compare the result with the output address in the current transaction. If they are equal, it concatenates the output address into Pathi. After making sure that the order of switches in all adjacent transactions is correct, ci calculates the hash value H4Pathi. By comparing it with the hash value hpathi, ci can confirm whether the forwarding order of switches in its domain is correct or not. Specific steps are shown in Algorithm 2. Second, ci checks individual signatures signed by switches in Domi and then aggregates all signatures into a single one which will be sent to Admin for cross-domain validation. The specific steps of individual signatures verification will be explained in the aggregation signature scheme later.Algorithm 2: Verification of the order of switches in Domi.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;i,k: i=1,k=m or i=2,k=n;hpathi: hash value of Pathi;Output: valid, invalid;(1)
ci traces back all txij about Tagf published by switches in Domi;(2)
Pathi←Addri1;(3)
for each j∈1,k−1do(4)
ifAddri1==AddrUi1 and outputAddrij==AddrUij+1then(5)
j←j+1;(6)
Pathi←Pathi‖Addrij+1;(7)
end if(8)
end for(9)
ifhpathi==H4Pathithen(10)
return valid(11)
else(12)
return invalid(13)
end if


## 4.4.2. Cross-Domain Validation

In the process of forwarding to destination host phase,Admin looks over the information on Verichain and obtains all forwarding transactions associated with Tagf published by switches in different domains. First, Admin judges whether the cross-domain forwarding order of switches is correct. It verifies the forwarding order in Dom1 and Dom2, respectively, and then it verifies whether the equation outputaddr1m=AddrU21 holds or not according to the information in tx1m and tx21. If it holds, Admin calculates the nested hash value H4hpath2,H4hpath1. By comparing it with the hash value hpathf, Admin can confirm whether the forwarding order of switches in multiple domains is correct or not. Specific steps are shown in Algorithm 3. Second, Admin verifies aggregate signatures from c1 and c2 to effectively ensure the validity of the multi-controller rule enforcement verification.Our proposed aggregation signature scheme is defined by six polynomial-time bounded algorithms: Setup, Key-Gen, Individual-Sign, Individual-Verify, Aggregate-Sign, and Aggregate-Verify. Specific steps are described as follows:(i)
Setup. Admin inputs the security parameter λ and outputs the system parameter Params=GA,GM,P^,q,e,Y,H1,H2,H3,H4, where Y=xP^ is the public key and x∈Rℤq∗ is the master key.(ii)
Key-Gen. In the entity registration process, sij obtains its partial secret key Bij, and ci obtains its partial secret key Bi0.(iii)
Individual-Sign. For txij, let mij=Uij,Tagf,Tijf. sij chooses a random number rij∈ℤq∗ and computes Rij=rijP^, Hij=H2aijUi0Y, hij=H3mij,Uij, and Wij=rij+aijHij+hijBij. Then sij’s individual signature is σij=Rij,Wij.(iv)
Individual-Verify. ci is responsible for verifying signatures in its domain. For k signatures σij=Rij,Wij, 1≤j≤k, k∈m,n, ci performs the following steps:(a)
Tracing on Verichain for all operating transactions associated withTagf in Domi and judging whether the order of addresses is the same with that in Pathi, as shown in Algorithm 2.(b)
Verifying the signature ofsij on Pathi. ci calculates Hij=H2ai0UijY, hij=H3mij,Uij, and Dij=H1Addrij. Checking whether the equation(1)eWij,P^=ehijDij,Y⋅eHij,Rij⋅eHij,Uijholds or not. If it holds,ci accepts σij.(v)
Aggregate-Sign. For k accepted individual signatures σij=Rij,Wij given by distinct switches on Pathi, where i=1,k=m or i=2,k=n, ci calculates W˜i=∑j=1kWij and generates the aggregate signature σ˜i=Ri1,Ri2,…,Rik,W˜i.(vi)
Aggregate-Verify. Admin completes the verification of aggregate signatures which are generated by c1 and c2, respectively. When Admin receives σ˜i=Ri1,Ri2,…,Rik,W˜i, it performs the following steps:(a)
Tracing all the operating transactions associated withTagf on Verichain and judging whether the order of transactions is the same with Pathf, in order to ensure that the sequence of forwarding nodes is correct. The trace process is similar to that in Individual-Verify step, except for the extra validations pubkeyhash1m=AddrU21 and hpathf=H4hpath2,H4hpath1 needed to be done, as shown in Algorithm 3.(b)
ComputingHij=H2xUijUi0, hij=H3mij,Uij and Dij=H1Addrij and checking whether the equation(2)eW˜i,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij∏j=1keHij,Uijholds or not. If it holds,Admin accepts the aggregate signatures σ˜i.Because of the properties of bilinear pairings, we can conclude that the aggregate signature scheme mentioned above is correct.(3)eW˜i,P^=e∑j=1kWij,P^=e∑j=1krij+aijHij+hijBij,P^=e∑j=1kxhijDij,P^⋅∏j=1kerijHij,P^⋅∏j=1keaijHij,P^=e∑j=1khijDij,Y⋅∏j=1keHij,Rij⋅∏j=1keHij,Uij.If multiple flows are assigned with the same forwarding rules simultaneously, the batch verification technique is adopted to improve the efficiency of validation operations in our mechanism. The tag of batch flows isTagf˜, which will replace Tagf in the above scheme to perform batch verification.Algorithm 3: Verification of the cross-domain forwarding order of switches.
Input:txij: forwarding transaction published by sij;Uij: public key of sij;outputAddrij: output address in txij;m,n: m,n∈ℤ+;hpathi: hash value of Pathi;hpathf: forwarding path hash value of f;Output: valid, invalid;(1)
Admin traces back all txij about Tagf;(2)
i←1;k←m;(3)
if the result of executing Algorithm 2 is “valid” then(4)
hpath1←H4Path1;(5)
end if(6)
i←2;k←n;(7)
if the result of executing Algorithm2 is “valid” then(8)
hpath2←H4Path2;(9)
end if(10)
ifoutputAddr1m==AddrU21 and hpathf==H4hpath2,H4hpath1then(11)
return valid(12)
else(13)
return invalid(14)
end if


## 5. Security Analysis

We adopt the adaptive chosen-message security model to prove our algorithm. In this model, given a designated address, the adversaryA wants to obtain the existential forgery of an aggregate signature.Definition 1.
Bilinear map: letGA and GM be an additive cyclic group and a multiplicative cyclic group, respectively, with the same prime order q, and P^ is a generator of GA. Let e be a bilinear map such that e:GA×GA⟶GM which has the following properties:(1)
Bilinear: for allP1^,P2^∈GA and a,b∈ℝℤq∗, eaP1^,bP2^=eP1^,P2^ab(2)
Non-degenerate:eP^,P^≠1, where P^ is the generator of GA.(3)
Computable: for allP1^,P2^∈GA, eP1^,P2^ is efficiently computable.Definition 2.
Computational Diffie–Hellman (CDH) problem: GivenP^,aP^,bP^∈GA as input, compute abP^∈GA for unknown a,b∈ℝℤq∗.
We say that CDH problem ist,ε-hard if there is no algorithm that can solve the problem with probability no more than ε in time at most t.Definition 3.
An aggregate signature schemeΠ^ is existentially unforgeable under an adaptive chosen-message model, if for all probabilistic polynomial-time adversaries A, there is a negligible function N^ for the advantage AdvA such that(4)AdvA=PrAggSigForgeA,Π^=1≤N^.
A wins if his advantage, AdvA, is non-negligible. His aggregate signature is valid and non-trivial, i.e., A does not inquire about the signatures of at least one message under the designated address.Definition 4.
A forgerA is t,ε,qH1,qH2,qH3,qpsk,qfsk,\\qar,qs,k−breaks an aggregate signature scheme in BlockREV with the adaptive chosen-message model if: A makes at most qH1, qH2 and qH3 queries to the hash function, at most qpsk queries to the partial secret key oracle, at most qfsk queries to the full secret key oracle, at most qar queries to the address replacement oracle, at most qs queries to the signing oracle, runs in time at most t with at most k users, and AdvA is at least ε.Definition 5.
An aggregate signature scheme in BlockREV ist,ε,qH1,qH2,qH3,qpsk,qfsk,qar,qs,k−secure against existential forgery if there is no adversary t,ε,qH1,qH2,qH3,qpsk,qfsk,qar,qs,k−breaks it in the adaptive chosen-message model.Theorem 1.
If there exists a forgerA that can t,ε,qH1,qH2,qH3,\\qpsk,qfsk,qar,qs,k−break the aggregate signature scheme in BlockREV by non-negligible probability ε, an algorithm C can solve an instance of CDH problem in polynomial time t′≤t+qH1+qH2+qpsk+3qs+3k−1tsm+tinv with non-negligible probability ε′≥ε/qH1⋅e1−k−qs−qfsk/qH1. Here tsm is the time of a scalar multiplication in GA, tinv is the time to compute an inverse in ℤq, and e is the natural logarithm base.Proof.
AlgorithmC simulates a challenger. Assume that C is given an CDH problem instance q,P^,aP^,bP^ and will interact with A as follows to compute abP^. Let Addr∗ be the target victim, and the detailed process is as follows.
Setup:C sets the system parameters—Params=GA,GM,P^,q,e,Y,H1,H2,H3, public key Y=aP^. H1,H2,H3 are three random oracles controlled by C. Then, C sends Params to A.
Queries:C maintains empty list ℒH1, ℒH2, ℒH3, ℒpsk, ℒfsk, ℒar, ℒs, and A simulates the oracle queries in the following types.(i)
H1−query: upon receiving the entry Addrij, C performs the following:(a)
C checks whether existing Addrij,coinij,θij,Dij\\∈ℒH1 or not. If so, C sends Dij to A.(b)
Otherwise,C generates a random coin coinij∈0,1 so that Prcoinij=0=1/qH1.C randomly selects θij∈ℤq∗. If coinij=0 holds, C computes Dij=θijbP^. If coinij=1 holds, C computes Dij=θijP^. C responds to A with Dij and saves Addrij,coinij,θij,Dij into the hash list ℒH1.(ii)
H2−query: upon receiving the entry Uij,Ui0, C checks whether existing Uij,Ui0,ηij,Hij∈ℒH2 or not. If so, C sends Hij to A; otherwise, C randomly selects ηij∈ℤq∗, computes Hij=ηijP^, sends Hij to A, and saves Uij,Ui0,ηij,Hij into the hash list ℒH2.(iii)
H3−query: upon receiving the entry mij,Uij, C checks whether existing mij,Uij,hij∈ℒH3 or not. If so, C sends hij to A; otherwise, C randomly selects hij∈ℤq∗, sends hij to A, and saves mij,Uij,hij into the hash list ℒH3.(iv)
PartialSecretKey−query: upon receiving the entry Addrij, C performs the following:(a)
C checks whether existing Addrij,coinij,Bij∈ℒHpsk or not. If so, C sends Bij to A.(b)
Otherwise,C makes H1−query on Addrij. If coinij=0 holds, C computes Bij=θijbY. If coinij=1 holds, C computes Bij=θijY. C responses Bij to A and saves Addrij,coinij,Bij into the partial secret key list ℒpsk.(v)
FullSecretKey−query: upon receiving the address Addrij, C performs the following:(a)
C checks whether existing Addrij,aij,Bij∈ℒfsk or not. If so, C sends aij,Bij to A.(b)
Otherwise,C makes H1−query on Addrij. If coinij=0 holds, C aborts and outputs ⊥. If coinij=1 holds, C randomly selects aij∈ℤq∗ and makes PartialSecretKey−query on Addrij. Then, C responses aij,Bij to A and saves Addrij,aij,Bij into the full secret key list ℒfsk.(vi)
AddressePlacement−query: A randomly selects aij∗∈ℤq∗, computes Uij∗=aij∗P^ and Addrij∗=AddrUij∗, and sends Addrij∗,Uij∗ to C for the replacement of any original legitimate address. C saves Addrij∗,Uij∗ into the list ℒar.(vii)
Sign−query: upon receiving the entry Addrij,Uij,Ui0,mij, C performs the following:(a)
C checks whether existing Addrij,Uij,Ui0,mij,rij,Wij∈ℒs or not. If so, C computes Rij=rijP^ and sends Rij,Wij to A.(b)
Otherwise,C randomly selects rij∈ℤq∗ and computes Rij=rijP^ and Wij=Rij+Uijηij+hijθijY. C responds to A with Rij,Wij and saves Addrij,Uij,Ui0,mij,rij,Wij into the sign list ℒs.
Forge. After adaptive queries, A outputs the aggregate signature σ˜i∗=Ri1∗,Ri2∗,…,Rik∗,W˜i∗ on Addri1∗,…,Addrik∗ and mi1∗,…,mik∗, in which the messages are all distinct, and at least one address Addrij∗ does not perform the full secret key query; furthermore, mij∗ does not make sign-query.
IfAddr∗∉Addri1∗,Addri2∗,…,Addrik∗, C outputs failure and halts. Otherwise, let Addr∗=Addri1∗, and C proceeds only if coini1=0 and for 2≤j≤k, coinij=1. Since the aggregate signature σ˜i∗ is valid, it must satisfy verification equation (2), and we can get(5)eW˜i,P^=eWi1,P^e∑j=2kWij,P^=eri1+ai1Hi1+hi1Bi1,P^⋅e∑j=2kRij+Uijηij+hijθijY,P^=eηi1P^,Ri1⋅eηi1P^,Ui1⋅ehi1θi1bP^,Y⋅∏j=2keηijP^,Rij⋅∏j=2keηijP^,Uij⋅∏j=2kehijθijP^,Y.
Then,C outputs abP^=hi1θi1−1⋅W˜i−ηi1Ri1−ηi1Ui1−∑j=2kηijRij+ηijUij+hijθijY as the solution of CDH problem.
Suppose that(1)
EventEi1 represents that C does not output ⊥ at FullSecretKey−query and Sign−query stages.(2)
EventEi2 represents that A generates a valid aggregate signature forgery.(3)
EventEi3 represents that C does not abort at the forge stage.
The probabilities of solving the CDH problem byC are as follows:(6)PrEi1≥1−1qH1qfsk+qs,PrEi2|Ei1≥ε,PrEi3|Ei1Ei2≥1qH11−1qH1k−1.
Therefore,(7)PrEi1Ei2Ei3=PrEi1⋅PrEi2|Ei1⋅PrEi3|Ei1Ei2≥εqH11−1qH1qfsk+qs+k−1.
When three events have all happened, algorithmC can successfully solve the CDH problem with a non-negligible probability(8)ε′≥PrEi1Ei2Ei3≥εqH1⋅e1−k−qs−qfsk/qH1.
C’s extra time cost includes that for computing at most one scalar multiplication in GA on each H1−query, H2−query, and PartialSecretKey−query and three scalar multiplications on each sign−query. After the forgery operation is completed, the time cost should be plus at most the time for computing 3k−1 scalar multiplication in GA and an inverse computation in ℤq. Therefore, C can solve an instance of CDH problem in polynomial time t′≤t+qH1+qH2+qpsk+3qs+3k−1tsm+tinv.
We have the conclusion that assuming the CDH problem is hard, the proposed aggregate signature scheme in BlockREV is existentially unforgeable against adaptive chosen-message attacks in the oracle model.
We next show security properties of BlockREV mechanism in the context of typical attacks.(i)
Resistance to single-point failure attack: the information on blockchain is transparent and tamper resistant. When a controller is compromised, the administrator can still verify the forwarding behaviors by tracing the transactions on the blockchain and determine the reliability of the controller.(ii)
Resistance to middle-man attack: due to the cryptography theory, transactions published by malicious switches cannot pass signature verification. Because the controller can only verify signatures of switches in its domain, a malicious controller cannot obtain the information about path index and switches’ identities in other domains.(iii)
Resistance to path deviation attack: based on public forwarding address information in transactions, the order of forwarding nodes is verified by controllers to ensure the correct execution of forwarding. Through nesting method of forwarding path hash values, the administrator guarantees the correct index of different domains. In addition, our novel aggregate signature scheme provides the security in cryptography technology.


## 6. Performance and Evaluation

In this section, we evaluate the performance of our algorithms in terms of computation cost and communication cost compared with other existing schemes.


### 6.1. Analysis of Computation Cost

We compare the performance of the aggregate signature scheme in BlockREV with two related aggregate signature schemes [27, 35] and adopt the computation evaluation method proposed in [30] using the MIRACL cryptographic library [36], in which the experimental platform is an Intel I7-4770 processor (3.40 GHz) with 4 GB RAM, and the operating system is Windows 7. The aggregate signature scheme in BlockREV is simulated on the elliptic curve y2=x3+xmodp, where p and q are 512 bit and 160 bit prime numbers, respectively.Some notations about cryptographic operation execution time are listed as follows.(i)
tbp denotes the time for a bilinear pairing operation eP1^,P2^, where P1^,P2^∈GA, tbp=4.2110ms.(ii)
tsm denotes the time for a scale multiplication operation r⋅P^ in the bilinear pair, where r∈ℤq∗ and P^∈GA, tsm=1.7090ms.(iii)
tpa denotes the time for a point addition operation P^+Q^ in the bilinear pair, where P^,Q^∈GA, tsm=0.0071ms.(iv)
thtp denotes the time for a hash-to-point operation in the bilinear pair, which maps a string to a point of GA, thtp=4.4060ms.(v)
th denotes the time for a general hash function operation, th=0.0001ms.(vi)
n is the number of individual signatures.(vii)
lG denotes the length of a group element in G, lG=128 bytes.(viii)
lℤq∗ denotes the length of ℤq∗ element. lℤq∗=20 bytes.The comparison of computational costs is performed between the related aggregate signature schemes [27, 35] and our scheme in three aspects: Individual-Sign, Individual-Verify, and Aggregate-Verify. The specific comparison results are presented in Table 2.Table 2
The comparison of computation cost.
SchemeIndividual-SignIndividual-VerifyAggregate-VerifyGao et al. [35]5tsm+2thtp+3tpa5tbp+3thtpn+4tbp+2n+1thtp+3n−1tpa≈17.3783ms≈34.273ms≈13.0443n+21.2429msGong et al. (CAS 2) [27]3tsm+2thtp+2tpa3tbp+tsm+3thtp+tpan+2tbp+ntsm+2nthtp+ntpa≈13.9532ms≈27.5670ms≈14.7391n+8.422msGong et al. (CAS 1) [27]2tsm+thtp+tpa3tbp+thtp2n+1tbp+2nthtp≈7.8311ms≈17.039ms≈17.2340n+4.2110msOur proposed scheme4tsm+thtp+tpa+th4tbp+2thtp+th2n+2tbp+2nthtp+n−1tpa+nth≈10.2492ms≈25.6460ms≈17.2412n+8.4149msAs shown in Figure5, for the computation cost of the individual signature algorithm, we can conclude that both Gao et al.'s scheme [35] and Gong et al.'s CAS 2 scheme [27] pay more running time than ours. For the total execution time, the percentage improvement of our algorithm over Gao et al.’s scheme and Gong et al.’s scheme (CAS 2) is about 17.3783−10.2492/17.3783≈41.02% and 13.9532−10.2492/13.9532≈26.55%, respectively. Our individual signature algorithm reduces one hash-to-point operation in the bilinear pair compared with the above two schemes, which takes more than 4 ms to run. Due to the low cost of computing in the individual signing process, BlockREV is feasible for SDN environments in which switches as signers have limited computational ability.Figure 5
The comparison of individual signature time.For the execution of the individual verification algorithm, Figure6 shows that as the number of signatures increases, the computation cost of ours is smaller than that in Gao et al.’s scheme and Gong et al.’s scheme (CAS 2). In the aspect of individual verification algorithm design, Gao et al.’s scheme has one more bilinear pairing operation and one more hash-to-point operation than our scheme, which results in an additional 2.1210 ms for each signature verification. Therefore, BlockREV is more efficient in individual signature verification and will be better suited to the controller which consumes a huge computation cost to manage its domain.Figure 6
The comparison of individual verification time.As shown in Table2, for the execution of the aggregate verification algorithm, the computation cost of our scheme is close to that of Gong et al.’s scheme (CAS 1) [27]. The reason for the above result is that in the process of verifying aggregate signatures in our scheme, the administrator is the only legal verifier with the authority to verify aggregate signatures of different domains. Each signature contains the information about the public key of the administrator, which leads to higher computational overhead. As a manager of the whole network, the administrator has strong computing power and can bear such computing overhead.Figure7 shows a comparison between non-aggregate signature and aggregate signature. With the increase of the number of switches, the time of verifying the signature one by one increases rapidly which results in high computation cost. When the number of switches increases to 20, non-aggregate signature verification takes 159.6811 ms more than aggregate signature verification. The aggregate signature scheme can reduce a lot of computing overhead for the verifier; therefore, it is suitable for the administrator node in the case that the cross-domain forwarding path contains a large number of switches.Figure 7
The comparison between non-aggregate signature and aggregate signature.


### 6.2. Analysis of Communication Cost

Table3 shows the communication cost of the aggregate signature scheme and related aggregate signature schemes [35, 37]. We can see that the aggregate signature length of all schemes is increased with the number of individual signatures. The length of the aggregate signature in our scheme is 2n−1lG less than that in Shim’s scheme and nlG less than that in Gao et al.’s scheme.Table 3
The comparison of communication cost.
SchemeAggregate signature lengthShim [37]3nlGGao et al. [35]2n+1lGOur proposed schemen+1lGAs shown in Figure8, the communication cost of our scheme is obviously smaller than that of the above two schemes; therefore, our proposed aggregate signature scheme can effectively improve the communication efficiency.Figure 8
The comparison of aggregate signature length.


## 6.1. Analysis of Computation Cost

We compare the performance of the aggregate signature scheme in BlockREV with two related aggregate signature schemes [27, 35] and adopt the computation evaluation method proposed in [30] using the MIRACL cryptographic library [36], in which the experimental platform is an Intel I7-4770 processor (3.40 GHz) with 4 GB RAM, and the operating system is Windows 7. The aggregate signature scheme in BlockREV is simulated on the elliptic curve y2=x3+xmodp, where p and q are 512 bit and 160 bit prime numbers, respectively.Some notations about cryptographic operation execution time are listed as follows.(i)
tbp denotes the time for a bilinear pairing operation eP1^,P2^, where P1^,P2^∈GA, tbp=4.2110ms.(ii)
tsm denotes the time for a scale multiplication operation r⋅P^ in the bilinear pair, where r∈ℤq∗ and P^∈GA, tsm=1.7090ms.(iii)
tpa denotes the time for a point addition operation P^+Q^ in the bilinear pair, where P^,Q^∈GA, tsm=0.0071ms.(iv)
thtp denotes the time for a hash-to-point operation in the bilinear pair, which maps a string to a point of GA, thtp=4.4060ms.(v)
th denotes the time for a general hash function operation, th=0.0001ms.(vi)
n is the number of individual signatures.(vii)
lG denotes the length of a group element in G, lG=128 bytes.(viii)
lℤq∗ denotes the length of ℤq∗ element. lℤq∗=20 bytes.The comparison of computational costs is performed between the related aggregate signature schemes [27, 35] and our scheme in three aspects: Individual-Sign, Individual-Verify, and Aggregate-Verify. The specific comparison results are presented in Table 2.Table 2
The comparison of computation cost.
SchemeIndividual-SignIndividual-VerifyAggregate-VerifyGao et al. [35]5tsm+2thtp+3tpa5tbp+3thtpn+4tbp+2n+1thtp+3n−1tpa≈17.3783ms≈34.273ms≈13.0443n+21.2429msGong et al. (CAS 2) [27]3tsm+2thtp+2tpa3tbp+tsm+3thtp+tpan+2tbp+ntsm+2nthtp+ntpa≈13.9532ms≈27.5670ms≈14.7391n+8.422msGong et al. (CAS 1) [27]2tsm+thtp+tpa3tbp+thtp2n+1tbp+2nthtp≈7.8311ms≈17.039ms≈17.2340n+4.2110msOur proposed scheme4tsm+thtp+tpa+th4tbp+2thtp+th2n+2tbp+2nthtp+n−1tpa+nth≈10.2492ms≈25.6460ms≈17.2412n+8.4149msAs shown in Figure5, for the computation cost of the individual signature algorithm, we can conclude that both Gao et al.'s scheme [35] and Gong et al.'s CAS 2 scheme [27] pay more running time than ours. For the total execution time, the percentage improvement of our algorithm over Gao et al.’s scheme and Gong et al.’s scheme (CAS 2) is about 17.3783−10.2492/17.3783≈41.02% and 13.9532−10.2492/13.9532≈26.55%, respectively. Our individual signature algorithm reduces one hash-to-point operation in the bilinear pair compared with the above two schemes, which takes more than 4 ms to run. Due to the low cost of computing in the individual signing process, BlockREV is feasible for SDN environments in which switches as signers have limited computational ability.Figure 5
The comparison of individual signature time.For the execution of the individual verification algorithm, Figure6 shows that as the number of signatures increases, the computation cost of ours is smaller than that in Gao et al.’s scheme and Gong et al.’s scheme (CAS 2). In the aspect of individual verification algorithm design, Gao et al.’s scheme has one more bilinear pairing operation and one more hash-to-point operation than our scheme, which results in an additional 2.1210 ms for each signature verification. Therefore, BlockREV is more efficient in individual signature verification and will be better suited to the controller which consumes a huge computation cost to manage its domain.Figure 6
The comparison of individual verification time.As shown in Table2, for the execution of the aggregate verification algorithm, the computation cost of our scheme is close to that of Gong et al.’s scheme (CAS 1) [27]. The reason for the above result is that in the process of verifying aggregate signatures in our scheme, the administrator is the only legal verifier with the authority to verify aggregate signatures of different domains. Each signature contains the information about the public key of the administrator, which leads to higher computational overhead. As a manager of the whole network, the administrator has strong computing power and can bear such computing overhead.Figure7 shows a comparison between non-aggregate signature and aggregate signature. With the increase of the number of switches, the time of verifying the signature one by one increases rapidly which results in high computation cost. When the number of switches increases to 20, non-aggregate signature verification takes 159.6811 ms more than aggregate signature verification. The aggregate signature scheme can reduce a lot of computing overhead for the verifier; therefore, it is suitable for the administrator node in the case that the cross-domain forwarding path contains a large number of switches.Figure 7
The comparison between non-aggregate signature and aggregate signature.


## 6.2. Analysis of Communication Cost

Table3 shows the communication cost of the aggregate signature scheme and related aggregate signature schemes [35, 37]. We can see that the aggregate signature length of all schemes is increased with the number of individual signatures. The length of the aggregate signature in our scheme is 2n−1lG less than that in Shim’s scheme and nlG less than that in Gao et al.’s scheme.Table 3
The comparison of communication cost.
SchemeAggregate signature lengthShim [37]3nlGGao et al. [35]2n+1lGOur proposed schemen+1lGAs shown in Figure8, the communication cost of our scheme is obviously smaller than that of the above two schemes; therefore, our proposed aggregate signature scheme can effectively improve the communication efficiency.Figure 8
The comparison of aggregate signature length.


## 7. Conclusion

In this paper, we propose a blockchain-enabled multi-controller rule enforcement verification mechanism in SDN, called BlockREV. The mechanism adopts an address-based aggregation signature scheme with the cryptography technology and can securely store and share forwarding information with the blockchain technology. We also present the implementation results and prove the security in the random oracle model. The BlockREV mechanism can be used in many scenarios in which nodes have limited computation power, such as Internet of things and smart grid. In our future work, we will find more efficient aggregation signature constructions requiring less computation cost and design zero-knowledge proof schemes for forwarding rule verification with perfect privacy protection.



---

*Source: 7294638-2022-01-11.xml*