APK verifier

Solidity verifier implementation for accountable light client. This project is funded by the web3 foundation.

Overview

This repo holds two scheme apk verifier and associated libs:

• Basic scheme verifier
• Packed scheme verifier
• Libs
  • BLS12-377
  • BW6-761
  • bytes
  • math
  • pcs
  • piop
  • transcript
  • bitmask

Documentation

Usage

To install with Foundry:

forge install darwinia-network/apk-verifier

Install

To install dependencies and compile contracts:

git clone --recurse-submodules https://github.com/darwinia-network/apk-verifier.git && cd apk-verifier
make tools
make

See inline code docs in the book

Testing and Testing Guide

1. Install Rust.

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

2. Install Foundry.

curl -L https://foundry.paradigm.xyz | bash

3. Build Darwinia Node.

git clone https://github.com/darwinia-network/darwinia.git --branch apk-verifier
cargo build --release -p darwinia --features pangolin-native

4. Run darwinia node.

./target/release/darwinia --chain pangolin-dev --alice --tmp --rpc-external --rpc-cors all --execution=native

5. Deploy basic/packed contract to local darwinia node.

make deploy-basic
make deploy-packed

6. Contract deployed at last transaction hash.
7. Run test script.

make test-basic  ADDR=0x3ed62137c5DB927cb137c26455969116BF0c23Cb
make test-packed ADDR=0xeAB4eEBa1FF8504c124D031F6844AD98d07C318f

8. Seeing the following results indicates that the test was successful.

0x0000000000000000000000000000000000000000000000000000000000000001

Run Test in Docker

1. Run darwinia dev node

local% docker run -it --name my_container ghcr.io/darwinia-network/apk-verifier:v0.1.1 "./bin/darwinia --chain pangolin-dev --alice --tmp --rpc-external --rpc-cors all --execution=native"

2. Deploy test contracts

Enter the running my_container:

local% docker exec -it my_container bash

In my_container:

root@097f7b4f10da:/usr/src/app# make deploy-basic
root@097f7b4f10da:/usr/src/app# make deploy-packed

3. Run test

In my_container:

root@097f7b4f10da:/usr/src/app# make test-basic  ADDR=0x3ed62137c5DB927cb137c26455969116BF0c23Cb
root@097f7b4f10da:/usr/src/app# make test-packed ADDR=0xeAB4eEBa1FF8504c124D031F6844AD98d07C318f

Seeing the following results indicates that the test was successful:

0x0000000000000000000000000000000000000000000000000000000000000001

License

Apache License v2.0

Contents

• bls12377
• bw6761
• bytes
• math
• pcs
• piop
• poly
• transcript
• Bitmask
• BitMask
• KeysetCommitment
• KeySet
• PackedProof
• Challenges
• AccountablePublicInput
• PublicInput
• SimpleProof
• Challenges

Contents

• Bls12Fp
• BLS12FP
• Bls12Fp2
• BLS12FP2
• Bls12G1
• BLS12G1Affine
• Bls12G2
• BLS12G2Affine
• BLS12Pairing

Bls12Fp

Git Source

BLS12-377 prime field.

struct Bls12Fp {
    uint256 a;
    uint256 b;
}

BLS12FP

Git Source

State Variables

MOD_EXP

MOD_EXP precompile address.

uint256 private constant MOD_EXP = 0x05;

Functions

q

Returns base field: q = 258664426012969094010652733694893533536393512754914660539884262666720468348340822774968888139573360124440321458177

function q() internal pure returns (Bls12Fp memory);

Returns

zero

Returns the additive identity element of Bls12Fp.

function zero() internal pure returns (Bls12Fp memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bls12Fp memory self) internal pure returns (bool);

Parameters

Returns

eq

Returns true if x is equal to y.

function eq(Bls12Fp memory x, Bls12Fp memory y) internal pure returns (bool);

Parameters

Returns

gt

Returns true if x is larger than y.

function gt(Bls12Fp memory x, Bls12Fp memory y) internal pure returns (bool);

Parameters

Returns

neg

Returns the result negative of self.

function neg(Bls12Fp memory self) internal pure returns (Bls12Fp memory z);

Parameters

Returns

add_nomod

Returns the result of x + y.

function add_nomod(Bls12Fp memory x, Bls12Fp memory y) internal pure returns (Bls12Fp memory z);

Parameters

Returns

sub

Returns the result of (x - y) % p.

function sub(Bls12Fp memory x, Bls12Fp memory y) internal pure returns (Bls12Fp memory z);

Parameters

Returns

into

Convert Bls12Fp to Bw6Fr.

function into(Bls12Fp memory x) internal pure returns (Bw6Fr memory);

Parameters

Returns

serialize

Serialize Bls12Fp.

function serialize(Bls12Fp memory self) internal pure returns (bytes memory);

Parameters

Returns

debug

Debug Bls12Fp in bytes.

function debug(Bls12Fp memory self) internal pure returns (bytes memory);

Parameters

Returns

norm

Normalize Bls12Fp.

function norm(Bls12Fp memory fp) internal view returns (Bls12Fp memory);

Parameters

Returns

Bls12Fp2

Git Source

BLS12-377 quadratic extension fields.

struct Bls12Fp2 {
    Bls12Fp c0;
    Bls12Fp c1;
}

BLS12FP2

Git Source

State Variables

DST_PRIME

See https://datatracker.ietf.org/doc/html/rfc9380#section-5.3.1

bytes private constant DST_PRIME = "APK-PROOF-with-BLS12377G2_XMD:SHA-256_SSWU_RO_.";

Z_PAD

See https://datatracker.ietf.org/doc/html/rfc9380#section-5.3.1

bytes private constant Z_PAD =
    hex"00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";

Functions

eq

Returns true if x is equal to y.

function eq(Bls12Fp2 memory x, Bls12Fp2 memory y) internal pure returns (bool);

Parameters

Returns

hash_to_field

Hash an arbitrary msg to 2 elements from field Fp2.

function hash_to_field(bytes memory message) internal view returns (Bls12Fp2[2] memory);

Parameters

Returns

expand_message_xmd

A uniformly random byte string using a cryptographic hash function H that outputs b bits.

