Sharding with OmniLedger and NEAR | Stanford Blockchain Club

Captions as YouTube publishes them, usually machine-generated, so product and people names can be misheard.

1. 0:10

   yeah what we are talking about today is and I will show you this framework how you can do charting in a secure and decentralized way so before I start however I want to acknowledge my co-authors this is of course not a work that I did just on my own so there is a big team behind that research project most of which are my colleagues at the dailies lab at EPFL so there is lift area Nicholas Linus and then there is Ava she's our collaborator here in the u.s.

2. 0:49

   at Trinity College on the at the East Coast and then there is Brian who is the head of Diddy's yeah so I guess I can skip that so the talk is structured like that first of all I will give some motivation on why we want to actually do sharding then I will present our framework and the implementation evaluation results and then finally I will conclude so yeah first question actually to you guys so what so what are

3. 1:21

   people using blockchains for what are the the most common use cases payments speculation smart contracts okay what are people doing with smart contracts i SEOs yes what else cryptic it is yes exactly so and so people are playing games right so this is like a big deal on on many of these block chains and if you followed that space some time ago there was this infamous game called crypto kitties where you could trade digital cats on

4. 2:04

   the etherium blockchain and that game was so popular that it basically crowd over crowded the whole aetherium network so and there that shows like like a really critical problem in in this space that open block chains they don't scale very well right you have the first application that's somewhat popular and the whole network goes basically down in is unusable so now the question is like why why is that right what is the core problem here

5. 2:35

   and when you look at this one of the core problems actually is the the nakamoto consensus and that the nakamoto consensus is not very scalable per se it gives you a lot of robustness in resilience but in itself it's not very scalable so what are the what are the reasons okay so maybe I first like just briefly recap what what it does I guess most of you are familiar with that so in the nakamoto consensus the miners when when it's a proof-of-work chain they run

6. 3:10

   these crypto puzzles on on the next block and every time a miner solves one of these puzzles he is allowed to extend the blockchain so here in this example this yellow miner found a solution to that crypto puzzle and thereby he's broadcasting it to the network the other validators in the network check that the proof is correct and then they extend the copy of their of their blockchain and thereby you have a consistent linear

7. 3:43

   history so but as I already hinted that this approach has several drawbacks first of all in specifically in Bitcoin the time that it takes to find a new block is roughly 10 minutes right so that's a fixed parameter in the protocol specification so that means that any transaction a client issues takes at least 10 minutes until it appears on the blockchain and you receive a confirmation for that then when you

8. 4:16

   additionally look at the size of blocks these are 1 megabyte blocks and the combination of like a 10 minutes interval to issue a new block plus the size of one megabyte gives you a very low throughput so bitcoin is roughly on the order of 4 to 4 to 7 transactions per second and if you compare that that's roughly like what an Ikea does on a busy Saturday so that's certainly not enough throughput to maintain a global currency

9. 4:49

   another problem that's that's coming from the way how Nakamoto consensus reaches consistency is that it's only a probabilistic process to reach this consistency meaning that here in the last part of the of the chain Forks still might happen because miners here in the network might find blocks in parallel and thereby you have for some time a split or a fork in in the blockchain so and when you do the math

10. 5:23

    then you then you see that the probable is the probability falls off exponentially the more blocks you add to to a given fork and to be really sure that your transaction is confirmed you need at least six blocks you need that your transaction is six blocks deep in the in the chain to say with some very high probability that no other fork will fork off here of your chain so that

11. 5:56

    means overall that to be sure that your transaction is committed you need to wait at least one hour and then of course there's also proof of work mining because yeah these cryptic puzzles are basically just a brute-force approach to find a a hash value of a certain shape and this of course wastes a huge amount of energy so in this talk we will be focusing mostly on the first three topics and proof of work we will not

12. 6:27

    discuss that further right so okay now we've seen so this is not very scalable right you have huge latency you have bad throughput so when you come from like a cloud computing background maybe then you will see okay let's just throw more hardware at the problem and we get more scalability right that's how many of the cloud computing companies work but here it not as easy right you could add more notes more validators or miners here but that doesn't change the fact that that

13. 7:04

    the block issue time is still 10 minutes and the block size is still 1 megabyte right so that doesn't change anything about the latency or the throughput of your problem so of course you could fiddle here with with with the issuance time of the of the like the the block issuance time or the size of the blocks but overall that doesn't buy you that much because if you get two numbers that are really interesting like you have very large blocks in a very quick issuance of your

14. 7:37

    blocks then the Nakamoto consensus actually becomes insecure because you have too many Forks happening at the same time so and what we actually want from a system when you like coming back to to cloud computing is if we throw more resources on it we want that also the capacity or the throughput of our system increases linearly in the amount of available resources so here is a graph like that shows here on the bottom we have Bitcoin and here we have the

