Threshold Signing

Transcript

[applause] for this workshop. We're going to do a workshop on the past two talks. So hopefully everyone has plenty of questions ready to go. I think because it's a small group, what we should do is let's try and get a bit closer together. Um and that way we can make it a little bit more interactive. Um do you want to do it some whiteboards here? >> Yeah. Great. Okay. So as I said, we've just had two excellent talks. All of those speakers are still in this room. So, and we've got I know plenty of people with opinions. MueL, I'm sure you've worked and thought a lot about this. We've got Ledger. We've got Emil.

I know you have some thoughts on this as well. Um, we also have some seated questions up on the on the uh slideshow. They're just there if we need them. We don't need to go through any of them or all of them at all. Um, but yeah, so let's get very interactive. It's a small group. We can get the pen pen and paper out um and just shout with your questions. Before we kick off on those, does anyone have any talking points or any questions they want to kick off with? >> Yeah. Yeah. >> Assume we have a way better a basic dumb dumb.

>> Yeah, >> that's working. have way better ashbased scheme that are friendly. >> I mean what we like Ethereum be open to such schemes or you say no only shu 56 or blake are the as function we are fired to consider for asb signatures. I think we can have MPC friendly hashbased signatures with Blake or SHA but if you maybe >> maybe it depends in what price but some way I give you like 10 times 100 times better schemes which are different why I mean why to be that conservative I think I think you can make it practical with black >> maybe I yes I think yeah >> okay but if not why to be that

conservative >> because you think you can Yes. Yes. Yes. >> For no price >> as yes there is a price but um >> even like you know for ECDSA we paying price to do it threshold signatures right I'm speaking of threshold signatures even for ECDSA but a lot of effort has been made in the last 10 years or so we still pay for doing this signatures so I guess for ashb going to pay way more what my question is why to insist of using blake which is what I asked before as the oneway may function for us by signatures which we don't need. If are you open to others alternative? We said no we're very conservative here only Blake maybe >> later today we're going to have a whole

workshop on you know the choice of hash function and if you have a an extra suggestion to add to the mix then >> MPC friendly MPC friendly oneway functions yeah >> there are exam they are candidates >> okay then I would encourage you to join the workshop later today yeah um I mean we care about all sorts of things you know we care about snark friendliness for aggregation. We care about lindiness like how old, you know, has these how old is this oneway function? How battle tested it is. Um, so there there's all sorts of considerations above and beyond MPC friendliness.

not no postponten. So we've been really experimental on hash function for years with Poseidon. just kind of move it away from it. So maybe now we're going to be a bit more >> Yeah. So we've been really experimental with you know >> great Emil I know you want to you have

some interesting work you wanted to share as well. >> Um so I can try to explain my reasoning but uh to be clear I'm not an MPC expert so please interrupt me if at the moment I said something wrong. So my understanding is that in MPC um you need honest majority to make it kind of efficient and um my understanding is that you can have malicious security honest majority MPC is kind of efficient. It's like one you pay one bit approximately one bit of bandwidth per gate in your circuit. So this is the assumption I took and with this assumption

um sometimes you like in threshold you want I don't know four out of um five threshold and if you want four out of five four out of five it means that you are not in the honest majority case so you cannot have efficient MPC for this um four out of five or three out of Um but you have prons like PRs. So the paper by Dan Bon and all um requires a trusted dealer. So there is a ceremony with a trusted dealer. Then you um the residular generates all the the secret hashes and encrypts like gor encrypt every hash with a context aware

threshold PRF distributes the data in the public and every um ser can if you have the t out of n you can um have you can reconstruct the pr and decrypt the the preage and it works nice and using this threshold PRF you can have any t out of n, it works nicely. Like you can have 15 out of 16, it works nicely. And so um uh my idea was can we um take but the main drawback of pron is first that it has been described for essentially stateful schemes like xmss it had not been applied to any um stateless schemes and um second drawback obviously it's

not distributed key generation it's with a trusted dealer and so my idea was can we but it's not a new idea like it's it's a something That is an idea in the bronze paper but um I tried it with to play with numbers and the idea is to replace the trusted dealer in the ceremony by MPC and so doing so um let's say you like what you would get is a scheme where typically you can say out of n um threshold like four out of five three out of four whatever but at key generation at the ceremony you still requires honest majority. So the the

security assumption is um like let's say you requires that it's three out of five at kijen but then after ken you can require four out of five and um so in some sense is not as good as you can what we can do with bs I don't know but it's maybe a good compromise and I run some number some numbers and maybe uh does it work Okay. Um, thank you very much.

>> I guess this is alpha then. >> Okay. Um and so what I took is essentially um the this NIST standard candidate um SHSA 12824 which is like something that the NIST um has been advocating it's essentially um it's so in the original NIST proposition it's a sphinx with only one layer of XMSS and then you have your watts and then you have your force So in some sense is the very simple um things I just um replaced the values like it's a bigger tree it's um there are more for like the forest

trees are much smaller but there are more of them and it works essentially thanks to hypert printing because what I wanted is to get um a big lifetime to let users with I don't know um Coinbase and Binance since a lot of time but essentially um thanks to hyper pruning pruning you don't pay for this big lifetime because you can always prune on the range of words that interest you for the desired lifetime and I run some numbers and if you assume essentially one bit per and and you let's say you want this is the lifetime so if you want to

only sign I don't know 8,000 times like 7 7.5 the bandwidth um the bandwidth requirement is um on the order of dozens of gigabytes so it's kind of practical if you have I don't know like a good internet connection you can make it in a few hours um so honestly I hope I didn't miss anything that makes I don't know like because I'm not M6 so maybe I miss something but um unless Unless I miss something just my point is that um with the good sphinx parameter set it's possible and the key idea is that the force needs to be cheap because in this scheme you will need at the ceremony to

compute all like every force needs to be computed at the ceremony at the key generation. So you want to make your force extremely cheap. So you want to use a lot of forest trees but uh small heights for trees and that's it uses 24 for trees of height 10 and for the lifetime there proves in lin that the lifetime are correct um anyway and you can have something close to like I mean I think it's practical for some use case anyway um and you still need to store. So this is the bandwidth the main bottleneck with DKJ I think is the

