Introduce and use a new `compact_size` module by tcharding · Pull Request #3259 · rust-bitcoin/rust-bitcoin

tcharding · 2024-08-28T02:40:26Z

We would like to move the witness module to primitives but there is a bunch of usage of VarInt.

Introduce a module that does the encoding and decoding instead, note that while the functionality is internal decoding returns an error which may one day end up in the public API. So put the module in primitives and make it public.

Adds the module to primitives, adds a public MAX_ENCODABLE_SIZE variable that is commented with an issue link.

#3264

apoelstra · 2024-08-28T03:12:13Z

I don't think we should have a type for this. We decided elsewhere that it should be a method as part of the encoding/decoding traits.

And interesting re MAX_SIZE. Yes, we should start enforcing this. It might even simplify some things here.

tcharding · 2024-08-28T03:33:16Z

I don't think we should have a type for this. We decided elsewhere that it should be a method as part of the encoding/decoding traits.

We need it in Witness and I believe that was not realised when the "have functions as part of encoding/decoding" thing was discussed.

apoelstra · 2024-08-28T03:44:24Z

How is the usage in Witness different from the usage anywhere else? It looks like we always create this type ephemerally as a wrapper around an integer. It would be just as easy to use function calls.

If we are just trying to match the existing code to minimize the diff, then we shouldn't do the rename.

tcharding · 2024-08-28T03:55:58Z

Oh I follow you, the same logic but just use stand alone functions instead of creating a type. I can try that and see how it looks.

Kixunil · 2024-08-28T04:03:54Z

Exactly, the type is basically over-engineering. I suggest putting these methods to internals:

fn encode_compact_size(num: impl ToU64) -> ArrayVec<u8> { /* ... */ }
fn decode_compact_size(bytes: &mut &[u8]) -> Result<u64, () /* too short */> { /* ... */ }
fn encoded_size_of_compact_size(num: impl ToU64) -> usize { /* ... */ } // technically could be `u8` but that'll likely be annoying.

Kixunil · 2024-08-28T04:05:09Z

Just make this ArrayVec in internals.

I removed this function and returned a [8u; 9].

tcharding · 2024-08-28T06:00:33Z

I had hacked up a new solution before seeing your review @Kixunil, I'm EOD today, I'll take another look tomorrow.

tcharding · 2024-08-28T21:46:42Z

Note in this PR compact_size is as required for the witness stuff, it does not include the ToU64 version of encoded_size as done in #2931. I'll do that when I get to the VarInt stuff.

tcharding · 2024-08-28T23:45:16Z

In case its not obvious, this is needed for the work on primitives to progress, please prioritize.

Kixunil · 2024-08-29T07:01:40Z