function expand_message_xmd(bytes memory message) internal pure returns (bytes memory);

Parameters

Returns

norm

Normalize Bls12Fp2.

function norm(Bls12Fp2 memory fp2) internal view returns (Bls12Fp2 memory);

Parameters

Returns

debug

Debug Bls12Fp2 in bytes.

function debug(Bls12Fp2 memory fp2) internal pure returns (bytes memory);

Parameters

Returns

Bls12G1

Git Source

BLS12-377 G1 of affine coordinates in short Weierstrass.

struct Bls12G1 {
    Bls12Fp x;
    Bls12Fp y;
}

BLS12G1Affine

Git Source

State Variables

G1_ADD

BLS12_377_G1ADD precompile address.

uint256 private constant G1_ADD = 0x0801;

INFINITY_FLAG

INFINITY_FLAG

bytes1 private constant INFINITY_FLAG = bytes1(0x40);

Y_IS_NEGATIVE

Y_IS_NEGATIVE

bytes1 private constant Y_IS_NEGATIVE = bytes1(0x80);

Functions

generator

G1 generator

function generator() internal pure returns (Bls12G1 memory);

Returns

neg_generator

Negative G1 generator

function neg_generator() internal pure returns (Bls12G1 memory);

Returns

zero

Returns the additive identity element of Bls12G1.

function zero() internal pure returns (Bls12G1 memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bls12G1 memory self) internal pure returns (bool);

Parameters

Returns

is_infinity

Returns true if self is infinity point.

function is_infinity(Bls12G1 memory self) internal pure returns (bool);

Parameters

Returns

complement

Returns complement in G1 for apk-proofs.

function complement() internal pure returns (Bls12G1 memory);

Returns

add

Returns the result of p + q.

function add(Bls12G1 memory p, Bls12G1 memory q) internal view returns (Bls12G1 memory);

Parameters

Returns

from

Derive Bls12G1 from uint256[4].

function from(uint256[4] memory x) internal pure returns (Bls12G1 memory);

Parameters

Returns

serialize

Serialize Bls12G1.

function serialize(Bls12G1 memory g1) internal pure returns (bytes memory r);

Parameters

Returns

Bls12G2

Git Source

BLS12-377 G2 of affine coordinates in short Weierstrass.

struct Bls12G2 {
    Bls12Fp2 x;
    Bls12Fp2 y;
}

BLS12G2Affine

Git Source

State Variables

G2_ADD

BLS12_377_G2ADD precompile address.

uint256 private constant G2_ADD = 0x0804;

MAP_FP2_TO_G2

BLS12_377_MAP_FP2_TO_G2 precompile address.

uint256 private constant MAP_FP2_TO_G2 = 0x0809;

Functions

eq

Returns true if x is equal to y.

function eq(Bls12G2 memory a, Bls12G2 memory b) internal pure returns (bool);

Parameters

Returns

hash_to_curve

Produce a hash of the message. This uses the IETF hash to curve's specification for Random oracle encoding (hash_to_curve) defined by combining these components. See https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-09#section-3

function hash_to_curve(bytes memory message) internal view returns (Bls12G2 memory);

Parameters

Returns

add

Returns the result of p + q.

function add(Bls12G2 memory p, Bls12G2 memory q) internal view returns (Bls12G2 memory);

Parameters

Returns

map_to_curve

Map an arbitary field element to a corresponding curve point.

function map_to_curve(Bls12Fp2 memory fp2) internal view returns (Bls12G2 memory);

Parameters

Returns

from

Derive Bls12G1 from uint256[8].

function from(uint256[8] memory x) internal pure returns (Bls12G2 memory);

Parameters

Returns

debug

Debug Bls12G2 in bytes.

function debug(Bls12G2 memory p) internal pure returns (bytes memory);

Parameters

Returns

BLS12Pairing

Git Source

State Variables

BLS12_PAIRING

BLS12_377_PAIRING precompile address.

uint256 private constant BLS12_PAIRING = 0x0807;

Functions

verify

Checks that a signature is valid for the octet string message under the public key PK See https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-04#section-2.8

function verify(Bls12G1 memory public_key, Bls12G2 memory signature, Bls12G2 memory message)
    internal
    view
    returns (bool);

Parameters

Returns

pairing

Computes a "product" of pairings.

function pairing(Bls12G1[] memory a, Bls12G2[] memory b) internal view returns (bool);

Parameters

Returns

Contents

• Bw6Fp
• BW6FP
• Bw6Fr
• BW6FR
• Bw6G1
• BW6G1Affine
• Bw6G2
• BW6G2Affine
• BW6Pairing

Bw6Fp

Git Source

BW6-761 prime field.

struct Bw6Fp {
    uint256 a;
    uint256 b;
    uint256 c;
}

BW6FP

Git Source

Functions

q

Returns base field: q = 0x122e824fb83ce0ad187c94004faff3eb926186a81d14688528275ef8087be41707ba638e584e91903cebaff25b423048689c8ed12f9fd9071dcd3dc73ebff2e98a116c25667a8f8160cf8aeeaf0a437e6913e6870000082f49d00000000008b

function q() internal pure returns (Bw6Fp memory);

Returns

zero

Returns the additive identity element of Bw6Fp.

function zero() internal pure returns (Bw6Fp memory);

Returns

one

Returns the multiplicative identity element of Bw6Fp.

function one() internal pure returns (Bw6Fp memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bw6Fp memory self) internal pure returns (bool);

Parameters

Returns

is_geq_modulus

Returns true if self is equal or larger than q.

function is_geq_modulus(Bw6Fp memory self) internal pure returns (bool);

Parameters

Returns

eq

Returns true if x is equal to y.

function eq(Bw6Fp memory x, Bw6Fp memory y) internal pure returns (bool);

Parameters

Returns

gt

Returns true if x is larger than y.

function gt(Bw6Fp memory x, Bw6Fp memory y) internal pure returns (bool);

Parameters

Returns

neg

Returns the result negative of self.

function neg(Bw6Fp memory self) internal pure returns (Bw6Fp memory z);

Parameters

Returns

add_nomod

Returns the result of x + y.

