plans for implementing BIP 324

[stratospher]

curious to know whether there’s interest in implementing BIP 324 in rust bitcoin. starting points would be implementing FSChaCha20Poly1305(a cryptographic primitive to encrypt/decrypt the network messages) and creating bindings for elligator swift.

what do you think of FSChaCha20Poly1305 implementation as a summer of bitcoin project? i’m willing to mentor and have been helping with testing/reviewing BIP 324 in bitcoin core the past year.

[apoelstra]

I think this is a great idea for a SoB project, if you're willing and able to do the mentoring :).

It probably should live in a separate crate, at least initially, because it's a fair bit of additional complexity. We also may need to bring on a RustCrypto dependency to get chacha, at least initially, which I am loath to do. (Eventually we should be able to drop this; chacha20 is implemented in secp256k1-zkp so I assume it will find its way into libsecp eventually, and even if it doesn't, it's a conceptually very simple algorithm that we could maybe try to hand-roll.)

Alternately, it sounds like you think that implementing chacha20 is feasible for one SoB student, that sounds even better.

[stratospher]

thanks a lot! true, chacha20 sounds like a better plan for an SoB student.

[Kixunil]

Concept ACK, especially having a separate crate makes sense.

[sanket1729]

strong concept ACK. Having a separate crate makes best sense to me.

[apoelstra]

If you create a separate crate please post it here so that we can subscribe. I think a good SoB goal would be to get it into the rust-bitcoin org, which roughly means:

• It works and is of reasonably high code quality (passing cargo +nighly clippy will go a long way toward this, and I guess cargo fmt as well)
• It has a MSRV of Rust 1.56.1 or earlier, and has CI tests that check this
• It has a small dependency tree (for this we may be able to get away with only rust-secp, or a forked rust-secp). Probably this would exclude chacha20 ... although if you find a small no-dep chacha20 crate that we can reasonably review, that's probably alright.

[Kixunil]

I would also add adheres to Rust API Guidelines. Doesn't need to be 100% perfect from start but should head in that direction.

[Davidson-Souza]

Hi @stratospher, any updates on this? I'm excited to help with this.
It will be very different from the current codebase because all the p2p code holds little to no external context. With BIP-324 we need to keep track of decryption/encryption contexts. Apart from the SoB project about ChaCha20, we need to update rust-libsecp256k1 with the Elligator-Swift encoding (once upstream merges it, perhaps), code the new types and respective [de]serialization methods. I'll look into some of this. Perhaps it's good to create a repo to coordinate it?

[stratospher]

Happy to hear you're interested in this! @Adidev-KGP has started working on his SoB project in this repo and is moving towards getting it into rust-bitcoin org by end of this summer. It's still in the early stage but feel free to use the repo. I imagine you'd get much greater visibility from the rust bitcoin community for ellswift bindings in the rust-secp256k1 repo though!

[stevenroose]

BIP324 definitely sounds like something that could merit its own crate as it will depend on some new crypto stuff and perhaps some other new dependencies? If it's really just crypto, it could maybe be in rust-bitcoin IMO. I'm definitely interested in an impl for this (SoB gogogo) for the bitcoin-p2p crate I've been working on.

[Adidev-KGP]

Seeking Feedback: Introducing FSChaCha20 Implementation for Rust-BIP324 in Rust Bitcoin

I am thrilled to share my recent progress on implementing FSChaCha20 under BIP324 for Rust Bitcoin. I have successfully implemented ChaCha20 Block and utilized it to develop FSChaCha20, which efficiently avoids wasting pseudorandom bytes, as discussed in the BIP324 specification. FSChacha20 is just Chacha20 which gets rekeyed every 224 packets and it is ultimately used to encrypt the length of P2P message which is stored as 3 bytes.

Code Repository

To review my code and provide your valuable feedback, you can find the implementation in my GitHub repository: Adidev-KGP/rust-bip324#1.

Next Steps

I have made a simple/basic implementation for FSChaCha20 with tests which work based on the BIP324 specifications.
I realise there's additional maintenance burden when bringing external crates but still curious to know whether it's desirable to make the operations in the code constant time, more secure and flexbile. I have listed a few ideas below for the same.

