De-Anonymization in Bitcoin with Sarah Meiklejohn | a16z crypto research talks

Transcript

I'm very happy to Welcome Back Sir Michael Jones uh professor of UCL also a faculty fellow on 360 secret Deborah Williams star today as we're talking about you know the anonymization thank you Tim it is wonderful to be back um and yeah today I'm going to talk about the anonymization in Bitcoin um this is most of the talk will cover um some new work that I'll be presenting in two days at using security but I'll also give a kind of overview of where things are at before then um those of you who are at my talk earlier in the summer there is some definite overlap but I think you will not be too bored um and yeah please do chime in with questions uh anytime you

have any because this is new material so I don't yeah it might be unclear so um hopefully I don't need to tell anyone in this room or on Zoom um that Bitcoin is not Anonymous um so there has been uh you know there have been a lot of papers published on this topic um you know in case none of you care about Bitcoin by the way or I mean some of you might I assume that not all of you don't care about Bitcoin but yeah uh if any of you don't care about Bitcoin you know this this result these results apply very directly to thousands of other cryptocurrencies um and there's other related results that apply to you know other

cryptocurrencies as well including potentially your favorite sort of privacy coins um and of course you know a lot of us here are academics um so you know we find academic papers convincing um but you know they are in general kind of theoretical feasibility type things um so you know but this isn't right this has been put into practice there's many companies now that do this and you know there's been some very high profile uses of Bitcoin kind of um analysis in order to uh take down all sorts of sort of illicit operations by essentially doing the kind of age-old technique of you know tracking the money and um using that to identify the criminal

so um the way that a lot of this is achieved both in practice and in obvious papers that I showed is um via the use of what we call clustering heuristics so the idea of a clustering heuristic is especially in utxo based cryptocurrencies um you know an entity either an individual or a service like an exchange generates a large number of addresses or pseudonyms through their operation right so they they create new addresses all the time and so clustering heuristics allow us to essentially collapse all these different addresses that they generate and that they use into um a single sort of cluster that

represents uh the The Entity itself right so in exchange for example might use millions of different addresses but the idea is that we can put we can say with a lot of confidence that hey all of these million addresses actually seem to belong to the same entity and then we can look at the transaction flow in a more sort of semantically meaningful way right rather than tracking the money inside of each of their million individual addresses we can actually track them as an entity does that make sense okay so these this is again kind of the heart of all of this analysis so I'm going to cover in this talk really two of the major heuristics that are used uh

to do this so the first one is clustering by input addresses and just very simply stated if you are familiar with it for example because you saw me presented a month ago um then the idea is that all input addresses in a transaction belong to the same entity but just in a bit more detail in case you need the refresh um so let's imagine that Bob here is asking Alice for six coins and Alice doesn't have you know a balance of six in any of her utos with any of her addresses um but she can sort of put these three together and in that way she can pay uh Bob okay so again this is the heuristic it's

often called the multi-input heuristic or the coast Bend heuristic and it basically says that the same user controls all of these addresses um and of course you know I should mention that the impact of running this kind of heuristic you know goes far beyond a single transaction right this operates transitively across all transactions um and so we can it does really collapse things down quite a lot are there any questions about how the multi-input heuristic works great um okay so the multi remote input heuristic um is really considered very safe today and this is a little surprising maybe because actually this heuristic is known

to be completely invalidated by a privacy technique called a coin join in which basically multiple users get together agree on the details of a transaction and then sort of form a transaction in which all of their addresses or the inputs and all of you know the different recipients that they want um to get their money are are in the outputs right so this is a coin join is you know the easiest example um of a case where the same entity definitely does not control all the inputs in a transaction okay but despite this we generally you know in practice again believe this to be a pretty safe heuristic um and you know I I won't speculate too much on the reason why I think the idea is that you know exchanges and other

large entities are the ones where it uh it's really most effective to apply the multi input heuristic and those kinds of entities are not really using coin joints right they have no incentive to engage in coin joins they have actually incentives to not engage in coin joints I would say um and so in general you know for the ways that the multi-input heuristic is used um we're not the idea is you know we're not expecting to encounter too many coin joins in the entities or the Clusters that tend to be of the most interest okay but but it's still true that you know if you run the multi-input heuristic over every address in the blockchain there's going to be many false positives right because there there are many coin joints so there will

be many clusters that are incorrect they do not represent a common entity okay all right so the next heuristic um I also presented so it's hopefully also relatively familiar um and This concerns the idea of change addresses in Bitcoin so briefly um how are change addresses made you know what's the the role of a change address um so let's imagine that now uh Bob wants Alice to pay him 14 coins so again Alice doesn't have exactly 14 coins to send him in like a one-to-one transaction uh but she does have sort of more than 14 coins and so if we think of you know spending out of our bank account this seems very easy right we're