function add_nomod(Bw6Fp memory x, Bw6Fp memory y) internal pure returns (Bw6Fp memory z);

Parameters

Returns

add

Returns the result of (x + y) % p.

function add(Bw6Fp memory x, Bw6Fp memory y) internal pure returns (Bw6Fp memory z);

Parameters

Returns

subtract_modulus_to_norm

function subtract_modulus_to_norm(Bw6Fp memory self) internal pure;

sub

Returns the result of (x - y) % p.

function sub(Bw6Fp memory x, Bw6Fp memory y) internal pure returns (Bw6Fp memory z);

Parameters

Returns

serialize

Serialize Bw6Fp.

function serialize(Bw6Fp memory self) internal pure returns (bytes memory);

Parameters

Returns

debug

Debug Bw6Fp in bytes.

function debug(Bw6Fp memory self) internal pure returns (bytes memory);

Parameters

Returns

Bw6Fr

Git Source

BW6-761 scalar field.

struct Bw6Fr {
    uint256 a;
    uint256 b;
}

BW6FR

Git Source

State Variables

MOD_EXP

MOD_EXP precompile address.

uint256 private constant MOD_EXP = 0x05;

Functions

r

Returns scalar field: r = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c00000000001

function r() internal pure returns (Bw6Fr memory);

Returns

zero

Returns the additive identity element of Bw6Fr.

function zero() internal pure returns (Bw6Fr memory);

Returns

one

Returns the multiplicative identity element of Bw6Fr.

function one() internal pure returns (Bw6Fr memory);

Returns

two

Returns the two of Bw6Fr.

function two() internal pure returns (Bw6Fr memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bw6Fr memory self) internal pure returns (bool);

Parameters

Returns

is_geq_modulus

Returns true if self is equal or larger than r.

function is_geq_modulus(Bw6Fr memory self) internal pure returns (bool);

Parameters

Returns

eq

Returns true if x is equal to y.

function eq(Bw6Fr memory x, Bw6Fr memory y) internal pure returns (bool);

Parameters

Returns

gt

Returns true if x is larger than y.

function gt(Bw6Fr memory x, Bw6Fr memory y) internal pure returns (bool);

Parameters

Returns

add_nomod

Returns the result of x + y.

function add_nomod(Bw6Fr memory x, Bw6Fr memory y) internal pure returns (Bw6Fr memory z);

Parameters

Returns

add

Returns the result of (x + y) % p.

function add(Bw6Fr memory x, Bw6Fr memory y) internal pure returns (Bw6Fr memory z);

Parameters

Returns

subtract_modulus_to_norm

function subtract_modulus_to_norm(Bw6Fr memory self) internal pure returns (Bw6Fr memory z);

sub

Returns the result of (x - y) % p.

function sub(Bw6Fr memory x, Bw6Fr memory y) internal pure returns (Bw6Fr memory z);

Parameters

Returns

sub

Returns the result of x - y.

function sub(Bw6Fr[2] memory x, Bw6Fr[2] memory y) internal pure returns (Bw6Fr[2] memory z);

Parameters

Returns

mul

(x * y) = ((x + y)^2 - (x - y)^2) / 4

function mul(Bw6Fr memory x, Bw6Fr memory y) internal view returns (Bw6Fr memory z);

Parameters

Returns

sum

Sum of the list of Bw6Fr.

function sum(Bw6Fr[] memory xs) internal pure returns (Bw6Fr memory);

Parameters

Returns

mul_sum

Mul and Add.

function mul_sum(Bw6Fr[] memory xs, Bw6Fr[] memory ys) internal view returns (Bw6Fr memory z);

Parameters

Returns

div2

self / two

function div2(Bw6Fr[2] memory self) internal pure returns (Bw6Fr[2] memory z);

Parameters

Returns

inverse

Constant time inversion using Fermat's little theorem. For a prime p and for any a < p, a^p = a % p => a^(p-1) = 1 % p => a^(p-2) = a^-1 % p

function inverse(Bw6Fr memory self) internal view returns (Bw6Fr memory);

Parameters

Returns

square

self^2 % r.

function square(Bw6Fr memory self) internal view returns (Bw6Fr memory);

Parameters

Returns

pow

base^exp % r

function pow(Bw6Fr memory base, uint256 exp) internal view returns (Bw6Fr memory);

Parameters

Returns

mod_exp

base^base % modulus

function mod_exp(Bw6Fr memory base, uint256 exp, Bw6Fr memory modulus) internal view returns (Bw6Fr memory);

Parameters

Returns

square_nomod

self^2

function square_nomod(Bw6Fr memory self) internal view returns (Bw6Fr[2] memory);

Parameters

Returns

norm

Normalize Bw6Fr[2].

function norm(Bw6Fr[2] memory self) internal view returns (Bw6Fr memory);

Parameters

Returns

powers

(max_exp+1)-sized vec: 1, base, base^2,... ,base^{max_exp}

function powers(Bw6Fr memory base, uint256 max_exp) internal view returns (Bw6Fr[] memory);

Parameters

Returns

horner_field

Horner field

function horner_field(Bw6Fr[] memory bases, Bw6Fr memory nu) internal view returns (Bw6Fr memory);

Parameters

Returns

from_random_bytes

Derive Bw6Fr from bytes in LE order.

function from_random_bytes(bytes16 input) internal pure returns (Bw6Fr memory);

Parameters

Returns

serialize

Serialize Bw6Fr.

function serialize(Bw6Fr memory self) internal pure returns (bytes memory);

Parameters

Returns

debug

Debug Bw6Fr in bytes.

function debug(Bw6Fr memory self) internal pure returns (bytes memory);

Parameters

Returns

Bw6G1

Git Source

BW6-761 G1 of affine coordinates in short Weierstrass.

struct Bw6G1 {
    Bw6Fp x;
    Bw6Fp y;
}

BW6G1Affine

Git Source

State Variables

G1_ADD

BW6_G1_ADD precompile address.

uint256 private constant G1_ADD = 0x080a;

G1_MUL

BW6_G1_MUL precompile address.

uint256 private constant G1_MUL = 0x080b;

G1_MULTIEXP

BW6_G1_MULTIEXP precompile address.

uint256 private constant G1_MULTIEXP = 0x080c;

