checksum: introduce `PrintImpl` object that can compute various code properties

apoelstra commented 5 months ago

This PR does a couple things:

Bumps the MSRV to 1.56.1 to match rust-bitcoin (and get us const generics which are useful for defining extension fields) as well as cleaning up a couple warnings.
Introduces the GF1024 field, a simple polynomial type, the Chein root-finding algorithm, and a couple other misc algorithms that will be useful for error correction. (All this is internal and not reflected in the public API.)
Introduces the GF32768 field which will be needed for error correction of the descriptor checksum.
To demonstrate this new functionality, adds an object to the API which can produce the impl Checksum block for codes which can be corrected using a quadratic or cubic field extension. This will hopefully provide some context for people not super familiar with BCH code about where these magic numbers come from.

We also add unit tests that produce the parameters for codex32 and the descriptor checksum. A later PR will introduce more parameters which will be needed for error correction.

apoelstra commented 5 months ago

I updated the API files inline with each commit so it's clear what commits change the API in what ways. Let me know if it'd be better to pull these out into their own commit(s).

apoelstra commented 5 months ago

This is ready for review. I extended it a bit to support the descriptor checksum but I'll stop extending it and do future changes in a later PR.

tcharding commented 5 months ago

Meant to mention before, I found the API files very useful when reviewing.

apoelstra commented 5 months ago

Addressed all comments.

apoelstra commented 5 months ago

@clarkmoody what are next steps for this PR?

tcharding commented 4 months ago

I rekon we can merge this, its been open for a while now. @clarkmoody speak now or forever hold your peace :)

apoelstra commented 4 months ago

It's a nontrivial change and unlike rust-bitcoin, I don't have a mandate to steer this crate (and actually even Github won't let me because you're not an approved approver), so I think we've gotta wait for Clark.

tcharding commented 4 months ago

Fair.

tcharding commented 2 months ago

Hi @clarkmoody, is there anything we can do to make reviewing this easier for you? I got a message out of band from FROST devs chasing error correction. I realize this is a massive PR and not at all easy to review.

cc @nickfarrow

clarkmoody commented 2 months ago

This is some real Big Brain stuff! I've pointed out some minor things here and there.

I apologize for going AWOL for so long.

apoelstra commented 2 months ago

Let me open a PR to get CI working then I'll rebase this and address your comments. In the last couple months there has been a bunch of breakage in check-api and even rustc itself.

apoelstra commented 2 months ago

Rebased and addressed all nits.

tcharding commented 2 months ago

Thanks @clarkmoody, way to go.

tcharding commented 2 months ago

I'm not going to re-review this, I don't think a shallow re-ack from me adds much value.

rust-bitcoin / rust-bech32

checksum: introduce `PrintImpl` object that can compute various code properties #180