Module `0x1::crypto_algebra`

This module provides generic structs/functions for operations of algebraic structures (e.g. fields and groups), which can be used to build generic cryptographic schemes atop. E.g., a Groth16 ZK proof verifier can be built to work over any pairing supported in this module.

In general, every structure implements basic operations like (de)serialization, equality check, random sampling.

A group may also implement the following operations. (Additive group notation is assumed.)

order() for getting the group order.
zero() for getting the group identity.
one() for getting the group generator (if exists).
neg() for group element inversion.
add() for group operation (i.e., a group addition).
sub() for group element subtraction.
double() for efficient doubling.
scalar_mul() for group scalar multiplication.
multi_scalar_mul() for efficient group multi-scalar multiplication.
hash_to() for hash-to-group.

A field may also implement the following operations.

zero() for getting the field additive identity.
one() for getting the field multiplicative identity.
add() for field addition.
sub() for field subtraction.
mul() for field multiplication.
div() for field division.
neg() for field negation.
inv() for field inversion.
sqr() for efficient field element squaring.
from_u64() for quick conversion from u64 to field element.

For 3 groups that admit a bilinear map, pairing() and multi_pairing() may be implemented.

For a subset/superset relationship between 2 structures, upcast() and downcast() may be implemented. E.g., in BLS12-381 pairing, since Gt is a subset of Fq12, upcast<Gt, Fq12>() and downcast<Fq12, Gt>() will be supported.

See *_algebra.move for currently implemented algebraic structures.

Struct Element
Constants
Function eq
Function from_u64
Function zero
Function one
Function neg
Function add
Function sub
Function mul
Function div
Function sqr
Function inv
Function double
Function multi_scalar_mul
Function scalar_mul
Function multi_pairing
Function pairing
Function deserialize
Function serialize
Function order
Function upcast
Function downcast
Function hash_to
Function abort_unless_cryptography_algebra_natives_enabled
Function handles_from_elements
Function add_internal
Function deserialize_internal
Function div_internal
Function double_internal
Function downcast_internal
Function from_u64_internal
Function eq_internal
Function hash_to_internal
Function inv_internal
Function mul_internal
Function multi_pairing_internal
Function multi_scalar_mul_internal
Function neg_internal
Function one_internal
Function order_internal
Function pairing_internal
Function scalar_mul_internal
Function serialize_internal
Function sqr_internal
Function sub_internal
Function upcast_internal
Function zero_internal
Specification
- Function handles_from_elements
- Function add_internal
- Function deserialize_internal
- Function div_internal
- Function double_internal
- Function downcast_internal
- Function from_u64_internal
- Function eq_internal
- Function hash_to_internal
- Function inv_internal
- Function mul_internal
- Function multi_pairing_internal
- Function multi_scalar_mul_internal
- Function neg_internal
- Function one_internal
- Function order_internal
- Function pairing_internal
- Function scalar_mul_internal
- Function serialize_internal
- Function sqr_internal
- Function sub_internal
- Function upcast_internal
- Function zero_internal

use 0x1::error;
use 0x1::features;
use 0x1::option;

Struct `Element`

This struct represents an element of a structure S.

struct Element<S> has copy, drop

Fields

handle: u64

Constants

const E_NON_EQUAL_LENGTHS: u64 = 2;

const E_NOT_IMPLEMENTED: u64 = 1;

const E_TOO_MUCH_MEMORY_USED: u64 = 3;

Function `eq`

Check if x == y for elements x and y of a structure S.

public fun eq<S>(x: &crypto_algebra::Element<S>, y: &crypto_algebra::Element<S>): bool

Implementation

public fun eq<S>(x: &Element<S>, y: &Element<S>): bool {
    abort_unless_cryptography_algebra_natives_enabled();
    eq_internal<S>(x.handle, y.handle)
}

Function `from_u64`

Convert a u64 to an element of a structure S.

public fun from_u64<S>(value: u64): crypto_algebra::Element<S>

Implementation

public fun from_u64<S>(value: u64): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: from_u64_internal<S>(value)
    }
}

Function `zero`

Return the additive identity of field S, or the identity of group S.

public fun zero<S>(): crypto_algebra::Element<S>

Implementation

public fun zero<S>(): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: zero_internal<S>()
    }
}

Function `one`

Return the multiplicative identity of field S, or a fixed generator of group S.

