Blockchain Incentives and Authentication with Ittay Eyal | a16z crypto research talks

Transcript

Very happy to introduce Tai Eyal, professor at Technion. He's been in the space for a very long time, despite the fact he's not still quite young. Uh blockchain incentives and authentications is what he's going to talk about today. Thanks very much. So, yeah, like the title hints, I uh would like to talk about both incentives and authentication here. Before I start, just a few words about the group back at the Technion. So, we're focusing on mainly on three key points for the blockchain world.

First of all, security with incentives. This is uh the way you get security in a decentralized systems. So, work on selfish mining analysis, uh on incentives, how incentives can use can be used to attack the system, uh how incentives can be used across layers to secure applications using uh the um the miners themselves, and um about uh designing more resilient uh incentive uh incentive systems resilient more more resilient with incentives. Second topic is uh performance.

We take care of uh higher higher bandwidth, uh some layer two protocols, vertical sharding. Uh if you want to improve blockchain performance with horizontal sharding, please talk to me. And uh getting deterministic safety, that's a recent result that will be shown in PodC this year. And the third topic is client-side security. We had work about vaults at the time and uh how to design your cryptocurrency wallets. These are three, I think, key challenges for the blockchain world, and a lot of the solutions you see and what we are trying to avoid is making this more centralized. So, we want to achieve all this in a decentralized fashion and continuing the discussion from lunch, sometimes this

means relying on proof of work rather than other mechanisms. So, another angle that I'm particularly interested in is using the features of proof of work, but in a more climate-friendly way. Unfortunately, I won't have time to talk about anything right here. I'll be glad to talk about this later. I'm going to be a little bit ambitious though and really try to talk about two things. One is a new resilient protocol with a better security against irrational participants and the second is wallet design, which is something um

very new and I think there's a lot of room for discussion and research here. So, I'm going to start with this one. So, more broadly, this is about authentication, but we'll focus today here on specifically on authentication for blockchain cryptocurrencies. All the range from decentralized cryptocurrencies all the way to central bank digital currencies. In all the cases, if you want to secure your digital assets, then this is this becomes relevant. So, this is for individuals storing small amounts, for companies storing large amounts, for asset management companies that store clients amounts,

relevant for everyone. Really again, for any authentication context, if you're large tech company with users who log in, that's relevant as well. But, we'll focus on cryptocurrencies. So, in the cryptocurrency world, the scenario is essentially this. You have some blockchain. The users send orders in the form of transactions and then they can send more orders and move the money around. The key is that there is no central uh party. So, if something happens to your funds and you cannot access them, you cannot go to your credit card company or your bank and say this transaction was faulty. So, the problem becomes much more crucial and much harder to solve.

Um interestingly, the users in these systems, they choose their own their own authentication methods. So, they uh design some smart contract, they put it on the blockchain, everyone can see it. And then the users tell whoever they want to get money from, "Please send the money to this smart contract." And then they can later get the money uh somewhere else by authenticating to that smart contract. So, it's all very visible. We'll call this contract that holds the money wallet. Doesn't matter if it's an elaborate Ethereum thing or just a two-out-of-three signature in in a Bitcoin, right? That's a wallet.

I said this already, the both the orders and the smart contracts themselves are visible. The authentication is typically, not always but typically, done with uh cryptographic signatures. And so, we will call the secrets maintained by the users the keys. The users have keys, these are essentially credentials. Now, there's been a lot of work on uh client-side security. There was uh Joe's paper from the time to passwords, quite a quite a big variety. In the context of cryptocurrencies, this was listed among the the chief problems for uh

for um uh usage of cryptocurrencies, how to secure clients' funds, both because they might be lost or hacked uh sorry, both because they might be hacked and stolen, but also if they're lost. Uh there are techniques uh to maintain uh a keys locally and remotely with encrypting or not encrypting or even using physical physical hardware so the keys the secret keys never actually hit a connected machine. And ways to implement K out of N wallets so you need to use three out of five wallets or whatever. This has all been discussed and the techniques for these are well established. Now secret sharing can also be used so we can split our

secret among different machines including with threshold cryptography so the keys never actually reach ever a single point. Uh One last thing that's kind of related is authorization policies. This is work from back in the end of the '90s. This is about authorization not really authentication about how for example in large organization can express the fact that certain parties, certain managers for example can be allowed to provide certain orders and others cannot.

This work was mostly about how to define formally these policies so not exactly related to what I have here but this is the closest I found. So some examples that we know password is a form of credential a physical device protected by a pin some paper hidden in a vault in Zurich and K out of N uh padlocks These are all examples of this type of authentication.

