hashedmap_en.md

HashedMap

HashedMap 简体中文版

Map is a very commonly used data structure. sCrypt's standard library provides a library contract HashedMap that implements the Map data structure. The concept is similar to the map in java and the dictionary in python, but there are some differences in usage.

Definition of HashedMap

In HashedMap, there are no restrictions on the types of key and value. They can be basic data types such as integers, bytes, and booleans, or they can be complex data structures such as arrays and structures. The syntax for defining HashedMap is as follows:

1. Full definition

HashedMap<int, int> map = new HashedMap<int, int>(b'')

2. Abbreviated definition on the right

HashedMap<int, int> map = new HashedMap(b'')

3. Use the auto keyword definition

auto map = new HashedMap<int, int>(b'')

Serialization

The data() method can serialize HashedMap into bytes. scryptlib also provides the corresponding toData(map) function. Used to serialize the HashedMap off-chain.

Below is a stateful contract with HashedMap as the state.

contract StateMapTest {

    @state
    bytes _mpData;  //Save the serialized data of the map

    // Add key-value pairs to the map
    public function insert(MapEntry entry, SigHashPreimage preimage) {
        require(Tx.checkPreimage(preimage));
        HashedMap<int, int> map = new HashedMap(this._mpData);
        require(map.set(entry.key, entry.val, entry.keyIndex));
        require(this.passMap(map.data(), preimage));
    }

    // update key-value pairs in the map
    public function update(MapEntry entry, SigHashPreimage preimage) {
        require(Tx.checkPreimage(preimage));
        HashedMap<int, int> map = new HashedMap(this._mpData);
        require(map.set(entry.key, entry.val, entry.keyIndex));
        require(this.passMap(map.data(), preimage));
    }

    // delete key-value pairs in the map
    public function delete(int key, int keyIndex, SigHashPreimage preimage) {
        require(Tx.checkPreimage(preimage));
        HashedMap<int, int> map = new HashedMap(this._mpData);
        require(map.delete(key, keyIndex));
        // Serialize map, update state
        require(this.passMap(map.data(), preimage));
    }

    // update state _mpData, and build a output contains new state
    function passMap(bytes newData, SigHashPreimage preimage) : bool {
        this._mpData = newData;
        bytes outputScript = this.getStateScript();
        bytes output = Util.buildOutput(outputScript, Util.value(preimage));
        return (hash256(output) == Util.hashOutputs(preimage));
    }
}

Add Element

The HashedMap contract provides many useful methods. To add key-value pairs, you can use the set(K key, V val, int keyIndex) method of the HashedMap contract. Unlike map in other languages, adding key-value pairs requires passing the keyIndex parameter, which can be calculated off-chain by the findKeyIndex function provided by scryptlib. First, we need to maintain a map outside the chain that is synchronized with the chain, and add the elements to be added to the map first. Then use findKeyIndex to calculate keyIndex.

scrypt:

public function insert(MapEntry entry, SigHashPreimage preimage) {
    require(Tx.checkPreimage(preimage));
    HashedMap<int, int> map = new HashedMap(this._mpData);
    require(map.set(entry.key, entry.val, entry.keyIndex));
    require(this.passMap(map.data(), preimage));
}

typescript:

let map = new Map<number, number>();
map.set(key, val);  // First add the key-value pair to the map outside the chain

const tx = buildTx(map);
const preimage = getPreimage(tx, mapTest.lockingScript, inputSatoshis)
const result = mapTest.insert(new MapEntry({
    key: key,
    val: val,
    keyIndex: findKeyIndex(map, key) // Get the `keyIndex` parameter
}), preimage).verify()
expect(result.success, result.error).to.be.true;

mapTest._mpData = toData(map)

If you add all the elements to the map before starting to calculate the keyIndex, you need to convert the map into an ordered array first. Use the following code to convert directly:

const mapEntrys = Array.from(sortmap(map), ([key, val]) => ({ key, val }))
    .map((entry, index) => {
        ...entry,
        keyIndex: index
    })

Update Element

Updating elements is the same as adding elements, using the set(K key, V val, int keyIndex) method of the HashedMap contract.

Delete Element

Use the delete(K key, int keyIndex) method of the HashedMap contract to delete elements. If the deleted element does not exist, it will return failure. It is also necessary to use the findKeyIndex(map, key) function outside the chain to calculate the keyIndex.

scrypt:

public function delete(int key, int keyIndex, SigHashPreimage preimage) {
    require(Tx.checkPreimage(preimage));
    HashedMap<int, int> map = new HashedMap(this._mpData);
    require(map.delete(key, keyIndex));
    require(this.passMap(map.data(), preimage));
}

typescript:

const keyIndex = findKeyIndex(map, key);  // Before deleting from the off-chain map, first calculate the keyIndex and save it
map.delete(key);

const tx = buildTx(map);
const preimage = getPreimage(tx, mapTest.lockingScript, inputSatoshis)

const result = mapTest.delete(key, keyIndex, preimage).verify()  // To call the delete method of the contract, you need to provide the key and keyIndex
expect(result.success, result.error).to.be.true;

mapTest._mpData = toData(map)

Storage Model

HashedMap only stores the hash of key and value. It is not possible to deserialize the original key-value pairs through the serialization of data of HashedMap. This is very helpful for some privacy-focused application scenarios. You can pass in the original key-value pair from the outside and call the canGet(key, val, keyIndex) interface to check whether a key-value pair is included.

require(map.canGet(key, val, keyIndex));

Or check whether a key is included through the has(key, keyIndex) interface.

require(map.has(key, keyIndex));