Sometime in 1996 on the coderpunks mailing list, Hal Finney posed the idea of a “visual hash,” which would be designed so that two hashes could be compared visually to quickly and reliably determine whether they were the same. Among other potential uses, hashes can be used to identify public keys without relying on certificate authorities. One idea is that the visual hash could be printed on a business card, and then when validating an electronic signature, the key could be compared with the one on the card to make sure it wasn't a forged key.
Ian Goldberg, then a grad student at UC Berkeley, followed up quickly with visprint, which was based on an iterated fractal system, in which the parameters of the fractal were determined from the hash. I liked the idea (so much so that I came up with a way to add color), but was concerned about the security. In particular, given one visprint, there was no guarantee that it would actually be difficult to synthesize another visprint that was sufficiently distinguishable.
I decided that a good solution for visual hashes would need to be injective, meaning that if the inputs were different, the visual hashes would also be guaranteed to be different. It also needs to be visually appealing - a 2D barcode would satisfy the mathematical property, but to most people all QR codes look pretty much alike. I decided that symmetry and connectivity would be two visual features that would help people actually recognize patterns. In particular, modeling snowflake growth might satisfy all the requirements.
My first attempt was pretty ugly (if concise) C code, and the resuts weren’t very nice either (I wont post an example but you can run the code yourself if youre motivated. I switched to a hex (rather than triangular) grid and got much nicer results.
We’ll make our snowflakes on a hex grid, where each cell is either filled or not (in fact, as we’ll see later, these decisions mostly correspond to bits in the input hash. We’ll use this coordinate system:
Snowflakes are in the D6 symmetry group, which implies 6 axes of reflection. As a consequence, to draw a snowflake design, we only have to produce a 1/12 pizza slice of it, and the rest will follow by symmetry.
To model this symmetry in our coordinate system, we only have to fill cells (i, j) with j ≥ 0 and i ≥ j. For a cell that’s on one of the axes of reflection (j = 0 or i = j), there are 6 copies. For other cells, there are 12. Mouse over to see:
We use a frontier to keep track of which cells are available to accept new bits from the hash. Initially it’s just the center. We repeat the following steps until the input hash is consumed:
The seed for the pseudo-random choice is fixed, so that different runs always give the same visual hash for the same hash input.
This is an implementation of procedural generation of snowflakes. The original motivation was as a cryptographically secure visual hash, so that people would reliably be able to tell by visual inspection whether two hashes were identical.
Tip: try editing the hash; that'll give insight into how it's grown.
I was reminded of this by vrk's plantsim project, which has a similar procedural growth concept.
Raph Levien • Recurse Center, New York City • 2017-09-08