Bitcoin, Explained 62: Hash functions

Aaron van Wirdum Live from Utrecht, this is Bitcoin

Sjors Provoost Explained.

Aaron van Wirdum Welcome back, Sjors.

Sjors Provoost Thank you.

Aaron van Wirdum You were on holiday. That's why we were out for a couple of weeks. Where did you actually go?

Sjors Provoost I'm not going to say.

Aaron van Wirdum Is that your OPSEC strategy?

Sjors Provoost Exactly.

Aaron van Wirdum Or just ashamed of where you went?

Sjors Provoost Both.

Aaron van Wirdum Okay, well, Bitcoin Amsterdam is coming up just a couple of months from now. You know what that means, right, Sjors? A conference in Amsterdam. It means

Sjors Provoost It means having to go to Amsterdam.

Aaron van Wirdum It means 420 blaze it. That's why we're gonna talk about hash today. Do you get it?

Sjors Provoost Oh.

Aaron van Wirdum That's that's the first pun. The first pun of the new season. I'm gonna consider this a new season and we're strong out of the gate with with fresh new puns for our listeners

Sjors Provoost I did expect you were gonna make a a pun around that topic. yes.

Aaron van Wirdum We are going to talk about hashes, hash functions to be specific. This is a topic that has come up here and there. And it's obviously a topic that everyone knows something about. And you, our dear listener, might now think where you're talking about hashes, we already know what hashes are. But do you really? Do you really know what a hash is? I didn't. I thought I did. But I learned something in preparation for this show. So you might as well. Sjors, I'm going to start with the first basic question. I think most people have a general idea of what a hash is, but still, Sjors, what is a hash?

Sjors Provoost Well, it's basically a function that goes in one way. It garbles the input. So if you start with the word hello, then out comes some garbage. And if you start with the word hello too, out comes some different garbage.

Aaron van Wirdum Yeah, well, you say garbage, but what you really mean is a number.

Sjors Provoost yes.

Aaron van Wirdum Data.

Sjors Provoost yes.

Aaron van Wirdum Essentially, zeros and ones.

Sjors Provoost Yes but I mean everything is zeros and ones so that's why a number. yeah.

Aaron van Wirdum Is that the best way to put it? A number comes out a number goes in a number comes out, and any data you can convert any data a picture or a song or as long as it's digital you can convert it into a number and then you can You can hash that number and you get a different number, right?

Sjors Provoost Yeah, that's right.

Aaron van Wirdum Okay, now there are some important properties for a hash function to be a hash function. You can't just say multiply everything by two. If you do that, you get a different number, but that's not a hash function. A hash function needs to do something specific. So what does it need to do?

Sjors Provoost Yeah, it needs to make sure that if you know the hash, like you can't just change it basically or maybe a better way to say it is so if you have the word hello and you hash it it comes out a number and then you shouldn't just be able to say well I want to make hello too I'm just going to change the hash now, and then I know that it was hello too.

Aaron van Wirdum Right so what you're saying is…

Sjors Provoost So if in your example of multiplying by two let's say that the hash of the word hello is one and if the hash of the word hello2 is 2, well, it's a little bit too predictable.

Aaron van Wirdum Right.

Sjors Provoost I mean, that would be a weird example. Maybe a better example would be if the hash of the word hello, hello was 2. It would be very predictable because now if I can take the number 3 and I can guess, oh, then the original must be hello, hello, hello.

Aaron van Wirdum Yeah, so essentially... The outcome needs to be completely unpredictable. So if you hash an entire book and then you hash the exact same book, but you change one period into a comma, the hash needs to be completely different, right?

Sjors Provoost Yes, absolutely.

Aaron van Wirdum And there needs to be no way to figure out which hash came from which book.

Sjors Provoost Yeah, well, in particular, like...

Aaron van Wirdum Unless you have the book, I should add.

Sjors Provoost Yeah, I think one thing you want to prevent is the thing called collisions, right? So that means that if I take your book and now I change some comma in a very specific place that I would get the same hash, that's a problem. Because then I could show you two different books and it would have the same hash. And so now I've cheated because the whole point of the hash was to prove that, you know, I was actually referring to the book and not some other book.

Aaron van Wirdum Right. So each piece of data should result in a different hash.

Sjors Provoost Yes.

