build tool is now blocked on file-based checksum and i am L O C K E D the fuck in
42
Replies
6
Boosts
directory checksum is otherwise solved, for simple trees as well as arbitrary cyclic directed graphs. hashing a cyclic graph is much less difficult than everyone makes it out to be
the reason cycles are difficult is because it breaks a hidden invariant of every single tree that is deeply nonobvious yet extraordinarily simple to prove: in a tree, every vertex is the root
@hipsterelectron You're cooking, but to be perfectly honest I genuinely thought that was supremely obvious. That's pretty much what every elegant algorithm on trees relies on, it's why you can implement such algorithms trivially with a stack (and even collapse the tree away by making it implicit from some generating data).
this is not novel, that's a well-known fun fact. jeremy spinrad was clearly delighted to mention it in lecture
what "every vertex is the root" means is that the path from the root (any vertex) to any other vertex (leaf or otherwise) is unique. and this uniqueness makes hashing more or less obvious (i might venture to say a little too obvious)
so if you have a cycle, that definitionally means you have more than one path universally across the graph. so you have to make a Decision
importantly, directory trees are incredibly highly structured. so not only do we have a fixed root, we have a strict requirement that all edge directions point downwards.
what is downwards? in fact, this is yet another distinction obscured by the "parent" vs "child" terminology, which describes absolutely nothing useful about the data structure
the definition of "downwards" is determined specifically by the ordering of vertices within the undirected paths generated by a breadth-first search from the fixed root (the root we were given at the start of the problem)
recall that in a tree, all paths are unique (and the converse is also true--paths are unique if and only if the graph is a tree. isn't that cute?).
as a result, the directionality between any two vertices is always fixed--hence the desire to refer to it with hierarchical terminology like "parent" and "child"
but note that this "parent"/"child" terminology is a relative distinction, and says nothing about the identity of each vertex.
in fact, in every filesystem, this is what an "inode" designates--a unique vertex identifier. but this isn't exposed in any useful way at all
i have crashed out about the inode deception many times
anyway, the problem statement that gives you a "root" (i.e. a specific inode to start your paths from--that's all the / directory is, in a virtualized/sandboxed scenario) makes this problem fully deterministic. this requires another small but important inference, which is that directory cycles must necessarily occur as the result of a depth-first traversal
(i said "breadth-first" earlier, which was actually wrong, but only because the distinction didn't matter at all there)
this is to say: directory traversals from a fixed root do not consider arbitrary "back edges" (not yet). and a cycle therefore only arises if you can keep going "downwards" and find a vertex you've seen before
in fact i was boasting earlier. i totally don't know how directory cycles should work yet
but instead of going downwards, what happens if we went upwards from the leaves?
importantly, leaves are definitionally files and not directories. so we're not repeating ourselves the same way.
and more importantly, we have no choice about how we pick the upward path from a leaf!
so we would obviously like to assume that we can only ever have one cycle at a time. but in fact it's very easy to describe a mutually recursive data structure by accident--this is why i believe it's important to support this!
and more importantly, inodes are much nicer for several practical reasons!
in particular, inodes are how you can abstract away a tree-like object database from any particular hashing algorithm. this isn't just a security concern--it in fact makes the case in itself that so-called "universal" identifiers in content-addressed stores are fundamentally flawed
but possibly even more importantly, an inode can be allocated before a checksum is even possible to calculate. and a collection of inodes can be transferred from one connected repository to another completely losslessly
the distinction between a symlink and a directory hard link (the latter of which is currently illegal) is that a directory link is in fact a kind of capability--not only does the filesystem ensure it's always valid by efficient reference counting, it's also guaranteed to represent the same data at all times, no matter who dereferences it
think about that for a moment and then consider our original problem: hashing a directory tree to verify it represents the same data
furthermore, just how important is it that the precise directory hierarchy is the same when we compare tarball checksums? sure, it's tangentially relevant, if you can trigger variant behavior depending upon paths. but we're not using cargo here
i see the data stored in files as fundamentally distinct from its arrangement into some sort of graph structure. and i don't think it serves any end users, or maintainers, or packagers, or anyone else to enforce that in our measurement of filesystem integrity
oh this is so cooking. this is a ratatouille. anton ego is shook
i wasn't even trying to go for this. but yeah obviously it makes everything make so much more sense if the graph is distinct from the file resources
i was actually trying to move on to file hashing which is actually much less obvious to me and also something i think i need to solve sooner rather than later
what i was going to say:
i have a "simple" answer which considers a file as an unstructured contiguous bit string of known size. but one reason my directory checksum is very useful is the ability to maintain a hash tree independently of the input data that attests to the integrity of every recursive component.
this especially means you can merge hash trees (e.g. composing directories to form a chroot) and diff tree states (e.g. to capture output from a process execution) without reference to any object database
in other words you can create an algebra of filesystem states which is far more than merely "reproducible", and can actually describe what changed and whether that was correct
and all that is even more true with the flattened representation described above where each inode vertex has its directed graph relationships described completely independent of its identity
what i was trying to do was to shit on the "sponge construction" used in sha-3. it's sof ucking funny
https://en.wikipedia.org/wiki/Sponge_function
The sponge function "absorbs" (in the sponge metaphor) all blocks of a padded input string as follows:
Sis initialized to zero- for each
r-bit blockBofP(string)
Ris replaced withR XOR B(using bitwise XOR)Sis replaced byf(S)
what is f(S)? well,
fproduces a pseudorandom permutation of the2^bstates fromS.
in other words, f is the actual fucking hash function
like very literally f is producing a permutation (i.e. an encryption) that is predicated only upon the bits of S instead of a separate key. that's the actual definition of a hash function
that's why it's so deceptive to say "a hash function produces a smaller output". no it doesn't!!!!
; printf '' | wc -c
0
; printf '' | sha256sum
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 -
that's an encryption! and that sucks if i actually want to know what my data is, as opposed to wanting my data to be secret. using the same construct for cryptographic signatures is completely fucked when applying it to data integrity
and it's also just completely not the way hashes are used literally ANYWHERE else. the reason bloom filters work is because the hash functions are crafted to achieve collisions without having to calculate pairwise bit-for-bit equality over each pair of database entries!
radix sort gets better than n log n runtime for this exact reason!
so i refuse to call it a "hash". it's a "checksum" at best
i fervently believe that describing an actual literal parse forest for the file content that comes from actually parsing the data in an application-specific context is the correct way to achieve both data compression as well as integrity.
if the value of a single bit modifies the semantics of the entire rest of the file, that's information you kinda do need to know!
i actually refer to it as a "parse graph" to be fully general, because in fact most data serialization formats do not neatly compose into nested paired delimiters and a single "parse tree".
once you describe the relationships between atomic data blocks, you can directly use the parse graph to record checksum values that summarize not just the bits in your data, but what the bits mean.
and you (the application developer with domain expertise) can and should be able to construct a hash function that clearly summarizes the important facets of your data structure