Welcome to the first lecture in our series on Bitcoin and cryptocurrencies. I want to start by introducing the four lecturers who are going to be speaking in the series. The first lecture is Joseph Bono. He's a postdoctoral researcher in computer science at Princeton University. The second lecture is me, Ed Fulton. I'm a professor at Princeton in computer science and in the Woodrow Wilson School. The third lecture is Arvind Narayanan. He's a computer science professor at Princeton and fourth, our special guest lecturer, is Andrew Miller. He's a PhD student in computer science at the University of Maryland. There will be 11 lectures in total. In this lecture number one, we're going to do two things. First, we'll introduce some cryptographic primitives that turn out to be necessary for talking about cryptocurrencies. In particular, we'll talk about cryptographic hashes and digital signatures, and we'll talk about some of the ways in which those are used to build cryptocurrencies. Then at the end of the lecture, we'll start talking about cryptocurrencies, and I'll give some examples of simple cryptocurrencies that illustrate some of the design challenges that we need to deal with. I want to apologize for covering the cryptographic material at the beginning. Unfortunately, we have to eat some of our vegetables a little bit in order to lay groundwork for the cryptocurrency stuff. So if you came for the cryptocurrency stuff, let me assure you, first of all, that we will get to it in this lecture and that having laid the groundwork in this lecture, there's going to be a lot more specifically cryptocurrency-focused material in later lectures. All right, so let's get to it. In segment 1.1, we're going to talk about cryptographic hash functions. We'll talk about what they are and what their properties are, and then later we'll move on and talk about what their applications are. So a cryptographic hash function is a mathematical function, and it has three attributes that we need to start with. First of all, a hash function can take any string as input, absolutely any string of any size. It produces a fixed-size output. We'll use 256 bits in this series of lectures, because that's what Bitcoin does, and it has to be efficiently computable, meaning given a string, in a reasonable length of time you can figure out what the output is. So that's a hash function, but we're going to need hash functions that are cryptographically secure. The cryptographic properties of hash functions are a complicated topic in general, but we're going to focus here on three particular properties, and I'll explain in a minute what those are. In particular, that the function is collision-free, that it has a hiding property, and that it's puzzle-friendly. And for each of these, I'll talk about what the property is, what it means, and then I'll talk about why it's useful to have a function that has that property. So first, collision-free. So the first property that we need from a cryptographic hash function is that it's collision-free. And what that means is that it's impossible, nobody can find values x and y, such that x and y are different, and yet the hash of x is equal to the hash of y. And so if we look at the operation of the function as depicted by one of these red arrows, here's x and h of x, and here's y and h of y, then nobody can find a situation like this, that you have an x and y that are separate, and yet when you hash them, they hash to the same value. Now one thing to notice is that I said nobody can find. I didn't say that there is no collision, because if you think about it, there has to be a collision. Collisions do exist, and to understand why that is, we can use this diagram. Over here on the left, I'm depicting all of the possible inputs to this function, which can be a string of any size, and over here I have all of the possible outputs, which has to be a string of 256 bits in size. So the right-hand side here, the outputs, there are only 2 to the 256 possibilities. Over here there are more possibilities. And so if you think that every point over here on the left is going to be mapped by an arrow to some point on the right, you can see that as you go from all the points over here on the left into the right, it has to get crowded, and in fact that there have to be multiple values over here on the left that map to the same output over here. In fact, in general, there will be a very large number of possible inputs that map to any particular output. So collisions do exist. I said before, nobody can find a collision, and that's the key question. We know collisions exist. The question is, are there any collisions that are findable by regular people using regular computers? Okay, now to make things even worse, I said that it has to be impossible to find a collision. Let me tell you how to find a collision, because there's a method that's guaranteed to work. And the method works like this. That we're going to pick 2 to the 130 randomly chosen inputs over on the left cloud of that previous diagram. And if we pick those 2 to the 130 randomly chosen inputs, it turns out there's a 99.8% chance that at least two of them are going to collide. And so this is a very simple method for finding a collision. It works no matter what the hash function is, but of course the problem is that this takes a very very long time to do. You have to compute the hash function 2 to the 130 times, and and that's of course an astronomical number. This method works no matter which hash function we're using. There's still a 99.8% probability that this works, and if it doesn't work just try it again, and it'll probably work the next time. But this doesn't really matter, and the reason it doesn't really matter is that this procedure takes 2 to the 130 steps in order to get to that high probability. So we can say something like this. We can say that if every computer ever made by humanity was computing since the beginning of the entire universe up to now, the odds that they would have found a collision is still infinitesimally small. So small that it's way less than the odds that the Earth will be destroyed by a giant meteor in the next two seconds, which didn't happen. Okay, so we know how to find a collision, but this method takes too long to matter. The question is, is there some other method that could be used on a particular hash function in order to find a collision? And that's the question that is harder to answer. Is there a faster way to find collisions? Well, for some possible values of hash functions, of course there are. For example, if our hash function were to simply take the input, modulo 2 to the 256, that is it just selected the last 256 bits of the input, then we would know an easy way to find a collision. One collision would be the values 3 and 3 plus 2 to the 256. So for some possible values of the hash function, it's very easy to find a collision. For others we don't know. Now one thing I need to note is that there's no hash function in existence, which has been proven to be collision free. There are just some that people have tried really, really hard to find collisions and haven't succeeded. And so we choose to believe that those are collision free. Okay. Now, what good does collision freedom do us? If we can assume that we have a hash function that is collision free, then we can use that hash function as a message digest. And what I mean by that is the following, that if we know that x and y have the same hash, then it's safe to assume that x and y are different. Because if someone knew an x and y that were different that had the same hash, of course that would be a collision. Since there's not a collision that we know of, then knowing the hashes are the same, we can assume that the values are the same. And this lets us use the hash as a kind of message digest. Suppose, for example, that we had a file, a really big file, and we wanted to be able to recognize later whether another file was the same as the file we saw the first time. Right? So one way to do that would be to save the whole big file, and then when we saw another file later, just compare them. But because we have hashes that we believe are collision free, it's more efficient to just remember the hash of the original file. Then if someone shows us a new file and claims that it's the same, we can compute the hash of that new file and compare the hashes. If the hashes are the same, then we conclude that the files must have been the same. And that gives us a very efficient way to remember things we've seen before and recognize them again. And of course, this is useful because the hash is small. It's only 256 bits, while the original file might be really big. So hash is useful as a message digest, and we'll see later on in this lecture and in subsequent lectures why it's useful to use hashes as a message digest. So the second property that we want from our hash function is that it's hiding. And the property that we want is something like this, that if we're given the output of the hash function, that there's no feasible way to figure out what the input X was. The problem is that this property doesn't exactly hold. And to understand why that's the case, let's look at this example. So here, what we're going to do is an experiment where we flip a coin, and if the result of the coin flip was heads, we're going to return the hash of the string heads, and if the result was tails, we're going to return the hash of the string tails. And now we're going to ask someone who didn't see the coin flip but only saw this hash output to figure out what the string was that was hashed. That, of course, is going to be easy. It's easy in this scenario to find what the input string was. It's easy to find X. You simply compute the hash of the string heads and the hash of the string tails, and you see which one you got. And so in just a couple of steps, you can figure out what X was. So the reason this example failed, that is the reason why an adversary was able to guess what the string was, was that there were only a couple of possible values of X. And so if we're going to have a hiding property like this, it needs to be the case that there's no value of X, which is particularly likely. That is, all the X has to be chosen from a set that's in some sense very spread out, so that this method for the adversary of just trying all the possible values of X, or just trying a few values of X that are especially likely, is not going to work. So the hiding property that we are going to need to set up is a little bit more complicated. And the way we're going to fix this problem with the common value X, like heads and tails, is we're going to take the X, and we're going to put next to it, we're going to concatenate with it a value R, which is chosen from a distribution that's really spread out. And so this H of R concatenated with X, that means take all the bits of R and put after them all the bits of X. And so what we're going to say is given the hash of R together with X, that it's infeasible to find X, and that this will be true in the formally stated property, that if R is a random value chosen from a distribution that has high min entropy, then given the hash of R concatenated with X, it's infeasible to find X. And what does high min entropy mean? Well, it captures this intuitive idea that R is chosen from a distribution that's really spread out. And what that means specifically is that there's no particular value that R could have had that would occur with more than a negligible probability. So for example, if R is chosen uniformly from among all of the strings that are 256 bits long, then any particular string was chosen with probability 1 in 2 to the 256, which is truly a negligible value. So as long as R was chosen that way, then the hash of R concatenated with X is going to hide X. And that's the hiding property that the hash function will be deemed to have. Okay, now let's look at an application of that hiding property. And in particular, what we want to do is something called a commitment. And this is kind of the digital analogy of taking a value, a number, and sealing it in an envelope and putting that envelope out on the table where everyone can see it. Now when you do that, you've committed to what's in the envelope, but you haven't opened it. It's secret from everyone else.  So commit to a value and reveal it later. We want to do that in a digital sense. So to be more specific about what is the API that we're going to provide here, the commitment API looks like this, that there are two things you can do. First, you can commit to a message and that's going to return two values, a commitment and a key. Think of the commitment as the envelope that you're going to put on the table and the key as a secret key for unlocking the envelope. Then later you allow someone else to verify, given a commitment and given a key which you've told them in the meantime and the message, they can verify that that commitment, key and message really do go together and this will return true or false. Okay, now to seal MSG in an envelope, what we do is we commit to the message and that returns a commitment and a key and then we publish the commitment. That's putting the envelope on the table. Now later to open the envelope, what we're going to do is publish the key and the message that we committed to and then anybody can use this verify call with the commitment that we published previously, the key and message that we just announced to check the validity of our opening the envelope. Okay, and the property of course we want from this is that it behaves like sealing an envelope and in particular the two security properties are these. First, give and calm the commitment, the envelope on the table that someone just looking at the envelope can't figure out what the message is. The second property is that it's binding that when you commit to what's in the envelope, you can't change your mind later. That is, it's infeasible to find two different messages such that you can commit to one message and then later claim that you committed to another and the whole thing will verify. Okay, so how do we know that these two properties hold? Well, first we need to talk about how we're going to actually implement commitments and the way we're going to implement commitments is like this, that in order to commit to a value message, we're going to generate a random 256-bit value and call it the key and then we're going to as the commitment return the hash of the key concatenated together with the message and as the key value we're going to return h of this key and then later to verify someone is going to compute this same hash of the key they were given concatenated with the message and they're going to check whether that's equal to the commitment that they saw. Okay, so this is a way of using hash functions both in the commitment and in the verification. So now the security properties, if we go down to the security properties that were at the bottom of the previous slide and we just plug in the definitions of how we're going to implement this here, that is this used to say com, given com infeasible to find message, we just plug in what com is, com is the hash of key concatenated with message and similarly down here this is what happens when we take what was written there before and plug in the definition of verify in com. Okay, so now what these properties become, the first one is given h of key concatenated with message it's infeasible to find message. Well it turns out that that's exactly the hiding property that we talked about before. Key was chosen as a random 256-bit value and therefore the hiding property says that if we take the message and we put before it something that was chosen from a very spread out distribution like I said a random 256-bit value then it's infeasible to find the message so this is exactly the hiding property and this one down here turns out to be exactly the collision free property so that if someone can find two messages which have the same hash like this, well then they have an input value here and an input value there that are different and yet those have the same hash. And so because of the two security properties we've talked about for hashes so far, this commitment scheme will work in the sense that it will have the necessary security properties. Okay, so that's the second security property of hashes that they're hiding and the application of that is commitments. The third security property we're going to need is that they're puzzle friendly and this is again a little bit more complicated but let me just go through it a bit by bit that for any possible output value y that you might want from the hash function we're going to use y as an output value of the hash later that if k is chosen from a distribution that has high min entropy that is k is chosen randomly from some set that's super spread out then there's no way to find an x such that the hash of k and x is equal to y. So what this means is basically that if someone wants to target the hash function if they want it to come out to some particular output value y that if there's part of the input that is chosen in a suitably randomized way that it's very difficult to find another value that hits exactly that target. So the application we're going to use of this is we're going to build a search puzzle and what that means is we're going to build a mathematical problem which requires searching a very large space in order to find the solution and where there's no shortcuts a way to find a good solution other than searching that large space. That's a search puzzle. To be more specific the idea is that if we're given a puzzle ID which is chosen from some high min entropy distribution that is some very spread out probability distribution and we're given a target set y which someone tries to wants to make the hash function fall into then we want to try to find a solution x so that if we hash the puzzle ID together with the solution x we get a result that's in the set y. So the idea is y is a target range or set of hash results that we want. ID specifies a particular puzzle and x is a solution to the puzzle. And the puzzle friendly property here implies that there's no solving strategy for this puzzle which is much better than just trying random values of x. And so if we want to if we want to pose a puzzle that's difficult to solve that we can do it this way as long as we can generate puzzle IDs in a suitably random way and we're going to use that later when we talk about Bitcoin mining. That's the sort of computational puzzle we're going to use. Okay so we've talked about three properties of hash functions and one application of each of those now let me talk just very briefly about the particular hash function we're going to use. There are lots of hash functions in existence but this is the one Bitcoin uses and it's a pretty good one to use. It's called SHA256 or SHA256 and it works like this. Basically it takes the message that you're hashing and it breaks it up into blocks that are 512 bits in size. The message isn't going to be in general necessarily exactly a multiple of the block size so we're going to add some padding at the end. The padding is going to consist of at the end of the padding a 64 bit length field which is the length of the message in bits and then before that it's going to consist of a one bit followed by some number of zero bits and you choose the number of zero bits so that this comes out exactly to the end of a block. So once you've padded the message so that its length is exactly a multiple of the 512 bit block size you then chop it up into blocks and you then execute this computation. You start with the 256 bit value called the IV that's just a number that you look up in a standards document and then you take the IV and the first block of the message you take those 768 total bits and you run them through the special function C and the compression function and out comes 256 bits. You now take that with the next 512 bits of the message run it through C again and you keep going each iteration of C crunches in another 512 bit block of the message and mixes it in sort of logically to the result and when you get to the very end you have consumed all of the blocks of the message plus the padding the result is the hash that's a 256 bit value and it's easy to show that if this function C this compression function is collision-free then this entire hash function will also be collision-free. The other properties are a little bit more complicated so I want to talk about them here. Okay so we've talked about hash functions we've talked about what hash functions do we've talked about three properties of hash functions and applications of those properties and the specific hash function that we use in Bitcoin. In the next lecture segment we'll talk about ways of using hash functions to build more complicated data structures that are used in distributed systems like Bitcoin. In section 1.2 we're going to talk about hash pointers and their application a hash pointer is a kind of data structure that turns out to be used a lot in the systems that we're talking about and a hash pointer is basically a simple thing that we're going to take a pointer to where some information is stored and we're going to together with that pointer store a cryptographic hash of the information so whereas a regular pointer gives you a way to retrieve the information a hash pointer is going to let us ask to get the information back and it's also going to let us verify that the information hasn't changed so hash pointer tells us where something is and what its value was. Okay and we're going to draw a hash pointer in diagrams like this that we're going to have we're going to have H of and then an arrow that points to something so anything drawn like this you think of it as being a hash pointer to this this thing it's a pointer to where it's stored and it's also the hash of the value that this data had when we last saw it and we can take hash pointers and we can use them to build all kinds of data structures so a key idea here take any data structure a linked list a binary search tree or something like that and implement it with hash pointers instead of pointers as we normally would for example here's a linked list that we've built with hash pointers and this is a data structure that we're going to call a blockchain so just like a regular linked list where you have a series of blocks and each block has data as well as a pointer to the previous block in the list here the previous block pointer will be replaced with a hash pointer so it says where it is and what the value of this entire previous block was and we're going to store we're going to remember the head or of the list like this just as a regular hash pointer okay and a use case for this for a blockchain like this is a tamper evident log that is if we want to build a log data structure that stores a bunch of data so that we can add data on to the end of the log but if somebody goes later and messes with data that is earlier in the log we're going to detect it that's what the tamper evidence means so to understand why a blockchain gives us this tamper evident property let's ask what happens if an adversary wants to go back and tamper with data later that's in the middle of the chain okay so let's assume that an adversary wants to tamper with this block down here he wants to change the data here and he wants to do it in such a way that we the holders of the of the hash pointer at the head here won't be able to detect it all right so the adversary changed the contents of this block and therefore the hash here which is a hash of this entire block is not going to match up because the hash function is collision-free it must be the case that the hash of this block is now different and so we could detect the inconsistency between this data and the hash pointer that we remembered before or we could do that in unless the adversary also tampers with the hash pointer if he tampers with this hash pointer then he makes these two match up but now he's changed the content of this block and what that means is that when we come back later and hash the contents of this block it's not going to match the hash that we remembered before because the contents of the block has changed and so we're going to detect the inconsistency between this the contents of this block and this hash unless the adversary also tampers with the block over here on the right but now when he does that the hash of this block is not going to match the hash that we remembered up here and the hash that we're holding on to and this the adversary can't tamper with because this is the value that we remembered as being the head of the list and so the upshot of this is that if the adversary wants to tamper with data anywhere in this entire chain in order to keep the story consistent he's going to have to tamper with the hash pointers all the way back to the beginning and he's ultimately going to run into a roadblock because he won't be able to tamper with the head of the list and so what this means is that just by remembering this hash pointer we've essentially remembered a kind of hash a tamper evident hash of the entire list all the way back to the beginning and so we can build a blockchain like this containing as many blocks as we want going back to some special block at the beginning of the list which we might call the Genesis block and that's a tamper evident log built out of a blockchain now another useful data structure that we can build using hash pointers is a binary tree we can build a binary tree with hash pointers and this is called in the jargon a Merkel tree after Ralph Merkel who invented it and the idea is this suppose we have a bunch of data blocks which will draw across the bottom down here we're going to take pairs consecutive pairs of these data blocks and for these two data blocks we're going to build a data structure here that has two hash pointers one to each of these blocks and similarly all the way across we'll then go another level up and this this block here will will contain a hash pointer of these two children down here and so on all the way back up to the root of the tree and then just like before we're going to remember just the hash pointer up here at the head of the tree and we can then if we want traverse down through the hash pointers to any point in the list and we can make sure that the data hasn't been tampered with because just like I showed you with the blockchain if an adversary tampers with some block down here at the bottom with the data that will change that will cause the hash pointer that's one level up to not match so we'll have to tamper with that and therefore he'll have to tamper with the hash pointer one level up from there and therefore he'll have to tamper with the hash pointer one level up from there and eventually he'll get up to the top where he won't be able to tamper with the hash pointer that we've remembered so again any attempt to tamper with any piece of data across the bottom will be insured against by just remembering the hash pointer at the top. Now, another nice feature about Merkle trees is that unlike the blockchain that we built before, that if someone wants to prove to us that a particular data block is a member of this Merkle tree, all they need to show us is this amount of data. So if we remember just the root and someone wants to convince us that this block is in the Merkle tree, they need to show us this block. And we can verify that the hash matches up. And then they need to show us this block. And we can verify that the hash of this matches that. They can show us this block. We verify that the hash of this block matches this hash pointer. And then they show us the data. And just by verifying the hashes up to the root, we can ensure we can verify that this data block was in the Merkle tree. So that takes about log n items that we need to be shown. And it takes about log n time for us to verify it. And so with a very large number of blocks, data blocks in the Merkle tree, we can still verify, prove membership in a relatively short time. OK, so Merkle trees have various advantages. One advantage, of course, is the tree holds many items. But we just need to remember the one root hash, which is only 256 bits. We can verify membership in a Merkle tree in logarithmic time and logarithmic space. That's nice. And there's a variant, which is a sorted Merkle tree. That's just a Merkle tree where we take the blocks at the bottom and we sort them into some order, say alphabetical lexicographic order or numerical order or some order that we agree on. Now, having done that, once we've sorted the Merkle tree, now it's possible to verify non-membership in a Merkle tree. That is, we can prove that a particular block is not in the Merkle tree. And the way we do that is simply by showing a path to the item that's just before where that item would be and just after where it would be. And then we can say, look, both of these items are in the Merkle tree. They're consecutive. And therefore, there's no space in between them. There's nothing in between them. And so the thing that we're trying to prove non-membership of can't be there. All right. So a Merkle tree is a binary search tree built with hash pointers. We can do logarithmic time membership proofs, non-membership proofs if we sort the tree. And it's very efficient. More generally, it turns out that we can use hash pointers in any pointer-based data structure as long as the data structure doesn't have cycles. If there are cycles in the data structure, then we won't be able to make all the hashes match up. If you think about it, in an acyclic data structure, we can sort of start near the leaves or near the things that don't have any pointers coming out of them, compute the hashes of those, and then work our way back sort of toward the beginning. But in a structure with cycles, there's no end that we can start with and compute back from. So for example, a directed acyclic graph out of hash pointers, and we'll be able to verify membership in that dag very efficiently, and it will be easy to compute. So this is a general trick that you'll see over and over throughout the distributed data structures and throughout the algorithms that we talk about later in this lecture and in subsequent lectures. In segment 1.3, we're going to talk about digital signatures. This is the second cryptographic primitive, along with hash functions that we need as building blocks for the cryptocurrency discussion later on. So a digital signature is supposed to be just like a signature on paper, only in digital form. And what that means is this. What we want from signatures is two things. First, that just like an idealized paper signature, only you can make your signature, but anyone who sees your signature can verify that it's valid. And then the second thing you want is that the signature is tied to a particular document so that somebody can't take your signature and snip it off one document and glue it onto the bottom of another one. Because the signature is not just a signature, it signifies your agreement or endorsement of a particular document. OK, so the question is, how can we build this in a digital form using cryptography? So let's get into the nuts and bolts. Here's an API for digital signatures. There are three things, three operations that we need to be able to do. The first one is we need, in the beginning, to be able to generate keys. And so we have a generate keys operation, and we tell it a key size. How big in bits should the keys be? And this produces two keys, SK and PK. SK will be a secret signing key. This is information you keep secret that you use for making your signature. And PK is a public verification key that you're going to give to everybody and that anybody can use to verify your signature when they see it. The second operation is the sign operation. The sign operation, you take your secret signing key and you take some message that you want to put your signature on and it returns SIG, which is a signature, just some string of bits that represents your signature. And then the third operation is a verify that takes something that claims to be a valid signature and verifies that it's correct. It takes the public key of the signer. It takes the message that the signature is supposedly on and it takes the supposed signature. And it just says yes or no. Is this a valid signature? So these three operations, these three algorithms constitute a signature scheme. And I'll note that the first two can be randomized algorithms. The verification won't be. It will always be deterministic. And in fact, if you think about it, generate keys had better be randomized because it ought to be generating different keys for different people. Okay, so the requirements for the signatures at a slightly more technical level are the following two requirements. First of all, that if a signature is, that valid signatures will verify. If a signature is valid, that is if I sign a message with SK with my secret key, that if someone then later tries to validate that using my public key and the same message that that will validate correctly. So this says that signatures are useful at all. But then the second thing you want is that it's impossible to forge signatures. That is an adversary who knows your public key, who knows your verification key and gets to see signatures on some other messages, can't forge your signature on some message that he wants to forge it on. And in order to explain this property in a little bit more detail, it's normally formulated in terms of a sort of game that we play with an adversary. So the game, I'll depict it here with this diagram. So over here on the left, you have the challenger who's a TV judge. And the challenger is going to test a claim by an attacker. The attacker claims that he can forge signatures and we're going to test that claim and the judge will pass judgment on it. The attacker here, this guy is actually Whit Diffie who is one of the inventors of digital signatures of the concept of digital signatures and a distinguished cryptographer. So I thought I'd let him play the attacker role here. Okay, so the game works like this. The first thing we do is we use generate keys to generate a secret key, a secret signing key and a public verification key that match up. Now we give the secret key to the challenger to the judge and we give the public key to both parties, both to the challenger and to the attacker. So the attacker only knows information that's public, he only knows the public key and his mission is going to be to try to forge a message. The challenger knows the secret key so he can make signatures. Right now, if you think about a real life application and a real life attacker would be able to see valid signatures from their would be victim on a number of different documents and maybe the attacker could even manipulate the victim in designing innocuous looking documents if that's useful to the attacker. So in our game, we're going to allow the attacker to get signatures on some documents of his choice and we see that in the diagram like this. The attacker is going to send over a message M0 to the challenger and the challenger is going to sign that message and send the signature back. The attacker can look at that scratch his head a little bit and send over another message M1. The challenger will sign that and we do that for as long as the attacker wants. The attacker can send over any sequence of messages he wants and get signatures on them. Once the attacker is satisfied that he's seen enough signatures and we're going to let him see only a plausible number, then he's going to pick some message M that he wants to forge a signature on and he's going to try to forge a signature and of course there's a rule that says that this M, this message that he's trying to forge a signature on isn't one of the ones that messages that he's already seen because it would be really easy for him to forge to send over a valid signature on M0. I mean, we sent him a valid signature on M0 earlier. So he's going to pick some other message that he hasn't seen a signature for already and he's going to send over what he claims as a signature on that message and then the question is can he succeed? So the challenger is going to run the verify algorithm, use the public verification key and on that message and the signature that the attacker provided and is going to check whether it verifies and if it does verify, if this returns true then the attacker wins, the attacker has forged a message. And so this game is what we use to define what it means for a digital signature scheme to have the unforgeability property and if we want to get really precise, what we say is that the attacker's probability of winning this game is negligible and that that's true no matter what algorithm the attacker is using. In other words, we're going to say that the signature scheme is unforgeable if no matter what algorithm the attacker is using the attacker has only a negligible chance of successfully forging a message. And if we have that property together with the much easier property that valid messages verify then we have a digital signature scheme that is suitable. Okay. Now, there's a bunch of practical things that we need to do to turn that algorithmic idea into a more practically implementable signature mechanism. For example, the algorithms we talk about are randomized at least some of them will be and so we need a good source of randomness and the importance of this really can't be underestimated. Band randomness will sink you, your algorithm will be insecure. And I'll just point out here that attacks on the source of randomness are a favorite trick of intelligence agencies and those are the people who know what kinds of attacks are likely to be successful. In practice, there's a limit on the message size that you're able to sign because real schemes are going to operate on bit strings of limited length. The fix to that is simply to use the hash of the message rather than the message itself. That way the message can be really big but the hash will be only 256 bits. And because hash functions are collision-free it's safe to use the hash of the message as the input to the digital signature scheme rather than the message. And by the way, a fun trick which we'll see used later is that you can sign a hash pointer. And if you sign a hash pointer then the signature covers or protects the whole structure. Not just the hash pointer itself but everything it points to and everything it points to. For example, if you were to sign the hash pointer that was at the end of a blockchain the result is that you would effectively be digitally signing the entire contents of that blockchain. That's a useful trick that we'll see used later. Okay, now let's get into the nuts and bolts. Bitcoin uses a particular digital signature scheme that's called ECDSA. That's the Elliptic Curved Digital Signature Algorithm and it's a US government standard. And we won't go into all the details of how ECDSA works. It relies on some extremely hairy math and trust me, you don't wanna see all the details of how that works. You can look it up if you're interested. So we'll skip that. One thing I'll note though is with ECDSA good randomness. I said this before but I'll say it again because it's really essential. Good randomness is especially essential with ECDSA. If you use bad randomness in generating keys or even in signing, you probably leaked your private key. It stands to reason that if you use bad randomness in generating a key that the key that you generate is maybe not secure. But it's a quirk of ECDSA that even if you use bad randomness just in making a signature using your perfectly good key that also will leak your private key and then it's game over. So we need to be especially careful about this in practice. This is a common mistake. So that completes the discussion of digital signatures as a cryptographic primitive. And then in the next segment we'll move on and talk about some applications of digital signatures that will turn out to be useful in building cryptocurrencies. In segment 1.4, we'll move on having covered digital signatures and talk about a nice trick that we can use that goes along with digital signatures. And the useful trick is this. The idea is to take a public key one of those public verification keys from a digital signature scheme and equate that to an identity. That is an identity of a person or an actor in a system. So if you see a signature that verifies correctly, that is if you see a signature such that you can verify with someone's public key that that is a signature on a particular message then you can think of that as that public key saying the message. You can literally think of a public key as kind of like an actor or a party in a system and that they can make statements by signing those statements. And so if you think in that mindset then this public key is like an identity. It's an actor who can do stuff in the system. And if you think about it then for someone to speak for PK that is for someone to be able to make statements that will be seen as coming out of PK's mouth you have to know the matching secret key SK. And so if you know the secret key that corresponds to the public key PK then you can sign messages with that secret key and what you're doing essentially is making statements on behalf of that public key. And that means that there is an identity in the system which only you can speak for and of course that's what you want an identity to be something that one person can speak for or on behalf of that everybody can see. All right, so if we're going to treat public keys as identities one of the consequences of that is that you can make a new identity whenever you want. If you want to make a new identity you just do this. You create a new random key pair SK and PK by doing the generate keys operation in our digital signature scheme.  PK is then the public name that you can use that's the name of that identity what it's called although in practice you'd probably use the hash of PK because public keys are big but again that we'll leave that aside as a detail. So PK or the hash of it is the public name that you use to talk about the identity and SK the secret key is the information that lets you the person who generated this identity speak for the identity. You control the identity because only you know the secret key and if you generated this in such a way that the public key PK looks random then nobody needs to know who you are. You can generate a fresh identity that looks random that looks like a face in the crowd that only you control. This brings us to the idea of decentralized identity management that rather than having a central place that you have to go in order to register as a user in a system you don't need to get a username you don't need to inform someone that you're going to be using a particular name if you want a new identity just make one. Anybody can make a new identity at any time and you can make as many as you want if you prefer to be known by five different names no problem just make five identities. If you want to be somewhat anonymous for a while you can make a new identity use it just for a little while then throw it away. All of these things are possible with decentralized identity management and there's no central point of control so that you don't have to have anyone who's in charge of it. The system operates in an entirely decentralized way and this is the way Bitcoin in fact does identity. These identities are called addresses in Bitcoin jargon and so you hear the term address used in talking about Bitcoin and cryptocurrencies but what that really is is just a public key or a hash of a public key. It's an identity that someone made up out of thin air as part of this decentralized identity management scheme. Now the obvious question that arises when you're talking about decentralized identity management and people making up these identities is how private is this? And the answer is it's complicated. On the one hand the addresses that are made up this way are not connected to your real world identity. You can execute a randomized algorithm. It will make some kind of PK that looks kind of random and nothing exists initially to connect that to who you are. You can do that in the privacy of your own home. So that's good news if you wanna be able to act privately but the bad news if you wanna act privately is that if that address, if that identity is making a series of statements over time, if it's engaging in a series of acts over time that people can see that whoever this is has done a certain series of actions and they can start to connect the dots. Gee, this person is acting a lot like Joe. Maybe this person is Joe. And so an observer can link together these things over time and make inferences. And so this balance between on the one hand there being no initial tie to real world identity and on the other hand that a pattern of behavior of an address emerging over time and the question of what can be inferred and which dots can be connected that gets pretty complicated. And that's really the question of privacy in a cryptocurrency like Bitcoin. And there's a whole lecture about that later on.  I just wanna give you an idea of how decentralized identity makes privacy a complicated question. In segment 1.5 we're going to move from talking about cryptography and we're going to move on to cryptocurrencies. Now I know that many of you showed up here for the cryptocurrency stuff and trust me there will be a lot more cryptocurrency material in future lectures. Unfortunately we needed to eat some of our cryptographic vegetables in order to have the background to talk about cryptocurrencies. And now you'll see when I start talking about cryptocurrencies, how these pieces fit together and why the cryptographic operations like hash functions and digital signatures are actually useful. All right, so in this section I wanna talk about some simplified cryptocurrencies that give us ideas about how systems like Bitcoin work. Of course it's going to require about 10 more lectures in order to really spill out all of the implications of how Bitcoin works and what that means. But let me talk about some very simple cryptocurrencies to get the discussion started. And first let's talk about Goofycoin. Goofycoin is about the simplest cryptocurrency we can imagine. And it works kinda like this. There are just a couple rules of Goofycoin. The first rule is that Goofy can create new coins. Goofy can make a new coin whenever he wants and when he makes a new coin it belongs to him. So when Goofy makes a coin it's represented by a data structure like this. Here you have the create coin operation and there's a unique coin ID that Goofy generated and then there's a digital signature that was put on it by Goofy which anyone can verify. So anyone being given this can verify that the signature is valid and that it's a signature of this statement. And new coins belong to Goofy by definition because those are the rules that Goofy made. So that's the first rule, Goofy can create new coins. The second rule of Goofycoin is that whoever owns a coin can pass it on to someone else, they can spend it. So for example, here we have the coin that I showed you before that Goofy created. And now we're gonna take a hash pointer to that coin and then we're gonna create a statement. Goofy's gonna make a statement that says pay this to Alice. Alice is being named by a public key here. Pay to public key Alice, the coin that's represented by this hash pointer. And this is also signed by Goofy. Now Goofy is the one who owned that coin and so Goofy has to sign any transaction that spends the coin. And once this has happened, now Alice owns the coin. Alice owns the coin and Alice can prove that she owns the coin because she can present this data structure here which is validly signed by Goofy and points to a coin that was validly owned by Goofy. And so the correctness of this coin is self-evident in the system. Now Alice can move on and she can spend the coin as well. So here we have the coin we had before. This is down here at the bottom. We have the creation of the coin signed by Goofy. Now Goofy paid the coin to Alice via this hash pointer and he signed that. Now Alice is the owner of the coin. Now she can create a statement like this that says pay this coin to Bob's public key and here's a hash pointer to the coin. And now Alice signs that. So because Alice was the valid owner of the coin which we could verify by walking this chain, now we know that this is valid and the coin belongs to Bob. So Bob is now the owner of this coin. So those are all the rules of Goofy coin. Goofy can create new coins by simply signing a statement that he's making a new coin with a unique coin ID. And then whoever owns a coin can pass it on to someone else by signing a statement saying pass on this coin to person X. And you can verify the validity of a coin by simply following the chain and verifying all of the signatures along the way. That's Goofy coin. All right, now there's a problem though. There's a big security problem with Goofy coin and we can see it in this structure here. So look at this coin here. This is the coin that Goofy made and then paid to Alice. Alice was the owner of that coin. And there's a problem. Alice paid this coin on to Bob but now Alice makes another data structure like this which pays to Chuck the very same coin. And this is signed by Alice. Now if Chuck doesn't know about this thing up on the upper left, this data structure, let's say Alice just gave that to Bob and didn't tell Chuck. Now Chuck will look at this and he'll think that this is perfectly valid and now he's the owner of the coin. Chuck has a valid looking claim to be the owner of this coin and Bob has an equally valid looking claim to be an owner of this coin and that's a problem because coins are not supposed to work that way. This is called a double spending attack. It's called double spending because Alice is spending the same coin twice. And double spending attacks are one of the key problems that a cryptocurrency has to solve. Goofy coin does not solve the double spending attack and therefore Goofy coin is not secure. So although Goofy coin is simple and we understand its rules, it won't cut it as a cryptocurrency because it allows double spending. So in order to build a cryptocurrency that is going to be workable, we need to have some solution to the double spending problem and indeed the double spending problem is the main design challenge that we face in designing a cryptocurrency. So we need to somehow improve on Goofy coin and we'll do that by designing another coin which I'll call Scrooge coin. Scrooge coin is going to be rather like Goofy coin except it will solve the double spending problem in a particular way and this coin was created by Scrooge. Okay, so this is a little bit more complicated in terms of data structures but here's one of the key ideas. That Scrooge is going to publish a history of all the transactions that have happened. This will be a blockchain, that data structure we talked about before and it will be digitally signed by Scrooge. So anyone can, and it looks like this of course, it's a series of blocks, data blocks. Each block will have one transaction in it. This block has the transaction with transaction ID number 73 and it has the contents of this transaction and then there's a hash pointer to the previous block in the history. Okay, and then Scrooge will take the hash pointer which represents this entire structure and he'll digitally sign it and publish it. Now anybody can verify that Scrooge really did sign this hash pointer and then they can follow this chain all the way back and see what is the entire history of all the transactions in the history of Scrooge coin as endorsed by Scrooge. Now I said here that we put one transaction in each block. We do that for simplicity of explanation but in practice as an optimization we'd really put multiple transactions into the same block as Bitcoin does. So you can bear in mind as I talked about Scrooge coin that that's the way we'd really do it in practice. So Scrooge publishes this history. What does the history do? Well the thing the history does for us is it allows us to detect double spending because assume Alice owns a coin and she's going to pay that coin on to Bob and she's then later going to try to pay that coin on to Charlie. Charlie's gonna notice that something is wrong because Charlie will be able to look into the history and see that Alice already paid that coin to Bob. In fact everyone will be able to see that Alice already paid that coin to Bob. So if she tries to pay that coin to Chuck then everyone can see that that's a double spend and they'll be able to reject it. Scrooge will reject it and everyone else will reject it and know that they really shouldn't trust Alice. All right so in Scrooge coin there are two kinds of transactions. The first kind is a create coins transaction and what it does is create new coins. That's like the operation Goofy could do in Goofy coin that makes a new coin but here we're going to allow multiple coins to be created in one transaction. So here's what a create coins transaction looks like. It has transaction ID number 73. Let's say in this case it's transaction type is create coins and then down here there's a list of which coins are created. Each coin is going to have a serial number within this transaction, zero, one, two, et cetera. Each coin has a value, it's worth a certain number of Scrooge coins and each coin has a recipient which is going to be a public key who gets that coin as it's created. So this transaction type creates a bunch of new coins and assigns them to people as initial owners. Now we're going to have a concept in Scrooge coin of a coin ID that refers to a particular coin. So this particular coin here is coin ID 73 per end zero because it was created in transaction 73 and it was number zero within that transaction. Similarly we have 73 per end one, 73 per end two and so on. So every coin in Scrooge coin has a coin ID that we can use to refer to it. A create coins transaction is always valid. Why is it valid? Well because Scrooge said so and they call it Scrooge coin for a reason. If Scrooge puts this into the history which he signs then it's valid by definition. We don't need to worry about whether Scrooge is entitled to create coins just like we didn't need to worry in Goofy coin about whether Goofy is entitled to create coins. The rules of the system which were created by Scrooge simply say that if Scrooge wants to make coins then that's valid. So anything he puts into the history is valid. The second kind of transaction we're going to talk about is a pay coins transaction. And this is a transaction that consumes some coins and destroys them and creates new coins of the same total value but which might belong to different people. So over here on the left we have an example of what a pay coins transaction looks like. This is transaction ID number 73. Let's say it's type is pay coins. We have here a list of the coins that this one consumes. All of these coins are being consumed and destroyed by this pay coins transaction. So we're going to add up the value of all of those coins and then we're going to create a bunch of new coins down here, zero, one, and two, et cetera, just like before in the create coins transaction each one has a value. Each one will belong to a certain recipient. And those new coins had better add up to the same total value as the coins that we consumed. And then at the bottom we have a set of digital signatures. This transaction has to be signed by everyone who's paying in a coin. So if you're the owner of one of the coins that's going to be consumed in this transaction then you need to digitally sign the transaction to say that you're really okay with spending this coin. The rules of Scrooge coins say that a pay coins transaction is valid if four things are true. First, if the consumed coins are valid, that is they really were created in previous transactions. Second, that the consumed coins were not already consumed in some previous transaction. That is that this is not a double spend. Third, that the total value of the coins that come out of this transaction is equal to the total value of the coins that went in. And finally, that the transaction is validly signed by the owners of all of the consumed coins. If all of those things are true then this pay coins transaction is valid. Scrooge will accept it. He'll write it into the history, into the blockchain and everyone will see that this transaction has happened. One thing to note about this scheme is that coins are immutable. Coins are never changed. They're never subdivided. They're never combined. All they are is created once in one transaction and then later consumed in some other transaction. But you can get the same effect as being able to subdivide or pay on or combine coins by using transactions. For example, if you want to subdivide a coin, you can just create a new transaction that consumes that one coin and then produces two new coins of the same total value.  That's a way that you can subdivide a coin that you own. Similarly, you can combine coins or you can pay on a coin in effect by just creating a chain of transactions, each of which pass that value on in the form of a new coin to someone else. So although coins are immutable in this system, it has all of the flexibility of a system that didn't have immutable coins. Okay, now we come to the core problem with Scroogecoin. Scroogecoin will work. People can see which coins are valid. It prevents double spending because everyone can look into the blockchain and see that all of the transactions are valid and that every coin is consumed only once. But the problem is Scrooge. Scrooge thinks this is fine, right? Scrooge says, don't worry, I'm honest. But the fact is if Scrooge starts misbehaving, then we're going to have a problem. Or if Scrooge just gets bored of the whole Scroogecoin scheme and stops doing the things that he's supposed to do, then the system won't operate anymore. And so the problem we have here is centralization. That although Scrooge is happy with this system, we as users of it might not be. So the central technical challenge that we need to solve in order to improve on Scroogecoin is can we desgrugify the system? That is, can we get rid of that centralized Scrooge figure? Can we have a cryptocurrency that operates like Scroogecoin in many ways but doesn't have any central trusted authority? In order to do that, we're going to need to figure out how to provide the services that Scrooge provides but do it in a decentralized way in a way in which no particular party is particularly trusted. That means we're going to need to figure out how everyone can agree upon a single published blockchain that is the agreed upon history of which transactions have happened. We need to figure out how people can agree which transactions are valid and which transactions have actually occurred. And we need to figure out how we can assign IDs to things in a decentralized way. If we can solve all of those problems then we can build a currency that is very much like Bitcoin which is like Scroogecoin but without a centralized party. But in order to do that it's going to take a few more lectures and we hope you'll stick around and watch them. Thanks.


