-
Notifications
You must be signed in to change notification settings - Fork 2
/
comparison.tex
165 lines (117 loc) · 13 KB
/
comparison.tex
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
\section{Comparison}
\label{comparison}
\newcolumntype{R}[2]{%
>{\adjustbox{angle=#1,lap=\width-(#2)}\bgroup}%
l%
<{\egroup}%
}
\newcommand*\rot{\multicolumn{1}{R{45}{1em}}}% no optional argument here, please!
\def\half{{\freeserif \char9680}}
\def\full{{\freeserif \char9679}}
\begin{table*}
\caption{A comparison of the cryptocurrency wallets in practice. Proposals with an asterisk* appear for the first time in this work. Server lookups only refers to the computation the server is required to do to determine what to serve to a wallet during the synchronisation process and does not include previous or continuous computation like maintaining an address index. Partial satisfaction of a criterion is denoted with \half{} and full satisfaction is denoted with \full.\label{tbl:comparison}}
\centering
\begin{tabular}{r|c|c|ccc|cccc}
\multicolumn{3}{c}{} &
Communication &
Client computation &
\rot{Server lookups} &
\rot{Open participation} &
\rot{Privacy} &
\rot{Chain check} &
\rot{Uncensorability}
\\ \hline
\textbf{Proposal}&
\textbf{TX Model}&
\textbf{Privacy Model}&
\multicolumn{3}{c|}{\textbf{Performance $\Theta(\cdot)$}}&
\multicolumn{4}{c}{\textbf{Security}} \\
\hline
%name &mode&transp &bandwidt&client &server &open &priva&dblad&onval&uncen
Full Node&UTXO&Transparent&$n+m$&$n+m$&$1$ &\full&\full&\full&\full\\
SPV &UTXO&Transparent&$n+y\lg{\alpha}$&$n+y\lg{\alpha}$&$m$&\full&\half&\full& \\
Electrum &UTXO&Transparent&$n+y\lg{\alpha}$&$n+y\lg{\alpha}$&$1$& & &\full& \\
Neutrino &UTXO&Transparent&$n+y\alpha$&$n+y\alpha$&$1$ &\full&\half&\full&\full\\
Explorer-based&Both&Transparent&$y$ &$1$ &$1$ & & & & \\
Full Node&Account&Transparent&$n+m$&$n+m$&$1$ &\full&\full&\full&\full\\
Electrum-like*&Account&Transparent&$n+y\lg{\alpha}+\lg{m}$ &$n+y\lg{\alpha}+\lg{m}$ &$1$ & & &\full&\full\\
Full Node&UTXO&Private&$n+m$&$n+m$&$1$ &\full&\full&\full&\full\\
SPV &UTXO&Private&$n+m$&$n+m$&$1$&\full&\full&\full&\full\\
MyMonero &UTXO&Private&$y$&$1$&$m$& & & & \\
Superlight*&Both&Transparent&$\polylog{n} + y + \lg{m}$&$\polylog{n} + y + \lg{m}$&$1$&\full& &\full&\full\\
Superlight*&UTXO&Private&$\polylog{n} + y\lg{\alpha}$&$\polylog{n} + y\lg{\alpha}$&$m$&\full& &\full& \\
\hline
\end{tabular}
\end{table*}
We now provide a comparison between all the wallets presented. The notation used can be found in~\cref{notation-comparison}.
\begin{table*}
\caption{The notation used throughout our comparison.\label{notation-comparison}}
\centering
\begin{tabular}{r|l}
$n$ & number of all blocks \\
$m$ & number of all transactions \\
$y$ & number of relevant transactions (implicating the wallet user) \\
$\alpha$ & number of transactions per block \\
\end{tabular}
\end{table*}
Our performance comparison is asymptotic in terms of the aforementioned variables and is broken down on the following aspects.
\begin{itemize}
\item \textbf{Communication}: The communication complexity between the wallet and server necessary to fully synchronise from scratch.
\item \textbf{Client computation}: Any computation it is necessary for the wallet to perform in order to finish synchronisation and enter a usable state (for funding transaction descriptions, balance and transaction history).
\item \textbf{Server lookups}: Computation the server needs to decide what data it needs to relay to the wallet. In the case of SPV this can be bloom filter checks, in the case of private wallets it can be trial-decryption with a viewing key.
\end{itemize}
Our security comparison focuses on the following aspects.
\begin{itemize}
\item \textbf{Open participation}: Whether participating as a wallet's server is possible for everyone.
\item \textbf{Privacy}: Whether the wallet reveals information about the user's addresses to any server in order to synchronise.
\item \textbf{Chain check}: We say that a wallet fulfills chain check whether the wallet will only accept transactions included in the best chain.
\item \textbf{Uncensorability}: Whether the server is not able to lie by omitting transactions from the wallet.
\end{itemize}
A comparison of the wallets in tabular form is presented in \cref{tbl:comparison}.
\subsection{Communication}
The full node requires the most amount of communication, $n+m$ as all full blocks must be downloaded. This is the case for both UTXO and account models.
SPV implementations for transparent cryptocurrencies require $n+y\lg{\alpha}$ communication, which is broken down as (a) each block header (b) each relevant transaction and (c) a Merkle inclusion proof for each transaction. In the worst case each transaction belongs to a different block and no re-use of parts of the proof can take place thus we need $y$ proofs of size $\lg{\alpha}$ each.
Electrum-based implementations for UTXO have the same communication complexity. In Neutrino, all block headers need to be downloaded as well. In addition, for every block including a relevant transaction it also needs to be downloaded in full. In the worst case each relevant transaction will be included in a different block yielding a communication complexity of $n+y\alpha$.
Our Electrum based construction for accounts requires $n+y\lg{a}+\lg{m}$ communication, with the $\lg{m}$ representating the state trie proof size. We assume that the state trie grows as $\Theta(m)$.
Explorer-based wallets and MyMonero are all querying a trusted-third party and obtain the relevant transactions directly, thus have a communication complexity of $y$.
SPV wallets for private cryptocurrencies that do not reveal the private viewing key to a server require that all full blocks be downloaded, resulting in $n+m$ communication complexity.
Our superlight wallets based on some NIPoPoW superlight client have a communication complexity of $\polylog{n} + y + \lg{m}$, and our private superlight wallets have communication $\polylog{n} +y\lg{\alpha}$.
\subsection{Client computation}
Full nodes need to verify all blocks and transactions in history resulting in $n+m$ computation.
In SPV wallets, for each block header verification takes place and for each relevant transaction verification of its attached Merkle proof takes place, thus client computation is also $n+y\lg{\alpha}$. The same holds for Electrum-based wallets.
Our Electrum based construction for accounts requires $n+y\lg{a}+\lg{m}$ computation.
For Neutrino the client computation is $n+y\alpha$, as every header is verified and the full block including each transaction is also verified.
Explorer-based wallets base their security on a trusted third party and perform no verification of what they obtain from the server, thus yielding a complexity of $1$. The same is true for privacy wallet MyMonero.
Our private superlight wallets based on NIPoPoWs verify NIPoPoW infix proofs and for each relevant transaction its inclusion in a block of the proof, resulting in a client computation of $\polylog{n} + y\lg{\alpha}$. Our transparent superlight wallets only verify a single Merkle inclusion proof after syncing through the superlight client, resulting in $\polylog{n} + y + \lg{m}$ computation.
\subsection{Server lookups}
A full node server (its peer) does not need to perform any lookup to evaluate what it needs to send to the client, yielding lookups of order $1$.
BIP-37 SPV's weak point is in server lookups, as the server looks though every single transaction in history to evaluate if it matches the provided bloom filter or not, thus it has the worst server computation complexity of all proposals, $n+m$.
An Electrum server, simply relays all block headers, and because it maintains an index of addresses to transactions where it can just look up the client's advertised addresses, resulting in a constant number of lookups.
The strong point of Neutrino is server lookups compared to BIP-37 that it is designed to replace. The server simply acts as a relay of information so the number of lookups is constant.
Explorer-based wallet servers (i.e. explorers) also hold an index of addresses to their corresponding transactions as Electrum servers do. Similarly to electrum, server lookups are constant.
\subsection{Open Participation}
The full node network is P2P and fully open to participation. Additionally full nodes usually act as servers for BIP-37 SPV wallets, making them to open to participation.
Server addresses are hardcoded in the Electrum software so participation is limited.
Neutrino is planned to be integrated in the full node P2P protocol which makes participation open.
For explorer-based wallets, the server address is hardcoded in the software, this is not a P2P protocol and participation is not open.
\subsection{Privacy}
A full node has the best privacy as everything is downloaded thus no network peer can distinguish which transactions or blocks are of interest. The address of the wallet is never revealed to the network.
SPV wallets reveal a lot of information to the servers, even though the addresses are not directly revealed as shown in~\cite{gervais2014privacy}.
For private cryptocurrencies, SPV wallets that download full blocks but don't verify the transaction validity while relying on SPV security are fully private. However solutions like compact blocks which provide a constant factor optimization need to be treated carefully. The reason is that after the wallet detects the compressed transactions that are relevant to its secret key, it may request to get the full transactions for some reason (for example to examine the transaction's memo field in Zcash). This would lead to privacy loss. To mitigate this the suggestion in~\cite{compact-blocks} is to ask for all transactions in the block the transaction is included in instead of the single transaction.
In Electrum, and explorer-based wallets addresses are directly provided to the servers for efficiency.
For Neutrino, addresses are not leaked directly, however full blocks are only received when they contain transactions of interest which could yield some information about the identity of the client to an adversary. In~\cite{bip157} the mitigation proposed is that full blocks be queried from servers at random. However in the face of a Sybil attack~\cite{sybil} the same loss of privacy ensues.
In MyMonero and our superlight client solution for private cryptocurrencies the private viewing key is directly provided to the server, leading to complete privacy loss.
\subsection{Chain check}
\paragraph{Motivation.} If the wallet does not verify the transactions it receives, we show an easy attack that can be performed against its user. Assume the user of the wallet is a vendor that provides an item for some fee in Bitcoin. A transaction that looks like it directs funds to the vendor can very easily faked. A full node would not accept that transaction, as it spends inputs that are already spent or never existed. However, if the wallet performs no check that the transactions received are in the best chain, it cannot know that the transaction is fake. The attack works as follows. The server, who now is a customer of the vendor, presents the vendor's wallet with a fake transaction. The wallet shows the transaction but performs no check and considers it valid. The vendor is satisfied enough and ships the item, for which the customer never actually paid.
The full node by definition verifies that any transaction used is contained in the best chain.
BIP-37 SPV wallets and Electrum perform verification of Merkle proofs of inclusion against the longest header-chain provided. By SPV security we know that chain is actually the best chain a honest full node would adopt, so transactions are actually verified against inclusion in the best chain.
Neutrino also maintains the best chain due to SPV security. For blocks that contain transactions of interest the whole block is downloaded and verified against some header in the best header chain.
Explorer-based wallets do not have any notion of a chain locally and trust the transactions provided. Thus the server could provided transactions that are not part of the best chain and the wallet would have no way of knowing.
Our superlight wallet constructions synchronise the best chain due to NIPoPoW security. All transactions provided are checked against blocks in that chain.
\subsection{Uncensorability}
A full node cannot be censored as it obtains all transactions and holds the full blocks.
Unfortunately for most other solutions: SPV, Electrum (UTXO-based), explorer-based, MyMonero the server can very easily not include transactions and the wallet has no way of knowing.
For Neutrino however, as long as the filters are correct, transactions cannot be censored. If a filter matches the whole block is downloaded and verified.
For our Electrum construction in the account model, a transaction-omitting server can be easily identified.
Finally, for our ideal superlight wallet construction as proven in~\cref{superlight-uncensorability} no censorship of transactions can take place.
For our superlight wallet construction for private cryptocurrencies no such commitment exists to prevent censorship and the server may lie by omitting transactions with no way to be detected.