INFINITY_FLAG

INFINITY_FLAG

bytes1 private constant INFINITY_FLAG = bytes1(0x40);

Y_IS_NEGATIVE

Y_IS_NEGATIVE

bytes1 private constant Y_IS_NEGATIVE = bytes1(0x80);

Functions

zero

Returns the additive identity element of Bw6G1.

function zero() internal pure returns (Bw6G1 memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bw6G1 memory self) internal pure returns (bool);

Parameters

Returns

is_infinity

Returns true if self is infinity point.

function is_infinity(Bw6G1 memory self) internal pure returns (bool);

Parameters

Returns

eq

Returns true if a is equal to a.

function eq(Bw6G1 memory a, Bw6G1 memory b) internal pure returns (bool);

Parameters

Returns

neg

If self.is_zero(), returns self (== Self::zero()). Else, returns (x, -y), where self = (x, y).

function neg(Bw6G1 memory self) internal pure;

Parameters

add

Returns the result of p + q.

function add(Bw6G1 memory p, Bw6G1 memory q) internal view returns (Bw6G1 memory);

Parameters

sub

Returns the result of p - q.

function sub(Bw6G1 memory p, Bw6G1 memory q) internal view returns (Bw6G1 memory z);

Parameters

Returns

mul

Returns the result of p * scalar.

function mul(Bw6G1 memory p, Bw6Fr memory scalar) internal view returns (Bw6G1 memory);

Parameters

Returns

msm

Multi-scalar multiplication

function msm(Bw6G1[] memory bases, Bw6Fr[] memory scalars) internal view returns (Bw6G1 memory);

Parameters

Returns

from

Derive Bw6G1 from uint256[6].

function from(uint256[6] memory x) internal pure returns (Bw6G1 memory);

Parameters

Returns

serialize

Serialize Bw6G1.

function serialize(Bw6G1 memory g1) internal pure returns (bytes memory r);

Parameters

Returns

debug

Debug Bw6G1 in bytes.

function debug(Bw6G1 memory self) internal pure returns (bytes memory);

Parameters

Returns

Bw6G2

Git Source

BW6-761 G2 of affine coordinates in short Weierstrass.

struct Bw6G2 {
    Bw6Fp x;
    Bw6Fp y;
}

BW6G2Affine

Git Source

State Variables

INFINITY_FLAG

INFINITY_FLAG

bytes1 private constant INFINITY_FLAG = bytes1(0x40);

Y_IS_NEGATIVE

Y_IS_NEGATIVE

bytes1 private constant Y_IS_NEGATIVE = bytes1(0x80);

Functions

zero

Returns the additive identity element of Bw6G2.

function zero() internal pure returns (Bw6G2 memory);

Returns

is_zero

Returns true if self is equal to the additive identity.

function is_zero(Bw6G2 memory self) internal pure returns (bool);

Parameters

Returns

is_infinity

Returns true if self is infinity point.

function is_infinity(Bw6G2 memory self) internal pure returns (bool);

Parameters

Returns

serialize

Serialize Bw6G2.

function serialize(Bw6G2 memory g2) internal pure returns (bytes memory r);

Parameters

Returns

BW6Pairing

Git Source

State Variables

BW6_PAIRING

BW6_PAIRING precompile address.

uint256 private constant BW6_PAIRING = 0x0810;

Functions

pairing

Computes a "product" of pairings.

function pairing(Bw6G1[] memory a, Bw6G2[] memory b) internal view returns (bool);

Parameters

Returns

Contents

• Bits
• ByteOrder

Bits

Git Source

State Variables

ONE

uint256 private constant ONE = uint256(1);

ONES

uint256 private constant ONES = type(uint256).max;

Functions

setBit

Sets the bit at the given 'index' in 'self' to '1'. Returns The modified value.

function setBit(uint256 self, uint8 index) internal pure returns (uint256);

clearBit

Sets the bit at the given 'index' in 'self' to '0'. Returns the modified value.

function clearBit(uint256 self, uint8 index) internal pure returns (uint256);

toggleBit

Sets the bit at the given 'index' in 'self' to: '1' - if the bit is '0' '0' - if the bit is '1' Returns the modified value.

function toggleBit(uint256 self, uint8 index) internal pure returns (uint256);

bit

Get the value of the bit at the given 'index' in 'self'.

function bit(uint256 self, uint8 index) internal pure returns (uint8);

bitSet

Check if the bit at the given 'index' in 'self' is set. Returns: 'true' - if the value of the bit is '1' 'false' - if the value of the bit is '0'

function bitSet(uint256 self, uint8 index) internal pure returns (bool);

bitEqual

Checks if the bit at the given 'index' in 'self' is equal to the corresponding bit in 'other'. Returns: 'true' - if both bits are '0' or both bits are '1' 'false' - otherwise

function bitEqual(uint256 self, uint256 other, uint8 index) internal pure returns (bool);

bitNot

Get the bitwise NOT of the bit at the given 'index' in 'self'.

function bitNot(uint256 self, uint8 index) internal pure returns (uint8);

bitAnd

Computes the bitwise AND of the bit at the given 'index' in 'self', and the corresponding bit in 'other', and returns the value.

function bitAnd(uint256 self, uint256 other, uint8 index) internal pure returns (uint8);

bitOr

Computes the bitwise OR of the bit at the given 'index' in 'self', and the corresponding bit in 'other', and returns the value.

function bitOr(uint256 self, uint256 other, uint8 index) internal pure returns (uint8);

bitXor

Computes the bitwise XOR of the bit at the given 'index' in 'self', and the corresponding bit in 'other', and returns the value.

function bitXor(uint256 self, uint256 other, uint8 index) internal pure returns (uint8);

bits

*Gets 'numBits' consecutive bits from 'self', starting from the bit at 'startIndex'. Returns the bits as a 'uint'. Requires that:

• '0 < numBits <= 256'
• 'startIndex < 256'
• 'numBits + startIndex <= 256'*

function bits(uint256 self, uint8 startIndex, uint16 numBits) internal pure returns (uint256);

highestBitSet

Computes the index of the highest bit set in 'self'. Returns the highest bit set as an 'uint8'. Requires that 'self != 0'.