bandwidth at the um ceremony key gen and you still have to store the public um encrypted hashes uh in the but it can be stored in the but there must still some be someone that stores the that is the same as in pron and so but it's the order of of a gigabyte so it's honestly it's fine. Yeah. So yeah. So the only problem with this uh thing is when you put uh two to the 30 signing budget for the whole tree you >> yeah you say okay I can hyper prune it and then it's fine but the problem is

now your main scheme is not really usable because generating an XMss 2 to the 33 no it's doable but I'm not sure if it is really The key idea of the scheme is that uh pruning is very cool. >> Yeah. But if you design the scheme that the basic construction >> Yeah. >> is not feasible. But with pruning >> it's feasible like if you have a good CPU it's feasible. >> No. Yeah. Okay. It is feasible but it's it's costy. It's cost but I mean the thing is it's not expensive like let's say here I have this

I could have added even four or five um um uh three hats in the XMSS it doesn't this hat like if you use h equals 30 you only pay four or five additional hashes at verification and at signing and at kitchen which is extremely cheap because you can always prune the part that interests you. I can also think if we considering a single tree instead of doing a fixed tree plus pruning we can do a flexible tree and then I don't even have to prune then I don't have to search I can decide on

my own site what type of tree I want to use and then still flexible stateful thingy but uh the core part of it why flexibility was only applied to the stateful part because I want a single tree because when uh when I have multi trees the things become a little bit fishy there maybe it is still usable but it's not that I'm not that confident about multi- tree flexible trees but if I consider just a single tree then this can also be a trade-off >> agre um yeah with one big tree I agree that probably It's a a bit of a concern for

kijun. But if you do like even two layers, then kunen if you just want to to do the 30 fork sleeves. You even if you do two two layers is fine. And okay, the signal is a bit larger but and then you can still use pruning to if you need smaller uh smaller >> the advantage of I agree it's totally like it works. It's a bit more efficient. I would say the advantage of not giving the flexibility to the user to select the hate of the is that you hide in some way every user has the same scheme. So you hide the lifetime because otherwise it leaks information.

>> It is looks like the same scheme but I think it's pretty detectable if I use multiple signatures. >> I agree. I agree. Maybe maybe you could do like pruning some small sub trees at random and so you don't leak. But I agree. Yeah. >> The problem with that part is that if you have a nondeterministic pruning, this becomes your state that you need to store because if you forget what you pruned, you won't be able >> you can make the state depending like the you could say the part that is kept in the print part depends on the secret key. But in practice in this scheme the force are extremely like the force can

handle 30 or 40 signatures on the same force and it still hold the security. So in practice even this idea that I said doesn't work because you would end up having only a few parts of the trees extremely used. So you can easily detect that the lifetime of this guy is I don't know 10,000 100,000. So so in some sense I agree it leaks information anyway. Maybe you might >> maybe need >> Yeah, >> Emil I was asking actually uh hopefully like in the in the future like we're going to have some outcome from sik.gov and I wonder like how much is the idea will be compatible with >> um by the way just by fun fact um so

this is the the like the easy version and if thanks to s.golf golf. There is this idea by Jonas from Blogstream where you you can do like you do um sorry if you are fine with more fancier construction you can have a forest of of what and exact and this is this is the thing it's go ahead >> so so will will actually work your idea with it okay >> this idea I I wasn't aware of this idea and on think jonas Nick submitted it And so that's why yeah and it actually it turns out it's kind of like you have the numbers here um it's it's much more efficient but worse

threshold because in force half of the secrets in the typical fors are secrets and half are public in this case most of the most of the hashes in the fors are done or secrets so it needs to be done in MPC which is more costly >> a a quite general question so uh what is the typical say 99% use uh parameter setting for threshold signatures is like uh four out of five two out of three or is it really like uh 50% of 200 keys? this question one because if it's small like if it's two out of three or four out of five would be the standard why not uh shifting uh the logic of uh

of threshold signatures to the aggregation layer. Well the two out of three is very common. Three out of five is very common. Smaller ones are common. However, big thresholds are critical. Like you can have 20 out of 30 type of things. You have chain link for example, you have bridges, you have all of these uh essential things within the ecosystem. And so although maybe it's one pair of keys, obviously not one but like a couple of like setup pair of keys, then they are relevant to the entire ecosystem like chain link for instance is. And so the solution still has to cater for for big thresholds

somehow. Um and then the setup of the of the of the MPC can vary so much like you have um let's discuss one setup from one company. Um there's let's say five machines, but three of these machines in three different continents are located down a mine and someone has to physically go down a mountain with a specialized elevator for every round of computation.

>> So in terms if you aggregate there is no MPC needed anymore. >> What do you mean? >> So I mean If if you just aggregate signatures and and and bind proof the logic, it's now uh say 12 out of 20 who signed. Of course, the proof of it, the Stark, snark, whatever would be maybe if you if you have a quite number crunching machine and use grinding, you maybe get it down uh 30k, 20k, depends on uh so uh so what what am I what I'm saying? If MPC is so costly, why not uh shifting the cost on

post-processing a proof that proves you okay, I've collected 12 valid signatures out of 20. >> When you say costly, what do you mean exactly? uh costly uh well that has to be seen but if you think you you would use a binary stark here with packing and high blow up read solommon encoding really high blow up like uh one uh two to the 7 two to the 8 uh >> uh blow up uh so uh I I don't have numbers here but uh I think you could get it down to maybe something that is that is that is deleable in the big picture of aggregate ation. It's

definitely not a thing that that probably uh Bitcoin was would be looking for. Uh I just want to add one thing like some of the companies even refuse to tell the numbers they're using for security. I mean they don't even disclose that they're like two out of three three out of they don't say they don't they don't even say this because for them it's even because if you say okay they're like seven out of 10 you know that you have to attack seven people they don't even want to that's a good point that's a good point thanks >> yeah actually that's in line with what I was saying like once you are paying the millions that you need for a setup like someone going up and down for an hour on a mountain you know that they're not

