Awesome
Oliver: efficient Baby-JubJub point arithmetic for smart contracts
Oliver (full name: Oliver Twisted Edwards) is a smart contract that performs elliptic curve point multiplication on the Baby-JubJub curve.
It can multiply up to 15 points (with up to 15 distinct scalars) at once.
Optimisations
Oliver is written in Huff, a low-level language that compiles to Ethereum Virtual Machine opcodes. It also uses many of the same optimisations employed by weierstrudel:
- Shamir's trick, which combines multiple scalar multiplications into a single double-and-add loop, fixing the number of 'point doubling' operations to ~254
- Sliding Window Non-Adjacent Form, a representation of scalar multipliers which reduces the number of 'point addition' operations to ~50 per point
- Using the difference between the Baby-JubJub curve's 254-bit field modulus and the EVM's 256 word size to defer modular reductions until absolutely necessary
Because Baby-JubJub is a Twisted Edwards curve, a couple of optimisations from weierstrudel could not be used, namely the curve endomorphism which halved the number of point doubling operations required, and the trick whereby one could pretend points in projective coordinates had a Z value of 1. For these reasons, it's a bit less efficient than weierstrudel.
Benchmarks
Gas estimates can be obtained by running yarn benchmark.
| Number of points | Approximate gas cost (average of 25 runs) | Cost per point |
|---|---|---|
| 1 | 82,209 | 82,209 |
| 2 | 107,060 | 53,530 |
| 3 | 132,017 | 44,006 |
| 4 | 157,479 | 39,370 |
| 5 | 183,351 | 36,670 |
| 6 | 210,331 | 35,055 |
| 7 | 236,715 | 33,816 |
| 8 | 265,050 | 33,131 |
| 9 | 292,186 | 32,465 |
| 10 | 321,404 | 32,140 |
| 11 | 349,137 | 31,740 |
| 12 | 379,098 | 31,592 |
| 13 | 408,159 | 31,397 |
| 14 | 439,310 | 31,379 |
| 15 | 469,646 | 31,310 |
Usage
- Run Oliver tests with
yarn test - Run Oliver benchmarks with
yarn benchmark