Mapping Ring Signatures and Stealth Addresses in Monero

With an example from a recent XHV hack (of June 2021)

Introduction

I originally published this article on Medium, where it is still available.

Since Monero has been forked and used as a basis for multiple other blockchains, the same concepts of Ring Signatures and Stealth Addresses also apply more broadly to those forked blockchains as well. One of these forked projects is the Haven Protocol (XHV) private stablecoin project. The example I will use is from the June 2021 XHV hack, highlighting an interplay of the Stealth Addresses and Ring Signatures, and how they were relevant in how the XHV developers tried to address the hack.

Since the exploits were not fully rolled back on the XHV blockchain, the data should still be there to check in practice for anyone interested. As long as the blockchain exists, anyway. In any case, lets start with a brief look at the relevant Monero privacy features to set the stage.

Monero Privacy Features

Monero uses multiple privacy enhancing mechanisms. These include Pedersen Commitments, Ring Signatures, Ring Confidential Transactions (RingCT), and Stealth Addresses. These can be divided into techniques for hiding the amount of Monero transferred in a transaction, hiding the receiver of a transaction, and hiding the sender. That’s a lot of hiding there, so lets see about each one.

Transaction Amounts

One core aspect of transaction anonymity is the transaction amount, i.e., how much funds is the transaction spending / sending. This is relevant to hide the amount itself, but also for the sake of correlating the inputs of one transaction with outputs of another transaction. For example, if you could look at a specific sum that is sent in one transaction, and find the same sum spent later in another transaction, you could deduce that the recipient of the first transaction is likely the spender of the second one, or that it matches the price of some other asset that you think was acquired.

Monero originally did not hide the amounts, and the transaction input and output sums were visible on the blockchain. You can still see this if you look at the earlier Monero transactions on the blockchain, for example this one from year 2014 in block 100000.

These days Monero uses a cryptographic scheme called Pedersen Commitment to hide the amounts. I described the Pedersen Commitment in detail in my article on Zero Knowledge Proofs. Related to this, later in this article I also discuss Ring Signatures, which also used to need to take the amounts into account. However, since the introduction of the RingCT protocol, the Ring Signatures now also hide the amounts along with the Pedersen Commitment.

So, in general, with regards to transaction amounts, the current Monero-based blockchains hide them well, and this is very transparent to the user. That is, the user does not need to really concern about it, as it happens always and automatically when using the protocol.

Transaction Receiver

The approach to hiding the recipient of a transaction in Monero is called Stealth Addresses. There appears to be some ambiquity with regards to what a Stealth Address means in the Monero community, but here I refer to its use as the transaction receiver addresses visible on the blockchain.

Stealth addresses are different from the wallet addresses. The Monero wallet address, as I refer to it here, is the one you get if you start the official Monero Command Line (CLI) wallet, and type the “address” command. Or the same in GUI or whatever wallet you use. This wallet address actually never appears on a Monero-based blockchain, only the Stealth Addresses do.

Given a target (receiver) wallet address, the sender wallet generates a one-time Stealth Address. This generated Stealth Address is used in the blockchain as the transaction receiver address. Elliptic Curve mathematics are used to create a Stealth Address from public keys encoded in the given receiver wallet address, along with using a large randomized factor. This makes each Stealth Address unique. Even if the same sender sends Monero to the same receiver, the Stealth Address is always different and unique for each transaction. This is the mechanism to hide the transaction recipient.

For the details of building Stealth Addresses, I recommend this excellent Stack Exchange post, and similarly excellent article by Luigi1111. When looking at the blockchain, without matching private keys, a Stealth Address cannot be matched to any wallet address. Only the receiver has access to the private keys matching the public keys used to generate the Stealth Address, and thus only their wallet can identify transactions intended for them.

Monkey See, Monkey Do (a Doodle)

To make this a bit more visual, I made the following most beautiful doodle about the mail system as a metaphora for how a Stealth Address works.

My most impressive doodle on using mail as a metaphora for a Stealth Address. Pics from Pixabay: monkey, envelope 1, envelope 2, envelope 3, heads 1, heads 2, heads 3, heads 4, trashcan, piggymailman.

