Scrypt

Scrypt é uma função hash criptográfica que foi originalmente projetada para uso como uma função de derivação de chaves a partir de senhas no Tarsnap. Ela foi formalizada em um artigo científico e apresentada por Colin Percival em maio de 2009 na conferência BSDCan'09 e teve sua primeira implementação lançada no dia 08 do mesmo mês. Um paper posterior sobre scrypt foi publicado no Internet Engineering Task Force (IETF) como um Request For Comments (RFC) de número 7914 em Agosto de 2016.

O desenvolvimento da função scrypt ocorre de maneira open-source no seu repositório do git, e tem implementações nas linguagens C, Go, Python, Haskell, Node e Ruby.

Ela é uma função que por design exige um uso de memória mais alto na sua computação em comparação a outras funções de derivação de chaves, como PBKDF2 e bcrypt . Ela foi projetada dessa forma para dificultar ataques de força bruta, onde um atacante conhece um valor hash H e deseja saber qual chave o gerou, para isso ele itera sobre uma possível lista de chaves e aplica a função hash sobre cada uma delas até que a saída da função seja igual a H.

Algoritmo

Entradas:

• P: Palavra chave que será digerida pela função, uma sequência de bytes.
• S: Sal, uma sequência de bytes que têm como defender contra ataques de dicionário e contra ataques pré-computados como rainbow table.
• N: Custo CPU/memória.
• p: Parâmetro de paralelização, um inteiro positivo que satisfaz p ≤ (2³²− 1) * 32/ SMixLen.
• dkLen: Tamanho da saída desejada em bytes, um inteiro positivo que satisfaz dkLen ≤ (2³²− 1) * 32.

Saídas:

• DK: Chave derivada, com dkLen bytes

Function scrypt(P,S,N,p,dkLen):
    (B0 ... Bp−1) ← PBKDF2(HMAC_SHA256, P, S, 1, p * SMixLen)
    for i = 0 to p-1 do
        Bi ← SMix(Bi,N)
    end for
    DK← PBKDF2(HMAC_SHA256, P, B0 || B1 ... Bp−1, 1, dkLen)

Integerify() é uma função bijetiva de {0, 1}^k para {0,...,2^k− 1}.

Function SMix(B,N):
    X ← B
    for i = 0 to N − 1 do
       Vi ← X
       X ← BlockMix(X)
    end for
    for i = 0 to N − 1 do
        j ← Integerify(X) mod N
        X ← BlockMix(X ⊕ Vj)
    end for
    Output ← X

Function BlockMix(B):
    (B0, ... , B2r-1) ← B
    X ← B2r−1
    for i = 0 to 2r − 1 do
        X ← H(X ⊕ Bi)
        Yi ← X
    end for
    Output ← (Y0, Y2, ... , Y2r−2, Y1, Y3, ... , Y2r−1)

Versões

Todas as versões oficiais do projeto scrypt estão disponíveis para download no seu repositório do Github e no Tarsnap.

Versão	Data de Lançamento
scrypt 1.2.1	11/02/2017
scrypt 1.2.0	30/07/2015
scrypt 1.1.6	16/01/2010
scrypt 1.1.5	06/11/2009
scrypt 1.1.4	15/06/2009
scrypt 1.1.3	25/05/2009
scrypt 1.1.2	20/05/2009
scrypt 1.1.1	16/05/2009
scrypt 1.1	16/05/2009
scrypt 1.0	08/05/2008

Uso como prova de trabalho

A sua natureza de ser propositalmente custosa de ser computada várias vezes e fácil de ser computada apenas uma vez torna scrypt um bom candidato para uso na construção de uma prova de trabalho. Prova de trabalho é um pedaço de data que é difícil de ser produzida, mas é fácil de ser verificada e foi inicialmente criada para evitar spam de emails e ataques de negação de serviço. Por exemplo, antes que um remetente possa enviar um e-mail, é preciso que sua máquina realize uma computação que é pouco demorada se o usuário deseja enviar o e-mail para apenas um destinatário e muito demorada caso o remetente deseje enviar e-mail para vários destinatários. Essa técnica atribui um custo ao envio de e-mail para vários destinatários, efetivamente diminuindo o modelo do spam, que depende de enviar uma grande quantidade de emails de uma maneira barata.

