Ergo e O Mecanismo de Consenso Autolykos: Parte II

Na semana passada, introduzimos uma exploração aprofundada do mecanismo de consenso Autolykos do Ergo. Com este artigo, completamos a segunda parte dessa discussão e mergulhamos em mais detalhes. Antes de ler este documento, é recomendável que os leitores dêem uma olhada na Parte I.

Como lembrete, aqui estão os pseudocódigos de mineração de bloco e função hash.

Pseudocódigo de Mineração de Bloco Autolykos

Função Hash Baseada em Blake2b256

Linhas 3, 4 – começa o loop while e a adivinhação

Após calcular list R, o minerador cria uma adivinhação de nonce e entra em um loop para testar se o nonce, em última análise, cria uma saída que está abaixo do valor alvo dado.

Linhas 5, 6 – semente para gerar índices

A linha 5, i = takeRight(8, H(m||nonce)) mod N, produz um inteiro em [0,N). O Algoritmo 3 é utilizado, mas com m e o nonce como entradas. Uma vez que o hash H(m||nonce) é retornado, os 8 bytes menos significativos são mantidos e, em seguida, passados por mod N. Como nota lateral, o maior valor inteiro possível com 8 bytes é 2⁶⁴ – 1, e assumindo N = 2²⁶, um hash de 8 bytes mod N resultará nos primeiros dígitos sendo zero. O número de zeros em i diminui à medida que N cresce.

A linha 6 produz e, uma semente para a geração de índices. O Algoritmo 3 é chamado com as entradas i (gerado na linha 5), h, e M. Então, o byte mais significativo do hash numérico é descartado, e os 31 bytes restantes são mantidos como valor e. Também deve ser notado que o valor e pode ser recuperado de list R em vez de ser computado, uma vez que e é um valor r.

Linha 7 – gerador de índices

O índice do elemento J é criado usando o Algoritmo 6 com as entradas e, m, e nonce. A função genIndexes é uma função pseudorrandômica que retorna uma lista de k (=32) números em [0,N).

função genIndexes

Existem alguns passos extras que não são mostrados no pseudocódigo, como uma troca de bytes. A criação e aplicação de genIndexes podem ser explicadas através do seguinte exemplo:

GenIndexes(e||m||nonce)...

