Rethinking Crypto Attacker Models with Mahimna Kelkar | a16z crypto Research Series

Transcript

Okay, welcome everyone to today's A6Z crypto research seminar. Very pleased to introduce Mimna Kelkar who was our very own intern from two summers ago. Uh he's just wrapping up his PhD right now uh under Ari Jules's supervision at uh at Cornell. He's worked broadly across the blockchain space, consensus, cryptography, now increasingly game theory and mechanism design. Uh so welcome back. Very excited to hear about rethinking crypto attacker models. >> Thank you for the introduction. Yeah, really excited to be here again after as Tim mentioned being an intern two years ago. Um today I'm going to talk about uh rethinking crypto attacker models. A little bit of a technical talk, a little bit of a philosophy perspective as well.

So, it's kind of no secret, you know, for the past 15 years, blockchains have seen a sort of meteoric rise. I mean, that's kind of why we're all here. From Bitcoin, if you look at, you know, in 2008 or 2009 as sort of a cryptocurrency that didn't require centralized coordination from the government to now sort of thousands of companies, hundreds of millions of users, and a lot of applications way beyond just cryptocurrencies. But from sort of an outsider's perspective, there's this dichotomy that's usually associated with blockchains. So on the one hand, you have this sort of trillion dollar potential impact applications in fintech or decentralized finance with things like election transparency, uh legal

industry with smart contracts, even something like gaming. But on the other side, there's also this trillion dollar hype phenomenon where you have constant articles on the price of Bitcoin today or what the last NFT sold for or even things like outright scams which lead to 25 years in prison for example. So how do we sort of uh deal with this trillion dollar impact question versus trillion dollar hype? So the question we want to ask is like how do we get masscale adoption of blockchains? So there's a few different things that we can try to think about how we get masscale adoption. So the first obvious thing is of course performance. We have this great functionality that blockchains can provide us but how do we scale this in a way that's practical for millions of

users. The other interesting thing is regulation. How do we separate sort of uh the noise from the real applications? And that's something that can potentially done with regulation. But today what I'm going to focus on is this third aspect of security. So what does fundamentally blockchain security and the security of blockchain applications even look like? And my sort of central claim here is that one reason why we see a lot of attacks on blockchains, a lot of skepticism associated with blockchain protocols in general is that even as researchers, we don't fully understand how to secure blockchains and their applications. So blockchains from a traditional system security aspect operate in a completely new setting. So

this completely new sort of decentralized setting that is very different from the applications we've built from a classical security sense. There's sort of these complex interactions between different protocols, different security models, incentives come into play for instance. And the other kind of thing is we're building these protocols in essentially the wild. So any design vulnerabilities that pop up. So design flaws, not just uh program errors, but sort of these complex design flaws that pop up can be effectively monetized by by attackers or anonymous attackers trying to steal from these applications.

And we've seen a lot of these attacks in the wild on blockchain protocols where complex interactions between different, for example, DeFi applications um have resulted in millions of dollars of loss. The real point here is that blockchains sort of fundamentally intertwine many different research areas. So we know things about like cryptography and distributed systems which are often used for just building uh secure protocols in the modern system security context. But now for blockchains in particular, we've had to think about mechanism design, game theory, even things like macroeconomics because blockchains come with this built-in money aspect. But moving forward, we also want to think about governance, how to do sort of these DAO protocols with social choice

and potentially many more maybe from a legal context for example. But one thing's sort of true that security can no longer be thought of in just one vein. We have to sort of think about security more holistically. And that's kind of my fundamental thesis here. Like the purpose of this talk is to argue that we need sort of a first principles approach to uh designing these secure protocols even thinking about what security means in the decentralized uh context. This isn't meant to be uh sort of an approach to defining what security means. I think we're sort of really far away from combining these different areas into one seamless model. But it's more so about um giving examples from my research of what can go wrong when you

sort of try to meld models from different uh fields. So I talked about you know using cryptography, droid systems, mechanism design and a lot more in this talk. So I'll I'll talk about sort of a couple learnings from the research. Um the first learning is that security in these decentralized settings has a lot of novel challenges and in particular I'll show sort of new attacks that make us rethink how we define security because they work by violating underspecifications and implicit assumptions in the models uh of security that we've thought of. And the learning number two is that understanding how to secure blockchains and their applications has broader utility um even

for the purpose of sort of modern system security. And I'll show this by showing sort of new insights of how thinking about blockchain security can provide on just normal general security models. So in this talk in particular I will u talk about two works of mine um and these are sort of new attacks that make nefarious use of emerging technologies and these are motivated by blockchains but the impact is potentially much broader. The first attack I'll talk about is what I'll call uh new incumbrance attacks that make nefarious use of trusted execution environments or multi-party computation protocols which are typically used for building secure applications. And this actually ends up

providing new insights onto how cryptography defines knowledge and this proofs of knowledge primitive itself. And we provide a new uh kind of knowledge definition called proofs of complete knowledge. In the second part of the talk, I will mention uh new attacks on accountable cryptography by making nefarious use of blockchain smart contracts essentially as a coordination mechanism between attackers. And this will provide new insights onto collusion and incentives in general uh amongst cryptographic protocols.

Okay, so let's get started. Uh the first one I'll give is these encumbrance attacks and definitions of knowledge in general. So sort of a common intuitive goal that's followed for a lot of these cryptographic protocols is the following. So usually there's a completeness like goal which says that an honest user who knows the key will succeed in the protocol and there's usually a soundness like goal which says that an adversary and this is uh this is a person that doesn't know the key will fail. But what does it actually mean to know this key? So here's sort of the implicit mental model that we think about when we design these protocols. So Alice uh knows this key if she can explicitly furnish it as private input

