CESC2020: Verifiably Delaying adaptive adversaries in 1 Consensus

2020 Ford F150. Hi everyone, PhD student at MIT csail. Today, I'll be presenting some work that was completed with Chase Tria and they have the ruler. While I was interning at the MIT digital crime initiatives this past summer or specifically I'll be presenting delaying adaptive a series in consensus. Explain what each of these terms mean in the following few slides? Just very quick to start. I will Define consensus consensus involves schemes or protocols meant to ensure our participants, reach agreement and decentralized network. Some desirable properties of resources

include. Of course, having everyone agree on the same value. Suppose you have the following set of participants, we propose the values, ABC these values can be anything. For example, blocks you may want to add to the blockchain or functions, you want to execute in a distributed database or cobase. if everyone talks to everyone is honest about their proposal, they can simply decide on a values like the lexicographically first value, which in this case is a furthermore, we want the additional property that if everyone starts with the same value, they also agree on the same value.

For example, if everyone starts with B agree on, be, not a or c, In Real Life 2 should be the system, not everyone. Participating in consensus is honest. Thus we also want the property that all honest players can reach a agreement, even in the presence of a series. Sure, even if there is an adversary, all the honest, participants should reach agreement on the value. Be Two properties by which we measure the affections of effectiveness of a consensus protocol liveness and Safety. License is defined as a property that

progress is always made in the system. This means that for example blocks are continuously being added to the blockchain. Safety is defined as a property that all honest players agree. On the history of values committed to the chain, for example, of Persistence of a cryptosystem should agree on the history of transactions that were performed. Throughout this presentation, we assumed the synchronous model in which agreement over values proceed in rounds. And there is a fixed maximum. Amount of time, messages can be delayed in Lighthouse applications of consensus. Two large cryptosystems,

we want excessive protocol database, lightness, and safety in the presence of millions of participants This is far too many persons pins for everyone to be able to send messages to everyone before these messages flood the network. Does an additional desirable property for consensus protocols for the system. Is that we want only a small. Number of honest knows to speak. Before consensus can be reached for the more out of surgery, some more motivated in these systems to perform targeted attacks. Since only a small number of participants are seeking adversaries can for example, launch

attacks only on the speaking. Participants A balanced strategy then is to observe the network for messages sent, and then attacked the important players in the consensus protocol. We also want protocols that are robust against the strong adversaries. Finally, some existing cryptosystem already achieved the two desirables above. However, each has some caveats, which I will mention later, pacifically in the context of protocol is based on proof of work, we want to create a protocol that has a chew desirable properties above. But a boy's

energy-wasting, who's the work that can be paralyzed using special Hardware. Will first start with the first property? What, which by which country does the stumps deal? With only having a small number of participants speaking is via cryptographic sortition as used by the El Gran cryptosis cryptographic. So tuition is a procedure by which all participants in the protocol, elects a small committee at random among the small number of participants, which makes a decision and then informs all other participants

off their decision. some characteristics of cryptographic sortition as used by Cal grant included having a small number of proposals which proposed blocks Is also having a small number of Voters will vote on the blocks proposed by the holders. In this case, it's a number of composers and voters are Polly logarithmic in n4n is the total number of participants. The total number of messages sent by these proposals and borders, everyone, the Olaf and Polly login, which is a much smaller value that N squared. When you consider end

to be on the order of millions or billions of users, And other important characteristic of cryptographic sortition is that each individual decides committee membership secretly. This can be done if we are cryptographic from reduce verifiable random functions or vrs, Although membership is decided secretly committee members can inform others improve their membership later on. Such ideas are used in a variety of crypto systems including algor an affinity filecoin with net and others.

This concept of cryptographic sortition allows us to satisfy our first durable property. Now we'll talk about the second property note that from this point forward, I only talk about the remaining properties for protocols, that satisfy the first property. FirstBank quickly traditional consensus. Protocols mayonnaise considered static at the series. What are static Apple series? Let me quickly Define that suppose we have a set of Byzantine knows these byzantino so I decided before we run our

consensus protocol, the name, static then we run our consensus protocol and reach consensus. But large monetary gain, has led to Stronger adaptive a series. The first observed, the network before attacking the crucial players. Initially, there are very few or no Byzantine notes, then the protocol is run. Suppose the protocol Alexa leader. Then the leader sends a message by the time, the leader sent the message, and the adversary would have known that the highlighted player is the

leader. So after the leader, sends the first message, the Apple Street rules together all his resources to mount an attack against the server of this leader. for example, the attackers to choose to DDOS the leader or bribe or have any number of such attacks may work, then the corrupted leader, can perform malicious actions, immediately potentially violating both of lightness and safety of the protocol, Now, we'll take a look at some case studies of their how adaptive a series can break the protocol in each of these cases. In the first case

adaptive adversaries can violate the life support. A coffee shop. Predictable, leader, schedules, you can corrupt the leader before they are elected and have them never sent out a proposal. Even if the leader schedule is not predictable, the adversary can corrupt the leader right after they send their first message. For example, they can corrupt ever, elected leader, and then send many different photos missing. Boaters, unable to decide on the same proposal. This would also violate liveness Finally, if there is a

small committee, the adversary can corrupt the committee right after election and send bolts for every proposal or some subset of the proposals to different participants bus potentially causing that participants to believe that different proposal are committed. This would violate safety. The cryptographic partition solve the first problem with the pretty predictable leader schedules. By itself, it does not solve the problem of corrupting leaders and committee members after election. Clear replaceability, solve the problem of