Aaron van Wirdum Right. Okay. So that ties into my next question. And I'm not sure if we completely answered this question already, but so let's see if we did or didn't. What would it make? So some hash functions have been broken in the past. So what does it mean if a hash function is broken?

Sjors Provoost Yeah, so then we can get into some numbers, I guess. So let's say the resulting hash is a number with like it's 64 bytes or 256 bits, right? 256 bits, that's the hash. And that means there are two to the power of 256 possibilities. Right?

Aaron van Wirdum Yeah, and bits are literally the zeros and ones that I mentioned earlier.

Sjors Provoost Right, so 256 zeros and ones, that's the hash itself. So that means that if you have some piece of text, say the word hello, and that results in this hash, now the question would be, can you find another word that results in the same hash? For example, the word hello too. And if the hash works really well, then you just have to guess. You would try, you know, 2 to the power of 256 different words or different sentences until you get the same hash as hello. And that should take a very long time. Now, the hash is very broken if it doesn't take a very long time. If it turns out that you can just try maybe 100 different things and then you find a duplicate hash or a collision.

Aaron van Wirdum Right. So as soon as any hash collision is found, which has happened with previous, or I'm not sure why, with older hash functions. So as soon as any collision is found, is at that point the hash function considered broken?

Sjors Provoost I don't know what the exact criteria is, but you can try and measure it. So if, for example, it should take 2 to the power of 256 attempts, but in practice, you can do it once in 100 times, then obviously it's broken. But if it takes 2 to the power of 255 attempts, that's still a huge number. So there might still be some practical limit. But probably in the case of this, if you're able to find a single collision, that means the odds are already too high because it should really never happen with that big of a number. It's such an astronomical number that it should take you longer than the age of the universe to try all these combinations. So if you find something in less than the age of the universe, that's a really bad sign.

Aaron van Wirdum And if you do find something, it was presumably in less time than the age of the universe.

Sjors Provoost Yes, because you're alive. And so in historical examples, there have been hash functions that were able to be broken earlier. See if I can find the list or you might have it. Yes. So for example, there was MD5, I think. And MD5 was supposed to be 128-bit of hash. So that's 2 to the power of 128 attempts. That is a very long time. Not as long as 256.

Aaron van Wirdum Or the age of the universe.

Sjors Provoost But still, that's still age of the universe longer than that. But 256 is even longer.

Aaron van Wirdum Right.

Sjors Provoost Yeah, yeah. Because 128 bits is the security of a 12-word mnemonic. So if you have 12 words written down, the 12-word seed, that is 128 bits.

Aaron van Wirdum Got it.

Sjors Provoost 24 one is 256 bits, right so it's it should be very very secure. However it turns out that somebody was able to find a collision with only two to the power 18 attempts.

Aaron van Wirdum Right I see.

Sjors Provoost That is roughly… Should not try to do that off my head, but I think it's less than a million.

Aaron van Wirdum Right. So in that case, the hash function is considered broken.

Sjors Provoost It's completely broken because if you can, you know, brute force a million different words on a computer, like a million different passwords to guess what the hash means, that's nothing. You can do that in a very short time.

Aaron van Wirdum Yeah. And you just use the word brute force. Is that the only way to break a hash function in this way, or in this is well… Or can you also…

Sjors Provoost Brute force should not help you at all, right because that should take you the age of the universe. No but it's usually combination with some trick right, whatever that trick is and then brute force.

Aaron van Wirdum Right yeah that was going to be my question indeed. So there's a more pointed way to try and break it. You're you're using some kind of strategy to break it then.

Sjors Provoost Yeah but you're still probably brute force looking but you have a better idea where to look.

Aaron van Wirdum Right, got it. Is this the only or at least the main failure mode or failure model of a hash function?

Sjors Provoost Yeah, that's when the hash function itself would be considered a failure, right? But there are ways that you can use hashes that make you more prone to failure. So for example there are websites that store passwords. Well they store they don't store the password, that's really bad, but there are websites that store the hash of a password.

Aaron van Wirdum Yeah right.

Sjors Provoost And now, let's say that that hash is not very good or even if it is very good actually, somebody could make something called a rainbow table. So somebody would say, well, what if the [unclear] password is hello? What if the password is hello too? And they calculate the hash for each of these passwords. And then if you find a leaked database with all these passwords, you can very quickly guess which password belongs to which hash because you have this lookup table.

