Ergo e o Mecanismo de Consenso Autolykos: Parte I

A seguir, uma análise técnica detalhada do mecanismo de consenso do Ergo, Autolykos. Como este é um tópico extenso e detalhado, publicaremos em segmentos ao longo das próximas duas semanas. Na Parte I, o autor começa a analisar o pseudocódigo de mineração de blocos e nos guia pela criação da "lista R."

Parte I

Autolykos, o mecanismo de consenso do Ergo, é um dos poucos quebra-cabeças de prova de trabalho assimétricos e resistentes a ASIC - garantindo assim que a blockchain permaneça o mais descentralizada possível. Autolykos é baseado no artigo Equihash[1] e no problema do aniversário. Para resumir, o minerador tem a tarefa de encontrar k (=32) entre N elementos, de modo que o hash da soma dos elementos seja menor que o alvo. O seguinte pseudocódigo explica o processo de mineração e esta análise irá detalhar cada linha extensivamente, uma vez que há muito poucos recursos online que explicam o Autolykos em sua totalidade.

Pseudocódigo de Mineração de Blocos Autolykos

Antes de discutir o procedimento de mineração de blocos, o algoritmo primeiro requer um grupo cíclico muito grande G de ordem prima q com gerador fixo g e elemento identidade e. Este grupo primo é usado para retornar inteiros em Z/qZ durante a função de hash baseada em Blake2b256.

Exemplo de grupo cíclico com gerador z, elemento identidade 1, ordem 6[2]

Não nos concentraremos extensivamente no grupo cíclico, pois ele cobre apenas um pequeno segmento do esquema de PoW. Agora, vamos abordar a mineração de blocos Autolykos linha por linha.

Linha 1 – Entrada h e m

O PoW começa com as duas entradas: a altura do bloco h e o hash do cabeçalho do próximo bloco m. O hash do cabeçalho do bloco é um hash dos componentes do cabeçalho do bloco, como o hash do cabeçalho do bloco anterior, raiz merkle, nonce, etc.

Linha 2 – Calcular lista R

Primeiramente, é importante notar a notação H() na linha 2. Esta notação chama a função de hash Algoritmo 3. O Algoritmo 3 é uma função de hash baseada em Blake2b256 e é usada ao longo do Autolykos. O Algoritmo 3 afirma que se o hash Blake das entradas estiver abaixo de 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), então hash.mod(q) é retornado. Caso contrário, o Algoritmo 3 repete até alcançar um hash numérico dentro da faixa válida. Para referência, note que q é a ordem prima do grupo G, as saídas do hash Blake2b256 são de 256 bits, 64 dígitos de comprimento, e o Algoritmo 3 sempre retornará um hash numérico em Z/qZ.

Função de Hash Baseada em Blake2b256

Na linha 2, o foco é a criação da lista R. A lista R contém valores r que são hashes numéricos de 31 bytes criados a partir de inteiros em [0, N). Os valores r são gerados por takeright(31,H(j||h||M)). As variáveis são as seguintes:

• j, inteiro em [0, N)
• h, altura do bloco
• M, 8kb de dados constantes - preenchimento para desacelerar o cálculo do hash

A seção takeRight(31,H(…)) significa que dado H(…), uma saída de 32 bytes de Blake2b256, os 31 bytes à direita (ou seja, em little endian (enquanto outros algoritmos de hash são em big endian)) são retornados. Em outras palavras, o byte mais significativo, o byte mais à esquerda, é descartado. Como resultado, cada valor r é os 31 bytes menos significativos derivados da saída de 32 bytes H(j||h||M)). Por exemplo, se j = 1, r1 = takeRight(31,H(1||h||M)). A lista R consiste em N elementos e pode ser gerada para cada bloco incrementando j em 1 N-1 vezes. Como H(…) retorna hash.mod(q), podemos afirmar que a lista R consiste em r0, 1, 2, 3 … N-1 e lista R ⊂ Z/qZ. Como afirmado no whitepaper do Autolykos v2[3], “N elementos são derivados da altura do bloco e constantes, ao contrário do Autolykos v1, então os mineradores podem recalcular candidatos a blocos facilmente agora (apenas os índices dependem deles).” Em outras palavras, j está sempre em [0,N), N é determinado por h, M é sempre constante, e h muda a cada bloco, a única variável que um minerador precisa para calcular a lista R é h.

A lista R é armazenada na RAM. No Autolykos, N = 2²⁶ (67.108.864 inteiros) é usado na implementação para cada bloco antes de 614400. Assim, a exigência de memória para blocos antes do bloco 614400 é (226 * 31 bytes =) 2,08GB. N aumentou pela primeira vez no bloco 614400. Após o bloco 614400, a cada 51200 blocos, N aumenta em 5%. Em outras palavras, a exigência de memória de um minerador Ergo aumenta em 5% a cada ~71 dias. No bloco 4198400, o valor de N se torna constante e igual a 2.143.944.600[4]. Note que os últimos 2 valores listados na tabela devem ser 2.143.944.600 e não 2.147.387.550. Após o bloco 4198400, a exigência de armazenamento da lista R será (31 bytes * 2.143.944.600) = 66,46GB.

N elementos baseados na altura do bloco

N elementos, Ethash vs. Autolykos

Autolykos é como Ethash no sentido de que a altura do bloco determina os N elementos a serem armazenados na RAM. Com o Autolykos, a altura do bloco determina os N hashes numéricos de 31 bytes a serem armazenados. Com o Ethash, a altura do bloco determina os N páginas DAG de 128B a serem armazenadas. Você pode se perguntar, se um bloco Ergo ocorre a cada 2 minutos, como os mineradores Ergo conseguem gerar um conjunto de dados de 2GB+ tão rapidamente? Os mineradores Ethereum só regeneram o DAG a cada 100 horas porque leva tanto tempo... Para um minerador Ergo, o fardo de calcular a lista R é N instâncias do Algoritmo 3; lembre-se, cada valor r é calculado como takeRight(31,H(j||h||M)). No entanto, uma GPU pode fazer isso muito rapidamente, as GPUs geralmente têm multiprocessadores de 32 ou 64, o que significa que 32 ou 64 instâncias do Algoritmo 3 podem ser feitas simultaneamente, dependendo da GPU. Por exemplo, uma GPU de 32 vias como a RTX570 pode preencher a lista R em apenas alguns segundos.

Para a Parte II, continuaremos a partir daqui e continuaremos a explicação do Autolykos v2. Fique atento aos canais de mídia social do Ergo para atualizações sobre a Parte II desta série.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] Crédito a Wolf9466#9466 no Discord