Skip to content

Latest commit

 

History

History
108 lines (68 loc) · 6.55 KB

README.md

File metadata and controls

108 lines (68 loc) · 6.55 KB
Raw

Miden Crypto

LICENSE test build RUST_VERSION CRATE

This crate contains cryptographic primitives used in Polygon Miden.

Hash

Hash module provides a set of cryptographic hash functions which are used by the Miden VM and the Miden rollup. Currently, these functions are:

  • BLAKE3 hash function with 256-bit, 192-bit, or 160-bit output. The 192-bit and 160-bit outputs are obtained by truncating the 256-bit output of the standard BLAKE3.
  • RPO hash function with 256-bit output. This hash function is an algebraic hash function suitable for recursive STARKs.
  • RPX hash function with 256-bit output. Similar to RPO, this hash function is suitable for recursive STARKs but it is about 2x faster as compared to RPO.

For performance benchmarks of these hash functions and their comparison to other popular hash functions please see here.

Merkle

Merkle module provides a set of data structures related to Merkle trees. All these data structures are implemented using the RPO hash function described above. The data structures are:

  • MerkleStore: a collection of Merkle trees of different heights designed to efficiently store trees with common subtrees. When instantiated with RecordingMap, a Merkle store records all accesses to the original data.
  • MerkleTree: a regular fully-balanced binary Merkle tree. The depth of this tree can be at most 64.
  • Mmr: a Merkle mountain range structure designed to function as an append-only log.
  • PartialMerkleTree: a partial view of a Merkle tree where some sub-trees may not be known. This is similar to a collection of Merkle paths all resolving to the same root. The length of the paths can be at most 64.
  • PartialMmr: a partial view of a Merkle mountain range structure.
  • SimpleSmt: a Sparse Merkle Tree (with no compaction), mapping 64-bit keys to 4-element values.
  • Smt: a Sparse Merkle tree (with compaction at depth 64), mapping 4-element keys to 4-element values.

The module also contains additional supporting components such as NodeIndex, MerklePath, and MerkleError to assist with tree indexation, opening proofs, and reporting inconsistent arguments/state.

Signatures

DSA module provides a set of digital signature schemes supported by default in the Miden VM. Currently, these schemes are:

  • RPO Falcon512: a variant of the Falcon signature scheme. This variant differs from the standard in that instead of using SHAKE256 hash function in the hash-to-point algorithm we use RPO256. This makes the signature more efficient to verify in Miden VM.

For the above signatures, key generation, signing, and signature verification are available for both std and no_std contexts (see crate features below). However, in no_std context, the user is responsible for supplying the key generation and signing procedures with a random number generator.

Pseudo-Random Element Generator

Pseudo random element generator module provides a set of traits and data structures that facilitate generating pseudo-random elements in the context of Miden VM and Miden rollup. The module currently includes:

  • FeltRng: a trait for generating random field elements and random 4 field elements.
  • RpoRandomCoin: a struct implementing FeltRng as well as the RandomCoin trait using RPO hash function.
  • RpxRandomCoin: a struct implementing FeltRng as well as the RandomCoin trait using RPX hash function.

Make commands

We use make to automate building, testing, and other processes. In most cases, make commands are wrappers around cargo commands with specific arguments. You can view the list of available commands in the Makefile, or run the following command:

make

Crate features

This crate can be compiled with the following features:

  • std - enabled by default and relies on the Rust standard library.
  • no_std does not rely on the Rust standard library and enables compilation to WebAssembly.

Both of these features imply the use of alloc to support heap-allocated collections.

To compile with no_std, disable default features via --no-default-features flag or using the following command:

make build-no-std

AVX2 acceleration

On platforms with AVX2 support, RPO and RPX hash function can be accelerated by using the vector processing unit. To enable AVX2 acceleration, the code needs to be compiled with the avx2 target feature enabled. For example:

make build-avx2

SVE acceleration

On platforms with SVE support, RPO and RPX hash function can be accelerated by using the vector processing unit. To enable SVE acceleration, the code needs to be compiled with the sve target feature enabled. For example:

make build-sve

Testing

The best way to test the library is using our Makefile, this will enable you to use our pre-defined optimized testing commands:

make test

For example, some of the functions are heavy and might take a while for the tests to complete if using simply cargo test. In order to test in release and optimized mode, we have to replicate the test conditions of the development mode so all debug assertions can be verified.

We do that by enabling some special flags for the compilation (which we have set as a default in our Makefile):

RUSTFLAGS="-C debug-assertions -C overflow-checks -C debuginfo=2" cargo test --release

License

This project is MIT licensed.