<p>Since you indicated in a comment that you are fine with multiple edges representing the same transaction, you get a node for each coinbase transaction and each TXO ever created, and edges to the tune of summing up across all transactions the product of inputs and outputs:</p>
<pre><code>node_count = blockheight + TXOs_created
edge_count = Σ_tϵtxs(input_count(t)×output_count(t))
</code></pre>
<p>since each input in every transaction will will be connected to each output in the transaction with a separate edge representing the same transaction.</p>

CC BY-SA 4.0
2024-02-22T13:40:20.060Z
2024-02-22T14:06:50.873Z
2024-02-22T14:06:50.873Z
Murch
<p>Imagine a graph where the leaf nodes are the UTxOs, the intermediate nodes are spent TxOs (vout), the root nodes are the blockheaders and coinbase merklepairs, and the edges are the data required to verify the transition between nodes (i.e. the transactions):</p>
<p>How many nodes and edges would this graph have, as of block 831276?
What would be the longest path through the graph?
Are there any interesting ways to categorise the graph from graph theory? Is it acyclic for example? How many disjoint sub-graphs are there?</p>
<p>What would be the mean/median/range number of leaf-to-root hops through the graph.</p>
<hr />
<p>Small example sub-graph:</p>
<p><strong>RootNode</strong> <em>blockheader coinbase-merklepair (the number required to prove that the coinbase tx is in the blockheader's tx_root)</em></p>
<p><strong>Edge0</strong> <em>coinbasetx</em></p>
<p><strong>IntermediateNode</strong> <em>Vout id from edge0 transaction</em></p>
<p><strong>Edge1</strong> <em>a transaction (vin id == IntermediateNode and input_tx == edge0)</em></p>
<p><strong>LeafNode</strong> <em>the vout for an unspent output from edge1</em></p>
<p>Thanks to RedGrittyBrick and Murch for prompting clarification</p>

CC BY-SA 4.0
2024-02-22T13:15:01.590Z
What is a "coinbase-merklepair"? It’s not clear to me what "Edge1" is supposed to be. Should that be a second transaction that spent the output of the coinbase transaction to create a new unspent output that is the LeafNode? Since transactions can have multiple inputs and outputs, the graph you propose would have many different edges that represent the same transaction. If you instead make both transactions and TXOs nodes, and use edges to connect transactions with their inputs and outputs that might make more sense to me: e.g. [coinbasetx] -- [coinbasetx:0] -- [tx1] -- [tx1:0].
Murch
CC BY-SA 4.0
2024-02-22T13:22:49.883Z
Proving that a transaction is committed to by the merkleroot requires a merkle branch or merkle proof.
Murch
CC BY-SA 4.0
2024-02-22T13:34:15.587Z
@Murch I've made an update. Yes multiple edges would contain same transaction data, the distinction being the destination node. Perhaps your formulation is indeed more sensible.
Lee
CC BY-SA 4.0
2024-02-22T13:48:29.833Z
@Murch yes edges to leaf nodes would require a merkle inclusion proof
Lee
<transactions><utxo><transaction-verification><coinbase-transaction><utxo-set>
How many nodes and edges does the UTXO-coinbase graph have?
Lee
# How many nodes and edges does the UTXO-coinbase graph have?

(Asked by: username_0 on 2024-02-22)

Imagine a graph where the leaf nodes are the UTxOs, the intermediate nodes are spent TxOs (vout), the root nodes are the blockheaders and coinbase merklepairs, and the edges are the data required to verify the transition between nodes (i.e. the transactions):

How many nodes and edges would this graph have, as of block 831276?
What would be the longest path through the graph?
Are there any interesting ways to categorise the graph from graph theory? Is it acyclic for example? How many disjoint sub-graphs are there?

What would be the mean/median/range number of leaf-to-root hops through the graph.

---

Small example sub-graph:

**RootNode** *blockheader coinbase-merklepair (the number required to prove that the coinbase tx is in the blockheader's tx\_root)*

**Edge0** *coinbasetx*

**IntermediateNode** *Vout id from edge0 transaction*

**Edge1** *a transaction (vin id == IntermediateNode and input\_tx == edge0)*

**LeafNode** *the vout for an unspent output from edge1*

Thanks to RedGrittyBrick and username_1 for prompting clarification

**Tags:** transactions, utxo, transaction-verification, coinbase-transaction, utxo-set

> **Comments:**
> **username_1**: What is a "coinbase-merklepair"? It’s not clear to me what "Edge1" is supposed to be. Should that be a second transaction that spent the output of the coinbase transaction to create a new unspent output that is the LeafNode? Since transactions can have multiple inputs and outputs, the graph you propose would have many different edges that represent the same transaction. If you instead make both transactions and TXOs nodes, and use edges to connect transactions with their inputs and outputs that might make more sense to me: e.g. [coinbasetx] -- [coinbasetx:0] -- [tx1] -- [tx1:0].  
> **username_1**: Proving that a transaction is committed to by the merkleroot requires a merkle branch or merkle proof.  
> **username_0**: @username_1 I've made an update. Yes multiple edges would contain same transaction data, the distinction being the destination node. Perhaps your formulation is indeed more sensible.  
> **username_0**: @username_1 yes edges to leaf nodes would require a merkle inclusion proof  

---

## 1 answers

### Answer by username_1 on 2024-02-22. Score: 1

Since you indicated in a comment that you are fine with multiple edges representing the same transaction, you get a node for each coinbase transaction and each TXO ever created, and edges to the tune of summing up across all transactions the product of inputs and outputs:

```
node_count = blockheight + TXOs_created
edge_count = Σ_tϵtxs(input_count(t)×output_count(t))

```

since each input in every transaction will will be connected to each output in the transaction with a separate edge representing the same transaction.


---