Aaron van Wirdum Right. It's basically you're just entering passwords yourself, seeing what the hash is, and then remembering that. If someone pops up using that hash as a password, then you can link the two, right?

Sjors Provoost Yeah, and that's not a mistake in the hash function. That's just the way that you're using it. And the solution to that is called a salt, which means that every time you store a hash, before you do that, you add something to it, to the original text, like just the word salt or something, or one, two, three, four, and then you hash it. And then that means that these tables are of no use.

Aaron van Wirdum Right.

Sjors Provoost Which means the attacker will have to guess a password and then do this calculation. It just makes it more work for the attacker.

Aaron van Wirdum So this reminds me of something that I've been wondering about for a while. And somehow I think this is going to be, well, let's see. So I've always wondered about this and I've never thought about it for much longer than 10 seconds, but maybe you have the answer. So when I enter a password, like I'm creating a new account on a website and I'm entering my password there. And then the website tells me, no, no, that password is no good because you need to use a capital letter and you need to use the number and the special, whatever. If the website is only getting my hash, then how do they know I'm not using a capital letter or a number or any of that?

Sjors Provoost Well, if you're really lucky, then your browser is actually doing these checks. But usually, unfortunately, sadly, you are sending the actual password to the server. And the server is looking at that password, comparing it. Well, when there's a new password, it's just looking at the password. And then it tells you what's wrong with it.

Aaron van Wirdum So they're storing it in a hash ideally, but the first time you're creating your account, you're actually sending them your text password.

Sjors Provoost Yeah, and every time you log in.

Aaron van Wirdum That is sort of the easy answer to my question, and I was hoping that there was a more sophisticated solution. I was hoping they had a more sophisticated way of dealing with that, but basically you're just trusting them to not.

Sjors Provoost I'm sure there are theoretically better ways to do this, but I don't think they're used. At least they're usually not used.

Aaron van Wirdum Okay well this was a little bit of an off-topic question. Let's move on to the probably more most important question of the of this entire episode here it comes. So sure what actually… So we've now explained what a hash does, but how does a hash do it? How does a hash function actually do it? Like what's going on? What's the magic sauce?

Sjors Provoost yes. Well, it really does, to me, just looks like magic. So what happens is every piece of text that you put into a hash function, you can just represent as a series of zeros and ones. Basically bits. And then what happens is the hash function will take little chunks of it. So we'll cut it into chunks, say, of 64 bits. It will cut the whole text in 64-bit chunks. And then it will say, okay, for each chunk, I'm going to look at the first bit and I'm going to flip it around and move it to the third position. And then I'm going to take the second bit and I'm going to flip that around twice and move it to the first position. And I'm going to take the third bit and I'm going to... Not flip it around, but compare it to the first bit and say, I want the inverse of the two bits added up together or something like that. So you're basically just doing this random, well, not random, but specifically designed way of scrambling the original text. And you repeat that for every 64-bit chunk. And that results in this this hash.

Aaron van Wirdum Right so this was in this is what I mentioned at the start of the episode this was for me kind of probably the most surprising thing but…

Sjors Provoost It looks very much like sorcery or like you know whatever.

Aaron van Wirdum Well but the thing is it really isn't. Like it's really just a design that was designed by someone with the specific intent of just shoveling bits around in a specific way.

Sjors Provoost Yeah, but in terms of design, it's not like they have an absolute formula of how to make something random. It's just that if you do these operations, people have found that that is enough to make it really random.

Aaron van Wirdum Right. Yeah. In my mind, that was some sort of elegant math trick or something. But when I was looking into it more closely, it really seemed like more mechanical. It is a designed algorithm by someone that does something deterministically, but then the results should be random as far as we can hope.

Sjors Provoost Well, it's predictably random, right? It's pseudo-random, because for anything that goes in, you know exactly what's going to come out. So in that sense, it's not random, but it looks random if you plot it, for example. If you represent the output as a number, then on a chart, then the number might be 1, and then the number might be 256, and then the number might be 128, and that should look completely random. It should look like noise.

Aaron van Wirdum Right, so that's the way to test it. You basically chart out the results and... Just by looking at the chart, it should look random enough.