function highestBitSet(uint256 self) internal pure returns (uint8 highest);

lowestBitSet

Computes the index of the lowest bit set in 'self'. Returns the lowest bit set as an 'uint8'. Requires that 'self != 0'.

function lowestBitSet(uint256 self) internal pure returns (uint8 lowest);

ByteOrder

Git Source

Functions

reverse256

Reverse uint256

function reverse256(uint256 input) internal pure returns (uint256 v);

reverse128

Reverse uint128

function reverse128(uint128 input) internal pure returns (uint128 v);

reverse64

Reverse uint64

function reverse64(uint64 input) internal pure returns (uint64 v);

reverse32

Reverse uint32

function reverse32(uint32 input) internal pure returns (uint32 v);

reverse16

Reverse uint16

function reverse16(uint16 input) internal pure returns (uint16 v);

Contents

• Math

Math

Git Source

Functions

adc

Add with carry (carry, d) = a + b + carry.

function adc(uint256 a, uint256 b, uint8 carry) internal pure returns (uint8, uint256);

sbb

Sub with borrow (borrow, d) = a - b - borrow.

function sbb(uint256 a, uint256 b, uint8 borrow) internal pure returns (uint8, uint256);

Contents

• aggregation
• kzg

Contents

• Single

Single

Git Source

Functions

aggregate_claims_multiexp

Aggregate claims multiexp

function aggregate_claims_multiexp(Bw6G1[] memory cs, Bw6Fr[] memory ys, Bw6Fr[] memory rs)
    internal
    view
    returns (Bw6G1 memory, Bw6Fr memory);

Contents

• AccumulatedOpening
• KzgOpening
• KZG
• RVK
• KZGParams

AccumulatedOpening

Git Source

e(acc, g2) = e(proof, tau.g2)

struct AccumulatedOpening {
    Bw6G1 acc;
    Bw6G1 proof;
}

KzgOpening

Git Source

KZG Opening

struct KzgOpening {
    Bw6G1 c;
    Bw6Fr x;
    Bw6Fr y;
    Bw6G1 proof;
}

KZG

Git Source

Functions

accumulate

KZG accumulate

function accumulate(KzgOpening[] memory openings, Bw6Fr[] memory rs, RVK memory vk)
    internal
    view
    returns (AccumulatedOpening memory);

verify_accumulated

KZG verification

function verify_accumulated(AccumulatedOpening memory opening, RVK memory vk) internal view returns (bool);

RVK

Git Source

KZG raw verifier key.

struct RVK {
    Bw6G1 g1;
    Bw6G2 g2;
    Bw6G2 tau_in_g2;
}

KZGParams

Git Source

Functions

raw_vk

KZG verifier key.

function raw_vk() public pure returns (RVK memory);

Returns

serialize

function serialize(RVK memory self) internal pure returns (bytes memory);

Contents

• PartialSumsCommitments
• AffineAdditionEvaluations
• AffineAdditionEvaluationsWithoutBitmask
• BasicProtocol
• BitmaskPackingCommitments
• PartialSumsAndBitmaskCommitments
• SuccinctAccountableRegisterEvaluations
• PackedProtocol

PartialSumsCommitments

Git Source

Partial sums commitments

struct PartialSumsCommitments {
    Bw6G1[2] partial_sums;
}

AffineAdditionEvaluations

Git Source

Affine addition evaluations

struct AffineAdditionEvaluations {
    Bw6Fr[2] keyset;
    Bw6Fr bitmask;
    Bw6Fr[2] partial_sums;
}

AffineAdditionEvaluationsWithoutBitmask

Git Source

Affine addition evaluations without bitmask

struct AffineAdditionEvaluationsWithoutBitmask {
    Bw6Fr[2] keyset;
    Bw6Fr[2] partial_sums;
}

BasicProtocol

Git Source

State Variables

POLYS_OPENED_AT_ZETA

uint256 internal constant POLYS_OPENED_AT_ZETA = 5;

Functions

restore_commitment_to_linearization_polynomial

Restore commitment to linearization polynomial.

function restore_commitment_to_linearization_polynomial(
    AffineAdditionEvaluations memory self,
    Bw6Fr memory phi,
    Bw6Fr memory zeta_minus_omega_inv,
    Bw6G1[2] memory commitments
) internal view returns (Bw6G1 memory);

evaluate_constraint_polynomials

Evaluate constraint polynomials.

function evaluate_constraint_polynomials(
    AffineAdditionEvaluations memory self,
    Bls12G1 memory apk,
    LagrangeEvaluations memory evals_at_zeta
) internal view returns (Bw6Fr[] memory);

evaluate_conditional_affine_addition_constraints_linearized

Evaluate conditional affine addition constraints linearized.

function evaluate_conditional_affine_addition_constraints_linearized(
    Bw6Fr memory zeta_minus_omega_inv,
    Bw6Fr memory b,
    Bw6Fr memory x1,
    Bw6Fr memory y1,
    Bw6Fr memory x2,
    Bw6Fr memory y2
) internal view returns (Bw6Fr memory, Bw6Fr memory);

evaluate_bitmask_booleanity_constraint

Evaluate bitmask booleanity constraint.

function evaluate_bitmask_booleanity_constraint(Bw6Fr memory bitmask_at_zeta) internal view returns (Bw6Fr memory);

evaluate_public_inputs_constraints

Evaluate public inputs constraints.

function evaluate_public_inputs_constraints(
    Bls12G1 memory apk,
    LagrangeEvaluations memory evals_at_zeta,
    Bw6Fr memory x1,
    Bw6Fr memory y1
) internal view returns (Bw6Fr memory, Bw6Fr memory);

serialize

Serialize AffineAdditionEvaluations.

function serialize(AffineAdditionEvaluations memory self) internal pure returns (bytes memory);

Parameters

Returns

BitmaskPackingCommitments

Git Source

Bitmask packing commitments

struct BitmaskPackingCommitments {
    Bw6G1 c_comm;
    Bw6G1 acc_comm;
}

PartialSumsAndBitmaskCommitments

Git Source

Partial sums and bitmask commitments