just like oh yeah she'll just like you know subtract uh 14 um send that to Bob and then she'll kind of have like one left in her account right and this is how this would work in an account-based cryptocurrency um but this isn't how this works in um in utxo based cryptocurrencies right and this is because the whole idea of a utxo is that you have to spend all the Bitcoins associated with it all at the same time um and so the idea is that what we do instead is we um generate a sort of new change address uh like so a fresh address that uh has never been used before um and then Alice is going to create a transaction with two in one input sorry

and two outputs uh one output is her change address um and the other output is Bob's address Bob is going to get his 14 and then she's going to send the change back to herself to her freshly generated address okay so this is you know this is how I've chosen to present this there's actually no inherent reason that this address has to be freshly generated and never used before it could be literally any other address that Alice controls um it could be the the exact same address that she used uh for the utxo to spend the money so um you know you see that all the time as well um but it's just it this is just kind of how it's done in the standard idiom so

this is how it started in you know Bitcoin D um and this is still you know a very common use of uh the change addresses so the idea is that you know Alice as a user when she's looking at kind of her account and it says you know here are the addresses that you control and she can like add addresses if she wants to you know Branch out and like transact with new people the idea is that as as a human again she'll never even see that address you know unless she goes and looks at the blockchain she'll never know that that address belongs to her um you know the the wallet software just won't show it to her basically so again this is not always how it goes but this is certainly the standard kind of idiom of use

okay any questions about about how change addresses work okay so then let me get to the heuristic uh the heuristic basically says that if we see a transaction with multiple outputs um then if we can identify the change address um then that also belongs to the input user so whatever entity we've labeled as the input user you know whatever cluster they belongs to we're essentially going to add this change address and fold it into that uh into that cluster and say it belongs to the same entity so you know the multi-input heuristic again is all about sort of collapsing

different addresses down into a larger entity and then looking at the kind of patterns of that entity and we can use the change here heuristic in the same way right we can use it just as a method for expanding these clusters and trying to make these clusters a bit more precise I guess right so if we don't take into account the change Behavior then these clusters contain a lot of like churn right the user just sending money back to themselves and it kind of looks external um and the idea is that you know the change heuristic uh captures all of that and sort of keeps it all within the cluster where it belongs but I'd actually like to convince you that this this heuristic the idea of identifying a change address goes really well beyond kind of clustering addresses

together um and in particular it allows us to essentially follow money as it moves around the Bitcoin Network right so the idea is that if in a transaction we can isolate which address is the change address then we can also say well who was the meaningful recipient in that transaction right and so we can follow this very common pattern um again there's no reason it has to be this way but this is extremely common in the Bitcoin Network and this is a pattern that we call peel chains so what does a peel chain kind of look like so the idea is that this sort of blue user here might have a sort of large amount of coins stored in a single utxo okay we can say like 100 or something like that and then let's say

this they're in exchange um and now this sort of red user comes along and they say hey um I'd really like to withdraw one Bitcoin from my account okay so the exchange says that's fine I've got 100 Bitcoins sitting in this this address sitting in this utxo so I'm going to send you year one and then I'm going to send the 99 and change back to myself and then um well we'll see what what happens next so the idea is that if in this transaction we can actually say with again a high degree of confidence you know this is the change address and that's the meaningful recipient then now what we can do is we can say okay well why don't we keep following what that

blue user is doing right because the next thing they're going to do is probably peel another sort of amount off of this large utxo right the chances you know that you want to spend like 99 Bitcoin in one go is small right and the idea is that especially in this kind of context you know users come along um you know they take off their little appeals and then you just kind of continue down the line so the idea is that by identifying change addresses we can actually confidently follow these peel chains for hundreds or thousands of hops and again these peel chains are really everywhere in in Bitcoin um essentially every transaction in in one way or another is part of one of these kind of peel chains

um and if you're curious by the way when we kind of get to the end when that you know large chunk of of Bitcoins becomes very small um what services often do is they just combine all of those together to form a giant Clump again and then just start another appeal chain um that's that's a very common pattern so it just didn't give you a way to change address from the meaningful recipient is it just can you just use the ordering of them often do they bounce that would be in like two slices yeah um yeah great question so yeah so the idea is um really the hypothesis kind of here is that by identifying these recipients we can actually potentially de-anonymize the user okay so let me sort of flip

