Use @q for rendering tickets

[jtobin]

Various stuff around @q:

• Pulls in urbit-ob (i.e. ob-js) as a dependency
• Adds shardPatq and combinePatq for sharding on @q values
• Uses @q values for tickets in full wallets
• Adds property tests
• Major version bump (1.1.3 -> 2.0.0)

[jtobin]

Holy shit I love property testing.

 Error: Failed after 122 tests and 0 shrinks. rngState: 08238a1b4f795dec60; Counterexample: {"type":"Buffer","data":[151,187]}

Time to see what all that is about..

[jtobin]

Interesting. The sharding algorithm can occasionally produce faulty shards in small-byte-length input cases.

In the one-byte-long case, recombining the shards will occasionally (say, once every 300 tests) fail, i.e. produce the wrong value, always with a byte of value 130 included somewhere in the shards. On the two-byte case it fails much more rarely -- once every 30000-50000 cases or so, always with a byte of value 151 in the shards.

It took me well over a million cases to hit the thing, but I also observed a failure in the 3-byte-long case. It took over six million further iterations to reproduce it once, and over fifteen million more to hit it again! In these cases a byte of value 62 was included somewhere in the shards.

I don't understand what's going on exactly, but my suspicion is that it has something to do with getting an unlucky random draw inside the sharding algorithm (which uses entropy to produce random bytes). What the properties of that draw are, I don't know. I suspect that the probability of a "shard collision" or whatever this is for 48 bytes is astronomically low (like, Serious Cryptography Level low), but I want to understand what's going on, precisely.

[Fang-]

These are the kinds of tales that we will tell our children, to inspire them to do property testing. Godspeed! (But also, if you have a decent confidence level that this is practically a non-issue for realistic shard sizes, probably don't waste all day on it.)

[jtobin]

Got it. It's just when you wind up drawing such that two of the shard components are the same.

Say you're sharding k. Take shards:

• s0 = [k0, k1]
• s1 = [k0, k2]
• s2 = [k1, k2]

If k1 = k2, then you have that s0 = s1. So combining s0, s1 will give you a different result than would combining {s0, s1}, s2. Similarly, if a randomly-drawn shard component is equal to the thing you're sharding itself, that will also give you grief (say if k = k1).

So: you get a collision if k = k1, k = k2, or k1 = k2. For p bytes per shard component, that means the probability of collision is approximately 2^(-8p), or, for our purposes, 2^(-384). 😄