Björn Tackmann - Threshold Cryptography for Multichain Dapps

Transcript

[Applause] thank you very much for the introduction so you may have seen that threshold cryptography actually uh becomes a lot more prominent in in the entire blockchain space so there have been early adopters like thorchain or ICP was also pretty early and now recently more and more projects seem to join that train so Exar is a recent one near has just announced that they're also be part of the threaded crew so as a cryptographer I thought what's the best I can do for you and I thought I'd give you some uh overview of threshold cryptography and so uh I set myself two goals the first one is for all the non- cryptographers I want to give you one or two of these beautiful aha moment where

where something really becomes clear and that goal number two without any potential cryptographers in the audience later beating me up for oversimplifying the beautiful things so what is thr cryptography I mean on on the uh high level it's very simple it's like this we have a group of nodes such as the four nodes there on the left uh and they together want to perform some cryptographic computation and they want to do this under two conditions so the first one is for some thresold T which four nodes could be three for example any three nodes together should be able to actually do that computation but any less than t two three or generally T

nodes should should not be able to do that in particular they should not learn anything useful for them and so when I was a student in cryptography I found this really fascinating like how do you get this properly that for T minus one you know nothing the nodes cannot do anything with a material they have and yet you just add one additional note doesn't matter which one anyone and they suddenly can do everything so how is that possible and the answer is of course math um in this case it's a polom because pols that was detected by Shamir or the application was detected by Shamir in the 7s or ' 80s is pretty old pols have this beautiful property where I mean I've shown a degree 3 polom there

and uh that has the property that if you know three points three of the gray points say on that polinomial you have no information at all about the pink point the pink Point could be anywhere on the Y AIS in that case case but if you know any additional Point any additional fourth point you know the entire polinomial you can use LR interpolation to compute every single point of that polom so this gives us this very hard uh gap between what happens at in this case D and and D+ one and so of course we're going to use this to uh put the private key that we will use in cryptography we put that at

the uh Pink Dot there so it's it's convention that one puts it at at the axis but you could actually put it anywhere it doesn't matter just a convention um and yeah so how do we go forward if we want to do threshold computation I'll now specialize a bit to public key cryptography in particular uh digital signatures we have a private key space and we have a public key space and the two are usually mathematically very different so in in the elliptic curve schemes that widely used today the private key key space is just numbers and the public key space is points on the elliptic curve and so there is functions between the two and it's easy to go from a number to a point on the

elliptic curve it's practically infeasible to revert it okay so what we're going to do with the threshold scheme as I've now replaced the the gray by three different colors here so it's bit easier to distinguish uh what we're going to do is we give three parties these three colored dots and together they kind kind of know the uh Pink Dot on the right the key where we want to go to and so now we can ask the question how do we compute the public key and if we have the pink one that's easy right we can just do the standard computation from the number to the elliptic curve and and we have the key and of course we also have this lrange interpolation so if we if we have the key shares of all

the parties we can interpolate and get the private key and from there we can go to the public key unfortunately that's not really useful uh because that means we have to compute that interpolation in some way right someone has to comput it and they will know the Pink Dot and once they know the pink dot they know the private key and so that's bad no single note should ever know the private key so this is not something we can do so we're not going to use LR interpolation here we're not going to compute this thing and in particular we're not going to compute anything from it instead what we realize is that the colored dots are mathematically very similar to this pink

dot right there're the same thing they're also just a number and so we can interpret them as private keys and we can compute private keys from these public uh sorry public keys from these private keys so every node that has such a key share uh can compute the corresponding um private key corresponding to its key share and since we have a nice homomorphic ISM property which is mathematical speech for it preserves structure uh we can also do the LR interpolation on the level of public keys right and so this is the idea this is the core idea of most threshold cryptography protocols we share the private key but whenever we need to

compute something we go to a different space and we compute in that space so here for computing the public keys and if we think about threshold signatures we basically do the same thing for the signatures so we can just replace all the public key stuff by signatures it's easy to compute the signature from the uh private key it's hard in the other direction um and every party can compute using the private key a corresponding signature um share and again there is such a homomorphism property so that these parties can use the same type of interpolation to compute the signature now this has to be taken with a grain of Sal so there is some cryptograph scheme such as BLS which if

you know the proof of stake ethereum you probably have some had some exposure to BLS is super nice in all the properties and so for BLS this diagram works exactly and you can think about it in exactly that way if you have somewhat less nice signature schemes such as schnor EDSA ecdsa in particular it still kind of works in an intuitive sense but the protocols are a lot more complicated than than I can show here now okay now we have the threshold cryptography threshold signature scheme um and it's exactly that if we have sufficiently many notes we can sign otherwise we cannot now you may ask wait wait wait isn't that a multi signature

