Bitcoin Forum
August 17, 2019, 06:12:59 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Find shortest path between two addresses?  (Read 2600 times)
Cyberdyne
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
July 08, 2013, 11:31:19 PM
 #1

I know blockchain.info has it's Taint Analysis thing, but you can only enter 1 address, and then you need to search for the 2nd address manually, on the page that's returned.

Does anyone know of a place I can input 2 addresses, and have it show me the shortest list of transactions that connect them? (If there is any connection at all)?
1566065579
Hero Member
*
Offline Offline

Posts: 1566065579

View Profile Personal Message (Offline)

Ignore
1566065579
Reply with quote  #2

1566065579
Report to moderator
1566065579
Hero Member
*
Offline Offline

Posts: 1566065579

View Profile Personal Message (Offline)

Ignore
1566065579
Reply with quote  #2

1566065579
Report to moderator
1566065579
Hero Member
*
Offline Offline

Posts: 1566065579

View Profile Personal Message (Offline)

Ignore
1566065579
Reply with quote  #2

1566065579
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1566065579
Hero Member
*
Offline Offline

Posts: 1566065579

View Profile Personal Message (Offline)

Ignore
1566065579
Reply with quote  #2

1566065579
Report to moderator
dexX7
Legendary
*
Offline Offline

Activity: 1106
Merit: 1005



View Profile WWW
July 09, 2013, 04:21:50 AM
 #2

You'd need to walk through each possible path till you find a connection, if any. Quite complex. :/

piotr_n
Legendary
*
Offline Offline

Activity: 2002
Merit: 1049


aka tonikt


View Profile WWW
July 09, 2013, 08:25:26 AM
 #3

This is not an impossible problem to solve, buy rather beyond my math skills.
You'd definitely want to use some smart algo here - probably some flavor of finding the shortest route between two nodes in a graph.
Analyzing all possible paths is too complex.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
domob
Legendary
*
Offline Offline

Activity: 1079
Merit: 1099


View Profile WWW
July 09, 2013, 08:43:53 AM
 #4

This is not an impossible problem to solve, buy rather beyond my math skills.
You'd definitely want to use some smart algo here - probably some flavor of finding the shortest route between two nodes in a graph.
Analyzing all possible paths is too complex.

Excactly.  Without having thought it through, what about simply applying Dijkstra's algorithm?  Its complexity (when edges are stored in a heap) is like N log N, where N is the order of magnitude of number of addresses / transactions, which seems feasible to me.  But please correct me if not, as I said, I haven't really thought that through.

Use your Namecoin identity as OpenID: https://nameid.org/
Donations: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
dexX7
Legendary
*
Offline Offline

Activity: 1106
Merit: 1005



View Profile WWW
July 09, 2013, 02:07:54 PM
Last edit: July 09, 2013, 05:04:44 PM by dexX7
 #5

Excactly.  Without having thought it through, what about simply applying Dijkstra's algorithm?  Its complexity (when edges are stored in a heap) is like N log N, where N is the order of magnitude of number of addresses / transactions, which seems feasible to me.  But please correct me if not, as I said, I haven't really thought that through.

Dijkstra's helps to find the shortest path, but I'm not sure if it reduces the complexity at all in this case, because each edge weight is equal and thus there is no path in favor and so we'd start with the source address and visit each neighbor. If target isn't found, we'd need to visit each neighbor of each neighbor. If it's not found, each neighbor of each neighbor of each neighbor and so on. I guess that would take something like E(k^n) = k^0 + k^1 + k^2 ... steps, where k is the number of connections per node and n is the search depth.

O(n*log(n)) (n for comparison, log(n) for going deeper in a tree) is the best possible complexity for searching based on pairwise comparison, but we don't have any attribute like "this tx-path is more likely than the others" to create an order.

Please correct me if I'm wrong, this is all stuff I know only vague about. Smiley

Cyberdyne
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
July 09, 2013, 09:17:37 PM
 #6

Maybe finding ANY path is too complicated as you guys are discussing, but what about just finding a STRONG path if it exists.

For example, on blockchain.info's Taint page, it lists the associated addresses and the % that they are connected.

What would be great would be if you could enter 2 addresses, and see if they were connected to each other in a strong way.

On a practical level, this would involve nothing more than entering 1 or 2 of addresses into blockchain.info's Taint page and seeing if the other address is on that list, but in an automated way, so one doesn't need to use CTRL-F.

Like, find out if two addresses have a X% or more linkage, otherwise forget it!
domob
Legendary
*
Offline Offline

Activity: 1079
Merit: 1099


View Profile WWW
July 10, 2013, 08:10:00 AM
 #7

Maybe finding ANY path is too complicated as you guys are discussing, but what about just finding a STRONG path if it exists.

For example, on blockchain.info's Taint page, it lists the associated addresses and the % that they are connected.

What would be great would be if you could enter 2 addresses, and see if they were connected to each other in a strong way.

On a practical level, this would involve nothing more than entering 1 or 2 of addresses into blockchain.info's Taint page and seeing if the other address is on that list, but in an automated way, so one doesn't need to use CTRL-F.

Like, find out if two addresses have a X% or more linkage, otherwise forget it!

This would correspond to running Dijkstra's algorithm (I looked up the exact complexity, it is O(E + V log V) where E is the number of edges = transactions, and V is the number of vertices = addresses) in such a way that you stop early as soon as your distance is larger than the treshold you want and you haven't yet found your second address.

Note also that I believe the percents showed on the taint page are related also to the number of coins actually transferred between both addresses, and it is not clear how/if this correlates strongly with the shortest path in the graph.  So I'm not sure what exactly you are looking for.

Use your Namecoin identity as OpenID: https://nameid.org/
Donations: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS | GPG 0xA7330737
Cyberdyne
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500



View Profile
July 10, 2013, 11:25:28 AM
 #8

Note also that I believe the percents showed on the taint page are related also to the number of coins actually transferred between both addresses, and it is not clear how/if this correlates strongly with the shortest path in the graph.  So I'm not sure what exactly you are looking for.

Oh, I didn't realize that, but I guess that's what I'm looking for - How about I word it like this:

Input:  2 addresses

Output:  A number between 0 and 100, showing how strongly the addresses are 'connected' or related, and the number of coins in each transaction would be a useful metric in this case.

0 being there is no connection between them whatsoever, and 100 being that the ONLY coins sent from one address were to the other one.

Ah, if only I had all the time in the world...
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!