summaryrefslogtreecommitdiff log msg author committer range
path: root/coinselection/ilp.tex
blob: ee74b60e78c48be7cc067a195738cd1476fb85db (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 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}