# Privacy-Friendly Monero Transaction Signing on a Hardware Wallet

Dusan Klinec, Vashek Matyas

► To cite this version:

Dusan Klinec, Vashek Matyas. Privacy-Friendly Monero Transaction Signing on a Hardware Wallet. 35th IFIP International Conference on ICT Systems Security and Privacy Protection (SEC), Sep 2020, Maribor, Slovenia. pp.338-351, 10.1007/978-3-030-58201-2_23. hal-03440818

HAL Id: hal-03440818

https://inria.hal.science/hal-03440818

Submitted on 22 Nov 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Privacy-friendly Monero transaction signing on a hardware wallet

Dusan Klinec and Vashek Matyas

Masaryk University, Brno, Czech Republic,
xklinec@fi.muni.cz, matyas@fi.muni.cz

**Abstract** Keeping cryptocurrency spending keys safe and being able to use them when signing a transaction is a well-known problem, addressed by hardware wallets. Our work focuses on a transaction signing process for privacy-centric cryptocurrency Monero, in the hardware wallets. We designed, implemented, and analyzed a privacy-preserving transaction signing protocol that runs on a hardware wallet and protects the spending keys. Moreover, we also implemented a privacy-preserving multi-party version of the Bulletproof zero-knowledge prover algorithm, which runs on a hardware wallet with constant memory. We present the protocols and evaluate their performance on a real hardware wallet.

**Keywords:** Monero · transaction signing · Bulletproofs · zero-knowledge system · multi-party computation · hardware wallets.

## 1 Introduction

Cryptocurrencies gained popularity and increased adoption by general public in the recent years. They became a valuable asset worth protecting. In the vast majority of the cryptocurrency designs, the only thing needed to transact (spend) the coins is a cryptographic key (master key). Recently, we have seen several attacks on the software wallets storing the master keys and leading to coin thefts [4,11].

Software wallets are inherently vulnerable to malware threats, so users seek better ways to protect their cryptographic assets. One option is to use a dedicated hardware device, the hardware wallet, that stores the master key securely and performs the signature on the transactions specified by the user. The device can be equipped with a display to show the transaction details to the user (e.g., destination and the amount) and buttons to confirm the transaction information. As the hardware wallet (HW) is a special-purpose device, it has a much smaller attack surface than a PC. The HW is limited and usually needs a PC client for operation, e.g., transaction construction, transaction scanning.

Bitcoin, the first massively used cryptocurrency, does not provide much privacy to its users. i.e., the whole transaction history is stored in a public blockchain (append-only ledger), it contains source, destination addresses (cryptographic keys, pseudonymous identifiers), and transacted amounts in a clear form so the attacker can mount several chain analysis techniques to trace the
financial flow between the users. On the other hand, creating the signature and
implementing the logic in the HW is usually straightforward as it requires just
transaction serialization logic and ECDSA signature over the data.

We focus on a privacy-centric cryptocurrency, *Monero* [1], which is the most
used privacy-centric cryptocurrency<fnref n="1" />. In Monero, all destination addresses are
unique, and the amounts being transacted are hidden using Pedersen commit-
ments [9]. The secure implementation of the Monero transaction signing is thus
a more challenging task. Moreover, HWs are resource-constrained devices with
limited memory and computational power.

For the practical testing, we choose a Trezor HW model T<fnref n="2" /> (Trezor for short) as it represents a class of HWs with generally available processors used in the embedded devices, with around 100 kB of RAM. It runs Micropython<fnref n="3" />, a Python version for resource-constrained devices.

*Contribution:* This work builds on our previous technical report [5] and for an extended version of this paper please refer to the [6]. We designed and implemented a Monero transaction signing protocol for HWs. The protocol is simple, which helps with the security analysis. Moreover, it mimics the already deployed cold-signing protocol [5] used with offline Monero wallets. We implemented the protocol to Trezor and Monero codebases, and it is being used in practice. Moreover, we designed and implemented a secure multi-party protocol (MPC) version of a zero-knowledge proving system called Bulletproof [3], which uses constant memory and works on HWs. The MPC version protects private values, from PC-based attacker. To the best of our knowledge, this is the first MPC implementation of the Bulletproof runnable on HWs.

*General methods:* As the HW is a resource-limited device, the general methods for converting arbitrary protocols into MPC, such as Garbled circuits [10], are not applicable, as those usually require significantly more memory and running time than we have available. We thus resort to a more effective protocol offloading design tailored specifically to the application domain, to preserve the practical usability of the resulting protocol.

1.1 Cryptocurrency primer

The elementary operation of transacting a particular amount from a sender to a receiver is called *transaction*. The transaction is an atomic state transition. Transactions are stored in the blocks, the block contains a hash of a previously generated block, thus forming a ledger of blocks, a blockchain. A new block is created every 10 minutes.

Transaction has $|\mathcal{T}^{\text{in}}| = m$ inputs $\mathcal{T}_{j}^{\text{in}}$, $|\mathcal{T}^{\text{out}}| = p$ outputs $\mathcal{T}_{t}^{\text{out}}$ and a fee. The amounts values in the input and the output side have to be equal, i.e., $\sum_{j=1}^{m} v_{j}^{\text{in}} = \sum_{t=1}^{p} v_{t}^{\text{o}} + \text{fee}$, so the transaction is a valid state transition (and no value is lost or created). Let's denote transaction outputs TXOs. Transaction inputs are also

<footnote n="1">¹ By the market value https://coinmarketcap.com, accessed on 5. 1. 2020.</footnote>

<footnote n="2">² https://wiki.trezor.io/Trezor_Model_T</footnote>

<footnote n="3">³ https://micropython.org</footnote>
called unspent transaction outputs (UTXOs). UTXOs are addresses that have a non-zero balance that can be spent. A balance can be trivially computed by replaying all transactions recorded in the blockchain. Blockchain clients usually track all UTXOs and update the state with each new block.

Transaction construction is controlled from the PC client as it scans the blockchain for UTXOs that can be spent. A user enters the transaction recipient addresses and amounts on the PC. The client then performs the transaction signing protocol with an HW to obtain a signed transaction. The signed transaction is then broadcasted to the cryptocurrency network and eventually added to a block.