15. 8:17

    number of validators which go from yeah and then we double them to 2 n + 3 + + 4 n and as I've showed you before that doesn't affect the throughput here but what we actually want is if we double the number of validators or triple them then we also want to be able to double the throughput or triple the throughput so yeah so for scale so this is basically this property which we call in

16. 8:42

    general scale out right you have more resources and the number the throughput increase or the capacity and the compute power of your system increases linearly with that so one idea how you can do this is this notion called sharding and the idea here is that you take your validators and you group them into distinct subsets and you assign the validators each one of them to a different blockchain let's say for example you have yellow validators who are responsible for the yellow blockchain

17. 9:16

    and you have green validators who are responsible for the green blockchain and then the validators the transactions who go to the yellow blockchain are processed by by those validators and the green ones by the green validators and thereby you basically have achieved parallelization right so you can now process twice as many transactions as before however you have a problem namely

18. 9:44

    for the first question if you think about it is how do you actually assign the validators to the sharts what is the what is the process there and then of course also the the system is fairly is not very usable if you are if you're not allowing cross card transactions right because then it's just if you don't have cross browser transaction then it's just like two distinct cryptocurrencies like for example Bitcoin in etherium or

19. 10:10

    something like that so you also want to have a mechanism how to do actually cross card transactions so when we started looking into that problem we also investigated what's already out there what was the research that other people have looked into to tackle that problem and we found basically three properties that any such system should achieve so which is scalar decentralization and security here on

20. 10:38

    the axis of scale out and decentralization is a system called elastico which was presented at CCS 2016 in the paper a secure shard in protocol for open block chains which actually achieved scale out in decentralization but it did so at the cost of security so when you look at elastic whole then the security degrades in the number of shards that you get which is of course not ideal right I cannot scale my system

21. 11:11

    and then at some point I say oh my system is now insecure so on on this other axis of scale out in security is a system call Center RS coin presented in the paper centrally Bank cryptocurrencies and that system a chief scaler in security at the cost of decentralization and basically what they have is they have a trusted third party that does the synchronization of transactions and they

22. 11:42

    are even they they are only using a two-phase commit to commit transactions to to their chain which means that they don't even have a Byzantine fault-tolerant process in there which means that if the client and the trusted third party would collude with each other then they could basically double spend in that system a third system which is actually our own researcher which is called Bitcoin which was presented as use next security in 2016 a Chiefs decentralization and security and

23. 12:17

    in that in that paper we showed how you can create an very efficient consensus mechanism that you can deploy on top of Bitcoin that gives you very high throughput but you have this with Bitcoin you have this problem that it doesn't scale out so you can add more validators but at a certain point you've you're hitting a bar a boundary that you cannot scale more with with Bitcoin so

24. 12:47

    okay so and in here in this talk I will present you on the ledger that achieves all of these three properties so when we set out we thought about the goals that we want to achieve with with Omni later we've we've already seen that we wanted to have a scale out decentralization and security and in particular we we set out to have these three security goals for Omni ledger so we want to achieve full decentralization meaning we don't have any trusted third party we want to have

25. 13:20

    shard robustness meaning that shards can process transactions correctly in a continuous manner and we also want to have these secured cross transactions so that I can send transactions from the from the yellow to the green shirt on top of that we had also three performance goals namely scale out because that's the whole reason why we looked into that meaning that the throughput increases linearly in the number of active validators then another problem that we wanted to tackle is for

26. 13:53

    any high throughput chain that you have your blockchain will grow very very quickly so you need to somehow deal with with the storage overhead that comes with that so we wanted to get to a mechanism where validators do not need to store the entire short transaction history and the final problem that we wanted to tackle is that we that our system should also achieve low latency meaning that transactions are confirmed very quickly that has to do also with

27. 14:28

    this trade-off usually that you have where you either have large blocks and you get a very high throughput or you have but then processing these large blocks has the has a gives you a lowly a high latency sorry or you have small blocks that you can process very quickly that give you like bad throughput but you have very low latency with with respect to the transaction confirmation

28. 14:59

    so to start with the design of omnilogic we first came up with a strumming solution that achieves somewhat what we wanted and we call this drum and solution here simple ledger and simple ledger works roughly as follows it evolves in epochs and each epoch has a number of blocks assigned to it and here for our strumming approach we assumed okay we have a trusted third party that gives us the the shard configuration at the beginning of an epoch right so basically here we have a short coordinator that at the beginning

29. 15:36

    of an epoch says here is the configuration and he sends it to all the validators and then the validators go and say ok i'm in the yellow shot I'm in the green shot I'm in the blue chart then they do their setup and they start processing transaction afterwards so now we already have like a scalar letter right because the yellow green and blue short they will trend process transactions in parallel so

30. 16:02

    basically we achieve scale-out throughput however of course as you can see this has several drawbacks first of all we have security drawbacks namely okay the short coordinator is a trusted third party we want to get rid of that then also at the beginning of an epoch when the coordinator issues a new configuration all of the short validators will be busy like figuring out to which chart they are assigned and

