BLS Signatures

BLS Signatures

Introduction

Most signature schemes give you one signature for each message and one public key for each signer. If a thousand people sign the same block of data, you store a thousand signatures. BLS signatures change that. Any number of signatures can be added together into a single signature that is as short as one of them. The sum still proves that every signer signed.

The scheme is named after Dan Boneh, Ben Lynn, and Hovav Shacham. It works in a pairing-friendly elliptic curve, where a special function called a pairing compares points of two different groups. That function lets a verifier check a signature without ever knowing the secret key, and it is also the reason that signatures can be added. BLS signatures are also deterministic, so they avoid the nonce failures of ECDSA.

This guide builds the scheme on the curve BLS12-381 with the proof-of-possession ciphersuite from the IETF draft. It writes the field arithmetic, the pairing, the hash to the curve, and the signatures in Python. It checks them against the test vectors of RFC 9380, of the pairing-friendly curves draft, and of the Ethereum project, and it demonstrates the rogue key attack. The elliptic curve guide covers the basic group arithmetic that this guide builds on.

Table of Contents

• History and Standards
• Pairings in Brief
• The Curve BLS12-381
• The Signature Scheme
• Hashing to the Curve
• Encoding Points
• Aggregation
• Rogue Keys and Proofs of Possession
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Is Used
• Limitations
• Security Status
• FAQ
• References

History and Standards

Boneh, Lynn, and Shacham introduced the scheme in the paper “Short Signatures from the Weil Pairing”, published in the Journal of Cryptology in 2004. Wikipedia describes it as provably secure, in the random oracle model, against existential forgery under adaptive chosen-message attacks. It assumes that the computational Diffie-Hellman problem is hard in a gap Diffie-Hellman group. In 2003, Boneh, Gentry, Lynn, and Shacham showed how signatures from many signers on many messages can be aggregated into one.

The curve in this guide is newer. Wikipedia says that BLS12-381 was designed by Sean Bowe in early 2017 as the foundation for an upgrade of the Zcash protocol. It belongs to a family of curves named after Barreto, Lynn, and Scott, a different trio of authors with the same initials as Boneh, Lynn, and Shacham.

The standardization effort is an IETF draft, “BLS Signatures”, by Boneh, Gorbunov, Wahby, Wee, Wood, and Zhang. This guide follows version 5 of June 2022. Such a draft is a work in progress and not a final standard. It leaves the hashing to the curve to RFC 9380, “Hashing to Elliptic Curves”, and the curve parameters and the encoding of points to a second draft, “Pairing-Friendly Curves”. The test vectors of the Ethereum project cover the same ciphersuite, as that project’s description states.

Pairings in Brief

A pairing is a function e that takes a point of one group and a point of a second group and returns an element of a third group. The pairing-friendly curves draft states its two properties. It is bilinear: for points S and T and integers K and L, e(K*S, L*T) = e(S, T)^(K*L). It is non-degenerate: e(S, T) is 1 only if one of the points is the point at infinity. It must also be efficient to compute.

The three groups are called G1, G2, and GT. In this guide G1 is a group of points on a curve over the prime field with p elements. G2 is a group of points over the extension field with p^2 elements, and GT is a subgroup of the multiplicative group of the field with p^12 elements. All three have the same prime order r.

Bilinearity is the whole trick. It lets a verifier move a secret number from one side of the function to the other without knowing it. If a public key is pk = sk * G1 and a signature is sigma = sk * H, then e(pk, H) = e(sk * G1, H) = e(G1, H)^sk = e(G1, sk * H) = e(G1, sigma). The verifier sees only the two ends of this chain, and they are equal exactly when the same sk is behind both.

How is a pairing computed? The draft calls the optimal ate pairing the most efficient one and the one most used in practice. Its algorithm walks along the bits of the curve parameter. In each step it doubles a point of G2, evaluates a line through that point at the point of G1, and multiplies the result into an accumulator. This is the Miller loop. A last step, the final exponentiation, raises the accumulator to the power (p^12 - 1) / r, so that the result lies in the group of order r. The pairing-friendly curves draft gives the algorithm in its appendix A, and my code follows it.

The Curve BLS12-381

BLS12-381 is a Barreto-Lynn-Scott curve with embedding degree 12. The draft defines it by the parameter t = -2^63 - 2^62 - 2^60 - 2^57 - 2^48 - 2^16, which is -0xd201000000010000. The size of p becomes 381 bits, and the group order r has 255 bits. The parameter has only 6 bits set, which makes the Miller loop short: 63 doublings and 5 additions.

The two curves are:

• E1: y^2 = x^3 + 4 over the prime field Fp. Its subgroup G1 has order r, and the cofactor is h = 0x396c8c005555e1568c00aaab0000aaab.
• E2: y^2 = x^3 + 4(u + 1) over Fp2, the twist of E1. Its subgroup G2 has order r as well.

The fields are built as a tower. According to the draft, Fp2 = Fp[u] / (u^2 + 1), Fp6 = Fp2[v] / (v^3 - u - 1), and Fp12 = Fp6[w] / (w^2 - v). The draft calls the twist of BLS12-381 M-type. Computing in the twist keeps the points of G2 over the small field Fp2, instead of over Fp12, and the code maps a point of the twist to Fp12 only when it computes a line. A point of G1 takes 48 bytes and a point of G2 takes 96 bytes in compressed form.

The draft says that the security level of this pairing is expected to be 126 bits and not 128. It cites a published estimate for that figure.

I confirmed the parameters by computation. The prime p and the order r are prime. The order satisfies r = t^4 - t^2 + 1, and p = (t - 1)^2 * r / 3 + t. The number of points of E1 is h * r, where h = (t - 1)^2 / 3. The smallest k with p^k = 1 modulo r is 12, which is the embedding degree. Both generators lie on their curves and have order r. The pairing of the two generators in my code equals the twelve coordinates of the test vector in appendix B of the pairing-friendly curves draft, which is a strong check of the whole computation. It is also non-degenerate, bilinear for random multipliers, and returns an element of order r.

The Signature Scheme

The draft defines the scheme with a small set of operations. It offers two variants. In the minimal-pubkey-size variant, public keys are points of G1 and signatures are points of G2. In the minimal-signature-size variant, the groups are swapped. The draft says that implementations that use aggregation should prefer the first, because the size of the public keys dominates for even a small number of signers. This guide uses it. A public key takes 48 bytes and a signature takes 96 bytes.

