Comprometendo-se com grandes conjuntos de dados usando árvores Merkle no PyTeal - Algorand

Ori Shem TovFundação Algorand
10 de janeiro de 2022
Ver código

Visão geral

Introdução

Armazenar dados on-chain pode ser muito caro, pois cada parte de dados é duplicada em todos os nós. Na Algorand especificamente, você pode teoricamente armazenar uma quantidade muito grande de estado por contrato inteligente, utilizando o armazenamento local de muitas contas. No entanto, o custo (em termos de saldo mínimo) pode se tornar rapidamente proibitivo.

Como você pode imaginar, não há solução mágica. Este artigo está sugerindo uma compensação: os dados precisam ser armazenados fora da cadeia e fornecidos como argumento para o contrato inteligente (com informações adicionais usadas para verificar esses dados). Para muitos aplicativos que usam grande quantidade de dados, essa compensação é muito razoável.

Esta solução está aqui para fornecer uma maneira de permitir que os contratos inteligentes armazenem um pequeno valor que represente (ou se comprometa com) uma quantidade potencialmente muito grande de dados usando árvores Merkle.

Uma árvore de Merkle é uma estrutura de dados de árvore (tipicamente binária) na qual cada nó folha armazena um hash criptográfico de um bloco de dados, e cada nó fora da folha não armazena um hash criptográfico da junção de seus nós filhos. Essa estrutura permite a verificação eficiente e segura do conteúdo de grandes estruturas de dados.

A imagem abaixo mostra uma árvore Merkle de altura 2 se comprometendo com os dados L1, L2, L3, L4.
L1, L2, L3, L4 podem ser dados arbitrários armazenados fora da cadeia.

A raiz da árvore (também conhecida como hash superior) define exclusivamente (ou se compromete com) o valor L1, L2, L3, L4. Portanto, basta armazenar essa raiz no contrato inteligente.

Da Wikipédia :

Nesta solução, vamos demonstrar como criar e usar árvores Merkle usando Contratos Inteligentes da Algorand gerados com PyTeal (TEAL v5).

VISÃO GERAL DO PROJETO

Suposições

Nesta solução, assumimos que a altura da árvore é fixa e cada folha vazia contém o valor de hash de uma string vazia. Por exemplo na imagem acima, quando inicializamos a árvore, L1, L2, L3 e L4são strings vazias e a altura da árvore é fixada em 2.

Estado

Nosso contrato inteligente contém 2 variáveis ​​de estado globais:

1. Raiz - uma fatia de byte que contém o Top Hash da árvore.
2. Tamanho - o número de elementos na árvore. No início, Size é definido como 0 e Root é calculado como se as folhas da árvore fossem todos hashes de fatias de bytes vazias (e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 quando a altura da árvore é 2).

Isso significa que o valor Root depende da altura da árvore.

Operações

Nossa árvore Merkle suporta 3 operações:

1.anexar - adiciona um novo bloco de dados ao final da sequência de dados.
2.verificar - verifica se um bloco de dados está armazenado na árvore.
3.atualizar - atualiza um bloco de dados existente.

As operações acima esperam receber entrada por meio da matriz de argumentos do aplicativo e todas compartilham os mesmos esquemas:

1. Primeiro argumento: nome-do-comando - anexar , verificar ou atualizar
2. Segundo argumento: valor - o valor que desejamos anexar/verificar/ atualizar (na imagem acima, Li para i em [1,2,3,4])
3. Terceiro argumento e assim por diante: sibling1 , sibling2 … - uma lista de irmãos na árvore. Mais detalhes abaixo.

Além disso, o comando atualizar também espera que o último argumento seja o novo valor a ser atualizado.

• comando de acréscimo
  Esta operação espera receber o novo bloco de dados para anexar e seus irmãos ao longo do caminho para a raiz. Por exemplo, no diagrama acima, para anexar L1(supondo que a árvore esteja vazia), o usuário forneceria L1, Hash 0-1 e Hash 1.
  O contrato inteligente verificará se a posição de L1 está realmente vazia e, em seguida, atualizará o Root com o novo valor e incrementará o Size.
  Observe que neste ponto L2, L3 e L4 são definidos como string vazia e Hash 0-1 é o hash da string vazia.

