Author: Borui Li

In computer and networking security course we learned about the communication and interactions between the user and servers via OpenPGP, which intrigued me to research about graph theory and the network properties of these communication relationships. The trust in openPGP nowadays relies on social relations for identify verification; ideally a web of trust should model real world relationships.

OpenPCP consist of two main subcategories PGP and GPG.

Pretty good privacy, also known as PGP is a way for people to communicate over the internet, protected from eavesdropping. This technology is used in everyday communication such as emails and messages. The idea of PGP is consisted of both a public and a private key for each user. Where messages are encrypted with the receiver’s public key, only the receiver can decrypt the message using their private key; there for ensures no one else other than the receiver can get the message.

OpenPGP is the newer version of PGP that is capable for international use. Where the certificate is verified by finding a trustworthy certification path to an already verified key, meaning all verified certificates are linked to one and other in some way. Every user using OpenPGP will be generating a public/private key that becomes the certificates to verify each other. The generated keys are stored in a Synchronizing Keyservers (SKS) for later referencing.

This table is the overall data set that was gathered in 2009 about 2.7 million keys found in the key database storing key transactions within OpenPGP. Within that data there is one signature chain between every key pair that forms strongly connected components (SCC). The signature chain is the connection between all keys that are trusted. A key become trusted after a already existing trustworthy key accepts this new key.

Graph (a) is the average distances between nodes (keys) in a log-log degree scale from the table above. Meaning the distribution of the node degrees (number of keys) follows a power law distribution. In the graph (a), the largest SCC range is between four and seven. The certification path for GPG must be no longer than 5 keys. So the average of graph (a) is slightly below the GPG limit. Further indicating that the OpenPGP is as powerful as the usage of the GPG. Graph (b) shows the indegrees in the largest SCC, which shows the result to be heavily skewed, which a much higher average. The keys in OpenPGP show a impeccable example of large data and degree distributions.

GPG also known as GnuPG is branch off of OpenPGP, where it serves as a replacement for PGP.  In the basic concept of GPG follows closely to the structural Balanced/unbalanced Network we studied in class. GPG uses a decentralized trusted model, where it branch out to other trusted source; similar to the motto “friend of my friend is my friend”. Identical to the theory of structural balance, where the edges of the structural triangles are all positive is consistent with “friend of a friend” intuition.

This is the case with trusted interaction processed by the GPG forms a balanced network. On the other hand, the unreliable sources can also be processed by GPG and form a balanced network. This is followed by the intuition that “the enemy of my friend is my enemy”. In GPG, if a user A or a source A is flagged to be untrustworthy by some trusted source B, then the untrustworthy source A will become untrustworthy to the sources that believe the trusted source B. Therefore forming the balanced structure, where all trusted source distrust the malicious source A. GPG is a perfect example of a balanced structure in a large network.

The relationship of online interactions and the trust between each user is quite intriguing and heavily related to what we have learned in Social and Information Networks course. From something that we use every day, in the background of all our communication on the internet, is importantly associated to some of the most important network properties.

Ulrich, A., Holz, R., Hauck, P., & Carle, G. (2011). Investigating the OpenPGP Web of Trust. Computer Security – ESORICS 2011 Lecture Notes in Computer Science, 489-507. doi:10.1007/978-3-642-23822-2_27

[Schematic diagram of a Web of Trust]. (n.d.). Retrieved November 12, 2020, from https://en.wikipedia.org/wiki/Web_of_trust#/media/File:Web_of_Trust-en.svg

What is Bitcoins:

Bitcoin is an online currency and its popularity has been growing in recent years. It was create to be a purely online cryptocurrency, which has been decentralized as an electronic currency, and it was first introduced to the public in 2008 on the domain name Bitcoin.org. The growth of this currency did not accelerate until 2015 to 2018. It peak in the late 2017, where 1 Bitcoin was worth nearly twenty thousand dollars USD. After three years, the value of a single Bitcoin did drop; nonetheless, it is still worth an impressing fourteen thousand dollar USD. As the value of each Bitcoin rose, the interest of people mining and using them as virtual currency also increased. Mining for Bitcoin became a very common phrase, where people visualize programmers online digging large data worth of riches with a fantasy pickaxe. In reality, Bitcoin mining is performed by high-powered computers that solve complex computational math problem some of these problems are so complex that it is impossible to be solved by normal computers.

Interests:

The uniqueness of the Bitcoin online transaction is the users and their transactions can remain anonymous, while in traditional bank records all transactions between all users. The connection and users of normal banks would create an intriguing graph to analyze; however, the graph between anonymous Bitcoin users will be much more interesting to analyze.  Each user of Bitcoin contain their special key that allows them to access their Bitcoin account anonymously, yet all the transactions of these anonymous nodes can all be accessed and tracked publicly, which can provide an unusual graph.

User Analysis:

The main contributors to Bitcoin’s success are the data miners and the users who use and bank them. Many type of contributers:

1. The user that deposits Bitcoins into the bank and receives a public key
2. The user that incorporates his public key and allows bank to track his transactions
3. The transactions that allows the network to flow
4. The transactions between the miners and transaction block
5. The linking of transactional blocks

In the following simple graph displays the micro transactions between users, banks and miners.

From this simple depiction of a simple Bitcoin transaction, the user’s relationship with Bitcoin forms the structure of a bowtie. The interaction of each user and other users forms a strongly connected component. The public key received from the bank to each user and the transaction blocks formed by users can represent as the IN of the structure.  The OUT structure of this bow-tie structure would be the miners. The Tube connecting the miners to the transaction block allows new currency to flow back into the network.

Graph Analysis:

In the following data graph shows the visualization of the user network. The large clusters shows the external incomes, such as Bitcoins received from other clusters. The edge between any two nodes represents at least 200 transactions.

The nodes are colored by category: blue nodes are mining pools; orange are fixed-rate exchanges; green are wallets; red are vendors; purple are bank exchanges; brown are gambling; pink are investment schemes; and grey are uncategorized.

The three main clusters in this graph are between satoshi, mtgox and deepbit/slush. Satoshi is the pseudonymous of the inventor of bit coin, as he holds a large share of the Bitcoin transaction between him and other users should be most frequent.  Mtgox is arguably the second largest cluster center in this graph as they are a Bitcoin exchange base for Japan that process most bank exchanges. Deepbit/slush are large mining sites for Bitcoins, they provide new funding for rest of the graph, resulting them to become the third largest cluster hot zone. These three large clusters form a strongly connected graph. The connection between each cluster centers forms strong ties as they contain millions of transactions.

Conclusion:

In conclusion the graphs show the characterization of the Bitcoin network, focusing on the user to user transaction with no real identification of each user other than a public key. To accomplish this task, the analysis of the new clustering heuristic of each graph. This shows the intricate network of Bitcoin transaction and the connection between anonymous users.

Reference:

Meiklejohn, S., Pomarole, M., Jordan, G., Levchenko, K., Mccoy, D., Voelker, G. M., & Savage, S. (2013). A fistful of bitcoins. Proceedings of the 2013 Conference on Internet Measurement Conference – IMC ’13. doi:10.1145/2504730.2504747

https://www.researchgate.net/publication/262357109_A_fistful_of_bitcoins_characterizing_payments_among_men_with_no_names