DeSo / Bitclout Security Vulnerability

This post has also been published in ZenGo’s blog.

Introduction

In this post, I will describe a vulnerability and its exploitation in the Bitcoin to DeSo bridge within the Bitclout backend service that I’ve found. If you don’t know what Bitclout is, we will get there shortly.

The vulnerability itself is based on a double-spending attack in the Bitcoin network by having some miners holding one set of transactions in their mempool while others holding another set of transactions such that both sets are contradictory.

If you find interest in the internals of Bitcoin, this article reaches great depths of how Bitcoin works and what makes it secure and gives a glimpse on what makes the solving of double-spending in Bitcoin so important. I will be assuming some familiarity with Bitcoin and how it works along the article.

I named this vulnerability “Griphook”, the character from the Harry Potter world who helped Harry, Ron and Hermoine to break into Gringotts Bank. If you want to know the connection, continue reading :) !

The article is structured as follows:

First I’ll give some background information about Bitclout and the process of buying Bitclout coins from Bitcoin using Bitclout’s backend’s exchange service.

Next I’ll explain the key issues with the existing mechanism, followed by a pseudo-code styled exploitation outline.

To conclude, I’ll try to give a general sense of what can be done to resolve similar issues in the future and what was done concretely in the case of Bitclout’s service.

Q: I’m a Bitclout user, are / were my coins at risk? Should I sell my coins? Is Bitclout insecure? Is DeSo insecure?
A: The bug only affects Bitclout’s vault and none of the coins / wallets of any user were at risk at any point in time. The security and robustness of the DeSo blockchain was neither at risk.

Background

DeSo (abbreviation of Decentralized Social) is a decentralized blockchain-based social network giving the users a whole new ecosystem by introducing sophisticated usage of creator coins.

The native DeSo coin, denoted as $DeSo, is used to purchase such creator coins. We will get rid of the ‘$’ sign and simply use DeSo to denote both the blockchain and the coin itself where the meaning should be implied from the context.

The original and the most popular gateway into the realms of DeSo is known as Bitclout, and it is a website through which users can use the decentralized social network of DeSo.

The DeSo coin itself can be traded on various crypto exchanges and can be natively exchanged within the Bitclout website from Bitcoin.

To get a better sense of what Bitclout is, the options it gives its users and the philosophy at the basis of its design follow the Intro to Bitclout Page.

Notice that distinguishing between Bitclout and DeSo is a relatively new concept so some of the documents may still be referring to Bitclout while the correct term should be DeSo. This research was conducted before the introduction of DeSo, but this doesn’t affect the final results of the research.

In the rest of this section we will focus on the proceedings involved in buying DeSo using the BTC-DeSo exchange within the Bitclout website.

Buying DeSo Coins

Much like various Bitcoin wallets, every user signing up to Bitclout gets a seed of 12 words from which it can derive various keys used to sign transactions in Bitclout.

After signing up, buying DeSo using BTC can be done from within the Bitclout website using this page looking something like this:

Figure 1: Bitclout Despoit Page

In particular, this can be done with the following steps:

  1. Deposit some BTC into a predetermined address, surrounded in an orange rectangle in Figure 1. This address is unique per user, and the user can derive the private key associated with this address from it. The derivation is based on HD-wallet mechanism (see my post about it). Thus, from a technical point of view, the user, sending some BTC to this address, doesn’t yet lose control over the sent BTCs.
  2. Determine how much Bitcoin are you willing to swap or how much DeSo are you willing to buy.
  3. Hit the buy $DeSo button and confirm the swap.

After waiting for a few seconds, the swap is confirmed and your Bitclout address will be rewarded with the appropriate amount of DeSo.

This was the moment when I was alarmed and started wondering, “how come my Bitclout account is immediately credited with CLT while the Bitcoin transaction hasn’t been confirmed yet?”.

Technical Details

Bitclout’s backend Github repo is a good source to get a better technical sense on what is happening under the hood when buying DeSo with BTC.

The function handling the exchange of Bitcoin to Bitclout can be found here.

The function (as its name suggests) is stateless, in a sense that it doesn’t hold any state information between consecutive calls. In each call it receives from the client all the necessary pieces of information to generate a Bitcoin transaction from the deposit address, controlled by the client, to Bitclout’s Bitcoin deposit address.

