Subject: [Cbor] tag 24, CBOR sequence and non-CBOR sequence

From: Laurence Lundblade <[email-masked]>
Date: Fri, 5 Jun 2020 08:13:04 -0700

Here’s some example of CBOR sequence (e.g., application/cbor-seq) and CBOR that is not a sequence (e.g., application/cbor)

0x00 
This is a legal sequence or non-sequence

0x00 0x00
This is a legal sequence, but not non-sequence. A non-sequence can contain only one data item, this contains two.

0x82 0x00 0x00
This is a legal sequence or non-sequence. It is how you encode two zeros as a non-sequence.

Looks to me that tag 24 cannot contain a CBOR sequence. It says “a data item”. The use of “a” implies one data item and thus not a sequence. That means a decoder should always consider a sequence in the contents of a tag 24 invalid.

This seems overly restrictive and unfortunate to me.  Would it be wrong for a generic decoder to allow this?

The wording for tag 55799 avoids the issue of sequence or not.

Technically, it seems that something labeled application/cbor or in a file named foo.cbor can’t contain the CBOR 0x00 0x00 because it is not a legal non-sequence. That might implies a generic decoder should have a sequence mode and a non-sequence mode. In practice this doesn’t seem like a very useful restriction. What is useful is whether the encoded CBOR is legal for the protocol being implemented.

From what I’ve experienced, it seems easier if everything is just a CBOR sequence and no distinction is made. Individual CBOR protocols can decide on their own structure either deciding to bind things together in an array or not. Am I missing something?

LL

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 5 Jun 2020 20:50:20 +0200

Hi Laurence,

> On 2020-06-05, at 17:13, Laurence Lundblade <[email-masked]> wrote:
> 

“CBOR data item” (or “encoded CBOR data item”) is my preferred wording for the latter.

> This is a legal sequence, but not non-sequence. A non-sequence can contain only one data item, this contains two.

Right.

> This is a legal sequence or non-sequence. It is how you encode two zeros as a non-sequence.

Right.

> Looks to me that tag 24 cannot contain a CBOR sequence.

Indeed, no.

> It says “a data item”. The use of “a” implies one data item and thus not a sequence. That means a decoder should always consider a sequence in the contents of a tag 24 invalid.

(A sequence that doesn’t happen to contain exactly one data item.)

> This seems overly restrictive and unfortunate to me.  Would it be wrong for a generic decoder to allow this?

Yes.
(Well, it might not be checking the validity.)

It seems we forgot to define an equivalent to tag 24 in RFC 8742.
But a registration for such a tag can easily be made now.

> Technically, it seems that something labeled application/cbor or in a file named foo.cbor can’t contain the CBOR 0x00 0x00 because it is not a legal non-sequence.

Correct.

> That might implies a generic decoder should have a sequence mode and a non-sequence mode.

Yes.  You can always use the sequence mode, though (just check that you got exactly one data item back).

My preferred API asks the generic decoder to decode one CBOR data item from a position given and returns the position of the first input byte beyond that CBOR data item.
A sequence decoder is built trivially from this.
But you can also use it for cases where a CBOR data item is the “header” for some blob that is not decoded as CBOR.

> In practice this doesn’t seem like a very useful restriction. What is useful is whether the encoded CBOR is legal for the protocol being implemented.

If the protocol wants one CBOR data item and gets two (or zero), that doesn’t help.

> From what I’ve experienced, it seems easier if everything is just a CBOR sequence and no distinction is made. Individual CBOR protocols can decide on their own structure either deciding to bind thi…

I think the important observation is that it took us a couple of years to rationalize the weird text about “streaming decoders” in RFC 7049 into a clear concept of CBOR sequences.
So there is a lot of code out that that doesn’t cope very well with CBOR sequences, just with single CBOR data items — and that is often also exactly what’s needed.

Grüße, Carsten

---

From: Laurence Lundblade <[email-masked]>
Date: Sat, 6 Jun 2020 12:42:06 -0700

Well glad I asked. 

> On Jun 5, 2020, at 11:50 AM, Carsten Bormann <[email-masked]> wrote:
> 
> Hi Laurence,
> 

How about stating it like this? While tag 24 can contain a sequence of length one, it cannot contain most sequences as defined in 8742. 

Personally, I’d prefer to just say tag 24 can’t contain sequences. That way you’d have tag 24 for non-sequences and new tag XX for sequences. You don’t want people designing a protocol that uses sequences and using tag 24 when the sequence happens to be length 1 and tag XX when it is larger. That’s just confusing and more code.

Basically a protocol designer should either design a protocol that uses sequences or one that doesn’t and declare that up front. If some messages in a sequence-based protocol happen to be just one item, they are still part of a sequence-based protocol.

> But you can also use it for cases where a CBOR data item is the “header” for some blob that is not decoded as CBOR.