Now in order to everything here I think everybody knows this is our life but how to model this is what I'd like to talk about. So here's the model. It starts simple and gradually becomes more complicated, so bear with me. We'll have two principles, an owner and an attacker. These are the only only the only two principles we care about apart from the authenticator. The wallet defines the authentication scheme and the owner uh authenticates using those keys.

And the attacker is trying to authenticate instead of the owner. Now, each key can be in four different states. It can be safe, meaning only the owner has it. It can be lost, meaning no one has it. It can be leaked, meaning the owner has it and the attacker has it. Or it can be stolen. That's the event of theft and then the attacker has the key and the owner does not have the key. So far so good? This translates to our example, so a password lost maybe because it was forgotten or it is leaked maybe because someone guessed it. There are other ways for it to be leaked, but that's an

example. Uh for the physical key uh for loss it's enough to forget the PIN or to actually lose the physical device but remember the PIN. For theft, you would need to the attacker would need to both steal the device and figure out the PIN. I'm going to just call both of these theft. I mean the combination of these two events is is theft from the authenticator's point of view. Uh for for a safety deposit box in Zurich, you know, if if uh unbelievable scenario, of course, but if all global transportation stopped and you're not able to reach Switzerland when you need to, that's equivalent to a loss in the case of a safe.

Uh and finally uh threshold schemes even if on the client side this is a threshold crypto, we're going to call each piece hidden a separate key. Okay? Going on with our model. So, we have keys, we enumerate them one through n, and each key has a state. It is either safe, lost, leaked, or stolen. Now, together, we have a scenario. A scenario is a vector of the states of the keys.

So, a vector of the different states. Now, given a scenario vector, we can reach the availability vector for each of the parties. So, the owner's availability vector is going to be sigma O, with its element I is sigma I, and for the attacker, similarly, sigma AI. So, if sigma I is safe, for example, then the in the availability availability vectors, it's available, it's true for the owner, but false for the attacker.

Let's take one more. In case of a leakage, it's true, it's available to the owner, but also available to the attacker because the key was leaked. Yeah. Now for now, actually for this work, we're going to assume that there are probabilities for the events of for the different events, different states of each key, and the probabilities are going to be independent. So, the chances for one key being in a state is independent of the probability of another key being in whatever state. So, there are a total of

four to the n possible scenarios, and each one has a probability given by the product of the probabilities of each of the states. Um Uh, for this table, I'm assuming the keys are symmetric, so the same probabilities for both keys. So, for example, for safe and lost, the probability is P safe and P lost. Uh, the vector for the owner is true and false, right? Safe and lost. And for the attacker is false and false, safe and lost. And so on. Now, a wallet is then a predicate on the availability vector.

Okay? For example, let's say we have three keys, one to K1, K2, and K3. Then, the wallet, uh, requiring K1 and K2 or K2 or K3 will look like this. Okay, that's a wallet. And we're going to say this is a model choice. You can have a different choice and it will result in something different. But, we're saying that a wallet is successful if the owner can authenticate and the attacker cannot authenticate. The reasoning is that if the attacker can authenticate, he will be very quick.

We want to be conservative and not give him that option at all. So, we're only interested in cases where the attacker cannot authenticate and the owner can authenticate. And the probability of failure is the probability of an unsuccessful scenario. I mean, the probability that the scenario will be an unsuccessful one. Moving on from the model, naturally, we're looking for optimal wallets.

So, here's an option. Let's just scan the entire range of options and, uh, see what the best wallet is. So, how many wallets are there? Wallets are, in fact, monotone Boolean functions, right? They only switch from false to true. If you learn another key, you will not be less able to evaluate. So, it's a monotone Boolean function. The number of monotone Boolean functions is the Dedekind number um almost. So, if we have uh no keys, we're going to have no wallets. Uh there are still two uh monotone functions, the constant false and the constant true. We're not interested in those, obviously.

If we have one key, uh so yeah, one key, then there's just one wallet, K1. Um so again, the Dedekind number is plus two, but that's not interesting. With two keys, we already have four options. Why right? We can use just K1, just K2, the AND key, K1 and K2, and the OR key. And the the AND wallet or the OR wallet, K1 OR K2. With three keys, we already get to 20. These are the options. Uh this is requiring just one of the keys. This is requiring all three of them. You have somewhere here, yeah, any pair, specific pairs.