public fun one<S>(): crypto_algebra::Element<S>

Implementation

public fun one<S>(): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: one_internal<S>()
    }
}

Function `neg`

Compute -x for an element x of a structure S.

public fun neg<S>(x: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun neg<S>(x: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: neg_internal<S>(x.handle)
    }
}

Function `add`

Compute x + y for elements x and y of structure S.

public fun add<S>(x: &crypto_algebra::Element<S>, y: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun add<S>(x: &Element<S>, y: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: add_internal<S>(x.handle, y.handle)
    }
}

Function `sub`

Compute x - y for elements x and y of a structure S.

public fun sub<S>(x: &crypto_algebra::Element<S>, y: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun sub<S>(x: &Element<S>, y: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: sub_internal<S>(x.handle, y.handle)
    }
}

Function `mul`

Compute x * y for elements x and y of a structure S.

public fun mul<S>(x: &crypto_algebra::Element<S>, y: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun mul<S>(x: &Element<S>, y: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: mul_internal<S>(x.handle, y.handle)
    }
}

Function `div`

Try computing x / y for elements x and y of a structure S. Return none if y does not have a multiplicative inverse in the structure S (e.g., when S is a field, and y is zero).

public fun div<S>(x: &crypto_algebra::Element<S>, y: &crypto_algebra::Element<S>): option::Option<crypto_algebra::Element<S>>

Implementation

public fun div<S>(x: &Element<S>, y: &Element<S>): Option<Element<S>> {
    abort_unless_cryptography_algebra_natives_enabled();
    let (succ, handle) = div_internal<S>(x.handle, y.handle);
    if (succ) {
        some(Element<S> { handle })
    } else {
        none()
    }
}

Function `sqr`

Compute x^2 for an element x of a structure S. Faster and cheaper than mul(x, x).

public fun sqr<S>(x: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun sqr<S>(x: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: sqr_internal<S>(x.handle)
    }
}

Function `inv`

Try computing x^(-1) for an element x of a structure S. Return none if x does not have a multiplicative inverse in the structure S (e.g., when S is a field, and x is zero).

public fun inv<S>(x: &crypto_algebra::Element<S>): option::Option<crypto_algebra::Element<S>>

Implementation

public fun inv<S>(x: &Element<S>): Option<Element<S>> {
    abort_unless_cryptography_algebra_natives_enabled();
    let (succeeded, handle) = inv_internal<S>(x.handle);
    if (succeeded) {
        let scalar = Element<S> { handle };
        some(scalar)
    } else {
        none()
    }
}

Function `double`

Compute 2*P for an element P of a structure S. Faster and cheaper than add(P, P).

public fun double<S>(element_p: &crypto_algebra::Element<S>): crypto_algebra::Element<S>

Implementation

public fun double<S>(element_p: &Element<S>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<S> {
        handle: double_internal<S>(element_p.handle)
    }
}

Function `multi_scalar_mul`

Compute k[0]*P[0]+…+k[n-1]*P[n-1], where P[] are n elements of group G represented by parameter elements, and k[] are n elements of the scalarfield S of group G represented by parameter scalars.

Abort with code std::error::invalid_argument(E_NON_EQUAL_LENGTHS) if the sizes of elements and scalars do not match.

public fun multi_scalar_mul<G, S>(elements: &vector<crypto_algebra::Element<G>>, scalars: &vector<crypto_algebra::Element<S>>): crypto_algebra::Element<G>

Implementation

public fun multi_scalar_mul<G, S>(elements: &vector<Element<G>>, scalars: &vector<Element<S>>): Element<G> {
    abort_unless_cryptography_algebra_natives_enabled();
    let element_handles = handles_from_elements(elements);
    let scalar_handles = handles_from_elements(scalars);
    Element<G> {
        handle: multi_scalar_mul_internal<G, S>(element_handles, scalar_handles)
    }
}

Function `scalar_mul`

Compute k*P, where P is an element of a group G and k is an element of the scalar field S associated to the group G.

public fun scalar_mul<G, S>(element_p: &crypto_algebra::Element<G>, scalar_k: &crypto_algebra::Element<S>): crypto_algebra::Element<G>

Implementation

public fun scalar_mul<G, S>(element_p: &Element<G>, scalar_k: &Element<S>): Element<G> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<G> {
        handle: scalar_mul_internal<G, S>(element_p.handle, scalar_k.handle)
    }
}

