# SUAVE Information Leaking

The following is an abstraction of a problem. For more context on application, a brief description is attached below.

### Description
**The setting**
An adversary is given a finite set of functions $\mathcal{F}$ where every element $f_i\in\mathcal{F}$ is a mapping from a set $X$ to a set $L$. $\mathcal{F}$. The adversary is also given a prior distribution, $\mathcal{D}$, over $F$.

**The game**
A function $f^*$ is drawn from $\mathcal{D}$. The adversary does not know $f^*$.

Now there are $n$ rounds. In each round $i$, the adversary selects any $x_i\in X$ and is told $f^*(x_i)$.

After the $n$'th round, the adversary attmepts to guess $f^*$.

**Example**
$X:={(1,1),(0,1),(0,0),(1,0)}$
$L:={0,1}$
$\mathcal{F}:={\text{AND, OR, NAND, XOR}}$
$\mathcal{D}$ is uniform over F.
$n=1$

A valid policy for the adversary is to query (1,1). If $f^*(1,1)=1$, choose either OR or AND according to a cointoss. If $f^*(1,1)=0$ choose NAND or XOR in the same way.

The success rate of this policy if $\frac{1}{2}$ which is better than complete random guessing which yields $\frac{1}{4}$.

This is a relatively basic example with small sets. In general, $|L|,n<<|F|,|X|$. One can also reasonably assume $\mathcal{D}$ is power law distributed.

**Question**
* Is there existing literature which studies this setting? Information theory and computational learning theory seem like the most obvious areas to investigate.
* Given a setting, how much can the adversary learn from the best possible policy? One way of measuring this is the reduction of entropy from the prior distribution to the posterior belief after the last query as a function of $n$.
* Assuming the adversary is polynomially bounded, what is the best policy they can find given the setting?

### The actual application
This question comes up when considering doing computation on private information which may leak some information. More particularly, this problem comes up in a blockchain setting in which a transaction must be ordered in a block which requires doing computation on the transaction.

A transaction in blockchain can be considered a function which takes as input the state of a VM and outputs the future state. In this case $\mathcal{F}$ is the set of all transactions (finite because of gas limits), $X$ is the set of all possible VM states and $L$ are the bits of information leaked (e.g. boolean for success/revert of the transaction). One can simplify the problem by considering $\mathcal{F}$ the set of all swaps, with each swap parameterised by pool, size and slippage limit.