One of the parameters, named $\mathtt{broadcast}$, can be used to determine whether to broadcast the generated transaction to the Bitcoin network or not.

This parameter is necessary because in order to make the exchange, the client will make two calls to the exchange API.

The first will not be broadcast to the network and will only be used to generate a TX which will be sent back to the client and signed by him.

The second call will contain the signature generated by the client for the TX. Using this signature the Bitclout backend is able to broadcast the transaction to the Bitcoin network.

In summary, the communication pattern between Bitclout and the client, in the process of exchanging Bitcoin to DeSo constitutes the following messages:

  1. The client sends all the required information, such as Bitcoin amount to exchange, fees to be paid, a list of UTXOs to spend, and DeSo address to the Bitclout backend. With the $\mathtt{broadcast}i$ parameter set to $\mathtt{0}$, indicating that the backend should not broadcast the resulting transaction. Important Note: The server 100% trusts the information provided by the client at this point, so if the client reports some UTXOs that don’t really exist, the server doesn’t verify it at this step.
  2. The backend sends the resulting transaction’s hash back to the client, requesting this hash to be signed using the client’s private key.
  3. The client signs the hash and sends back to the server the resulting signature with all the information that was sent in the first message and the $\mathtt{broadcast}$ parameter is set to $\mathtt{1}$.
  4. The backend is performing some additional checks on the resulting transaction and broadcasts it to the Bitcoin network.

In step 4, as mentioned, the backend is making some verifications regarding the resulting transaction such as:

  1. Some offline checks: Validating the signature, that the address has sufficient funds etc.
  2. That any of the inputs to the transaction isn’t marked with RBF, either explicitly by setting the RBF bit, or implicitly by relying transitively on RBF-marked inputs of ancestor-transactions that are not confirmed yet. This check is done against an API served by Blockonomics. Upon failure the transaction is dismissed and the procedure is aborted.
  3. If the transaction verification passes, the backend will broadcast it to the Bitcoin network using the BlockCypher push-tx (transaction-pushing) service.

After doing so it waits for five seconds and then queries the BlockCypher TX-API whether the transaction is a double spend or not.

If this isn’t a double spend transaction the Bitclout address is credited with the appropriate amount of DeSo coins by transferring the coins from Gringotts account using a standard transaction over DeSo network.

The Vulnerability

Race Condition Issue

In this section I’ll try to describe a simplified version of the attack. This version doesn’t work and never worked but it is important to understand it before diving into the attack that did work eventually.

So, the first and most basic attack one could come up with, according to the aforementioned procedure, is to create a double spending attack as we describe in this subsection.

We denote by $\mathtt{A}$ a UTXO encumbered to some address $\mathtt{Addr}_{\mathtt{A}}$ owned by the attacker, which creates the following two TXs:

  1. The attacker, in a well-timed manner, will transmit a $\mathtt{B}$ transaction to the Bitcoin network spending $\mathtt{A}$ and creating a UTXO $\mathtt{B}$. This transaction will have a very high fee to incentivize the network to confirm it. The receiver of output of the transaction is the attacker itself. We call this TX the self-TX.
  2. The attacker will initiate a BTC-DeSo exchange which spends UTXO $\mathtt{A}$. This is double spending, since we’ve already broadcast a transaction spending UTXO $\mathtt{A}$ by sending it from the attacker to itself in the self-TX. We call the TX created as a result of the exchange in this step the exchange-TX.

Notice that since exchange-TX and self-TX are contradictory in the sense that they both spend UTXO $\mathtt{A}$,only one of them will eventually be confirmed. The idea is that if the DeSo purchasing, done with exchange-TX is successful but eventually the self-TX gets confirmed on Bitcoin, then we managed to buy DeSo without paying the BTC for it, thereby successfully attacking Bitclout’s service.

