Richard Agbeyibor

Jonathan Butts

Michael Grimaila

Robert Mills

Evaluation of Format-Preserving Encryption Algorithms for Critical Infrastructure Protection

Keywords:

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Legacy industrial control systems were developed and implemented well before the threats associated with modern networking were recognized. The trend to interconnect industrial control systems, however, has introduced many security concerns [START_REF] Stouffer | Guide to Industrial Control Systems (ICS) Security[END_REF]. The systems were designed for performance, reliability and safety using proprietary hardware, software and communications protocols. The communications protocols incorporate basic error detection and correction functionality, but lack the secure communications capabilities required by mod-ern interconnected systems. Many legacy protocols associated with industrial control systems are incompatible with modern IP-based security such as message encryption. Arbitrarily-formatted data associated with control operations cannot be padded or truncated; this prevents the use of standard encryption that relies on fixed message data lengths (e.g., the 128 or 256 block size associated with the Advanced Encryption Standard (AES)).

The Computer Security Act of 1987 assigned the National Institute of Standards and Technology (NIST) the task of developing security standards and guidelines to secure sensitive federal information and communications systems [15]. Among the most sensitive of these federal systems are those categorized as critical infrastructure assets. According to Executive Order 13636 of February 2013, "the cyber threat to critical infrastructure continues to grow and represents one of the most serious national security challenges" [START_REF] Obama | Improving critical infrastructure cybersecurity: Executive Order 13636[END_REF]. Executive Order 13636 also defines critical infrastructure as "the assets, whether physical or virtual, so vital to the United States that the incapacity or destruction of such systems and assets would have debilitating impact on security, national economic security, national public health or safety, or any combination of those matters" [START_REF] Obama | Improving critical infrastructure cybersecurity: Executive Order 13636[END_REF].

In response, NIST started the development of a cybersecurity framework in collaboration with researchers and stakeholders from the telecommunications, energy, financial services, manufacturing, water, transportation, healthcare, and emergency services sectors [16]. The interconnected nature of systems used in these sectors requires comprehensive risk management and infrastructure assurance plans. A major concern in critical infrastructure protection is the ubiquity of systems that employ aging (legacy) technologies with limited security functionality. Many of the legacy communications protocols used in sectors such as energy and transportation are incompatible with modern IPbased security, but are too costly to replace.

An important focus of NIST is the development of cryptographic standards. Cryptography includes the algorithms used to encrypt and decrypt information, and to perform other security functions such as digital signatures, authentication and key exchange [15]. One notable success is the adoption of the Advanced Encryption Standard (AES), the gold standard for symmetric-key encryption.

In July 2013, NIST released Draft Special Publication 800-38G, which recommends methods for format-preserving encryption (FPE) [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF]. FPE allows the encryption of data with non-standard formats that are not suitable for modification (e.g., information transmitted in non-IP networks or stored in legacy databases). FPE can potentially provide security to legacy critical infrastructure systems that were not designed with security in mind and that are incompatible with standard encryption technology. This paper investigates the security and performance of the three NIST-recommended FPE algorithms for use in critical infrastructure protection.

Background

Encryption is the mathematical manipulation of data in a manner that makes it unintelligible to unauthorized parties, yet recoverable by intended recipients [START_REF] Trappe | Introduction to Cryptography with Coding Theory[END_REF]. Figure 1 shows the modern cryptography hierarchy. Cryptographic algorithms can be categorized as symmetric or asymmetric algorithms, also known as private-key or public-key algorithms, respectively. Symmetric algorithms use the same key for encryption and decryption; the key must be distributed offline or via a secure key distribution protocol. Asymmetric algorithms use two keys: one for encryption and the other for decryption. One of the keys (private key) is kept secret by one party; the other key (public key) can be distributed openly. This resolves the problem of key distribution, but asymmetric algorithms are typically more complex and computationally intensive than symmetric algorithms.

Cryptographic algorithms operate as block ciphers or stream ciphers. Stream ciphers encipher the plaintext one character at a time and concatenate the independent encryptions to produce the ciphertext. Stream ciphers are fast, but are prone to weaknesses with regard to integrity protection and authentication [START_REF] Trappe | Introduction to Cryptography with Coding Theory[END_REF]. On the other hand, block ciphers are slower, but their mechanisms ensure the security properties of confusion and diffusion. Confusion means that the key does not relate in a simple manner to the ciphertext; it refers to making the relationship as complex as possible using the key non-uniformly throughout the encryption process. Diffusion means that changing a single character in the plaintext causes several characters in the ciphertext to change, and vice versa [START_REF] Trappe | Introduction to Cryptography with Coding Theory[END_REF]. Block ciphers are widely used in modern cryptography, and three in particular -AES, 3DES and Skipjack -are recommended for use by NIST [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF].

AES, 3DES and Skipjack are applied to 64-bit or 128-bit blocks of data. When AES was designed, 128-bit message blocks were commonly used for cryptographic applications [START_REF] Rogaway | A Synopsis of Format-Preserving Encryption, Voltage Security[END_REF]. Messages that do not fit the prescribed block size are padded or truncated. However, many supervisory control and data acquisition (SCADA) systems used in the critical infrastructure do not permit padding. SCADA systems traditionally use low-bandwidth links and compact communications protocols such as Modbus and DNP3 [START_REF] Tsang | Yasir: A low-latency, high-integrity security retrofit for legacy SCADA systems[END_REF]. Solutions have been developed to retrofit security in these systems, but they often incur significant processing and buffering overhead that cannot be tolerated in systems with strict timing constraints [START_REF] Tsang | Yasir: A low-latency, high-integrity security retrofit for legacy SCADA systems[END_REF]. A preferred solution is an algorithm that can transform formatted data into a sequence of symbols such that the encrypted data has the same format and length as the original data [START_REF] Rogaway | A Synopsis of Format-Preserving Encryption, Voltage Security[END_REF].

Format-Preserving Encryption

