<p>Nodes maintain multiple databases, they do not just store the blockchain and scan it every time it wants to do something. These databases include a block index (so that it knows where to find a block) and the UTXO set. The database containing the UTXO set is what matters here. That database contains the identifiers for every single UTXO and the UTXO itself. A UTXO consists of a spending condition (known as the scriptPubKey) and an amount.</p>

<p>A node will begin building its UTXO database when it starts syncing the blockchain. As it validates blocks, it goes through every transaction in that block and adds to its UTXO database the outputs that every transaction creates. It also removes every UTXO that is spent by a transaction. So once a node is fully synced, the UTXO database contains every Unspent Transaction Output in a way that is easy to lookup.</p>

<p>So when validating a transaction, to determine whether the inputs have not yet been spent, the node will try to find the UTXO using the txid and output index (a UTXO's unique identifiers) in its UTXO database. If it is successful and gets exactly one result, then it knows that the UTXO has not been spent. If it gets no results, the UTXO has already been spent and thus the transaction can be marked invalid.</p>

<p>Once the node has the UTXO for an input, it can proceed to verify that the input satisfies the spending conditions. The spending conditions are contained within the UTXO in a field known as the scriptPubKey. The scriptPubKey is a script written in Bitcoin's transaction scripting language. It is half of a program. When combined with the scriptSig that is provided in the transaction input, the program should be complete and executable.</p>

<p>So the node will (essentially) take the scriptSig, append the scriptPubKey to the end of it, and execute the resulting program. If that program completes execution and returns true, then the script is valid and the spending conditions have been met. Thus that input is valid. If all inputs are valid, and the rest of the transaction checks pass (locktime checks, outputs have valid amounts, etc.) then the entire transaction is accepted as valid.</p>

<hr>

<p>If you noticed, I mentioned that UTXOs have spending constraints, not owners. This is because UTXOs don't have owners. Some can be spent by anybody because the spending constraint says that anyone can spend the output. All that a node cares about is that the spending constraints are met.</p>

<p>But we as humans care about owners, so there are a subset of spending constraints that are commonly used to indicate that someone is an "owner" of a UTXO and is the only person allowed to spend it. These spending constraints basically say the following:</p>

<p>"in order to spend this output, the spender must provide both a public key which matches this particular hash  and a signature over the spending transaction produced with the private key of the public key with the aforementioned hash"</p>

<p>This spending condition can be abstracted into human terms as saying "the person with the private key that corresponds to the public key whose hash is in the script owns that output".</p>

CC BY-SA 4.0
2019-03-27T12:34:28.270Z
Thanks @Andrew Chow. "The database containing the UTXO set is what matters here." So is each node is maintaining a massive in-memory hashtable indexed by UXTO of size O(n) where n is # of UXTOs in the system? That sounds infeasible to me. The bitcoin chain as of now has about 600k blocks in it. Each block containing about 3000 transactions. In worst case this gives n = 600k * 3k = 1.8G. ouch!
morpheus
CC BY-SA 4.0
2019-03-27T12:46:48.277Z
Is bitcoin open source? Could I get a pointer to the relevant code which answers the 2 questions in OP?
morpheus
CC BY-SA 4.0
2019-03-27T14:29:59.487Z
The most common node software used in Bitcoin is open source (as is basically everything else used in Bitcoin). Code that does the UTXO lookup can be found here: https://github.com/bitcoin/bitcoin/blob/master/src/validation.cpp#L663. Script execution happens here: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1472
Ava Chow
CC BY-SA 4.0
2019-03-27T16:17:45.077Z
thanks. Could you answer my other question in comment as well? As you say "the node will try to find the UTXO using the txid and output index (a UTXO's unique identifiers) in its UTXO database" This does not sound scalable to me at all. as I argued earlier, the bitcoin ecosystem would be having approx 1 billion UTXOs and this number will only increase in future. Do you think this is scalable? Could we move the discussion to chat? I don't see any option to do that.
morpheus
CC BY-SA 4.0
2019-03-27T16:34:38.130Z
Also I'd like to know details of the UTXO database. Is it a MySQL db? Is the lookup done using a combination of in-memory LRU cache and the mysql db? Thanks!
morpheus
CC BY-SA 4.0
2019-03-27T16:46:16.163Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/91613/discussion-on-answer-by-andrew-chow-how-is-a-bitcoin-transaction-validated).
Ava Chow
CC BY-SA 4.0
2019-03-27T04:33:51.853Z
2019-03-27T04:33:51.853Z
Ava Chow
<p>w.r.t. a bitcoin transaction, I am really struggling to understand how does bitcoin network validate that I <strong>1) have the bitcoin that I want to send, and 2) haven’t already sent it to someone else.</strong></p>

