Tredd appendix: Frontier sets

This is an appendix to Tredd: Trustless Escrow for Digital Data.

Before hitting on the unencrypted-prefix solution used by Tredd for compactly proving a string is not in a given set, an earlier version used something called a frontier set.¹ It’s much less efficient than the unencrypted-prefix solution in both space and time, so it was an easy choice to remove it from the Tredd implementation. But it’s also pretty cool and I didn’t have the heart to remove all mention of it, so here it is in this appendix. An implementation is here.

Recall that the problem we needed to solve was being able to say “this value is not in the Merkle tree.” We ultimately solved it by saying, “here’s a different value with the same prefix that is in the Merkle tree, so this one can’t be.” But a frontier set compactly represents the complement of a set of strings — all the strings that are not in some particular other set. So if you build a Merkle tree from a given collection of strings and a frontier set from the same collection, then proving the string is in one also proves that it’s not in the other.

You might think that the set of strings not in some other set is infinite, and you can’t store an infinite set of strings — and you’d be right. But it’s easy to list the prefixes of even an infinite set, as long as the strings are formed from a finite alphabet. For example, consider this set of strings:

• bird
• cat
• dog

If we limit ourselves to strings using the English alphabet, we can see that the complement of this set includes any string starting with one of these letters:

a, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

as well as any string starting with:

ba, bb, bc, bd, be, bf, bg, bh, bj, bk, bl, bm, bn, bo, bp, bq, br, bs, bt, bu, bv, bw, bx, by, bz

(i.e., anything other than “bi”) and any string starting with:

bia, bib, bic, bid, bie, bif, big, bih, bii, bij, bik, bil, bim, bin, bio, bip, biq, bis, bit, biu, biv, biw, bix, biy, biz

(anything other than “bir”) and any string starting with:

bira, birb, birc, bire, birf, birg, birh, biri, birj, birk, birl, birm, birn, biro, birp, birq, birr, birs, birt, biru, birv, birw, birx, biry, birz

and anything starting with:

birda, birdb, birdc, birdd, birde, birdf, birdg, birdh, birdi, birdj, birdk, birdl, birdm, birdn, birdo, birdp, birdq, birdr, birds, birdt, birdu, birdv, birdw, birdx, birdy, birdz

and, furthermore, any string starting with:

cb, cc, cd, ce, cf, cg, ch, ci, cj, ck, cl, cm, cn, co, cp, cq, cr, cs, ct, cu, cv, cw, cx, cy, cz

caa, cab, cac, cad, cae, caf, cag, cah, cai, caj, cak, cal, cam, can, cao, cap, caq, car, cas, cau, cav, caw, cax, cay, caz

cata, catb, catc, catd, cate, catf, catg, cath, cati, catj, catk, catl, catm, catn, cato, catp, catq, catr, cats, catt, catu, catv, catw, catx, caty, catz

da, db, dc, dd, de, df, dg, dh, di, dj, dk, dl, dm, dn, dp, dq, dr, ds, dt, du, dv, dw, dx, dy, dz

doa, dob, doc, dod, doe, dof, doh, doi, doj, dok, dol, dom, don, doo, dop, doq, dor, dos, dot, dou, dov, dow, dox, doy, doz

doga, dogb, dogc, dogd, doge, dogf, dogg, dogh, dogi, dogj, dogk, dogl, dogm, dogn, dogo, dogp, dogq, dogr, dogs, dogt, dogu, dogv, dogw, dogx, dogy, dogz

To show that a string like “cargo” is not in the set “bird, cat, dog,” you can show that it has a prefix (“car”) that is in the corresponding frontier set, and you can use a Merkle tree of this (large) set of prefix strings to do that compactly.

¹ Discussed in “Zero Knowledge Sets” by Micali, Rabin, and Kilian.