to a protocol. So for example, if you have a protocol with some step uh where Alice computes an output um with some function of the key and an input and then sends it over to a remote party Bob, what you kind of think about in your mental model is that Alice has this key and input locally in her state. She computes the function locally and then sends it over to Bob. But what I'm going to show is that there's actually a subtle discrepancy in this mental model that leads to a new class of what I'll call encumbrance attacks which eventually lead to new insights on how we define knowledge within cryptography. And here's sort of the highle picture of encumbrance. On the left side we have this protocol expectation of the key and input being

held locally by Alice. And on the right in the encumbrance setting, what actually um so what we're going to do instead is that the key is going to be locked inside of this lock box instead of being owned by Alice and access to this key is going to be partial and hidden in this lock box. So Alice can query the lock box with the input and um get some response from it. And what I'll call these new encumbrance attacks is that in fact locking a key in this way in a partial way in a hidden way can break protocol guarantees because the protocol cannot distinguish between the expectation world and the encumbrance

world. And um what's more interesting is that this lockbox can be instantiated through sort of common security tools like trusted hardware uh and MPC. So just to uh give some background on TEEES, I'll illustrate some concrete attacks after this point. But um just to give some background on Tees, everything I'll say will also apply to sort of MPC based attacks. Um but I'll for concreteness I'll I'll talk about TEES. So very sort of informally trusted hardware trusted execution environments are sort of these tamperproof hardware [snorts] components built into the CPU uh that can hold sort of private data and do sort of arbitrary um computation

on it and these are sort of becoming popular in industry with things like Intel SGX or ARM trust zone or AWS nitro and kind of the property that these provide are as follows. So there's usually an integrity property which means that the even the operating system or other programs that are running on the computer can't tamper with the control flow of whatever program is running. And there's like a privacy confidentiality property which says that even the operating system or other processes can't learn anything about the internal state of the program or sort of the data that's held inside of this trusted hardware. Now in the context of encumbrance, what we're going to do is essentially place this key uh inside of the trusted hardware box. So we'll

actually just generate the key inside of the trusted hardware itself so that only this trusted hardware knows what the key is. And the idea here is that the program of the TE will restrict access to this key. And this is where our incumbrance attacks are going to come from. The typical assumption that's made in a lot of protocols is that a user won't share her key. And this is kind of natural to make because if I share my key, uh, then whoever I share to can just completely impersonate me. They can see all my money. They can take my identity and so on. So, usually there's this assumption made that a user won't share her key. But what encumbrance allows this user to do is sort of share or rent partial access to different functionalities of the key. So because

the key is held inside trusted hardware and nobody knows the key uh and you can use the program to restrict access or split access to the key uh what you can do is keep only the access or the functionality that you want and sort of rent or sell any of the functionality of the key that you no longer care about. And here I'll also sort of mention that all of these attacks are essentially caused by the user willingly encumbering her key and um colluding with the adversary in some sense. I'll give some sort of concrete powerful attacks. The one I'll start with is um sort of a powerful attack on blockchain voting in a way that kind of gets around all prior work on coercion resistant or bribery

resistant voting. So in a blockchain context, you can typically think about a user's wallet or key uh let's say having two uh two use cases. One is it has some money that the user can spend and the other is let's say the key also allows the user to vote privately on a proposal and let's say a DAO. Now suppose that Alice is willing to be paid for her vote. She cares about her money but she doesn't actually care about her vote. Um, so she's willing to just be bribed or paid for whoever uh the briber wants to vote for. Now, in some sense, Alice can't just give her key to the briber because if she does that, then the briber will just steal her money. But with encumbrance,

Alice gets a new power of collusion with the briber. So what Alice can do is she willingly encumbers her key inside of this TE and installs a vote by program as follows. So the program still allows Alice to spend her mo own money. So it will sign any transactions that deal with the spending of money and for this particular election it will only sign messages that correspond to voting uh for the candidate of the briber's choice. And what ends up happening here is that this is essentially a way for Alice and the briber to trustlessly collude to exchange a bribe for a vote.

Now notice like Alice is okay with the bribe because she only cares about her access to her own money. She doesn't care about the vote. She's willing to be paid for it and she still has access to her own money here. And the briber is okay with this because Alice provably can only vote for his candidate of his choice and she can't sort of double cross him and vote for someone else. So he's okay with giving the bribe as well. And it turns out that this breaks a long line of prior work on coercion resistant voting mainly because there are implicit assumptions in all this work that the user Alice has full access to her key at some point. Typically this is during some sort of registration phase before the adversary comes in or uh sometime

after the voting whether the adversary has gone away. But at some point during the protocol, it's sort of implicitly assumed that Alice has full access to her key. And this assumption is violated if the key is held inside trusted hardware in the first place. And what's interesting is you can sort of generalize this attack to create sort of hidden marketplace which can anonymously connect voters who want to sell their voting power to bribers who want to buy this voting power. So it's anonymous in the sense that uh these voters and vote buyers don't need to even know each other and hidden in the sense that it's hidden uh its identity is hidden from the voting platform. itself and we actually built a prototype of this in a

recent work and called it essentially a dark dowo. We also wrote this sort of recent paper on all kinds of shenanigans that you can do with this sort of encumbrance. Essentially the idea here is violation of what we called the single entity address ownership assumption which is pervasive in a lot of protocols. The idea that one private key means one owner. And this is something you can violate using incumbrance, right? If the key of the account exists inside trusted hardware, the program can allow you to essentially split access between different parties in a completely undetectable way. So, for example, if you have an account with five ETH, that doesn't mean that you have five ETH, right? It could be that you only have one ETH out of it, someone