31. 16:26

    then figuring out to do the setup of the chart which all takes time in which the entire system cannot process transactions so you have a downtime basically at the beginning of an epoch that's of course not good so we want to get rid of that I haven't also so this system also currently does not provide any cross chart transactions and it also has performance drawbacks namely that we are using as a consensus mechanism within a shard we use this coin and this

32. 17:02

    coin has the problem that if it has a leader and a consensus group attached to it and if this leader fails for a given time then you need to do something which is called a view change and during the view change you try to figure out okay who is the next leader in my in my for my for my next phase and during that time you also have a downtime where the where the shard cannot process transactions so you want to also get rid of that we have still high storage in

33. 17:34

    bootstrapping cost because a validator that's getting assigned in from one epoch to the other for example from the yellow to the green chart he has to read the entire short history which also takes some time and you still also have this route throughput versus late the latency thread trade-off that if you want to get high throughput you need big blocks but that has bad latency and if

34. 17:59

    you wanna get good latency then you need to have small which has bad throughput alright so and here's the roadmap how you get from simple ledger to Omni ledger so to tackle the first three problems what we do is I will introduce how to do randomized charging then two to tackle the the downtime during epoch transitions you need a way how to do a secure system your rate configurations in a continuous manner then to do cross

35. 18:33

    chart transactions you need a protocol that does that atomically meaning that the transactions commit atomically or abort eventually then for the performance on the performance side you want to get a bisque that you want to make Bitcoin more failure resistant to deal with to have having to do the view change only very rarely hopefully then to deal with with the storage overhead you want to do something like blockchain

36. 19:05

    pruning where you from time to time to do snapshots that summarize the current state of our chart and then we also introduce something that's called trust but verify validation which deals with this high throughput versus low latency transaction validation problem for the sake of time I will only talk about the three most interesting problems which is like randomized charting atomic restore transactions and trust but verify

37. 19:38

    validation all right so back to our roadmap okay first of all we talked about randomized charting so if you remember we have this problem how do we assign these validators tool to shorts in our straumann we had this we have this trusted third party that gives us this configuration and tells the validators to which chart they should go so here we will of course want to get rid to rid of that so but now the question becomes how how do we assign these validators to shards in a decentralized way so

38. 20:17

    you have basically two options you can do so in a deterministic way telling Valladares okay there is some kind of scheduling mechanism that assigns them to to the charts but if that's deterministic then the adversary can exploit that to position his notes in a way that he would be able to compromise an entire chart which we want to avoid right because as soon as a shard is compromised that chart basically can

39. 20:47

    also poison all the other charts and thereby the entire and entire system so what we want to do instead is we want to have a mechanism that assigns the validators to the shards in a in a random manner and in a way that's really unbiased and bias pool where the randomness is unviable because then the adversary cannot control or predict the the assignment of the validators to the shorts so and then once you figured that

40. 21:22

    out the next question of course also becomes how do you ensure the long-term shard security because an adversary might actually be adaptive and once you've assigned the validators to the shards in a random manner the adversary might over time compromise enough validators in a shard to also compromise the entire chart and you want to want to avoid that so in the the answer to that

41. 21:48

    is you make the shards large enough and you also periodically reassign the validators to other shards in a randomized manner so here in the group in the diagram you see some mathematical and analysis that shows you depending on the adversarial power in the entire system how large your shards have to be and for example if you take 25% adversary and you assume a total failure probability of 10 to the power of minus 6 then you need roughly a shard size of 600 so you probably can't see that but

42. 22:24

    yeah this this this point here is roughly 600 so okay so we established we want to do the short validated assignment in an unbiased will and unpredictable random manner so yeah we we need to do the assignment in an unbiased scible unpredictable and scalable manner and the solution for that is we combine a we RF based lottery with a protocol that gives us unbiased little randomness so why are we doing this combination so

43. 23:00

    first of all what we do with these brf's is basically every validator that's assigned to a shard issues a lottery ticket and then after some time we determine the winner in this lottery so in that case it's the read note however then the problem is we cannot trust this one note to do the short assignment because that note might be corrupt right so we need something on top of that but why why are we why are we doing that

44. 23:32

    because we have another protocol that needs a coordinator or a temporary leader to generate an unbiased level random string from all the nodes in the system basically we elected a temporary leader and that guy then runs a protocol which is called rent hound taking the inputs of all the nodes in the chart and they collectively generate a verifiable random string and once you have this verifiable random string you use that to do the the short assignment so here

45. 24:07

    again yellow blue and end green ok so coming to the next problem that we that we want to tackle is the Tomy crossroad transactions and here we also can take some inspirations from distributed database systems where you have a protocol which is called two-phase commit and that works is following you usually have a coordinator and you have a set of service so for simplicity I know I only show one and this coordinator goes to all the to all the server and ask them hey can you commit

