{"id":"PfabikgnD08","title":"Cryptographic Hash Functions with Evgeny Kapun","description":"Follow the latest from NEAR Protocol on:\nWebsite: https://near.org/\nDiscord: https://near.chat/\nBlog: https://near.org/blog/\nTwitter:   / nearprotocol  \nGitHub: https://github.com/near  https://github.com/nearprotocol\n#Blockchain #FutureIsNEAR #NEAR #nearprotocol","channel_name":"NEAR Protocol","published_at":"2021-09-08T00:00:00.000Z","thumbnail_url":"https://img.youtube.com/vi/PfabikgnD08/hqdefault.jpg","transcript_text":"yeah you can restart i hope hi i hope everyone sees my screen and if you have any questions please use raise your hand function in zoom and so this today i'm talking about cryptographic functions we are this is probably the most widely used cryptographic primitive in near we have many data structures mostly miracle trees but not all but also some other that are using them so what is a cryptographic hash function it is a function from strings of arbitrary lengths to strings of some fixed length where strings are sequences of some elements this function should behave like random function so ideally it like when described when proving something about her function sometimes we actually can replace it with a random function random function is such a function that its result for every possible input is uniformly distributed independently from all other inputs so for every possible input 3 input value it should provide some uniformly distributed hash value and also be the set from which input and output sequences are taken can be said a set of all bytes or bits and in fact mainly her function for example mda5 or sha all sha functions are defined in terms of bits rather than bytes so it is possible to use this function to hash sequences of bits which are not a whole number of bytes but only a small number of implementations actually support this but yeah for this reason if you look at the definition of this function you can see for example that they use message length as the number of bits because because they are designed to support any number of beats but some newer hash functions like blake 2 or blake 3 actually only support hash and whole number of bytes because that's what most users need so it should be like render and shoot work like random function and if it were a random function it would be very secure like for example a value of a hash function won't give you any information except that if you can guess the exact message that was hashed you can try to hash it again and you will get identical value but actual her functions have some different security properties or don't have so the first one of them the first image resistance which means that if you are given only the value of a hash function then you can't find any message which has the same hash and this is a property that pretty much every hash function actually possesses but there is also second pre-image resistance which means that if you have some message it should be difficult to find a different message which has the same hash value and then there is collision resistance meaning that it should be difficult to find any two different messages which have the same hash value and the final one is indifferentiability which is pretty complex so it means that her functions behaves in in a certain sense like a random function which all her functions are supposed to do but many don't so it the mathematical definition of indifferentiability is pretty complex but also when some the functions were designed the indifferentiability was not taken into consideration so those older function lack this property by design unlike the part where md5 md5 and sha1 lack collision resistance they were actually designed to be collision resistant but later they were broken and some ways were discovered to actually find collisions for those functions but they are still considered premature resistant and so these four properties are ordered from weakest to strongest so if a function doesn't have first premature resistance then it won't have any of the later properties as well and if a function doesn't have second pre-image resistant then it won't be collision resistant and if a function is not collision resistant then it won't be indifferentiable so later hash function because functions provide strictly more security than the earlier ones and so how her functions are implemented most hash functions are pretty much all her functions are based on a so-called one-way compression function which is a function that just maps some longer fixed length input to a shorter one this is because those fixed length functions are easier to design and it's easier to prove their security properties so to turn a function with the fixed length input into a function with the variable length input there is a so-called miracle dam guard comes construction which basically pads a message splits it into blocks and passes each block to a compression function together with the result of the previous call so there is some initial value which is called initial state and then it is updated with the message blocks and the final state is the resulting hash value and the message needs to be padded so that its length is multiple of block size and this padding suit should be designed in such a way that different messages are result in different padded messages so that there is no collision because of padding so for example if you just pad the message with zero bytes it won't be good padding because different messages which differ by adding zero bytes to the end may result in identical padded messages and then the hashes will be also identical so many hash functions solve this by appending message lengths to the end but there are other approaches unfortunately this construction has a weakness which is length extension attack so if you have a message you can if you know just hash of some message but not the message itself you can pad it then append anything and then take the result as a new message and you can compute its hash so how do you do this you know the output state of processing the initial message and the padding so you can take the state apply compression function a number of times and then you will get a new state builder did you don't ask something well yes i am i wanted to only ask why is that uh what kind what could happen if those kind of attacks are allowed yes so it depends on what you are using hash function for this attack doesn't violate collision resistance so if that's all that you need then you're fine but sometimes hash functions are used for authentication for example in some protocols to authenticate some request you need to pass a hash of some secret key plus that request and for this kind of usage length extension attack actually breaks its security because you can append some additional data to the request and compute so if you can intercept original request with its hash you can append some data and make modified requests with a hash that you also know even if you don't know the key so also this is one of the way in which hash function materially differs from random function because with the true random function you can't do this one of the functions which has a different structure is blick 3 unlike most functions it has a built-in miracle tree so it works as follows it split the input into chunks of length of one kilobyte each chunk is hashed normally sequentially and then there is a miracle tree on top of those chunks so this is done to improve it before its performance because different chunks can be hashed in parallel and official breakthrough implementation uses sim to actually do this it can hash it can compute up to 16 instances in parallel so if you have at least 16 kilobytes of data you can actually get the full performance yeah so but pretty much every other function uses simple sequential structure yes so the next thing i wanted to talk about is miracle trees we use miracle trees a lot so a simple structure just pair up the values hash concatenate the hashes then pair up the resulting values concatenate the hashes hash all of this what's good about miracle tree what the first thing is that it is as collision resistant as the hash function itself so only single root hash can be used to commute to the entire set of three values and you can't provide make a different set of values which will have the same hash another thing that is specific to miracle trees is that it is possible to provide short proofs of a specific element so suppose that you want to prove that the value d2 is in a in the tree with a given root hash you need in this case to provide only three different hashes and to and you also need to provide information about which which hash of the left child and which one is right child but this is very small amount of information then to check the hash the verifier needs to compute the hash of d2 then concatenate it with the hash of d3 and hash that then concatenated with the another hash and has that and then repeat this again and then the resulting hash must be equal to the root hash unfortunately this trivial implementation of merkel tree is not secure so depending on which values are possible as leaves it might be possible for an attacker to prove that some different value is present in the tree which wasn't included in the list of elements when the tree was created so there are two attacks one is extension so suppose that one of the data elements can be controlled by the attacker to some extent and they can make it look like a concatenation of two hash values then they can construct a proof that one of then the preimage of one of these values is actually a tree element so what they need to do they need to somehow make the value d2 in this example to have the same length as a concatenation of two hashes and they need to know a pre-image for one of those caches either the first one like in this example or the second one and then they can append this hash to this proof to make a false proof then some potential arbitrary value is present in the tree and the second attack works in the opposite direction so you can take an internal an internal node and try to make a proof that this node is a leaf node so you just truncate your proof remove one of the hashes from the end and you get also a valid proof for some value which is not actually in the tree so how to the defend against this attack there are two approaches one is to make the height explicit so for example one can make the three all leaves in the tree to be at the same depth and then include this depth and the heater somewhere next to this root the root hash and then the verification validation procedure must actually make sure that the number of hashes in the proof is correct there are more complicated ways for example if the depth is not the same everywhere but the tree has some fixed predictable structure and again whoever is verifying this proof has the necessary information to check that the proof ends at the right position exactly at the leaf node before and not after and the second approach is to disambiguate the internal nodes and the leaf nodes so to make just to make sure that they don't have identical serialization for example it is possible to prepend the byte to each node length depend by zero to internal nodes and by 1 to lymph nodes or do disintegrate them in any other way for example in many cases a leaf node cannot have the same length as an internal node and this is enough to prevent this attack because now it's not possible to misrepresent one for the other but this is something that should be considered because in near when i looked i didn't find any explicit countermeasures against those attacks but on the other hand i couldn't find any place where it can be exploited either so pretty much everywhere length of the leaf item cannot be exactly 64 bytes and the leaf of an internal node is always 64 bytes because it's just a concatenation of two hashes but maybe if we introduce some other hashtag it might be vernal vulnerable to this kind of attack so if you are designing any sort of curve-based data structure you should be aware of this and check if it can be attacked in a similar fashion and that's it do you have any questions no questions then thank you for watching i mean so what are the what are the pl so what are you planning to do next do you have any other ideas what are the possible improvements or what else we can investigate improvements for what i mean are there any other hash functions that could be used instead of the one that you mentioned you swear like are you saying about using a different function in near yes i have considered using different ones so currently we are using sha-256 mostly and i'm thinking about switching to either black 2 or black 3 are there any other besides black hash functions besides black 2 or black 3 that actually meet all those properties there are many functions that need the security properties if you are talking about this this group yes for example all sha-3 candidates are actually meeting all those properties because this is was one of the design goals for those 463 and i'm not aware of any of them being broken but black 2 and black 3 are the most popular of the newer her functions and i don't see a good reason to use any others i could consider other function if they were substantially better in some characteristic than those popular hash functions but i'm not aware of any other functions that are significantly better for our use cases okay that makes sense so basically you have chosen one that's currently seems to be the most computer so what's the difference between the black to our black tree blake 3 is a newer it is designed for so it has better performance it's designed for parallelism as i explained but in terms of security they're pretty similar also because blake 3 has the built-in miracle tree you can prove that some some sequence is a substring of a hashed message without providing the entire message yogurt do you have a question uh yes have you thought about suppose we want to change our function what happens with challenges on the border of changing i guess there is there wouldn't be any problem but uh but if you thought about it already can you say something about it i think it's the same as with any protocol change so if you are challenging a block that was using a different protocol version then you have to validate it using that protocol version that was in effect at that time any other questions well thank you for watching yep thanks","transcript_synced_at":"2026-11-04T04:10:41.125Z","segments":[{"start_seconds":10,"text":"yeah you can restart i hope hi i hope everyone sees my screen and","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=10s"},{"start_seconds":19,"text":"if you have any questions please use raise your hand function in","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=19s"},{"start_seconds":27,"text":"zoom and so this today i'm talking about cryptographic","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=27s"},{"start_seconds":35,"text":"functions we are this is probably the most widely used cryptographic primitive in","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=35s"},{"start_seconds":43,"text":"near we have many data structures mostly miracle trees but not all but also some other that are","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=43s"},{"start_seconds":52,"text":"using them so what is a cryptographic hash function it is a function from","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=52s"},{"start_seconds":60,"text":"strings of arbitrary lengths to strings of some fixed length where strings are sequences of some","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=60s"},{"start_seconds":69,"text":"elements this function should behave like random function so ideally it like when","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=69s"},{"start_seconds":78,"text":"described when proving something about her function sometimes we actually","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=78s"},{"start_seconds":86,"text":"can replace it with a random function random function is such a function that its","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=86s"},{"start_seconds":92,"text":"result for every possible input is uniformly distributed independently from","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=92s"},{"start_seconds":100,"text":"all other inputs so for every possible input 3 input value it should provide","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=100s"},{"start_seconds":108,"text":"some uniformly distributed hash value and also be the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=108s"},{"start_seconds":116,"text":"set from which input and output sequences are taken can be said a set of all bytes or bits","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=116s"},{"start_seconds":124,"text":"and in fact mainly her function for example mda5 or sha all sha functions","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=124s"},{"start_seconds":132,"text":"are defined in terms of bits rather than bytes so it is possible to use this","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=132s"},{"start_seconds":140,"text":"function to hash sequences of bits which are not a whole number of bytes but","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=140s"},{"start_seconds":148,"text":"only a small number of implementations actually support this but","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=148s"},{"start_seconds":155,"text":"yeah for this reason if you look at the definition of this function you can see for example that they use message length","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=155s"},{"start_seconds":163,"text":"as the number of bits because because they are designed to support any","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=163s"},{"start_seconds":171,"text":"number of beats but some newer hash functions like blake 2 or blake 3 actually","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=171s"},{"start_seconds":179,"text":"only support hash and whole number of bytes because that's what most","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=179s"},{"start_seconds":187,"text":"users need so it should be like render and shoot","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=187s"},{"start_seconds":194,"text":"work like random function and if it were a random function it would be very secure like for example a value of a","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=194s"},{"start_seconds":203,"text":"hash function won't give you any information except that if you can","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=203s"},{"start_seconds":210,"text":"guess the exact message that was hashed you can try to hash it again and you will get","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=210s"},{"start_seconds":217,"text":"identical value but actual her functions have some different","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=217s"},{"start_seconds":226,"text":"security properties or don't have so the first one of them the first image","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=226s"},{"start_seconds":232,"text":"resistance which means that if you are given only the value of a hash function then you can't find any","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=232s"},{"start_seconds":242,"text":"message which has the same hash and this is a property that pretty much every","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=242s"},{"start_seconds":248,"text":"hash function actually possesses but there is also second pre-image resistance","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=248s"},{"start_seconds":255,"text":"which means that if you have some message it should be difficult to find a different message which","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=255s"},{"start_seconds":263,"text":"has the same hash value and then there is collision resistance meaning that it should be difficult to","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=263s"},{"start_seconds":270,"text":"find any two different messages which have the same hash value","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=270s"},{"start_seconds":277,"text":"and the final one is indifferentiability which is pretty complex so it means that her functions","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=277s"},{"start_seconds":286,"text":"behaves in in a certain sense like a random function which all her functions are supposed to do but","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=286s"},{"start_seconds":295,"text":"many don't so it the mathematical definition of","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=295s"},{"start_seconds":302,"text":"indifferentiability is pretty complex but also when some the functions were","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=302s"},{"start_seconds":311,"text":"designed the indifferentiability was not taken into consideration so those older function","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=311s"},{"start_seconds":320,"text":"lack this property by design unlike the part where md5 md5 and","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=320s"},{"start_seconds":328,"text":"sha1 lack collision resistance they were actually designed to be collision resistant but","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=328s"},{"start_seconds":335,"text":"later they were broken and some ways were discovered to actually find collisions for","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=335s"},{"start_seconds":344,"text":"those functions but they are still considered premature resistant","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=344s"},{"start_seconds":351,"text":"and so these four properties are ordered from weakest to strongest so if a function","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=351s"},{"start_seconds":360,"text":"doesn't have first premature resistance then it won't have any of the later properties as well","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=360s"},{"start_seconds":369,"text":"and if a function doesn't have second pre-image resistant then it won't be collision resistant and if a function is","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=369s"},{"start_seconds":378,"text":"not collision resistant then it won't be indifferentiable","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=378s"},{"start_seconds":386,"text":"so later hash function because functions provide strictly more","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=386s"},{"start_seconds":394,"text":"security than the earlier ones and so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=394s"},{"start_seconds":403,"text":"how her functions are implemented most hash functions are pretty much all her functions are based","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=403s"},{"start_seconds":411,"text":"on a so-called one-way compression function which is a function that just maps some","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=411s"},{"start_seconds":419,"text":"longer fixed length input to a shorter one this is because those fixed length","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=419s"},{"start_seconds":426,"text":"functions are easier to design and it's easier to prove their security properties","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=426s"},{"start_seconds":435,"text":"so to turn a function with the fixed length input into a function with the variable","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=435s"},{"start_seconds":442,"text":"length input there is a so-called miracle dam guard comes construction","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=442s"},{"start_seconds":448,"text":"which basically pads a message splits it into blocks and passes each block to a","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=448s"},{"start_seconds":456,"text":"compression function together with the result of the previous call so there is some initial","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=456s"},{"start_seconds":462,"text":"value which is called initial state and then it is updated with the message blocks","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=462s"},{"start_seconds":471,"text":"and the final state is the resulting hash value and the message needs to be padded so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=471s"},{"start_seconds":479,"text":"that its length is multiple of block size and this padding suit should be designed","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=479s"},{"start_seconds":488,"text":"in such a way that different messages are result in different padded messages so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=488s"},{"start_seconds":496,"text":"that there is no collision because of padding so for example if you just","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=496s"},{"start_seconds":503,"text":"pad the message with zero bytes it won't be good padding because different messages which differ by adding","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=503s"},{"start_seconds":512,"text":"zero bytes to the end may result in identical padded messages and then the hashes will be also","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=512s"},{"start_seconds":519,"text":"identical so many hash functions solve this by appending message lengths to the end","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=519s"},{"start_seconds":528,"text":"but there are other approaches unfortunately this construction has a","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=528s"},{"start_seconds":536,"text":"weakness which is length extension attack so if you have a message","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=536s"},{"start_seconds":545,"text":"you can if you know just hash of some message but not the message itself you can","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=545s"},{"start_seconds":552,"text":"pad it then append anything and then take the result as a new message and you can compute its hash","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=552s"},{"start_seconds":561,"text":"so how do you do this you know the output state of processing the initial","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=561s"},{"start_seconds":570,"text":"message and the padding so you can take the state apply compression function","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=570s"},{"start_seconds":579,"text":"a number of times and then you will get a new state","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=579s"},{"start_seconds":587,"text":"builder did you don't ask something well yes i am i wanted to only ask why is that uh","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=587s"},{"start_seconds":596,"text":"what kind what could happen if those kind of attacks are allowed","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=596s"},{"start_seconds":603,"text":"yes so it depends on what you are using hash function for this attack doesn't violate collision","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=603s"},{"start_seconds":611,"text":"resistance so if that's all that you need then you're fine but sometimes hash functions are used for","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=611s"},{"start_seconds":620,"text":"authentication for example in some protocols to authenticate some request you need to","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=620s"},{"start_seconds":629,"text":"pass a hash of some secret key plus that request and for this kind of usage","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=629s"},{"start_seconds":638,"text":"length extension attack actually breaks its security because you can append some","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=638s"},{"start_seconds":646,"text":"additional data to the request and compute so if you can intercept original request with its","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=646s"},{"start_seconds":654,"text":"hash you can append some data and make modified requests with a hash that you","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=654s"},{"start_seconds":660,"text":"also know even if you don't know the key so also this is one of the way in which","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=660s"},{"start_seconds":671,"text":"hash function materially differs from random function because with the true random function you can't do this","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=671s"},{"start_seconds":685,"text":"one of the functions which has a different structure is blick 3 unlike most functions it has a built-in","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=685s"},{"start_seconds":694,"text":"miracle tree so it works as follows it split the input into chunks of length of one kilobyte","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=694s"},{"start_seconds":703,"text":"each chunk is hashed normally sequentially and then there is a miracle tree on top of those","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=703s"},{"start_seconds":712,"text":"chunks so this is done to improve it before its performance because different","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=712s"},{"start_seconds":721,"text":"chunks can be hashed in parallel and official breakthrough implementation uses sim","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=721s"},{"start_seconds":728,"text":"to actually do this it can hash it can compute up to 16","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=728s"},{"start_seconds":736,"text":"instances in parallel so if you have at least 16 kilobytes of data you can actually get the full performance","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=736s"},{"start_seconds":748,"text":"yeah so but pretty much every other function uses simple","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=748s"},{"start_seconds":755,"text":"sequential structure yes so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=755s"},{"start_seconds":764,"text":"the next thing i wanted to talk about is miracle trees we use miracle trees a lot","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=764s"},{"start_seconds":772,"text":"so a simple structure just pair up the values hash","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=772s"},{"start_seconds":779,"text":"concatenate the hashes then pair up the resulting values concatenate the hashes hash","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=779s"},{"start_seconds":786,"text":"all of this what's good about miracle tree","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=786s"},{"start_seconds":793,"text":"what the first thing is that it is as collision resistant as the hash function itself so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=793s"},{"start_seconds":801,"text":"only single root hash can be used to commute to the entire","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=801s"},{"start_seconds":808,"text":"set of three values and you can't provide make a different set of values which will have","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=808s"},{"start_seconds":816,"text":"the same hash another thing that is specific to miracle trees is that it is possible to","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=816s"},{"start_seconds":823,"text":"provide short proofs of a specific element so suppose that you want to prove that","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=823s"},{"start_seconds":830,"text":"the value d2 is in a in the tree with a given root hash you need in this case to provide only","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=830s"},{"start_seconds":839,"text":"three different hashes and to and you also need to provide information","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=839s"},{"start_seconds":847,"text":"about which which hash of the left child and which one is right child but this is very","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=847s"},{"start_seconds":855,"text":"small amount of information then to check the hash the verifier needs to compute the hash","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=855s"},{"start_seconds":863,"text":"of d2 then concatenate it with the hash of d3 and hash that then concatenated with the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=863s"},{"start_seconds":871,"text":"another hash and has that and then repeat this again and then the resulting hash must be","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=871s"},{"start_seconds":880,"text":"equal to the root hash unfortunately this trivial implementation of merkel tree is","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=880s"},{"start_seconds":889,"text":"not secure so depending on which values are possible as","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=889s"},{"start_seconds":896,"text":"leaves it might be possible for an attacker to prove that some different value is present in the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=896s"},{"start_seconds":905,"text":"tree which wasn't included in the list of elements when the tree was created","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=905s"},{"start_seconds":912,"text":"so there are two attacks one is extension so suppose that one of the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=912s"},{"start_seconds":920,"text":"data elements can be controlled by the attacker to some extent and they can make it look like a","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=920s"},{"start_seconds":928,"text":"concatenation of two hash values then they can construct a proof that one of","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=928s"},{"start_seconds":935,"text":"then the preimage of one of these values is actually a tree element so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=935s"},{"start_seconds":943,"text":"what they need to do they need to somehow make the value d2 in this example to have the same length as a","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=943s"},{"start_seconds":951,"text":"concatenation of two hashes and they need to know a pre-image for one of those caches","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=951s"},{"start_seconds":958,"text":"either the first one like in this example or the second one and then they can append this","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=958s"},{"start_seconds":966,"text":"hash to this proof to make a false proof then some potential arbitrary value is present","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=966s"},{"start_seconds":975,"text":"in the tree and the second attack works in the opposite direction so you","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=975s"},{"start_seconds":981,"text":"can take an internal an internal node and try to make a proof that this node is a leaf","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=981s"},{"start_seconds":990,"text":"node so you just truncate your proof remove one of the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=990s"},{"start_seconds":996,"text":"hashes from the end and you get also a valid proof for some value which is","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=996s"},{"start_seconds":1004,"text":"not actually in the tree so how to","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1004s"},{"start_seconds":1012,"text":"the defend against this attack there are two approaches one is to make the height explicit so","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1012s"},{"start_seconds":1020,"text":"for example one can make the three all leaves in the tree to be at the same depth","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1020s"},{"start_seconds":1028,"text":"and then include this depth and the heater somewhere next to this root the root hash and then the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1028s"},{"start_seconds":1035,"text":"verification validation procedure must actually make sure that the number of hashes in the proof is correct","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1035s"},{"start_seconds":1045,"text":"there are more complicated ways for example if the depth is not the same everywhere but the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1045s"},{"start_seconds":1053,"text":"tree has some fixed predictable structure and again whoever is verifying this proof has the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1053s"},{"start_seconds":1061,"text":"necessary information to check that the proof ends at the right position","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1061s"},{"start_seconds":1069,"text":"exactly at the leaf node before and not after and the second approach is to disambiguate the internal nodes and the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1069s"},{"start_seconds":1078,"text":"leaf nodes so to make just to make sure that they don't have identical serialization","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1078s"},{"start_seconds":1086,"text":"for example it is possible to prepend the byte to each node length depend by zero to internal nodes and by 1 to lymph","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1086s"},{"start_seconds":1095,"text":"nodes or do disintegrate them in any other way for","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1095s"},{"start_seconds":1103,"text":"example in many cases a leaf node cannot have the same length as an internal node","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1103s"},{"start_seconds":1111,"text":"and this is enough to prevent this attack because now it's not possible to","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1111s"},{"start_seconds":1118,"text":"misrepresent one for the other but this is something that should be considered","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1118s"},{"start_seconds":1126,"text":"because in near when i looked i didn't find any explicit countermeasures against those","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1126s"},{"start_seconds":1136,"text":"attacks but on the other hand i couldn't find any place where it can be exploited either","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1136s"},{"start_seconds":1144,"text":"so pretty much everywhere length of the leaf item cannot be exactly 64 bytes and","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1144s"},{"start_seconds":1153,"text":"the leaf of an internal node is always 64 bytes because it's just a concatenation of two","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1153s"},{"start_seconds":1160,"text":"hashes but maybe if we introduce some other hashtag it might be","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1160s"},{"start_seconds":1169,"text":"vernal vulnerable to this kind of attack so if you are designing any sort of","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1169s"},{"start_seconds":1178,"text":"curve-based data structure you should be aware of this and check if it can be","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1178s"},{"start_seconds":1186,"text":"attacked in a similar fashion and that's it","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1186s"},{"start_seconds":1193,"text":"do you have any questions","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1193s"},{"start_seconds":1207,"text":"no questions then thank you for watching i mean so what are the what are the pl","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1207s"},{"start_seconds":1216,"text":"so what are you planning to do next do you have any other ideas what are the possible improvements or what","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1216s"},{"start_seconds":1223,"text":"else we can investigate improvements for what i mean are there","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1223s"},{"start_seconds":1231,"text":"any other hash functions that could be used instead of the one that you mentioned","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1231s"},{"start_seconds":1241,"text":"you swear like are you saying about using a different function in near yes","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1241s"},{"start_seconds":1249,"text":"i have considered using different ones so currently we are using sha-256","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1249s"},{"start_seconds":1257,"text":"mostly and i'm thinking about switching to either black 2 or black 3","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1257s"},{"start_seconds":1266,"text":"are there any other besides black hash functions besides black 2 or black 3 that actually meet all those properties","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1266s"},{"start_seconds":1276,"text":"there are many functions that need the security properties if you are talking about","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1276s"},{"start_seconds":1284,"text":"this this group yes for example all sha-3 candidates are","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1284s"},{"start_seconds":1292,"text":"actually meeting all those properties because this is was one of the design goals for","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1292s"},{"start_seconds":1299,"text":"those 463 and i'm not aware of any of them being broken","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1299s"},{"start_seconds":1307,"text":"but black 2 and black 3 are the most popular of the newer her functions and i","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1307s"},{"start_seconds":1315,"text":"don't see a good reason to use any others i could consider other function if they were","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1315s"},{"start_seconds":1324,"text":"substantially better in some characteristic than those popular hash functions but i'm not aware of","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1324s"},{"start_seconds":1332,"text":"any other functions that are significantly better for our use cases","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1332s"},{"start_seconds":1340,"text":"okay that makes sense so basically you have chosen one that's currently seems to be the most computer so what's the difference between the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1340s"},{"start_seconds":1347,"text":"black to our black tree blake 3 is a newer it is designed for","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1347s"},{"start_seconds":1356,"text":"so it has better performance it's designed for parallelism as i explained","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1356s"},{"start_seconds":1365,"text":"but in terms of security they're pretty similar also because blake 3 has the built-in","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1365s"},{"start_seconds":1374,"text":"miracle tree you can prove that some some sequence is a substring of a hashed","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1374s"},{"start_seconds":1382,"text":"message without providing the entire message","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1382s"},{"start_seconds":1389,"text":"yogurt do you have a question uh yes","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1389s"},{"start_seconds":1394,"text":"have you thought about suppose we want to change our function what happens with challenges on the","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1394s"},{"start_seconds":1402,"text":"border of changing i guess there is there wouldn't be any problem but uh but if you thought about it already can","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1402s"},{"start_seconds":1410,"text":"you say something about it i think it's the same as with any protocol change so if you are","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1410s"},{"start_seconds":1417,"text":"challenging a block that was using a different protocol version then you have to validate it using that protocol","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1417s"},{"start_seconds":1425,"text":"version that was in effect at that time","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1425s"},{"start_seconds":1448,"text":"any other questions","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1448s"},{"start_seconds":1463,"text":"well thank you for watching yep thanks","url":"https://www.youtube.com/watch?v=PfabikgnD08&t=1463s"}],"youtube_url":"https://youtube.com/watch?v=PfabikgnD08","url":"https://near-pedia.xyz/videos/PfabikgnD08"}