Deterministic CBOR (dCBOR) Presentation

TRANSCRIPT: This is a excerpt of the dCBOR Presentation from a meeting of the Gordian Development Community held on March 1, 2023. The archive of this presentation is available as a YouTube Video, an MP3 Audio and the Slides PDF are available on GitHub. See our meetings directory for a complete list of meetings.)

ABSTRACT: In this presentation, Wolf McNally from Blockchain Commons provides a comprehensive introduction to deterministic CBOR and libraries created to support it. These dCBOR libraries provide a solid foundation for creating unambiguous and easily verifiable CBOR-encoded data, making them ideal for use in many cryptographic applications.

dCBOR is a subset of CBOR, a data serialization format that is particularly useful for cryptographic applications. The goal of dCBOR is to ensure that CBOR-encoded data is unambiguous and can be easily verified, making it ideal for use in applications such as digital signatures and other digital proofs.

The Blockchain Commons dCBOR libraries have been created in Swift and Rust, and are designed to be compatible with each other. The libraries provide protocols and traits that allow developers to create CBOR-friendly structures that are easy to read and write. The libraries are also strict about what is compliant with the core deterministic encoding requirements, making it hard to write non-compliant dCBOR and an error to read non-compliant dCBOR.

The presentation discusses some of the specific features of dCBOR, such as the encoding of numeric values, which uses the shortest possible serialization to ensure that there is only one way to encode a value. And careful encoding of maps, which are key-value pairs, must be encoded in a canonical order, and how the dCBOR libraries provide a special purpose map structure that keeps key-value pairs in a canonical sorted order.

The presentation ends demonstrating a dCBOR command-line diagnostic tool that leverages the dCBOR libraries, and allows developers to view and validate CBOR-encoded data. The tool can report validation warnings and throw errors if certain kinds of violations of validation occur, such as data running out before it can be deserialized or misordered map keys, or developers can also define their own errors if they wish.

I'm Wolf McNally , I'm the lead researcher for Blockchain Commons, and in this video I'm going to talk about not just CBOR, but deterministic CBOR, and explain why we actually chose to create a couple of implementations that we hope will kind of set the stage for other people creating additional implementations for other languages.

So, we chose CBOR out of quite a variety of contenders for our layer where we're doing encoding and serialization of binary structures. Because CBOR is binary, because it's concise, it encodes short structures very short. It doesn't take a lot of room. It's self-describing. It's very good in constrained environments like embedded systems and resource constraints, systems with resource constraints. It's platform and language agnostic. standardized via the IETF RFC and it's deterministic and we're gonna be talking a lot about that particular aspect of this video. We have another video where we've talked about why we chose CBOR.

Now we're going to talk about how we're handling dealing with the determinism. So our specification for Gordian envelope which is currently an IETF draft says to be considered a well-formed envelope a sequence of bytes must be well formed to determine a deterministic CBOR according to RFC 8949. So we're going to talk a little bit about the spec, what it says, and then how we're dealing with that.

So what's the point of determinism? Because I've said that several times. Well, first of all, it's to eliminate choices for how to serialize particular data. Why is that good? Well, we want the API to enforce these kinds of standards rather than have to give developers a lot of choices. Because when developers make choices, then that often brings up problems with interoperability. So we like the API to enforce these standards as much as possible.

Where it's not possible-- and there are a few edge cases where it's not as easy to do, then developers need to be aware that they must specify how to serialize and how to validate onto deserializing. The goal being that multiple agents who are serializing the same data should automatically achieve consensus on the exact form of that data. And this is important, again, when you're trying to compare two data structures. Are they the same? Well, it could be the same data semantically, but encoded differently. So we want to avoid that problem entirely. And CBOR takes us almost all the way there. And then just a little bit of extra effort brings us the rest of the way.

All right, so what does the actual spec for CBOR say? The spec is RFC 8949, and section 4.2 specifically deals with deterministic encoded CBOR. So here's the-- I'll just read this verbatim:

Some protocols (which is things built on CBOR), may want encoders to only emit CBOR in a particular deterministic format. Those protocols might also have the decoders check that their input is in that deterministic format when reading it back in. Those protocols are free to define what they mean by a deterministic format.

My hackle start to rise at language like that. It's like, you shouldn't be free to determine these things. Continuing, and what encoders and decoders are expected to do. This section defines a set of restrictions. Okay, that's good. That can serve as the base for such a deterministic format.

Okay, so now let's look at their restrictions. So that was verbatim, this is a summary. Section 421, core deterministic encoding requirements. So, variable-length integers must be as short as possible. So integers in CBOR can be up to 64 bits, but if it only takes you one byte to encode it, you use one byte, you must, or it's badly formed.

Floating point values must use the shortest form that preserves the value. There's actually three sizes of floating point values, 16, 32, and 64 bits that CBOR supports. Indefinite length arrays and maps must not be used. If you've studied CBOR, then you know that most things give you a length or number of items and then followed by those items, so you know how long the structures are going to be, or at least how many items to count.

Indefinite length arrays is a feature of CBOR that's primarily aimed at streaming services. For example, if you're a video streamer, you don't know how many frames you're going to get, so it can't give you a number up front. So there's a subset of CBOR which supports those, but that is not allowed when you're trying to encode deterministically.

And finally, map keys, and a map is a dictionary, so it's key value pairs, must be sorted in byte-wise lexicographic order of their deterministic encodings. We'll talk a little bit more about what that means, but it's fairly straightforward. And you encode the key, and then you use the actual bytes of that CBOR encoded key as the alphabetization key, lexicographic key, for how you sort them when you serialize and how you expect them to be sorted when you deserialize.

So the spec goes on to a section 4.22, additional deterministic encoding considerations. These are things that can't be necessarily controlled in the API, but must be considered by developers. So protocols must specify the circumstances under which a data item must or must not be tagged.

So CBOR has a very useful way of extending its self-describing nature with adding what they call CBOR tags, which are integers which identify semantically the data that follows. And so, you know, some things are self-evident from context, from position, what they are, or what their semantics are. Other times you want to actually include a tag. So, but you can't just have the option.

Again, the idea is removing options from developers so they know what to do. Protocols allow use of big nums, tags two and three, must specify whether values less than two to 64, must use regular integer encodings. Now, we're not even currently supporting this at the moment, but if we were to add support for big nums, then this is a requirement there as well.

And protocols allowing the use of floating point numbers, which we do, must decide how to encode values like negative zero, which is, you know, this zero with a sign bit on, NaN and signaling NaN, subnormal values. So if you've ever studied binary floating point, you know that there's certain kinds of semantically equivalent encodings of the same floating point number. And again, that gives a kind of a choice to developers. There's usually one canonical way of doing it, but there isn't always. So you need to decide, if you're gonna use floating point, you need to decide how you're gonna do it. And we do give some guidance in our API for this.

I'll come to that momentarily. So what do we say as Blockchain Commons? So we have, first of all, we believe that deterministic encoding is essential for cryptographic smart documents like Gordian Envelope. Other certain standards like JSON-LD and so on, they have to go through a whole other canonicalization steps to transform JSON documents to a form that can be encoded and then, for example, signed, whereas we want to bake that in from the very start.

So all of our existing CBOR specs, and there's quite a few of them, dealing with things like keys and derivation paths and various kinds of things, we've been writing those for several years now, and they're already deterministic and coding compliant. So they fit right into this. And we believe that being opinionated is good because we want to determine what best practices are, determine what will serve many developers needs and then promulgate those opinions. But we also feel that enforcing opinionated best practices at the software or API level is even better.