The self-TX and exchange-TX transactions should be transmitted to the network such that the following assertions hold:

  1. exchange-TX reaches Blockonomics’ node before self-TX, so only exchange-TX will get into Blockonomics’ mempool and the RBF check will pass. Notice that either exchange-TX or self-TX will get into Blockonomics’ mempool, because these transactions are contradictory (both spend the same UTXO $\mathtt{A}$) and Bitcoin nodes don’t let contradictory transactions into their mempool to prevent DoS (denial of service) of nodes. If exchange-TX doesn’t reach Blockonomics’ node first then it will never get into the Blockonomics’ node mempool. Then, when we try to make the exchange against the DeSo-BTC bridge, it will check whether the exchange-TX has RBF checked and will fail to do so since Blockonomics doesn’t know the exchange-TX.
  2. self-TX reaches BlockCypher’s mempool after BitClout’s backend checks that exchange-TX isn’t a double-spend.
  3. self-TX reaches substantially more nodes on the Bitcoin Network than exchange-TX so that it will be confirmed with higher probability so the attack will succeed.

What we try to achieve here is that while Bitclout’s backend will credit the attacker’s account with DeSo coins, the Bitcoin-TX from the attacker to BitClout’s account will not be confirmed using double spending.

However, the three restrictions make it difficult to exploit because in order to satisfy the first two assertions we want to send self-TX much later than exchange-TX, but in order to satisfy the third assertion we will be interested in sending self-TX earlier than exchange-TX making the possibility of successfully timing the attack questionable. Thus, this variant of the exploitation, while seems simple, may require some collusion from the miners to mine, and accept into the mempool, the self-TX despite it reaching them after the exchange-TX.

BlockCypher’s API

Bitclout’s backend uses BlockCypher’s API to check whether a transaction is a double spending. The API is used by sending an HTTP GET request to https://api.blockcypher.com/v1/btc/main/txs/.

For example, by initiating a GET to:

https://api.blockcypher.com/v1/btc/main/txs/38c404ebeb86b72a616636cc38e579ad6478ddbca4fe63c83004cb851a2a391e

We get the following response with the double_spend field in bold:

{
  "block_height": -1,
  "block_index": -1,
  "hash": "38c404ebeb86b72a616636cc38e579ad6478ddbca4fe63c83004cb851a2a391e",
  "addresses": [
"1GtZ85mQ36ZbXEPUvS8Nx9Y3HekWW3dZMi"
  ],
  "total": 200661,
  "fees": 200,
  "size": 191,
  "vsize": 191,
  "preference": "low",
  "relayed_by": "3.89.107.32",
  "received": "2021-08-25T12:11:55.248Z",
  "ver": 2,
  "double_spend": false,
  "vin_sz": 1,
  "vout_sz": 1,
  "confirmations": 0,
  "inputs": [
{
   "prev_hash": "cc22f4f0824ba1e70d6f95e17e6184dab149796c6eaa6e7c332619f8fc99bc3d",
   "output_index": 0,
   "script": "473044022078a8a38f4b307a49892d5f35d86bda65063b6807dd7f8491c28070d50f1ea13a02203f7a74e3001fad59204a620dabe772ea1636465222fd44f8a66d21ed71515759012102f86e9dd205e0e47b8268df43c0084cd7621b4abe5817d26e97d1d4027b002959",
   "output_value": 200861,
   "sequence": 4294967295,
   "addresses": [
     "1GtZ85mQ36ZbXEPUvS8Nx9Y3HekWW3dZMi"
   ],
   "script_type": "pay-to-pubkey-hash",
   "age": 0
}
  ],
  "outputs": [
{
   "value": 200661,
   "script": "76a914ae49ea3ce84872d517ef958a7c4b225f4904020788ac",
   "addresses": [
     "1GtZ85mQ36ZbXEPUvS8Nx9Y3HekWW3dZMi"
   ],
   "script_type": "pay-to-pubkey-hash"
}
  ]
}

Given the output of this format, Bitclout takes the double_spend key and checks whether it is true or false.

The Bug

To make the exploitation of BTC-DeSo exchange much simpler we introduce a bug in the way Bitclout makes use of BlockCypher’s API which occurs in a uniquely and specially crafted generated situation.

The issue stems from Bitclout misinterpretation of how BlockCypher determines whether a transaction is a double spend, and more precisely, whether the property of being a double-spend transaction is transitive or not. Let’s look at an example.

Assume the following tree of UTXOs/transaction:

Figure 2. A small set of transactions causing the bug

We begin with UTXO A and double spend it to create two UTXOs denoted by B1 and B2.

To make things clear when we say double spend it means that in the network of Bitcoin there exists different nodes that hold either B1 or B2 in their mempool, as a side note we mention again that in bitcoin-core by default a node will reject double spending so typically either B1 or B2 will reside in a node’s mempool, but theoretically a custom node could hold them both.