Key generation. The secret key is an integer from 1 to r - 1. The draft recommends deriving it from at least 32 secret bytes IKM with HKDF-SHA-256. It runs HKDF-Extract on IKM followed by a zero byte, then HKDF-Expand to 48 bytes, and reduces the result modulo r. If the result is zero, it hashes the salt and tries again. The draft sets the default salt as the SHA-256 hash of the string BLS-SIG-KEYGEN-SALT-. For the input bytes 000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f, my code produces the secret key 23360db7e337b0a32b264e06bc11c1b474d16f55665373de1ce93cf15ddb3456, and Node.js with OpenSSL gets the same key from HKDF for all 30 random cases that I compared.

Public key. The public key is the point pk = sk * G1.

Signing. The signer hashes the message to a point H(m) of G2 and multiplies it by the secret key: sigma = sk * H(m). There is no random number in signing, so the same key and message always give the same signature.

Verifying. The verifier checks e(pk, H(m)) = e(G1, sigma). My code multiplies the two pairings, one of them inverted, and tests the product for 1: e(-G1, sigma) * e(pk, H(m)) = 1. That needs two Miller loops and a single final exponentiation. Before the pairing, it decodes the signature and checks that it is in the subgroup G2, and it checks that the public key is valid.

Validation. The draft lists what a valid public key is: it decodes, it is not the point at infinity, and it is in the correct subgroup. Section 5.3 of the draft explains why the subgroup check of the signature is required. For most pairing-friendly curves the pairing is undefined outside the prime-order subgroups, which gives unpredictable behavior and may enable forgeries. The point at infinity as a public key would belong to the secret key 0. Then the point at infinity would be a valid signature on every message.

The draft’s comparison with ECDSA shows the trade-off. At a similar level of security, it reports that ECDSA takes 37 and 79 microseconds to sign and verify on a typical laptop, while BLS takes 370 and 2,700 microseconds. ECDSA uses 32 bytes for a public key and 64 bytes for a signature. BLS uses 48 bytes and 96 bytes in this variant, or the other way around in the second one.

Hashing to the Curve

The message must be turned into a point of G2, in a way that behaves like a random function. The draft requires a function that is a random oracle encoding or a nonuniform encoding as defined in the hash-to-curve document. It also requires a domain separation tag, so that a hash made for one use cannot be mistaken for another. This guide uses the suite BLS12381G2_XMD:SHA-256_SSWU_RO_ of RFC 9380 with the tag 43 bytes long, BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_.

The steps of the suite are these.

1. Expand the message. The function expand_message_xmd uses SHA-256 to turn the message and the tag into 256 pseudorandom bytes. It hashes a block b0 of the input and then chains eight blocks of 32 bytes. For the message in the worked example, the first 24 bytes are e761814a584d3dc553cf53e454f856d89d9605672f2a3215.
2. Make two field elements. The 256 bytes are cut into four numbers of 64 bytes. Each is reduced modulo p. Two of them form the element u0 of Fp2, and two form u1. The suite uses 64 bytes for each number to match a security parameter of 128 bits, so that reducing it modulo p introduces only a negligible bias.
3. Map each element to a curve. The simplified Shallue-van de Woestijne-Ulas map sends u to a point of a helper curve E', which has the form y^2 = x^3 + A'x + B' with A' and B' both nonzero. The map of RFC 9380 needs both to be nonzero, and E2 has A = 0, so the suite maps to E' first. The sign of y is chosen to match the sign of u.
4. Move to E2. A fixed 3-isogeny, given as four rational functions with constants listed in appendix E.3 of the RFC, maps the point from E' to E2.
5. Add and clear the cofactor. The two points are added. The sum lies on E2 but not necessarily in the subgroup G2. Multiplying by the fixed number h_eff, which has 636 bits, moves it into G2.

I tested every step of this against the values that the RFC prints in appendix J.10.1. For five test messages, my code reproduces u[0], u[1], the two mapped points Q0 and Q1, and the final point. All of them are in G2. The vectors of the Ethereum project contain the same four hash values. The test code reads all of these from the text of the RFC and from the JSON files.

Encoding Points

A point must be written as bytes. The draft on pairing-friendly curves describes the compressed format that the Zcash project defined. It uses three flag bits in the top of the first byte: one for compression, one for the point at infinity, and one that tells which of the two possible y values is meant. The sign of y is 1 when y is larger than (p - 1) / 2. For a point of G2, the sign comes from the second coordinate of y unless that is zero.

A point of G1 is its x coordinate in 48 bytes. A point of G2 is the two parts of x in 96 bytes, with the part that belongs to u first. The point at infinity is a zero string with only the flag bits set, so its first byte is c0. The generator of G1 encodes as 97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb, and that of G2 as 93e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049334cf11213945d57e5ac7d055d042b7e024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8.

Decoding is where mistakes become attacks. A decoder must reject a wrong length, a value of x that is not smaller than p, an x that is not on the curve, a point that is not in the subgroup, and flag combinations that make no sense. The test vectors of the Ethereum project include 28 cases of this kind, and my decoders agree with all of them.

Aggregation

Aggregation is the feature that sets BLS apart. The Aggregate function adds signatures as points of G2, and the result is one signature of 96 bytes. The draft states that the aggregate can be verified with only n + 1 pairings, instead of 2n for n separate checks. My code does it with n + 1 Miller loops and one final exponentiation.

There are two verification functions for an aggregate.

• AggregateVerify takes n public keys and n messages. It computes H(m_i) for each message and checks that the product of e(pk_i, H(m_i)) equals e(G1, sigma).
• FastAggregateVerify is for the common case in which all signers signed the same message. It adds the public keys first, since e(pk_1, H) * e(pk_2, H) = e(pk_1 + pk_2, H), and then runs a single ordinary check. The draft says it is faster than AggregateVerify.

The example in this guide uses three signers and the message of 32 bytes of ab. The three public keys are a491d1b0ecd9bb917989f0e74f0dea0422eac4a873e5e2644f368dffb9a6e20fd6e10c1b77654d067c0618f6e5a7f79a, b301803f8b5ac4a1133581fc676dfedc60d891dd5fa99028805e5ea5b08d3491af75d0707adab3b70c6a6a580217bf81, and b53d21a4cfd562c469cc81514d4ce5a6b577d8403d32a394dc265dd190b47fa9f829fdd7963afdf972e5e77854051f6f. Their three signatures are added to give the aggregate signature:

9712c3edd73a209c742b8250759db12549b3eaf43b5ca61376d9f30e2747dbcf842d8b2ac0901d2a093713e20284a7670fcf6954e9ab93de991bb9b313e664785a075fc285806fa5224c82bde146561b446ccfc706a64b8579513cfc4ff1d930