The OR key, any of the OR wallet, any of the keys, etc. So, after three, we're fine. Four is going to be larger. 166 wallets. Five is going to be even larger. And we know the Dedekind number. So, the Dedekind number grows very quickly. In fact, the Dedekind number beyond eight is not known to humanity. We only know up to eight. So, we cannot hope to go through all the possible wallets beyond eight since we don't even know how many there are.

Instead, uh we're reduced to evolutionary approximation or um or simulated annealing. Uh I'll do this one for this work. Uh so, you start with a random population of wallets. Uh and iteratively, you select some subset. Say, you select three wallets from this random population. You choose the best one among them. You make some random changes. You take the result, you put it in the next uh generation. You do this until you have the full generation, then you start again until it stabilizes.

Now, let's get some results. One key we can go through all the options. This is the options. We're going to look so over a few of those. So, let me go through this. So, this is the wallet just A1. Uh we'll have more keys later on. I'm assuming a symmetrical distribution, so they all have the same probability of leak and of loss. Okay? So, this is more probability that it's going to leak. This is more probability that it's going to be lost. This is both of them are high. So, obviously dark is good as the probability of leakage and loss gets smaller, we get a better uh wallet security, smaller probability of failure.

And here through most of the examples, we'll have probability of theft is 1%. Does this make sense? Okay. So, now two keys. Same question, but so this is like a slice of a three-dimensional graph where you fix the probability of theft. Exactly. .01 Exactly. Mhm. Yeah, that makes sense. Um so, you have like the key leak and key loss or it's possible that they're both Oh, never mind. You're only looking at the diagonal where they sum to Yeah. Yeah.

Otherwise, you'd get too many percent. Yeah. Okay, expanding to two keys. Now, let's look at the end key and the or key. You get a similar result. The symmetry is obvious. Uh so, the end key is more resilient to leakage. So, even if one key is leaked, the attacker can't take the money. And the OR key is more resilient to loss cuz even if we lose one key, we're still able to move the money. To authenticate. Yeah.

And now things become interesting. Which wallet is better for two keys? So, again, the probability of theft is 1%. We get this. I'm going to switch to 4% just so that's a bit more uh uh obvious. So, here, I mean, it's the same axis, but uh this is the category which wallet is better. So, if leakage is very likely, then the AND is better. And if loss is uh very likely, then OR is better. But the interesting area, the area we really care about is around here, right? We're looking for keys that are unlikely to be uh faulty. And here,

the best wallet is actually to just use one, either K1 or K2. Okay? This might not be that intuitive, but only with actual careful formal analysis we get uh we get here. And what This is just the So, when you say best, you mean maximizes the probability that the honest party can authenticate and an attacker can't? Yeah. Precisely. And is there in hindsight uh intuition for the green stripe?

I Not really. I mean, uh Yeah, not yet. Can you try graphing in three dimensions and like That's what I'm curious about cuz it looks like as you go on this dimension of increasing the probability of theft, that square is getting wider, isn't it? Yeah, I mean if for this you can actually uh write down exactly the the areas. It's it's very clear. I mean that this will become wider. What you expect? Um but with the three-dimensional graph it's like It's it's a pain to read.

It's a pain to read. Uh but but I'll I'll I'll show you some some more of these results and hopefully it will help gain some some sort of intuition of what this looks like and how unintuitive this is. This is three keys. Um some good news here. So again, a lot of loss uh probably best or but uh here you see close close to the basis. You see that actually the best wallet is the any pair. Which is great news because this is the common intuition and is used in a lot of cases. And this actually stays the case even if you increase the theft probability. So below it was no before

it was no theft and this is with theft. Actually high probability of theft so everything becomes very pronounced. You see that in the area we care about we get this any any pair. Four keys, about the same. I mean if you transition from three keys to four keys you need to make a decision, right? Do you want two out of four or three out of four? And uh well this is roughly I think what one would have expected. If you add theft it becomes complicated and again we see what we saw for two keys.

So the close to zero probability the best wallet is actually not the symmetric one. So not any pair and not any triad. So to understand the behavior with with multiple keys we're going to switch to these graphs. Here I increase the number of keys and we look at the failure probability of the wallet. And this the goal is to show here the optimal wallet.

So, up to five my quick Python simulation can just go through all the options. Beyond that, there two curves. There is the guess, which is just any symmetric keys for up to whatever. And there is the the heuristic. Okay, the evolutionary algorithm in there. So, this I think is what you'd expect, right? This is either only loss or only leak result in the same result. You get exponential improvement with the number of keys. When there's only theft, haha, things become a bit more surprising.

