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}
|