this example you know before I said oh the blue user is like in exchange and the red users are all like um users of that exchange who want to you know get cash out into their own uh accounts okay now let's say that at the at the start of this PL chain um is what there was a massive Heist there was a massive hack and theft of Bitcoins and now the blue user is actually a thief and the sort of meaningful recipients are attempts to kind of not send all the stolen money to any one place in one go right which would be very detectable and very easy to follow all right so this is a really common technique again in Bitcoin and in money laundering in

general um and so the idea is that you know maybe these in individual red users represent you know different ways that they're trying to cash out right maybe some of it is local Bitcoins maybe some of it is you know unregulated exchanges uh but maybe you know one or two of these Hops uh one or two of these peels are actually regulated exchanges that law enforcement can then essentially go they can subpoena they can say I saw this deposit in this transaction and I need you to tell me who that account holder is right so this was kind of the the running hypothesis that we had um when we were first developing these kinds of heuristics does that all sort of make sense cool okay so uh to Tim's question yes

how do we actually identify this change address it sounds hard it is hard um and also I should say the consequences of getting it wrong are very significant right if we you know imagine we're trying to follow up heel chain hundreds or thousands of hops and we accidentally just sort of swap things um I can tell you from personal experience that this very quickly garbles everything you know you end up just like down a rabbit hole um and drawing some very incorrect conclusions um about what was actually going on so this is sort of uh the the heart of of uh the question here okay so how how can we do this well so one approach one idea is kind of what I

hinted at before with this standard idiom of use right so I basically said that you know nine times out of ten or whatever um that's not an actual statistic but you know very frequently um the change address is going to be used in this like very one-time kind of way okay so it will receive money and then it will spend money and that's it it'll never be used again right because again the user you know Alice using it she doesn't know it exists so she's certainly not going to give it out to anyone it's not going to receive money in any other way um and yeah and the wallet software you know by the way it's written is not going to reuse it either okay so it's just going to use it to collect change

once it's going to use it you know when Alice needs to kind of make up the balance in another like multi-input transaction later and that's it that's the end for the change address okay so that is um essentially kind of what we what we've tried um you know the the research Community we can essentially say okay here's our attempt at defining the change address we can say it's the only fresh output address where fresh means that it's never been used before all right so we look through the list of outputs in a transaction and we say have have any of these you know which of these have been used before or which of these haven't been used before rather is is a better question I guess if the answer is none then we don't know which

is the change address if the answer is multiple then we again say we don't know which is the change address um but if the answer is this is the only one then we feel safe in saying that this is the change address I should say that this is not exactly you know there are a lot of modifications you make here right the heuristic as I just described it is horribly unsafe um uh you would like collapse probably everything together at this point in bitcoin's uh Evolution um so yeah this on its own is extremely unsafe um you can make a lot of modifications and exceptions for you know certain services that do things in a certain way um but but this is kind of the gist of

it basically um is you know we're relying on on this property um okay so um I also just very briefly want to mention so you know once we have these heuristics you know now what we have these sort of entities you know or clusters that represent entities we can kind of see the transactions between them um but we still don't know who they are so there's just like this missing piece of the puzzle that I just kind of want to you know stick in somewhere and I picked here um which is this idea that you know we we actually want to know which entities these clusters represent and we can do this by actually manually tagging addresses ourselves um whether that's just engaging in our own transactions whether it's scraping tags that we find online

um you know whether it's it's just any sort of manual investigation um and although that sounds like it doesn't give you a lot of of information the idea is that by combining this with these clustering heuristics um we can actually you know tag these these entities right so the ideas you know these represent sort of three little transactions that we've done by hand potentially um but the idea is that if these addresses you know the pink ones that we sort of know now from our own observation from our own interactions if we know that they belong to a given entity you know an exchange let's say and we know that that uh address sits within this larger cluster that we

believe with very high confidence you know every address in that cluster belongs to the same user then we can actually essentially you know taint the whole cluster and say okay now this you know million address cluster belongs to that exchange that I transacted with because I saw that one address um that one time that I did my own transaction okay so this is um the kind of approach that um that again we were kind of doing um both myself and and other research groups back in like 2013 2014. um and you know it it's it's quite effective to be honest you know um especially the multi input heuristic um you know is really effective um and so you know in in this kind of um

paper that we published in 2013 we we kind of did this like follow the money analysis for a number of heists that we identified um you know we I did sort of other individual work talking to people who had their Bitcoins stolen and trying to attract the flow of that um and you know we again it felt effective at the time um you know we were able to trace over three million dollars worth of bitcoin directly backed to illicit activities um and then of course as I said you know this went well beyond academic research um to create you know companies that kind of do this um type of work yes exactly yeah maybe I should update that with

