Benchmarking 1: Create a hash chain scenario for BLAKE3 of 1, 10, 100, and 1000 hashes about examples HOT 22 CLOSED

@itzmeanjan I have two questions before I can push a PR for this issue:

• Can you help me and post the masm program for the BLAKE3 1to1 hash here?
• Do you know where I can find the BLAKE3 hash function in Rust? chiplets::hasher::hash_elements(&output) uses Rescue Prime, but there must be a BLAKE3 implementation in minden-core as well, right?

from examples.

What I mean @itzmeanjan is a masm program for the 1to1 BLAKE3 hash that I can copy and paste into the benchmarking program, like:

let source = format!(
            "
        begin  
            repeat.{}
                BLAKE3<?>
            end
        end", 
       self.num_iter
      );

from examples.

What I mean @itzmeanjan is a masm program for the 1to1 BLAKE3 hash that I can copy and paste into the benchmarking program, like:

let source = format!(
            "
        begin  
            repeat.{}
                BLAKE3<?>
            end
        end", 
       self.num_iter
      );

If you're looking for the one I wrote, here it is https://github.com/itzmeanjan/miden/blob/9092607c758183cee571713638faeab200e1fda7/stdlib/asm/crypto/hashes/rescue_prime.masm

from examples.

• Do you know where I can find the BLAKE3 hash function in Rust? chiplets::hasher::hash_elements(&output) uses Rescue Prime, but there must be a BLAKE3 implementation in minden-core as well, right?

It lives in our crypto-crate, probably you're looking for https://github.com/0xPolygonMiden/crypto/blob/ed07f89fe7260bdcfd462c4e6b8450269e6473c3/src/hash/blake/mod.rs

from examples.

What I mean @itzmeanjan is a masm program for the 1to1 BLAKE3 hash that I can copy and paste into the benchmarking program, like:

let source = format!(
            "
        begin  
            repeat.{}
                BLAKE3<?>
            end
        end", 
       self.num_iter
      );

If you're looking for the one I wrote, here it is https://github.com/itzmeanjan/miden/blob/9092607c758183cee571713638faeab200e1fda7/stdlib/asm/crypto/hashes/rescue_prime.masm

Thanks @itzmeanjan . I found the implementations in the folder. Is the BLAKE3 masm 900 lines long?

from examples.

Looks like I misread your question.

I found the implementations in the folder. Is the BLAKE3 masm 900 lines long?

Yes, https://github.com/0xPolygonMiden/miden-vm/blob/9c8af67a7768b920772b3a42d89947f7f639e089/stdlib/asm/crypto/hashes/blake3.masm, here is blake3.

from examples.

Thanks a lot. This looks like an impressive piece of masm code, ser. I am unsure how to use in a new masm file. Can you help me there? Do I need to import that or simply copy & paste?

from examples.

Thanks a lot. This looks like an impressive piece of masm code, ser. I am unsure how to use in a new masm file. Can you help me there? Do I need to import that or simply copy & paste?

This test case can be helpful https://github.com/0xPolygonMiden/miden-vm/blob/9c8af67a7768b920772b3a42d89947f7f639e089/miden/tests/integration/stdlib/crypto/blake3.rs.

Let me know if not.

from examples.

Thanks, that helps. But some parts are still unclear to me. So I try to clarify here:

My goal is to use the BLAKE3 1-to-1 hasher two times. First I want to use it in an assembly program. Second, I want to use it outside the Miden VM to compare the result.

BLAKE3 1-to-1 hasher in Miden Assembly

I need a Miden Assembly program that hashes let input = vec![0u64; 4]; using the BLAKE3 1-to-1 implementation n-times.

When I use your example, I get the following:

        use.std::crypto::hashes::blake3
        begin  
            repeat.{}
                exec.blake3::hash 
            end
        end"

To me, this now looks like the "normal" BLAKE3 hashing function that hashes 2-to-1.

• Is my understanding correct?
• If so, can you provide me with a Miden assembly program that uses the 1-to-1 hash?

BLAKE3 1-to-1 hasher outside the Miden VM

To be able to compare the results, I need the BLAKE3 1-to-1 hashing function implemented in RUST that hashes the same input n-times.

