The alt_bn128 curve

Module Contents

Classes

`BNF`	The prime field over which the alt_bn128 curve is defined.
`BNP`	The alt_bn128 curve.
`BNF2`	BNF extended with a square root of 1 (i).
`BNP2`	A twist of BNP. This is actually the same curve as BNP under a change
`BNF12`	BNF2 extended by adding a 6th root of 9 + i called w (omega).
`BNP12`	The same curve as BNP, but defined over the larger field. This curve has

Functions

`bnf2_to_bnf12`	Lift a field element in BNF2 to BNF12.
`bnp_to_bnp12`	Lift a point from BNP to BNP12.
`twist`	Apply to twist to change variables from the curve BNP2 to BNP12.
`linefunc`	Evaluate the function defining the line between points p1 and p2 at the
`miller_loop`	The core of the pairing algorithm.
`pairing`	Compute the pairing of q and p.

Attributes

`ALT_BN128_PRIME`
`ALT_BN128_CURVE_ORDER`
`ATE_PAIRING_COUNT`
`ATE_PAIRING_COUNT_BITS`

Module Details

ALT_BN128_PRIME

ALT_BN128_PRIME

ALT_BN128_PRIME = 21888242871839275222246405745257275088696311157297823662689037894645226208583  # noqa: E501

ALT_BN128_CURVE_ORDER

ALT_BN128_CURVE_ORDER

ALT_BN128_CURVE_ORDER = 21888242871839275222246405745257275088548364400416034343698204186575808495617  # noqa: E501

ATE_PAIRING_COUNT

ATE_PAIRING_COUNT

ATE_PAIRING_COUNT = 29793968203157093289

ATE_PAIRING_COUNT_BITS

ATE_PAIRING_COUNT_BITS

ATE_PAIRING_COUNT_BITS = 63

BNF

The prime field over which the alt_bn128 curve is defined.

class BNF

Bases: ethereum.crypto.finite_field.PrimeField

PRIME

BNP

The alt_bn128 curve.

class BNP(x: F, y: F)

Bases: ethereum.crypto.elliptic_curve.EllipticCurve

FIELD

A

B

BNF2

BNF extended with a square root of 1 (i).

class BNF2

Bases: ethereum.crypto.finite_field.GaloisField

PRIME

MODULUS = [1, 0]

i :BNF2

i_plus_9 :BNF2

FROBENIUS_COEFFICIENTS

BNF2.FROBENIUS_COEFFICIENTS

BNF2.FROBENIUS_COEFFICIENTS = BNF2.calculate_frobenius_coefficients()

i

BNF2.i

BNF2.i = BNF2((0, 1))

i_plus_9

BNF2.i_plus_9

BNF2.i_plus_9 = BNF2((9, 1))

BNP2

A twist of BNP. This is actually the same curve as BNP under a change of variable, but that change of variable is only possible over the larger field BNP12.

class BNP2(x: F, y: F)

Bases: ethereum.crypto.elliptic_curve.EllipticCurve

FIELD

A

B

BNF12

BNF2 extended by adding a 6th root of 9 + i called w (omega).

class BNF12

Bases: ethereum.crypto.finite_field.GaloisField

PRIME

MODULUS

w :BNF12

i_plus_9 :BNF12

__mul__(right: BNF12) → BNF12 : Multiplication special cased for BNF12.

FROBENIUS_COEFFICIENTS

BNF12.FROBENIUS_COEFFICIENTS

BNF12.FROBENIUS_COEFFICIENTS = BNF12.calculate_frobenius_coefficients()

w

BNF12.w

BNF12.w = BNF12((0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))

i_plus_9

BNF12.i_plus_9

BNF12.i_plus_9 = BNF12.w**6

BNP12

The same curve as BNP, but defined over the larger field. This curve has both subgroups of order ALT_BN128_CURVE_ORDER and allows pairings to be computed.

class BNP12(x: F, y: F)

Bases: ethereum.crypto.elliptic_curve.EllipticCurve

FIELD

A

B

bnf2_to_bnf12

bnf2_to_bnf12(x: BNF2) → BNF12 : Lift a field element in BNF2 to BNF12.

def bnf2_to_bnf12(x: BNF2) -> BNF12:
    return BNF12.from_int(x[0]) + BNF12.from_int(x[1]) * (
        BNF12.i_plus_9 - BNF12.from_int(9)
    )

bnp_to_bnp12

bnp_to_bnp12(p: BNP) → BNP12 : Lift a point from BNP to BNP12.

def bnp_to_bnp12(p: BNP) -> BNP12:
    return BNP12(BNF12.from_int(int(p.x)), BNF12.from_int(int(p.y)))

twist

twist(p: BNP2) → BNP12 : Apply to twist to change variables from the curve BNP2 to BNP12.

def twist(p: BNP2) -> BNP12:
    return BNP12(
        bnf2_to_bnf12(p.x) * (BNF12.w**2),
        bnf2_to_bnf12(p.y) * (BNF12.w**3),
    )

linefunc

linefunc(p1: BNP12, p2: BNP12, t: BNP12) → BNF12 

Evaluate the function defining the line between points p1 and p2 at the point t. The mathematical significance of this function is that is has divisor (p1) + (p2) + (p1 + p2) - 3(O).

Note: Abstract mathematical presentations of Miller’s algorithm often specify the divisor (p1) + (p2) - (p1 + p2) - (O). This turns out not to matter.

def linefunc(p1: BNP12, p2: BNP12, t: BNP12) -> BNF12:
    if p1.x != p2.x:
        lam = (p2.y - p1.y) / (p2.x - p1.x)
        return lam * (t.x - p1.x) - (t.y - p1.y)
    elif p1.y == p2.y:
        lam = BNF12.from_int(3) * p1.x**2 / (BNF12.from_int(2) * p1.y)
        return lam * (t.x - p1.x) - (t.y - p1.y)
    else:
        return t.x - p1.x

miller_loop

miller_loop(q: BNP12, p: BNP12) → BNF12 : The core of the pairing algorithm.

def miller_loop(q: BNP12, p: BNP12) -> BNF12:
    if p == BNP12.point_at_infinity() or q == BNP12.point_at_infinity():
        return BNF12.from_int(1)
    r = q
    f = BNF12.from_int(1)
    for i in range(ATE_PAIRING_COUNT_BITS, -1, -1):
        f = f * f * linefunc(r, r, p)
        r = r.double()
        if (ATE_PAIRING_COUNT - 1) & (2**i):
            f = f * linefunc(r, q, p)
            r = r + q
    assert r == q.mul_by(ATE_PAIRING_COUNT - 1)

    q1 = BNP12(q.x.frobenius(), q.y.frobenius())
    nq2 = BNP12(q1.x.frobenius(), -q1.y.frobenius())

    f = f * linefunc(r, q1, p)
    r = r + q1
    f = f * linefunc(r, nq2, p)

    return f ** ((ALT_BN128_PRIME**12 - 1) // ALT_BN128_CURVE_ORDER)

pairing

pairing(q: BNP2, p: BNP) → BNF12 : Compute the pairing of q and p.

def pairing(q: BNP2, p: BNP) -> BNF12:
    return miller_loop(twist(q), bnp_to_bnp12(p))