Comments (12)
To hash more than 8 elements, we need to use the hperm
instruction. The high-level approach is:
- Initialize the hasher state on the stack: this requires 12 elements as we are using RPO as the hash function.
- 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 ofhperm
). - 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.
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.
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.
@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)
- Challenges surrounding sub-second order-book performance on Miden
- Miden Assembly Linter? HOT 3
- Allow user to set the aux field when creating a note HOT 1
- Add CI job for `doc` + make sure that Miden base passes `make doc` HOT 1
- winter_rand_utils Compiled Under Testing Feature Breaks for WASM Builds HOT 1
- Refactor `apply_delta` for Storage Maps HOT 3
- Allow increasing an account's nonce without changing its state HOT 1
- Add `create_wallet_with_custom_code` wallet helper function in miden-lib HOT 5
- Refactor transaction kernel events and errors
- Make memory setters consistent HOT 1
- Checking that a transaction does not consume two identical notes
- Update names used for input/output notes HOT 4
- Refactor batch/block note tree structure
- Refactor `NoteOrigin` / `NoteInclusionProof` structs
- Fix the stack management for account procedures HOT 7
- Allow setting block timestamp and block number when using TransactionContextBuilder HOT 3
- Refactor delta's vault and storage to use maps HOT 1
- feat: add a procedure for basic wallets that creates notes with 0 or more assets
- Refactor account storage to use sequential hash rather than a Merkle tree
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from miden-base.