whatever that would be in in today's bitcoin price um okay so this this was kind of you know the story and it's you know felt very successful certainly for a long time but I I will admit at this point that this is a very brittle heuristic this change heuristic right so I said the multi-input heuristic you know yes it is invalidated by coin joins but it does feel very safe um the change heuristic I think never felt safe certainly not to me um you know in the work I kind of highlighted um I I can admit very freely now this was very manual work right so it would sort of run the change heuristic you know see it fail kind of go look at the

transaction myself in uh a block Explorer and like make a best guess kind of as to what the change address was um you know using some kind of internal heuristic that I couldn't identify um and so you know this this is sadly kind of how it went and so you know I think this heuristic has definitely not seen as much adoption in practice um or you know it wouldn't be recognizable um at least not to me you know the way the way it looks right it would have so many modifications so many qualifications and ultimately again a lot of the kind of tracking the money investigation style work that's done is I think largely still like fairly manual because uh you know we don't have a good heuristic for doing

this so of course with all that build up I'm going to say that this new work that we have um that's going to appear at ucx security so this is work with um my PhD students George capos and her and Yousef and also some collaborators in Austria Reiner Stutz Sophia Rowlett and Bernard hustlehofer and this is a real like significant departure from how we were identifying change addresses before so rather than rely on you know the value uh being received by you know each output address or that you know the freshness or anything like this we're going to actually say that for each multi-input cluster we're going to build up a series of features so things

we kind of expect from that cluster and then when we're trying to identify the change address we're going to say you know which in this list of output addresses is the one that we think matches the expected behavior of that input cluster and if the answer again is one and only one address then we will say we think that's the change address um and we'll label it as such okay so let me you know get into a little more about what these features look like and you know have a heuristic actually actually works okay so you know it's it's somewhat hard to believe uh you know if you've been following this space for a long time and you see how rapidly you know newer cryptocurrencies things like ethereum

are changing it's a little hard to believe that Bitcoin actually has changed enormously um you know since it was deployed and in particular in the past 10 years um so you know there are many new transaction features um uh or yeah there are many ways you can use transactions so I won't enumerate them um but feel free to ask if you're curious about what any of these are um not listed here also is um you know whether things are segwit enabled or not you wouldn't think that that would be like a differentiating feature but it actually is and I should also mention that there's some concurrent work from Princeton from Malta Moser and arvind narianen that came out at FC this year that actually uses uh way more features

than than we did um I think we picked four transaction features um they have like a whole big table of them and there's also many different address types right so again Bitcoin kind of started out with like three address types maybe and there's now like quite a quite a large uh number of them um so those are kind of just the ways in which Bitcoin has evolved essentially the different ways people are using it and the idea is that you know in in these features in these address types each kind of um wallet software for example is going to have its own kind of Trace right so you know one wallet software might produce a transaction kind of feature Vector uh

you know that looks very different from the ones produced by another piece of software um and you can also imagine that exchanges and other big entities that you know generate transactions programmatic programmatically are also going to leave their own kind of uh Footprints right that look very distinct from each other so those are the transaction features and the address features and then the last feature actually concerns not an individual transaction or address but actually the cluster as a whole so it's it looks so simple um and it is so simple the idea is that in some um you know some exchanges some entities the way that they do things is they always put the change address uh in the

same place in the list of outputs okay so we we can kind of um encode this as one of four values so either it's always the first in the list or it's always the last in the list or it's always either the first or the last so uh you know it goes where it feels or there's no discernible pattern in in the location the index of the change address uh you mean the the one oh yeah none oh I mean yeah none just means we don't we can't identify a pattern whether it means that they've

randomized it or not I don't know um but yeah I mean in theory you could imagine that one would be like fairly common right because a lot of transactions have only two outputs um but but actually I mean none we saw I don't remember the exact breakdown um but we certain we saw Zero and minus one you mean like well so I think I don't know if any of the wallet software will end up like by default usage would end up in zero or minus one um but you know a lot of the again a lot of the entities that transact very

frequently are using the wallet software in the way a user would right they're like crafting the raw transactions themselves and then just feeding it into the software to process to the network um so then that's kind of where you see more patterns like that okay any other questions about these features okay so um with these features in place we can kind of now Define our new change heuristic so the idea is that we for Alice we have now identified a cluster all right we've seen Alice reuse these addresses together and we can say with confidence because of the multi-input

heuristic that you know these five addresses all belong to Alice so now what we're ready to do is to define the features of this cluster according to what I just said so in particular we just we Define a set of transaction features so for every Transat so often I talk about clusters as consisting of addresses but obviously clusters also consist of transactions it's just all the transactions made by these addresses um or associated with these addresses so essentially what we do is we say for every transaction in the cluster you know figure out what it's uh what its features are and then we add that to the set of possible transaction features