But, this kind of matches what we saw earlier. So, with two keys, you're just as good if as if you just used one. With four and three, six and five, maybe it goes on, I don't know. I'm being honest with you here. The evolutionary algorithm wasn't able to do as well. Obviously, you can bootstrap it with the guess, but I wanted to see how it does. And so, it wasn't able to reach the optimum here. And this is I think a more interesting example. Now, the keys are not symmetric.

Okay, so the first key has a 1% theft probabilities and the rest of the keys have 1% loss probability. So, the general trend you see here is still kind of exponential, but you see that the symmetric solution doesn't do anymore. You need something else. This is not surprising, right? But, you need something else. And here the evolutionary algorithm at least continues this trend. If you have any idea on how to find this in a non-heuristic way, then I'd love to talk to you. Now two two small things to to note here. One is like practical implications of this.

This is a three curves showing you the fault probability with 1% theft probability, but with different loss probability. And you see here that you're better off using six keys that are prone to loss than three keys that are not so prone to loss, like order of magnitude better. And I know, I mean if if you speak to large institutions, their strategy is often to place one very good very big secret in a vault underground with armed guards and not replicate that and use some hot wallet strategy while this is kept secret. This demonstrates that it's in fact better to have a few secrets maybe hidden a little less underground.

You will get you will get better bottom line security. Yeah, this I think is clear. Now I want to explain two curves here. This is the probability of loss for two keys. And we have a third key whose probability of loss goes from zero to 10%. And the rest is leak probability. So if the loss probability is zero, then the leak probability of key three is 10% and vice versa. So we have like a security budget and we're shifting the

fault probabilities of key three between loss and leak. So this is an analysis of the asymmetric case. You see here here the um uh keys are symmetric kind of. So they're they're all probably lost. That's the main thing that can happen. And so, the best wallet is the two out of three. But at this point, suddenly the third key loss probability uh becomes uh so high, it's not likely it will be leaked that we're better off just oring that key three.

So, key three is enough because it's unlikely that it will be leaked. And then, either that or both K1 and K1 and K2. And if we had uh the I mean, the flip side you'll see it's symmetric. And if you have a 5% key loss and 5% uh leak probability, then it's like it's a version of this where if it's very likely that uh P3 is lost, then we'll or it. But it's if it's very likely that it's leaked, then we will require it in both cases.

Yeah. It's unlikely that it will be lost. If you want to play more with it, uh we have an online uh calculator. You can feed in your probabilities. You can try to design a wallet and calculate a probability, or it will calculate the optimal wallet from from you. Uh this was originally uh designed a while back, and uh this week uh there was a a hackathon group at the IC3 bootcamp uh at Cornell. And this is the new result where not only it will compute the optimal wallet for you, it will actually take from you your uh your private keys

and generate a smart contract you can uh deploy on uh Ethereum. This is all done on on client side, including the compilation of the solidity. So, nothing goes to any server. And that's what I had to say about uh authentication. Um but let let me pause for a second for a question about this. I think this is new and there are potentially different ways one can take this.

Yeah. So, one thing that point that jumps out from the graphs is that it's quite sensitive to probabilities, right? Like the answer. So, like how I'm wondering how one would get any amount of confidence about what those P's are. So, and I guess a related question would be like if some you know, random promising project said, "Bring your key and multi sig, what you can and what you can't and what you tell them." So sorry? If some project asked last you what you can and can't do in a key and multi sig. Yeah. What would you tell them?

So, that's a that's an excellent question. I think I think this is really one question because the to make this practical, you would want a wallet that is resilient to miscalculation of your probabilities. So, this gives you the ability that did not exist before to actually evaluate your fault probability. This is very important especially if you have large sums of money. Now, to design your wallet based on that, you would probably also have some estimate on how accurate your estimation is of your key fault probabilities. And this is a thing that is waiting for future work.

Yeah. So, how sensitive is that for like allocation of my private keys and disaster? How sensitive is that to, for example, nailing the optimal design with, say, 20 keys versus like like, for example, one thing that's coming to my mind is like if you used a union bound over the two sources of failure, probably like that's much more tractable than trying to nail the exact probability of failure. Um is losing a factor of two in the you know, like finding is is that like useless or is that if you can do that for a loss of keys, that would probably still be useful for some applications.

Since right now 20 keys is extremely far from tractable, then any approximation would be would be appropriate. You'd still need to figure out the process which I'm I don't know how to do at this point. Um but like like I said, I'd love to discuss. Yeah, but like again, when you're talking about this Dedekind number, seems like that's ordered though, but at least in your earlier examples, like if you assume the keys are symmetric, then that number goes like way down, right?