At this point if we query BlockCypher’s API regarding B1 and B2 it will report both transactions as a double spend, because both of them are spending UTXO A.

However, and here is the tricky part, if we spend UTXO B1 to create a new UTXO C, then querying BlockCypher will report C as a non-double-spend transaction.

To make things clear, the implied definition of BlockCypher to a double-spend transaction from the responses of their API is:

Double spend: A transaction will be considered as a double-spend if at least one of its inputs is an input of another transaction that has been in the mempool.

However, the implied definition Bitclout assumes for double spending is:

Double spend: A transaction will be considered as a double-spend if at least one of its inputs is either an output of a double-spend transaction or an input of another transaction that has been in the mempool.

In other words, Bitclout implicitly assumes that the definition of double-spend is transitive, while on BlockCypher this isn’t the case.

The Exploit

Initial, Simplistic Approach

In this section we’ll give an exploit to the bug from the previous section. This exploit isn’t optimal and doesn’t really work. It is important to understand it in order to understand the fully optimized exploit that follows it. Consider the following diagram from the previous subsection illustrating a tree of UTXOs:

Figure 3. A small set of transactions causing the bug

Note: For simplicity, we will refer to $\mathtt{A}$, $\mathtt{B_1}$​, $\mathtt{B_2}$​ and $\mathtt{C}$ sometimes as UTXOs and sometimes as the transactions whose output is the corresponding UTXO.

In our exploitation we begin with a UTXO $\mathtt{A}$ owned by the attacker.

The attacker will send two transactions creating two UTXOs, both spending UTXO $\mathtt{A}$.

  • $\mathtt{B_1}$​ will be sent from BlockCypher’s push-tx web API which is also used by Bitclout’s backend to push their transaction to BlockCypher (browser-friendly version available here). This transaction will be sent from the attacker to itself as well and will be accompanied with very low fees.
  • $\mathtt{B_2}$​ will be sent from a local bitcoin node using the bitcoin-cli sendrawtransaction command, from the attacker to itself with high fees, incentivizing the network to confirm it.

Now the attacker will initiate a BTC-DeSo exchange against Bitclout. As we mentioned earlier, when initiating an exchange in the BTC-DeSo bridge, the client reports which UTXOs it wishes to spend. Thus, the attacker will be reporting only UTXO $\mathtt{B_1}$​ as available, so the Bitclout backend will try to spend UTXO $\mathtt{B_1}$​ by creating a new transaction $\mathtt{C}$ with minimal fees (as fees are controlled by the attacker) to the address of Bitclout’s Bitcoin address.

Upon making the appropriate verifications, the transaction will obviously not be considered an RBF, passing Blockonomics’ verification.

When Bitclout’s backend will be sending the created UTXO $\mathtt{C}$ to BlockCypher this transaction will obviously not be considered a double spend since this is the only transaction spending UTXO $\mathtt{B_1}$​.

At this point the attacker’s Bitclout address will be credited with an appropriate amount of DeSo.

However, since UTXO $\mathtt{B_2}$​ has much more fees attached, a miner will much more likely prefer it over UTXO $\mathtt{B_1}$​ and $\mathtt{C}$ thus cancelling the payment to Bitclout’s address, completing the attack successfully.

Now this attack sounds quite simple, and it is, this is why it doesn’t really work in practice.

At this point I have had come up with multiple hypotheses which all stem from the following basic rule:

Not All Bitcoin Nodes Are Born Equal!

You see, the Bitcoin network is composed of nodes, interconnected in mysterious and unknown ways to each other. In our attack we have created two UTXOs:

  1. $\mathtt{B_1}$​ – which we don’t want to be confirmed.
  2. $\mathtt{B_2}$​ – which we want to be confirmed.

We have sent $\mathtt{B_1}$​ via a node owned by BlockCypher, thus we can assume this node is connected to multiple other large nodes and big-shots in the crypto industry. Therefore, the message sent from BlockCypher’s node will probably quickly propagate to Blockonomics’ node, which is good, because we need Blockonomics’ node to know this TX to pass the RBF test, but it will also quickly propagate to other nodes, some owned by the great mining pools for example.