for this cluster all right so you know if a cluster has four transactions and they all have different features then we'll end up with a set of size four if they all have the same features a set of size one same thing for the address types right so for every address in the cluster we record what its type is and we put feed that into a set and say these are all the possible address types that that we've seen for this cluster so far and then we have a singular again change strategy for the entire cluster does this make sense so step one run the multi-input clustering heuristic step two Define this sort of uh Associated data for that cluster

so now when we see a new transaction initiated from this cluster okay so for example we see Alice Payne Bob then what we do is we look at the input and we say okay let me go look up the features for that cluster and now we look at the two outputs and we say which of these outputs matches the features that I expect for that cluster right meaning uh yes sorry it's actually not clear at all what it means so first of all um we have the you know let's say the list is um the change address is first and the

Bob's address is second so if the change strategy for this cluster is defined as um zero meaning the change address is always first then we're not even going to look at Bob's address right we're going to say we're only interested in things that match what we know the cluster does and we know that the cluster always puts a change address first so the the first address is now our only candidate change address right we don't even consider the other ones because that would violate the change strategy whereas if the change strategy is none or in this case uh one meaning either first or last then now both of these would still kind of be in the running all right so that's kind of how the change strategy is used in considering just you know it either just essentially

throws away all but two of the outputs or it just leaves them all open then what we look at is the address types right so for each of these that's easy we can say what's the type of the address um is that address type in the set or not right and if it's not in the set then again we rule this out this can't be the change address and then finally we want to consider the transaction features okay so we're not going to look at this transaction right we already know that this transaction is is part of the cluster we're going to look actually at the next hop right so if I should say if we don't if let's imagine that one of these outputs hasn't um spent its contents yet

then we don't actually care if it's a danger dress or not to be honest right we're interested in like following peel chains and if there's no chain to follow then we don't care if if we if it's the change address there's there's nowhere to go at that point so we look at the next hop okay so imagine that that both of these addresses have now spent their contents then we look at the transaction in which they've spent their contents we look at the features of that transaction and we see if that transaction matches the features we expect from the cluster okay so again we're not interested in the features of of this transaction because we know this is part of the cluster already so we're just going to take you know imagine that this transaction had new features we would just add them to the set rather than

than doing anything with them is this clear okay and so again this is just a process of kind of like ruling things out right so the change strategy says okay which of the outputs are we even going to consider that they might possibly belong to the cluster or not we might rule out again a lot of them at that stage the address types again which is just sort of filtering are they in that set or not and then the transaction features just requires going one hop further and then again seeing is it in the set or not the features of this next transaction and the idea is that again if we have you know at this point we've crossed things off the list if there's one thing left on the list and only one then that's the change address so again it's about finding the unique output

that that satisfies all our kind of conditions does this make sense so like I mean kind of for everything everything for the media a candidate for the change address every aspect of it Nationals that you've seen before exactly if we're seeing new behavior um then we're not interested sir yes the initial cluster use the property from so um well what do you mean how do you bootstrap how do you form the first input yeah okay so this is this is the heuristic

and if you think about it um you know I don't have any slides about it or anything but it's worth just considering you know when would a false positive happen and the answer is that You Know Not only would the entity have to change their behavior completely from how we've seen them transact before but the entity that they were transacting with in this transaction in which they've decided to do something radically different The Entity that they're transacting with would have to behave exactly like them in that exact transaction in which money was changing house right that would be the only way in which we would get something wrong if the entity that they were transacting with was not behaving

like them then this would just be a dead end right we would just say oh you know they change their behavior we don't know anymore at the end so it would actually have to be like almost a complete swap in in Behavior right um and so we we think you know that this is low and later in the talk I'll show you how we we didn't just have to rely on our own thinking luckily um we've actually been able to validate this heuristic but before I get into this as you know as I described it as a change heuristic right as a way to increase the size of clusters and to track money around the network I should say that actually the way we conceived of this was was quite different um what we were really trying to do um was to validate the multi-input

heuristic in the first place right so something very like uncomfortable about this heuristic and a lot of heuristics uh in this space is that the multi input heuristic is really all or nothing right it really says um you know here's a million addresses and they all belong to the same entity and you know every any pair of these addresses are equally likely to belong to the same entity right we make no distinction between addresses and the Clusters it's either yes they're in the same cluster or no they're not yes they belong to the same entity or no we don't think they do um and that that's weird right like because a lot of the times we don't know right like again I said that multi input heuristic is very

