Skip to content
Aptos Docs

crypto_algebra - [mainnet]

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.

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

Constants

const E_NON_EQUAL_LENGTHS: u64 = 2;
const E_NOT_IMPLEMENTED: u64 = 1;
const E_TOO_MUCH_MEMORY_USED: u64 = 3;

Structs

Element

This struct represents an element of a structure S.

struct Element<S> has copy, drop
Fields
handle: u64

Functions

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

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

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>()
    }
}

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>()
    }
}

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

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

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

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

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()
    }
}

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

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()
    }
}

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

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> {
    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)
    }
}

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

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

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

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()
    }
}

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

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>()
}

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

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()
    }
}

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

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

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
}

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;

deserialize_internal

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

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

double_internal

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

downcast_internal

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

from_u64_internal

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

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;

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;

inv_internal

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

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;

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;

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;

neg_internal

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

one_internal

fun one_internal<S>(): u64
Implementation 
native fun one_internal<S>(): u64;

order_internal

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

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;

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;

serialize_internal

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

sqr_internal

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

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;

upcast_internal

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

zero_internal

fun zero_internal<S>(): u64
Implementation 
native fun zero_internal<S>(): u64;

Specification

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;

add_internal

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

deserialize_internal

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

div_internal

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

double_internal

fun double_internal<G>(element_handle: u64): u64
pragma opaque;

downcast_internal

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

from_u64_internal

fun from_u64_internal<S>(value: u64): u64
pragma opaque;

eq_internal

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

hash_to_internal

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

inv_internal

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

mul_internal

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

multi_pairing_internal

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

multi_scalar_mul_internal

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

neg_internal

fun neg_internal<F>(handle: u64): u64
pragma opaque;

one_internal

fun one_internal<S>(): u64
pragma opaque;

order_internal

fun order_internal<G>(): vector<u8>
pragma opaque;

pairing_internal

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

scalar_mul_internal

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

serialize_internal

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

sqr_internal

fun sqr_internal<G>(handle: u64): u64
pragma opaque;

sub_internal

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

upcast_internal

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

zero_internal

fun zero_internal<S>(): u64
pragma opaque;