A self-contained, evaluable treatment of the two operations behind the live demos — authenticating a transaction, and proving the right to spend. Every precondition is stated, every step is worked with concrete values, and each security claim is given as a definition, a theorem, and a proof a reviewer can check independently.
Two mechanisms are analysed. The authentication tag is a Carter–Wegman one-time message authentication code whose security is information-theoretic — it holds against a computationally unbounded (hence quantum) adversary. The proof of authority is a transaction-bound, hash-commitment protocol whose security is computational but post-quantum, resting only on the preimage-resistance of a hash function. The two are independent; an implementation may use either or both.
Worked values below come from the same reference implementation that drives the live demos; a reviewer reproducing the construction will obtain identical numbers.
Both parties to an authentication (the wallet and whichever party shares its Q-Block — a second device, a custody service, a counterparty) hold the following before any transaction. These are the assumptions the proofs depend on; each is stated as an explicit requirement.
B: N bytes drawn from a quantum random number generator, identical at both ends, secret, and never sent over any channel. Requirement P1: the bytes of B are uniform and independent. (Demo: N = 256; production: a large buffer.)Path(seed, cursor) → (i₁,…,iₗ), a deterministic generator of distinct indices into B. Requirement P2: regions selected for different messages do not overlap (the cursor advances by ℓ each message), so each message draws fresh key bytes.K = B[i₁] || … || B[iₗ] and from it two field elements:Requirement P3 (one-time): the pair (r, a) is used to authenticate exactly one message, then discarded; the path advances. Theorem 2 shows this is necessary, not merely prudent. By P1 the 64-bit slices are uniform, so r and a are within 2⁻⁵⁸ of uniform on F_p (the reduction of a uniform 64-bit value mod 2⁶¹−1 has statistical distance below 2⁻⁵⁸ from uniform); we treat them as uniform and absorb this negligible term into the bounds.
Used throughout the worked examples (Q-Block seeded from the label wallet-demo-0001, first transaction path):
The tag is a polynomial-evaluation universal hash, masked by the one-time pad. The construction deliberately has no degree-zero term and binds the message length, for the reasons the proofs make precise (without these two properties the scheme is forgeable — see the remark after Lemma 2).
A message M of m bytes is split into 7-byte blocks c₁,…,cₜ (the last zero-padded), each interpreted as an integer in [0, 2⁵⁶) ⊂ F_p. A final length block cₜ₊₁ = m is appended. Write L = t+1 for the total number of field elements. The map M → (c₁,…,c_L) is injective.
Verification is symmetric: it requires the same (r,a), hence the same Q-Block and path. The party that verifies the tag is therefore one that shares B — this is the wallet-layer check, distinct from the public on-chain proof of §7.
Take M = "pay:bob:0.5" (m = 11 bytes) with the example key above.
The verifier, holding the same (r,a), repeats the three Horner steps and the addition, obtains the same eight bytes, and accepts. Changing any byte of M — or its length — changes at least one coefficient c_i, and the analysis below shows the resulting tag is effectively unrelated.
B, the path, and hence (r,a). An observer of the channel and of the ledger sees only messages and 8-byte tags.(r,a). Lemma 3 shows a single tag is uniformly distributed and independent of r, so it carries zero information about the key — not “little”, none.M′ ≠ M and chosen tag T′, the relation H_r(M′) − H_r(M) = T′ − T in the unknown r. Theorem 1 bounds the success probability of this at L/p, irrespective of computing power.B; full exposure of one message’s (r,a) reveals nothing about any other message’s key (forward and backward secrecy at the message granularity).The key (r,a) ←$ F_p × F_p is drawn uniformly. A computationally unbounded adversary A chooses a message M and is given its tag T = H_r(M)+a. A then outputs a pair (M′, T′) with M′ ≠ M. A wins if Verify(·, M′, T′) accepts, i.e. T′ = H_r(M′)+a. Write Adv(A) for its winning probability over the choice of (r,a).
A family {H_r}_{r∈F_p} is ε-almost-Δ-universal if for all M ≠ M′ and all δ ∈ F_p,
For M ≠ M′, the difference Δ(r) := H_r(M) − H_r(M′) is a nonzero polynomial in r over F_p, of degree d with 1 ≤ d ≤ L_max (the larger block-count), and with Δ(0) = 0.
By the encoding, H_r(·) = ∑_{i≥1} c_i r^{L−i+1} has only terms of degree ≥ 1, so any difference satisfies Δ(0)=0. The encoding map M → (c_i) is injective and the length block fixes L; therefore M ≠ M′ forces the coefficient tuples to differ in at least one position, so Δ has a nonzero coefficient and is not the zero polynomial. Its degree is at most the highest power present, L_max. □
The family {H_r} is ε-AΔU with ε = L_max / p.
Fix M ≠ M′ and δ. Let D(r) = Δ(r) − δ. By Lemma 1, Δ is nonzero of degree d ≥ 1; subtracting the constant δ changes only the degree-0 coefficient, so D retains the same nonzero leading term and is a nonzero polynomial of degree d. Over a field, a nonzero polynomial of degree d has at most d roots, hence Pr_r[D(r)=0] ≤ d/p ≤ L_max/p. □
Remark (why the two design choices matter). Had the hash included a degree-0 term equal to a message block, an adversary could change only that block by Δc; then Δ(r) = Δc is a constant, independent of r, and setting T′ = T + Δc forges with probability 1. The length block likewise prevents trivial differences between a message and its zero-extension. Both choices are what make Lemma 1 — and therefore the security bound — hold.
For every fixed r and M, if a ←$ F_p then T = H_r(M)+a is uniform on F_p. Consequently T is statistically independent of r, and the posterior of r given (M, T) equals the uniform prior.
For fixed r, M the map a ↦ H_r(M)+a is a bijection of F_p, so T is uniform: Pr[T=t | r,M] = 1/p for every t, independent of r. By Bayes, for any ρ, Pr[r=ρ | M,T=t] = (1/p · 1/p)/(1/p) = 1/p. □
In the game of Definition 1, for every unbounded adversary, Adv ≤ ε = L_max / p.
A holds (M, T) with T = H_r(M)+a and outputs (M′, T′), M′ ≠ M. Verification accepts iff T′ = H_r(M′)+a. Subtracting the known relation eliminates a:
The right side is a value δ := T′ − T ∈ F_p that A fixes from its view. By Lemma 3, conditioning on that view leaves r uniform on F_p. Hence
by Lemma 2, since M′ ≠ M. The bound holds for the optimal A. □
Concrete numbers. With p = 2⁶¹−1: a transaction of up to ~21 bytes (L_max = 4) gives Adv ≤ 2⁻⁵⁹; a 112-byte transaction (L_max = 16) gives Adv ≤ 2⁻⁵⁷; a 1 KB message (~148 blocks) gives Adv ≤ 2⁻⁵⁴. The bound is combinatorial, so no amount of computation — classical or quantum — lowers it; there is no key-search to accelerate.
If a single key (r,a) authenticates two distinct messages M₁ ≠ M₂ with tags T₁, T₂, an unbounded adversary recovers (r,a) and thereafter forges a valid tag for any message with probability 1.
Subtracting the two tag equations cancels a:
G is a polynomial of degree ≤ L whose coefficients are public (they are functions of the two known messages). The adversary forms G(x) − (T₁−T₂) and computes its ≤ L roots over F_p; the true r is among them. For each candidate r̂ it sets â = T₁ − H_{r̂}(M₁), recovering at most L candidate keys including the true one. A single further observed tag eliminates the spurious candidates. With (r,a) known, every future tag is computable. □
This is the formal reason the path always advances: each message must draw an independent (r,a). The construction therefore depends on the Q-Block supplying a fresh, non-overlapping region per message (Requirement P2) — the protocol’s single most important operational invariant.
A forger possesses neither B nor (r,a). To pass verification on a chosen new transaction it must solve Δ(r) = δ for the unknown, uniform r — succeeding with probability at most L/p ≈ 2⁻⁵⁷ per attempt, by Theorem 1. Because each tag is independent of r (Lemma 3), observing genuine traffic does not improve this; because the Q-Block is never transmitted, there is no key to capture; and because the bound is information-theoretic, a quantum computer is no better placed than a classical one. The only route that ever helps an attacker — reuse of a key — is closed by Requirement P2 and quantified by Theorem 2.
The authentication tag is symmetric and so is checked by a Q-Block-sharing party. The on-chain gate is different: it must be verifiable by a public network that holds no secret. It is a transaction-bound hash-commitment proof; its security is computational but rests only on hash preimage-resistance, which is not broken by a quantum computer.
(Demo parameters: n = 32, k = 8.) The anchors are one-way images, so publishing them on an immutable ledger leaks nothing about s_i or K — in contrast to an elliptic-curve public key, which a quantum computer inverts into the private key.
Completeness: a holder of K recomputes each s_i and is accepted with probability 1. Soundness: model H as a random oracle. An adversary without K, given the public anchors and transcripts revealing a leaf-set R, can have a fresh transaction T* accepted only if either (a) Sel(H(T*)) ⊆ R, or (b) it finds a preimage of some published anchor A_i with i ∉ R.
Acceptance requires revealing s_i with H(s_i)=A_i for every i ∈ S* = Sel(H(T*)). For indices in R the adversary already has the leaf. For any index in S* ∖ R it has never seen s_i; producing a value hashing to A_i is, in the random-oracle model, a preimage search succeeding with probability ≤ q/2²⁵⁶ in q classical queries, and requiring Ω(2¹²⁸) queries under Grover search. Absent a preimage, acceptance demands S* ⊆ R. □
Route (a) is the covering attack of hash-based (HORS-style) signatures. With |R| leaves revealed, and Sel a random oracle, Pr[Sel(H(T*)) ⊆ R] = C(|R|, k) / C(n, k), and an adversary grinding Q candidate transactions succeeds with probability at most Q · C(|R|, k)/C(n, k). The protocol rotates the authority key as the path advances, so each anchor set authorises one transaction: a fresh target therefore faces |R| = 0 for its anchor set, eliminating route (a) and reducing forgery to the preimage search of route (b) — ≈ 2¹²⁸ quantum work. (For reference, even without rotation a single revealed set gives 1/C(32, 8) ≈ 2⁻²³ per attempt.)
The proof’s unforgeability rests solely on preimage-resistance of H. Against a quantum adversary the best generic attack is Grover search, which provides only a quadratic speed-up: a 256-bit anchor retains ≈ 128 bits of preimage security. No sub-exponential (Shor-type) attack applies, because the construction contains no period-finding or hidden-subgroup structure and exposes no discrete-log or factoring problem.
Forgery against a fresh anchor set reduces (Theorem 3, with rotation) to inverting H on a published 256-bit value. Grover inverts an N-point search in Θ(√N); here N = 2²⁵⁶, giving Θ(2¹²⁸). The objects on-chain are hash images only; there is no element of an abelian group whose discrete log or order would yield K, so Shor’s algorithm has nothing to act on. □
Zero-knowledge note (honest scope). The construction above reveals the selected leaves {s_i}_{i∈S} directly; this is sound and binding but discloses those leaf values (it is a hash-based few-time signature, not yet zero-knowledge about the revealed positions). It leaks nothing about K beyond the one-way images of revealed leaves, and nothing about unrevealed leaves. The production Q-Path replaces each direct reveal with a zero-knowledge proof that H(s_i) = A_i — so even revealed positions disclose nothing — while the verification predicate against the public anchors, and hence public verifiability, is unchanged. The proofs of Theorems 3–4 carry over: the soundness reduction still terminates at preimage-resistance.
| Mechanism | Assumptions relied on | Security statement | Forgery bound | Under quantum attack |
|---|---|---|---|---|
| Authentication tag (Carter–Wegman one-time MAC) |
Uniform, independent, one-time (r,a) (P1–P3). Field arithmetic. No computational assumption. |
Information-theoretic (Thm 1). Necessity of single use (Thm 2). | ≤ L/p ≈ 2⁻⁵⁷ for a typical transaction |
Unaffected — bound is combinatorial, not a key-search. |
| Proof of authority (transaction-bound hash commitments) |
Preimage-resistance of H; random oracle for Sel; per-use key rotation. |
Computational, post-quantum (Thm 3–4). Complete and sound. | ≈ 2¹²⁸ quantum work (Grover) per fresh anchor set |
Grover only (quadratic). No Shor-vulnerable structure; no key on-chain to invert. |
The two layers compose: the symmetric tag gives information-theoretic integrity and replay-resistance between the holder and a key-sharing party, while the hash-commitment proof gives a public, untrusting network a post-quantum way to verify authority — with no secret on the chain and nothing for a quantum computer to reverse. A reviewer can reproduce every numeric value here from the stated construction, and check each theorem against the definitions independently of any code.