The origins of the format-preserving encryption (FPE) problem go back 32 years. In 1981, the U.S. National Bureau of Standards (later renamed NIST) published FIPS 74 that described an approach for enciphering arbitrary strings over an arbitrary alphabet [START_REF] Bellare | The FFX Mode of Operation for Format-Preserving Encryption[END_REF]. The scheme was subsequently proven to be insecure. It was not until 1997 that Brightwell and Smith [START_REF] Brightwell | Using datatype-preserving encryption to enhance data warehouse security[END_REF] specifically mentioned the FPE problem and its utility, which they referred to as "datatypepreserving encryption" [START_REF] Brightwell | Using datatype-preserving encryption to enhance data warehouse security[END_REF]. In 2002, Black and Rogaway [START_REF] Black | Ciphers with arbitrary finite domains[END_REF] published a seminal paper that proposed three methods for ciphers with arbitrary finite domains: a prefix method, a cycle-walking cipher and a Feistel construction. The first two methods have strong security bounds, but are targeted for tiny-space and small-space messages. In the case of tiny-space FPE, the size of the message space N = |X| is so small that it is feasible to spend O(N ) time or O(N ) space for encryption or decryption. For small-space FPE, the size of the message space N = |X| is at most 2 w where w is the block size of the cipher underlying the FPE scheme. AES is most often used as the block cipher, so w = 128 bits and N = 2 128 ≈ 10 38.5 becomes the cutoff for "small" [START_REF] Morris | How to encipher messages on a small domain[END_REF]. The third method encrypts a much wider variety of data using the Feistel construction that was first examined by Luby and Rackoff in 1988 [START_REF] Luby | How to construct pseudorandom permutations from pseudorandom functions[END_REF]. The Feistel construction has the desirable property that ciphers built from it can be proven to reduce to the cipher that is used as a round function [START_REF] Patarin | Seven rounds are enough for 2 n(1-ε) security[END_REF].

In 2003, Spies [START_REF] Spies | Feistel Finite Set Encryption Mode[END_REF] proposed the FFSEM algorithm that employs the Feistel construction for FPE. The development of FFSEM was motivated by the desire to add security to legacy protocols and systems in the financial services sector [START_REF] Spies | Format Preserving Encryption, Voltage Security[END_REF]. In these systems, one of the barriers to adopting effective encryption methods was the cost of modifying databases and applications to accommodate encrypted information. Applications often expect input in specific formats. Moreover, data such as social security numbers and personal account numbers are often used as keys or indices in databases, so any randomization of these fields by a randomized or stateful algorithm can require significant schema changes [START_REF] Rogaway | A Synopsis of Format-Preserving Encryption, Voltage Security[END_REF]. In 2010, Bellare, et al. [START_REF] Bellare | The FFX Mode of Operation for Format-Preserving Encryption[END_REF] submitted specifications for FFX, a format-preserving, Feistel-based encryption. Note that the "X" in FFX is a placeholder for implementations of the algorithm that are tailored to particular applications.

NIST Recommendations. The release of the FFX specification raised awareness about the FPE problem and encouraged security researchers to develop alternative algorithms. After nearly two years of deliberation, NIST released a draft of Special Publication 800-38 [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF] for public comment. The publication specifies three FPE methods: FF1, FF2 and FF3. Each of these methods is a mode of operation of the AES algorithm, which is used to construct a round function within the Feistel structure for encryption as shown in Figure 2. FF2 Algorithm: The FF2 algorithm is derived from the VAES3 algorithm proposed by Vance [START_REF] Vance | VAES3 Scheme for FFX: An Addendum to the FFX Mode of Operation for Format Preserving Encryption[END_REF]. Figure 4 describes the FF2 algorithm, which generates a subkey for the block cipher in the Feistel round function; this can help protect the original key from side-channel analysis [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF]. FF2 differs from FF1 in that it employs a larger tweak with an independent tweak radix to allow for additional variation in the cipher.

FF3 Algorithm: The FF3 algorithm is essentially equivalent to the BPS-BC component of BPS [START_REF] Brier | BPS: A Format-Preserving Encryption Proposal[END_REF] instantiated with a 128-bit block and limited to tiny-and small-space messages [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF]. Figure 5 describes the FF3 algorithm, which has only eight rounds, but is the least flexible in terms of the tweaks that are supported. In particular, the FF3 employs a 64bit tweak, which is split into right and left halves that are used to add diffusion to odd and even encryption rounds, respectively.

Evaluation of the Algorithms

One of the criteria used during the evaluation of the AES candidate algorithms in 1999 was demonstrated suitability as a random number generator. Specifically, the evaluation of the output utilizing statistical tests should not provide any means to distinguish it from a truly random source. NIST [START_REF] Soto | Randomness Testing of the AES Candidate Algorithms[END_REF]. The Rijndael algorithm performed satisfactorily in all the tests and was selected as the AES algorithm.

Since FPE algorithms are modes of operation of the underlying block cipher, FF1, FF2 and FF3 should benefit from the statistical characteristics of AES. This hypothesis is supported by theoretical results [START_REF] Naor | On the construction of pseudorandom permutations: Luby-Rackoff revisited[END_REF][START_REF] Patarin | Seven rounds are enough for 2 n(1-ε) security[END_REF][START_REF] Patarin | Security of random Feistel schemes with five or more rounds[END_REF]. Our evaluation uses Shannon entropy measurements to assess the security characteristics of the three FFX algorithms. Note that entropy is a measure of unpredictability or information content; Shannon entropy quantifies the expected value of the information contained in a message and is typically measured in bits per byte [START_REF] Trappe | Introduction to Cryptography with Coding Theory[END_REF].

In addition to security performance, the computational performance of the algorithms is an important criterion. Several metrics may be used to measure the computational performance: encryption time, processing time and total clock cycles per encryption [START_REF] Good | AES on FPGA from the fastest to the smallest[END_REF]. The total clock cycle metric was used in this research to evaluate the computational speed of the FF1, FF2 and FF3 algorithms.

Experimental Design

In order to determine the security and performance of the FF1, FF2 and FF3 algorithms for critical infrastructure assets, a set of experiments was designed to test the hypothesis suggested by the algorithm designers and NIST [START_REF] Dworkin | Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption[END_REF] that the algorithms inherit the strong security characteristics of the underlying block cipher. NIST has not released details of its internal deliberations and performance assessments.

As such, statistical tests were conducted to determine the ability of the FPE algorithms to provide confusion and diffusion, and to output ciphertext that is computationally indistinguishable from a random process. A dataset containing input plaintext with varying levels of entropy was created. The FF1, FF2 and FF3 algorithms were applied to this dataset. The algorithms were implemented in C using the offspark AES library [START_REF] Offspark | offspark: Straightforward Security Communication[END_REF] and the entropy of the resulting ciphertext was measured.

The second objective of our research was to evaluate the computational speed of the three algorithms by measuring the operational latency of a hardware implementation. This was accomplished by implementing the algorithms in VHDL using the Xilinx ISE suite for the Virtex-6 FPGA (XC6VLX240T) [START_REF]Xilinx, Virtex-6 Family Overview, Xilinx Data Sheet[END_REF]. A hardware-agnostic design was used to mitigate effects due to the Virtex-6 CMOS technology and Xilinx FPGA architecture. The operational latency was estimated using the number of clock cycles between the input of plaintext and the output of its ciphertext.