+/// assert_eq!(size, 1);
+/// assert_eq!(encoded, [0x20, 0, 0, 0, 0, 0, 0, 0, 0]);
+/// ```
+pub fn encode(value: u64) -> ([u8; 9], usize) {


Why not ArrayVec<u8, 9>?

No used, found a bug too - so WIN.

EDIT: Now used.

Kixunil · 2024-08-29T07:03:19Z

+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum DecodeError {
+    /// Tried to decode a `CompactSize` from an empty slice.
+    Empty,


Empty is literally an instance of TooShort, we don't need it.

Ha! Conceptually yes but we don't have the expected length until we read the first byte.

(I removed Empty at one stage to find this out :)

Empty means we have less than one. Having less than one means empty.

To make Kix's point more explicit, the "expected minimum length" should be 1.

As for whether we should combine the two variants, I could go either way. I guess the fewer variants the better, especially here where we only have two variants and we could eliminate the whole enum.

"expected minimum length" should be 1.

Ah, adding "minimum" indeed solves the problem.

Also FTR we could've just wrapped the error.

I'd prefer Result<_, ()> to Option.

To imply its an error case but we don't provide a specific error?

Yes, also triggers the must_use warning.

Sorry to pile on, but I'd prefer we use a dummy error type which we mark #[non_exhaustive] so users can't construct it. This will give us the freedom to add information to the error variant in the future.

internals is unstable anyway, but I'm not opposed to it.

Kixunil · 2024-08-29T07:04:24Z

+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TooShortError {
+    initial_byte: u8,
+    expected_minimum_length: usize,


These are redundant since you can compute one from the other.

Who cares? There is no perf hit in having an extra field in an error type, right? Its more brain-dead-simple to carry the redundant info than having more byte -> length conversions.

Technically, there actually is. Size of error types causes the whole Result to be larger if it's larger than the Ok variant and this slows down Result operations downstream. We generally don't pay too much attention to this since bad errors are worse than bad performance in most cases but if we can reasonably compress the information we should. The return type of the function is u64 which makes your Result ~twice as large as it would be if it was just the value itself. However it'd be really strange if this simple function didn't get inlined which may remove the cost entirely.

And really, the information we need can fit just 4 bits (see below). But I'm not asking you to implement that madness, I'm only asking to fit it into ~u64. :)

Side note: it annoys me that ArrayVec has to use usize for length tracking even if CAP is small enough to fit u8.

4 bits because the errors that can possibly exist are only these:

The input is empty

The input encodes two-byte requirement and one of the bytes is missing

The input encodes four-byte requirement and at most four bytes are missing - four combinations

The input encodes eight-byte requirement and at most eight bytes are missing - eight combinations

Which gives us 1 + 1 + 4 + 8 == 14 combination which can be encoded by 4 bits.

Yes, it was a fun puzzle to find the true lower bound and not just any solution that fits into a byte. :)

BTW the most efficient way you can write it in Rust is to enumerate all the possibilities as enum because that also gives niche optimizations.

I didn't read Kix's crazy analysis, but definitely +1 to minimizing error type sizes where it's reasonably possible.

In miniscript we have a massive error types everywhere and it's a big problem for us. It's not so big a problem here but we shouldn't get complacent.

Cool, thanks for the explanation. TIL.

In miniscript we have a massive error types everywhere and it's a big problem for us. It's not so big a problem here but we shouldn't get complacent.

TIL about the result_large_err clippy lint, which fires on errors that are over 128 bytes, but which can be configured to fire at a lower threshold.

Kixunil · 2024-08-29T07:09:51Z

+/// let (compact, _) = compact_size::decode(&[0x20, 0xAB, 0xCD]).unwrap();
+/// assert_eq!(compact, 32);
+/// ```
+pub fn decode(slice: &[u8]) -> Result<(u64, usize), DecodeError> {


Rather than returning usize and forcing the callers to recompute it's better to take slice as &mut &[u8] and mutate it to update the start of the slice. You can then avoid a bunch of redundant code.

I'll take a look, thanks.

With fresh eyes I still don't understand what you mean, can you extrapolate please?

This signature is better:

pub fn decode(slice: &mut &[u8]) -> Result<u64, DecodeError>

Where the function updates the slice by moving start by the number of consumed bytes.

Because callers always want to update their positions in the slice, this method is more helpful and doing it manually is annoying and error-prone.

I thought that was what you might be meaning but in both callsites in this PR the caller does not update the slice.

It does, check again.

Oh you are right, the iterator does update it. The other callsite (in element_at), does not and does not have a mutable reference to it ether (called from nth). Also decode_cursor does not mutate the slice, I still rekon we should leave it as is. Thoughts?

All of them mutate the slice in the sense that they re-construct the new one in the exact same way - to start after the compact size bytes. They could as well make a mut bytes copy and mutate it. You could argue we should return (u64, &[u8]) to keep the style functional which is not terrible either, I'm just used to mutating style because of deserializers. Also I'm not sure what the borrow checker will think of it although it's likely fine.

tcharding · 2024-08-29T09:13:13Z

Thanks for the review @Kixunil , I"ll re-spin tomorrow.

tcharding · 2024-08-29T17:05:01Z

Now uses ArrayVec (uncovered a bug also), and removes the error type entirely.

tcharding · 2024-08-29T17:20:24Z

Another question: While rebasing Steven's work in #2931 on top of this I see that we do checks or non-minimal encoding when decoding a compact size slice, should we be doing that here?

Non-minimal means encoding a value that fits in a u16 using the u32 encoding.

    fn read_compact_size(&mut self) -> Result<u64, Error> {
        match self.read_u8()? {
            0xFF => {
                let x = self.read_u64()?;
                if x < 0x1_0000_0000 {
                    Err(Error::NonMinimalVarInt)
                } else {
                    Ok(x)
                }
            }
            0xFE => {
                let x = self.read_u32()?;
                if x < 0x1_0000 {
                    Err(Error::NonMinimalVarInt)
                } else {
                    Ok(x as u64)
                }
            }
            0xFD => {
                let x = self.read_u16()?;
                if x < 0xFD {
                    Err(Error::NonMinimalVarInt)
                } else {
                    Ok(x as u64)
                }
            }
            n => Ok(n as u64),
        }
    }

apoelstra · 2024-08-29T17:28:57Z

Yes. In Core these checks are done unconditionally.

Kixunil · 2024-09-03T06:31:34Z

I'd rather remove non-minimality check entirely. It doesn't really matter for Witness. Or at best it should be debug_assert.

tcharding · 2024-09-03T23:42:27Z

OMG, we are really going around in circles. I can remove the checks but please note that above we agreed that we should have them (see #3259 (comment)).

tcharding · 2024-09-03T23:47:14Z

And they are unconditionally check in Core

template<typename Stream>
uint64_t ReadCompactSize(Stream& is, bool range_check = true)
{
    uint8_t chSize = ser_readdata8(is);
    uint64_t nSizeRet = 0;
    if (chSize < 253)
    {
        nSizeRet = chSize;
    }
    else if (chSize == 253)
    {
        nSizeRet = ser_readdata16(is);
        if (nSizeRet < 253)
            throw std::ios_base::failure("non-canonical ReadCompactSize()");
    }
    else if (chSize == 254)
    {
        nSizeRet = ser_readdata32(is);
        if (nSizeRet < 0x10000u)
            throw std::ios_base::failure("non-canonical ReadCompactSize()");
    }
    else
    {
        nSizeRet = ser_readdata64(is);
        if (nSizeRet < 0x100000000ULL)
            throw std::ios_base::failure("non-canonical ReadCompactSize()");
    }
    if (range_check && nSizeRet > MAX_SIZE) {
        throw std::ios_base::failure("ReadCompactSize(): size too large");
    }
    return nSizeRet;
}

apoelstra · 2024-09-04T01:44:07Z

@tcharding sure, the checks need to pass -- but there shouldn't be any possible way for them not to pass. This is why a debug_assert would be sufficient.

tcharding · 2024-09-04T02:25:55Z

Added calls to debug_assert to assert minimal encoding. No other changes.

tcharding · 2024-09-04T02:50:47Z

Must be time for lunch, I had <= around the wrong way (should be >).

Kixunil · 2024-09-04T06:36:58Z

@tcharding we agreed to those checks because we didn't notice the functions are not taking outside inputs. Now that we've realized that it's obvious that the checks are just wasted performance. I guess this should be explicitly documented on the functions.

tcharding · 2024-09-04T09:48:00Z

Can we merge as is and follow up now? Docs and things is no bother to add later.

Kixunil · 2024-09-04T10:20:19Z

The commit message is stale.

Kixunil · 2024-09-04T10:36:26Z

Could've been ToU64 to simplify the callers.

Ha! Can't call that in const, sadly I had to make the change before I remembered why I didn't use it originally :)

const trait methods would be awesome.

I just removed the const - we will likely need to add it again later but in this PR its better as you suggest.

apoelstra · 2024-09-04T14:12:52Z

utACK b9706fca04ed1aee7bc4db91c4868ef7449000eb. This is fine for internal code.

In a later rev we should:

Call the decode method _unchecked or something to indicate that it assumes it's receiving a well-formed object
(or just fold it into ConsensusDecodable and do the checks, as we eventually intend to do)
remove the explicit panics on SIZE and just let the slice indexing panic, to reduce noise
make Witness::push and Witness::push_slice fallible if you try to push something exceeding u32's range (actually maybe we have to do this now since it's an API-breaking change)

Also +1 to Kix's comments above -- the commit message refers to primitives not internals and using ToU64 would simplify the caller.

Kixunil · 2024-09-04T17:21:13Z

remove the explicit panics on SIZE and just let the slice indexing panic, to reduce noise

That wouldn't reduce noise just make debugging harder. But enums are better anyway.

make Witness::push and Witness::push_slice fallible if you try to push something exceeding u32's range (actually maybe we have to do this now since it's an API-breaking change)

