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 L4
são strings vazias e a altura da árvore é fixada em 2
.
Estado
Nosso contrato inteligente contém 2 variáveis de estado globais:
- Raiz - uma fatia de byte que contém o Top Hash da árvore.
-
Tamanho - o número de elementos na árvore.
No início,
Size
é definido como0
eRoot
é 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:
- Primeiro argumento: nome-do-comando - anexar , verificar ou atualizar
- Segundo argumento: valor - o valor que desejamos anexar/verificar/ atualizar (na imagem acima,
Li
parai
em[1,2,3,4]
) - 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 anexarL1
(supondo que a árvore esteja vazia), o usuário forneceriaL1
,Hash 0-1
eHash 1
.
O contrato inteligente verificará se a posição deL1
está realmente vazia e, em seguida, atualizará oRoot
com o novo valor e incrementará oSize
.
Observe que neste pontoL2
,L3
eL4
são definidos como string vazia eHash 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 verificarL1
o usuário forneceriaL1
,Hash 0-1
eHash 1
.
O contrato inteligente verificará se a posição deL1
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 valorRoot
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 realRoot
.
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 valorold
na matriz de argumentos do aplicativo. -
UPDATE_VALUE_INDEX
- índice do valornew
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 permitirOptIn
a todos e restringirDeleteApplicatione
eUpdateApplication
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.
Latest comments (0)