Plaintext Dataset Design

In 1999, NIST tested the ability of the AES candidate algorithms to encrypt a plaintext avalanche comprising various sequences of random and fixed plaintext bits [START_REF] Soto | Randomness Testing of the AES Candidate Algorithms[END_REF]. Similarly, our research focused on the ability of the FPE algorithms to encrypt a plaintext avalanche comprising various sequences of random plaintext and fixed plaintext bytes. We studied the effect of repetitive and, thus, predictable input data on the entropy of the ciphertext. Input strings of thirteen bytes were used; this non-standard block size is used by a legacy protocol employed in the transportation sector for aircraft transponder messages [START_REF] Finke | ADS-B encryption: Confidentiality in the friendly skies[END_REF].

Our research employed randomized experiments to enhance the reliability and validity of the statistical results. The True Random Number Generator (TRNG) service provided by Random.org [START_REF]Random Binary File 2013-09-17[END_REF] formed the backbone of the experimental design. Unlike pseudo-random number generators that use mathematical formulas to generate sequences of numbers that appear random, TRNG extracts randomness from physical phenomena (i.e., by measuring atmospheric noise), producing 1 MiB (2 20 bytes) of raw random data. These true random numbers were used to create a dataset of input plaintext strings with varying levels of random and deterministic data. The experimental factor used in the study was the number of deterministic bytes in the plaintext.

The experiments involved eight scenarios in which three, six, nine and twelve bytes of the thirteen-byte plaintext string were held constant at the front or dispersed randomly throughout the string. Each of the eight scenarios was replicated 20 times in unique plaintext files, each containing 4,000 different thirteen-byte strings. In the 3 Front scenario, the first three bytes were the same in all input strings within the file. In the 3 Random scenario, the three deterministic bytes were randomly dispersed throughout the string as shown in Figure 6.

The other six scenarios followed the same design. The 4,000 thirteen-byte strings in each input file repeated the same deterministic sequence; however, each trial used a different deterministic byte sequence. The non-deterministic part of the message was composed of random data extracted from the Random.org sequence of 2013-09-17 [START_REF]Random Binary File 2013-09-17[END_REF].

Implementation and Entropy Measurement

All three FPE algorithms require a NIST-approved block cipher operation CIPH. The 128-bit AES algorithm was used in the implementation. The cryp-tography community discourages the use of unverified implementations of AES because of its complexity. Therefore, we used offspark, a vetted open source implementation of AES used to encrypt official Dutch Government communications [START_REF] Offspark | offspark: Straightforward Security Communication[END_REF]. The offspark implementation is written in the C programming language, which partly motivated the use of C in the research. The research validated the offspark AES implementation by comparing its output with known vectors published in NIST's Known Answer Test [START_REF]Advanced Encryption Standard (AES), Federal Information Processing Standards Publication 197[END_REF].

No known answers tests exist for FF1, FF2 and FF3, nor are there any vetted implementations. Therefore, we verified our implementation via decryption. The decryption algorithms provided by NIST were applied to the ciphertext to reverse the encryption process. Satisfactorily-decrypted ciphertext provided confidence that the implementations were accurate.

Entropy is a measure of the amount of information that can be gleaned from ciphertext. The entropy H(X) of a variable or distribution is defined as:

H(x) = - p(x)log 2 p(x).
Comparisons of the entropy of ciphertext and the entropy of a random distribution were used to assess the security of the algorithms. The ENT tool [START_REF] Walker | Ent: A Pseudorandom Number Sequence Test Program, Fourmilab[END_REF] was used to measure entropy. ENT applied various statistical tests to the sequences of bytes stored in the files and reported the aggregate entropy of the 4,000 output ciphertext strings in each file.

Hardware Implementation

Hardware performance was another criterion used by NIST in 1999 to evaluate the AES candidate algorithms. The Rijndael algorithm was selected partly because it proved to be one of the fastest and most efficient algorithms, and implementable on a wide range of platforms [START_REF] Elbirt | An FPGA-based performance evaluation of the AES block cipher candidate algorithm finalists[END_REF].

A number of different architectures can be considered when implementing an encryption algorithm in hardware or using a field programmable gate array (FPGA). Iterative looping is where only one round is designed; hence, for an n-round algorithm, n iterations of the round are used to perform an encryption. Loop unrolling involves the unrolling of multiple rounds. Pipelining is achieved by replicating the round and placing registers between each round to control the flow of data. A pipelined architecture generally provides the highest throughput [START_REF] Mcloone | High performance single-chip FPGA Rijndael algorithm implementations[END_REF]. Our research employed a pipelined implementation of 128-bit AES and an iterative looping architecture for the Feistel structure of FPE. Iterative looping saves hardware resources by implementing only one round of the algorithm and using control logic to manage data flow.

The NIST pseudocode description is primarily intended for software implementations. As a consequence, certain operations that depend on previous operations require carefully synchronized logic when implemented in hardware. The pseudocode of algorithm was, therefore, expanded to identify parallelizable modules and blocks that can be implemented with combinational logic. Function calls to AES within the F-block of each round require the use of loop counters. The algorithms were coded in VHDL, simulated, placed and routed, and synthesized on a Virtex-6 (XC6VLX240T) device using the Xilinx ISE design suite. Post-PAR static timing analysis and device utilization analysis were performed on each implementation.

The throughput, latency and hardware resource requirements are usually the most critical parameters when evaluating a hardware implementation. Our research evaluated the speed of each algorithm by measuring the operational latency of an encryption cycle. To eliminate bias due to the use of a particular FPGA technology, we estimated operational latency as the number of clock cycles required for an algorithm to encrypt plaintext.

Results and Analysis

This section presents and analyzes the experimental results.

Security

A thirteen-byte sequence of random data obtained from Random.org served as the control in the entropy experiment. An all-random input plaintext file created with the sequence was determined to have an entropy of 7.996 bits/byte. In the following analysis, the mean entropy was calculated for 20 trials of each scenario. Note that there was no statistical significant variance between the various trials. Figure 7 and Table 1 present the security performance of each algorithm estimated in terms of the ciphertext entropy for each level of the experimental factor. As expected, the entropy decreases in the plaintext as the number of deterministic bytes increases. The input entropy ranges from 7.24 bits/byte for three deterministic bytes out of the thirteen total bytes to 4.25 bits/byte for twelve out of thirteen fixed bytes. The distribution of the deterministic bytes, whether located in the front of the string or randomly dispersed throughout the string, does not have a significant effect on the entropy of the plaintext. All three algorithms provide high levels of ciphertext security with no discernible differences in performance. In all but one scenario (12 Front), the ciphertext is indistinguishable from a random sequence with entropy above 7.996 bits/byte. The plaintext in the 12 Front scenario with entropy of 4.256 bits/byte causes a lower entropy in the ciphertext of 7.94 bits/byte versus the 7.996 bits/byte for the random sequence. The lowered entropy presents an upper bound on the obfuscation capabilities of FPE. Further study is necessary to clarify this performance limitation and categorize suitable plaintext.