Function `multi_pairing`

Efficiently compute e(P[0],Q[0])+…+e(P[n-1],Q[n-1]), where e: (G1,G2) -> (Gt) is the pairing function from groups (G1,G2) to group Gt, P[] are n elements of group G1 represented by parameter g1_elements, and Q[] are n elements of group G2 represented by parameter g2_elements.

Abort with code std::error::invalid_argument(E_NON_EQUAL_LENGTHS) if the sizes of g1_elements and g2_elements do not match.

NOTE: we are viewing the target group Gt of the pairing as an additive group, rather than a multiplicative one (which is typically the case).

public fun multi_pairing<G1, G2, Gt>(g1_elements: &vector<crypto_algebra::Element<G1>>, g2_elements: &vector<crypto_algebra::Element<G2>>): crypto_algebra::Element<Gt>

Implementation

public fun multi_pairing<G1,G2,Gt>(g1_elements: &vector<Element<G1>>, g2_elements: &vector<Element<G2>>): Element<Gt> {
    abort_unless_cryptography_algebra_natives_enabled();
    let g1_handles = handles_from_elements(g1_elements);
    let g2_handles = handles_from_elements(g2_elements);
    Element<Gt> {
        handle: multi_pairing_internal<G1,G2,Gt>(g1_handles, g2_handles)
    }
}

Function `pairing`

Compute the pairing function (a.k.a., bilinear map) on a G1 element and a G2 element. Return an element in the target group Gt.

public fun pairing<G1, G2, Gt>(element_1: &crypto_algebra::Element<G1>, element_2: &crypto_algebra::Element<G2>): crypto_algebra::Element<Gt>

Implementation

public fun pairing<G1,G2,Gt>(element_1: &Element<G1>, element_2: &Element<G2>): Element<Gt> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<Gt> {
        handle: pairing_internal<G1,G2,Gt>(element_1.handle, element_2.handle)
    }
}

Function `deserialize`

Try deserializing a byte array to an element of an algebraic structure S using a given serialization format F. Return none if the deserialization failed.

public fun deserialize<S, F>(bytes: &vector<u8>): option::Option<crypto_algebra::Element<S>>

Implementation

public fun deserialize<S, F>(bytes: &vector<u8>): Option<Element<S>> {
    abort_unless_cryptography_algebra_natives_enabled();
    let (succeeded, handle) = deserialize_internal<S, F>(bytes);
    if (succeeded) {
        some(Element<S> { handle })
    } else {
        none()
    }
}

Function `serialize`

Serialize an element of an algebraic structure S to a byte array using a given serialization format F.

public fun serialize<S, F>(element: &crypto_algebra::Element<S>): vector<u8>

Implementation

public fun serialize<S, F>(element: &Element<S>): vector<u8> {
    abort_unless_cryptography_algebra_natives_enabled();
    serialize_internal<S, F>(element.handle)
}

Function `order`

Get the order of structure S, a big integer little-endian encoded as a byte array.

public fun order<S>(): vector<u8>

Implementation

public fun order<S>(): vector<u8> {
    abort_unless_cryptography_algebra_natives_enabled();
    order_internal<S>()
}

Function `upcast`

Cast an element of a structure S to a parent structure L.

public fun upcast<S, L>(element: &crypto_algebra::Element<S>): crypto_algebra::Element<L>

Implementation

public fun upcast<S,L>(element: &Element<S>): Element<L> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element<L> {
        handle: upcast_internal<S,L>(element.handle)
    }
}

Function `downcast`

Try casting an element x of a structure L to a sub-structure S. Return none if x is not a member of S.

NOTE: Membership check in S is performed inside, which can be expensive, depending on the structures L and S.

public fun downcast<L, S>(element_x: &crypto_algebra::Element<L>): option::Option<crypto_algebra::Element<S>>

Implementation

public fun downcast<L,S>(element_x: &Element<L>): Option<Element<S>> {
    abort_unless_cryptography_algebra_natives_enabled();
    let (succ, new_handle) = downcast_internal<L,S>(element_x.handle);
    if (succ) {
        some(Element<S> { handle: new_handle })
    } else {
        none()
    }
}

Function `hash_to`