Actually it already panics for values larger than u32::MAX and it's not documented because we're storing the indices as u32 rather than usize.

actually maybe we have to do this now since it's an API-breaking change

Definitely before 1.0 release and ideally also before any other release.

We would like to move the witness module to `primitives` but there is a bunch of usage of `VarInt`. Introduce a module that does the encoding and decoding instead, this code is internal so put it in `internals`. Note we add an unused public `MAX_ENCODABLE_SIZE` variable that is commented with an issue link. Done like this because its quite important that we see to it and it makes it clear that we are not and we know about it. rust-bitcoin#3264

tcharding · 2024-09-04T23:53:05Z

The force push is:

Re-name to decode_unchecked
Use impl ToU64 for encode and encoded_size (removing const from encoded_size)

I checked the range-diff and its easy enough to review. Thanks for your patience on this one, its been trying :)

tcharding · 2024-09-08T20:36:46Z

Bump please, this guy is P-high

apoelstra

ACK d65de7c successfully ran local tests

Kixunil

ACK d65de7c

tcharding · 2024-09-09T20:39:52Z

ooooo nice, I hope your merge script has finished running by the time I'm done the school run!

apoelstra · 2024-09-10T13:27:48Z

Lol, it had finished but I forgot to type "push".

tcharding · 2024-09-10T20:24:10Z