You're probably right. I was not able to find that number yet. Uh in the symmetric keys, it should be much more uh tractable. And um in in most of the cases where uh I could actually run through all the options, the optimal wallet was simply asymmetrical one. Maybe not the symmetrical for using all the keys, but one less. But that was the best. So they they make the asymmetrical wallet design that you assume are at least symmetrical, but if you assume all the keys are identical, then yeah then like a lot of different configurations are equivalent, right?

Yes, but the question is how to reduce them and how to find the ones that you care about. Um yeah still also an open question. Maybe a lower hanging fruit, but uh yeah. I I just 20 seconds. I I didn't immediately realize that this was the Dedekind number. So I had an approach similar to to what you just said. So, let me count the number of possible wallets. So, I took a marker and whiteboard and started running through this and after a a couple of hours of feeling very stupid, I I started looking around and it turned out that this is an an actual hard problem. So, there there are

trickier things hiding here than what I expected. Okay, now for something completely different. Can we defer this to later? Yeah, because I have an ambitious plan to talk about incentives a little bit. So, something really completely different. Classical consensus protocols are permissioned. We know who's going to participate. There is no obvious transition to the permissionless world. Um we need an algorithm to be resilient to a attackers and it's okay. The thing things should work okay when the majority of mining power and I'm talking

specifically proof of work here. The majority of mining power is honest and there is a smaller attacker than things should be okay, secure and if the attacker is larger, it will break. We're fine with that. But, why would these honest parties follow the protocol because they are incentivized? Right? And we want to look for a Nash equilibrium where they're all better follow the protocol and not do something different. Now, Nakamoto's proof of work blockchain works like this. I know you all know this, but there is one fine point I want to go through. So, anyone can join. They generate these blocks. What about fairness? We get that from proof of work.

If you have about 1/4 of the mining power, you should get about 1/4 of the block because exponential distributions, yada yada. So, the wins are proportional to your computational power, which actually means that your revenue is proportional to your computational power and I mean that uh in terms of dollars per month. Okay, this is not immediately intuitive. The reason is that we have this difficulty tuning mechanism. So, if there is more mining power coming into the system, puzzles will become harder.

If there people leaving, puzzles will become easier. But, at the end of the month, you really only care about your ratio of blocks on the chain. The state needs to be immutable even though there can be forks. So, we pick the longest chain and the minority cannot outrun the honest chain except with negligible probability. Great. What do we actually want from the system? Three things as defined by Garay et al. and later by Passel et al. Consistency, growth, and quality.

Consistency meaning everyone agrees on at least a prefix of the past. Growth means there is a linear increment extension of the ledger. And quality meaning certain fraction of No, this is only a rough, but this is enough for us now. A constant fraction of the blocks are generated by honest parties. These are the desiderata. This is what we want from the blockchain.

Now, Nakamoto said we get security with an honest majority, but if we want to talk about selfish selfish behavior, this is the work with Gun Sirer. Then we see that the attacker can do better, right? They risk losing some of their own blocks, but they get the honest parties to lose a a lot of blocks. So, their ratio of the blocks on the main chain is higher. The analysis of this is done with a state machine. It's pretty easy because we can clearly define all we need in the state with just a single number and zero prime.

Standard analysis and we're done. Bottom line, there are different curves here for the revenue of the attacker depending on the rushing control of the network. But even if we assume no rushing, so the most optimistic assumptions, after 1/3, the attacker rational player prefers to be selfish and not follow the protocol. Great. Now, in 2017, there was a major progress to address this in fruit chains by Rafael Pass and Elaine Shi. And what they did is the following. They said the miners don't just try to append blocks to the end of the chain. They also try

to mine earlier in the chain for a different type of block. And so, if it's at the end of the this chain, it's called a block, expanded regularly. And if it's here, it's called a fruit. The fruit are actually going to include transactions. So, if the miner managed to generate a fruit, he puts the transactions in the fruit and extends adds the fruit. Hangs the fruit on the chain. And there can be more fruit, etc. and there can be more blocks. Okay?

So, the same mining effort will result either in a fruit or in a block. Now, you proceed with this, you get many fruit hung on the blocks, and then each block also has pointers or hash pointers to fruit earlier on. Once a fruit is referenced by a block, the transactions of the fruit are actually considered to be placed here. And whoever generated the fruit gets rewarded.

If a fruit becomes very old without being referenced, then it's called ripe, it's discarded, no reward, and no no transactions, just lost. All good? Okay. So, the desired behavior in fruit chain is the following. The longest uh blockchain, like Nakamoto for the main chain, and then you add fruit not too recent because there might be small reorgs in the chain. That's a common behavior in a blockchain, and that's okay. So, not too recent and not too old because we don't want it uh uh to rot.