On the contrary, we have sent $\mathtt{B_2}$​ via our local Bitcoin node, connected to a small set of random nodes on the Bitcoin network and thus may endure longer propagation delays to reach some nodes such as Blockonomics’ node and miners’ nodes.

In the following section we’ll get a better sense of what propagation delays are and how to use them as part of the exploit.

Propagation Delays in Bitcoin

Consider the following figure:

Figure 4. A set of nodes and their messages’ propagation delays

This figure gives a general illustration of the Bitcoin network, with several nodes in it.

The large circle resembles the Bitcoin network. Inside, we have two main “nodes”, denoted with pink rectangles.

  1. Our Bitcoin node on the left.
  2. BlockCypher’s Bitcoin node in the center.

Surrounding each of these nodes is a circle, delineating the portion of the network reachable from each node within a 2 milliseconds delay. In other words, each circle marks the portion of the network that will receive a Bitcoin message sent from each node with at most 2 milliseconds delay. Since each node is connected to a different set of nodes, the circles cover different parts of the network, both in placement and in size.

Therefore, consider our original scenario where we send two different transactions, both spending the same UTXO, one is sent from our local Bitcoin node and the other is sent from BlockCypher’s Bitcoin node. We would like to know for four different nodes in the network, positioned in points labelled A, B, C and D, which Bitcoin transaction did they accept into their mempool after 2 milliseconds from the moment these two transactions were broadcast into the network.

  • Node A will have BlockCypher’s TX in its mempool, since the message from our node still hasn’t arrived at that node yet.
  • Node B will have the TX from our node in its mempool, since the message from BlockCypher’s node hasn’t arrived at that node yet.
  • Node C may have either our TX or BlockCypher’s TX and we can’t tell from the diagram which message arrived first at its mempool.
  • Node D will not have any of these transactions since both transactions still didn’t arrive at this node yet.

It is important to mention that node C will accept only one of the transactions into its mempool to prevent DoS attacks on Bitcoin nodes. This is the default behavior in the Bitcoin-core project, and some nodes may behave differently. Due to this fact, we want to transmit the two transactions to the network in a way that will promise the following three properties:

  • We need Blockonomics’ node to receive the transaction creating UTXO $\mathtt{B_1}$​ (the UTXO we don’t want to be confirmed). This is because Bitclout checks for RBF in UTXOs before exchanging Bitcoin via Blockonomics’ API, so we must ensure Blockonomics knows of UTXO $\mathtt{B_1}$​.
  • BlockCypher should know of UTXO $\mathtt{B_1}$​, this is because the transaction from the attacker’s wallet to BitClout’s Bitcoin address will use UTXO $\mathtt{B_1}$​ as input. This TX will be pushed to BlockCypher and thus UTXO $\mathtt{B_1}$​ should be known to BlockCypher. The upside of this is that BlockCypher doesn’t conform with Bitcoin-core’s default behavior and may accept into the mempool various contradicting transactions.
  • As many nodes as possible will receive the transaction from our node (creating UTXO $\mathtt{B_2}$​) before receiving the transaction from BlockCypher. This is to ensure that UTXO $\mathtt{B_2}$​ will be confirmed on the network with very high probability. In particular we want mining pools to receive this TX.

Ideally, we would prefer sending TX $\mathtt{B_1}$​ directly from Blockonomics’ node or connect directly to their node so this TX will reach Blockonomics’ node WHP (with high probability) before TX $\mathtt{B_2}$​ while reaching as few other nodes on the Bitcoin network along the way, this way TX $\mathtt{B_2}$ will reach more nodes and will be confirmed WHP.

In other words, we want to create a setting in the mempools of the nodes in the Bitcoin network that a large portion of the nodes disagree with Blockonomics’ node. To be precise a node disagrees with another node if each has a different TX spending the same UTXO. For example, in the previous case where we have concurrently sent TXs $\mathtt{B_1}$ and $\mathtt{B_2}$, all nodes who have accepted $\mathtt{B_1}$ to their mempool disagree with all nodes who have accepted $\mathtt{B2}$ to their mempool.

The problem is that we don’t know the structure of the network and we don’t even know which node is Blockonomics’ node. If we did know, we could have simply sent Blockonomics’ node TX $\mathtt{B_1}$ and relentlessly broadcast to any other node on the network TX $\mathtt{B_2}$ so that TX $\mathtt{B_1}$ would reach only a small number of nodes.

