How to use era-boojum-cuda to construct a Poseidon Merkle tree

[Hodgeson]

I need your assistance as I'm unsure how to use era-boojum-cuda to construct a Poseidon gl64 Merkle tree.

Taking the following 8*3 data as an example, with each row of data representing a leaf node, and cap_height set to 2:

[12852248239109630610, 150122697527067040, 2414224445258003781,
640589317948453723, 14616040317717145777, 7810758275598151172,
5296545862410716452, 16838779205816693011, 17090251512124308012, 
2689677893401679973, 8346677443438677118, 3757402564327742599,
17561766655132747193, 483103342997302027, 17486808908692778320, 
14398696217693053613, 3819232589908700220, 11704272067400675253,
14290795314492815348, 1770007938389474033, 13266887134956869254, 
12714517697316809793, 6752018153669903448, 8558345529080022388 ]

I appreciate your help.

[robik75]

Please take a look at this function as an example.
You would need to change the constants and replace the randomly generated input with your particular values to get the expected result.

[Hodgeson]

First off, a big thanks for getting back to me.

My test code is as follows:

       type P = Poseidon;
        const VALUES_PER_ROW: usize = 3;
        const LOG_N: usize = 3;
        let N: usize = 1 << LOG_N;
        let LAYERS_COUNT: u32 = (LOG_N +1) as u32;
        let values_host_u64:Vec<u64> = vec![
            12852248239109630610, 150122697527067040, 2414224445258003781,
            640589317948453723, 14616040317717145777, 7810758275598151172,
            5296545862410716452, 16838779205816693011, 17090251512124308012,
            2689677893401679973, 8346677443438677118, 3757402564327742599,
            17561766655132747193, 483103342997302027, 17486808908692778320,
            14398696217693053613, 3819232589908700220, 11704272067400675253,
            14290795314492815348, 1770007938389474033, 13266887134956869254,
            12714517697316809793, 6752018153669903448, 8558345529080022388
        ];
        let values_host = values_host_u64.iter().map(|u|GoldilocksField::from_u64(*u).unwrap()).collect::<Vec<_>>();
        let mut results_host = vec![GoldilocksField::ZERO; N * CAPACITY * 2];
        let stream = CudaStream::default();
        let mut values_device = DeviceAllocation::<GoldilocksField>::alloc(values_host.len()).unwrap();
        let mut results_device =
            DeviceAllocation::<GoldilocksField>::alloc(results_host.len()).unwrap();
        set_to_zero(&mut results_device, &stream).unwrap();
        memory_copy_async(&mut values_device, &values_host, &stream).unwrap();
        build_merkle_tree::<P>(
            &values_device,
            &mut results_device,
            0,
            &stream,
            LAYERS_COUNT,
        )
            .unwrap();
        memory_copy_async(&mut results_host, &results_device, &stream).unwrap();
        stream.synchronize().unwrap();
        println!("leaves:{:?}", &values_host);
        println!("results_host:{:?}", &results_host);

The printed resulted is:

leaves:[0xb25c5bade944ea92, 0x021557cc4ad301a0, 0x21810c5783aaf545, 0x08e3d497373a335b, 0xcad69b3ad85168b1, 0x6c656344bb786e04, 0x49811c66498e4524, 0xe9af5c78d5f03113, 0xed2cc533c6407a2c, 0x2553a7cb246d9865, 0x73d55ae986ed8c7e, 0x3424f9b984e59c87, 0xf3b7edba037cc5b9, 0x06b453ee4d286b0b, 0xf2ada00da9c4ed50, 0xc7d271ec245ae2ad, 0x3500a3ce2c1a6c3c, 0xa26ded6ef3f1afb5, 0xc6531a9f662937f4, 0x189054d791537af1, 0xb81d738eea4dd686, 0xb0730a7b36fc6c41, 0x5db3fcbcae7bc458, 0x76c559ea25de0574]

