Building lots of onchain stuff that is interesting

Hi everyone! Hey! Okay, cool. So, for this talk, I've given a couple of talks at DevCon. If you listened to my one on Monday, you heard some of the crazy, weird ideas in my notebook.

If you listened to the one yesterday, you heard about end-to-end internet games and a couple of new technologies that I think could enable a bunch of insane new consumer crypto apps. But today, I figured for Mud Day, and because this is a classroom, we do something a little bit different, and I take it in a different direction. I figured that today, what would be most interesting and useful to probably this group of people would be if I just went through a couple of kind of hard slash interesting technical challenges I faced building random stuff over the past year. And better? People can hear me well?

Yeah. I figured I'd go through a couple of technical challenges I faced building stuff over the past year and talk through some problems and what they were and what I did to fix them. And so with that, the talk is called... Three Things from Building stuff by Small Brain. And so what we're going to do, because this is a classroom, is we're going to play a game.

And the game is called Who's Smarter Than Small Brain? And how it's going to work is I'm going to propose to you one problem that I ran into. And just like for some poetry, it's really fun that these problems exist because the things I build are really simple, right? It's not like you're trying to cure cancer and you have a hard math problem. It's like you're trying to get people to yell at each other over the internet and you have a hard math problem.

And some of them are going to be math problems, some of them are going to be solidity questions. And we have very smart people in this room, like Dr. J and Mr. Indexer and Paco and David and Frolic and, you know, our German friend in the back. And so maybe this is going to be really lame and you guys are going to get the answers really quickly.

But hope it's going to happen is you're going to struggle a little bit, then get the answer and then it'll be interesting. But please participate. Okay. Question number one. We're going to start easy and on Ethereum in a smart contract.

And then I want to have a password that I give to somebody. And I want anybody with this password to be able to unlock the funds. It's like a really, really simple escrow smart contract. I put some money in a smart contract, I have a password, and then I give this password to somebody and they can unlock the funds. How do you do it?

And while I give you a little bit of time to think, this was useful. Okay, amazing. Well, this was useful for an app I built called Yonk, which was an app where you can send people voice memos with a little bit of payment attached. And if they don't listen to your voice memo in time, face ID, no headphones, they won't get the money. The longer they wait, the less they get.

And it was used in this app to do invite links. So if we have this primitive, we can actually send people who don't have wallets yet an invite link with a yonk in it. But anyways, getting back to the question, yeah, does any one of you want to jump in? You want to use your mic? Yeah, what do you think?

Yeah, so mine is kind of a brute force. But what you do is you hash the secret. Yeah. You put it on chain. Yeah.

And in order to prove that you know the secret, you make a simple ZKP that you know the pre-image of the hash. But it's kind of brute force. the room. And Justin, can you explain why it needs to be a ZKP? Yeah.

So, okay. So do you guys know what a hash is? Like you take some, some value, you can turn into a hash, but you can't go from the hash and turn it back into the value. So if you put the hash of the password on the blockchain, you commit to the password, but people cannot recover the password from the hash. And now your problem is, can someone show that they know the thing behind the hash without revealing to everybody else?

So if you were to just put the password in a transaction and be like, look, look, blockchain, if you hash my password, you'll get the hash. The issue is people can front run you and see it in the mempool and front run you. So what you do instead is you make a zero knowledge proof that you know the preimage of the hash. Yes, that's exactly right. And I think what's interesting here is this is the solution I also initially came up with.

And then I was sitting in my room like four days before ETH Denver, like, you know, trying to write CIRCOM and being very sad. And like, I felt in my heart that there had to be a better solution. And there actually was. Ryan, do you have a different, was your solution different? Here, I'll run over to you with the mic.

You make a new hash from the address of the sender with the password. Okay. Oh, no, no, no. Never mind. That's not going to work.

Okay, cool. Never mind. Well, I think there's something interesting there. All right. Are we ready for the answer to be revealed, or does anybody have it?

