Files
mpcvm/test/mpcvm_determinism_test.cpp
zeekay 9777ff09d2 v0.62 — per-slot fan-out + parallel reduction; 18.6x Metal speedup on xlarge
Replaces v0.61.1's `if (tid != 0u) return;` scalar pattern with per-slot
parallel dispatch in the bulk paths. Determinism preserved by canonical
slot ordering (open-addressing hash) plus intra-threadgroup prefix sum
for byte-equal share_id allocation.

Kernel split (per backend):
  1. mpcvm_ceremony_apply  (1x1x1)         - Phase 1+2 ops apply, serial
  2. mpcvm_ceremony_sweep  (256 threads)   - Phase 3 sweep + share emit
                                              with intra-tg prefix sum
  3. mpcvm_compute_leaves  (per-slot grid) - parallel keccak per leaf
  4. mpcvm_compose_root    (1x1x1)         - serial fold over precomputed
                                              leaf hashes + state root

emit_keygen_shares replaces O(N_contribs) linear scan with O(1) hash
lookup via contribution_locate, eliminating the dominant O(N**2) cost.

Speedups (v0.62 vs v0.61.1, mean ms):
  Metal:   FROST kg 30.6x, FROST sg 4.2x, CGGMP21 kg 3.8x,
           CGGMP21 sg 7.1x, Ringtail dkg 4.2x, xlarge 18.6x
  WGPU:    FROST kg 2.6x, FROST sg 2.8x, CGGMP21 kg 2.8x,
           CGGMP21 sg 4.1x, Ringtail dkg 4.3x, xlarge 8.8x

Determinism: all 21 tests pass byte-equal CPU<->Metal<->WGSL across
small/medium/large/xlarge plus the original 6 cases (FROST keygen,
CGGMP21 keygen, replay drop, timeout sweep, 3-way concurrent, empty
round). v0.62 BENCHMARKS.md target met (>=5x Metal speedup on xlarge).
2026-04-26 21:47:45 -07:00

