Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Shymaa-Arafat on May 12, 2021, 04:32:59 AM



Title: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 12, 2021, 04:32:59 AM
Could anyone elaborate more on Bitcoin Transaction Graph?
I only found 2 papers, 2015
https://www.researchgate.net/publication/271855021_Bitcoin_Transaction_Graph_Analysis
and 8/2018:
Bitcoin_tcm18-302979.pdf
"Do Bitcoin Users Really Care About Anonymity?
An Analysis of the Bitcoin Transaction Graph", Anil Gaihre, Yan Luo, Hang Liu, University of Massachusetts Lowell.

It's stated as a topic in the next ACM conference, so there must be more there???
https://aft.acm.org/aft21/cfp.html

From the paper, page5
Quote
With the available transaction and address information from the tool, we create mappings from transactions and addresses to numerical vertex IDs. Since each edge in the graph always connects to one address and one transaction, this graph is thus a bipartite graph [50]. Further, to conduct time evolving
analysis of the transaction graph, we select vertices based
upon their timestamps. In total, the amounts of transactions and addresses are 321,043,952 (321 million) and 399,344,697
(399 million), respectively, as well as edges are 1,692,308,191
(1.6 billion).
.
-Which stands for UTXOs here?edges or address vertices?
-So u think such analysis could help in deducing things like the Merkle Tree structure, more accurate analysis on the increase in the expected number of UTXOs thru time???
.
Here's a fig. from the paper to help in seeing some connection.
https://user-images.githubusercontent.com/83260375/117694193-22769a00-b1bf-11eb-8796-c46e41db0138.jpg

