The Lace failures I forgot about

2026-06-18 - terminology has become outdated; this post is left for posterity.

In the last Lace post, I described the happy version of the idea.

Lace is supposed to turn a messy distributed-systems negotiation problem into one simpler question:

what is the set of accepted packets?

Both sides contribute packet-selection rules. The rules are merged by intersection. Each side advertises the validated packets it can serve, asks for the advertised packets it wants and does not have, validates received bytes, and repeats until the current fixed point.

That is still the shape I want. It is the part that feels like the real crack in the problem.

But the first write-up skipped over the part where that idea almost accidentally became a private database query system.

This post is about the failures I had not fully accounted for, and the workaround that became the current algorithm: origin-aware packet views and faceted exchange plans.

Where the previous post left off

The previous model had two important pieces.

First, packet facts only come from validated local packets:

Have(P)
Field(P, Name, Index, Value)
Verifier, packet links, and so on

A peer can advertise claims about packets, but those claims are not truth. Offer(P,S,'Group',...,'team') is just discovery metadata until the bytes arrive and validate.

Second, a mergeable lacegram had two views of a selector:

LocalSelect(P) :- Have(P), Field(P,'Group',GI,'team').
OfferSelect(P,S) :- Offered(P,S), Offer(P,S,'Group',GI,'team').

LocalSelect says what I can serve from my validated store. OfferSelect says what advertised peer packets might be worth requesting. If I contribute “team packets” and you contribute “marked by Bob’s verifier”, the merged selected set is their intersection.

Then interlace does the ordinary loop:

1. agree on the merged selection policy;
2. advertise currently served packets;
3. reconcile peer offers;
4. request missing wanted packets;
5. validate received bytes;
6. repeat, because new validated facts may unlock more selected packets.

So far, so good.

The mistake was assuming that direct packet-transfer safety was the whole safety problem.

Failure 1: direct exfiltration was not the only leak

The obvious rule is:

send P only when Have(P) and Serve(P)

And similarly:

advertise P only when Have(P) and Serve(P)
request P only when Want(P), Offered(P,S), and not Have(P)

Those rules block the dumb failure. If Bob only serves Group = X, Alice should not be able to make him send private Group = Y packets just by asking.

But there is a subtler failure: Alice does not need Bob to send the private packet. She only needs Bob’s visible behavior to depend on whether the private packet exists.

Imagine Bob contributes the normal policy:

LocalSelect(P) :- Have(P), Field(P,'Group',GI,'X').
OfferSelect(P,S) :- Offered(P,S), Offer(P,S,'Group',GI,'X').

Bob thinks he is only exchanging Group X.

Now Alice contributes a selector shaped like this:

LocalSelect(P) :- Have(P), Field(P,'Group',GI,'X').
OfferSelect(P,S) :- Offered(P,S), Offer(P,S,'Group',GI,'X'), Field(Q,'Group',GJ,'Y').

Then Alice advertises a harmless Group X bait packet.

If Bob evaluates Alice’s rule against Bob’s whole local packet-fact database, Bob will want the bait packet only when he has some private Group Y packet. Alice observes whether Bob requests the bait packet. One bit leaked.

No Group Y bytes moved. No Group Y offer record was advertised. The direct send/offer invariant held.

Still broken.

The contributed rule turned Bob into an oracle over his private facts.

Failure 2: the oracle can extract sets, not just one bit

One bit is already bad, but the same pattern scales.

Alice can advertise many bait packets with different keys:

Group: X
Key: guess-0001

Group: X
Key: guess-0002

Group: X
Key: guess-0003

Then Alice writes the peer selector so Bob wants exactly the bait packets whose offered key matches a private Group Y key in Bob’s store:

OfferSelect(P,S) :- Offered(P,S), Offer(P,S,'Group',GI,'X'), Offer(P,S,'Key',KI,K), Field(Q,'Group',GJ,'Y'), Field(Q,'Key',KQ,K).

Bob’s request list becomes an answer sheet.

This is the important correction to my mental model: the protocol’s visible behavior is itself an output channel. Requests, offers, partition-summary counts, timing, and open-exchange changes can all disclose information if untrusted peer rules can inspect private local facts.

So the real question is not only:

which packets may be sent?

It is also:

which local facts may a peer-authored rule query while deciding what becomes visible?

Failure 3: a flat merged program erases authority

The old merge story was too flat.

It is tempting to take Alice’s lacegram, Bob’s lacegram, namespace the helper predicates, generate intersection rules, lower to Serve and Want, and call the result one Datalog program.

But a rule’s origin matters.

The exact same canonical rule text means something different depending on who contributed it. Bob-authored rules running on Bob may be allowed to see Bob’s full local packet facts. Alice-authored rules running on Bob must not get that same view unless Bob explicitly grants it.