<p>If my account balance was being kept track of then it would have been easy. The nodes would do a simple if check to test if I have sufficient balance in my account before I spend any money. But as I have learnt a bitcoin transaction destroys bitcoins and generates new ones (UTXO). So a transaction looks like:</p>

<pre><code>FromAddress, ToAddress, Id_of_Bitcoin_being_destroyed, Id_of_bitcoin_being_created
</code></pre>

<p>The above assumes that I have the exact change I want to pay - since that is sufficient for purposes of my question.</p>

<p>So now before committing this transaction, the nodes need to verify:</p>

<pre><code>isDestroyed(Id_of_Bitcoin_being_destroyed) == false; i.e. coin has not been spent already

Owner(Id_of_Bitcoin_being_destroyed) == me; i.e., coin belongs to me
</code></pre>

<p>could someone please explain in detail how is this happening? </p>

<p>Is a node doing a <strong>reverse table scan</strong> (i.e., scan the blockchain starting from most recent transaction to oldest one) until it locates <code>Id_of_Bitcoin_being_destroyed</code>? Then it can answer both questions above. <strong>However, this algorithm cannot scale at all</strong> and is the crux of what I am trying to understand.</p>

<p>To make it concrete lets say <code>Id_of_Bitcoin_being_destroyed = 1234</code>. A reverse table scan happens and following record is located:</p>

<pre><code>From:Me, To:Brian, 1234, 5678
</code></pre>

<p>The node detects I have already spent the coin and transaction fails.</p>

<p>Another example. In this case a reverse table scan finds:</p>

<pre><code>From:Brian, To:Me, 5678, 1234
</code></pre>

<p>The node can say with confidence that I own the coin and it has not been spent. </p>

<p>I have sincerely tried very hard to understand this and find the answer online including looking at<a href="https://bitcoin.stackexchange.com/questions/77950/understanding-how-validation-of-a-transaction-works"> [1</a>, <a href="https://www.coindesk.com/information/how-do-bitcoin-transactions-work" rel="nofollow noreferrer">2] </a>but was unsuccessful. E.g., <a href="https://www.coindesk.com/information/how-do-bitcoin-transactions-work" rel="nofollow noreferrer">1</a> just says this:</p>

<blockquote>
  <p>This transaction can be validated – that is, it can be confirmed that
  I own the bitcoin that I am transferring to you, and that I haven’t
  already sent it to someone else – by plugging the signature and my
  public key (which everyone knows) into the bitcoin program.</p>
</blockquote>

<p>But this leaves much unexplained to me.</p>

CC BY-SA 4.0
2019-03-27T23:32:27.020Z
related: https://bitcoin.stackexchange.com/questions/29780/why-does-bitcoin-store-all-transaction-inputs-and-outputs-instead-of-just-an-a
morpheus
CC BY-SA 4.0
2019-03-28T03:32:27.983Z
an excellent article and video: http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html
morpheus
CC BY-SA 4.0
2019-03-28T03:41:59.557Z
related: https://bitcoin.stackexchange.com/a/36038/93046
morpheus
<validation>
How is a bitcoin transaction validated?
morpheus
# How is a bitcoin transaction validated?

(Asked by: username_0 on 2019-03-27)

w.r.t. a bitcoin transaction, I am really struggling to understand how does bitcoin network validate that I **1) have the bitcoin that I want to send, and 2) haven’t already sent it to someone else.**

If my account balance was being kept track of then it would have been easy. The nodes would do a simple if check to test if I have sufficient balance in my account before I spend any money. But as I have learnt a bitcoin transaction destroys bitcoins and generates new ones (UTXO). So a transaction looks like:

```
FromAddress, ToAddress, Id_of_Bitcoin_being_destroyed, Id_of_bitcoin_being_created

```

The above assumes that I have the exact change I want to pay - since that is sufficient for purposes of my question.

So now before committing this transaction, the nodes need to verify:

```
isDestroyed(Id_of_Bitcoin_being_destroyed) == false; i.e. coin has not been spent already

Owner(Id_of_Bitcoin_being_destroyed) == me; i.e., coin belongs to me

```

could someone please explain in detail how is this happening?

Is a node doing a **reverse table scan** (i.e., scan the blockchain starting from most recent transaction to oldest one) until it locates `Id_of_Bitcoin_being_destroyed`? Then it can answer both questions above. **However, this algorithm cannot scale at all** and is the crux of what I am trying to understand.

To make it concrete lets say `Id_of_Bitcoin_being_destroyed = 1234`. A reverse table scan happens and following record is located:

```
From:Me, To:Brian, 1234, 5678

```

The node detects I have already spent the coin and transaction fails.

Another example. In this case a reverse table scan finds:

```
From:Brian, To:Me, 5678, 1234

```

The node can say with confidence that I own the coin and it has not been spent.