46. 24:41

    this this transaction to your database so basically you have first a voting phase and then all the all the servers say yes or no if all the say the the service say yes I can commit this transaction then this transaction goes through and if one of the service says no then the system does a rollback which is basically here the the completion phase so this is already a nice idea however the problem is that in a Byzantine setting where these guys the service can be malicious that doesn't

47. 25:16

    work because as soon as you ask a malicious server he can always say oh no I'm not committing and basically then he is stalling the system forever so but there is a workaround on around that we can consider the shards as Byzantine fault tolerant processes meaning the shards since we assigned the validators to the shards in a random manner we ensure that that these guys that the

48. 25:48

    shards themselves are honest so we can consider them as honest processes so now we can run this two-phase commit on top of the shorts and we use the client as the coordinator because the client is has an interest to commit his transaction so he will be there to do the coordination of the two-phase commit so in here I show an example how that might go for example the client wants to

49. 26:15

    spend a transaction where he has like ut EXO's in shards 1 & 2 and he wants to pay somebody in in shard 3 so and what he then does is he sends this transaction to the input charts they locked the funds in in the respective shard and get and the client collects acknowledgements from from all the input charts and if he is successful - if he can do so then he can go with these acknowledgments - the output chart and

50. 26:48

    say look I have confirmations from from all the impure charts and you can spend the funds done if however on the other hand one of the shards aborts because for example the client has not enough funds in that chart he gets an error and he can go with that error to the other input charts and reclaims the transaction inputs and basically does a rollback all right so the last step that we want the last interesting problem that we want to

51. 27:20

    tackle is this high throughput low latency trade-off and what we came up with here is a mechanism called trust but verify transaction validation where we split the validators within a short into optimistic and core validators and a client who wants to commit a transaction will only communicate with the optimistic validators so he sends his transactions his transaction the the validators briefly check if the

52. 27:50

    transaction is consistent according to their view of the state and they send back a confirmation to the client and at the same time they also collect these transactions batch them together into blocks and forward them to the core validators and the core validators will collect these optimistically validated blocks batch them together in even bigger blocks revalidate them to check if it's really okay and then if that's okay they they put them into the into the

53. 28:25

    blockchain so and this gives us now the best of both worlds because the clients get a very quick confirmation a very yeah very low latency confirmation and the core validators by batching a lot of blocks together and doing a revalidation they get a very high throughput and since these guys will be always the majority in the system they can also ensure that nothing funny is is happening here okay so coming to the to the evaluation we implemented all of

54. 29:03

    that in a prototype in Ingo meaning we have the we implemented on the ledger and its sub protocols like biscone X and the cross chart transaction protocol and so on it's based on some of our other libraries that we develop in the deadest lab a crypto library and network library and the protocol framework you can find all of that as open source code on github and we evaluated this on detail app which is an academic test network so

55. 29:34

    to say for distributed systems on 48 physical machines that had yeah until C on processors 24 gigabytes of RAM and 10 gigabits per second network link and to simulate a more realistic network we artificially limited for example the network to 20 megabits per second bandwidth and then a 200 millisecond round-trip latency so the first question that we wanted to answer is of course yeah does only ledger really scale out

56. 30:03

    and so this basically brings us back to the beginning of the talk where where I already showed you how an ideal system looks like and here in that in that example here the Green Line is Bitcoin and here the blue line is on the ledger and as you as we increase the number of validators and charts you see that the throughput increases linearly so for 70 validators we have a throughput of 404 under 140 we have 800

57. 30:34

    than 1600 3,200 and so on so we achieved our goal here we also wanted to look into the maximum throughput that omnilogic in achieve and here on the x-axis you see different configurations of our Omni ledger system for example if you're basically in a permission setting and you have maybe just a 1% adversary you can make your shards very small and actually just like for example you can have consensus groups of 4 which gives

58. 31:07

    you very very high throughput on the on the order of tens of thousands transactions per second and on the other end of the spectrum if you are in a in a permissionless setting and you face a very strong adversary you need to make your shards bigger that's where the the value 600 comes back in so your shards have to be of the size of 600 but you still get like decent throughput and for example with

59. 31:34

    the trust but verify transaction validation I think that's roughly 2,000 transactions per second so we're here almost at the level of visa what we say is doing on average I mean maybe a tool can say more more more on that if that number is correct or not so and then the third point that we wanted to evaluate is the latency so here on the bottom you see the the latency that Bitcoin gives us which is which are these known

60. 32:07

    numbers so the first confirmation that you get is after 10 minutes because that's the time that it takes that a transaction is included in the blockchain and to be sure about consistency you need 3600 seconds no matter how many how many valid it is you have in your system so on the other hand for a four Omni ledger when we take this for example this trust but verify approach then the optimistic validation you get a

61. 32:36

    confirmation after four seconds and if you have for example a very high-value transaction for example let's say you were buying a house or something like that then you might want to wait for a minute until you were until the core validators have actually confirmed the transaction and included in the blockchain yeah so this is again for for 500 kilo buy for 500 kilobyte blocks and for 16 mega byte blocks yeah so to

