0

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 Murch for prompting clarification

4
  • 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
    Commented Feb 22 at 13:15
  • Proving that a transaction is committed to by the merkleroot requires a merkle branch or merkle proof.
    – Murch
    Commented Feb 22 at 13:22
  • @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
    Commented Feb 22 at 13:34
  • @Murch yes edges to leaf nodes would require a merkle inclusion proof
    – Lee
    Commented Feb 22 at 13:48

1 Answer 1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.