Weierstrudel

Weierstrudel makes zero-knowledge cryptosystems that utilize the bn254 curve, such as the AZTEC protocol substantially cheaper.

weierstrudel is a highly optimized smart contract that performs elliptic curve scalar multiplication on the short Weierstrass 254-bit Barreto-Naehrig curve, formerly used by ZCash and currently available as a precompile smart-contract in the Ethereum protocol.

The current gas schedule for Ethereum's scalar multiplication precompile smart contract is 40,000 gas. When multiplying more than one point, weierstrudel is substantially more efficient than the precompile contract (see Benchmarks).

Huff

weierstrudel is written entirely in Huff, a low-level domain-specific language that compiles to Ethereum Virtual Machine opcodes. In addition, the following techniques are used to minimize gas costs:

• Using the GLV technique to exploit a curve endomorphism and reduce the number of 'point doubling' operations in half.

• Using Shamir's trick to combine multiple scalar multiplications into a single algorithm, fixing the number of 'point doubling' operations to ~127

• Using Windowed-Non-Adjacent-Form representations for scalar multipliers, reducing the number of 'point addition' operations to ~50 per point

• Using the difference between the bn254 curve's 254-bit field modulus and the EVM's 256 word size to defer modular reductions until absolutely neccessary

weierstrudel makes extensive use of bit-shift opcodes and is only compatible with Ethereum once the Constantinople hard-fork has been activated.

Additional resources

If you would like to learn more about Weierstrudel, please refer to our Github repo or Zac's Medium article.