Consider the process in the figure in 7 steps listed in it:

  1. George (the Monkey on left) wants to send 10 Monero to Bob (balding guy on right). So he starts to build a Monero transaction, and putting the 10 Monero in it.
  2. George has Bob’s wallet address. Maybe he found it from Bob’s Github project, asking for donations. George wants to send a few bucks. Using the public keys encoded in Bob’s public wallet address, George’s wallet generates a unique Stealth Address to send funds to Bob.
  3. George puts this newly generated Stealth Address on the 10 Monero transaction as the receiver address.
  4. George gives the transaction to the postman for delivery. The postman here represents the Monero peer-to-peer blockchain network. Consisting of nodes running the Monero Daemon software.
  5. The postman, or in this case the Monero network, delivers a copy of the transaction to every single user of the blockchain. Or their wallets.
  6. Everyone tries to read and open the transaction by attempting to fit their private keys to the Stealth Address. Or their wallet automatically does this.
  7. Everyone else discards the transaction, since their keys did not match, except Bob, whose private keys match the public keys George used from his wallet address. So Bob gets the 10 Monero and adds them to his wallet (piggybank) for later spending.

For the purposes of this article, the key takeaway is that for each transaction a unique receiver address is generated, and this is the one you see on the blockchain as the transaction receiver address. And this is (what I call) the Stealth Address. This is an important element for the next step of hiding the transaction sender using Ring Signatures, and how we can later use this to look for links between the Ring Signatures and Stealth Addresses. The XHV hack I discuss later will illustrate this link more concretely.

Transaction Sender

As I noted already, the approach to hiding the sender of a transaction in Monero is called Ring Signatures. A Ring Signature is so named due to the ring-like structure in how the algorithm is applied. The general idea of this algorithm is to create an anonymity set of possible signers, and hide the true sender/signer in that anonymity set. A signer in this case refers to a transaction output (Stealth Address) that could be spent in the transaction the Ring Signature is attached to. The following illustrates a Ring Signature (yes, its just a doodle based on my understanding):

My Ring Signature doodle. Green is the real tx, hiding in yellow decoys.

In the above figure, I colored T9 (as Transaction Output 9 in the ring) in green to illustrate it being the real input in this case. This is just for illustration, as the real input / signer is randomly placed on the ring. Because if it was always at the same position, it would be obvious which one it is. The Ring Signature algorithm processes these in a ring-like sequence, hence the name.

Monero currently enforces a ring size of 11, meaning the ring contains the real transaction input and 10 fake decoy transaction outputs (sometimes called mixins). Ring size used to be open to user change, but the forced count of 11 is currently used to avoid distinct ring sizes giving away additional metadata about specific users and thus weakening the overall anonymity set.

The signatures in a ring are generated using a set of Stealth Addresses from real transactions on the blockchain. Anyone can prove that one of the signatures is real, but not which one. This gives every ring participant plausible deniability. The real signer is of course the one who sends the real funds, or spends the output they received at that Stealth Address. But you cannot tell which of the 11 it is. Further, a key image is included in each transaction spend to make sure each output is only spent once.

For details on Ring Signatures implementation, I recommend the excellent Stack Exchange answer for Monero and RingCT specifics, or the Wikipedia article with example code for the original Ring Signature scheme.

For the purposes of this article, it is enough to understand that Stealth Addresses define the transaction recipient, and when a transaction output is spent, the Stealth Address of that spent output appears in the transactions Ring Signature. But the Stealth Address may also appear as fake decoys in other transactions.

Visualize it: Stealth Address and a Ring Signature from XHV Explorer

To illustrate, here is a screenshot of the Haven protocol (XHV) explorer showing one of the hacked coinbase outputs (normally amounts are hidden but coinbase / miner transactions show them):

Screenshot of a coinbase output on XHV chain. This link should take you to it, if the explorer exists as used to.

Note that the above screenshot shows how each transaction output has a visible Stealth Address for the receiver. And it is always unique even if going to the same receiver wallet. All the outputs in the above screenshot are actually paid to the same (hacker) wallet, but have different Stealth Address each. In the above screenshot I highlighted one row with the 101k xUSD output. Let’s map it to a Ring Signature.

Here is a screenshot of the explorer, showing how the above highlighted Stealth Address is used in a Ring Signature:

Screenshot of explorer with a ring signature using the previous screenshots Stealth Address. Link.

In this screenshot I marked it as the real output. Generally we could not tell if it was a real input or a decoy input. In this case, I believe it is the real spend, as I will explain soon, due to some telling ways the hackers spent it. However, in general this should illustrate how the Stealth Address appears in Ring Signatures as the real or decoy one. From the public data on the blockchain we cannot really tell which one it is.

Finally after all that lengthy explaining, lets look at the promised XHV hack, and how the Stealth Addresses and Ring Signatures play out in that.

Example by Looking at the XHV Hack

First, some brief background to understand the XHV exploit descriptions, and their relation to Stealth Addresses and Ring Signatures a bit better.

What is XHV

XHV, or Haven Protocol, is called an “algorithmic stablecoin”. The basic XHV token is, surprisingly, called XHV. It can be traded on exchanges, and sent between wallet, similar to XMR for Monero. To create the algorithmic stablecoin functionality, XHV implements also other token types on the blockchain, such as xUSD to track US dollar value, xBTC to track Bitcoin value, and xJPY to track the Japanese Yen value. Special transactions can be created on the XHV blockchain to change one of these token types to another, and these tokens can be sent between wallets just like the base XHV itself.

The tracked prices for USD, BTC, etc., are determined by Chainlink oracles, such as the one for XHV-USD. Without going into too much detail, these concepts are only relevant for this article at a higher level with the multiple asset types, as they come up discussing the following examples with the XHV exploits.

The Exploits

At the time of the example used here, there were multiple different exploits applied in the course of a few days on the XHV blockhain. I will use the first exploit on that list as an example. This exploit abused some missing checks on how the miner (coinbase) transaction is created. The output of the other exploits could be analyzed similarly if interested, as they are all listed on the XHV teams Medium post.

The first exploited miner transaction on that list is in the XHV block 882877. Specifically, the attackers used an exploit to take advantage of missing checks for validating mining rewards / fees in the miner reward (a.k.a. coinbase) transaction for the additional asset tokens. In the block 882877 mining transaction (also the screenshots above in theRing Signatures section), you can see 101k xUSD and 6.73 xBTC being created out of thin air. The miner transaction is exploited again in block 883040 for the same amounts of 6.73 xBTC and 101k xUSD.

So how does this relate to Stealth Addresses and Ring Signatures? After the XHV developers noticed / were notified of the abnormally large miner rewards, they attempted to stop the hackers from using those hacked 101k xUSD and 6.73 xBTC outputs. This is where the Stealth Addresses and Ring Signatures of those transaction outputs come to play.

Attempting to Block Spending of the Exploited Funds

As I described earlier, Monero does not include the actual receiver address on the blockchain. Instead, it creates the one-time Stealth Addresses for each transaction, based on the receivers cryptographic public keys encoded in their wallet address. And while you cannot map a single Stealth Address to any specific recipient/wallet, you can map it to Ring Signatures of specific transactions, where the output identified by the Stealth Address is possibly used as input / spent (or as a decoy). The screenshots earlier illustrated this.

In this case, the XHV developers would have taken the Stealth Addresses used as target addresses for payment of the exploited transactions, and scanned the blockchain to find any Ring Signatures using these Stealth Addresses as inputs, and thus any potential spends of those funds. With no matching Ring Signatures / transaction spends found, one could assume that the funds were not yet spent / moved from the initial target Stealth Address. Reading their report, this would have been the case they assumed.

To block the attacker from using their exploited funds, they provided the biggest XHV mining pools with a modified software that discarded any new transactions using those Stealth Addresses as part of their Ring Signatures. These biggest mining pools would give them control of well over 51% of the network hash power. This 51%+ hash power gives anyone power to discard any blocks mined by someone else, in this case those that would have contained those Stealth Addresses from the exploited outputs as inputs.

However, reading their report and the Medium post, the developers seem to have made some mistake in their scanning, and the idea that the funds were not spent was not the real case. We can verify this simply by using the Monero Daemon RPC API that is shared by the XHV Daemon. We can query a network node with this API for blocks and transactions, and look for any with a specific Stealth Address as an input in the Ring Signatures. Let’s see how it looks.

Mapping Stealth Addresses to Ring Signatures