503 lines
19 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
// Copyright (C) 2026, Lux Partners Limited. All rights reserved.
// SPDX-License-Identifier: Apache-2.0
//
// mpcvm_determinism_test.cpp — cross-backend determinism harness.
//
// Compares CPU reference vs GPU engine across canonical workloads:
// 1. FROST 7-of-10 keygen (3 rounds)
// 2. FROST 7-of-10 sign (2 rounds)
// 3. CGGMP21 5-of-9 keygen (3 rounds)
// 4. Replay dropped
// 5. Timeout sweep
// 6. Concurrent ceremonies (3 different kinds)
// 7. Empty round deterministic non-zero
// 8. Two engines run-twice — bytes match
//
// The GPU side is selected at link time by the platform-specific
// MPCVMGPUEngine::create() implementation.
#include "lux/mpcvm/mpcvm_gpu_engine.hpp"
#include "lux/mpcvm/mpcvm_cpu_reference.hpp"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace mpcvm::gpu;
namespace {
int g_passed = 0;
int g_failed = 0;
#define EXPECT(name, cond) \
do { \
if (!(cond)) { \
std::printf(" FAIL[%s]: %s\n", (name), #cond); \
std::fflush(stdout); \
++g_failed; \
return; \
} \
} while (0)
#define PASS(name) \
do { \
std::printf(" ok : %s\n", (name)); \
std::fflush(stdout); \
++g_passed; \
} while (0)
MPCVMRoundDescriptor make_desc(uint64_t round, uint64_t now_ns = 1700000000000000000ULL,
uint64_t epoch = 0)
{
MPCVMRoundDescriptor d{};
d.chain_id = 1u;
d.round = round;
d.timestamp_ns = now_ns;
d.epoch = epoch;
d.mode = static_cast<uint32_t>(MPCVMTransitionMode::FullRound);
d.closing_flag = 1u;
return d;
}
CeremonyOp make_begin(uint64_t cid, uint32_t threshold, uint32_t total, uint32_t kind,
uint64_t deadline = 2000000000000000000ULL, uint8_t fill = 0xAB)
{
CeremonyOp op{};
op.ceremony_id = cid;
op.deadline_ns = deadline;
op.kind = static_cast<uint32_t>(CeremonyOpKind::Begin);
op.ceremony_kind = kind;
op.threshold = threshold;
op.total_participants = total;
for (auto& b : op.subject) b = uint8_t(fill ^ 1u);
for (auto& b : op.ceremony_seed) b = fill;
return op;
}
ContributionOp make_contribution(uint64_t cid, uint32_t round, uint32_t holder,
uint8_t fill = 0xCC, uint32_t plen = 64u)
{
ContributionOp op{};
op.ceremony_id = cid;
op.holder_addr = 0xA00000000ULL + holder;
op.round = round;
op.holder_index = holder;
op.payload_len = plen;
for (uint32_t k = 0; k < plen; ++k) op.payload[k] = uint8_t(fill ^ k);
return op;
}
struct WorkloadResult {
uint8_t ceremony_root[32];
uint8_t key_share_root[32];
uint8_t contribution_root[32];
uint8_t mpcvm_state_root[32];
uint32_t ceremony_apply_count;
uint32_t contribution_apply_count;
uint32_t round_advance_count;
uint32_t finalized_this_round;
uint32_t failed_this_round;
uint32_t active_ceremony_count;
uint32_t key_share_count;
static WorkloadResult from(const MPCVMTransitionResult& r) {
WorkloadResult w{};
std::memcpy(w.ceremony_root, r.ceremony_root, 32);
std::memcpy(w.key_share_root, r.key_share_root, 32);
std::memcpy(w.contribution_root, r.contribution_root, 32);
std::memcpy(w.mpcvm_state_root, r.mpcvm_state_root, 32);
w.ceremony_apply_count = r.ceremony_apply_count;
w.contribution_apply_count = r.contribution_apply_count;
w.round_advance_count = r.round_advance_count;
w.finalized_this_round = r.finalized_this_round;
w.failed_this_round = r.failed_this_round;
w.active_ceremony_count = r.active_ceremony_count;
w.key_share_count = r.key_share_count;
return w;
}
bool equals(const WorkloadResult& o) const {
return std::memcmp(ceremony_root, o.ceremony_root, 32) == 0
&& std::memcmp(key_share_root, o.key_share_root, 32) == 0
&& std::memcmp(contribution_root, o.contribution_root, 32) == 0
&& std::memcmp(mpcvm_state_root, o.mpcvm_state_root, 32) == 0
&& ceremony_apply_count == o.ceremony_apply_count
&& contribution_apply_count == o.contribution_apply_count
&& round_advance_count == o.round_advance_count
&& finalized_this_round == o.finalized_this_round
&& failed_this_round == o.failed_this_round
&& active_ceremony_count == o.active_ceremony_count
&& key_share_count == o.key_share_count;
}
};
WorkloadResult run_cpu(const MPCVMRoundDescriptor& desc,
const std::vector<CeremonyOp>& cer_ops,
const std::vector<ContributionOp>& cnt_ops)
{
auto state = ref::MPCVMReferenceState::empty();
auto r = ref::run_reference(state, desc, cer_ops, cnt_ops);
return WorkloadResult::from(r);
}
WorkloadResult run_gpu(MPCVMGPUEngine* engine,
const MPCVMRoundDescriptor& desc,
const std::vector<CeremonyOp>& cer_ops,
const std::vector<ContributionOp>& cnt_ops)
{
auto h = engine->begin_round(desc);
if (!cer_ops.empty()) engine->push_ceremony_ops(h, cer_ops);
if (!cnt_ops.empty()) engine->push_contribution_ops(h, cnt_ops);
auto r = engine->run_until_done(h);
engine->end_round(h);
return WorkloadResult::from(r);
}
void test_frost_keygen_round0(MPCVMGPUEngine* engine)
{
std::vector<CeremonyOp> begins{
make_begin(42u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen)),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 7u; ++i) r0.push_back(make_contribution(42u, 0u, i, 0xC0u));
auto desc0 = make_desc(1u);
auto cpu = run_cpu(desc0, begins, r0);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc0, begins, r0);
EXPECT("frost.kg0.match", cpu.equals(gpu));
} else {
auto cpu2 = run_cpu(desc0, begins, r0);
EXPECT("frost.kg0.cpu_det", cpu.equals(cpu2));
}
PASS("FROST keygen round 0 — CPU<->GPU match");
}
void test_cggmp21_keygen_round0(MPCVMGPUEngine* engine)
{
std::vector<CeremonyOp> begins{
make_begin(7u, 5u, 9u, static_cast<uint32_t>(CeremonyKind::Cggmp21Keygen)),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(7u, 0u, i, 0xA0u));
auto desc0 = make_desc(1u);
auto cpu = run_cpu(desc0, begins, r0);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc0, begins, r0);
EXPECT("cgg.kg0.match", cpu.equals(gpu));
} else {
auto cpu2 = run_cpu(desc0, begins, r0);
EXPECT("cgg.kg0.cpu_det", cpu.equals(cpu2));
}
PASS("CGGMP21 keygen round 0 — CPU<->GPU match");
}
void test_replay_dropped(MPCVMGPUEngine* engine)
{
std::vector<CeremonyOp> begins{
make_begin(11u, 3u, 5u, static_cast<uint32_t>(CeremonyKind::FrostSign)),
};
std::vector<ContributionOp> ops{
make_contribution(11u, 0u, 0u),
make_contribution(11u, 0u, 0u, 0xFFu),
};
auto desc = make_desc(1u);
auto cpu = run_cpu(desc, begins, ops);
EXPECT("rp.cpu.applied", cpu.contribution_apply_count == 1u);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc, begins, ops);
EXPECT("rp.match", cpu.equals(gpu));
}
PASS("Replay dropped");
}
void test_timeout(MPCVMGPUEngine* engine)
{
std::vector<CeremonyOp> begins{
make_begin(13u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen),
/*deadline=*/1000ULL),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(13u, 0u, i));
auto desc = make_desc(1u, /*now=*/2000ULL);
auto cpu = run_cpu(desc, begins, r0);
EXPECT("to.cpu.failed", cpu.failed_this_round == 1u);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc, begins, r0);
EXPECT("to.match", cpu.equals(gpu));
}
PASS("Timeout sweep");
}
void test_concurrent_ceremonies(MPCVMGPUEngine* engine)
{
std::vector<CeremonyOp> begins{
make_begin(1u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen),
2000000000000000000ULL, 0xA0),
make_begin(2u, 5u, 9u, static_cast<uint32_t>(CeremonyKind::Cggmp21Keygen),
2000000000000000000ULL, 0xB0),
make_begin(3u, 3u, 5u, static_cast<uint32_t>(CeremonyKind::FrostSign),
2000000000000000000ULL, 0xC0),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 7u; ++i) r0.push_back(make_contribution(1u, 0u, i, 0xA0u));
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(2u, 0u, i, 0xB0u));
for (uint32_t i = 0; i < 3u; ++i) r0.push_back(make_contribution(3u, 0u, i, 0xC0u));
auto desc = make_desc(1u);
auto cpu = run_cpu(desc, begins, r0);
EXPECT("conc.cpu.advance", cpu.round_advance_count == 3u);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc, begins, r0);
EXPECT("conc.match", cpu.equals(gpu));
}
PASS("3 concurrent ceremonies");
}
void test_empty_round(MPCVMGPUEngine* engine)
{
auto desc = make_desc(1u);
auto cpu = run_cpu(desc, {}, {});
bool nz = false;
for (auto b : cpu.mpcvm_state_root) if (b != 0) { nz = true; break; }
EXPECT("empty.cpu.nz", nz);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc, {}, {});
EXPECT("empty.match", cpu.equals(gpu));
}
PASS("Empty round deterministic non-zero");
}
// Build a sized workload of `count` finalizing FROST 7-of-10 keygens. Each
// ceremony has 7 contributions for round 0; the sweep advances round 0->1.
// Used to exercise per-slot fan-out at scale.
void make_sized_workload(uint64_t count, uint64_t cid_base,
std::vector<CeremonyOp>& begins,
std::vector<ContributionOp>& contribs)
{
for (uint64_t i = 0; i < count; ++i) {
uint64_t cid = cid_base + i;
begins.push_back(make_begin(cid, 7u, 10u,
static_cast<uint32_t>(CeremonyKind::FrostKeygen),
/*deadline=*/2000000000000000000ULL,
/*fill=*/uint8_t(0xC0u + (cid & 0x0Fu))));
for (uint32_t h = 0; h < 7u; ++h) {
contribs.push_back(make_contribution(cid, 0u, h,
/*fill=*/uint8_t(0xC0u + (cid & 0x0Fu))));
}
}
}
void test_sized(MPCVMGPUEngine* engine, const char* label, uint64_t count)
{
std::vector<CeremonyOp> begins;
std::vector<ContributionOp> contribs;
make_sized_workload(count, 1000u, begins, contribs);
auto desc = make_desc(1u);
auto cpu = run_cpu(desc, begins, contribs);
if (engine != nullptr) {
auto gpu = run_gpu(engine, desc, begins, contribs);
bool eq = cpu.equals(gpu);
if (!eq) {
std::printf(" diff[%s]: applied cer cpu=%u gpu=%u cnt cpu=%u gpu=%u adv cpu=%u gpu=%u\n",
label,
cpu.ceremony_apply_count, gpu.ceremony_apply_count,
cpu.contribution_apply_count, gpu.contribution_apply_count,
cpu.round_advance_count, gpu.round_advance_count);
}
EXPECT(label, eq);
}
PASS(label);
}
void test_two_engines_match(MPCVMGPUEngine* engine)
{
if (engine == nullptr) {
PASS("two-engines (skipped — no GPU)");
return;
}
auto a = MPCVMGPUEngine::create();
auto b = MPCVMGPUEngine::create();
EXPECT("twoeng.a", a != nullptr);
EXPECT("twoeng.b", b != nullptr);
std::vector<CeremonyOp> begins{
make_begin(99u, 5u, 8u, static_cast<uint32_t>(CeremonyKind::FrostKeygen),
2000000000000000000ULL, 0x55),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(99u, 0u, i, 0x55));
auto desc = make_desc(1u);
auto ra = run_gpu(a.get(), desc, begins, r0);
auto rb = run_gpu(b.get(), desc, begins, r0);
EXPECT("twoeng.match", ra.equals(rb));
PASS("Two engines bytewise identical");
}
} // namespace
#ifdef LUX_MPCVM_ENABLE_WGPU
namespace {
void run_wgpu_workload_set(MPCVMGPUEngine* wgpu)
{
if (wgpu == nullptr) {
std::printf(" note: WGPU engine factory returned null (no adapter?)\n");
return;
}
std::printf(" wgpu device: %s\n", wgpu->device_name());
auto dump_root = [](const char* tag, const uint8_t* r) {
std::printf(" %s: ", tag);
for (int i = 0; i < 8; ++i) std::printf("%02x", r[i]);
std::printf("..\n");
};
auto compare = [&](const char* label,
const std::vector<CeremonyOp>& begins,
const std::vector<ContributionOp>& cnts,
const MPCVMRoundDescriptor& desc)
{
auto cpu = run_cpu(desc, begins, cnts);
auto gpuw = run_gpu(wgpu, desc, begins, cnts);
bool eq = cpu.equals(gpuw);
if (!eq) {
std::printf(" diff[%s]: applied cer cpu=%u wgpu=%u cnt cpu=%u wgpu=%u adv cpu=%u wgpu=%u fail cpu=%u wgpu=%u\n",
label,
cpu.ceremony_apply_count, gpuw.ceremony_apply_count,
cpu.contribution_apply_count, gpuw.contribution_apply_count,
cpu.round_advance_count, gpuw.round_advance_count,
cpu.failed_this_round, gpuw.failed_this_round);
dump_root("cpu cer", cpu.ceremony_root);
dump_root("wgp cer", gpuw.ceremony_root);
dump_root("cpu cnt", cpu.contribution_root);
dump_root("wgp cnt", gpuw.contribution_root);
dump_root("cpu shr", cpu.key_share_root);
dump_root("wgp shr", gpuw.key_share_root);
dump_root("cpu st", cpu.mpcvm_state_root);
dump_root("wgp st", gpuw.mpcvm_state_root);
}
EXPECT(label, eq);
PASS(label);
};
// 1. FROST 7-of-10 keygen round 0.
{
std::vector<CeremonyOp> begins{
make_begin(142u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen)),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 7u; ++i) r0.push_back(make_contribution(142u, 0u, i, 0xC1u));
compare("WGPU frost.kg0", begins, r0, make_desc(1u));
}
// 2. CGGMP21 5-of-9 keygen round 0.
{
std::vector<CeremonyOp> begins{
make_begin(207u, 5u, 9u, static_cast<uint32_t>(CeremonyKind::Cggmp21Keygen)),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(207u, 0u, i, 0xA1u));
compare("WGPU cgg.kg0", begins, r0, make_desc(1u));
}
// 3. Replay dropped.
{
std::vector<CeremonyOp> begins{
make_begin(311u, 3u, 5u, static_cast<uint32_t>(CeremonyKind::FrostSign)),
};
std::vector<ContributionOp> ops{
make_contribution(311u, 0u, 0u),
make_contribution(311u, 0u, 0u, 0xFEu),
};
compare("WGPU replay.dropped", begins, ops, make_desc(1u));
}
// 4. Timeout sweep.
{
std::vector<CeremonyOp> begins{
make_begin(413u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen),
/*deadline=*/1000ULL),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(413u, 0u, i));
compare("WGPU timeout", begins, r0, make_desc(1u, /*now=*/2000ULL));
}
// 5. 3-way concurrent ceremonies.
{
std::vector<CeremonyOp> begins{
make_begin(501u, 7u, 10u, static_cast<uint32_t>(CeremonyKind::FrostKeygen),
2000000000000000000ULL, 0xA1),
make_begin(502u, 5u, 9u, static_cast<uint32_t>(CeremonyKind::Cggmp21Keygen),
2000000000000000000ULL, 0xB1),
make_begin(503u, 3u, 5u, static_cast<uint32_t>(CeremonyKind::FrostSign),
2000000000000000000ULL, 0xC1),
};
std::vector<ContributionOp> r0;
for (uint32_t i = 0; i < 7u; ++i) r0.push_back(make_contribution(501u, 0u, i, 0xA1u));
for (uint32_t i = 0; i < 5u; ++i) r0.push_back(make_contribution(502u, 0u, i, 0xB1u));
for (uint32_t i = 0; i < 3u; ++i) r0.push_back(make_contribution(503u, 0u, i, 0xC1u));
compare("WGPU 3-way concurrent", begins, r0, make_desc(1u));
}
// 6. Empty round.
{
compare("WGPU empty round", {}, {}, make_desc(1u));
}
// 7-10. Sized workloads (per-slot fan-out at scale).
auto sized = [&](const char* label, uint64_t count) {
std::vector<CeremonyOp> begins;
std::vector<ContributionOp> contribs;
make_sized_workload(count, 2000u, begins, contribs);
compare(label, begins, contribs, make_desc(1u));
};
sized("WGPU sized.small (10)", 10u);
sized("WGPU sized.medium (50)", 50u);
sized("WGPU sized.large (100)", 100u);
sized("WGPU sized.xlarge (200)", 200u);
}
} // namespace
#endif // LUX_MPCVM_ENABLE_WGPU
int main(int /*argc*/, char** /*argv*/)
{
setvbuf(stdout, nullptr, _IOLBF, 0);
std::printf("[mpcvm_determinism_test] starting\n");
auto engine = MPCVMGPUEngine::create();
if (engine == nullptr) {
std::printf(" note: no GPU backend — running CPU-only path\n");
} else {
std::printf(" device: %s\n", engine->device_name());
}
test_frost_keygen_round0(engine.get());
test_cggmp21_keygen_round0(engine.get());
test_replay_dropped(engine.get());
test_timeout(engine.get());
test_concurrent_ceremonies(engine.get());
test_empty_round(engine.get());
// v0.62: per-slot fan-out determinism at scale.
// Sizes mirror the benchmark suite (small/medium/large/xlarge), bounded
// by arena (256 ceremonies × 4096 contributions per round). xlarge
// tests an N=200 workload that uses 1400 contributions in round 0.
test_sized(engine.get(), "sized.small (10 ceremonies)", 10u);
test_sized(engine.get(), "sized.medium (50 ceremonies)", 50u);
test_sized(engine.get(), "sized.large (100 ceremonies)", 100u);
test_sized(engine.get(), "sized.xlarge (200 ceremonies)", 200u);
test_two_engines_match(engine.get());
#ifdef LUX_MPCVM_ENABLE_WGPU
std::printf("[mpcvm_determinism_test] WGPU 4-way determinism\n");
auto wgpu_engine = create_mpcvm_wgpu_engine();
run_wgpu_workload_set(wgpu_engine.get());
#endif
std::printf("[mpcvm_determinism_test] passed=%d failed=%d\n",
g_passed, g_failed);
return g_failed == 0 ? 0 : 1;
}