It works! Here's a rust implementation (gist with syntax highlighting and tests):

use std::collections::BTreeSet;

/// Find the power of two <= the given number (`None` for 0).
fn prev_power_of_two(n: u64) -> Option<u64> {
    if n == 0 {
        None
    } else if n.is_power_of_two() {
        Some(n)
    } else {
        Some(n.next_power_of_two() >> 1)
    }
}

/// Return the set of sequence numbers whose hash the n-th message has to include.
pub fn link_to(n: u64) -> BTreeSet<u64> {
    // Each natural number can be uniquely decomposed into a sum of powers of two (i.e. a binary
    // representation). The set of messages to link to depends on this decomposition:
    // Begin with an additional accumulator of zero, then for all those powers of two in descending
    // order: Add the power of two to the accumulator and link to the message whose sequence number
    // is one less than the accumulator. Note that this results in the zero-th message not linking
    // to anything, and each other message links to at least its predecessor. Each message links to
    // as many previous messages as the binary representation of the sequence number has ones,
    // resulting in O(n * log(n)) total size of the feed.
    let mut acc = 0;
    let mut out = BTreeSet::new();

    while (n - acc) > 0 {
        match prev_power_of_two(n - acc) {
            None => return out, // the zero-th message links to no other message
            Some(largest_pow_2) => {
                acc += largest_pow_2;
                out.insert(acc - 1);
            }
        }
    }

    debug_assert!(out.len() == (n.count_ones() as usize));
    return out;
}

/// Compute the smallest possible certificate that proves that m transitively links to n.
pub fn find_min_cert(n: u64, m: u64) -> BTreeSet<u64> {
    assert!(n <= m); // Good luck finding a certificate otherwise.
    let mut cert = BTreeSet::new();

    // The smallest certificate is obtained by iteratively following backlinks starting at m, going
    // to the smallest message greater or equal to n.
    let mut current = m;
    while current > n {
        current = *link_to(current).range(n..).next().unwrap();
        cert.insert(current);
    }

    // Since the backlinks can jump up to the next-smaller power of two in each iteration step,
    // the certificate contains at most O(log_2(n)) entries.
    return cert;
}

/// Check whether a given set of messages proves that message m transitively links to message n.
pub fn check_cert(n: u64, m: u64, cert: &BTreeSet<u64>) -> bool {
    assert!(n <= m);

    // The backlinks have been chosen in a way such that a certificate is valid if and only if it
    // contains the minimal certificate.
    return cert.is_superset(&find_min_cert(n, m));
}

/// Suppose we have message n, and a peer wants to verify that it is signed by some m. While it is
/// easy to find a logarithmically sized certificate for a pair of messages via
/// `find_min_cert(n, m)`, there's still a problem: We don't know in advance which m the peer will
/// provide. Storing the results of find_min_cert for all possible m takes linear space, which we
/// want to avoid.
///
/// Instead, we need to store a logarithmically sized set of messages depending only on n, such
/// that the union of this set and the corresponding set for m is a valid certificate for the pair
/// (n, m) for any n and m. This function computes such a set.
pub fn cert_pool(n: u64) -> BTreeSet<u64> {
    let mut pool = BTreeSet::new();
    // Let (l + 1) be the largest power of two less than or equal to n, and let (o + 1) be the
    // smallest power of two greater than n. The certificate pool needs to contain message to cover
    // the following cases:
    //
    // m <= l <= n
    // l <= m < n
    // n < m <= o
    // n <= o <= m
    match prev_power_of_two(n) {
        None => {
            // For n == 0, the cert pool is just the zero-th message itself.
            pool.insert(0);
            return pool;
        }
        Some(prev_pow) => {
            let l = prev_pow - 1;
            let o = (n + 1).next_power_of_two() - 1;

            // Intuitively, we make sure that we can connect o to n, and n to l, and l to 0, in a way that
            // we can always "catch" m in-between. The last case where o < m is handled by symmetry (the
            // certificate pool of m "catches" n in-between).
            pool.append(&mut find_min_cert(0, l));
            pool.append(&mut find_min_cert(l, n));
            pool.append(&mut find_min_cert(n, o));
            // All three of those sets are logarithmic in size.

            return pool;
        }
    }
}