Deterministic canonical form for CBOR/DagCBOR not implementable, prevents other representations

[msporny]

At present, the deterministic canonical form for CBOR is meant to apply to all CBOR-based formats. The rules in the specification today are as follows:

• Property names MUST be represented as text string (major type 3) and contain only UTF-8 strings.
• Undefined Values of Required Properties as defined in the Data Model that are absent from the CBOR representation SHOULD be labeled with Primitive type (major type 7) with value 23 (Undefined value).
• Property names in each CBOR map MUST be unique.
• Integer encoding MUST be as short as possible.
• The expression of lengths in CBOR major types 2 through 5 MUST be as short as possible.
• The keys in every map must be sorted lowest value to highest. Sorting is performed on the bytes of the representation of the keys. If two keys have different lengths, the shorter one sorts earlier. If two keys have the same length, the one with the lower value in (byte-wise) lexical order sorts earlier.

These rules are partially copied from RFC7049 (the CBOR specification) in the following ways:

Property names MUST be represented as text string (major type 3) and contain only UTF-8 strings. <-- this is NOT from RFC7049, text created by @jonnycrunch

Undefined Values of Required Properties as defined in the Data Model that are absent from the CBOR representation SHOULD be labeled with Primitive type (major type 7) with value 23 (Undefined value). <-- this is NOT from RFC7049, text created by @jonnycrunch

Property names in each CBOR map MUST be unique. <-- this is NOT from RFC7049, text created by @jonnycrunch

Integer encoding MUST be as short as possible. <-- this is from RFC7049, but leaves out really important details from RFC7049

The expression of lengths in CBOR major types 2 through 5 MUST be as short as possible. <-- this is from RFC7049, but leaves out really important details from RFC7049

The keys in every map must be sorted lowest value to highest. Sorting is performed on the bytes of the representation of the keys. If two keys have different lengths, the shorter one sorts earlier. If two keys have the same length, the one with the lower value in (byte-wise) lexical order sorts earlier. <-- this is from RFC7049, verbatim

The first rule prevents CBOR formats that would want use a more compact form by transforming map keys to small integers, which is common for a CBOR format.

The second rule imposes a mandate that other CBOR formats might want to avoid (for example, by dropping the value instead of preserving it as undefined).

The rest of the rules don't properly transfer the meaning of RFC 7049 by leaving out text that is important to ensure implementers can create a canonical form.

All of the rules also presume that all CBOR serializations were serialized in the same way, which is an assumption that cannot be made in the DID specification. One might go from JSON->ADM->CBOR while others may go from CBOR->ADM->CBOR -- JSON and CBOR implementations are not guaranteed to keep order when sets are used, and it is expected that many will use sets in their implementations. Therefore, a false sense of security is created that the rules above create a canonical CBOR form when that cannot be guaranteed given the rules above.

The specification shouldn't be proposing that it provides a canonical form across representations, or even one representation. The group wasn't chartered to do that work, we have not been doing that work, and we're now two weeks out from going into the Candidate Recommendation phase (so we don't have the appropriate time left to do that work).

We should mark this section at risk, in the very least. Ideally, we'd remove any mention that we guarantee any sort of deterministic canonical form from the specification. We don't want to give people that impression.

[jonnycrunch]

@cabo, I'd value your input.

My thoughts are that it is important in our spec to have a deterministically encoded representation to get consistent encoders/decoders. The group seems to think this is a daunting task and not worth the effort. I'm thinking given our spec isn't that complex and we aren't dealing with numbers, with a little bit more work we can do it and will pay off in spades down the road. ... just like all the work we put in to having an Abstract Data Model will.....( I hope!)

@cabo, I also appreciate your work with the updated CBOR #rfc8949
and perhaps the compromise is to normatively point to the Core Deterministic Encoding Requirements, which seems to satisfy everything that I was attempting to cover. Realize of course that my original contribution to this section is now >3 months and a normative encoding requirement now exists.

@msporny regarding first constraint: Property names MUST be represented as text string (major type 3) and contain only UTF-8 strings, that was to be compatible with JSON and the property constraints in the Abstract Data Model that were present at the time aka the Vanilla CBOR discussion.

[jonnycrunch]

@msporny, btw, this also leave to door open for CBOR-LD and dagCBOR to co-exist.