Sjors Provoost Exactly. I'm sure there's a more mathematical way to prove that.

Aaron van Wirdum I guess so, yeah. But that's how you prove it, right? Okay, and so there have been a number of hash functions. So which one does Bitcoin use?

Sjors Provoost Well, Bitcoin uses at least two or three. The most important one, I would say, is called SHA-256, which is part of the SHA-2 family.

Aaron van Wirdum Yeah, what does SHA stand for, Sjors?

Sjors Provoost If you had asked me that earlier, I would have told you.

Aaron van Wirdum Well, I can tell you because I didn't know either, but it just stands for secure hash algorithm.

Sjors Provoost Okay, that's impressive.

Aaron van Wirdum The little nuggets of knowledge you get from this podcast.

Sjors Provoost And that proves that it is secure.

Aaron van Wirdum There you go.

Sjors Provoost Well, we'll get to that there's such a thing as a non-secure hash, which is not always a bad thing. But yeah, the SHA-256 one is important. It basically means that whatever you throw into it, you'll get back 256 bits of data. And that happens to be this, well, the size of a transaction identifier, but also the size of a block hash because a block hash is the SHA-256 or actually the double SHA-256. So you just do it twice of a block, of the contents of a block.

Aaron van Wirdum Okay before we get because that will be the next and last part of the episode I guess is how hashes are used in Bitcoin so we'll get there in one minute. Okay but very briefly before we get there can we… So there have been several hash functions since so when was the first hash function introduced invented?

Sjors Provoost As far as I know in the 1970s but I haven't done super deep research, but it's not that old. So the I think the general idea was known or suspected that there are mathematical operations which this is that will take some input and will produce predictably garbage output and that you cannot go back from the output to the input so it's a one-way function.

Aaron van Wirdum Hang on you just use the term one-way function. So one-way function is an umbrella term for mathematical tricks, functions that are easy to calculate in one way and harder in the opposite direction.

Sjors Provoost I would say impossible in the other direction. So this is distinct from the elliptic curve cryptography where it's very hard to go one way. So it's very easy to go from a public key to a... Sorry, it's very easy to go from a private key to a public key. It's very hard to go from a public key to a private key, but mathematically it's possible.

Aaron van Wirdum Wait, so wouldn't you...

Sjors Provoost But a hash, it is not possible to go back.

Aaron van Wirdum Right, but this is just how we apply terms. Maybe this is not the most interesting thing, but wouldn't you consider both one-way functions? Like wouldn't one-way function be the umbrella term for both of these things?

Sjors Provoost It could be. I don't know if mathematicians look at it that way, so you'd have to ask them. I mean, they are different in the sense that one of them you can, in theory, go back from a mathematical point of view. It just goes both ways. And these hash functions, really, they don't go back.

Aaron van Wirdum Yeah at least yeah okay got it. So a but anyway so a one-way function is an umbrella term at least that's how you use it for mathematical functions that can only go one way and then hash is a good example of that.

Sjors Provoost Yeah and a very useful example of that, right because a simple one-way function could be take the take the input and then output zero always that's that's one way.

Aaron van Wirdum Sure right.

Sjors Provoost Not useful yeah.

Aaron van Wirdum Okay, yeah. As far as I know, one-way functions have been sort of considered and discussed within the circles of cryptographers since the early 70s. It's also what inspired Diffie and Hellman to come up with public key cryptography. And then the first hash functions were like the late 70s. And that evolved from, I think the first one, was it called MDA? Was that, am I saying it right? MDA, yeah. I think that's, that's what I had in mind. Possibly the first one or the oldest one.

Sjors Provoost It could be much older I think because that's the 1990s and I think there were some ones in the 1970s too.

Aaron van Wirdum But okay possibly but then… So where I'm getting at really is so where does Bitcoin's hashing algorithm come from? Who designed it? How did it develop over the years, because it started with MDA I think somehow and then it evolved into SHA.

Sjors Provoost Yeah, I mean, it may have started, like I said, with something even older. But generally what happens is somebody designs this hash function in the way we just described. And then it turns out there's a collision or it's too easy to find collisions. And so somebody tweaks, usually just tweaks it a little bit, like adds one little operation that flips another bit. You know, it takes the left bit and moves it to the right. Just a slight change and then hope, praise that it works better. That seems to be, I'm sure I'm not doing it justice here, but generally they're constantly based on each other. So the other one that's in Bitcoin is...

