[Bug] the function `txids_to_roots` generate subroots always the state subtree root about snarkvm HOT 4 CLOSED

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

from snarkvm.

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?

from snarkvm.

@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.

from snarkvm.

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).

from snarkvm.