[cabo]

Most definitely, we wrote Section 4.2 of RFC 8949 based on what we had learned in seven years of using CBOR in a wide variety of environments. You want to point to that (Section 4.2.1 specifically), not try to rephrase it.

Re the additional rules: You can't really have a SHOULD in deterministic encoding. I don't understand what that rule is trying to do -- why not say you MUST leave out entries that would have an undefined value?

If the CBOR encoding defines some integer labels (as opposed to text string labels), and both are equivalent, I'd probably err on the side of using the shorter ones (i.e., integer). But that requires correctly curating the numeric labels: You cannot add one after the fact after you already have had a text string version, because that would cause older implementations that only know the text strings to produce different output than newer ones that know the integer labels. In SenML (RFC 8428), which also supports JSON and CBOR, we went radical about this: The set of integer labels is fixed and cannot grow; new labels are always text only.

[jonnycrunch]

@cabo, many thanks for your input, much appreciated and fine work on the RFC 8949!

SHOULD

yes, that makes sense, at the time we were having a debate about Unknown properties and how to handle them, this was a placeholder for us to finish that discussion and update it for the CBOR section.

[iherman]

The issue was discussed in a meeting on 2021-01-28

List of resolutions:

• Resolution No. 1: The DID Working Group will not define a canonical form for the Abstract Data Model.

View the transcript

2. CBOR sections

See github issue #585, #551.

See github pull request #552.

Manu Sporny: Let's talk about the CBOR section and the DagCBOR section. Jonathan, can you give an overview on those sections now?

Jonathan Holt: On our call on Tuesday, we're working on a security document. We need to have deterministic encoding of the DID document, especially if the method will be signing and having a deterministic ordering is important.
… My DID method relies on that and is on dagCBOR. The deterministic encoding of dagCBOR is really important.
… I mentioned, I'm by no means a CBOR expert, I do have a lot of reliance on deterministically encoded CBOR in our method. The challenges of writing the requirement are the RFC 7049 gives some guidance but it's up to protocols to clearly state what they mean to be canonical or deterministic. I gave some guidelines. At first I was over zealous to add every possible combination.

Jonathan Holt: #586

Jonathan Holt: Including 64-bit integers and floats, but the language that's now in the dagCBOR section, but should be in the CBOR section. So here's a new PR to fix it.
… To get us onto a fresh discussion on deterministically encoded CBOR. So we can dice out, what does that mean, is it canonical, is it deterministic, we can decide how to move forward.