Aaron van Wirdum I think MDA was designed or at least based on the design by Ronald Rivest, which is also the R in RSA. One of the three designers of the RSA algorithm. And then that design inspired SHA. And wasn't SHA... Designed by the NSA? Didn't they have a hand in the design?

Sjors Provoost They always have a hand in all these things. I don't know those specific details who was involved with what. What I do know is that...

Aaron van Wirdum No, it is. Because while we're discussing this, I have my phone in my hand and I'm scrolling through Wikipedia. I did this before the show, but I'm just making sure. Yeah, no, it was designed by the NSA.

Sjors Provoost Okay.

Aaron van Wirdum Is this something we should be worried about?

Sjors Provoost This was the pre-Snowden NSA, right?

Aaron van Wirdum I mean, it was the NSA that was going to war on encryption in the 90s.

Sjors Provoost Well, you wouldn't go to war over something if you thought it didn't work. But that wasn't about hash functions, I think. That was mostly about public key encryption.

Aaron van Wirdum Yeah, it was.

Sjors Provoost But what I was trying to say is that the Europeans didn't trust the NSA, and so they came up with this RIPEMD, or I don't know how you would pronounce it, but it is basically a variation of SHA-2 or SHA, where they just... If you read the original paper, you can see, oh, yeah, we changed a few bit flips here and there, but we didn't want to deviate too much from the original algorithm because we know it works. But one of the problems is, how do you pick these little bits and things and operations? It looks very arbitrary. And that means that if you don't trust the person who made it, you might be worried that they build in some sort of sneaky backdoor, some vulnerability that they know, but you don't know. And then one way to defend against that is, Well, there's two things. One is that the NSA would say, well, this is how we, you know, how we designed it. And that's all arbitrary. But here's like a series of numbers of like one plus five plus 17 plus like 15 different, like a very elegant looking series of numbers and say, well, if you just add this to it and then it still works. And that kind of proves like, well, these numbers are so elegant that they probably were chosen randomly or something. That's one way. And the other thing is you just change it— that they were… Or that the end result could not have been tampered with. Because you're saying you're adding so much stuff to it that is very hard, that makes it more difficult to design a malicious system. But it's still a bit hand-wavy. And the other thing you would do is what the Europeans did, I guess. They just changed it a bit. Not too much, but a little bit, so that any backdoor that might have been in there would be broken.

Aaron van Wirdum Right. Okay. Let's move on to... what this podcast is or at least promises to be about in in the title… How does hashes… A hash is really maybe the core fundamental building block for Bitcoin, wouldn't you say?

Sjors Provoost Well, it's certainly quite useful.

Aaron van Wirdum It's used here and there. So where are hashes used? How do hashes help Bitcoin?

Sjors Provoost Well, for one thing, every block, if you take the entire contents of the block, that's hashed. And, you know, descriptively call it the block hash. And it turns out that this hash of the block, well, first of all, the block itself consists of transactions. And so every transaction also has a hash. So that's two use cases.

Aaron van Wirdum Which is its transaction ID.

Sjors Provoost Yeah. Now blocks link to each other. So one block links to the previous block. And the way it links to that block is using the hash of that block. Because the hash itself of a block is not in the blockchain. The block is in the blockchain. And then your computer just reads the block and then figures out, okay, this is the hash. And so the next block will mention that hash, and that's how you know that the next block actually builds on top of the first one. This, again, is why you really don't want collisions, right? Because if it was possible to create another block with very different transactions in it with the same hash, you would have a problem.

Aaron van Wirdum Right. What would be the problem exactly?

Sjors Provoost Well, let's say the first block creates 25 Bitcoin and sends it to you. And everybody accepts that block and builds on top of it. And that means you will have that Bitcoin forever, essentially, until you decide to move it. But now I come in and I create a new block where that 25 Bitcoin actually goes to me. I find a way to produce the same hash of the block, which is impossible. But if I were able to produce the same hash, then I could send everybody else my block and they would look at the hash and say, okay, that's definitely a valid hash of that second block in the blockchain. So all the blocks are still connected. So that means that existing users wouldn't be tricked in this case, right? Because they would already have the block and they have no reason to replace it. But any new person downloading the blockchain would be confused because they would just get the fake block. But it's not fake in any sense that the Bitcoin software cares about because it would have the same hash. So there would be two different blocks with the same hash with very different events. And that would be a complete disaster.