The three FPE algorithms provide higher levels of entropy when the same number of deterministic bytes are randomly distributed throughout the string in the 12 Random scenario, These results indicate that the distribution of repeated patterns in the plaintext affects the ability of the algorithms to obfuscate the data more than the amount of repeated information.

Performance

The performance results shown in Table 2 indicate that the underlying AES core is the principal factor in the area and speed of the implementation. The AES implementation employed in the designs requires 31 clock cycles per encryption and 1,864 slices (slices are the basic building blocks in an FPGA implementation). Each slice contains a number of look up tables (LUTs) that are used to implement AND gates, OR gates and other Boolean functions. In addition to LUTs, slices also contain a number of registers that hold state and are used to implement sequential logic. In the device utilization report, any slice that is used even partially is counted towards the number of occupied slices. A design may be fitted into fewer slices if necessary, but mapping unrelated logic into the same slice may impact the ability to meet timing constraints [START_REF]Xilinx, Virtex-6 Family Overview, Xilinx Data Sheet[END_REF]. The Virtex-6 provides 18 Kb and 36 Kb blocks of RAM for storing data. Our implementations did not require any 36 Kb RAM blocks. The iterative looping architecture employed in the design minimizes the hardware resources needed for each algorithm. The FF1 implementation uses two cascaded AES blocks per round, which causes the area and number of slices required to be approximately twice those of one AES block. FF2 makes only one call to AES per round, but uses an additional AES block to generate the subkey. FF3 has the smallest footprint of the three algorithms because it relies sparingly on calls to AES.

The maximum frequency is based on the worst path delay found in the design, and it indicates the fastest frequency at which a signal may be toggled given this constraint. A simulation test bench was used to measure to operational latency of each implementation. The numbers of clock cycles required for completing one round and for completing an entire encryption cycle are reported for each algorithm (Table 2). The FF1 algorithm makes two calls to AES per round, which makes it the slowest of the three algorithms. FF2 is faster than FF1 because of its single call to AES in its F-block. FF3 is the fastest of the three algorithms because it uses only eight rounds. The overall results indicate that the FF3 algorithm requires the least hardware resources and has the lowest operational latency.

Conclusions

The FF1, FF2 and FF3 format-preserving encryption algorithms have important applications in critical infrastructure protection. In particular, the algorithms could be incorporated in security modules for legacy protocols and databases that are currently incompatible with standard cryptographic practices.

The experimental results demonstrate that algorithms are secure based on their ability to obfuscate repetitive input data. The algorithms successfully encipher plaintext with twelve of thirteen bytes containing a deterministic sequence. The three algorithms (as recommended by NIST) demonstrate the inherited security characteristics of the underlying AES cipher.

Because the algorithms can be implemented with AES as the underlying block cipher, they are suitable for implementation on any number of hardware platforms. The characteristics of the underlying AES implementation contribute strongly to the security and speed of the three algorithms. The FF3 algorithm requires the least hardware resources, has the lowest operational latency and has similar security performance as the other two algorithms.

The results also demonstrate that the three algorithms can obfuscate data streams with large amounts of repeated data without overhead or significant hardware costs. As such, the FF1, FF2 and FF3 algorithms provide good options for retrofitting encryption in legacy critical infrastructure systems without sacrificing interoperability or performance.

The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense or U.S. Government.

Figure 1 .

 1 Figure 1. Modern cryptography hierarchy [1].

Figure 2 .

 2 Figure 2. Feistel structure of the FF1, FF2 and FF3 algorithms [6].

Figure 3 .

 3 Figure 3. FF1 encryption algorithm adapted from [6].

FF1

  Algorithm: The FF1 algorithm is derived from FFX as proposed by Bellare, et al.[START_REF] Bellare | The FFX Mode of Operation for Format-Preserving Encryption[END_REF]. Figure3describes the FF1 algorithm. The NIST recommendation designates a maximally balanced Feistel structure that for an odd length message of size n divides the message into A and B halves of size u = ⌊n/2⌋ and v = nu. The original FFX algorithm uses an alternating-Feistel structure, leaving the user to choose the size of the halves along with eight other parameters. Of the three recommendations, FF1 supports the greatest range of lengths for formatted data and the tweak.

Figure 4 .

 4 Figure 4. FF2 encryption algorithm adapted from [6].

Figure 5 .

 5 Figure 5. FF3 encryption algorithm adapted from [6].

Figure 6 .

 6 Figure 6. Plaintext strings in the 3 Front and 3 Random scenarios.

Figure 7 .

 7 Figure 7. Mean entropy.

  used several statistical tests to evaluate the AES candidates: frequency test, block frequency test, cumulative sums test, runs test, long runs of ones test, rank test, spectral test, non-periodic templates test, overlapping template test, universal statistical test, random excursion test, random excursion variant test, Lempel-Ziv complexity test, linear complexity test and an approximate entropy test

Table 1 .

 1 Mean entropy.

	Scenario	Plaintext	FF1	FF2	FF3
	3 Front	7.240370	7.996331 7.996487 7.996388
	3 Random	7.240221	7.99654	7.996503 7.996498
	6 Front	6.402844	7.996482 7.996472 7.996564
	6 Random	6.402425	7.996358 7.996373 7.996502
	9 Front	5.448800	7.996368 7.996341 7.996511
	9 Random	5.448699	7.996375 7.996554 7.996432
	12 Front	4.256321	7.942249 7.939892 7.942226
	12 Random	4.256166	7.996518 7.996558 7.996404
	All Random	7.996332	7.996460 7.996348 7.996424

Table 2 .

 2 FPGA performance.

		AES	FF1	FF2	FF3
	Number of Slice Registers	5,801	11,285	11,323	5,592
	Number of Slice LUTs	3,452	7,426	6,825	3,587
	Number of Occupied Slices	1,864	3,850	3,728	1,820
	Number of 18K Block RAMs 172	343	342	170
	Maximum Frequency (MHz)	336.315 279.587 284.592 283.427
	Clock Cycles per Round	3	68	33	32
	Clock Cycles per Encryption 31	707	374	269