Hash an arbitrary-length byte array msg into structure S with a domain separation tag dst using the given hash-to-structure suite H.

NOTE: some hashing methods do not accept a dst and will abort if a non-empty one is provided.

public fun hash_to<S, H>(dst: &vector<u8>, msg: &vector<u8>): crypto_algebra::Element<S>

Implementation

public fun hash_to<S, H>(dst: &vector<u8>, msg: &vector<u8>): Element<S> {
    abort_unless_cryptography_algebra_natives_enabled();
    Element {
        handle: hash_to_internal<S, H>(dst, msg)
    }
}

Function `abort_unless_cryptography_algebra_natives_enabled`

fun abort_unless_cryptography_algebra_natives_enabled()

Implementation

fun abort_unless_cryptography_algebra_natives_enabled() {
    if (features::cryptography_algebra_enabled()) return;
    abort(std::error::not_implemented(0))
}

Function `handles_from_elements`

fun handles_from_elements<S>(elements: &vector<crypto_algebra::Element<S>>): vector<u64>

Implementation

fun handles_from_elements<S>(elements: &vector<Element<S>>): vector<u64> {
    let num_elements = elements.length();
    let element_handles = std::vector::empty();
    let i = 0;
    while ({
        spec {
            invariant len(element_handles) == i;
            invariant forall k in 0..i: element_handles[k] == elements[k].handle;
        };
        i < num_elements
    }) {
        element_handles.push_back(elements[i].handle);
        i += 1;
    };
    element_handles
}

Function `add_internal`

fun add_internal<S>(handle_1: u64, handle_2: u64): u64

Implementation

native fun add_internal<S>(handle_1: u64, handle_2: u64): u64;

Function `deserialize_internal`

fun deserialize_internal<S, F>(bytes: &vector<u8>): (bool, u64)

Implementation

native fun deserialize_internal<S, F>(bytes: &vector<u8>): (bool, u64);

Function `div_internal`

fun div_internal<F>(handle_1: u64, handle_2: u64): (bool, u64)

Implementation

native fun div_internal<F>(handle_1: u64, handle_2: u64): (bool, u64);

Function `double_internal`

fun double_internal<G>(element_handle: u64): u64

Implementation

native fun double_internal<G>(element_handle: u64): u64;

Function `downcast_internal`

fun downcast_internal<L, S>(handle: u64): (bool, u64)

Implementation

native fun downcast_internal<L,S>(handle: u64): (bool, u64);

Function `from_u64_internal`

fun from_u64_internal<S>(value: u64): u64

Implementation

native fun from_u64_internal<S>(value: u64): u64;

Function `eq_internal`

fun eq_internal<S>(handle_1: u64, handle_2: u64): bool

Implementation

native fun eq_internal<S>(handle_1: u64, handle_2: u64): bool;

Function `hash_to_internal`

fun hash_to_internal<S, H>(dst: &vector<u8>, bytes: &vector<u8>): u64

Implementation

native fun hash_to_internal<S, H>(dst: &vector<u8>, bytes: &vector<u8>): u64;

Function `inv_internal`

fun inv_internal<F>(handle: u64): (bool, u64)

Implementation

native fun inv_internal<F>(handle: u64): (bool, u64);

Function `mul_internal`

fun mul_internal<F>(handle_1: u64, handle_2: u64): u64

Implementation

native fun mul_internal<F>(handle_1: u64, handle_2: u64): u64;

Function `multi_pairing_internal`

fun multi_pairing_internal<G1, G2, Gt>(g1_handles: vector<u64>, g2_handles: vector<u64>): u64

Implementation

native fun multi_pairing_internal<G1,G2,Gt>(g1_handles: vector<u64>, g2_handles: vector<u64>): u64;

Function `multi_scalar_mul_internal`

fun multi_scalar_mul_internal<G, S>(element_handles: vector<u64>, scalar_handles: vector<u64>): u64

Implementation

native fun multi_scalar_mul_internal<G, S>(element_handles: vector<u64>, scalar_handles: vector<u64>): u64;

Function `neg_internal`

fun neg_internal<F>(handle: u64): u64

Implementation

native fun neg_internal<F>(handle: u64): u64;

Function `one_internal`

fun one_internal<S>(): u64

Implementation

native fun one_internal<S>(): u64;

Function `order_internal`

fun order_internal<G>(): vector<u8>

Implementation