else's two ETH, and then someone else has the rest of the two. Yes. um all these conditions need to be chosen a priority right so you need to hardcode them into the tea for instance the candidate you want to vote for so it's it's not something you can adjust so if I'm an adversary and I want to buy uh your vote for a specific candidate and in a month I want to buy another vote for another specific candidate we need to agree >> uh at the very beginning right we can't adjust it on the fly >> so um so in this new work basically we developed sort of a policy engine that essentially you have some starting state and then you have like a transition function of what you can change the policy to. Uh so in the case of voting

for example um if there's like a voting window that's only open for like a week then you can at the start of that week um have a bribe for that vote period. If the vote is like open indefinitely then you'll have to agree to it before that sort of begins. But if it's sort of like a bounded window, then you can kind of agree to it uh as uh like the new voting period is going on essentially >> and you can verify that. >> Yeah. So the the only concern is like any any access that you have right now.

So let's say I can sign a vote right now, but I should not be allowed to do it later uh because someone's going to bribe me for that vote. That's sort of the only attack vector in some sense for this like policy engine. Um and you can sort of prevent that in natural applications where I can't sign a message uh for voting on something uh two weeks from now because that um proposal itself doesn't exist. Right? So when that proposal exists then you can create the bribe at that point. So it doesn't have to be fixed at the start. One kind of really cool thing that's applicable here is the idea of selling unvested tokens. So the kind of example here is as follows. Let's say you have a VC investor who wants to invest in a startup in particular wants the startup

founder Alice to be incentive aligned and the typical approach you can do here is like the founder tokens are locked for a certain amount of time so they can't sort of dump their tokens and be uh detached from the success of the protocol. But what you can do with liquefaction or this encumbrance phenomenon is it can allow uh this founder Alice to privately sell her unvested tokens. So the idea is uh the tokens lock tokens through the smart contract on chain but they will be held inside a T encumbered address. So an address whose key relies in the TE and now essentially selling this token privately just corresponds to changing the owner and the trusted hardware and

nothing will be visible on chain. Um so sort of the founder can just sell all of her tokens uh privately to a third party without sort of the VC investor realizing this. >> Sorry. >> Do have access to secure randomness? >> Yep, they should. >> Okay. who who controls this TE. >> So uh so yeah that's a good question. So basically we actually developed this on a TE blockchain. Um so uh we developed it on Oasis which is sort of you can think about like a decentralized TE blockchain. From a theoretical standpoint all of this can be done with a single TE that is assumed to be live.

Uh so let's say it's held by someone and they're uh assumed to be live for any responses. And basically to get rid of that livveness assumption, you're just decentralizing the TE. So it's sort of like a T network of TE's that simulate a single T. So there's this platform called Oasis, which essentially functions as this TE blockchain. Another sort of really cool thing here is um this demo that we created called takemyap.com, which I encourage you to take a look at. And the idea here is we actually bought an ape for this demo and we allow you to own the ape, not just rent it, actually own the ape for 15 minutes. And the way it can work is as follows. So we allow you to create an

encumbered account. So a key an account whose key is inside of a TE and we transfer the ape to that account. Um, but the account doesn't allow you to transfer that uh ape outside of it. But you can still prove your ownership of the ape to the board ape yacht club. And essentially from the chain's perspective, you are sort of the owner of the ape just for the 15 minutes. And only you can sort of prove access to the account. So you can essentially own an ape for 15 minutes um for something like $2 basically the cost of a transaction which is something really cool.

>> And since what enforces that after 15 minutes it gets transferred back or >> um so the way we have it is basically anyone uh can transfer it from that encumbered wallet to their own encumbered wallet after 15 minutes. So you kind of need to have enough gas like we ensure that you have enough gas for someone else to also transfer it out. Uh but you could also do it so that it transfers back after 15 minutes. It's just this is more uh gas efficient. >> It feels me like the T's are more of a means to an end here. Like what you're really worried about is the fair exchange problem in some sense. You're saying in a world where people can do fair exchange, the definitions we have for what it means to know things are

wrong. Uh so like like am I correct that you don't really need pees in some sense here? >> Yeah. I mean basically even fair exchange is kind of like you know usually assumed to be done with some sort of trusted party. >> Sure. >> Um but essentially this is even more it's like sort of more complex forms of fair exchange right because uh it's sort of any arbitrary functionality of the key. >> I see like oblivious trans >> and the other thing is you if anyone physically owns the key then they can do everything with the key right. So this is sort of a fair exchange of like limited functionality of the key that nobody has access to essentially. So it's not really an exchange of that sort. Like it's not that I have uh access to some functionality that I'm giving to you. It's like even I don't

have access to that functionality because it's held inside of a TE. So there's a little bit of a difference there. >> So so basically so so all this has is kind of like a timer to ensure that you get it at least 15 minutes. Is that right? >> Yeah. Yeah. Basically. >> But then after that anyone can just >> anyone can take it >> take control as you said. Okay. So, it's like, yeah, I really encourage you to go take a look at this website. Um, yeah, and we actually bought like a 14 E ape for this, which was kind of fun. >> I I I think it's important in your model that Alice uh doesn't have the key herself. Yes. And only has the key inside the TE. How is that enforced?

>> So, basically, the key itself is generated inside of the TE and the TE will prove that the key was generated inside. Yeah. Wait, why is that important? I think that's the essence of what I'm confused about as well, >> right? So, the idea is like if I have the key outside of the key, then I can do everything with that key, right? Like I can sign arbitrary messages with that key. I can do arbitrary transactions with that key. >> True. I thought the concern was that that people that don't have the key can solicit services of someone that does have the the key to prove that they know the key for some specific application. >> So, it's the thing that uh when I'm actually so I'm not like renting it to you, right? I'm actually giving you ownership of it in that I don't have