transitive right and so you know two addresses that were used as input to the same transaction you know we might think okay we we could have like higher confidence about those belonging to the same user as maybe ones that you know this one was used with that one and that one and that one and that one and they're separated by like a watch a much wider kind of chain of like common usage across transactions so really you know this was the initial kind of provocation here this was the initial thing we were trying to achieve um and fortunately we can actually also all sort of hopefully convince you that this technique is actually a really nice way to to do this um and then of course conveniently it also functions

quite well as a change heuristic as I described it as a way to expand clusters as a way to track flows of money as they move around um but let me sort of talk about the validation first um before I do that I um you know it wouldn't have been possible I should say to do any of what I'm about to describe if we didn't have some really nice ground truth data um so what we did is we worked with channelysis which is one of these big uh blockchain analytic companies and chain analysis was very nice and they gave us 241 Bitcoin addresses and over 20 000 coin joints so what was special about these Bitcoin addresses that they gave us um these Bitcoin addresses actually

lived in what I called true positive clusters meaning to analysis had actually like hand verified with the entity that this cluster belonged to that these were all their addresses okay so there was there's no risk that you know this was a bad cluster or anything like that there's no risk that there's a coin join here or any other type of false positive and I should say by the way you know ethically we were very careful to not learn who these clusters belonged to um uh so yeah so that's the kind of true positives and then from the queen joins of course we could just run the multi-input heuristic ourself and generate false positive clusters right

um okay so um I won't give any of the details they're all in the paper though if you're interested but from this we were able to create a balanced data set of 60 true positive and 60 false positive clusters okay so yeah why is the number so much smaller well basically a lot of the true positive clusters were much bigger than the false positive clusters so we wanted the Clusters to be consistent in their size in the time frame in which they were operating and features like that so you know this was already a big part of our work was creating this this data set um and I should say by the way you know if you're thinking about this idea of oh you know like what I said about false positives right like oh this entity would have to almost kind of like

impersonate the input entity in order for us to generate a false positive um we can actually see that uh well this isn't convincing from what I've written here but I you know clusters were largely consistent in their behavior meaning actually the majority of these clusters the set of transaction features was of size is one and similarly the set of address types was of size one they only ever used one address type um um it was more true of the TP clusters but it was true of both and then also I should say the most clusters were also fairly distinct um you know I don't remember what the like Jacquard similarity score was or

anything like that but uh it's in the paper okay so now let's look at how we can kind of validate these multi-input clusters so the idea is that to validate a cluster we really want to stay within the cluster right we really only want to look at addresses that we already believe belong in the cluster so what we do is we essentially start at every transaction contained in the cluster and we initiate a kind of peel chain from that transaction right meaning we try to identify the change address of that transaction and then from the change address we try to look at it the next top and again kind of go as far as we can but crucially we added a sort of extra criteria to um to our identification of

change addresses which said we're only interested in ones that are already in the cluster okay because again we're not interested in expanding the cluster at this point we're just interested in staying within the cluster and seeing kind of how far can we follow a peel chain without leaving the cluster all right so this might again this might not seem like interesting on on the surface um but you know anyway I'll keep going with it so it allows us to Define this kind of uh value so the idea is that this this will partition the cluster into a set of Peel chains okay so if we can't follow any transaction within the cluster then the set of PL chains will be the same as the set of transactions right every transaction

will just immediately lead to a dead end okay so that's the kind of default state in some sense of this value is one right but the idea is that the more peel chains do stay within the cluster um the smaller this value is going to get right because the number of field chains will get smaller the denominator will stay the same does that make sense okay so again on its surface this is not obviously interesting or obviously useful um but if we run it then we do see a really significant difference uh at least you know pictorially in in between true positive uh and false positive

clusters so the the Bluer the kind of paler Bluer the value is the closer it is to zero and the sort of like more pink the value is um the closer it is to one Okay so we can definitely see again this is not definitive um you know it there there are blue values that are false positives and there are pink ones that are true positive this is not like a perfect separation but again the idea was really just to try to increase our confidence in some sense uh over whether something was a true or false positive cluster and also at a more individual level level whether two addresses active uh actually do belong to the same entity right so the idea is that you know

um at a kind of early stage of an investigation potentially this can give you a sort of boost of confidence if you see if you run this for your cluster and you see that the value is quite close to zero you know maybe it allows you to feel more confident that this is worth pursuing um whereas if it's sort of you know more pink then maybe maybe you have to reconsider it and again you know that's not definitive um but you know maybe maybe like it's you can have higher confidence in addresses that are actually part of the same peel chain right so now you say not only were these addresses sort of common across some large transitive set of transactions um you know and they belong in the same