Manu Sporny: Thanks for that overview, Jonathan. There are numerous concerns around deterministic canonical form for CBOR. Just so everyone is on the same page for deterministic canonical form. Typically when you digitally sign things you want to have them in a deterministic canonical form.
… There are other ways to do signing where you, for example, base64 encode anything and just sign that. The issue with that, however, is that if there are any blank space/white space/formatting changes that changes the signature. There are other technologies that use canonicalization with JSON-LD/JCS, and so on.
… When we say deterministic canonicalization form we are transforming the input in some way to ensure that the output is always the same (there's one way to express it) regardless of the input.
… With that being said, I personally don't think the group is chartered to do canonical forms and new signature formats and things of that nature. It could be argued that the group is supposed to do things of that nature. I would note we have 2 weeks left and this is something we should have figured this out well before it. So, concerns are, are we chartered to do this work and do we have time.
… The other concern is the current canonical form in the spec makes it impossible for other CBOR flavors to exist; the current mechanism applies to all CBOR encodings. So, for example, any CBOR flavors that don't use strings for properties are illegal. To be fair, Jonathan has said that isn't his intent and he doesn't want that to happen. But fundamentally that's squaring a circle.
… Defining something for all of CBOR without limiting what certain flavors can do is a problem. We'd be in a greenfield exercise. The last item is that the dagCBOR section, which does require canonical form.
… The dagCBOR spec is an external spec by Protocol Labs and that text there needs to be the minimum necessary without relying on an external spec.
… These are the issues we're grappling with in the spec in its current form.

Jonathan Holt: I think the digital signatures are not in scope for the charter. I agree with that. Data modeling is. How we get to data modeling to ordering is relevant for us to sign.
… Regarding the reference to external libraries. I think that should be resolved pretty quickly. The reference in the canonical ordering borrows from RFC 7049, and the updated one RFC 8949.
… There should be no surprise that there's language on deterministic ordering to ensure we're all doing the same thing.

Orie Steele: I think I agree with most of what jonathan said. We have an ADM and serializations of that ADM in various different forms. If we're limiting ourselves to just JSON forms, there are multiples in JSON alone and the same applies to CBOR. Thinking of a canonical representation of an ADM, I'd like to dispel the idea that that is possible. I don't believe it is. If it were, we'd have a holy war and all the representations would fight to "be it".
… We moved away from that -- and it feels like people don't know what the ADM has done. There's an ADM and serializations, each with a mimetype, there are an unbounded number of these, an undefined process for adding more of these, and no one has done the work to define these things.

Jonathan Holt: +1 to Orie, thanks!

Justin Richer: You don't sign the ADM. You sign the representation. Signatures need to define how to sign the representation. This isn't our fight.

Manu Sporny: +1 to justin_r

Orie Steele: The people who proposed the ADM never finished the work to solve the registration problem and now jonathan is encountering that. It should be trivial to register the mime type, we should say, here's where you reference the external spec that makes it trivial to implement, and this should not be hard. There's tension over what goes in DID core and what goes in the registries. DID core will get frozen, and you should put things you're

Dave Longley: still working on in the registries and you can update it when you want.

Justin Richer: Representations need to define how to get in and out. Sometimes that has inherent ordering (like a JSON array for an infra set)

Orie Steele: If you can't create a new mime type after DID core is done then the ADM was a mistake.

Justin Richer: -1 to canonicalization of the ADM

Justin Richer: (without hearing the actual argument)

Orie Steele: -1 to canonicalization of the ADM

Brent Zundel: -1 to ADM canonicalization

Manu Sporny: To propose two questions: Do we want to specify a canonical form/rules for the ADM or the information model. I expect everyone to say no to that, no one signed up to do that.
… Second question is: Do we want to specify a canonical form for any of the representations? Does this WG want to do that and will we all pitch in to do that work? Then the question becomes do we think we can solve that problem in two weeks? We are supposed to be frozen in two weeks.

Justin Richer: -1 to specifyng canonical forms for representations

Manu Sporny: -1 to canonicalization of the ADM

Jonathan Holt: I don't think canonicalization of the ADM makes sense to me, but certainly what you're signing is a representation in a particular format. Getting a one way in and one way out -- as suggested by the RFC ... our protocol should say how to sign the CBOR and get into a particular format.

Manu Sporny: -1 to specifying canonical forms for representations in DID Core

Manu Sporny: (DID Representations outside of DID Core can do whatever they want)

Orie Steele: I would propose that "did+dag+cbor" support should be out of scope.... in the same way that "did+xml" should be out of scope... based on where we are now.

Justin Richer: signature methods specify canonicalization of data structures if they need it

Jonathan Holt: Also from the perspective of the order here, the conversations we had ... ordering matters and it matters for signatures, but what I didn't highlight -- is that it's up to the DID Doc producer to put it in the right order.
… The way the author puts them in order doesn't matter, but it matters what order it is in when signing it.

Justin Richer: I agree w/jonathan, the order matters WHEN SIGNING -- which is why it's up to the signature method to specify, including verification. Maybe I need to keep the original byte stream to validate, like with JWS. Maybe I don't.

Dave Longley: in response ot manu's question, -1 for canonicalising the ADM, I don't understand what that would mean
… -1 to specifying canonical forms for representations
… if a given representation wants to do that they can do so but I don't think there's support.. this WG would be fine with someone doing that but I don't think we could get it done into DID core
… a lot of these problems could be solved by addressing the problem Orie mentioned

Orie Steele: agree, -1 to specifying canonical forms of JSON, CBOR... not what I signed up for

Dave Longley: getting text in the spec that says here is how you can add more representations, and into the registries
… that gets these issues out of the way of DID core
… I support being able to put DID docs in dagCBOR
… it's great that jonathan is working on that. I have no idea if the timelines are going ot match up with what we need to freeze for DID Core
… I want to make sure we don't lose the entire DID Core spec because of this extra piece that I am in support of
… It would be great if DID docs were in ipfs
… I'd be interested in using that
… but we need to be careful that we don't end up losing the entire DID Core spec because of these issues
… if we can find a way to enable people to continue their work and make sure other people can create representations and help the DID ecosystem flourish we should do that

Dave Longley: The other thing I wanted to say that I forgot ... was that we must not block other flavors of CBOR in the future.

Markus Sabadello: Moving the other representations in to the DID spec registries -- I wanted to do that, would that be ok with jonathan? We have registered properties, parameters, DID methods, so on. If we have a process for representations, that would be ok with that.

Jonathan Holt: If we can flush out the governance, I may be ok with that. It's just dangling out there right now.

Orie Steele: agree with markus... we could fix registration of new representations... and it will suck if we don't.

Ivan Herman: Just for my understanding, as far as I understood, the only reason we're talking about canonicalization here, is for the purpose of signature. If that is the case, and we're not defining signature for the time being. We don't say how you would sign the JSON representation, and if we don't talk about signature, then there is no reason to have canonicalization in the document.
… I wanted to have that on record, someone also said this in IRC.

Jonathan Holt: lossless encoding/decoding

Manu Sporny: Seeing some of the feedback in IRC and where the discussion seems to be headed. Two proposals I'd like to emote in IRC to look at before we take them up.

Orie Steele: The second part of Manu's proposal isn't clear enough to me, if we can be clear about the registration process and that representations are free to define canonical forms, etc. that would help.

Manu Sporny: I think everyone wants the process to be more detailed. I thought we agreed to not put registration processes in DID core. Because those are hard to change. I thought consensus was that the registration processes would go in the DID registries document. I'd be fine with specifying how to define representations in that doc, doing it in DID core would be a problem.

Dave Longley: I think DID core just needs to say you can define more representations via the registries process (see doc over here).

Drummond Reed: I think if we want to put the process over in the registries, I think that's what we want to do. I totally agree that we need to document it and I want to help work on it and that's where it belongs.

Ivan Herman: +1 to drummond, that is what W3C would probably go towards

Drummond Reed: I agree with what Dave Longley just said that DID core just needs to say go look at the registries doc for the process.

Orie Steele: I recall -- Drummond and Manu are correct that the consensus is that the DID spec registries would define the process and that's where the work needs to get done. And it just hasn't happened. And so that's why it's hard to see how it will work.
… I think this would help address jonathan's concerns.
… With DID core defining JSON/JSON-LD/etc. then there's a feeling of second class citizenry. I don't know how to address that feeling, but it seems impractical to address that but stuffing everything into the registries.

Jonathan Holt: I think I can defer to Mike Jones and Justin Richer on this. Unlike JSON which isn't as strict, CBOR facilitates more strictness in the RFCs to facilitate this problem with base64 encoding with JWT for instance. It's natively supported in the RFC. It's specified that protocols should consider deterministic encoding of the representation.
… Unlike in other representations.

Orie Steele: imo, this issue has almost nothing to do with canonicalization or cbor... we could be talking about yaml or xml... same problem.

Jonathan Holt: I'm also reading that other RFCs such as for COSE, the RFC punts that back up to CBOR RFC 7049 and the updated one. It's saying why it's a bad idea ... it battles with the JOSE spec. There's a lot of language, and I wish I had expertise as Jim Schaad, and Carsten, to get some weigh in for the implications of not addressing this right now.

Michael Jones: With respect to COSE, because there isn't a standard canonical CBOR, is what COSE does, when it wants to sign something it just puts it in a binary string and encapsulates it. It's kind of the equivalent of what JOSE with base64. COSE side steps this by representing it as a binary string.

Manu Sporny: I'm going to put in the poll, but before doing that. Just real quick. On the CBOR language, that is being referred to. It does not guarantee a canonical form. It was never meant to be that -- that's why it says "These are things you might want to keep in mind". It says "If you want a canonical form, you might want to try and do at least these things" But it's up to other specs to do that and as Mike says other specs just print out a binary string and sign it.
… I'm thinking that you think that text does more than it does. It only applies to binary serializations that are deserialized -- it does not apply to production and consumption and round trips through ADMs. It just says if you have a binary string and you want two implementations to pull in and understand in the same way -- that's all they got to.

Jonathan Holt: It is possible, and I'd like to tease out, what parts of it do you have problems with. I'd love to address those concerns.

Proposed resolution: The DID Working Group will not define a canonical form for the Abstract Data Model. (Manu Sporny)

Orie Steele: +1

Brent Zundel: +1

Manu Sporny: +1

Ivan Herman: 1

Dave Longley: +1

Amy Guy: +1

Jonathan Holt: +1

Drummond Reed: +1

Shigeya Suzuki: +1

Markus Sabadello: +1

Ted Thibodeau Jr.: +1

Resolution #1: The DID Working Group will not define a canonical form for the Abstract Data Model.

Michael Jones: +1

Adrian Gropper: +1

Jonathan Holt: You know I'm going to object. I'm really harping on this canonicalization, it makes it so much easier if we have a canonical representation in CBOR. I think the ADM, it's just too abstract. So having a concise binary object representation helps facilitate the lossless encoding and decoding into other formats. It behooves us to tackle this, as it opens the door.
… Carsten has a lot of libraries for going back and forth because CBOR is so extensible.

Ivan Herman: I could say similar things about other formats. The reasons why I started work on doing various types of constraint languages, e.g., for json schema and for JSON-LD -- and I've put them into the registry repo right now... part of that to be discussed. Having your work put there would be what I would expect to happen. That can be done one the CR is published because this is not something absolutely necessary to go ahead with the CR.
… Yes, I believe you, I'm not an expert, it's very useful for testing, implementations, all kinds of different things, yes we should produce these things for the various representations we put into core, but it doesn't have to be in core itself.

Brent Zundel: I'm getting pretty concerned that we're getting close to things that are officially out of scope for our group. It could argued that explaining a deterministic algorithm for signatures could be out of scope because it's too close to signatures. If we're not past the point of our scope we're very close to it.

Proposed resolution: The DID Working Group will not define a canonical form for any representation in DID Core. Representations that want to define a canonical form as a DID Specification Registry extension are free to do so. The DID WG will define the registration process in the DID Specification Registries and provide an example of at least one registration in DID Specification Registries. (Manu Sporny)

Orie Steele: +1

Dave Longley: +1

Drummond Reed: +1

Manu Sporny: +1

Adrian Gropper: +1

Brent Zundel: +1

Amy Guy: +1

Ted Thibodeau Jr.: +1

Shigeya Suzuki: +1

Michael Jones: +1

Jonathan Holt: -.5

Ivan Herman: I have a question on the proposal. I thought what we'd do in the registries, is not only the canonical forms, but also any kind of additional representations.

Manu Sporny: Yes, that is correct, do you feel that the proposal doesn't say that?
… We could put all the representations in the registries to address the second class citizen concern.

Ted Thibodeau Jr.: Representations, with or without a canonical form, may be added to the DID Specification Registry as extensions.

Ivan Herman: If I want to have a yaml representation of the model, I should be able to do that in the registry. That, for me, is not clearly in the proposal.

Manu Sporny: Yes. That's the intent.

Jonathan Holt: How about this compromise, only the core model is in the DID core spec, and the representations are all in the registries.

Ted Thibodeau Jr.: I think jonathan, that's roughly the intent at this time. Part of the pushback against you right now is that you have acknowledged that you're not an expert on the thing you want in the spec and we're up against tight timelines right now. Without the expertise to write the PR for what you want to add, I don't see that as possible.
… I think we'll put all the representations in the registry -- and it doesn't say anything about any representations being in DID core right now.

Manu Sporny: I think we should take up another proposal to clarify what's going on.

Ivan Herman: +1

Michael Jones: This talk of all the representations being in the registry doesn't match what we've actually done in the spec. The JSON and JSON-LD and the dagCBOR representations are all defined in the core spec, not in any registries. I propose we don't change that and don't make any resolutions so it appears that's not true.

Manu Sporny: I would like the group to focus on getting one proposal passed at a time.
… Does anyone have a proposal they'd like to float for moving all the representations into the registries? I will float one if not.

Jonathan Holt: hence, second class

Amy Guy: +1 selfissued

Michael Jones: Yeah, specifications are specifications and registries are registries. Registries are lists of things. Specs have normative text. Talking about moving large blocks of text into a registry is nonsensical.

Brent Zundel: +1 to selfissued

Orie Steele: +1 to =selfissued

Dave Longley: I put a proposal in IRC. Can we solve the second class citizen issue by being clear in the core spec
… by saying there are representations in this spec, but they are not any more important than any other representation in the registries, go look there for others, which will have links to the specs where those are defined

Drummond Reed: +1 to Dave's suggestion

Amy Guy: +1 to dlongley too... the only difference between them is that some were ready in time for CR and others were ready later

Manu Sporny: I don't think that would address the issue, Dave. But let's run proposals.

Drummond Reed: +1 to Amy

Proposed resolution: Move the existing representations in the DID Core specification into their own specifications and register each representation in the DID Specification Registries. (Manu Sporny)

Michael Jones: -1

Amy Guy: -1

Drummond Reed: -1

Brent Zundel: -1

Dave Longley: -1

Manu Sporny: -1

Orie Steele: -1

Ivan Herman: -1

Jonathan Holt: +1

Markus Sabadello: -1

Adrian Gropper: -1

Brent Zundel: brent: It is clear from this result that we do not need to run the counter proposal

Manu Sporny: Do we need to run the opposite proposal? Where we say we're going to keep the core representations in the spec?

Brent Zundel: brent: the representations in the spec will stay there

Proposed resolution: The DID Working Group will not define a canonical form for any representation in DID Core. Representations, with or without a canonical form, may be added to the DID Specification Registry as extensions. The DID WG will define the registration process in the DID Specification Registries and provide an example of at least one registration in DID Specification Registries. (Manu Sporny)

Ivan Herman: +1

Manu Sporny: +1

Orie Steele: +1

Drummond Reed: +1

Amy Guy: +1

Shigeya Suzuki: +1

Adrian Gropper: +1

Ted Thibodeau Jr.: +1

Markus Sabadello: +1

Dave Longley: +1

Michael Jones: -1

Jonathan Holt: -1

Brent Zundel: +1

Amy Guy: +1 selfissued that's how I interpreted this

Michael Jones: This is very strangely worded. You make a representation in a specification. You might also list that specification in a registry. You don't add a representation directly to a registry. A registry is a list not a spec.

Proposed resolution: The DID Working Group will not define a canonical form for any representation in DID Core. Representations, with or without a canonical form, may be registered in the DID Specification Registry as extensions. The DID WG will define the registration process in the DID Specification Registries and provide an example of at least one registration in DID Specification Registries. (Manu Sporny)

Manu Sporny: +

Ivan Herman: +1

Manu Sporny: +1

Drummond Reed: +1

Ted Thibodeau Jr.: +1

Dave Longley: +1

Amy Guy: +1

Brent Zundel: +1

Michael Jones: +1

Shigeya Suzuki: +1

Orie Steele: +1

Brent Zundel: acl jonathan_holt

Jonathan Holt: I haven't seen this in any protocol/place where some representation isn't able to handle this, the deterministic section in CBOR says it's up to authors. We are supposed to clearly state how to handle a representation. Not kicking the can down the road into some registry process.

Ted Thibodeau Jr.: there's no protocol here

Drummond Reed: My understanding is that everything that is defined in DID core is listed in the registry. Everything in the registry is official. It doesn't really matter whether a representation is in DID core or outside of DID core. All are siblings, all are in the registry.

Manu Sporny: That's correct.

Ivan Herman: That's correct.

Dave Longley: That's correct.

Jonathan Holt: -0.5

Amy Guy: +100 to fleshing out governance of registries!

Jonathan Holt: It's a fair compromise, I think we need to flush out the governance of the registry -- in which case it will be seamless, but it's punting it and I don't like that.

Orie Steele: yes please, help by making PRs!

Brent Zundel: Thanks for coming, thanks to scribe, thanks for the input.

Drummond Reed: Thanks Dave for scribing

---

[msporny]

PR #593 addresses this issue. This issue will be closed once that PR is merged.

[peacekeeper]

PR #606 also addresses aspects of this issue.

[msporny]

PR #593 has been merged, PR #606 addresses the remaining parts of this issue. This issue will be closed once PR #606 is merged.

[msporny]

PR #606 has been merged, closing.