going uh disclose anything, tell you anything like it's it's a bit like we are talking billions of dollars of protected value. So it's yeah kind of difficult even on the like developing the tools you you cannot see the full architecture for that is the reference use case for what you're building. So it has to be like it has to cover possibly everything somehow. Yeah. what what I didn't get is just a general question also on on because I don't have any experience with MPC here. Uh so for both talk uh talks I mean on the one hand so even for small death circuits uh I mean what kind of uh timings do we get

under normal communication back and forth if it was online uh if it wasn't online it's probably hours or days I don't know to run through such a circuit in MPC uh so I I don't know So how complex I didn't get it from the two talks how complex the MPC in the end is really practically >> okay should work and I can tell you like for example our experiments there with computing the sphinx uh slots uh compute all the ashes required go going through all the ashes required to build one slot

was about uh I think couple of minutes um >> 3 minutes. >> Yeah, about 3 minutes on the three servers that we have which are which have basically very low latency and this can get very like we use Kekak as a as a a function that has uh as in previous talk we've seen uh 24 depth and depth. If you use uh ash functions that have thousands of depth uh you get a lot of a lot more computation rounds. So latency is a bigger factor there and I mean the yeah in our experience it's it's around like minus for some thousand a couple hundred thousands of ashes kashes but

again it depends a lot of a lot of things because um when you need to do that many hashes you it depends on how much you can parallelize communication in how much bandwidth do you have between servers and yeah it uh it's very implementation depending But it can it can be made very practical from an like from a enterprise product perspective. Uh it's not something like you know you need to stay there days waiting for things to happen. >> Great. We can also talk about hardware signing. So I know we have some folks from Ledger here. Um and that was part of the first talk from Antonio Matteo and Aleandro. Um, one pretty interesting

conversation still to have is the impacts this might have on UX. Uh, so you mentioned this briefly in your talk. I wonder if you want to just kick off a bit of a conversation about what some of these implications would be for UX for constrained devices. >> Yeah, I think >> and feel free to jump up or use the whiteboard or whatever you want. Yeah, in general I think this is very interesting from a user perspective and obviously would be great to hear more feedback but like um so who is using a hardware signer here or has used a hardware signer at least. Okay. Well, the ledger [laughter] person is a bit obvious, but yeah, I think most users do from a couple of thousands of dollars of value onwards, or at least they should. Um, the

experience that you have, usually depending if you're using it wired or Bluetooth, you still have some interruptions in a sense. For instance, there is a new firmware, you have to wait. Like there is a new update, you have to wait, you have to do the update, and then you can do your your operations. So, I think it's unlikely that you're going to use it in a uh fast trading environment or in an environment where the time that it takes to produce a transaction is vital to the economic outcome of your operation. And so in a sense I think having a premputee window of time is can be made very reasonable from a UX perspective. Like for instance I could uh depending on how much memory

there is and I don't know if newer models are going to have or at least there is a trajectory in there for the memory to increase significantly. I'm a little bit surprised about the whole memory thing because can't you just offload more precomputed things to a host that stores you know and then you you have some sort of authentication mechanism so that when you pull from the host that has gigabytes of of memory you just verify that this is indeed the correct stuff.

you can you definitely dig down a bit on that because u it's a bit unclear for me if the premputes are actually sensitive or not. So are they done purely on public information and you could actually store and if you lose them >> no it's private >> they're private information. Yeah that's so so they need to reside on a device or somewhere uh that you can trust. So >> well >> the the assumption was that we store that like that in normal usage scenario you would have to have enough memory for the Ethereum app for instance and then to store some of these uh some of the material for the premputed slots and possibly you would also want to install I don't know the Bitcoin app right this is like a more of a standard usage

scenario so if you can increase the memory significantly like model to model over time then you can just fit more material and you can do one longer premputee at the beginning and so then forget for a while. >> So what's the trade-off um what's the trade-off of losing the premputees and uh computing more or less uh slots? Is there a security trade-off associated with that or no? No, but having more slots means well first of all grinding is faster so that helps but the the signature process is already so fast that that is not a major UX concern. But the thing is if you can have a premputation window initially and you

know that that is enough to cover maybe your yearly usage of the device that is a much better UX because like I I plug in and it's going to update itself. update it takes what five minutes let's say. So if I'm also having 10 minutes of of premputee but then for the entirety of the year I don't have to worry about it. It's a very convenient UX if instead and then I have to refill eventually right so this needs to be obviously this is manufacturer by manufacturer but there needs to be a vision for that.

Sorry for the nave question last question for do do you need um a full list of the premputes if you when you do the grinding or how is the grinding work correlating to the premputee you have on the device the qu mostly I'm asking this question to understand exactly how much you can offload the premp compute outside of the device because one pattern which is very frequent is basically we we encrypt uh whatever we want to offload by the device out it can be stored outside and you just send it back to the device when you want to use it, >> right?

>> But if the premputee is like 2 megabytes, uh we're not going to fit them in the RAM of the of the device and uh and and that's a limitation for sure. >> So my understanding of the premputee is that to to do the premputee, you need the secrets, but once you've done the premputee, it's all public. Okay? So you can offload it to a host without any encryption. But what one thing that you do need to do is that when you bring it back from the host to the to the ledger device, you need to authenticate it to make sure that it wasn't tampered, you know, in transit. Um, yeah, go ahead.

>> Yeah. No, so yeah, basically the the things that you need to keep on the device which are secrets are the the secrets. So the pre images and stuff, but um all the XMs path all all of that uh is basically can be stored anywhere. It's not does not contain uh private information and also for the grinding to work you need to the only information you need to to to give to the grinder is uh the indices the indexes of the slots which are premputed and and once the grinder knows that and also when you start the grinding you need to provide a seed and at that point he just grinds until you hit one of the indices and that's the the whole grinding process.

>> [clears throat] >> So that premp computation that's for one key. Well, >> yeah, the premp computation this premputation is for one key. Then you repeat this for for one uh for one signature under one key and then when you you repeat this how many times you want and you prepare n signatures >> and yeah and then the grinder starts grinding until it hits one of those premputed slots. So if you if we have many applications with many different keys, we have to do all that premputation for each application basically.