results_host:[0xddfa9ab3fd9ee45a, 0xf25a951d584854ba, 0x8d9731c57c4a7b90, 0xbe0e7d7ec4e1f75a, 0xad90dc4003e7e893, 0xb73fa1a9b9655946, 0x8afbee6bc6d50b4f, 0x9d45a5038c04fd42, 0xc977329c59804a61, 0x97a4874dd559a35c, 0x1cc5e561de082b98, 0x196234f63c5cc2ff, 0x3c889c7d38772e16, 0xa63d28dc5abeeb6a, 0x485619c922ec895d, 0xd783c7813c29a54a, 0x03c2ffbddd6adb4e, 0xa2a6711a58b2e1f6, 0xd43c4e41b38065f4, 0x857b6c931ce1c799, 0xbc05fb07c700d9d4, 0x943f636be77c9fee, 0xafb47c1694adfcfd, 0xcd5a0ee2e0245adf, 0x05ee435981fedc3f, 0x49c618cac5b9a47a, 0xcab283fe5ce3ff7f, 0x6eac6a8d8f4a26d9, 0x071ea31e9200ae0f, 0x410385f61bcce676, 0x271a892641fd80f6, 0x8cc7640da9ba3a35, 0x409065acf3cfbf17, 0x01f9b6c882cc1e49, 0xba74ac72314861a2, 0x23299d98b3b66787, 0x8efec9efc0768e50, 0xa360660b7e2504d5, 0xda128ec0d32c09aa, 0xaf58536252d28fc3, 0x36e10d2875af9cea, 0xfd7d0bf9520b5125, 0x66586595a2bf69de, 0x62db95b5b83a4e46, 0x5d826c19fb8cf545, 0x6ab15fa41b903862, 0xeb7bba94b01b3bc1, 0xfb0119a8076bf667, 0x0c2dd08730d13cdb, 0xf1e000e5bec5b855, 0x75f04d39bbe8b6e6, 0xbc6e22b5d559bd9e, 0xe952bcfedcb366b0, 0xed3dcc0da9d07fe7, 0xad0a3f99076ec436, 0x93299019b6f8d0ad, 0xc26eb6243147ec21, 0x909606d49c4f8ebd, 0xc838e775d36f72cf, 0x89eb99f3e2e50b22, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000]

But I used the code from this, here's my test code for the same:

#include <iostream>

#include "merkle_tree.cuh"

#define CAP_HEIGHT 0
#define LEAVE_LEN 3
#define LOG_N_LEAVES 3

int main() {
    uint32_t cap_height = CAP_HEIGHT;
    uint32_t num_leaves = 1 << LOG_N_LEAVES;
    uint32_t leave_len = LEAVE_LEN;
    uint32_t num_digests = 2 * (num_leaves - (1 << cap_height));
    uint32_t num_digests_caps = num_digests + (1 << cap_height);

    F leaves[24] ={ F(12852248239109630610), F(150122697527067040), F(2414224445258003781),
                    F(640589317948453723), F(14616040317717145777), F(7810758275598151172),
                    F(5296545862410716452), F(16838779205816693011), F(17090251512124308012),
                    F(2689677893401679973), F(8346677443438677118), F(3757402564327742599),
                    F(17561766655132747193), F(483103342997302027), F(17486808908692778320),
                    F(14398696217693053613), F(3819232589908700220), F(11704272067400675253),
                    F(14290795314492815348), F(1770007938389474033), F(13266887134956869254),
                    F(12714517697316809793), F(6752018153669903448), F(8558345529080022388)};

    F* digests_caps = (F*)malloc(sizeof(F)*HASH_WIDTH*num_digests_caps);

    /******
       Init
    *******/
    for (int i=0; i<num_digests_caps; i++) {
        for (int j=0; j<HASH_WIDTH; j++) {
            digests_caps[i*HASH_WIDTH + j] = F(0);
        }
    }

    host_fill_digests_caps(
            digests_caps,
            num_digests,
            leaves,
            num_leaves,
            leave_len,
            cap_height
            );

    print_leaves(leaves, num_leaves, leave_len);
    print_digests(digests_caps, num_digests);
    print_caps(digests_caps, num_digests, cap_height);

    return 0;
}

