sui_types/
global_state_hash.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// Copyright (c) Mysten Labs, Inc.
// SPDX-License-Identifier: Apache-2.0

/// A type to represent the root hash of all live objects in the network.
pub type GlobalStateHash = fastcrypto::hash::EllipticCurveMultisetHash;

#[cfg(test)]
mod tests {
    use crate::base_types::ObjectDigest;
    use crate::global_state_hash::GlobalStateHash;
    use fastcrypto::hash::MultisetHash;
    use rand::seq::SliceRandom;

    #[test]
    fn test_global_state_hash() {
        let ref1 = ObjectDigest::random();
        let ref2 = ObjectDigest::random();
        let ref3 = ObjectDigest::random();
        let ref4 = ObjectDigest::random();

        let mut a1 = GlobalStateHash::default();
        a1.insert(ref1);
        a1.insert(ref2);
        a1.insert(ref3);

        // Insertion out of order should arrive at the same result.
        let mut a2 = GlobalStateHash::default();
        a2.insert(ref3);
        assert_ne!(a1, a2);
        a2.insert(ref2);
        assert_ne!(a1, a2);
        a2.insert(ref1);
        assert_eq!(a1, a2);

        // GlobalStateHash is not a set, and inserting the same element twice will change the result.
        a2.insert(ref3);
        assert_ne!(a1, a2);
        a2.remove(ref3);

        a2.insert(ref4);
        assert_ne!(a1, a2);

        // Supports removal.
        a2.remove(ref4);
        assert_eq!(a1, a2);

        // Removing elements out of order should arrive at the same result.
        a2.remove(ref3);
        a2.remove(ref1);

        a1.remove(ref1);
        a1.remove(ref3);

        assert_eq!(a1, a2);

        // After removing all elements, it should be the same as an empty one.
        a1.remove(ref2);
        assert_eq!(a1, GlobalStateHash::default());
    }

    #[test]
    fn test_global_state_hash_commutativity() {
        let ref1 = ObjectDigest::random();
        let ref2 = ObjectDigest::random();
        let ref3 = ObjectDigest::random();

        let mut a1 = GlobalStateHash::default();
        a1.remove(ref1);
        a1.remove(ref2);
        a1.insert(ref1);
        a1.insert(ref2);

        // Removal before insertion should yield the same result
        assert_eq!(a1, GlobalStateHash::default());

        a1.insert(ref1);
        a1.insert(ref2);

        // Insertion out of order should arrive at the same result.
        let mut a2 = GlobalStateHash::default();
        a2.remove(ref1);
        a2.remove(ref2);

        // Unioning where all objects from a are removed in b should
        // result in empty global_state_hash
        a1.union(&a2);
        assert_eq!(a1, GlobalStateHash::default());

        a1.insert(ref1);
        a1.insert(ref2);
        a1.insert(ref3);

        let mut a3 = GlobalStateHash::default();
        a3.insert(ref3);

        // a1: (+ref1, +ref2, +ref3)
        // a2: (-ref1, -ref2)
        // a3: (+ref3)
        // a1 + a2 = a3

        a1.union(&a2);
        assert_eq!(a1, a3);
    }

    #[test]
    fn test_global_state_hash_insert_stress() {
        let mut refs: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
        let mut global_state_hash = GlobalStateHash::default();
        global_state_hash.insert_all(&refs);
        let mut rng = rand::thread_rng();
        (0..10).for_each(|_| {
            refs.shuffle(&mut rng);
            let mut a = GlobalStateHash::default();
            a.insert_all(&refs);
            assert_eq!(global_state_hash, a);
        })
    }

    #[test]
    fn test_global_state_hash_remove_stress() {
        let mut refs1: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
        let mut refs2: Vec<_> = (0..100).map(|_| ObjectDigest::random()).collect();
        let mut global_state_hash = GlobalStateHash::default();
        global_state_hash.insert_all(&refs1);

        let mut rng = rand::thread_rng();
        (0..10).for_each(|_| {
            refs1.shuffle(&mut rng);
            let mut a = GlobalStateHash::default();
            a.insert_all(&refs1);
            a.insert_all(&refs2);
            refs2.shuffle(&mut rng);
            a.remove_all(&refs2);
            assert_eq!(global_state_hash, a);
        })
    }
}