>> Yeah. Yeah. This this premputation is specific to that key. >> So yeah. >> Okay. >> Yeah. from a from a hardware signer perspective, you wouldn't have much of a difference because like you use I don't know ledger live and you have plugged in the the ledger device and that is your your instance then if you plug in another one it's still a different thing. Um it doesn't take this much memory so it's not like you need a specialized computer or anything. every test has been done on traditional MacBooks um without having the ability to change the the way the device and the computer talk which obviously the manufacturer will have the slot production time has been brought down to

right 23 seconds per slot and in roughly six minute we do 16 slots. So then you are covered for 16 signatures. However, if we had to decide how to implement it, there's a million different optimizations you can do. So, like commercially, this can be made much faster, much easier from a UX perspective. In MPC is different because if you're using servers for instance, you can say, okay, tonight I'm going to premp compute everything I need for the next five years and that's it.

>> Okay. So you said 6 minutes of premputmentation for 16 signatures and after that we will need to do a premputation again >> either. Yes. So it's 16 minutes for 16 slots >> and then you can sign 16 times and then either you let it just go or you which would be I mean advisable you refill over time so your grinding time doesn't increase too much. So for instance, you could you could say, okay, now I have 10 left and so today I'm going to plug it and spend one minute premputing three to four more slots. And so I'm there constantly refilled.

>> The demo might work. >> So when you do the math, it takes 22.5 seconds to premputee one slot. So what you can do is that once you've signed one message and you've burned one of the slots, whenever you have 22.5 seconds free, you know, the ledger just happens to be plugged in or whatever, then you can just use that that idle time to just re regenerate the slot. >> Yeah. Actually, just saying like in the paper we're writing like we are modeling it like signing and replace basically. So when you sign, you replace the the bucket you burn or the the slot you burned.

>> Second. I mean it's a strings but I mean as Mate was showing the slide is a is a for >> you need to be stateful otherwise >> no it is stateless from a security perspective there is an operational concept that is close to state but it's just to go faster if if you lose your state you go on a new device fresh device you just redo the seven minutes premputee and you're good to go but there was no security risk involved obviously there there are some types of risk but >> what about if you reuse a precomputed slot. So if you manage to trick the device that this is a precompetit to reuse a premputed slot the grinding gives you twice the same precomposite

slot is >> yeah the force budget is going to handle that like let's say you can use it 16 times and you happen to summon it 16 times is still within the scheme. >> I think there is a slight security thing but I would say it's quite low. Uh so yes you have this state for example you have this 16 instances that you're searching for and uh if you lose the state no problem it is just the cost of regenerating everything is fine you can set up multiple devices that they don't have to sync each of their own state so it is very different from the stateful signatures that we're talking uh for example XMSS so in that regard it's

uncmped terribly better. So I would even call this stateless. But there is still this state and it's important that it is updated. So after I signed with specific instance, if there is a malfunction or there is a manipulation that my sets stay the same, it is bad for the security. Uh yes, but uh it is a much more heavier attack actually. Someone needs to remove the update or >> kind of Yeah. Yeah. If if >> so there is a a mitigation against this

which is to use increment only counters. >> Yes. Yes. There are ways to do this but I think it is still important to highlight that there is something that is added in this security assumption. So for example you need the >> monotonic counter which the legend devices do have. >> Yes. Some devices may may >> some devices may not. And then another degradation is that you're using local randomness. So if your random number generator is not is broken. >> Yeah. So I think this is all pretty minor and I I would be comfortable with these extra assumptions but I think it's just important to be aware.

>> So so that's very true but when you start offloading the the state outside of the device that what it gets a little bit complicated. So this security assumption is the one I'm scared about typically because if you start offloading that means uh what you've offloaded you actually need to authenticate it against the monotonic counter we have inside. Uh and there's one consequence a fairly strong consequence is that there's one property of most hardware wallet that you lose is that when you migrate your 24 hours from one device to the other you get the same level of access to your funds and and security levels. Uh if you start to have a state that actually impacts the security like the monotic counter then you lose this property. So basically let's say I'm loading my 24word that

deres my whole uh my my whole key of my whole key of secrets used for generating signatures potentially on a new device you might generate state that have been already uh used. So >> so the the monotype counter is only local to the one machine. >> Yes. >> So if you have a new ledger device then you can just reset it from fresh and and and you're fine. You still have access to all your funds. Yeah. But yeah, wouldn't wouldn't you generate recompiled states that might be in the same uh >> No, no, because you use local randomness that's freshness every single time you generate that.

Okay, that's all. >> Okay, that's no fine. Yeah. So, >> question for you guys. Do you still do the Vanadium project like with the offloading the app to the >> not not not as a generic compute mechanism but uh the the ability to just encrypt data store it outside and reing inject it in the device is is a is usual practice for for hardware wallet. So so not not easy to not difficult to build in the in the map for instance that itself. So >> okay but not the page by page uh >> yeah not not the full basically vanium was just a way to offload the code itself so it's very easy to offload the data code is a bit more complicated but

uh >> we still have the we still have it somewhere we can can resurrect it if needed or >> okay >> but we in general we don't like we don't claim the entire security of the device depends on the scheme itself like if I have physical access to the device and very specialized hardware then the manufacturer has its own ways of protecting the the device that doesn't belong to the scheme itself. It's just added security on top. >> You wanted to present something or >> Yeah. So, actually might help as well.

We've got I believe an unreleased tool. Is that correct? Or have we released it since I last checked? >> So, this is a visualizer. >> Yeah, you explain. Yeah, go for it. >> Yeah. Uh the idea so the reason why we build a visualizer is that for people that didn't spend a lot of time working with sphinx plus signatures it might be a bit hard to to grasp the way the premputee on sphinx g works and so this this visualizer I think it's best if you just explain as you do but uh build builds a basically toy version of spin plus where every card is a slot and then we will show you what what happens when you sign a message and how it is different on both variants.

>> Uh yeah, I don't know why it's >> Oh, the resolution is slow. Okay. Okay. Okay. Well, I mean the the core of parts is here. So um like this is how like a toy action of things plus like we don't assume anyone everyone is familiar with this hashbased signatures like um what happens is when you when you select when you are writing the message here you see that this symbol is changing what this represents and this is the randomizer what this represents is as as I'm changing the message I'm basically selecting which slot I'm going to use