There are many different BLAKE3 implementations in crypto and in winter-crypto, e.g. Blake3_192. Let's assume Blake3_192 is the correct 1-to-1 BLAKE3 implementation that is used in the above assembly program. Then, what I get as an output is [u8; 32] but what I need is [Felt; 4]. Unfortunately, the type ByteDigest seems not to have the handy function as_elements(). Do you know how I can get as output of the BLAKE3 hash function a [Felt; 4]?

            output = Blake3_192::hash_elements(&output)
                .as_bytes()

I hope my questions are clearer now and happy to jump into a short call.

from examples.

Thanks for nicely describing the question @Dominik1999 .

1. Looks like I've linked you to a older revision of Blake3 assembly program. You look at https://github.com/0xPolygonMiden/miden-vm/blob/22cb8006298bf95f7feab70d3828135d35dcad06/miden/tests/integration/stdlib/crypto/blake3.rs. There you can find two test cases, one for 2-to-1 hashing and anther one for 1-to-1 hashing.
2. For computing blake3 1-to-1 hashing outside of VM, you're looking for blake3-256 hash_elements API, which should take 4 Felts and produce 32 -bytes output. Here it's https://github.com/0xPolygonMiden/crypto/blob/1332299a82af642fad899719a5475572b15b82d7/src/hash/blake/mod.rs#L127-L134

from examples.

Then, what I get as an output is [u8; 32] but what I need is [Felt; 4]. Unfortunately, the type ByteDigest seems not to have the handy function as_elements(). Do you know how I can get as output of the BLAKE3 hash function a [Felt; 4]?

It can be achieved using following code snippet, which I took from https://github.com/0xPolygonMiden/miden-vm/blob/22cb8006298bf95f7feab70d3828135d35dcad06/miden/tests/integration/stdlib/crypto/blake3.rs#L49-L53

let ibytes = [0u8; 32];
let ifelts = group_slice_elements::<u8, 8>(&ibytes)
             .iter()
             .map(|&bytes| Felt::new(u64::from_le_bytes(bytes)))
             .collect::<Vec<Felt>>();

from examples.

Perfect, thanks. Might it be that proc.blake3::hash_1to1 is not yet in Miden v0.3.0?

At least I get

'Could not compile source: ImportedProcModuleNotFound(ProcedureId([132, 65, 166, 176, 0, 112, 95, 35, 223, 2, 180, 211, 203, 115, 127, 68, 35, 128, 185, 178, 182, 38, 47, 33]))'

And I am using

[dependencies]
miden = "0.3.0"
miden-core = "0.3.0"
miden-crypto = "0.1.0"
miden-prover = "0.3.0"
miden-stdlib = "0.2.0"
miden-verifier = "0.3.0"

from examples.

Might it be that proc.blake3::hash_1to1 is not yet in Miden v0.3.0?

Yes, you're correct. I suggest you use next branch from Github ( of miden-vm ) as your dependency. Also you may try to pin cargo dependency to commit 22cb8006298bf95f7feab70d3828135d35dcad06.

from examples.

When I try to use your commit here I get

