aip | title | author | discussions-to (*optional) | Status | type | created |
---|---|---|---|---|---|---|
20 |
Generic Cryptography Algebra and BLS12-381 Implementation |
zhoujun-ma, alin |
Accepted |
Standard (Framework) |
2023/03/15 |
This AIP proposes the support of generic cryptography algebra operations in Aptos standard library.
The initial list of the supported generic operations includes group/field element serialization/deserialization, basic arithmetic, pairing, hash-to-structure, casting.
The initial list of supported algebraic structures includes groups/fields used in BLS12-381, a popular pairing-friendly curve as described here.
Either the operation list or the structure list can be extended by future AIPs.
Algebraic structures are fundamental building blocks for many cryptographic schemes, but also hard to implement efficiently in pure Move. This change should allow Move developers to implement generic constructions of those schemes, then get different instantiations by only switching the type parameter(s).
For example, if BLS12-381 groups and BN254 groups are supported, one can implement a generic Groth16 proof verifier construction, then be able to use both BLS12-381-based Groth16 proof verifier and BN254-based Groth16 proof verifier.
BLS12-381-based Groth16 proof verifier has been implemented this way as part of the reference implementation.
An alternative non-generic approach is to expose instantiated schemes directly in aptos_stdlib.
For example, we can define a Groth16 proof verification function
0x1::groth16_<curve>::verify_proof(vk, proof, public_inputs): bool
for every pairing-friendly elliptic curve <curve>
.
For ECDSA signatures which require a hash function and a group, we can define
0x1::ecdsa_<hash>_<group>::verify_signature(pk, msg, sig):bool
for each pair of proper hash function <hash>
and group <group>
.
Compared with the proposed approach, the alternative approach saves the work of constructing the schemes for Move developers. However, the size of aptos_stdlib can multiply too fast in the future. Furthermore, the non-generic approach is not scalable from a development standpoint: a new native is needed for every combination of cryptosystem and its underlying algebraic structure (e.g., elliptic curve).
To keep the Aptos stdlib concise while still covering as many use cases as possible, the proposed generic approach should be chosen over the alternative approach.
On the backend, the native functions for the generic API implement dynamic dispatch:
they act based on the given marker types.
E.g., in the context of BLS12-381,
the native for add<S>(x: &Element<S>, y:&Element<S>): Element<S>
will calculate x*y
if S
is Gt
that represents the multiplicative subgroup Gt
in BLS12-381,
or x+y
if S
is the scalar field Fr
.
This is required by the generic API design.
Module aptos_std::crypto_algebra
is designed to have the following definitions.
- A generic struct
Element<S>
that represents an element of algebraic structureS
. - Generic functions that represent group/field operations.
Below is the full specification in pseudo-Move.
module aptos_std::crypto_algebra {
/// An element of the group `G`.
struct Element<S> has copy, drop;
/// Check if `x == y` for elements `x` and `y` of an algebraic structure `S`.
public fun eq<S>(x: &Element<S>, y: &Element<S>): bool;
/// Convert a u64 to an element of an algebraic structure `S`.
public fun from_u64<S>(value: u64): Element<S>;
/// Return the additive identity of field `S`, or the identity of group `S`.
public fun zero<S>(): Element<S>;
/// Return the multiplicative identity of field `S`, or a fixed generator of group `S`.
public fun one<S>(): Element<S>;
/// Compute `-x` for an element `x` of a structure `S`.
public fun neg<S>(x: &Element<S>): Element<S>;
/// Compute `x + y` for elements `x` and `y` of a structure `S`.
public fun add<S>(x: &Element<S>, y: &Element<S>): Element<S>;
/// Compute `x - y` for elements `x` and `y` of a structure `S`.
public fun sub<S>(x: &Element<S>, y: &Element<S>): Element<S>;
/// 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: &Element<S>): Option<Element<S>>;
/// Compute `x * y` for elements `x` and `y` of a structure `S`.
public fun mul<S>(x: &Element<S>, y: &Element<S>): Element<S>;
/// 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: &Element<S>, y: &Element<S>): Option<Element<S>>;
/// Compute `x^2` for an element `x` of a structure `S`. Faster and cheaper than `mul(x, x)`.
public fun sqr<S>(x: &Element<S>): Element<S>;
/// Compute `2*P` for an element `P` of a structure `S`. Faster and cheaper than `add(P, P)`.
public fun double<G>(element_p: &Element<G>): Element<G>;
/// Compute `k*P`, where `P` is an element of a group `G` and `k` is an element of the scalar field `S` of group `G`.
public fun scalar_mul<G, S>(element_p: &Element<G>, scalar_k: &Element<S>): Element<G>;
/// 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<Element<G>>, scalars: &vector<Element<S>>): Element<G>;
/// Efficiently compute `e(P[0],Q[0])+...+e(P[n-1],Q[n-1])`,
/// where `e: (G1,G2) -> (Gt)` is a pre-compiled 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.
public fun multi_pairing<G1,G2,Gt>(g1_elements: &vector<Element<G1>>, g2_elements: &vector<Element<G2>>): Element<Gt>;
/// Compute a pre-compiled pairing function (a.k.a., bilinear map) on `element_1` and `element_2`.
/// Return an element in the target group `Gt`.
public fun pairing<G1,G2,Gt>(element_1: &Element<G1>, element_2: &Element<G2>): Element<Gt>;
/// 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<Element<S>>;
/// Serialize an element of an algebraic structure `S` to a byte array using a given serialization format `F`.
public fun serialize<S, F>(element: &Element<S>): vector<u8>;
/// Get the order of structure `S`, a big integer little-endian encoded as a byte array.
public fun order<G>(): vector<u8>;
/// Cast an element of a structure `S` to a super-structure `L`.
public fun upcast<S,L>(element: &Element<S>): Element<L>;
/// 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 is performed inside, which can be expensive, depending on the structures `L` and `S`.
public fun downcast<L,S>(element_x: &Element<L>): Option<Element<S>>;
/// Hash an arbitrary-length byte array `msg` into structure `S` with a domain separation tag `dst`
/// using the given hash-to-structure suite `H`.
public fun hash_to<St, Su>(dst: &vector<u8>, msg: &vector<u8>): Element<St>;
#[test_only]
/// Generate a random element of an algebraic structure `S`.
public fun rand_insecure<S>(): Element<S>;
In general, every structure implements basic operations like (de)serialization, equality check, random sampling.
For example, A group may also implement the following operations. (Additive notions are used.)
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 basic group operation.sub()
for group element subtraction.double()
for efficient group element doubling.scalar_mul()
for group scalar multiplication.multi_scalar_mul()
for efficient group multi-scalar multiplication.hash_to()
for hash-to-group.
As another example, a field may also implement the following operations.
order()
for getting the field order.zero()
for the field additive identity.one()
for 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.
Similarly, for 3 groups G1
, G2
, Gt
that admit a bilinear map, pairing<G1, G2, Gt>()
and multi_pairing<G1, G2, Gt>()
may be implemented.
For a subset/superset relationship between 2 structures, upcast()
and downcast()
may be implemented.
E.g., in BLS12-381 Gt
is a multiplicative subgroup from Fq12
so upcasting from Gt
to Fq12
and downcasting from Fq12
to Gt
can be supported.
Some groups share the same group order, and an ergonomic design for this is to allow multiple groups to share the same scalar field (mainly for the purpose of scalar multiplication), if they have the same order.
In other words, the following should be supported.
// algebra.move
pub fun scalar_mul<G,S>(element: &Element<G>, scalar: &Scalar<S>)...
// user_contract.move
**let k: Scalar<ScalarForBx> = somehow_get_k();**
let p1 = one<GroupB1>();
let p2 = one<GroupB2>();
let q1 = scalar_mul<GroupB1, ScalarForBx>(&p1, &k);
let q2 = scalar_mul<GroupB2, ScalarForBx>(&p2, &k);
There is currently no easy way to ensure type safety for the generic operations.
E.g., pairing<A,B,C>(a,b,c)
can compile even if groups A
, B
and C
do not admin a pairing.
Therefore, the backend should handle the type checks at runtime.
For example, if a group operation that takes 2+ type parameters is invoked with incompatible type parameters, it must abort.
For example, scalar_mul<GroupA, ScalarB>()
where GroupA
and ScalarB
have different orders, will abort with a “not implemented” error.
Invoking operation functions with user-defined types should also abort with a “not implemented” error.
For example, zero<std::option::Option<u64>>()
will abort.
To support a wide-enough variety of BLS12-381 operations using the aptos_std::crypto_algebra
API,
we implement several marker types for the relevant groups of order r
(for G1
, G2
and Gt
) and fields (e.g., Fr
, Fq12
).
We also implement marker types for popular serialization formats and hash-to-group suites.
Below, we describe all possible marker types we could implement for BLS12-381 and mark the ones that we actually implement as "implemented". These, we believe, should be sufficient to support most BLS12-381 applications.
The finite field
A serialization format for Fq
elements,
where an element is represented by a byte array b[]
of size 48 with the least significant byte (LSB) coming first.
A serialization format for Fq
elements,
where an element is represented by a byte array b[]
of size 48 with the most significant byte (MSB) coming first.
The finite field Fq
, constructed as
A serialization format for Fq2
elements,
where an element in the form b[]
of size 96,
which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first:
-
b[0..48]
is$c_0$ serialized usingFormatFqLsb
. -
b[48..96]
is$c_1$ serialized usingFormatFqLsb
.
A serialization format for Fq2
elements,
where an element in the form b[]
of size 96,
which is a concatenation of its coefficients serialized, with the most significant coefficient (MSC) coming first:
-
b[0..48]
is$c_1$ serialized usingFormatFqLsb
. -
b[48..96]
is$c_0$ serialized usingFormatFqLsb
.
The finite field Fq2
, constructed as
A serialization scheme for Fq6
elements,
where an element in the form b[]
of size 288,
which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first:
-
b[0..96]
is$c_0$ serialized usingFormatFq2LscLsb
. -
b[96..192]
is$c_1$ serialized usingFormatFq2LscLsb
. -
b[192..288]
is$c_2$ serialized usingFormatFq2LscLsb
.
The finite field Fq6
, constructed as
A serialization scheme for Fq12
elements,
where an element b[]
of size 576,
which is a concatenation of its coefficients serialized, with the least significant coefficient (LSC) coming first.
-
b[0..288]
is$c_0$ serialized usingFormatFq6LscLsb
. -
b[288..576]
is$c_1$ serialized usingFormatFq6LscLsb
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
A group constructed by the points on the BLS12-381 curve
The group G1Full
with a prime order Fr
is the associated scalar field).
A serialization scheme for G1
elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.
Below is the serialization procedure that takes a G1
element p
and outputs a byte array of size 96.
- Let
(x,y)
be the coordinates ofp
ifp
is on the curve, or(0,0)
otherwise. - Serialize
x
andy
intob_x[]
andb_y[]
respectively usingFormatFqMsb
. - Concatenate
b_x[]
andb_y[]
intob[]
. - If
p
is the point at infinity, set the infinity bit:b[0]: = b[0] | 0x40
. - Return
b[]
.
Below is the deserialization procedure that takes a byte array b[]
and outputs either a G1
element or none.
- If the size of
b[]
is not 96, return none. - Compute the compression flag as
b[0] & 0x80 != 0
. - If the compression flag is true, return none.
- Compute the infinity flag as
b[0] & 0x40 != 0
. - If the infinity flag is set, return the point at infinity.
- Deserialize
[b[0] & 0x1f, b[1], ..., b[47]]
tox
usingFormatFqMsb
. Ifx
is none, return none. - Deserialize
[b[48], ..., b[95]]
toy
usingFormatFqMsb
. Ify
is none, return none. - Check if
(x,y)
is on curveE
. If not, return none. - Check if
(x,y)
is in the subgroup of orderr
. If not, return none. - Return
(x,y)
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
A serialization scheme for G1
elements derived from https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.
Below is the serialization procedure that takes a G1
element p
and outputs a byte array of size 48.
- Let
(x,y)
be the coordinates ofp
ifp
is on the curve, or(0,0)
otherwise. - Serialize
x
intob[]
usingFormatFqMsb
. - Set the compression bit:
b[0] := b[0] | 0x80
. - If
p
is the point at infinity, set the infinity bit:b[0]: = b[0] | 0x40
. - If
y > -y
, set the lexicographical flag:b[0] := b[0] | 0x20
. - Return
b[]
.
Below is the deserialization procedure that takes a byte array b[]
and outputs either a G1
element or none.
- If the size of
b[]
is not 48, return none. - Compute the compression flag as
b[0] & 0x80 != 0
. - If the compression flag is false, return none.
- Compute the infinity flag as
b[0] & 0x40 != 0
. - If the infinity flag is set, return the point at infinity.
- Compute the lexicographical flag as
b[0] & 0x20 != 0
. - Deserialize
[b[0] & 0x1f, b[1], ..., b[47]]
tox
usingFormatFqMsb
. Ifx
is none, return none. - Solve the curve equation with
x
fory
. If no suchy
exists, return none. - Let
y'
bemax(y,-y)
if the lexicographical flag is set, ormin(y,-y)
otherwise. - Check if
(x,y')
is in the subgroup of orderr
. If not, return none. - Return
(x,y')
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
A group constructed by the points on a curve
The group G2Full
with a prime order Fr
is the scalar field).
A serialization scheme for G2
elements derived from
https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.
Below is the serialization procedure that takes a G2
element p
and outputs a byte array of size 192.
- Let
(x,y)
be the coordinates ofp
ifp
is on the curve, or(0,0)
otherwise. - Serialize
x
andy
intob_x[]
andb_y[]
respectively usingFormatFq2MscMsb
. - Concatenate
b_x[]
andb_y[]
intob[]
. - If
p
is the point at infinity, set the infinity bit inb[]
:b[0]: = b[0] | 0x40
. - Return
b[]
.
Below is the deserialization procedure that takes a byte array b[]
and outputs either a G2
element or none.
- If the size of
b[]
is not 192, return none. - Compute the compression flag as
b[0] & 0x80 != 0
. - If the compression flag is true, return none.
- Compute the infinity flag as
b[0] & 0x40 != 0
. - If the infinity flag is set, return the point at infinity.
- Deserialize
[b[0] & 0x1f, ..., b[95]]
tox
usingFormatFq2MscMsb
. Ifx
is none, return none. - Deserialize
[b[96], ..., b[191]]
toy
usingFormatFq2MscMsb
. Ify
is none, return none. - Check if
(x,y)
is on the curveE'
. If not, return none. - Check if
(x,y)
is in the subgroup of orderr
. If not, return none. - Return
(x,y)
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
A serialization scheme for G2
elements derived from
https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-.
Below is the serialization procedure that takes a G2
element p
and outputs a byte array of size 96.
- Let
(x,y)
be the coordinates ofp
ifp
is on the curve, or(0,0)
otherwise. - Serialize
x
intob[]
usingFormatFq2MscMsb
. - Set the compression bit:
b[0] := b[0] | 0x80
. - If
p
is the point at infinity, set the infinity bit:b[0]: = b[0] | 0x40
. - If
y > -y
, set the lexicographical flag:b[0] := b[0] | 0x20
. - Return
b[]
.
Below is the deserialization procedure that takes a byte array b[]
and outputs either a G2
element or none.
- If the size of
b[]
is not 96, return none. - Compute the compression flag as
b[0] & 0x80 != 0
. - If the compression flag is false, return none.
- Compute the infinity flag as
b[0] & 0x40 != 0
. - If the infinity flag is set, return the point at infinity.
- Compute the lexicographical flag as
b[0] & 0x20 != 0
. - Deserialize
[b[0] & 0x1f, b[1], ..., b[95]]
tox
usingFormatFq2MscMsb
. Ifx
is none, return none. - Solve the curve equation with
x
fory
. If no suchy
exists, return none. - Let
y'
bemax(y,-y)
if the lexicographical flag is set, ormin(y,-y)
otherwise. - Check if
(x,y')
is in the subgroup of orderr
. If not, return none. - Return
(x,y')
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
The group Fq12
,
with a prime order Fr
is the scalar field).
The identity of Gt
is 1.
A serialization scheme for Gt
elements.
To serialize, it treats a Gt
element p
as an Fq12
element and serialize it using FormatFq12LscLsb
.
To deserialize, it uses FormatFq12LscLsb
to try deserializing to an Fq12
element then test the membership in Gt
.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0.
The finite field
A serialization format for Fr
elements,
where an element is represented by a byte array b[]
of size 32 with the least significant byte (LSB) coming first.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0, blst-0.3.7.
A serialization scheme for Fr
elements,
where an element is represented by a byte array b[]
of size 32 with the most significant byte (MSB) coming first.
NOTE: other implementation(s) using this format: ark-bls12-381-0.4.0, blst-0.3.7.
The hash-to-curve suite BLS12381G1_XMD:SHA-256_SSWU_RO_
that hashes a byte array into G1
elements.
Full specification is defined in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#name-bls12-381-g1.
The hash-to-curve suite BLS12381G2_XMD:SHA-256_SSWU_RO_
that hashes a byte array into G2
elements.
Full specification is defined in https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#name-bls12-381-g2.
https://github.com/aptos-labs/aptos-core/pull/6550/files
Developing cryptographic schemes, whether in Move or in any other language, is very difficult due to the inherent mathematic complexity of such schemes, as well as the difficulty of using cryptographic libraries securely.
As a result, we caution Move application developers that
implementing cryptographic schemes using crypto_algebra.move
and/or the bls12381_algebra.move
modules will be error prone and could result in vulnerable applications.
That being said, the crypto_algebra.move
and the bls12381_algebra.move
Move modules have been designed with safety in mind.
First, we offer a minimal, hard-to-misuse abstraction for algebraic structures like groups and fields.
Second, our Move modules are type safe (e.g., inversion in a group G returns an Option).
Third, our BLS12-381 implementation always performs prime-order subgroup checks when deserializing group elements, to avoid serious implementation bugs.
The crypto_algebra.move
Move module can be extended to support more structures (e.g., new elliptic curves) and operations (e.g., batch inversion of field elements), This will:
- Allow porting existing generic cryptosystems built on top of this module to new, potentially-faster-or-smaller curves.
- Allow building more complicated cryptographic applications that leverage new operations or new algebraic structures (e.g., rings, hidden-order groups, etc.)
Once the Move language is upgraded with support for some kind of interfaces, it can be use to rewrite the Move side specifications to ensure type safety at compile time.
The change should be available on devnet in April 2023.