Repository: paritytech/ink
Pull request #1393 (2022-09-13 23:30:45)

Use XXH32 instead of sha256 for const hashing
Would it be feasible to use ~~[FNV](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function)~~ `xxhash` instead of sha256 for Key hashing, since we use only 32bits of the sha hash anyways? With ~~FNV~~ `xxhash` being a much simpler algorithm, it would allow us to use `ink_metadata` with stable rust without relying on `RUSTC_BOOTSTRAP`. Also what do you think @xgreenx ?

xgreenx: I thought about this solution(in the first implementation I used a custom hash function). The problem is that the chance of getting collision is higher, and it will make the implementation of the same storage key calculation for other languages harder because they need find implementation of this not popular function=) The same for documentation, we need to describe the usage of an unusual hashing algorithm.

But if other members of the ink! team like this idea, of course, go with it=)
xermicus: Thanks for your feedback! At first I shared your concerns about collisions, but as I thought a bit about it I came to a different conclusion. My guess was that reducing sha2 to 32 bits only has significant impact on its collision rate as well. And FNV1A is actually not that bad: According to [this stack overflow answer](https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633), there are only ~4 collisions per ~200K hashes of UUIDS.

This left me wondering, how bad is FNV1A compared to 32bit SHA256? I quickly hacked together [my own very small and totally unscientific experiment](https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=0b76f70bf0be3fec23a33536887727a1). If you run this multiple times, you'll observe that the SHA2 option, if at all, does only insignificantly better than FNV1a. In fact, sometimes there are even more collisions for SHA2:

```
Testing for 200000 UUIDs with 32 runs...
FNV1A collisions: 137 (avg. 4.28125 per 200000 UUIDs)
SHA2_32 collisions: 155 (avg. 4.84375 per 200000 UUIDs)
```

Based of that it seems like we don't really gain much in terms of collision resistance by using 32bit SHA2 instead of FNV1A. This only applies to hashing UUIDs though (behavior in our use case might be different!).

> the usage of an unusual hashing algorithm

I don't think FNV is "unusual". To my knowledge it is a solid (in terms of speed vs collision resistance) and often used non cryptographic hash.

> But if other members of the ink! team like this idea, of course, go with it=)

I'd be very happy to hear some more opinions on this one as well :blush:



Patch:
diff --git a/.cargo/config.toml b/.cargo/config.toml
new file mode 100644
index 0000000000..b677b9b2ae
--- /dev/null
+++ b/.cargo/config.toml
@@ -0,0 +1,4 @@
+[env]
+# We need to enable `RUSTC_BOOTSTRAP` so that the nightly ink!
+# features still work on stable.
+RUSTC_BOOTSTRAP = "1"
\ No newline at end of file
diff --git a/.github/workflows/examples.yml b/.github/workflows/examples.yml
index b88177bd8c..e0bbb6fc93 100644
--- a/.github/workflows/examples.yml
+++ b/.github/workflows/examples.yml
@@ -35,11 +35,6 @@ jobs:
       UPGRADEABLE_CONTRACTS:    "forward-calls set-code-hash"
       DELEGATOR_SUBCONTRACTS:   "accumulator adder subber"
       RUST_BACKTRACE:           full
-      # We need to enable `RUSTC_BOOTSTRAP` so that the nightly ink!
-      # features still work on stable. This is done automatically by
-      # `cargo-contract`, but in our CI here we also use e.g.
-      # `cargo check` directly.
-      RUSTC_BOOTSTRAP:          "1"
     steps:
 
       - uses: actions/setup-node@v3
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 0c0b61f078..7250ced468 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -34,11 +34,6 @@ variables:
   ALL_CRATES:                      "${PURELY_STD_CRATES} ${ALSO_WASM_CRATES}"
   DELEGATOR_SUBCONTRACTS:          "accumulator adder subber"
   UPGRADEABLE_CONTRACTS:           "forward-calls set-code-hash"
-  # We need to enable `RUSTC_BOOTSTRAP` so that the nightly ink!
-  # features still work on stable. This is done automatically by
-  # `cargo-contract`, but in our CI here we also use e.g.
-  # `cargo check` directly.
-  RUSTC_BOOTSTRAP:                 "1"
   # TODO `cargo clippy --verbose --all-targets --all-features` for this crate
   # currently fails on `stable`, but succeeds on `nightly`. This is due to
   # this fix not yet in stable: https://github.com/rust-lang/rust-clippy/issues/8895.
