#!/usr/bin/env python3 """Generates src/modules/frost_enrollment/vectors.h. These are REGRESSION vectors, not cross-validation vectors. FROST enrollment has no BIP and therefore no published test vectors, and the reference proof of concept (https://github.com/siv2r/frost-enrollment) draws its randomness from secrets.randbits, which is not seedable -- so there is nothing to check the C implementation against. This script therefore re-implements the same math independently, in plain Python, and freezes the result. What that buys is real but bounded: it pins the two tag strings, the exact parameters hash serialization, the share-splitting derivation and the identifier conventions, so that any change to them is a loud, deliberate, vector-breaking change rather than a silent one. It is NOT evidence that the protocol is implemented correctly -- the algebraic invariants in src/modules/frost_enrollment/tests_impl.h are what carry that. The one thing this file does establish independently is the group arithmetic: the elliptic curve operations below are written from the secp256k1 parameters rather than borrowed from the library, so a vector mismatch in the derived public share or the threshold key really is a disagreement between two implementations. Usage: %s > src/modules/frost_enrollment/vectors.h """ import hashlib import sys import textwrap # secp256k1 domain parameters. P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 G = (GX, GY) MAX_PARTICIPANTS = 128 # --- group arithmetic (points are (x, y) or None for infinity) --- def point_add(a, b): if a is None: return b if b is None: return a if a[0] == b[0] and (a[1] + b[1]) % P == 0: return None if a == b: lam = 3 * a[0] * a[0] * pow(2 * a[1], P - 2, P) % P else: lam = (b[1] - a[1]) * pow(b[0] - a[0], P - 2, P) % P x = (lam * lam - a[0] - b[0]) % P return (x, (lam * (a[0] - x) - a[1]) % P) def point_mul(point, scalar): result = None scalar %= ORDER while scalar: if scalar & 1: result = point_add(result, point) point = point_add(point, point) scalar >>= 1 return result def cbytes(point): """33-byte compressed serialization.""" assert point is not None return bytes([2 + (point[1] & 1)]) + point[0].to_bytes(32, "big") # --- hashing --- def tagged_hash(tag, msg): tag_hash = hashlib.sha256(tag.encode()).digest() return hashlib.sha256(tag_hash + tag_hash + msg).digest() def ser32(x): return x.to_bytes(4, "big") # --- the protocol, mirroring src/modules/frost_enrollment/enrollment_impl.h --- def params_hash(thresh_pk, ids, new_id, n_participants, threshold): msg = cbytes(thresh_pk) msg += ser32(n_participants) + ser32(threshold) + ser32(new_id) msg += ser32(len(ids)) for i in sorted(ids): msg += ser32(i) return tagged_hash("FROST enrollment/params_hash", msg) def lagrange_at(ids, my_id, new_id): """The Lagrange basis polynomial of my_id over ids, at the target. Identifier space: the x-coordinate of identifier id is id + 1, so an x-coordinate difference is an identifier difference and the +1 cancels.""" num, deno = 1, 1 for other in ids: if other == my_id: continue num = num * (new_id - other) % ORDER deno = deno * (my_id - other) % ORDER return num * pow(deno, ORDER - 2, ORDER) % ORDER def derive_mask(rand32, ph32, my_id, recipient_id): msg = rand32 + ph32 + ser32(my_id) + ser32(recipient_id) # from_bytes_wrapping: reduce mod the group order rather than reject. return int.from_bytes(tagged_hash("FROST enrollment/share_split", msg), "big") % ORDER def shares_gen(secshare, thresh_pk, ids, my_id, new_id, n_participants, threshold, secrand32): ph32 = params_hash(thresh_pk, ids, new_id, n_participants, threshold) v = lagrange_at(ids, my_id, new_id) * secshare % ORDER rand32 = bytes( a ^ b for a, b in zip( tagged_hash("FROST enrollment/share_split", secrand32), secshare.to_bytes(32, "big"), ) ) out = [0] * len(ids) my_pos = ids.index(my_id) for j, recipient in enumerate(ids): if j == my_pos: continue out[j] = derive_mask(rand32, ph32, my_id, recipient) v = (v - out[j]) % ORDER out[my_pos] = v return out, ph32 def trusted_dealer_keygen(thresh_sk, n_participants, threshold): """The frost module's trusted dealer (src/modules/frost/keygen_impl.h).""" coeffs = [] for i in range(1, threshold): h = tagged_hash("BIP0445/trusted/keygen", thresh_sk.to_bytes(32, "big") + ser32(i)) c = int.from_bytes(h, "big") assert 0 < c < ORDER coeffs.append(c) secshares = [] for i in range(n_participants): x = i + 1 share = 0 for c in coeffs: share = (share * x + c) % ORDER share = (share * x + thresh_sk) % ORDER assert share != 0 secshares.append(share) return secshares, point_mul(G, thresh_sk), [point_mul(G, s) for s in secshares] def run_case(thresh_sk, n_participants, threshold, ids, new_id, seeds): secshares, thresh_pk, pubshares = trusted_dealer_keygen(thresh_sk, n_participants, threshold) ph32 = params_hash(thresh_pk, ids, new_id, n_participants, threshold) shares = [] for k, my_id in enumerate(ids): out, ph = shares_gen( secshares[my_id], thresh_pk, ids, my_id, new_id, n_participants, threshold, seeds[k] ) assert ph == ph32 shares.append(out) # Round 1.2: helper j sums entry j of every helper's output. sigmas = [sum(shares[i][j] for i in range(len(ids))) % ORDER for j in range(len(ids))] # Round 2, and the independent check that the result really is f(x_new). new_secshare = sum(sigmas) % ORDER expected = sum(lagrange_at(ids, i, new_id) * secshares[i] for i in ids) % ORDER assert new_secshare == expected new_pubshare = None for i in ids: new_pubshare = point_add(new_pubshare, point_mul(pubshares[i], lagrange_at(ids, i, new_id))) assert new_pubshare == point_mul(G, new_secshare) return { "n_participants": n_participants, "threshold": threshold, "ids": ids, "new_id": new_id, "thresh_pk": thresh_pk, "pubshares": [pubshares[i] for i in ids], "secshares": [secshares[i] for i in ids], "seeds": seeds, "params_hash": ph32, "shares": shares, "sigmas": sigmas, "new_secshare": new_secshare, "new_pubshare": new_pubshare, } # --- C emission --- def byte_array(b): return "{ %s }" % ", ".join("0x%02X" % x for x in b) def scalar_array(x): return byte_array(x.to_bytes(32, "big")) def indent(s, level=1): return textwrap.indent(s, 4 * level * " ") def emit_case(c): n_ids = len(c["ids"]) lines = [] lines.append("%d, %d, %d, %d," % (c["n_participants"], c["threshold"], n_ids, c["new_id"])) lines.append("{ %s }," % ", ".join(str(i) for i in c["ids"])) lines.append("%s," % byte_array(cbytes(c["thresh_pk"]))) lines.append("{ %s }," % ", ".join(byte_array(cbytes(p)) for p in c["pubshares"])) lines.append("{ %s }," % ", ".join(scalar_array(s) for s in c["secshares"])) lines.append("{ %s }," % ", ".join(byte_array(s) for s in c["seeds"])) lines.append("%s," % byte_array(c["params_hash"])) lines.append( "{ %s }," % ", ".join( "{ %s }" % ", ".join("0x%02X" % b for s in row for b in s.to_bytes(32, "big")) for row in c["shares"] ) ) lines.append( "{ %s }," % ", ".join("0x%02X" % b for s in c["sigmas"] for b in s.to_bytes(32, "big")) ) lines.append("%s," % scalar_array(c["new_secshare"])) lines.append("%s" % byte_array(cbytes(c["new_pubshare"]))) return "{\n" + indent("\n".join(lines)) + "\n}," # Fixed inputs. Nothing here is random at run time: the whole point is that # regenerating this file without an intentional change reproduces it byte for # byte. CASES = [ # A 2-of-3 group enrolling a fourth participant with the minimum helper # set. The base case, and the one the module documentation walks through. # This key and the next have EVEN Y, the last two odd Y; among the derived # public shares, case 3 is the even one and the rest are odd. Nothing in # enrollment depends on either parity -- unlike frost signing, it never # takes an x-only view of a key -- so this is coverage rather than a # distinction the code makes. run_case() in this file prints nothing about # parity; the values above were read off the generated vectors, so treat # this comment as documentation of the current set rather than a # constraint on it. dict( thresh_sk=0x0202020202020202020202020202020202020202020202020202020202020202, n_participants=3, threshold=2, ids=[0, 1], new_id=3, seeds=[bytes([0x10 + i] * 32) for i in range(2)], ), # The same group with an oversized helper set: u = 3 > t = 2. The resulting # share must be the one the u = 2 case produces, which the C test checks # separately; here it is simply frozen. dict( thresh_sk=0x0202020202020202020202020202020202020202020202020202020202020202, n_participants=3, threshold=2, ids=[0, 1, 2], new_id=3, seeds=[bytes([0x20 + i] * 32) for i in range(3)], ), # Repair: a 3-of-5 group reproducing participant 2's lost share. The helper # set is deliberately unsorted, to pin that the parameters hash # canonicalizes identifiers while the share buffers follow the caller's # order. dict( thresh_sk=0x02030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F2021, n_participants=5, threshold=3, ids=[4, 0, 3], new_id=2, seeds=[bytes([0x30 + i] * 32) for i in range(3)], ), # A larger enrollment, 4-of-6 to 4-of-7, at the largest threshold and # helper count in this set. dict( thresh_sk=0x1122334455667788990011223344556677889900112233445566778899001122, n_participants=6, threshold=4, ids=[0, 2, 3, 5], new_id=6, seeds=[bytes([0x40 + i] * 32) for i in range(4)], ), ] def main(): cases = [run_case(**c) for c in CASES] max_ids = max(len(c["ids"]) for c in cases) out = """/** * Automatically generated by tools/test_vectors_frost_enrollment_generate.py. * * REGRESSION vectors, not cross-validation vectors. FROST enrollment has no * BIP and no published test vectors, and the reference proof of concept * (https://github.com/siv2r/frost-enrollment) draws its randomness from * secrets.randbits, which is not seedable, so there is nothing to check * against. The generator re-implements the math independently in Python and * freezes the result. * * What these pin: the two tag strings ("FROST enrollment/params_hash" and * "FROST enrollment/share_split"), the parameters hash serialization, the * share-splitting derivation, and the identifier conventions. Changing any of * them is a vector-breaking change. What they do NOT establish is protocol * correctness -- the algebraic invariants in tests_impl.h carry that. * * Used by the tests in src/modules/frost_enrollment/tests_impl.h. */ #ifndef SECP256K1_MODULE_FROST_ENROLLMENT_VECTORS_H #define SECP256K1_MODULE_FROST_ENROLLMENT_VECTORS_H #define FROST_ENROLLMENT_VEC_MAX_IDS %d struct frost_enrollment_vec_case { /* Parameters. */ size_t n_participants; uint32_t threshold; size_t n_ids; uint32_t new_id; uint32_t ids[FROST_ENROLLMENT_VEC_MAX_IDS]; /* Group key material, aligned with ids. */ unsigned char thresh_pk33[33]; unsigned char pubshares33[FROST_ENROLLMENT_VEC_MAX_IDS][33]; unsigned char secshares32[FROST_ENROLLMENT_VEC_MAX_IDS][32]; /* Round 1.1 inputs and outputs. shares32[i] is helper ids[i]'s output * buffer, aligned with ids. */ unsigned char session_secrand32[FROST_ENROLLMENT_VEC_MAX_IDS][32]; unsigned char params_hash32[32]; unsigned char shares32[FROST_ENROLLMENT_VEC_MAX_IDS][FROST_ENROLLMENT_VEC_MAX_IDS * 32]; /* Round 1.2 and round 2 outputs. */ unsigned char sigmas32[FROST_ENROLLMENT_VEC_MAX_IDS * 32]; unsigned char new_secshare32[32]; unsigned char new_pubshare33[33]; }; static const struct frost_enrollment_vec_case frost_enrollment_vec_cases[%d] = { """ % ( max_ids, len(cases), ) for c in cases: out += indent(emit_case(c)) + "\n" out += "};\n\n#endif /* SECP256K1_MODULE_FROST_ENROLLMENT_VECTORS_H */\n" sys.stdout.write(out) if __name__ == "__main__": main()