Devcon 5 - Ethereum Swarm Breakout Session: When Merkle Met Entanglements - 8.10.2019

okay hello everybody i am associate professor at university of estabango rossin is a phd student from the same university today we talk about well-market entanglements so in this talk i will talk about redundancy people systems about our collaboration with swan and the prototype that frazzin is working on use of size redundancy and then the impact of redundancy in the market raise something that removes so our motivation is to store a document for long term in a decentralized system do you think you can recover a file after a decade or more with current redundant mechanisms it's a bit of a challenge so this is one there's many many cutes these those sound notes and uh but these beasts may decide to be free at some point and some may fail or disappear and so it's a failure the failure happens so what happens if you have your family that know that just suddenly disappear you will be very sorry for that so i will talk about three different approaches to achieve redundancy in a building's existence basically they are like well-known man for somehow that's i call it the more the better and the less the and then i will talk about my word this is this was developed during my phd in terms codes okay so let's go to replication replication is very easy just copy the file it's a straightforward but it has expensive space requirements because you need to complete the whole file and it's not good for long-term storage especially because for instance in in swan when you are seeing the files uh or you know if you have be a network when basically when you are copying uh blogs it's your copy of blogs that are popular but in long-term restoration something that is a document that is your personal document nobody cares okay yeah you can use a device but still you need some some redundant method that is appropriate for long-term storage so here is a block that is missing so then in this in this way with replication basically you have two different uh with the three copies you have two different small ways to record them and when you distribute this this file and these free replicas yeah okay there's some notes that participate in this and when they when one audience disappears so these nodes can can give you the file that is missing without any decoding without any repeats just a straightforward in erasure coding i will talk about amount of end blocks what does it mean so basically you have the file and instead of just storing the file you split the file in blocks in m blocks and with some magic base of arithmetics of doing detailed fields you create more redundancy with this redundancy you can save with this with this approach you can save a space requirements but this is very expensive with repairs and with the maintenance in the system because you always need to read envelopes to recover the file and so okay again you need you have some parallels some other ways to record the file but these are involved many blocks and here in this case we distribute the blocks uh so instead of of the original replica that we have in replication we split in four fragments we generate some redundancy so they are like more more peers involved in the repairs and you see that if one of this is missing you have you have to found four other peers that are available to recover those you can increase so in this previous example you can tolerate up to three failures then how do you impressive for tolerance okay you can subdivide this initial fragments and then you generate more uh more redundant fragments and uh but this in this case we are with the same space of our head and now there are more more nodes involved but the problem is that we are also increasing the number of peers that need to be available to do the repair and this is a problem in the other networks or if for instance if the if the system is under attack or other or if they have low availability this node so this is this is not good so what will happen with the dynamics internal the main idea is that you mix the file with other files in the system or you mix the blocks of your file with other blocks of your file and how do we do it with an is this is based on operations so it's it's much cheaper operation than the caliber fields and is uh and it's very simple like is xor into your your block with alpha other blocks and that will generate alpha locks but because this is part of a system that is all entangled together then you can use other blocks out of this alpha and alpha other blocks that can be used during the remains so the good thing about alpha dynamics is that repair cost is constant no matter the the alpha that you use you will always need two blocks for repairing one single failure and the storage overhead is is given into the alpha blocks that you're generating and photographs grows exponentially with this alpha blocks because now when the when the block is missing you will have this path of two blocks or this path of two blocks actually alpha path of this but then you will have more and more as a larger path to recover the the develop if there is a big failure that is affecting the system crossing we'll talk about entanglements first so in this case we have now we have an equivalent block that is equivalent to the replication and now if it's if the block is missing because the vr is not there so we will use only two nodes and you will see you see now that we have blue that are the direct blocks and that were generated during the entanglement but there are also many other blocks that were already stored in the system or they were stored later in the system that can be used during this repair process so that increases the the that increases the the number of peers that can participate during repairs and the possibilities and we are distributing more the information and that's actually good and uh and also if we want uh to increase even more uh the involvement of of of the peers in the system we can instead of using uh this this size we can use a small block uh so that we split the again the original blocking four fragments and then we with this in this way we are using the same expression for our kettle as the previous example but now we are basically distributing the file in many many more peers and then the repairs can be parallelized better can be can can be done in a more efficient way so in a nutshell so here are replicas and replicas you always need so like peer availability requirement is something that is not that is not good so so so replicas are the best because it's just one one bill that you need uh in entanglements you always need two peers for doing the repairs and in the traditional eraser cause it depends but s is m but we can also as as i showed in the previous slides we can increase the block distribution in in the large number of peers which is something positive but in the case of erasure codes uh the in this way growing in this way requires more storage of our head and but with entanglements yeah we can use small blocks and without increasing the stars and uh last thing we'll talk about this demo so i'll go through the prototype very briefly and then show you a demo of the repair algorithm and show some results so in a nutshell this is how the traditional or parallel offloading this one is now that the entire file is sent to some small node it might be your own strong node and then you this changes the file into 4k and the file is synced across the network so what we did in our prototype is that we had implemented an additional layer and gold which splits the file into 4k and adds the encoded blocks according to the redundancy scheme and this is sent to the swarm node in the same way and synced across the network but in the when once the nodes receive the file the user gets back the manifest hash which is it keeps in a collection uh because this collection is then used when the user wants to restore the file because it has the information about what is the data what is the purpose so i will show you the demo here so this this shows all the data blocks in the whole file so total 115 data blocks and then the coloring downhills means the red ones will be unavailable and unavailable means that it could not retrieve the file within one second so it doesn't distinguish what kind of pair they said we can't get the data within one second it's a failure then the blue ones it's repaired and the green is done so it starts off by this coloring cup and as you can see there's some which is already red but when it goes to number 49 59 so this is event 459 it requests a parity clock for number 25 which we will use to repair later on but also what can happen is that the parity can also fail so the algorithm keeps running and on number 41 you see that the one block is data block is repaired using these two parities on the side and then if we go to 160 yeah so here you have a case where there's two parities after each other which is fair and what the algorithm does here it first prepares the parity which is further away and now it can repair the one it needs and then now it has the sufficient information to repair the and this keeps running until all of the blocks are either gray green or blue and then terminates so to go back to the presentation here we also have done some uh evolutions and here we inserted errors of 5 and 15 and we used one prototype with entanglement force and one prototype with solomon and again it's this one second failure that if you cannot achieve the block within one second it's a failure this is what we see in return so this is the result for a file of one megabyte and as you can see the for the baseline swarm the entanglement scopes are performing better there and we believe that this is because we are only connecting to one single uh swarm node when we are retrieving the file and then this has some limit on concurrency but with our prototype we are sort of overloading this currency then because we're issuing all of the requests in parallel and the results with the reinstallment they are also not too good because we this is like we need to do some more work on the implementation there and we also think this will be more reduced if we run swarm nodes ourselves but the main takeaway here is that we can implement user side redundancy and even with relatively high amounts of failure it doesn't have any costs in the download time so next step system side redundancy so what's happening if we move redundancy to the network to system uh what we are interesting now is how how these marketplace are affected also with redundancy and so then when you have uh if you're storing data off chain uh like if you use one to store that off chain usually uh you can create a mercury and this is include the root of the merkel reading block in the blockchain or in ethereum so so here we have the data block at the leaves of the tree and all these other blocks are basically hashes so and this is interesting because we can do an efficient content verification also if we want to know that this vlog is part of this market read this blog it's part of the fight that i'm going to download so i need to only uh verify with some some some more blogs uh hedge but how this american dream is modified when we introduce redundancy uh so well when we are using replicas this basically is not modified because unless we are inserting some tag or label to this replica i mean the replica is identical so we have exact exact hashes under what will be exact so no modification when we are using erasure codes basically the mercury grows to all directions because first we if we we we will have more leaves because we will have the the encoded blocks and then we will have more crashes and then basically it's also increases in kind and there are also some other challenges that that that we have seen in previous implementations in tahoe and also in the heat condo when they are using erasure costs that need to be careful because there are some some kind of attacks that you can like for instance include a second file uh here in the in the goats and and they will have the same uh the same route balance so it's not them to discuss this anyway with entangled blocks the thing is that because in the way that the the the process is done the coding is done basically we are creating a kind of a chain of entangled blocks and this chain is basically if you absorb every uh two consecutive blocks these two consecutive blocks will represent exactly the original data block so so as as you see like in this case the first one is equivalent to this one but this one can be regenerated with two blocks and this one with these two on this one exactly and we have actually uh multiple layers that you can do like this so basically you can play in the plantation so to avoid modifying the mercury but because because of this property of the entire we didn't go further than this but we are thinking in this for for previous implementation for next implementations so concluding remarks swans is ambitious to provide long-term storage so it needs to combine different redundancy methods to to to to to provide a service to to write different services and so at the moment it only adds replication and the address the thinking process and and it's considering implementing the erasure coding and an endowment so towards this goal we show how it how can we add entanglements is at the user side and we show some some measurements about this and then we expect to complete this continue with this work and apply anonymous after facing it inside the note so that's all for it for today [Applause] any questions so could we go back to the slide with the purple tree yes so the green the green blocks the green chunks which weren't the merkle tree are the yeah those ones are they in any way uh protected against laws because they are just regular like the sworn network does not distinguish between blue and green chunks it doesn't know which one is green which one is blue the chunk is a challenge yes so do you are you considering some redundancy for the green ones as well yeah that's what we discussed in the in when we went to madrid for the strong summit that we could increa also include the maiden dynamics at this house but but we are actually at that moment we are not sure if that will be necessary i mean the the the storage extras of our head for doing this entanglement adding redundancy here it will be not much but about but it adds complexity to to do those no and but on the other side because these are well protected you can regenerate all these because basically this is the hash so if you can recover this because you have you have a very high fat tolerance because you have you can't find that that's how you that's how you retrieve a file you basically start uh they don't know how to regenerate they don't know which notes it takes to regenerate it if you just ask for like give me this hash and it's missing you you access the file from the root that's how you need to compact each other yeah that's the best that that's true i mean for for no for locality your exit from here and and and yeah my talk here focus actually on the verification of this of uh if this block belongs to a certain file or that if it is for localities yes you need uh you really need to add this uh extraordinary we are running already late so let's go for the last question yeah so i i just kind of assume that the context of entanglement as to like what can be obtained with what is like that's like this is soon to be like application specific to not necessarily like a global the the uh it depends on how do you implement and one way could be like the the the node that uploads the the content just has in memory some last like like for instance with this example that we did it's like 15 blocks in memory and keeps doing the entanglement with these last blocks and keeps always india that's one way the second way will be if you want to entangle with with blocks that are in the system then you need to download like free blocks for it or you can keep it like like you maybe you don't need to download if you have a pool of like blocks that you were already thinking before and reuse this pool to do that and automatically you are entangled your file with other blocks in the system yeah so i guess my question is if like i'm a node on this network am i going to know the context of the entanglement of what i'm storing or will i just not know well this can be encrypted this is you don't know is is that what you're asking we can discuss we are running thank you so much again