aboutsummaryrefslogtreecommitdiff
path: root/crypto.c
diff options
context:
space:
mode:
Diffstat (limited to 'crypto.c')
-rw-r--r--crypto.c33
1 files changed, 30 insertions, 3 deletions
diff --git a/crypto.c b/crypto.c
index e8759d5..ce88d0f 100644
--- a/crypto.c
+++ b/crypto.c
@@ -113,6 +113,18 @@ hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t
return parent;
}
+/* Given a node's index, return the index of the parent in an array
+ * representation of a binary tree. */
+int bintree_parent(int idx)
+{
+ return (idx - ((idx & 1) ? 1 : 2)) / 2;
+}
+
+int bintree_sibling(int idx)
+{
+ return idx + ((idx & 1) ? 1 : -1);
+}
+
/* Calculate the indicies of the complementary nodes to a
* leaf. `leafidx' is 0 for the rightmost leaf node. This function
* will return an array with a length equal to the number of levels in
@@ -137,18 +149,33 @@ int *merkle_complement(int leafidx, int logleaves, int **orders)
for(int i = 0; i < logleaves; ++i)
{
/* output index of sibling node */
- comp[i] = idx + ((idx & 1) ? 1 : -1);
+ comp[i] = bintree_sibling(idx);
+ /* we really don't need the orders array */
if(orders)
- (*orders)[i] = ((idx&1) ? 1 : 0);
+ (*orders)[i] = idx & 1;
/* find parent index and loop */
- idx = (idx - ((idx & 1) ? 1 : 2)) / 2;
+ idx = bintree_parent(idx);
}
return comp;
}
+int *merkle_dependents(int leafidx, int logleaves)
+{
+ int *dep = calloc(logleaves, sizeof(int));
+
+ int idx = (1 << logleaves) - 1 + leafidx;
+ for(int i = 0; i < logleaves; ++i)
+ {
+ idx = bintree_parent(idx);
+ dep[i] = idx;
+ }
+
+ return dep;
+}
+
/* Shim to get only the orders */
int *merkle_complement_orders(int leafidx, int logleaves)
{