Optimizing cryptographic algorithm implementations

[Federico2014]

Background

Currently, the BN128Addition, BN128Multiplication, and BN128Pairing precompiled contracts suffer from performance bottlenecks, leading to transaction timeouts and limiting the application of zero-knowledge proofs on the TRON network, as shown in #4311 and #5492.

The zkBob team has proposed two optimization approaches:

• The first one, described in #5507, wraps the arkworks cryptographic library via JNI. It offers significantly higher performance, achieving a 3x to 30x speedup for BN128 precompiled contracts.

• The second one, described in #5611, uses Montgomery optimizations. This results in a 17% performance degradation for BN128Addition, but offers around 30% improvement for BN128Multiplication and BN128Pairing.

To optimize BN128 precompiled contract performance, Besu supports two implementations:

• A pure Java implementation;

• A gnark-crypto wrapper using JNA.

We conducted a comprehensive benchmark of these implementations:

Test results on macOS (2.6 GHz 6-Core Intel Core i7, 16GB RAM), in microseconds (μs):

	BN128Addition	BN128Multiplication	BN128Pairing (2 pairs)
java-tron	32.718	2584.739	62751.503
arkworks	12.971	97.659	1792.001
Montgomery	41.512	1731.617	41900.001
besu-java	6.5	14163.3	1295543.0
besu-gnark	4.1	55.5	654.2

On Ubuntu 22.04.5 LTS, AMD x86_64, 16 cores, 32GB RAM, the benchmark results (μs):

	BN128Addition	BN128Multiplication	BN128Pairing (2 pairs)
java-tron	23.654	1896.336	46889.459
arkworks	5.154	83.243	1646.457
Montgomery	29.903	1543.336	35772.447
besu-java	2.5	10413.6	796687.1
besu-gnark	2.4	53.5	655.9

Taking the Ubuntu results as an example, we can see that integrating arkworks significantly improves the performance of BN128 precompiled contracts on java-tron:

• BN128Addition: ~2.5× speedup

• BN128Multiplication: ~26× speedup

• BN128Pairing: ~35× speedup

Moreover, java-tron’s performance is far behind the besu-gnark implementation:

• BN128Addition: ~10× slower

• BN128Multiplication: ~35× slower

• BN128Pairing: ~71× slower

Taking this Groth16 contract example, which involves 6 BN128Addition, 5 BN128Multiplication, and 4 BN128Pairing operations:

• java-tron execution time:

  6×23.654+5×1896.336+2×46889.459≈103402.44 μs

• arkworks execution time:

  6×5.154+5×83.243+2×1646.457≈3740.05 μs( 27.6×faster)

• besu-gnark execution time:

  6×2.4+5×53.5+2×655.9≈1593.70 μs( 65×faster)

In addition to BN128 precompiled contracts, Besu has also optimized EcRecover and Secp256k1 signature verification. The besu-java implementation uses the BouncyCastle library, while besu-native wraps bitcoin-core/secp256k1 via JNA. We benchmarked and compared their performance as well:

Test results on macOS (2.6 GHz 6-Core Intel Core i7, 16GB RAM), in μs:

	EcRecover	Secp256k1	ModExp
java-tron	1956.975	1218.343	58.418
besu-java	959.4	891.7	21.222
besu-native	50.6	45.3	34.585

Test results on Ubuntu 22.04.5 LTS, AMD x86_64, 16 cores, 32GB RAM:

	EcRecover	Secp256k1	ModExp
java-tron	916.184	875.647	20.168
besu-java	679.2	670.2	16.428
besu-native	50.4	47.3	34.165

From the Ubuntu benchmark results, we can see that besu-native achieves ~18× speedup over java-tron in both EcRecover and Secp256k1 signature verification. For ModExp, the performance difference is smaller, possibly due to limited test coverage.

From the above benchmarks, it is clear that optimizing the performance of the BN128 precompiled contracts and other cryptographic algorithms is necessary. The besu-native implementation serves as a strong reference, as it also includes optimized support for Blake2bf and BLS12-381, which can help improve the scalability of the TRON network.

Rationale

Why should this feature exist?

• Optimize the performance of BN128 precompiled contracts to avoid transaction timeouts and promote ZK-based applications on the TRON network;
• Accelerate EcRecover and Secp256k1 signature verification to improve TRON’s scalability;
• Optimize additional cryptographic primitives such as ModExp, Blake2bf, and BLS12-381.

What are the use-cases?

• ZK application developers;
• Reducing signature verification time for all TRON transactions;

Specification

• Replace the current java-tron BN128 precompiled contract implementation with the optimized version;
• Replace the current java-tron implementation of EcRecover and Secp256k1 with optimized versions;
• Apply similar performance improvements to other cryptographic primitives.

Test Specification

• Benchmark execution speed of the optimized BN128 precompiled contract and compare it to the current implementation;
• Benchmark EcRecover and Secp256k1 verification performance before and after optimization;
• Measure execution time of ZK-related transactions before and after optimization;
• Measure execution time of regular transactions before and after optimization;

Scope Of Impact

• BN128 and EcRecover precompiled contracts;
• Reduced transaction processing time by accelerating signature verification;
• Potential gas cost adjustments for affected precompiled contracts;
• Performance improvements must preserve consensus correctness to avoid network forks, requiring proposal-level changes;
• As signature verification is a major performance bottleneck in block production, improvements should be evaluated in the context of block time scheduling.

Implementation

Do you have ideas regarding the implementation of this feature?