corrupting a leader or Committee Member after election by having each Chris and speak only once before the next committee is elected. To ensure player replaceability, many current systems use the computer Acer model, which makes participants erase their current chief and generous for your new keys before announcing their leader, or committee membership. Plus even if an adversary cross them, they cannot send a new message, using the old keys because these Keys have been erased. Give a bit of background

on the model in the key of arrays or model. It is assumed that she's can be erased. I will arbitrarily from one storage without any recovery possibilities. Such an assumption is difficult to realize in real life since complete Erasure on hardware and in software, is difficult to accomplish. For example, Hardware failure could prevent a key from being fully erased. Similarly fault, tolerance, software back up and she was an error and software can also prevent fully rager Furthermore, they could

exist even in his sense of scheme to retain and sell. It seems important to explore alternatives to clean, razor. Just solve the problem of corrupting leaders and committee members after election, Recently a number of researchers used both specific eligibility instead of the rear razor model to determine bolts for a specific stock class of consensus, binary Byzantine agreement or BBA BBA participants either agree on the digit, 1 or 0, so the setup possible proposal. A leader can make us only if one or zero. In their protocol one.

Can mine a volt by passing into the vrs OR cryptographic sortition function, either, one, or zero, and the round number Honest, replicas Maya volt for 1 of 1 or 0, have a serious and mine for both but it is difficult to obtain enough votes for 1 or 0 probabilistically speaking. Committee membership is done tied to a successful mining off of boat. The natural extension of this protocol then is to pass and blocked proposals to the full function. So, pasta an arbitrary

block, proposals to the volt function in order to my novel. However, the adversarial strategy is then to try an arbitrarily large number of transactions and blocks to attempt to create a block that obtains, a disproportionate number of adversarial. The situation then dissolves into proof of work in which the adversary will paralyze. The grinding of various blocks and dust the greater the computational power off the Apple. Siri the greater its ability to get more votes or to grind more votes.

Consensus to hurting presents a solution to this issue by a science quartz two transactions by age. This essentially ensures that older transactions are included in a committed lock, and limits the ability of a series to grind through many new blocks. However, it appears that the safety and lightness of such a scheme is tied to this temporal ordering of the blocks and it is unclear how such a scheme can work with other priorities functions on the blocks, such as

determining pop priority based on transaction fees, which are used in in real life, Crystal systems. That's all do previous work. Provides guarantees for these two items. They are not quite the optimal ways to provide for these desirables. Don't let me just give a quick recap. We want a protocol that protects against adaptive Alpha Series without using the arrays Remodel and also preventing against a book writing or block writing. Now I'll talk about

our solution. So the intermission of our solution is a following, which must be performed before. The proposal can be sent out this number of time, steps can be performed even by parallel adversaries, and they must be performed, even if the adversaries have parallel abilities, Ralph. Take some fixed amount of time guaranteed by our assumption that message delay is fixed in a synchronous Network. Do we make it impossible to perform the time steps? Necessary, for two different blocks before the round roll over to the next round. So, let me just quickly restate that

again, We are able to ensure this property because since rounds are fixed it is impossible to propose two different blocks by performing the necessary number of time. Time stops before the round rolls over. You just don't have enough time. Even if you have access to parallel processors to perform the necessary time steps before the round rolls over to the next round. Does this is intuitively a way to commit to your block, before you send it, and an Adaptive, as Siri does not have time to commit to a different Block in the same round.

In our protocol, we use the cryptographic from it is called a verifiable delay function, or vdf. Such a function requires say control X compute, even on a parallel computer, but the output can be quickly verified by anyone. Instead of giving the full cryptographic definition of EDS, I'll just highlight some Key Properties. First honest parties, take the same amount of time to complete the PDF. Not much more than East control time. Second, I was serious, must spend, at

least the time even if they can paralyze the computation a month, polynomial processor. Arbitrary polynomial processors. 3rd. And I'm a Serial algorithm cannot shoot it out. Put that is not equal to the intended output. This means that I'll puts our unique given the input. Finally, this is very important. Verification of the country station is fast. So if you have a solution to the CDF and you sent this to me, Shannon and is proof to everyone, they can verify that. You can

shoot it, the PDF correctly, in a very short amount of time. So here is a simplified visual diagram of our proper protocol. Our paper contains the Full detailed description of our protocol, as well as the proof for his property. We use five different phases in our protocol. And the first face, the leader, which is determined randomly a call to a vrf computes. The PDF associated with a block away. Wants to propose, suppose let that block, b. M. Then it sends both M, the block and wants to propose and the computer output from the vdf to everybody

who has participated in the consensus protocol, then participant of the next building committee compute the video associated with. They're both, there are Lock & Lock squared in members of the voting committee. That is also determine randomly the Aquarius to vrs So after Computing, the BDS associated with their volt they then send both their vote and the BDF output to everyone so you proceed like this by electing three more committees proceeding for three more rounds. Until everyone has received at least two lakh squared and over three bolts

on a color block and log squared, + / 320 Square. 10/3 volts must hose for the same block for all three of the voting routes So that's it. So in conclusion by using vdf and the number of other observations necessary to the implementation of our protocol, we propose a new consensus protocol that satisfies all three properties and hopefully it will lead to efficient safe and secure protocols in practice. And I'm happy to take questions now.