So duplicate handling cannot be “same text means same rule”. It has to include origin:

(origin, facet, canonical module bytes)

Otherwise a merge step can accidentally collapse away the security boundary.

Helpers were another version of the same bug. It is not enough to gate LocalSelect and OfferSelect directly. A malicious module can put the private query in a helper predicate, then use the helper from OfferSelect. Negation and cardinality have the same issue. If those operations range over the raw store, the oracle comes back.

The current workaround: query views

The fix is to stop treating local packet facts as ambient facts for peer-origin modules.

A local store still has the full validated fact view. But peer-authored rules see only the packet facts that local policy exposes to that peer. The internal gate is packet-level:

QueryPacket(Viewer,P)

Conceptually, when Alice’s module runs on Bob, packet fact access is rewritten like this:

Have(P)               => Have(P) and QueryPacket('Alice',P)
Field(P,N,I,V)        => Field(P,N,I,V) and QueryPacket('Alice',P)
PacketLink(P,N,I,D,T) => PacketLink(P,N,I,D,T) and QueryPacket('Alice',P)

Same for the rest of the packet fact surface.

So Alice’s malicious rule effectively becomes:

OfferSelect(P,S) :- Offered(P,S), Offer(P,S,'Group',GI,'X'), Field(Q,'Group',GJ,'Y'), QueryPacket('Alice',Q).

If Bob did not expose Group Y packets to Alice’s query view, Alice cannot test for them through Bob’s request behavior.

Bob can expose a view with local policy, for example:

AllowQueryPacket('Alice',P) :- Have(P), Field(P,'Group',GI,'X').

Multiple ordinary query constraints compose by intersection. If nothing grants a query view, the default is empty.

This is not magic secrecy. Queryable means queryable. If Bob exposes a packet to Alice’s query view, Alice may learn Datalog-expressible properties of that view through requests, offers, counts, negation, and timing. But the boundary is now explicit: Alice can query what Bob made queryable to Alice, not Bob’s whole store.

Faceted exchange plans

The algorithm now has a more precise setup phase.

Instead of flattening everything immediately, each contribution keeps metadata:

• origin/source label;
• facet role;
• canonical module bytes;
• deterministic namespace;
• required offer fields;
• public runtime facts used by the plan.

The two sides agree on a canonical faceted exchange plan, identified as an E.* value. Each side then compiles that same plan into a local executable policy using its own store and its own query views.

The shared selected set is still an intersection:

MergedLocalSelect(P) :- m1_LocalSelect(P), m2_LocalSelect(P), ...
MergedOfferSelect(P,S) :- m1_OfferSelect(P,S), m2_OfferSelect(P,S), ...

And interlace still consumes generated mechanics:

Serve(P) :- MergedLocalSelect(P).
Want(P) :- MergedOfferSelect(P,S).

But now those generated predicates remember where each source rule came from. Alice-origin packet facts on Bob resolve through Bob’s Alice query view. Bob-origin packet facts on Bob can use Bob’s local view. The same plan runs on both sides, but fact resolution is origin-aware.

That is the main algorithm update.

Other things this forced into focus

A few smaller fixes fell out of the same analysis.

Offer fields are negotiated per exchange plan. If a selector depends on Offer(...,'Verifier',...), the plan has to require that offer field. Otherwise one side could evaluate a different discovery world than the rule expects.

Prepared flat lacegrams are now a separate authority surface. If a binding supplies a fully prepared policy as trusted local code, that is allowed, but it is not the same thing as accepting peer-authored fragments. Peer-authored fragments still need origin metadata and origin-aware fact resolution.

The fixed-point loop also needed a sharper definition. Stopping just because no packet transferred in the last round is too weak. Offer snapshots, raw Serve, and raw Want can change even before a transfer happens. The driver has to keep going when the relevant state changes, and stop only when there is no currently wanted, advertised, missing packet that the peer still serves.

And because generated faceted programs get hard to debug, canonical lacegrams stay annotation-free, but authoring tools can now carry comments and JSON annotations as a source-map sidecar. That does not change protocol behavior. It just makes traces explainable when a generated Want(P) did or did not happen.

The better problem statement

The earlier problem statement was:

converge both stores toward the selected packet set.

That remains true, but it was missing the trust boundary.

The better version is:

converge both stores toward the shared selected packet set, while peer-origin rules can inspect only the local packet facts explicitly exposed to that peer.

That one sentence is less cute, but much closer to the real system.

The nice part is that the original shape survived. Lace is still packet-set convergence. Interlace still advertises, reconciles, transfers, validates, and repeats. The programmer-facing goal is still “describe the accepted packet set” rather than manually wiring push, pull, list, get, and auth paths.

The difference is that rule origin is now part of the algorithm, not a comment in the margins.

First written: 2026-06-11
Last edited: 2026-06-18