QCBOR is a more powerful generic decoder than the one implied by the API you describe. It aims to relieve the protocol implementor of a lot of these details and hard-to-understand aspects of CBOR. It aims to make the work of the protocol implementor a lot easier. As a shared library it reduces overall object code because it handles things common to many protocols (e.g. duplicate detection (coming soon)).

It’s of course fine to have all different sorts of decoders.

I find the distinction between sequences and non-sequence subtle and it took until this conversation about tag 24 (started by mcr) to really get it sharp for me. It was definitely one of the things that was confusing to me when I started working with CBOR a few years ago. Easy to gloss over in a way, but a niggling issue that finally came to light. Seems like it wasn’t just me.

One of the reasons I try to do more in QCBOR is to help others get these kinds of details right. They are hard to to understand from the RFCs. The average protocol implementor won’t spend the five plus years reading them we all have here.

> If the protocol wants one CBOR data item and gets two (or zero), that doesn’t help.

Protocol implementors have to deal with lots of errors.

> So there is a lot of code out that that doesn’t cope very well with CBOR sequences, just with single CBOR data items — and that is often also exactly what’s needed.

QCBOR is fine with sequences or not as input. The CBOR playground doesn’t allow sequences.

Personally, I still think it would be better to relax the distinction and allow tag 24 to carry sequences rather than define a new tag. It is a broadening, not a narrowing so it doesn’t break anything. There’s no backwards compatibility issue just like there was no backwards compatibility issue for 7049 when 8742 was published. 

If not relaxing the distinction and a new tag is defined for 8742, maybe 3.4.5.1 should say that 8742 CBOR sequences are invalid as content for tag 24. It is OK for CBORbis to make normative reference to 8742.

LL

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 7 Jun 2020 20:22:40 +0200

Hi Laurence.

> 
> How about stating it like this?

We could, but stating for every encoded CBOR data item that it is not intended to allow CBOR sequences with 0, 2, or more encoded CBOR data items in them strikes me as confusing.

If I read a book about tomatoes, I would be confused if that states again and again for some content that that does not apply to apples.

> While tag 24 can contain a sequence of length one, it cannot contain most sequences as defined in 8742. 

Yes, and we can be abundantly clear about that, see PR #200.
Without mentioning CBOR sequences.

[…]
> QCBOR is fine with sequences or not as input.

That is certainly a valid way to do things, but that should be made obvious at the API.

> The CBOR playground doesn’t allow sequences.

Right, because it was written before we got a handle on how useful sequences are as a separate concept.

> Personally, I still think it would be better to relax the distinction and allow tag 24 to carry sequences rather than define a new tag.

That would add some confusion between CBOR data items and CBOR sequences, so for me that would be a change for the worse.

> It is a broadening, not a narrowing so it doesn’t break anything. There’s no backwards compatibility issue just like there was no backwards compatibility issue for 7049 when 8742 was published. 

There is a backwards compatibility issue: Without the change, both sides of the communication can rely to get what they expect — one CBOR data item.  After the change, new implementations might start to send two, and that kills backwards compatibility with old implementations.

> If not relaxing the distinction and a new tag is defined for 8742, maybe 3.4.5.1 should say that 8742 CBOR sequences are invalid as content for tag 24.

It does so (and more so with #200), but not with these exact words.

> It is OK for CBORbis to make normative reference to 8742.

Actually, no (that would be a downref).  But that did not stop us from putting in informative references.  I just don’t think we need another one here; PR #200 is about as far as we want to go here before we add confusion.

Grüße, Carsten

---

From: Laurence Lundblade <[email-masked]>
Date: Thu, 11 Jun 2020 12:43:47 -0700

Hi Carsten,

One could say CBOR protocol world is bifurcated into sequence protocols and single-item protocols, but it’s more complex than that because a CBOR protocol that has both could be defined. And there is the 55799 tag which allows either a sequence or single item. 

To be abundantly clear, I’m tempted to write of this in CBOR protocol design considerations.

Was thinking that COSE payload was similar to 55799 in allowing both, but it is actually another thing entirely. It is not tag 24 or any other tag. It uses the MIME / COAP typing system which can indicate CBOR or CBOR sequence or name some other protocol that then in turn indicates which.

I don’t know what the advantage of this variability and complexity is. Wouldn’t be simpler for the CBOR world if sequences were the only thing? They are a super-set of single items. The only thing I can think of is that this complexity allows some decoders to be a little simpler by omitting support for sequences.

But, it seems the main reason is that no one thought about this in detail until recently (me included; in theory I should have about four years ago when I started on QCBOR :-) )

What do you think of this as a way forward to reduce the complexity a little? 

Define a new standard tag alternate to tag 24 the content of which is a sequence (as planned).

A CBOR sequence is always able to carry a single item, therefore encourage use of this new tag and the MIME and COAP types for sequences over the ones for single items.

Encourage CBOR decoders to support sequences.