cluster via the multi-input heuristic but also they actually seem to appear in the same peel chain um the idea is that maybe this gives you some extra confidence that yes these addresses really do belong to the same user um whereas ones that are in you know destroyed peel chains or something like that uh you you have lower confidence so again this isn't perfect by any stretch of the imagination this isn't uh you know an exact probability that two things belong to the same user um but our goal was to kind of be better than you know yes or no um and uh you know I think this seems sort of like one way to get there the smallest development everything in this clusters

yes which we did see you have okay so then your point is that there's not two completely orthodical stories about why this might be the same entity right one based on just difficulty and characteristics especially with your confidence that exactly if both of these heuristics say yes these addresses belong together then it's better than if just one of them says it of course it's still not definitive but yeah okay um and then finally I um want to talk about this as an actual expansion heuristic um so again kind of the way we can think of it as like following the money so this time we've removed the Restriction um about staying within the same cluster

now we just want to sort of follow it as far as it goes and we're going to consider two factors one is the expansion rate so how many new transactions do we bring into the cluster as a result of running this heuristic and the other is um the false Discovery rate right so of course we we would want to get something like you know so how well can we do this right so um again thanks to analysis we were able to identify any tags of the Hops that we were following um and if we encountered a tag that well to be honest if we encountered a tag then we essentially treated this as a false positive um right because if this was tagged as belonging to another entity you know

distinct from the the one that we already had associated with the multi-input user um then we would essentially say that that's a false positive right um and then but so the reason we couldn't um yeah so we can definitely say that something is a false positive um and then essentially what we did is we sort of said that unknown positives you know for for the sake here we're going to count as well no actually sorry that's all we said the idea is that we can't say what the true positives are right because we don't know um if something doesn't have a tag that doesn't mean we were right it just means we weren't like demonstrably wrong um okay so um first thing we did of course was not just evaluate our own

heuristic now with this very exciting ground truth data we were actually able to uh evaluate all these other heuristics in the literature um and this was the first time we were able to do this so um these kind of heuristics um from 2013 we can see are very bad in terms of their false Discovery rate uh yeah the false Discovery rate is very very high um and uh similarly there was another heuristic uh by goldfetter at all I should say that wasn't designed explicitly for this um but was a kind of refinement of these previous ones and this also achieves a very high false Discovery rate right so again this this really means that we should not have any confidence at all in the results of

these heuristics that it's very possible um that they will be wrong a large portion of the time um and then there's this other heuristic by Emmy love it all that uh was published in 2017 and we can kind of see the effect here so this um they're all I should say based on the same fundamental principle of like fresh you know let's identify the fresh address and then they just all sorts all have like various refinements that have been added to them so the Army loved one we can see is by far the most restrictive you know it requires the most sort of conditions to say that something is the change address so we can see that the false Discovery rate is a lot lower but we can see that this happens you know by sacrificing us

essentially the utility of the heuristic right so the expansion rate is also quite low compared to the other ones so it's very conservative which is good better for sort of false positives but also of course lots of false negatives so in contrast um our heuristic has an incredibly low false Discovery rate um and also um is is more expansive is more effective than these other ones um so yeah I I don't have a lot more to say about it actually than that so you know I I think certainly the way Bitcoin is yeah I should say I mean it wasn't possible to run our heuristic in 2013 all addresses

looked the same all transactions looked the same essentially this idea of separating on features wasn't possible um so you know I should say that our heuristic is really only possible thanks to the evolution of of Bitcoin um but I I think clearly given the evolution of Bitcoin that's happened you know I think this idea of identifying things but via this like idea that they're fresh um it just clearly like is is going to be way too problematic and way too brittle today um so you know at this heuristic in contrast seems like you could actually run it in a kind of automatic way rather than doing this kind of manual like following the chains yourself um that sort of impersonation thing

I think it's just that's wild Behavior so yeah I think for sure it's that I mean again the Clusters we had were very consistent and also very distinct um and yeah I think it's also I mean the truth is you know I said oh yeah change addresses like they're defining feature is you know that they get money in once and they spend it and it's gone but the truth is that's the defining feature of a lot of other things in Bitcoin and it always has been right so you know within exchange for example a lot of exchanges every time you want to deposit coins they'll give you a new deposit address like a one-time deposit address and so that's going to have the exact same property right it's going to take in your money

um then often what happens is it combines your deposit with the deposits of many other users into one of these large chunks of money that you know then initiates like a peel chain and so the idea is that if you get that wrong right then it's it's like a huge clustering error because that one-time deposit address that you might have mistakenly labeled as a change address might get used with like 50 other um addresses at the same time so yeah I think the idea is that you know this one-time approach kind of did well enough but Bitcoin is just being used so much more today and and the truth is again that there's lots of other things that have that like one-time behavior um