The Monero user wallet has two key-pairs, $(k^v, K^v)$ and $(k^s, K^s)$, the view-key, and spend-key, respectively. The view-key is used to scan the blockchain for incoming transactions to the user wallet; the spend-key is required to create a signature for spending the incoming coins.

## 1.2 Attacker model

HWs are considered as trusted in all attacker models in this paper, i.e., HW securely stores master keys, and an attacker can gain no knowledge by observing and tampering the HW device. We only focus on an attacker controlling the PC client. The honest-but-curious attacker model is defined by an attacker that obeys the protocol precisely but tries to learn new information observing the protocol transcripts. The malicious attacker model is stronger, an attacker can arbitrarily deviate from the protocol. He can start multiple instances of protocols, interleave protocol runs, send, replay, delay, or drop any protocol messages.

## 1.3 Notation

We use a standard notation used in the related literature, such as [1,3]. Due to the paper application domain in the Monero transactions, we use the elliptic curve (EC) Ed25519 [2] as a specialization of the cyclic group $\mathbb{G}$ of the prime order $l$, let's denote $\mathbb{Z}_l$ the ring of integers modulo $l$. The $\mathbb{Z}_l^*$ denotes $\mathbb{Z}_l \setminus \{0\}$. The $x \stackrel{\S}{\leftarrow} \mathbb{Z}_l^*$ denotes a uniform sampling of an element from $\mathbb{Z}_l^*$. Capital letters represent points on the curve $\mathbb{G}$, lower-case letters represent scalars from $\mathbb{Z}_l^*$ unless said otherwise. We use the EC additive notation for $\mathbb{G}$, e.g., $P+Q$ is a point addition, $aP = (P + \cdots + P)$ is a scalar multiplication, $0P = O$, i.e., neutral element, point in infinity. Let $\mathbb{F}^n$ denote a vector space over $\mathbb{F}$, the $\mathbf{a} \in \mathbb{F}^n$ is a vector from the vector space with elements $a_0, \dots, a_{n-1} \in \mathbb{F}$. The $\mathbf{a} \cdot \mathbf{b} = \sum_{i=0}^{n-1} a_i b_i$ denotes a dot-product of $\mathbf{a}, \mathbf{b} \in \mathbb{F}^n$, the $\mathbf{a} \circ \mathbf{b} = \{(a_i b_i)\}_i$ is element product. We also use Python notation for vector slicing, i.e., $\mathbf{a}[i] = (a_0, \dots, a_{l-1})$, $\mathbf{a}[i:] = (a_l, \dots, a_n)$. For $k \in \mathbb{Z}_l^*$, the $\mathbf{k}^n \in \mathbb{F}^n$ denotes the vector $k_{[l]} = k^i$. The $\mathcal{G}$ is a generator of the $\mathbb{G}$, i.e., a base point. Let's define a cryptographic hash function $\mathcal{H} : \{0,1\}^* \to \{0,1\}^{256}$, the $\mathcal{H}_p : \{0,1\}^* \to \mathbb{G}$ is a cryptographic hash function to curve points, $\mathcal{H}_s : \{0,1\}^* \to \mathbb{Z}_l^*$ is a cryptographic hash function to scalars. Moreover, let's define $H = \mathcal{H}_p(\mathcal{G})$, a point of unknown logarithm. Binary format of the scalars
and points is 256 bits long. Let's denote the binary concatenation as $||$ and a
key derivation function as $KDF(x) = \mathcal{H}(\mathcal{H}(x))$.

## 2 Transaction signing protocol

Ring signatures are signatures generated by a single private key $k_\pi$ correspond-
ing to the public key $K_\pi$ which is in the ring of unrelated public keys $\mathcal{R} =$
$\{K_0, \dots, K_\pi, \dots, K_n\}$. The verifier is not able to tell which $K_i \in \mathcal{R}$ generated
the signature. This provides n-anonymity for the signer. Keys $K_i, i \neq \pi$ are
called decoy keys. Let's define $n = |\mathcal{R}|$, i.e., the ring size.

Monero uses Schnorr-style multilayered linkable spontaneous anonymous group signatures (MLSAG) [8]. The linkability is a property that links signatures generated with the same private keys. The linked signatures have the same key image (explained later). Signatures with already seen key images are considered as invalid to protect from double-spending the same UTXO.

Monero uses the *Pedersen commitment* to conceal the transacted amounts and to prove that transaction input amounts are equal to transaction output amounts. A Monero *range proof* is a zero-knowledge proof that the TXO amount encoded in the scalar value $v \in \mathbb{Z}_l^*$ lies$^4$ in the interval of allowed values $[0, 2^N], N = 64$. The range proof is an essential part of the confidential transactions as it protects from overflows and new coin generation.

The *transaction generator* takes $\mathcal{T}^{\text{in}}$ and set of destination addresses and amounts $\mathcal{T}^{\text{out}}$ and produces a transaction with signature. The value $|\mathcal{T}^{\text{in}}|$ can be quite high and is limited by the fee the user is willing to spend for the transaction to be added to the blockchain and the current block size. The current Monero protocol version (0.15.0.1), i.e. hard-fork, specifies that for a valid transaction it holds that $2 \le |\mathcal{T}^{\text{out}}| \le 16$. Thus the $|\mathcal{T}^{\text{in}}|$ is the main limiting factor for the transaction generator with respect to the memory. The ring size $n$ is fixed to 11 at the current version, but it is likely to increase in the future.

It is not feasible to construct a transaction in the HW in one pass. Thus the
building process has to be separated into several steps so it can be computed
with limited memory. We designed, implemented, and tested the transaction
generation protocol that runs in the HW with unlimited $\mathcal{T}^{\text{in}}$ (the protocol).

**Transaction signing protocol with state offloading:** *The offloaded signing protocol* is described fully in the extended paper [6]. Here we explain only key ideas of the protocol construction.

A *state offloading* is required to build the transaction incrementally. Some
parts of the state are sent to the host for later retrieval during the transaction
construction. The protocol uses HMAC to protect the public state parts, e.g.,
parts of the final transaction, and an authenticated encryption (Chacha20Poly1305)
for private state information, e.g., *T*<sup>in</sup> private spending keys.

