CVS commit: othersrc/external/bsd/hashtree

["Alistair G. Crooks" <agc%netbsd.org@localhost>]

Module Name:    othersrc
Committed By:   agc
Date:           Tue Jun 21 14:51:38 UTC 2011

Update of /cvsroot/othersrc/external/bsd/hashtree
In directory ivanova.netbsd.org:/tmp/cvs-serv26431

Log Message:
Initial import of hashtree functions into othersrc.

The hashtree, or Merkle tree algorithms, split a file up into blocks,
and calculate a message digest on those blocks.  Subsequent digests
are concatenated onto the previous digests.  If there is more than one
digest calculated, a higher level of digest is then calculated across
the lower-order digests, to provide a tree-like structure of message
digests.

If there is only one digest calculated, then the hashtree in this
degenerate case is the same as the digets of the file.

        % hashtree -n 1 dist/hashtree.c
        HASHTREE/sha1/1/10358/10358 (dist/hashtree.c) = 
253f185d39783fd29ca6a7936fee4b50e3775f39
        % sha1 dist/hashtree.c
        SHA1 (dist/hashtree.c) = 253f185d39783fd29ca6a7936fee4b50e3775f39
        %

hashtree(1) can be used to specify the hashing algorithm used
(including hmac algorithms), and the size of the blocks. 

        % hashtree -b 4096 dist/hashtree.c
        HASHTREE/sha1/2/10358/4096 (dist/hashtree.c) = 
1a958db53705b1ef4ef4e7418f7aa6e25226c4468783684b4ff3d152a66a38e7ad3e5c8d88ad0851b5f916e7d015015c6e0ddf0cef4cf7af2d48a0ad6db45855c61ea5454b579221bcbeeb5e282e626d
        %

Alternatively, the number of desired blocks can be specified, and
hashtree will work out the block size from that parameter and the size
of the file.  By default, a blocksize of 1024 is used.  There is the
possibility of producing very large digests using hashtree(1):

        % hashtree dist/hashtree.c
        HASHTREE/sha1/2/10358/1024 (dist/hashtree.c) = 
6a765d5809534fa75fd2f4f2f88168e65cb1182f91ac14db77b0052ae083743c10ed0ccea98ebf44a945eb72ee0303a8b5b89a2a590ec2e684418942bae3e0be34567bd12721167239fdf641c24ec51b59426924a32760adf11370aca375d60a97364613f93e1e44f848a3557c141b7422aa7e63fef99ff4e056124513c228c9a33e0dff08e6baa2903f959f428dd60f9a6390b0d4108d0826713d33ab6e5520fe20e61ac700659eb5e6a1cf5653da05d65c0d792cd3affaadd037372cfbf7085e14caea50dd89e2790cd982824fec985e2a97fcbbc415e91c27dc4f3089ec446784262269677aa1736fba2e5a768114

Merkle trees can be used to implement Lamport's signature scheme - see

        http://www.rsa.com/rsalabs/node.asp?id=2003

and there are also uses in ZFS:

        http://blogs.oracle.com/bonwick/entry/zfs_end_to_end_data

(although indirect pointers can be a tad difficult here?)

Hash trees are written up more generally in:

        http://en.wikipedia.org/wiki/Hash_tree

There are also uses of the tiger algorithm being used to produce more
specific "tiger trees".

Status:

Vendor Tag:     CROOKS
Release Tags:   hashtree-base
                
N othersrc/external/bsd/hashtree/Makefile
N othersrc/external/bsd/hashtree/dist/hashtree.c
N othersrc/external/bsd/hashtree/dist/Makefile
N othersrc/external/bsd/hashtree/dist/TODO
N othersrc/external/bsd/hashtree/dist/libhashtree.3
N othersrc/external/bsd/hashtree/dist/hashtree.h
N othersrc/external/bsd/hashtree/dist/main.c
N othersrc/external/bsd/hashtree/dist/hashtree.1
N othersrc/external/bsd/hashtree/hashtree/Makefile
N othersrc/external/bsd/hashtree/libhashtree/Makefile
N othersrc/external/bsd/hashtree/libhashtree/shlib_version

No conflicts created by this import