1. Constant-Time Operations in ChaCha20 Implementation

During the development process, I encountered a concern regarding the use of wrapping_add() in the quarter_round() function within the ChaCha20 implementation. As wrapping_add() is not a constant-time operation, it is crucial to ensure all operations, including addition, are executed in constant time. After careful consideration, I have identified two potential approaches to achieve this:

1. Subtle Crate: One option is to leverage the subtle crate, which provides constant-time operations. Integrating this crate into the implementation would ensure that the quarter_round() function is performed in a constant-time manner. However, I am open to suggestions and insights from the Rust Bitcoin Community regarding the use of this crate or any alternative approaches.

2. Bitwise Operations and Conditional Masking: Alternatively, I have come across a blog post titled "Constant-Time Operations" (Link), which discusses techniques for achieving constant-time operations. By combining bitwise operations and conditional masking, we can potentially accomplish constant-time addition and other required operations. I am interested in hearing your opinions on this method and any additional suggestions you may have.

2. Leveraging const-generics for Flexibility and Reusability

Furthermore, I am considering the adoption of const-generics in the FSChaCha20 implementation to minimize the overhead of dynamic allocation. This would enable passing the key length, and nonce length as constants during runtime using const-generics. We can combine const-generics with traits to make the code more generic, extensible, and flexible, we can ensure its reusability for future implementations.

3. Memory Security

To address memory security concerns, I aim to incorporate the zeroize crate into the codebase. By zeroizing sensitive data, we can overwrite memory with zeros, preventing adversaries from extracting secrets from buffers. This approach ensures the confidentiality of the data and aligns with security best practices.

I genuinely appreciate your time and expertise in reviewing my work! Your feedback will play a vital role in refining and advancing the FSChaCha20 implementation for Rust-BIP324. Thank you for your dedication to the Rust Bitcoin Community, and I eagerly anticipate the opportunity to collaborate with you.

[sanket1729]

Anyway, I agree with the points above that we should just rewrite it in Rust for now.

Agreed. This seems to be one of the cases where we either get all the tests write or get all of them wrong.

[Davidson-Souza]

+1, won’t this algorithm be eventually replaced by chacha20 in libsecp in the future?

I hope so. We've had an implementation in secp256k1-zkp for years now. I'm a little surprised that we have elswift in libsecp but not chacha20.

I don't think this will ever make its way to libsecp, unless it's used as a PRNG for batch validation. Core keeps all its non-ecc crypto on the main repo.

This is a cool idea! I'm not sure if we can mark data uninitialized in Rust the way that we do in C, but if you're willing to explore doing this I think it'd be really great to have. (But don't try too hard ... I don't think it's necessary and I suspect that it's way more trouble than we want to deal with :)).

I did my test by exposing the API in a cdynlib and creating a simple C program that links against the Rust one. A bit ugly, but I found it easier than binding valgrind's lib for Rust.
I've added a few dummy key dependent branch throughout the code and valgrind complained about them. What do you think?

[apoelstra]

Super cool! Do you think you could wrap that up in a way that we could do it in the CI for rust-secp?

[Davidson-Souza]

I think it is possible. I made a small gist showing a simple example: https://gist.github.com/Davidson-Souza/e90fb262ed73ad6c6d8f7d74f0d87ec9

[Kixunil]

I missed the news here, reading it now:

wrapping_add() is not a constant-time operation

Source? There's no reason it wouldn't be, it's literally letting the value overflow and translates directly to a constant-time addition instruction. There's no reason to worry about it unless you have a proof that in some cases it leads to non-constant-time code.

[apoelstra]

Lol, I like it. Funny that we'll likely wind up with C-wrapped Rust-wrapped C for rust-secp.

[Adidev-KGP]

My SoB project on FSChaCha20 is done and can be found here. I would appreciate any reviews on the code to make it acceptable for rust-bitcoin. Thankyou.

[apoelstra]

Thank for letting me know! I have this on my TODO list.

