From 745c30cf96d142f569ef315692da743bc758b66f Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Wed, 12 Sep 2018 22:31:38 +0200 Subject: starting point for an ILP model for coin selection --- coinselection/ilp.tex | 133 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 133 insertions(+) create mode 100644 coinselection/ilp.tex (limited to 'coinselection/ilp.tex') 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} -- cgit v1.2.3