bits.

FREE CONTRIBUTION CHRONOLOGY · 1970–1976

Structured state over untrusted networks

How can independent users query shared state and communicate securely across unreliable infrastructure?

The historical question

Relations separated logical questions from storage paths; packets shared links and tolerated route changes; internetworking joined heterogeneous networks; public-key methods changed key distribution.

A shared system becomes evolvable when data meaning, delivery, internetworking, and trust are separated into explicit contracts.

Separate four contracts

A student-information service illustrates why data, delivery, routing, and trust are distinct contracts. The relation Enrollment(student, course) describes meaning independent of a particular disk layout. A query for students in a course should survive a change from a scan to an index if both implementations preserve the same semantics.

A network must then carry requests and responses. Packet delivery does not by itself promise ordered bytes, a successful application operation, or an authenticated peer. An acknowledgment at one layer may mean only that a frame or segment arrived. If a response is lost after a write commits, retrying can duplicate the operation unless the application defines an idempotent request identity.

Public-key cryptography addresses another boundary. An unauthenticated key agreement can establish shared secrets while remaining vulnerable to an active intermediary. Authenticating the peer requires an additional trust mechanism. A database with correct relational queries, a working network, and a cryptographic primitive can therefore still implement an insecure or incorrect service. Compositional reasoning requires explicit guarantees and assumptions at every interface, not a list of impressive components.

What the evidence does not establish

Each abstraction solves a narrower problem than popular retellings suggest. For example, encryption does not establish authorization or truthful endpoints.

Reconstruction exercise

A registration request commits, but its reply is lost. Describe a safe retry contract and explain why encrypting the connection alone does not prevent duplicate registration.

Worked solution

Give the operation a stable request ID and atomically store the ID with its outcome. A retry returns the recorded outcome instead of applying the write again. The retention period, uniqueness scope, and transaction boundary must be defined. Encryption protects a communication channel under its assumptions; it does not define application-level duplicate handling or transaction semantics. These guarantees belong to different contracts.

Test the limits and transfer the idea

1. Modular trace and threat model · allow 35 minutes

Compute a shared key and then break its identity assumption

For a tiny teaching Diffie-Hellman exchange, use p=23 and g=5. Alice chooses a=6; Bob chooses b=15. Compute public values and the shared value. An active relay instead sends 5³ mod 23 to Alice and 5⁷ mod 23 to Bob. Compute the two endpoint secrets and show the relay can derive each from the intercepted public values. Explain what the arithmetic establishes and what authentication must add. These tiny parameters are deliberately unsuitable for real security.

Get a starting hint

Use (gᵇ)ᵃ=(gᵃ)ᵇ modulo p; the relay arranges two separate instances of that identity.

Compare your reasoning with the worked solution

Alice's public value is 8 and Bob's is 19; 19⁶ mod 23=8¹⁵ mod 23=2. The relay sends 10 to Alice and 17 to Bob. Alice derives 10⁶ mod 23=6, which the relay computes as 8³ mod 23. Bob derives 17¹⁵ mod 23=15, which the relay computes as 19⁷ mod 23. The relay now knows both session values and can translate traffic between them. The exchange arithmetic alone proves agreement with whoever supplied the received public value, not the intended person's identity. An authenticated protocol must bind the exchange transcript and intended identity under a justified trust mechanism. Diffie and Hellman's primary paper supplies the historical technical proposal; this attack trace uses original classroom numbers.

Check your reasoning

  • Computes public values 8 and 19 and honest secret 2.
  • Computes relay secrets 6 and 15 on both sides.
  • Separates agreement from authenticated identity.

2. Failure trace · allow 30 minutes

An acknowledgment at one layer does not prove a transaction

A client submits enrollment request r. The network transport acknowledges all request bytes, the database commits the enrollment, and the application reply is lost. In another run the same transport acknowledgment occurs but the server crashes before committing. Show why the client cannot infer commitment from the acknowledgment alone. Define a retry and result-query contract with an atomic request record, and explain why an encrypted connection changes neither ambiguity.

Get a starting hint

Construct two histories with the same client observations but different database states.

Compare your reasoning with the worked solution

In the first history r committed; in the second it did not. Transport acknowledgment says the transport accepted bytes, not that application processing committed. The client sees the same acknowledgment and absent reply, so deciding committed versus uncommitted from those observations would be wrong in one history. Give r a stable unique identity tied to the authenticated requester and payload. Atomically commit its stored result with the enrollment. Identical retries return that result; a conflicting payload under r is rejected. If no record exists, a retry can attempt the transaction under the same identity, with concurrency control preventing duplicate effects. A result query helps resolve uncertainty but must have stated consistency semantics. Encryption protects specified communication properties; it does not make network acknowledgment an application commit proof.

Check your reasoning

  • Builds indistinguishable client observations with different outcomes.
  • Commits deduplication record and effect atomically.
  • Separates transport, transaction and cryptographic guarantees.

Check your understanding

Which mechanism addresses a lost reply after a committed operation?

  • Idempotent request handling with a durable recorded outcome
  • Increasing the font size of the reply
  • Encrypting the same non-idempotent retry again
Explanation

Give the operation a stable request ID and atomically store the ID with its outcome. A retry returns the recorded outcome instead of applying the write again. The retention period, uniqueness scope, and transaction boundary must be defined. Encryption protects a communication channel under its assumptions; it does not define application-level duplicate handling or transaction semantics. These guarantees belong to different contracts.

Sources and further reading