(I'm thinking of connections to my idea  previously stated here
https://bitcointalk.org/index.php?topic=5334763.0
but I think I'd better here a feedback from the group before I state my thoughts, maybe there r more info & research papers that I missed)


Title: Re: Bitcoin Transaction Graph
Post by: odolvlobo on May 12, 2021, 07:26:47 AM
I don't know if there is a uniform definition for a "Bitcoin Transaction Graph". You can represent transactions as a graph in many different ways.

However, I think that the most accurate graph would be a DAG with transaction as nodes and outputs as a directed edges between transactions.

You can convert the graph, turning outputs into nodes and transactions into edges, but then a single transactions could be represented by multiple edges. In this form you can group output nodes into addresses and wallets, though it would no longer be acyclic.


Title: Re: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 12, 2021, 01:45:53 PM
Quote
However, I think that the most accurate graph would be a DAG with transaction as nodes and outputs as a directed edges between transactions
It is already stated in the paper that transactions & addresses the nodes, edges r in/outs bet them.

The paper was studying the ratio of address reuse, so can we deduce if new addresses r always used that
no of edges will be equal to no address nodes, both equal to no of UTXOs at a given time stamp (or to total of in & out? or SUM of no. of UTXOs in the studied interval?
I'm more convinced with the 2nd ( edges = TXins +TXouts), but I'm not sure.

If this is correct, we could say that no. edges = no. of operations done (deletions & insertions that I'm trying to shortcut into fewer steps by replacements) on the Merkle Tree processing a single block???

Maybe from the attached fig in the paper I can predict the probability of each case in my strategy, or more over a more accurate formula for the expected number of UTXOs deduced from the expected increase of their number after each block(related to the no. of new addresses when the use of old addresses is allowed)
.
These r still just thoughts or ideas


Title: Re: Bitcoin Transaction Graph
Post by: NotATether on May 12, 2021, 07:27:27 PM
Given that most transactions are done from an exchange or wallet which only lets you make a 1-input --> 2-output transaction, we can assume that the number of addresses increases by sqaure-root or similar with respect to time. My reasoning is that even though 1-2 is the most common, where you're sending to a likely-reused receiving address and a completely new change address, 2/3/4/5-2 transactions aren't rare either and generally they wipe some input addresses clean - since in this configuration there is probably multiple inputs being spent from 1 or 2 addresses - while making a single new change address.

So some old addresses being wiped while new change addresses are steadily made brings us below linear growth, but I think square-root growth is too small to represent it so it's kind of like when you take an exponent or N but the exponent is near 1, like 0.9 or something, you know what I'm saying?

I'm always assuming the receiving address is reused to keep calculations simple.

Data that shows how many times an address is reused (and when) will be very helpful to figure out if most 1-2 transactions are actually spending the only input of an address or one of several inputs from it.

And of course, there are anomalies where address-less exchanges like Coinbase do all their movement through a single daily transaction with high inputs/outputs count, I consider such transactions as outliers and would just remove them from the dataset.


Title: Re: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 12, 2021, 08:13:20 PM
Quote
Data that shows how many times an address is reused (and when) will be very helpful to figure out if most 1-2 transactions are actually spending the only input of an address or one of several inputs from it.
I'm not sure if u  had a look at the paper or not, it does too analyze miner coinbase transactions differently (Fig10, which I didn't attach), but there r 2 comments:
.
1- u have to know the paper and even the official Bitcoin site does NOT recommend reusing the same address because it reduces anonymity. I just use the assumption to analyze the number of UTXOs and the tree structure ( considering replacement analogous to using the same address without the bad side effects; I'm just using the same node in the Merkle Tree with a different key address)
.
2-The most common 1:2 transactions u r talking about, even without Transaction Graph analysis, implies that the expected no of UTXOs in a given Bitcoin state is roughly the total number of transactions since the beginning of time.
It is like a recursive formula calling "no of UTXOs in a given block (i)", T(i), then:
T(i) = T(i-1)+Sum{(outputs-inputs)}for all TXs in block i
If we assume the av difference is one, then roughly speaking

T(i)=T(i-1)+no.of TXs
      = Sum(no. of TXs)from"0"to"i"

.
I think this is straight forward although no one state it directly.
What I'm trying to do is minimize the tree operations to this limit by never delete if u r going to insert in the same next step for the same transaction. Can this transaction graph analysis help me predict the tree structure ( how balanced it is, or lend itself to degenerate?)
.
3-Can I find a programming partner in this group (software developer to do the coding steps & get the test results) obviously will be partner in the paper with name written and everything???


Title: Re: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 13, 2021, 12:49:51 PM
Quote
If we assume the av difference is one, then roughly speaking

T(i)=T(i-1)+no.of TXs
      = Sum(no. of TXs)from"0"to"i"

Note that this kind of resembles reality, since the counter says it's about 279,000 TXs per day, approximately
256*1024*(256+128)*12yrs ~ 2³⁰ UTXOs nowadays
(The exact total no of TXs as stated in
https://www.blockchain.com/charts/n-transactions-total
is 2³⁰ > 641.156m > 2²⁹)
-While the exact total no of UTXOs is  > 78m, ie 2²⁷>UTXOs>2²⁶
-The difference maybe implies that " miners merge TXs" constitute a considerable ratio (those as described in the paper n:1 TXs where miners gather their rewards from different blocks into one address, case I in the fig.)
![IMG_20210514_090144](https://user-images.githubusercontent.com/83260375/118234296-70c3bb80-b493-11eb-9328-fbce7b16f10f.jpg)



Title: Re: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 14, 2021, 02:56:37 AM
@NotATether
To not be giving wrong/mixed up info...
It seems this is not the only or standard graph representation, in
https://appliednetsci.springeropen.com/articles/10.1007/s41109-019-0249-6#ref-CR9
They used a different mapping ...
Quote
In the transaction graph of a cryptocurrency, vertices are accounts (or addresses) in the currency network, and the edges between them are transactions between those accounts.
.
It's also said that it follows the Power law distribution, as Utreexo paper said statistics show about UTXOs life span

Quote
We also found that the transaction graph of these currencies is non-assortative, i.e. addresses do not tend for transact with a particular type of addresses of higher or lower degree, and the degree sequence of their transaction graph follows the power law distribution.


Title: Re: Bitcoin Transaction Graph
Post by: Shymaa-Arafat on May 22, 2021, 12:07:26 AM
Resulting Remark/observation:

I observed from the test net, that coinbase block reward UTXOs lifetime could reach +35000 block with min 366 thru a fast sampling scan.
Yes it is not very accurate  scan yet, however, I think it might be misleading to put all UTXOs in one bucket and say they follow a power law distribution with alpha bet 1-2.