control of it myself. So the idea where these encumbrance attacks comes from is it's not that I'm giving you access to the thing that I have access to currently as well. It's more that uh nobody has access to it except for you even I don't have access to it. So if I had access to for example voting in the uh voting example and I give you access as well, you're still not convinced that I'm just not going to sidestep you and vote on my own. But if the key is inside of the TE, I physically can't vote because I don't have access to that functionality at all. Only you do, right? So you're sort of guaranteed that uh the vote is only going to happen according to you. There's a lot of powerful attacks that we found both

within and beyond blockchains. Um so for example, you can break deniability in end-to-end encrypted deniable messaging platforms. Um I showed you like the bribery on bribery resistant voting. you can sort of sever the soul of soulbound tokens by making them not attached to a single account anymore. Uh you can transfer sort of these designated verifiable proofs which are supposed to be non-transferable. You can um have undetectable renting of account credentials and reputation like if you have uh Twitter account you could rent it out so that someone else can tweet on your behalf for example. You can rent reputation. So if there's like an application like Uniswap that's giving you a better trading price for frequent

high volume traders, you can rent that reputation to someone else in a trustless fashion. Um you can do things like wash trading in more complex ways like you can fake theft of your funds. You can do um sort of more hidden privacy pools like tornado cash for example uh that are more undetectable to onchain uh snoopers. But in general sort of what we show is that these seemingly unrelated attacks can be unified essentially by identifying a problem with the way we define knowledge and sort of just to take a step back and understand the root cause of these attacks. Um here's sort of the high level description. So in the normal scenario uh as I mentioned where the key is physically held by Alice you can

intuitively say that Alice's knowledge of the key. But in the encumbered scenario, intuitively you want to say that Alice doesn't have knowledge of the key. And so this like proof of knowledge primitive seems purpose-built to distinguish between these scenarios. In one case, you have knowledge, one case you don't. But the reality is that this proof of knowledge protocol can be successfully completed uh exactly the same way in both scenarios. And the sort of insufficiency comes from a very subtle uh understanding of the spruce of knowledge primitive. So just to uh give a brief background. So in a proof of knowledge primitive you have a prover who wants to convince something to the verifier. Essentially the prover wants to convince the verifier that she knows some witness w um for this public

statement x being in a language. So typically some np language. So the highle uh example that you can think about for this is let's say the knowledge of a secret key corresponding to a public key that's known to the verifier. And usually you have a completeness property that needs to hold which just says that an honest prover can convince the verifier. And a soundness property which is the thing that formalizes the knowledge part uh says something like if a prover convinces the honest verifier. Then there is this efficient extractor machine that can interact with the prover uh and recover the witness from the prover. And this extractor uh can be sort of white box or blackbox. can interact just with the prover in an oracle fashion or it can even have

access to the code but regardless there's this sort of extractor machine and this is how knowledge is defined and it turns out that this is actually where the problem lies that enable these incumbrance attacks. So the highle idea is that this extractor is sort of a theoretical proof construct and sometimes it can't be run in practice even given arbitrary time because of things that exist outside of the model. So for example in our trusted hardware use case if the TE holds the secret key then the hardware assumption itself prevents extraction uh outside of the TE or as I mentioned you can also do this incumbrance using multi-party computation where here each party individually holds a random uh looking

string but they can be combined together to reconstruct the key and essentially here the extractor requires access to all of these parties in order to be able to extract out the witness, but in practice, it's only given access to one of these parties. So even if it was given arbitrary amount of time, it still wouldn't be able to recover the key. And this is sort of this gap between theoretical modeling and reality which leads to these encumbrance attacks. I'll I'll talk about our work on proofs of complete knowledge. And sort of the core idea here is we want to instantiate this extractor as a physical entity instead of it just being a theoretical proof construct. So here's sort of the mental model so that you

have a prover trying to do a proof of complete knowledge to the verifier. And we have this sort of new resource assumptionbased formalism. So the reason for that is basically you can't get a proof of complete knowledge in the standard model because any uh any operation any anything that you can do inside of a TE you can do outside of a TE and same thing for MPC. So basically you wouldn't be able to distinguish it just based on that. So we have this sort of new resource assumption based formalism as follows. >> Just question I don't know if that makes any sense like um a TU usually has a specific functionality. It's usually a general purpose thing. So you can have an arbitrary program in the TE, >> but like it's a it's a specified program

before I build the TE in some sense, right? Like what if I define proof of complete knowledge to mean like the adversary chooses a functionality and then I need to run that that functionality on the key like the like like is sort of like not allow you to design the TE >> expecting what functionality I will expect you to do. So the T can take in an arbitrary general >> like a universal >> and then basically what it does is it it has this functionality of remote at a station where it can prove uh that it ran this program on this input and this was the output right but then you can load it with a different program for example.

So the idea for this resource assumption based formalism is that um an honest prover will only be allowed to use the set of approved resources say are honest the adversary can use unapproved resources as well but only those that are considered practical. So this is sort of where our hardware assumptions will be baked in. Um and now the idea is this extractor instead of being a theoretical proof construct will be the physical channel that connects the prover to the resource. And the idea here is that if the prover can convince the verifier of a proof of complete knowledge, uh then the witness will be exposed on this physical channel allowing the extractor to extract it.

So essentially the prover can convince the verifier only if it has unencumbered access to this witness. So if you look at the formalism and try to compare between the proof of knowledge and proof of complete knowledge um there's actually very little delta of adding this resource-based formalism. So if you look at the completeness property we can just say instead of just the honest prover uh convincing the honest verifier it does so using one of these approved honest resources. And now what the soundest property says is that if a prover convinces the honest verifier using a practical resource. So this is uh the resource set that it uh that sort of encodes our hardware assumption. Then

our extractor can recover witness from the channel between the prover and the resource where this extractor will uh will lie. the CK soundness definition doesn't capture the fact that there could exist some P star that convinces me using some other resource. >> So that's why I said um there's this set of all practical resources are PC which is larger than the set of honest resources. So it can use any arbitrary resource that it wants >> as long as it's practical and that's sort of where a hardware assumption is baked in of what resources are considered practical >> and how do you is there a formal definition of R prep? So it sort of depends protocol to protocol right. So even the set of honest resources is like okay for this protocol this is the