62. 33:08

    conclude so I presented you on the literature which is a skew scale out distributed ledger framework that achieves sharding through unbiased of randomness and has a linearly scaling throughput I also showed you Atomics which is this client managed cross card transaction protocol what I didn't show you is Bitcoin X which is a more robust variant of Bitcoin that for for intra shart consensus and I also

63. 33:40

    showed you this trust but verify validation that a Chiefs like low latency and high throughput at the same time and what I also didn't mention but we had like a question on that before on the ledger basically works with any of the proof of work proof of stake or in a permission setting because we assume that we use these mechanisms only to create Sibyl resistant identities in the

64. 34:06

    system and then for the actual processing of transactions we use our regular DFT consensus so the paper is freely available online it was published earlier this year at I Triple E secured in privacy all our code is on on github and yeah that's that's it from my side thanks for your attention so I'm Alex and let's talk more about charting so I was already introduced very quick introduction about what near protocol is your protocol is a hard block chain we are building it our headquarters in San

65. 34:50

    Francisco it's a team of multiple people from méxico besides me there's two more people engineer number four engineer number five one of the later guys and a few other folks we have four people from Google and the primary focus of near protocol is to build a usable blockchain so scalability is one part but we're also looking heavily into how to make it work in a way that you don't have to pay

66. 35:15

    gas that if you buy cryptic each it actually gets purchased and it doesn't fail with some weird cryptic error message etc and I'm going to talk about charting in general today since I'm presenting right after emulator only ledger actually covers a lot of how sharding is built in general today by most of the companies that built on sharding so I will just talk about few interesting aspects of sharding which are not necessarily

67. 35:45

    all of them relate to all the protocols alright so first of all let me quickly give you an overview of how charting usually looks today on a higher level so that would be that that's what for example the theorem is building their short endoscope polka dot his work in cosmos quark chain elrond and naturally near always you would have a series of short chains that's that's the entire purpose of shorting and in most cases you will also have some sort of a main chain so in a theorem or near that would

68. 36:21

    be called the beacon chain in polka dot that's the relation and cosmos that's the hub and the main chain has multiple purchases purposes one of the primary purposes for the main chain is to assign validators to the shorts right so the idea here is that that's what Philip covered is that if validators are assigned to shorts and never move then they will ultimately get corrupted and this is so in fact if you have 1,000

69. 36:52

    shirts and you're saying you have a pool of validators and every shirt has a subset of validators corrupting any of those charges 1,000 times cheaper than corrupting a single block chain that had the entire pool of validators if you frequently rotate validators that is not the case anymore because at that point if you have a large pool of validators let's say 1 million validators and you assign 1,000 validators to every 1,000 shorts but you frequently rotate them

70. 37:18

    then it is not sufficient to corrupt to to have to control any thousand rows validators because you never know if those 1,000 will ever be assigned to a single shark or moreover probabilistically they will never be assigned to a single shard now if those urchins never communicate that is something we call a beam Spock if you think of a beanstalk it's a lot of those strings which are interleaved but they

71. 37:41

    are not connected in any way beanstalk on itself actually has you can actually build a usable block chain using Beanstalk there is a protocol called fleeta which in one of their very early white papers were presenting an approach where you use a bill for a payment watching with the idea that every single person would have an account on every shirt and if you want to send money to another person you would send money in one of the shirts on the shirt on which you have sufficient funds and if you don't have any shirt on

72. 38:13

    which you have sufficient funds you would use a subsidy a SAP sort of shirts work in aggregate you have sufficient funds so in the worst case you would have to send on every shirt and lose any benefit of scalability but in in majority of cases you will be sending on a single short the fact you were getting linear throughput improvement and and that happens without any cross or communication right so that's a beanstalk based usable blockchain for payments in practice however you would

73. 38:40

    you would mean some sort of course or communication right so every now and then short will be sending either directly or through the main chain some messages to each other effectively communicating all right so a good example and this approach is usually called G seats so imagine a payment transaction where L is trying to pay book and they happen to be on different shirts in that case

74. 39:02

    Alice will send the transaction to the first surcharge zero on the bottom where she has yeah yeah so Ellis is sending it to chart zero where she has her account on that account the validators will execute the first half of the transaction they will subtract mining from her account and then they will create some sort of receipt that was sent to shard one where money will be credited to Bob's account now the the entire

75. 39:37

    complexity of the cross short transactions is in this receipt and there's this idea but the me city failures right so consider these two chars these short one and short two they both have block chains block chains in general might have Forks right and so consider this cross card transaction which insured one it was initiated and in block a in block a this is some sort of let's say the block ay is the Block

76. 40:03

    in which Alice's transaction was that Alice's account was debited and then the receipt was sent to the set of the shard number two where the block X prime was created that credit public Bob's account now the block chains people could keep on evolving and if this if this chart is very of this chain ultimately ends up being the canonical chain and this chain ends up being the canonical chain we