Live from Orlando, Florida, it's theCUBE. Covering Pentaho World 2017. Brought to you by Hitachi Ventura.  I'm your host, Rebecca Knight, along with my co-host, James Kobielus. We're joined by Dr. Ella Halal. She is the Director of Innovation at IMS. Thanks so much for coming on theCUBE, Ella. Thanks, I'm excited to be here. So you described your mission this morning as the mission to enable the connected car. Tell our viewers, what is the connected car? Oh, that's a very interesting question. So to us, to us at IMS, we define the connected vehicle in a little bit of a different way. So most people define it as being connected to the internet, but having it connected to the internet is not very useful to us drivers. But having it connected to you, the driver, is the key, is the essential point. And this is how we define the connected vehicle. So if by connecting it to you, we need to connect it to the internet, then that's a byproduct. But the key is giving you actionable insights as you're driving along, doing your daily commute. And as I mentioned this morning, you spend about 4.5 years of your life in a vehicle. That's a long time. That's a lot of time on your behalf. So if we are able to make this commute or your time in a vehicle more productive, then you get to enjoy this ride a little bit more. So augmenting the driver or passenger's experience with analytics, as opposed to what people usually think of which is self-driving autonomous vehicles. So it's one step of the way. You cannot have an autonomous vehicle without having connected vehicles. Because if you think about it, if you're having autonomous vehicles that has a horrible user experience, then what are you really doing, right? Nobody will want to ride it. So talk about what are some examples of these actionable insights that you could give someone as they're driving along. Okay, so imagine this. So if you're driving in the middle of highway and we know your destination in advance, but we know that there's no parking space and we can redirect you to another parking spot. That's an actionable insight that would be useful. If we know that you're driving and because of the way you're driving, your premiums will go up because you impose a little bit more high risk. We can give you coaching and feedback on how you can get to be a better driver and save some money. Think about it another way. You can be driving in a harsh braking, harsh exploration, imposing wear and tear on your tires that will cost you money because you would need to change them. If we give you this information early on, your incentive is to change your behavior a little bit to prolong the lifetime of your vehicle as well as save some gas. So IMS is a longtime IoT customer. Can you tell us how you've been able to stay relevant? Oh, that's a very interesting question. So definitely it's been an interesting, ever-changing market. So we focus on delivering a suite of services, not just one service with one provider. We actually provide a suite of services and we can enable different ones at different times. So we're not just a usage-based company, we're a connected car company. That means that we enable road user charging. So you know road user charging, right? So like multiple states in North America, as well as in Europe, different countries are focused now on having road charging. Instead of you paying the gas tax at the gas pump, every time you put gas in the car to offset the cost of the infrastructure, you pay the road user charge. At all. Well, similar to at all, but it's different because you're already paying it somehow. So at all is its choice. You need to take this road, you pay the toll for it. But for road user charging, it's trying to have a fair system to offset the cost of the infrastructure.  Now you have hybrid vehicles, now you have fuel efficient vehicles, as well as you have electric vehicles that are imposing wear and tear on the roads, but there's not money coming to the government to help offset this cost. So they are trying to have a more fair system where we all contribute to the roads that we're driving in. So what's the metering infrastructure to enable road or usage-based road charges? Okay, so road user charging is actually quite interesting. So you think it has a lot of different additional overhead that you need, but actually it's not. You can, we as a company, enable road user charging through an OBD dongle that you add on your vehicle, and that's enough for us to get all the information needed, whether it's just mileage information without GPS. Again, it's a diagnostic port, yes, yes. So it has multiple ways, right? So you can enable it. Road user charging has multiple flavors of it. So one of them with GPS information, so we only charge you on public roads, not private roads. So if you're driving on a campus or a big campus at work, you're not charged for that. You only pay for public roads. If we don't have GPS, we do a mileage-based approach where we collect this data and we provide it to the government to charge you for it. And the nice thing about it, they actually do a gas rebate. So gas tax rebates. So you claim these mileage, you claim what you're paying for road use charging, and you rebate your gas tax. Another flavor of it would be based on an OBD2, sorry, other than the OBD2 is a mobile phone. So we can use a mobile phone to collect similar data and again, understand where you are and accordingly, send the information for the government to charge you as such. As it relates to the internet of things, then are those our approaches that would you regard? Those are both as IoT related approaches. Is there any other like metering technologies that you're exploring for gathering this data in a way that's more or less invisible? So I would definitely consider this as an IoT because again, the IoT is having the sensors embedded in multiple services. And so definitely to me, that's an IoT application. That being said, there are the existing tolling approaches which are like cameras and sensors at entry points and exit points. These are roadside infrastructures. You can also have like lane, high occupancy lanes where if you're in it, they can take a picture or sense how many people in the vehicle. So there are a lot of technology that enables road usage charging. That being said, I think using an OBD2 or a mobile phone is one of the most seamless things that you can do simply because you plug it in once and you don't have to interact with it. So how is Pentaho, how are you partnered with Pentaho to manage all this data to drive these programs? Actually, that's an interesting question. We're at Pentaho World, so let's hear it. Yeah, exactly, this is the right question to ask you. So Pentaho has helped us accelerate the ETL, the extract, transform and load process. Especially that we're collecting data from diverse sources, from heterogeneous platforms, whether it's from an OBD2, from a mobile phone or even from vehicles themselves. So collecting data from all of these different sources, Pentaho enabled us to ingest it fast, extract it, transform it and load it. It also helped with data integration. So the Pentaho data integration platform helped us work with multiple sources, get stuff fast, get it ready, and above all, it helps with the visualization because we work with different clients and each of them require a different report or view of the data in an aggregated way. So Pentaho definitely helped us accelerate and adapt fast to the requirement of our clients. Are the clients, are they fleet managers? Are the clients insurance companies? Give us a sense for the sort of dashboards you provide to them. And I'm using dashboards in a double entendre sense. To what extent can this technology be embedded in the dashboards of the future, connected cars to help drivers and passengers to modify their behavior while they're using the road system? So I will answer that onto two parts. So first, who are our clients? So we work with definitely insurance companies, some of the top on in the world, which would need data in a different form. We work with governments. We provide them for road user charging, for example, work with governments. So we provide them a different view of the data as the requirement. We work with fleet managers, a fleet insurance company, which is commercial lines. We also provide information to the end driver, to the end user, because how can you change, help them change their behavior? How can you give them actionable insights if you're not interacting with them? So all of these are different end points to our data and how we're exposing it. Regarding what can we show in the dashboard? If you think about it today on some sense, we're showing some information. We're showing actually a lot of information. So we have the mobile app that acts as an interface or a touch point between us and the end user. Because at the end of the day, the end user is the one who owns the data. It's not IMS, it's the end user who owns the data. And he's allowing us to use it to give him insights to get insurance discounts or know how much he's being charged for road user charging or enable services like roadside assistance and others. So the mobile app is our interaction point. And we have screens that show the logs of your trips and what good did you do, what bad did you do? We have analytics on this behavioral side. Where are you in terms of percentile on all different drivers? So that also gives you an encouragement and we always focus on positive feedback to help you enhance and change your driving to the better. What are you doing in terms of data masking and anonymization to protect the privacy of this data that's being processed through your applications? Definitely, I- Very privacy sensitive, obviously. No, yeah, and we are very, very aware of it. We're actually- And how are you using Pentaho in that regard? Okay, and we're very, very aware of it and we're very, very security conscious. So if you think about it, who are our clients? Our insurance company, who are our security focus and then governments are security focused. And so when you work with such big companies and big institutions that are very aware of security, you need also to step up and show that. And this is why we're ISO certified in many, many areas. So we're very aware of privacy. We never use any PII and our PII officer, we have a security officer that is very, very, very strict. Let me tell you that. And when we use data, we use it in an aggregated and anonymized format. So you cannot, and we use differential privacy on it, so you cannot identify one person added or removed out of it. So we use all of these different measures. And all the data that is being sent from the device is double encrypted on a VPN as well as sent in a binary format to our backend through a secure system. The devices are unhackable because they are designed such that they cannot receive input. They just made to send out input. So we work on privacy and security. We are actually privacy and security focused in Institute. And this is why we have been chosen by top tier insurers as well as governments to work with. So how far are we from fully autonomous vehicles? I mean, in your keynote, you talked about how actually people think we're further along in the journey than we actually are. But can you walk us through the next sort of next steps and then give us an estimate? Tell me when to ditch my car right now. Yeah, exactly. That's what I want to know. Okay, that's an interesting question. And I'm sure it's a very controversial one because everybody would have a different opinion. I know somebody in my team and if he's watching, he would say like in the next three years, I will have my next autonomous vehicle. And it all falls back to the definition of autonomy. As I mentioned this morning, there are five levels of autonomy. So level zero is having no autonomy whatsoever. So it's like your 1970 or 1960 car that you drive, you enjoy, but it does nothing except it enables you to drive. You have then your level one autonomy which will enable one feature only. So it's either cruise control, automatic braking, one thing to assist you. So it's one thing. And then you have level two, that enables two or more things in the same time, but you need to be fully alert and aware. Level three, well, it can drive a little bit autonomously, but you need to be alert, fully engaged and ready to engage at any time, ready to go at any time. Level four, it is autonomous under certain conditions. So for example, autonomous on highways or autonomous in specific cities, but not autonomous in others. Level five, it's autonomous everywhere all the time. This is what we're all waiting for, where we can sit. I'm on tenterhooks. Exactly, where you can sit. Yes, I want to sleep while I'm driving. I want to binge on Netflix or catch up on all the readings. Right, exactly. I got a lot of Game of Thrones on my face. Exactly, yes, exactly. So it depends on how you define autonomy and this is where it defines where we are on the progress. So if you look at Tesla and Google car, we're actually somewhere between level two and level three. Multiple systems are engaged, but you need to be fully alert and ready to intervene at any time. We're still not at the phase where you can lay back and relax and sleep. So what is your opinion finally? How many years are we looking? Okay, it depends on the level. So if I say level three, yeah, well, we have it. Ella! No! If we're talking about. You're hedging. Level four, I would expect, okay, so level four, level five has challenges. Level four, I would expect it to be between five to 10 years, somewhere in between, but level five is a little bit further and the reason is multiple things. I would say 15 to 20 and I'll tell you why. Number one, you would have multiple cars coexisting on the road and humans' decisions are subjective and are not always predictable. So you will always need to default to human intervention when needed. Road infrastructure takes a long time to be developed and for government investment. Third one, you need human acceptance and trust into these systems so that I can trust my six-year-old daughter to sit there and I will not be afraid for her life. So these things take time to develop and this is why I'm saying 15 to 20 years. Okay, you heard it here folks, all right? 15 to 20 years. Great. I'm all for it. Ella, thanks so much for coming on the keep. Yes, awesome. Great conversation. I really enjoyed it so much. Thanks for having me. I'm Rebecca Knight for James Kobielus. We will have more from the cube at Pentaho World in just a little bit.