And then when you create a block, you point to all the unreferenced fruit. That's the desired behavior. However, here's a deviation. Rather than point to all unreferenced fruit, you point only to your own unreferenced fruit, ignoring fruit generated by others. Now, this deviation carries no risk. Whatever everyone else is doing can only help you, and you will only reference your own fruit, so you will get whatever reward you might get. Now, what this protocol guarantees, this is an epsilon Nash equilibrium.

So, the protocol guarantees that you cannot make more than some negligible amount by deviating in any way, and specifically in this way. However, the bottom line is that fruit chain is always almost a Nash equilibrium. You're always better off deviating. You will earn only a little bit, but there is no risk. Yeah. So, just to clarify, there's no reward in the block, so that's how they get around selfish mining.

Correct. If you had rewards for the blocks, you would run the risk of I mean you'd open the door to selfish mining to some level. And what we what we learned recently from this work by aviation company is that miners do take advantage of small gain opportunities. This has been to my knowledge this is the first observation in the wild of selfish behavior on the on the consensus layer.

Moving on. I'd like to present color dag. This is work with Itai Braun, Danny Dolev, and Joe Halpern. And the idea is the following. So, what we want to do is get better resilience. And we're going to use a dag rather than a chain. There are a lot of works that use dag starting with Levenberg's Sompolinsky and Zohar from 2015.

We don't care for this work. You can you can do whatever you want with a dag, but for this work we only use the dag for incentives. We don't care about performance or bandwidth or this is just about incentives. So, color dag uses three techniques to achieve this resilience. First of all, we color the blocks. Each block gets a color uniformly at random. After you generate the block, you find out what its color is. Um in practice you can use like the the LSB of the of the hash.

And this way we take the original graph and you divide it we divide it into different miners for each color. If we increase the number of colors, we increase the number of miners, and we reduce the probability that there will be a fork in one of the miners because blocks of a single color become more rare. So, we actually reduce arbitrarily the ratio, the rate of benign forks.

And from now on, we're only going to look at a single color. Actually, we're going to look at each of the single colors separately. Okay, so we removed the the forks inside a single color, and then we can now look at each of the colors separately. The goal Okay, the goal is to um assign the rewards in a way that will make extending the DAG the best response, and by extending the DAG, I mean adding a new block that references all leaves and publish it immediately.

Thank you for this question. Yeah subgraphs. Um So, specifically, I mean, you take all the for for uh yellow, right? You take all the yellow blocks, and you add an edge if there is a path from uh two between two yellow um uh blocks, and there is no path between these blocks that has another yellow graph in it, a yellow block in it. And that's a miner. That's like standard graph theory. Nothing uh nothing fancy.

For example, uh No, it cannot be disconnected because every every Well, I mean, we we start with a genesis that has all the colors, a white genesis. And then, uh every block will have at least one predecessor of its color. So, there might be forks here, but they're very rare. And by increasing the number of colors, we can make them arbitrarily rare. And so how many predecessors does each block have? As many as it needs. I mean, uh you you should you should reference all leaves you are aware of.

So, it depends on network properties. Okay. So, now let's look just at one color. And this will be uh for every color. So, the second uh technique uh is symmetric penalty. Now, since we reduced the probability of forks, if we do see a fork, we know that it is the result of some malicious behavior. Someone intentionally uh uh created this fork. However, we don't know which one.

Right? So, what we do is uh we apply a symmetric penalty. So, neither block gets any reward. For For simplicity, I did not say this, but for simplicity, assume the rewards are either one or zero for all blocks. And is that penalty burned or does it go to the person who reports it? No one needs to report it because it's evident from the graph, and it is burned, yes. So, it never They simply do not get the reward.

But that is reporting, right? Cuz they could not like they could not include a reference to one of them, right? Right? Like in your example there. Uh this guy could not could have avoided referencing this guy. Yeah. Right. No, we I I see I I see where you're headed. We're not doing that. So, simply simply symmetric penalty here, this guy gains nothing. So, It's the same this Um it is jumping ahead a little bit, but um W- What we will show is that it's the best response to simply follow this

protocol uh in in the sense of the strict Nash equilibrium. No, we do not look into that. So, it's all internal. Yeah. It's a that's a good point. Now, why would symmetric penalty even make sense? We're punishing everyone. So, intuitively it's obvious like right? If I deviate and I get no reward, then I get no reward. But, the point is this. If if an attacker gets X over X plus Y, so his reward divided by his and everybody else's reward, and we apply symmetric penalty, then we