diff --git a/crates/primitives/Cargo.toml b/crates/primitives/Cargo.toml
index 143ab28065..96c1b81ebc 100644
--- a/crates/primitives/Cargo.toml
+++ b/crates/primitives/Cargo.toml
@@ -19,7 +19,7 @@ derive_more = { version = "0.99", default-features = false, features = ["from",
 ink_prelude = { version = "4.0.0-alpha.1", path = "../prelude/", default-features = false }
 scale = { package = "parity-scale-codec", version = "3", default-features = false, features = ["derive", "full"] }
 scale-info = { version = "2", default-features = false, features = ["derive"], optional = true }
-sha2-const = { version = "0.1.2", default-features = false }
+xxhash-rust = { version = "0.8", features = ["const_xxh32"] }
 
 [features]
 default = ["std"]
diff --git a/crates/primitives/src/key.rs b/crates/primitives/src/key.rs
index 7c7ed6a195..5e63ff3ff9 100644
--- a/crates/primitives/src/key.rs
+++ b/crates/primitives/src/key.rs
@@ -13,7 +13,10 @@
 // limitations under the License.
 
 use ink_prelude::vec;
-use sha2_const::Sha256;
+use xxhash_rust::const_xxh32::xxh32;
+
+/// The value 0 is a valid seed.
+const XXH32_SEED: u32 = 0;
 
 /// A key into the smart contract storage.
 ///
@@ -33,18 +36,12 @@ impl KeyComposer {
     /// Concatenate two `Key` into one during compilation.
     pub const fn concat(left: Key, right: Key) -> Key {
         // If one of the keys is zero, then return another without hashing.
-        // If both keys are non-zero, return the hash of both keys.
+        // If both keys are non-zero, return the hash of the XOR difference of both keys.
         match (left, right) {
             (0, 0) => 0,
             (0, _) => right,
             (_, 0) => left,
-            (left, right) => {
-                let hash = Sha256::new()
-                    .update(&left.to_be_bytes())
-                    .update(&right.to_be_bytes())
-                    .finalize();
-                Key::from_be_bytes([hash[0], hash[1], hash[2], hash[3]])
-            }
+            (left, right) => xxh32(&(left ^ right).to_be_bytes(), XXH32_SEED),
         }
     }
 
@@ -59,8 +56,7 @@ impl KeyComposer {
             return 0
         }
 
-        let hash = Sha256::new().update(bytes).finalize();
-        Key::from_be_bytes([hash[0], hash[1], hash[2], hash[3]])
+        xxh32(bytes, XXH32_SEED)
     }
 
     /// Evaluates the storage key of the field in the structure, variant or union.
@@ -69,8 +65,7 @@ impl KeyComposer {
     /// 1. If `variant_name` is not empty then computes the ASCII byte representation and call it `V`.
     /// 1. Compute the ASCII byte representation of `field_name` and call it `F`.
     /// 1. Concatenate (`S` and `F`) or (`S`, `V` and `F`) using `::` as separator and call it `C`.
-    /// 1. Apply the `SHA2` 256-bit hash `H` of `C`.
-    /// 1. The first 4 bytes of `H` make up the storage key.
+    /// 1. The `FNV1A` 32-bit hash of `C` is the storage key.
     ///
     /// # Note
     ///
@@ -119,33 +114,33 @@ mod tests {
     fn concat_works_correct() {
         assert_eq!(KeyComposer::concat(0, 13), 13);
         assert_eq!(KeyComposer::concat(31, 0), 31);
-        assert_eq!(KeyComposer::concat(31, 13), 0xD83A5CD8);
+        assert_eq!(KeyComposer::concat(31, 13), 0x9ab19a67);
         assert_eq!(KeyComposer::concat(0, 0), 0);
     }
 
     #[test]
     fn from_str_works_correct() {
         assert_eq!(KeyComposer::from_str(""), 0);
-        assert_eq!(KeyComposer::from_str("123"), 0xa665a459);
-        assert_eq!(KeyComposer::from_str("Hello world"), 0x64ec88ca);
+        assert_eq!(KeyComposer::from_str("123"), 0xb6855437);
+        assert_eq!(KeyComposer::from_str("Hello world"), 0x9705d437);
     }
 
     #[test]
     fn from_bytes_works_correct() {
         assert_eq!(KeyComposer::from_bytes(b""), 0);
-        assert_eq!(KeyComposer::from_bytes(b"123"), 0xa665a459);
-        assert_eq!(KeyComposer::from_bytes(b"Hello world"), 0x64ec88ca);
+        assert_eq!(KeyComposer::from_bytes(b"123"), 0xb6855437);
+        assert_eq!(KeyComposer::from_bytes(b"Hello world"), 0x9705d437);
     }
 
     #[test]
     fn compute_key_works_correct() {
         assert_eq!(
             KeyComposer::compute_key("Contract", "", "balances"),
-            Ok(0x05e859ec)
+            Ok(0xf820ff02)
         );
         assert_eq!(
             KeyComposer::compute_key("Enum", "Variant", "0"),
-            Ok(0x9d029590)
+            Ok(0x14786b51)
         );
         assert_eq!(
             KeyComposer::compute_key("", "Variant", "0"),


Test patch:
diff --git a/crates/ink/tests/ui/storage_item/fail/collections_only_packed_1.stderr b/crates/ink/tests/ui/storage_item/fail/collections_only_packed_1.stderr
index 194d2ad17e..72ccdd0dcf 100644
--- a/crates/ink/tests/ui/storage_item/fail/collections_only_packed_1.stderr
+++ b/crates/ink/tests/ui/storage_item/fail/collections_only_packed_1.stderr
@@ -7,7 +7,7 @@ error[E0277]: the trait bound `Vec<NonPacked>: parity_scale_codec::Decode` is no
    = help: the trait `parity_scale_codec::Decode` is implemented for `Vec<T>`
    = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 
 error[E0277]: the trait bound `[NonPacked]: Encode` is not satisfied
   --> tests/ui/storage_item/fail/collections_only_packed_1.rs:11:8
@@ -21,7 +21,7 @@ error[E0277]: the trait bound `[NonPacked]: Encode` is not satisfied
    = note: required because of the requirements on the impl of `Encode` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 
 error[E0277]: the trait bound `Vec<NonPacked>: parity_scale_codec::Decode` is not satisfied
   --> tests/ui/storage_item/fail/collections_only_packed_1.rs:9:1
@@ -32,7 +32,7 @@ error[E0277]: the trait bound `Vec<NonPacked>: parity_scale_codec::Decode` is no
    = help: the trait `parity_scale_codec::Decode` is implemented for `Vec<T>`
    = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 note: required because it appears within the type `Contract`
   --> tests/ui/storage_item/fail/collections_only_packed_1.rs:10:8
    |
@@ -57,7 +57,7 @@ error[E0277]: the trait bound `[NonPacked]: Encode` is not satisfied
    = note: required because of the requirements on the impl of `Encode` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 note: required because it appears within the type `Contract`
   --> tests/ui/storage_item/fail/collections_only_packed_1.rs:10:8
    |
@@ -79,7 +79,7 @@ error[E0277]: the trait bound `Vec<NonPacked>: parity_scale_codec::Decode` is no
     = help: the trait `parity_scale_codec::Decode` is implemented for `Vec<T>`
     = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
     = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 note: required because it appears within the type `Contract`
    --> tests/ui/storage_item/fail/collections_only_packed_1.rs:10:8
     |
@@ -104,7 +104,7 @@ error[E0277]: the trait bound `[NonPacked]: Encode` is not satisfied
     = note: required because of the requirements on the impl of `Encode` for `Vec<NonPacked>`
     = note: required because of the requirements on the impl of `Packed` for `Vec<NonPacked>`
     = note: required because of the requirements on the impl of `StorableHint<()>` for `Vec<NonPacked>`
-    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `Vec<NonPacked>`
+    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `Vec<NonPacked>`
 note: required because it appears within the type `Contract`
    --> tests/ui/storage_item/fail/collections_only_packed_1.rs:10:8
     |
diff --git a/crates/ink/tests/ui/storage_item/fail/collections_only_packed_2.stderr b/crates/ink/tests/ui/storage_item/fail/collections_only_packed_2.stderr
index 84f12b8ef7..921762a341 100644
--- a/crates/ink/tests/ui/storage_item/fail/collections_only_packed_2.stderr
+++ b/crates/ink/tests/ui/storage_item/fail/collections_only_packed_2.stderr
@@ -7,7 +7,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: parity_scale_codec::De
    = help: the trait `parity_scale_codec::Decode` is implemented for `BTreeMap<K, V>`
    = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 
 error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: Encode` is not satisfied
   --> tests/ui/storage_item/fail/collections_only_packed_2.rs:11:8
@@ -18,7 +18,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: Encode` is not satisfi
    = help: the trait `Encode` is implemented for `BTreeMap<K, V>`
    = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 
 error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: parity_scale_codec::Decode` is not satisfied
   --> tests/ui/storage_item/fail/collections_only_packed_2.rs:9:1
@@ -29,7 +29,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: parity_scale_codec::De
    = help: the trait `parity_scale_codec::Decode` is implemented for `BTreeMap<K, V>`
    = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 note: required because it appears within the type `Contract`
   --> tests/ui/storage_item/fail/collections_only_packed_2.rs:10:8
    |
@@ -51,7 +51,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: Encode` is not satisfi
    = help: the trait `Encode` is implemented for `BTreeMap<K, V>`
    = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
    = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+   = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 note: required because it appears within the type `Contract`
   --> tests/ui/storage_item/fail/collections_only_packed_2.rs:10:8
    |
@@ -73,7 +73,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: parity_scale_codec::De
     = help: the trait `parity_scale_codec::Decode` is implemented for `BTreeMap<K, V>`
     = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
     = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 note: required because it appears within the type `Contract`
    --> tests/ui/storage_item/fail/collections_only_packed_2.rs:10:8
     |
@@ -95,7 +95,7 @@ error[E0277]: the trait bound `BTreeMap<u128, NonPacked>: Encode` is not satisfi
     = help: the trait `Encode` is implemented for `BTreeMap<K, V>`
     = note: required because of the requirements on the impl of `Packed` for `BTreeMap<u128, NonPacked>`
     = note: required because of the requirements on the impl of `StorableHint<()>` for `BTreeMap<u128, NonPacked>`
-    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<2085512762_u32>>` for `BTreeMap<u128, NonPacked>`
+    = note: required because of the requirements on the impl of `AutoStorableHint<ManualKey<453539032_u32>>` for `BTreeMap<u128, NonPacked>`
 note: required because it appears within the type `Contract`
    --> tests/ui/storage_item/fail/collections_only_packed_2.rs:10:8
     |