Huffing for crypto with Weierstrudel
Hello there! Time for a little show and tell.
You see, I have a problem. Well, I have several problems, but one of them is the cost of elliptic curve cryptography on Ethereum.
We at AZTEC use a lot of elliptic curve cryptography. It is the foundation stone of our protocol. The private transactions we enable speak a language written in elliptic curve arithmetic operations.
And it is a frustratingly expensive language to speak.
Any transaction processed by the Ethereum protocol incurs a gas cost that is proportional to the time it takes to process the transaction. This makes smart contracts that verify zero-knowledge proofs…expensive.
To combat this, the Ethereum protocol supports a few precompile ‘smart contracts’ that perform elliptic curve arithmetic. These aren’t really smart contracts in the traditional sense — when called, the Ethereum node processing the transaction runs a hard-coded algorithm. Compiled into machine code, these algorithms are lightning-fast compared with interpreting a program expressed as opcodes for the Ethereum Virtual Machine.
The gas cost of these precompiles are usually well over an order of magnitude less than an equivalent implementation of their logic as a normal smart contract. However this still makes validating zero-knowledge cryptography inside an Ethereum smart contract an expensive proposal. Calling the ‘elliptic curve scalar multiplication’ smart contract will set you back by 40,000 gas. To contrast, adding two variables together inside a smart contract costs 3 gas, validating an ECDSA signature (on a different elliptic curve) costs 3,000 gas.
As a developer on top of the Ethereum protocol this presents a problem. There is an EIP in the works to reduce the gas costs of these precompiles but it’s not going to be integrated into Constantinople. So what is one to do? How does one reduce the cost of this problem without protocol upgrades?
It seems like we just have to live with it…
Unless, you know, somebody writes a smart contract that is more gas-efficient than a precompile.
Like that would ever happen…
And if it did, it wouldn’t have a ridiculous name like weierstrudel.
Weierstrudel
Weierstrudel is a smart contract that performs elliptic curve scalar multiplication on the short Weierstrass curve y² = x³ + 3, the same curve that the precompile (and AZTEC) uses.
Specifically, it performs multiple scalar multiplication. With the precompile, you can only multiply one point by one scalar — if you need several multiplications then you have to do them one by one.
This little project has been something of an obsession of mine for several months. My research while developing AZTEC led me down the path of elliptic curve multiplication algorithms and I had this…itch that needed scratching.
You see, there are a bunch of mathematical tricks and techniques you can use when implementing this kind of algorithm. And the idiosyncrasies of the Ethereum Virtual Machine unlocks some strange optimizations that would usually slow things down on a normal, compiled, program.
I suspected that, when integrated together, the result would cost less gas than calling the precompile contract. The rest is just an implementation detail, yes?
Well, eight months of implementation detail. Along the way I’ve learned far more than I care to admit about the Ethereum Virtual Machine, played a round of Solidity Gas Golf and littered dozens of notebooks with lines of nonsense like dup8 swap4 mulmod 0x00 mstore mload mload jump .
I’ve thrown everything I can think of into weierstrudel. GLV endomorphisms, batched sliding windowed NaFs, deferred modular reductions, jump tables integrated into the contract bytecode, point lookup tables expressed on a curve isomorphism to remove point inversions.
The contract doesn’t use variables to save on gas costs.
I wrote a domain-specific-language that compiles to EVM assembly just so I could finish weirstrudel.
If there was a spare kitchen sink going, that would have been thrown in there too.
Simply put, weierstrudel is an algorithm that should not exist. The opportunity cost alone of developing this thing was outrageous. When EIP-1108 goes live all of this work will immediately become redundant. A rational analysis of the merits of this work would have shelved this as soon as “you need to develop a new language to make this thing” became a reality.
But I could not let this one go. It is a silly, ridiculous folly attached to an absurd language.
And it does exist.
And it is efficient.
The cost of weierstrudel
Despite my best efforts, weierstrudel is slightly more expensive when used for a single elliptic curve point.
But who only needs to multiply one puny point? Not the AZTEC protocol, that’s for sure.
When combining more than one point together, weierstrudel becomes quite a bit more efficient — around 45% more efficient at the top-end.
Cheaper zero-knowledge cryptography
All said and done, weierstrudel offers ~15-40% savings for typical use cases. When we’re done with it, it should reduce the gas costs of AZTEC smart contract verifiers by ~15-20%.
Naturally, terms and conditions apply — the algorithm needs some more work before its ready for prime-time (and a lot more testing) and there are a couple more optimizations that need to be implemented (a giant lookup table for the generator point is foremost on my mind).
It also caps out at 15 points, any more and the algorithm would exceed the maximum stack depth of the EVM.
You also need to send the smart contract 1 wei if you want it to not throw an error. There is a reason for this. The algorithm requires the integer 1 about 500 times per run, and thecallvalue opcode is 1 gas cheaper than the push1(0x01) opcode.
Hey, 500 gas is 500 gas.
Weierstrudel can also be useful for zk-SNARK verifiers, although zk-SNARK gas costs are more weighted towards bilinear pairings, which this thing doesn’t do…for now.
Huff, optimized EVM assembly programming
That language I mentioned before is Huff, which is due an article of its own.
It’s built around macros — composable blocks containing EVM assembly and other macros. It also supports a crude form of templating, where macro invocations can accept template parameters which themselves are macros.
It enables complex algorithms to be broken down into constintuent macros, that can in turn be rigorously tested.
On the other hand, it doesn’t have variables, functions, or about 90% of the syntactic sugar of more advanced languages.
Still, it might be of some use for anybody looking to write highly optimized EVM code, at the small expense of turning your development experience into Edvard Munch painting.
Well, that’s about it. If you want to see a deployed version of weierstrudel, you can find one lurking on Ropsten. It uses bit shift opcodes so main-net has to fork to Constantinople before it works there.
If you want to know more, you can find weierstrudel in our AZTEC monorepo.
Cheers,
Zac.