<footnote n="4">⁴ v in Pedersen commitment $\gamma G + vH$, $\gamma \stackrel{\$}{\leftarrow} \mathbb{Z}_l^*$. Refer to Section 3 for more details.</footnote>
All MLSAG signatures are generated in the HW, the $k^s$ never leaves the device, while the $k^v$ is exported to the host so it can scan all blockchain transactions to determine whether the funds were sent to the recipient wallet keys. Performing the blockchain scanning with the device would be inefficient.

The transaction is built on the host incrementally, from the information provided by the HW. In general, the host sends initial transaction information to the HW. The user is asked to confirm transaction details on the HW screen, such as destination address, amounts, and transaction fee. If confirmed, the HW generates HMACs for transaction input elements so they cannot be changed later (commitment to values).

Then all $\mathcal{T}^{\text{in}}$ are sent to the HW one by one; the HW derives required signing keys, serializes $\mathcal{T}^{\text{in}}$ to blockchain format, incrementally hashes information required for later MLSAG construction. Then destination information is sent one by one; the HW generates $\mathcal{T}^{\text{out}}$ related information, serializes $\mathcal{T}^{\text{out}}$ to the blockchain format, range proof generation (see Section 3) is handled. Finally, the MLSAG is generated per $\mathcal{T}^{\text{in}}$.

**Key construction scheme:** Let's describe HMAC key construction on the $\mathcal{T}^{\text{out}}$ example, generated after user confirmation. HW returns to the host $\mathcal{T}^{\text{out}}$: $\{\mathcal{T}_i^{\text{out}}, \text{HMAC}(\mathcal{T}_i^{\text{out}}, \text{key} = \text{KDF}(k^{\text{mac}} ||"\text{txdest}||i))\}_i$, where $k^{\text{mac}}$ is a random HMAC master key generated per-transaction. The HMAC keys construction prevents from changing destination specification later in the protocol by an attacker. All the offloading keys used in the protocol are generated correspondingly, i.e., the keys are unique per offloaded element to make the protocol strictly commit to the offloaded values and their ordering. The key is derived from the master keys, the domain separator, e.g., "txdest", and the item index.

**Encrypt-then-reveal:** In order to limit the attacker's reactivity, MLSAG signatures are returned encrypted to the host. The encryption key is returned to the host after the protocol finishes successfully.

**Analysis:** The protocol is based on the cold-signing protocol [5] implemented in Monero codebase, which takes all transaction inputs $\mathcal{T}^{\text{in}}$, transaction outputs $\mathcal{T}^{\text{out}}$, asks the user to confirm transaction outputs, and a fee and generates a valid Monero transaction. Cold-signing protocol is trivially secure as it is evaluated in a secure environment (offline Monero wallet), and the user confirms all transaction outputs. Our offloaded protocol mimics the cold-signing protocol. It is evaluated in a HW, which is considered a secure environment. The transaction is constructed incrementally, from the basic input blocks $\mathcal{T}^{\text{in}}$, $\mathcal{T}^{\text{out}}$ sent one by one to the HW. The user confirms the $\mathcal{T}^{\text{out}}$ on the HW, as it has a display and touch screen. After the confirmation is done, the HW generates HMAC for confirmed $\mathcal{T}^{\text{out}}$. Thus it cannot be later modified by an attacker.

Each call is guarded by a state automaton, set up in step 1 by the parameters of the transaction. This prevents from calling protocol methods in a different than expected order. Moreover, due to HMAC and encryption key construction, it is not possible to modify, reorder, reply, or drop the offloaded state elements. Protocol aborts if invalid input is provided.
The only place where the $k^s$ is used is during spend key computation, during $\mathcal{T}^{in}$ construction. The result of the computation is offloaded in an encrypted form, which could only be used as input in the last protocol step, during MLSAG generation per each $\mathcal{T}^{in}$. MLSAG signature is generated over hash commitment $m$, which hashes the entire transaction specification ($\mathcal{T}^{in}, \mathcal{T}^{out}$). The protocol is thus secure in the malicious attacker model as cheating in each protocol step is detected by HMAC, auth tag, or state transition failure.

The only information the attacker can obtain from the protocol runs (without a need to finish the protocol) is key images corresponding to the $\mathcal{T}_j^{in}$. The key images are part of the constructed transaction. As we need the host to sort key images so some kind of order-preserving encryption would have to be used to protect key images from leaking before the protocol finish. However, we do not consider this as a required measure as the key images are computed during the blockchain scanning once the transaction sent to our wallet has been found.

**Performance and space complexity:** The space complexity is determined by $O(n+p)$, i.e., by a ring size and the number of the transaction outputs, i.e., $n = 11$ and $p \le 16$ in the current Monero version. The whole ring is needed only for the MLSAG signature, which can be easily extended to support large rings. If the $p$ is increased later, the protocol can be easily changed to offload all output-related values. The transaction signing protocol implemented in Micropython for Trezor HW was tested with various input transactions. Refer to Table 1 for performance overview data.