resource that the honest user will use and now the adversary is allowed to use any resource um as long as it follows some uh practicality thing like you know it doesn't compute too fast or something like I can u mention a little bit more about that when I talk about the protocols. Okay, so I'll just provide one example of a proof of complete knowledge protocol and very uh brief overview of this. So the intuition here is that you take a sigma protocol which is this common three round proof of knowledge design and you combine it with a bitcoin style proof of proofof work mining and the idea here is that this proofof work as will be used as the hardware resource and the hardware assumption here will be that the proofof

work as much much faster at computing hash functions than any sort of trusted computation uh that's CPU or GPU based. Essentially the set of practical resources are you can use anything as long as it's it doesn't compute hash functions very very fast and can be encrypted at the same time. So that's sort of the hardware assumption. So intuitively the protocol looks as follows. >> So don't you need a bit more that you can actually like tap that channel between. >> So basically the channel is the basically the wire that connects the prover to the resource uh which we assume to be uh visible to the prover itself. sort of in the local domain of the prover. Think about like the wire that I used to connect the ASIC

to my computer. >> But why is this equivalent to the ASIC resource? >> Uh can you repeat the question? >> Like why why why should I assume that because you have an ASIC I have access to this? Like I don't see the connection there. >> So essentially uh the channel is sort of the physical wire that connects my machine to the ASIC. So it's sort of being plugged on my local computer where I'm trying to do the proof. So the assumption is like you I can view it. >> Uhhuh. >> Right. But that's not the only kind of ASIC one could build or is it? Uh >> I mean you have to like connect it to some computer in some sense, right? And that's sort of the extraction.

>> What if the ASIC itself had the TE? >> Yeah. Then this would if the ASIC itself can be encrypted um >> in some sense, >> right? And it can basically do uh still as fast computation. >> Sure. Yeah. The TE does a fast computation basically. >> So then this would break the protocol. But that's sort of part of the practicality assumption that you can't or there currently at least doesn't exist. >> Okay. So that so our pract basically captures this. >> Exactly. >> Yeah. Cool. Um so basically the idea is you have a sigma protocol between the prover and the verifier that generates say some transcript t. >> Um and the idea is you want to embed this transcript t into a proofof work mining puzzle. So you want to try to find a nons that uh such that the hash value of this t comma mu uh is less than

some difficulty parameter. So I'm kind of hiding over a lot of details here. Uh but basically the idea is once you find that nons the proof just looks like the transcript and the nons that verifies the uh proof of work puzzle. Essentially the idea here is that we use the resource in such a way that um the witness will be leaked onto this extraction channel using the special soundness property of the sigma protocol. And essentially the security property that we get is that the prover can't convince the verifier unless it has sort of unencumbered access. Um so sort of like this witness is revealed on this channel between the prover and the resource. So let's look at the case where the prover is malicious. It's an

encumbered prover where the witness is held inside of the trusted hardware box. So in the first case uh if the encumbered prover still uses the asich hardware then the special soundness property of the signal protocol will still kick in and we'll be able to extract the witness out here in plain text. Otherwise, if it doesn't use the ASIC resource, it just tries to compute the hat functions locally inside of the TE itself, then because of the resource assumption we have, um you the prover won't be able to complete the proof of work in time. So, the verifier will reject. And kind of the high level takeaway here is that if the voting platform requires a proof of complete knowledge from the user, then they can be guaranteed that the user owns their

key. um and you know sort of can't sell access to her vote without also losing access to her wallet which is basically the thing we wanted. So kind of just to summarize this part I showed sort of these new encumbrance attacks that exploit subtle gaps in the way uh proofs of knowledge are defined and I defined this new proof of complete knowledge primitive which we show to be necessary to prevent these attacks. >> To what extent do you have intuition about how much harder it is to get this sort of complete knowledge property versus knowledge? Right. So like I could imagine even a blackbox positive result like whenever you can get proof of knowledge you do something with the proof system and under assumptions about R pract or whatever you also get complete knowledge or maybe there are like separations between the two. I have

no idea. >> Yeah that's a good question. I don't know too much uh about how that would pan out. Um so one thing we show is you can take any sigma protocol that's specially sound and do it uh construct a proof of complete knowledge this way. Um there's also a simpler proof of complete knowledge where we use um a trusted hardware as the resource itself with the assumption that you can't simulate a trusted hardware inside of another trusted hardware whatever that means. Um but we wanted to define it in this sort of broad resource-based formalism because it allows for other resources that we haven't been thought of to create new uh say complete knowledge protocols.

So if I wanted to deploy protocol, I would want to prove both soundness and complete knowledge separate like the two definitions separately is what you're saying. >> Uh >> you're saying they're incomparable. The standard definition of knowledge, soundness and complete knowledge or >> No, I mean in some sense the complete knowledge is >> is going to imply the knowledge >> is going to Yeah. Yeah. >> Okay. >> So it is a proof of knowledge in some form. Yes. Cool. Okay. So the second thing I'll talk about is sort of these new attacks on accountable cryptography that make use of smart contracts essentially for coordination purposes. So there's a lot of these sort of multi-party cryptographic protocols or multi-party protocols in general that make some sort of honesty assumptions on quorums of participants. So for example, you can have a protocol uh that works

when there's say two out of five nodes that are corrupt but doesn't work when three out of the five nodes become corrupt. And kind of a high level question or a natural question to ask is can we detect protocol failure of this form. So we have these sort of typical accountability goals within cryptography. And the idea is like we want to identify when things go wrong. So for example failure of an assumption or failure of a protocol property. And then if possible we also want to identify uh one or more of the culprits. And for this talk I'll focus on scenarios where the sort of failure is not publicly visible. So don't think about things like double signing which is publicly visible on chain but rather thinks about examples where you want