77. 40:26

    have no problem right both both sides of the transaction get committed if this chain gets canonical and this chain becomes canonical there's no problem either the transaction is entirely rolled back the problem arises in any other case right if this chain is canonical but this chain is canonical then Alice's account was debited but the money never reached Bob that would be a problem however practically in every

78. 40:50

    starting proposal today the consensus that is end of the consensus that is run on every short is some sort of Byzantine fault tolerant consensus meaning that Forks in principle should be impossible or at least unless there's something very bad happening and unless a large number of nodes are simultaneously colluding and when we start talking about a large set of validators colluding forking is not the only way they can actually mess up the chain they can and that would create a problem we just

79. 41:26

    discussed alternatively they can they can do something worse they can in principle apply some transition in the block which is invalid so for example they can create a block which out of thin air means 1 billion tokens and puts them into one of the accounts which is controlled by one of the validators right and this malicious behavior if you do not have shortening or let's consider bitcoin for example in bitcoin forking is possible it's not even a malicious behavior but invalid state transition is

80. 42:00

    impossible why let's consider a fork and then this fork happened to here there is no forking and at some point three malicious nodes so there's more than 51% let's say of malicious more than 50% of hash power is controlled by malicious nodes let's say and so at some point they create a block which applies invalid state transition and then they mind faster than the owners validators and so their chain is longer however in Bitcoin every single user of the chain validates every single block

81. 42:34

    so if you're some sort of point-of-sale terminal or you just monitoring blocked a Bitcoin network for any other purpose you will validate every single block and so the moment you observe a prime you will you will immediately recognize it is malformed and so you will not even consider these blocks as well so every single person who uses Bitcoin in that case will know that this is the

82. 42:58

    canonical chain even even even though the validators that build on top of an invalid block control more than 50% of has power in presence of charging however with cross card transactions invalid state transitions become becomes a problem because in an image in a network in which we have 1,000 shirts the entire promise of sharding is that no single entity can validate every shirt so like we want to scale to such

83. 43:26

    an extent that it becomes completely infeasible for any single entity to validate all shirts so at that point if one shard gets completely corrupted and they can apply an invalid state transition which from perspective of other other shirts have no way to tell that happened and so that that shirt that was malicious and credit invalid state transition can later start sending the receipts that are based on that invalid

84. 43:51

    state transition so they can mint 1 billion tokens put them into the account of one of the validators and then they can start sending payments from that account they would send the receipt or the short saying look I have 1 billion tokens I want to send 10 of them to account on your chart and from that short perspective unless they validate the entire short they have no way of telling that that happened now as was

85. 44:18

    just presented at the previous presentation if we frequently rotate validators and we have assumption of let's say we assume that the entire pool of validator has as less than 25 percent malicious actors then we would never expect a single shirt to have more than 33 percent of malicious actors and if these less than 33 percent of malicious actors in every shard then it is unreasonable to expect that either 14 or invalid state transition

86. 44:44

    can happen right the entire promise of the Byzantine consensus is that if you have less than one-third of malicious actors then everything happens according to the plan the problem however is that in principle validators can be corrupted so you don't need to control 25% 30% of validators before they get assigned you instead can go find the validators after they got assigned and corrupt them in some way you can try to hack them you can try to to bribe them at that point

87. 45:15

    you only need to corrupt validators that were sent to a given shirt bringing again the problem that corrupting a single shard is 1,000 times cheaper than corrupting the entire network so there are multiple solutions proposed to that problem one problem is rotated so frequently that it becomes infeasible to corrupt such validators or another proposal famously proposed by Elgar and is not to reveal validators at all until they actually perform the task that was assigned to them so effectively

88. 45:45

    there is a person that at some point is expected to produce a blog that person is only revealing themselves to the to the blockchain when they produced that block right and that way if the validator is not known in advance it naturally cannot be corrupted in general I would argue that neither of those approaches works and here's here's the argument in principle it is possible to set up a so let's say I'm an add an adversary and I want at some point corrupt say a large percentage of

89. 46:18

    validators in a single shot the way I would approach it and without loss of generality let's say I'm trying to corrupt one of the short chains in the theorem serenity when they want shorting what I will do is I will launch a smart contract on a theorem classic or any other smart contract chain which is not a zero and you add any chain which is not the one I'm trying to corrupt I will launch a smart contract on which I will

90. 46:42

    publish the list of private keys of all the validators in the chart the moment they become known so if it's not an algorithm it any chain which which rotates no matter how frequently the moment I know those private keys I will publish that smart contract and after that I will the smart contract will offer 40th to any person who submits the private key matching sorry I will list public use of course I will these public

91. 47:08

    keys of validators and any person who will provide me with the private key that matches any of those public key kids will immediately receive 40th and it costs 30 to Eve to become a validator an ethereal right so for any before any validator that's an immediate profit of 8 if they are 32 if on the theorem get get burnt they they will get slashed because like clearly I'm planning to do something adversarial but they already

