3c962b00cc
The last of the review findings, plus the comment and structure fixes it
listed.
The example's repair run used the pre-enrollment participant count.
Two blocks earlier the example teaches that every participant must
update its record of n from 3 to 4 after an enrollment, and the
signing session duly uses N_PARTICIPANTS_AFTER. Then enroll() -- which
hard-coded N_PARTICIPANTS -- ran the repair at n = 3. It worked only
because the Lagrange math never involves n and every party in this
single-process demo passed the same stale value.
In a real post-enrollment repair it would not. n is bound into the
parameters hash, so helpers feeding their updated n = 4 into
shares_gen while the requester feeds n = 3 abort round 1.2 with no
visible cause. enroll() now takes n_participants as a parameter, the
repair passes N_PARTICIPANTS_AFTER, and both the function's contract
comment and the repair call site say why. The repaired share is still
byte-identical to the original, which is the point: n changes the
hash, not the arithmetic.
The example leaked secrets on its failure paths.
enroll() erased the delta and sigma buffers only on success; four
early returns left them live. sign_and_verify() returned from three
places without erasing already-generated secnonces. Both now route
every exit through a cleanup block. This example is otherwise more
careful about erasure than its siblings, so the asymmetry was exactly
what a reader copying it would carry into production -- on the fault
paths where hygiene matters most.
The double-wipe of session_secrand is gone with it: shares_gen and
nonce_gen both wipe the seed on every path, and doing it again read
as uncertainty about the contract. The comment now states the
contract instead. The fill_random failure path does erase, since
nothing else has touched the buffer there.
The example's mismatch message asserted a cause it cannot know.
It printed "Helper %u disagrees about the enrollment parameters" for
what may equally be a corrupted share, per the previous commit's
finding. It now says the helper "contributed a share this helper
cannot use", with a comment noting that share_agg does not
distinguish the two causes so neither can the message.
Comment and structure fixes, all noted in the review:
- The vector generator claimed case 4 was "the only case whose DERIVED
public share has odd Y". It is not -- cases 1, 2 and 4 are odd and
case 3 is even. The comment existed to justify a coverage choice and
misinformed; both parity comments now describe the set accurately and
say they document it rather than constrain it. Regenerating vectors.h
still reproduces it byte for byte.
- The secp256k1_frost_sort_ids declaration in frost/session.h no longer
duplicates the definition's doc comment, which was two copies to keep
in sync. It says what the function is for and points at the
definition for the contract.
- The t >= 2 rationale was stated in full in three places. The impl now
states the conclusion and names frost_enrollment.md as the single
place to edit if the policy moves.
- The ctime_tests comments read ambiguously ("the parameters hash is
public, the delta values are not" against a header calling deltas
secret), and computing direct_hash without asserting anything invited
a "forgotten assertion" reading. Both are now explicit.
- The example moves next to frost_example in Makefile.am rather than
after iceberg, matching the FROST-stack grouping used in
configure.ac, ci.sh, ci.yml and README.
- frost_enrollment.md now distinguishes what is unstable (the C API)
from what is frozen (the wire-visible encodings), which the two
statements together previously left easy to conflate.
Not fixed, deliberately, and now recorded where the tree can see it: the
plan called for a CHANGELOG.md entry. That file states in its first two
lines that it is upstream libsecp256k1's changelog and not this fork's,
and none of frost, chilldkg, iceberg or prefractal has an entry. Adding
the first one is a decision about all five modules, not this one. The
README link is the fork's actual convention for announcing a module and
is in place.
Verification: autotools builds warning-free and `make check` is 12/12
including the example; ctime_tests is clean under valgrind; `make dist`
carries all nine frost_enrollment files; CMake with examples builds
warning-free and ctest is 542/542; the example source is clean under
gcc -std=c89 -pedantic -Wall -Wextra; regenerating vectors.h reproduces
it byte for byte.
Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
364 lines
13 KiB
Python
Executable File
364 lines
13 KiB
Python
Executable File
#!/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()
|