<table><caption>Table 1: Performance of the transaction signing protocol on Trezor HW. The algorithm was tested on the emulator and Trezor T HW. Configuration is a tuple (#inputs, #outputs). The first metric, "Time emu", is a runtime in an emulator, other statistics are from runs on the real hardware. "$\Sigma$ Steps" is protocol computation time without communication overhead, "rounds" is a total number of message round-trips. Rows with "State" show a maximal state size over the protocol, where "real" is the real size measured in the implementation, "min" is the minimal space required, without Micropython objects overhead. Note that the range-proof is not included in the statistics as it is measured separately in section 3. It is visible that the state size is constant, and timing is linear to the number of inputs.</caption><thead><tr><th>Configuration</th><th>2-2</th><th>16-2</th><th>32-2</th><th>64-2</th><th>128-2</th><th>2-16</th></tr></thead><tbody><tr><td>Time Emu [s]</td><td>9.31</td><td>29.93</td><td>58.13</td><td>106.32</td><td>209.88</td><td>21.45</td></tr><tr><td>Time [s]</td><td>16.90</td><td>83.22</td><td>156.82</td><td>306.74</td><td>604.09</td><td>46.13</td></tr><tr><td>Σ Steps</td><td>12.49</td><td>56.30</td><td>106.69</td><td>207.33</td><td>408.42</td><td>36.62</td></tr><tr><td>Rounds</td><td>14</td><td>56</td><td>104</td><td>200</td><td>392</td><td>28</td></tr><tr><td>RAM [B]</td><td>41 264</td><td>42 176</td><td>42 208</td><td>42 048</td><td>58 512</td><td>41 376</td></tr><tr><td>State min [B]</td><td>2 385</td><td>2 385</td><td>2 385</td><td>2 385</td><td>2 385</td><td>4 406</td></tr><tr><td>State real [B]</td><td>5 315</td><td>5 315</td><td>5 315</td><td>5 315</td><td>5 315</td><td>9 224</td></tr></tbody></table>
## 3 Range proof

A range proof is a zero-knowledge proof that the amount encoded in a scalar $v \in \mathbb{Z}_l^*$ (256-bit number for Ed25519), lies in the interval $[0, 2^{64})$, without revealing the amount value. Range proof computations are the most resource expensive operations in the transaction construction (time and memory). Thus it makes sense to offload the computation to the host.

The range proofs make use of commitments $V = \gamma G + vH$, where $\gamma \stackrel{*}{\leftarrow} \mathbb{Z}_l^*$ is a mask, and the $V$ is part of the publicly stored information. If the attacker generates the masks in a special way, he can exfiltrate information about the keys or the transaction. From the binding property of the commitment scheme which relies on the discrete logarithm problem, it is infeasible to find a different $v', \gamma'$, s.t. $\gamma'G + v'H = \gamma G + vH$. The attacker already knows the amount as he observes the transaction construction, but knowing the masks enables the attacker to prove the amount to a third party (e.g., court). This poses a privacy risk as the attacker can prove that he has seen the transaction construction or knows the amount keys.

The *Bulletproof* [3] (BP) is the range proof system used in Monero. The proof size increases logarithmically with respect to the number of statements (transaction outputs). BP can prove statement of the form $M = 2^x$. We implemented the memory-optimized prover version for the Trezor HW, described in Algorithm 1.

**Space complexity:** Up to the while-loop on line 29, all vectors can be evaluated on-the-fly with a constant memory and low CPU overhead with just $v, \gamma$ stored. Vector foldings on lines 36-39 dominate the space complexity. Overall the space complexity is $O(MN)$. Please refer to full paper [6] for detailed analysis.

**Implementation:** We implemented the in-memory Bulletproof prover as specified in the Algorithm 1 and the verifier in Micropython and tested on the Trezor HW. The memory usage is $32(128M + 12\log(M)) + O(max(\log(N), M))$ B. The verification algorithm runs with $O(max(\log(N), M))$ memory. Table 2 shows the performance of the prover and the verifier implemented on the Trezor.

### 3.1 Offloaded Bulletproofs

Due to increasing space complexity, it is not possible to generate BPs with $M \ge 4$ on the Trezor. We thus designed a new privacy-preserving secure multi-party computation protocol (MPC) to compute Bulletproofs jointly with the PC host and an HW with a constant memory on the HW side. We do not consider the time and memory requirements of the protocol running on the host in the following.

A naïve offloading protocol computes all vector-related operations by chunking, i.e., exporting encrypted vectors to a host, then asks for vector chunks to compute the intermediate results. The vectors $l, r$ and dot-products $c_L, c_R, t$

<footnote n="5">5 Multiplying by $8^{-1}$ protects from small subgroup addition https://www.getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html</footnote>
<caption>**Algorithm 1 Bulletproof prover.** $N = 64, M = |v|, v$ is a vector of amounts</caption>

1 function BULLETPROOFPROVER(v, γ) ▷ Input: Amounts and masks
2 (V, A, S, T1, T2, τₓ, µ, x, h, l₀, i, l₁, i, r₀, i, r₁, i) ← BULLETPROOFPREFIX(v, γ)
3 lᵢ ← l₀, i + xl₁, i ▷ Vector l
4 rᵢ ← r₀, i + xr₁, i ▷ Vector r
5 t ← l · r; x' ← H_s(x||x||τₓ||µ||t) ▷ Evaluated with const. memory up to here
6 (L, R, a'₀, b'₀) ← BULLETPROOFLOOP(l, r, Ḑ, y⁻|H| ◦ Ḑ, MN, -1, x', x')
7 return (V, A, S, T1, T2, τₓ, µ, L, R, a'₀, b'₀, t)
8 function BULLETPROOFPREFIX(v, γ) ▷ varint encodes integer to bytes
9 Ḑᵢ∈[0,...,MN) ← H_p(H("bulletproof"||H||varint(2i + 1)))
10 Ḑᵢ∈[0,...,MN) ← H_p(H("bulletproof"||H||varint(2i)))
11 Vⱼ ← γⱼG + vⱼH ▷ Compute commitment vector V used on line 18
12 α ← $\$Z_l^*$ ▷ expand(v) = x: $\sum_{i=0}^{63} 2^i x_{64j+i} = v_j, j \in [0, |v|), x_i \in \{0, 1\}$
13 a_L ← expand(v); a_R = a_L - 1$^{MN}$
14 A ← $8^{-1} (\alpha G + \sum_{i=0}^{MN-1} a_{L,i} \hat{G}_i + s_{R,i} \hat{H}_i)$ ▷ Commitment over values⁵
15 ρ, R ← $\$ (Z_l^*)^2$ ▷ randVct(j) = x: $|x| = MN, x_i = H_s(\text{"mask"}||R||i||j)$
16 s_L ← randVct(0), s_R ← randVct(1)
17 S ← $8^{-1} (\rho G + \sum_{i=0}^{MN-1} s_{L,i} \hat{G}_i + s_{R,i} \hat{H}_i)$ ▷ Commitment over random masks
18 y ← H_s(H_s(V)||A||S); z ← H_s(y) ▷ Compute commitments over inputs
19 l₀ ← a_L - z1$^{MN}$; l₁ ← s_L ▷ Evaluated with const. memory, with v
20 ζᵢ ← z²+|i/N|2$^{i%N}$ ▷ Evaluated with const. memory and time
21 r₀ ← ((a_R + z) ◦ y$^{MN}$) + ζ; r₁ ← s_R ◦ y$^{MN}$
22 t₁ ← l₀ · r₁ + l₁ · r₀; t₂ ← l₁ · r₁
23 τ₁, τ₂ ← $\$ (Z_l^*)^2$
24 T₁ = 8⁻¹ (τ₁G + t₁H); T₂ = 8⁻¹ (τ₂G + t₂H)
25 x ← H_s(z||z||T1||T2)
26 τₓ ← τ₁x + τ₂x² + $\sum_{i=0}^{M} \gamma_i z^{i+2}$; µ ← ρx + α
27 return (V, A, S, T1, T2, τₓ, µ, x, h, l₀, i, l₁, i, r₀, i, r₁, i)
28 function BULLETPROOFLOOP(a', b', G', H', n', c, w, x')
29 while n' > 1 do
30 $\bar{n}$ ← n'; n' ← n'/2; c ← c + 1
31 c_L ← a'_{[0,...,n')} · b'_{[n',...,\bar{n})}
32 c_R ← a'_{[n',...,\bar{n})} · b'_{[0,...,n')}
33 L_c ← $8^{-1} ((\sum_{i=0}^{n'} a'_i \quad G'_{i+n'} + b'_{i+n'} H'_i) + (c_L x') H)$
34 R_c ← $8^{-1} ((\sum_{i=0}^{n'} a'_{i+n'} G'_i + b'_i \quad H'_{i+n'} + (c_R x') H)$
35 w ← H(w, L_c, R_c)
36 a'_{i∈[0,...,n')} ← w · a'_i + w⁻¹ a'_{i+n'} ▷ Scalar vector folding
37 b'_{i∈[0,...,n')} ← w⁻¹ b'_i + w · b'_{i+n'} ▷ Folding reduces vector size by 2
38 G'_{i∈[0,...,n')} ← w⁻¹ G'_i + w · G'_{i+n'} ▷ Hadamard folding
39 H'_{i∈[0,...,n')} ← w · H'_i + w⁻¹ H'_{i+n'} ▷ Folding reduces vector size by 2
40 return (L, R, a'₀, b'₀) ▷ vector L composed from L_c
<table><caption>Table 2: BP performance on the Trezor T HW. Verifier is faster than prover and requires significantly lower memory. Prover time and space complexity increase linearly to the input size. The *RAM min* shows the minimal amount of RAM required to cover the BP generation w.r.t. dominating cost - vectors, excluding the constants and state required for on-the-fly evaluation. The difference between Total RAM and minimal RAM is due to memory handling mechanisms in Micropython and constant memory overhead for on-the-fly vector evaluation.</caption><thead><tr><th></th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td>Prover outputs</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Time [s]</td><td>16.88</td><td>30.55</td><td>57.40</td><td>121.21</td><td>246.57</td></tr><tr><td>RAM min [B]</td><td>4 480</td><td>8 640</td><td>16 896</td><td>33 344</td><td>66 176</td></tr><tr><td>RAM total [B]</td><td>9 648</td><td>13 536</td><td>22 224</td><td>39 696</td><td>74 400</td></tr><tr><td>Verifier outputs</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Time [s]</td><td>5.12</td><td>9.58</td><td>18.56</td><td>39.00</td><td>80.40</td></tr><tr><td>RAM total [B]</td><td>5 664</td><td>6 256</td><td>6 912</td><td>7 616</td><td>8 512</td></tr><tr><td>Proof size [B]</td><td>704</td><td>800</td><td>928</td><td>1120</td><td>1440</td></tr></tbody></table>

can be computed incrementally as $t = \sum l_i r_i$. This yields a constant memory protocol, but with high communication overhead.

We present basic offloading techniques in the following paragraphs, which are used to transform the in-memory prover to the privacy-preserving MPC prover with constant memory.

**Dot-product offloading:** We can evaluate dot-products and foldings on the host privately, using homomorphic property of a *blinding*. We export the vectors $\pi_{a'}a', \pi_{b'}b'$ to the host, where $\pi_{a'}, \pi_{b'} \stackrel{\$}{\leftarrow} \mathbb{Z}_l^{*2}$ are random blinding scalars known only to the HW. The host computes the dot-product of blinded vectors $\bar{r} = \pi_{a'}a' \cdot \pi_{b'}b' = \sum \pi_{a'}a'_i \pi_{b'}b'_i = \pi_{a'}\pi_{b'} \sum a'_i b'_i$ and returns $\bar{r}$, i.e., blinded value $r$, to the HW. The HW then unblinds the $\bar{r}$ as $\pi_{a'}^{-1}\pi_{b'}^{-1}\bar{r} = r = a' \cdot b'$ to get the dot-product.

As the scalars are from $\mathbb{Z}_l^*$ and vector elements are essentially random, the attacker cannot infer $a'$ from $\pi_{a'}a'$. The $\pi_{a'}a'_0 = z$ does not have a unique factorization, i.e., $\forall z, x \exists y: xy = z; y = zx^{-1}$. Thus, a blinded vector is indistinguishable from an unblinded one for an attacker. Moreover, each element is divisor of 1 in $\mathbb{Z}_l^*$ so we cannot extract the blinding masks by GCD($\pi l_0, \pi l_1$) as it is undefined.

**Folding offloading:** A vector folding is defined as $a'_{i \in (0,...,n')} = wa'_i + w^{-1}a'_{i+n'}$, before folding it holds $|a'| = 2n'$, after the fold $|a'| = n'$. Computing the folding on the host saves CPU and communication round-trips. Only the $w$ is needed for the host to compute the folding, but it is desired to keep internal constants secret to preserve the privacy-preserving property of the offloading. Thus $\{w, w^{-1}\}$ are incorporated into blinding masks.
We have two distinct blinding constants for one vector. One for the lower half (LO), the other for the higher half (HI): {$\pi_{a'_{LO}}, \pi_{a'_{HI}}$}. The folding is then computed in two parts, as we preserve the LO/HI blinding also for the folding result vector, as shown in equation 1, so this blinding scheme is composable.

Let's thus define $\mathbf{x}_{LO} = \mathbf{x}_{[\frac{n}{2}]}$ and $\mathbf{x}_{HI} = \mathbf{x}_{[\frac{n}{2}]}$ for vector $\mathbf{x}$ of length $n$, $Lh(0)=LO$, $Lh(1)=HI$, then define folding constants as $\phi_{\mathbf{x},j}, \mathbf{x} \in \{\mathbf{a}', \mathbf{b}', \mathbf{G}', \mathbf{H}'\}$, $j \in [0, 3]$, $\phi_{\mathbf{x},j} = \theta_{\mathbf{x}_{Lh([j/2])}} w^{1-(2j/4)} \pi_{\mathbf{x}_{Lh([j/2])}}$, e.g., $\phi_{\mathbf{a}',0} = \theta_{\mathbf{a}'_{LO}} w \pi_{\mathbf{a}'_{LO}}^{-1}$, where $\theta$ are randomly generated blinding masks from $\mathbb{Z}_{l}^{*}$ for the next round. The $\phi$ is constructed so it cancels the blinding mask $\pi$, multiplies by $w^{\{1,-1\}}$, and multiplies by a new blinding mask $\theta$. It is also easy to observe that folding offloading is compatible with the dot-product offloading, as $c_L = \mathbf{a}'_{LO} \cdot \mathbf{b}'_{HI}$, $c_R = \mathbf{a}'_{HI} \cdot \mathbf{b}'_{LO}$.

The blinding technique differs from the dot-product offloading due to constants {$w, w^{-1}$} being used. We need to have distinct blinding masks for each term in the folding sum, so an attacker cannot extract the $w$ from the blinding masks. The folding offloading works in the following way:

$$ \theta_{a'_{LO}} \mathbf{a}'_{[\frac{n}{2}]} \leftarrow \underbrace{\left(\theta_{a'_{LO}} w \pi_{a'_{LO}}^{-1}\right)}_{\phi_{a',0}} \left(\pi_{a'_{LO}} \mathbf{a}'_{[n':]}\right) + \underbrace{\left(\theta_{a'_{LO}} w^{-1} \pi_{a'_{HI}}^{-1}\right)}_{\phi_{a',1}} \left(\pi_{a'_{HI}} \mathbf{a}'_{[n':]}\right) \\ \underbrace{\theta_{a'_{HI}} \mathbf{a}'_{[\frac{n}{2}]:}}_{\text{High half of new } \mathbf{a}'_{HI} \text{ blinded by } \theta_{a'_{HI}}} \leftarrow \underbrace{\left(\theta_{a'_{HI}} w \pi_{a'_{LO}}^{-1}\right)}_{\phi_{a',2}} \left(\pi_{a'_{LO}} \mathbf{a}'_{[n':]}\right) + \underbrace{\left(\theta_{a'_{HI}} w^{-1} \pi_{a'_{HI}}^{-1}\right)}_{\phi_{a',3}} \left(\pi_{a'_{HI}} \mathbf{a}'_{[n':]}\right) \quad (1) $$