some party to prove failure to a judge. We'll sort of think about this as like a whistleblowing protocol. I'll give examples um in the future slides as well. But the idea here is we want some one of the colluding parties to prove collusion to a publicly verifiable judge. So essentially at a broad scope you can think about this like whistleblowing framework as let's say you have some endparty protocol that emulates a functionality. So basically you have security as long as say t minus one parties collude and if you have more than t parties or uh t parties collude then uh security breaks and sort of the idea of whistleblowing is that if you have some t-sized collusion here so that the protocol will ideally break then a

whistleblowing uh scheme will allow uh one of the parties inside of this collusion to obtain this sort of publicly verifiable proof of collusion that they can show to a whistleblowing mechanism or a judge um and can sort of uh get a reward that way. So the judge can execute rewards or penalties and we'll sort of focus on situations where the judge doesn't require any private state or tracing key for example to execute these rewards. So it can itself be deployed as a smart contract. You sort of for this whistleblowing you want to kind of integrate two things together. One is this cryptography question is when is it possible for cryptographic protocols to produce this sort of whistleblowing proof of

collusion? What protocols can support such a proof? And there's this natural mechanism design or game theory question which asks are colluding players even incentivized to submit such a proofs. So if there's a collusion and I obtain a proof, is it better for me to actually submit this proof or just stay silent in the first place? How do we think about rewards and penalties for that? And for this we'll also model I'll call a new smart contractbased collusion technique. Uh I'll call this smart collusion. So I'll sort of focus mainly on the mechanism design side of things in this talk. Um but I'll quickly talk about sort of natural whistleblink properties in general as well.

So the properties that you want from whistleblowing protocol kind of obviously you have we want some uh notion of completeness which just means that if uh these two parties collude then one of them obtains this whistleblowing proof. Uh there's a soundness property that says if there's no collusion of large enough size then no one will be able to obtain a proof that convinces the judge. We can have sort of this unframability property which is specifically useful for proofs that can identify colluders. So this is sort of a strong property that says even if everyone except for one honest person colludes uh they still cannot blame this honest person. So this is sort of this like unframability property.

>> So if what does it mean collude here like suppose I just share my we have some any arbitrary honest protocol and t players share their internal states which is not an instruction in the protocol. Thus they have colluded >> but they follow the next message protocol. >> So in that sense >> so that they deviate from the colluding proto uh from the honest protocol you can say they've colluded. Let's >> but that's what I'm saying. Me sending to you my private state over a private channel >> that's violating the honest protocol.

Yes. >> However that's undetectable. It's it it'll be indistinguishable from another observer. >> Um yeah. So I mean we can assume sort of for these sort of um cryptographic properties we can assume an adversary like a powerful adversary just controls all of these n minus one includers. So it's just one entity right for the game theory part we'll separate out this adversary instead of considering one giant adversary they'll actually be individually rationally players. But for all the for all the cryptographic components we can think about it as just one adversary controlling all of the malicious players. I mean maybe there is a way to think about it like consider an execution where the output of the protocol is different than everyone was honest and then you want to go back and find out sort of why or >> um

>> I mean like I think a point is kind of like that's a collusion which is like doesn't have a effect on the protocol execution and so you can start from a >> start from the assumption that the collusion changes the protocol. Uh so in some sense you don't need to right because even if you send that sort of private state and it doesn't change the output then you can't frame anyone else right >> the last property yeah fair yeah >> so the problem is if you're doing a multiple you know like multiple instances of same sort of let's say threshold signature we can collude in one iteration >> but not deviate from the protocol >> but thus learn for example a secret key or learn some secret information and then in the next instance

use that to pick our inputs. For example, again, following the honest protocol, but like if it was a coin flipping protocol, for example, with some sort of like setup state or something like that, >> you could learn something in a way that's indistinguishable in the first iteration and use that knowledge in the second iteration to, for example, bias the coin flip. >> Um, that's an example of collusion where you still follow all of the protocol instructions, >> but can you frame sort of an honest party? I I don't fully understand like how you can use that to uh attack like a whistleblower.

>> You break the correctness of the whatever protocol. I mean >> but then that's just sort of the security of the protocol itself. So for for here for this purpose just think about a single execution protocol rather than executing like multiple instances of the same protocol as well. Right. >> He's talking about completeness, right? He's saying like why wouldn't like completeness be violated in that example? Um so then that wouldn't be like a whistleblowing protocol. If you can't get a proof uh then that wouldn't be a valid whistleblowing protocol. >> Do you have an example of a natural so do you have a result that says given any protocol that's like whatever normally sound uh like complete and sound and so forth you can compile it into a whistleblowing protocol or is there just like a subset of protocols that support

this type of thing? >> Yeah, there's just a subset. We don't have like a generic result let's say. We kind of looked at some natural applications that kind of by design support whistleblowing. Um, and there's also some recent work that tries to build sort of these style of whistleblowing protocols for specific uh applications. And then we also focus mainly on the mechanism design of how do we even incentivize these proofs. Um, so basically on the mechanism design side, you want some sort of incentive compatibility that like playing the honest strategy is some sort of subgame perfect Nash equilibrium. Yes. >> Yeah. I I I also feel the completeness property as written seems a little too strong, right? So then for for any protocol if uh tea parties just send a message um good evening,

>> right? That how can that um how can you generate a proof that they deviated? >> So in some sense it's like if tea parties collude to break the property is is that what it should uh actually be right. Um so it's not just like tea parties just talk to each other and they automatically get occlusion proof. Um it's that if they use it to break the property right so this is sort of like a broad framework that can actually capture a lot of natural applications. Um so we have some new applications specifically where like a server is or a set of servers are providing a client uh with some computational service and you want to prevent them from colluding with the client. So you can think about for

