Blockchains have an incredible impact on our economic systems. Over the last years, more and more illicit activities have taken place not only via the traditional nancial space but also via cryptocurrencies, where tracking illicit activities is more complex. Yet, several blockchain toolkits have been introduced that explore blockchain data. There is a clear industrial need to bring together many of those valuable methods into a principled approach that upholds central aspects such as the ability to provide explainable analytics. In this paper, we report on an international industrial and academic collaboration that uses a declarative, rule-based approach on top of a Knowledge Graph system and describes the use-case of analyzing the Petya ransomware.
Business Case and Importance. Blockchains have an incredible impact on
our economic systems with a total market capitalization of 1500 billion US
Dollar [
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). clear industrial need to bring together many of those valuable, but ad-hoc combined methods into a principled approach. This principled approach must uphold central aspects such as the ability to provide explainable analytics, so that the derived insights are based on a solid foundation. Meeting these challenges is one of the traditional strong points of rule-based, declarative AI.
Solution. Researchers have recognized [
In this paper, we introduce a connection on top of the graph by interpreting
the blockchain as a logic-based Knowledge Graph. We show that blockchains
share di erent research questions with the Knowledge Graph domain. One
particular area of such relationship is given by detecting illicit activities such as fraud
or ransomware payments [
Apart from this general connection, this paper is motivated by the challenge:
can a rule-based, declarative Knowledge Graph be used to provide an
end-toend analysis of the Petya ransomware, a particularly widely discussed case in
media, e.g., [
Main Contributions. To summarize, our main contributions are:
{ We identify a novel relationship between blockchains and Knowledge Graphs,
which goes beyond the graph-like structure. We show that reasoning in
Knowledge Graphs share common tasks with typical blockchain work ows.
{ We present a rule-based approach for detecting illicit activities in
blockchains. By using Datalog rules we provide a transparent and declarative way
to formalize speci c questions.
{ We show our approach by constructing and querying the Petya ransomware
graph. We provide several non-trivial answers to industrial use-cases.
Organization. The remainder of this paper is organized as follows: In Section 2
we provide background information required in the following chapters. Section 3
explains the relationship between a Knowledge Graph system and blockchains
in detail. In Section 4 we provide an in-depth analysis of the Petya ransomware.
We provide related work in Section 5 and conclude the paper in Section 6.
Blockchains. A blockchain is a type of distributed ledger, where blocks are
structured in a single-linked list which is linked with a hash reference to the previous
block. Each block contains a list of transactions, which contain information
required to transfer coins (and data) between di erent accounts. An account is
created by a private and public key pair. The private key is used to spend the
coins, while the (hash of) the public key is used to receive the coins, hence called
the address of the account. In Bitcoin, each transaction can have multiple inputs
and outputs either from one or from di erent users. An input is used to spend
a previous output, which creates an acyclic graph of spent outputs. The di
erence between the inputs (i.e., output values of the previous transaction) and the
output values in one transaction are the fee paid to the miner of the block [
Mixing services. Mixing services are used to enhance the privacy of the user.
While mixing services are embedded into the protocol in some blockchains, the
usage in Bitcoin requires expertise. In case of Bitcoin, mixing tries to hide the
mappings between the inputs and outputs of the transaction taking the
transferred values in consideration to obfuscate which input and output address
belongs to the same user. In simple words, a perfectly mixed transaction would
have the same value for each input and output. It turned out, that many
mixing attempts are not perfect. Address-reuse, same output or input addresses, or
di erent output values make mixing attempts more or less useless [
As discussed in the previous sections, the Bitcoin blockchain structure can be
interpreted as a graph-like structure for di erent blockchain applications. While
this connection builds the fundamental relationship to Knowledge Graphs by
mapping the Bitcoin transaction structure to the extensional component of the
Knowledge Graph, we can identify several additional properties that overlap
between blockchains and the Knowledge Graph system. All the mentioned tasks
in Section 1, such as clustering, have in common that they infer new knowledge
based on existing data, which can be seen as generating new nodes and edges
(the derived extensional component) by using the intensional component. Hence,
Knowledge Graphs and blockchain tools share additional functionalities:
{ Shared reasoning tasks. The typical behavior of tasks involving
blockchains highly relates to Knowledge Graph reasoning. For example,
identifying the real-world entities behind accounts depends on the clustering of
several accounts into one real-world entity, which is comparable to entity
resolution [
While so far our focus has been on the abstract connection, we now concentrate on a very concrete use-case, namely the Petya ransomware challenge. We do want to mention that the provided description will only focus on the transaction level, yet Knowledge Graphs are also made to perfectly model smart contracts as part of the intensional component, i.e., the contract as rules. Smart contracts are applications living inside the blockchains such as lottery services or supply chain applications.
Third-Party Tools
Discover Knowledge
Graph Fee Distribution
Exchange Tagging
In this main section, we report how our approach performed on a concrete usecase, namely the analysis of the Petya ransomware. This is only one example, but representative for demonstrating how a concrete use-case can be solved using a rule-based Knowledge Graph system. In fact, it requires to give answers to three questions, spanning the entire life cycle of Knowledge Graphs: { How to construct a Knowledge Graph for analyzing the Petya ransomware in order to include relevant data sources. (Section 4.1) { How to discover new facts based on the data in the Knowledge Graph to get better insights. (Section 4.2) { How to formulate and use reasoning queries to perform blockchain analytics and extract relevant information. (Section 4.3) In Figure 2 we detailed the concrete steps of the work ow to address the previously described questions. It begins with the construction by using the blockchain and tagging services, then moves on to handling distinct discovery processes (e.g., fee distribution, linkability) on three di erent graph perspectives, before concluding with a coin ow analysis as a reasoning task. We will provide details on each part in the respective subsections. 4.1
Knowledge Graph construction has the goal of collecting and modeling relevant data sources as the extensional component in a Knowledge Graph system. In the case of the Petya Knowledge Graph, we use two di erent data sources, namely (i) the Bitcoin blockchain itself for the basic data and (ii) tags to Bitcoin addresses belonging to exchanges (i.e., services that swap di erent cryptocurrencies with other parties) from di erent reliable online sources.
Bitcoin Model. There exist di erent views on the Bitcoin blockchain, for example the default structure of the blockchain as de ned in Section 2, or the linking of transactions on the transaction or on the output level. Since e cient Knowledge Graph Management Systems allow to convert between di erent views with negligible performance overhead, we de ne the complete blockchain structure as our extensional component of the KG and then convert this structure to di erent views with rules for analysis during the discovery step (see Section 4.2, where we will show graphical illustrations). The main relations are:
Relations 1-4 de ne the structure of the blockchain. Each transaction is part of a block and has several inputs and outputs. An input references to an output, which it consumes, while a block references to its predecessor (as described in Section 2). We want to point out that any additional attributes, like the address of the output, will be provided by additional relations, if required, e.g., TxOutAddr (txHash, outIndex, addr).
Exchange Model. For modelling exchanges we use facts in the Knowledge Graph that mark an address as an exchange, i.e., Exchange(addr). Petya Blockchain Source. For Petya, we extracted the Bitcoin blockchain data only in the relevant time frame of the event, i.e., between the blocks 473.000 and 490.000. In detail, we scanned the blockchain for transactions sending money to the ransomware address \1Mz7153h. . . " and imported all following transactions in the Knowledge Graph until we reached one of our three termination criteria: (i) We identi ed an exchange by checking the output address against the exchange model. (ii) We reached the end of our interval of interest, i.e., block number 490.000. (iii) We exceeded a depth-limit of ten in our search graph. This depth-limit was chosen due to the exponentially increased breadth of the transaction tree in the deeper levels and the reduced likelihood that the coins in the transaction are still belonging to the Petya user. 4.2
Knowledge Graph discovery extends the Knowledge Graph by deriving the
extensional component through applying rules of the intensional component. In
case of Petya, we extend the Knowledge Graph during discovery with additional
facts to gain more insight during the analysis. These facts can be either added by
our own rules or by rules interacting with other blockchain analytic frameworks.
In order to integrate additional knowledge, it is required to answer the following
three highly important questions:
{ How can we use di erent views of the blockchain for analytical tasks?
{ How can we use data provided by other analytical tools? We show this by
calculating the linkability (introduced in Section 2) between in- and outputs.
{ How can we use existing knowledge to extend the Knowledge Graph with
our own rules? We show this by extending the list of exchanges.
In order to answer these questions, we show rules that describe and highlight
the logic-based approach. These rules are given and executed in Vadalog [
Tx In/Out Fee (b)
Output-Input Fee (c) KG structure. The goal of our Petya analysis is to investigate the coin ow between the ransomware address and possible exchanges. As brie y mentioned in the previous section, depending on the task, di erent views of the blockchain as graphs are preferable. Figure 3 visualizes three di erent views. In (a) we show the transaction graph of the blockchain, which we use to calculate the fees and can be directly extracted from the blockchain data, in (b) we show the outputinput graph with all possible edges of a single transaction, which can be inferred from the blockchain data and in (c) we show the link graph, where outputs and inputs are linked if there is a known ow of coins between inputs and outputs of a transaction, which has to be estimated from the blockchain data. These three views are complementary, since in case of coin ow analysis, we are required to know general properties of a transaction, as shown in (a)|e.g., fees, input and output volumes for weighing the coin ow|as well as the actual ow of the coins. In order to capture the ow, we introduce possible \edges" (b) between the inputs and outputs of the transaction, since this information is not present in the blockchain. Note that the link graph (c) is an uncertain graph, as the available information in the blockchain is only su cient to predict such links with a certain likelihood (e.g., via linkability discussed in the preliminaries). Algorithm 1 Fee Distribution
TxOut(t; i; v); ov = sum(v) ! OutVolume(t; ov) TxIn(t; i; st; si); TxOut(st; si; v); iv = sum(v) ! InVolume(t; iv) InVolume(t; iv); OutVolume(t; ov); f = iv ov ! Fee(t; f )
TxIn(t; i; st; si); TxOut(st; si; v); InVolume(t; iv); Fee(t; f ); if = (v=iv) f ! InFee(t,i,if) (1) (2) (3) (4) Algorithm 1 presents the concept of \fee". Rules 1 and 2 de ne the total input and output volume per transaction. Rule 3 uses these values to de ne the fee. Rule 4 assigns to each input of the transaction the weighted fee according to the ratio between the input value and the total input volume.
Algorithm 2 Mapping from Blockchain View to Output-Input (Oi) View
TxIn(t; i; st; si) ! OiNode(st; si; t; i) OiNode(ot; oi; it; ii) ! 9id OiId(id); OiOut(id; ot; oi); OiIn(id; it; ii) (5) (6) OiIn(id1; t; ii); OiOut(id2; t; oi) ! PossibleEdge(t; ii; oi); PossibleOiEdge(id1; id2) (7) Algorithm 2 presents the conversion between the blockchain view and the output view. Rule 5 rewrites the blockchain in- and outputs identi ed by its transaction and index to create a combined view of them. Rule 6 assigns each output-input node a unique id and splits it into an output and input part. Rule 7 creates a possible edge between in and outputs of a single transaction for the output-input view as well as the blockchain view.
Linkability. As described, we extend the possible edges of the output-inputview (b) of the Knowledge Graph with some metric that describes the likelihood of an existing coin ow from an input to an output. The metric we choose here is linkability (as discussed in Section 2). For this, we compute the linkability with Boltzmann for each transaction, where a calculation is feasible in time. We use the default timeout value of 600 seconds and limit the maximum to 16 input or output values (the default is 12). Algorithm 3 shows the application of the output of the Boltzmann computation (i.e., a value between 0 and 1 for each address combination), where we de ne only edges larger than or equal to the threshold value of the linkability score, here 100%, as a link.
Algorithm 3 Linkability-based Link View
PossibleOiEdge(id1; id2); OiAddr(id1; a1); OiAddr(id2; a2);
OiIn(id1; t; ); Linkability(t; a1; a2; l); l 1:0 ! Link(id1; id2) (8) Note that we allow to include the computation of external tools in the reasoning process (here with accessing the Linkability fact), allowing an interaction with highly optimized, task-speci c tools. However, the usage of such tools causes a trade-o between explainability and performance, as such computations provide us only with the output value (i.e., a black-box algorithm). For interested readers we provide excerpts of a non-trivial, fully explainable (white-box) approach, expressed in a rule-based format, in the appendix.
Exchange identi cation. Online sources provide some, but not nearly all addresses of exchanges. Therefore, our goal is to identify additional exchanges based on existing exchange data.
For this, we analyze di erent transactions where some inputs are from exchanges. Consider for example the transaction \0f44a800. . . " presented in Figure 4, which is part of our Petya graph. The gure shows that all inputs have a 2-of-3 multisig format (i.e., two of three users have to sign the input that it is accepted in the transaction) and that four of these inputs are tagged by a (d) EX EX
EX EX Address Existing Tag
New Tag speci c exchange which we shall refer to as \exchange X", which is an exchange provider for cryptocurrencies. This transaction reveals that there exist some exchange transactions which follow a speci c format. In this case, we assume that all inputs are from \exchange X", because they share the same input-type, e.g., 2-of-3 multisig. Therefore, we de ne a generalized heuristic: If a transaction has several inputs and one input is tagged as exchange, then all inputs have to be tagged as exchange.
The idea is that it is unlikely that an exchange collaborates with a di erent party to send transactions. This heuristic allows us to cut the reasoning space by reducing the number of relevant nodes.
The heuristic is visualized in Figure 5 (d), where an existing tag propagates this information to the transaction and to the other addresses of the input nodes. Algorithm 4 Exchange Tagging
TxIn(t; i; st; si); TxOutAddr(st; si; a); Exchange(a) ! ExchangeTx(t) TxIn(t; i; st; si); ExchangeTx(t); TxOutAddr(st; si; a); ! Exchange(a) (9) (10) Algorithm 4 presents this in rules. Rule 9 models that every transaction having as input an address that belongs to an exchange is an exchange transaction; Rule 10 tags each address of the input of such a transaction as exchange. In this section, we provide rst a general overview of some interesting statistical properties followed by a detail analysis of the coin ow.
Statistical properties. Our goal is to get an overview of the KG, before going into detailed tasks. For this, stakeholders asked the following questions: { How many coins have been received and spent by the ransomware address?
This question indicates the number of relevant coins for analysis.
{ For how many transactions are not we able to compute the linkability? Can
the linkability computation failure be associated with recurring patterns?
These questions indicate the performance of the linkability computation.
Table 1 summarizes the answers to our questions. Our graph has about 100.000
nodes, thereof are about 25% exchanges, with about 770.000 edges between the
nodes. Petya collected about 4.4 Bitcoins in the chosen block-interval, whereof
about 92% have been moved and thus can be tracked in the coin ow analysis.
To answer the second question, we see in Table 1 that we were not able to
compute the linkability of 23% of the transactions. In a detailed analysis, we
analyzed these transactions to identify clusters in input and output
combinations. We identi ed that 286 transactions have 2 outputs (i.e., 64.4% of the total
transactions without linkability). We use this nding, to improve the linkability
in the graph by following \simpli ed" Bitcoin ow heuristic [
Link(id1; id2); OiVal(id2; val) ! VLink(id1; id2; val) (11)
VLink(id1; ; v); s = sum(v) ! OutVolume(id1; s)
OiDepth(id; 0); OiVal(id; vsent) ! VNode(id; vsent) VNode(id1; vsent); Link(id1; id2); OutVolume(id1; vov);
InFee(id1; vfee); OiVal(id1; vin); OiVal(id2; vout); sentR = vsent=vin; totalSent = vsent
(vfee sentR); receiveR = vout=vov; vrecv = totalSent receiveR ! VNode(id2; vrecv) In order to calculate the coin ow, we use a graph traversal query, where we follow all paths with a threshold value (e.g., 100%) of the linkability. Since some paths contain also other inputs, the actual value transferred in an transaction may be higher than the actual value currently owing through this path. We use weighted fees to approximate the fees of the input and de ne the following heuristic to approximate the ow value to the output: The ow to an output is weighted according to all relevant outputs of the input. An output is relevant, if the linkability is higher or equal as the threshold. Consider Figure 5 (e). We have three inputs i1 of 60, i2 of 30 and i3 of 10 coins, two outputs, o1 of 36 and o2 of 54 coins, a linkability of i1 with 0:0 for o1 and 1:0 for o2 and a input ow of i1 of 40. Then the fee is 10 coins, whereof input i1 pays 6 coins, i2 3 coins, and i3 1 coin. The input ow is 40=60 = 2=3 and hence the fee of the input ow of i1 is 4 coins. The total amount of relevant output is 54, and the weighted output of o1 is 54=54 = 1:0. Then the ow from i1 to o1 is (40 4) 1:0 = 36 coins.
Algorithm 5 presents the coin- ow computation. Rule 11 annotates each link with the value of the output, which is used in Rule 12 to calculate the output volume of all valid outputs. Rule 13 initializes the nodes at depth 0 (i.e., transactions to the ransomware address) with the transferred value. Rule 14 propagates this value recursively to the following nodes according to the de ned heuristics.
Table 2 provides an overview of the results. We see that 96.7% of the value is tractable (89% to an exchange and 7.7% as fee), which leaves only 3.3% of the coins intractable. While both heuristics improved the result, we see that the exchange heuristic has a much higher impact on the result and increased the coins, which ow to exchanges, from 84.3% up to 88.9%.
Even without the two heuristic we could track more than 84% of the coins to
exchanges. This can be explained by an exchange at depth 3, which was used
(12)
(13)
(14)
43509166
339588561
a2a6c377...[
We would like to point out that the results are derived using mathematical relationships of Bitcoin transactions and heuristics given by domain experts, so we can guarantee accuracy only with respect to these heuristics. The main goal of this research is to demonstrate how rule-based systems can be used for blockchain analytics, with an emphasis on their ease of use for analytical reasoning tasks and seamless integration with sophisticated algorithms. 5
The related work in the area of blockchain analytics is manifold, as multiple
problems have been studied in detail such as clustering of blockchain
identities [
Bartoletti et al. [
Multiple studies have investigated ransomware activity in the Bitcoin
network. One main direction of the work is the detection of addresses related to
ransomware [
In this paper, we showed how the key industrial challenge of tracking illicit activities in blockchains can be solved via a rule-based, declarative AI approach. We discussed our methodology for the entire life cycle of the Knowledge Graph, including di erent views on the blockchain data, integration of third-party tools and a analytical scenario.
Importance and impact. It is a key mission for the nancial system to prevent being exploited for illicit activities. For this reason, being able to detect and highlight the risks in new systems, such as blockchains, is crucial to its correct operations. The approach showed impact in a variety of aspects: { Simple integration of di erent tools to use in analysis { Ease of trying out new ideas and using explainable, rule-based formulation for interaction between stakeholders. { Low barrier of entry, as only high-level technical knowledge is required, and more people can use and understand the platform.
Our approach allows fully recursive blockchain queries in a declarative way, which increases the maintainability of blockchain analytics scripts. In future work, we want to improve our system by considering speci c performance optimizations for acyclic blockchain graphs, extend the Knowledge Graph to the complete Bitcoin blockchain and develop or use more sophisticated heuristics to improve the overall result.
The nancial support by the Vienna Science and Technology Fund (WWTF) grant VRG18-013 is gratefully acknowledged. A
Assume, we already have created a list of valid combinations by starting with the parent of all inputs linked to all outputs, followed recursively by all nonintersecting pairs of valid input-output sets (i.e., a set is valid if the di erence between input volume and output volume is greater or equal than zero and smaller or equal than the fee), which union of input sets and output sets match the parent. Such a list is presented in Table 3 for four inputs with the values (30, 6, 3, 3) and two outputs with the values (10, 15) with the according max depth of each child. For calculating the linkability, we have to calculate the number of valid mappings and the actual number of usages of each (partial) mapping. This calculation is shown in Figure 7, where (a) counts the number of mappings and (b) counts the number of usages. These numbers are used to calculate the nal linkability between each input and output value by counting each left child, where the input
I0,I1,I2,I3 o0,o1 2 oi00,,io31 i1,i2
i0,i2 2 i1,i3 o0,o1 1 i0o,0i,10,1i3 i2 1 oi00,,io21 i1 1
i0 i1,i2 o0,o1 1 oi00,,io21 i1 1 1 1 and output value is present, used mappings times and each right child, where the values are present, used times. The multiplication of the left child considers the number of sub-mappings provided by the right child.
Algorithm 6 de nes the number of mappings (a). Rule 1 de nes for each element, whether it has a child. Rule 2 uses this information to set the number of mappings to one for all elements that have no children. Rule 3 recursively de nes the number of mappings by the sum of the child mappings plus its own mapping. Algorithm 6 Linkability: Calculation of Mappings Algorithm 7 presents the calculation of the number of usages for each mapping (b). For this, we init in Rule 4 the root mapping with 1 and de ne in Rule 5 recursively the number of usages as the sum of its parents.
Algorithm 7 Linkability: Calculation of Usage per (partial) Mapping List(il; ol; ir; or; ); Usage(ilp; olp; ip; op; v); ip = iljir; op = oljors = msum(v; < ilp; olp; ip; op >) ! Usage(il; ol; ir; or; s)