• comando de verificação
  Semelhante à operação de acréscimo , verifique espera um valor e irmãos.
  Por exemplo, no diagrama acima, para verificar L1 o usuário forneceria L1, Hash 0-1 e Hash 1.
  O contrato inteligente verificará se a posição de L1 realmente mantém seu bloco de dados esperado.

• comando de atualização
  Esta operação pode ser pensada como uma composição das operações acima.
  Neste caso são esperados 2 valores: valor antigo e valor novo .
  O contrato inteligente primeiro verificará se o valor antigo está na posição correta na árvore e, em seguida, calculará e atualizará o valor Root usando o novo valor.

Passando a lista de irmãos
Como mencionado acima, todos os três comandos esperam receber uma lista de irmãos onde cada irmão é uma fatia de byte contendo o valor de hash de seu nó na árvore.
Como as árvores Merkle são binárias, precisamos marcar cada irmão se for direito ou esquerdo.
Para isso, cada irmão manterá sua orientação como o primeiro byte da fatia de bytes: 0xaa para a direita e 0xbb para a esquerda.

O primeiro irmão na lista é o 1st irmão da ordem, o segundo é o 2nd da ordem (ou seja, irmão do pai) etc.

Com este método garantimos que a posição do valor a anexar/verificar/atualizar é determinística.

Código PyTeal

Agora, vamos entrar na implementação real.

Estaremos usando PyTeal para gerar um TEAL v5 script que será executado AVM 1.0 como um contrato inteligente.

SUB-ROTINAS ÚTEIS

Uma vez que o cálculo da raiz é o núcleo, vamos introduzir uma sub-rotina TEAL apenas para isso:

TREE_HEIGHT = Int(2)
FIRST_SIBLING_INDEX = Int(2)
LAST_SIBLING_INDEX = FIRST_SIBLING_INDEX + TREE_HEIGHT - Int(1)

LEFT_SIDE = Int(170)  # Bytes("base16", "aa")

@Subroutine(TealType.bytes)
def hash_concat(left: TealType.bytes, right: TealType.bytes):
    return Sha256(Concat(left, right))

@Subroutine(TealType.bytes)
def calc_root(init_value: Expr):
    i = ScratchVar(TealType.uint64)
    result = ScratchVar(TealType.bytes)

    init = i.store(FIRST_SIBLING_INDEX)
    cond = i.load() <= LAST_SIBLING_INDEX
    itr = i.store(i.load() + Int(1))
    return Seq(
        result.store(init_value),
        For(init, cond, itr).Do(
            result.store(
                If(GetByte(Txn.application_args[i.load()], Int(0)) == LEFT_SIDE)
                .Then(
                    hash_concat(
                        result.load(),
                        Extract(Txn.application_args[i.load()], Int(1), Int(32)),
                    )
                )
                .Else(
                    hash_concat(
                        Extract(Txn.application_args[i.load()], Int(1), Int(32)),
                        result.load(),
                    )
                )
            )
        ),
        result.load(),
    )

calc_root simplesmente itera sobre a lista de irmãos, concatenando-os de acordo com cada orientação e hash. A init_value é uma expressão TEAL que avalia o hash do valor da folha a partir do qual desejamos iniciar nossa computação.
Observe que os For limites do loop são constantes: o FIRST_SIBLING_INDEX que é definido como 2 e o LAST_SIBLING_INDEX que é definido como FIRST_SIBLING_INDEX + TREE_HEIGHT - 1.
A próxima sub-rotina é para calcular a inicial Root quando a árvore está vazia:

@Subroutine(TealType.bytes)
def calc_init_root(tree_height: Expr):
    i = ScratchVar(TealType.uint64)
    result = ScratchVar(TealType.bytes)

    init = i.store(Int(0))
    cond = i.load() < tree_height
    itr = i.store(i.load() + Int(1))
    return Seq([
        result.store(Sha256(Bytes(''))),
        For(init, cond, itr).Do(
            result.store(Sha256(Concat(result.load(), result.load())))
        ),
        result.load()
    ])

Isso será usado pela sequência de criação:

on_creation = Seq([
        App.globalPut(Bytes('Root'), calc_init_root(TREE_HEIGHT)),  # init root
        App.globalPut(Bytes('Size'), Int(0)),  # init size
        Approve()
    ])

Observe que a Root inicial pode realmente ser pré-computada, mas como o orçamento do opcode é suficiente, podemos fazê-lo em TEAL.

anexar sequência

A sequência de acréscimo valida primeiro se o número correto de argumentos do aplicativo foi recebido e se o valor a ser acrescentado não é uma fatia de byte vazia.

Em seguida, ele valida que a posição (derivada das orientações dos irmãos) está vazia, calculando a raiz esperada da posição específica e comparando-a com a Root.

Caso todas as asserções sejam aprovadas, as variáveis ​​de estado Root e Size são atualizadas para o novo estado.

append = Seq([Assert(Txn.application_args.length() == Int(NUM_APP_ARGS_APPEND)),
        Assert(Txn.application_args[VALUE_INDEX] != Bytes('')),
        Assert(App.globalGet(Bytes('Root')) == calc_root(
            Sha256(Bytes(''))
        )),
        App.globalPut(Bytes('Root'), calc_root(
            Sha256(
                Txn.application_args[VALUE_INDEX]
            )
        )),
        App.globalPut(Bytes('Size'), App.globalGet(Bytes('Size')) + Int(1)),
        Int(1)
    ])

Observe que temos as seguintes constantes no código:

• NUM_APP_ARGS_APPEND - o número de argumentos esperados para a operação de acréscimo.
• VALUE_INDEX - índice do valor na matriz de argumentos do aplicativo. verificar a sequência A sequência de verificação valida primeiro se o número correto de argumentos do aplicativo foi recebido. Em seguida, ela calcula a raiz esperada de acordo com o valor e a matriz de irmãos e a compara com o valor real Root.

verify = Seq([
        Assert(Txn.application_args.length() == Int(NUM_APP_ARGS_VERIFY)),
        Assert(App.globalGet(Bytes('Root')) == calc_root(
            Sha256(Txn.application_args[VALUE_INDEX])
        )),
        Int(1)
    ])

NUM_APP_ARGS_VERIFY - o número de argumentos esperados para a operação de verificação.
sequência de atualização
A sequência de atualização valida primeiro se o número correto de argumentos do aplicativo foi recebido e se o valor a ser atualizado não é uma fatia de byte vazia.
Em seguida, ele calcula a raiz esperada de acordo com o valor e a matriz de irmãos e a compara com o valor real Root.
Caso todas as asserções sejam aprovadas, as variáveis Root e Size ​​de estado são atualizadas para o novo estado.

update = Seq([
        Assert(Txn.application_args.length() == Int(NUM_APP_ARGS_UPDATE)),
        Assert(Txn.application_args[UPDATE_VALUE_INDEX] != Bytes('')),
        Assert(App.globalGet(Bytes('Root')) == calc_root(
            Sha256(
                Txn.application_args[VALUE_INDEX]
            )
        )),
        App.globalPut(Bytes('Root'), calc_root(
            Sha256(
                Txn.application_args[UPDATE_VALUE_INDEX]
            )
        )),
        Int(1)
    ])

Observe que temos as seguintes constantes no código:

• NUM_APP_ARGS_UPDATE - o número de argumentos esperados para a operação de atualização .
• VALUE_INDEX - índice do valor old na matriz de argumentos do aplicativo.
• UPDATE_VALUE_INDEX - índice do valor new na matriz de argumentos do aplicativo. O programa de aprovação O programa de aprovação final é simplesmente um roteador para todas as sequências acima, além de permitir OptIn a todos e restringir DeleteApplicatione e UpdateApplication de qualquer pessoa que não seja o criador do aplicativo.

program = Cond(
        [
            Txn.application_id() == Int(0),
            on_creation
        ],
        [
            Txn.on_completion() == OnComplete.OptIn,
            Approve()
        ],
        [
            Txn.on_completion() == OnComplete.DeleteApplication, 
            Return(Txn.sender() == Global.creator_address())
        ],
        [
            Txn.on_completion() == OnComplete.UpdateApplication,
            Return(Txn.sender() == Global.creator_address())
        ],
        [
            Txn.on_completion() == OnComplete.NoOp,
            Cond(
                [
                    Txn.application_args[COMMAND_INDEX] == Bytes('verify'), 
                    Return(verify)
                ],
                [
                    Txn.application_args[COMMAND_INDEX] == Bytes('append'), 
                    Return(append)
                ],
                [
                    Txn.application_args[COMMAND_INDEX] == Bytes('update'),                
                    Return(update)
                ]
            )
        ]
    )