because the slot that I'm going to use is uh is a function of the message and my secrets. But once I I if I sign twice the same message, you see that um we're going to use twice the same slot and and this is a property of um sphinx plus in sphinx g like this this is this changes because um when I write the message I'm not deciding which slot I'm going to use. This depends on which slot is going to be precomputed at the time. So if I want to use things G, what I do is premp compute message slots and this is agnostic from the message. I don't know which message I'm going to assign with

this. I will compute a few slots and you can think of this as um as drawing cards from a deck. like I I now have this this hand of cards and when I decide to sign this message, what happens is basically I start grinding this randomizer until I find one slot that is actually in my hand and then I delete it. And then I can sign another message with the slots I have remaining or I can compute more slots. And this is the like the freedom that we were talking about earlier like for for the UX like you can just premp compute a bunch of slots uh at the at the start of the year. If you want uh like 100

signatures you can do that provided you have sufficient memory and then uh as while I while I use the like this key um basically my computer slots get depleted. Yeah. So, and this is yeah and also as you've seen sending the same message yields different slots because the the hand I have changes. So now if I like if by chance I have the same exact hand twice and assign the exact same message twice I always use the same slot that is deterministic but this is a great coincidence coincidence and would be actually good for the scheme but yeah it doesn't happen and yeah this is it and of course use lots have let's say u

the force budget is being eroded and if I if I draw it again in my hand like it happened a couple of times if I happen to sign with it again. Well, it's not happening. >> Yeah. Yeah, but it just throws it again. Okay. If I pick it from my hand, it just has two two different uses. Well, now, okay, this is uh this this shouldn't happen. But yeah, a different message uh works down the forks. Yeah, that's it.

And basically the probability that I use twice the same force is um basically equivalent to to the to the one in uh in Sphinx Plus because once I delete it, I still have to redraw it in my hand um before I can use it again. Yeah, I hope it's a bit clearer like yeah >> just a general question about uh the security analysis which is about to work in progress as I understood so so I expect like against generic attacks like rand random oracle model for the hash functions if you say you prepare 16 slots just to name a number and now you allow 16

signatures that that changes the distribution does it doesn't it >> because because I think >> uh so if we assume good scenario the main idea from the sphinx is that you should choose the leaves uniformly at random and here essentially it doesn't matter you can have this game in mind that I don't you show the 16 uh signatures uh 16 16 leaves in advance I will hide them from you but I will just reveal them from

this I have it the 16 set but I will just reveal them one by one >> I mean just by symmetry must be must be >> the thing is it must be randomly send them >> I choose 16 slots >> and then uh you could even take more signatures on on that slot. I suppose >> no you shouldn't. This will break because now you you have this different distribution. Previously it's like okay if I support 2 to the 64 signatures and for each of them I sample uniformly at random then I have this distribution over leaves blah blah blah. If I say okay I have 16 signatures and then I for each signature I allow three or four

signings and then I resample this is slightly different distribution. This could still be secure but this also increase uh the state dependency. Now I have to kind count how many times I signed with this specific uh instance and after I reach the limit I remove it here. every time I sign I I I delete this better matches uh actually the distribution of honest signing. >> I have to think about it >> cuz I thought you know if you just say let's choose our slot at random of course.

>> Mhm. >> Our slots. Our set of slots. >> Yeah. Yeah. Yeah. >> And now just the other edge case I I use it only for one signature. uh that should that should produce the same distribution as uniformly random I suppose. >> Yes. >> Now you say up to 16 still does uh but if I in the 16 slot if I say now not not just for 16 but also for 32 signatures the 16 slot >> but this will be random among the 16 slots and what I want is the global picture. I want every signature essent.

So may I draw? Yeah, I know that's why I thought initially it would change distribution but if you say the choice of slot itself >> again what what what I don't know where I should stand what happens here we have I don't know some number with some we say we prepared these slots and then I have the first message previously what happened imagine I didn't do anything it mapped to a randomly If let's assume it actually mapped here.

>> Mhm. >> But uh how I can also see this is uh I f instead of after seeing the message I chose >> first you choose the partition and >> yes and then I map it. So now in our scenario we say okay uh but before our scenario actually and let's look then message two mapped for example here. This is already outside of this set bound. But in our scenario, what we do? We do the same thing. We have the first message map here in our three slots. We then remove slot, add a new one, and then message two is

mapped here. But if I continue, if I don't remove and I continue mapping, everything should land in the same area. and only then I somehow generate a new set and then this will slightly change the distribution. Does it make sense? >> I'm not sure if I understood. So So you're saying the second one when you say really you remove a node and add something. I mean what what what what's your statement that you want I thought if you if you say we first choose just look at the random game we first choose a set of uh three slots.

>> Yeah. >> And then we choose for a message a random subset of these three. This is the same as from the initial start. Choose a uniformly random one. >> Exactly. >> Yeah. And now comes the second >> the second stage I add a new random slot. >> Okay. So you need to rec add some recompetition. >> Uh you I think this is better. I think you can still uh yeah I think this is this is better >> or you or you need to allow collisions in your set composition.

So this is some details that we're still figuring out whether to allow set composition whether you have to add but I think it's a it's computationally easy to add because again this is just a one extra node. Uh but what you can also do if you don't want to add I think if you're selecting three nodes you need to allow the same node to be selected multiple times then this will represent also um a uniform distribution. Yeah, I wonder what what kind of distribution it would be if you >> uniformly random. If you if you allow um >> collisions then it is uniformly it's the

same as like every time I uniformly right. Yeah. >> Yeah. Yeah. >> I was thinking at the workshop >> by symmetry no just by symmetry just >> but I I have to meditate about it. It's very easy to make mistakes here. >> That's why Justin, did you want to talk about flip-flops and swimming trunks? Was that what the slide you had loaded up?

>> Yeah, this was just a [laughter] just a mental model. So this is um just for those who are not familiar I guess everyone's now familiar with hashbased signatures but um so for lin xmss the best idea that we have right now to make it mpc friendly is to have two two layers each layer is uh an xss with with two to the 16 uh one-time signatures. So um you know this this is very fast to keygen um and in order to get the lifetime that we want which is 2 to the 32 which is the equivalent of 400 years of

