sig-skip-list.rs

#[cfg(test)]
extern crate quickcheck;
#[cfg(test)]
extern crate rand;

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 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;
}

// A convenience macro for concisely writing test cases (from https://docs.rs/maplit/1.0.1/src/maplit/lib.rs.html#143-155)
#[cfg(test)]
macro_rules! set {
    ($($key:expr,)+) => (set!($($key),+));
    ( $($key:expr),* ) => {{
            let mut _set = ::std::collections::BTreeSet::new();
            $(_set.insert($key);)*
            _set
    }};
}

#[test]
fn test_link_to() {
    assert_eq!(link_to(0), set![]);
    assert_eq!(link_to(1), set![0]);
    assert_eq!(link_to(2), set![1]);
    assert_eq!(link_to(3), set![1, 2]);
    assert_eq!(link_to(10), set![7, 9]);
    assert_eq!(link_to(15), set![7, 11, 13, 14]);
    assert_eq!(link_to(16), set![15]);
    assert_eq!(link_to(17), set![15, 16]);
    assert_eq!(link_to(18), set![15, 17]);
    assert_eq!(link_to(19), set![15, 17, 18]);
}

/// 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;
}

#[test]
fn test_find_min_cert() {
    assert_eq!(find_min_cert(0, 1), set![0]);
    assert_eq!(find_min_cert(3, 8), set![3, 7]);
    assert_eq!(find_min_cert(24, 29), set![24, 25, 27]);
}

/// 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));
}

#[test]
fn test_check_cert() {
    assert!(check_cert(0, 1, &set![0]));
    assert!(check_cert(3, 9, &set![3, 7]));
    assert!(check_cert(3, 10, &set![3, 7, 9]));
    assert!(check_cert(3, 10, &set![3, 7]));

    assert!(!check_cert(3, 10, &set![3, 9]));
    assert!(!check_cert(3, 10, &set![7, 9]));

    assert!(check_cert(24, 26, &set![15, 19, 23, 24, 25]));
    assert!(check_cert(24, 29, &set![24, 25, 27]));
}

/// 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;
        }
    }
}

// To test this, we randomly generate pairs of numbers (n, m) and check that their combined
// certificate pools form a valid certificate.
#[cfg(test)]
mod tests {
    use super::*;
    use rand;
    use quickcheck::*;

    #[test]
    fn test_cert_pool() {
        // This implementation runs into u64 overflows on numbers greater than std::u64::MAX >> 1.
        let rng = StdGen::new(rand::thread_rng(), (std::u64::MAX >> 1) as usize /* largest generated input */);
        let mut quickcheck = QuickCheck::new().gen(rng).tests(100 /* number of runs */);
        quickcheck.quickcheck(do_test_cert_pool as fn(u64, u64) -> bool);

        // also test with smaller numbers to find cornercases (similar numbers, powers of two)
        let rng2 = StdGen::new(rand::thread_rng(), 16);
        let mut quickcheck2 = QuickCheck::new().gen(rng2).tests(10000);
        quickcheck2.quickcheck(do_test_cert_pool as fn(u64, u64) -> bool);
    }

    fn do_test_cert_pool(mut n: u64, mut m: u64) -> bool {
        // without loss of generality assume n <= m
        if n > m {
            let tmp = n;
            n = m;
            m = tmp;
        }

        let pool_n = cert_pool(n);
        let pool_m = cert_pool(m);
        let cert = pool_n.union(&pool_m).map(|msg_ref| *msg_ref).collect();
        // println!("n: {:?}, m: {:?}, cert: {:?}\n", n, m, cert);

        return check_cert(n, m, &cert);
    }
}