struct PartialSumsAndBitmaskCommitments {
    Bw6G1[2] partial_sums;
    Bw6G1 bitmask;
}

SuccinctAccountableRegisterEvaluations

Git Source

Succinct accountable register evaluations

struct SuccinctAccountableRegisterEvaluations {
    Bw6Fr c;
    Bw6Fr acc;
    AffineAdditionEvaluations basic_evaluations;
}

PackedProtocol

Git Source

State Variables

POLYS_OPENED_AT_ZETA

uint256 internal constant POLYS_OPENED_AT_ZETA = 8;

Functions

restore_commitment_to_linearization_polynomial

Restore commitment to linearization polynomial.

function restore_commitment_to_linearization_polynomial(
    SuccinctAccountableRegisterEvaluations memory self,
    Bw6Fr memory phi,
    Bw6Fr memory zeta_minus_omega_inv,
    PartialSumsAndBitmaskCommitments memory commitments,
    BitmaskPackingCommitments memory extra_commitments
) internal view returns (Bw6G1 memory);

evaluate_constraint_polynomials

Evaluate constraint polynomials.

function evaluate_constraint_polynomials(
    SuccinctAccountableRegisterEvaluations memory self,
    Bls12G1 memory apk,
    LagrangeEvaluations memory evals_at_zeta,
    Bw6Fr memory r,
    Bitmask memory bitmask,
    uint64 domain_size
) internal view returns (Bw6Fr[] memory constraint_polynomial_evals);

evaluate_inner_product_constraint_linearized

Evaluate inner product constraint linearized.

function evaluate_inner_product_constraint_linearized(
    Bw6Fr memory bitmask_chunks_aggregated,
    LagrangeEvaluations memory evals_at_zeta,
    Bw6Fr memory b_zeta,
    Bw6Fr memory c_zeta,
    Bw6Fr memory acc_zeta
) internal view returns (Bw6Fr memory);

evaluate_multipacking_mask_constraint_linearized

Evaluate multipacking mask constraint linearized.

function evaluate_multipacking_mask_constraint_linearized(
    Bw6Fr memory a,
    Bw6Fr memory r_pow_m,
    LagrangeEvaluations memory evals_at_zeta,
    Bw6Fr memory c_zeta
) internal view returns (Bw6Fr memory);

serialize

Serialize PartialSumsAndBitmaskCommitments.

function serialize(PartialSumsAndBitmaskCommitments memory self) internal pure returns (bytes memory);

Parameters

Returns

serialize

Serialize BitmaskPackingCommitments.

function serialize(BitmaskPackingCommitments memory self) internal pure returns (bytes memory);

Parameters

Returns

serialize

Serialize SuccinctAccountableRegisterEvaluations.

function serialize(SuccinctAccountableRegisterEvaluations memory self) internal pure returns (bytes memory);

Parameters

Returns

Contents

• domain
• evaluations

Contents

• Radix2EvaluationDomain
• Radix2

Radix2EvaluationDomain

Git Source

Defines a domain over which finite field (I)FFTs can be performed. Works only for fields that have a large multiplicative subgroup of size that is a power-of-2.

struct Radix2EvaluationDomain {
    uint64 size;
    uint32 log_size_of_group;
    Bw6Fr size_as_field_element;
    Bw6Fr size_inv;
    Bw6Fr group_gen;
    Bw6Fr group_gen_inv;
    Bw6Fr offset;
    Bw6Fr offset_inv;
    Bw6Fr offset_pow_size;
}

Radix2

Git Source

State Variables

LOG_N

log_n

uint32 internal constant LOG_N = 8;

Functions

init

Domain used to interpolate pks.

function init() public pure returns (Radix2EvaluationDomain memory);

serialize

Serialize Radix2EvaluationDomain.

function serialize(Radix2EvaluationDomain memory self) internal pure returns (bytes memory);

Parameters

Returns

Contents

• LagrangeEvaluations
• Lagrange

LagrangeEvaluations

Git Source

Values of the polynomials at a point z

struct LagrangeEvaluations {
    Bw6Fr vanishing_polynomial;
    Bw6Fr l_first;
    Bw6Fr l_last;
    Bw6Fr zeta_minus_omega_inv;
    Bw6Fr zeta_omega;
}

Lagrange

Git Source

Functions

lagrange_evaluations

Lagrange evaluations.

function lagrange_evaluations(Bw6Fr memory z, Radix2EvaluationDomain memory dm)
    internal
    view
    returns (LagrangeEvaluations memory);

barycentric_eval_binary_at

function barycentric_eval_binary_at(Bw6Fr memory z, Bitmask memory evals, Radix2EvaluationDomain memory dm)
    internal
    view
    returns (Bw6Fr memory);

Contents

• Transcript
• SimpleTranscript

Transcript

Git Source

Transcript

struct Transcript {
    bytes buffer;
}

SimpleTranscript

Git Source

Functions

simple_fiat_shamir_rng

Simple fiat shamir rng

function simple_fiat_shamir_rng(Transcript memory self) internal pure returns (Transcript memory);

set_protocol_params

function set_protocol_params(Transcript memory self, bytes memory domain, bytes memory kzg_vk) internal pure;

set_keyset_commitment

function set_keyset_commitment(Transcript memory self, bytes memory keyset_commitment) internal pure;

append_public_input

function append_public_input(Transcript memory self, bytes memory public_input) internal pure;

append_register_commitments

function append_register_commitments(Transcript memory self, bytes memory register_commitments) internal pure;

get_bitmask_aggregation_challenge

function get_bitmask_aggregation_challenge(Transcript memory self) internal pure returns (Bw6Fr memory);

append_2nd_round_register_commitments

function append_2nd_round_register_commitments(Transcript memory self, bytes memory register_commitments)
    internal
    pure;

get_constraints_aggregation_challenge

function get_constraints_aggregation_challenge(Transcript memory self) internal pure returns (Bw6Fr memory);

append_quotient_commitment

function append_quotient_commitment(Transcript memory self, bytes memory point) internal pure;

get_evaluation_point

function get_evaluation_point(Transcript memory self) internal pure returns (Bw6Fr memory);

append_evaluations

