@aljoscha node 31 is correct. It signs the previous node, then the previous tree (tree[26] two nodes), then next previous tree (tree[8]). The hashes you send are all correct, but you can leave off the extras.

I can't remember why I included the pubkey at the start. If that's the identify of the feed it's not necessary to send that. Lets drop that.

If do decide to do a full replica of a feed, you don't need to send any additional data - you have everything you need to reconstruct a proof.

When you request a one-off message, and it's the first message you have, your peer (who we are assuming has the entire feed) sends that message, plus the preceding full tree hashes. log(n) (using the numbering system it's easy to figure out which trees using some bitwise stuff, but I don't recall the code... and it's quite late here now.)

If you already have a message in the feed, give me 5, I have 25. So, whoever Z5 to A, lets say D, knows that A has 25, and assumes that they also have the tree hashes preceding 25.
So D sends tree[2], msg[5], tree[7]=hash(msg[7]), and tree[12]. that's enough to reconstruct

tree[8] == hash(
  tree[4]=hash(
    tree[2] +
    hash(
      tree[5]=hash(msg[5]) +
      tree[7]
    )
  ) +
  tree[12]
)

If they have msg[25], we can assume they'll have tree[8], so that should be enough to convince them msg[5] is signed by 25.

and A now has tree[7], which they can provide to C when needed.

Since you can reconstruct the structure if you know the numbers, a proof/certificate is just the lower number, the higher number and a list of hashes.

Also, now that A has two messages, if they want a message in-between those two, they say I want message 17, I have 5, and 25. Their peer then sends sufficient hashes to tie 5 to 17 (because we know they'll have the trees before 5) and 17 to 25. A sends request(17, 5, 25)
and D returns [proof(5, 17), get(17), proof(17, 25)]

If A requests a range, we only need send extra hashes for the gaps, because the hashes of the messages in the range can be recalculated.

I also made a better picture:

Arrows point to the arguments to a hash function - dotted lines for what a message signs, solid lines for trees. Unfortunately, to make it more confusing, I used the odd numbers for the trees like dat's paper. Looking at this now, I think I prefer even numbers, so the the big trees are easily recognizable as powers of two.

It's possible that a peer has a message - say only 17, but not 25, so can't prove that 17 was part of 25. I think it would be better in this case just not to give out msg[17]. On the other hand, if they'd asked for msg[15], they can tie it back to tree[8], which they know is part of 25 even without knowing 25.