• This repository has been archived on 16/Mar/2023
  • Stars
    star
    111
  • Rank 314,510 (Top 7 %)
  • Language
    JavaScript
  • Created almost 6 years ago
  • Updated about 5 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Huff implementation of the bn254 curve, for Ethereum smart contracts

weierstrudel: efficient elliptic curve arithmetic for smart contracts

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 contract will multiply up to 15 elliptic curve points with up to 15 different scalars.

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).

"Wait...what?"

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 necessary

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

"Hang on...what is Huff?"

Huff enables the construction of composable, EVM assembly macros. Huff also supports a crude form of templating - macros can accept template arguments, which in turn are also Huff macros. This allows for highly optimized, customizable blocks of assembly code.

See the Huff repository for more details.

"What are the implications of weierstrudel?"

Until the gas schedule for Ethereum's precompile contracts changes, weierstrudel makes zero-knowledge cryptosystems that utilize the bn254 curve, such as the AZTEC protocol substantially cheaper.

"Is there a catch?"

The weierstrudel smart contract requires precisely 1 wei to be sent to it or it will refuse to perform elliptic curve scalar multiplication. No more, no less.

"...really?"

Yes. Doing so saves approximately 500 gas per contract call.

Is weierstrudel production ready?

Not yet! We're in the process of applying more rigorous testing to ensure the correctness of weierstrudel's algorithms. In addition we still need to implement the following:

  1. Fully supported edge-cases for weierstrudel's point addition formulae - currently the contract throws an error if the following edge cases are hit:
    • Adding two points equal to one another
    • Adding a point to the point's negative counterpart
  2. Montgomery batch inverses in Huff - points are currently expressed in Jacobean form.
    • Supplying a point's inverse as a transaction input is the most efficient method of obtaining an inverse (~2,000 gas), but we still want to implement this to maintain a consistent interface when compared to the precompile
  3. Precomputed point lookup tables for generator points
    • There are substantial gas optimizations to be claimed by integrating a lookup table for bn254's fixed generator point

"Can I use weierstrudel in my project?"

Of course! weierstrudel is open-source software, licensed under LGPL-3.0. However we would urge caution until we've finished thoroughly validating weierstrudel's Huff macros.

Benchmarks

Gas estimates can be obtained by running yarn benchmark. For reference, the scalar multiplication precompile costs 40,000 gas per point. This is excluding the overheads of having to make a contract call per point when using the precompiles, as well as calling the point addition precompile to combine points into a single sum.

Number of points Approximate gas cost (average of 10 runs) Cost per point
1 47,593 47,593
2 69,057 34,528
3 89,997 29,999
4 111,554 27,889
5 133,580 26,716
6 154,759 25,793
7 176,051 25,150
8 196,570 24,571
9 219,103 24,244
10 239,872 23,987
11 261,243 23,749
12 282,349 23,529
13 304,197 23,400
14 324,816 23,201
15 348,173 23,211

Deployed weierstrudel

weierstrudel is currently deployed on Ropsten.

Usage

  1. Run weierstrudel tests via yarn test
  2. Run reference javascript methods via yarn test:js
  3. Run weierstrudel benchmarks via yarn benchmark
  4. Compile the weierstrudel smart contract via yarn compile

More Repositories

1

aztec-v1

Public repository for the AZTEC V1 protocol. For the latest zkRollup release see here https://github.com/AztecProtocol/aztec-2-bug-bounty
JavaScript
631
star
2

aztec-connect

aztec connect repository
TypeScript
430
star
3

huff

Repository for Huff - an EVM programming language
JavaScript
232
star
4

aztec-connect-bridges

Solidity
229
star
5

aztec-packages

C++
192
star
6

noir-starter

Solidity
168
star
7

barretenberg

C++
140
star
8

aztec-2.0

C++ elliptic curve library
C++
134
star
9

aztec-nr

Noir
105
star
10

interview-test

TypeScript
80
star
11

dev-rel

All of Aztec's workshops, resources, tutorials, ideas, and useful tools
TypeScript
44
star
12

aztec-v1-loan-dapp

A kitchen sink example of how to build private dApps using AZTEC
JavaScript
35
star
13

aztec-v1-specification

AZTEC protocol specification
31
star
14

Setup

AZTEC protocol trusted setup MPC
TypeScript
31
star
15

aztec-verifier-contracts

Solidity
28
star
16

awesome-aztec

28
star
17

interview-tests

C++
23
star
18

consolerr

Solidity error logging
Solidity
23
star
19

aztec-2-bug-bounty

C++
17
star
20

plonk-with-lookups

TeX
17
star
21

aztec-starter

A simple aztec contract + test to get started.
Rust
15
star
22

Oliver

Huff implementation of the BabyJubJub curve
JavaScript
13
star
23

aztec3-circuits

Circuit infrastructure for Aztec 3.0
C++
12
star
24

ignition-verification

Repository to verify contributions to the AZTEC Ignition ceremony
JavaScript
12
star
25

aztec-security

Security contacts and disclosure reports
12
star
26

rollup-encoder

I'm encoooderrrring
Solidity
11
star
27

sandbox-version-manager

Tool to manage sandbox versions
Rust
10
star
28

aztec3-l1-contracts

L1 contracts for Aztec3
Solidity
9
star
29

docs

Aztec docs site
JavaScript
8
star
30

zk-money

TypeScript
8
star
31

engineering-designs

Internal engineering designs
Jupyter Notebook
6
star
32

aztec-connect-explorer

TypeScript
5
star
33

polaris

4
star
34

snark-benchmarks

basic Groth16 benchmarks
Rust
4
star
35

aztec-connect-contracts

Aztec Connect Rollup's Solidity Smart Contracts
Solidity
4
star
36

stackproofs

TeX
3
star
37

build-system

Shell
3
star
38

foundation

TypeScript
3
star
39

ab2

Alpha Build 2 project repository.
3
star
40

msgpack-c

Fork of msgpack-c repo with a few more safety checks
C++
2
star
41

aztec-connect-cpp

C++
2
star
42

dev-bb.js

JavaScript
2
star
43

protocol-specs-pdf

2
star
44

git-metadata

Currently used for https://github.com/ben-z/gh-action-mutex
1
star
45

wallet-ui

WalletConnect-based secure wallet for Aztec Connect
TypeScript
1
star
46

dev-connect-workshop

JavaScript
1
star
47

AZIPs

An AZIP is a design document providing information to the Aztec community, or describing a new feature for Aztec or its processes or environment.
1
star