Benchmarking Hash and Signature Algorithms

By Peng Wang, Carl Hua, and Michael Zochowski

Introduction

Hash and signature algorithms are the cornerstone of blockchain and crypto networks. Among other uses, they enable unforgeable identification and messaging, immutable recording of transactions, and efficient data storage. These properties make them a critical part of consensus, transaction verification, and, in proof-of-work networks, mining.

With the exception of proof-of-work (which, aside from extreme cases, is decoupled from the hash algorithm performance), the performance of the chosen hash and signature algorithms in a network has a major impact on performance. Every block and each transaction contained therein requires multiple signature verifications, hash verifications, and — for validators — a signature production. We estimate that the average crypto network node spends 25–65% of its CPU usage for hashing and signing, excluding mining. Optimizing these functions is one of the best ways to boost overall network performance, including transaction capacity and confirmation latency.

When we were architecting the Logos system, we were faced with the question of what signature and hashing algorithms best match our needs for high performance and minimal overhead. While there are many benchmarking results available on the web, they can vary significantly depending on the exact system environment. In particular, Logos uses proof-of-stake and a heavily optimized PBFT consensus scheme. We require multisignatures for efficient consensus, single signatures for transaction approval, and hashing for message digests, Merkle Trees, hashchains, and other data structures.

We therefore tested the performance of several hash algorithms and signature algorithms in our development environment last summer. For this benchmarking, we used AWS t2.2xlarge instances with 8 vCPUs from an E5–2686 v4 CPU at 2.30GHz running Ubuntu 16.04 with kernel 4.4.0.

In this article, we summarize those benchmarking findings. You can find the raw code we used published on our Github here. This article is intended to be a technical overview and assumes familiarity with the various concepts and algorithms we tested.

Hash Algorithms

We tested some of the hash algorithms available in Openssl’s libcrypto, version 1.1.1. The figure below is the per byte time (nanoseconds) of the hash algorithms with different message sizes. The x-axis is in log scale. The table underneath is the raw data, sorted by the column of message size 1024 bytes.

We can see that (1) for smaller messages up to 3KB, the cost per byte decreases when the message size increases, and for larger messages, the cost per byte is constant; and (2) the sha256 and sha512 have good performance, and blake2b512 is even faster.

Please note that sha1 and md5 were included only for reference, and they were not considered for use in Logos due to their security issues.

Messages in Logos are typically in the range of 512B to 2KB. The next figure shows the cost of hashing 512B, 1KB, and 2KB messages. Please note the y-axis is per message time. This clearly confirms the intuition that when the message size doubles, cost also roughly doubles.

We chose blake2 for Logos’s hashing algorithm due to its speed. We specifically use blake2b256 because it targets 64 cpu architecture and provides 128-bit security.

In addition to its use in data structures and message digests, hashing algorithms are used in Logos for a minor proof-of-work spam prevention mechanism. For this role, we additionally considered Scrypt, Balloon, and Argon2id, but exclude them here for simplicity.

Signature Algorithms

We tested the performance of the following signature algorithms: ECDSA (Openssl), EdDSA (Nano), EC-Schnorr (Zilliqa), and BLS (Keep).

Single signatures

First, we show the cost of single signatures in the figures below. Similar to the previous section, we have the “Time per byte” figure for all message sizes, its raw data table, and the “Time per message” figure for 512B, 1KB, and 2KB messages, where time is measured in microseconds. We can see that (1) EdDSA is very fast, (2) for any algorithm, the cost of signing (verifying) 512B, 1KB, or 2KB messages are about the same.

In general, a signature algorithm signs the digest of messages. I.e., a message is hashed to a fixed size digest, then the signature is computed on the digest. So the cost includes two parts (1) hashing cost which grows with message size, (2) signature operation cost which is constant. This is clearly shown in the last figure in this section. For this reason, we included blake2b512 in all the figures as a reference. In general, the cost of (2) significantly dominates that of (1).

We decided to use EdDSA for Logos since it was the most efficient signature scheme and has a number of robust, open source implementations.

Multisignatures

Transaction validation in Logos involves a set of 32 elected delegates running consensus instances in parallel. Each consensus instance involves a batch of transactions and is run by a primary delegate with 31 backups. A supermajority (greater than ⅔) of delegates must sign off on each batch of transactions for them to be confirmed. Safety is strongly guaranteed through a combination of mathematically proven distributed algorithms and game theory.

If Logos were to implement this system using single signatures, validating that a batch (and thus the contained transactions) is valid as well as storing the network history would be extremely inefficient in both CPU and storage space since each batch involves at least 22 signatures. We therefore use a multisignature scheme to make signature size constant, regardless of the number of individual signatures it contains.

We tested three multisignature algorithms. The Schnorr multisignature is a two-round interactive algorithm. The BLS_Diff_Msg is a simple aggregation algorithm included in herumi’s code “github.com/herumi”. It does not have a public key aggregation algorithm and is not secure when the messages could be the same. The BLS_Same_Msg is built on top of herumi’s code. It has a public key aggregation algorithm, and it requires all the messages are the same.

In this section, all the messages are 512B, since we already know message sizes only affect the hashing cost of signatures, from the previous section. The figure below shows the time cost of the operations. Some observations:

1. “Public key aggregation” cost is small, and is a one time cost for the same set of delegates.
2. The Schnorr algorithm’s signing operation is a bit higher than BLS.
3. BLS_Diff_Msg’s signature aggregation cost is very low and BLS_Same_Msg’s signature aggregation cost is much higher.
4. The signature verification cost of BLS_Diff_Msg is very high.
5. No matter which algorithm, if some of the input to the signature aggregation function are corrupted, the cost of finding the corrupted ones (marked as Response Verify in the figure) is very high.

The next figure is the cost of the delegates of one multi-signature generation. We considered two cases, (A) all 31 delegates returned good individual signatures (or equivalent in Schnorr) to the primary, (B) some (<1/3) individual signatures are corrupted. Other cases such as missing signatures, or too many corrupted signatures which resulted in a failed round should have less cost as compared to cases (A) and (B).

Thus, Schnorr outperforms BLS in CPU space, but BLS is within an order of magnitude. What these results do not show is the cost of messaging. In particular, a Schnorr multisignature requires one more round of messages between the aggregator and single signers than BLS, which complicates the core consensus protocol and imposes a significant time overhead due to latency and communication. Assuming a 200ms latency (a multisignature is limited by the highest latency signer), the Schnorr multisignature would have an additional latency of 200,000 microseconds. This means that BLS is drastically more time efficient than Schnorr in a real world setting. In addition, BLS requires only half the data as Schnorr for the equivalent security level. For example, the signature size of Schnorr multisignature scheme is 64 bytes for 128-bit security, while the signature size of BLS is only 32 bytes.

For these reasons, among others, we decided to use BLS multisignatures in Logos. To enable signature aggregation, we extended publicly available implementations based on Boneh et al. We’ll release that implementation publicly when we open-source the Logos core codebase.

More Benchmarking Data: eBACS

While it’s always important to test out the algorithms in the specific context you wish to deploy them, ECRYPT Benchmarking of Cryptographic Systems (eBACS) is a great source of general benchmarking results of many cryptographic algorithms.

If you’d like to keep up with what we are doing:

Follow us: Twitter | Discord | Telegram | Reddit

Read: White paper | Logos website