ethereum.crypto.alt_bn128

  1"""
  2The alt_bn128 curve
  3^^^^^^^^^^^^^^^^^^^
  4"""
  5
  6from . import elliptic_curve, finite_field
  7
  8ALT_BN128_PRIME = 21888242871839275222246405745257275088696311157297823662689037894645226208583  # noqa: E501
  9ALT_BN128_CURVE_ORDER = 21888242871839275222246405745257275088548364400416034343698204186575808495617  # noqa: E501
 10ATE_PAIRING_COUNT = 29793968203157093289
 11ATE_PAIRING_COUNT_BITS = 63
 12
 13
 14class BNF(finite_field.PrimeField):
 15    """
 16    The prime field over which the alt_bn128 curve is defined.
 17    """
 18
 19    PRIME = ALT_BN128_PRIME
 20
 21
 22class BNP(elliptic_curve.EllipticCurve):
 23    """
 24    The alt_bn128 curve.
 25    """
 26
 27    FIELD = BNF
 28    A = BNF(0)
 29    B = BNF(3)
 30
 31
 32class BNF2(finite_field.GaloisField):
 33    """
 34    `BNF` extended with a square root of 1 (`i`).
 35    """
 36
 37    PRIME = ALT_BN128_PRIME
 38    MODULUS = (1, 0)
 39
 40    i: "BNF2"
 41    i_plus_9: "BNF2"
 42
 43
 44BNF2.FROBENIUS_COEFFICIENTS = BNF2.calculate_frobenius_coefficients()
 45"""autoapi_noindex"""
 46
 47BNF2.i = BNF2((0, 1))
 48"""autoapi_noindex"""
 49
 50BNF2.i_plus_9 = BNF2((9, 1))
 51"""autoapi_noindex"""
 52
 53
 54class BNP2(elliptic_curve.EllipticCurve):
 55    """
 56    A twist of `BNP`. This is actually the same curve as `BNP` under a change
 57    of variable, but that change of variable is only possible over the larger
 58    field `BNP12`.
 59    """
 60
 61    FIELD = BNF2
 62    A = BNF2.zero()
 63    B = BNF2.from_int(3) / (BNF2.i + BNF2.from_int(9))
 64
 65
 66class BNF12(finite_field.GaloisField):
 67    """
 68    `BNF2` extended by adding a 6th root of `9 + i` called `w` (omega).
 69    """
 70
 71    PRIME = ALT_BN128_PRIME
 72    MODULUS = (82, 0, 0, 0, 0, 0, -18, 0, 0, 0, 0, 0)
 73
 74    w: "BNF12"
 75    i_plus_9: "BNF12"
 76
 77    def __mul__(self: "BNF12", right: "BNF12") -> "BNF12":  # type: ignore[override] # noqa: E501
 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        )
 95
 96
 97BNF12.FROBENIUS_COEFFICIENTS = BNF12.calculate_frobenius_coefficients()
 98"""autoapi_noindex"""
 99
100BNF12.w = BNF12((0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))
101"""autoapi_noindex"""
102
103BNF12.i_plus_9 = BNF12.w**6
104"""autoapi_noindex"""
105
106
107class BNP12(elliptic_curve.EllipticCurve):
108    """
109    The same curve as `BNP`, but defined over the larger field. This curve has
110    both subgroups of order `ALT_BN128_CURVE_ORDER` and allows pairings to be
111    computed.
112    """
113
114    FIELD = BNF12
115    A = BNF12.zero()
116    B = BNF12.from_int(3)
117
118
119def 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    )
126
127
128def 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)))
133
134
135def 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    )
143
144
145def 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
163
164
165def 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)
189
190
191def 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))