USO

Compile o contrato inteligente

goal app create --creator $creator \
    --approval-prog ./mt_approval.teal --clear-prog ./mt_clear.teal \
    --global-byteslices 1 --global-ints 1 --local-byteslices 0 --local-ints 0

mt_approval.teal é o script TEAL gerado a partir do código pyteal acima.
mt_clear.teal é um script TEAL simples que retorna 1 para cada chamada.
Ambos podem ser facilmente gerados usando o código pyteal no repositório do Github.

Anexando

goal app call \
    --app-id $app_id \
    --app-arg "str:append" \
    --app-arg "str:record0" \ # L1
    --app-arg "b64:quOwxEKY/BwUmvv0yJlvuSQnrkHkZJuTTKSVmRt4UrhV" \ # Hash 0-1
    --app-arg "b64:qi26XbwznnMWrqJoP6+DnBt7HuIxPbeSESWIEY3wZqo1" \ # Hash 1
    --from $creator

Observe que como Hash 0-1 e Hash 1 estão orientados à direita, têm o prefixo byte 0xaa.

Verificando

goal app call \
    --app-id $app_id \
    --app-arg "str:verify" \
    --app-arg "str:record0" \ # L1
    --app-arg "b64:quOwxEKY/BwUmvv0yJlvuSQnrkHkZJuTTKSVmRt4UrhV" \ # Hash 0-1
    --app-arg "b64:qi26XbwznnMWrqJoP6+DnBt7HuIxPbeSESWIEY3wZqo1" \ # Hash 1
    --from $creator

Atualizando

goal app call \
    --app-id $app_id \
    --app-arg "str:update" \
    --app-arg "str:record0" \ # L1
    --app-arg "b64:quOwxEKY/BwUmvv0yJlvuSQnrkHkZJuTTKSVmRt4UrhV" \ # Hash 0-1
    --app-arg "b64:qi26XbwznnMWrqJoP6+DnBt7HuIxPbeSESWIEY3wZqo1" \ # Hash 1
    --app-arg "str:new_record0" \ # new L1 value
    --from $creator

ALGUMAS ADVERTÊNCIAS

O uso dessa implementação de contrato inteligente com árvores grandes pode exceder o limite de custo operacional permitido para contratos inteligentes no AVM.

Felizmente, podemos usar o recurso de orçamento de opcode agrupado do AVM agrupando nossas chamadas de aplicativos originais com chamadas de aplicativos “fictícias” e, assim, aumentando nosso orçamento operacional.

Por exemplo, poderíamos criar o seguinte código de aprovação para usar como um aplicativo “Fictício”:

def dummy_approval():
    return Approve()

O código acima tem o custo operacional mínimo para um programa TEAL e, portanto, agrupar chamadas para ele com outras chamadas “caras” aumentará substancialmente nosso orçamento operacional.

Comentários e extensões

• Esta solução destina-se apenas a fins de aprendizagem. Não cobre a verificação de erros e outros casos extremos. Os contratos inteligentes nesta solução NÃO foram auditados. Portanto, ele não deve ser usado como um aplicativo de produção.
• Há muitas maneiras de ajustar o design para diferentes propósitos. Por exemplo, o contrato inteligente também pode calcular o índice do valor (a partir das orientações de irmãos 0xaa/ 0xbb) e produzi-lo como uma variável de bloco de rascunho para outra transação.
• Na produção, recomenda-se usar a separação de domínio para hash, que é prefixar valores a serem hash por algum prefixo exclusivo (e um prefixo diferente para o hash de dados como Hash 0-0 e os hashes “internos” como Hash 0 e root)

Esse artigo foi escrito por Ori Shem-Tov e traduzido por Arnaldo Campos. Seu original pode ser lido aqui.