WIP on database backend

10 files changed, 595 insertions, 177 deletions

diff --git a/client.c b/client.c
index bc947cd..7c057b1 100644
--- a/client.c
+++ b/client.c
@@ -326,12 +326,12 @@ static struct tm_request verify_and_sign(int fd, const struct user_request *req)
         if(tmr.type != ACL_UPDATE ||
            tmr.idx == 0 ||
            tmr.counter != 0 ||
-           !hash_equals(hash_node(&acl_node), tmr.val))
+           !hash_equals(hash_node(acl_node), tmr.val))
         {
             printf("Refusing to sign request because %d %d %d %d\n", tmr.type != ACL_UPDATE,
                    tmr.idx == 0,
                    tmr.counter != 0,
-                   !hash_equals(hash_node(&acl_node), tmr.val));
+                   !hash_equals(hash_node(acl_node), tmr.val));
             return req_null;
         }
         break;
diff --git a/crypto.h b/crypto.h
index b14dd45..e82bbbc 100644
--- a/crypto.h
+++ b/crypto.h
@@ -48,9 +48,6 @@ int *bintree_complement_ordersonly(int leafidx, int logleaves);
  * given leaf node. Will be ordered from nearest relative to root. */
 int *bintree_ancestors(int leafidx, int logleaves);
 
-hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n);
-void restore_nodes(hash_t *nodes, const int *indices, const hash_t *values, int n);
-
 int bintree_parent(int idx);
 int bintree_sibling(int idx);
 
