Giter VIP home page Giter VIP logo

Comments (4)

bobbinth avatar bobbinth commented on July 26, 2024 1

To hash more than 8 elements, we need to use the hperm instruction. The high-level approach is:

  1. Initialize the hasher state on the stack: this requires 12 elements as we are using RPO as the hash function.
  2. Absorb elements to hash into the state and then execute the hperm instruction after each absorption (up to 8 elements can be absorbed for a single invocation of hperm).
  3. Squeeze out the hash (second word on the stack).

Specifically, if we want to hash 9 elements, the could would look something like this:

use.std::crypto::hashes::native->rpo

begin
    # push the capacity portion of the hasher state onto the stack; since the number of elements we are
    # hashing is not divisible by 8, the first capacity register must be set to 1 (this is RPO's padding
    # rule)
    push.1.0.0.0
    # => [0, 0, 0, 1]

    # absorb the first 8 values into the hasher state
    push.1.2.3.4.5.6.7.8
    # => [8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 1]

    # execute the RPO permutation
    hperm
    # => [R2, R1, C]

    # absorb the 9th element into the state; the padding rule is that we need to append 1 followed by the 
    # number of zeros needed to get the state to the next multiple of 8
    dropw dropw
    # => [R2, R1, C]

    push.9.1.0.0.0.0.0.0
    # => [0, 0, 0, 0, 0, 0, 1, 9, C]

    # execute the RPO permutation
    hperm
    # => [R2, R1, C]
    
    exec.rpo::state_to_digest
    # => [R1]
end

If the data you want to hash is already in memory, we have a couple of convenience procedures in Miden stdlib.

from miden-base.

partylikeits1983 avatar partylikeits1983 commented on July 26, 2024

Simply through trial and error I figured it out. For finding the hash of 9 stack elements this is how the procedure would look like:

begin
    # Initialize the capacity portion of the hasher state.
    padw
    # => [0, 0, 0, 0]

    # Absorb the first 8 values into the hasher state.
    push.1.2.3.4.5.6.7.8
    # => [8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0]

    # Execute the RPO permutation.
    hperm
    # => Permuted state [R2, R1, C]

    # Drop the two capacity elements to absorb the 9th element.
    dropw dropw
    # => [R2, R1]

    # Absorb the 9th element and apply padding.
    push.9.0.0.0.0.0.0.0
    # => [0, 0, 0, 0, 0, 0, 0, 9, R2, R1]

    # Execute the RPO permutation.
    hperm
    # => Permuted state [R2, R1, C]

    # Convert the state to the digest.
    exec.state_to_digest
    # => [Digest]
end

Snippet from rust test (https://github.com/compolabs/spark-miden-v1/blob/main/tests/mock_integration/swap_recipient_test.rs):

  let vec_inputs = vec![
      Felt::new(1),
      Felt::new(2),
      Felt::new(3),
      Felt::new(4),
      Felt::new(5),
      Felt::new(6),
      Felt::new(7),
      Felt::new(8),
      Felt::new(9),
  ];

  let inputs = NoteInputs::new(vec_inputs.clone()).unwrap();

  let padded_values = pad_inputs(&vec_inputs);

  let inputs_commitment = Hasher::hash_elements(&padded_values);
  println!("inputs commitment: {:?}", inputs_commitment);

The inputs_commitment is the same as the stack output.

Will work on making this more generalized for more inputs, but so far it seems to handle up to 16 inputs.

from miden-base.

bobbinth avatar bobbinth commented on July 26, 2024

Nice! The reason why this is slightly different from what I described is that when hashing note inputs we currently manually pad the elements to the next multiple of 8. This means that when we hash [1, 2, 3, 4, 5, 6, 7, 8, 9], we actually hash [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0]. This changes how we need to do padding in MASM (e.g., instead of push.1.0.0.0 for capacity, we can just do padw).

Based on this and also on an off-line discussion, I think it may be useful to add the following two procedures to the notes module in miden-lib:

#! Computes hash of note inputs starting at the specified memory address.
#!
#! Inputs:  [inputs_ptr, num_inputs]
#! Outputs: [HASH]
#!
#! Panics if num_inputs is greater than 128.
export.compute_inputs_hash

and

#! Returns recipient digest of the note that is currently being processed.
#!
#! Inputs:  []
#! Outputs: [RECIPIENT]
#!
#! Panics if called outside of the note script context.
export.get_recipient_digest

from miden-base.

bobbinth avatar bobbinth commented on July 26, 2024

@partylikeits1983 - computing hash for an arbitrary number of notes inputs was merged in #750. Is there anything else outstanding in this issue (e.g., do you still need get_recipient_hash procedure)?

from miden-base.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.