**Initial G', H' folding:** The folding of the $G', H'$ cannot be performed as defined above as the vectors are protocol constants in the first round (known to attacker), i.e., $\pi_{G'} = \pi_{H'} = 1$. Thus the attacker could extract $w$ from the $\phi$ and unblind the folded vectors. We define folding constants $\phi^{(0)}$ for the first round as in the equation 2: $\phi_{\mathbf{x},j}^{(0)}, \mathbf{x} \in \{\mathbf{G}', \mathbf{H}'\}, j \in [0, 3], \phi_{\mathbf{x},j}^{(0)} = \theta_{\mathbf{x}_{Lh([j/2])}} w^{(2j/4)-1} + (1-j/2)\pi_{\mathbf{x}_{LO}}, \text{e.g., } \phi_{\mathbf{G}',0}^{(0)} = \theta_{\mathbf{G}'_{LO}} w^{-1} + \pi_{\mathbf{G}'_{LO}}$.

The host computes the folding with the $G', H', \phi^{(0)}$, the HW then generates a vector of correction points $\pi_{G'_{LO}} G'_{LO}$ and returns it to the host so the host can remove extraneous component caused by the additive blinding mask $\pi_{G'_{LO}}$.

$$ \theta_{G'_{LO}} G'_{[\frac{n}{2}]} + \pi_{G'_{LO}} G'_{LO} \leftarrow (\theta_{G'_{LO}} w^{-1} + \pi_{G'_{LO}}) G'_{[n':]} + (\theta_{G'_{LO}} w) G'_{[n':]} \quad (2) \\ \theta_{G'_{HI}} G'_{[\frac{n}{2}]:} + \pi_{G'_{LO}} G'_{LO} \leftarrow (\theta_{G'_{HI}} w^{-1} + \pi_{G'_{LO}}) G'_{[n':]} + (\theta_{G'_{HI}} w) G'_{[n':]} $$

**$L_c, R_c$ offloading:** Observe that $L_c$ from line 33 contains 3 independent components: $L_c = 8^{-1} \left( \left( \left( \sum_{i=0}^{n'} a'_i G'_{i+n'} \right) + \left( \sum_{i=0}^{n'} b'_{i+n'} H'_i \right) \right) + (c_L x') H \right)$. Each component can be computed by the host with blinded vectors. The $c_L$ is offloaded dot-product, host returns $\pi_{a'_{LO}} \pi_{b'_{HI}} c_L$. The sum $\sum_{i=0}^{n'} a'_i G'_{i+n'}$ is computed from the blinded vectors in a similar way, the host returns: $\bar{L}_{cA} = \pi_{a'_{LO}} \pi_{G'_{HI}} \sum_{i=0}^{n'} a'_i G'_{i+n'}$, the other sum is analogical. The HW unblinds the components and computes $L_c$.
**Analysis:** The offloaded Bulletproof prover as defined in Algorithm 2 was implemented in the Micropython for the Trezor and performance of the implementation was evaluated. Please refer to Table 3 and Fig 1 for performance metrics. **Attacker constraints:** As we transformed the Algorithm 1 to the Algorithm 2 using offloading steps that preserve the privacy of the computation, the protocol remains secure in the honest-but-curious attacker model. The malicious attacker could tamper the intermediate results to learn new information or break the security properties of the protocol. However, such manipulation leads to an invalid proof with overwhelming probability due to the use of a cryptographic hash function on line 16. Rejection of an invalid proof leads to attack being detected. We could also run a Bulletproof verifier on the generated proofs, abort the transaction signing, and alert the user on the invalid proof. As in-memory verifier runs in constant memory, the protocol becomes malicious attacker resistant; however, the running time increases. There might be more effective methods to verify intermediate results or catch attacker cheating with high probability. Such extensions are left for future work.

<table><caption>Table 3: Offloaded BP performance on the Trezor emulator and Trezor, parameters: $b_{tch} = 32, n_{thr} = 32$. Offloaded version is faster and requires only constant memory compared to in-memory prover. The table shows a total time and memory consumption for the HW PC-based emulator and the HW. The performance statistics for previous in-memory implementation is included for comparison. The HW part contains maximum RAM needed for all steps of the algorithm, which gives minimal RAM needed for the offloaded algorithm. Real total RAM usage is higher due to Micropython memory management, message recoding, serialization, etc.</caption><thead><tr><th>Prover outputs</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td>Time Emu [s]</td><td>6.97</td><td>9.69</td><td>14.75</td><td>25.48</td><td>44.81</td></tr><tr><td>Total RAM Emu [B]</td><td>24 896</td><td>25 056</td><td>25 120</td><td>25 408</td><td>25 632</td></tr><tr><td>Time HW [s]</td><td>25.10</td><td>37.49</td><td>59.03</td><td>99.96</td><td>184.02</td></tr><tr><td>Total RAM HW [B]</td><td>8 768</td><td>8 928</td><td>9 488</td><td>10 656</td><td>12 816</td></tr><tr><td>Max state RAM used [B]</td><td>5 576</td><td>7 720</td><td>7 848</td><td>8 040</td><td>8 360</td></tr><tr><td>Time HW in-mem [s]</td><td>16.88</td><td>30.55</td><td>57.40</td><td>121.21</td><td>246.57</td></tr><tr><td>RAM HW in-mem [B]</td><td>9 648</td><td>13 536</td><td>22 224</td><td>39 696</td><td>74 400</td></tr></tbody></table>

# 4 Related work

The work in [7] presents a signature protocol for a Ledger<fnref n="6" /> HW (Ledger for short). Ledger is an HW with a secure element (SE). Using the SE and the overall architecture limits the usable RAM to a few tens kB. Thus they had to

<footnote n="6">⁶ https://www.ledger.com</footnote>
**Algorithm 2** Bulletproof prover with offloading. $b_{tch}$ is a number of elements to offload in one batch, $n_{thr}$ is a $n'$ threshold for in-memory finish

1 **function** BULLETPROOFPROVEROFFLOADED(v, γ)
2   (V, A, S, T1, T2, τ<sub>x</sub>, μ, x, h, l<sub>0,i</sub>, l<sub>1,i</sub>, r<sub>0,i</sub>, r<sub>1,i</sub>) ← BULLETPROOFPREFIX(v, γ)
3   t ← 0; c ← -1; n' ← MN; π ← $\S(Z_l^*)^8$ ▷ New random blinding masks π
4   **for** i ∈ [0, ..., $\frac{MN}{b_{tch}}$) **do** ▷ Compute t, export blinded l, r vectors
5     l<sub>c</sub> ← l<sub>0,j</sub> + x l<sub>1,j</sub>; r<sub>c</sub> ← r<sub>0,j</sub> + x r<sub>1,j</sub>, j ∈ [ib<sub>tch</sub>, (i + 1)b<sub>tch</sub>)
6     l̅<sub>c</sub> ← π<sub>a'<sub>δ(i)</sub></sub> l<sub>c</sub> ▷ δ(x) = x < n' ? LO : HI, l̅<sub>c</sub> means blinded l<sub>c</sub>
7     r̅<sub>c</sub> ← π<sub>b'<sub>δ(i)</sub></sub> r<sub>c</sub>; t ← t + l<sub>c</sub> · r<sub>c</sub>
8     Send(l̅<sub>c</sub>, r̅<sub>c</sub>) ▷ l̅<sub>c</sub>, r̅<sub>c</sub> are a', b' for the first while iteration
9     w ← x' ← H<sub>s</sub>(x||x||τ<sub>x</sub>||μ||t) ▷ t = l · r
10    Send(y) ▷ The host needs y to compute H' and L<sub>c</sub>, R<sub>c</sub> related sums
11    **while** n' > 1 **do** ▷ The y is public, computable from the final proof
12    n̄ ← n'; n' ← n'/2; c ← c + 1
13    Receive(cL̄, cR̄, L̄<sub>cA</sub>, L̄<sub>cB</sub>, R̄<sub>cA</sub>, R̄<sub>cB</sub>) ▷ L̄<sub>cA</sub> is first blinded sum from the L<sub>c</sub>
14    L<sub>c</sub> ← 8<sup>-1</sup> (π<sub>a'<sub>LO</sub></sub><sup>-1</sup> π<sub>G'<sub>HI</sub></sub><sup>-1</sup> L̄<sub>cA</sub> + π<sub>b'<sub>HI</sub></sub><sup>-1</sup> π<sub>H'<sub>LO</sub></sub><sup>-1</sup> L̄<sub>cB</sub> + x'π<sub>a'<sub>LO</sub></sub><sup>-1</sup> π<sub>b'<sub>HI</sub></sub><sup>-1</sup> cL̄H)
15    R<sub>c</sub> ← 8<sup>-1</sup> (π<sub>a'<sub>HI</sub></sub><sup>-1</sup> π<sub>G'<sub>LO</sub></sub><sup>-1</sup> R̄<sub>cA</sub> + π<sub>b'<sub>LO</sub></sub><sup>-1</sup> π<sub>H'<sub>HI</sub></sub><sup>-1</sup> R̄<sub>cB</sub> + x'π<sub>a'<sub>HI</sub></sub><sup>-1</sup> π<sub>b'<sub>LO</sub></sub><sup>-1</sup> cR̄H)
16    w ← H<sub>s</sub>(w||L<sub>c</sub>||R<sub>c</sub>); θ ← $\S(Z_l^*)^8$ ▷ Compute w, generate blinding θ
17    **if** n' ≤ n<sub>thr</sub> **then** ▷ Finish in-memory with original algorithm
18    Receive(a', b', G', H'); Unblind to obtain {a', b', G', H'}
19    (L, R, a'<sub>0</sub>, b'<sub>0</sub>) ← BULLETPROOFLOOP(a', b', G', H', n', c, w, x')
20    **return** (V, A, S, T1, T2, τ<sub>x</sub>, μ, L, R, a'<sub>0</sub>, b'<sub>0</sub>, t) ▷ Combine L, R
21    Send(φ<sub>x,l</sub><sup>(c)</sup>: x ∈ {a', b', G', H'}, l ∈ [0, 3]) ▷ Compute and send blinding
22    **if** c = 0 **then**
23      Compute and send folding correction points for G', H', by chunks
24      π ← θ ▷ Update blinding masks for the next round

implement a more low-level protocol with basic operations such as: generate key image, $H_s(x)$, $xP$, get sub-address secret key, etc.

Low-level cryptographic operations are computed in the device, acting as crypto proxy. The protocol is tightly integrated into the Monero codebase, and it imposes maintainability challenges as a Monero algorithm change usually requires an HW signing protocol change. The low-level protocol design makes the security analysis difficult as the information flow is quite complicated, and the attacker can call several methods in an arbitrary order, which can lead to information leak and potential vulnerability.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Privacy-preserving multi-party BP with $M = 16$ cryptographic operations and timing breakdown. The most expensive operations are $aP$ and point recodings.</figcaption></figure>

To the best of our knowledge, the overall protocol is not documented nor analyzed. The low-level commands are documented in [7] only. The protocol does not use a state machine to guard the command calls.

To the best of our knowledge, there is no other Monero transaction signing protocol published nor used. Our protocol addresses issues with the security analysis, works on higher abstraction level, has very simple interface and thus reduced attack surface, it is more stable over protocol changes, easy to maintain, and needs less message round trips. Moreover, we compute the Bulletproofs in HW thus protecting blinding masks.

# 5 Conclusion

We designed, implemented, and tested a secure Monero transaction signing protocol for HWs. We designed and analyzed the memory and time complexity of the zero-knowledge proofs (range-proofs, Bulletproofs [3]), algorithms focused on low-memory consumption so they can be computed in HW. The memory consumption is linear in the number of inputs / UTXOs. The results can be easily applied to other protocols based on ring signatures, Pedersen commitments, and Bulletproof range proofs.

We also designed, implemented, and tested a privacy-preserving two-party Bulletproofs computation protocol with constant memory, enabling the computation of large input instances securely and in a reasonable time. This is the first privacy-preserving Bulletproof prover implementation running on an HW in constant memory. Techniques used in the protocol are applicable to similar protocols like Bulletproof, and Bulletproof also has several applications outside of Monero.

The implemented protocols are practically usable. The transaction signing protocol has been deployed since Nov. 7, 2018, integrated both to Trezor and
Monero codebases. All implemented sources are available online under a permissive open source license at: https://github.com/ph4r05/monero-tx-paper.

*Acknowledgement:* We thank our colleagues Petr Švenda and Marek Sýs, who provided valuable insights and ideas that helped to improve the protocols. Thanks also go to SatoshiLabs employees, Tomáš Sušánka, Jan Pochyla and Ondřej Vejpustek who did the security review of the design and implementation and helped significantly with simplifying the protocol implementation. We also thank the anonymous reviewers for their feedback and suggestions for improvement, and to Daniel Slamanig for shepherding the final revisions of our submission. This work was partly supported by the Czech Science Foundation project 20-03426S. For an extended paper please refer to the [6].

## References

1. Alonso, K.M.: Zero to monero: First edition. https://www.getmonero.org/library/Zero-to-Monero-1-0-0.pdf (2018), accessed: 20. Feb 2020

2. Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. Journal of Cryptographic Engineering 2(2), 77–89 (Sep 2012). https://doi.org/10.1007/s13389-012-0027-1

3. Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bullet-proofs: Short proofs for confidential transactions and more. pp. 315–334 (05 2018). https://doi.org/10.1109/SP.2018.00020

4. Goodin, D.: Official monero website is hacked to deliver currency-stealing malware. https://arstechnica.com/information-technology/2019/11/official-monero-website-is-hacked-to-deliver-currency-stealing-malware (2019), accessed: 26. Feb 2020

5. Klinec, D.: Monero wallet trezor integration. https://github.com/ph4r05/monero-trezor-doc (2018), accessed: 26. Feb 2020

6. Klinec, D., Matyas, V.: Privacy-friendly monero transaction signing on a hardware wallet, extended version. Cryptology ePrint Archive, Report 2020/281 (2020), https://ia.cr/2020/281

7. Mesnil, C.: Ledger device for Monero. online (2019), https://github.com/LedgerHQ/ledger-app-monero, Accessed: 20. Feb 2020

8. Noether, S.: Ring signature confidential transactions for monero. Cryptology ePrint Archive, Report 2015/1098 (2015), https://eprint.iacr.org/2015/1098

9. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Advances in Cryptology, CRYPTO '91. pp. 129–140. Springer Berlin Heidelberg (1992)

10. Yao, A.C.: Protocols for secure computations. In: 23rd Annual Symposium on Foundations of Computer Science. pp. 160–164. IEEE (1982). https://doi.org/10.1109/SFCS.1982.88

11. Young, J.: Malware Steals User Funds & Bitcoin Wallet Keys From PCs. https://cointelegraph.com/news/malware-steals-user-funds-bitcoin-wallet-keys-from-pcs-bitcoin-altcoins-targeted (2017), accessed: 26. Feb 2020