ethereum.crypto.alt_bn128

The alt_bn128 curve ^^^^^^^^^^^^^^^^^^^

ALT_BN128_PRIME

8
ALT_BN128_PRIME = 21888242871839275222246405745257275088696311157297823662689037894645226208583

ALT_BN128_CURVE_ORDER

9
ALT_BN128_CURVE_ORDER = 21888242871839275222246405745257275088548364400416034343698204186575808495617

ATE_PAIRING_COUNT

10
ATE_PAIRING_COUNT = 29793968203157093289

ATE_PAIRING_COUNT_BITS

11
ATE_PAIRING_COUNT_BITS = 63

BNF

The prime field over which the alt_bn128 curve is defined.

class BNF:

PRIME

19
    PRIME = ALT_BN128_PRIME

BNP

The alt_bn128 curve.

class BNP:

FIELD

27
    FIELD = BNF

A

28
    A = BNF(0)

B

29
    B = BNF(3)

BNF2

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

class BNF2:

PRIME

37
    PRIME = ALT_BN128_PRIME

MODULUS

38
    MODULUS = (1, 0)

i

40
    i: "BNF2"

i_plus_9

41
    i_plus_9: "BNF2"

BNF2.FROBENIUS_COEFFICIENTS

autoapi_noindex

44
BNF2.FROBENIUS_COEFFICIENTS = BNF2.calculate_frobenius_coefficients()

BNF2.i

autoapi_noindex

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

BNF2.i_plus_9

autoapi_noindex

50
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:

FIELD

61
    FIELD = BNF2

A

62
    A = BNF2.zero()

B

63
    B = BNF2.from_int(3) / (BNF2.i + BNF2.from_int(9))

BNF12

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

class BNF12:

PRIME

71
    PRIME = ALT_BN128_PRIME

MODULUS

72
    MODULUS = (82, 0, 0, 0, 0, 0, -18, 0, 0, 0, 0, 0)

w

74
    w: "BNF12"

i_plus_9

75
    i_plus_9: "BNF12"

__mul__

Multiplication special cased for BNF12.

def __mul__(​self: "BNF12", ​​right: "BNF12"​) -> "BNF12":
78
        """
79
        Multiplication special cased for BNF12.
80
        """
81
        mul = [0] * 23
82
83
        for i in range(12):
84
            for j in range(12):
85
                mul[i + j] += self[i] * right[j]
86
87
        for i in range(22, 11, -1):
88
            mul[i - 6] -= mul[i] * (-18)
89
            mul[i - 12] -= mul[i] * 82
90
91
        return BNF12.__new__(
92
            BNF12,
93
            mul[:12],
94
        )

BNF12.FROBENIUS_COEFFICIENTS

autoapi_noindex

97
BNF12.FROBENIUS_COEFFICIENTS = BNF12.calculate_frobenius_coefficients()

BNF12.w

autoapi_noindex

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

BNF12.i_plus_9

autoapi_noindex

103
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:

FIELD

114
    FIELD = BNF12

A

115
    A = BNF12.zero()

B

116
    B = BNF12.from_int(3)

bnf2_to_bnf12

Lift a field element in BNF2 to BNF12.

def bnf2_to_bnf12(​x: BNF2​) -> BNF12:
120
    """
121
    Lift a field element in `BNF2` to `BNF12`.
122
    """
123
    return BNF12.from_int(x[0]) + BNF12.from_int(x[1]) * (
124
        BNF12.i_plus_9 - BNF12.from_int(9)
125
    )

bnp_to_bnp12

Lift a point from BNP to BNP12.

def bnp_to_bnp12(​p: BNP​) -> BNP12:
129
    """
130
    Lift a point from `BNP` to `BNP12`.
131
    """
132
    return BNP12(BNF12.from_int(int(p.x)), BNF12.from_int(int(p.y)))

twist

Apply to twist to change variables from the curve BNP2 to BNP12.

def twist(​p: BNP2​) -> BNP12:
136
    """
137
    Apply to twist to change variables from the curve `BNP2` to `BNP12`.
138
    """
139
    return BNP12(
140
        bnf2_to_bnf12(p.x) * (BNF12.w**2),
141
        bnf2_to_bnf12(p.y) * (BNF12.w**3),
142
    )

linefunc

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:
146
    """
147
    Evaluate the function defining the line between points `p1` and `p2` at the
148
    point `t`. The mathematical significance of this function is that is has
149
    divisor `(p1) + (p2) + (p1 + p2) - 3(O)`.
150
151
    Note: Abstract mathematical presentations of Miller's algorithm often
152
    specify the divisor `(p1) + (p2) - (p1 + p2) - (O)`. This turns out not to
153
    matter.
154
    """
155
    if p1.x != p2.x:
156
        lam = (p2.y - p1.y) / (p2.x - p1.x)
157
        return lam * (t.x - p1.x) - (t.y - p1.y)
158
    elif p1.y == p2.y:
159
        lam = BNF12.from_int(3) * p1.x**2 / (BNF12.from_int(2) * p1.y)
160
        return lam * (t.x - p1.x) - (t.y - p1.y)
161
    else:
162
        return t.x - p1.x

miller_loop

The core of the pairing algorithm.

def miller_loop(​q: BNP12, ​​p: BNP12​) -> BNF12:
166
    """
167
    The core of the pairing algorithm.
168
    """
169
    if p == BNP12.point_at_infinity() or q == BNP12.point_at_infinity():
170
        return BNF12.from_int(1)
171
    r = q
172
    f = BNF12.from_int(1)
173
    for i in range(ATE_PAIRING_COUNT_BITS, -1, -1):
174
        f = f * f * linefunc(r, r, p)
175
        r = r.double()
176
        if (ATE_PAIRING_COUNT - 1) & (2**i):
177
            f = f * linefunc(r, q, p)
178
            r = r + q
179
    assert r == q.mul_by(ATE_PAIRING_COUNT - 1)
180
181
    q1 = BNP12(q.x.frobenius(), q.y.frobenius())
182
    nq2 = BNP12(q1.x.frobenius(), -q1.y.frobenius())
183
184
    f = f * linefunc(r, q1, p)
185
    r = r + q1
186
    f = f * linefunc(r, nq2, p)
187
188
    return f ** ((ALT_BN128_PRIME**12 - 1) // ALT_BN128_CURVE_ORDER)

pairing

Compute the pairing of q and p.

def pairing(​q: BNP2, ​​p: BNP​) -> BNF12:
192
    """
193
    Compute the pairing of `q` and `p`.
194
    """
195
    return miller_loop(twist(q), bnp_to_bnp12(p))