And the printed result as follow:

leave0 is [b25c5bade944ea92, 21557cc4ad301a0, 21810c5783aaf545, ]
leave1 is [8e3d497373a335b, cad69b3ad85168b1, 6c656344bb786e04, ]
leave2 is [49811c66498e4524, e9af5c78d5f03113, ed2cc533c6407a2c, ]
leave3 is [2553a7cb246d9865, 73d55ae986ed8c7e, 3424f9b984e59c87, ]
leave4 is [f3b7edba037cc5b9, 6b453ee4d286b0b, f2ada00da9c4ed50, ]
leave5 is [c7d271ec245ae2ad, 3500a3ce2c1a6c3c, a26ded6ef3f1afb5, ]
leave6 is [c6531a9f662937f4, 189054d791537af1, b81d738eea4dd686, ]
leave7 is [b0730a7b36fc6c41, 5db3fcbcae7bc458, 76c559ea25de0574, ]

digest0 is [b25c5bade944ea92, 21557cc4ad301a0, 21810c5783aaf545, 0, ]
digest1 is [8e3d497373a335b, cad69b3ad85168b1, 6c656344bb786e04, 0, ]
digest2 is [1acd499a632463d1, b6bc1bbf7ec7d766, c20ddfcc06142ffd, 303e5508f9cd965f, ]
digest3 is [e6eb4c7be2ca25b3, 70dea4641816094d, f166782b4ba15781, ed2c4b86536a519a, ]
digest4 is [49811c66498e4524, e9af5c78d5f03113, ed2cc533c6407a2c, 0, ]
digest5 is [2553a7cb246d9865, 73d55ae986ed8c7e, 3424f9b984e59c87, 0, ]
digest6 is [95b5f5d5b0774bc, 7a0abc5a1d64af63, 190346b5259ecb2b, 3fa64597753723c2, ]
digest7 is [976eeb0fd205be70, 59346d1d320d841a, d1f106cb1419c59d, 524ab01be9d115f5, ]
digest8 is [f3b7edba037cc5b9, 6b453ee4d286b0b, f2ada00da9c4ed50, 0, ]
digest9 is [c7d271ec245ae2ad, 3500a3ce2c1a6c3c, a26ded6ef3f1afb5, 0, ]
digest10 is [39102b8d66202494, cd1d5363a6cf9b2e, 289bb1ded8a7c2ce, 60a61194075d7d22, ]
digest11 is [c7152cf69682e127, 9ebf4eff1303f91f, a2c3e8aac6e2ed58, 32cc5358d4cdd5b6, ]
digest12 is [c6531a9f662937f4, 189054d791537af1, b81d738eea4dd686, 0, ]
digest13 is [b0730a7b36fc6c41, 5db3fcbcae7bc458, 76c559ea25de0574, 0, ]

3e421ff7d0db03d6, c332b94df473a76a, 553dd2a6c018fd08, de4a3266f7e94dcf,

They don't match.

And I couldn't find the CPU code for Poseidon GL64 in the era-boojum-cuda . So I have no idea about it.

Then I obtained some information from this article.

Are the varied results due to the difference in Poseidon instances?

I hope to get your assistance, , and I truly appreciate it. Thank you.

[robik75]

You will not get the same result unless the two implementation equal in all the constants and parameters which in this case they do not.
In boojum we actually use poseidon2 and there is a CPU implementation here: https://github.com/matter-labs/era-boojum/tree/main/src/implementations
The test function i linked in my previous answer is calling that CPU code to verify the GPU result.
Also be aware that the result returned from the GPU code contains the whole merkle tree as a single vector, if you look at the function that is doing the verification vs CPU result, you will see how it can be decomposed into layers and digests.