theory.md

Theory: Peer-to-peer Non-Consensus Partial Event Ordering

This document summarizes the design described in the original paper, Peer-to-peer Non-Consensus Partial Event Ordering Network by Levente Mészáros (local copy: Peer-to-peer Non-Consensus Partial Event Ordering Network.pdf). It is the conceptual background for the simulation model; see implementation.md for how the code realizes these ideas and paper-vs-implementation.md for what is and is not implemented.

The goal in one sentence

Build an information system where all participants can mathematically prove lower and upper bounds for the time of digital events generated by any participant, such that the time interval is shorter than a predefined value (e.g. a minute) according to the local clock of the participant.

The emphasis on the local clock of the participant is essential: the system does not try to establish a single global timeline that everyone agrees on. Instead, each node can independently derive a time interval for any event, expressed in terms of its own clock. Two nodes may derive different intervals, and that is acceptable — the system is "non-consensus" and "disagreement supporting."

Requirements and non-requirements

The paper lists these design requirements:

• permissionless — anyone can participate without authorization
• trustless — require as little trust in other participants as possible
• dynamic — allow rapid changes in participant relationships and network topology
• decentralized and redundant — no single point of failure
• distributed — efficient use of resources over the whole network
• consistent — different participants must not reach conflicting orderings
• disagreement supporting — anyone may form their own partial ordering
• efficient in memory, disk, CPU, and network bandwidth

And explicit non-requirements:

• global consensus is unnecessary and would require sacrificing too much
• no implicit transfer of value for publishing (unlike proof-of-work blockchains), because resource usage is low

This positions the system deliberately against blockchains: there is no global ledger, no mining, no total order, and no coin. It is closer to a distributed, hash-linked DAG of timestamps that each node grows locally and shares with its neighbors.

Components

Term	Meaning
Node (N, Nᵢ)	A computing device connected in a network.
Event (E, Eᵢ)	A data structure generated and stored by a node (a tweet, a photo, a measurement, …).
Clock event (C, Cᵢ)	A special event that carries a local timestamp T(C).
Timestamp (T, Tᵢ)	A point on some node's local clock.

Notation

• If Eᵢ contains the hash of Eₖ, this is written Eₖ ← Eᵢ ("Eₖ is referenced by Eᵢ"; equivalently Eₖ happened before Eᵢ and is provably older).
• An event chain is written E (underlined) or C, and satisfies Eᵢ ← Eᵢ₊₁ for every consecutive pair. A chain is thus a hash-linked path: each element embeds the hash of the previous one, so the whole chain is tamper-evident and strictly ordered.

Operation

Running nodes

• Anyone can run as many nodes as they see fit.
• Nodes have private/public keys to prove identity.
• Nodes have neighbors; the topology may change over time.
• Nodes continuously share the hashes of their clock events with current neighbors.
• Nodes may share events (optional; by default events are not distributed).

Creating events

Any node can create any number of events at any time. An event contains:

• some content (picture, audio, video, text, …),
• some hashes (and locations) of selected local clock events,
• optionally a randomly generated salt,
• optionally a signature.

By embedding the hash of one or more recent local clock events, the event pins itself to a position in that node's clock-event chain: it is provably after the clock events it references.

Creating clock events

Any node can create clock events at any time, usually periodically (~1 per second). A clock event contains:

• a local timestamp (no global clock is needed),
• hashes (and locations) of selected local events,
• hashes (and locations) of selected clock events, both local and from neighbors, whose timestamps are smaller than this clock event's timestamp (this ordering is guaranteed for local clock events, but not necessarily for neighbor clock events, because clocks are local and unsynchronized),
• optionally a salt,
• optionally a signature.

After creating a clock event, the node broadcasts its hash to current neighbors.

The result, across the whole network, is an ever-growing, hierarchical, redundant distributed DAG of clock events. Each clock event points backward to the previous local clock event, to the latest known neighbor clock events, and to the local events created since the last clock event. Because everything is hash-linked, an edge in the DAG is a cryptographic proof of "happened-before."

Proving relationships

Proving the order of two events

To prove that Eₐ was created earlier than E_b, a node exhibits one or more chains E such that Eₐ is the first element and E_b is the last:

Eₐ ← E₁ ← E₂ ← … ← Eₙ₋₁ ← Eₙ ← E_b

Because each ← is a hash inclusion, and hashes cannot be predicted, the chain is a proof that Eₐ existed before E_b.

Proving event time boundaries

To prove that an event E was created between Tₐ and T_b according to the local clock of node N, the node exhibits:

• a clock event Cₐ of N with T(Cₐ) ≥ Tₐ such that E was created later than Cₐ (a chain from Cₐ to E), and
• a clock event C_b of N with T(C_b) ≤ T_b such that E was created earlier than C_b (a chain from E to C_b).

Cₐ is the lower bound and C_b is the upper bound of E according to N. The interval [T(Cₐ), T(C_b)] is N's proven time window for E.

Partial event ordering example

The paper's worked example (see the figure on page 3 of the PDF) has three nodes N₁, N₂, N₃, each with its own chain of clock events, cross-linked by neighbor references. An event E₁ is created by N₁ (attached above C₃ of N₁).