Goitom Weldehawaryat

Stephen Wolthusen

Asynchronous Binary Byzantine Consensus over Graphs with Power-Law Degree

Keywords: Critical infrastructures, Byzantine consensus, power-law networks

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The consensus problem is a fundamental problem in the domain of faulttolerant distributed systems. It requires the system processes to agree on a common value despite the presence of some faulty processes. Fischer, et al. [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] have shown that it is impossible to achieve consensus in an asynchronous distributed system that is subject to even a single crash fault. However, Ben-Or [START_REF] Ben-Or | Another advantage of free choice: Completely asynchronous agreement protocols[END_REF] has shown that a randomization approach can achieve binary consensus in an asynchronous distributed system that is subject to crash faults.

In applications involving the monitoring and control of electrical power networks, it is critical to detect faults and potential attacks such as sensor manipulations, as well as to ensure that network operations satisfy the mandatory real-time constraints. Existing results have explicitly or, more often, implicitly assumed full or random connectivity, but many large real networks (e.g., electrical power and telecommunications networks) display a scale-free nature, and are sparse and follow a power-law degree sequence. While it is possible to add edges to the graphs (e.g., adding communications links to control networks that partially coincide with electrical power networks), the cost of the additional links must be minimized.

Most critical infrastructure systems require correct interactions among large numbers of geographically-dispersed nodes (e.g., sensors and actuators) as well as at higher levels (e.g., SCADA systems). These systems cannot normally employ fail-stop semantics and must be fault-tolerant; however, robustness to targeted attacks requires a stronger model, namely Byzantine fault tolerance. Byzantine fault detection and tolerance is a known hard problem, as is the consensus problem in the presence of Byzantine faults. The ability to rapidly reach consensus is critical; in most cases, the dominant problem is message complexity.

Castro and Liskov [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], Chun, et al. [START_REF] Chun | Attested appendonly memory: Making adversaries stick to their word[END_REF] and Veronese, et al. [START_REF] Veronese | Highly-resilient services for critical infrastructures[END_REF] have proposed replication algorithms to implement highly-resilient services; some of these algorithms can be used to control services such as water, power and gas [START_REF] Hauser | Security, trust and QoS in next-generation control and communication for large power systems[END_REF][START_REF] Verissimo | The CRUTIAL architecture for critical information infrastructures[END_REF]. Critical infrastructures require highly-resilient services that function correctly even under Byzantine faults that may corrupt some of the computers involved. Asynchronous Byzantine consensus algorithms address this problem by allowing critical services to continue to operate correctly even when system components exhibit arbitrary behavior (e.g., crashes or intrusions by attackers). Recently, the problem of solving asynchronous Byzantine consensus with 2f +1 processes has attracted attention [START_REF] Chun | Attested appendonly memory: Making adversaries stick to their word[END_REF][START_REF] Correia | Asynchronous Byzantine consensus with 2f + 1 processes[END_REF]. This is possible with a hybrid system model, which extends the traditional model by incorporating a trusted/trustworthy component that constrains the power of faulty processes to exhibit certain behaviors.

One of the core benefits of such an approach is the ability to rely on redundant sensors in large networks for detecting faults and adversarial actions without degrading real-time operations. It is, therefore, critical to minimize the message complexity of a consensus algorithm that reduces latency (e.g., for management of telecommunications networks and state estimation and control in electrical power networks). This has led to the consensus problem being studied in scale-free networks by Wang, et al. [START_REF] Wang | Optimal agreement in a scale-free network environment[END_REF] using the Barabasi-Albert model [START_REF] Barabasi | Emergence of scaling in random networks[END_REF], which relies on a generative model. However, the preferential attachment model only produces networks with a power-law exponent of three, and some important properties observed in large real-world networks are still missing in graphs that exhibit different exponents while still showing a power-law degree sequence. Therefore, we argue that non-complete graphs are particularly interesting when studying the feasibility and efficiency of consensus problems.

Building on our earlier work on Erdos-Renyi random graphs [START_REF] Weldehawaryat | Asynchronous message-passing binary consensus over non-complete graphs[END_REF], this paper focuses on randomized asynchronous binary Byzantine consensus for graphs in the G(n, ⃗ d) configuration model with power-law degree sequence and presents an algorithm that achieves the desired primary result with reduced message complexity for non-complete graphs. To reach this objective, a refinement of Ben-Or's algorithm recently proposed by Correia, et al. [START_REF] Correia | Asynchronous Byzantine consensus with 2f + 1 processes[END_REF] is considered. Their approach differs from this work in that it considers fully-connected communications networks. This paper shows that, when choosing a non-complete graph as a communications system, no additional asynchronous messaging assumptions are needed. Moreover, it is possible to increase message complexity efficiency by considering higher degree nodes that forward received messages with high probability P high and lower degree nodes that forward messages with low probability P low .

Related Work

The consensus problem is a fundamental problem in the domain of distributed systems. Fischer, et al. [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] proved that a deterministic algorithm cannot solve the consensus problem in an asynchronous model even in the presence of one faulty process. In the asynchronous model, each communication can take an arbitrary and unknown amount of time, and there is no assumption of a joint clock as in the synchronous model. However, Ben-Or [START_REF] Ben-Or | Another advantage of free choice: Completely asynchronous agreement protocols[END_REF] showed that a randomized algorithm can solve the consensus problem even when a constant fraction of processes are faulty. Interested readers are referred to [START_REF] Aguilera | The correctness proof of Ben-Or's randomized consensus algorithm[END_REF][START_REF] Aspnes | Randomized protocols for asynchronous consensus[END_REF] for a complete proof of correctness of Ben-Or's algorithm and a detailed survey of randomized consensus protocols. Consensus in the asynchronous Byzantine message-passing model has been shown to require n ≥ 3f + 1 processes in several variations of the basic model. Recently, Correia, et al. [START_REF] Correia | Asynchronous Byzantine consensus with 2f + 1 processes[END_REF] showed that it is possible to solve Ben-Or's asynchronous Byzantine binary random consensus problem with 2f + 1 processes. Consensus protocols play an important role in replication algorithms that can be utilized to protect critical infrastructures [START_REF] Correia | Byzantine consensus in asynchronous message passing systems: A survey[END_REF]. Castro and Liskov [START_REF] Castro | Practical Byzantine fault tolerance and proactive recovery[END_REF], Chun, et al. [START_REF] Chun | Attested appendonly memory: Making adversaries stick to their word[END_REF] and Veronese, et al. [START_REF] Veronese | Highly-resilient services for critical infrastructures[END_REF] proposed replication algorithms to implement highly-resilient services; some of these algorithms can be used to control services such as water, power and gas [START_REF] Hauser | Security, trust and QoS in next-generation control and communication for large power systems[END_REF][START_REF] Verissimo | The CRUTIAL architecture for critical information infrastructures[END_REF].

