aztecprotocol / aztec-2.0 Goto Github PK

View Code? Open in Web Editor NEW

134.0 134.0 37.0 72.45 MB

C++ elliptic curve library

CMake 0.06% C++ 96.91% C 0.63% Perl 0.01% Shell 0.01% TypeScript 1.76% Dockerfile 0.01% JavaScript 0.06% Solidity 0.55%

aztec-2.0's People

Contributors

Stargazers

Watchers

aztec-2.0's Issues

Dockerfile didn't work when running dockerfiles/Dockerfile.wasm-linux-clang

I go some errors when trying to run docker and get the wasm file.

Sending build context to Docker daemon 104.5MB
Step 1/11 : FROM ubuntu:latest AS builder
---> d13c942271d6
Step 2/11 : RUN apt-get update && DEBIAN_FRONTEND=noninteractive apt-get install -y build-essential wget git libssl-dev cmake curl
---> Using cache
---> b8d842ac719b
Step 3/11 : RUN curl https://wasmtime.dev/install.sh -sSf | bash /dev/stdin --version v0.25.0
---> Using cache
---> 9ca51857212b
Step 4/11 : WORKDIR /usr/src/barretenberg/src
---> Using cache
---> fafa72c1b368
Step 5/11 : RUN curl -s -L https://github.com/CraneStation/wasi-sdk/releases/download/wasi-sdk-12/wasi-sdk-12.0-linux.tar.gz | tar zxfv -
---> Using cache
---> a3670743bf36
Step 6/11 : WORKDIR /usr/src/barretenberg
---> Using cache
---> 932c244e11b9
Step 7/11 : COPY . .
---> adb9504dbcbb
Step 8/11 : RUN mkdir build && cd build && cmake -DWASM=ON .. && make -j$(nproc) barretenberg.wasm rollup_proofs_tests
---> Running in 68de8d87c90d
-- The CXX compiler identification is Clang 11.0.0
-- The C compiler identification is Clang 11.0.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Compiling for WebAssembly.
-- Multithreading is disabled.
-- Could NOT find PythonInterp (missing: PYTHON_EXECUTABLE)
-- Looking for pthread.h
-- Looking for pthread.h - not found
-- Could NOT find Threads (missing: Threads_FOUND)
-- Could NOT find Threads (missing: Threads_FOUND)
CMake Error at CMakeLists.txt:46 (include):
include could not find load file:

cmake/build.cmake

-- Using fallback non-assembly methods for field multiplications.
-- Configuring incomplete, errors occurred!
See also "/usr/src/barretenberg/build/CMakeFiles/CMakeOutput.log".
See also "/usr/src/barretenberg/build/CMakeFiles/CMakeError.log".
The command '/bin/sh -c mkdir build && cd build && cmake -DWASM=ON .. && make -j$(nproc) barretenberg.wasm rollup_proofs_tests' returned a non-zero code: 1

Please update the About field and link the noir definition reference in the subfolder

For clear orientation update the description in the repo to reflect the shift for mono-repo,
please also link some general sources for noir in the subfolder with VScode support.

Research notes, SIMD implementation, faster multiplication and `GF(2^m)`

I also found this really useful too: https://www.iacr.org/workshops/ches/ches2013/presentations/CHES2013_Session6_1.pdf (although it focuses a lot on binary curves, rather than prime)

However, it seems like it can't beat the MULX, ADOX, ADCX sequence as described by: https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf

And this covers squaring using MULX, ADOX and ADCX sequences: https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/large-integer-squaring-ia-paper.pdf

This repository, in addition to https://github.com/cloudflare/sidh/blob/master/p503/arith_amd64.s seems to be enough to adapt libff with the MULX + ADOX/ADCX optimisations, batching loads and then a batch of interleaved adox/adcx for best pipeline usage.

From https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/polynomial-multiplication-instructions-paper.pdf (pages 13-15) - The CLMUL instruction looks like it's unlikely to be able to outperform the above without being able to represent the G(p) field over G(2^n) (I can't find an appropriate irreducible polynomial,... I don't think that's possible to easily represent some arbitrary prime over a binary field)