Okay, cool. This is how it works. I'm so excited about this one because this is like one of the most elegant pieces of like real world like simple cryptography I've seen. All right. So the first thing you do is you generate a new key pair.

And we are going to call it so like a private key and a public key. Pretty much a new wallet. And we're going to call this key an ephemeral wallet. Okay? pretty much a new wallet.

And we're going to call this key pair an ephemeral wallet, okay? Because like we're just going to use it to make this happen and we're going to throw it away pretty quickly afterward, all right? So the big insight, and some of you might be seeing the whole punchline by now, is that the private key from this key pair is going to be the password that we give to people. And so what you do is you scroll in the smart contract, the money you want to put in, and the public key associated with that ephemeral wallet. Then what you do is you take the private key, which is the password, and you give the password to somebody else.

You give the private key to somebody else. When they want to unlock the payment, what they do is they take their own address, their own actual address, and sign it with the private and public key pair from the ephemeral wallet. And then they can use that signature to claim the funds on-chain. Because the smart contract on-chain just does a signature check to see that, okay, cool, the person with the password said that this wallet should have the money, so that we should give them the money. And this prevents like front run and all of the problems that the ZKP was solving, because you are signing exactly which address should get the money.

Yeah, so the signature is a ZKP. Like a signature is a zero-lunch proof. It's not a ZK snark. Yeah. So we went too far on the heaviness of the solution.

That's actually a better way to think about it. It's exactly the same solution, but a much smaller proof that shows exactly what you need to versus writing something in Sercom. This solution is not credited to me, actually. It was deep in the Dymo code because Dymo uses exactly the same thing for invite links. So big shout-out to DC and Nolan for doing an extremely elegant piece of cryptography to do invite links on chain.

So this is a little trick for fully on chain invite links. Okay, cool. Little breath. Let's move on to question number two, which I'm looking at it is a little bit of a mouthful. But let me take you through the question and then you can, like can throw out what you think will be a good answer to me.

Okay, this is the problem, and you need to do this again on a blockchain. There's a round, all right? And during the round, people are posting vectors to the chain. Vectors is like a long sequence of numbers. So a bunch of players are posting vectors to a blockchain during a round.

And then, at some time, it's the end of the round. At the end of the round, an oracle comes and puts another vector on chain. This is the truth vector. And let's say the players are like, me, Justin, Elena, Frolic, Ryan, etc. What we want at the end is we want the sum of the distance between the Oracle and Justin vectors and the Oracle and Elena's vectors and the Oracle and Frolic's vectors, etc.

We want the sum of the distances between the truth vector and the player's vectors. Does that make sense? Cool. Okay. Any ideas on how you can efficiently calculate this?

All right. I need to give you a second to think while I give you context. That's the pattern, so don't jump in just yet. Oh, and the formula we're using for distance between vectors, actually we can use anything reasonable. We can literally just use Euclidean distance.

But another valid formula, which is a nice little hint for this question, is cosine distance, which is the dot product of the two vectors over the magnitude of the two vectors. All right, sweet. Anyways, the context for this is this app called tomorrow.news, which is a prediction market for tomorrow's New York Times headline, that's TMR. That pays people out based on how close in meaning they are to the truth.

And we use sentence embeddings to do this. Sentence embeddings are a way to turn a sentence into a vector. And when two sentences are close to each other in meaning, the vectors are close to each other in distance. So we can actually use this to build a prediction market that's semantic. Anyways, back to the problem.

How do you do this nicely on chain? What were you going to say? Oh, I mean, I don't have a full answer, but one thing I'm wondering if it's useful is to consider the truth vector to be zero. Okay. And then we shift everything by the truth vector.

I mean, okay, so as a first kind of like start, just assume truth vector is zero and then we're going to have to reshift everything. That should make a bunch of the distance stuff much simpler, at least conceptually. So this is what I thought too, but it actually doesn't, because the truth vector could end up anywhere. And distance from 0 is the vector itself. So it kind of keeps everything exactly the same in your example.