Currently, the optimization of BN128 precompiled contracts mainly considers two implementations: arkworks and besu-gnark. The arkworks-based version has already been developed by the zkBob team (see #5507), but recent benchmarks show that besu-gnark performs slightly better. Since besu-native relies on JDK 21, we also need to evaluate how to maintain compatibility with JDK 8.

A thorough discussion is still required to evaluate the advantages and potential risks of each solution before choosing the final optimization path. For EcRecover and Secp256k1, it should also be discussed within the community whether to adopt the optimization strategy used in besu-native.

Are you willing to implement this feature?
Y

[jwrct]

@Federico2014 From the benchmark results you provided, it seems that the performance of java-tron's signature verification is really bad, and this optimization seems to be necessary. besu-gnark is undoubtedly the best, but java-tron currently only supports JDK 8, but I see that there are already issues discussing support for higher versions of JDK, for example: #5976.

[Federico2014]

@jwrct besu-native is built with JDK 21, while java-tron is based on JDK 8, so it cannot be used directly. Currently, we haven't decided how to handle the JDK compatibility issue. Alternatively, we could consider modifying besu-native to downgrade it to JDK 8.

[jwrct]

@Federico2014 OK, I understand. If there is any progress, please update in time. I am looking forward to the implementation of this optimization.

[Federico2014]

I also tested the execution time for verifying a single Groth16 proof transaction under three scenarios: java-tron, arkworks, and Montgomery. The test environment was a Mac with a 2.6 GHz 6-core Intel Core i7 and 16GB of RAM. The transaction timeout in java-tron was set to 200 ms.

All test cases executed the same transaction for verifying a Groth16 proof, and the execution time was measured separately in the broadcast, pack, and apply stages. The test results are as follows (unit: ms):

java-tron

	broadcast	pack	apply	Result
Test case 1	881	909	2	timeout
Test case 2	787	622	1	timeout
Test case 3	536	437	0	timeout
Test case 4	426	206	0	timeout
Test case 5	122	156	107	success
Test case 6	133	139	125	success
Test case 7	116	113	106	success

arkworks

	broadcast	pack	apply	Result
Test case 1	33	23	18	success
Test case 2	16	17	12	success
Test case 3	9	13	14	success
Test case 4	8	11	11	success
Test case 5	12	8	9	success

Montgomery

	broadcast	pack	apply	Result
Test case 1	244	199	167	success
Test case 2	261	232	2	timeout
Test case 3	130	462	90	success
Test case 4	253	308	1	timeout
Test case 5	140	178	113	Success

From the above test results, it can be seen that with the arkworks optimization, the execution time for verifying a single Groth16 proof transaction stays within 50 ms. However, with the current java-tron implementation and Montgomery optimization, the execution time is less stable — even with the transaction timeout set to 200 ms, sometimes the transaction executes successfully, but other times it fails due to a timeout.

[Sunny6889]

@jwrct besu-native is built with JDK 21, while java-tron is based on JDK 8, so it cannot be used directly. Currently, we haven't decided how to handle the JDK compatibility issue. Alternatively, we could consider modifying besu-native to downgrade it to JDK 8.

Will downgrade it to JDK 8 decrease the algorithm performance?

[Federico2014]

@jwrct besu-native is built with JDK 21, while java-tron is based on JDK 8, so it cannot be used directly. Currently, we haven't decided how to handle the JDK compatibility issue. Alternatively, we could consider modifying besu-native to downgrade it to JDK 8.

Will downgrade it to JDK 8 decrease the algorithm performance?

I think the impact should be relatively small.

[Federico2014]

I have modified besu-native to make it compatible with JDK 8 and integrated it into java-tron. After that, I conducted benchmarks for the BN128 precompiled contract.

Test results on macOS (2.6 GHz 6-Core Intel Core i7, 16GB RAM), in μs:

	BN128Addition	BN128Multiplication	BN128Pairing（2 pairs）
java-tron	58.279	2407.683	61829.418
java-tron-arkworks	10.711	172.058	2036.048
java-tron-gnark	74.698	50.744	758.094

Based on the test results above, after integrating besu-gnark into java-tron, the performance of both BN128Mul and BN128Pairing has significantly improved. However, BN128Add shows no noticeable performance gain. I noticed that in besu-native, benchmarking is performed after a warm-up phase, where the precompiled contracts are executed multiple times beforehand. This allows the JVM to complete class loading, method compilation, and other preparations, preventing first-time execution overhead from affecting the benchmark results. After introducing a similar warm-up phase, my test results are as follows:

	BN128Addition	BN128Multiplication	BN128Pairing（2 pairs）
java-tron	23.514	2370.796	62461.821
java-tron-arkworks	6.246	101.516	1990.414
java-tron-gnark	3.945	49.713	640.455

The benchmark results of java-tron-gnark are very close to those of besu-gnark, indicating that integrating besu-gnark into java-tron can effectively improve the performance of BN128 precompiled contracts. The performance of BN128Addition, BN128Multiplication, and BN128Pairing has improved by 6x, 47x, and 97x, respectively. Moreover, it proves to be more efficient than the arkworks-based implementation.

[Federico2014]

Similarly, I also tested the execution time of Groth16 proof verification transactions using java-tron-gnark. The results are as follows (unit: ms):

	broadcast	pack	apply	Result
Test case 1	29	14	19	success
Test case 2	16	18	18	success
Test case 3	13	10	11	success
Test case 4	9	10	10	Success
Test cast 5	27	18	36	success

From the results, we can see that for Groth16 proof verification transactions, the execution time using java-tron-gnark is comparable to the arkworks-optimized implementation — both stay within 40 ms. This ensures smooth execution of zero-knowledge related transactions.