It equals the aggregate that the Ethereum test vector fast_aggregate_verify_valid_3d7576f3c0e3570a lists. The aggregate public key is a095608b35495ca05002b7b5966729dd1ed096568cf2ff24f3318468e0f3495361414a78ebc09574489bc79e48fca969, which is also the public key of the sum of the three secret keys. That shows the algebra at work: the signature of the summed key is the sum of the signatures. For one thousand signers, the public keys and the one signature together take 48096 bytes, and the keys dominate.

Rogue Keys and Proofs of Possession

Aggregation has a danger. The draft names it the rogue key attack: a specially crafted public key is used to forge an aggregated signature. Here is how it works in the setting of FastAggregateVerify, where keys are added.

1. The victim has an honest public key pk_v.
2. Mallory picks a number x and publishes pk_r = x * G1 - pk_v. It is a valid point, but Mallory does not know a secret key for it.
3. The sum pk_v + pk_r equals x * G1. Mallory knows the secret number x behind that sum.
4. Mallory signs a message with x alone. The signature x * H(m) verifies against the pair of keys, although the victim never signed.

I ran this attack with real keys. The victim’s public key is 9112a0386a2340714ba0c6d2df235377a8679c3899d03e6ef04dba7a50ef49e5a1dc93105e9374e93ed301b63487e17c, and the rogue key is 8d40b52464921cfdef54f8d453429005e4f11e5ff9648fc89ec060597be3d59e0503a3c89d4128bf3625cbf1113d1c1f. The message is “the victim agrees to pay Mallory”. The rogue key passes the validation of a public key, since it is a valid point in the right subgroup. The forged signature verifies for the pair of keys, and the victim’s own key rejects it.

The draft describes three ways to defend against the attack. The three schemes differ in this choice.

• Basic. Require all messages in an aggregate to be distinct. The attack needs the same message. The draft’s AggregateVerify for this scheme rejects equal messages.
• Message augmentation. Sign the concatenation of the public key and the message. Different signers then always sign different messages.
• Proof of possession. Require each public key to come with a signature on itself, using a different domain separation tag. This lets FastAggregateVerify add keys safely, as the draft says. The key holder proves that they know the secret number.

My code implements the proof of possession scheme, since it is the one that the Ethereum vectors use and the one that makes FastAggregateVerify possible. A proof is sign(sk, pk) with the tag BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_. For the example key it is 88bb31b27eae23038e14f9d9d1b628a39f5881b5278c3c6f0249f81ba0deb1f68aa5f8847854d6554051aa810fdf1cdb02df4af7a5647b1aa4afb60ec6d446ee17af24a8a50876ffdaf9bf475038ec5f8ebeda1c1c6a3220293e23b13a9a5d26, and it differs from a normal signature on the same bytes because of the tag. In my test, Mallory cannot produce a valid proof for the rogue key, either with the number x or with the proof function. The draft states the precondition clearly: if a caller does not check the proofs, FastAggregateVerify provides no security against forgery.

Interactive Visualizer

The visualizer above runs the real scheme with four modes.

• Sign a message. Enter a secret key and a message. The log shows the public key, the expansion of the message, the two field elements, the map to the curve, the clearing of the cofactor, the signature, and a check by pairing. A message that starts with 0x is read as hexadecimal bytes, as in the test vectors. Any other message is read as text.
• Verify a signature. Enter a public key of 96 hexadecimal digits, a message, and a signature of 192 digits. The log shows the decoding with the subgroup checks, the hash of the message, and the pairing product. Change one digit to see the rejection.
• Aggregate three signatures. Enter three secret keys and one message. The log shows each key and signature, the sums, and the single check for all three.
• Rogue key attack. Enter a victim’s secret key, a number x for Mallory, and a message. The log shows the rogue key, the forged signature, the acceptance by the aggregate check without proofs, the rejection by the victim’s key, and the failed proof of possession.

The defaults are keys and the message of the Ethereum test vectors, so the first runs give signatures you can compare with the vectors. A run takes a second or two, because a pairing is heavy work for a browser.

A Worked Example

The second key of the Ethereum test vectors is 47b8192d77bf871b62e87859d653922725724a5c031afeabc60bcef5ff665138. Its public key is a point of G1:

b301803f8b5ac4a1133581fc676dfedc60d891dd5fa99028805e5ea5b08d3491af75d0707adab3b70c6a6a580217bf81

The message is 32 bytes of ab. After the five hashing steps, the message becomes this point of G2, shown in compressed form:

979451d90ade914f7a6ffc5062914af990af297abdebf81dcebcaff93a5cb959e7f5db624bc8abb8cdb2660374c86a350bc0f071f2d0655a5edbf6b9208a6649d3309b8692d2f55bde74c52cc2de0fed2bb60b4c45935b11c32827da1b80cb8f

The signature is the secret key times that point:

9674e2228034527f4c083206032b020310face156d4a4685e2fcaec2f6f3665aa635d90347b6ce124eb879266b1e801d185de36a0a289b85e9039662634f2eea1e02e670bc7ab849d006a70b2f93b84597558a05b879c8d445f387a5d5b653df

This is the output that the Ethereum test vector lists for this key and message. Verification multiplies two pairings and finds 1, so the signature is valid. A change of one bit in the message gives a different point H(m) and the product is no longer 1. The secret key has 255 bits, so the multiplication by sk takes about 254 doublings. The multiplication by h_eff is longer, because that number has 636 bits.

On the computer that I used, one pairing in my Python takes about 180 milliseconds. Signing takes about 40 milliseconds and verifying takes about 260 milliseconds. These are the figures of a teaching implementation. Optimized libraries are much faster.

Python Implementation

The code is in three files. The first has the fields, the two groups, the pairing, and the encoding of points.

# bls12_381.py
# The pairing-friendly curve BLS12-381: the fields, the groups G1 and G2, the optimal ate pairing,
# and the ZCash encoding of points. Teaching code. It is slow and not constant time.

