I am going to try and recap the history of encoders/decoders (I am calling these coders) and encodables/decodables (and these codables) in rust-bitcoin. An encoder pushes bytes into a sink of some sort. This could be an I/O sink, like a TCP stream, but there are also more side effect-y use cases like a checksum or length calculations. Decoders pull bytes from a source. While the operations are kind of symmetrical, decoders are usually working with un-trusted input which can make side effect calculations risky. A slight tweak in requirements which keeps the paths from looking exactly the same.
rust-bitcoin used to have traits for encoders and decoders.
pub trait Encoder {
fn emit_u64(&mut self, v: u64) -> Result<(), Error>;
fn emit_u32(&mut self, v: u32) -> Result<(), Error>;
fn emit_u16(&mut self, v: u16) -> Result<(), Error>;
fn emit_u8(&mut self, v: u8) -> Result<(), Error>;
fn emit_i64(&mut self, v: i64) -> Result<(), Error>;
fn emit_i32(&mut self, v: i32) -> Result<(), Error>;
fn emit_i16(&mut self, v: i16) -> Result<(), Error>;
fn emit_i8(&mut self, v: i8) -> Result<(), Error>;
fn emit_bool(&mut self, v: bool) -> Result<(), Error>;
fn emit_slice(&mut self, v: &[u8]) -> Result<(), Error>;
}
pub trait Decoder {
fn read_u64(&mut self) -> Result<u64, Error>;
fn read_u32(&mut self) -> Result<u32, Error>;
fn read_u16(&mut self) -> Result<u16, Error>;
fn read_u8(&mut self) -> Result<u8, Error>;
fn read_i64(&mut self) -> Result<i64, Error>;
fn read_i32(&mut self) -> Result<i32, Error>;
fn read_i16(&mut self) -> Result<i16, Error>;
fn read_i8(&mut self) -> Result<i8, Error>;
fn read_bool(&mut self) -> Result<bool, Error>;
fn read_slice(&mut self, slice: &mut [u8]) -> Result<(), Error>;
}
rust-bitcoin’s old Encoder/Decoder traits, could be implemented with I/O or something like a length counter.
Coders are per-I/O, while codeables are per-type. The codable traits take a coder as an input.
impl<S: Encoder> Encodable<S> for Transaction {
fn consensus_encode(&self, s: &mut S) -> Result<(), Error>;
}
Define a Transaction type’s encoding for any Encoder.
I think this is pretty slick and a great separation of complexity. But after attempting to make the bip324 library sans-io, I see a big short coming. The coder traits are tied to blocking I/O. Separate AsyncEncoder/AsyncDecoder traits would need to be defined, and double codable implementations.
Something I noticed here too is that the Encoder functions are essentially encodables for the root primitives of the bitcoin protocol. All the other types (e.g. transactions, blocks) boil down to writing out a linear sequence of these types. Which I think kinda shows how we got to the rust-bitcoin pattern of today. The Encoder and Decoder traits were morphed into WriteExt and ReadExt. These extend I/O traits. Instead of encodables taking an Encoder, they take a straight up I/O interface where they write bytes. No structure at all. This is fine, all the structure lives in the encodable impls, but it does tie the encodables to the standard I/O.
rust-bitcoin mitigated the standard library tie by introducing their own io module with a bridge (aka wrapper) around standard I/O sources and sinks. I don’t think this is much different than having the old Encoder/Decoder traits wrap a std I/O implementation. Just some shifts in responsibilities, although there might be some subtle caller ergonomic effects I am missing. Or perhaps it changes how difficult it would be to manage a blanket implementation across the standard I/O traits? Coherence rules seem like tricky business. I think adding blanket impls retroactively is generally a bad call because it could conflict with a user’s existing impls. Whereas a bridge/wrapper, FromStd<T>, is always a distinct type.
#[cfg(feature = "std")]
impl<T: std::io::Write> crate::Write for T {
fn write(&mut self, buf: &[u8]) -> crate::Result<usize> {
std::io::Write::write(self, buf).map_err(Into::into)
}
fn write_all(&mut self, buf: &[u8]) -> crate::Result<()> {
std::io::Write::write_all(self, buf).map_err(Into::into)
}
fn flush(&mut self) -> crate::Result<()> {
std::io::Write::flush(self).map_err(Into::into)
}
}
#[cfg(feature = "std")]
impl<T: std::io::Read> crate::Read for T {
fn read(&mut self, buf: &mut [u8]) -> crate::Result<usize> {
std::io::Read::read(self, buf).map_err(Into::into)
}
}
Blanket impl the bitcoin::io across the std:io traits so the caller doesn’t have to care about the types…but a blanket impl should probably always be released with a trait to avoid coherence hell.
Another thing to think about is how a blanket impl restricts a caller from implementing something themselves (not that this would happen much in bitcoin land where there is a limited number of types which don’t change often.
// bitcoin-io has blanket impl
impl<T: std::io::Write> bitcoin_io::Write for T { ... }
struct MyWriter;
impl std::io::Write for MyWriter { ... } // std compatibility.
impl bitcoin_io::Write for MyWriter { ... } // Attempt to add custom bitcoin behavior.
Rust won’t allow this since the blanket impl and custom impl conflict.
In any case, things are still tied to blocking I/O. To be sans-io (blocking or async agnostic), the codables need to work against byte slice based interfaces. Instead of pushing bytes into the encoder or pulling bytes from a decoder, they are driven by what is passed into them, sometimes described as “completion-based decoding”. The decoder pushes the decodable and some driver needs to push the decoder. It seems awkward for an I/O driver to have to push data to a decoder, which pushes it to a decodable, and the driver listens on that end. Instead of having a decoder push root types to a decodable, the I/O driver could just push bytes directly to the decodable itself. We would still have a driver per I/O type, but now have shared logic in the codeables (vs. double impl in the split trait case).
Would rust-bitcoin migrate to this pattern?
Minimum Viable Push Decode
There is an effort to bring a sans-io coder interface to rust-bitcoin using the push decode library, but it hasn’t landed yet. I am wondering if the underlying library is perhaps just a tad too complicated, I have struggled to wrap my head completely around its interface.
For any library that could bring sans-io coder support to bitcoin, I believe it should strike a balance between two complexity points. For the maximum, it does not need to a full on grammar parsing library. The library should take advantage of the simple, linear, streaming nature of bitcoin messages. No backtrack or look-ahead features need to be supported. We are not parsing a complex grammar, but rather a fairly predictable structure. For the minimum complexity though, bitcoin types are nested (e.g. blocks contain transactions which contain inputs which contain IDs…) and although the structure is predictable, the amount of content is not. For example, a transaction can contain one or hundreds of inputs.
I believe the push_decode library fits this niche well, compared to something like nom which is massively complex to handle a grammar. push_decode is designed just for streaming binary formats. It has combinators leveraging the type system to link together coders which handles the nested requirement of bitcoin types. I believe this is preferable to something a little lighter weight like deku or binrw which use derive statements. Feels like those wouldn’t handle conditionals and composability very well.
push_decode requires defining coders for each bitcoin type, much like the codables of today, but these are separate structs not traits on the type. The separate struct allows bytes to be held onto between multiple calls, which is likely to happen as the coder state machine needs to advance to the end. This could technically still just be a trait on the type, but then the coding becomes all or nothing based on the passed in bytes, and I have a hunch that gets painful as you compose coders.
I think coders need to be defined for the root bitcoin types, maybe the set in the old rust-bitcoin traits? But then composability can be used for the higher level types. And then rust-bitcoin can ditch its confusing codable-to-I/O connection, and instead offer wrappers (e.g. blocking with std::io) around the sans-io coders.
But there are a few spots in push_decode that I am not sure if the cost to benefit checks out. I want to either convince myself that they do, or drop them to make the library easier to digest.
- Pre-built utf8 decoders.
- Sub decoders.
- The
Futureimplementation for async. - The exported macros.
- The use of
eitherdependency.
Pre-built UTF-8 Decoders
The library has a pre-built utf8_string decoder. It looks hyper optimized for a utf8, which is used in all sorts of domains. But not in bitcoin. I wonder if this could be moved into a push_decode_utf8 library to minimize the surface area of the base library.
Sub Decoders
The Decoder trait has two “sub” methods, sub_decode and wrap_sub_decode, which I think are supposed to be used in complex composed scenarios, but it is not clear to me how they are better than just using the combinators.
There are two main combinators.
chain// Run two decoders back to back, return both values.then// Run first decoder and pass its value to the second.
chain is probably a little simpler, easy to reason about. then is required if downstream decoders need a previous decoding (variable length), might also help on memory usage.
The combinators build a nice big coder state machine for you. So why use the sub methods? I am not sure. They wrap up some boilerplate (about 4 lines), but are not even used in the library itself. Might just be easier to drop them and point users to the combinators?
The Future Impl
The heart of push_decode is crating the sans-io state machines for the coders. But it also provides little connectors between specific I/O drivers and the sans-io coders. These do the busywork of pushing and pulling bytes between the I/O and the coders.
/// Synchronously decodes a value from the given reader using a custom decoder.
#[cfg(feature = "std")]
pub fn decode_sync_with<D: Decoder, R: std::io::BufRead + ?Sized>(reader: &mut R, mut decoder: D) -> Result<D::Value, ReadError<D::Error>> {
loop {
let buf = match reader.fill_buf() {
Ok(buf) => buf,
Err(error) if error.kind() == std::io::ErrorKind::Interrupted => continue,
Err(error) => return Err(ReadError::Read(error)),
};
if buf.is_empty() {
break decoder.end().map_err(ReadError::Decode);
}
let num = decoder.bytes_received(buf).map_err(ReadError::Decode)?;
let buf_len = buf.len();
reader.consume(num);
if num < buf_len {
break decoder.end().map_err(ReadError::Decode);
}
}
}
The connection between the synchronous std io library and a sans-io decoder.
This includes three different connections for async runtimes. This isn’t super surprising since there is no async I/O interface in the standard library yet. What is a little interesting though is that there is a Future implementation in push_decode. Given that the coders are sans-io, I would have assumed each async connector would use the “leaf” future implementation of which ever runtime to pull/push bytes from I/O and pass them to the coder. Implementing leaf futures in rust is still pretty hairy looking code, and you have to look directly at the Pin‘ing!
The Future impl does allow logic to be share between the three supported async runtime connectors. The connectors are simply wrappers around this future. I think the future could be dropped and each runtime would have some duplicate logic like the following.
#[cfg(feature = "tokio")]
pub async fn decode_tokio_with<D: Decoder, R: tokio::io::AsyncBufRead>(
mut reader: R,
mut decoder: D
) -> Result<D::Value, ReadError<D::Error>> {
use tokio::io::AsyncBufReadExt;
loop {
let buf = reader.fill_buf().await.map_err(ReadError::Read)?;
if buf.is_empty() {
return decoder.end().map_err(ReadError::Decode);
}
let consumed = decoder.bytes_received(buf).map_err(ReadError::Decode)?;
reader.consume(consumed);
if consumed < buf.len() {
return decoder.end().map_err(ReadError::Decode);
}
}
}
A tokio specific connector with no Future under the hood.
The future impl does bring some consistency though, since the higher level async/await I/O APIs can be a little different between runtimes. The runtimes might yield control at slightly different points even if the code looks about the same. But given how few runtimes there are in the rust ecosystem at the moment, and how this introduces a dependency on pin_project, I wonder if it should just be dropped in favor of the simpler async/await syntax?
Macros
push_decode exports two macros, mapped_decoder and delegate. For the record, #[macro_export] is an attribute allows a macro defined with the high level macro_rules! to be exported from a crate. It is auto-exported to the root of the crate too. Since macros are expanded at a different point in compilation, they have different visibility rules, they don’t use pub.
Anyways, despite the different naming conventions, these kinda serve similar purposes. mapped_decoder is a 1:1 of an underlying decoder whose output then gets mapped. delegate is on the encoder side, where a single field of the struct represents the encoding. Maybe a better name would be forward_encoder? In any case, that macro implementation is gnarly. I think the goal was for the input to look like normal rust, but sure makes looking at the impl hard. Maybe it could dialed back and support most of the use cases still?
Either
The either crate is used in push_decode with the std feature is enabled. It is the one dependency I am not sure exactly if required. It is pretty straight forward, it provides a type Either<L, R> that represents one of two possible values. I think there is some debate on if this belongs in the type system which is why this isn’t in the std library. push_decode is using it to essential create types on the fly when composing coders. This allows you to chain together coders with different error types (like version parsing errors or script parsing errors) while preserving the ability to handle each error type specifically.
let decoder = U32Decoder::new() // Error: IntError
.chain(ScriptDecoder::new()) // Error: Either<IntError, ScriptError>
.chain(AmountDecoder::new()); // Error: Either<Either<IntError, ScriptError>, AmountError>
// Usage requires nested pattern matching.
match result {
Err(Either::Left(Either::Left(int_error))) => { /* handle int error */ },
Err(Either::Left(Either::Right(script_error))) => { /* handle script error */ },
Err(Either::Right(amount_error)) => { /* handle amount error */ },
Ok(((version, script), amount)) => { /* success */ },
}
Error types of chain’d decoders.
This is probably fine, but maybe some docs are needed for callers to help with the potentially gnarly match statements. Or could it just be implemented in push_decode itself?
What Happened Last Time?
A while back, pull request #2184 was opened to bring push_decode into rust-bitcoin, but it never left the draft state. Why did it get stuck?
Macros
A part that I still am wrapping my head around is all the macros. There are at least three layers. And as soon as a macro reaches like three lines my mind breaks. In the new consensus-encode crate, things get busy with the Encode and Decode traits. I believe the goal of these traits is to implement them directly on the type being encoded or decoded. There is an associated type for the actual coder for the type. The encoding side gets especially tricky though with things like the gat_like macro. Really getting hairy here. But I think the desire was for Encode to expose an encoder method on a type which pops out an Encoder struct for it. Ideally, it is referencing the type itself instead of copying all the data (which could be large for like a block). But this would require a lifetime on the associated type.
trait Encode {
type Encoder: push_decode::Encoder; // But this can't capture lifetimes!
fn encoder(&self) -> Self::Encoder; // encoder() borrows from &self, but how long?
}
impl Encode for Transaction {
type Encoder = TransactionEncoder<???>; // What lifetime goes here?
fn encoder(&self) -> Self::Encoder {
TransactionEncoder::new(self) // self has some lifetime, but trait can't express it
}
}
Life without GATs.
The Decode side looks like how you want it. Helper methods on a type which depend on the type’s decoder. The decoders naturally accumulate state and produce owned input, no referencing. The Encode would like to reference its type’s data though. Anyway to accomplish this without so many macros? Can Encode be made simpler even without GAT support (1.65…so close)?
Here are some helpful methods on the Encode trait which justifies it. They create the type’s encoder with self.encoder() and ideally there is not a lot of data copying happening here. We want to add some encoding convenience methods to all types that can produce an encoder for themselves. In other words, we want types to be able to call .consensus_encode_to_vec() on themselves, which requires them to produce an appropriate encoder. The difficulty is that some encoders take a reference to the type they are encoding. By the way, the current Encodable trait avoids this completely since it is implemented directly on the type, not a separate coder struct.
/// Counts precisely how many bytes the value produces.
fn count_consensus_bytes(&self) -> usize {
let mut encoder = self.encoder();
let mut total = 0;
while !encoder.encoded_chunk().is_empty() {
total += encoder.encoded_chunk().len();
if !encoder.next() {
break;
}
}
total
}
/// Consensus-encodes the value and stores the bytes in a vec.
#[cfg(feature = "alloc")]
fn consensus_encode_to_vec(&self) -> alloc::vec::Vec<u8> {
let mut buf = alloc::vec::Vec::with_capacity(self.reserve_suggestion(20).0);
self.encoder().write_to_vec(&mut buf);
buf
}
Why you want to implement Encode on a type, easy access to these.
What if these were just defined as free functions for now, and when rust 1.65 is adopted, a GAT is introduced to tie them to a type.
pub trait Encode {
type Encoder<'a>: Encoder + 'a where Self: 'a;
fn encoder(&self) -> Self::Encoder<'_>;
fn consensus_encode_to_vec(&self) -> Vec<u8> {
consensus_encode_to_vec(self.encoder())
}
fn count_consensus_bytes(&self) -> usize {
count_consensus_bytes(self.encoder())
}
fn consensus_encode<W: Write>(&self, writer: &mut W) -> io::Result<()> {
consensus_encode(self.encoder(), writer)
}
}
Tie the free functions to a type with a GAT.
Maybe a blanket impl on Encoder would be nice?
pub trait EncoderExt: Encoder + Sized {
fn consensus_encode_to_vec(self) -> Vec<u8> {
consensus_encode_to_vec(self)
}
fn count_consensus_bytes(self) -> usize {
count_consensus_bytes(self)
}
fn consensus_encode<W: Write>(self, writer: &mut W) -> io::Result<()> {
consensus_encode(self, writer)
}
}
impl<T: Encoder> EncoderExt for T {}
let bytes = tx.encoder().consensus_encode_to_vec();
Blanket impl for types which implement Encoder.
But since consensus_encode is implemented per-type anyway, each implementation can just use its own encoder directly for the first pass.
impl Encodable for MyType {
fn consensus_encode(...) -> ... {
MyTypeEncoder::new(self).write_to(writer)
}
}
No GAT needed!
Transaction Decoder
The other beast is the TransactionDecoder which uses manual sub decoders instead of composing decoders. In bitcoin, the transaction type is probably the most complex consensus encoding. Like, Script is complex, but it is just a byte array for consensus encoding. A PSBT is complex, but not stored on chain. Transactions though are structurally complex due to their legacy versions being on chain forever. The type of the decoder chain is probably going to be complicated, so I think this justifies the kickout to manual sub decoders. But is just naming the type of the decoder chain that is painful? If that is the case, can it just be hidden from the caller?
pub struct TransactionDecoder(/* complex hidden type */);
impl TransactionDecoder {
/// Creates a new transaction decoder.
pub fn new() -> Self {
TransactionDecoder(
version_decoder()
.then(|version| inputs_decoder())
.then(|(version, inputs)| {
if inputs.is_empty() {
Either::Left(segwit_branch(version))
} else {
Either::Right(legacy_branch(version, inputs))
}
})
.then(|tx_data| assemble_transaction(tx_data))
)
}
}
impl Decoder for TransactionDecoder {
type Value = Transaction;
type Error = TransactionDecodeError;
fn decode_chunk(&mut self, bytes: &mut &[u8]) -> Result<(), Self::Error> {
self.0.decode_chunk(bytes)
}
fn end(self) -> Result<Self::Value, Self::Error> {
self.0.end()
}
}
Hide the complex chain in a newtype.
The Goal
Ideally, consensus encodable types have the Encode and Decode traits applied which link to sans-io coders, plus have some useful coder enabled methods. This is preferable to traits tied to specific IO libraries. And once adopted, rust-bitcoin can drop its troublesome io module.
However, the Encoder trait requires GAT support (rust 1.65) to be useful. So as a first step, just sans-io encoder and decoder structs are defined for each consensus type. This isn’t wasted work, it just lacks the ergonomics of the Encode and Decode traits for the caller. The existing Encodable and Decodable traits, which are tied to the io module, can be refactored to use the new sans-io coders under the hood. So the caller interface doesn’t change for now, unless they reach for the coders themselves.
Compared to the first attempt to pull in push_decode, I think macros should be avoided and instead just offer less support for now (e.g. do not attempt a gat_like macro, just wait for GAT support). I also think the sub decoder interface should be avoided in favor of just the composable chain/then interface. This might get hairy with the Transaction type, but that should be the high water mark of complexity.