To build this example, I queried the XHV network for transactions that have the Stealth Addresses of the exploited miner transactions in their Ring Signatures. Once I found any, I repeated this scan one more time, to find transactions using those potential spends as inputs in their ring signatures. The following figure shows the results of this process, and how the exploited miner transactions spread into the blockchain in the blocks coming after it:

Hacker TX fan-out into the blockchain and its ring signatures.

The above figure illustrates how the two exploited transaction outputs fan out from the original exploited miner transaction from block 882887. The two exploited miner transactions in the above are the ones on left side of the figure, labeled 882877 xUSD 100k and 882877 6.73 xBTC. If you look at the miner transaction on the block explorer, the xUSD transaction is paid to Stealth Address 3b8e80a279000d3d32826010b665e2c78aaf25d1744c49cac8a5da154d293875, and the xBTC to Stealth Address 7dec1f53dd30416458926bd35e9c1fff98d0ac86fc185a8fedfad546ff7d4546.

Scanning for these Stealth Addresses as part of a Ring Signature, the xUSD output is used as input in Ring Signatures of three transactions, in blocks 882939, 883064, 883410. The xBTC output is similarly used as input in two Ring Signatures, in blocks 882939, and 883041.

I highlighted 882939 in the above figure in green, since it seems quite clear to me that this is the actual transaction to spend the exploited funds from block 882877. I cannot prove it 100% because the Ring Signature obfuscates the sender in 10 other decoys for both the xUSD and xBTC transaction. However, this is a good illustration of where these privacy mechanisms don’t necessarily alone hide you, if your actions betray you through other heuristics.

I say this because block 882877 contains transactions using both the xUSD and xBTC exploited outputs as ring members. Both outputs also appear in any Ring Signature for the first time in this same block. With the way Monero chooses its decoys, having two transactions in the same block using decoys from the exact same previous transaction is extremely unlikely. Even more, Monero has an unlock time of 60 blocks for miner (coinbase) transactions such as the exploit in block 882877, and the difference between 882939 and 882877 is 62 blocks. So 882939 is one of the first blocks where this hacked output could ever be spent. What a coincidence to have all this happen together. This illustrates how the technology can work perfectly fine, but your actions can still betray you. Probably makes no difference to the hacker, but a good example.

Why Only 2–3 Rings Use the Exploited Outputs

The above figure shows how there are only 3 and 2 blocks where the xUSD and xBTC outputs appear as ring inputs but for the other transactions in the figure there are many more. This is the effect of the XHV developers efforts to stop their use, which was just a bit late as they already were used as real inputs/decoys in those 3 and 2 blocks. But if not, the stopping likely would have worked fine as the cutoff shows.

Fanning Out Into the Blockchain

In the figure above, I expanded the two transaction outputs from the xUSD payment in the block 882939 as examples of what a more realistic fan-out from an output would look like into multiple Ring Signatures in the following blocks. The first (marked output1 in the figure) is paid to stealth address 71d224f0043fdf8c5b6e8bc292f1c1e07bf820d707c2d9b04b6335d49bf37e4b. The second fanned-out output (output2) is paid to stealth address afa169a74b1581cafedf215219ca7b7708802ec13945540d3fb9ba30e188d842.

As the figure shows, the output 1 of block 882939 can be found as (input) member of Ring Signatures in transactions in blocks 883000, 883105, 883155, 883247, 883302, 883987, 883993, 884002, and 884003. Similarly, output 2 can be found in 882970, 883903, 883925, 883986, 883991, 883996, 884440 and 885705. If you want to check for yourself, just open these links and search for the stealth address I copy-pasted above.

Relevance to User Privacy

Beyond all this technological aspect, reading about hacks and all can be interesting. Or maybe everyone already fell asleep. But is any of this relevant to a normal user?

If you only care about having some basic privacy, or if you don’t care about privacy and anonymity at all, you are likely fine just using the Monero based protocols as is. If you do care more deeply about it, there are a few points we can gather from this that are good to keep in mind:

  • When you receive any transaction, consider re-sending it a short time after to yourself, or in general churning it a few times. This will obfuscate what stealth address the funds are in, beyond just inclusion in other Ring Signatures. But beware of obvious patterns such as the one above for the miner exploit.
  • Consider other metadata that could be used to identify and link your transaction. In the above XHV hack example, the metadata was the use of multiple outputs from the same miner transaction at the same time, right after the original transaction unlocked.