attestations which should be enough um you you you have this uh you know this quadratic blow up. So it's like 2 to 16 times 2 to 16. And um kind of the the names that I have in my mind here is that it's it it you have the cap at the top because it's it's the the Merkel cap. Um and the the nice thing about the cap is that you use it once and you you you never clean it, you know, you just keep it all the time. Uh you don't put it in the in the washing machine. And then uh if you if you if if this is the root of the tree and these are the leaves, then this must be the trunk, right? So we have the the trunks um and and and these basically would last for

for for three days. So um [clears throat] you if if you're making an attestation uh once per once per slot then you you you consume two to the 16 in in in in roughly three days. And so you know [clears throat] you wash your trunks every every three days and you you you move on. And then for um for so that's that's that's lean xmss and then one thing that we could do is basically have lean sphinx use the exact same framework where you it's just lean xmss plus a little bit at the bottom here. So this is a one few time signature. So this would be fours. And here you have

basically the flip-flops that um finish the whole summer outfit uh with with the the cap, the trunks. And the the the thinking of the flip-flops here is that the they're the leaves, right? They they go on the feet and they they break after after a few days, right? So you can use them maybe over 30 days and then after that they stop they start breaking. And it's the same thing with with few time signatures. you can you can sign safely up to 32 times and then the security degrades very quickly after after 32 32 times. Um so it's it's just a kind of a neat mental model to to to think about uh hashbased signatures. And you know the I and the N in sphinx do people know what it stands for?

It stands for incredibly nice. So, it's stateless uh practical hashbased incredibly nice. Um, I forget what the C is. Um, >> costly. >> What What is the C? >> Costly. >> No, it's not costly. [laughter] Something signatures. Oh, the C is cryptographic. Cryptographic uh, signatures. And I I kind of really resonate with the incredibly nice. I just think is just so so incredibly simple and and beautiful. [snorts] >> Maybe a first question is is this an explicit goal to unify the two schemes or is this just a more of a mental model for now?

>> So one thing which I think would be a very nice disata is that the key gen for both Linux MSS and LIN Sphinx would be exactly the same. So you know this just something that that people understand very very well. Um, the idea of having this be a tree of size to the 16 for lean sphinx introduces inefficiencies and and so it's it's more of a of a metal model than a a super optimized thing. Uh we also thought about putting uh just a one-time signature at the very very top so that the key genen is just

generating a single one time signature. >> Mhm. >> But it introduces bigger size, right? >> More computations, but now your key generation is empty essentially. Yes, >> if you need a lot of key gen and maybe not that much signing verification, that might be interesting for some use cases, but we declined the idea, I think, more or less. >> Yep. Yep. Yep. Um, so what is this for your key gen in in in shrinks? What is the size of the top tree?

>> Uh, I don't remember by heart, but I think it's 10. >> 10. Okay. But I can check but I don't know. >> No, no, just one uh one sub tree at the top. >> No. So there is a hyper tree, a tree of trees and Merkel tree. A single Merkel tree. I think in our case the single Merkel tree is number of leaves is two to the 10. So the height is 10. >> So age is 10.

>> Yeah. Yeah. Yeah. >> Yeah. Yeah. Yeah. Yeah. >> Is this shrinks shrinks? >> Uh yeah, but I I might be wrong about the numbers. I I will check. [snorts] >> H sorry. Usually H in sphinx is the like is the total eight of the tree and the if I understand correctly this tree that we that we're talking about is just the top hyper tree the keyun one because when you when you need to do kenun for things >> you just need to compute the the public key and so the the top h the top three. >> Yeah. So so that Yeah. Yeah. >> So here is it fair to say that h is equal to two, right?

>> Here h would be 32 >> 22 or >> 32 because it 32 is the combination >> h prime let's say would be 16 and the product. >> Okay. And what is the parameter that counts the number of >> d in usually is d. >> Okay. So cool. >> But that like that assumes um equal layers >> which we do have here. >> Yes. Here here [laughter] it works. But in general like if you want to do fancy things with uh different height layers then you need more complete parameters. >> It's nine >> with five layers. So we have 45 height right now.

>> Okay. And do you see a world where this could be increased to 16? >> Uh maybe. Okay. >> Yes. I don't know. Yeah. The parameter search is very is very difficult because it it it it always comes at the cost of something else. So if you build build uh bigger trees it's smaller sizes and smaller verification but it uh takes your kitchen and signing time. I think what we what our cap was uh to not exceed swings plus on any anywhere signing key gen verification

we we say okay things plus >> oh I see uhhu >> is it a good idea maybe not >> okay but uh [laughter] like do do is it fine to go twice this time of things plus maybe Yeah. Yeah. So it is >> So yesterday during dinner you mentioned that um Blockstream or the Bitcoin community might be interested in launching an alternative to Sik.golf with new parameters. >> It's not um >> No, it's not it's not a secret. It's not confirmed.

>> Not confirmed. It's just an idea. >> It's main. Yeah, it's it's discussed. >> Okay, cool. Um I mean it would be because we I think we also intend to kind of extract all the alpha from sik.gov. >> Yeah. >> And you know learn more about all the constraints that we have and then have a second version of seg.golf with like the final parameters if that makes sense. >> Yeah. >> And maybe >> MPC in particular. >> Yeah. MPC in particular. And uh it might make sense to to have discussions to kind of converge on these parameters. >> Yeah. Yeah. Yeah. What would what would be the reason to split the competition at this stage? Do you think there's a reason for Bitcoin to have its own sigggo at this stage or is it still worthwhile to do all at once?

>> Yeah, there was some discussion as well because um here again for Ethereum it's a big uh part is that you need cheap verification and in general the verification is already cheap. If I do 150 hashes or 300 hashes, uh if I really have to do verification, maybe I don't care that much. It doesn't matter. But when for the Ethereum, it's it pays a bigger role because uh this is when the snark will draw the circuit and the circuit becomes more complex and then the snarking becomes more comp. And so in that regard they have this uh uh size times

verification. I would uh if I would think something for Bitcoin I would put more weight on on on size and bit less weight on on um verification. But yeah I mean that's something that could work for us as well potentially where we have size to the power two times verification. So there's more weight on the size as the thing that you're trying to optimize. >> But if it is times times, it's commutative. So you don't know what's the weight. You need addition or something. I [laughter] don't know. If two times size times verification, it's the same is size time verification times two.

