Hash Map Design Pattern

May 19, 2022

Hash Tables or dictionaries are valuable data structures that are used to build associations between keys and corresponding values for quick, constant-time lookup and retrieval. While Solidity provides the Mapping type data structure that is similar to hash tables, the Algorand Virtual Machine doesn’t natively support hash tables or mapping type data structures (full list of supported data types can be found here). Nevertheless, a combination of smart signature and stateful smart contract can be used to build something similar to the mapping type data structure.

In principle, since the Algorand stateful smart contract can store up to 64 key-value pairs in its global state and it conceptually functions as a hash table but 64 key-value pairs are often not enough for practical use cases such as a domain name service. The Hash Table design described in this article enables a mapping of practically (limits of SHA512_256 cryptographic hash functions still apply) unlimited number of key-value pairs.

Hash function

A hash function is used in a hash table to generate an index to a storage location based on the input key where the corresponding value will be stored. The hash function produces a deterministic, fixed-size index for variable-sized input. And in AVM, the generation of contract account can be used as a hash function by standardizing a smart signature program with variable inputs that are compiled to generate a contract account. The contract account can then be used as a storage location in a stateful smart contract for storing corresponding values. AVM 1.1 supports two modes of use for smart-signatures: Contract account and Delegated approval.

Mapping

Stateful smart contracts allow an unlimited number of accounts to opt-in and access local state in the application. And the contract accounts generated from the standardized program (hash function) can be used to opt-in to the smart contract and store corresponding value in the smart contract’s local state. Depending on the stateful smart contract’s schema, upto 16 key-value pairs can be stored per account in the local state of a smart contract.

Lookup

The smart signature contract account can be regenerated by using the same input to the standardized program. Since the process of generating the smart signature contract (through program compilation) account involves the process of evaluating SHA512_256 hash of the program, we can be certain that the output is deterministic and unique.

Security

It is important to note that anyone with access to the Smart Signature program will be able to authorize transactions from that account. Hence, changes to the local state of the smart contract corresponding to a smart signature account must be fully secured. Guidelines and best practices recommended by Algorand must be strictly followed. Especially RekeyTo property must be validated as set to ZeroAddress to ensure the generated smart signature contract is not rekeyed to an attacker’s wallet account.

Example:

Consider the simple Smart Signature program:

from pyteal import *

def ValidateRecord(name):

    program = Cond(
        [Len(Bytes(name)) >= Int(3), Return(Int(1))]
    )

    return program

and a simple smart contract:

from pyteal import *

def approval_program():

    optin_to_app = Seq([
        App.localPut(Int(0), Bytes("registered"), Int(1)),
        Return(Int(1))
    ])

    program = Cond(
        [Txn.application_id() == Int(0), Return(Int(1))],
        [Txn.on_completion() == OnComplete.OptIn, optin_to_app]
    )

    return program

def clear_state_program():
    return Int(0)

We can generate a logic signature account by:

from pyteal import *
from lsig import ValidateRecord

logic_sig_teal = compileTeal(ValidateRecord("ans"), Mode.Signature, version=5)

compiled_logic_sig_teal = compile_program(algod_client, str.encode(logic_sig_teal))

lsig = LogicSig(compiled_logic_sig_teal)

The address of logic sig:

print(lsig.address())

The lsig account can opt into a smart contract and utilize its local storage:

# Creating an optin txn

optin_txn_unsigned = transaction.ApplicationOptInTxn(lsig.address(), algod_client.suggested_params(), APP_ID)

# Signing the optin txn

optin_signed_txn = LogicSigTransaction(optin_txn_unsigned, lsig)

# Send txn to network

algod_client.send_transactions(optin_signed_txn)

Algorand Name Service