Research shelf / Information theory / Izaac protocols
Written Updated
Twelve protocols built on one primitive: randomness both sides already have
If two parties hold the same compact state σ, they can each derive the same arbitrarily long pseudorandom sequence with no communication at all. The theoretical paper argues that this is information-theoretically equivalent to a free broadcast channel with zero latency, which collapses a surprising number of communication lower bounds at once. The applications paper turns that into twelve engineering specifications.
Specified in detail; implementation partial or absent.
A compact shared cryptographic state σ acts as a free broadcast channel — and twelve concrete protocols, from Byzantine consensus to coordinated differential privacy, are derived from that one observation.
The primitive is deliberately small: a shared state σ ∈ {0,1}S from which both parties compute identical streams locally. The meta-theorem is that shared deterministic randomness behaves like a broadcast channel that costs nothing to use — and that this is why so many barriers in distributed computing, cryptography and information theory fall to the same trick.
Five consequences are proved in the theoretical paper: Byzantine consensus with zero post-setup communication while still tolerating f < n/3 faults, matching PBFT’s optimal fault tolerance without its O(n²) messages; compression below the unconditional entropy limit via shared side information; single-round verifiable random functions; non-interactive multi-party computation with privacy by simulation and correctness by mask cancellation; and space-optimal probabilistic data structures.
The companion paper specifies twelve protocols at production-engineering detail — blockchain leader election, privacy-preserving analytics, deterministic consensus, shared-hash Bloom-style structures, reproducible Monte Carlo with O(log n) fast-forward, coordinated differential privacy, deterministic coverage-guided fuzzing, trading-backtest commitment for regulators, lazy infinite structures from compact seeds, content-addressed replica placement, synchronised rate limiting without datacentre coordination, and collision-free MAC scheduling. Each carries a formal security claim, a complexity analysis and a worked example.
Every number, and what stands behind it
A claim is only worth the evidence attached to it. Each row below carries its basis: measured on the author’s own hardware, derived from the construction, measured on synthetic data, projected from literature, or simply cited.
| Claim | Figure | Basis | Context |
|---|---|---|---|
| Byzantine fault tolerance | f < n/3 | Derived | Matches PBFT’s optimum |
| Post-setup communication for consensus | zero | Derived | Against PBFT’s O(n²) messages |
| Compression with shared side information | ≈1.2 bits/char, English text | Measured | Against a no-side-information baseline |
| Shared-state size | Θ(λ + log k) | Derived | Compact: the whole point of the construction |
| Fast-forward cost | O(log n); O(1) in CTR mode | Derived | Property of the σ construction |
| Protocols specified | 12 | Derived | Each with a security claim and complexity analysis |
| VRF rounds | single | Derived | Satisfying uniqueness, pseudorandomness and verifiability |
Measured — author-run experiment on the stated setup. Synthetic — measured, but on synthetic rather than real data. Derived — follows from the stated construction or proof. Projected — paper-stated projection, not an author-run benchmark. Cited — taken from external literature.
How it works
- Shared deterministic stream σ. Both parties derive identical randomness locally from a compact state — no messages, no latency.
- Free-broadcast meta-theorem. The unifying claim: shared randomness is information-theoretically a free broadcast channel.
- Mask cancellation. The NI-MPC correctness mechanism — masks derived from σ cancel exactly when the parties combine shares.
- Formal reductions. Every construction reduced to standard assumptions: PRF security and collision resistance.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- Everything depends on secure setup of σ. Compromise it and every protocol in the suite fails at once, predictably rather than gracefully.
- The sub-entropy compression is a Wyner–Ziv side-information result. Beating a no-side-information baseline given side information is expected, not a broken bound.
- "Zero communication" covers the post-setup steady state. Distributing σ, rotating it, and recovering from a fork all cost messages the analysis does not price.
- Protocol specifications are engineering references with reference Python. No production deployment or third-party security review.
- The consensus tables underspecify: leader selection needs no messages, but proposal propagation still does.
Free under AGPL-3.0+ for almost everyone
Personal use, charities, education and organisations under AUD 50,000 a year pay nothing. A tiered commercial licence covers everyone else.