Traditionally, the consensus problem was formulated in the context of random and fully-connected networks, although this assumption is typically not stated. Unfortunately, many large complex networks are poorly approximated by complete graphs or even simple random graphs. Many of these networks also exhibit scale-free properties. This has led to the consensus problem being studied in scale-free networks by Wang, et al. [START_REF] Wang | Optimal agreement in a scale-free network environment[END_REF] using the Barabasi-Albert model [START_REF] Barabasi | Emergence of scaling in random networks[END_REF], which relies on a generative model. However, the preferential attach-ment model only produces networks with a power-law exponent of three and some important properties observed in large real-world networks are still missing in these graphs, which exhibit different exponents while showing a powerlaw degree sequence. This paper focuses on the randomized asynchronous binary Byzantine consensus problem for graphs in the G(n, ⃗ d) configuration model with power-law degree sequence.

Asynchronous Byzantine Consensus Problem

This section describes the Byzantine consensus problem and its assumptions.

Asynchronous Byzantine Consensus

Asynchronous Byzantine consensus algorithms are important when constructing Byzantine fault-tolerant systems. The consensus problem seeks to get a set of processes to agree on a common value. Many variants of the consensus problem have been proposed. However, this paper considers binary consensus in an asynchronous environment, where faulty processes can behave in an arbitrary manner and no assumptions are made about the relative speed of processes and the timely delivery of messages. A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to agree on a value.

The consensus problem is solved when the following requirements are satisfied [START_REF] Correia | Byzantine consensus in asynchronous message passing systems: A survey[END_REF]:

Agreement: All the processes choose the same value.

Validity:

The common output value is an input value of some process. P-Termination: Every correct process eventually decides with probability one.

Fischer, et al. [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] have shown that a deterministic protocol cannot guarantee agreement even against benign failures in asynchronous systems. Over the years, several techniques have been proposed to circumvent this impossibility result. One of the first approaches to solving the consensus problem was to use randomization. Existing results allow processes to reach an agreement in fullyconnected networks. However, the case of non-complete graphs is particularly interesting when studying the feasibility and efficiency of consensus problems in real-world networks such as the Internet, World-Wide Web, metabolic networks and power networks with approximate structures [START_REF] Pagani | The power grid as a complex network: A survey[END_REF], all of which have the power-law form P (k) ∼ k -γ .

Several models have been introduced to generate graphs with power-law distributions. This paper considers a simple generalization of the traditional random graph model called the configuration model [START_REF] Aiello | A random graph model for power-law graphs[END_REF][START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF]. Chung and Lu [START_REF] Chung | Complex Graphs and Networks[END_REF] introduced a modified version of the configuration model, where, given a sequence (d 1 , . . . , d n ), nodes v i , v j are connected with probability proportional to d i d j . Bollobas, et al. [START_REF] Bollobas | The degree sequence of a scale-free random graph process[END_REF] also showed analytically that graphs constructed according to the preferential attachment rule obey a power-law degree distribution with an exponent of three. The consensus problem has been studied in scale-free networks proposed by Barabasi and Albert [START_REF] Barabasi | Emergence of scaling in random networks[END_REF]. However, the preferential attachment model only produces networks with a power-law exponent of three and some important properties observed in large real-world networks are still missing in these graphs.

The structure of electrical power transmission networks has been studied extensively in a number of countries [START_REF] Pagani | The power grid as a complex network: A survey[END_REF]; despite differences in structure, the efforts have retained an overall power-law degree sequence. This clearly motivates our work on arbitrary power-law degree sequences because it allows the fine-tuning of message complexity and the identification of minimum additional edge requirements.

System and Network Models

This section describes the system and network models.

System Model. We consider a distributed system consisting of n processes

where n ≥ 2. The processes may be correct or faulty. Correct processes always behave according to their specifications while faulty processes exhibit arbitrary (Byzantine) behavior.

We consider a Byzantine failure model that does not impose any constraints on how processes fail for a certain fraction of network nodes in a distributed system. This (non)assumption about how processes fail is essential for systems that are exposed to malicious attacks and intrusions. However, only f out of n processes can be faulty with n ≥ 2f + 1, where n is the number of processes in the system and f is the maximum number of faulty processes [START_REF] Correia | Asynchronous Byzantine consensus with 2f + 1 processes[END_REF]. The communications network consists of communications channels used by processes to communicate via messages sending and message receiving primitives. The communication channels are reliable in that messages that sent to and received by the correct processes and are not modified by the communications medium. However, messages may be delayed and may be delivered in a different order than they were sent.

We also consider an asynchronous system in which there are no bounds on the message delays and relative speeds of processes. In such a system, it is impossible to detect missing messages; there is also no way to distinguish between a delayed message and a message that is not sent. This (non)assumption is important because attackers often violate some timing properties by launching denial-of-service attacks against processes and communications. However, we assume the existence of failure detector modules that provide hints about faulty processes. In particular, we employ muteness failure detectors, which suspect that a process is mute either because it crashed or is Byzantine and stopped sending messages according to the algorithm [START_REF] Doudou | Tolerating arbitrary failures with state machine replication[END_REF].

Network Model. Power-law (scale-free) networks are characterized by a specific structural feature of power-law degree distributions. Examples of scale-free real-world networks include power networks, the World-Wide Web, email networks, social networks and networks of Internet routers [START_REF] Crucitti | Efficiency of scalefree networks: Error and attack tolerance[END_REF]. Scale-free networks usually have nonhomogeneous topologies where the majority of the nodes have few links, but a small number of nodes have a large number of links and P (k) decays according to the power-law P (k) ∼ k -γ where γ is the power-law exponent [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF]. Most real-world networks have the scale-free property with γ satisfying the constraint 2 < γ < 3 [START_REF] Albert | Statistical mechanics of complex networks[END_REF]. For 2 ≤ γ < 3, a network with N nodes has constant or at most O(logN ) average degree, but the variance of the degree distribution is unbounded. It is in the regime of γ that power-law networks display many of the advantageous properties, such as small diameter, tolerance to random node deletions and a natural hierarchy where there are sufficiently many nodes of high degree.

Many models have been proposed for representing real networks. One of them is the configuration model, which creates random graphs that can have any generic degree distribution, and can, therefore, capture the degree characteristics of real-world networks. This paper uses the configuration model with a predefined degree distribution to generate static power-law networks.