example distributed randomness beacons uh that is provided as a service from a set of servers and you want to ensure that randomness is not leaked earlier to the client. So they don't generate the randomness and give it to the client in advance um or sort of like these rate limited credentials or tokens uh where you want to ensure that the set of servers are not giving extra credentials to the client. So in each of these cases sort of the client who receives this extra service through collusion will naturally obtain a whistleblowing proof. For example in the randomness case they can show that they have access to this randomness before it was supposed to be uh generated. But it also captures a lot of recent works on accountability uh for

classical primitives that have been done in the past few years. So for example is there's this new primitive of secret sharing with snitching um which generalizes or extends secret sharing rather so that if the colluders uh collude to reconstruct the secret earlier than expected then one of the colluders gets a proof that uh there was a collusion for example >> proof just the secret >> uh yes essentially so the idea here is that uh in a normal secret sharing protocol you can collude with MPC uh so nobody they can collude and uh use the secret without actually reconstructing it but in the secret sharing with snitching protocol the idea

is you have to reconstruct the full secret to one entity in order to be able to use it externally as well. So there's also this uh new primitive of accountable threshold decryption which can prove that colluders uh decrypted some encrypted message cipher text early and this can apply to sort of privacy based me minimization approaches for example. It also works for sort of BFT some class of BFT forensics protocol uh where an adversary can get a proof that more than say an over three servers colluded and this kind of broad framework allows our game theoretic results to apply to a broad range of these accountable cryptography protocols. So let me just get to the game theory model. Um so let's say you

know you have this cryptography protocol that's designed so that you end up with a proof of collusion whenever tea parties collude. So the question now from a game theoretic standpoint is should you submit this proof or just keep it to yourself. So here's sort of the road map I'll talk about the game theory in um so you can think about this base game B is the incentives without any whistleblowing protocol. So just a natural primitive and then you can think about this sort of whistleblowing game for setting up the rewards of the whistleblowing in a way that incentivizes whistleblowing. But then I'll show this sort of third stage which is this retaliation game which will model or sort of final smart collusionbased technique uh which will essentially try to penalize defectors

who try to whistleblow. So this will be uh done by colluders to strengthen their collusion and disincentivize whistleblowing. Okay. So if you think about the base game B um each player can either play honest or collude. For simplicity, I'll talk about only n out of n collusion where everyone needs to be colluding um for the collusion to go through. So here the utility function for each individual player you can think of as follows. So if everyone plays collude, each player gets utility v otherwise everyone gets zero. It's kind of easy to see that in just this pure game collusion is a pure Nash equilibrium. So now you know a

cryptographer comes in and designs a way for players to provide this sort of proof of collusion. Um and we can sort of think about like the proof being publicly verifiable. So it can be verified by a smart contract and you can also allow it to be anonymous. So the smart contract doesn't know who submitted the proof. Essentially we can sort of think about it as a smart contract as I said and we have the game theory question of how do we design this reward mechanism. So sort of uh here's a basic design for again as the game without the smart contract based retaliation. So you can think about each player deposits some value D into the whistleblowing mechanism. Uh and now after that happens each player can decide whether to play honest or play collude. If there's a collusion then

each coller further has u the opportunity to play sort of whistleblow or stay silent. And then this mechanism can decide on the whistleblowing reward uh and sort of penalize or slash the other players accordingly. And because the whistleblowing is anonymous um we have to account for the fact that multiple players can submit whistles. Even a single player can submit sort of multiple whistles. So really here RNs are functions of the number of whistles that are blown. And you can think about the deposit that's required is essentially the maximum of whatever slashing penalty you want to enforce. So there's sort of natural properties that you would want from these functions. So the first thing is

let's say uh we want no reward or penalty to be given when there's no whistle being blown. So this is sort of the honest case, right? We also want something like no money is created. Um so any reward that you give must be smaller than uh all the slashes that you're doing. if you're not sort of creating money. [snorts] And another thing is like an individual whistleblower in order to incentivize them to whistleblow should be better off whistleblowing than not whistleblowing, right? So, uh the reward from one whistle should be larger than the slash.

And here's sort of an an effective mechanism that works in a game without retaliation. So, the high level idea is uh let's say you know the collusion utility that you get from collusion which is V. So you just take a slightly larger deposit than that. If there's zero whistles that are blown, you take no action. If there's one whistle that's blown, you essentially give the whistleblower a reward v plus n minus one * epsilon and then you just slash everyone else. U and if there's more whistles, you actually just give zero reward and slash everyone at the same time. So why does this work? The idea is you sort of create a prisoner's dilemmaesque situation for whistleblowing. So it's always better for individual colluders to blow the

whistle. But if all colluders whistle blow, then the colluders are worse off. So in all cases, it's sort of like a dominant strategy to just play uh the whistleblowing if you decide to collude. And what that means is you should not collude in the first place. But now I'll talk about this new strategy that colluders can use which I'll call smart collusion which is basically using smart contracts to strengthen the collusion by penalizing any defectors or whistleblowers. And the idea here is that smart contracts can be essentially used as commitment devices. So you can have the colluders create a contract C that holds a large retaliation deposit from each coller for example larger than the deposit that they have to pay into the original whistleblowing mechanism.

And the idea is that if anyone tries to whistleblow, all of this retaliation deposit will get burnt. And this sort of incentivizes colluders to stay faithful to the collusion and not whistleblow. And the the idea here is that the colluders can actually decide on this collusion mechanism after the whistleblowing mechanism is announced. So they have this sort of last mover advantage. Um and the idea is you can use this to circumvent a lot of prior results in accountable cryptography. If you go back two slides, does your mechanism burn money? For example, uh you lose D if uh there's zero whistles.

