Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Insofar as I understand it, tools like Git and Mercurial derive checksums from their data, and those checksums are used to derive other checksums used in aggregate, leading to a kind of accumulative checksumming (checksums being the input to other checksums), that ensures a high level of integrity.

Is there a name for that, and if so, what is it? (Other than "accumulative checksumming" (which, according to Google, is not well used, or I just made up.) My Google foo is failing me here...

Another way to put it, is there a name for the way a Git repository ensures its integrity?

Sorry for the vagueness - grasping for terminology I sense should exist but I can't actually find.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

It's called a hierarchical checksum.

The corresponding tree is known as a Merkle Tree or hash tree or more rarely authentication tree.

share|improve this answer
5  
I would upvote it if you cited some source for it. –  Jan Hudec Aug 30 '13 at 10:52
    
Just check google if you don't believe it. After all, the question stated was "google fu failing". –  MSalters Aug 30 '13 at 10:57
2  
Where did you get this info? Googling hierarchical checksum gives info on a special kind of checksum that is distributed among the data for ensuring reliability on data-loss, so it seems this has nothing to do with a recurrence or iterative definition. Also, the term itself, hierarchical, could be misleading as the usual acceptation of the term imply a different "scope" or "meaning" for each instance. –  Laurent Aug 30 '13 at 10:57
    
See e.g. mail-archives.apache.org/mod_mbox/www-legal-discuss/200904.mbox/… which uses the term in connection with Git. It's also used to describe ZFS's checksum. @Laurent: for Google, you should quote the term. That will search for the phrase, instead of individual words. Most hits are for ZFS, which used exactly the checksum structure described in the question. –  MSalters Aug 30 '13 at 11:21
    
@JanHudec Feel free to upvote, these terms are standard terms, at least among people who use cryptography (Merkle/hash tree) or design storage and networking protocols (hierarchical checksum). –  Gilles Aug 30 '13 at 11:48

As far as I'm concerned it's still just "checksum".

The "sum" part of the name is a little misleading - the algorithms used to create checksums usually involve much more than just addition*. When you aggregate checksums, you're really just creating a more complicated algorithm.

* In fact, checksum algorithms which just involve summing are typically going to do a much poorer job of detecting differences.

share|improve this answer

I would call it a recurrence checksum.

In mathematics, a recurrence relation is used for a sequence recursively defined, starting with an initial value, and where the following term is defined from the previous one: u(0)=u0, u(n+1)=f(u(n)).

The git checksum mechanism is a typical example of that kind of function. I would stick with the commonly-accepted term in the mathematical circle, which is usually intersecting with the computer science one.

For another version of a recurrence checksum, please see this paper on rolling checksum, used by rsync. However you can't generally call them rolling checksum as this algorithm is only a special case.

share|improve this answer
    
The funny thing is that usually checksum are defined using recurrence functions themselves. So a recurrence checksum is really a kind of "recurrence^2" function... –  Laurent Aug 30 '13 at 11:11
    
The relationship between recurrence and what's happening here is so tenuous that I wouldn't understand it if you didn't explain what you meant, and after explaining I find the name weird. Google shows that you're the only person to use that name. Iterated checksum sounds more logical but almost nobody has used it on the web and would only apply to checksums in a list form, not in a tree form. –  Gilles Aug 30 '13 at 11:49

You understand it correctly. A Git initial commit checksum can be used to identify the entire repo. I have never heard / seen an exact term for it. It's just a method of ensuring integrity, as you said.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.