[Bug] the function `txids_to_roots` generate subroots always the state subtree root

[mengsuenyan]

The following test code always generate the state subtree root except the transactions numbers equal to $2^x, x \in \mathbb{N}$, and the number of transactions is not make up to the power of 2 in the function of miner.mine_block().

pub fn txids_to_roots(transaction_ids: &[[u8; 32]]) -> (MerkleRootHash, PedersenMerkleRootHash, Vec<[u8; 32]>) {
    let (root, subroots) = merkle_root_with_subroots(transaction_ids, MASKED_TREE_DEPTH);
    let mut merkle_root_bytes = [0u8; 32];
    merkle_root_bytes[..].copy_from_slice(&root);

    (
        MerkleRootHash(merkle_root_bytes),
        pedersen_merkle_root(&subroots),
        subroots,
    )
}

pub fn merkle_root_with_subroots(hashes: &[[u8; 32]], subroots_depth: usize) -> ([u8; 32], Vec<[u8; 32]>) {
    merkle_root_with_subroots_inner(hashes, &[], subroots_depth)
}

fn merkle_root_with_subroots_inner(
    hashes: &[[u8; 32]],
    subroots: &[[u8; 32]],
    subroots_depth: usize,
) -> ([u8; 32], Vec<[u8; 32]>) {
    if hashes.len() == 1 {
        // Tree was too shallow.
        let root = hashes[0];
        let subroots = if subroots.is_empty() {
            vec![root]
        } else {
            subroots.to_vec()
        };
        return (root, subroots);
    }

    let result = merkle_round(hashes);
    if result.len() == 1 << subroots_depth {
        merkle_root_with_subroots_inner(&result, &result, subroots_depth)
    } else {
        merkle_root_with_subroots_inner(&result, subroots, subroots_depth)
    }
}

    #[test]
    #[allow(deprecated)]
    fn test_posw_gm17() {
        let rng = &mut XorShiftRng::seed_from_u64(1234567);

        // PoSW instantiated over BLS12-377 with GM17.
        pub type PoswGM17 = Posw<GM17<Bls12_377>, Bls12_377>;

        // run the trusted setup
        let posw = PoswGM17::setup(rng).unwrap();
        // super low difficulty so we find a solution immediately
        let difficulty_target = 0xFFFF_FFFF_FFFF_FFFF_u64;

        // let transaction_ids = vec![[1u8; 32]; 8];
        let transaction_ids = vec![[1u8; 32]; 9];
        let (_, pedersen_merkle_root, subroots) = txids_to_roots(&transaction_ids);

        // generate the proof
        let (nonce, proof) = posw
            .mine(&subroots, difficulty_target, &mut rand::thread_rng(), std::u32::MAX)
            .unwrap();
        assert_eq!(proof.len(), 193); // NOTE: GM17 compressed serialization

        let proof = <GM17<Bls12_377> as SNARK>::Proof::read(&proof[..]).unwrap();
        posw.verify(nonce, &proof, &pedersen_merkle_root).unwrap();
    }

[ljedrz]

I think this is just due to the fact that this test uses identical values for all the transaction ids (which is not a valid scenario) and a [1u8; 32] hashed with another [1u8; 32] will result in the same hash as every other pair of leaves; I wrote my own test case which uses randomized transaction ids and checks the root hashes for all the subsequent merkle trees they would create and didn't encounter this issue:

#[test]
fn test_changing_tx_roots() {
    let mut rng = thread_rng();

    // The number of transactions for which to check subsequent merkle tree root values.
    const NUM_TXS: usize = 200;

    // Create a vector with transaction ids consisting of random values.
    let transaction_ids = {
        let mut vec = Vec::with_capacity(NUM_TXS);
        for _ in 0..NUM_TXS {
            let mut id = [0u8; 32];
            let random = Standard.sample_iter(&mut rng).take(32).collect::<Vec<_>>();
            id.copy_from_slice(&random);
            vec.push(id);
        }
        vec
    };

    // Collect the transactions into a collection of their growing sequences, i.e.
    // [[tx0], [tx0, tx1], [tx0, tx1, tx2], ..., [tx0, ..., NUM_TXS]].
    let growing_tx_ids = transaction_ids.into_iter().scan(Vec::with_capacity(NUM_TXS), |acc, tx_id| {
        acc.push(tx_id);
        Some(acc.clone())
    }).collect::<Vec<_>>();


    // Calculate the root hashes for the sequences of transactions.
    let subsequent_root_hashes = growing_tx_ids.into_iter().map(|tx_ids| {
        let (root, pedersen_root, _subroots) = txids_to_roots(&tx_ids);
        (root, pedersen_root)
    }).collect::<Vec<_>>();

    // Ensure that the subsequent roots differ for every new transaction.
    let mut hashes_differ = true;
    for window in subsequent_root_hashes.windows(2) {
        match window {
            [(root1, pedersen_root1), (root2, pedersen_root2)] => {
                if root1 == root2 || pedersen_root1 == pedersen_root2 {
                    hashes_differ = false;
                    break;
                }
            }
            _ => unreachable!(),
        }
    }

    assert!(hashes_differ);
}

[mengsuenyan]

I think this is just due to the fact that this test uses identical values for all the transaction ids (which is not a valid scenario) and a [1u8; 32] hashed with another [1u8; 32] will result in the same hash as every other pair of leaves; I wrote my own test case which uses randomized transaction ids and checks the root hashes for all the subsequent merkle trees they would create and didn't encounter this issue:

#[test]
fn test_changing_tx_roots() {
    let mut rng = thread_rng();

    // The number of transactions for which to check subsequent merkle tree root values.
    const NUM_TXS: usize = 200;

    // Create a vector with transaction ids consisting of random values.
    let transaction_ids = {
        let mut vec = Vec::with_capacity(NUM_TXS);
        for _ in 0..NUM_TXS {
            let mut id = [0u8; 32];
            let random = Standard.sample_iter(&mut rng).take(32).collect::<Vec<_>>();
            id.copy_from_slice(&random);
            vec.push(id);
        }
        vec
    };

    // Collect the transactions into a collection of their growing sequences, i.e.
    // [[tx0], [tx0, tx1], [tx0, tx1, tx2], ..., [tx0, ..., NUM_TXS]].
    let growing_tx_ids = transaction_ids.into_iter().scan(Vec::with_capacity(NUM_TXS), |acc, tx_id| {
        acc.push(tx_id);
        Some(acc.clone())
    }).collect::<Vec<_>>();


    // Calculate the root hashes for the sequences of transactions.
    let subsequent_root_hashes = growing_tx_ids.into_iter().map(|tx_ids| {
        let (root, pedersen_root, _subroots) = txids_to_roots(&tx_ids);
        (root, pedersen_root)
    }).collect::<Vec<_>>();

    // Ensure that the subsequent roots differ for every new transaction.
    let mut hashes_differ = true;
    for window in subsequent_root_hashes.windows(2) {
        match window {
            [(root1, pedersen_root1), (root2, pedersen_root2)] => {
                if root1 == root2 || pedersen_root1 == pedersen_root2 {
                    hashes_differ = false;
                    break;
                }
            }
            _ => unreachable!(),
        }
    }

    assert!(hashes_differ);
}

Does the PoSW have the above process? Why is the number of subroots 1 instead of 5, when the number of transactions is 9, and so on?

[ljedrz]

@mengsuenyan as someone who has only tweaked the related code I'm not sure if this particular behavior is expected, so I'll leave the answer to the others assigned.

@howardwu if you agree that we should be testing random unique transaction ids instead of fixed dummy values (which I've seen in more places, and duplicated as well), I can publish this test as a PR and look for other places that could use an adjustment like this.

[akattis]

The expected behaviour of the POSW process should be to compute the subtree roots from the transactions, as @mengsuenyan mentions above in the table. These should then be fed into the circuit, which should only verify the MaskedPedersen hashes up to a fixed depth, which we constrained to always be 2. Therefore, even though the number of txids can be much larger, the circuit should always verify 3 MaskedPedersen circuits (i.e. a tree of depth 2).