get X minus D over X minus D plus Y minus D. And if X is a minority, so any minority attacker, this would be worse than this. So, in absolute terms, the situation of the attacker would be strictly worse because of the symmetric penalty. And there's another catch here, uh which is that these symmetric penalties can be applied after a very long time, right? I can now go and create this fork from 2 weeks ago, and then someone in 2 weeks ago should have been penalized, even though they maybe already got the reward and used it, right? So, this is why we have the third mechanism, which we call unacceptable blocks.

The The idea is that we take blocks that are obviously from misbehavior and we call them unacceptable. Not only they do not get a reward, they also do not cause punishment or penalty to others. They're simply ignored. They will be on the DAG or not, but they are going to simply be ignored. Uh The the formal definition maybe is not very important, but it's it's simple, so I will go over it quickly. We define a single canonical path. That's a longest path starting from Genesis and going all the way to a leaf.

And then if a block is too far, meaning the smallest cycle of this form is larger than some uh parameter NL, then this block is called unacceptable and these blocks are acceptable. Yeah. But if there's no nothing to try, but if the B2 is not to refer to B, is that B like abandoned? Uh well, if we look at a snapshot, then we will logically add a virtual node at the end and assume that B is connected to that virtual node.

But eventually some honest miner will see this B and actually add it, so it will eventually the cycle will form. So this is the summary. We color the blocks, we apply symmetric penalty and ignore unacceptable blocks. And what we achieve is what we call epsilon Nash equilibrium. This is a different solution concept that we propose and it says the following. We look at histories, executions of the system. And we assume an extremely strong adversary because we don't want to mess with the probabilistic behavior of uh of the Markov chain. So we assume an extremely strong adversary. And it works

like this. The scheduler chooses the minor sizes throughout time for every step under the restriction that there is always a strict majority of honest miners. And then the scheduler chooses who gets to mine in every step according to the sizes chosen in the previous step. And then the attacker having seen this schedule chooses their strategy. So, it's a very weak model or an incredibly strong adversary that really sees into the future.

And in this model, the attacker takes no risk because they also they always know what's going to happen. They will never regret a step. And so, each history has a probability over the scheduler's coin. The the history has some probability. And what we're looking for is some is is an equilibrium in one one minus epsilon of the histories where epsilon can be made arbitrarily small. In other words, we want and we we show that color dog is this. So, an epsilon sure Nash equilibrium. In almost all executions with high probability, it is a strict Nash equilibrium.

So, first we define a safe history for for our system and has certain certain good properties. Unlikely events uh do not happen. And then we prove that by choosing appropriate parameters, there really are there really is an overwhelming probability that we will have a safe history. And then we show that given a safe history all honest blocks are acceptable. So, in a safe history, the attacker cannot make a block an honest block unacceptable. And for every honest penalty, there is a matching adversarial penalty.

Which means that the strict best response in a safe history is to follow the protocol. Which leaves us with showing you that this is actually a ledger as we wanted it to be. So, um we're using here a simple choice. I As I said before, you have the DAG structure, you could do something fancy, maybe for a different talk, but here we simply pick one of the colors um and say this is the ledger color and blocks of this color will have the transactions, and the longest path of this color will be the the ledger.

And so, consistency quality uh chain quality and growth, we get uh immediately from these properties of the safe execution. I'm not going to uh drag you through them. There's just one interesting point that I want to uh emphasize here, which is revenue consistency. So, most blockchains uh um Ethereum uh and fruit chains included, you can look at the longest chain and realize who has how much. The the revenue the rewards are defined by looking at this longest chain and you're done.

And here we also need to show explicitly that the rewards remain consistent. It's not enough to show that the longest chain the ledger chain is consistent, we also need to show that the rewards are consistent and one cannot come a week later and change the rewards uh back in time. And this happens because of the uh acceptable block story and and again, uh it's derived from the safe history properties. So, this was the story of incentives uh um talked about better protocols and specifically about color DAG.

And uh I would be very interested to talk about uh future problems applying to both proof of work and not proof of work particularly things that cross uh uh cross layers. So, protocols at the application level that take advantage of minor behavior, minor strategies, and exogenous incentives as Joe mentioned before. That's it. Thank you very much. Um I have a couple questions about color dag. So, first is if I just wanted the theoretical

result you have. So, if I just wanted the theoretical result, let's say I didn't care about whether this would make sense in practice. Like I could say I just got rid of the colors, everything is one color, I still use the same rule that when I ask people to point to a fork, whenever there's a fork, I just give no one the reward. And and would that get the same theoretical result, but that's just not usable in practice because there would be natural forks? So, you gave up the coloring and the notion of acceptable blocks or just the coloring?

