common: generalize BOLT12 merkle generation.

diff --git a/common/bolt12_merkle.c b/common/bolt12_merkle.c
index f4a1374b..0b2bd586 100644
--- a/common/bolt12_merkle.c
+++ b/common/bolt12_merkle.c
@@ -1,8 +1,10 @@
 #include "config.h"
 #include <assert.h>
 #include <bitcoin/tx.h>
+#include <ccan/array_size/array_size.h>
 #include <ccan/cast/cast.h>
 #include <ccan/ilog/ilog.h>
+#include <ccan/mem/mem.h>
 #include <common/bolt12_merkle.h>
 #include <common/utils.h>
 
@@ -62,7 +64,7 @@ static void h_simpletag_ctx(struct sha256_ctx *sctx, const char *tag)
  */
 
 /* Create a sha256_ctx which has the tag part done. */
-static void h_lnnonce_ctx(struct sha256_ctx *sctx, const struct tlv_field *fields)
+void bolt12_lnnonce_ctx(struct sha256_ctx *sctx, const struct tlv_field *field)
 {
 	struct sha256_ctx inner_sctx;
 	struct sha256 sha;
@@ -70,8 +72,7 @@ static void h_lnnonce_ctx(struct sha256_ctx *sctx, const struct tlv_field *field
 	sha256_init(&inner_sctx);
 	sha256_update(&inner_sctx, "LnNonce", 7);
 	SUPERVERBOSE("tag=SHA256(%s", tal_hexstr(tmpctx, "LnNonce", 7));
-	assert(tal_count(fields));
-	sha256_update_tlvfield(&inner_sctx, &fields[0]);
+	sha256_update_tlvfield(&inner_sctx, field);
 	sha256_done(&inner_sctx, &sha);
 	SUPERVERBOSE(") -> %s\n",
 		     fmt_sha256(tmpctx, &sha));
@@ -82,15 +83,16 @@ static void h_lnnonce_ctx(struct sha256_ctx *sctx, const struct tlv_field *field
 }
 
 /* Use h_lnnonce_ctx to create nonce */
-static void calc_nonce(const struct sha256_ctx *lnnonce_ctx,
-		       const struct tlv_field *field,
-		       struct sha256 *hash)
+void bolt12_calc_nonce(const struct sha256_ctx *lnnonce_ctx,
+		       bigsize_t fieldtype,
+		       struct sha256 *hash,
+		       void *unused)
 {
 	/* Copy context, to add field */
 	struct sha256_ctx ctx = *lnnonce_ctx;
 
 	SUPERVERBOSE("nonce: H(noncetag,");
-	sha256_update_bigsize(&ctx, field->numtype);
+	sha256_update_bigsize(&ctx, fieldtype);
 
 	sha256_done(&ctx, hash);
 	SUPERVERBOSE(") = %s\n", fmt_sha256(tmpctx, hash));
@@ -111,15 +113,14 @@ static void calc_lnleaf(const struct tlv_field *field, struct sha256 *hash)
 /* BOLT #12:
  * The Merkle tree inner nodes are H("LnBranch", lesser-SHA256||greater-SHA256)
  */
-static struct sha256 *merkle_pair(const tal_t *ctx,
-				  const struct sha256 *a, const struct sha256 *b)
+static struct sha256 merkle_pair(const struct sha256 *a, const struct sha256 *b)
 {
-	struct sha256 *res;
+	struct sha256 res;
 	struct sha256_ctx sctx;
 
 	/* Make sure a < b */
 	if (memcmp(a->u.u8, b->u.u8, sizeof(a->u.u8)) > 0)
-		return merkle_pair(ctx, b, a);
+		return merkle_pair(b, a);
 
 	SUPERVERBOSE("branch: H(");
 	h_simpletag_ctx(&sctx, "LnBranch");
@@ -129,68 +130,192 @@ static struct sha256 *merkle_pair(const tal_t *ctx,
 	sha256_update(&sctx, a->u.u8, sizeof(a->u.u8));
 	sha256_update(&sctx, b->u.u8, sizeof(b->u.u8));
 
-	res = tal(ctx, struct sha256);
-	sha256_done(&sctx, res);
-	SUPERVERBOSE(") -> %s\n", fmt_sha256(tmpctx, res));
+	sha256_done(&sctx, &res);
+	SUPERVERBOSE(") -> %s\n", fmt_sha256(tmpctx, &res));
 	return res;
 }
 
-static const struct sha256 *merkle_recurse(const struct sha256 **base,
-					   const struct sha256 **arr, size_t len)
+/* Compute the leaf-pair hash for a TLV field: merkle_pair(H("LnLeaf",f), nonce) */
+static void calc_leaf_pair(const struct sha256_ctx *lnnonce_ctx,
+			   const struct tlv_field *f,
+			   struct sha256 *hash,
+			   void *unused)
 {
-	const struct sha256 *left, *right;
+	struct sha256 leafhash, nonce;
+	calc_lnleaf(f, &leafhash);
+	bolt12_calc_nonce(lnnonce_ctx, f->numtype, &nonce, NULL);
+	*hash = merkle_pair(&leafhash, &nonce);
+}
+
+/* Omitted nodes in the tree are represented by all-0 hashes */
+static bool is_omitted(const struct sha256 *hash)
+{
+	return memeqzero(hash->u.u8, ARRAY_SIZE(hash->u.u8));
+}
+
+static struct sha256 make_omitted(void)
+{
+	struct sha256 hash;
+	memset(hash.u.u8, 0, ARRAY_SIZE(hash.u.u8));
+	assert(is_omitted(&hash));
+	return hash;
+}
+
+/* Compute the actual (non-omitted) subtree hash for all entries in arr[0..len-1].
+ * Used by the creator to find the real hash of an omitted subtree. */
+static struct sha256 *compute_actual_subtree(struct sha256 **base,
+					     struct sha256 **arr, size_t len)
+{
+	struct sha256 *left, *right, *ret;
+
+	if (len == 1)
+		return arr[0];
+	left = compute_actual_subtree(base, arr, len / 2);
+	right = compute_actual_subtree(base, arr + len / 2, len / 2);
+	if (!right)
+		return left;
+	ret = tal(base, struct sha256);
+	*ret = merkle_pair(left, right);
+	return ret;
+}
+
+static struct sha256 *merkle_recurse(struct sha256 **base,
+				     struct sha256 **arr,
+				     struct sha256 **actual_arr,
+				     size_t len,
+				     void (*resolve_omitted)(struct sha256 *, void *),
+				     void *arg)
+
+{
+	struct sha256 *left, *right;
+	struct sha256 *ret;
+	bool left_omitted, right_omitted;
 	if (len == 1)
 		return arr[0];
 
 	SUPERVERBOSE("Merkle recurse [%zu - %zu] and [%zu - %zu]\n",
 		     arr - base, arr + len / 2 - 1 - base,
 		     arr + len / 2 - base, arr + len - 1 - base);
-	left = merkle_recurse(base, arr, len / 2);
-	right = merkle_recurse(base, arr + len / 2, len / 2);
+	left = merkle_recurse(base, arr, actual_arr, len / 2, resolve_omitted, arg);
+	right = merkle_recurse(base, arr + len / 2,
+			       actual_arr ? actual_arr + len / 2 : NULL,
+			       len / 2, resolve_omitted, arg);
 	/* left is never NULL if right is not NULL */
 	if (!right) {
 		SUPERVERBOSE("[%zu - %zu] is NULL!\n",
 			     arr + len / 2 - base, arr + len - base);
 		return left;
 	}
-	return merkle_pair(base, left, right);
+	ret = tal(base, struct sha256);
+	left_omitted = is_omitted(left);
+	right_omitted = is_omitted(right);
+	if (left_omitted && right_omitted) {
+		*ret = make_omitted();
+		return ret;
+	}
+	if (left_omitted) {
+		if (actual_arr)
+			*left = *compute_actual_subtree(base, actual_arr, len / 2);
+		resolve_omitted(left, arg);
+	} else if (right_omitted) {
+		if (actual_arr)
+			*right = *compute_actual_subtree(base, actual_arr + len / 2, len / 2);
+		resolve_omitted(right, arg);
+	}
+
+	*ret = merkle_pair(left, right);
+	return ret;
+}
+
+struct leaf_iter {
+	const struct tlv_field *fields;
+	size_t n;
+};
+
+static const struct tlv_field *next_field(bool *is_omitted, struct leaf_iter *iter)
+{
+	if (iter->n >= tal_count(iter->fields))
+		return NULL;
+	*is_omitted = false;
+	return &iter->fields[iter->n++];
 }
 
 /* This is not the fastest way, but it is the most intuitive. */
-void merkle_tlv(const struct tlv_field *fields, struct sha256 *merkle)
+void merkle_tlv_full_(struct sha256 *merkle,
+		      const struct tlv_field *(*next_field)(bool *, void *),
+		      void (*calc_nonce)(const struct sha256_ctx *lnnonce_ctx,
+					 bigsize_t fieldtype,
+					 struct sha256 *hash, void *),
+		      void (*resolve_omitted)(struct sha256 *, void *),
+		      void *arg)
 {
-	struct sha256 **arr;
+	const struct tlv_field *f;
+	struct sha256 **leaves, **actual_leaves, *ret;
 	struct sha256_ctx lnnonce_ctx;
-	size_t n;
+	bool omitted;
 
 	SUPERVERBOSE("nonce tag:");
-	h_lnnonce_ctx(&lnnonce_ctx, fields);
+
+	leaves = tal_arr(NULL, struct sha256 *, 0);
+	actual_leaves = tal_arr(leaves, struct sha256 *, 0);
+	while ((f = next_field(&omitted, arg)) != NULL) {
+		struct sha256 leaf;
+
+		/* First field is used as nonce to initialize the lnnonce_ctx */
+		if (tal_count(leaves) == 0)
+			bolt12_lnnonce_ctx(&lnnonce_ctx, f);
+
+		if (is_signature_field(f))
+			continue;
+
+		if (omitted) {
+			struct sha256 actual_leaf;
+			leaf = make_omitted();
+			calc_leaf_pair(&lnnonce_ctx, f, &actual_leaf, NULL);
+			tal_arr_expand(&actual_leaves,
+				       tal_dup(actual_leaves, struct sha256, &actual_leaf));
+		} else {
+			struct sha256 leafhash, nonce;
+
+			calc_lnleaf(f, &leafhash);
+			calc_nonce(&lnnonce_ctx, f->numtype, &nonce, arg);
+			leaf = merkle_pair(&leafhash, &nonce);
+			tal_arr_expand(&actual_leaves,
+				       tal_dup(actual_leaves, struct sha256, &leaf));
+		}
+		tal_arr_expand(&leaves, tal_dup(leaves, struct sha256, &leaf));
+	}
+	/* No fields means we don't have nonce. */
+	assert(tal_count(leaves) != 0);
 
 	/* We build an oversized power-of-2 symmentic tree, but with
 	 * NULL nodes at the end.  When we recurse, we pass through
 	 * NULL.  This is less efficient than calculating the
 	 * power-of-2 split as we recurse, but simpler. */
-	arr = tal_arrz(NULL, struct sha256 *,
-		       1ULL << ilog64(tal_count(fields)));
+	tal_resizez(&leaves, 1ULL << ilog64(tal_count(leaves)));
+	tal_resizez(&actual_leaves, tal_count(leaves));
 
-	n = 0;
-	for (size_t i = 0; i < tal_count(fields); i++) {
-		struct sha256 leaf, nonce;
-		if (is_signature_field(&fields[i]))
-			continue;
-		calc_lnleaf(&fields[i], &leaf);
-		calc_nonce(&lnnonce_ctx, &fields[i], &nonce);
-		arr[n++] = merkle_pair(arr, &leaf, &nonce);
+	ret = merkle_recurse(leaves, leaves, actual_leaves, tal_count(leaves),
+			     resolve_omitted, arg);
+	if (!ret) {
+		/* This should never happen, but define it a distinctive all-zeroes */
+		*merkle = make_omitted();
+	} else {
+		/* Cannot *all* be omitted! */
+		*merkle = *ret;
+		assert(!is_omitted(merkle));
 	}
+	tal_free(leaves);
+}
+
+void merkle_tlv(const struct tlv_field *fields, struct sha256 *merkle)
+{
+	struct leaf_iter iter;
+
+	iter.fields = fields;
+	iter.n = 0;
 
-	/* This should never happen, but define it a distinctive all-zeroes */
-	if (n == 0)
-		memset(merkle, 0, sizeof(*merkle));
-	else
-		*merkle = *merkle_recurse(cast_const2(const struct sha256 **, arr),
-					  cast_const2(const struct sha256 **, arr),
-					  tal_count(arr));
-	tal_free(arr);
+	merkle_tlv_full(merkle, next_field, bolt12_calc_nonce, NULL, &iter);
 }
 
 /* BOLT #12:
diff --git a/common/bolt12_merkle.h b/common/bolt12_merkle.h
index 8e6ab517..e014e5e1 100644
--- a/common/bolt12_merkle.h
+++ b/common/bolt12_merkle.h
@@ -1,6 +1,7 @@
 #ifndef LIGHTNING_COMMON_BOLT12_MERKLE_H
 #define LIGHTNING_COMMON_BOLT12_MERKLE_H
 #include "config.h"
+#include <ccan/typesafe_cb/typesafe_cb.h>
 #include <common/bolt12.h>
 
 /**
@@ -10,6 +11,55 @@
  */
 void merkle_tlv(const struct tlv_field *fields, struct sha256 *merkle);
 
+/**
+ * merkle_tlv_full - generic TLV merkle, handling omitted fields.
+ * @merkle: returned merkle hash.
+ * @next_field: iterator to return next field, setting is_omitted true
+ *   if it is omitted from the hash.
+ * @calc_nonce: function to determine the nonce hash.  lnnonce_ctx
+ *   is the partial H("LnNonce"||first-tlv,...) of the first TLV.
+ * @resolve_omitted: called when an omitted hash is used (or must be retrieved).
+ * @arg: parameter to pass to @next_field and @resolve_omitted.
+ */
+#define merkle_tlv_full(merkle, next_field, calc_nonce, resolve_omitted, arg) \
+	merkle_tlv_full_((merkle),					\
+			 typesafe_cb_preargs(const struct tlv_field *,	\
+					     void *,			\
+					     (next_field),		\
+					     (arg),			\
+					     bool *),			\
+			 typesafe_cb_preargs(void,			\
+					     void *,			\
+					     (calc_nonce),		\
+					     (arg),			\
+					     const struct sha256_ctx *, \
+					     bigsize_t,			\
+					     struct sha256 *),		\
+			 typesafe_cb_preargs(void,			\
+					     void *,			\
+					     (resolve_omitted),		\
+					     (arg),			\
+					     struct sha256 *),		\
+			 (arg))
+
+void merkle_tlv_full_(struct sha256 *merkle,
+		      const struct tlv_field *(*next_field)(bool *is_omitted,
+							    void *arg),
+		      void (*calc_nonce)(const struct sha256_ctx *lnnonce_ctx,
+					 bigsize_t fieldtype,
+					 struct sha256 *hash, void *arg),
+		      void (*resolve_omitted)(struct sha256 *h, void *arg),
+		      void *arg);
+
+/* Helper to create lnnonce_ctx from TLV0 */
+void bolt12_lnnonce_ctx(struct sha256_ctx *sctx, const struct tlv_field *field);
+
+/* Helper to calculate the nonce hash given lnnonce_ctx and a field type */
+void bolt12_calc_nonce(const struct sha256_ctx *lnnonce_ctx,
+		       bigsize_t fieldtype,
+		       struct sha256 *hash,
+		       void *unused);
+
 /**
  * sighash_from_merkle - bolt12-style signature hash using this merkle root.
  * @messagename: message name, such as "offer".