Good house. Okay, so maybe I'll continue so. So again, as I said, our goal is to so we have, we have this, we have until so. We deserve continuing we have until I don't know I guess I'll temporarily call it was a name until the. I'm going to move to pie to end. And so I want to let until the of X lambda, the inverse image of it's lambda so now it's so now so by the way when I talked about before with this generally spare as mission isn't is in all types and that's not this is this is not just in. This is actually in all works in all types. But I mean, you know some of what I'm doing now could be extended to other types to I believe but but as far as you know the comment or it's isn't has worked out yet so I'm going to just be in type A for the rest of this talks, you know, so most of the rest of this talk. And so I want to let until the next land, the inverse image of X lambda and wanted to find describe our orbit paving of until the. But I think I guess from the tour picture you can sort of believe why you might need an orbit paving because you know you sort of are naturally putting in this variety which is CR model finding group so you may end up meeting something like that so. Let me tell you what the situation is here so. So, let me make a definition here. So a tableau Sigma is divisible by D. If the entries of Sigma appear in blocks in horizontal blocks of D consecutive integers. D divides Sigma. So for, for example, I could have a tableau that looks something like this. So this is a tableau, which is diesel why to because every, because you can see it's divided up into blocks of two of pairs of integers which are, you know, consecutive so. This tableau is a Y2 but if I, you know, if I interchange the, the two and the three, it won't be divisible Y2 anymore because I've gotten rid of the consecutive integer condition. So I hope it's clear what I mean by divisible. This is divisible by two. So then, so then we can call what, what D Sigma and be the largest, be the largest D dividing Sigma, because obviously the tableau is a little by four it's a little by two as well so we may as well talk about the largest divisor of the tableau. And that for this to happen of course all the parts of build does it have to be increasing consecutive or could it be decreasing consecutive increasing. At least at least it will see an R in for me I mean one could make them decrease I guess but but I'm only interested in very strict tableau anyway so. So they're going to be only concerned about them being increasing but I suppose you could make them. So, but for this to exist all parts of lambda of course must then be your 5634 isn't very strict. Yeah, I guess you're right this is an honest you're okay well I anyway I do want them to be increasing you're right though you're right I mean this isn't a very strict one. Well, I guess I was only thinking of them being increasing let me put it that way there's no reason they would have to be actually all increasing. So maybe we'll cross that off. So, so then, let me so then here's the theorem. And this is, this is with Martha pre cup, Amber Russell. So just try this is unfortunately off the page here but so so we have just to this location. You know we have I'll just write it down here again so we have until the going down to Ada with until they're here. And so that's the math and so then what's so let. Let's see Sigma be, you know in until the of X lambda be the cell of the paving corresponding to to the restrict, then. The inverse of C Sigma. It's a district union of I'll call them C still the Sigma one. See till the Sigma, the Sigma, where each. See till the Sigma I is isomorphic to CR mod this finite abelian group. And moreover, is he transitively permutes. And so what you know how to how would one prove something like this so the proof. So the proof. I mean, you have to look at the way the paving of the springer fiber is constructed so you have to look at the construction of the paving until the of X lambda, and then basically you have to reduce the reduce the theorem is basically you're after all you're starting of of until the of X lambda so you're starting off with that and then you reduce the theorem to result about the map of torque varieties each of the. Add. Well so you so you actually and then you can actually just, you can work in the land of torque varieties and you actually you do want to bring that right until the here as well and they'll put until the here just for that occurs in the proof so. But maybe I won't say anything more about that but but it ultimately boils down you can imagine that it could be something like this because it ultimately boils down to a result about toward varieties. But maybe I won't say anything else about that right now. But let me. Let me. So using this one. So I, one can describe the Poincare polynomial, Pt of until the land and let me. So to get the nicest such description, it's want to bring in the center so bring in the center. So. So let's, so I'll bring in. So the center is G is just isomorphic to Z in here. And so let's let Z hat be the characters of Z. I'll call me the characters is the energy is chi zero. The chi and minus one. So I mean if I think of Z and is being an influence of unity, then the characters are these were chi I of a is a root of unity I just take a raise it to the power. So then, because the accident things the X, I can decompose the co homology of them to the X lambda, as a direct sum of its chi J isotropic components. And I guess I should take co homology with with complex coefficients here. So let me do that with a comment. And then so what I can do is I can so, so let. And T chi of J of M tilde of X lambda be the dimension of the of the chi J isotropic component of each to I have until the X lambda times T to the I. So then, then I just have the PT of M tilde. And so then the theorem is just the sum as J goes from goes from zero to N minus one of P of T chi J of until the X lambda. And so then the theorem is that, which is again from this is that is in is that let E in. So here is actually quite elementary. It's just an elementary, it's an elementary consequence of this previous stuff it's not it's, it's, you know, but, and I'll let, I'll let D be equal to N over the GCD of any. The concrete polynomial of T, the chi E isotopic component of this concrete polynomial. It actually just it's actually, it's a power of T to some power here times the Poincare polynomial of just the springer fiber, where I take the partition and I divide it by D. And this power here that the exponent is actually D minus one times the dimension of B of X, B of X of lambda. So what's happening here is that is that in this in this co homology you're actually seeing these co homology of the smaller springer fibers sitting is the isotopic components in there. So I'm out of time but the point is that maybe not the point but it in type A, we proved earlier that this that we know that this variety until the map until it's M is closely connected to lose things, generalized springer correspondence. And if you make that connection, this result about this Poincare polynomials can actually is actually sort of in the literature in a way I mean it's it's it's known to experts I guess that, because you can compute some of these Poincare polynomials via an algorithm called the algorithm and it's known that the part of the generalized springer correspondence that this part is picking up does look like, you know, representations of smaller symmetric groups, you know, we're as a symmetric in terms of size and over D. So in a sense this is, this is this, if you make the connection of this variety with the generalized springer correspondence than this result here could be deduced from this generalized springer correspondence fact but from another point of view, this this this result doesn't rely at all on the generalized springer correspondence and it's kind of a very geometric manifestation of this fact that is sort of the this takes work in this much more indirect way in this example so, but I think I'm out of time so maybe I will just stop here so thank you. Okay, thanks very much let's thank the speaker.