Any other thoughts? All right, should I ruin it? Give us a hint. The hint is you have to stare. So do we understand the core problem with this?

I guess a question somebody should ask is why don't we just sum the distances at the end? Yeah, are you assuming you don't want to have an O of N? Exactly. Because we're on a block. I kind of expected somebody to say it and then I would be like, no.

But why we can't just sum the distances at the end is because there might be N players and then we need to do, like, you know, on the order of N computations, it might brick the game unless there's batching. So you want a constant time solution? We want a constant time solution to this problem. Alright, I'll give it to you. Can it be an incremental solution?

What does that mean? Well, every time someone adds a vector, they do an incremental amount of computation. Yeah, it can. Okay. So it would still be O of N, it's just you don't pay it in one go at the end.

Exactly, great. But you don't have the truth vector until the very end. Is another hint that it's done pairwise? What do you mean by that? Well, you always do it with respect to the previous vector?

I will give you a hint that you just increment one big value as you go on. Yes, yes. Oh, amazing. Thank you. Oh, thanks.

I wonder if this expression can be factorized. Yeah, how would you factor it? I see there is a dot product. I'm not sure about if the dot product can be factorized. Yeah, how would you factor it?

I see there's the dot product. I'm not sure about if the dot product can be factorized, but I think that you can keep the ones on the side, sum the factor, and then do the operation on the sum. That's it. That's exactly it. Oh, my God.

I'm so happy. The computer is gone. Yeah, yeah, it's coming back. Okay, cool. That's exactly it.

What's your name? Bobosh? Great job. That's literally what you do. So here are all your, you know, these things you need to sum.

These are everybody's guesses. Like, this is somebody's guess. This is somebody's guess. This is somebody's guess. you're like B over magnitude of B is the truth vector over the magnitude of the truth vector.

And that's like a common factor in all of these terms. So you can just like pull that baby out. And also all the ones you can just like, you know, pull out to the side of the sum. And then this thing starts looking like, sorry, I didn't math script, but it starts looking like, you know, N, which is all the ones that you pulled out, minus the common factor times the sum of other stuff. And so all you do is you keep track of the sum of other stuff as people are making their votes, and you do a nice little multiplication at the end, and you're all very happy.

The problem with this really is that what we ended up needing to do is we ended up needing to square everything or actually raise anything to a power we wanted to decide because the distances weren't crazy enough and so the market was kind of boring. And fundamentally now, this kind of sucks because you can expand this out, actually can use Euclidean distance here and then because there's a squared and a square root, it ends up being kind of nice, but you still can't do it. Because high level, what you did is you, like, added non-linearities to a thing which we were, like, it was really nice that it happened to be linear. And so to do this, there's two things that we aligned on. One was you could do a ZKP using something like SP1, right, to, like, succinctly verify the sum on-chain later and compute it off-chain.

But it turns out that the cost of doing that on their prover network is actually more than the cost of literally just looping on-chain and doing the sum because the vectors were of such high dimension. And so we actually did end up doing the stupidest thing, which was looping on-chain. Great. All right. Okay.

Third question. Third question is a really open-ended question, and there's not, like, a correct answer to this one. But what it is is, I guess first is, like, are people here familiar with words three? All right. Like, maybe, like like a fourth of you.

So I'll go over just the part of the game you need to know to motivate this question. Words 3 is a game where you're playing Scrabble on chain on like an infinite grid, and you have to buy in letters to play. And the price of buying letters changes with some formula. That formula used to be a VRGDA. That's how the game, one edition of the game looked.

It's a bunch of people playing letters and then letters are in different price curves. The letters, the pricing curve of letters used to be a VRGDA with target rates per letter set based on the rarity of the letter. What that means, what a VRGDA tries to do, like