We consider an undirected simple graph G(n, d) consisting of N vertices with a degree sequence ⃗ d = (d(1), d(2), . . . d(n)). The neighborhood of n i is denoted by Λ i and the degree distribution for the graph denoted by P (k) is defined to be the fraction of nodes in the graph with degree k. The degree distribution can be calculated as follows [START_REF] Sharan | Analysis of Biological Networks: Random Models[END_REF]:

P (k) = |{v|d(v) = k}| N where d(v)
is the degree of node v and N is the number of nodes in the graph. The average degree in the graph is denoted by ⟨k⟩ ≡ k kP (k). The number of edges in the graph is given by m = ⟨k⟩N/2.

Reliable Broadcast in Power-Law Networks

This section investigates the performance of an efficient reliable broadcasting algorithm in the configuration model with power-law degree sequence. The performance of reliable broadcasting in power-law networks can be improved by separating nodes into two sets, each set using a different probability when selecting the neighbors to which received messages are forwarded [START_REF] Hu | Efficient dissemination algorithm for scale-free topologies[END_REF]. This allows high-connectivity nodes to forward messages to their neighbors with a high probability and low-connectivity nodes to forward messages with low probability. The idea behind the algorithm is to reduce the number of redundant messages sent to high-degree nodes and, thus, reduce the overall message complexity. The algorithm has two phases. The first phase searches for high-degree node(s) while the second phase disseminates messages. During the first phase, the network is searched using short biased random walks and bond percolation, where a query message is forwarded on each edge with probability higher than the bond percolation threshold of the network.

Percolation Search for High-Degree Nodes

The percolation search technique is an efficient way of searching for highdegree node(s) in power-law networks. Power-law networks have few nodes with very high degrees. A node is considered to be highly connected if its degree is greater than or equal to half the maximum degree in the network. The percolation search algorithm leverages the power-law property by making queries reach high-degree nodes.

Cohen, et al. [START_REF] Cohen | Resilience of the Internet to random breakdowns[END_REF] have shown that, if the power-law degree distribution γ is greater than three, then the critical probability threshold for the integrity of a power-law network system being compromised is one. In other words, they showed that, for a network with γ less than three, the critical value q c of q where the transition takes place at which a giant component forms is zero or negative (this indicates that the network always has a giant component or the network always percolates). The results ensure the connectivity of an undirected power-law network when γ is less than three.

The percolation search algorithm has three phases [START_REF] Sarshar | Percolation search in powerlaw networks: Making unstructured peer-to-peer networks scalable[END_REF]:

Content Implantation: During this phase, a node caches or implants its content in some other nodes in the network. The node does this by taking a short random walk through its nodes, starting from itself and duplicating its content at each step. The random walk has size O(logN ) where N is the number of nodes in the network.

Query Implantation: When a node issues a query, it first executes a short random walk of size O(logN ) and implants its query request in the nodes visited. For a power-law graph, the random walk quickly converges towards high-degree nodes. However, choosing high-degree nodes to traverse first, improves the search. This way, the requester and all the nodes that have the query implanted in them take part in the search. If a query reaches a node that has already received the same query from another neighbor, the query is not implanted; this avoids loops in the query path.

Bond Percolation: All the implanted query requests are propagated independently and in parallel using a probabilistic broadcast scheme. In this scheme, a node receiving a query message for the first time, relays the message on each of its edges with a probability q, which is vanishingly greater than the percolation threshold q c (q= q c γ) of the underlying power-law network [START_REF] Sarshar | Finite Percolation at a Multiple of the Threshold[END_REF]. The percolation probability q corresponds to the probability with which network nodes communicate a message to any of their neighbors.

Message Complexity

In a straightforward parallel search technique, each node, upon receiving a query message, forwards it to all its neighbors, unless a node has already received the query message. This leads to O(ln(ln N )) total messages for every Algorithm 2 : Byzantine Consensus Algorithm (Process pi).

esti → vi {current estimate of the value to be decided}

Step 0: ri → 1 {round number} Step 1: RELIABLE BROADCAST PHASE1(ri, esti)