You would assume that an optimising compiler could produce something similar to the following for fq_impl_int128:

Karatsuba Multiplication 128-bit x 128-bit = 256-bit

// c1c0 = a * b
void GF2m_mul_2x2_xmm(__m128i *c1, __m128i *c0, __m128i b,
__m128i a)
{
 __m128i t1, t2;
 *c0 = _mm_clmulepi64_si128(a, b, 0x00);
 *c1 = _mm_clmulepi64_si128(a, b, 0x11);
 t1 = _mm_shuffle_epi32(a, 0xEE);
 t1 = _mm_xor_si128(a, t1);
 t2 = _mm_shuffle_epi32(b, 0xEE);
 t2 = _mm_xor_si128(b, t2);
 t1 = _mm_clmulepi64_si128(t1, t2, 0x00);
 t1 = _mm_xor_si128(*c0, t1);
 t1 = _mm_xor_si128(*c1, t1);
 t2 = t1;
 t1 = _mm_slli_si128(t1, 8);
 t2 = _mm_srli_si128(t2, 8);
 *c0 = _mm_xor_si128(*c0, t1);
 *c1 = _mm_xor_si128(*c1, t2);
}

Karatsuba Multiplication 256-bit x 256-bit = 512-bit

// c3c2c1c0 = a1a0 * b1b0
{
 a1 = _mm_set_epi64x(a->d[3], a->d[2]);
 a0 = _mm_set_epi64x(a->d[1], a->d[0]);
 b1 = _mm_set_epi64x(b->d[3], b->d[2]);
 b0 = _mm_set_epi64x(b->d[1], b->d[0]);
 GF2m_mul_2x2_xmm(&c1, &c0, a0, b0);
 GF2m_mul_2x2_xmm(&c3, &c2, a1, b1);
 a0 = _mm_xor_si128(a0, a1);
 b0 = _mm_xor_si128(b0, b1);
 GF2m_mul_2x2_xmm(&c5, &c4, a0, b0);
 c4 = _mm_xor_si128(c4, c0);
 c4 = _mm_xor_si128(c4, c2);
 c5 = _mm_xor_si128(c5, c1);
 c5 = _mm_xor_si128(c5, c3);
 c1 = _mm_xor_si128(c1, c4);
 c2 = _mm_xor_si128(c2, c5);
}

Quick Squaring (256-bit)^2 = 512-bit

// c3c2c1c0 = a1a0 * a1a0
{
 c0 = _mm_clmulepi64_si128(a0, a0, 0x00);
 c1 = _mm_clmulepi64_si128(a0, a0, 0x11);
 c2 = _mm_clmulepi64_si128(a1, a1, 0x00);
 c3 = _mm_clmulepi64_si128(a1, a1, 0x11);
}

Test failure

x86_64, Ubuntu 18.04, clang++ 10.0
virtual waffle::Prover waffle::BoolComposer::preprocess(): Assertion "(n == q_left_bools.size())"

Got Segmentation fault (core dumped) for run_stdlib_sha256_bench

Dear maintainers,

Thanks for building this great projects! I am interested in the benchmark number of plonk on sha256, but the benchmark script failed.

What's wrong

make run_stdlib_sha256_bench returns error Segmentation fault (core dumped)

make run_stdlib_sha256_bench
...
Scanning dependencies of target run_stdlib_sha256_bench
src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/build.make:57: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench' failed
make[3]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench] Segmentation fault (core dumped)
CMakeFiles/Makefile2:4021: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/all' failed
make[2]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/all] Error 2
CMakeFiles/Makefile2:4028: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/rule' failed
make[1]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/rule] Error 2
Makefile:1345: recipe for target 'run_stdlib_sha256_bench' failed
make: *** [run_stdlib_sha256_bench] Error 2

Environment

AWS t2.xlarge Ubuntu, 18.04 LTS, amd64 bionic image build on 2020-04-08

gcc-9
cmake 3.16.5

Steps to reproduce

