text: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
   * Institution: Technical University of Munich, Germany
   * Department:  Electrical and Computer Engineering
   * Group:       Embedded Systems and Internet of Things
   * 
   * Project:     Hash-based Signature
   * Authors:     Emanuel Regnath (emanuel.regnath@tum.de)
   *
   * Description: Models a Merkle Tree. Stores only some right nodes.
   *
   *  h=3                  root                d = 0
   *                   __/     \__           
   *  h=2          ⊕                r2         d = 1
   *             /   \            /   \      
   *  h=1      ⊕      r0        ⊕      r1      d = 2
   *          / \    / \      / \     / \    
   *  h=0    0  1   2   3    4   5   6   7     d = 3
   *                                    
   *   Fig 1: Merkle tree of height h and depth d   
   * 
   * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  
  #ifndef MERKLE_TREE_H_
  #define MERKLE_TREE_H_
  
  // system includes
  #include <stdint.h>
  
  // own includes
  #include "hash.h"
  #include "wots.h"
  
  
  // ============================================================================
  // public types
  // ============================================================================
  
  typedef void** MT_leafs_t;
  typedef uint16_t MT_index_t;
  
  
  typedef enum {
      MT_FRACTAL_ZERO,  // store all right nodes
      MT_FRACTAL_ONE,   // 
      MT_FRACTAL_HALF,
  } MT_Fractal_t;
  
  
  
  // this can be compressed to 2 byte
  typedef struct {
      HASH_Config cfg_hash;
      uint8_t height;
  } MT_Config;
  
  
  typedef struct {
      HASH_Config cfg_hash;
      uint8_t height;
      MT_index_t leaf_idx;
      hash_t* hashes;
  } MT_Path;
  
  
  typedef struct {
      HASH_Config cfg_hash;
      uint8_t height;
      uint32_t leaf_idx;
      bool is_full;
      hash_t* root;  // pointer to all hashes
      hash_t* right_nodes;
      hash_t* left_nodes;
  } MT_Subtree;
  
  
  typedef struct {
      MT_Config config;
      uint32_t leaf_idx;
      bool is_full;
      hash_t* root;
      MT_Subtree top;    // right-nodes top tree
      MT_Subtree exist;  // bottom existing tree
      MT_Subtree desire; // bottom desired tree
      //hash_t* leafs;     // additional leafs
  } MT_Tree;
  
  
  
  
  
  // ============================================================================
  // public functions
  // ============================================================================
  
  
  /**
   * Allocates and initializes a byte array suitable to store all hash values. 
   * \param[in] config struct that specifies height and hash algorithm
   * \param[in] levels specify the number of levels of the bottom subtree.
   *            Determines space requirements of the tree.
   * \return pointer to the MT_Tree struct
   */
  MT_Tree MT_init(const MT_Config* config, const MT_Fractal_t levels);
  
  
  /**
   * Allocates and initializes a MT_Path struct. 
   * \param[in] config struct that specifies height and hash algorithm
   * \return pointer to the MT_Path struct
   */
  MT_Path MT_init_path(const MT_Config* config);
  
  
  /**
   * Frees the memory of the merkle tree.
   * \param[in] tree pointer to the merkle tree.
   */
  void MT_free(MT_Tree* tree);
  
  
  /**
   * Frees the memory of the path.
   * \param[in] path pointer to the authentication path.
   */
  void MT_free_path(MT_Path* path);
  
  
  /**
   * Adds a new leaf hash to an unfinished tree. Automatically finalizes the
   * the tree when the (2^h)-th leaf is added. 
   * \param[in,out] tree pointer to the merkle tree. 
   * \param[in] leaf pointer to the hash that will be added as leaf
   */
  void MT_add(MT_Tree* tree, const hash_t* leaf);
  
  
  /**
   * Generates the path for the current leaf. Automatically iterate to the next leaf.
   * \param[in,out] tree pointer to the merkle tree.
   * \param[out] path pointer to the memory where the path will be stored.
   */
  void MT_generate_path(MT_Tree* tree, const hash_t* leaf, MT_Path* path);
  
  
  /**
   * Returns the leaf index that is needed to grow the tree.
   * \param[in,out] tree pointer to the merkle tree.
   * \return index of the leaf. 0 if growing is not necessary.
   */
  MT_index_t MT_get_grow_leaf_idx(MT_Tree* tree);
  
  
  /**
   * Grows the internal tree structure. This needs to be called in order to generate the next paths.
   * The passed leaf needs to be at the index given by MT_get_grow_leaf_idx()
   * \param[in,out] tree pointer to the merkle tree.
   * \param[in] next_leaf pointer to the hash of the next leaf. Must be stored or re-generated by the caller.
   */
  void MT_grow_dtree(MT_Tree* tree, const hash_t* leaf);
  
  
  
  /**
   * Generates the root hash from an authentication path.
   * \param[in] path pointer to the authentication path.
   * \param[in] leaf pointer to the hash of the leaf hash.
   * \param[in] leaf_idx index of the leaf.
   * \param[out] root root hash of the Merkle tree.
   */
  void MT_root_from_path(const MT_Path* path, const hash_t* leaf, const MT_index_t leaf_idx, hash_t* root);
  
  
  /**
   * Determines the size of the data that represents the Merkle tree.
   * return size of the Merkle tree in bytes.
   */
  size_t MT_sizeof_tree(const MT_Config config);
  
  #endif
  