# ---------- the parameters ----------
T = -(2 ** 63 + 2 ** 62 + 2 ** 60 + 2 ** 57 + 2 ** 48 + 2 ** 16)  # the curve parameter, -0xd201000000010000
P = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
R = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001  # the order of G1, G2, and GT
H1 = 0x396C8C005555E1568C00AAAB0000AAAB  # the cofactor of G1
G1_GEN = (
    0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB,
    0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1,
)
G2_GEN = (
    (0x024AA2B2F08F0A91260805272DC51051C6E47AD4FA403B02B4510B647AE3D1770BAC0326A805BBEFD48056C8C121BDB8,
     0x13E02B6052719F607DACD3A088274F65596BD0D09920B61AB5DA61BBDC7F5049334CF11213945D57E5AC7D055D042B7E),
    (0x0CE5D527727D6E118CC9CDC6DA2E351AADFD9BAA8CBDD3A76D429A695160D12C923AC9CC3BACA289E193548608B82801,
     0x0606C4A02EA734CC32ACD2B02BC28B99CB3E287E85A763AF267492AB572E99AB3F370D275CEC1DA1AAA9075FF05F79BE),
)


# ---------- the field tower: Fp, Fp2 = Fp[u]/(u^2 + 1), Fp6 = Fp2[v]/(v^3 - u - 1), Fp12 = Fp6[w]/(w^2 - v) ----------