sudo apt update && sudo apt install -y build-essential wget git libssl-dev
wget https://cmake.org/files/v3.16/cmake-3.16.5.tar.gz \
  && tar zxf cmake-3.16.5.tar.gz \
  && cd cmake-3.16.5 \
  && ./bootstrap \
  && make -j$(nproc) \
  && sudo make install \
  && cd .. \
  && rm -rf cmake*
sudo su
apt install -y software-properties-common \
  && add-apt-repository ppa:ubuntu-toolchain-r/test \
  && apt update \
  && apt install -y \
    xz-utils \
    make \
    gcc-9 \
    g++-9 \
    curl \
  && update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-9 60 --slave /usr/bin/g++ g++ /usr/bin/g++-9

cd barretenberg/barretenberg
mkdir build
cd build
cmake ..
make -j4
make run_stdlib_sha256_bench

The cmake log can be found here

Run with docker

sudo docker-compose build x86_64-linux-gcc
sudo docker run -it --rm aztecprotocol/barretenberg:x86_64-linux-gcc
root@b96a191d2828:/usr/src/barretenberg# cd build/
root@b96a191d2828:/usr/src/barretenberg/build# make run_stdlib_sha256_bench
[ 12%] Built target stdlib_primitives_objects
...
[100%] Built target stdlib_sha256_bench
Scanning dependencies of target run_stdlib_sha256_bench
src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/build.make:57: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench' failed
make[3]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench] Segmentation fault (core dumped)
CMakeFiles/Makefile2:3815: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/all' failed
make[2]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/all] Error 2
CMakeFiles/Makefile2:3822: recipe for target 'src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/rule' failed
make[1]: *** [src/aztec/stdlib/hash/sha256/CMakeFiles/run_stdlib_sha256_bench.dir/rule] Error 2
Makefile:1267: recipe for target 'run_stdlib_sha256_bench' failed

Barretenberg library test problem. Test named test_root_rollup_3x2 failed.

Reproduction Scenario:

Build barretenberg library via ./bootstrap.sh (as described in the build instruction)
Go to build directory named build
Run ctest

Expected result:
All tests are passed

Actual result:
One test named test_root_rollup_3x2 is failed. Logs are here

hummus package not working

After building and running the server, it complains it can't find barretenber.wasm file.
I built barretenber package and got the barretenber.wasm but I couldn't find the correct folder to add it so hummus PoC works.

A potential bug in scalar_multiplication.cpp

Hi,

Thanks for the great optimizations on batch affine!

When reading the implementation for add_affine_points_with_edge_cases(...), I found the following for loop which seems to iterate forever.

for (size_t i = (num_points)-2; i < num_points; i -= 2) { ... }

Any suggestions? Thanks!

Segfault when running pippenger_bench

make run_pippenger_bench -j16

initializing
executing normal fft
make[3]: *** [src/aztec/plonk/pippenger_bench/CMakeFiles/run_pippenger_bench.dir/build.make:57: src/aztec/plonk/pippenger_bench/CMakeFiles/run_pippenger_bench] Segmentation fault (core dumped)
make[2]: *** [CMakeFiles/Makefile2:3153: src/aztec/plonk/pippenger_bench/CMakeFiles/run_pippenger_bench.dir/all] Error 2
make[1]: *** [CMakeFiles/Makefile2:3160: src/aztec/plonk/pippenger_bench/CMakeFiles/run_pippenger_bench.dir/rule] Error 2

cmake version 3.16.3
make version 4.2.1

Barretenberg build failure on Apple M1 processor

Attempting to compile barretenberg on an apple M1 currently fails during cmake configuration and fixing it seems non-trivial.

First, configuring cmake for barretenberg currently gives an error due to M1s storing binaries at different locations than intel-based macs:

 --- stderr
  CMake Error at CMakeLists.txt:9 (project):
    The CMAKE_CXX_COMPILER:

      /usr/local/opt/llvm/bin/clang++

    is not a full path to an existing compiler tool.

    Tell CMake where to find the compiler by setting either the environment
    variable "CXX" or the CMake cache entry CMAKE_CXX_COMPILER to the full path
    to the compiler, or to the compiler name if it is in the PATH.


  CMake Error at CMakeLists.txt:9 (project):
    The CMAKE_C_COMPILER:

      /usr/local/opt/llvm/bin/clang

    is not a full path to an existing compiler tool.

    Tell CMake where to find the compiler by setting either the environment
    variable "CC" or the CMake cache entry CMAKE_C_COMPILER to the full path to
    the compiler, or to the compiler name if it is in the PATH.

