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