>> No, it's to the power to >> ah power of squ. [laughter] >> Are you trying to just fit more transactions in a block in Bitcoin or what? No, this is the rough idea is that yes you we we have the limited block size increasing block size will spiral another uh age but >> there is no increasing block size like let's not go there but >> some discounting is discussed and and and things like this but anyways the smaller thing we can fit uh into the block general it feels like this is the better >> but you Starting from here, it's a very long way to be able to fit a normal or

comparable number of transactions. >> No comparable. There is no comparable. We are in postquantum comparable is out of the window. So, but we still can do uh the best we can. And this is also where the stateful part uh comes in our proposal because in the stateful part instead of building a balanced uh tree uh we allow flexible tree and so you can build a skewed one kind of so that the first is at very top and then this is roughly you can get 400 plus minus 100 bytes signatures. So it's like 500 bytes signatures.

>> Yeah. But like if you start from numbers like this and this is even with the contribution from your own team, right? >> Yes. But this does >> even if you decrease it I don't know >> uh >> 45% more. Aren't you still too far away from having a block that is uh including a decent amount of transactions? >> It is away but it's closer. 45% closer. >> Yeah, that work is not happening. No, I mean you have to deal. This is not some magic that we can perform and say oh somewhere from nowhere we arrived with a signature of 200 bytes. maybe when uh isogen is mature

[laughter] but uh this is nowhere to be seen right now and you cannot wait 5 10 years or I don't know how long till you say okay now I'm ready to do it I think it makes more sense to have a cashbased scheme it will lie there you can also not use it you can still continue using CDSA until quantum um you think is dangerous for you and then uh you have something to use and uh the best we can give is the best we can give is it not satisfiable no I'm sorry this is the best we have [laughter]

>> so that is going to be sg good enough >> not good enough [laughter] so one uh one cool observation if you go to sik.gov golf and then you click on the the parto uh tab. So you can see all these are all of the historical um submissions and one thing that I find extremely surprising is that um basically improving the size and reducing the number of verification cycles is basically go hand in hand. It's like very high correlation. So we we started here and then we went here.

We done now here we went here. And so basically it looks like, you know, we're going to end up maybe maybe somewhere here. But what I would have expected is that if you allow for larger signatures, you know, there's an opportunity to have fewer cycles like this. I would have expected some sort of curve. But uh spoilers yes I think the Hogwarts can do better than the best result here but it will give 6.5 kiloby signatures.

>> Submit it please. >> I I I yeah I don't have a proof and I don't have uh yeah I don't have yet. It's not ready but maybe it will be sometime. I also wonder if like the stuff that um Alon showed yesterday might be applied here like they has less. >> Yes. The really annoying thing about Elon's idea is that you lose a few bits of security. So you get 125 or whatever and this competition requires 127. >> 127. Yeah. >> But does the competition does the competition also I think it counts uh hash function call regardless of the size of input as one. Is it?

It counts um like you can hash any uh input size essentially but it will count the number of compressions that it would do if it was bl. So essentially you divide you the input size by 30 sorry 64 bytes >> and it gives you the number of compression calls. >> Okay. Okay. Okay. Then actually this will take into account but I will it really lose bits of security maybe. Okay.

Yeah. So that's something that we the analysis hasn't been fully finalized. So Elon mentioned so there was Mitri's paper in 2021 and they had terrible parameters. it was like 65,000 or log of 65,000 bits lost and then they managed to reduce the number of bits lost to like three or four or something and maybe there's an opportunity to squeeze the number of bits lost even more so it's still unknown um but yeah it seems like there is some nonzero amount degradation when you do the these fancy exos yeah some yeah Well, I guess there's just more

flexibility for the attacker to to play games. Um I I don't know. Alon is the person to ask. Yeah, I think regarding what you said earlier, um we could have gone the other direction, but the way the competition is made is like people are going to build on top of the best submission. Uh, and so when I started to submit and reduce the sync, I drove the competition in a specific way and I could have gone the other way.

[laughter] Um, because I think for Ethereum it's more >> interesting to go that way. But uh yeah, >> I mean what we saw on EC failed is that over time we're we're drawing the entire parto frontier and I think this is something that we want to do to kind of understand the whole parto frontier. >> Yeah, I actually um so I participated in this competition. Um I had a whole day of I actually don't care about the cycles at all. all I care about is the bites >> and it was hard to get like a winning score um without >> like building on the tree uh building on the top or the crown. Um so I think there is space there to just have the

focus going I guess that way if we're looking um at this graph. Um cuz there were some like levers there and there were some ideas that um Claude Co came up with, but um I Yeah, they they kind of just like sitting there um had to be killed because the verification cycles added um too many wins. >> Mhm. No, >> no, >> this might be coming up later, so we don't have to talk about it now, but you mentioned something interesting there about a new version. I I know this is meant to be thresholds, but we're kind of all things digital signatures at this point.

>> Yeah, >> you mentioned a second competition. Is that being spoken about later or is it worth sharing a little bit about that today? >> Yes, I think we're going to discuss it later, but there is no exclusive can. So one of the things that's actually very relevant to hardware signing is that we have assistance from the host. So the host can do computation you know and it can compute arbitrarily you know communicate arbitrarily with the with the ledger device and it can also provide hints of sorts. So it's in some sense it's similar to to to to the snark environment. Um and um you know one of the things that you can do for example

in the in the grinding setting is that you have the host do the grinding and it could be a lot and if there's some trust involved in the grinding then you can have a a proof of of grinding to make sure that um you know it was it the proof of work was was not uh cho chosen maliciously. Um but you can do yeah like more fancy things and right now the model that we have doesn't allow for these optimizations. So if we relax the model and allow for all of this assistance from the host then we can probably dramatically uh improve the the signatures. So in some sense this is just the first round where you know

we're just picking the lowh hanging fruit and then the the second version of the model would would tweak the parameters but also potentially just completely change the model to be much more relaxed and flexible for for these new ideas >> printing is very powerful >> and hypertree printing yeah as well. Um yeah. Yep. Yep. Yep. Do >> you also have the security proof uh in the in the challenge like that? So do does do the submitter have to submit security proof? >> Yeah. Yeah. So um every submission comes with a with a with a proof. Um so you can uh you can just click here on the submission and you you can just go to the the GitHub and uh so so see you