On my system, the path for apple clang is at /usr/bin/clang instead. Using this gives an error for -fopenmp not being supported however. Using the homebrew clang at /opt/homebrew/opt/llvm/bin/clang works instead. Then changing barretenberg/cmake/toolchains/x86_64-apple-clang.cmake from

set(CMAKE_CXX_COMPILER "/usr/local/opt/llvm/bin/clang++")
set(CMAKE_C_COMPILER "/usr/local/opt/llvm/bin/clang")

set(CMAKE_C_COMPILER $ENV{CC})
set(CMAKE_CXX_COMPILER $ENV{CXX})

works as a quick band-aid to the problem, though perhaps cmake should detect an M1 processor and defer to a new arm64-apple-clang.cmake file instead. Running cmake . again from there we run into a similar error to #65:

CMake Error at CMakeLists.txt:46 (include):
include could not find load file:

    cmake/build.cmake

For some reason, this last error isn't present on the branch kw/noir-dsl-mac. Continuing on that branch, building via make fails due to clang (13.0.0) not supporting -march=native on an apple M1:

$ make
[  1%] Building CXX object src/aztec/env/CMakeFiles/env_objects.dir/logstr.cpp.o
clang-13: fatal error: the clang compiler does not support '-march=native'
make[2]: *** [src/aztec/env/CMakeFiles/env_objects.dir/logstr.cpp.o] Error 1
make[1]: *** [src/aztec/env/CMakeFiles/env_objects.dir/all] Error 2
make: *** [all] Error 2
exit 2

arch.cmake can be patched up a bit to get past this:

include(CheckCCompilerFlag)
check_c_compiler_flag("-march=native" marchNativeSupported)
if(NOT WASM AND marchNativeSupported)
    add_compile_options(-march=native)
endif()

After which make gives a different error since libomp is installed to a different directory (/opt/homebrew/lib/libomp.a) instead of the expected:

make[2]: *** No rule to make target `/usr/local/lib/libomp.a', needed by `src/aztec/numeric/numeric_tests'.  Stop.

After manually creating a link for the library to the expected location the build fails in a dependency:

/Users/.../barretenberg/_deps/benchmark-src/src/complexity.cc:85:10: error: variable 'sigma_gn' set but not used [-Werror,-Wunused-but-set-variable]
  double sigma_gn = 0.0;
         ^

This error is fatal unless we build in debug mode instead. Compiling in debug gets us a bit further but fails here instead:

/Users/.../barretenberg/src/aztec/ecc/curves/bn254/scalar_multiplication/../../../groups/group_impl_asm.tcc:107:30: fatal error: unknown token in expression
        __asm__ __volatile__("xorq %%r8, %%r8                              \n\t"
                             ^
<inline asm>:1:7: note: instantiated into assembly here
        xorq %r8, %r8                              
             ^
1 error generated.

static mul bench is measuring in-place addition

The static mul bench seems to be measuring in-place addition:

https://github.com/AztecProtocol/barretenberg/blob/d815655681e8e42db3e716afdb60d8afb2e8f279/barretenberg/src/aztec/ecc/curves/bn254/fr.bench.cpp#L221-L228

https://github.com/AztecProtocol/barretenberg/blob/d815655681e8e42db3e716afdb60d8afb2e8f279/barretenberg/src/aztec/ecc/curves/bn254/fr.bench.cpp#L291-L298

Is that intended? (As I suppose it's for multiplication with compile-time operand)

Unable to cmake -DARM=ON .. for cross-compiling

I tried to cross compile on ubuntu 20 LTS x86-64 for aarch64 devices, and it failed.

-- The CXX compiler identification is GNU 9.3.0
-- The C compiler identification is GNU 9.3.0
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Compiling for ARM.
-- Could NOT find OpenMP_C (missing: OpenMP_C_FLAGS OpenMP_C_LIB_NAMES) 
-- Could NOT find OpenMP_CXX (missing: OpenMP_CXX_FLAGS OpenMP_CXX_LIB_NAMES) 
-- Could NOT find OpenMP (missing: OpenMP_C_FOUND OpenMP_CXX_FOUND) 
-- Multithreading is disabled.
S-- Found PythonInterp: /usr/bin/python3.8 (found version "3.8.5") 
-- Looking for pthread.h
-- Looking for pthread.h - not found
-- Could NOT find Threads (missing: Threads_FOUND) 
-- Could NOT find Threads (missing: Threads_FOUND) 
-- Found Git: /usr/bin/git (found version "2.25.1") 
-- git Version: v1.5.0
-- Version: 1.5.0
-- Performing Test HAVE_CXX_FLAG_STD_CXX11
-- Performing Test HAVE_CXX_FLAG_STD_CXX11 - Success
-- Performing Test HAVE_CXX_FLAG_WALL
-- Performing Test HAVE_CXX_FLAG_WALL - Success
-- Performing Test HAVE_CXX_FLAG_WEXTRA
-- Performing Test HAVE_CXX_FLAG_WEXTRA - Success
-- Performing Test HAVE_CXX_FLAG_WSHADOW
-- Performing Test HAVE_CXX_FLAG_WSHADOW - Success
-- Performing Test HAVE_CXX_FLAG_WERROR
-- Performing Test HAVE_CXX_FLAG_WERROR - Success
-- Performing Test HAVE_CXX_FLAG_PEDANTIC
-- Performing Test HAVE_CXX_FLAG_PEDANTIC - Success
-- Performing Test HAVE_CXX_FLAG_PEDANTIC_ERRORS
-- Performing Test HAVE_CXX_FLAG_PEDANTIC_ERRORS - Success
-- Performing Test HAVE_CXX_FLAG_WSHORTEN_64_TO_32
-- Performing Test HAVE_CXX_FLAG_WSHORTEN_64_TO_32 - Failed
-- Performing Test HAVE_CXX_FLAG_FSTRICT_ALIASING
-- Performing Test HAVE_CXX_FLAG_FSTRICT_ALIASING - Success
-- Performing Test HAVE_CXX_FLAG_WNO_DEPRECATED_DECLARATIONS
-- Performing Test HAVE_CXX_FLAG_WNO_DEPRECATED_DECLARATIONS - Success
-- Performing Test HAVE_CXX_FLAG_WNO_DEPRECATED
-- Performing Test HAVE_CXX_FLAG_WNO_DEPRECATED - Success
-- Performing Test HAVE_CXX_FLAG_WSTRICT_ALIASING
-- Performing Test HAVE_CXX_FLAG_WSTRICT_ALIASING - Success
-- Performing Test HAVE_CXX_FLAG_WD654
-- Performing Test HAVE_CXX_FLAG_WD654 - Failed
-- Performing Test HAVE_CXX_FLAG_WTHREAD_SAFETY
-- Performing Test HAVE_CXX_FLAG_WTHREAD_SAFETY - Failed
-- Performing Test HAVE_CXX_FLAG_COVERAGE
-- Performing Test HAVE_CXX_FLAG_COVERAGE - Success
-- Performing Test HAVE_STD_REGEX
-- Performing Test HAVE_STD_REGEX -- failed to compile
-- Performing Test HAVE_GNU_POSIX_REGEX
-- Performing Test HAVE_GNU_POSIX_REGEX -- failed to compile
-- Performing Test HAVE_POSIX_REGEX
-- Performing Test HAVE_POSIX_REGEX -- failed to compile
CMake Error at armbuild/_deps/benchmark-src/CMakeLists.txt:251 (message):
  Failed to determine the source files for the regular expression backend

I also tried the dockerfile, but the image's not on the Dockerhub anymore.

It could be the issue of aarch64 lib paths retrieval on x84-64, but after checking
https://github.com/AztecProtocol/barretenberg/blob/master/barretenberg/cmake/toolchains/arm64-linux-gcc.cmake
I can't find anything suspicious for me to try.

Any input is appreciated.