Introduction

This document is a companion to the Post-Quantum Safety Analysis of the Logos Bedrock Layer, which identified the quantum-vulnerable components across the Bedrock stack — Ed25519 signatures at five sites, the four coupled Groth16/BN254 circuits, and the libp2p TLS transport — and classified each under the shared threat-model taxonomy. This document evaluates specific post-quantum candidate primitives for those components: digital signature schemes, zero-knowledge proof systems, and the key encapsulation mechanism for the shared transport.

The purpose of this document is to present the pros and cons of candidate primitives along the relevant trade-off axes — not to select one, and not to recommend any particular combination. Deployment decisions (security category per component, lattice-vs-non-lattice posture, specific candidate selection, multi-signature construction, ZK compression strategy) are deferred to dedicated decision documents and RFCs. Critically, several of these decisions cannot be made by Bedrock in isolation: the ZK proof system is a single coupled choice spanning four circuits across Cryptarchia, Blend, and Mantle, and the transport KEM is shared with Blend. The analysis below is intended as input to those decisions, providing a consistent comparison baseline aligned with the companion Post-Quantum Primitive Candidates for the Blend Protocol.

This document deliberately reuses the Blend candidate framework — the same NIST Category 3 comparison reference point, the same candidate algorithms, and the same hardness-assumption families — and extends it with the candidates that Bedrock’s structure additionally admits (stateful hash-based signatures for single-use keys, and threshold/aggregating constructions for the multi-signature channel operations). Where a candidate’s evaluation is identical to the Blend treatment, we summarize and cross-reference rather than repeat.

<aside> 💡

On performance figures. Absolute timings are platform- and implementation-dependent and are reported in the shared companion benchmark document — measured on a Raspberry Pi 5 (the validator baseline) and an Apple M3 MacBook, through three independent implementations (the liboqs C library, the pure-Rust RustCrypto crates, and aws-lc-rs) and two TLS stacks (OpenSSL and rustls, the stack the Logos libp2p transport uses) — not here. Throughout this document, performance is characterized only by order of magnitude (microsecond / millisecond / sub-second) and by relative comparison between candidates, both of which the benchmark shows to be stable across platforms and implementations. The benchmark additionally quantifies the worst-case latency of the operations whose running time is intrinsically variable (rejection-sampled signing and key generation) — the figure that matters wherever a Bedrock operation sits inside a deadline, such as the leader’s slot budget. Sizes (public key, signature, proof) are deterministic functions of the parameter set and are reported in full.

</aside>

The evaluation criteria are driven by Bedrock’s specific constraints, which differ from Blend’s in instructive ways:

• Per-block-header overhead (consensus bandwidth). Every Cryptarchia block header carries a leader_key (Ed25519 public key), a Proof of Leadership (Groth16 proof), and a block signature (Ed25519). The block proposal is a fixed-size message (33,129 bytes) padded to preserve indistinguishability in the Blend Protocol; growth in the header’s cryptographic fields directly enlarges every proposal broadcast through the network.
• Per-transaction overhead (permanent storage gas). Mantle charges a permanent storage gas proportional to the encoded size of the signed transaction. Signature and proof sizes therefore translate directly into a recurring on-chain fee, not merely a one-time bandwidth cost. This makes Bedrock more size-sensitive per artifact than Blend, where headers are ephemeral.
• Verification on the block-validation path. Block header validation verifies the PoL proof and the block signature inline, and Mantle transaction validation verifies every ZkSignature and channel signature. Unlike Blend’s asynchronous PoQ pipeline, these verifications gate block acceptance, so verification speed (and batchability) matters on the critical path.
• Proving latency for consensus timeliness. The PoL proof must be generated by the leader during block construction within the slot; proving latency directly affects consensus timeliness, more tightly than Blend’s PoQ.
• Single-use versus reusable keys. The leader_key is single-use (a fresh key per block), as is the one-time claim key in PoCl. This opens the candidate space to stateful hash-based signatures, which are impractical for reusable identities but well-suited to one-time keys. The provider_id, accredited_keys, and zk_id are long-lived reusable identities and require general-purpose schemes.
• Multi-signature surface. CHANNEL_CONFIG and CHANNEL_WITHDRAW require threshold-of-N authorization, currently as N independent signatures. The migrated construction may keep N independent PQ signatures (linear overhead) or adopt a threshold/aggregating PQ construction (constant size, lower maturity).
• Four-circuit ZK coupling. PoL, PoQ (Blend), ZkSignature, and PoCl share one proof system, one hardness assumption, and one trusted-setup pipeline. The ZK candidate choice is a single stack-wide decision; this document characterizes the per-artifact cost it imposes at each Bedrock site.
• Assumption diversity. As in Blend, where the primary candidate relies on lattice hardness, backup candidates from code-based and hash-based families should be identified to hedge a single-assumption break.

Migration Phases

The Bedrock analysis adopts the same four-phase threat framing as the Blend baseline, with one structural difference: Bedrock has no per-message confidentiality surface, so the message-level KEM phase (Blend’s Phase 1) has no Bedrock analogue. We restate the phases here for self-containment, noting Bedrock’s relationship to each:

• Phase 0 — Connection-level HNDL protection (TLS key exchange). The libp2p ECDHE key exchange is upgraded to a hybrid PQ KEM (e.g., X25519 + ML-KEM-768). This is the only HNDL surface across the entire Bedrock stack (the leader privacy protected by the PoL and PoCl creates no HNDL surface — its hiding is information-theoretic; see the analysis document), and it is shared with — and inherited from — the Blend transport migration. It is the single retroactive-threat defense Bedrock requires.
• Phase 1 — Message-level HNDL protection. Not applicable to Bedrock. On-chain consensus and execution data are public by construction; there is no per-message Bedrock ciphertext to protect. This phase exists only in Blend.
• Phase 2 — Message integrity and authentication (signatures). Ed25519 is replaced with a PQ signature scheme across the five Bedrock sites (block signing, SDP provider_id, channel single-signer, channel multi-signer, and TLS authentication). A real-time-forgery defense with no retroactive component.
• Phase 3 — Proof unforgeability (ZK proof system). The Groth16/BN254 proof system is replaced with a post-quantum ZK system across the four coupled circuits (PoL, PoQ, ZkSignature, PoCl). This is the most invasive migration in per-artifact overhead; the proof size dominates, which makes the choice of ZK system the single most consequential design decision in the Bedrock migration. A real-time-forgery defense with no retroactive component (witness hiding is information-theoretic) — though the replacement must preserve zero-knowledge, since the PoL and PoCl carry leader privacy.