can you can see the commit And you can see, you know, all of the all of the lean for code. If you go to the where is it? Uh [sighs] if you go to the rules. Mhm. Where is the how it works? How it works? Yeah. You have every like every hole here for instance. I don't know like the the security you can click and you should be able to access the where is it the lin statements. Yes. For instance the security claim click this.

Yeah. So this this is one of the things that we were talking about um yesterday where the uh the the security claim is extremely short. So here you have the statements.lean lean and it's it's 62 lines but only 15 lines of code and you know that is that fair to say um Emil that uh this describes what we're trying to achieve >> of stuff in this fight particular you have the risk five semantics and but yes it's the rules are quite simple um yeah questions for the security proof require that it's

tight reduction. >> The security proof requires the reduction to be tight. So someone can come with a better scheme which is less secure and it's still fine from you. >> What do you mean >> tight? I mean you have you prove when you when you say security proof I guess it's reduction to to what >> it's not a reduction based security proof >> in the sense like typically um traditionally the papers in like SJSA have reductions to like standard model model properties and this is not the case >> random one >> sorry >> it's random model and what about security loss I mean can you

>> yes and it turns out and that um historically the security of SLGSA by NIST and and others I believe correct me if I'm wrong like there was in particular a log like a loss in W in particular the the the number of chains in in WS and it turns out um you can avoid this loss it was not a fundamental issue but the just the proof is more complicated and it turns out uh um like we can have 127 bits of security proven uh >> so you require in the competition you require 127 bits of But that is the random oracle one. This is so the it is

>> a little little bit comparing apples to bananas because >> the W loss is to in the standard model no random oracle assumption. This is one thing and another thing is you count queries differently. So if I understand correctly the statement um usually what you say okay there is some function let's say Q uh is your variable is the number of hash function queries you do divided by something let's say 2 to the 128 this is the best we want to achieve in the random oracle model and uh usually signing query free key generation free.

These things are free for the adversary. This doesn't go to the queue with the one that is stated right now in the in the C golf. this goes into Q and then uh it I wouldn't say it is bad but it is it is good for the competition I would say but it needs a more careful analysis at the very end because what can happen for the parameters uh in sig golf it's not that dramatic but for example if you do the same thing for swings plus you have 2 to the 64 signatures Each signature takes roughly 2 to the 20

something computations. So you have a denominator Q + 2 to the 80 divided by 2 to the 128. So your bound becomes Q over 28 + 1 / 2 40. This 1 / 2 40 you can effect with adversarial computations. But this is a pretty low number. And if you read it as it is essentially if if we just we don't look at the reduction but we just look at the number that means one in every 2 to the 40 uh key keys will be broken without any effort.

It is not true per se, but if you look at the proof result, this is roughly what it tells you. I I totally agree. Um I believe Benedict told me that some papers have the very tight uh version where you do not count the queries from the game and some do count them. Yeah. >> So, and the easiest way was to count them. I think it's fine for the computer because again this is editive >> the problem that is happening is actually manageable and we will have a paper released soon with where we do all of this care very careful accounting

which query hurts you where under which assumption we can think of them as independent and doesn't hurt so I think for the competition it's actually fine but this is some some differences >> and it's it's fine as As long as you have some bounds on the signing time in particular um >> and key generation time also. >> Exactly. Because otherwise you can make the the security totally meaningless. >> And that's why we require in the rules that each program of signing and must terminate in like at least two to the 32 I don't know cycles to make the security meaningful.

>> Yes. Yes. Yes. Yeah. Agree. Yeah. Question. Have you guys uh worked a bit on sort of like trying to reduce the time of verification? Uh cuz like the time from submission to when it's actually live on the dashboard is quite long. I think it's like an hour and a half or something and it hurts a bit. The UX I think. >> Well, this is a Yukon that is running the script on this. So no, we didn't improve it, but what we did is the proof became uh bigger and bigger. So we increased the uh max size of the submission. So it takes even longer now, >> right?

>> But yeah, maybe we could have a a look at the I think it's blackmissu the the script that Yukon is running on this. Uh but yeah, that would be a question for Yukon. Okay, sounds good. I just uh little bit out of the topic if you want >> just to close this topic um there is an open PR here um to basically um reuse proofs and do better caching um so yeah that should be coming and then there's also a whole effort to make lean for itself faster um so there might be like a lean forfast uh you know auto research uh compos

>> [laughter] >> Sorry. Go go go go go ahead. uh so I was running the search for the parameters for for the new scheme and uh they don't land in the restrictions of the seag but essentially again if we say I am happy to do the same amount of computations for signing and uh uh verification key generation as things plus or maybe not more than two times that I think you can get uh 2.6 six uh kilobytes signatures for 2 to the 32 budget.

>> This HD >> which scheme is this >> HD what's Yes. Yes. But uh that is not in the budget for um key gen signing maybe it it breaks the budgets from the se competitions but for example again yes 2 to the 32 is 2.6 Six >> 2 to the 64.5. So it's full stateless swings plus like scheme 4.5 maybe twice less efficient. Uh didn't check the numbers vibe numbers cloud numbers.

So but probably true big if true >> and so this is the because of the signing and kitchen budget of the competition or >> yeah I mean this is a a different scheme that is not in the sele yet but it is similar to this what's children stuff uh and uh this is increased uh siding and stuff. Yeah, >> one of the things that we try to do with s.golf is be very conservative on the parameters so that going forward we only relax. So we only you know increase the budgets or make the models more general.

So in some sense the what we're seeing right now is the the absolute worst case scenario. Um things should improve dramatically from what we have right now. Anything else? Great. I think we're just one minute over time. >> You do. >> Perfect timing. >> Oh, great. Yes. Perfect timing. Yeah. Yeah. So, lunchtime. That was great. Thank you very much. We covered a ton. NPC signing, then into hardware, and then into all things digital signatures.

H if anyone has any more questions, we can also break out at lunchtime and and have some side quests. Thank you. Thanks. [applause]