function append_evaluations(
    Transcript memory self,
    bytes memory evals,
    bytes memory q_at_zeta,
    bytes memory r_at_zeta_omega
) internal pure;

get_kzg_aggregation_challenges

function get_kzg_aggregation_challenges(Transcript memory self, uint256 n) internal pure returns (Bw6Fr[] memory);

init

function init(bytes memory message) internal pure returns (Transcript memory);

update

function update(Transcript memory self, bytes memory message) internal pure;

reset

function reset(Transcript memory self) internal pure;

finalize

function finalize(Transcript memory self) internal pure returns (bytes16);

_get_128_bit_challenge

function _get_128_bit_challenge(Transcript memory self, bytes memory label) internal pure returns (Bw6Fr memory);

_get_128_bit_challenges

function _get_128_bit_challenges(Transcript memory self, bytes memory label, uint256 n)
    internal
    pure
    returns (Bw6Fr[] memory);

_append_serializable

function _append_serializable(Transcript memory self, bytes memory label, bytes memory message) internal pure;

rand_u128

function rand_u128(Transcript memory self) internal pure returns (Bw6Fr memory);

Bitmask

Git Source

The highest limb of bitmask is left padded with 0s.

Bitmask bitvector of signers.

struct Bitmask {
    uint256[] limbs;
    uint64 padding_size;
}

BitMask

Git Source

State Variables

M1

Constants used to efficiently calculate the hamming weight of a bitfield. See https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation for an explanation of those constants.

uint256 internal constant M1 = 0x5555555555555555555555555555555555555555555555555555555555555555;

M2

uint256 internal constant M2 = 0x3333333333333333333333333333333333333333333333333333333333333333;

M4

uint256 internal constant M4 = 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f;

M8

uint256 internal constant M8 = 0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff;

M16

uint256 internal constant M16 = 0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff;

M32

uint256 internal constant M32 = 0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff;

M64

uint256 internal constant M64 = 0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff;

M128

uint256 internal constant M128 = 0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff;

BITS_IN_LIMB

uint256 internal constant BITS_IN_LIMB = 256;

NNNN

uint256 internal constant NNNN = 4;

Functions

count_ones

Calculates the number of set bits by using the hamming weight of the bitfield. The algorithm below is implemented after https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation. Further improvements are possible, see the article above.

function count_ones(Bitmask memory self) internal pure returns (uint256);

Parameters

Returns

count_ones

function count_ones(uint256 x) internal pure returns (uint256);

size

Actual size of bitmask, not including the padding.

function size(Bitmask memory self) internal pure returns (uint256);

Parameters

Returns

at

Bit at index of bitmask.

function at(Bitmask memory self, uint256 index) internal pure returns (bool);

Parameters

Returns

serialize

function serialize(Bitmask memory self) internal pure returns (bytes memory);

KeysetCommitment

Git Source

In light client protocols the commitment is to the upcoming validator set, signed by the current validator set. Honest validator checks the proofs of possession, interpolates with the right padding over the right domain, computes the commitment using the right parameters, and then sign it. Verifier checks the signatures and can trust that the properties hold under some "2/3 honest validators" assumption. As every honest validator generates the same commitment, verifier needs to check only the aggregate signature.

*Polynomial commitment to the vector of public keys. Let 'pks' be such a vector that commit(pks) == KeysetCommitment::pks_comm, also let domain_size := KeysetCommitment::domain.size and keyset_size := KeysetCommitment::keyset_size Then the verifier needs to trust that:

1. a. pks.len() == KeysetCommitment::domain.size b. pks[i] lie in BLS12-377 G1 for i=0,...,domain_size-2 c. for the 'real' keys pks[i], i=0,...,keyset_size-1, there exist proofs of possession for the padding, pks[i], i=keyset_size,...,domain_size-2, dlog is not known, e.g. pks[i] = hash_to_g1("something"). pks[domain_size-1] is not a part of the relation (not constrained) and can be anything, we set pks[domain_size-1] = (0,0), not even a curve point.
2. KeysetCommitment::domain is the domain used to interpolate pks*

struct KeysetCommitment {
    Bw6G1[2] pks_comm;
    uint32 log_domain_size;
}

KeySet

Git Source

Functions

serialize

Serialize KeysetCommitment.

function serialize(KeysetCommitment memory self) internal pure returns (bytes memory);

Parameters

Returns

hash_commitment

Hash commitment to BLS12-377 G2 element.

function hash_commitment(KeysetCommitment memory self) internal view returns (Bls12G2 memory);

Parameters

Returns

PackedProof

Git Source

PackedProof

struct PackedProof {
    PartialSumsAndBitmaskCommitments register_commitments;
    BitmaskPackingCommitments additional_commitments;
    Bw6G1 q_comm;
    SuccinctAccountableRegisterEvaluations register_evaluations;
    Bw6Fr q_zeta;
    Bw6Fr r_zeta_omega;
    Bw6G1 w_at_zeta_proof;
    Bw6G1 r_at_zeta_omega_proof;
}

Challenges

Git Source

struct Challenges {
    Bw6Fr r;
    Bw6Fr phi;
    Bw6Fr zeta;
    Bw6Fr[] nus;
}

AccountablePublicInput

Git Source

Accountable public input.

struct AccountablePublicInput {
    Bls12G1 apk;
    Bitmask bitmask;
}

PublicInput

Git Source

Functions

serialize

Serialize AccountablePublicInput.

function serialize(AccountablePublicInput memory self) internal pure returns (bytes memory);

Parameters

Returns

SimpleProof

Git Source

SimpleProof

struct SimpleProof {
    Bw6G1[2] register_commitments;
    Bw6G1 q_comm;
    AffineAdditionEvaluationsWithoutBitmask register_evaluations;
    Bw6Fr q_zeta;
    Bw6Fr r_zeta_omega;
    Bw6G1 w_at_zeta_proof;
    Bw6G1 r_at_zeta_omega_proof;
}

Challenges

Git Source

struct Challenges {
    Bw6Fr r;
    Bw6Fr phi;
    Bw6Fr zeta;
    Bw6Fr[] nus;
}

Basic

Git Source

APK verifier based 'basic' scheme.