92. 47:32

    got 40 if which is like that's profit that's immediate profit and then for as long as I have any reasonable channel to which I can reach out to a large number of validators they can get corrupted immediately effectively like the moment they get assigned the moment I know about that I published a smart contract they can immediately claim their money right then you would need some sort of bookkeeping here first of all people cannot submit their private keys because

93. 47:56

    then the private you would get known to every single user of a theorem classic so probably what you would want to do is you would want to publish some private key here that they will you to encrypt their public key private key and so then there will be some grace period where I can decrypt it test it and challenge it and there are couple other bookkeeping but in general this approach in principle works and if it's Elgar in style instead of publishing list of public keys what I will what I

94. 48:22

    as a malicious actor will do is I will publish a smart contract which will do the verification that the person is actually the person who's supposed to produce the block the idea now grant is that the validator when they said me at the blog they also produced some proof that they are the validator which can be checked by any person in the algorithm which can also naturally be checked in this smart contract so I will just ask them to submit that proof to my smart contract before they become before they

95. 48:46

    produce the block and then I can produce the block or correspondingly participate in consensus so factor this is an approach to bribing to instantaneous breathing naturally it has many assumptions it has an assumption that more than 50% are corruptible it has an assumption sorry more than 33 it has an assumption that I can reach out to all those people which neither of those assumptions is super reasonable but neither of them is also super unreasonable right so building a blockchain that has both of those assumptions

96. 49:16

    underlying it is it's not like that I would not call that blockchain super reasonable yeah that's what my first assumption more than more than more than 30% of the total population of the validators a bribable yes so with that let's get back to atomicity failures right so the mr. failure was if if the fork happens or invalidate transaction Eliza how people try to solve it on the

97. 49:45

    theorem and many other blockchain the the solution they propose is so this is the big inch and this is the mention we talked about at the beginning the beacon chain is only one beacon chain so the beacon chain naturally has significantly higher security it is maintained by all the validators they might also rotate from block to block but but generally the entire pool of validators is producing the security for it

98. 50:07

    so when short-chain wants to initiate a cross chain communication they in some way communicate through the beacon chain the easiest way would be to crosslink so cross-linking means that the moment the block is produced the half of the block is submitted to the beacon chain and the beacon chain stores the hash on in the block and then the fork choice rule in the church and says that if the block is cross-linked that block has to be on the

99. 50:30

    communique chain meaning that even if there is another fork which is longer this one will be preferred because the block from this chain is cross-linked to the beacon chain and the beacon chain would never accept the cross link which does not contain like this she cannot be cross-linked later because she does not contain in its chain the previous previously cross beam take a prime right and so if the block was cross-linked then the other chain can be certain that

100. 50:55

     that block will never get worked out that make sense another proposal is Vlad Vlad Zamfir Stirling which I'm not going to go into too much detail given time is sort of limited but Vlad sharding is it has significantly more sophisticated machinery to avoid forking specifically however both of those approaches only help with 14 they do not help with invalid state transition so in this case one of the blocks here could still have an invalid state transition application

101. 51:27

     and unless there's some way to prove to the beacon chain that all the blocks here are valid it will still get cross-linked and the idea here is that so let's consider consider this chart where on x axis I plot the number of militias validators who got bribed and then the y-axis is the probability of them being capable of pulling off a fork if there's less than one third they cannot pull out the fork or pull off a

102. 51:57

     fork because that's the guarantees of the Byzantine consensus if there's more than 2/3 they absolutely certainly can do any Forks because they they control the Byzantine majority they can create absolutely any decision in between it gets easier and easier if they have just 1/3 plus one doing a fork is extremely complex they would have to separate the network into two halves they would have

103. 52:20

     to for quite a while communicate with those house independently and if those halves at any point managed to send any message to each other the and is immediately revealed and they get slashed the probability of applying invalid state transition is different until you have two thirds you cannot apply invalid state transition because you will not be able to reach Byzantine consensus on the block no honest

104. 52:44

     validator will sign it the one when you have to third again it is 100 percent so effectively all those solutions from Vlad or in aetherium crosslinking they optimize for this little triangle here however if we assume that one-third of validators can be corrupted we should always assume that two-thirds can also be corrupted right so here we have and that's a very fundamental problem to which I have a short-term solution and short-term solution is make sure we are here right so effectively build a for

105. 53:17

     example short-term we don't need actually 1,000 shirts short term even if we launch a blockchain which has 10 charts that's already a huge improvement over what we have today and those 10 charts probabilistically we're here it would be very hard to corrupt one third more than one-third of the validators for long term solution one solution would be so-called fishermen were the idea is that whenever any action is about to be taken on the result of the

106. 53:41

     consensus any validator has some grace period during which annually data can report that that there was some malicious behaviour if there is a fork it's fork fork is of this de provable and and invalid state transition transition is obviously provable so for as long as it is one honest validator that validator has sufficient time to report it right so that's a solution that would work today the problem with this solution is that that grace period