class Fp:
    __slots__ = ("n",)

    def __init__(self, n):
        self.n = n % P

    def __add__(self, o): return Fp(self.n + o.n)
    def __sub__(self, o): return Fp(self.n - o.n)
    def __neg__(self): return Fp(-self.n)
    def __mul__(self, o): return Fp(self.n * (o if isinstance(o, int) else o.n))
    def __eq__(self, o): return self.n == o.n
    def inv(self): return Fp(pow(self.n, -1, P))
    def is_zero(self): return self.n == 0

    def sqrt(self):
        root = pow(self.n, (P + 1) // 4, P)  # P = 3 mod 4
        return Fp(root) if root * root % P == self.n else None


class Fp2:
    __slots__ = ("a", "b")  # a + b*u

    def __init__(self, a, b=0):
        self.a, self.b = a % P, b % P

    def __add__(self, o): return Fp2(self.a + o.a, self.b + o.b)
    def __sub__(self, o): return Fp2(self.a - o.a, self.b - o.b)
    def __neg__(self): return Fp2(-self.a, -self.b)

    def __mul__(self, o):
        if isinstance(o, int):
            return Fp2(self.a * o, self.b * o)
        return Fp2(self.a * o.a - self.b * o.b, self.a * o.b + self.b * o.a)

    def __eq__(self, o): return self.a == o.a and self.b == o.b
    def is_zero(self): return self.a == 0 and self.b == 0
    def conj(self): return Fp2(self.a, -self.b)
    def mul_xi(self): return Fp2(self.a - self.b, self.a + self.b)  # times 1 + u

    def inv(self):
        n = pow(self.a * self.a + self.b * self.b, -1, P)
        return Fp2(self.a * n, -self.b * n)

    def __pow__(self, e):
        result, base = Fp2(1), self
        while e:
            if e & 1:
                result = result * base
            base = base * base
            e >>= 1
        return result

    def sqrt(self):
        """A square root, or None. P = 3 mod 4, so this is the method for that case (Adj and Rodriguez-Henriquez)."""
        if self.is_zero():
            return Fp2(0)
        a1 = self ** ((P - 3) // 4)
        alpha = a1 * (a1 * self)
        x0 = a1 * self
        root = Fp2(-x0.b, x0.a) if alpha == Fp2(-1) else (Fp2(1) + alpha) ** ((P - 1) // 2) * x0
        return root if root * root == self else None


class Fp6:
    __slots__ = ("c",)  # c[0] + c[1]*v + c[2]*v^2, with v^3 = 1 + u

    def __init__(self, c0, c1, c2):
        self.c = (c0, c1, c2)

    def __add__(self, o): return Fp6(*(x + y for x, y in zip(self.c, o.c)))
    def __sub__(self, o): return Fp6(*(x - y for x, y in zip(self.c, o.c)))
    def __neg__(self): return Fp6(*(-x for x in self.c))
    def is_zero(self): return all(x.is_zero() for x in self.c)

    def __mul__(self, o):
        a0, a1, a2 = self.c
        if isinstance(o, int):
            return Fp6(a0 * o, a1 * o, a2 * o)
        b0, b1, b2 = o.c
        return Fp6(a0 * b0 + (a1 * b2 + a2 * b1).mul_xi(),
                   a0 * b1 + a1 * b0 + (a2 * b2).mul_xi(),
                   a0 * b2 + a1 * b1 + a2 * b0)

    def mul_v(self):
        return Fp6(self.c[2].mul_xi(), self.c[0], self.c[1])

    def inv(self):
        a0, a1, a2 = self.c
        t0 = a0 * a0 - (a1 * a2).mul_xi()
        t1 = (a2 * a2).mul_xi() - a0 * a1
        t2 = a1 * a1 - a0 * a2
        d = (a0 * t0 + (a2 * t1 + a1 * t2).mul_xi()).inv()
        return Fp6(t0 * d, t1 * d, t2 * d)


ZERO2 = Fp2(0)
ZERO6 = Fp6(ZERO2, ZERO2, ZERO2)


class Fp12:
    __slots__ = ("c0", "c1")  # c0 + c1*w, with w^2 = v

    def __init__(self, c0, c1):
        self.c0, self.c1 = c0, c1

    @staticmethod
    def one():
        return Fp12(Fp6(Fp2(1), ZERO2, ZERO2), ZERO6)

    def __add__(self, o): return Fp12(self.c0 + o.c0, self.c1 + o.c1)
    def __sub__(self, o): return Fp12(self.c0 - o.c0, self.c1 - o.c1)
    def __neg__(self): return Fp12(-self.c0, -self.c1)
    def __eq__(self, o): return (self.c0 - o.c0).is_zero() and (self.c1 - o.c1).is_zero()
    def is_zero(self): return self.c0.is_zero() and self.c1.is_zero()
    def conj(self): return Fp12(self.c0, -self.c1)  # the p^6 power

    def __mul__(self, o):
        if isinstance(o, int):
            return Fp12(self.c0 * o, self.c1 * o)
        t0, t1 = self.c0 * o.c0, self.c1 * o.c1
        return Fp12(t0 + t1.mul_v(), (self.c0 + self.c1) * (o.c0 + o.c1) - t0 - t1)

    def inv(self):
        d = (self.c0 * self.c0 - (self.c1 * self.c1).mul_v()).inv()
        return Fp12(self.c0 * d, -(self.c1 * d))

    def __pow__(self, e):
        result, base = Fp12.one(), self
        while e:
            if e & 1:
                result = result * base
            base = base * base
            e >>= 1
        return result


# ---------- the groups ----------
# E1: y^2 = x^3 + 4 over Fp.  E2: y^2 = x^3 + 4(1 + u) over Fp2.  A point is (x, y), the point at infinity is None.

B1 = Fp(4)
B2 = Fp2(4, 4)
G1 = (Fp(G1_GEN[0]), Fp(G1_GEN[1]))
G2 = (Fp2(*G2_GEN[0]), Fp2(*G2_GEN[1]))


def on_curve(point, b):
    if point is None:
        return True
    x, y = point
    return y * y == x * x * x + b


def add(p1, p2):
    if p1 is None:
        return p2
    if p2 is None:
        return p1
    (x1, y1), (x2, y2) = p1, p2
    if x1 == x2:
        if (y1 + y2).is_zero():
            return None
        slope = x1 * x1 * 3 * (y1 * 2).inv()
    else:
        slope = (y2 - y1) * (x2 - x1).inv()
    x3 = slope * slope - x1 - x2
    return (x3, slope * (x1 - x3) - y1)


def neg(point):
    return None if point is None else (point[0], -point[1])


def multiply(k, point):
    if k < 0:
        return multiply(-k, neg(point))
    result = None
    while k:
        if k & 1:
            result = add(result, point)
        point = add(point, point)
        k >>= 1
    return result


def in_subgroup(point):
    """A point is in G1 or G2 when R times it is the point at infinity."""
    return multiply(R, point) is None


# ---------- the pairing ----------

def _untwist(q):
    """The point of E2 as a point of E over Fp12: (x, y) goes to (x / w^2, y / w^3)."""
    xi_inv = Fp2(1, 1).inv()
    x = Fp12(Fp6(ZERO2, ZERO2, q[0] * xi_inv), ZERO6)
    y = Fp12(ZERO6, Fp6(ZERO2, q[1] * xi_inv, ZERO2))
    return x, y


def _embed(p):
    return (Fp12(Fp6(Fp2(p[0].n), ZERO2, ZERO2), ZERO6), Fp12(Fp6(Fp2(p[1].n), ZERO2, ZERO2), ZERO6))


def miller_loop(p, q):
    """The Miller loop of the optimal ate pairing for p in G1 and q in G2."""
    if p is None or q is None:
        return Fp12.one()
    xp, yp = _embed(p)
    qx, qy = _untwist(q)
    tx, ty = qx, qy
    f = Fp12.one()
    for bit in bin(-T)[3:]:
        slope = tx * tx * 3 * (ty * 2).inv()                       # the tangent at T
        f = f * f * ((yp - ty) - slope * (xp - tx))                # the line through T, at p
        nx = slope * slope - tx - tx
        tx, ty = nx, slope * (tx - nx) - ty
        if bit == "1":
            slope = (qy - ty) * (qx - tx).inv()                    # the line through T and Q
            f = f * ((yp - ty) - slope * (xp - tx))
            nx = slope * slope - tx - qx
            tx, ty = nx, slope * (tx - nx) - ty
    return f.conj()  # T is negative


def final_exponentiation(f):
    f = f.conj() * f.inv()                  # f^(p^6 - 1)
    f = f ** (P * P) * f                    # then ^(p^2 + 1)
    return f ** ((P ** 4 - P * P + 1) // R)  # the rest of (p^12 - 1) / r


def pairing(p, q):
    return final_exponentiation(miller_loop(p, q))


def pairing_product_is_one(pairs):
    """True when the product of e(p, q) over the pairs is 1. One final exponentiation serves all the pairs."""
    f = Fp12.one()
    for p, q in pairs:
        f = f * miller_loop(p, q)
    return final_exponentiation(f) == Fp12.one()


# ---------- the ZCash encoding of points (compressed) ----------
# Three flag bits in the top of the first byte: compressed, infinity, and the sign of y.

HALF = (P - 1) // 2


def _sign(y):
    if isinstance(y, Fp):
        return int(y.n > HALF)
    return int(y.b > HALF) if y.b != 0 else int(y.a > HALF)


def g1_to_bytes(point):
    if point is None:
        return bytes([0xC0]) + bytes(47)
    data = bytearray(point[0].n.to_bytes(48, "big"))
    data[0] |= 0x80 | (_sign(point[1]) << 5)
    return bytes(data)


def g2_to_bytes(point):
    if point is None:
        return bytes([0xC0]) + bytes(95)
    data = bytearray(point[0].b.to_bytes(48, "big") + point[0].a.to_bytes(48, "big"))
    data[0] |= 0x80 | (_sign(point[1]) << 5)
    return bytes(data)


def _flags(data, length):
    if len(data) != length:
        raise ValueError("wrong length")
    c, i, s = data[0] >> 7, (data[0] >> 6) & 1, (data[0] >> 5) & 1
    if not c:
        raise ValueError("only the compressed form is supported")
    body = bytes([data[0] & 0x1F]) + data[1:]
    if i:
        if s or any(body):
            raise ValueError("a point at infinity has no other bits set")
    return i, s, body


def g1_from_bytes(data, check_subgroup=True):
    """The point for 48 bytes. Raises ValueError for anything that is not a valid point of G1."""
    infinity, sign, body = _flags(data, 48)
    if infinity:
        return None
    x = int.from_bytes(body, "big")
    if x >= P:
        raise ValueError("x is not smaller than p")
    y = Fp(x * x * x + 4).sqrt()
    if y is None:
        raise ValueError("x is not the coordinate of a point")
    if _sign(y) != sign:
        y = -y
    point = (Fp(x), y)
    if check_subgroup and not in_subgroup(point):
        raise ValueError("the point is not in the subgroup G1")
    return point


def g2_from_bytes(data, check_subgroup=True):
    infinity, sign, body = _flags(data, 96)
    if infinity:
        return None
    x1, x0 = int.from_bytes(body[:48], "big"), int.from_bytes(body[48:], "big")
    if x0 >= P or x1 >= P:
        raise ValueError("a coordinate is not smaller than p")
    x = Fp2(x0, x1)
    y = (x * x * x + B2).sqrt()
    if y is None:
        raise ValueError("x is not the coordinate of a point")
    if _sign(y) != sign:
        y = -y
    point = (x, y)
    if check_subgroup and not in_subgroup(point):
        raise ValueError("the point is not in the subgroup G2")
    return point


if __name__ == "__main__":
    print("G1 and G2 generators are on their curves:", on_curve(G1, B1), on_curve(G2, B2))
    print("G1 generator, compressed:", g1_to_bytes(G1).hex())
    print("G2 generator, compressed:", g2_to_bytes(G2).hex())
    a, b = 5, 7
    left = pairing(multiply(a, G1), multiply(b, G2))
    right = pairing(G1, G2) ** (a * b)
    print("e(5 * G1, 7 * G2) equals e(G1, G2)^35:", left == right)

Running it produces this output:

G1 and G2 generators are on their curves: True True
G1 generator, compressed: 97f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
G2 generator, compressed: 93e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049334cf11213945d57e5ac7d055d042b7e024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8
e(5 * G1, 7 * G2) equals e(G1, G2)^35: True

The second file hashes a message to G2 with the suite of RFC 9380. Its constants are the ones of appendix E.3 of the RFC.

# hash_to_curve.py
# Hashing a message to a point of G2 on BLS12-381, with the suite BLS12381G2_XMD:SHA-256_SSWU_RO_ of RFC 9380.
# Teaching code. It is not constant time.

import hashlib

from bls12_381 import Fp2, add, multiply

# ---------- the parameters of the suite ----------
L = 64                   # bytes drawn for each field element: ceil((381 + 128) / 8)
M = 2                    # Fp2 has two coordinates
Z = Fp2(-2, -1)          # the constant of the map, -(2 + u)
A_ISO = Fp2(0, 240)      # the curve E': y^2 = x^3 + A' * x + B'
B_ISO = Fp2(1012, 1012)
H_EFF = int(
    "bc69f08f2ee75b3584c6a0ea91b352888e2a8e9145ad7689986ff031508ffe13"
    "29c2f178731db956d82bf015d1212b02ec0ec69d7477c1ae954cbc06689f6a35"
    "9894c0adebbf6b4e8020005aaa95551",
    16,
)  # the scalar that clears the cofactor

# The 3-isogeny from E' to E: x = x_num / x_den, y = y' * y_num / y_den. Each list starts with the constant term.
ISO_X_NUM = [
    Fp2(
        0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6,
        0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6,
    ),
    Fp2(0, 0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71a),
    Fp2(
        0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71e,
        0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38d,
    ),
    Fp2(0x171d6541fa38ccfaed6dea691f5fb614cb14b4e7f4e810aa22d6108f142b85757098e38d0f671c7188e2aaaaaaaa5ed1, 0),
]

ISO_X_DEN = [
    Fp2(0, 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa63),
    Fp2(
        0xc,
        0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa9f,
    ),
    Fp2(1),
]

ISO_Y_NUM = [
    Fp2(
        0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706,
        0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706,
    ),
    Fp2(0, 0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97be),
    Fp2(
        0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71c,
        0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38f,
    ),
    Fp2(0x124c9ad43b6cf79bfbf7043de3811ad0761b0f37a1e26286b0e977c69aa274524e79097a56dc4bd9e1b371c71c718b10, 0),
]

ISO_Y_DEN = [
    Fp2(
        0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb,
        0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb,
    ),
    Fp2(0, 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3),
    Fp2(
        0x12,
        0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99,
    ),
    Fp2(1),
]


# ---------- from a message to two elements of Fp2 ----------

def expand_message_xmd(message, dst, length):
    """Stretch a message to `length` bytes with SHA-256 (expand_message_xmd)."""
    b_len, r_len = 32, 64
    ell = -(-length // b_len)
    if ell > 255 or len(dst) > 255:
        raise ValueError("too long")
    dst_prime = dst + bytes([len(dst)])
    msg_prime = bytes(r_len) + message + length.to_bytes(2, "big") + bytes([0]) + dst_prime
    b0 = hashlib.sha256(msg_prime).digest()
    block = hashlib.sha256(b0 + bytes([1]) + dst_prime).digest()
    out = block
    for i in range(2, ell + 1):
        block = hashlib.sha256(bytes(x ^ y for x, y in zip(b0, block)) + bytes([i]) + dst_prime).digest()
        out += block
    return out[:length]


def hash_to_field(message, dst, count):
    data = expand_message_xmd(message, dst, count * M * L)
    elements = []
    for i in range(count):
        coords = [int.from_bytes(data[L * (j + i * M):L * (j + i * M + 1)], "big") for j in range(M)]
        elements.append(Fp2(*coords))  # reduced modulo p
    return elements


# ---------- from an element of Fp2 to a point ----------

def sgn0(x):
    """The 'sign' of an element of Fp2: the parity of the first nonzero coordinate."""
    return x.a % 2 if x.a != 0 else x.b % 2


def map_to_curve_simple_swu(u):
    """The simplified Shallue-van de Woestijne-Ulas map from Fp2 to the curve E'."""
    tv = (Z * Z * u * u * u * u + Z * u * u)
    x1 = (Fp2(0) - B_ISO * A_ISO.inv()) * (Fp2(1) + tv.inv()) if not tv.is_zero() else B_ISO * (Z * A_ISO).inv()
    gx1 = x1 * x1 * x1 + A_ISO * x1 + B_ISO
    x2 = Z * u * u * x1
    gx2 = x2 * x2 * x2 + A_ISO * x2 + B_ISO
    y = gx1.sqrt()
    if y is not None:
        x = x1
    else:
        x, y = x2, gx2.sqrt()
    if sgn0(u) != sgn0(y):
        y = -y
    return x, y


def _polynomial(coefficients, x):
    result = Fp2(0)
    for k in reversed(coefficients):
        result = result * x + k
    return result


def iso_map(point):
    x, y = point
    x_den, y_den = _polynomial(ISO_X_DEN, x), _polynomial(ISO_Y_DEN, x)
    if x_den.is_zero() or y_den.is_zero():
        return None
    return _polynomial(ISO_X_NUM, x) * x_den.inv(), y * _polynomial(ISO_Y_NUM, x) * y_den.inv()


def hash_to_g2(message, dst):
    """A point of G2 for the message. The domain separation tag dst names the use of the hash."""
    u0, u1 = hash_to_field(message, dst, 2)
    q0 = iso_map(map_to_curve_simple_swu(u0))
    q1 = iso_map(map_to_curve_simple_swu(u1))
    return multiply(H_EFF, add(q0, q1))  # a point on E, moved into the subgroup G2


if __name__ == "__main__":
    # The first test vector of RFC 9380, appendix J.10.1: the empty message
    dst = b"QUUX-V01-CS02-with-BLS12381G2_XMD:SHA-256_SSWU_RO_"
    x, y = hash_to_g2(b"", dst)
    print("P.x = %096x + %096x * I" % (x.a, x.b))
    print("P.y = %096x + %096x * I" % (y.a, y.b))

Running it prints the point for the empty message, which is the first vector of the RFC:

P.x = 0141ebfbdca40eb85b87142e130ab689c673cf60f1a3e98d69335266f30d9b8d4ac44c1038e9dcdd5393faf5c41fb78a + 05cb8437535e20ecffaef7752baddf98034139c38452458baeefab379ba13dff5bf5dd71b72418717047f5b0f37da03d * I
P.y = 0503921d7f6a12805e72940b963c0cf3471c7b2a524950ca195d11062ee75ec076daf2d4bc358c4b190c0c98064fdd92 + 12424ac32561493f3fe3c260708a12b7c620e7be00099a974e259ddc7d1f6395c3c811cdd19f1e8dbf3e9ecfdcbab8d6 * I

The third file is the signature scheme itself.

# bls.py
# BLS signatures on BLS12-381 with the proof-of-possession ciphersuite
#     BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_
# of the IETF draft "BLS Signatures". Public keys are points of G1 (48 bytes) and signatures
# are points of G2 (96 bytes). Teaching code. It is slow and not constant time.

import hashlib
import hmac

from bls12_381 import (
    G1, G2, R, add, g1_from_bytes, g1_to_bytes, g2_from_bytes, g2_to_bytes, multiply, neg, pairing_product_is_one,
)
from hash_to_curve import hash_to_g2

DST_SIG = b"BLS_SIG_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_"  # the domain separation tag of signatures
DST_POP = b"BLS_POP_BLS12381G2_XMD:SHA-256_SSWU_RO_POP_"  # a different one for proofs of possession


# ---------- keys ----------

def _hmac(key, data):
    return hmac.new(key, data, hashlib.sha256).digest()


def key_gen(ikm, salt=None, key_info=b""):
    """A secret key from at least 32 secret bytes, with HKDF as in the draft (section 2.3)."""
    if len(ikm) < 32:
        raise ValueError("the input key material must have at least 32 bytes")
    salt = hashlib.sha256(b"BLS-SIG-KEYGEN-SALT-").digest() if salt is None else salt
    length = 48  # ceil(3 * 255 / 16)
    while True:
        prk = _hmac(salt, ikm + bytes([0]))  # HKDF-Extract
        okm, block = b"", b""
        for i in range(1, 3):  # HKDF-Expand, two blocks of 32 bytes are enough for 48
            block = _hmac(prk, block + key_info + length.to_bytes(2, "big") + bytes([i]))
            okm += block
        secret = int.from_bytes(okm[:length], "big") % R
        if secret != 0:
            return secret
        salt = hashlib.sha256(salt).digest()


def sk_to_pk(secret):
    if not 1 <= secret < R:
        raise ValueError("a secret key must be between 1 and r - 1")
    return g1_to_bytes(multiply(secret, G1))


def key_validate(pk):
    """A public key must decode, must not be the point at infinity, and must be in the subgroup."""
    try:
        point = g1_from_bytes(pk)  # includes the subgroup check
    except ValueError:
        return False
    return point is not None


# ---------- signing and verifying ----------

def sign(secret, message, dst=DST_SIG):
    if not 1 <= secret < R:
        raise ValueError("a secret key must be between 1 and r - 1")
    return g2_to_bytes(multiply(secret, hash_to_g2(message, dst)))


def verify(pk, message, signature, dst=DST_SIG):
    """True when e(pk, H(m)) = e(G1, signature), checked as e(-G1, signature) * e(pk, H(m)) = 1."""
    try:
        sig_point = g2_from_bytes(signature)  # includes the subgroup check
    except ValueError:
        return False
    if not key_validate(pk):
        return False
    return pairing_product_is_one([(neg(G1), sig_point), (g1_from_bytes(pk), hash_to_g2(message, dst))])


# ---------- aggregation ----------

def aggregate(signatures):
    """One signature that stands for all of them, or None when the input is invalid."""
    if not signatures:
        return None
    total = None
    for signature in signatures:
        try:
            total = add(total, g2_from_bytes(signature, check_subgroup=False))
        except ValueError:
            return None
    return g2_to_bytes(total)


def aggregate_verify(pks, messages, signature, dst=DST_SIG):
    """One signature on n messages by n keys: n + 1 pairings."""
    if not pks or len(pks) != len(messages):
        return False
    try:
        sig_point = g2_from_bytes(signature)
    except ValueError:
        return False
    if not all(key_validate(pk) for pk in pks):
        return False
    pairs = [(neg(G1), sig_point)]
    pairs += [(g1_from_bytes(pk), hash_to_g2(m, dst)) for pk, m in zip(pks, messages)]
    return pairing_product_is_one(pairs)


def fast_aggregate_verify(pks, message, signature, dst=DST_SIG):
    """Signatures on one message: add the public keys, then verify once. Every key needs a proof of possession."""
    if not pks or not all(key_validate(pk) for pk in pks):
        return False
    total = None
    for pk in pks:
        total = add(total, g1_from_bytes(pk, check_subgroup=False))
    if total is None:
        return False
    return verify(g1_to_bytes(total), message, signature, dst)


# ---------- proof of possession ----------

def pop_prove(secret):
    """A signature on the public key itself, made with a different domain separation tag."""
    return sign(secret, sk_to_pk(secret), DST_POP)


def pop_verify(pk, proof):
    return verify(pk, pk, proof, DST_POP)


if __name__ == "__main__":
    secret = key_gen(bytes(range(32)))
    pk = sk_to_pk(secret)
    message = b"hello"
    signature = sign(secret, message)
    print("secret key:", format(secret, "064x"))
    print("public key:", pk.hex())
    print("signature: ", signature.hex())
    print("valid:     ", verify(pk, message, signature))
    print("altered:   ", verify(pk, b"hellp", signature))

Running it produces this output:

secret key: 23360db7e337b0a32b264e06bc11c1b474d16f55665373de1ce93cf15ddb3456
public key: 9112a0386a2340714ba0c6d2df235377a8679c3899d03e6ef04dba7a50ef49e5a1dc93105e9374e93ed301b63487e17c
signature:  a91b093442e741c53a937bf09c142a6666c45d787bab03edd7bef7d68d49923a2874101801cd0368114a6f24a4e1c010025df698fc3f4ec823e13dac4d1efeb7e70207c4a2e3c7c3f482a32de757e2a00941fdc8d263d1844e1d202980ca9259
valid:      True
altered:    False

I checked this code against several independent sources. The pairing of the generators equals the test vector of the pairing-friendly curves draft, and the parameters satisfy the relations listed above. The hash to the curve matches all five messages of RFC 9380 appendix J.10.1, including the intermediate values. The test vectors of the Ethereum project cover the same ciphersuite. 94 of their files match. They hold 10 signing cases, 29 verification cases, 6 aggregations, 12 checks of aggregates on one message, 5 checks of aggregates on several messages, 28 decoding cases, and 4 hash values. This includes cases of the point at infinity, tampered signatures, and the secret key zero. I did not run the 4 batch verification cases, since batch verification is not part of the draft. HKDF in Node.js agrees with my key generation. The visualizer code has its own SHA-256, which matches OpenSSL for 305 input lengths, and its hash to the curve matches my Python in 35 cases. It matches all 74 test vectors that this Python code produces, and I ran its page in a simulated browser.

Where It Is Used

• Ethereum. Wikipedia reports that by 2021, BLS signatures were used in the consensus layer of proof-of-stake Ethereum, to aggregate the signatures of all validators. The test suite of this guide comes from that project.
• Chia. Wikipedia lists the Chia network among the users of BLS signatures.
• drand. The drand randomness service uses the curve BLS12-381 in a threshold scheme, according to Wikipedia.
• Skale. The Skale network also uses a BLS signature algorithm, according to the same page.
• Other uses named by the draft. It mentions authentication for public key infrastructure and blockchains, aggregated signature chains for PKI and for the Secure Border Gateway Protocol, and consensus protocols, where aggregation reduces bandwidth and storage.

Limitations

This is a teaching implementation, not a production one:

• Slow. The code uses affine coordinates with an inversion in every step, and a plain exponentiation for the final step of the pairing. Optimized libraries use projective coordinates, sparse line multiplications, and fast subgroup checks.
• Not constant time. The multiplication branches on the bits of the secret key. The draft says that implementations of signing should protect the secret key from side-channel attacks, and that they should run in constant time.
• Compressed points only. The code reads and writes the compressed encoding and rejects the uncompressed one.
• One ciphersuite. The code implements the proof of possession ciphersuite. The basic and message augmentation schemes differ only in a few lines and are not included.
• No batch verification and no threshold signatures. Both exist for BLS but are outside this guide.
• A draft, not a standard. The scheme is described in an IETF draft that its own text marks as a work in progress. Interoperating libraries follow a version of that draft, and the earlier versions used a different salt for key generation.

Security Status

Wikipedia states that the scheme is provably secure in the random oracle model, under an assumption about the curve. The draft estimates the security of BLS12-381 at 126 bits. The scheme is deterministic, and the draft points out that this protects against the failures of random nonces, such as the nonce reuse attack on ECDSA. It is also non-malleable.

The weak points are in the use. A public key that has no proof of possession in an aggregation setting allows the rogue key attack. A signature without a subgroup check can make the pairing behave in an undefined way. The domain separation tag must be unique for each use of the hash. The key generation input must be secret and impossible to guess.

BLS signatures rely on the discrete logarithm problem, so a large quantum computer would break them like it breaks the elliptic curve schemes. Wikipedia notes that the Ethereum community considers BLS aggregation a solution for the medium term, and that it expects STARK aggregation to be a replacement over a longer period. For post-quantum signatures, see the Dilithium guide.

FAQ

Why are BLS signatures called short?

A signature is a single point of a group. On BLS12-381 it takes 96 bytes in the variant of this guide, or 48 bytes in the other variant, compared with 64 bytes for ECDSA on a curve of 256 bits. The scheme became known as “short signatures” after the title of the original paper. The real saving comes from aggregation, because the size of an aggregate does not grow with the number of signers.

What is the difference between BLS and ECDSA?

ECDSA needs a fresh random nonce for every signature, and the signatures cannot be added. BLS is deterministic and aggregates. The price is speed. The draft reports about 370 and 2,700 microseconds to sign and verify with BLS, against 37 and 79 for ECDSA. ECDSA verification needs two scalar multiplications, and BLS verification needs two pairings. The ECDSA guide covers the other scheme.

Why is the verification check written as a product of pairings?

Because it needs only one final exponentiation. The check e(pk, H) = e(G1, sigma) would cost two. The product e(-G1, sigma) * e(pk, H) equals 1 exactly when they are equal, and the two Miller loops can be multiplied before the single final exponentiation.

Can I aggregate signatures on different messages?

You can aggregate them. AggregateVerify checks n keys and n messages with n + 1 pairings. For the basic scheme, the draft requires the messages to be distinct, which is its defense against rogue keys. In the proof of possession scheme, every key must come with a proof.

What is a domain separation tag?

It is a fixed string that is mixed into the hash to the curve. Signatures and proofs of possession use different tags, so a proof cannot be used as a signature on the public key, and the reverse. The draft requires unique tags for each hash function of a ciphersuite.

Does BLS resist quantum computers?

It does not resist them. A large quantum computer would solve the discrete logarithm problem on these groups. The Ethereum community treats BLS as a solution for the medium term, as Wikipedia reports. The Dilithium guide covers a post-quantum alternative.

References

1. Boneh, Dan, Gorbunov, Sergey, Wahby, Riad S., Wee, Hoeteck, Wood, Christopher A., and Zhang, Zhenfei. “BLS Signatures.” draft-irtf-cfrg-bls-signature-05, Internet Research Task Force, June 2022. Available at: https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/

2. Sakemi, Yumi, Kobayashi, Tetsutaro, Saito, Tsunekazu, and Wahby, Riad S. “Pairing-Friendly Curves.” draft-irtf-cfrg-pairing-friendly-curves-11, November 2022. Available at: https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/

3. Faz-Hernandez, Armando, Scott, Sam, Sullivan, Nick, Wahby, Riad S., and Wood, Christopher A. “Hashing to Elliptic Curves.” RFC 9380, August 2023. Available at: https://www.rfc-editor.org/rfc/rfc9380

4. Boneh, Dan, Lynn, Ben, and Shacham, Hovav. “Short Signatures from the Weil Pairing.” Journal of Cryptology, 17(4), 2004, pp. 297-319.

5. Boneh, Dan, Gentry, Craig, Lynn, Ben, and Shacham, Hovav. “Aggregate and Verifiably Encrypted Signatures from Bilinear Maps.” Eurocrypt 2003, LNCS 2656, pp. 416-432.

6. Wikipedia contributors. “BLS digital signature.” Wikipedia. Available at: https://en.wikipedia.org/wiki/BLS_digital_signature

7. “BLS 12-381 tests.” Ethereum project, test suite version 0.1.2. Available at: https://github.com/ethereum/bls12-381-tests