Aaron van Wirdum Right. So hashes are used to link blocks together into a blockchain. And then the other thing about a block hash is that it also... determines whether the block itself is even valid in the first place.

Sjors Provoost Well, that's the proof of work part.

Aaron van Wirdum Right.

Sjors Provoost So what happens is that this hash is just 256 bits. And so what you can do, and that's what proof of work essentially does, is it says the first several bits need to be zero, or roughly, like the whole hash needs to be lower than a certain number, but it doesn't really matter. You could see it as, okay, so we're going to require that the first 10 bits of the block are zero. And then you can, because the only way to figure out what a hash is is brute force, the only way to get 10 zeros is to just try two to the power of 10 different things. And so the thing you would change in the block, you'd have to change something in the block to get a different hash. And so one of the things you would change is the nonce in the header of the block.

Aaron van Wirdum Which is just a random number.

Sjors Provoost Yeah, exactly. That's just a random number.

Aaron van Wirdum Add a random number to a block and then you get a different hash and then you check if the hash is valid. If not, you try again with a new random number.

Sjors Provoost Yeah, exactly. And the one thing that's in the block is the timestamp. So every second that timestamp changes as well. So there's a couple of things there and there's some trouble around it that we don't have to go into. But that's basically how the proof of work works. So it's using this fact that the hashes are random, which means you cannot... There's no way to say I'm just going to put 10 zeros in front of this at the start of this hash and then figure out the rest of the hash later. You can't do that.

Aaron van Wirdum Right. Okay. So that's blocks, transactions. One detail about transactions that's maybe kind of interesting to mention before we move on is that the hash of a transaction doesn't include the entire transaction, right? Because it doesn't include the signature, most notably.

Sjors Provoost Not in SegWit, yeah.

Aaron van Wirdum Because the signature needs to sign.

Sjors Provoost Well, because we want to be compatible with old nodes. So as far as all the nodes before SegWit is concerned, everything in the transaction is hashed. But as far as SegWit is...

Aaron van Wirdum No, no, no. You can't... The signature was not hashed because then you can't sign the transaction.

Sjors Provoost That's different. So the signature... So there's two hashes involved here. One is what I was describing is to refer to another transaction. That's using the hash and that covers the entire transaction. Well, minus the SegWit stuff at the moment.

Aaron van Wirdum Okay, yeah.

Sjors Provoost And then the transaction itself has a signature, but the signature, of course, cannot refer to the signature itself. So in order to make a signature, you don't take the hash of the transaction. You take certain chunks of the transaction and leave the rest. You set it to zero, and then you sign that hash.

Aaron van Wirdum Right. So you take chunks out of the transaction, you hash that, and you sign that.

Sjors Provoost Yes.

Aaron van Wirdum And now the whole package is hashed again, which is referenced by other transactions. Am I saying that right now?

Sjors Provoost Yeah. So other transactions don't refer to the SegWit part of a transaction.

Aaron van Wirdum Right, right, right.

Sjors Provoost But the way that's solved is because in the Coinbase of every block, there is a hash that does refer to all these things.

Aaron van Wirdum Okay. So hash is actually used twice, even in a single transaction.

Sjors Provoost Yeah, in multiple ways. Yeah, exactly.

Aaron van Wirdum In multiple ways, yeah. Okay, so that's blocks, transactions, proof of work. I think most people knew that or at least kind of knew that. But there's more ways in which hashes are used. So it's used now in Taproot?

Sjors Provoost Well, maybe easier to say, well, yeah, in Taproot, that's right. If you have this tree with multiple conditions, multiple ways that you can spend the script, that tree uses hashes. And like go into a Merkle tree. We've described that in a different episode.

Aaron van Wirdum Yeah, let's not get into the whole Merkle tree.

Sjors Provoost But that's where you have hashes. Again, SHA-256. Then you have addresses. Originally, anyway, addresses you would start from a public key and then you would take the SHA-256 hash or double SHA-256 hash of the public key. And then you would take this European RIPEMD hash of that hash and that would be your address.

