QR Codes & DIDs

(To the DID and CCG lists. Please keep the cc: to Wolf if you want him to
reply to any questions)

Blockchain Commons has a goal to be able to DID documents and VCs
leveraging airgap QR Codes, and asked Wolf do to some research for me.

This research came from a comment by Ryan Grant <rgrant@rgrant.org>:

> The reason I ask about side of diddoc is that the brace characters are
not in the qrcode alphanumeric  alphabet. The iphone qrcode will only
reliably read 2953 binary bytes. I think the most interoperabe qrcode
encoding of the diddoc will be base64, which means the limit on an iphone
reader is 2214 bytes.

The result from Wolf McNally <wolf@wolfmcnally.com> is:

> I conclude from these experiments that there is unlikely to be any great
benefit from first transcoding a JSON document to a less dense character
set in order to activate a more dense QR encoding.


I hope you find this helpful.

Some longer-term questions we have are to do with what to do when we do
exceed the limits of a single QR code. For instance, we've considering
proposing something like this wrapper in QR codes that are multipart and
need to be animated. We have seen a business-card-sized device (the SafePal
bitcoin wallet https://safepal.io/ ) with a camera and small screen that
can do animated QR codes, so we know this is feasible on low-powered
hardware:

```
{
    "header": {
        "format": "Airgap",
        "version": 1
    },
    "multiPart": {
    "uid": "449C40FE-E207-4AC9-B552-51B007B68D50",
    "part": 0,
    "count": 1,
    "data": "VGhlIHF1aWNrIGJyb3duIGZveCBqdW1wcyBvdmVyIHRoZSBsYXp5IGRvZy4K"
    }
}
```

We have also found that QR code size limits are smaller when using a camera
on a laptop because of lack of closeup focus. Does anyone have any
experience with this?

Any other thoughts, advice, questions on using QR codes with DIDs and VCs?

— Christopher Allen


---------- Forwarded message ---------
From: Wolf McNally <wolf@wolfmcnally.com>
Date: Fri, Feb 14, 2020 at 1:15 AM
Subject: QR Code Density Comparison
To: Christopher Allen <christophera@lifewithalacrity.com>


*QR Code Density Comparison*

This is a comparison of various encodings of a piece of JSON text, with the
goal of determining whether the QR Code generation algorithm in iOS selects
an encoding mode (binary vs. alphanumeric) automatically, and whether it
makes sense to pre-encode the JSON in some other format that will be more
efficiently encoded by the QR Code generator.

All QR encodings in the document use the Low Error Correction option.

Text 1 below is a default DID document. When QR encoded, the resulting
image is 91x91 modules (8,281 modules total)

Text 1 (639 characters):

{ "@context": "https://w3id.org/did/v0.11",
  "id": "did:btcr:xsdv-zrtp-qe4h-vga",
  "publicKey": [ {
      "id": "did:btcr:xsdv-zrtp-qe4h-vga#satoshi",
      "controller": "did:btcr:xsdv-zrtp-qe4h-vga",
      "type": "EcdsaSecp256k1VerificationKey2019",
      "publicKeyBase58": "22zj7sFEsYQXcvLFV55Z4oA6yQZwwKGPa893D8V3EnipS"
    }, {
      "id": "did:btcr:xsdv-zrtp-qe4h-vga#vckey-0",
      "controller": "did:btcr:xsdv-zrtp-qe4h-vga",
      "type": "EcdsaSecp256k1VerificationKey2019",
      "publicKeyBase58": "22zj7sFEsYQXcvLFV55Z4oA6yQZwwKGPa893D8V3EnipS"
  } ],
  "authentication": ["#satoshi"],
  "assertionMethod": ["#vckey-0"] }

Text 1 encoded (91x91 modules):


————————

Text 2 consists of the same number of characters as Text 1, but drawn from
the QR Code alphanumeric set, excluding space. This consists of the 43
characters:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ$%*-./:

Table of Alphanumeric Values - QR Code Tutorial
<https://www.thonky.com/qr-code-tutorial/alphanumeric-table>

The result of QR encoding this text is an image that consists of only 75x75
modules = 5,625 modules, which is about 30% smaller than Text 1. From this
we conclude that the QR code generator is auto-detecting whether the input
string can be encoded using the alphanumeric mode and switching to it if
possible.

Text 2 (639 random characters in A...Z):

/FBMCUE$1K/67DXM:$HTT5H46KSN4$N$EK2J7B0GA3RL8IXZ%B*%R9M7HCS*UB199-S5-2*M:*PZ42698MA/D4TK4:7B*011RKLDN085D53G$M.-U9*YFXE.*CCBM49DPJFXK%2C$QYBMLJCAG.HJTJ7ZQWS.WH0PN%MEMN/2B-$8L8F4CKOYML4M4PQTZS17A9.Z.HWBRRMGISTI%V1*NB/DVTT*R*.GF58UM%::OW1G$65ZIGQR38T16A-LJHHAJNI8C3/J2AYXBAC-DMMJNUKS:.GK3D08-$*62UTEK.8Q8:VE3UTXJMC:U:$7*IVX:VN924JENFBLWDKR1CN$%RG24T4J5GKHD9RK7MVO2JYAH0KDLSOEF:*M1AJ/28*QG6HEQ48:TGQJTX73/44C%ON6C:I31DIU:BC52YXS83NZ-.XZULG:0XAYPM/LJC9C/3GLJ285W*$-W5SP337/*$*JOH.S$OGJ6KZ8YZTY/2ZWLDO3YNLGI4HD3I/7AM7B*.O9K8SZUB*CJCX.UEKRG-$R%4ZI8MBIUG2ONFU%RL1Y::CVMYI6K7N6%F65FEQQ/X40ND/LNX-ASZ60DF-B3*N$AQU2UO*$UNHUS*W0HBH/W6:VZC:Y6%M30KJN1H

Text 2 encoded (75x75 modules):


————————

To begin to test alternate encodings, we encode Text 1 using Base-64 and
then QR encode that. The result is an image that is 103x103 modules =
10,609 modules, whch is almost 30% *larger* than the encoded form of Text
1. Obviously Base-64 uses characters not in the QR code's alphanumeric set,
so the encoding must take place in binary mode.

Text 3 (Text 1 base 64 encoded, 852 characters):

eyAiQGNvbnRleHQiOiAiaHR0cHM6Ly93M2lkLm9yZy9kaWQvdjAuMTEiLAogICJpZCI6ICJkaWQ6YnRjcjp4c2R2LXpydHAtcWU0aC12Z2EiLAogICJwdWJsaWNLZXkiOiBbIHsKICAgICAgImlkIjogImRpZDpidGNyOnhzZHYtenJ0cC1xZTRoLXZnYSNzYXRvc2hpIiwKICAgICAgImNvbnRyb2xsZXIiOiAiZGlkOmJ0Y3I6eHNkdi16cnRwLXFlNGgtdmdhIiwKICAgICAgInR5cGUiOiAiRWNkc2FTZWNwMjU2azFWZXJpZmljYXRpb25LZXkyMDE5IiwKICAgICAgInB1YmxpY0tleUJhc2U1OCI6ICIyMnpqN3NGRXNZUVhjdkxGVjU1WjRvQTZ5UVp3d0tHUGE4OTNEOFYzRW5pcFMiCiAgICB9LCB7CiAgICAgICJpZCI6ICJkaWQ6YnRjcjp4c2R2LXpydHAtcWU0aC12Z2EjdmNrZXktMCIsCiAgICAgICJjb250cm9sbGVyIjogImRpZDpidGNyOnhzZHYtenJ0cC1xZTRoLXZnYSIsCiAgICAgICJ0eXBlIjogIkVjZHNhU2VjcDI1NmsxVmVyaWZpY2F0aW9uS2V5MjAxOSIsCiAgICAgICJwdWJsaWNLZXlCYXNlNTgiOiAiMjJ6ajdzRkVzWVFYY3ZMRlY1NVo0b0E2eVFad3dLR1BhODkzRDhWM0VuaXBTIgogIH0gXSwKICAiYXV0aGVudGljYXRpb24iOiBbIiNzYXRvc2hpIl0sCiAgImFzc2VydGlvbk1ldGhvZCI6IFsiI3Zja2V5LTAiXSB9

Text 3 encoded (103x103 modules):


————————

Next we encode Text 1 using Base-32. The resulting QR code is 91x91 modules
= 8,281 modules. This is the same size QR code generated for the original
Text 1, thus in this case we gain no advantage from the extra encoding step.

Text 4 (Text 1 base 32 encoded RFC 4648, 1024 characters):

PMQCEQDDN5XHIZLYOQRDUIBCNB2HI4DTHIXS65ZTNFSC433SM4XWI2LEF53DALRRGERCYCRAEARGSZBCHIQCEZDJMQ5GE5DDOI5HQ43EOYWXU4TUOAWXCZJUNAWXMZ3BEIWAUIBAEJYHKYTMNFRUWZLZEI5CAWZAPMFCAIBAEAQCAITJMQRDUIBCMRUWIOTCORRXEOTYONSHMLL2OJ2HALLRMU2GQLLWM5QSG43BORXXG2DJEIWAUIBAEAQCAIBCMNXW45DSN5WGYZLSEI5CAITENFSDUYTUMNZDU6DTMR3C26TSORYC24LFGRUC25THMERCYCRAEAQCAIBAEJ2HS4DFEI5CAISFMNSHGYKTMVRXAMRVGZVTCVTFOJUWM2LDMF2GS33OJNSXSMRQGE4SELAKEAQCAIBAEARHA5LCNRUWGS3FPFBGC43FGU4CEORAEIZDE6TKG5ZUMRLTLFIVQY3WJRDFMNJVLI2G6QJWPFIVU53XJNDVAYJYHEZUIOCWGNCW42LQKMRAUIBAEAQH2LBAPMFCAIBAEAQCAITJMQRDUIBCMRUWIOTCORRXEOTYONSHMLL2OJ2HALLRMU2GQLLWM5QSG5TDNNSXSLJQEIWAUIBAEAQCAIBCMNXW45DSN5WGYZLSEI5CAITENFSDUYTUMNZDU6DTMR3C26TSORYC24LFGRUC25THMERCYCRAEAQCAIBAEJ2HS4DFEI5CAISFMNSHGYKTMVRXAMRVGZVTCVTFOJUWM2LDMF2GS33OJNSXSMRQGE4SELAKEAQCAIBAEARHA5LCNRUWGS3FPFBGC43FGU4CEORAEIZDE6TKG5ZUMRLTLFIVQY3WJRDFMNJVLI2G6QJWPFIVU53XJNDVAYJYHEZUIOCWGNCW42LQKMRAUIBAPUQF2LAKEAQCEYLVORUGK3TUNFRWC5DJN5XCEORALMRCG43BORXXG2DJEJOSYCRAEARGC43TMVZHI2LPNZGWK5DIN5SCEORALMRCG5TDNNSXSLJQEJOSA7I=

Text 4 encoded (91x91 modules):


————————

A hypothetical Base43 converter would fully utilize the bandwidth available
in the QR code alphanumeric character set. We can estimate the number of
characters needed for the 639 characters of text 1:

639 characters * 8 bits/character = 5,112 bits
Number of bits encoded in a single QR code alphanumeric encoder:
Solve[2^n == 43, n, Reals] // N
{{n → 5.42626}}
5,112 bits / 5.42626 bits/character = 942 characters

Generating another random 942 characters from the QR code character set to
simulate the output of the hypothetical Base54 converter, we get Text 5. QR
encoding text 5 again gives us a QR code that is 91x91 modules— the same
size as the Base32 encoded Text 4.

Text 5

U8BDDGI7/8NBETWBLB3FC.-/O.6OCHDT0H.00QOC5T4/B-CP4C7$GZOYD*.-SISN72XXJTLIDJ5C-*X:3:D57A4*NOZI8AMCV75D.2N5KNFBL-ZZ1PC/RUOXGLSD1HIF8:AT8.KIROQ9G-$.T6MZG:4K2CA-JKNGJGY8V60X5R%
QGQQXN10383.CO
%7OSYAGJE:RD:3LI4K:LHQYNEJ5$SXYGN0PF53F9MC3TN31WTL:CU1D83G1XWZVCHIKO.VKA9CLIK$JXIFO0AD6XDVK4SS37E60*SOUM/1R$T-TJEU9AW4DBK2NE:WIR8$EGHRU%*91UAEG0D48R75-048/711V8:M2XLSW0%96RJGN4P36HI-LF1MT24P:L/D6W00D5:FK18K8FIQ0PTAO:%-XY.7UAD/XRKC3RPLDA0MC9UNT3W*.ZRQHNZKZ%Z$3OP8O--28543TRQTV$BK6JI2SB3Y5V$S9OCER400AQQ%61WR07VFU/WSM99$$HBKD/4HY7KFY4LMHTLC-BGU1$8M39O3-NB%64LFKYS8VB1VVOM1O5QW-SE*U0VTR:I.0WO:*WONDT664E/0NOJMYMGW/SS-*/AMR5FO-2P9UKNGYQ43.LIY03*PSFUB6FAWZRB/X9H6FGN$/6OZP/Y$K:DXRIM0FS3532B/$9*:I2YN%1RN.7CIRH7R7:A6%D::Z8.6YN.*38DQ%0QGAI:2MHV8-SC75LWWEXZQ9VPESQO24AI**1KEZ70G1K9-XFZX1JSAJOMYE66WJZ/WMAX2DP26*UBLTV2OO3J77D5BUPD7AX1-W8F/AW65HHXLT2V*Z:QKY-Q*MKETR76G*/GV58L9::-KB2MMEDQN5OF0:E2FVI%V0D*OBMJW9OR-SW/U%PM2$$JZ05Q/JK0YVYB2W3LSSFP2P/1TWY5$8/E*O*6F5U0Z%5C

Text 5 encoded (91x91 modules):

[image: QR Code 5.png]

————————

I conclude from these experiments that there is unlikely to be any great
benefit from first transcoding a JSON document to a less dense character
set in order to activate a more dense QR encoding. The alphanumeric mode of
QR codes is clearly suited to text that can be expressed in its original
form in the particular alphanumeric character set. JSON requires characters
that are not in the QR code alphanumeric set, like the curly braces, and
even its alphabetical components (key names and values) are case sensitive.
If an encoding other than JSON were designed that only used characters from
the QR code alphanumeric set, then it is possible that greater efficiency
could be achieved. But a general scheme would still need to encode
case-preserving strings such as user-entered data, and this data would
still have to be transcoded field by field before the whole data structure
could be QR encoded.

My recommendation is that further attempts to use only the QR code
alphanumeric mode be set aside as premature optimization requiring
considerable work for uncertain gain.

🐺