[Cbor] Challenges in supporting bignum tag

[Emile Cormier <[e-mail]>]

Hi Everyone,

I'm in the process of supporting CBOR "bignums" (which I think should have
been named "bigint") in my C++ serialization library, and have encountered
the following challenges:

1. When transcoding to other binary formats (such as MessagePack), the sign
of the bignum is lost because it is deduced by the tag value and is not
part of the message payload. I have to resort to converting it to [sign,
byte_array], which makes it no longer round-trippable to its original CBOR
format.

2. In CBOR decoders that ignore tags, the sign of the bignum is lost when
passed up to the application. This goes against the following passage in
section 3.4 of the spec:

*"Decoders do not need to understand tags of every tag number, and tags may
be of little value in applications where the implementation creating a
particular CBOR data item and the implementation decoding that stream know
the semantic meaning of each item in the data flow."*

So even if the application knows the semantic meaning of the received byte
array (it's expecting a bignum), it cannot reconstitute the sign of the
received magnitude without knowing the tag.

Note that the same sort of information loss occurs with typed arrays,
although it is more likely that an application would know the endianness
and element size of a received typed array.

3. Most arbitrary precision libraries represent big integers in signed
magnitude format. CBOR wants negative values to be stored as (-1 - N). I
therefore need to subtract one from the magnitude stored in a negative
multiprecision integer. Because the multiprecision subtraction algorithm
needs to start from the least significant byte (to propagate carries), I
have to perform subtraction on the entire bigint before I can serialize it
to CBOR. This is because CBOR wants the bytes to be in big endian order.
It's therefore not possible to process and serialize each source byte "on
the fly" starting from the most significant byte. If I'm serializing a huge
bigint, then there's a space doubling penalty in the temporary bigint
needed for the subtraction.

4. Because of #3, my CBOR codec implementation now depends on
multiprecision integer arithmetic. I'm now forced to do one of the
following:

a) Add a dependency to a multiprecision arithmetic library, which may not
be the same one that's used by the application. For example, my library
depends on Boost.Multiprecision, but the application wants to serialize a
GMP bignum. The application now ends up with dependencies on *two*
multiprecision libraries - yuck!

b) Write the multiprecision subtraction by hand to avoid introducing a
dependency on a multiprecision arithmetic library. While the algorithm
isn't too complicated, what I write is certain to be slower than a
multiprecision library.

c) Require that the intermediary byte format passed to the encoder be the
same as what CBOR expects (which may not be the same format as what other
binary serialization formats want). For example, the header in my library
which adds GMP serialization support could use GMP itself to perform the -1
subtraction and pass those bytes to the encoder. I should note here that
the encoder interface in my library is agnostic of the serialization
format. That is, the JSON encoder interface is the same as the CBOR encoder
interface. This makes it easy for the application to serialize to different
formats (JSON, CBOR, etc) without having to change anything in the
application's serialization code.


In short, my life would be much easier if CBOR bignums were different in
the following way:

- The sign is part of the message payload, and not "deduced" by the tag
value,
- The bytes represent the magnitude of the bignum: no subtraction/addition
by 1 for negative values.

There are other tags that currently depend on the existing bignum tag
(bigdecimal, bigfloat, extended time), so I don't expect there to be much
interest in a new "sane bignum" tag that addresses the "flaws" I brought up
here. I'm just documenting the challenges I'm facing with the existing
bignum tag so that they're considered if there's ever a fork of this
standard, or if some other binary protocol wants to implement bignums.

Overall I feel there's too much emphasis in CBOR on cramming everything
into as few bytes as possible, and not enough on decoding simplicity and
speed. I also think some tags have been "abused" for storing information
that should otherwise be part of the message payload (all in the name of
saving a few bytes). This makes tags go beyond their purpose of providing
semantic meaning.

Sorry if this comes across as a rant. It's not my intention to belittle
anyone. I just wanted to share my challenges in implementing CBOR for my
C++ serialization library. Perhaps someone here will have advice on how I
can overcome these challenges.

Cheers,
Emile Cormier