O sistema Hashcash implementa essa prova de trabalho só permitindo que o destinatário receba o e-mail após verificar uma estampa válida do cabeçalho do email. No entanto, a única forma do remetente encontrar uma estampa válida é aplicar uma função hash sobre valores aleatórios até que o valor hash tenha uma certa quantidade de zeros.

Com o advento do Bitcoin o sistema Hashcash começou a ser utilizado em criptomoedas de modo a determinar qual dos nós mineradores pode sugerir o próximo bloco a ser adicionado a blockchain e consequentemente ser recompensado. No Bitcoin o sistema Hashcash é usado de uma análoga a forma que é utilizado em um sistema de emails. Um nó que esteja minerando precisa calcular um valor tal que ao ser processado por uma função de hash SHA-256 junto com o bloco que ele deseja sugerir tenha uma certa quantidade de zeros que todos da rede sabem. Um nó que achar tal valor, pode então transmitir para o resto da rede Bitcoin o bloco que encontrou e qualquer outro nó da rede pode verificar se o novo bloco é válido, aplicando a função hash SHA-256 sobre o bloco recebido e vendo se o resultado tem o número de zeros necessário.

Por ser uma função hash criptográfica, o scrypt pode ser usado como uma alternativa ao SHA-256 no processo de mineração de criptomoedas, e é de primeira vista interessante pelo seu custo elevado não só de cpu mas também de memória.

Criptomoedas que utilizam scrypt

O fato do scrypt, quando utilizado como prova de trabalho, aparentemente ser resistente à mineração utilizando placas de vídeo e circuitos de integrados de aplicação específica (ASICs) causada por um grande custo de memória na hora de sua computação, atraiu muitos desenvolvedores de novas criptomoedas. A partir do fim dos anos 2011, foram criadas várias criptomoedas utilizando scrypt, que buscavam fugir do algoritmo de hash SHA-256 utilizado pelo Bitcoin, que desde o final de 2010 já tinha seu processo de mineração dominado por placas de videos.

Tenebrix

Foi a primeira criptomoeda criada a implementar um esquema de prova de trabalho baseado em scrypt. Foi proposta em 26 de setembro de 2011 no fórum bitcointalk pelos membros “Lolcust” e “ArtForz”. Outro fato notável sobre essa criptomoeda é que ela foi lançada com cerca de 7 milhões de moedas pré mineradas.

Fairbrix

Foi proposta por Charlie Lee utilizando o apelido de “coblee” no fórum bitcointalk em 2 de outubro de 2011. Fairbrix foi um fork do Tenebrix, logo utilizava scrypt, e tinha como maior diferença um número mais reduzido de blocos pré-minerados.

Litecoin

Lançada em 9 de outubro de 2011 no fórum bitcointalk também por Charlie Lee. Litecoin teve a proposta de tentar melhorar o Bitcoin, reduzindo o tempo de chegada de blocos para dois minutos e meio, quadruplicando o número de moedas que podem ser criadas e utilizando um algoritmo diferente do SHA-256, utilizado pelo Bitcoin. Litecoin teve um grande sucesso no mercado de criptomoedas e chegou a ficar em segundo lugar no ranking de capitalização de mercado, ao lado do Bitcoin nos meados de 2014. Em Agosto de 2017, Litecoin continua sendo desenvolvida como código aberto e ocupa quinta posição no ranking de capitalização de mercado com aproximadamente 2 bilhões e 500 milhões de dólares. Litecoin utiliza uma versão simplificada da função scrypt sem a feature de alongamento de chave, a mineração utiliza os parâmetros de 1 iteração e 128Kb de uso de memória. O motivo da escolha desses parâmetros é que os desenvolvedores do Litecoin consideraram que o custo da verificação seria muito elevado, apesar de que parâmetros maiores iriam dificultar a produção de circuitos de integrados de aplicação específica (ASIC) para a mineração.