So we believe that the implementations I'm gonna show you, hopefully are good exemplars of that. So before we decided to do this, we decided to look around and see how many existing CBOR implementations directly support deterministic encoding as a core value, because it's really kind of an optional part of the spec. And for example, all the implementations out there, if you say, encode the keys in this dictionary in this order, it just says fine. Whatever order you want to put them in is fine. But that's not fine if you want a deterministic encoding. There has to be a canonical order of the keys in a map. So we looked around, and how many did we find? Well, actually none found.

So we decided that we would go ahead and create our own. So now we built two of them. And we decided to start with dCBOR Swift, which is this is the obviously because the iOS mobile environment is very popular and also because I'm a huge Apple fan, but I'm very comfortable and very productive with Swift. So I often do things first in Swift, but Rust is one of the other, most upcoming systems programming languages and used by widely the crypto community.

So we felt these were the first two obvious targets for this. So we've created these very compatible libraries in Swift and Rust, and those are available now. You can use those QR codes to get right to them. And of course, there'll be links in the chat and in the description of the video if you're watching the video.

So what are our goals for dCBOR? What are we trying to accomplish by our implementations here? First of all, we want to make it easy to write and read deterministic CBOR or dCBOR that complies with that section 4.21 that I read you, the core deterministic encoding requirements. We want to be strict about what is written in red.

In the HTML world, there's be strict in what you write and lean in what you read. Well, that doesn't work so well for the cryptographic environments. We want to be strict about both, which basically means if you write something out that's not canonical, it won't be successfully read it, and we want to be upfront about that. So we want to make it hard to write non-compliant DCBOR, and make an error to read non-compliant DCBOR.

So we also want to facilitate as much as possible, the considerations in section 4.22, the additional deterministic encoding considerations. So I'll talk about a couple of the ways we've done that here too.

So our actual implementations provide protocols, as they're called in Swift, or traits as they're called in Rust, to make structures CBOR-friendly. So you basically can create your own structures, conform to these protocols or implement these traits, and be cCBOR compatible. So the CBOR codable conformance adds serialization and deserialization to any type.

Many fundamental built-in types on both targets, both Swift and Rust, we've basically our libraries conform them to these things. So integers, floating point values, strings, byte strings, arrays, Booleans, and dates all have conformances to dCBOR. Second, we have another protocol called CBOR Tag Decodable. Remember I mentioned tags earlier, that you can also declare a tag that's always written on serialization and expected on de-serialization. But other than that, it becomes transparent. You just say, here's a type and it encodes it, and then decodes it and expects that tag every time.

We haven't actually made any attempts to make dCBOR compatible with the Codable Protocol in Swift, or the Serde serialization framework in Rust, these are kind of the standard serialization formats. I've worked extensively with both. And I realized that in this case, because CBOR is actually very different and our dCBOR even more so, this is a lot of work with little benefits I could perceive. A lot of sharp edge and corner cases to deal with.

So we decided to say, okay, we're gonna make this very solid, just do it the best way for CBOR. But if you feel like the codable conformance or Serde compatibility is very important. We welcome PRs. And of course, this is again, this is where I want to hear the community feedback. If you feel like there's very good use cases and very good arguments to be made that we should actually be implementing this from day one, let me know.

OK, so I want to get down to a couple of specifics here. For example, encoding of numeric values, because integers floating point, we use a lot of those. And there should be only one way to encode a value. So all encoded numeric values use the shortest possible serialization. And this is specified by the RFC.

But we go a little bit beyond that in our dCBOR implementations. So as I mentioned before, there's four different sizes of integers, even down to one byte. So numbers like under, I think, under 23 in CBOR get encoded as a single byte. Floating point values, there's half width of 32-bit floats and 64-bit double precision. And that floating points with no fractional part, in other words, can be rounded to integers without any loss of accuracy, are serialized as integers if possible. So even if you had a floating point number 24 and 24.0, it will still serialize it as integer 24. This also means that certain ambiguous numbers, like 0.0 floating point, negative 0.0 floating point, and 0 integer are all serialized as integer 0, exactly the same way. So that removes choices. And so after deserialization, any numeric value can be extracted as a floating point value.

