Libsecp256k1 Maintainers Meeting
Date: October 12, 2022
Transcript By: Bryan Bishop
Tags: Libsecp256k1
Q: Why C89? When I asked you this question a few years ago, I think you said gmaxwell.
A: There are a number of embedded devices that only support C89 and it’d be good to support those devices. That was the answer back then at least.
Q: Is it a large cost to keep doing C89?
A: The only cost is for the context stuff we want to make threadlocal. The CPUid or the x86-specific things. These could be optional. If you really want to get into this topic, then perhaps later. It makes sense to start with a list of topics.
Topics
- release
- MuSig and FROST in secp vs -zkp?
- write context
- scope of the library in general, staging branch, adaptor signatures, etc.
- PR for anti-exfil in Schnorr (it’s in -zkp)
- sidechannels, big picture; with the new CPU speed leaking thing. It’s more about synthetic nonces for ECDSA.
- cryptographically impossible branches: coding conventions for things that are cryptographically impossible to reach, into a CONTRIBUTING.md or something; can we change this to not include it? To get rid of the branches. Like when you hash a value and check if it’s in the curve, should you really have case handling code for the unlikely things to occur?
- cmake/Makefile is another topic that regularly comes up
- immutable context
Release
For people who aren’t very aware of the status of the bitcoin libsecp256k1 project, some context: we’ve never had a release. That’s it. That’s the context. Well, we want to change this. We want to change this because people ask about this a lot, and it’s been distributed in debian and other distros distribute our libraries with version numbers as commit ids. It raises some questions about API stability. At the moment we’ve been trying to maintain stable API because we know people are using our code. But without versioning or releases, there’s no way to signal breaking releases. We have effectively transitioned to a mode of development where we treat the code as a stable branch because people are using it as such. There is no development branch.
The current conclusion about releases has been, just tag a release. It doesn’t need to be v0.1. We have just a very small TODO list and I think it’s actually that’s why I’m going into my personal opinion but I think we’re still okay with this small TODO list. It’s currently blocked on me because of documentation changes. One of the changes we want to make, we had some API changes that are backwards compatible officially but still deserve some documentation. We made the changes without changing the documentation; it’s currently, I have a PR that changes the documentation. It has had some review. I’ve been saying for several weeks that I would address it. I still believe I will do this in a reasonable bounded amount of time.
API cleanup with respect to context. This one was changed to draft because it had.. I didn’t want to make this change everywhere. I made it in a few places to show it as a showcase but I want it to be done everywhere. It has been concept ACKed in the IRC meeting. So really it’s just me being slow.
There are two other pull requests on the initial release milestone. One is enabling non-experimental modules by default. Non-experimental modules are ECDH and Schnorr … I think recovery stays experimental. Why? Just because we hate it? Yes. The rationale is in the commit message. There is an additional reason not explained in the commit message. We don’t recommend new protocols implementing ECDSA pubkey recovery. This pull request currently has only one ACK. Bitcoin Core uses ECDSA pubkey recovery for signmessage.
One question is experimentalness, and another one is enabling a module by default. We can’t reasonably say that recovery is experimental. Its API has literally never changed as far as I know. We could change that, I guess. I wanted to change it, I don’t know if you remember, to optimize Russell’s idea to optimize the n-choose-crate… But do you really want to write this code now? No, well, I wrote a lot of it already but then there were additional optimization ideas and that basically killed it. They were good ideas. It required much more work and I abandoned it at some point.
Are all APIs in secp256k1 meant to only be used in Bitcoin Core? No. In fact, ECDH isn’t. This is the main reason why secp256k1 is a separate library. We think this is the best implementation of Schnorr signatures in the world and we want hardware wallets to use it and other wallets to use it. There are some that do. There are lots of non-bitcoin and non-cryptocurrency projects that are using the library.
One final PR on the milestone is prepare initial release by bumping the version to v0.2.0 because v0.1 is basically already in the world. Version v000 is the library version.. no, okay. I thought it was 0.0.1. It looks a little bit weird that.. you can’t skip versions. The first release of Windows NT was 3, you know.
Another topic to discuss, maybe, do we really want experimental modules? Rusty’s argument is that basically if you have a module and you expose it then people will use it and start depending on it. You can’t hide behind “oh we called it experimental and you shouldn’t use it”. If it’s useful and it’s the best implementation out there, then people will use it regardless. That’s a fair argument. But sometimes there are actual situations where … I think we should have experimental modules, but we should treat them as actually experimental. If they are not under active development or consideration for API changes, then they are not experimental and they should stop being so. I can’t imagine saying that the batch validation API being added that we do want to experiment with that and seeing once it’s there can we integrate it into Bitcoin Core or are there changes that would be informed by users of it? That’s a good reason to keep something experimental.
With the release process, this is getting easier because we can say we don’t guarantee API stability for those experimental modules. You can pin those at your own risk. The autotools argument is that you can’t know if a library or distribution has that model or not. The dynamic library argument is, if you think of this as a library being installed system-wide, you can compile it with the Schnorr module or without it and then you have something that needs that?
What’s the argument against just having an experimental branch instead of a module? If we pull stuff into Bitcoin Core and there’s a commit not on the main branch…. strictly speaking, this has been an argument in the past that because of overlap between development in Bitcoin Core and libsecp, it’s not unreasonable for Bitcoin Core to use an experimental API because first of all it pins versions and others can do that too. Second of all, it’s the same people. The experimental branch needs to get rebased all the time which kind of sucks. But honestly, not that often. It’s also not an answer to the dynamic library problem. You still have the problem of… if it’s not in the main branch, then it’s not part of the library. That’s a different thing. That’s no different from the user’s perspective of it being experimental and off-by-default and not expected to be in the mainline compiled versions. It depends on what distributions do. With other packages, there are bug reports from a distribution saying recompile with these flags and then that would be a fight. It would be reasonable for us to say that if you are using experimental modules as a user, then you need to compile as a static library. So then distributors should turn on every feature, unless marked as experimental. We’ve been saying don’t distribute this library, and they have been distributing it anyway. Well, we haven’t really been saying anything in the first place.
Action items: more review. PRs need to be cleared out. Experimental modules maybe add additional ones like MuSig. I think the release process PR adds documentation around experimental modules. Any change to an experimental module is a patch. The release process will mitigate a lot of these problems so maybe it’s to the point where we don’t need to care about that. I guess the expectation is that everyting non-experimental becomes by-default-on, except for recovery. Things that have APIs that are not expected to change will become non-experimental.
Sidechannels
There’s this recent CPU boosting/throttling, and then also leading into.. Hertzbleed. Every attack needs a good name. Then another one is context randomization which has a high cost. Those two sidechannels would be good to talk about.
There’s a module used in key generation and signing and computing public nonces this is where it’s used. What I considered here is an attacker model.. first of all, this is a very interesting operation to protect because it’s the most expensive in key generation and then signing. If you are a sidechannel attacker, the longer the computation it takes and the more resources it takes then the more opportunity you have as an attacker. It makes sense to focus on expensive operations first.
Say an attacker observes the point multiplication of n * G for many many times with the same n value. If I compute n * G once, then if the attacker can already extract n then we have lost anyway, so we assume this is about repeated point multiplications. The sidechannel attacker models generally require a nuanced where it’s a nuanced attacker that is all powerful and can read your memory but you have to make some assumptions about the attacker but not make the attacker too weak. These are somewhat arbitrary bounds.
There are a few things already in the code that provide protection against sidechannel attacks for ECmultchan. One is synthetic nonces which is what we have in Schnorr. This is really helpful because what we do here is randomize the secret scalar itself. Whenever there is a, when in ECDSA we use deterministic nonces which are a good idea for deriving from the secret key and message so your security doesn’t rely on having good randomness at signing time, at least in traditional security terms. This is nonce reuse protection. The reason why you are worried about nonce reuse is because of bad randomness and with deterministic nonces you don’t need to worry about that.
What we can do additionally- so the problem with this is that, if the attacker for some reason has a signing oracle which means it can ask your code to sign things.. if I ask you to sign the same message a million times then you will use the same nonce a million times and it can observe the same nonce a million times which is not great for sidechannel protection. In Schnorr, we derive the nonce using the message, the key, and then some also some randomness. So if the randomness is broken then you’re back to deterministic nonces, but if you do have additional randomness then you have additional protection. It never gets worse than deterministic nonces. It could also be a counter, not necessarily randomness, depending on the attacker model. Some non-repeating value at least. The secret scalar and the secret nonce will be randomized. If I ask for a signature on the same message a million different times, I will get a million different nonces and signatures.
Mixing in the CPU cycle could be useful, depending on the attacker model. There’s a difference between hardware fault injection attacker versus others. The instruction counter is like a counter, you could use that. You could use PRNG, you could use a timestamp, etc.
There was a PR for using the synthetic nonces but it doesn’t do that.
Passing randomness into the nonce generation function doesn’t achieve that? It actually does. You can pass with the n vector.
So we do this for Schnorr because the idea came up when we were working on bip340. It’s not yet in the ECDSA code. That’s one observation.
Another thing that we do is have random scalar … if you compute n * G then we have a value p in the context which we generate at context creation time. The context is some object that you first need to create before you can use library functions. We have some random value p in the context and when you compute n * G what we actually compute is (n - p) * G + pG where pG is pre-computed. The randomization operation consists of subtracting a precomputed number from a scalar, do the multiplication, and then add a pre-computed point. The pG point is precomputed so we don’t need to do two multiplications every time but only once. We can use this technique for every EC mult that we’re actually doing.
With this attacker model that I consider here, if you look at this, then actually this random blinding is not that particularly useful. It uses the same blinding every time. It would be different between distinct hardware devices. Oh, I’m wrong. What I wrote in here is that it is useful, actually. The point of this is as an attacker now you see one multiplication p * G precomputation so you can’t learn p because you only see it once. Then you see the million other computations; maybe you can extract (n - p) from this but it wouldn’t help you. But there’s a random value at context creation time that you wouldn’t be able to extract. It uses randomization that you provide; secp has no randomizer itself. There’s also some other blinding trick that I won’t talk about now but it’s part of this.
After every signature, what if you throw another bit into the b value? That also relates to the context.
One caveat here is that when I had this argument, I only focused on EC mult itself. If you see a million times the scalar operation (n - p) then you can compute what p is then again we are lost. In this attacker model, my conclusion was that synthetic nonces are actually a strong defense because they randomize the scalar itself. Whenever possible, I believe you should do this. Currently it’s only used for Schnorr signatures and not for ECDSA. We have it in the ECDSA code, true, but Core doesn’t do it. But neither does Core do it for Schnorr signatures- or does it? I remember there was a PR for doing it but it was both ECDSA and Schnorr. I think it does it for ECDSA now. If it does that, then it will also do it for Schnorr. There was a PR for doing it for Schnorr. If you’re going to do that, then you should do it for everything. Checking… ECDSA does not have randomness in Core right now.
At least, I claim that you should do this. Last time I checked Core code for ECDSA, I was trying to create a PR, but there were so many things I couldn’t prove in the code. It’s not broken but I really didn’t like the code. It just took me too long to work on the changes.
The synthetic nonce trick only works if you have nonces. You can’t use this for key generation because the key is fixed. Also can’t use this for ECDH.
One question I raise in this issue is, should we actually do a similar thing also for key generation? Where we could derive a one-time p value and just do two multiplications. This doubles the cost but how expensive is key generation and how often do we generate keys? I don’t know. We almost never do key generation. What we generate is a master key and all the key generation happens through the bip32 scheme which is where, by the way, also the EC mult gen plays a role.
Also in the tweak operations we can take the tweak as randomness. They are using the tweak operations. We can take that tweak as also randomness. But the tweak is fixed? It at least can’t decrease security. I think in practice we recompute the whole thing when there’s a new private key being derived. That means you are repeating the same…. you can ask for recomputation of the same secret key many times and this is why I think, I don’t think that’s a bottleneck in Bitcoin Core so doubling that time. Doubling sounds very bad but maybe it’s worth it. But… okay, I see. Your point is that you’re computing the same conclusion multiple times and every time you’re going to compute it in a different way with a different split. The nice thing about this is that it doubles the computation time but if you have like in the synthetic nonce code if you have additional randomness or a counter available then the API of this is easy. You just need a function that takes an additional randomness and use that and the secret to derive the p value, and then you have a random p value every time. The reason why I like this is becaus eit doesn’t go into the context randomization stuff. That’s a more complicated API.
Contexts
Here’s a more simple API equestion. You could have a flag when you create the context. You could add this flag that disables it if you really know what you’re doing. No, you can’t because you need randomness for that. The way it would do this is just have another function. One function without the randomness argument, and then another one without. Unless you had an immutable context that contained an RNG.
Another easy thing would be if we could choose a context size at runtime. There are no sizes anymore, it’s all compile-time. In rust-secp, we’re still fighting each other over immutable contexts.
The idea of immutable contexts is that we have this fixed p value in the context and also p * G precomputation. There’s more things in the context still. Everything else is fixed value. No, the context has the callbacks which right now can be changed. The illegal argument and all that. There is a proposal for someone to use CPU id argument in the context. There are three kinds of context: the one you have been talking about until now, the callbacks one which I think we should delete right now… the only problem with deleting the callbacks is that it will complicate the tests because it will override the… users can put this in a mutex and it’s fine if there is contention.
Let’s first talk about the context things that are related to the sidechannels. I’d like to remove any contexts so that rust libraries won’t have to care about contexts. One thing here is that context randomization would mean that from time to time you would compute a different p value. In the attacker model I consider here, that’s not so helpful as I explained earlier because already with a fixed p we get a protection against these kinds of attackers. It doesn’t mean that we shouldn’t do it. But we should look into these other possibilities maybe first.
So the idea would be to just from time to time change the b value? I would suggest doing it every time. Doesn’t that require computing a new b * G? Well it depends on what you want to do, like addition. Once we have synthetic nonces, we may not want to do it after nonce computation but maybe only after the public key computation. If you do the doubling computation time thing, then you may not want to do it at all because it might be unnecessary. Maybe all the things we want to achieve with that are covered by other things.
Then the question is, when you want to do this, and then how do you want to do this? First of all, do we want to compute a new p value every time? Then we’re better off with my earlier suggestion. Or we could do something like, a little bit cheaper, is just add one bit of randomization with every call which could still be very useful because that means after 128 bits you’re randomized enough. After 128 calls you’re randomized enough and hopefully the attacker can’t extract from only 128 calls.
How do you add only one bit of randomness without recreating p? One possibility is that after every operation you either add a constant or substract a constant and then double. After 256 bit operations, if that 1 bit is effectively uncorrelated with what the attacker knows then the complete thing has been randomized. The problem is where do you get the bit from? The quadratic residue from the … no, you can’t do that, and also we don’t have that as a constant time operation. Well, we get a secret key in public key creation. We can hash it. We already hash it to compute a nonce. I’m saying during public key creation it could be interesting for that, where you take the secret key and hash it.
The context is mutable at the moment. The further question is if we want to do larger API changes, do we want an automatic randomization? Will the context get mutated? Will public key generation mutate the context? Right now the contract is that no functions modify the state except the creation, deletion and re-randomization of a context which explicitly modify the context. This is easy for users because it means you don’t need synchronization overhead or you don’t need to think about thread safety. One possibility is just adding variants of existing API calls that take a mutable context as an argument and then when using these functions you need to make sure you are able to use those. Another alternative is thta maybe we consider an API break where everything requires mutable contexts. You can use threadlocal. With atomics, it’s just a bit too big.
Threadlocal .. you may want to do this in rust, and in C I think we would require C11 even.. unless you use extensions, like GCC extensions. Another alternative, like from, threadlocal variables may have an overhead on some platforms way more than others. You can do this externally by having the caller have not a threadlocal but one context per thread and just hand the right context to the library. That will map very nicely in rust if you just go and feed it in a mutable variable. Rust can figure that out. Right now in rust we support nonstd right now. But there might be advantages to, even if the possibility exists of using threadlocal variables perhaps there are alternatives that would be preferred for some users.
I think pushing that to the user could be reasonable. Generic API and then tell the user one good way to do this depending on your platform is to use the threadlocal context. The difference here is, do you have a threadlocal context, or do you have in your context do you have a threadlocal variable?
Ideally I’d like to remove the context completely from the API so that there would be no context at all. That would make our lives easier. We tried to do that with the current static context except now we have a global variable. We move the precomputed tables; we have 3 last things. If we can do some kind of weird threadlocal thing… No. I don’t think we want to have something static and global. In that case, I would prefer having a context passed around.
But making the context simpler? What you could do is get rid of callbacks. There are reasons for this. CPU id is easy. We don’t even have CPU id right now. You could basically turn the current general purpose contex tinto just the ECmult context and then pass it to every ECmult call and not pass it into other calls.
Even if we keep the context object in the rust library, where does the user get it? Ideally they could just use a global variable that the library exports. If they want to make their own, that’s fine. If they are using the global variable, and they need to mutate it, then we have a problem. You don’t want to lock it for the entirety of the entire call because what if you have four threads that do secp operations all at the same time.
Imagine you would open up the inside of the context object and then what I would do is copy out the p and p * G which are small, and then I would do the expensive update to b, and then I would lock, copy and unlock. So only lock for the required amount of time, only for copying in and out of the context object. You’re fine if it updates in the middle because you just add randomness. Right now the context is just a single opaque multi-byte object. The problem is that in C locking requires p-threads, unless you use spinlocks. What if the C library exposed just enough inners to me in rust?
Wait, that’s a good idea. So we have a function where the user provides a locking mechanism. Well, that’s a callback. Yes, that’s a possibility. That’s different from exposing the … no, these would be statically linked callbacks. These are similar enough for my purposes. Okay. Would this allow us to remove the callbacks completely? Unfortunately no, it doesn’t.
Right now if I lock the entire context and it’s locked while I’m calling rerandomizer, then I’m locking the context for the entire rerandomization which is like 60 microseconds or something. But we can lock only for the copying or something. I think you’re still way better off just having threadlocal contexts. I agree, but if I don’t have threadlocal storage…. okay, I also don’t have mutexes in that case.
I think for now in rust-secp where we have landed is that if we have threadlocal storage, then we use that for the entire context object. Right now you can’t copy a context because… well right now you can’t use a statically.. there’s a clone function. We can’t from the outside clone the memory because it has pointers inside of it. The new clone function just does a memcpy. You can’t guarantee this, but you can call clone. Can we make the context non-opaque? Are we not okay with that? For future changes. That’s a question to bring up like in the low level secp that also exposes group operations and fields and stuff. Not exposing like we expose a public key.. like raw data. Right now we don’t even… we can’t commit to a fixed size. That’s the problem.
You can rerandomize the cloned context, then only lock for a moment when you copy it back. You might be able to do it with atomics. You can swap out the pointers and free the memory. If two different threads, copy the pointer, edited, and now they replace the pointer then they will both free the same one. I see what you’re saying. We could use ARCs and replace the ARKs and they would take care of garbage collection. That’s double allocation though.
If we have threadlocal, then rust-secp will use threadlocal. If not, then we will do something like this. So what do we need from the standard library? This becomes a rust discussion at this point. Is the problem solved? Do we actually need anything from upstream secp? If we don’t have threadlocals and we make the context mutable, then I don’t know what we can do. It sounds like to me, how do I solve the problem of having multiple threads mutating the same data without having access to a mutex, and the answer is you can’t. How can I synchronize across threads without synchronization primitives?
I want to revisit the callback idea. We have atomics so we have some synchronization mechanism. Atomics.. we can write our own spinlocks and other horrible things. You can have unlockable data structures with just atomics. We’re going to do something worse: we’re going to do a spinlock. It won’t spin; if it is contended at all, we just don’t rerandomize. We optimistically try to do a single iteration with a spinlock. If we get exclusive access, we rerandomize, and if we can’t then we don’t. How do you prevent something else during that time accessing it? I don’t remember. We have a way. I think this can work. It’s more complex than my description. There’s more to a spinlock than just a loop and an atomic. I forget, but we do have code.
The other suggestion is to get a context, and when you want to update it you clone it. But how do you know when to free the memory? This is really a rust-specific discussion. But if the context has compile-time size, then we could put it in static memory. Just saying. We can discuss that offline. Others have brought this question up before. For a user who is going to be pinning the library, which the rust project is, then there is in principle no reason why they can’t make assumptions about what the sizes are. You could have a function that gives you the size, but it’s not guaranteed to give you the same size every time you call it…? Let’s add a randomizer to it, yeah.
We pin the library and we even edit the C code using sed for build system. We’re not above modifying. We set out all the symbol names and apply patches, like removing the callbacks. In rust-secp there are no callbacks. We remove it. Isn’t there a config flag to remove the callbacks? You can set them at compile time. Everyone does this because the problem is that you can get an illegal callback when trying to create the context and at that point you couldn’t have set it already. That’s where our patch comes in; we don’t want it to.. to exist in the code. The reason to replace the context is…before you replace them, you need to be able to call them.
Is there any benefit or some new in principle that upstream can add a callback? Or can we probably solve stuff in rust ourselves? From the callbacks, yes. The only thing is to remove the runtime callbacks which is a separate issue. I don’t see a callback for locking and unlocking. They could be NOPs. That might be acceptable for a C library, which is how every user uses it right now. I still believe you don’t need a context, but if you do need one, …. pointer vs const pointer. Link-time executions, if there are NOPs at the end of the linking.. they are a mutable function pointer. Reasoning through that, I don’t think your LTO can… if you want function pointers, why not statically linked functions? Changing compilation is not possible for users of a system library. A lot of people expect a library that they can just link against and use. It’s not the same as in current callbacks. My assumption is that a user the only users that want to change the callbacks are users that are compiling the library and have special knowledge on what’s happening, at the moment. That’s probably true right now.
So I’m going to pass in a non-const pointer.. and if I implement lock and unlock in my own way? That’s a good question. There are a bunch of ways through which we can do this mutability stuff. One is, we add new APIs that take a mutable version. They would assume external locking. Alternatively, there could be a flag you set on context creation and this context would only ever be used in a single thread of context and you provide your own external synchronization and thus since I’m giving you a const pointer secp is allowed to modify it and this is kind of ugly and really only for backwards compatibility. I see some very concerned faces. A const pointer doesn’t mean anything. It’s basically a lint. But in principle, you can have static memory behind a static pointer and then something can cast that away. Rust is different, of course. Another solution could be, whether or not the pointer itself is context, but there could be a flag saying for anything mutable please use the callbacks. If I’m a user, I have a context object, and I call sign on it, and it will automatically re-randomize. What does this look like? I imagine it would depend on a sort of synchronization mode flag that you set on the context. There’s a whole bunch of combinations that we could come up with: one would be that for any mutable operation, the locking, you have to provide a locking and unlocking callback, things would fail if you don’t, and they would be called before any modification of the context. An interesting question of course is, we currently have APIs and most of them use a constant object and others don’t. Really the reason it’s there is to signal to the user that this one is safe to use without synchronization and the other isn’t. If the expectation remains say for the one mutable one, mainly context re-randomize, and you set this mode of oh I want external…. I guess it would call it too, even for re-randomize then. I think this is okay for the re-randomize function because it’s a weird function and you have to read the docs to know when to call it. But I would like to move to a world where there is a version of signing with automatic re-random, or again in key generation. Signing will have synthetic nonces, so you won’t care, so key generation becomes the easier one to talk about. Maybe we will have two key generation functions: one taking a constant context and the other doesn’t, just for backward compatibility. Is it the expectation that the constant one never modifies, or is it still going to modify after the locking? That’s scary because what if it’s a global static context object? The lock callback will probably return a boolean. We make an API promise saying we may modify the contexts in these functions only if we call your lock callback and it returns 1. Even though it was a constant pointer? Yes.
What platforms don’t have threadlocal? Webassembly is one example. All of the embedded RISC-V. That’s more interesting. There are no threads. The reason I’m asking is that if we could provide a function, for let’s say we have synthetic nonces and then we could give you a key generation function where you could add entropy to double the computation times but avoids all of these API discussions entirely. Say I give you a key generation function where you can add entropy, and then it would derive the p value at runtime without context at all? And then we can remove the context completely? I’m sorry. I would love that though, I think that would resolve. It’s so much more simple but it does come with a significant cost of doubling the computation time. Maybe users could decide and we just offer both.
With synthetic nonces, the only advantage of randomization is in the key generation. Yes. If we actually do synthetic nonces, then we should do this. Could we provide not more entropy but instead hash the private key and use that as randomness? In the tweak case, you can’t. Deriving the same public key multiple times will be deterministic, too. Unless we had a destruction counter or something… but that should be provided externally. I guess we could add a callback whose job is to somehow side-effect….. on ARM, you can’t read the instruction counter without a syscall. In x86, you can just call the LD run and that’s it- well, very modern x86. On very secure x86. Let’s not have that fight here. No proof of Intel. It might help on some platforms.
…. a random value isn’t… it should be ephemeral, the kind of protections on it. It’s not even secret from the attacker, we hash it together with the secret key. It’s like the meta counter in synthetic nonces. It depends on the attacker model, again. But sure. If the attacker can read your sha256 memory, then…. yes, that’s why I brought this up. There is a more advanced attacker model. Randomness is better than public randomness, and randomness is better than a counter, and a counter is a whole lot better than nothing.
I would really like to have an API where I don’t have to mutate a context.
We could have an atomic counter in secp. But that requires atomic variables. In rust we somehow for some reason have atomics. Either they have atomics or they are single-threaded.
Action items: make an API. Make two keygen APIs. And one for the public tweak functions too. Maybe add an API to generate the extra randomness and that one can do platform-specific weird things. I don’t want that inside the normal… We can do it external, but we can provide the external thing. The keygen API is the main item.
You are a user of the secp library, a library that deals with very secret information and you don’t have access to a random number generator? If we want to add a random number generator to secp, then it would need a context. We could make a platform-specific context that is global because then we also have p-threads. Nevermind, nevermind. I’m sorry. Ignore me, please.
We can close the context discussion as constant context. We can leave re-randomize in, and add documentation that says, you don’t need to use this. There’s no benefit to use this if you are using the alternate APIs. If people for some reason think mutability is easier to think about. Okay, we can now close our 2-year-old 500 comment thread. After Matt went into spinlocks, I stopped reading.
Library scope
People are free to leave. Lock the doors. What’s the scope of the scope discussion?
There is this weird situation where we have libsecp, we have libsecp256k1-zkp and then other forks of it. There’s no written rule about what goes into which library. One approximation would be, well the purpose of libsecp256k1 is that it’s under the Bitcoin Core library and maybe it only includes functionality that is also in Core. This would be wrong because it already includes ECDH. You could say, it’s right except for ECDH. Or you can say it’s going to be right in the future, or you can say it should be right and we should remove ECDH. I believe this is completely wrong. I don’t think that should be the goal of libsecp256k1. It’s a relatively well defined scope… if the main goal is to serve Bitcoin Core then we should focus on that and don’t expend resources on other things. This is how libsecp256k1 can best serve Bitcoin Core is by limiting our scope.
-zkp in general doesn’t have the kind of stability and Q&A and correctness guarantees. Even just using ECDSA signing, I wouldn’t want to use ECDSA from -zkp even though I’m the author and I know it hasn’t changed, I still won’t use it. For libsecp256k1 itself, I think ECDH is used in lightning and it’s pretty simple to maintain now. We changed the hashing API recently. No, the tweak where 1 to 2 was changed to 0 and 1. Someone figured out your whole hack wasn’t necessary.
I really think we should expose ECDH and SHA2. But I won’t start that fight here. Well, I want to import SHA2. I want secp to have a way to use the caller’s SHA256. There is an issue for that. This is a different discussion though. That discussion was about importing, not exposing.
It’s not the discussion I had in mind when I said scope. I would argue that we want to expand scope because at the end of the day MuSig2 and FROST are going to be used by the bitcoin ecosystem. This is basically all the cryptographers in the bitcoin ecosystem. If a meteor hits us in this room, Lloyd can step up I guess. libsecp256k1 is the best library in the world for secp in terms of correctness.
It’s much harder to get these kinds of correctness guarantees for MuSig2 and FROST. They are interactive protocols with a lot of moving parts. I’m not really sure MuSig2 will make its way into Bitcoin Core. I certainly hope it does make its way into Core. MuSig-DN perhaps. MuSig2 requires to securely hold state and not reuse nonces and that’s very hard to guarantee unless you already make that guarantee like in lightning.
Musig2 API wise is more complex than the things that we have. I think you agree. FROST even more so. But I don’t think we should only have simple things in the library as a mandatory criterion to distinguish. If they are going to be implemented anywhere, and we think we have the expertise to give the best possible review available in the ecosystem, then why wouldn’t we include it in the scope of the library? Not just the best possible review, but also the best possible underlying functions. People could fork it. It is more ambitious, I agree, and there are more risks involved.
MuSig is hard for Bitcoin Core to do because you cannot guarantee to a user that nonces won’t be reused. Why not? Because if your system state is cloned at the wrong time, then it will reuse the nonce. That’s a new assumption in Bitcoin Core. I don’t know. I see this argument but I think we also shouldn’t forget that the point of having MuSig is that it actually gives you more security because you can do multisignatures. If you don’t re-compute nonces, and you’re dropping all the state if something goes wrong in any way, but you don’t know if something goes wrong, right?
The reason why you’re saying MuSig in Bitcoin Core may not make sense is because it’s dangerous for Core on state. Yes, but it’s dangerous for everyone except for lightning because they already have this assumption. It’s still dangerous for them. But are you saying nobody should use MuSig? Another question would be is Core willing to add lightning? Should people not assuming lightning’s assumptions, should they use MuSig? Probably not. No. So they should stick with multisignatures, tapscript and SIGADD? Perhaps.
There’s potentially safe ways to use MuSig if people know how to use it correctly in certain contexts. His point is that there is no such way that exists right now. The argument here is that you’re running MuSig in a virtual machine which gets revived and snapshotted in two places. The state between those two might be literally indistinguishable. This is a forking lemma. The signatures are forgeable if you can’t forge them this way. That’s what we prove. But, there is an obvious not perfect protection but, the best anyone could do is get really good system randomness before they call. Make the time window as small as possible. There’s mitigations. It is more important to be aware of this problem than to use it as a- to jump to don’t do it at all.
In MuSig, you need uncorruptible unreplayable state. A problem appears if someone does round 1 with you, and then… there’s a way to extract your private key. If you manage to end up in a situation where a VM gets snapshotted after the first round and then gets restored on two machines and the attacking co-signer manages to interact with both of these restored systems then they will be able to extract the key. You don’t have control of the time window between round 1 and round 2.
If you assume your own machine is not malicious, then you could write code that says after a few seconds we’ll destroy the nonces and redo round 1. It doesn’t solve the problem though. In practice, if you assume clocks are consistent in VMs which is usually true that might save you. You can go and determine the clock. Why would you choose as a co-signer another co-signer that is willing to run on such an unsafe model of operation? You should not trust those people, right?
We should not have pre-computed nonces in Bitcoin Core. And in libsecp256k1. Possibly. Why? Pre-processing… adding the message as an argument to create the nonces. It is only defense in depth. You need randomness anyway. The point is not saving. Saving, yes that’s bad. I think we have got sidetracked by the security of MuSig.
Let’s say it was not a security issue with MuSig and there was a secure way to use it that we’re comfortable with, but it wouldn’t be going into Bitcoin Core, would it make sense to put it into libsecp256k1 instead of -zkp? I say yes because it is clear it will become an important part of the ecosystem, apart from something better getting adopted and invented in short notice. But we could also remove MuSig from the library in the future. We once upon a time removed the Schnorr signature implementation. The original before MuSig just adding the points and the signatures, that was a long time ago. We were all young.
There are a few ideas for how people think about libsecp256k1. On the one side there is the thinking that it should only serve Bitcoin Core. Another side is that it should serve the broader bitcoin ecosystem of course with some restrictions on scope. Not every possible feature, of course, because we need to develop it and maintain it. But we would like it to be the best reviewed library. If everyone comes with their feature request, then we won’t be able to maintain the quality that we already have. There should be some consensus among contributors that this is a feature that will be helpful for the ecosystem, for example. On the other extreme, it’s every module that people are PRing should be added. There’s a lot in between, like, on the extreme that it only serves Bitcoin Core then we don’t have to promise any API stability as long as Bitcoin Core gives us the right API.
I’ve often wanted to use internals which I think is impossible. Like for efficient protocols for my own work. Not related. It’s a different discussion but it’s certainly relate.d If there was an easier way to fork it, then some of this discussion wouldn’t matter, or have internals exposed. Fork with bindings to rust for the internals of libsecp256k1, that’s on my list. If the maintainers don’t want it in libsecp256k1, then being able to build on libsecp256k1 would be nice. The only option right now is forking. But if you want modules from multiple forks, then you need this rebasing stuff, so maybe you have a proposal for exposing internals as an experimental module?
How would you feel about the ability to compile another library from the same source code with some trickery to make sure you could link both at the same time, which exposes internals only? This idea has been brought up before. Another idea was to split it up into two layers with a low-level library and then a higher-level library but this runs into obvious issues. I don’t think we want to write everything high-level library as a function of a lower-level library because it incurs additional development cost.
His proposal is to add an internals module, marked experimental, that exposes the internals. Everyone linking the library expecting it to be there would be unfortunate. Having a second library would be nice, because then -zkp can use that other library. You incur a cost still, converting to serializable formats on every step in and out. If you have to marshal stuff across a boundary to make a runtime, I agree there’s a cost… or inline-ability of a field operation. Do you want to expose a field operation that takes a fraction of a nanosecond?
One concern I have with just exposing the low-level stuff, is say you want to implement something like MuSig, it would be annoying to not be able to use Schnorr verification functions for example. You can link both libraries at the same time too, in that proposal, though. You need to know when to call normalize and it’s not obvious. You would be totally on your own. Same if you fork. A sane low-level interface would not expose normalization and it would do it for you. But that’s a question: how low do you go? If you go as low as having normalization there then you really should just be copying the source code into your own thing. The cost of a function call is going to be worst than normalization.
For the internals library you wouldn’t have to expose much; scalars and group operations. Even with the overhead of losing inlineing and stuff, you can do high-performance stuff with Jacobian coordinates and call EC multgen. That’s the level that Simplicity uses I think. You need field operations if you want ECDSA. Shamir secret sharing you can do over scalars, though. Even if you expose field operations, if you were okay with the function call overhead and normalization overhead per call, which you might be because we don’t do many raw field operations. Even for bulletproofs, all of our heavy work is the ECmult stuff. We’d get so much of a benefit from.. we wouldn’t get a lot more benefit from being able to inline field operations versus the benefit we already get from having Jacobian points and being able to call ECmult.
The reason I suggested a separate library is more psychological more than anything else. I’m worried about exposing that in the same library and people having the misguided expectation that this is as good to use. “If I link with libsecp then I know what I’m doing”… can’t you just call the module call “I know what I’m doing”. But I think if we call it internals-unstable or something? Or something like dangerous-internals or something. Or words just like “unstable”. Or just discouraging words. Or “internals” should also be discouraging. You’d have to use both the libraries not just the internals one.
Before you use this library, then you need to call it with the exact version string or something. What are you going to do if it’s wrong? Just call it with a correct string version for it. I want you internals version X, and if you’re not, then die. Distributions can’t package it, though. Nature always finds a way though! They patched openssl randomness out. That’s what debian did. This breaks valgrind, let’s just remove randomness. Who needs it?
Can I please get back to scope? You could imagine we could agree on a proposal that says yes we want stuff that is probably significantly relevant for the bitcoin ecosystem according to us the people who have to do the work. Would it make sense to PR such a thing into the repository? I don’t know how much it helps if we say okay we decide on a case-by-case basis. But that’s always the case. If we have a policy, it helps future decisions. It could also give minimum requirements. Before you write it, you should read the policy.
There’s some stuff going on with silent payments. I don’t know how much of it is fleshed out. It looks like it needs this x-only ECDH which has a very old outdated pull request to libsecp. Given the apparent interest in silent payment addresses, I don’t think it’s unreasonable for us to have a look. That’s the sort of level of thing.
For somebody who is trying to decide, maybe I want this in secp or maybe it should live somewhere else, having some document where I can go look and see here are the kinds of things that usually go into secp and here’s the process for who to talk to and what the steps are. If it isn’t the right place, what do I do instead? Actions speak louder than words. The fact that we haven’t had new modules apart from Schnorr sig should set an expectation on its own regardless of whether people read this document or not.
Why did you PR MuSig into -zkp? Because it is easier to experiment and iterate there? The experimental modules in secp are really not experimental. The experimental modules in libsecp are only experimental in terms of the API is the way I think about it not in terms of security. The -zkp experimental modules, like remember the bulletproofs PR that nobody read for benchmarking the paper and stuff, that was deployed in grin. We should be aware of people doing that. So it’s not experimental now; someone is using it in production.
I had a pull request to libsecp/rust for grin that improves their performance by 80%. It’s been open for 3 years. They don’t care.
In addition to silent payments, what about adaptor signatures? I agree they are a big part of the ecosystem but it’s increasingly niche and away from the bounds of peer-reviewed cryptography. I don’t know if discreet log contracts would be appropriate either. A good way to get a feel would be to have more examples. A part of this is us primarily the maintainers but also reviewers and contributors getting a feel of what everyone’s tolerance and expectations are. There is a fact that libsecp was not well maintained for a long time. It has improved in recent years. I’m at fault for this. This has resulted in us not having a release, for example, and unclear expectations of the library, some things not moving forward. We can improve upon this.
It would be helpful to have a clear specification of any scheme before it can be included in libsecp256k1. What should that specification look like? Can it be a 20 line comment explaining? Does it have to be hac-spec? x-only ECDH you can perfectly well specify in a few lines… My point only was that this raises the bar a little for what we consider. It’s a reasonable requirement. It’s good too because what we don’t want is someone saying oh, you know, I need some variant of ECDH for whatever reason and I implemented it here’s a module. The only specification of the scheme is what is implemented there. At least we have the callback for hashing the coordinates so it’s generic… But there’s no spec, yes. Agree. So according to what I’m saying, I guess we shouldn’t accept ECDH in its current state. It is effectively- we invented an ECDH scheme and implemented it and it’s written down nowhere, and it impacted a lot of libraries. A lot of libraries support this now. Together with this, here we propose an ECDH scheme that is secp-compatible and here is an implementation different- oh everyone adopts the one implementation that exists and by this ad-hoc defines a standard, I don’t think libsecp256k1 should be the venue through which standards get adopted.
We probably also only want provable things. Like tweaking and stuff. That’s a good element to review of a scheme. Well, should we accept ECDSA? It’s proven. It depends on which assumptions. Confidence and security is a requirement for getting into libsecp256k1 and provable security is a very helpful component of that.
Should there be a suggestion to reach out to the maintainers and ask if this is something they are interested in before assuming that something will get merged in if written? That’s generally recommendable not just in libsecp256k1. Maybe if we have a written policy we could include a mention that hey before writing 2000 lines of code then perhaps reach out and talk with the maintainers. If we produce such a document, would it get review? If the document is a CONTRIBUTING.md file, that would be pretty good. Also a nice starting point for coding conventions.
Action item: a CONTRIBUTING.md file. Will we have to re-evaluate where MuSig belongs? Or does this need to be discussed later? The sentiment in the room is that probably MuSig2 should belong to libsecp256k1. There’s also a lot of people asking when is MuSig2 getting into libsecp256k1 so the library is de facto used in the ecosystem not just for Bitcoin Core. It’s a reality.
The CONTRIBUTING.md file should roughly say that the scope is the modules that are likely to be relevant in the bitcoin ecosystem that have some kind of specification or security proof and where we have some confidence in the security of the protocol and implementation. Maybe other requirements that we can add.
FROST might belong in that in the future. Conditional on a specification and confidence, given those I don’t see why not. If people just have a cool idea they want to play with, there’s a good chance they can PR it into -zkp. Blockstream has to decide if they want to keep maintaining -zkp, well I wouldn’t say we really maintain it. At least in -zkp we don’t have obligations to the bitcoin community there to be releasing well-vetted code.