I have sincerely tried very hard to understand this and find the answer online including looking at [[1](https://bitcoin.stackexchange.com/questions/77950/understanding-how-validation-of-a-transaction-works), [2]](https://www.coindesk.com/information/how-do-bitcoin-transactions-work) but was unsuccessful. E.g., [1](https://www.coindesk.com/information/how-do-bitcoin-transactions-work) just says this:

> This transaction can be validated – that is, it can be confirmed that
> I own the bitcoin that I am transferring to you, and that I haven’t
> already sent it to someone else – by plugging the signature and my
> public key (which everyone knows) into the bitcoin program.

But this leaves much unexplained to me.

**Tags:** validation

> **Comments:**
> **username_0**: related: https://bitcoin.stackexchange.com/questions/29780/why-does-bitcoin-store-all-transaction-inputs-and-outputs-instead-of-just-an-a  
> **username_0**: an excellent article and video: http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html  
> **username_0**: related: https://bitcoin.stackexchange.com/a/36038/93046  

---

## 1 answers

### Answer by username_1 on 2019-03-27. Score: 5 | Accepted answer

Nodes maintain multiple databases, they do not just store the blockchain and scan it every time it wants to do something. These databases include a block index (so that it knows where to find a block) and the UTXO set. The database containing the UTXO set is what matters here. That database contains the identifiers for every single UTXO and the UTXO itself. A UTXO consists of a spending condition (known as the scriptPubKey) and an amount.

A node will begin building its UTXO database when it starts syncing the blockchain. As it validates blocks, it goes through every transaction in that block and adds to its UTXO database the outputs that every transaction creates. It also removes every UTXO that is spent by a transaction. So once a node is fully synced, the UTXO database contains every Unspent Transaction Output in a way that is easy to lookup.

So when validating a transaction, to determine whether the inputs have not yet been spent, the node will try to find the UTXO using the txid and output index (a UTXO's unique identifiers) in its UTXO database. If it is successful and gets exactly one result, then it knows that the UTXO has not been spent. If it gets no results, the UTXO has already been spent and thus the transaction can be marked invalid.

Once the node has the UTXO for an input, it can proceed to verify that the input satisfies the spending conditions. The spending conditions are contained within the UTXO in a field known as the scriptPubKey. The scriptPubKey is a script written in Bitcoin's transaction scripting language. It is half of a program. When combined with the scriptSig that is provided in the transaction input, the program should be complete and executable.

So the node will (essentially) take the scriptSig, append the scriptPubKey to the end of it, and execute the resulting program. If that program completes execution and returns true, then the script is valid and the spending conditions have been met. Thus that input is valid. If all inputs are valid, and the rest of the transaction checks pass (locktime checks, outputs have valid amounts, etc.) then the entire transaction is accepted as valid.

---

If you noticed, I mentioned that UTXOs have spending constraints, not owners. This is because UTXOs don't have owners. Some can be spent by anybody because the spending constraint says that anyone can spend the output. All that a node cares about is that the spending constraints are met.

But we as humans care about owners, so there are a subset of spending constraints that are commonly used to indicate that someone is an "owner" of a UTXO and is the only person allowed to spend it. These spending constraints basically say the following:

"in order to spend this output, the spender must provide both a public key which matches this particular hash and a signature over the spending transaction produced with the private key of the public key with the aforementioned hash"

This spending condition can be abstracted into human terms as saying "the person with the private key that corresponds to the public key whose hash is in the script owns that output".

> **Comments:**
> **username_0**: Thanks @Andrew username_1. "The database containing the UTXO set is what matters here." So is each node is maintaining a massive in-memory hashtable indexed by UXTO of size O(n) where n is # of UXTOs in the system? That sounds infeasible to me. The bitcoin chain as of now has about 600k blocks in it. Each block containing about 3000 transactions. In worst case this gives n = 600k * 3k = 1.8G. ouch!  
> **username_0**: Is bitcoin open source? Could I get a pointer to the relevant code which answers the 2 questions in OP?  
> **username_1**: The most common node software used in Bitcoin is open source (as is basically everything else used in Bitcoin). Code that does the UTXO lookup can be found here: https://github.com/bitcoin/bitcoin/blob/master/src/validation.cpp#L663. Script execution happens here: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1472  
> **username_0**: thanks. Could you answer my other question in comment as well? As you say "the node will try to find the UTXO using the txid and output index (a UTXO's unique identifiers) in its UTXO database" This does not sound scalable to me at all. as I argued earlier, the bitcoin ecosystem would be having approx 1 billion UTXOs and this number will only increase in future. Do you think this is scalable? Could we move the discussion to chat? I don't see any option to do that.  
> **username_0**: Also I'd like to know details of the UTXO database. Is it a MySQL db? Is the lookup done using a combination of in-memory LRU cache and the mysql db? Thanks!  
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/91613/discussion-on-answer-by-andrew-username_1-how-is-a-bitcoin-transaction-validated).  

---