However, to make this more complicated, churning and other techniques are not so simple to do perfectly either. Some related discussion in this Stack Exchange post. To make it perfect, your churning should look like real decoy patterns look. But it can get a little complicated to do such perfect optimizations, so mostly some basic consideration for above points is likely good enough. It is especially tricky as I am now aware of any specific support for having granular control over which transaction outputs are spent, or even visibility to the specific inputs and outputs in a Monero wallet.

In general, timing related analysis seems to have been one of the most common ways to try and analyze Monero transactions. To look more deeply into the decoy selection algorithm, I wrote a small study on that here but it got a bit lenghty. It seems to happen to me a lot. So to avoid even more overly long writing, and too much digression, I will save my details on decoy selection and timing analysis for another day.

Other Metadata

Besides time-based analysis, various other issues related to transaction analysis, Ring Signatures, decoys, and related topics have been identified and addressed over Monero lifetime. A very nice and extensive discussion on this topic is available in the Breaking Monero YouTube series by the Monero team. I won’t go into any of those details here, but if interested in the topic, it is definitely a great series to watch.

Future Views on Ring Signatures

While the current Monero ring size is 11, recent Monero Labs Research topics include Triptych and related ideas that aim to enable much larger ring sizes in practice. This should make any analysis of the transaction sender, and the relations between them even more difficult. It should also provide broader decoy patterns, making it harder to fail to match them for your own transactions.

Obligatory Promotion of Software Testing

Having worked over many years in software testing (mainly the engineering part of it), I will take the chance for a few words about these cryptocurrency hacks and what I think about the topic, even if it is not really about Ring Signatures and Stealth Addresses. Sorry about that.

Regarding the XHV hack, the reports they released seem to point to quite lacking software development practices (search for Lessons Learned). There appears to have been little to no tests, lack of code reviews and audits, and getting any (helpful) community involvement in development seems to have had little to no support. Pretty dire reading for an open-source financial project running openly decentralized over the internet, and at times valued in hundreds of millions of dollars or more.

Reading those lessons learned, at least the XHV team seem to recognize this now and work to improve. I guess it remains to be seen how well one can change fundamental processes and peoples working practices in one go.

Of course, the XHV team are also not alone in this as, for example, about one month later (July 2021), another cryptocurrency project called Thorchain had similarly multiple hacks amounting to millions of dollars in damages. While not as bad, some of the reports I read pointed at similar limits in development processes, testing, etc. In general such hacks seem to occur almost monthly in cryptocurrency projects, especially for the newer projects with a larger new codebase (and thus untested attack surface). Maybe it goes with the territory, but maybe it wouldn’t hurt to put some thought into testing and security.

Of course, everyone makes mistakes, and I guess it is most important to learn from those mistakes. But that should not excuse ignoring even basic levels of quality assurance.

Conclusions

I hope this article provides some added understanding on what are Ring Signatures and Stealth Addresses, and how they work. I find it quite impressive how Monero applies much of the latest cryptographic research into practice, combines different cryptographic techniques to create a system of private and decentralized transactions, and has not had any big hacks like the one I partially described here.

The Monero technology can be quite complex, but in the end I find a good explanation helps make even complex topics understandable. Much like Bitcoin is similarly clever, but not too hard to understand once you find the right resources to explain it. Luigi1111’s Stealth Address article is great, too bad he never seems to have gotten around to his Ring Signatures article hinted there.

For anyone interested on how using the Monero API to analyze the blockchain might work, at the time I wrote my earlier article on Merkle Trees, I built a small tool to crawl the Monero blockchain using the Monero Daemon / node API. This let me locally analyze the data, which I also applied for this article. Maybe one of these days I will also finish the additions I made for this article and update the Github, even though it should already work as an example of the general process.

Personally, I feel like I got maybe halfway there in trying to get a good understanding of how to implement the Stealth Addresses and Ring Signatures in practice. Maybe for understanding their relations on the blockchain and tobasic Monero tracing, that could be enough already.

That’s all for today. Cheers.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s