Rust code for approximating size of compressed authentication structure vs. naive Merkle tree approach

merkle_tree.rs

// Add this test to `twenty-first`'s `twenty-first/src/util_types/merkle_tree.rs` to run it.
    #[test]
    fn size_test_for_swbfi_authentication_path_merging() {
        const NUM_SAMPLES: usize = 2000;
        const TREE_HEIGHT: usize = 12;
        const INDEX_RANGE: usize = 1 << 8;
        const BIG_TREE_HEIGHT: usize = 32;
        const NUM_LEAFS: usize = 1 << TREE_HEIGHT;
        const NUM_OPENED_LEAFS: usize = 45;

        let merkle_tree = MerkleTree::<Tip5>::test_tree_of_height(TREE_HEIGHT);
        let mut rng = thread_rng();

        let mut first_moment = 0f64;
        let mut second_moment = 0f64;
        for _ in 0..NUM_SAMPLES {
            let active_window_start = rng.gen_range(0..(NUM_LEAFS - INDEX_RANGE));
            let active_window = active_window_start..(active_window_start + INDEX_RANGE);
            let indices = (0..NUM_OPENED_LEAFS)
                .map(|_| rng.gen_range(active_window.clone()))
                .collect_vec();
            let proof = merkle_tree
                .inclusion_proof_for_leaf_indices(&indices)
                .unwrap();
            first_moment += proof.authentication_structure.len() as f64;
            second_moment += (proof.authentication_structure.len() as f64).powf(2f64);
        }

        let naive_approach = {
            let proof = merkle_tree.inclusion_proof_for_leaf_indices(&[4]).unwrap();
            let auth_paths = proof.into_authentication_paths().unwrap();
            (auth_paths.iter().flatten().count() * NUM_OPENED_LEAFS) as f64
        };

        let mean_compressed = first_moment / NUM_SAMPLES as f64;
        let std_deviation_avg_compressed =
            (second_moment / NUM_SAMPLES as f64 - mean_compressed.powf(2f64)).sqrt();
        let relative_savings = 1f64 - mean_compressed / naive_approach;
        let stddev_relative_savings = std_deviation_avg_compressed / naive_approach;

        println!(
            "compressed, number of digests: mean: {mean_compressed}±{std_deviation_avg_compressed}"
        );
        println!("naive approach: {naive_approach}");
        println!(
            "Savings: {} % ±{}",
            relative_savings * 100f64,
            stddev_relative_savings * 100f64
        );

        let compressed_in_big_tree = mean_compressed + (BIG_TREE_HEIGHT - TREE_HEIGHT) as f64;
        let naive_in_big_tree = BIG_TREE_HEIGHT as f64 * naive_approach / TREE_HEIGHT as f64;

        println!("compressed, number of digests, big tree: {compressed_in_big_tree}");
        println!("naive approach, big tree: {naive_in_big_tree}");
    }