Yesterdays rust-bitcoind-json-rpc progress was the result of this omission so its not all bad :)

github-actions Bot added C-bitcoin PRs modifying the bitcoin crate C-units PRs modifying the units crate labels Aug 28, 2024

tcharding mentioned this pull request Aug 28, 2024

Remove VarInt and use ReadExt and WriteExt trait methods instead #2931

Merged

Kixunil reviewed Aug 28, 2024

View reviewed changes

tcharding force-pushed the 08-28-compact-size branch from 1b86b5b to 8ca250d Compare August 28, 2024 05:59

github-actions Bot added C-primitives and removed C-units PRs modifying the units crate labels Aug 28, 2024

tcharding changed the title ~~Introduce and use a new CompactSize type~~ Introduce and use a new compact_size module Aug 28, 2024

tcharding force-pushed the 08-28-compact-size branch from 8ca250d to 0b20ee8 Compare August 28, 2024 20:52

github-actions Bot added C-internals PRs modifying the internals crate and removed C-primitives labels Aug 28, 2024

tcharding marked this pull request as ready for review August 28, 2024 20:53

tcharding mentioned this pull request Aug 28, 2024

Look into CompactSize MAX_SIZE #3264

Open

tcharding force-pushed the 08-28-compact-size branch from 0b20ee8 to 014ac3d Compare August 28, 2024 21:00

tcharding mentioned this pull request Aug 29, 2024

Move Witness to primitives #3269

Closed

Kixunil reviewed Aug 29, 2024

View reviewed changes

tcharding force-pushed the 08-28-compact-size branch from 014ac3d to d932736 Compare August 29, 2024 17:03

tcharding mentioned this pull request Aug 29, 2024

psbt: Encode keytype as a compact size unsigned integer #2906

Merged

tcharding force-pushed the 08-28-compact-size branch from 494d71a to ac04b1c Compare September 3, 2024 23:50

tcharding force-pushed the 08-28-compact-size branch from ac04b1c to b01a977 Compare September 4, 2024 02:25

tcharding force-pushed the 08-28-compact-size branch from b01a977 to b9706fc Compare September 4, 2024 02:50

Kixunil reviewed Sep 4, 2024

View reviewed changes

Kixunil mentioned this pull request Sep 4, 2024

Decide what to do about undocumented Witness::push panics #3302

Open

tcharding force-pushed the 08-28-compact-size branch from b9706fc to d65de7c Compare September 4, 2024 23:50

tcharding changed the title ~~Introduce and use a new compact_size module~~ priority: Introduce and use a new compact_size module Sep 9, 2024

apoelstra approved these changes Sep 9, 2024

View reviewed changes

Kixunil approved these changes Sep 9, 2024

View reviewed changes

apoelstra merged commit 060ad58 into rust-bitcoin:master Sep 10, 2024

tcharding deleted the 08-28-compact-size branch September 12, 2024 01:40

tcharding mentioned this pull request Sep 17, 2024

Consider checking/discussing error size limits #3369

Open

tcharding changed the title ~~priority: Introduce and use a new compact_size module~~ Introduce and use a new compact_size module Dec 4, 2024

tcharding mentioned this pull request Aug 6, 2025

Remove usage of term VarInt #4784

Closed

Uh oh!

Conversation

tcharding commented Aug 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

apoelstra commented Aug 28, 2024

Uh oh!

tcharding commented Aug 28, 2024

Uh oh!

apoelstra commented Aug 28, 2024

Uh oh!

tcharding commented Aug 28, 2024

Uh oh!

Kixunil commented Aug 28, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding commented Aug 28, 2024

Uh oh!

tcharding commented Aug 28, 2024

Uh oh!

tcharding commented Aug 28, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding Aug 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Kixunil Aug 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding Sep 1, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

tcharding commented Aug 28, 2024 •

edited

Loading

tcharding Aug 29, 2024 •

edited

Loading

Kixunil Aug 29, 2024 •

edited

Loading

tcharding Sep 1, 2024 •

edited

Loading

tcharding commented Aug 29, 2024 •

edited

Loading

tcharding commented Sep 3, 2024 •

edited

Loading