so yeah um okay so just to wrap up I should say of course our study has many limitations you know 60 true positive and 60 false positive clusters is not many um and yeah so there's certainly opportunities to to validate this in other ways but you know at least based on what we had available to us um this does seem really promising it seems quite effective in both validating multi-input clusters and expanding um expanding them by following the money in this way um I should say of course you know like all clustering heuristics thankfully there are countermeasures available you know uh the way I've described the heuristic hopefully makes it fairly obvious that you know if you just

randomize the features of every transaction you make then that's it you know you're not going to um like tracking your transactions will just lead to dead ends um and stuff like that um I should say there's of course stuff in the paper that I didn't talk about like some nice case studies that we looked at I'm trying to see you know where this heuristic kind of um could make connections that previous ones couldn't um and really I should say the point of all of this research is you know um just to make it very clear that Bitcoin is really not Anonymous um that no one should think it is somehow people still think it is and I would really like as forcefully as possible to make the point that it is not it's very very possible to track activity

um and with that I would like to very much thank alsus for working with us um and giving us this data and I'd like to thank uh thank ic3 for funding This research and I'd like to thank you for coming and listening and yeah happy to take any questions I also have the chat open in Zoom so if anyone on Zoom has questions happy to hear those too thank you [Applause] yeah um actually two questions did you uh were you able to run like you mentioned there was this paper by malty and urban this year were you able to run bears and Compare the numbers yeah yeah it really

came out like we submitted even though it's just appearing now it was like major revision we submitted this so long ago I don't even remember um so yeah we we didn't we we could um yeah and I should say George and Malta are both the channels now so maybe they have I don't know are you worried that the the ground truth data set from channels that doesn't necessarily representative it's like what the maybe they're able to I guess the set of things they can verify by hand might be biased something yeah I mean I wouldn't say I'm worried about it it's but it's

definitely a limitation right I mean you know as you said the entities that they can verify with are probably exchanges and other people that they work closely with rather than you know users for sure um and we wouldn't I mean we very expressively said that we would not want that kind of data um so yeah for sure but I I will say I mean you know exchanges are a key player in the ecosystem so even if all the true positive clusters belonged to exchanges um you know I would still feel that that was representative of what this kind of analysis gets used for anyway um yeah the other thing I will say is um we asked that the true positive clusters were not too

big because we don't have that much computing power right and running uh the features and and stuff is is expensive so um that's another for sure bias you know um that a lot of the big exchanges and stuff are have big clusters um so yeah it's a definite limitation but um it's basically the first time that we could get that kind of countries data so I'm not going to complain yep so you mentioned now so the the the changes to bitcoin is what sort of made because we're against serious as possible so I'm curious did it have anything to do with the specific features that were added to bitcoin over time which is just you could like literally anything that

got added to allow for like original set of patterns with kind of look at the similar results yeah the letter I don't think it has it has nothing to do with we're not using the features in any way or anything like that it's just you know the ideas that not truly as there's more like diversity of implementations in an ecosystem people are going to make different choices and that's kind of reflected in in these features so yeah I don't there's nothing inherent about these features that's another thing I I kind of like about this approach is if these features become irrelevant then we can look at transactions and see if there's new interesting features um and then use those instead of the ones we we used in this study you said that it's common for wallets to

combine multiple small accounts into one utx okay yeah did that help you at all like in identifying grouping uh well it certainly helps the multi-input characteristic you know the fact that is it very common that those type of transactions yeah so I mean the idea is that you know if you've like brought this PL chain into like dust right and you have very like what are you gonna do with that other than combine it and then use that like real amount of of Bitcoins again right like yeah but it's it it's confirmed that it confirms that all these field changes it's very useful oh I see um well yeah I guess implicitly we kind of would have used that because again at

the end when they're all combined that then combines them all into the same multi-input cluster yeah so yeah we would have used that implicitly go back well so actually in the paper we do talk about the thing about going backwards is that you can't rule out any of the input right like the change strategy allows you to in one Fell Swoop rule out a lot of the output addresses but when you're going backwards you can't rule out like the the set of addresses and and transactions in contention just grows and so it's a lot more computationally expensive so we actually didn't um we talk about it in the paper um but we didn't end up running it

because we didn't have the computational power to run it it's also less safe I would say the chances of having a false positive or yeah it feels slightly more likely that you would encounter a false positive going backwards than going forwards thanks sir great thanks