Adapting BLS Signature Aggregation to CodeChain Foundry
We introduced the BLS signing scheme to replace the Schnorr signing scheme in CodeChain Foundry. At present, the code can be found in the experimental branch of Foundry Github. (https://github.com/CodeChain-io/foundry/commits/bls-consensus-signature)
The main goal of adapting BLS signing is to exploit signature aggregation of the BLS scheme, which reduces the size of signatures in block seals. In fact, the Schnorr scheme, which we previously used, supported signature aggregation as well. However, we could not exploit the feature in Tendermint consensus because it requires the number of signers to be predetermined at the signing step. Compared to the Schnorr scheme, the BLS signature aggregation does not require any oracle for signature aggregation, so it can be easily adapted to the Tendermint consensus engine.
However, the BLS scheme is known to be slower than the Schnorr scheme. Therefore, we should measure the performance degradation by the BLS scheme as well as its storage benefits from achieving signature aggregation.
Storage
Each block header contains a seal field, which stores the aligned signatures of validators who voted to the block. This occupies considerable space in the block header, so reducing the signatures’ size is highly desired.
Each BLS signature occupies 48 bytes, which is 16 bytes smaller than a 64-byte-Schnorr-signature. Moreover, multiple BLS signatures can be aggregated into a single signature, allowing further compression. With the Schnorr scheme, 64 * 30 = 1920 bytes are required to store validator signatures in a block seal, assuming that there are 30 validators, which is a typical number in Foundry. Only 48 bytes, the size of a single signature, were needed when the BLS scheme was applied.
Performance benchmark
Performance of signing and verifying a single signature (ns)
However, the BLS scheme slows down the signing and the verification step significantly. As the table shows, each Schnorr signing and verification takes 47,381 ns and 52,116 ns, respectively. On the other hand, BLS signing and verification takes 393,143 ns and 2,989,363 ns, respectively, showing huge performance degradation. Moving from Schnorr to BLS scheme would put validators under heavier load, since the validators use the scheme to sign and verify every consensus message.
Performance of signing and verifying block seals (ns)
The BLS scheme is not slower when verifying signatures in block seals. If the Schnorr scheme is used, each block seal contains up to NUM_VALIDATORS Schnorr signatures because we cannot apply the signature aggregation and must verify them one by one. In other words, it takes 47,381 * NUM_VALIDATORS ns to verify each block seal.
With the BLS scheme, each block seal contains a single aggregated BLS signature, and verifying the aggregated signature is almost as lightweight as verifying a single signature. To verify an aggregated BLS signature, first we aggregate the public keys of the validators who voted to the block, and then we verify the aggregated signature using the aggregated public key. The cost of the latter step is exactly the same as the cost of a single BLS signature verification, and the cost of the former step is negligible compared to the latter one.
The table summarizes the benchmark result of verifying multiple signatures. When there are 30 signatures, the BLS scheme is about twice as slow as the Schnorr scheme. However, when the number of signatures grows to 300, the BLS scheme outpaces the Schnorr scheme. Since the cost of aggregation is negligible, this gap will widen as the number of validators grows.
The only extra overhead of using the aggregated signature is the cost of signature aggregation, which is negligible. As mentioned above, aggregation is a cheap operation compared to the verification step. Moreover, signature aggregation is done only by the proposer, once per block.
The reduced cost of the block seal verification is a valuable achievement because the operation is done by every participating node in the entire blockchain. Although introducing the BLS scheme puts extra overhead to validators, it mitigates the verification overhead of non-validators, which are far greater in numbers compared to validators.
Benchmark of actual implementation
To measure the effect of the performance degradation on consensus protocol, we tested our BLS scheme implementation on a small testnet configured in a local machine. We counted the number of blocks whose rounds had ended in the first view (a.k.a. Round in Tendermint), and the number of blocks that had moved to further views. Each view movement indicates that the validators have failed to reach a consensus in the previous view. In this experiment, no validator was Byzantine and there were no network issues, so a failure in consensus indicates a timeout due to performance issues.
Test Configuration
- On MacBook 13, 2017
- 6 validators
- Propose timeout limit 3000ms
- Prevote timeout limit 3000ms
- Precommit timeout limit 3000ms
- Commit timeout limit 3000ms
- Tested each scheme for about an hour.
You can see that the number of failed views increased significantly when the BLS scheme was used, indicating that the performance degradation was severe. However, we should not conclude that we cannot use the BLS scheme at all. In the testing environment, where six Foundry instances are running in a single laptop, CPU performance is probably a huge bottleneck. In real use cases, this would be much less problematic.
Conclusion
When signing and verifying a single signature, the BLS scheme is about eight times slower than the Schnorr scheme, and this puts a heavier load on the validators that handle consensus messages. On the other hand, the BLS scheme outperforms the Schnorr scheme when it comes to seal verification if the number of validators is large.
The benchmark result of the real implementation indicates that the performance degradation caused by the BLS scheme indeed affects the overall consensus. More tests should be done to measure the effect of this performance issue in real use cases, and aggressive optimizations should be applied if the problem turns out to be significant.