So when you deserialize in dCBOR, you get back this structure called cbor. It's basically an enumerated type, and it can contain-- it's nested, so it can contain other cbor objects. And so you parse this to extract values from it. And so when you reach a particular point, you can say extract this value as a floating point value. And if it's a numeric value, it will just give it back to you. It doesn't matter whether it was encoded as an integer or a floating point value.

However, attempting to extract an integer from a numeric value with a fractional part that was serialized as floating point and has a fractional part is an error. And that's to make sure that you can't hurt yourself by losing precision when you're extracting data. So also attempting to deserialize a CBOR stream with any numeric values not in their canonical shortest form is an error because it's not well-formed dCBOR. So there are certain things when it comes to floating point numbers like NAN versus signaling NAN or subnormal values, which are numbers extremely close to zero that floating point supports. We're not currently worrying about things like that. If they turn out to be an issue, please let us know. Generally speaking, if you're just using, for example, dates that are down to millisecond accuracy or whatever, and you're using a floating point number to model that, that's not a problem, because those won't ever fall into those ranges.

So maps, again, key value pairs. Normally, many key value pairs are encoded using methods like hash maps and so on, where the value-- where the order of the keys are not known in advance. So it's very important that when you encode maps for DCBOR that they be in a canonical order. In fact, the RFC says map keys must be sorted in byte-wise lexicographic order of their deterministic encoding. I explained what that means earlier.

So our dCBOR libraries provide a special purpose map structure that keeps key value pairs always in canonical sorted order as they are inserted or removed. So it's incremental in that sense. So it also provides iteration through key value pairs in canonical order. And in many ways they behave like normal dictionaries or maps, but they are primarily intended for use during the serialization and deserialization of CBOR. And if you try to deserialize an out of order map from a CBOR stream, if the keys are out of order, it throws an error.

So also, as an engineer, I try to design libraries I want to use. I want to have robust diagnostic tools. So our CBOR, once you've read in dCBOR, you want to view it, we have methods, for example, diagnostic and hex, which dump the actual CBOR diagnostic notation or hex dumps, but they're annotated. So you can actually provide them with a list of known tags. So if you associate your CBOR tags with current semantics, you can say, well, this is what they are, and it shows them to you. For example, we define 304 to be a crypto derivation key path for the bit 32. And here you see the CBOR diagnostic notation of that. It's a tag with a map inside it with a single key value pair. The key is one. The value is a CBOR array of derivation steps, which the Boolean there is whether it's hardened or not. So this is how that looks in hexadecimal. It's the exact same thing. This is using the hex method.

But again, it shows you what tag you're looking at, and it shows you the literal binary encoding of that. So we actually-- when you are decoding or extracting-- so decoding is when you're taking the CBOR binary stream and decoding it to the CBOR structure that you can parse in your code. Or extracting, that means taking values out of that. We can perform validation errors, or we can throw errors if there's certain kinds of violations of validation.

So for example, if the data runs out before it manages to deserialize it all, you get an underrun error, see more bad header values, non-canonical int or float, invalid UTF-8 strings, unused data at the end of the stream. So if too much data is encoded, if you successfully decoded it all, but there's still data left, that's some kind of encoding error, so we flag that.

Misordered map keys, as I mentioned before, duplicate map keys aren't allowed, Integers that are out of range, this is when you try to extract something. For example, let's say you try to extract an eight-bit integer, but the value itself was encoded as a 32-bit integer, it won't fit into a U8, so you get this error. If you try to extract, say, a string as an integer, you get the wrong type. Wrong tag. If you say extract a particular tag value, and you saw it should be this tag, and it's a different tag, you get an error. Or invalid format, which is a generic error that layers we build on top of it will often throw if they're decoding a particular structure and it's not what they expect. You of course can define your own errors if you wish that have more valuable semantics to you.

So that's the presentation on determining cBOR and this is where to contact us.