if sufficiently many can sign then it's going to be accepted and not quite and I think there's a nice Duality between the two uh that it makes sense to explore and that's as follows so for threshold signature every party as I've shown before has some kind of a share of a keys so you can think about it as every party owning some part of the key and if enough of those parties come together they kind of know the entire key and they can proceed so it's pretty complex on the sender side but it's very easy on the verifier side so for the verifier this looks and smells and feels like a standard signature and the verifier just has to run standard signature validation

in order to validate this uh threshold signature and multi signatures do a very different trade-off in multi signatures every node on the left hand side has their own independent key they just generate it and they sign as if they were just providing a single signature and the work in that case is very much on the on the verifier side the verifier has now now has to uh know all the public keys not only one it has to validate all those signatures and it has then to decide whether uh the signatures is so comply with a pol policy it's supposed to implement and so I've tried to make it uh in in to to examplify it in a a

bit in this table so in a threshold signature we have the same verification as in in in an existing signature scheme you can use exactly the same software where it's a multi- signature the verification is tailored you need to implement multiple signature verification and a policy in threshold signatures the policy is on the signer side because the verifier doesn't know about about it uh in multi signatures obviously on the on the verifier side in threshold signatures the group of signers could change and the verifier wouldn't notice uh in multi signatures if you want to change the group of signers you have to actually change things on the verifier side so make make a transaction for example where on on threshold that's not necessary on the

other hand for threshold signatures it's pretty much non-accountable like all you know is oh I have a valid signature enough nodes have signed but you don't know which ones in a multi signature you always know which nodes have signed right so the the two are kind of related but they are useful for uh somewhat uh different scenarios okay so what can we do with them wait not so fast the problem with this is especially as a young cryptography researcher you think like this right so there's threshold signatures and once you solved your threshold signature all you need to do is you need to bring them to practice and the reality is more like this sure you have your threshold signature but

now is where the hard workor actually starts and I just want to give you some examples so one is how do you actually choose the set of nodes like who do you give the key to the second one is how do you actually give them the key I mean no one is supposed to know the key so how do you actually come up with that key a third one is and what if one of those nodes dies and takes its key share with it like how do we recover right and so I want to give you some some hints here so choosing the nodes I mean here kind of the problem is that every node is the same every node has one share and that works very well for some cases where you

for example your consensus in ICP that's easy the consensus is every node has one vote and all the nodes are equal so in ICP we could just Implement threshold signatures in in the consensus or as on top of the consensus mechanism that we've been using but for other consensus mechanisms such as ethereum that wouldn't be so easy right because you have very different voting rights uh depending on on the stake and for threshold signatures that just doesn't work of course you can make many shares and distribute them uh somewhat unequally but that's an efficiency catastrophe so that's not what you can do in practice either and so for example what near seems to be doing based on their documentation their recent

implementation is they have their blockchain and then they have an MPC CL a permissioned MPC cluster sitting next to the blockchain so they completely separated it's just something I mean there are solutions um but it's very important to think about uh what your solution then actually also means for the security of the system now for the next part how do we generate the key and the nice thing is there's distributed protocols that are called distributed key generation that do exactly this and uh they were they start work on this started in the '90s um so today there's efficiency improvements but they still base on the same foundations and the idea is as follows on the right hand side we have the receivers those are the

ones that are supposed to have the key after we run this generation protocol and the dealers on top they're helpers they're just there in order to facilitate the protocol and the protocol itself the core structure is again very easy so what each of the dealers does is it just chooses a random key so the one on the right on on the on the left hand side it chooses this purple Dot and creates a sharing with the color dots and of course that dealer knows the purple dot right that's how it works and but then we have more dealers we have the one that does the squares and the one that does the triangles and so forth and so what we're going to do is we're going to collect many of those dings and every node will then basically sum up

all of its colored shares it receives and so overall what we're going to end up with is uh we need three things the first one is we need sufficiently many honest dealers actually if there's one honest dealer that's sufficient to provide enough entropy for everyone okay so we just need to make sure that we have at least one honest dealer that's going to uh to produce a correct dealing and and distribute it to everyone and then even if all the others are dishonest as long as the honest one deletes the key it's fine so you probably want to have more than one honest but anyway um the second property we need is uh we need the individual dealings to be correct now this is