native fun order_internal<G>(): vector<u8>;

Function `pairing_internal`

fun pairing_internal<G1, G2, Gt>(g1_handle: u64, g2_handle: u64): u64

Implementation

native fun pairing_internal<G1,G2,Gt>(g1_handle: u64, g2_handle: u64): u64;

Function `scalar_mul_internal`

fun scalar_mul_internal<G, S>(element_handle: u64, scalar_handle: u64): u64

Implementation

native fun scalar_mul_internal<G, S>(element_handle: u64, scalar_handle: u64): u64;

Function `serialize_internal`

fun serialize_internal<S, F>(handle: u64): vector<u8>

Implementation

native fun serialize_internal<S, F>(handle: u64): vector<u8>;

Function `sqr_internal`

fun sqr_internal<G>(handle: u64): u64

Implementation

native fun sqr_internal<G>(handle: u64): u64;

Function `sub_internal`

fun sub_internal<G>(handle_1: u64, handle_2: u64): u64

Implementation

native fun sub_internal<G>(handle_1: u64, handle_2: u64): u64;

Function `upcast_internal`

fun upcast_internal<S, L>(handle: u64): u64

Implementation

native fun upcast_internal<S,L>(handle: u64): u64;

Function `zero_internal`

fun zero_internal<S>(): u64

Implementation

native fun zero_internal<S>(): u64;

Specification

Function `handles_from_elements`

fun handles_from_elements<S>(elements: &vector<crypto_algebra::Element<S>>): vector<u64>

aborts_if false;
ensures forall i in 0..len(elements): result[i] == elements[i].handle;

Function `add_internal`

fun add_internal<S>(handle_1: u64, handle_2: u64): u64

pragma opaque;

Function `deserialize_internal`

fun deserialize_internal<S, F>(bytes: &vector<u8>): (bool, u64)

pragma opaque;

Function `div_internal`

fun div_internal<F>(handle_1: u64, handle_2: u64): (bool, u64)

pragma opaque;

Function `double_internal`

fun double_internal<G>(element_handle: u64): u64

pragma opaque;

Function `downcast_internal`

fun downcast_internal<L, S>(handle: u64): (bool, u64)

pragma opaque;

Function `from_u64_internal`

fun from_u64_internal<S>(value: u64): u64

pragma opaque;

Function `eq_internal`

fun eq_internal<S>(handle_1: u64, handle_2: u64): bool

pragma opaque;

Function `hash_to_internal`

fun hash_to_internal<S, H>(dst: &vector<u8>, bytes: &vector<u8>): u64

pragma opaque;

Function `inv_internal`

fun inv_internal<F>(handle: u64): (bool, u64)

pragma opaque;

Function `mul_internal`

fun mul_internal<F>(handle_1: u64, handle_2: u64): u64

pragma opaque;

Function `multi_pairing_internal`

fun multi_pairing_internal<G1, G2, Gt>(g1_handles: vector<u64>, g2_handles: vector<u64>): u64

pragma opaque;

Function `multi_scalar_mul_internal`

fun multi_scalar_mul_internal<G, S>(element_handles: vector<u64>, scalar_handles: vector<u64>): u64

pragma opaque;

Function `neg_internal`

fun neg_internal<F>(handle: u64): u64

pragma opaque;

Function `one_internal`

fun one_internal<S>(): u64

pragma opaque;

Function `order_internal`

fun order_internal<G>(): vector<u8>

pragma opaque;

Function `pairing_internal`

fun pairing_internal<G1, G2, Gt>(g1_handle: u64, g2_handle: u64): u64

pragma opaque;

Function `scalar_mul_internal`

fun scalar_mul_internal<G, S>(element_handle: u64, scalar_handle: u64): u64

pragma opaque;

Function `serialize_internal`

fun serialize_internal<S, F>(handle: u64): vector<u8>

pragma opaque;

Function `sqr_internal`

fun sqr_internal<G>(handle: u64): u64

pragma opaque;

Function `sub_internal`

fun sub_internal<G>(handle_1: u64, handle_2: u64): u64

pragma opaque;

Function `upcast_internal`

fun upcast_internal<S, L>(handle: u64): u64

pragma opaque;

Function `zero_internal`

fun zero_internal<S>(): u64

pragma opaque;

Keyboard shortcuts

The Aptos Framework Book