Push-based consensus decoding

[Kixunil]

I just realized push-based consensus decoding could solve a bunch of issues:

• Work with APIs that don't enable pull-based decoding
• Enables trivial async deserialization
• Potentially enable allocation-free decoding (this is somewhat orthogonal but I guess good to think about together)
• Reduce the complexity of no-std feature more problematic than anticipated #758 to just having a simple generic Write trait

Design draft (owned decoding only):

pub trait Decodable {
    type Decoder: Decoder<Item = Self>;
    
    /// Decodes `Self` by reading from a buffered reader.
    #[cfg(any(feature = "std", feature = "core"))]
    fn from_reader<R: BufRead>(mut reader: R) -> Result<Self, IoError<Self::Error>> {
        let mut deserializer = Self::Decoder::default();
        while let Ok(buf) = reader.fill_buf()? {
            if buf.is_empty() {
                break;
            }
            let consumed = deserializer.put_bytes(buf).map_err(IoError::Decode)?;
            reader.consume(consumed);
            if consumed < buf.len() {
                 break;
            }
        }
        deserializer.end().map_err(Into::into)
    }

    /// Decodes `Self` from given slice containing *full* data.
    ///
    /// The slice must **not** be partial - use `Decoder` API to handle partial slices.
    /// Returns the number of bytes consumed as the second field of the tuple on success.
    fn from_slice(bytes: &[u8]) -> Result<(Self::Item, usize), DecodeError<Self::Error> {
        let mut decoder = Self::Decoder::default();
        let consumed = decoder.put_bytes(bytes).map_err(DecodeError::Decode)?;
        let item = decoder.end()?;
        Ok((item, consumed))
    }
}

pub trait Decoder: Default {
    type Item;
    type Error; // perhaps we should require our own error trait?

    /// Add these bytes into deserializer state.
    ///
    /// Returns the number of consumed bytes on success, error if data was corrupted.
    /// If the returned number is less than `buf.len()` then this decoder finished decoding and `end()` should be called.
    /// It will no longer accept any bytes.
    ///
    /// ## Panics
    ///
    /// The function should panic if `bytes` is empty.
    fn put_bytes(&mut self, bytes: &[u8]) -> Result<usize, Self::Error>;

    /// Finishes decoding the item.
    ///
    /// Returns decoded item or `UnexpectedEndError` if decoding didn't finish.
    fn end(self) -> Result<Self::Item, UnexpectedEndError>;
}

// not entirely correct macro, just to give you an idea
macro_rules! fixed_size_decodable {
    ($type:ty, $decoder:ident, $len:expr, $conversion_method:ident) => {
        pub struct $decoder {
            // could be MaybeUninit in the future, this should be well-contained
            // or model it with an enum
            buf: [u8; $len],
            len: usize,
        }

        impl $crate::Decoder for $decoder {
            fn put_bytes(&mut self, bytes: &[u8]) -> Result<usize, Self::Error> {
               let dst = &mut self.buf[self.len..];
               let to_copy = dst.len().min(bytes.len());
               dst[..to_copy].copy_from_slice(&bytes[..to_copy]);
               self.len += to_copy;
               Ok(to_copy)
            }

            fn end(self) -> Result<Self, UnexpectedEndError> {
                if self.len == $len {
                    Ok($type::$conversion_method(self.buf))
                } else {
                    Err(UnexpectedEndError::new(self.len, $len))
                }
            }
        }
    }
}

fixed_size_decodable!(u32, U32Decoder, 4, from_be_bytes);

I also envision MinLenDecodable and ExactLenDecodable traits to simplify decoding for some types where they'd only have to implement conversions from byte arrays.

[dpc]

So this one is done, when put_bytes returns 0? And then you can call end?

Should it be pub trait Decoder : Write to reuse all the io::Write compat code?

[Kixunil]

Yes, 0 means done because it's definitely less than buf.len() - I just declared passing empty buf a bug in the caller. I definitely don't want to depend on io::Write - not only does it re-introduce dependency on std which I wanted to avoid, it has different semantics that can't be reasonably mapped. Write has no concept of "end writing but everything is OK"

[apoelstra]

I'm definitely interested in improving no_std compatibility, and somewhat interested in making async easier. I don't fully understand though what problems we're having and how this proposal resolves it, nor do I underrstand what you mean by "working with APIs that don't support pull-based decoding".

I also can't tell, in your example code, where any actual decoding is happening :)

[Kixunil]

no_std

The main no_std issue is that io::Error is not available in core and that implies no io::{Read, Write}. There's another problem that annoys me about std::io though: we have a bunch of foo.consensus_encode(&mut hash_engine).expect("hash engines don't error") sprinkled in the code (the message is even kinda wrong because Encodable implementations could produce io::Error even though they shouldn't).

There's an obvious solution for write:

pub trait Write {
    type Error;

    fn write(&mut self) -> Result<usize, Self::Error>;
}

pub trait Encodable {
    fn consensus_encode<W: Write>(&self, writer: W) -> Result<(), W::Error>;
}