hash = Blake2b256(e||m||nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (ou seja, troca de bytes e concatenação de 4 bytes repetindo os primeiros 4 bytes) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

O seguinte código python mostra o processo de fatiamento do hash estendido, retornando k índices. Neste exemplo, estamos assumindo h < 614,400, assim N = 2²⁶ (67,108,864).

Fatiamento e mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

A principal conclusão é que o fatiamento retorna k índices que são valores pseudorrandômicos derivados da semente, ou seja, e, m, e nonce.

return [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Este índice pode ser traduzido para valores em base 10, pois se refere a números em [0, N). Por exemplo, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314, e assim por diante. O minerador usa esses índices para recuperar k r valores.

A função genIndexes impede otimizações, pois é extremamente difícil, basicamente impossível, encontrar uma semente tal que genIndexes(seed) retorne os índices desejados.

Linha 8 – soma dos elementos r dados k

Usando o índice gerado na linha 7, o minerador recupera os correspondentes k (=32) r valores de list R e soma esses valores. Isso pode parecer confuso, mas vamos detalhar.

Continuando o exemplo acima, o minerador armazena os seguintes índices:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},
…
{31 | 8,830,952}

Dado os índices acima, o minerador recupera os seguintes valores r de list R armazenados na memória.

{0 | 46,131,392} → dropMsb(H(46,131,392||h||M))
{1 | 65,585,313} → dropMsb(H(65,585,313||h||M))
{2 | 12,624,314} → dropMsb(H(12,624,314||h||M))
{3 | 10,599,011} → dropMsb(H(10,599,011||h||M))
…
{31 | 8,830,952} → dropMsb(H(8,830,952||h||M))

Note que Takeright(31) operado em um hash de 32 bytes também pode ser escrito como dropMsb – descartar o byte mais significativo.

Como o minerador já armazena list R na RAM, o minerador não precisa computar k (= 32) funções Blake2b256 e, em vez disso, consulta os valores. Esta é uma característica chave da resistência a ASIC. Um ASIC com memória limitada precisa computar 32 iterações de Blake2b256 para obter os valores que poderiam ter sido consultados na memória, e buscar na memória leva muito menos tempo. Sem mencionar que um ASIC com memória limitada precisaria de 32 instâncias de Blake2b256 fisicamente no chip para alcançar um hash por ciclo, o que exigiria mais área e custos mais altos. É simples provar que armazenar list R na memória vale muito a pena. Suponha o seguinte, uma GPU tem uma taxa de hash de G = 100MH/s, _N = 2²⁶, k = 32, intervalo de bloco t = 120 segundos, e os elementos são consultados a cada 4 hashes. Gosto de assumir que os elementos são consultados a cada 4 hashes porque, para cada adivinhação de nonce, múltiplos elementos como i, J, e H(f) requerem o Algoritmo 3, ou seja, instâncias de hash blake2b. Podemos estimar que cada valor r será usado, em média, (G * k * t)/(N*4) = 1430.51 vezes.

Uma vez que os 32 r valores são consultados, eles são somados.

Linhas 9, 10, 11, 12 – verificar se o hash da soma está abaixo do alvo

A soma dos 32 r valores é hashada usando o Algoritmo 3, e se a saída estiver abaixo do alvo b, o PoW é bem-sucedido, m e nonce são retornados para os nós da rede, e o minerador é recompensado em ERG. Se o hash da soma estiver acima do alvo, Linhas 4 – 11 são repetidas com um novo nonce.

Se você chegou até aqui, parabéns! Após ler todas essas informações, você deve ter uma boa compreensão do Autolykos v2! Se você gostaria de ver uma demonstração visual do Autolykos, consulte o gráfico no final deste documento. Se você gostaria de uma explicação em vídeo, você pode encontrá-la aqui.

Resistência a ASIC

Sabemos pelo Ethereum que algoritmos 'hard memory' podem ser conquistados integrando memória em ASICs. O Ergo é diferente, mas vamos primeiro revisar por que um ASIC com memória limitada é não competitivo e por que um minerador precisa armazenar list R. A linha 8 da mineração de bloco Autolykos desencoraja máquinas com memória limitada. Se um minerador ASIC não armazenar list R, eles precisam de muitos núcleos para gerar os hashes numéricos de 31 bytes em tempo real. 32 r valores não podem ser calculados de forma eficiente usando um loop de núcleo único, pois uma saída só seria gerada a cada 32º ciclo de hash. Dado J, para computar um nonce por ciclo de hash, pelo menos 32 instâncias de Blake2b256 executando dropMsb(H(j||h||M)) são necessárias. Como mencionamos acima, isso aumenta significativamente o tamanho do chip e o custo. É claro que armazenar list R vale a pena, pois ter 32, ou mesmo 16, núcleos é muito caro. Mais importante ainda, ler da memória é mais rápido do que computar instâncias de Blake toda vez que um nonce é testado.

Vamos ver se um ASIC com memória suficiente é competitivo, pois isso é mais relevante para a discussão. Comparando Ethash e Autolykos, a diferença é que Ethash envolve N elementos ao hashar o nonce e o cabeçalho mistura 64 vezes, enquanto Autolykos envolve N elementos ao buscar 32 r valores com base nos índices gerados. Para cada nonce testado, Autolykos executa cerca de 4 instâncias de Blake2b256 e 32 buscas de memória, enquanto Ethash executa cerca de 65 instâncias semelhantes a SHA-3 e 64 buscas de memória. Sem mencionar que k está atualmente definido em 32, mas esse valor pode ser aumentado para recuperar mais r valores, se necessário. ASICs que executam Ethash têm muito espaço para aumentar a velocidade de hash SHA3, uma vez que 65 hashes são concluídos por nonce testado em comparação com cerca de 4 no Autolykos. A razão de buscas de memória para instâncias de hash é muito maior no Autolykos. Por essa razão, Autolykos é mais hard memory do que Ethash, uma vez que a largura de banda de memória desempenha um papel muito maior em comparação com a velocidade de hash.

Uma área onde a otimização do Autolykos poderia ocorrer é o preenchimento de list R. O preenchimento de list R requer N instâncias de uma função Blake2b256. N é grande e só está aumentando, então isso é muito hashing. Um ASIC poderia otimizar a velocidade de Blake2b256, proporcionando mais tempo para a mineração de blocos, uma vez que list R é preenchido mais cedo. Embora isso possa ser feito, preencher list R requer passar por [0, N) e uma GPU com multiprocessadores de 32 vias já pode preencher list R muito rapidamente (em segundos). Alguém precisaria de um ASIC com muitos núcleos Blake para ser significativamente mais rápido – novamente, muito caro, e provavelmente não vale a pena, uma vez que o gargalo poderia se tornar a largura de banda de escrita de memória (ou seja, escrever list R na RAM em vez da velocidade de hash).

A última área que pode ser otimizada para o Autolykos é a velocidade de leitura/escrita de memória. Mineradores ASIC Ethash têm uma velocidade de leitura ligeiramente mais rápida em comparação com GPUs, pois a memória é clockada mais alta sem o efeito de estrangulamento da GPU. No entanto, essa diferença é bastante insignificante e deve se tornar mais insignificante à medida que as GPUs avançam. Isso ocorre porque o hardware de memória em si é o mesmo: DRAM. Alguém pode questionar se um hardware de memória mais rápido poderia ser utilizado, onde a velocidade de leitura e escrita de memória é muito mais rápida… SRAM, por exemplo, poderia ser um próximo passo imaginável para quebrar algoritmos hard memory, no entanto, SRAM não é uma solução viável simplesmente porque é menos densa.

SRAM em FPGA[2]

A foto acima é de um FPGA com 8 chips de memória na frente, e há outros 8 na parte de trás. A memória total SRAM é apenas 576MB. Colocar SRAM suficiente em um chip não funcionará porque a SRAM precisará ser colocada mais longe do núcleo, pois não é densa o suficiente para caber em uma camada ao redor do núcleo. Isso pode resultar em atrasos de leitura/escrita porque a eletricidade precisa percorrer distâncias mais longas, mesmo que o hardware em si seja mais rápido. Além disso, para minerar Ergo, o requisito de memória aumenta à medida que N aumenta, então colocar SRAM suficiente não é viável ao longo do tempo. Assim, ASICs SRAM não valem a pena explorar, mesmo que alguém tivesse dinheiro suficiente para gastar na SRAM em si.

Blake2b256

Uma grande diferença entre um algoritmo como Autolykos e outros é o uso de Blake2b256. Isso não é uma coincidência. Blake depende fortemente de operações de adição para mistura de hash em vez de operações XOR. Uma operação como XOR pode ser feita bit a bit, enquanto a adição requer bits de transporte. Assim, Blake requer mais potência e área de núcleo em comparação com algoritmos SHA, mas ainda é tão seguro e, de fato, mais rápido. Como mencionado no site do Blake2, “BLAKE2 é rápido em software porque explora recursos de CPUs modernas, nomeadamente paralelismo em nível de instrução, extensões de conjunto de instruções SIMD e múltiplos núcleos.”[3] Assim, enquanto um ASIC pode produzir instâncias de Blake mais rapidamente, a natureza inata da função limita otimizações ao exigir adição e envolver recursos encontrados em CPUs, bem como em GPUs.

velocidade Blake2b em relação a outras funções hash

Conclusão

Autolykos é uma grande inovação que é uma resposta necessária para combater o aumento das máquinas ASIC otimizadas para PoW. Esperamos que esta série de 2 partes tenha ajudado você a entender o Autolykos em um nível mais técnico e por que ele é mais hard memory do que Ethash. À medida que o Ethereum faz a transição para uma rede PoS, haverá uma grande comunidade de mineradores em busca de um lugar para direcionar seu poder de hash, e o Ergo deve ser um jogador significativo na atração desses mineradores.

Se você gostou deste artigo, o autor convida você a conferir mais conteúdo através de sua conta no Twitter, @TheMiningApple.

[1] Crédito a Wolf9466#9466 no Discord
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).