starting point for an ILP model for coin selection

1 files changed, 133 insertions, 0 deletions

diff --git a/coinselection/ilp.tex b/coinselection/ilp.tex
new file mode 100644
index 0000000..ee74b60
--- /dev/null
+++ b/coinselection/ilp.tex
@@ -0,0 +1,133 @@
+\documentclass{article}
+\usepackage{amsmath,amssymb}
+\begin{document}
+
+\section{ILP variables}
+
+\begin{description}
+\item[$c$] Let $c \in {\cal C}$ represent a type of a fresh {\em coin} available in the wallet.
+      Coins differ by type if they have a different denomination, fees or expiration date.
+\item[$a_c$] Let $a_c \ge 0$ represent the number of available fresh coins of type $c \in {\cal C}$.
+\item[$d_c$] Let $d_c > 0$ represent the denomination of coins of type  $c \in {\cal C}$.
+\item[$f^{op}_c$] Let $f^{op}_c \ge 0$ represent the fee for of coins of type  $c \in {\cal C}$
+      with $op \in \{withdraw,deposit,refresh,refund\}$.
+\item[$e_c$] Let $e_c \in {\mathbb R}^+$ be a cost function associated with
+      the expiration time for coins of type $c \in {\cal C}$.  Larger values
+      are used to express longer expiration times and thus less urgency.
+      $e_c \le f^{refresh}_c + f^{withdraw}_c$ (as otherwise we could just refresh
+      immediately).\footnote{This is a slight simplification, as the refresh itself
+      changes the denomination. So technically this formula depends on the exact coins
+      we would obtain from a refresh. But in a first approximation, some bound like this
+      should hold for sanity.}
+\item[$p$] Let $p > 0$ be the amount to be paid in the spend/deposit operation (deposit ILP only)
+\item[$f$] Let $f \ge 0$ be the amount of fees the merchant would cover in the spend/deposit operation (deposit ILP only)
+\item[$w$] Let $w > 0$ be the amount to be withdrawn (withdraw ILP only)
+\end{description}
+
+The solution to compute is represented by the coin selection:
+\begin{description}
+\item[$s_c$] Let $s_c \in {\mathbb R^+_0}$ represent the contribution of coins of type $c$
+             to the deposit operation (deposit ILP only)
+\item[$n_c$] Let $n_c \in {\mathbb N^+_0}$ represent the number of coins of type $c$
+             selected for the deposit/withdraw operation.
+\end{description}
+
+
+We will use an additional variable to model the non-linearity that arises
+from the customer possibly paying fees above the threshold $f$:
+\begin{description}
+\item[$\tau$] Let $\tau \in \{0,1\}$ represent the customer paying some fees ($s=1$) or no fees ($s=0$).
+\end{description}
+
+We will use the big-M method to stress that customers paying any fees is bad.\footnote{Note that
+we could use a smaller $M$ to trade-off paying fees for using coins close to expiration. So maybe
+$M$ should just be a constant to represent this trade-off instead of the traditional big-$M$.}
+Thus, let $M$ be a sufficiently ``big'' number.  We will use $\alpha$ as an
+additional cost factor to model the bandwidth and computational cost per coin.
+
+
+\section{Withdraw ILP}
+
+Simple model:
+
+\begin{align}
+  \max \sum_{c \in {\cal C}} n_c \cdot d_c
+     - \sum_{c \in {\cal C}} n_c \cdot f^{deposit}_c
+     - \sum_{c \in {\cal C}} n_c \cdot \alpha \\
+  \texttt{such that} \quad
+  \bigwedge_{c \in {\cal C}} n_c \cdot (d_c + f^{withdraw}_c) &\le w \label{eq:sound} \\ 
+       n_c &\in {\mathbb N_0} \label{eq:nc} 
+\end{align}
+
+Explanations:
+\begin{description}
+\item[\eqref{eq:sound}] The withdraw operation is within the budget constraints.
+\item[\eqref{eq:nc}] Force selected coins to be a discrete number.
+\end{description}
+
+The above model fails to consider expiration periods of
+coins. However, is realistic to assume that expiration periods of
+freshly withdrawn coins will be roughly equal.  Coins types with equal
+denominations and fees where only the expiration time is worse should
+simply be excluded from ${\cal C}$ to reduce the size of the problem.
+
+It also deliberately fails to consider at all what types of coins we
+already have in the wallet, as that may disclose information about us
+which might hurt anonymity.  This model also fails to capture that we
+might {\em like} to have coins in the range where we typically spend
+them. Again, biasing withdrawal based on such data might have negative
+implications on privacy.
+
+
+\section{Deposit ILP}
+
+\begin{align}
+  \min &M \cdot \tau + \sum_{c \in {\cal C}} s_c 
+                     + \sum_{c \in {\cal C}} n_c \cdot \alpha)
+                     + refresh-cost \\
+  \texttt{such that} \quad
+  \bigwedge_{c \in {\cal C}} n_c \cdot d_c &\ge s_c  \label{eq:coinnum} \\ 
+  \bigwedge_{c \in {\cal C}} n_c &\le a_c \label{eq:exists} \\
+       \sum_{c \in {\cal C}} s_c &\ge p \label{eq:amount} \\
+       \sum_{c \in {\cal C}} (s_c - f^{deposit}_c \cdot n_c) + f &\ge p \label{eq:fees} \\
+       \sum_{c \in {\cal C}} s_c - \tau p &\le p \label{eq:tau} \\
+       \tau &\in \{0,1\} \label{eq:bin} \\
+       n_c &\in {\mathbb N_0} \label{eq:nc} \\
+       s_c &\in {\mathbb R^+_0} \label{eq:r}
+\end{align}
+
+Explanations:
+\begin{description}
+\item[\eqref{eq:coinnum}] This equation ensures that the number of coins we selected of a type
+  is sufficient to cover the total amount we want to pay with this type of coin.
+\item[\eqref{eq:exists}] This equation ensures that we do not select more coins of any type
+  than we have in the wallet.
+\item[\eqref{eq:amount}] The merchant requires that the amount we pay exceeds the contract
+  amount, irrespective of fees which the merchant may cover.
+\item[\eqref{eq:}] The merchant requires that we pay any left-over fees that are not covered
+  by the merchant.
+\item[\eqref{eq:}] Force $\tau$ to be 1 if we pay more than the contract amount (i.e. we cover
+  fees or otherwise simply pay more than necessary).
+\item[\eqref{eq:bin}] Force $\tau$ to be 0 or 1 as per our model.
+\item[\eqref{eq:nc}] Force selected coins to be a discrete number.
+\item[\eqref{eq:r}] Force coin contributions to be non-negative.
+\end{description}
+
+Note that the refresh cost is missing, as for that we will need to introduce
+a dependency on a withdraw operation as well!
+
+TODO: introduce additional variable to model when coins need to be
+refreshed, and model the refresh cost itself!
+
+
+\section{Refresh ILP}
+
+The refresh ILP is basically the withdraw ILP.
+
+\section{Refund ILP}
+
+Probably OK to use a simplistic solution at the merchant; let's leave it out for now.
+
+
+
+\end{document}