Step 2: wait until (valid messages PHASE1(ri, -) are received at least nf processes) and (∀j : valid message PHASE1(ri, -) is received from pj or pj is suspected by pi's FD module) if (more than n/2 messages have the same value) then RELIABLE BROADCAST PHASE2(ri, v,decision) else RELIABLE BROADCAST PHASE2(ri, ⊥) end if

Step 3: wait until (valid messages PHASE1(ri, -) are received at least nf processes) and (∀j : valid message PHASE2(ri, -) is received from pj or pj is suspected by pi's FD module) if (there are nf decision messages PHASE2(ri, v, decision)) then DECIDE(v) else if (there is one decision message PHASE2(ri, v,decision)) then esti → v else esti → 1 or 0 with probability 1/2 end if

Step 4: ri → ri + 1 go to Step 1 message is forwarded from n j to P high /P low |Λ i | other nodes. In a scale-free network, a given node on the average propagates a message to P high /P low ⟨k⟩ nodes. The decision about the degree of a node (high or low) depends on a threshold degree d. By changing the probability values, it is possible to control the effective connectivity of the network while information is forwarded. The message complexity of the algorithm can be considerably reduced because only high-degree nodes (e.g., hubs that are few in number in a power-law network) are responsible for message forwarding with high probability. This differs from normal broadcasting algorithms in which all the periphery nodes also forward messages.

Consensus Algorithm

This section describes the consensus algorithm and discusses its key features.

Consensus Protocol

In the consensus problem, each process begins with an initial value v i ∈ {0, 1} and all the correct processes must decide on one of the proposed values v. This section presents a binary consensus protocol (Algorithm 2) adapted from the Correia, et al. variant of Ben-Or's algorithm. The protocol uses the under-lying reliable broadcast over power-law networks as the basic communication primitive (Section 4).

The protocol operates in rounds, where each round has two stages. In the first stage of a round, each process p i reliably broadcasts its current estimate v i using the high-degree nodes and waits to receive nf valid messages. If a process receives a strict majority of reports for the same value v, then it proposes v to all the processes; otherwise, it proposes ⊥.

In the second stage of a round, p i broadcasts v using high-degree nodes to each destination process, waits for nf valid messages PHASE2, and then decides on v if there are nf decision messages PHASE2. If there is one decision message PHASE2 with value v different from ⊥, then p i adopts v as its new estimate and a new round is initiated. Otherwise, p i adopts a random bit (0 or 1) with probability 1/2 for the estimate and a new round is initiated.

Proof of Correctness

The following is a brief proof of correctness of the consensus algorithm:

Agreement: If a correct process decides v in round r, then no correct process decides v ′ ̸ = v in round r ′ ≥ r. A correct process p decides the value v in round r if and only if it receives (n-f )p valid decision messages PHASE2 (r i , v, decision).

Validity: If some process p decides v, then v is the initial value of some process.

Termination: Every correct process eventually decides. It is necessary to prove that the algorithm does not block indefinitely at some point. The only points where a process blocks are where it waits for messages, so it is only necessary to prove that the process does progress and eventually terminates.

Interested readers are referred to [START_REF] Weldehawaryat | Asynchronous message-passing binary consensus over non-complete graphs[END_REF] for a detailed proof of correctness of an algorithm that has the same basic structure.

Message Complexity Analysis

This section compares the message complexity of the Correia, et al. variant of Ben-Or's algorithm over non-complete graphs using the G(n, ⃗ d) configuration model with the original Correia, et al. variant of Ben-Or's algorithm, which assumes a flooding algorithm in which every node of a power-law network forwards its first-time received message once to its one-hop neighborhood.

First, we assume that correct processes do not suspect correct processes, i.e., all correct processes receive all the messages from each other. In both algorithms, messages are broadcast in both phases of each round. However, in the original Correia, et al. variant of Ben-Or's algorithm, messages are sent to every other process in the system, resulting in ⟨k⟩N/2 messages during each phase. On the other hand, in the modified Correia, et al. variant of Ben-Or's algorithm, a high-degree node forwards a received message msg with a high probability P high and a low-degree node forwards it with a low probability P low , resulting in a total of P high ⟨k⟩ + P low ⟨k⟩ messages during each phase.

In both algorithms, there is eventually a round r in which all the correct processes set est i to the same value v either in Line 13 or in Lines 11 and 13 of the algorithms. When this occurs, in round r + 1, all the correct processes broadcast v in Line 3, all the processes receive at least nf PHASE1 messages with the value (since there are at least that many correct processes), and all the correct processes broadcast PHASE2(r+1, v, decision) messages, and all receive each other's PHASE2 messages in Line 10. Since in round r + 1 all the correct processes broadcast v in Line 3 and PHASE2(r + 1, v, decision), the original Correia, et al. variant of Ben-Or's algorithm sends ⟨k⟩N 2 /2 messages over the entire graph. In contrast, the modified Correia, et al. variant of Ben-Or's algorithm sends only P high N ⟨k⟩ + P low N ⟨k⟩ messages over the non-complete graph.

It is important to also consider the message complexity of the percolation search for high-degree nodes during network setup in the modified Correia, et al. variant of Ben-Or's algorithm. Thus, with qE= q c ⟨k⟩N/γ total messages, any content/high-degree node can be located with probability approaching one in time O(logN ). Putting everything together, if no process is suspected by the eventually-perfect muteness failure detector, then the original Correia, et al. variant of Ben-Or's algorithm requires ⟨k⟩N/2 messages and the modified Correia, et al. variant of Ben-Or's algorithm requires P high ⟨k⟩+P low ⟨k⟩+q c ⟨k⟩N/γ messages. In the latter case, the original Correia, et al. variant of Ben-Or's algorithm requires ⟨k⟩N 2 /2 messages and the modified Correia, et al. variant of Ben-Or's algorithm requires P high N ⟨k⟩ + P low N ⟨k⟩ messages. Since O(P high ⟨k⟩ + P low ⟨k⟩ + q c ⟨k⟩N/γ) ≪ ⟨k⟩N/2 or O(P high N ⟨k⟩ + P low N ⟨k⟩ + q c ⟨k⟩N/γ) ≪ O(⟨k⟩N 2 /2), there is a significant reduction in message complexity in the modified Correia, et al. variant of Ben-Or's algorithm.

Conclusions

This paper has studied the existence and efficiency of randomized asynchronous binary Byzantine consensus for graphs in the G(n, ⃗ d) configuration model with power-law degree sequence. A key result is that it is possible to reduce the message complexity in non-complete random graphs using high-degree nodes to forward messages with high probability and low-degree nodes to forward messages with low probability. Additionally, the modified Correia, et al. variant of Ben-Or's algorithm over non-complete graphs using the G(n, ⃗ d) configuration model with power-law degree sequence yields the desired primary result. Specifically, it is possible to solve the asynchronous Byzantine binary consensus problem with 2f + 1 processes over non-complete graphs using the G(n, ⃗ d) configuration model with power-law degree sequence by employing a reliable broadcast algorithm (that requires a wormhole component, although this has a considerably lower cost than increasing the density of the graph) and an eventually-perfect muteness failure detector without any additional asynchrony assumptions.

The message complexity analysis shows a significant reduction in message complexity in the modified Correia, et al. variant of Ben-Or's algorithm over non-complete graphs using the G(n, ⃗ d) configuration model with power-law degree sequence. This occurs when high-degree nodes forward messages with a high probability and low-degree nodes forward messages with a low probability. Because the number of the low-degree nodes is much higher than the number of high-degree nodes in a scale-free network, the message complexity is considerably less than that for a flooding algorithm. The significantly lower message complexity for the consensus algorithm reduces latency during network management in telecommunications networks and state estimation and control in electrical power networks.

Our future research will investigate the properties of multiple power-law graphs and efficient consensus algorithms over these graphs. These graphs are commonly encountered in telecommunications networks and electrical power networks, which are nominally distinct, but frequently interconnected.

query. It has been proven that, when 2 < γ < 3, the diameter of the network d ∼ ln(ln N ) is smaller than small real-world networks (O(ln N )) and remains almost constant while the network is growing [START_REF] Cohen | Scale-free networks are ultrasmall[END_REF]. The bond percolation step guarantees that a query message is received by nodes in a high-connected component of diameter O(log N ) and consisting of high-degree nodes. The content and query implantation steps ensure that the content/message of a node are cached in at least one of the nodes in this high-degree connected component with probability approaching one, and that one of the nodes in the connected component receives a query implantation with probability approaching one.

When a node issues a query message, each edge passes it with probability q. Thus, with qE= q c ⟨k⟩N/γ total number of messages, any content/high-degree node can be located with probability approaching one in time O(log N ). After the first phase, the second phase of Algorithm 1 starts message dissemination using the hub node(s). Upon receiving this message and comparing the degree of a node with the degree threshold (d), a high-degree node forwards the received message msg with a high probability P high or a low-degree node forwards it with a low probability P low where P high > P low . At each step, the