Logo Search packages:      
Sourcecode: dc-qt version File versions  Download package

MerkleTree.h

Go to the documentation of this file.
/* 
 * Copyright (C) 2001-2005 Jacek Sieka, arnetheduck on gmail point com
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#ifndef _MERKLE_TREE
#define _MERKLE_TREE

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "TigerHash.h"
#include "Encoder.h"
#include "HashValue.h"

/**
 * A class that represents a Merkle Tree hash. Storing
 * only the leaves of the tree, it is rather memory efficient, 
 * but can still take a significant amount of memory during / after 
 * hash generation. 
 * The root hash produced can be used like any
 * other hash to verify the integrity of a whole file, while
 * the leaves provide checking of smaller parts of the file.
 */
template<class Hasher, size_t baseBlockSize = 1024>
00040 class MerkleTree {
public:
      enum { HASH_SIZE = Hasher::HASH_SIZE };
      enum { BASE_BLOCK_SIZE = baseBlockSize };

      typedef HashValue<Hasher> MerkleValue;
      typedef vector<MerkleValue> MerkleList;
      typedef typename MerkleList::iterator MerkleIter;

      MerkleTree() : fileSize(0), blockSize(baseBlockSize) { }
      MerkleTree(int64_t aBlockSize) : fileSize(0), blockSize(aBlockSize) { }

      /**
       * Loads a set of leaf hashes, calculating the root
       * @param data Pointer to (aFileSize + aBlockSize - 1) / aBlockSize) hash values,
       *             stored consecutively left to right
       */
00057       MerkleTree(int64_t aFileSize, int64_t aBlockSize, u_int8_t* aData) : 
            fileSize(aFileSize), blockSize(aBlockSize) 
      {
            size_t n = calcBlocks(aFileSize, aBlockSize);
            for(size_t i = 0; i < n; i++)
                  leaves.push_back(MerkleValue(aData + i * Hasher::HASH_SIZE));

            calcRoot();
      }

      /** Initialise a single root tree */
00068       MerkleTree(int64_t aFileSize, int64_t aBlockSize, const MerkleValue& aRoot) : root(aRoot), fileSize(aFileSize), blockSize(aBlockSize) {
            leaves.push_back(root);
      }

      ~MerkleTree() {
      }

      static int64_t calcBlockSize(int64_t aFileSize, int maxLevels) {
            int64_t tmp = baseBlockSize;
            int64_t maxHashes = ((int64_t)1) << (maxLevels - 1);
            while((maxHashes * tmp) < aFileSize)
                  tmp *= 2;
            return tmp;
      }

      static size_t calcBlocks(int64_t aFileSize, int64_t aBlockSize) {
            return max((size_t)((aFileSize + aBlockSize - 1) / aBlockSize), (size_t)1);
      }

      /**
       * Update the merkle tree.
       * @param len Length of data, must be a multiple of baseBlockSize, unless it's
       *            the last block.
       */
00092       void update(const void* data, size_t len) {
            u_int8_t* buf = (u_int8_t*)data;
            u_int8_t zero = 0;
            size_t i = 0;

            // Skip empty data sets if we already added at least one of them...
            if(len == 0 && !(leaves.empty() && blocks.empty()))
                  return;
            
            do {
                  size_t n = min(baseBlockSize, len-i);
                  Hasher h;
                  h.update(&zero, 1);
                  h.update(buf + i, n);
                  if((int64_t)baseBlockSize < blockSize) {
                        blocks.push_back(make_pair(MerkleValue(h.finalize()), baseBlockSize));
                        reduceBlocks();
                  } else {
                        leaves.push_back(MerkleValue(h.finalize()));
                  }
                  i += n;
            } while(i < len);
            fileSize += len;
      }

      u_int8_t* finalize() {
            while(blocks.size() > 1) {
                  MerkleBlock& a = blocks[blocks.size()-2];
                  MerkleBlock& b = blocks[blocks.size()-1];
                  a.first = combine(a.first, b.first);
                  blocks.pop_back();
            }
            dcassert(blocks.size() == 0 || blocks.size() == 1);
            if(!blocks.empty()) {
                  leaves.push_back(blocks[0].first);
            }
            calcRoot();
            return root.data;
      }

      MerkleValue& getRoot() { return root; }
      const MerkleValue& getRoot() const { return root; }
      MerkleList& getLeaves() { return leaves; }
      const MerkleList& getLeaves() const { return leaves; }

      int64_t getBlockSize() const { return blockSize; }
      void setBlockSize(int64_t aSize) { blockSize = aSize; }

      int64_t getFileSize() const { return fileSize; }
      void setFileSize(int64_t aSize) { fileSize = aSize; }

      bool verifyRoot(const u_int8_t* aRoot) {
            return memcmp(aRoot, getRoot().data(), HASH_SIZE) == 0;
      }

      void calcRoot() {
            root = getHash(0, fileSize);
      }

      vector<u_int8_t> getLeafData() {
            vector<u_int8_t> buf(getLeaves().size() * HASH_SIZE);
            u_int8_t* p = &buf[0];
            for(size_t i = 0; i < getLeaves().size(); ++i) {
                  memcpy(p + i * HASH_SIZE, &getLeaves()[i], HASH_SIZE);
            }
            return buf;
      }

private:    
      typedef pair<MerkleValue, int64_t> MerkleBlock;
      typedef vector<MerkleBlock> MBList;

      MBList blocks;

      MerkleList leaves;

      MerkleValue root;
      /** Total size of hashed data */
00170       int64_t fileSize;
      /** Final block size */
00172       int64_t blockSize;
      
      MerkleValue getHash(int64_t start, int64_t length) {
            dcassert((start % blockSize) == 0);
            if(length <= blockSize) {
                  dcassert((start / blockSize) < (int64_t)leaves.size());
                  return leaves[(u_int32_t)(start / blockSize)];
            } else {
                  int64_t l = blockSize;
                  while(l * 2 < length)
                        l *= 2;
                  return combine(getHash(start, l), getHash(start+l, length - l));
            }
      }

      MerkleValue combine(const MerkleValue& a, const MerkleValue& b) {
            u_int8_t one = 1;
            Hasher h;
            h.update(&one, 1);
            h.update(a.data, MerkleValue::SIZE);
            h.update(b.data, MerkleValue::SIZE);
            return MerkleValue(h.finalize());
      }

      void reduceBlocks() {
            while(blocks.size() > 1) {
                  MerkleBlock& a = blocks[blocks.size()-2];
                  MerkleBlock& b = blocks[blocks.size()-1];
                  if(a.second == b.second) {
                        if(a.second*2 == blockSize) {
                              leaves.push_back(combine(a.first, b.first));
                              blocks.pop_back();
                              blocks.pop_back();
                        } else {
                              a.second *= 2;
                              a.first = combine(a.first, b.first);
                              blocks.pop_back();
                        }
                  } else {
                        break;
                  }
            }
      }
};

typedef MerkleTree<TigerHash> TigerTree;
typedef TigerTree::MerkleValue TTHValue;

struct TTFilter {
      TTFilter(int64_t aBlockSize) : tt(aBlockSize) { };
      void operator()(const void* data, size_t len) { tt.update(data, len); }
      TigerTree& getTree() { tt.finalize(); return tt; }
private:
      TigerTree tt;
};

#endif // _MERKLE_TREE

/**
 * @file
 * $Id: MerkleTree.h,v 1.2 2005/08/21 14:03:43 olof Exp $
 */

Generated by  Doxygen 1.6.0   Back to index