# Architectural Considerations From Building Witness

Our programming language for private computation.

Source: https://hyperstition.cc/architectural-considerations-from-building-witness

September 20, 2026

Authors: Nahom Seyoum, Adit Srivastava, AJ

## Motivation

Witness was originally architected to be a programming language for agents to communicate with each other without leaking information or being susceptible to prompt injection.

It was designed for social contracts, where parties use agents to reveal private information to other agents without leaking it back to the human layer—preventing any form of front-running or malicious context extraction. This was part of our broader work to imagine newer protocols to increase the fluidity of information without detriment to social concerns of privacy.

It has since evolved into a foundation for more sophisticated strategies and systems of information revelation, including a [functional decision](https://www.lesswrong.com/w/functional-decision-theory) framework for asymmetric coordination in markets with humans and agents.

Witness unlocks a new paradigm with fractional information sharing, which informs new foundations and a more complete aperture to contemporary market structures. This prompts possible solutions to questions like “what does it mean to have [a financial market with hidden prices](https://hyperstition.cc/architectural-considerations-from-building-witness#sealed-prices)?”

## TL;DR

- Witness is our programming language for private computation.

- A permitted answer can leak extra private information in multiple ways and we reason through how to mitigate each one.

- We describe what the runtime needs to enforce these contracts, including fixed release schedules, reserved capacity and rollback rules that do not expose private dependencies.

- A market that has private prices, charges for market access and compensates contributors for their information is possible through Witness.

Note: This is not an introduction to the Witness programming language itself, its syntax or how to write programs in it—simply some of the considerations we found interesting to share.

## Introduction

Privacy, as software inherits it, is a property of “stored objects.” Each file has an owner who sets some interaction policy, which is later checked when an attempt to read or write the file is made. This is sufficient for most of our current infrastructure demands because objects are stable, i.e., a given file exists before and after anyone attempts to read it and is invariant to the questions being asked of it. This is clearly inadequate for information markets and coordination at scale.

In a negotiation or an information market, the object worth protecting isn’t fixed. It only comes to bear when two private contexts are run against each other and something is computed from the pair. As a consequence, they have a strange shape where they depend on both inputs, do not exist prior to the comparison and cannot be solely attributed to either party as theirs. Witness is the programming language we built for reasoning about joint facts.

While building Witness, we had to reason about certain architectural considerations unique to the object we require. Below, we walk through two of them: what execution reveals through timing and failure, and how individually authorised answers can be combined to expose a private input.

## Channels

At Hyperstition, most of the joint facts that we care about are shaped like a match. To see what we mean by this, let us consider the simplest case, a one-bit negotiation between Alice and Bob. Let $S_A$ and $S_B$ be their respective private sets of acceptable agreements, and we say a match exists when $S_A\cap S_B\neq\varnothing$. The constraint is that they want to evaluate this condition without disclosing either set.

The contract’s job is to simply return a Boolean saying whether an agreement exists. Alice is allowed to learn the result of the contract and whatever else it implies about Bob’s terms. Bob agrees with this arrangement but his threat model is disclosing other properties of his terms. For instance, he wouldn’t want to reveal how many people he is corresponding with, how compatible their terms are, etc. Therefore, the privacy requirement for the interaction between Alice and Bob is more than just “my answer to Alice is private.” Alice’s observations about the execution of her contract with Bob should not reveal additional information about Bob’s activity.

It is easy to see how the same requirement can carry over to more complex contracts rife in everyday life such as escrows, pricing and even recommendation systems. Their outputs clearly contain a signal richer than a bit, but the underlying structure is broadly the same.

Returning to Alice and Bob, let us consider how we might implement their contract in a conventional distributed system. One very natural and straightforward approach is to give Bob a shared matching record with a queue for incoming requests. Any candidate who then wants to query Bob submits their terms to that queue, and the runtime processes the requests one at a time and returns binary match or no-match.

```
Bob.match_queue = [
request from Alice,
request from Carol,
request from Dan,
...
]
```

This works provided our figure of merit is simply returning the authorised bit. However, there are some obvious side channels that a sufficiently motivated adversary can exploit:

- Queue contention. Alice’s request is added to Bob’s queue, so she must wait for prior requests to finish before she gets the answer. She can easily exploit this by repeatedly submitting requests and measuring how long the responses take. If she does this enough, she can time the delays and work out how many other candidates are querying Bob. This gives her a sense of her competition/Bob’s demand even if she didn’t necessarily have any access to anyone else’s request or result.

- Lock contention. Now suppose Bob, for some reason, wants to update his terms. A standard procedure is to provision a lock during the update. What happens if Alice’s request arrives at the same time he holds a lock? She now has to wait before her request can be processed. Alice can track this by repeatedly submitting requests and measuring how long they take. If she does this enough and times the delays, she can work out when Bob is updating his terms. This gives her information that she can use to time her next offer even if she doesn’t have access to the updated terms themselves.

- Transaction validation. Suppose we use an optimistic transaction where we need to read the records for the comparison and compute a result. Before releasing the result, even if it is a no-match, we need to recheck whether the records’ versions changed while the result was being computed. Suppose Alice wants to know whether Bob is considering buying gold. Alice sends an offer for gold, and Bob only reads the quote if he is indeed interested in gold; otherwise, he skips it. Alice has no interest in a match result but wants to know this information about Bob. To do this, she changes her quote after the comparison reads the quotes and computes the result but before it checks if their versions have changed. If Bob was considering gold, the comparison would have read her gold quote, so the version check catches her change, and the transaction has to retry. If he wasn’t considering gold, the comparison would have skipped her quote, so changing it causes no conflict. If Alice can see the retry, an extra charge or a timeout caused by it, she can figure out whether Bob was considering gold, even if the result is no-match.

Plot: An optimistic transaction validates the versions of records it read. Alice changes her gold quote from version 7 to version 8. If Bob read the quote, validation detects the change and retries; if he skipped it, there is no conflict. Both runs return no-match, but an observable retry reveals whether Bob read gold.

One fairly common response to timing leaks is padding. This is clearly not sufficient if Alice can still observe retries, extra charges or timeouts, but we can simply mandate that every request to Bob’s record runs in a fixed slot. This means the queue is always processed as though it contained exactly $M$ requests. If there are fewer than $M$, we just add dummies and Alice gets responses after the same time.

For this to work, however, $M$ must be a public and sufficiently large upper bound on the number of requests accepted per round. It must be fixed and cannot depend on the number of incoming requests. But how can one establish this bound?

In the simplest of cases, Bob’s market is public, has $n$ registered participants, and each participant is allowed a request per round. Here, it is sufficient if we simply pad to $n$. However, we want Witness to support a wider host of interactions including ones where knowledge of participation in the market itself is private. Sizing the schedule by counting participants would reveal that number, and if we opt to simply expand when someone joins, we reveal the change in participation. We need the contract to declare a capacity a priori but also be invariant to the set of participants, which is to be kept private.

In Witness, one of our solutions is to define a channel:

```
channel C_B:
writers:         {A_1, ..., A_d}
reader:          sealed matching node for B
payload:         candidate terms
reveal schedule: slots t_1, ..., t_d
```

The channel has these fields fixed before it is executed.

One important thing to note here is that we need to guarantee it is feasible to compute every result before the reveal schedule assigned to it. This is to prevent Alice from gaining any information about Bob’s other activity through the actual published result at the reveal time. So, as a consequence, we have some unused capacity between the actual completion and the scheduled time.

If the computation’s result is only supposed to depend on the input at the starting time, we can bind each request to an immutable input. In the case where it depends on the current value, we have to deal with an input conflict without giving Alice additional information through an extra charge, a late response or a timeout. We also can’t have her other requests’ results be affected by the resources consumed by the conflict [[4]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-sheff2016).

## Repeated queries

In the previous section, we reasoned about common timing side channels and some responses. However, there is also another type of side channel that an attacker can use to recover information. All it requires is sequencing queries in a clever manner.

Suppose Alice wants to do a deal with Bob and is trying to work out his reserve price. Let’s say Bob’s reserve is a private integer $b\in\{0,1,\ldots,10^6\}$ and the contract is set up such that it spits out a binary yes or no to a question in the form of “$b\leq x$?” Alice can recover the price in 20 queries!

$\def\arraystretch{0.88}\begin{aligned}
B_0 &= \{0,\ldots,10^6\},\\
x_1=500{,}000,\quad \text{yes}
&\;\Longrightarrow\; B_1=\{0,\ldots,500{,}000\},\\
x_2=250{,}000,\quad \text{no}
&\;\Longrightarrow\; B_2=\{250{,}001,\ldots,500{,}000\}.
\end{aligned}\tag{1}$

$x_t=\left\lfloor\frac{\min B_{t-1}+\max B_{t-1}}{2}\right\rfloor,
\qquad
|B_q|\leq\left\lceil\frac{10^6+1}{2^q}\right\rceil.\tag{2}$

$q=\left\lceil\log_2(10^6+1)\right\rceil=20
\quad\Longrightarrow\quad B_q=\{b\}.\tag{3}$

Smith’s information leakage measure [[1]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-smith2009) gives us an upper bound on the more general case. If we have a query with $k$ possible outputs, then the output leaks at most $\log_2 k$ bits of information.

The catch here is that Alice gets to retain what she learns. She can combine answers from previous queries to inform her next question. If she has $q$ queries and each one has $k$ possible answers, then there are at most $k^q$ possible answer sequences. This makes the bound $q\log_2 k$ even when we choose the question adaptively.

We address how we adjudicate who gets to ask and at what rate using a separate object in Section 5.

## Closing the clock

### 1. Independent reads

Even after closing some timing leaks, we can still have additional channels involved in the computation end up creating another side channel. Consider an example where Alice sends Bob a request but the computation of the result involves looking at two channels, one of them being a do not disturb bit. The naive implementation of this responds with a no-match instantly if the do not disturb flag is set. But this gives Alice additional information about Bob’s do not disturb bit given the latency she experiences on her request.

This can even happen at the CPU level, where an unprivileged process can recover secrets that a cached state depends on by simply looking at the timing of some unrelated memory accesses. No amount of sophisticated programming can avoid this.

Plot: Alice fills a shared cache and later probes her entries. Bob's private read can evict Alice's cached line, making her probe fetch it from RAM and take longer. Skipping the read leaves the line cached. The timing reveals Bob's action even though the authorized answer is unchanged.

Hence, the fix comes at runtime. We need a way to guarantee that a read’s completion time only depends on variables the reader is allowed to see.

We assign a public reveal time for each read a priori, and the computation runs behind a sealed boundary that finishes at any point within this window. So in the Alice and Bob case above, we can have the response time that Alice perceives be the same regardless of whether Bob’s DND flag was set. Therefore, within this execution, the reveal time doesn’t carry any bits of information about Bob’s flag or any other variable that Alice is not allowed to access, where a naive node implementation would have leaked $\log_2(s_{\max}+1)$ bits about Bob’s do not disturb flag and also his contact list.

There is also another hidden leak that fixing release times avoids in advance: a correlational leak between channels. Consider the case where, instead of fixing the release times, we choose to have random release times and batch requests by their owner, whose identity is to be kept private. Suppose Alice queries two anonymous offers, and in this case both of them always return no-match. We have each batch release its answers in a slot chosen uniformly at random among $m>1$ slots. If both of the offers belong to Bob, then they’re released in the same slot, and if not, then the probability of them arriving in the same slot as independent releases is $1/m$. By comparing the slots in which each offer was released, Alice gains partial information about whether the offers came from the same source or not, while looking at each offer channel alone reveals nothing about their source.

So, while designing the response schedule, we need to make Alice’s response schedule distribution invariant to the sources where they come from.

### 2. Numerical answers

Fixing the answer’s reveal schedule doesn’t prevent peripheral activity from having an effect on the answer itself. For example, suppose Alice submits a sequence of $n$ numbers, $x_1,\ldots,x_n$, and wants to know whether their sum exceeds $100$. This involves computing a floating-point sum of these numbers.

In Alice’s runtime, the calculation is grouped with unrelated executions that are happening, and the grouping with other executions can affect the order in which the scores are added. In floating-point addition, intermediate results are often rounded off, and the rounding rules used affect the final total sum. These imprecisions that arise from unrelated private executions can change the final Boolean value Alice gets. This gives her information on some of the other private activities going on even though her inputs stayed the same.

One solution is to compute the sum exactly on every request [[5]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-neal2015). Even if we specify 64-bit arithmetic, we can still have different orders of operations impact the answer. Fixing the order and rounding rules makes the calculations repeatable but doesn’t guarantee the exact comparison a result Boolean will need.

A more robust design requires the runtime to certify the permitted answer. Consider one where a fast implementation gives an approximation with rigorous bounds on the answer $L<\sum_i x_i<U$. Now there are cases where these bounds themselves are enough to determine the Boolean. If $L>100$, it can certify yes; if $U\leq100$, it can certify no. For example, an interval of $[103,104]$ settles the answer without determining the exact score. An interval of $[99,101]$ does not. If we don’t have a definitive answer for the Boolean, we fall back to a more precise calculation that can lead to a conclusive answer.

Different executions of the fast implementation can give different approximate rigorous upper and lower bounds. The runtime only needs enough numerical certainty to determine what the contract allows Alice to learn [[6]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-shewchuk1997).

There is also a possible timing side channel with this. The extra computation required in the case where the fast implementation cannot determine the Boolean must not change the reveal schedule for the request. We need to remember all the other side channels that we have prevented while implementing the prevention for this one.

### 3. Public faults

Witness has to be resistant to infrastructure failures which are fairly unpredictable (think Cloudflare going down, for example). We have to find a way to reason about what to do with every ongoing action, negotiation or otherwise, that the outage overlaps with.

The answer clearly involves a version of a rollback, but before deciding which actions to roll back, we need to define when an action becomes committed. The contract declares who can see what, and for Bob and Alice’s case, that set is $\{A,B\}$. When the scheduled release time arrives, we have to make sure the runtime commits the result for both parties or for neither. This guarantees the result is available to both in the committed state, even if their network notifications arrive at different times. Until then, we have to mandate that the action remains uncommitted even if its computation has already finished. This prevents retracting information one party has already learned, and we can safely discard the unpublished result.

The next question is to work out rollback procedures for uncommitted actions. The instinctive thing to do is to roll back the actions that depended on the broken piece. However, this can reveal private dependencies. For example, say Alice and Bob’s match accesses a cache that depends on their private inputs and the execution path the computation takes. So retrying only the actions that accessed the cache partially reveals dependencies even if the result is not revealed. If we have $k$ distinguishable and also recoverable patterns, this can leak up to $\log_2 k$ bits.

Once the fault epoch $F$ is published, every uncommitted action whose window $W_i$ intersects with the fault window $F$ is rolled back, regardless of whether the fault affected the action.

The hidden dependency graph isn’t used to decide this rollback, so as not to add information beyond the public fault epoch and action windows.

Even detecting the public fault can be an information leakage risk. If Witness only notices a fault when a secret-dependent branch tries to use the faulty service, then the fact that there is a public fault is a leak about Alice and Bob’s run.

## Spending trust

So far, we have worked through some of the basic timing side channel attacks and how to fend them off. The second class of attacks we will focus on next is the bit composing setup we outlined in Section 3.

Our ideal-case scenario is to refuse an answer when the queries start to look adversarial. However, it is impossible to depend on correctly inferring the querier’s intent for a privacy guarantee. The attacker can have the individual queries look perfectly sound while still probing for unauthorised information.

In Witness, we put a cap on how much an individual can learn through repeated queries. We give them a finite disclosure budget, and each answer spends some of it. If the next answer would exceed the remaining budget, the node refuses the query. More precisely, the bound we require on cumulative disclosure is

$H_\infty(b\mid O)\geq H_\infty(b)-B_{\mathrm{spent}},\tag{4}$

where $B_{\mathrm{spent}}$ is the total disclosure budget the transcript has consumed. [Note 1: Disclosure bound. Here $H_\infty$ uses Smith’s average guessing-success definition [[1]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-smith2009), conditional on the observer’s prior information. $B_{\mathrm{spent}}$ bounds disclosure across all admitted execution paths. A rare answer can still identify the secret exactly.]

The simplest way to do this is to have a linear correspondence between information and budget. A Boolean answer costs one unit, while an answer with $k$ possible values costs $\log_2 k$ units.

This can also be nonlinear. If $\varphi(S)$ is the total information allowance in bits, after spending $S$ units of trust, then spending another $x$ units increases that allowance by $\varphi(S+x)-\varphi(S)$. For instance, with $\varphi(S)=\sqrt{S}$, four units of trust permit two bits in total. But if we apply it separately to four one-unit requests, we get four bits. So we have to do more accounting to work out how much more Alice can learn conditional on how much she had already spent.

The trickiest part of this setup is guaranteeing that the budget object we choose is resistant to manufacture. An adversary cannot be allowed more “budget” than they started with. More importantly, they should not be able to make new identities that they can use to harvest budgets faster than our per-query checks can adjudicate. The appropriate object is the “Trust Graph.” We will walk through the construction in more detail in a separate blog, but the important property relevant to Witness is sybil resistance, i.e., creating more identities does not give the adversary more information/disclosure.

When a contract begins, Witness takes a snapshot of the Trust Graph to determine the effective allowance of the querier. Clearly, the trust added cannot retroactively fund earlier probes and a rollback cannot restore the budget spent on an answer that the querier has already seen. If observers pool their answers as well, the trust graph can still bound what they can collectively learn about the protected source.

## Sealed prices

The range of possible applications for Witness is infinite. One interesting example is a private prediction market. Consider what a standard prediction market is doing. Participants possess some privileged information they use to trade against the current price. Their order flow then moves the price, which acts like an endogenous aggregate signal. Anyone looking at the price can then update their belief about the question posed by the market without having direct access to the information which moved the price [[2]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-wolfers-zitzewitz2006).

This coordination effect is exactly what makes free markets useful. However, some participants have paid to acquire information, while anyone observing the price can benefit from what they learned. Granted, the informed participants can earn trading profits, but their advantage diminishes when their information becomes reflected in the price. So the distribution advantages of price also make it difficult to capture the value of producing it [[3]](https://hyperstition.cc/architectural-considerations-from-building-witness#ref-grossman-stiglitz1980).

With Witness, we can instead keep the price behind a contract and charge for the right to read it. The market can still do “price discovery” in the traditional sense, but the contract can now specify who can see it and how much they can learn through repeated access. An interested party could then subsidise the market to buy the access for itself or an agent representing it.

The agent could then use private signals to decide how to trade against that price. There are many variations of this setup, but one possible arrangement is like so:

- A subsidiser funds the market and designates an agent allowed to read its price.

- Data owners authorise the agent to use their private signals in choosing a trade. The permission does not mean the private signal has to necessarily be public.

- The agent updates the market’s private state by executing the trade at a publicly scheduled time.

- Come settlement, the contract distributes any earnings according to an attribution/payment rule agreed prior to the signals being used, and the data owners could be compensated for their contributions.

Clearly, the disclosure rules have to cover settlement as well. Any visible payment for a known quantity can potentially reveal the execution price, so any transfer and receipt must be held to the same restriction standards that direct price reads are.

This gives us an interesting market that can aggregate private information, grant paid access to the resulting price, and compensate the people whose signals inform its trades. This example is just a taste of what is possible. To have a proper market design, we have to establish incentive compatibility, welfare guarantees and much more. We take up those questions in a separate blog post on information markets.

## References

- Geoffrey Smith (2009). [On the Foundations of Quantitative Information Flow](https://cs.au.dk/~askarov/lbs-course/2025/reading/qif.pdf). Foundations of Software Science and Computational Structures, pp. 288–302.

- Justin Wolfers and Eric Zitzewitz (2006). [Prediction Markets in Theory and Practice](https://www.nber.org/papers/w12083). NBER Working Paper No. 12083.

- Sanford J. Grossman and Joseph E. Stiglitz (1980). [On the Impossibility of Informationally Efficient Markets](https://www.aeaweb.org/aer/top20/70.3.393-408.pdf). American Economic Review, 70(3), pp. 393–408.

- Isaac Sheff, Tom Magrino, Jed Liu, Andrew C. Myers, and Robbert van Renesse (2016). [Transactions and the Trade-Off Between Security and Consistency](https://www.cs.cornell.edu/andru/papers/abrtchan/). ACM Conference on Computer and Communications Security (CCS).

- Radford M. Neal (2015). [Fast exact summation using small and large superaccumulators](https://arxiv.org/abs/1505.05571). arXiv:1505.05571.

- Jonathan Richard Shewchuk (1997). [Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates](https://www.cs.cmu.edu/~quake/robust.html). Discrete & Computational Geometry, 18, pp. 305–363.