107. 54:04

     has to be pretty honorable right so that should be enough time for the validator to notice that the block was published to be verified which takes time right so that makes cross card transactions super slow or a longer term solution would be the key snarks which is effectively a way to prove that some computation was done properly if we can have a concise proof that the entire blockchain up to this point is computed properly that solves the problem

108. 54:27

     entirely the only problems that Zeke is not today takes 30 seconds to compute per transaction right so that's a that's super slow we have very little time so I'm just going to very quickly go through another idea is that bribing is one problem another problem is that the validators they might not be malicious they might just be reasonable so they might try to do exercise Sam behavior which is in their interest which might not be an interest of the of

109. 54:59

     the blockchain so one thing so if you think about Bitcoin and Bitcoin it is in your best interest to always build on the longest chain so incentives are sort of aligned to an extent right so there's this concept of 25 percent attack which is which provides one example of misaligned incentive but even that does not break Bitcoin too much sometimes incentive get a little misaligned I

110. 55:22

     couldn't use this opportunity to talk about so in Bitcoin they use pbft and pbft in general is very slow a B of T is N squared algorithm in terms of communication that isn't that is needed and that super slow and the Bitcoin proposed this idea where the instead there is a Qi where at the very bottom little layer we have all the validators and they look like in a library logarithmic number of steps they go to a certain litter and that litter is orchestrating the entire signature process and that takes logarithmic time

111. 55:55

     and log n instead of N squared and however it it relies on the fact that every everybody who started participating in the signature stays online until the very end and if any of them drops out then the process has to resort to N squared so Omni Ledger addresses it by having leaves having not a single validator but a multitude and as long as at least one of them stays online that works

112. 56:19

     however in in the bitcoins particular example if I'm the leader and I want to finish it in log at logon steps I have a huge incentive to include as few people on the lowest level as possible namely exactly 2/3 plus 1 because if all of them sign I have the Byzantine Agreement and that's all I need and if any of them doesn't sign then I would have to read I would have had to resort to the N squared even if I included more people

113. 56:44

     because if we include more people that person would also not have signed make sense right so in this case the leader has a strong incentive to misbehave however in this coins example at least that does not affect the security like some people will not get your words but the security of the system stays high meaning that the blow the Byzantine agreement is still reached I'm gonna skip iota but a yacht is broken in all aspects including including

114. 57:10

     reasonable actors in iota they are motivated to behave in such a way that if many of them start going to start behaving in such a way I hope the security breaks completely so that's worse than this coin in the theory of serenity there's a good example of incentives where so factor the how serenity works is that they propose blocks every eight seconds so every eight seconds there is one person who is expected to produce a block and when that person produces a block every single other validator is sent to the

115. 57:42

     heart attest to that block and the way it happens is you can attach to the block any time throughout those eight seconds or you attest to the absence of the block so effectively every eight seconds every person needs to attest to something which would either be the proposed block or the absence of it and it's up to them when they will attest throughout those eight seconds they can immediately attached to the absence of the block or they can wait till the very last moment and a test to the to the

116. 58:06

     block that if it was published by them and the recommended approach is to attest at second four and they are it's in their best interest to attest to what everybody else attested so so whichever whichever is going to be the final decision if they attest to that they get the reward and if not they get a slightly lower reward right interestingly in this case this is a there's always a chance you will not get

117. 58:30

     a reward it could be that you you're tested that second foreign block wasn't there and then the very next second it appeared or it is possible that you are tested to the block but majority of people didn't see it also interestingly there is a Nash equilibrium if nobody ever tested a block if everybody agrees at some point always to attest to the skip block suddenly they always get reward right however the difference between that and the previous two

118. 58:55

     examples is that in this example getting to that Nash equilibrium is very so if one validator starts doing that there will actually be losing money right so that Nash equilibrium exists but it is very unlikely that everybody will fall into it but if everybody did somehow fall into that Nash equilibrium exiting from there is impossible right so you would have to somehow just reboot

119. 59:16

     the short and so the the overall idea that I wanted to present in this presentation is that the the Charlotte blockchain is a very complex engineering task so there is no single problem it's a lot of so I presented to I presented bribing and incentives but there is a huge variety so I put ten buzzwords here on the slide each of which is a problem in charted blockchains so whenever you go to a presentation of

120. 59:41

     let's say Definity and they say threshold relates of everything or you go to Algar and and they say if you do not reveal people it solves everything that is always like you should always be skeptical why they only talking about a single feature and not all the rest of 99 problems that exists from the shard image are the blood chain and then on the very last night they will do a little bit of praising us we just open

121. 1:00:05

     sourced our repo today so if you're interested in seeing our progress it is easy to remember github.com flash near protocol we also have this core channel which i didn't put the link because it's impossible to remember but it's easy to google it on our disk or channel we have all the development conversation public and we have a lot of people outside of near who talk about economics governments etc and also please follow us on twitter thank you