Hello, traders at CMC Markets. Welcome to a new momentum update by RRG Research for Monday the 25th of July and I'm recording it on Friday the 22nd before the opening of the markets. My name is Julius de Campanar and I'm presenting to you from Amsterdam in the Netherlands. Let's start with a look at the RRG for international stock market indexes against 0% return. As you know that will show us the price direction of those markets in general and this image gives us a clear view of the general direction of stocks over the last week two weeks and what you can see here is that they be moving into the leading quadrant which means that stocks are in a short-term uptrend price-wise and that's good news after long long long declines that we've had. The question is how sustainable are these rallies and we'll try to have a look at that in a minute. The only market that is going against the tide is the Hangsang that's Hong Kong which you see here in the lagging quadrant that is in a short-term downtrend pretty much all the others are on the rise at least in the near term. If we bring this to a relative image and we compare all these stock markets to the MSCI world then we get a different image then we get a different picture. You see the rotations of the various indexes relative to the MSCI world and the ones that are standing out are I think the pretty much the European markets with the DAX, the stocks 50 and the French GAC which are all traveling at a nice positive RRG heading and they're either inside the leading quadrant or traveling towards it and on the opposite side you find that a number of the US indexes the S&P the Dow Jones industrials the NASDAQ are they have turned around and they are now moving at a negative heading either in inside weakening or towards it the NASDAQ here in a Russell 2000 is still doing pretty good. These opposite directions these opposite moves usually give us good trading opportunities it's very well possible to put together price agnostic directional agnostic trades by buying one lag and selling the other and the RRG will help you to pick potential candidates for that. The ones that stands out for me the disconnect between Europe and the US is the thing that I'm watching at the moment and if we look at the stocks that's the Europeans the Euro stocks 50 index and I want to put that against the S&P 500 because that's obviously the biggest US widely traded US index but you could take the DAJs industrials or the NASDAQ if you're very aggressive because that still has a way to go and I want to look at the individual charts for those indexes and if we start with the S&P the Euro stocks 50 index then you see that has bottomed around 3400 where we had that spike dip in March and we've been trying what we've been hovering above that 3400 area since the middle of June and it looks as if we're now getting out of it what we would need to happen preferably next week is breaking above let's say 3600 that will free up more upside potential and give the Euro stocks 50 index a little bit more room to the upside. What you see here are the RRG lines they're continuing to move higher that's what you see on that RRG that's why the Euro stocks 50 index is in that improving quadrant moving towards leaning that's because these lines are pointing higher and you'll see the difference when we move to the S&P chart we look at the S&P 500 chart you see a kind of similar image for price although the S&P dipped a little bit lower we also found a low in June but it was lower than what we had for the Euro stocks 50 index at an earlier date it's coming out of that bottom formation as well so from a price perspective both the S&P and the Euro stocks 50 index are they're not looking fantastic but they have some upside potential but the big difference is when you look at relative strength and you look at these RRG lines you can see that the RRG momentum line that's the stippled green line is already crossed below 100 which means that it is now losing relative momentum and that is starting to drag that RS ratio line lower giving it a weaker outlook from a relative perspective so from a relative point of view I think we are now in a move that favors Europe over the US and that brings me to the next subject that I want to quickly talk to you about for this week's update and that's if you look at the US sectors over the last few days then you can see that the biggest US sectors information technology and consumer discretionary are now strongly moving into the leading quadrant that is these two together are almost 50% of the US market so that is dragging the stock market up if you look at more defensive stuff health care staples utilities to a lesser degree real estate and telecom services they are moving in opposite direction so we're in a move that favors growth information technology because you are discretionary are clearly growth stocks and they are in favor right now however the question is how sustainable is this move how does that fit in the bigger picture and one of the relationships that I'm keeping a close eye on is the relationship between growth and value stocks and you can put that on an RRG and it looks like this this is the Dow Jones US growth index versus the Dow Jones US value index and the center the benchmark of the chart is the Dow Jones US index so this is a closed universe this is everything there is in this universe and you can see the improvements for growth and a weakened weakening for value however if you just look at the RS ratio then value is in a relative uptrend it's losing momentum but it's still in a relative uptrend and growth is in a relative downtrend it's picking up momentum but it's still in a relative downtrend and that you got to keep that in the back of your mind this is a little bit longer term picture than the other RRGs that we've been looking at this is a weekly RRG and if we bring that into one chart if we look at that one on one growth value relationship then I think that's painting us a very interesting and maybe sobering picture if you want this is a real long term chart of growth versus value you can see that it peaked in 2000 obviously off that's the dot-com bubble and you saw that massive decline and the stabilization and then it started to pick up again 2007 2000 day but it really started to take off 2014 and then really here in 2018 and after that for the first time since let's say 2006 I think there's now a massive top formation in place for growth versus value this relationship this ratio has put in in place a massive double top there's something that you cannot negate you can't pretend as if it's not there we had the initial decline and we're now rallying back towards the breakout level that is what you see in that RRG where you see growth picking up and where you see short-term growth sectors and growth stocks picking up but the longer term picture the longer term relationship between growth and value is dangerous I mean we've been used to growth beating value all the time and I think that from a longer term perspective that relationship is now under pressure and it will be very interesting to see what happens once this ratio goes back to 138 maybe 140 in that ratio number and how the growth sectors are then holding up I think we have a long-term turnaround in place we'll have to wait and see what happens but please remember that the from this point of view if you take this into account and if you see what I see and see that this is a big reversal pattern in place then the current rally for growth sectors and growth stocks is only temporary in nature and it will reverse once this growth value relationship hits its breakout level and will meet resistance that potentially start turning around again that's it for this week I hope you enjoyed the show and I'm looking forward to see you again next week same time same place