Clarify bit-to-byte ordering in bitstring serialization

[oriolcanades]

Summary

The specification does not explicitly define the bit ordering within bytes when serializing the bitstring prior to GZIP compression. This ambiguity is causing interoperability issues between independent implementations.

Current specification text

Section 3.3 (Bitstring Generation Algorithm) states:

"Let bitstring be a list of bits with a minimum size of 16KB, where each bit is initialized to 0 (zero)."

The algorithm describes the bitstring as an abstract list of bits, but does not specify how this list should be packed into bytes before compression.

The ambiguity

When mapping bit index n to a byte array, there are two possible conventions:

Convention	Byte index	Bit position within byte	Example: bit 0 set
MSB-first	floor(n / 8)	7 - (n mod 8)	0b10000000 (128)
LSB-first	floor(n / 8)	n mod 8	0b00000001 (1)

Real-world impact

We encountered this issue when integrating two independently developed implementations: one Issuer using LSB-first encoding and one validator using MSB-first decoding. Status verification failed despite both implementations following the specification as written.

Ecosystem observation

Digital Bazaar's implementation uses MSB-first ordering, which appears to be the prevailing convention in the ecosystem.

Proposal

Add normative language to Section 3.3 specifying the bit-to-byte mapping. Suggested addition:

"When serializing the bitstring to a byte array, implementations MUST use most-significant-bit-first (MSB-first) ordering. Specifically, bit index n MUST be stored in byte floor(n / 8) at bit position 7 - (n mod 8), where bit position 7 represents the most significant bit of the byte."

Questions for the working group

1. Is MSB-first the intended convention?
2. Should this be explicitly documented in the specification?
3. Would it be useful to include a test vector (e.g., "a bitstring with only bit 0 set compresses to X") to help implementers verify correctness?

Thank you for your consideration.

[dlongley]

Does this section help or does it need further clarification?:

https://w3c.github.io/vc-bitstring-status-list/#bitstring-encoding

Notably, this is linked from section 2.2 which states this about credentialSubject.encodedList:

The uncompressed bitstring MUST be at least 16KB in size. The bitstring MUST be encoded such that the first index, with a value of zero (0), is located at the left-most bit in the bitstring and the last index, with a value of one less than the length of the bitstring (bitstring_length - 1), is located at the right-most bit in the bitstring.

[dlongley]

There are test suites for implementers (https://github.com/w3c/vc-bitstring-status-list-test-suite), but it may be of use to include some test vectors in the specification itself.

Visualization of interoperability test suite reports can be found here: https://canivc.com

[oriolcanades]

Thank you for the pointer to Section 7.1. While that section is helpful, I'd like to respectfully emphasize two concerns:

1. Non-normative nature of Section 7.1. Section 7.1 is explicitly marked as "non-normative." While the diagram and explanation are useful conceptually, they don't constitute binding requirements for implementers. The phrase "left-most bit" provides a hint toward MSB-first ordering, but implementers following only the normative sections (particularly Section 3.3's algorithm) have no explicit guidance on byte-level encoding.
2. Real interoperability impact. This isn't a theoretical edge case—we've encountered actual interoperability failures between implementations in production. Both implementations were written by experienced developers who followed the specification as written. The fact that different reasonable interpretations are possible demonstrates the need for normative clarification.

Concrete proposal:

Would the working group consider either:

• Option A: Elevating the bit ordering guidance from Section 7.1 to normative language in Section 3.3 (as suggested in my original proposal)
• Option B: Adding a normative note in Section 3.3 that explicitly references the encoding rules and makes Section 7.1's guidance normative for that specific aspect

Test vector example:

To help future implementers avoid our mistake, a simple test vector could be added:

Given: A bitstring where only index 0 is set to 1
Expected: First byte = 0x80 (10000000 in binary)
Given: A bitstring where only index 7 is set to 1
Expected: First byte = 0x01 (00000001 in binary)

This would make the MSB-first ordering immediately verifiable without ambiguity.

I'm happy to contribute draft text if that would be helpful. Thank you for considering this clarification.