-
Notifications
You must be signed in to change notification settings - Fork 2
/
transparent-utxo.tex
129 lines (92 loc) · 16.2 KB
/
transparent-utxo.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
\section{Transparent UTXO-based Wallets}
\label{transparent-utxo}
A transaction description specifies the desired outputs of a transaction and a fee. In the simplest case of sending some funds to a specific address, the transaction description is comprised of a single P2PKH output.
A wallet needs to be able to turn a transaction description into a valid transaction in a process called funding. To fund a transaction description, the wallet performs the following steps:
\begin{itemize}
\item Collect a set $S$ of unspent transaction outputs spendable by the public key such that $$\sum_{o \in S} o.\text{value} \ge \textsf{value}$$
\item Create a change output directed back to the public key\footnote{A new public key is normally generated through the seed, but we study a simplified model here.} such that
$$\sum_{input} input.\text{value} - \sum_{output} output.\text{value} = \textsf{fee}$$
\item For each unspent transaction output in $S$, generate its unlocking script and use it as an input. In the typical case the unlocking script includes the signature of said transaction with the secret key of said output recipient.
\end{itemize}
The balance of a wallet can be obtained as the sum of the values of all unspent outputs destined to public key.
The transaction history of a wallet can be extracted from the set of all transactions implicating the public key. Specifically, inputs which are spent by the secret key are debits, and outputs which are directed to the public key are credits.
\subsection{Full Node}
A full node contains in its state the complete chain with full blocks, that include all of their transactions. In addition, the chain is assumed to be verified for validity.
\paragraph{Full construction.}
When presented with a public key, the full node wallet starts evaluating all transactions in every block from genesis up to the tip to detect which ones implicate the user's public key. This process is linear in the chain size, thus $\Theta(n)$.
\paragraph{Reduced functionality mode.}
A full node needs to hold at all times the state at the blockchain tip in order to be able to verify potential new blocks extending the tip. For UTXO-based cryptocurrencies this state is exactly the UTXO. When presented with a public key, the wallet, instead of looking through all transactions in history to obtain the full user's history, can locate all currently unspent outputs directed to the user by looking through the UTXO set. In this way the user's balance can be directly obtained as the sum of such outputs. However, the transaction history is not known but new transactions can be generated without a problem.
If the UTXO is stored as a list, performance is linear in its size. However, the UTXO can easily be indexed by address, which makes detection $\Theta(1)$.
\paragraph{In practice.}
Cryptocurrencies are defined by their full nodes so the implementation already exists, so they are the easiest to build a wallet on top of. Usually the wallet is included in the bundle of software that the full node ships with. This is the case with Bitcoin~\cite{bitcoin}, Litecoin~\cite{litecoin}, Dogecoin~\cite{dogecoin}, Ergo~\cite{ergo}, and many other cryptocurrencies.
\subsection{BIP-37 SPV}
SPV was first described in the Bitcoin whitepaper~\cite{bitcoin} and proposed how transactions can be verified by a node without them holding the full block chain, but instead by only holding the header chain.
The idea is as follows: a light node only requests and holds the header chain, that is only the header part of each block (which in Bitcoin is 80 bytes) and not the full block. When someone wishes to prove a transaction took place to an SPV node, they need to provide (a) the transaction (b) the id of the block that contains it and (c) a Merkle proof of inclusion to the Merkle root included in said block. The SPV node can check that the claimed block is part of its local best header chain and the Merkle proof provided is valid against the block's Merkle root.
For BIP-37 SPV, the server protocol supports the following special calls:
\begin{enumerate}
\item $\texttt{filterload}(\textsf{bloom-filter})$: sets the connection bloom filter to the one provided
\item $\texttt{getblock}(\textsf{height})$:
\begin{enumerate}
\item if the connection bloom filter is set, returns a partial block for $\chain[h]$ with:
\begin{enumerate}
\item the block header
\item only the transactions of the block with outputs that match against the bloom filter
\item a multi-element proof of inclusion in the block transaction tree for all the aforementioned transactions
\end{enumerate}
\item otherwise: returns the full block $\chain[h]$
\end{enumerate}
\end{enumerate}
Using this functionality of an SPV node as a building block and the server protocol, we examine how an SPV wallet according to BIP-37~\cite{bip37} can be built. The SPV wallet connects with the full node network. There, it establishes connection with some server. Remember the aim of the wallet is to figure out all transactions relevant to a specified public key $pk$. The wallet constructs a bloom filter that includes $pk$ and sets it as the connection bloom filter via a \texttt{filterload} call. After that it starts sending \texttt{getblock} requests to the server, starting from the genesis block.
For every block the server returns, it scans each transaction for matches to the set bloom filter. To the wallet, the block header is sent along with the transactions. Finally for verification, a multi-element Merkle proof of inclusion (named Partial Merkle Tree in BIP-37) for all the matching transactions is also sent. The wallet repeats \texttt{getblock} calls until it reaches the blockchain tip. By that point and assuming an honest peer, the full transaction history is known, along with the balance, and new transactions can be successfully created. The process is illustrated in detail in~\cref{alg.bip37}.
\input{algorithms/bip37}
\paragraph{In practice.} A well known implementation of BIP-37 SPV is included in the bitcoinj library~\cite{bitcoinj}, which is a full Bitcoin implementation in Java. Andreas Schildbach's famous Android Bitcoin wallet~\cite{schildbach} is based on that library, as well as decentralized exchange Bisq~\cite{bisq}. Other applications that implement BIP-37 SPV wallets include BRD~\cite{brd} and OpenBazaar~\cite{openbazaar}. Other libraries that implement BIP-37 include uspv~\cite{uspv} and its fork spvwallet~\cite{spvwallet} (available both for Bitcoin and Bitcoin Cash~\cite{bch-spv}).
Note that the protocol may seem wasteful, especially in case the header chain is already synced as it forces us to re-download the whole header chain. Additionally, it may seem wasteful that the peer needs to process every single transaction in history in order to service the peer. It has been shown that not only is it wasteful but can be an exploitable Denial-of-Service vector~\cite{todd-bip37-attack}. This lead to the reference implementation of Bitcoin, Bitcoin Core, to disable BIP-37 server functionality by default on full nodes~\cite{bip37-disable}. These inefficiencies are mitigated in the next protocol we are going to discuss.
%TODO: talk about how the server can withhold transactions
\subsection{Electrum}
\label{utxo-electrum}
%TODO: checkpoints
Electrum~\cite{electrum} was the first alternative and so-called ``light'' wallet for Bitcoin after the reference implementation.
The protocol it utilizes is as follows. First, the wallet connects to 10 servers chosen from a hardcoded list in the software. One of them is selected as primary at random. The servers speak an Electrum-specific protocol called Stratum which follows the design originally proposed in~\cite{stratum} and not the full node protocol.
In Electrum, servers hold an address index over all historical transactions. In early versions~\cite{electrumserver} of the server the index was arranged in a Merkle Patricia Trie~\cite{ultimate}. The most widely used server implementation~\cite{electrumserverrust} does not arrange the index in this way and simply relies on an underlying key-value store.
The wallet obtains all the header-chains advertised by its servers and verifies their Proof-of-Work. It then only keeps the heaviest valid chain for further processing. Subsequently it makes use of the \texttt{block\-chain.\allowbreak script\-hash.\allowbreak get\_history}
\footnote{The full API offered by an Electrum server is shown in \url{https://electrumx.readthedocs.io/en/latest/protocol-methods.html}}
API call to obtain all transactions concerning the address of the user. For each of these transactions it requires a Merkle proof of inclusion that is valid against some block in the heaviest chain. The full process of syncing is illustrated in~\cref{alg.electrum}.
We remark that the Electrum protocol is more efficient than the previous SPV wallet solution. Unfortunately, this comes at the cost of directly revealing the user's addresses to the remote server. An Electrum server customarily maintains an address index for all historical transactions, making servicing the \texttt{get\_history} very efficient, in contrast with the heavy work a full node has to do to service an SPV wallet.
\input{algorithms/electrum}
\subsection{Neutrino}
Neutrino is a new proposal for more efficient light syncing on Bitcoin which aims to be an improvement over SPV.
The simplest of its variants works as follows. It requires a hard or soft fork that is yet to occur for Bitcoin. With this fork, every block header includes a commitment to a bytearray which represents information about the block's transactions. Specifically, the bytearray which is called the \emph{filter} is a Golomb-Coded Set~\cite{golomb1966run}
which encodes the set of all output scripts and the scripts of the outputs the inputs spend (except \texttt{OP\_RETURN}s for technical reasons). The full construction for the filter is described in~\cite{bip158}.
With this filter in place the light wallet works as follows. Initially, it downloads all block headers as usual and verifies them. Then it proceeds to download the filter corresponding to each block. It then checks locally for every block if it contains transactions of interest by making use of the filter. If a block contains transactions of interest, all its transactions are requested without witness data (e.g. signatures and data belonging to unlocking scripts). Then from the transactions obtained the wallet only keeps the actual transactions of interest and discards the rest. The process is illustrated in~\cref{alg.neutrino}.
\paragraph{Deployment paths.}
We look at two ways of implementing Neutrino filters in an existing cryptocurrency like Bitcoin.
\paragraph{Forks.}
First, with a soft-fork or hard-fork a commitment to the filter can be included in each block. With a soft-fork the commitment is included in the coinbase transaction, similar to how the wtxid root is included for SegWit~\cite{segwit}. With a hard-fork the commitment is included directly in the block header as a new field. The soft-fork is also indirectly commited in the header due to the transaction Merkle Tree root in the header. The commitment can be verified by additionally verifying a Merkle proof of inclusion for the coinbase transaction against the tree root in the header and checking that the coinbase transaction itself contains the filter commitment. The hard-fork implementation of a Neutrino client is illustrated in~\cref{alg.neutrino}.
\paragraph{Majority vote.}
Another way to utilize Neutrino filters without adjusting the block structure and thus eliminating the need for either a soft- or hard-fork is to ask all servers for the filter of each block and pick the one with the most votes as valid, if a majority of the server has voted on it. This requires us to harden our security assumptions about the set of servers the wallet is connected to. Whereas previously we required that at least one server is honest, now we require that the majority of servers is honest.
\paragraph{The filter chain.}
\def\fltr{\text{filter}}
In~\cite{bip157} a construction is put forth which is secure under our standard assumption of at least one honest server in $\mathcal{S}$. The construction introduces the notion of a filter chain, which is a hash chain of block filters. More formally if $\fltr(\chain[i])$ refers to the Neutrino filter of block $\chain[i]$, the filter chain $F$ for the block chain $\chain$ is defined for $0 \le i < |\chain|$ as
\[
F[i] = \left\{
\begin{array}{cl}
H(F[i-1], H(\fltr(\chain[i]))) & \text{if } i > 0 \\
H(\fltr(\Gen)) & \text{otherwise}
\end{array}
\right.
\]
where every element of the filter chain is called a \emph{filter header}. Neutrino servers compute this chain based on their filters.
The construction on a high-level works as follows. After first syncing the header-chain $\chain$, the wallet connects with many Neutrino servers and requests all their filter chains. If two servers disagree on their filter chains we wish to tell who is honest and who is dishonest. The wallet finds the first filter header they disagree on, and obtains the filters for the corresponding block from both servers, as well as the full block. It then checks if one of the provided filters is invalid against the full block, and if it is the server that sent it is dishonest and the competing filter chain wins. This competition takes place for all disagreements and is how the honest filter chain is decided. Finally, the full filters can be downloaded from any server and verified against the local filter chain. The rest of the protocol proceeds as normal.
\input{algorithms/neutrino}
The improvements over SPV are twofold:
\paragraph{Privacy.} In an SPV wallet, the transactions of interest to the wallet are directly leaked to the peer, except with some relative deniability due to the bloom filter's false positive rate. Due to the low false positive rate of a bloom filter and the widely known transaction linking heuristics that can be applied~\cite{meiklejohn2013fistful,gervais2014privacy}
the peer can be almost certain which transactions belong to the same entity, breaking the pseudonymity of Bitcoin.
\paragraph{Server performance.} Observe how in Neutrino the server does no special computation for each client in contrast with an SPV server. In Neutrino servers are essentially relays of information, which is much cheaper and makes it more appealing to operators to operate them.
\paragraph{Client performance.} Additionally, in contrast with SPV, if the wallet happens to hold the header-chain through some means, it can just obtain the filters without the need to redownload the already downloaded headers as is the case with SPV.
However these improvements come at the cost of bandwidth. For each block its corresponding filter must be downloaded to detect relevant transactions in that block. The filter size for a 1.4MB block is approximately 20KB~\cite{jimmysong}. This is a significant overhead compared to SPV, where no such filter needs to be downloaded.
\paragraph{In practice.}
Neutrino is currently implemented in the bchd full node~\cite{bchd}, giving an easy option to any bchd full node to act as a Neutrino server if they so desire. The homonymous Neutrino wallet~\cite{neutrino-wallet} for Android works for Bitcoin Cash and uses the filter-chain variant of the Neutrino protocol. The Lightning wallet~\cite{lightning-wallet} makes use of their Lightning Lab's inhouse Neutrino library~\cite{neutrino-library} that implements the filter-chain variant of the Neutrino protocol.
\subsection{Explorer-based}
Most wallets in practice are explorer based. An explorer based wallet does not connect to full nodes or peers that relay block headers, only to a blockchain explorer. It requests the user's transactions from the explorer, but does not verify that the transactions are all included in blocks in the best chain. From them the wallet determines the UTXO set and can thus fund transaction descriptions, compute the balance and show the transaction history. Since no transaction verification is taking place, the explorer is a trusted third party.
\paragraph{In practice.}
The most popular wallets implement explorer-based solutions including Yoroi~\cite{yoroi}, Exodus~\cite{exodus} and Coinbarn~\cite{coinbarn}. Additionally, the apps that utilize hardware wallets like Ledger~\cite{ledger-live} and Trezor~\cite{trezor-beta} work in this manner.