I don’t see these types and tags as part of the mechanism that sets requirements for decoders implementing protocols. If you are going to implement a CBOR protocol, you have to know if it is a single-item protocol or sequence protocol and you have to select a CBOR decoder that can handle the protocol. That decision is made when code is written, not when a typed/tagged blob of CBOR arrives. 

Any implementation of a single-item protocol must deal with extra bytes to do a good job. Just because something has tag 24 doesn’t mean it won’t have some extra bytes (that might be CBOR), so the tag doesn’t defend against or relieve the decoder of this work.

Agreed there is a backwards compatibility issue in allowing sequence in tag 24, but it is only for decoders that explicitly check that there is only a single item in the content of tag 24 in their very explicit implementation of tag 24. If they just hand the contents of tag 24 to the next level protocol decoder there would be no backwards compatibility issue in practice.  I suspect most implementations of tag 24 don’t pre-check its contents before handing it off.  

I don’t want to implement tag 24 with that check for a single item because it adds code and seems like code that is not particularly necessary given the implementation of the decoding of the content will pretty much have to perform that check too as part of the protocol decoding it does. I will probably just treat tag 24 and the new sequence tag the same way and allow sequences in either. I can’t see a downside to doing that.

LL

> On Jun 7, 2020, at 11:22 AM, Carsten Bormann <[email-masked]> wrote:
> 
> Hi Laurence.
> 
>> 
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Laurence Lundblade <[email-masked]>
Date: Thu, 25 Jun 2020 13:22:51 -0700

So we do need to register / assign a tag for bstr wrapped CBOR sequences.

I can’t complete the implementation I’m working on until I know assigned tag number. We kind of have a (small) hole in CBOR without the definition of this tag.

It does seem like this should be a full standard tag since tag 24 is a full standard tag, so maybe tag 20? Seems the obvious place to do it is in CBORbis, if it’s not too late.

LL

> On Jun 11, 2020, at 12:43 PM, Laurence Lundblade <[email-masked]> wrote:
> 
> Hi Carsten,
> 
>> On Jun 7, 2020, at 11:22 AM, Carsten Bormann <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> Hi Laurence.
>> 
>>> 
>> [email-masked] <mailto:[email-masked]>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 25 Jun 2020 23:08:50 +0200

Hi Laurence,

Yes.

> I can’t complete the implementation I’m working on until I know assigned tag number. We kind of have a (small) hole in CBOR without the definition of this tag.

Yes.  Fortunately, registering a tag is low-threshold.

> It does seem like this should be a full standard tag since tag 24 is a full standard tag,

I don’t know what a full standard tag is.

> so maybe tag 20?

20 is a 1+0 tag, of which only 12 are left.
24 is 1+1, so the equivalent for CBOR Sequences should have a 1+1 tag, too.
63, the number we registered as a Content-Format ID for application/cbor-seq, happens to be free, so I am proposing that we use that as a tag number as well (we have achieved this little piece of mnemonic economy before).

> Seems the obvious place to do it is in CBORbis, if it’s not too late.

CBORbis is not intended to have additions to RFC 7049.
We already solved this problem once (for the invalid tags) using the notable-tags document.
I published an update to notable-tags that specifies the new tag in 

https://www.ietf.org/id/draft-bormann-cbor-notable-tags-02.html

and, in the interest of expedience, went ahead and asked IANA to register the tag.

Grüße, Carsten

---

From: Thiago Macieira <[email-masked]>
Date: Thu, 25 Jun 2020 14:21:04 -0700

> I don’t know what a full standard tag is.

RFC 7049 §7.2 "Tags registry" says
   New entries in the range 0 to 23 are assigned by Standards Action.
   New entries in the range 24 to 255 are assigned by Specification
   Required.  New entries in the range 256 to 18446744073709551615 are
   assigned by First Come First Served.

I guess Laurence got it wrong, tag 24 is not a Standards tag.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel System Software Products

---

From: Laurence Lundblade <[email-masked]>
Date: Thu, 25 Jun 2020 21:12:36 -0700

Off by one error on my part (23 ia standard).

No complaints about tag 63 in the notable tags doc (though the registry is where I mostly look and expect others will because it has all the tags).

Thanks.

LL

> On Jun 25, 2020, at 2:08 PM, Carsten Bormann <[email-masked]> wrote:
> 
> Hi Laurence,
> 
> On 2020-06-25, at 22:22, Laurence Lundblade <[email-masked] <mailto:[email-masked]>> wrote:
> 
> https://www.ietf.org/id/draft-bormann-cbor-notable-tags-02.html <https://www.ietf.org/id/draft-bormann-cbor-notable-tags-02.html>
>

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 27 Jun 2020 13:01:47 +0200

> No complaints about tag 63 in the notable tags doc (though the registry is where I mostly look and expect others will because it has all the tags).

Good.  The registry now has:

63	byte string	Encoded CBOR Sequence [RFC8742]	[draft-bormann-cbor-notable-tags-02, Section 2.1]

So all should be set for your usage of this in QCBOR.

Grüße, Carsten