For now, keep the notion of acceptable blocks. So, if if you if you give up on coloring, you would still get uh something that would work, but your bounds would be different because there there is a certain probability for uh arbitrary Okay, and okay, so then the second part of that is that um Uh maybe I wanted to sharpen this point a little bit. So, we we need for the competition, we need the honest blocks, the honest miners to extend the chain quick even in this world. It's It's It's a chain that has to extend quick.

And if there are forks, then their mining power is lost because of that. And there are I mean, you you can go back to the literature and there are expressions for exactly what you would lose in terms of resilience. And And then I said, okay, the the second question is going to be in terms of the acceptable blocks. If I also like if I just wanted to focus on the theoretical result, Mhm. could would that actually be easier if you didn't have the concept of acceptable blocks? Because then you could just use the math that you brought on the slide. You said that for every conflict, it's one attack, you know, the attacker is using a block, Genesis is losing a block.

And I'm wondering if it would just be literally the math you had on the slide. So, if we're being if we're being theoretical, then we need to be very accurate and then we're going to start having problems. Sure. Because I mean, if you if you get uh if you get all the way down to the details then the analysis is done for a bounded period. I mean, we need to assume something on the duration of the execution. If the execution ran to infinity, then every bad event will happen. So, the execution time is bounded. Now, if you don't have any restrictions on this acceptability notion, then someone could next year revoke I mean, after the time is done,

the attacker can just cause penalties to participants from last year. You need to redefine the model in a very curious way. Sure. And then let me clarify again. If I just wanted the theoretical result, would it still be the case that the attacker is paying more like attacker has to pay something to get rid like they're they're wasting their own block, too. Oh. of an agreement from a year ago. And then you're saying they they Yeah, that might work. Again, it it will not result in a sensible result, but that would be enough, I think. Yes.

And then the last last thing I want to ask is you mentioned that you simple you you targeted this epsilon for Nash equilibrium. Yeah. Because that simplified the analysis. Do you know that it's not a Nash equilibrium or it could be a Nash equilibrium? The the the reason the okay. It's not a Nash equilibrium. There is a probability that the execution I mean this is a probabilistic world. There is So if you have a weaker adversary, so the the adversary doesn't know the future.

Yeah. Then is it possible that it's a Nash equilibrium, but it's just a huge pain to prove or you know it's not a Nash equilibrium even if the adversary doesn't know the future. So this is still in the works, but if if you switch to a rational sorry, if you switch to a a realistic adversary that does not know the future, then you'll get much better um bounds. So here with this impossibly strong adversary, we get concrete result I I can I can show you on a board, you know.

But if you actually want to let the math run and use a machine to to find the optimum, then with a an adversary that is just looks at the probabilities and and has to guess what the best response is, then um we have initial results showing that this becomes very practical. So you're saying that right now it could be all the way up to 50% 49% adversary who doesn't know the future still is incentivized to follow it that that's possible.

Yeah, it it it becomes so I I these results do not exist yet. So I don't want to commit to anything, but if if you want to do a practical analysis then you get a bit further from the 50% because network because you still have some probability of you always still have some probability of forks, but uh uh you get closer. Yes. Yeah. It's kind of a follow up on the the prior question I was asking about.

What if like those two parties are actually the same so then the second one has kind of no incentive to report, you know, that there was a a fork. So essentially a coalition. What? Essentially a coalition. Of two miners. No, I mean what if it's just the same miner? The same miner? Yeah, so this is exactly what we're maybe I'm misunderstanding the question, but this is exactly what we're secure what you're secure against. It's I mean maybe maybe what you're saying is the following. You're saying if I already had a fork and I paid whatever I paid because of the fork then I have no incentive to immediately close that down until I

reach close to the acceptability region. And that's I think something that in a in a practical sense is something I would actually like to improve. But this protocol does not do it yet. Yeah, that's interesting. I thought I was thinking I was mostly just thinking about like incentives around reporting this thing, but so I guess you're saying like you're secure against it as long as it's like limited to a small coalition, but bribery would basically, you A whole new game.

Yeah. But there's no Yeah, I think so. But there's no like there's no for, I guess there's no incentive to report that. So I I I I unfortunately I just flashed it briefly when I mentioned future directions, but I think that this is a critical question to answer. This is not this work, but it's a critical question to answer, which is uh uh against how much bribery is your blockchain secure? Is your protocol secure? That's a basic question for future work.

Thanks very much.