On 2026-01-13 13:28:59 [+0100], Thomas Weißschuh wrote:

…

+static void build_proof(struct mtree *mt, unsigned int n, int fd)
+{
+	unsigned char cur[EVP_MAX_MD_SIZE];
+	unsigned char tmp[EVP_MAX_MD_SIZE];

This and a few other instances below could be optimized to avoid
hashing. I probably forgot to let you know.
-> https://git.kernel.org/pub/scm/linux/kernel/git/bigeasy/mtree-hashed-mods.git/commit/?id=10b565c123c731da37befe862de13678b7c54877

+	struct file_entry *fe, *fe_sib;
+
+	fe = &fh_list[n];
+
+	if ((n & 1) == 0) {
+		/* No pair, hash with itself */
+		if (n + 1 == num_files)
+			fe_sib = fe;
+		else
+			fe_sib = &fh_list[n + 1];
+	} else {
+		fe_sib = &fh_list[n - 1];
+	}
+	/* First comes the node position into the file */
+	write_be_int(fd, n);
+
+	if ((n & 1) == 0)
+		hash_entry(fe->hash, fe_sib->hash, cur);
+	else
+		hash_entry(fe_sib->hash, fe->hash, cur);
+
+	/* Next is the sibling hash, followed by hashes in the tree */
+	write_hash(fd, fe_sib->hash);
+
+	for (unsigned int i = 0; i < mt->levels - 1; i++) {
+		n >>= 1;
+		if ((n & 1) == 0) {
+			void *h;
+
+			/* No pair, hash with itself */
+			if (n + 1 == mt->entries[i])
+				h = cur;
+			else
+				h = mt->l[i][n + 1].hash;
+
+			hash_entry(cur, h, tmp);
+			write_hash(fd, h);
+		} else {
+			hash_entry(mt->l[i][n - 1].hash, cur, tmp);
+			write_hash(fd, mt->l[i][n - 1].hash);
+		}
+		memcpy(cur, tmp, hash_size);
+	}
+
+	 /* After all that, the end hash should match the root hash */
+	if (memcmp(cur, mt->l[mt->levels - 1][0].hash, hash_size))
+		errx(1, "hash mismatch");
+}

Sebastian