Poseidon go brr with Stylus: Cryptographic functions are 18x more gas-efficient via Rust on Arbitrum

Introduction

Arbitrum Stylus offers significant advantages for cryptographic applications, particularly in reducing gas costs for computationally expensive smart contracts. As advertised, it enables highly efficient execution of cryptographic primitives, making it an attractive building block for developers working with advanced cryptography.

One such cryptographic primitive is the Poseidon hash function. Poseidon is a hash function optimized for zero-knowledge proofs (zk-proofs). It is specifically designed to be efficient for field operations and is well-suited for zk-proofs due to its minimal constraints, when implemented in zk-friendly circuits.

Historically Poseidon usage in smart contracts on EVM chains has been very limited, given the prohibitive gas costs of writing the algorithm in Solidity - that changes today. Our optimized Rust implementation is up to 18x cheaper than popular Solidity implementation, as you will see below.

Implementation Overview

We won't go into the math details of the Poseidon permutation, since you always can find more information on its official reference. But we will point out here a few important observations that we consider important for efficient Poseidon hash and cryptography overall with Stylus.

Expensive Nature of Modular Multiplication

Poseidon permutation relies heavily on modular arithmetic operations. Some of them, like modular multiplications are quite expensive, because they would require an additional division by modulus. Division is inherently more costly than multiplication, contributing to the high overall expense of these operations. According to the official opcode pricing table,Stylus VM charges per division noticeably more than for multiplication. This cost makes optimizations essential for practical applications.

Using Montgomery Form for Multiplication

Montgomery form is a representation that allows modular multiplication to be performed without direct division operations. By transforming numbers into Montgomery form, costly division operations are replaced by more cost effective arithmetic steps, like multiplications and additions. This can significantly reduce computational overhead and improve performance.

Precomputing Parameters

The constants R , R2 and INV are crucial for reduction and converting numbers to and from Montgomery form. Computing these constants during runtime can be prohibitively expensive. With a modulus known at compile time, these constants can be precomputed in Rust. Thus we eliminate unnecessary overhead and ensure optimal performance.

Optimizations

Let’s start with a base implementation of Poseidon, that outsources constant computation of Montgomery parameters to Rust’s compile time. We have 86.952 gas execution cost and a WASM size of 8.6 KB. It is already a pretty good result, but we can do better.

WASM Multiplication

Operations involving 64-bit integer multiplications are significantly cheaper in WebAssembly, than those involving 128-bit integers. By representing 64-bit integer multiplication (overflowing to 128-bit), as four 64-bit integers multiplications, we can achieve gas execution cost of 75.082 , or 14% cheaper than before. This optimization reduces the WASM size by 0.1 KB.

Function Inlining

Function call doesn’t come for free on CPU’s and especially on Stylus VM. An optimization that can replace function call opcode with a function’s content is called inlining. Some inlines are done automatically by the rust compiler, others (especially ones, that bloat binary size) need to be defined explicitly. Applying Rust's #[inline] and #[inline(always)]attributes on frequently called functions, can result in significant gas cost reductions for Stylus smart contracts. In our case, we got 46.194 gas for execution, or 38% decrease in cost. This optimization is a tradeoff between WASM size and gas cost, and in our case it increased the WASM binary by approximately 0.3KB.

Unrolling Hot Loops

Loop control instructions can sometimes be expensive. Being able to remove loops or unroll loops for frequently executed operations, such as big integer’s multiplication and addition, can help in theory. In rust, unrolling loops can be done with macros, in a way that won't hurt code readability much. Updated modular arithmetic brought to Poseidon new results: 28.392 gas per execution. It has improved again by 39%, compared to the previous version. Unfortunately, this bloated binary size by 1.0 KB, but is still a worthy tradeoff considering the gas savings. Now we have a contract as heavy as 9.8 KB of ****WebAssembly.

Caching the Contract

Finishing with code related optimizations, we can use Stylus caching of WASM contracts. It allows for frequently used contracts to be called without a cold start. Forcing our contract to be cached on the dev nitro node, we already can see new amazing results: 15.148 execution price, an additional 47% improvement. This improvement doesn’t have any influence on WASM size.

WASM Optimizations

Previous optimizations were at the source code level, but we can also do some tricks to the WASM itself to help reduce costs. If you've heard about WebAssembly optimizers, probably wasm-opt tool may be familiar. Aggressive WASM optimization for “speed” opens new horizons for Poseidon, and yields additional 22% gas improvement. Now gas cost is as low as 11.887 for execution. Unlike other optimizations, there is no “binary size tradeoff”. WASM size is now 9.6KB, a reduction of 0.2KB.

Comparison to Solidity Implementations

As mentioned at the beginning of the article, one limiting factor for Poseidon in EVM chains has been expensive gas costs.

We now compare our optimized implementation with some popular Solidity alternatives out there, and as you can see the gains are significant. The Rust implementation is far more readable and auditable (and thus arguably more secure) than some of the Solidity assembly (Yul) implementations.

The table below compares gas costs for Poseidon hash, consuming two 256-bit integers as arguments. The hash operates over the bn256 field, with a state size of 3. This ensures that the Poseidon permutation is invoked only once. All implementations have the same degree and the same number of parameters. The 21000 base gas fee per EVM transaction was omitted for clarity and fair comparison.

The implementation of Poseidon using assembly (Yul), consisting of approximately 350 lines of assembly code, is 62% more expensive, than the Rust implementation with zero unsafe code.

The plain Solidity implementation, while being simpler and more audit-friendly (than assembly counterpart), is ~18 times more expensive compared to optimized Rust implementation.

Conclusion

Arbitrum Stylus provides an excellent environment for running highly optimized cryptographic primitives like Poseidon hash on-chain. Developers can achieve significant gas cost reductions and have their cryptography blazingly cheap, compared to traditional Solidity implementations. This efficiency makes Stylus a compelling choice for zk-proof based applications and other performance critical cryptographic systems.

Another big advantage of the Stylus implementation is that it can also be used by Solidity contracts in Arbitrum One and other Orbit chains. There just needs to be one deployment of the WASM implementation. All contracts on that chain can call it, just like any other contract.

While our implementation is still not production ready, we invite you to try it and use it in your development until it gets audited and can be confidently used in production.

There are still some optimizations that we might explore that can make Poseidon even more performant, and we have other crypto primitives like Pedersen hash and elliptic curves in our backlog. If you are a project building on Arbitrum and need highly optimized crypto primitives, please reach out to our team or open an issue in our repo.