[Kixunil]

Sounds like scope creep to add in libsecp256k1 and possibly rust-bitcoin. It could be a part of the P2P crate though.

[apoelstra]

@Kixunil well, the supporting code is going to live in libsecp256k1 (the C library), whose scope is "all the crypto primitives needed by Bitcoin Core" ... and then the scope of rust-secp256k1 is "all the functionality provided by libsecp256k1". So there is an argument for bringing it into rust-secp. (In general, I would like rust-secp to move toward pure-rust reimplementations of some C functionality, and I think chacha is a good candidate for this since it's short and simple and very hard to make non-constant-time even for a motivated compiler.)

[Kixunil]

libsecp256k1 (the C library), whose scope is "all the crypto primitives needed by Bitcoin Core

Sounds like it should be (re)named (to) libbitcoincrypto

[apoelstra]

Well, right now everything that it exposes (including elswift and so on) is specifically crypto on the secp256k1 curve.

[rustaceanrob]

Hi folks, as part of a Chaincode program I completed a BIP324 library (not trying to steal anyone's thunder this was completely random). I read through the discussion thus far and it sounds like there was great care taken in the design of the FSChaCha20 implementation, whereas I used a simple wrapper around ChaCha20. Understandable if we are trying build the implementation up from scratch, but I didn't go to great lengths to exclude deps. I use secp256k1, chacha20, sha2, chacha20poly1305, hkdf, and rand in my implementation.

My library exposes four unique functions that execute the handshake and a struct to encrypt and decrypt messages thereafter. All messages are expected to be a Vec<u8>, which should hopefully be suitable to use with TcpStream. I used and pass test vectors from the BIP as well as a handful of unit tests. While I don't think this should make it into the core rust-bitcoin crate, I am curious to see what everyone thinks about adding the repo to the greater rust community set of crates. The repo may be found here

In the meantime, I will fixup and fmt and enforce the MSRV stuff. On the dependency tree, perhaps I can work to remove chacha20.

Cheers!

[Kixunil]

used a BigInt library

You mean the big-int crate? I assume you need it for 256 bit integers. We have an implementation in bitcoin already and I was already thinking we could make it into a crate because secp256k1 will need it when we add pure-rust code verifying key validity. If chcha20-poly1305 needs it too it's more of a reason to do this.

I also found there's u256 crate which contains our old code - it still has Andrew's copyright notice. Makes it quite possible that we can get the crate and put our new code there.

[rustaceanrob]

Yes apologies for the loose language, I used a num-bigint crate for 256 bit math. The poly1305 function requires a modulo 2^130 - 5. The u256 would be sufficient for our implementation, happy to help in any way I can!

[rustaceanrob]

Hi, another update from our end. After looking at the C reference implementation linked in the RFC, the algorithm for Poly1305 is well defined and can be used without any BigInt generalization. By using a modulus multiplication rule, the BigInt parts of the algorithm can be reduced to simple multiplication and addition over u32 integers, described in this article if anyone is curious. I have a local implementation that seems to be working. That reduces the dependencies down to secp256k1, bitcoin_hashes, and rand.

[nyonson]

Hey all, @rustaceanrob and I cleaned up our BIP324 code and narrowed down the dependencies to just rust-bitcoin. We refactored things so the interface is no_std compliant and added alloc and std feature flags which layer on some useful functions for those environments. We also added a small proxy application which uses the library end to end which has been helpful. No rush, but might be worth another look now!

[apoelstra]

Hi all. FYI last week I was at a conference all week and am playing catch-up right now. I hope to get to this this week. It sounds from your comments like this is good to go, and we can pull it into rust-bitcoin org. But I want to poke at the source a bit, and then double-check my CONTRIBUTING.md docs to see if there's any more process I need to follow. (I think I can just BDFL it in, especially after a year+ of discussion so everybody knows about this crate, and when it's a crypto-heavy crate where other maintainers usually defer to me. But maybe there's a waiting period or something.)

[apoelstra]

Ok LGTM. I did not review the cryptography or even check that it works as a BIP324 implementation with a node.

But I did spend some time poking at the code which overall looks well-structured. I ran a bunch of off-by-default clippy lints which all passed, checked for unsafe, checked for documentation and unit tests, etc. I did find a bunch of unnecessary error variants which I filed an issue about, but that's hardly a blocking issue. I checked that the crate compiled with 1.56.1 (it does not, but I filed an issue). There's also plenty of room to improve CI. I hope that over the next couple weeks we'll have genericized our CI infrastructure enough that it'd be easy for people to copy it and get very thorough coverage.

If this were my codebase I would:

• Add SPDX license headers to every file
• Use module/mod.rs rather than module.rs
• Avoid using From impls on error types, instead preferring .map_err(Error::Variant)? which IMO is clearer

But these are all just stylistic things.

[nyonson]

Thanks @apoelstra , I'll take a look at the MSRV and error variant clean up today.

For your other points, is there a preferred license we should release this under? Should we just match rust-bitcoin? And for the module/mod.rs vs. module.rs, I am a little new to Rust so don't have a strong opinion, but read that the module.rs is a little more "grep-able". Do you think module/mod.rs just easier to read from a structure point of view?

[apoelstra]

No preferred license. We use CC0 here but actually, because CC0 has a carveout that allows patenting software, it's not as meaningfully free as I would have hoped. Apache has an explicit patent grant which ensures that anybody using the software also gets a license to any patents used by it.

Currently you are licensed MIT which is fine. I would suggest dual-licensing MIT/Apache to cover the patent gap.

Both are morally equivalent to CC-BY but more appropriate for software, and I don't think the added "freedom" granted by CC0 is worth the extra complexity.

As for module.rs being "more greppable", I have no idea what this means. My version of grep works on all files regardless of their filenames and I've never heard of one that didn't. But when you have a file called module.rs alongside a directory called module/, it breaks tab-completion for the directory which is very annoying. It also means that one of the files in your module is mysteriously not in the module directory, which is also annoying. Nobody has ever described to me a benefit of having module.rs (and Rust is full of stuff that are purely bad ideas, so its existence is not evidence that any benefits exist).

[nyonson]

I am no license expert, but from my interpretation it kinda sounds like 0BSD may be a more straight forward CC0? We will role with the dual MIT/Apache though, sounds good to me.

As for the module stuff, yea, this is coming from blog reading rather than personal experience so my bad on the vague description. By greppable, I meant that it might be easier to find things with distinct file names vs. a bunch of mod.rs files. But again, I don't have any experience with this pain point. Kinda just wish there was a single pattern!

[apoelstra]

Neat. I'll look into 0BSD. Though my feeling is that if it doesn't fix a real issue (e.g. the patent thing) it's probably not worth the hassle for me to try to relicense rust-bitcoin.

Kinda just wish there was a single pattern!

Yeah. There used to be..

[tcharding]

Re the foo/mod.rs vs foo.rs, there are arguments both ways. I personally would hate to have to work on two different code bases that use different styles that would be the worst outcome, so for me I'd prefer to use mod.rs because that's what we do elsewhere. I pity the folk that work all day on "modern" codebases that use the other style then try to read rust-bitcoin. It was probably a bad idea introducing a new contradictory method that has no clear benefit but oh well, engineers make mistakes.

[apoelstra]

Thanks for your work @Adidev-KGP -- I apologize for not reviewing your code. After a cursory review looks like it is not as complete or polished as the implementation by @nyonson and @rustaceanrob, so I am going to take the latter into the org and not your crate.

I don't mean this personally at all; it just happens that when I finally got around to digging into this issue, that there were two implementations, and one was much more complete than the other.

[apoelstra]

@rustaceanrob I have invited you to the rust-bitcoin org. I believe you need to accept the invite and then you can transfer the repository. I can't do it from my end because I don't own the repo.

This also gives you the ability to create arbitrary new repos but I request that you not do that without starting a discussion here or on the .github repo.

Cheers
Andrew

[rustaceanrob]

Thank you! We will be cleaning up those issues, as well as resolving one last API hole. Cheers!