W3C home > Mailing lists > Public > public-credentials@w3.org > August 2021

New Swift Library for Optimized QR-Code Generation

From: Christopher Allen <ChristopherA@lifewithalacrity.com>
Date: Mon, 30 Aug 2021 00:23:34 -0700
Message-ID: <CACrqygB0zfGuZv_ubJ2AMLwoWH-v8c_acgwWXx2u721WxJ9zHA@mail.gmail.com>
To: Credentials Community Group <public-credentials@w3.org>
Cc: Wolf McNally <wolf@wolfmcnally.com>
As many of you know, Blockchain Commons has been working with a number of
cryptocurrency wallet vendors to create interoperable specifications for
QR-based air-gap cryptographic use cases that we call Universal Resources
(aka "UR").

Our UR specifications are designed for the interoperable transmission and
storage of a variety of kinds of information, but in particular
cryptographic data, and we have an advanced QR and CBOR-based architecture.
(For more information on this see URs: An Overview
<https://github.com/BlockchainCommons/crypto-commons/blob/master/Docs/ur-1-overview.md>.)
For make it easier to implement our specs we also make available open
source reference libraries and demo apps in our repos on Github
<https://github.com/BlockchainCommons>.

One particular new feature of UR, a specification & libraries for
efficiently animating QRs has been popular among wallet vendors, and may be
of interest to this community, but we've also been releasing a number of
other useful libraries.

We've noticed that Verifiable Credentials edge upon being too large to
efficiently transmit in a single printable QR, where animating them is not
an option. We found this in particular while attempting to replicate how
the SMART Health Card (SHC) <https://smarthealth.cards/> hard-coded their
QRs, which with native libraries inside of iOS did not generate QRs as size
efficient as they did.

We have released today the first version of a Swift and iOS library that
makes it easier optimized QRs, and our first release is available now at
https://github.com/blockchaincommons/QRCodeGenerator

This library is a native Swift port of what we evaluated to be the best
library for generating QRs "Project Nayuki", which happens itself to be
written Javascript https://www.nayuki.io/page/qr-code-generator-library.
Our unit tests verify that it produces the exact same QR codes as those
produced in the original source Nayuki demo app. Though this is our first
release, we believe this release to be stable and useful.

Enclosed is an excerpt from our docs about why this library and how it
works.

If you appreciate our work in these libraries and these open
specifications, we would like to encourage your public Patronage with a
monthly contribution at https://github.com/sponsors/BlockchainCommons/ —
several of the members of this community support us at $100 a month, others
at $500 or $1000 a month.

Every bit helps — your financial supports allows us to pay for things like
independent third-party security reviews of our code that we otherwise
can't afford to do ourselves (we are just releasing the results of the code
review library of our Shamir & SSKR cryptographic libraries next week).

I hope you find this information and this library useful!

-- Christopher Allen
Why Another QR Code Generator?

The QR code standard provides for QR codes to be composed of a heterogenous
sequence of "segments," each of which is optimized for encoding different
sorts of data, and each of which requires a different number of bits per
character to encode. Therefore, choosing which segment type (or series of
segment types) to use for efficient encoding is important.
Segment TypeBits Per CharacterCharacter Set
bytes 8 0x00 - 0xff
numeric 3.33 0123456789
alphanumeric  5.5 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:
kanji 13 Shift JIS <https://en.wikipedia.org/wiki/Shift_JIS>

Many QR code generators, including the one built into iOS and macOS, take
an undifferentiated block of byte data as input and analyze it to determine
which single segment type can most efficiently encode it. For instance, if
the block contains only the ASCII Arabic numerals, the numeric segment type
is selected. This results in the encoding only taking 3.33 bits per
character. Similarly, if every character in the input block is in the
limited character set provided by the alphanumeric encoding node, the
encoding takes only 5.5 bits per character.

The Blockchain Commons UR standard
<https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-005-ur.md>
 is designed to be compatible with the alphanumeric segment encoding node:
URs are case-insensitive, and when a UR is transformed to upper case, it
always is encodable in the alphanumeric mode. This results in an efficient
encoding and therefore a less-dense QR code.

However, not all formats are this straightforward. For example the data for
the SMART Health Card (SHC) <https://smarthealth.cards/> format is a URI
that starts shc:/ followed by often over a thousand numeric digits. The
first five characters require the bytes encoding mode, while the following
digits would be most efficiently encoded using the numeric mode. But if
only one segment type can be selected, then it must be the bytes node. For
the SHC format, this results in a much denser QR code that requires more
screen resolution to display and higher quality cameras to read. The
solution is to encode the data as two segments: the first encoding the
header using the bytes mode, and the second with the body using the numeric
mode.

It important to understand that no matter how many segments of any time
used to create a QR code, all QR code readers are capable of reading them.
So which segments to use is strictly a matter for the encoder to decide:
the decoder always sees a scanned QR code as a string of UTF-8 bytes.

So for certain data types, the QR code generator built into iOS and macOS
will have less than efficient results. This QRCodeGenerator package allows
you to automatically pick a segment type as the built-in generator does, or
specify a sequence of segments, giving you control over encoding efficiency
over all the segments.

If you know the most efficient encoding for a data format in advance you
can manually specify a series of segments. But QRCodeGenerator also
includes "optimal encoding" functions that search for and discover not a
*single*segment type, but a *sequence* of most-efficient segment types. The
use of this optimal encoding is optional because it does take a bit more
processing power to search the space of possible segment encoding types to
arrive at the optimal one.

The ability to manually specify a sequence of segment types, or to have the
package pick an optimal one automatically are the major advantages that
QRCodeGenerator has over the built-in generator.

As an example, the following Chinese string includes a variety of types of
characters:

維基百科(Wikipedia,聆聽i/ˌwɪkᵻˈpiːdi.ə/)是一個自由內容、公開編輯且多語言的網路百科全書協作計畫

If Segment.makeBytes(text:) is called with the above string, it returns the
following single Segment that requires 1120 bits of space to encode:

Segment(mode: byte, characterCount: 140, data: <1120 bits>)

However, if Segment.makeSegmentsOptimally(text:) is called, it returns the
following sequence of Segments:

Segment(mode: kanji, characterCount: 5, data: <65 bits>)
Segment(mode: byte, characterCount: 9, data: <72 bits>)
Segment(mode: kanji, characterCount: 3, data: <39 bits>)
Segment(mode: byte, characterCount: 23, data: <184 bits>)
Segment(mode: kanji, characterCount: 6, data: <78 bits>)
Segment(mode: byte, characterCount: 3, data: <24 bits>)
Segment(mode: kanji, characterCount: 21, data: <273 bits>)

This totals to 735 bits, a 48% savings.
Received on Monday, 30 August 2021 07:24:25 UTC

This archive was generated by hypermail 2.4.0 : Thursday, 24 March 2022 20:25:22 UTC