The Blockchain Virus: Can a blockchain pay to replicate?

[Music] okay my name is Sergio Leone learner and I'm if you find and if you part of the Syrian community since its beginning when I did the first security audit of the code and design and currently I work for a company called SK labs which is developing an incompatible sidechain to Bitcoin but today's talk is about a research I did a couple of years ago that applies both to aetherium and towards K and to any other blogging platform so the talks name is the blockchain buyers can a blockchain pay to replicate can a blockchain itself pay for all their seed it needs to survive like a norges organism or it could have been called how to war full nodes or it could have been called how to create a reward based peer-to-peer file sharing system control entirely by smart contracts by no additional blockchain okay so first of all I'm gonna talk a little bit about the centralization because we wouldn't be here if not because we appreciate this in translation and any attempt to build a cryptocurrency or smart contract platform in the past that was centralized just fail okay so this is what we must stand this is what we must try to to to keep so why is this in transition so important well it brings back the power to the people so it means a lot of things like people being able to audit their payments disintermediation having open access no central control no monopolies no central point of failure and of course censorship resistance and corruption resistance these are very very important properties of our net so how do we promote the centralization well first we have to identify and measure it and then we can see how can we improve it so one of the ways is increasing the number of independent implementation developers full nodes okay and another way is by reducing the cost of running a full node because as the network scales the cost of running a full node increases so if I have to depend on a third party to know about my transactions then the network is going to be centralized and last the actual full node topology is very important if I take a node out and then the network's disrupt or disconnect then of course this is not a good decentralized network but we can see that in all kind of ways that we can improve the centralization it's very very important to have full nodes we cannot live without full nodes and have the centralization so what is the fool now anyway okay a full no it does a lot of services to the network it broadcasts blocks transactions it also hides the notes IP so we don't give an attacker the possibility to gather all information about the network and do partition attack source denial of service attacks also a node provides filtering services for light clients and of course the most important function it has a copy of the state and the blockchain to serve to new nodes that want to put strap and you know sync with the network but what are the incentives to run a full node currently there are not okay so currently is quite cheap so we do it but in the future we don't know so anything we can do to reward full nodes will foster the centralization so how can we do this well there are very simple ways but most of them do not work for instance we can create peer-to-peer pair space services like creating a micro channel for one no to appear then I can easy or probabilistic payment which also works and then I can't just ask for a block and then you give me the block I make you as very small maker payment well the problem with this setup is of course that we can have proxy nodes and proxy nodes can you know charge a little more and just forward the request to another node and so they just are there to you know they don't know contribute to the centralization it just make the network be more expensive some other cryptocurrencies and other networks rely on some calls something called master node of course this master node regulary ping nodes so they can vote so which nodes have to be rewarded this of course has a lot of problems with centralization these nodes are centralized and also these nodes gather a lot of information about the I piece of the nodes which is something we want to avoid so I will present a third way of doing this and the interesting thing is that this is a communication between smart contracts and full nodes without any other user or external system intervention so basically there is a smart contract that will say something like this give me a proof of work that proves with high probability that you store in your own house hard disk a copy of the blockchain okay or that you are so irrational that you are willing to buy a lot of hardware just to fake this proof but you will spend more more money than just buying the hardest to store the file ok and I will tell you if nobody else finds that you have cheat so if the fool node a submits a proof in transaction data then an our full node can come as you know this proof is fake and the smart contract can evaluate this proof this proof must be able to be evaluated with very low amount of gas and can keep a pretty posit it's per deposit and reward be for providing that useful information so in to summarize we want a node to be able to prove to all remaining nodes in the work that he is storing the blockchain okay so the benefits are obvious we can detect proxy nodes we won't pay proxy nodes and we don't require any special change to the network for the nodes that won't want to participate and maybe the drawback is that we are not actually proving we are serving the blockchain we are proving we have a copy of the blockchain but since we have a copy of the blockchain we are in sync with the network almost sure we are serving it and the cost of serving it will be small so to to manage to do it we are need we need some cryptographic protocols okay so these are the previous attempts to do this kind of things so we have provable data possession which allows you a verifier to send some data to a server and then challenge the server to see if this data is still there also we have proved over to ability where the thing very fiery can also have certain assurance that you will be able to recover this information in the future these two are called proof of storage so I will present a protocol very simple protocol which is I called proof of unique blockchain storage that it's a proof of storage scheme but also allows you to ensure that the other party the server has an actual copy of this file okay so it means that this file will be related to some some identity okay so the same file cannot be related to two identities so it is interesting that this year file coin presented as very similar proof that they call proof of replication and that I also publish a couple of years ago and it's kind of the same idea but it's worse and I will tell you later why it has many problems so in a nutshell we take the file we want to prove possession and we will encode it together with an identity and this identity will be generally your node address your film address or our skater dress so what we need is as decoding is fast but it should only be fast enough you know for not to interfere where your network operations on the contrary appending and updating will be a much slower operation but again not slow enough to interfere with operations the property is that when you encode the file and you encode a second file there is nothing to share in these same codings so the server will engage in a challenge response protocol with a verifier and he will use the encoded data not the uncut decoded data but just encoded data and we'll it must be irrational from the economic point of view to do anything else like relate to another party or like having a supercomputer or whatever so this is how the peer-to-peer protocol goes without without smart contracts so there is a harness verify say give me the hash of n Cellular randomly selected blocks of the file and that had been encoded with your node address and please do it in less than one second so the consumer has the information just put the information to memory and hash it and it works now if there is a malicious prover he can think of two things okay first he can think okay I'm gonna relay the same query the same challenge to another party but the problem is that there is the response you will receive is related to another identity so he's not going to get paid she's just going to be paying another party if he wants to redo this encoding it the problem is that it takes a lot more than one second okay so in a sense he cannot fake a proof so to create this asymmetry we did we need something I call practical and symmetric time encoders or parties so we have a program which is an encoder we have another program which is a decoder for a certain Turing machine and we define the steps this program performs as the number of step it requires to run for a random input until it halts and we will ask that this steps function is mostly uniform so with we we said that we have two programs and we said that the coding if you if i encode an input and I decode it I the same input so we define the asymmetry ratio as the number of steps it takes to the code divided by the number of steps it takes to encode so the desired properties at of course the program must be small and if I if there is any other party that encloses a mapping then this function this sorry this encoding must be relatively equally efficient efficient okay and to guarentees we need to rely on some complexity assumptions or number theoretic assumptions to make sure that the encoding that we peek is one of the fastest encoding Possible's for that mapping also we want as I said that the coning and encoding this piece will be practical for our application and we want the highest possible ask me to rate you because that is going to protect us from the attacker trying to encode on-the-fly well there is a function that has these these properties it's called the pollak Hellman cipher private key cipher is a very very old one of the first number theoretic encryption systems it works like this - well in this case it's the opposite decryption would be like encoding but so to decode a value we just rise it to the third power modulo P Prime and B prime and to encode it we will raise it to a value U which has approximately and bit which is the inverse of the three models P minus one so we get this encoding the coding property so using the standard Square and multiplayer algorithm encoding will take 1.5 times n multiplications while the coding takes only three multiplications so the asymmetry ratio here is an divided by 2 okay so we can make this asymmetry ratio as as large as we want just by taking a prime which is you know larger so what are the practical parameters that we can choose that serve this purpose okay I tested it in my laptop with a lib GMP so for N equals 2048 this is a bit little bit technical but please follow me exponentiation takes two point eight milliseconds while three multiplication takes only 3.6 microseconds so the theoretical asymmetry ratio is approximately 1,000 what I measure is approximately 7077 so now think about the Bitcoin blockchain okay so we get one megabyte block every 10 minutes and it takes only 11 seconds to encode it so it works perfectly for Bitcoin and it was also perfectly for our SK and if I receive you and the coding is really fast you get third 71 megabytes per second so that is not going to interfere with your node operations if you want to get a higher symmetry ratio you can take an equal twenty K and you see RB in the bones that you can still use for encoding your blockchain so this this is the one time duction encoding step you take your blockchain or your file and you split it in and beat chunks and then you scramble each one with your node address and this scrambling is can be very simple can be just soaring with a full domain hash of the of the node address and then you encode it with your slow function so this is what a typical proof of storage looks like you have some kind of memory bone problem because you want to prove you have a lot of lot of data and you transform it into a disk i/o problem like this you take a seed the verifier will will send you a seed and from that seed you derive a number of positions in the file and then you will just access those positions and and build a hash okay well the problem with all these constructions is that they depend on this technology so if I use SSD then the parameters are completely different if I use a hardest and also these disk characteristics properties change all over so this is what we really do we first do the step of encoding and creating this asymmetry and then we received from the verifier in this case is the poops contract the proof of unique blockchain storage contract we receive a z0 with this is zero we will take some parts we will derive some indexes some parts of the blockchain or at the file and we will bring all these into RAM ok so we are independent of the technology the disk access technology and this is the challenge response preparation phase now we have we received from the smart contract like 20 seconds later and second seed ok sit one and well from seed one we will derive these indexes of RAM where we will take these small pieces small blocks and hash them okay well we have transformed this memory bound problem into a CP bone problem well there is some important problem here that we cannot do this from a smart contract is that the block interval can be about 10 seconds 20 seconds so the number K the number of pieces we have to hash to prevent an attacker doing these encoding on the fly' will be very very high okay like in the order of 20 20 thousands or maybe more so the proof that we get is very large and the smart contract won't be able to you know with the gas limit to to evaluate if it is correct or incorrect so we change the last part and we transform a CPU bone problem into a memory bus IO problem and this has been done oh this has been done in Parma coin for instance the same the same procedure so instead of taking a large number of blocks to hash we take only 40 but we request that the hash that we obtain has proof-of-work okay so we will try many many times like deriving new seeds from the seed 1 and a nonce you know try a lot of times maybe 20 seconds ten seconds until we'll get one that has this property of the proof-of-work so this is how the whole protocol works and it's very very simple so in the step zero we have this one time encoding but we also have that who knows we'll register with these proofs smart contract and this can be they don't have to reveal their IP they just have to register RSK or receive your address to be paid also they will do some pre deposit because they are going to be penalized if they present an embolic proof so in step one the post contract will derive the seed zero from the block cash and we give the nodes enough time to bring all these pieces or a big piece into Ram so in step three because the proofs contract will derive as it won and now the competition begins that it's not the competition is cooperation actually but the full nodes will try to get this proof of work will try to get from all proof candidates we try to find one that matches that has a time much that whose cash is lower than the proof of work target so they will submit these proofs to the blockchain in normal transaction there will be plenty of time like six six blocks ahead to prevent censorship so that they can do that and in step six that there is a deadline for this and then an external challenge phase begins in this phase who knows we'll try to see if the other nodes are we are cheating so they will pick the nonce and then the hash that has been commit from other who knows and we'll reevaluate their that those proofs but since there are only 40 elements then it takes about 100 milliseconds so they can just evaluate every every other full nodes with commitment if one of them finds that ham someone has cheated then it just says a fraud proof to the blockchain to the pub smart contract which is just the full expansion of these of this proof cushion which will show if the original commitment was correct or right so in step 9 there is a end deadline for proof submission for fraud to submission and then there Wars has been paid of course they are oh they're only going to be paid to the nodes that are behaved honestly so because the the were what is going to be shared knows who knows are also incentivizes incentivize to detect cheaters now what's the difference I said before that this protocol can be used to prove any file not just the blockchain the blockchain is the easiest one because the node already has a copy of the blockchain maybe so it can more easily evaluate things but it can be used to any file to create you know a file sharing system that you can reward node just to hold the data for you and multiple copies you can just create a contract that create hundred copies of the same information but there are some difference between the file college group of replication and proof of unique file storage proof of replication depends on the success time so it's difficult to tune for all kinds of discs and it gives you typical symmetries of about ten to a hundred so it's very easy that technology changes and then an attacker is able to to to fake proof on the contrary proof of unique file storage does not depend on access time and has typical symmetries between 1000 and 10,000 and also you can combine them so you get 10 times more you can combine 10,000 of a symmetry 8 your of of proof of unique block file storage and combine them we'll know 10 times more for proof of replication well the summary is that well the central asian the centralization is very very important in these networks and increasing or setting of a full reward for the first time we can incentivize the creation of new full nodes and keep the number of who nodes even if we request them to store 10 times more information and this proof of unique file storage and proof of unique blockchain storage allows you to prove that you have this unique copy of the file of the blockchain and the important thing is this can be done right from a smart contract with almost no gas consumption and also the proofs are very short it's just a hash and a nonce okay so these could be implemented in a fume or in our skate amaro well we're working on implementation and so when we open source you will be able to to play with it well thank you very much the organizers [Applause] you [Music]