diff --git a/helper.c b/helper.c
index 3310e94..b909707 100644
--- a/helper.c
+++ b/helper.c
@@ -11,16 +11,16 @@
 #include "trusted_module.h"
 
 struct tm_cert cert_ru(const struct trusted_module *tm,
-                       const struct iomt_node *node, hash_t new_val,
+                       struct iomt_node node, hash_t new_val,
                        const hash_t *comp, const int *orders, size_t n,
                        hash_t *hmac_out)
 {
-    struct iomt_node new_node = *node;
+    struct iomt_node new_node = node;
     new_node.val = new_val;
     hash_t nu_hmac;
     struct tm_cert nu = tm_cert_node_update(tm,
                                             hash_node(node),
-                                            hash_node(&new_node),
+                                            hash_node(new_node),
                                             comp, orders, n,
                                             &nu_hmac);
 
@@ -28,7 +28,7 @@ struct tm_cert cert_ru(const struct trusted_module *tm,
 }
 
 struct tm_cert cert_rv(const struct trusted_module *tm,
-                       const struct iomt_node *node,
+                       struct iomt_node node,
                        const hash_t *comp, const int *orders, size_t n,
                        hash_t *hmac_out,
                        uint64_t b,
@@ -54,9 +54,9 @@ struct tm_cert cert_rv_by_idx(const struct trusted_module *tm,
                               hash_t *hmac_out)
 {
     uint64_t leafidx;
-    struct iomt_node *node = iomt_find_leaf_or_encloser(tree, idx, &leafidx);
+    struct iomt_node node = iomt_find_leaf_or_encloser(tree, idx, &leafidx);
 
-    if(!node)
+    if(!node.idx)
         return cert_null;
 
     /* find the complement */
@@ -65,7 +65,7 @@ struct tm_cert cert_rv_by_idx(const struct trusted_module *tm,
 
     struct tm_cert cert;
 
-    if(idx == node->idx)
+    if(idx == node.idx)
     {
         /* node exists */
         cert = cert_rv(tm,
@@ -97,19 +97,19 @@ struct tm_cert cert_rv_by_idx(const struct trusted_module *tm,
  * the ACL. */
 struct tm_request req_filecreate(const struct trusted_module *tm,
                                  uint64_t user_id,
-                                 const struct iomt_node *file_node,
+                                 struct iomt_node file_node,
                                  const hash_t *file_comp, const int *file_orders, size_t file_n)
 {
     /* construct a request to create a file */
     struct tm_request req = req_null;
-    req.idx = file_node->idx;
+    req.idx = file_node.idx;
     req.user_id = user_id;
     req.type = ACL_UPDATE;
     req.counter = 0;
 
     /* construct ACL with a single element (the user, with full access) */
     struct iomt_node acl_node = (struct iomt_node) { user_id, user_id, u64_to_hash(3) };
-    req.val = merkle_compute(hash_node(&acl_node), NULL, NULL, 0);
+    req.val = merkle_compute(hash_node(acl_node), NULL, NULL, 0);
 
     hash_t one = u64_to_hash(1);
 
@@ -133,21 +133,21 @@ struct tm_request req_filecreate(const struct trusted_module *tm,
  * contents, given the previously generated FR certificate, and the
  * ACL node giving the user's access rights. */
 struct tm_request req_filemodify(const struct trusted_module *tm,
-                                   const struct tm_cert *fr_cert, hash_t fr_hmac,
-                                   const struct iomt_node *file_node,
-                                   const hash_t *file_comp, const int *file_orders, size_t file_n,
-                                   const struct iomt_node *acl_node,
-                                   const hash_t *acl_comp, const int *acl_orders, size_t acl_n,
-                                   hash_t fileval)
+                                 const struct tm_cert *fr_cert, hash_t fr_hmac,
+                                 struct iomt_node file_node,
+                                 const hash_t *file_comp, const int *file_orders, size_t file_n,
+                                 struct iomt_node acl_node,
+                                 const hash_t *acl_comp, const int *acl_orders, size_t acl_n,
+                                 hash_t fileval)
 {
     /* modification */
     struct tm_request req = req_null;
     req.type = FILE_UPDATE;
 
-    req.idx = file_node->idx;
-    req.counter = hash_to_u64(file_node->val);
+    req.idx = file_node.idx;
+    req.counter = hash_to_u64(file_node.val);
 
-    req.user_id = acl_node->idx;
+    req.user_id = acl_node.idx;
 
     req.modify.fr_cert = *fr_cert;
     req.modify.fr_hmac = fr_hmac;
@@ -172,20 +172,20 @@ struct tm_request req_filemodify(const struct trusted_module *tm,
  * parameters as req_filemodify(), except the hash is the root of the
  * new ACL. */
 struct tm_request req_aclmodify(const struct trusted_module *tm,
-                                  const struct tm_cert *fr_cert, hash_t fr_hmac,
-                                  const struct iomt_node *file_node,
-                                  const hash_t *file_comp, const int *file_orders, size_t file_n,
-                                  const struct iomt_node *oldacl_node,
-                                  const hash_t *oldacl_comp, const int *oldacl_orders, size_t oldacl_n,
-                                  hash_t newacl_root)
+                                const struct tm_cert *fr_cert, hash_t fr_hmac,
+                                struct iomt_node file_node,
+                                const hash_t *file_comp, const int *file_orders, size_t file_n,
+                                struct iomt_node oldacl_node,
+                                const hash_t *oldacl_comp, const int *oldacl_orders, size_t oldacl_n,
+                                hash_t newacl_root)
 {
     struct tm_request req = req_null;
     req.type = ACL_UPDATE;
 
-    req.idx = file_node->idx;
-    req.counter = hash_to_u64(file_node->val);
+    req.idx = file_node.idx;
+    req.counter = hash_to_u64(file_node.val);
 
-    req.user_id = oldacl_node->idx;
+    req.user_id = oldacl_node.idx;
 
     req.modify.fr_cert = *fr_cert;
     req.modify.fr_hmac = fr_hmac;
diff --git a/helper.h b/helper.h
index 1ad948e..7cdbf61 100644
--- a/helper.h
+++ b/helper.h
@@ -2,12 +2,12 @@
 #include "crypto.h"
 
 struct tm_cert cert_ru(const struct trusted_module *tm,
-                       const struct iomt_node *node, hash_t new_val,
+                       struct iomt_node node, hash_t new_val,
                        const hash_t *comp, const int *orders, size_t n,
                        hash_t *hmac_out);
 
 struct tm_cert cert_rv(const struct trusted_module *tm,
-                       const struct iomt_node *node,
+                       struct iomt_node node,
                        const hash_t *comp, const int *orders, size_t n,
                        hash_t *hmac_out,
                        uint64_t b,
@@ -26,7 +26,7 @@ struct tm_cert cert_rv_by_idx(const struct trusted_module *tm,
  * the ACL. */
 struct tm_request req_filecreate(const struct trusted_module *tm,
                                  uint64_t user_id,
-                                 const struct iomt_node *file_node,
+                                 struct iomt_node file_node,
                                  const hash_t *file_comp, const int *file_orders, size_t file_n);
 
 /* Fill out a tm_request struct to modify an existing file's
@@ -34,9 +34,9 @@ struct tm_request req_filecreate(const struct trusted_module *tm,
  * ACL node giving the user's access rights. */
 struct tm_request req_filemodify(const struct trusted_module *tm,
                                  const struct tm_cert *fr_cert, hash_t fr_hmac,
-                                 const struct iomt_node *file_node,
+                                 struct iomt_node file_node,
                                  const hash_t *file_comp, const int *file_orders, size_t file_n,
-                                 const struct iomt_node *acl_node,
+                                 struct iomt_node acl_node,
                                  const hash_t *acl_comp, const int *acl_orders, size_t acl_n,
                                  hash_t fileval);
 
@@ -45,8 +45,8 @@ struct tm_request req_filemodify(const struct trusted_module *tm,
  * new ACL. */
 struct tm_request req_aclmodify(const struct trusted_module *tm,
                                 const struct tm_cert *fr_cert, hash_t fr_hmac,
-                                const struct iomt_node *file_node,
+                                struct iomt_node file_node,
                                 const hash_t *file_comp, const int *file_orders, size_t file_n,
-                                const struct iomt_node *oldacl_node,
+                                struct iomt_node oldacl_node,
                                 const hash_t *oldacl_comp, const int *oldacl_orders, size_t oldacl_n,
                                 hash_t newacl_root);
diff --git a/iomt.c b/iomt.c
index c6fff04..0e3a353 100644
--- a/iomt.c
+++ b/iomt.c
@@ -1,45 +1,307 @@
 #include "iomt.h"
 #include "crypto.h"
 
+#include <assert.h>
 #include <string.h>
 
 #include <openssl/hmac.h>
 #include <openssl/sha.h>
 
-hash_t hash_node(const struct iomt_node *node)
+#include <sqlite3.h>
+
+hash_t hash_node(const struct iomt_node node)
 {
-    return sha256(node, sizeof(*node));
+    return sha256(&node, sizeof(node));
 }
 
 /* internal nodes only */
 hash_t iomt_getnode(const struct iomt *tree, int idx)
 {
     if(tree->in_memory)
-        return tree->mt_nodes[idx];
+        return tree->mem.mt_nodes[idx];
+    else
+    {
+        sqlite3 *handle = tree->db.db;
+
+        char sql[1000];
+        if(tree->db.key1_name)
+        {
+            if(tree->db.key2_name)
+            {
+                snprintf(sql, sizeof(sql), "SELECT Val FROM %s WHERE %s = ?3 AND %s = ?5 AND NodeIdx = ?6;",
+                         tree->db.nodes_table,
+                         tree->db.key1_name,
+                         tree->db.key2_name);
+            }
+            else
+                snprintf(sql, sizeof(sql), "SELECT Val FROM %s WHERE %s = ?3 AND NodeIdx = ?6;",
+                         tree->db.nodes_table,
+                         tree->db.key1_name);
+        }
+        else
+            snprintf(sql, sizeof(sql), "SELECT Val FROM %s NodeIdx = ?6;",
+                     tree->db.nodes_table);
+
+        sqlite3_stmt *st;
+
+        sqlite3_prepare_v2(handle, sql, -1, &st, 0);
+
+        if(tree->db.key1_name)
+        {
+            sqlite3_bind_int(st, 3, tree->db.key1_val);
+
+            if(tree->db.key2_name)
+            {
+                sqlite3_bind_int(st, 5, tree->db.key2_val);
+            }
+        }
+
+        sqlite3_bind_int(st, 6, idx);
+
+        int rc = sqlite3_step(st);
+        if(rc == SQLITE_ROW)
+        {
+            hash_t ret;
+            memcpy(&ret, sqlite3_column_blob(st, 0), sizeof(ret));
+
+            return ret;
+        }
+        else
+        {
+            printf("Failed 0: %s\n", sqlite3_errmsg(handle));
+            printf("Failed to look up node %d in table %s\n", idx, tree->db.nodes_table);
+            return hash_null;
+        }
+    }
 }
 
+/* TODO: work out insert/delete/update details */
 void iomt_setnode(const struct iomt *tree, int idx, hash_t val)
 {
     if(tree->in_memory)
-        tree->mt_nodes[idx] = val;
+        tree->mem.mt_nodes[idx] = val;
+    else
+    {
+        printf("Setting node idx = %d in %s\n", idx, tree->db.nodes_table);
+
+        sqlite3 *handle = tree->db.db;
+
+        char sql[1000];
+        if(tree->db.key1_name)
+        {
+            if(tree->db.key2_name)
+            {
+                snprintf(sql, sizeof(sql), "UPDATE %s SET Val = ?2 WHERE %s = ?4 AND %s = ?6 AND NodeIdx = ?7;",
+                         tree->db.nodes_table,
+                         tree->db.key1_name,
+                         tree->db.key2_name);
+            }
+            else
+                snprintf(sql, sizeof(sql), "UPDATE %s SET Val = ?2 WHERE %s = ?4 AND NodeIdx = ?7;",
+                         tree->db.nodes_table,
+                         tree->db.key1_name);
+        }
+        else
+            snprintf(sql, sizeof(sql), "UPDATE %s SET Val = ?2 WHERE NodeIdx = ?7;",
+                     tree->db.nodes_table);
+
+        sqlite3_stmt *st;
+
+        sqlite3_prepare_v2(handle, sql, -1, &st, 0);
+        sqlite3_bind_blob(st, 2, &val, sizeof(val), SQLITE_TRANSIENT);
+
+        if(tree->db.key1_name)
+        {
+            sqlite3_bind_int(st, 4, tree->db.key1_val);
+
+            if(tree->db.key2_name)
+            {
+                sqlite3_bind_int(st, 6, tree->db.key2_val);
+            }
+        }
+
+        sqlite3_bind_int(st, 7, idx);
+
+        int rc = sqlite3_step(st);
+
+        sqlite3_finalize(st);
+
+        /* Failure, likely because node doesn't exist */
+        if(rc != SQLITE_DONE)
+        {
+            printf("Update failed, inserting...\n");
+            if(tree->db.key1_name)
+            {
+                if(tree->db.key2_name)
+                    snprintf(sql, sizeof(sql), "INSERT INTO %s ( NodeIdx, Val, %s, %s ) VALUES ( ?4, ?5, ?6, ?7 );",
+                             tree->db.nodes_table,
+                             tree->db.key1_name,
+                             tree->db.key2_name);
+                else
+                    snprintf(sql, sizeof(sql), "INSERT INTO %s ( NodeIdx, Val, %s ) VALUES ( ?4, ?5, ?6 );",
+                             tree->db.nodes_table,
+                             tree->db.key1_name);
+            }
+            else
+                snprintf(sql, sizeof(sql), "INSERT INTO %s ( NodeIdx, Val ) VALUES ( ?4, ?5 );",
+                         tree->db.nodes_table);
+
+            sqlite3_prepare_v2(handle, sql, -1, &st, 0);
+
+            sqlite3_bind_int(st, 4, idx);
+            sqlite3_bind_blob(st, 5, &val, sizeof(val), SQLITE_TRANSIENT);
+
+            if(sqlite3_step(st) != SQLITE_DONE)
+            {
+                printf("Failed 1: %s\n", sqlite3_errmsg(tree->db.db));
+            }
+
+            sqlite3_finalize(st);
+        }
+    }
 }
 
 struct iomt_node iomt_getleaf(const struct iomt *tree, uint64_t leafidx)
 {
     if(tree->in_memory)
-        return tree->mt_leaves[leafidx];
+        return tree->mem.mt_leaves[leafidx];
+    else
+    {
+        sqlite3 *handle = tree->db.db;
+
+        const char *sql = tree->db.key2_name ?
+            "SELECT Idx, NextIdx, Val FROM ?1 WHERE ?2 = ?3 AND ?4 = ?5 AND LeafIdx = ?6;" :
+            (tree->db.key1_name ?
+             "SELECT Idx, NextIdx, Val FROM ?1 WHERE ?2 = ?3 AND LeafIdx = ?6;" :
+             "SELECT Idx, NextIdx, Val FROM ?1 WHERE LeafIdx = ?6;");
+
+        sqlite3_stmt *st;
+
+        sqlite3_prepare_v2(handle, sql, -1, &st, 0);
+        sqlite3_bind_text(st, 1, tree->db.leaves_table, -1, SQLITE_TRANSIENT);
+
+        if(tree->db.key1_name)
+        {
+            sqlite3_bind_text(st, 2, tree->db.key1_name, -1, SQLITE_TRANSIENT);
+            sqlite3_bind_int(st, 3, tree->db.key1_val);
+
+            if(tree->db.key2_name)
+            {
+                sqlite3_bind_text(st, 4, tree->db.key2_name, -1, SQLITE_TRANSIENT);
+                sqlite3_bind_int(st, 5, tree->db.key2_val);
+            }
+        }
+
+        sqlite3_bind_int(st, 6, leafidx);
+
+        int rc = sqlite3_step(st);
+        if(rc == SQLITE_ROW)
+        {
+            struct iomt_node ret;
+
+            ret.idx = sqlite3_column_int(st, 0);
+            ret.next_idx = sqlite3_column_int(st, 1);
+            memcpy(&ret.val, sqlite3_column_blob(st, 2), sizeof(ret.val));
+
+            return ret;
+        }
+        else
+        {
+            printf("Failed 2: %s\n", sqlite3_errmsg(tree->db.db));
+            printf("Failed to look up leaf %d in %s\n", leafidx, tree->db.leaves_table);
+            return node_null;
+        }
+    }
 }
 
 void iomt_setleaf(struct iomt *tree, uint64_t leafidx, struct iomt_node val)
 {
     if(tree->in_memory)
-        tree->mt_leaves[leafidx] = val;
+        tree->mem.mt_leaves[leafidx] = val;
+    else
+    {
+        printf("Setting leaf idx = %d in %s\n", leafidx, tree->db.leaves_table);
+
+        sqlite3 *handle = tree->db.db;
+
+        const char *sql = tree->db.key2_name ?
+            "UPDATE ?1 SET Idx = ?2, NextIdx = ?3, Val = ?4 WHERE ?5 = ?6 AND ?7 = ?8 AND LeafIdx = ?9;" :
+            (tree->db.key1_name ?
+             "UPDATE ?1 SET Idx = ?2, NextIdx = ?3, Val = ?4 WHERE ?5 = ?6 AND LeafIdx = ?9;" :
+             "UPDATE ?1 SET Idx = ?2, NextIdx = ?3, Val = ?4 WHERE LeafIdx = ?9;");
+
+        sqlite3_stmt *st;
+
+        sqlite3_prepare_v2(handle, sql, -1, &st, 0);
+        sqlite3_bind_text(st, 1, tree->db.leaves_table, -1, SQLITE_TRANSIENT);
+        sqlite3_bind_int(st, 2, val.idx);
+        sqlite3_bind_int(st, 3, val.next_idx);
+        sqlite3_bind_blob(st, 4, &val.val, sizeof(val.val), SQLITE_TRANSIENT);
+
+        if(tree->db.key1_name)
+        {
+            sqlite3_bind_text(st, 5, tree->db.key1_name, -1, SQLITE_TRANSIENT);
+            sqlite3_bind_int(st, 6, tree->db.key1_val);
+        }
+
+        if(tree->db.key2_name)
+        {
+            sqlite3_bind_text(st, 7, tree->db.key2_name, -1, SQLITE_TRANSIENT);
+            sqlite3_bind_int(st, 8, tree->db.key2_val);
+        }
+
+        sqlite3_bind_int(st, 9, leafidx);
+
+        int rc = sqlite3_step(st);
+
+        sqlite3_finalize(st);
+
+        /* Failure, likely because node doesn't exist */
+        if(rc != SQLITE_DONE)
+        {
+            printf("Update failed, inserting...\n");
+
+            const char *sql2 = tree->db.key2_name ?
+                "INSERT INTO ?1 ( LeafIdx, Idx, NextIdx, Val, ?2, ?3 ) VALUES ( ?5, ?6, ?7, ?8, ?9, ?10 );" :
+                (tree->db.key1_name ?
+                 "INSERT INTO ?1 ( LeafIdx, Idx, NextIdx, Val, ?2 ) VALUES ( ?5, ?6, ?7, ?8, ?9 );" :
+                 "INSERT INTO ?1 ( LeafIdx, Idx, NextIdx, Val ) VALUES ( ?5, ?6, ?7, ?8 );");
+
+            sqlite3_prepare_v2(handle, sql2, -1, &st, 0);
+
+            sqlite3_bind_text(st, 1, tree->db.nodes_table, -1, SQLITE_TRANSIENT);
+
+            if(tree->db.key1_name)
+            {
+                sqlite3_bind_text(st, 2, tree->db.key1_name, -1, SQLITE_TRANSIENT);
+                sqlite3_bind_int(st, 9, tree->db.key1_val);
+            }
+
+            if(tree->db.key2_name)
+            {
+                sqlite3_bind_text(st, 3, tree->db.key2_name, -1, SQLITE_TRANSIENT);
+                sqlite3_bind_int(st, 10, tree->db.key2_val);
+            }
+
+            sqlite3_bind_int(st, 5, leafidx);
+            sqlite3_bind_int(st, 6, val.idx);
+            sqlite3_bind_int(st, 7, val.next_idx);
+            sqlite3_bind_blob(st, 8, &val.val, sizeof(val.val), SQLITE_TRANSIENT);
+
+            if(sqlite3_step(st) != SQLITE_DONE)
+            {
+                printf("Failed 3: %s\n", sqlite3_errmsg(handle));
+            }
+
+            sqlite3_finalize(st);
+        }
+    }
 }
 
 hash_t *merkle_complement(const struct iomt *tree, int leafidx, int **orders)
 {
     int *compidx = bintree_complement(leafidx, tree->mt_logleaves, orders);
-    hash_t *comp = lookup_nodes(tree->mt_nodes, compidx, tree->mt_logleaves);
+    hash_t *comp = lookup_nodes(tree, compidx, tree->mt_logleaves);
     free(compidx);
     return comp;
 }
@@ -54,7 +316,7 @@ void iomt_fill(struct iomt *tree)
     for(int i = 0; i < tree->mt_leafcount; ++i)
     {
         uint64_t mt_idx = (1 << tree->mt_logleaves) - 1 + i;
-        iomt_setnode(tree, mt_idx, hash_node(tree->mt_leaves + i));
+        iomt_setnode(tree, mt_idx, hash_node(iomt_getleaf(tree, i)));
     }
     /* now loop up from the bottom level, calculating the parent of
      * each pair of nodes */
@@ -79,18 +341,18 @@ void iomt_fill(struct iomt *tree)
  * to modify each function to take the array of all nodes in the tree
  * in addition to the complement indices, but this function will serve
  * as a shim in the meantime. */
-hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n)
+hash_t *lookup_nodes(const struct iomt *tree, const int *indices, int n)
 {
     hash_t *ret = calloc(n, sizeof(hash_t));
     for(int i = 0; i < n; ++i)
-        ret[i] = nodes[indices[i]];
+        ret[i] = iomt_getnode(tree, indices[i]);
     return ret;
 }
 
-void restore_nodes(hash_t *nodes, const int *indices, const hash_t *values, int n)
+void restore_nodes(struct iomt *tree, const int *indices, const hash_t *values, int n)
 {
     for(int i = 0; i < n; ++i)
-        nodes[indices[i]] = values[i];
+        iomt_setnode(tree, indices[i], values[i]);
 }
 
 /* Update mt_nodes to reflect a change to a leaf node's
@@ -118,63 +380,64 @@ void merkle_update(struct iomt *tree, uint64_t leafidx, hash_t newval, hash_t **
 
         /* save old value */
         if(old_dep)
-            (*old_dep)[i] = iomt_getnode(tree, mt_nodes[idx]);
+            (*old_dep)[i] = iomt_getnode(tree, idx);
 
-        tree->mt_nodes[idx] = parent;
+        iomt_setnode(tree, idx, parent);
     }
 }
 
 hash_t iomt_getroot(const struct iomt *tree)
 {
-    return tree->mt_nodes[0];
+    return tree->mem.mt_nodes[0];
 }
 
 /* find a node with given idx */
-struct iomt_node *iomt_find_leaf(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
+struct iomt_node iomt_find_leaf(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
 {
     for(int i = 0; i < tree->mt_leafcount; ++i)
-        if(idx == tree->mt_leaves[i].idx)
+        if(idx == iomt_getleaf(tree, i).idx)
         {
             if(leafidx)
                 *leafidx = i;
-            return tree->mt_leaves + i;
+            return tree->mem.mt_leaves[i];
         }
-    return NULL;
+    return node_null;
 }
 
-struct iomt_node *iomt_find_encloser(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
+struct iomt_node iomt_find_encloser(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
 {
     for(int i = 0; i < tree->mt_leafcount; ++i)
-        if(encloses(tree->mt_leaves[i].idx, tree->mt_leaves[i].next_idx, idx))
+        if(encloses(iomt_getleaf(tree, i).idx, iomt_getleaf(tree, i).next_idx, idx))
         {
             if(leafidx)
                 *leafidx = i;
-            return tree->mt_leaves + i;
+            return tree->mem.mt_leaves[i];
         }
-    return NULL;
+    return node_null;
 }
 
-struct iomt_node *iomt_find_leaf_or_encloser(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
+struct iomt_node iomt_find_leaf_or_encloser(const struct iomt *tree, uint64_t idx, uint64_t *leafidx)
 {
     for(int i = 0; i < tree->mt_leafcount; ++i)
     {
-        if(tree->mt_leaves[i].idx == idx ||
-           encloses(tree->mt_leaves[i].idx, tree->mt_leaves[i].next_idx, idx))
+        if(iomt_getleaf(tree, i).idx == idx ||
+           encloses(iomt_getleaf(tree, i).idx, iomt_getleaf(tree, i).next_idx, idx))
         {
             if(leafidx)
                 *leafidx = i;
-            return tree->mt_leaves + i;
+            return tree->mem.mt_leaves[i];
         }
     }
-    return NULL;
+    return node_null;
 }
 
 void iomt_update(struct iomt *tree, uint64_t idx, hash_t newval)
 {
     /* update the leaf first, then use merkle_update */
     uint64_t leafidx;
-    struct iomt_node *leaf = iomt_find_leaf(tree, idx, &leafidx);
-    leaf->val = newval;
+    struct iomt_node leaf = iomt_find_leaf(tree, idx, &leafidx);
+    leaf.val = newval;
+    iomt_setleaf(tree, leafidx, leaf);
 
     merkle_update(tree, leafidx, hash_node(leaf), NULL);
 }
@@ -182,10 +445,8 @@ void iomt_update(struct iomt *tree, uint64_t idx, hash_t newval)
 void iomt_update_leaf_full(struct iomt *tree, uint64_t leafidx,
                            uint64_t new_idx, uint64_t new_next_idx, hash_t new_val)
 {
-    struct iomt_node *leaf = tree->mt_leaves + leafidx;
-    leaf->idx = new_idx;
-    leaf->next_idx = new_next_idx;
-    leaf->val = new_val;
+    struct iomt_node leaf = (struct iomt_node) { new_idx, new_next_idx, new_val };
+    iomt_setleaf(tree, leafidx, leaf);
 
     merkle_update(tree, leafidx, hash_node(leaf), NULL);
 }
@@ -193,8 +454,10 @@ void iomt_update_leaf_full(struct iomt *tree, uint64_t leafidx,
 void iomt_update_leaf_idx(struct iomt *tree, uint64_t leafidx,
                           uint64_t new_idx)
 {
-    struct iomt_node *leaf = tree->mt_leaves + leafidx;
-    leaf->idx = new_idx;
+    struct iomt_node leaf = iomt_getleaf(tree, leafidx);
+    leaf.idx = new_idx;
+
+    iomt_setleaf(tree, leafidx, leaf);
 
     merkle_update(tree, leafidx, hash_node(leaf), NULL);
 }
@@ -202,8 +465,10 @@ void iomt_update_leaf_idx(struct iomt *tree, uint64_t leafidx,
 void iomt_update_leaf_nextidx(struct iomt *tree, uint64_t leafidx,
                               uint64_t new_next_idx)
 {
-    struct iomt_node *leaf = tree->mt_leaves + leafidx;
-    leaf->next_idx = new_next_idx;
+    struct iomt_node leaf = iomt_getleaf(tree, leafidx);
+    leaf.next_idx = new_next_idx;
+
+    iomt_setleaf(tree, leafidx, leaf);
 
     merkle_update(tree, leafidx, hash_node(leaf), NULL);
 }
@@ -211,8 +476,10 @@ void iomt_update_leaf_nextidx(struct iomt *tree, uint64_t leafidx,
 void iomt_update_leaf_hash(struct iomt *tree, uint64_t leafidx,
                            hash_t new_val)
 {
-    struct iomt_node *leaf = tree->mt_leaves + leafidx;
-    leaf->val = new_val;
+    struct iomt_node leaf = iomt_getleaf(tree, leafidx);
+    leaf.val = new_val;
+
+    iomt_setleaf(tree, leafidx, leaf);
 
     merkle_update(tree, leafidx, hash_node(leaf), NULL);
 }
@@ -227,9 +494,33 @@ struct iomt *iomt_new(int logleaves)
 
     tree->mt_leafcount = 1 << logleaves;
     tree->mt_logleaves = logleaves;
-    tree->mt_leaves = calloc(tree->mt_leafcount, sizeof(struct iomt_node));
+    tree->mem.mt_leaves = calloc(tree->mt_leafcount, sizeof(struct iomt_node));
 
-    tree->mt_nodes = calloc(2 * tree->mt_leafcount - 1, sizeof(hash_t));
+    tree->mem.mt_nodes = calloc(2 * tree->mt_leafcount - 1, sizeof(hash_t));
+
+    return tree;
+}
+
+struct iomt *iomt_new_from_db(void *db,
+                              const char *nodes_table, const char *leaves_table,
+                              const char *key1_name, int key1_val,
+                              const char *key2_name, int key2_val,
+                              int logleaves)
+{
+    struct iomt *tree = calloc(1, sizeof(struct iomt));
+
+    tree->in_memory = false;
+
+    tree->mt_leafcount = 1 << logleaves;
+    tree->mt_logleaves = logleaves;
+
+    tree->db.db = db;
+    tree->db.nodes_table = nodes_table;
+    tree->db.leaves_table = leaves_table;
+    tree->db.key1_name = key1_name;
+    tree->db.key1_val = key1_val;
+    tree->db.key2_name = key2_name;
+    tree->db.key2_val = key2_val;
 
     return tree;
 }
@@ -242,11 +533,11 @@ struct iomt *iomt_dup(const struct iomt *tree)
     newtree->mt_leafcount = tree->mt_leafcount;
     newtree->mt_logleaves = tree->mt_logleaves;
 
-    newtree->mt_leaves = calloc(tree->mt_leafcount, sizeof(struct iomt_node));
-    memcpy(newtree->mt_leaves, tree->mt_leaves, tree->mt_leafcount * sizeof(struct iomt_node));
+    newtree->mem.mt_leaves = calloc(tree->mt_leafcount, sizeof(struct iomt_node));
+    memcpy(newtree->mem.mt_leaves, tree->mem.mt_leaves, tree->mt_leafcount * sizeof(struct iomt_node));
 
-    newtree->mt_nodes = calloc(2 * tree->mt_leafcount - 1, sizeof(hash_t));
-    memcpy(newtree->mt_nodes, tree->mt_nodes, (2 * tree->mt_leafcount - 1) * sizeof(hash_t));
+    newtree->mem.mt_nodes = calloc(2 * tree->mt_leafcount - 1, sizeof(hash_t));
+    memcpy(newtree->mem.mt_nodes, tree->mem.mt_nodes, (2 * tree->mt_leafcount - 1) * sizeof(hash_t));
 
     return newtree;
 }
@@ -280,8 +571,7 @@ void iomt_serialize(const struct iomt *tree,
     {
         write_u64(write_fn, userdata, tree->mt_logleaves);
 
-        write_fn(userdata, tree->mt_nodes, sizeof(hash_t) * (2 * tree->mt_leafcount - 1));
-        write_fn(userdata, tree->mt_leaves, sizeof(struct iomt_node) * tree->mt_leafcount);
+        write_fn(userdata, tree->mem.mt_leaves, sizeof(struct iomt_node) * tree->mt_leafcount);
     }
     else
         write_u64(write_fn, userdata, IOMT_EMPTY);
@@ -297,8 +587,9 @@ struct iomt *iomt_deserialize(int (*read_fn)(void *userdata, void *buf, size_t l
 
     struct iomt *tree = iomt_new(logleaves);
 
-    read_fn(userdata, tree->mt_nodes, sizeof(hash_t) * (2 * tree->mt_leafcount - 1));
-    read_fn(userdata, tree->mt_leaves, sizeof(struct iomt_node) * tree->mt_leafcount);
+    read_fn(userdata, tree->mem.mt_leaves, sizeof(struct iomt_node) * tree->mt_leafcount);
+
+    iomt_fill(tree);
 
     return tree;
 }
@@ -307,8 +598,8 @@ void iomt_free(struct iomt *tree)
 {
     if(tree)
     {
-        free(tree->mt_nodes);
-        free(tree->mt_leaves);
+        free(tree->mem.mt_nodes);
+        free(tree->mem.mt_leaves);
         free(tree);
     }
 }
@@ -368,14 +659,14 @@ struct iomt *iomt_from_lines(const char *filename)
 
 void iomt_dump(const struct iomt *tree)
 {
-    if(tree)
+    if(tree && tree->in_memory)
     {
         for(int i = 0; i < tree->mt_leafcount; ++i)
         {
             printf("(%lu, %s, %lu)%s",
-                   tree->mt_leaves[i].idx,
-                   hash_format(tree->mt_leaves[i].val, 4).str,
-                   tree->mt_leaves[i].next_idx,
+                   tree->mem.mt_leaves[i].idx,
+                   hash_format(tree->mem.mt_leaves[i].val, 4).str,
+                   tree->mem.mt_leaves[i].next_idx,
                    (i == tree->mt_leafcount - 1) ? "\n" : ", ");
         }
     }
diff --git a/iomt.h b/iomt.h
index 8ccd0dc..2162bd6 100644
--- a/iomt.h
+++ b/iomt.h
@@ -7,43 +7,51 @@ struct iomt_node {
     hash_t val; /* all zero indicates placeholder */
 };
 
+/* indices cannot be zero */
+static const struct iomt_node node_null = { 0, 0, hash_null };
+
+/* Each level of the IOMT is stored sequentially from left to
+ * right, top to bottom, as follows:
+ *
+ *  [0]: root
+ *  [1]: root left child
+ *  [2]: root right child
+ *  [3]: left child of [1]
+ *  [4]: right child of [1]
+ *  [5]: left child of [2]
+ *  [6]: right child of [2],
+ *
+ * and so on.
+ */
 struct iomt {
-    bool in_memory;
-
-    void *db;
-    const char *nodes_table, leaves_table;
-
-    /* the IOMT code will use nodes with key1_name = key1_val and (if
-     * not NULL) key2_name = key2_val */
-    const char *key1_name, *key2_name;
-    int key1_val, key2_val;
-
     int mt_leafcount, mt_logleaves; /* mt_logleaves must equal 2^mt_leafcount */
 
-    /* The following members are valid only if in_memory ==
-     * true... really should use a union here: */
-
-    /* Each level of the IOMT is stored sequentially from left to
-     * right, top to bottom, as follows:
-     *
-     *  [0]: root
-     *  [1]: root left child
-     *  [2]: root right child
-     *  [3]: left child of [1]
-     *  [4]: right child of [1]
-     *  [5]: left child of [2]
-     *  [6]: right child of [2],
-     *
-     * and so on.
-     */
-    hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note
-                       * that the bottom level consists of hashes of
-                       * the leaf nodes. */
-
-    struct iomt_node *mt_leaves;
+    bool in_memory;
+
+    union {
+        struct {
+            void *db;
+            const char *nodes_table, *leaves_table;
+
+            /* the IOMT code will use nodes with key1_name = key1_val and (if
+             * not NULL) key2_name = key2_val */
+            const char *key1_name, *key2_name;
+            int key1_val, key2_val;
+        } db;
+        struct {
+            hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note
+                               * that the bottom level consists of hashes of
+                               * the leaf nodes. */
+
+            struct iomt_node *mt_leaves;
+        } mem;
+    };
 };
 
-hash_t hash_node(const struct iomt_node *node);
+hash_t hash_node(struct iomt_node node);
+
+hash_t *lookup_nodes(const struct iomt *tree, const int *indices, int n);
+void restore_nodes(struct iomt *tree, const int *indices, const hash_t *values, int n);
 
 hash_t *merkle_complement(const struct iomt *tree, int leafidx, int **orders);
 
diff --git a/service_provider.c b/service_provider.c
index 62efa09..baa8f88 100644
--- a/service_provider.c
+++ b/service_provider.c
@@ -70,25 +70,25 @@ struct service_provider {
  * node. It is the 0-based index of the POSITION of the leaf node,
  * counting from the leftmost leaf. */
 struct tm_cert cert_eq(struct service_provider *sp,
-                       const struct iomt_node *encloser,
+                       struct iomt_node encloser,
                        uint64_t encloser_leafidx,
                        uint64_t placeholder_leafidx, uint64_t placeholder_nodeidx,
                        hash_t *hmac_out)
 {
-    assert(encloses(encloser->idx, encloser->next_idx, placeholder_nodeidx));
+    assert(encloses(encloser.idx, encloser.next_idx, placeholder_nodeidx));
 
-    struct iomt_node encloser_mod = *encloser;
+    struct iomt_node encloser_mod = encloser;
     encloser_mod.next_idx = placeholder_nodeidx;
 
     struct iomt_node insert;
     insert.idx = placeholder_nodeidx;
-    insert.next_idx = encloser->next_idx;
+    insert.next_idx = encloser.next_idx;
     insert.val = hash_null;
 
     hash_t h_enc    = hash_node(encloser);
-    hash_t h_encmod = hash_node(&encloser_mod);
+    hash_t h_encmod = hash_node(encloser_mod);
 
-    hash_t h_ins = hash_node(&insert);
+    hash_t h_ins = hash_node(insert);
 
     int *enc_orders;
     hash_t *enc_comp = merkle_complement(sp->iomt, encloser_leafidx, &enc_orders);
@@ -115,7 +115,7 @@ struct tm_cert cert_eq(struct service_provider *sp,
 
     /* restore the tree */
     int *dep_indices = bintree_ancestors(encloser_leafidx, sp->iomt->mt_logleaves);
-    restore_nodes(sp->iomt->mt_nodes, dep_indices, old_depvalues, sp->iomt->mt_logleaves);
+    restore_nodes(sp->iomt, dep_indices, old_depvalues, sp->iomt->mt_logleaves);
 
     free(dep_indices);
     free(old_depvalues);
@@ -159,7 +159,11 @@ struct service_provider *sp_new(const void *key, size_t keylen, int logleaves)
 
     sp->tm = tm_new(key, keylen);
 
-    sp->iomt = iomt_new(logleaves);
+    sp->iomt = iomt_new_from_db(sp->db,
+                                "FileNodes", "FileLeaves",
+                                NULL, 0,
+                                NULL, 0,
+                                logleaves);
 
     /* The trusted module initializes itself with a single placeholder
      * node (1,0,1). We first update our list of IOMT leaves. Then we
@@ -179,7 +183,7 @@ struct service_provider *sp_new(const void *key, size_t keylen, int logleaves)
                                     i - 1,
                                     i, i + 1,
                                     &hmac);
-        assert(eq.type == EQ);
+        //assert(eq.type == EQ);
 
         /* update previous leaf's index */
         iomt_update_leaf_nextidx(sp->iomt, i - 1, i + 1);
@@ -189,7 +193,7 @@ struct service_provider *sp_new(const void *key, size_t keylen, int logleaves)
          * next node, if any */
         iomt_update_leaf_full(sp->iomt, i, i + 1, 1, hash_null);
 
-        assert(tm_set_equiv_root(sp->tm, &eq, hmac));
+        //assert(tm_set_equiv_root(sp->tm, &eq, hmac));
     }
 
     return sp;
@@ -237,7 +241,11 @@ static struct file_record *lookup_record(struct service_provider *sp, uint64_t i
         memcpy(&rec->fr_hmac, sqlite3_column_blob(st, 4), sizeof(rec->fr_hmac));
 
         int acl_logleaves = sqlite3_column_int(st, 5);
-        rec->acl = iomt_new_from_db(sp->db, "ACLNodes", "ACLLeaves", acl_logleaves);
+        rec->acl = iomt_new_from_db(sp->db,
+                                    "ACLNodes", "ACLLeaves",
+                                    "FileIdx", idx,
+                                    NULL, 0,
+                                    acl_logleaves);
     }
     return NULL;
 }
@@ -284,7 +292,7 @@ static void update_record(struct service_provider *sp,
     sqlite3_bind_blob(st, 4, &rec->fr_cert, sizeof(rec->fr_cert), SQLITE_TRANSIENT);
     sqlite3_bind_blob(st, 5, &rec->fr_hmac, sizeof(rec->fr_hmac), SQLITE_TRANSIENT);
     sqlite3_bind_int(st, 6, rec->acl->mt_logleaves);
-    sqlite3_bind_int(st, 6, rec->idx);
+    sqlite3_bind_int(st, 7, rec->idx);
 
     assert(sqlite3_step(st) == SQLITE_DONE);
 
@@ -360,8 +368,16 @@ static struct file_version *lookup_version(struct service_provider *sp,
 
         int bc_logleaves = sqlite3_column_int(st, 6);
         int cf_logleaves = sqlite3_column_int(st, 7);
-        ver->buildcode = iomt_new_from_db(sp->db, "BCNodes", "BCLeaves", bc_logleaves);
-        ver->composefile = iomt_new_from_db(sp->db, "CFNodes", "CFLeaves", cf_logleaves);
+        ver->buildcode = iomt_new_from_db(sp->db,
+                                          "BCNodes", "BCLeaves",
+                                          "FileIdx", file_idx,
+                                          "Version", version,
+                                          bc_logleaves);
+        ver->composefile = iomt_new_from_db(sp->db,
+                                            "CFNodes", "CFLeaves",
+                                            "FileIdx", file_idx,
+                                            "Version", version,
+                                            cf_logleaves);
     }
     return NULL;
 }
@@ -521,7 +537,12 @@ struct tm_request sp_createfile(struct service_provider *sp,
     int *file_orders;
     hash_t *file_comp = merkle_complement(sp->iomt, i, &file_orders);
 
-    struct iomt *acl = iomt_new(ACL_LOGLEAVES);
+    struct iomt *acl = iomt_new_from_db(sp->db,
+                                        "ACLNodes", "ACLLeaves",
+                                        "FileIdx", i,
+                                        NULL, 0,
+                                        ACL_LOGLEAVES);
+
     iomt_update_leaf_full(acl,
                            0,
                            user_id, user_id, u64_to_hash(3));
@@ -570,14 +591,14 @@ struct tm_request sp_modifyacl(struct service_provider *sp,
 
     int *file_orders, *acl_orders;
     uint64_t file_leafidx;
-    struct iomt_node *file_node = iomt_find_leaf(sp->iomt, file_idx, &file_leafidx);
+    struct iomt_node file_node = iomt_find_leaf(sp->iomt, file_idx, &file_leafidx);
 
     hash_t *file_comp = merkle_complement(sp->iomt,
                                           file_leafidx,
                                           &file_orders);
 
     uint64_t acl_leafidx;
-    struct iomt_node *acl_node = iomt_find_leaf(rec->acl, user_id, &acl_leafidx);
+    struct iomt_node acl_node = iomt_find_leaf(rec->acl, user_id, &acl_leafidx);
     hash_t *acl_comp = merkle_complement(rec->acl,
                                          acl_leafidx,
                                          &acl_orders);
@@ -632,14 +653,14 @@ struct tm_request sp_modifyfile(struct service_provider *sp,
 
     int *file_orders, *acl_orders;
     uint64_t file_leafidx;
-    struct iomt_node *file_node = iomt_find_leaf(sp->iomt, file_idx, &file_leafidx);
+    struct iomt_node file_node = iomt_find_leaf(sp->iomt, file_idx, &file_leafidx);
 
     hash_t *file_comp = merkle_complement(sp->iomt,
                                           file_leafidx,
                                           &file_orders);
 
     uint64_t acl_leafidx;
-    struct iomt_node *acl_node = iomt_find_leaf(rec->acl, user_id, &acl_leafidx);
+    struct iomt_node acl_node = iomt_find_leaf(rec->acl, user_id, &acl_leafidx);
     hash_t *acl_comp = merkle_complement(rec->acl,
                                          acl_leafidx,
                                          &acl_orders);
@@ -648,12 +669,12 @@ struct tm_request sp_modifyfile(struct service_provider *sp,
     hash_t lambda = calc_lambda(gamma, buildcode, composefile, kf);
 
     struct tm_request req = req_filemodify(sp->tm,
-                                             &rec->fr_cert, rec->fr_hmac,
-                                             file_node,
-                                             file_comp, file_orders, sp->iomt->mt_logleaves,
-                                             acl_node,
-                                             acl_comp, acl_orders, rec->acl->mt_logleaves,
-                                             lambda);
+                                           &rec->fr_cert, rec->fr_hmac,
+                                           file_node,
+                                           file_comp, file_orders, sp->iomt->mt_logleaves,
+                                           acl_node,
+                                           acl_comp, acl_orders, rec->acl->mt_logleaves,
+                                           lambda);
     free(file_comp);
     free(acl_comp);
     free(file_orders);
@@ -1037,7 +1058,7 @@ static hash_t test_sign_request(void *userdata, const struct tm_request *req)
 
 void sp_test(void)
 {
-    int logleaves = 5;
+    int logleaves = 1;
     printf("Initializing IOMT with %llu nodes.\n", 1ULL << logleaves);
 
     clock_t start = clock();
@@ -1060,10 +1081,10 @@ void sp_test(void)
         struct iomt_node node1 = { 1, 2, sha256("line1\n", 6) };
         struct iomt_node node2 = { 2, 1, sha256("line2", 5) };
 
-        hash_t correct_root = merkle_parent(hash_node(&node1), hash_node(&node2), 0);
+        hash_t correct_root = merkle_parent(hash_node(node1), hash_node(node2), 0);
         check("IOMT generation from file 2", hash_equals(iomt_getroot(buildcode), correct_root));
 
-#define N_MODIFY 100
+#define N_MODIFY 1
         start = clock();
         for(int i = 0; i < N_MODIFY; ++i)
             req = sp_modifyfile(sp, 1, test_sign_request, "a", 1, hash_null, hash_null, buildcode, NULL, "contents", 8, &ack_hmac);
@@ -1097,7 +1118,7 @@ void sp_test(void)
 
         struct iomt_node acl_node = { 1, 1, u64_to_hash(3) };
 
-        struct version_info correct = { 1, N_MODIFY + 1, 1, N_MODIFY, hash_node(&acl_node), lambda };
+        struct version_info correct = { 1, N_MODIFY + 1, 1, N_MODIFY, hash_node(acl_node), lambda };
         check("File info retrieval 2", !memcmp(&correct, &vi, sizeof(vi)));
     }
 
@@ -1156,7 +1177,7 @@ void sp_test(void)
     {
         struct iomt_node a = { 1, 2, u64_to_hash(2) };
         struct iomt_node b = { 2, 1, hash_null };
-        check("Merkle tree initialization", hash_equals(iomt_getroot(sp->iomt), merkle_parent(hash_node(&a), hash_node(&b), 0)));
+        check("Merkle tree initialization", hash_equals(iomt_getroot(sp->iomt), merkle_parent(hash_node(a), hash_node(b), 0)));
     }
 
     sp_free(sp);
diff --git a/sqlinit.txt b/sqlinit.txt
new file mode 100644
index 0000000..b5c5196
--- /dev/null
+++ b/sqlinit.txt
@@ -0,0 +1,101 @@
+CREATE TABLE FileRecords (
+Idx INTEGER,
+Ver INTEGER,
+Ctr INTEGER,
+Cert BLOB,
+HMAC BLOB,
+ACL_logleaves INTEGER
+);
+
+CREATE TABLE FileLeaves (
+FileIdx INTEGER,
+LeafIdx INTEGER,
+Idx INTEGER,
+NextIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, LeafIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx)
+);
+
+CREATE TABLE FileNodes (
+FileIdx INTEGER,
+NodeIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, NodeIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx)
+);
+
+CREATE TABLE Versions (
+FileIdx INTEGER,
+Version INTEGER,
+KF BLOB,
+encrypted_secret BLOB,
+Cert BLOB,
+HMAC BLOB,
+Buildcode_logleaves INTEGER,
+Composefile_logleaves INTEGER,
+PRIMARY KEY (FileIdx, Version),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx)
+);
+
+CREATE TABLE ACLLeaves (
+FileIdx INTEGER,
+LeafIdx INTEGER,
+Idx INTEGER,
+NextIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, LeafIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx)
+);
+
+CREATE TABLE ACLNodes (
+FileIdx INTEGER,
+NodeIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, NodeIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx)
+);
+
+CREATE TABLE BCLeaves (
+FileIdx INTEGER,
+Version INTEGER,
+LeafIdx INTEGER,
+Idx INTEGER,
+NextIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, Version, LeafIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx),
+FOREIGN KEY (Version) REFERENCES Versions(Version)
+);
+
+CREATE TABLE BCNodes (
+FileIdx INTEGER,
+Version INTEGER,
+Val BLOB,
+NodeIdx INTEGER,
+PRIMARY KEY (FileIdx, Version, NodeIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx),
+FOREIGN KEY (Version) REFERENCES Versions(Version)
+);
+
+CREATE TABLE CFLeaves (
+FileIdx INTEGER,
+Version INTEGER,
+LeafIdx INTEGER,
+Idx INTEGER,
+NextIdx INTEGER,
+Val BLOB,
+PRIMARY KEY (FileIdx, Version, LeafIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx),
+FOREIGN KEY (Version) REFERENCES Versions(Version)
+);
+
+CREATE TABLE CFNodes (
+FileIdx INTEGER,
+Version INTEGER,
+Val BLOB,
+NodeIdx INTEGER,
+PRIMARY KEY (FileIdx, Version, NodeIdx),
+FOREIGN KEY (FileIdx) REFERENCES FileRecords(Idx),
+FOREIGN KEY (Version) REFERENCES Versions(Version)
+);
diff --git a/trusted_module.c b/trusted_module.c
index 59cc503..b90046c 100644
--- a/trusted_module.c
+++ b/trusted_module.c
@@ -62,7 +62,7 @@ struct trusted_module *tm_new(const void *key, size_t keylen)
     /* initialize with a node of (1, 0, 1) in the tree */
     struct iomt_node boot = (struct iomt_node) { 1, 1, hash_null };
 
-    tm_setroot(tm, merkle_compute(hash_node(&boot), NULL, NULL, 0));
+    tm_setroot(tm, merkle_compute(hash_node(boot), NULL, NULL, 0));
 
     return tm;
 }
@@ -170,7 +170,7 @@ struct tm_cert tm_cert_combine(const struct trusted_module *tm,
 struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
                              const struct tm_cert *nu_encl, hash_t hmac_encl,
                              const struct tm_cert *nu_ins,  hash_t hmac_ins,
-                             const struct iomt_node *encloser,
+                             struct iomt_node encloser,
                              uint64_t a, hash_t *hmac_out)
 {
     if(!nu_encl || !nu_ins)
@@ -188,7 +188,7 @@ struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
         tm_seterror("invalid authentication");
         return cert_null;
     }
-    if(!encloses(encloser->idx, encloser->next_idx, a))
+    if(!encloses(encloser.idx, encloser.next_idx, a))
     {
         tm_seterror("encloser does not actually enclose placeholder index");
         return cert_null;
@@ -200,16 +200,16 @@ struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
     }
 
     hash_t ve = hash_node(encloser);
-    struct iomt_node encloser_mod = *encloser;
+    struct iomt_node encloser_mod = encloser;
     encloser_mod.next_idx = a;
-    hash_t veprime = hash_node(&encloser_mod);
+    hash_t veprime = hash_node(encloser_mod);
 
     struct iomt_node ins;
     ins.idx = a;
-    ins.next_idx = encloser->next_idx;
+    ins.next_idx = encloser.next_idx;
     memset(ins.val.hash, 0, sizeof(ins.val.hash));
 
-    hash_t viprime = hash_node(&ins);
+    hash_t viprime = hash_node(ins);
 
     if(!hash_equals(nu_encl->nu.orig_node, ve))
     {
@@ -249,7 +249,7 @@ struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
  * y */
 struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
                                      const struct tm_cert *nu, hash_t hmac,
-                                     const struct iomt_node *node,
+                                     struct iomt_node node,
                                      hash_t *hmac_out,
                                      uint64_t b,
                                      struct tm_cert *nonexist,
@@ -279,7 +279,7 @@ struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
     /* issue a certificate verifying that no node with index b exists as a child of y */
     if(b > 0 && nonexist && hmac_nonexist)
     {
-        if(encloses(node->idx, node->next_idx, b))
+        if(encloses(node.idx, node.next_idx, b))
         {
             *nonexist = cert_null;
             nonexist->type = RV;
@@ -301,8 +301,8 @@ struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
 
     cert.type = RV;
     cert.rv.root = nu->nu.orig_root;
-    cert.rv.idx = node->idx;
-    cert.rv.val = node->val;
+    cert.rv.idx = node.idx;
+    cert.rv.val = node.val;
 
     /* can be NULL */
     if(hmac_out)
@@ -312,7 +312,7 @@ struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
 
 struct tm_cert tm_cert_record_update(const struct trusted_module *tm,
                                      const struct tm_cert *nu, hash_t nu_hmac,
-                                     const struct iomt_node *node,
+                                     struct iomt_node node,
                                      hash_t new_val,
                                      hash_t *hmac_out)
 {
@@ -334,10 +334,10 @@ struct tm_cert tm_cert_record_update(const struct trusted_module *tm,
 
     hash_t orig_h = hash_node(node);
 
-    struct iomt_node new_node = *node;
+    struct iomt_node new_node = node;
     new_node.val = new_val;
 
-    hash_t new_h = hash_node(&new_node);
+    hash_t new_h = hash_node(new_node);
 
     if(!hash_equals(nu->nu.orig_node, orig_h) || !hash_equals(nu->nu.new_node, new_h))
     {
@@ -348,8 +348,8 @@ struct tm_cert tm_cert_record_update(const struct trusted_module *tm,
     struct tm_cert cert = cert_null;
 
     cert.type = RU;
-    cert.ru.idx = node->idx;
-    cert.ru.orig_val = node->val;
+    cert.ru.idx = node.idx;
+    cert.ru.orig_val = node.val;
     cert.ru.new_val = new_val;
     cert.ru.orig_root = nu->nu.orig_root;
     cert.ru.new_root = nu->nu.new_root;
diff --git a/trusted_module.h b/trusted_module.h
index f764ad0..6fca40a 100644
--- a/trusted_module.h
+++ b/trusted_module.h
@@ -139,7 +139,7 @@ struct tm_cert tm_cert_combine(const struct trusted_module *tm,
 struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
                              const struct tm_cert *nu_encl, hash_t hmac_encl,
                              const struct tm_cert *nu_ins,  hash_t hmac_ins,
-                             const struct iomt_node *encloser,
+                             struct iomt_node encloser,
                              uint64_t a, hash_t *hmac_out);
 
 /* nu must be of the form [x,y,x,y] to indicate that x is a child of y */
@@ -148,7 +148,7 @@ struct tm_cert tm_cert_equiv(const struct trusted_module *tm,
  * y*/
 struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
                                      const struct tm_cert *nu, hash_t hmac,
-                                     const struct iomt_node *node,
+                                     struct iomt_node node,
                                      hash_t *hmac_out,
                                      uint64_t b,
                                      struct tm_cert *nonexist,
@@ -156,7 +156,7 @@ struct tm_cert tm_cert_record_verify(const struct trusted_module *tm,
 
 struct tm_cert tm_cert_record_update(const struct trusted_module *tm,
                                      const struct tm_cert *nu, hash_t nu_hmac,
-                                     const struct iomt_node *node,
+                                     struct iomt_node node,
                                      hash_t new_val,
                                      hash_t *hmac_out);