Compiling miden-assembly v0.4.0 (https://github.com/0xPolygonMiden/miden-vm?rev=22cb800#22cb8006)
error[E0658]: generic associated types are unstable
  --> /Users/ich/.cargo/git/checkouts/miden-vm-3db6be6805d1979c/22cb800/assembly/src/library.rs:13:5
   |
13 | /     type ModuleIterator<'a>: Iterator<Item = &'a Module>
14 | |     where
15 | |         Self: 'a;
   | |_________________^
   |
   = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information
   = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable

error[E0658]: where clauses on associated types are unstable
  --> /Users/ich/.cargo/git/checkouts/miden-vm-3db6be6805d1979c/22cb800/assembly/src/library.rs:13:5
   |
13 | /     type ModuleIterator<'a>: Iterator<Item = &'a Module>
14 | |     where
15 | |         Self: 'a;
   | |_________________^
   |
   = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information
   = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable

error[E0658]: generic associated types are unstable
  --> /Users/ich/.cargo/git/checkouts/miden-vm-3db6be6805d1979c/22cb800/assembly/src/library.rs:43:5
   |
43 |     type ModuleIterator<'a> = Iter<'a, Module>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information
   = help: add `#![feature(generic_associated_types)]` to the crate attributes to enable

For more information about this error, try `rustc --explain E0658`.
error: could not compile `miden-assembly` due to 3 previous errors

Does it work on your side? Which Rust version are you using?

I am using

ich@MacBook-Pro-35 miden % rustc --version
rustc 1.65.0-nightly (40336865f 2022-08-15)

from examples.

I've following rustc

rustc --version
rustc 1.67.0-nightly (73c9eaf21 2022-11-07)

from examples.

I think generic associated types were stabilised in https://blog.rust-lang.org/2022/11/03/Rust-1.65.0.html

from examples.

ok, it works now. I can hash, prove and verify. However, I get different results.

  guest-compute: `[600956609, 2401493466, 1918081665, 3246643754]`,
 host-compute: `[8238098025478871594, 2581088984371552730, 12277472986340987080, 15779522484170287598]`

guest-compute is obtained by using Miden assembly

        let source = format!(
            "  
            use.std::crypto::hashes::blake3

            begin
                repeat.{}
                    exec.blake3::hash_1to1
                end
            end",
            num_iter
        );

        // We can also transform the input_data into 8-byte arrays and
        // then parse each 8-byte array into a u64
        let input = vec![0u64; 4];

and host-compute is obtained by the pure Rust implementation

        // We also hash a vector of four 0's
        let input = vec![Felt::ZERO; 4];
        let mut output: [Felt; 4] = input.try_into().unwrap();

        for _ in 0..self.num_iter {
            let pre_output = Blake3_256::hash_elements(&output);

            output = group_slice_elements::<u8, 8>(&pre_output)
                .iter()
                .map(|&bytes| Felt::new(u64::from_le_bytes(bytes)))
                .collect::<Vec<Felt>>()
                .try_into()
                .expect("slice with incorrect length");

        }

        Some(output.iter().map(|x| x.as_int()).collect::<Vec<u64>>())

Might it be that Blake3_256::hash_elements() is not the same as blake3::hash_1to1? @itzmeanjan

from examples.

@Dominik1999 - BLAKE3 is not an arithmetization-friendly hash - so, it works with bytes rather than elements. You can probably just use Blake3_256::hash() and probably no need to bring in Felts into this.

from examples.

Got it, then it should actually work like this

        // We also hash a vector of four 0's
        let input = vec![0u8; 32];
        let mut output = input;

        for _ in 0..self.num_iter {
            
            let pre_output = Blake3_256::hash(&output);

            output = pre_output.to_vec();

        }

        Some([WE NEED 4 ELEMENTS u64])

how would I get as an output a Vector of 4 Elements. What I get out of Blake3_256::hash() is

[42, 218, 131, 193, 129, 154, 83, 114, 218, 225, 35, 143, 193, 222, 209, 35, 200, 16, 79, 218, 161, 88, 98, 170, 238, 105, 66, 138, 24, 32, 252, 218]

And this must become in the end [600956609, 2401493466, 1918081665, 3246643754]

from examples.

Shouldn't the output be [u8; 32]? But either way, BLAKE3 procedure in stdlib leaves 8 elements on the stack each containing 32-bit values. So, you need to read top 8 elements from the stack, interpret them as 32-bit values, and then convert either to u64 or to bytes.

from examples.

So as an input, we have defined [0u8; 32] (32-bytes) for all hash chains in Scenario 1.

In the rescue prime example

https://github.com/delendum-xyz/zk-benchmarking/blob/307ac6e7a4923f290763c3aa58a9aeb4f1833fe2/miden/src/benches/iter_rescue_prime.rs#L62

as input and

https://github.com/delendum-xyz/zk-benchmarking/blob/307ac6e7a4923f290763c3aa58a9aeb4f1833fe2/miden/src/benches/iter_rescue_prime.rs#L95

as output. For the BLAKE3 benchmark, I was following this example. But maybe I am missing something here. Should we jump in a short call?

from examples.

Closed in delendum-xyz/zk-benchmarking#7

from examples.