Dogecoin

É uma das muitas criptomoedas que foram lançadas após o sucesso da Litecoin, utilizando scrypt com os mesmos parâmetros estabelecidos pela Litecoin. Foi anunciada no fórum bitcointalk em 8 de dezembro de 2013 e se destaca por utilizar o meme da internet "Doge" como seu logo.

Gridcoin

Ao ser criada em Outubro de 2013, Gridcoin utilizava um sistema de prova de trabalho utilizando o scrypt para manter a rede segura , atualmente essa versão que utilizava prova de trabalho é chamada de Gridcoin-Classic. Gridcoin visa recompensar mineradores que estão trabalhando na manutenção da rede e são voluntários do projeto BOINC, um projeto da Universidade de Berkeley que fornece uma plataforma para que voluntários possam fornecer o tempo ocioso de processamento para colaborar com pesquisas no ramos de medicina, biologia, matemática, climatologia e astrofísica. O maior benefício que Gridcoin queria oferecer era direcionar o poder computacional dos mineradores para projetos BOINC enquanto que operações de mineração ficariam em segundo plano.

Entre 12 de Outubro de 2014 e 26 de Abril do ano seguinte o sistema de prova de trabalho com scrypt utilizado pelo Gridcoin-Classic foi substituído totalmente, por causa do custo ainda elevado de energia, para um sistema de prova de pesquisa chamado de Gridcoin-Research. O processo de migração que durou 6 meses, consistiu na queima de moedas que foram transferidas para um endereço sem dono. Por fim, Gridcoin-Research se tornou Gridcoin e a blockchain do Gridcoin-Classic foi aposentada.

Variações do scrypt

A mineração da Litecoin que utilizava a versão original do scrypt, durou pouco tempo sendo feito através de gpu e cpu. Circuitos de integrados de aplicação específica (ASICs) para os parâmetros utilizados pelo Litecoin, e pelas outras inúmeras criptomoedas que a copiaram, começaram a ser produzidos a partir do fim de 2013 . Esse evento pode ser explicado devido aos baixo valor do parâmetro N (que determina o uso de memória) utilizado pelas altcoins baseadas em Litecoin. Qualquer mudança no algoritmo de forma a dificultar uso de ASICs após sua produção em massa é difícil, pois para que o algoritmo seja mudado é preciso que a maioria do poder computacional da rede vote para tal, e a maioria do poder computacional estaria na mão dos mineradores que utilizam ASICs.

Graças a sua popularidade em uso como prova de trabalho, foram criadas outras variações do scrypt que procuraram tornar criptomoedas que o utilizavam resistentes à mineração utilizando circuitos de integrados de aplicação específica (ASICs).

Scrypt-N

Scrypt-N ou Scrypt Adaptive-N é um algoritmo, usado primeiramente pela Vertcoin, aonde diferentemente do scrypt utilizado pelo Litecoin que têm parâmetro N fixo utiliza o parâmetro de requisito de memória variável e incremental com o tempo. A motivação inicial para uso de um N incremental era que o aumento da memória necessária para a computação da função iria dificultar a produção de ASICs, o que acabou não sendo verdade novamente com o possível desenvolvimento de ASICs para Scrypt-N e a eventual troca de função hash na Vertcoin.

Ver também

• ASIC
• Ataque de força bruta
• Alongamento de chave
• Altcoins
• Criptomoeda
• Função hash criptográfica
• Litecoin
• Prova de trabalho

Ligações externas

• Repositório do scrypt no Github