To overcome this issue we can use a different approach. Instead of bisecting the set of nodes in the network into two sets who disagree with each other in one shot, we will iteratively get more and more nodes to disagree with Blockonomics. This will be done without knowing which node is owned by Blockonomics. We will be assuming:

  • We are able to query Blockonomics’ node for the existence of a specific txid (transaction ID) in its mempool. In the case of Blockonomics’ API this is possible by setting an HTTP GET to https://www.blockonomics.co/api/tx_detail?txid=.
  • We are able to obtain a relatively large set of nodes from the Bitcoin network (say 1000). This can be done using Bitnodes API.
  • We are able to directly connect to each node and transmit a TX to it. This can be done using submittx program and in general it is allowed by Bitcoin’s protocol.

Consider a set of nodes $\mathcal{N}$, for simplicity we assume $\left|\mathcal{N}\right| = 2^k$. We can split $\mathcal{N}$ into two sets $\mathcal{H_1}$ and $\mathcal{H_2}$, each of size $2^{k-1}$.

Assume we have a UTXO $\mathtt{A}$. We want to create two transactions $\mathtt{B_1}$ and $\mathtt{B_2}$ such that $\mathtt{B_1}$ will enter the mempool of all nodes in $\mathcal{H_1}$ and $\mathtt{B_2}$ to enter the mempool of all nodes in $\mathcal{H_2}$. We can do this by broadcasting $\mathtt{B_1}$ to all nodes in $\mathcal{H_1}$ and $\mathtt{B_2}$ to all nodes in $\mathcal{H_2}$.

To estimate the effectiveness of this process we make a major assumption on the structure of the Bitcoin network and the sampled set of nodes. We call it “the structural assumption”:

We assume that by sending two conflicting TXs ($\mathtt{B_1}$ and $\mathtt{B_2}$) to two set of equally sized nodes on the Bitcoin network ($\mathcal{H_1}$ and $\mathcal{H_2}$) who were randomly sampled using Bitnodes API, approximately $50\%$ of all nodes will eventually hold $\mathtt{B_1}$ and $50\%$ will hold $\mathtt{B_2}$ in their mempool.

After broadcasting $\mathtt{B_1}$ to the nodes in $\mathcal{H_1}$ and $\mathtt{B_2}$ to the nodes in $\mathcal{H_2}$ we certainly know that one of them got into Blockonomics and one didn’t. Therefore, we can query Blockonomics’ API about whether it holds $\mathtt{B_1}$ or $\mathtt{B_2}$ in its mempool.

Let’s assume WLOG (without loss of generality) that $\mathtt{B_1}$ was accepted into Blockonomics’ node’s mempool. Therefore, all nodes in $\mathcal{H_2}$ disagree with Blockonomics and by our “structual assumption” we know that roughly $50\%$ of the network disagree with Blockonomics.

The first thing we will do at this point is to incentivize all nodes that accepted $\mathtt{B_2}$ into their mempool to mine $\mathtt{B_2}$. This can be done by sending a new TX $\mathtt{B_3}$ with very high fees that spend the output of $\mathtt{B_2}$. Since the miners want the fees from TX $\mathtt{B_3}$ they will also have to mine $\mathtt{B_2}$ on which $\mathtt{B_3}$ relies.

After doing this we are situated at a familiar state and we would like to apply this algorithm recursively, let’s see how this can be done. We have a TX that we want to double spend (originally: $\mathtt{A}$, now: $\mathtt{B_1}$) and a set of nodes who hold this TX in their mempool (originally: $\mathcal{N}$, now: $\mathcal{H_1}$). Now we can run the algorithm by splitting $\mathcal{H_1}$ into two, equally-sized, sets of nodes and sending to each half set a different TX (either $\mathtt{C_1}$ or $\mathtt{C_2}$) spending the output of $\mathtt{B_1}$ getting a TX tree like this:

Figure 5. First recursive amplification step

Now we check whether $\mathtt{C_1}$ or $\mathtt{C_2}$ is accepted into Blocknomics. Let’s assume WLOG it is $\mathtt{C_1}$. So we create a TX $\mathtt{C_3}$ with very high fees to incentivize the network to prefer mining $\mathtt{C_2}$ rather than $\mathtt{C_1}$, getting a tree like this:

Figure 6. Second recursive amplification step

Now to make sure you’ve been following the recursion. Try drawing the TX-tree after the next recursion step yourself, after trying to scroll further to make sure you’ve got it right.

The tree would look like:

Figure 7. Third recursive amplification step

Notice that after each recursive step the number of nodes in the Bitcoin network who agree with Blockonomics is cut by half. Since we started with $|\mathcal{N}| = 2^k$ nodes, after $k$ recursive steps only a single node in our set will agree with Blockonomics’ mempool on average.

For example, in the last diagram, for the attack to fail wee need that $1/8$ of the nodes who still agree with Blockonomics will mine $\mathtt{D_1}$ (for minimal fees) before $7/8$ who disagree with Blockonomics will mine either $\mathtt{D_3},\mathtt{C_3}$ or $\mathtt{B_3}$ (for very high fees). We can tell from the greedy nature of the miners that this scenario is unlikely to succeed after going all the way down the recursion, thus giving our attack a very high probability to succeed.

Using this algorithm I have managed to successfully attack and steal (with permission from DeSo’s team, of course) a small amount of coins from Gringotts Bank!

Mitigation

The solution suggested to DeSo team is to verify on Bitclout’s backend, that when making a purchase using Bitcoin, that all inputs of the purchase are either confirmed or not double a spending outputs. This will be done using BlockCypher’s API. For those inputs who aren’t confirmed or confirmed with less than 6 confirmations, check their inputs recursively for the same properties, until all paths from all inputs end in confirmed TXs with sufficient number of confirmations.

For example, consider the following graph of TXs:

Figure 8. A set of transactions to be verified. Green transactions are non-double-spent with 6+ confirmations

Each node in the graph is a TX and an arrow from TX $\mathtt{X}$ to TX $\mathtt{Y}$ means that one of the inputs of TX $\mathtt{Y}$ is an output from TX $\mathtt{X}$.

Green nodes are confirmed TXs with 6+ confirmations.

Notice that a TX may have many outputs and that the graph isn’t necessarily a tree. For example, TXs $\mathtt{D2}$ and $\mathtt{D1}$ have multiple outputs that were used as inputs in TXs $\mathtt{C1}$ and $\mathtt{C2}$.

Now, let’s assume that a user holding the outputs of TX $\mathtt{A}$ is trying to make a purchase using the TXs output. The Bitclout’s backend shall take $\mathtt{A}$ and check whether it is confirmed with at least 6 confirmations. If so, then the verification ends successfully. Otherwise, the backend shall, recursively, take $\mathtt{A}$‘s inputs, namely $\mathtt{B1}$ and $\mathtt{B2}$ and check whether those are confirmed or not.

Since $\mathtt{B1}$ is confirmed with 6+ confirmations, we shall not continue checking its inputs.

However, this isn’t the case for $\mathtt{B2}$. So we first check that it isn’t a double spending and then take its inputs $\mathtt{C1}, \mathtt{C2}$ and check whether they are confirmed with 6+ confirmations. Since they aren’t either, we check they aren’t double spent and if they aren’t we move to their inputs, $\mathtt{D1}, \mathtt{D2}$ and check whether those aren’t a double spending transactions.

Reminder: We say that a transaction is a double spend if one of its inputs was used as an input to another transaction in some other nodes’ mempools.

This suggestion was implemented (with some other edge cases) in a recently pushed commit into Bitclout’s core library.

Summary

By finding a minor vulnerability in Bitclout’s backend an attacker could steal very large amounts of money from the DeSo vaults using the BTC-DeSo bridge, with Bitclout coin price reaching a price 150$ as of 1st, Oct. 2021. DeSo’s BTC wallet address (3MxwZUJGpLYRhtMKXgCUi3x68uosEGhyGw) has received hundreds of Bitcoins only in the past three months. Their previous address which was active until July (1PuXkbwqqwzEYo9SPGyAihAge3e9Lc71b) and received thousands of Bitcoins. Thus, the potential financial damage from such an attack could have had devastating implications on the future of the project of Bitclout.

I want to thank DeSo’s team for making the reporting and the bounty award process smooth and simple and for taking the time and effort to deeply understand my commentary and suggestions.