(In practice I'd prefer write to have write_all semantics.)

We can have an adapter for std::io::Write. Infallible writers such as Vec<u8> or hash engines just set type Error = Infallible;

From glance Read impl looks equally easy. However since Read was stabilized in std Rust evolved to have MaybeUninit and the Read trait can't work with it. Simultaneously, I've read about people complaining that zeroing-out buffers seriously affect their performance. Ideally we would have a better API. A naive implementation would need Read to be unsafe (to implement) and probably introduce a custom out type to allow passing &mut [u8].

It's getting tricky at this point, I myself found several soundness issues related to MaybeUninit in various crates, including one very popular and well-maintained and one author of which is very skilled in unsafe Rust as far as I know. Even if it can be done correctly, I would rather try to bypass or at least simplify unsafe somehow without trashing performance.

async

The main problem here is that we don't have all the required bytes buffered and we can't simply wait for the next batch - that would be blocking. We must save the decoding state when there's not enough bytes and continue decoding later when they become available. That's pretty much exactly what my proposal does. We could have a trait similar to futures_io::AsyncbufRead but I'd rather not deal with the complexity of pins and contexts.

Completion-based decoding

Most things in rust have readiness-based (what I originally called pull-based) reading: the Read, Iterator, Future. However other languages tend to use callbacks - you get the bytes from external source that you can't control. If one tried to bridge Rust with other language this would spill into Rust and spawning a thread to wait for data sent over a channel is not great. It's not just other languages though e.g. the io-uring kernel API is completion based (really cool stuff, TL;DR: uses a ring buffer shared between kernel and user space to copy the bytes and thus reduce the number of syscalls if data is arriving fast). tokio-uring does some trickery with owned buffers to support Futures but I imagine one could probably avoid it with a completion-based API

Allocation-free API

Sometimes one wants wants to just scan consensus-encoded data without random access and thus shouldn't need to do multiple allocations - e.g. this is the case in electrs where we would prefer to just hash the data and not allocate vecs/scripts. Discalimer: I'm not sure if this would significantly help electrs indexing/querying speed but it could be interesting. For this we would need a very different API but I'm trying to think ahead to see if there's anything that could be shared.

I didn't flesh this one out completely but I'm thinking something like:

// Some of the traits may be unneeded and some should be auto-implemented - didn't resolve entirely how
pub trait DecodableBorrowed<'de> {
    type Error;
    fn decode_slice(bytes: &'de [u8]) -> Result<Self, Self::Error>;
}

impl<'de> DecodableBorrowed<'de> for &'de Script { /* ... */ } // unsized Script

// For `Cow`s so that you only allocate if you have to - if the borrowed data didn't come in one piece
pub trait BorrowingDecoder<'de> {
    type Item: DecodableBorrowed<'de>;
    fn put_borrowed_bytes(&mut self, bytes: &'de [u8]) -> Result<&'de [u8], Self::Error>;
    fn end(self) -> Self::Item;
}

impl<'de> BorrowingDecoder<'de> for CowScriptDecoder<'de> { /* ... */ }

pub trait Decodable /*Owned*/ : for<'de> DecodableBorrowed {
    fn put_bytes(bytes: &[u8]) -> Result<&[u8], Self::Error> {
        self.put_borrowed_bytes(bytes)
    }
}

[Kixunil]

For decoding example I've added an incomplete macro that implements fixed-size decoding, so hopefully it's more understandable.

[apoelstra]

Very interesting, thanks for writing all this up! It's starting to come together in my head.

It would be really nice to have an allocation-free API, but that does seem like a difficult goal.

[Kixunil]

I'm thinking maybe we should do this for encoding too.

trait IntoEncoder<'a>: IsRef<'a> where <Self::Encoder as Iterator>::Item: AsRef<[u8]> {
    type Encoder: Iterator;
    fn into_consensus_encoder(self) -> Self::Encoder;
    fn reserve_suggestion(self) -> usize {
        0
    }
    // other methods related to computation of reserve suggestion
}

mod sealed {
    pub trait IsRef<'a> {}
    impl<'a, T> IsRef<'a> for &'a T {}
}

// Workaround lack of GAT
trait Encodable: for<'a> &'a Self: IntoEncoder<'a> {
    fn consensus_encoder<'a>(&'a self) -> <Self as IntoEncoder<'a>::Encoder> {
        self.into_consensus_encoder()
    }

    #[cfg(feature = "bitcoin_hashes")]
    fn hash_consensus_bytes<H: bitcoin_hashes::Hash>(&self) -> H {
        let mut engine = H::Engine::default();
        for chunk in self.consensus_encoder() {
            engine.input(chunk.as_ref());
        }
        H::from_engine(engine)
    }

    #[cfg(feature = "std")]
    fn consensus_encode<W: std::io::Write>(&self, writer: &mut W) -> std::io::Result<usize> {
        let mut bytes_written = 0;
        for chunk in self.consensus_encoder() {
            let chunk = chunk.as_ref();
            writer.writ_all(chunk)?;
            bytes_written += chunk.len();
        }
        Ok(bytes_written)
    }

    #[cfg(feature = "alloc")]
    fn collect_consensus_bytes(&self) -> Vec<u8> {
        let mut vec = Vec::with_capacity(self.reserve_suggestion());
        for chunk in self.consensus_encoder() {
            vec.extend_from_slice(chunk.as_ref());
        }
        vec
    }
}

Advantages:

• Supports async
• Proves there are no spurious errors
• bitcoin_hashes not depending on bitcoin-consensus-encoding looks better to me

Disadvantages:

• More complicated to implement - need to track the state in a struct
• Needs a workaround to bypass GAT unless we want to have Iterator<Item=u8> which would be likely slow.