Re: New Swift Library for Optimized QR-Code Generation

Chris, thanks for sharing this excellent work from Blockchain Commons and also releasing it under the permissive BSD 2-Clause license.

For community members interested in this work's relevance, QR codes are and will continue to be one of core primitives this ecosystem uses in protocols related to credential exchange and identifier discovery. Therefore, this efficiency multiplied across millions or billions of devices will have significant impact. No doubt, the community will continue to experiment with the best ways to embed VCs/VPs in mediums such as QR codes to support offline use cases, and tools like this will surely facilitate that effort.

On Mon, Aug 30, 2021, at 3:23 AM, Christopher Allen wrote:
> 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 Type
> Bits Per Character
> Character 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 `Segment`s:
> 
> `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.
>