*Light client's state is initialized with a commitment 'C0' to the ('genesis') validator set of the era #0 (and some technical stuff, like public parameters). When an era (tautologically, a validator set) changes, a helper provides:

1. the commitment 'C1' to the new validator set,
2. an aggregate signature 'asig0' of a subset of validators of the previous era on the new commitment 'C1',
3. an aggregate public key 'apk0' of this subset of validators,
4. a bitmask 'b0' identifying this subset in the whole set of the validators of the previous era, and
5. a proof 'p0', that attests that the key 'apk0' is indeed the aggregate public key of a subset identified by 'b0' of the set of the validators, identified by the commitment 'C0', of the previous era. All together this is ('C1', 'asig0', 'apk0', 'b0', 'p0'). The light client:
6. makes sure that the key 'apk0' is correct by verifying the proof 'p0': apk_verify('apk0', 'b0', 'C0'; 'p0') == true
7. verifies the aggregate signature 'asig0' agains the key 'apk0': bls_verify('asig0', 'apk0', 'C1') == true
8. If both checks passed and the bitmask contains enough (say, >2/3 of) signers, updates its state to the new commitment 'C1'.*

State Variables

pks_comm

Genesis validator set of the era #0.

KeysetCommitment public pks_comm;

QUORUM

The majority amount of signers.

uint256 internal constant QUORUM = 171;

Functions

constructor

Init.

constructor(Bw6G1[2] memory c0);

Parameters

domain

Only for fields that have a large multiplicative subgroup of size that is a power-of-2.

Domain used to interpolate pks.

function domain() internal pure returns (Radix2EvaluationDomain memory);

verify_aggregates

*Core function aggregate all verify.

1. apk_verify.
2. bls_verify.
3. threhold check.*

function verify_aggregates(
    AccountablePublicInput calldata public_input,
    SimpleProof calldata proof,
    Bls12G2 calldata aggregate_signature,
    KeysetCommitment calldata new_validator_set_commitment
) external view returns (bool);

Parameters

Returns

verify_bls

Verify BLS aggregate signature.

function verify_bls(
    Bls12G1 memory aggregate_public_key,
    Bls12G2 memory aggregate_signature,
    KeysetCommitment calldata new_validator_set_commitment
) internal view returns (bool);

Parameters

Returns

verify_simple

APK verify for basic scheme.

function verify_simple(AccountablePublicInput calldata public_input, SimpleProof calldata proof)
    internal
    view
    returns (bool);

Parameters

Returns

restore_challenges

Restore challenges.

function restore_challenges(
    AccountablePublicInput calldata public_input,
    SimpleProof calldata proof,
    uint256 batch_size
) internal view returns (Challenges memory, Transcript memory);

Parameters

Returns

validate_evaluations

Validate evaluations.

function validate_evaluations(
    SimpleProof memory proof,
    AffineAdditionEvaluations memory protocol,
    Challenges memory challenges,
    Transcript memory fsrng,
    LagrangeEvaluations memory evals_at_zeta
) internal view;

Parameters

kzg_pvk

KZG verifier key.

function kzg_pvk() internal pure returns (RVK memory);

Returns

Packed

Git Source

APK verifier based 'packed' scheme.

*Light client's state is initialized with a commitment 'C0' to the ('genesis') validator set of the era #0 (and some technical stuff, like public parameters). When an era (tautologically, a validator set) changes, a helper provides:

1. the commitment 'C1' to the new validator set,
2. an aggregate signature 'asig0' of a subset of validators of the previous era on the new commitment 'C1',
3. an aggregate public key 'apk0' of this subset of validators,
4. a bitmask 'b0' identifying this subset in the whole set of the validators of the previous era, and
5. a proof 'p0', that attests that the key 'apk0' is indeed the aggregate public key of a subset identified by 'b0' of the set of the validators, identified by the commitment 'C0', of the previous era. All together this is ('C1', 'asig0', 'apk0', 'b0', 'p0'). The light client:
6. makes sure that the key 'apk0' is correct by verifying the proof 'p0': apk_verify('apk0', 'b0', 'C0'; 'p0') == true
7. verifies the aggregate signature 'asig0' agains the key 'apk0': bls_verify('asig0', 'apk0', 'C1') == true
8. If both checks passed and the bitmask contains enough (say, >2/3 of) signers, updates its state to the new commitment 'C1'.*

State Variables

pks_comm

Genesis validator set of the era #0.

KeysetCommitment public pks_comm;

QUORUM

The majority amount of signers.

uint256 internal constant QUORUM = 171;

Functions

constructor

Init.

constructor(Bw6G1[2] memory c0);

Parameters

domain

Only for fields that have a large multiplicative subgroup of size that is a power-of-2.

Domain used to interpolate pks.

function domain() internal pure returns (Radix2EvaluationDomain memory);

verify_aggregates

*Core function aggregate all verify.

1. apk_verify.
2. bls_verify.
3. threhold check.*

function verify_aggregates(
    AccountablePublicInput calldata public_input,
    PackedProof calldata proof,
    Bls12G2 calldata aggregate_signature,
    KeysetCommitment calldata new_validator_set_commitment
) external view returns (bool);

Parameters

Returns

verify_bls

Verify BLS aggregate signature.

function verify_bls(
    Bls12G1 memory aggregate_public_key,
    Bls12G2 memory aggregate_signature,
    KeysetCommitment calldata new_validator_set_commitment
) internal view returns (bool);

Parameters

Returns

verify_packed

APK verify for packed scheme.

function verify_packed(AccountablePublicInput calldata public_input, PackedProof calldata proof)
    internal
    view
    returns (bool);

Parameters

Returns

restore_challenges

Restore challenges.

function restore_challenges(
    AccountablePublicInput calldata public_input,
    PackedProof calldata proof,
    uint256 batch_size
) internal view returns (Challenges memory, Transcript memory);

Parameters

Returns

validate_evaluations

Validate evaluations.

function validate_evaluations(
    PackedProof calldata proof,
    Challenges memory challenges,
    Transcript memory fsrng,
    LagrangeEvaluations memory evals_at_zeta
) internal view;

Parameters

kzg_pvk

KZG verifier key.

function kzg_pvk() internal pure returns (RVK memory);

Returns