>> No, you get that money back. >> The fir Okay, so the first bullet is if there's zero whistles, you get Dback. Everybody gets Dback. >> Yeah. Yeah. >> So we have an impossibility result for this retaliation game, which is fairly straightforward to see, is that a smart coller with enough money can always win. And the idea is, you know, you just create a smart contract collusion with a very very large deposit. So essentially unconditional security is feasible without smart collusion but it's not feasible with smart collusion and the impossibility actually holds even when whistleblowing is anonymous and can actually identify all of the colluders involved. But we do have a sort of bounded positive result as well. And the idea being that you can have a small whistleblowing deposit held by the

mechanism and can protect against a much larger uh deposit which is sort of n times larger in this sort of smart collusion. And sort of the intuitive uh sketch here is that you'll collect d from each player and give uh the whistleblowing reward n* d minus epsilon. So essentially the whistleblower will uh lose their initial deposit d and get n * d minus epsilon. So they'll get n minus one * d minus epsilon. And um each coller will sort of need to put in a deposit that's larger than the whistleblowing reward uh because anyone could do the whistleblowing at this point. So in order to prevent them from whistleblowing, the smart collusion needs to hold a deposit that's larger

than the whistleblowing reward. So essentially you can take a deposit d from each player and to uh to attack this whistleblowing mechanism each coller needs to put in a deposit of n minus one * d into the smart collusion and we give a sort of roughly matching lower bound for this as well. I'll just briefly mention that you can extend these to a t out of n collusion as well roughly by replacing just uh all instances of n with t. There's a little bit of a subtlety here is like we only model one concrete sort of T-siz collision that just comes up out of the air and we analyze it. Uh the game can get really complicated if there sort of multiple collusions that can happen.

Players can sort of move between collusions or um leave one collusion and try to penalize the other ones for example. Uh so just to summarize this part, we talked about a new smart contract based collusion technique that can circumvent a lot of uh previous accountable cryptography protocols and the TLDDR here is you should think about incentives when building uh cryptography. Sort of just to recap in the last few slides, the question is like where do we go from here, right? So I talked about you know a first principles approach to designing these secure protocols and I want to talk a little bit more from a philosophical standpoint here as well and the kind of highle pitch I want to make is that we need broader approaches

to defining security not just for blockchains but maybe for modern system security as well and modern systems are becoming more and more complex than they were sort of the 80s and 90s when a lot of these primitives were defined there's a lot of new applications that are coming up and we should really think more critically really about what just what security even means and not just sort of build protocols um in the same sort of drop in attacker models from several decades ago. There's also new attacker capabilities now that didn't exist uh in the wild at least several decades ago. So I talked about how trusted hardware NPC uh smart contracts can be used for nefarious purposes by

attackers. So they're not just tools that security researchers should use, but they're also tools that attackers can use and should be analyzed as such. Um, another kind of futuristic thing that I see happening is um what happens when we get to a point where AI bots are indistinguishable from humans. Now, can you generate like an army of AI bots to extract more value from a system uh than you should have been given in the first place? Maybe some notions of permissionlessness that we've worked on on blockchain systems can come in handy when thinking about uh systems of these form in a world where AI bots are indistinguishable from humans. So we really do need uh new age cryptography.

The idea is we need so much more right we need a multi-pronged approach that combines tools from many different areas. So what we really want is to think about security as a central goal and how can we use ideas from cryptography, distributed systems, mechanism design and game theory, macroeconomics, uh maybe policy and law, social sciences, maybe many other things to kind of look at security as a central goal that we want to solve. And we're not really close to uh having like a overarching model of security, but we really should start thinking about more intersections of areas when thinking about security. And that's kind of the pitch of this talk. The second thing I want to talk about is sort of this inherent fickleness of our models uh that we look at everyday basis. Right?

So real world systems are very very messy and because these security models some model something about the real world, they're sort of inherently incomplete, right? So the models that we have today may not be relevant or appropriate to uh appropriate to reason about some decades into the future. And uh in general cryptography makes a lot of assumptions when improving security. Some of these are sort of mathematical in nature like say prime factorization or discrete log. Uh but there's a lot of these sort of soft assumptions that cryptography makes as well which are more likely to fail in practice. So things like non-olusion or trusted setup or just like what's in the scope of the model versus what's outside or thinking

about incentives, right? And we really should think more carefully about these soft assumptions when we're designing our security protocols. Really the idea is like all security models just like all statistical models are wrong but we want to think about what models are useful for existing applications today and how do we think about security from this multi-disiplinary lens. Uh I'll kind of end there. Uh happy to take questions and also chat offline. >> I would like to register my objection to using tic-tac-toe as the official icon for game theory and [laughter] mechanism design.

>> Did I Okay, cool. Any suggestions for what? Um, >> yeah, [laughter] I'll I'll give you some offline. >> Okay, perfect. >> Definitely can improve on >> looking for slides. Yes, perfect. >> When you model these uh the games with cryptographic proofs, >> uh generally the problem you have there is dealing with the soundness or uh soundness errors of those things if you ever want to prove. So, so h how do you abstract that? In other words, you can never say something's like a pure subgame Nash equilibrium.

>> Absolutely. Yeah. So, we basically for this purposes, we just assume like you know it's perfectly sound, perfectly complete kind of thing. Um there's some really recent work uh from Basillus and others that I really like of how to convert um Nash equilibrium to sort of this like pseudo Nash equilibrium where now you can analyze real cryptographic protocols. So you can identify uh analyze the um mechanism design side of things with a completely ideal crypto functionality and then when you substitute it for a real protocol, it still sort of goes through in this like pseudo Nash uh incentives context. Um yeah, I'm happy to send you the paper if you're interested. It's not my work, but

it's a work that I really like. All right. Thanks again.