Aaron van Wirdum Oh that that in that part of Bitcoin or at least… Yeah that's where they used we used Bitcoin used European…

Sjors Provoost Both and that may have been some like ah well I don't trust either thing by Satoshi, I haven't read the history of why he did…

Aaron van Wirdum Oh actually Satoshi introduced that as far as I know.

Sjors Provoost Yes this address format has been in there from from the beginning But with Taproot, there's no longer a hash involved in the address.

Aaron van Wirdum Okay. I see here in the notes that is, are hashes used in the random number generation part of?

Sjors Provoost In general.

Aaron van Wirdum I guess that would be creating private keys.

Sjors Provoost Yeah. So in general, when you create the seed, the randomness that uses a random number generator. And mostly that's done by your computer itself though there is also some code in Bitcoin that adds some extra randomness and generally random number generators use hash functions in all sorts of weird ways. Might be a little bit out of scope, but the idea is like because the computer doesn't have a way to actually throw dice so it needs to get randomness somehow, and what it does tends to do is like it'll look at what time it is, it'll look what's on its hard drive, which would be the result of many months of random things happening to it. It might maybe look at the temperature sensor of the CPU or things like that and then hash all those things and hash those things again. And that's where the random numbers come from, more or less.

Aaron van Wirdum Right. So you mentioned that something that your computer does and then the Bitcoin software does it again?

Sjors Provoost Does a little bit more. Yeah, the idea is if you have some random data from one source, you can mix it with random data from the other source. And as long as one of those two sources is really random, you're fine. So it just makes it better. If you have bad random data and you mix it with good random data, the result is good random data.

Aaron van Wirdum Right. Anything else?

Sjors Provoost Well, yeah. The other thing is if you have a seed, so you start with the 12 word mnemonic in order to go from that to individual keys that are derived from your wallet, you know, unique addresses that uses hashes too.

Aaron van Wirdum How does it use hashes?

Sjors Provoost Well, it, it derives like the next key from it. And I think the derivation involves a bunch of hashes inside of it to go from the private key to the next private key. It's not just plus one. It's like plus the hash of something, plus the hash of something else, right.

Aaron van Wirdum So each new private key is basically a hash of a previous private key.

Sjors Provoost Higher up in the tree, yeah.

Aaron van Wirdum Right, right.

Sjors Provoost And another place where we use it a little bit more fun is the address bucketing system. We talked about Eclipse attacks many episodes ago.

Aaron van Wirdum Yeah.

Sjors Provoost And one of the things we described is that when a Bitcoin node learns about other Bitcoin nodes, it has to store all these IP addresses of the other nodes. And it doesn't store those in one giant list. It divides those over a bunch of buckets. And the way to decide which IP address that you've gossiped around, which IP address goes in which bucket also involves a hash function. So you take a hash of the IP address and then you say, okay, if the hash is 1, it goes in bucket 1. If the hash is 2, it goes in bucket 2, etc.

Aaron van Wirdum Right, so it's basically a way to just get a random number in that sense.

Sjors Provoost And in this case, the security of the random number is not that important. So you don't need the secure hash algorithm, SHA. You can use a simpler hash function that is faster, basically, because that's the trade-off. You can do hashes faster, but then you're not going to get them perfectly random, but that's okay for this purpose.

Aaron van Wirdum So which one does it use?

Sjors Provoost I think this one's called SipHash. I don't know what it stands for.

Aaron van Wirdum Is it designed for Bitcoin?

Sjors Provoost No, no, it's older.

Aaron van Wirdum Okay. This doesn't refer to sipa?

Sjors Provoost No.

Aaron van Wirdum Okay, just making sure. Okay, so we've mentioned hashes are used in blocks, transactions, proof of work, which is also part of blocks, but either way. Addresses, Merkle trees, the random number generation, and...

Sjors Provoost Key derivation. It's used inside various cryptographic operations. So when you make a signature, you're making a hash before you sign it.

Aaron van Wirdum Plenty of hash in Bitcoin.

Sjors Provoost Yep, it's everywhere. Okay, I think that's all, right?

Aaron van Wirdum I think so.

Sjors Provoost Thank you for listening to Bitcoin

Aaron van Wirdum Explained.