complicated so I'll not go into this into detail there's interactive protocols with the receivers complaining there's zero knowledge proof based things this is really where where a lot of the work recently is also happening and the third one we need to make sure is uh that we have agreement on which kind on of which set of dealings we use now that's trivial right if blockchain can do one thing it's agree on something so that kind of that is kind of easy and now what's nice here is now the receivers on the right hand side they actually have a key that no one can know um right so the sum of all those keys is actually something that unknown another nice property is that we can slightly tweak the protocol and uh

use the receivers as dealers and they can re share their keys so instead of creating a new fully random key they take the key they already have and create a sharing out of that and with a slight adaptation of the math in the protocol this allows us then to have one group of uh receivers that own the key that act as dealers and transfer the key to another new group of receivers so this is how one can deal with a problem of having nodes that die you can replace them and then just use this protocol again um to provide a new sharing okay so that's what you need to

add to all the threshold signatures in order uh to make them usable in practice can we use them now yes we can and um just to give you an idea so this is my very easy description of the ICP architecture thresh keys are used in ICP everywhere uh in particular we have subnets which you may also know as cards um and each of those has its own threshold key now the advantage of this is it makes interaction between them extremely efficient because all that they have to know about each others is a few hundred byte of public key and then they get the signed messages and they can just verify and all is good so if we have Smart contracts on one chart

communicating to another chart it's basically a threshold signature verifying a threshold signature done there's no need for any node to replicate State and so on and so forth it also makes it super easy for clients to validate information they receive because they can just validate the threshold signature there's no need for clients uh to validate anything about consensus it's all about threshold signatures now what one can also do with those things is actually Implement multi-chain depth so that's where the title of the presentation came from so you can create a signature on one blockchain network and then sign a transaction that's going going to be executed by another um blockchain Network so I've taken ICP as the cender

side here so ICP would generate an ecdsa signature for the transaction pass that to ethereum and would just be a standard smart contract call from an account external account address from the perspective of ethereum and you can then use this to build uh nice kinds of multi-chain application I've like my simplest example here is just a timer application so smart contracts on IP can set a timer they can say wake me up at 5:00 p.m today uh which evm contracts cannot do right and so you can use this in order to implement uh things like limit trading or uh scheduled treasury Management in an evm contract in a fully

decentralized way because you just have a smart contract um on on ICP that would call out to this ethereum smart contract of course you can do more uh like the ICP contract has the capability to interact with web 2 Services it has has access to the Bitcoin utxo set it can also for example read uh events from evm chains and it can all do all this and provide the data um to the ethereum smart contract so you can basically Implement a full Oracle uh just into two smart contracts interacting with each other or this one is one I I find particularly nice is um ICP smart contracts have a pretty

high capacity in terms of memory and compute they have so you can build Dows entirely on chain the entire voting can be uh fully entain um but you may want to use this in a way to control assets or smart contracts on ethereum but for this you may want to actually take data from ethereum so uh a colleague of mine actually has a demo on this on at 3:30 at a neighbor stage showing how exactly this year Works uh where a governance contract running on the on on the internet computer fetches uh the the voting power data from an erc20 contract and then execute the transaction on the

ethereum blockchain and yeah so that's all I wanted to go through today if you're interested in this kind of thing um colleagues of mine uh will give several demos and and tutorials on this so Thursday sorry Sunday morning is another one so you'll find them across the schedule uh if you want to have a look at those uh that's going to be the same in much more detail on the technical side thanks again I was wondering um is there some signature scheme uh that has that is like some kind of a mutant scheme between multi- signature scheme and

treas signature as what I'm trying to get is the property with treasure hoold signatures normally you just observe the signature and you have no view on who actually signed on the uh who actually produced and partially signed the the data is there some kind of a signature scheme where you can do that where the signatures are actually different uh the resulting signature is still valid but is different based on who signed it so the answer is yes and no so there is research work on this by Dan Monet from Stanford University and that explores exactly the space between the two um so I think it's a very interesting research Direction the problem with this is it does not work for existing schemes so

whenever you need to uh to support something that is existing you will run into the problem of having this non-accountability but in principle it's it's totally possible just not with the currently standardized schemes but it's not implemented yet any like with any not that I'm aware of no I think it's right now it's really at the research stage but I think it's a very very promising direction for for exactly that reason yeah for some application that would be super helpful uh you know so you know and you can punish or reward the nodes that actually participated absolutely I I mean we've been implementing this and we've we would have loved to have full accountability for the threshold signatures problem is the current ones don't have it thank you

any other questions we have three more minutes but we will have a uh coffee break actually starting now for 30 minutes also feel free to approach be yep feel free to find me anytime I'll be upstairs so thank you so much