Node N₃ can prove that E₁ of N₁ was created between T(C₁) and T(C₆) according to N₃: C₁ of N₃ is the lower bound and C₆ of N₃ is the upper bound. The chain E from C₁ of N₃ up to E₁ and back down to C₆ of N₃ is found with the help of the intermediate node N₂, because N₃ is not directly connected to N₁ in the clock-event DAG. The single connected chain

C₁(N₃) ← C₂(N₂) ← C₃(N₂) ← C₃(N₁) ← E₁(N₁)   [lower half]
E₁(N₁) ← C₄(N₁) ← C₆(N₂) ← C₆(N₃)            [upper half]

(both halves being local-to-neighbor-to-…-to-origin and back) is exactly what a chain discovery must reconstruct. The key property: the chain begins and ends at the querying node's own clock events, so the bounds are expressed in that node's local time.

Finding boundaries and order

Finding event time boundaries

• Nodes maintain a hierarchical routing table over time, similar to IP routing.
• Finding the lower/upper bounds is done with a probabilistic beam search, recursively along the neighbor hierarchy toward the event's originator.
• During the search, each neighbor is either:
  • the originator of the event, which can directly provide local lower/upper bounds; or
  • not the originator, in which case it extends the lower/upper bounds received from the next neighbor toward the destination, using its own clock-event chain.
• Finding boundaries may require transfer of value to incentivize node operators to answer queries.
• The result is a lower/upper bound pair of clock events that form a single chain E with the target event E included.

Finding the order of two events

• Find the time boundaries of both events using the method above.
• Compare the two intervals:
  • if one interval is strictly before the other, the order is determined;
  • otherwise (the intervals overlap), the order cannot be determined according to the local clock of the node.

Estimating network efficiency

Network assumptions:

• a few billion nodes (comparable to IP nodes on the internet),
• a hierarchical, redundant, ever-growing distributed DAG of clock events,
• average distance of leaf nodes from top-level nodes ~10 hops,
• average ~10 neighbors per node (~10 neighbor clock events referenced),
• nodes generate events as content becomes available,
• clock-event hashes are distributed to neighbors; events are not distributed by default,
• ~1 clock event per second, ~100–1000 bytes each.

Rough approximation:

• nodes store their own local events only,
• nodes store ~3–30 GB of clock events per year,
• a chain between two clock events Cₐ, C_b of Nᵢ including an arbitrary event of any node is ~40 events long (2 × 2 × network depth — "there and back again," on both the lower and upper side, due to hierarchical routing),
• such a chain, excluding the event content, is roughly 40 × 10 × 100 = 40,000 bytes, which fits into a single UDP datagram,
• the timestamp of any event can be narrowed to less than ~40 seconds by any node according to that node's local clock.

Bounding storage: multi-resolution clock chains

The estimate above grows without bound — a chain kept forever accumulates ~3–30 GB/year and never shrinks. The implementation avoids this by having a node run several independent clock chains at once, at geometrically spaced intervals (chain 0 fastest, each next chain a fixed factor slower); each is an ordinary clock-event chain in the sense of Components above, just ticking less often.

Every event a node publishes is pinned into every chain, not just the fastest one: at creation it references each chain's current tip, and each chain's next tick references the event back. That symmetry is what makes pruning safe — a node can ring-prune a chain down to a fixed number of retained clock events without ever losing an event's orderability, because a dropped fast-chain clock event's role is still covered by a slower, still-retained chain. Old events don't disappear; their provable bound just widens to the coarser chain's own interval — roughly 1/C of the event's age for C clock events kept per chain. Storage is then flat (bounded by the number of chains times the ring size per chain) instead of growing with wall-clock time, while reach — the oldest age still orderable at all — grows exponentially with each additional chain.

Preventing attacks

The security rests entirely on the difficulty of inverting/predicting a cryptographic hash.

Postcomputing / forging the past

An attacker wants to insert an event back in time as if it had always been there:

1. at Tₐ, create an auxiliary event Eᵢ containing a non-existent event hash,
2. wait until T_b ≫ Tₐ when forging the past is needed,
3. forge Eₖ so that Eₖ ← Eᵢ (i.e. Eᵢ's placeholder hash actually equals Eₖ),
4. announce Eₖ as if it had been present at Tₐ all along.

This requires finding a preimage for the hash embedded at Tₐ — the hash function makes forging the past hard.

Precomputing / forging the future

An attacker wants to precompute an event and insert it later as if freshly created:

1. at Tₐ, precompute future content,
2. wait until T_b ≫ Tₐ,
3. insert Eᵢ at T_b with the precomputed content,
4. announce Eᵢ as if created at T_b.

The defense: a digital representation of a real-world event captures only a small subset of the available information, and the hash of a contained (fresh) clock event must be used to designate exactly which subset is being represented. Precomputing all possible digital representations of the future is generally hard (it amounts to simulating the real world), and the hash function makes precomputing only the required subset and pre-including it in the chain hard. (The paper marks the completeness of this argument as an open question: "is this always possible?")