Prova de importância

Prova de importância (do inglês, proof-of-importance ou POI), é um algoritmo usado para garantir consenso na block chain usada pela NEM, uma plataforma e criptomoeda criada em 2015. O modelo do algoritmo POI é baseado em teorias já consolidadas na computação sobre o grau de importância de nós em grafos. Portanto, a importância de um usuário, ou nó, na rede é calculada a partir de parâmetros considerados essenciais pela NEM, tais como: a quantidade de moedas que o usuário tem e a quantidade de transações feitas com sua carteira virtual. Considerando que a rede de transações é disponibilizada publicamente, é possível auditar essas transações e visualizar a topologia que a rede adquiri ao longo do tempo e essa é a proposta que a prova de importância traz para alcançar o consenso na block chain.

Histórico

A ideia de prova de importância foi publicamente apresentada e usada pela NEM em 2015 como um novo mecanismo de consenso para sua block chain. Suas características herdam naturalmente alguns conceitos de Prova de Participação (do inglês, Proof-of-Stake ou POS), no caso, POI, não apenas se beneficia do quanto um nó possui de saldo, mas também de outros atributos derivados das atividades transacionais de um nó na rede. Assim como a Prova de Participação (POS), a prova de importância, enfatiza também em sua base a preocupação em relação ao consumo de energia comparado ao POW. Por outro lado, POI, ataca o problema monopolização de mineração que POS enfrenta, popularmente parafraseado como "rich gets richer", ou seja, quanto mais saldo tem um usuário em um sistema POS, consequentemente mais participação e mais rico ele se torna na rede. Há questionamentos sobre a eficiência do POI comparada ao POS, apesar disso o crescimento da moeda XEM (nome atribuído a moeda da rede NEM) já figura entre as 5 primeiras posições na capitalização de mercado entre as criptomoedas.

Sistema de reputação de nós

O sistema de reputação é um módulo a parte em relação à POI, ou seja, enquanto a prova de importância trabalha em nível de conta virtual e suas transações com outros nós, ou seja um algoritmo voltado para a blockchain, o sistema de reputação opera sobre a rede peer-to-peer (P2P) dos nós. Isso é dado pela necessidade de identificar nós mal intencionados que propositalmente injetam falsas informações na rede.

A ideia básica da rede usada pela NEM é de que cada nó pode interagir com outro nós através da transmissão de informações de transações e blocos de transações. Portanto, cada nó pode tanto informar à rede sobre novas entidades quanto perguntar a outros nós sobre essas entidades. Com isso, o nó pode registrar se a verificação da informação recebida foi um sucesso (uma nova informação válida foi recebida), neutro (a informação é válida, porém já recebida) ou falha (informação inválida recebida). Cada nó tem um conjunto inicial de nós chamados pré-validados e cada nó também persiste todas suas interações com outros nós. Com esses dados, é possível aplicar os cálculos de reputação de um nó na rede. O sistema pontua de acordo com a vizinhança local dos nós, logo, essas pontuações não tem influência global.

Essa abordagem usada pela NEM é baseada no sistema de reputação chamado EigenTrust++, voltada para redes P2P e adaptada para a rede NEM e seu objetivo é oferecer suporte para que a rede não seja infectada por nós maliciosos.

Funcionamento

A prova de importância leva em consideração várias abordagens que auxiliam e promovem a elegibilidade de um nó e sua relevância na rede. O uso de teorias dos grafos consolidadas em áreas de pesquisa como redes sociais, neurociência, redes viárias, etc, formam a base de inovação proposta pela NEM para o consenso da block chain. O conjunto dessas técnicas atacam alguns problemas enfrentados por Prova de Trabalho e Prova de Participação, como Sybil attacks, Loop Attack, consumo de recursos energéticos e computacionais, o problema de monopólio, entre outros.

Elegibilidade da importância de um nó

Segundo a referência técnica do projeto NEM, para um nó ser elegível e estar apto a entrar no cálculo de importância é preciso atingir um mínimo de moedas XEM adquiridas (atrelado ao conceito de vesting, ou direito de aquisição), este montante foi inicialmente foi definido em 10.000 XEM, e esse limite mínimo pode ser alterado a medida que a rede cresce. A rede NEM dispõe de 8.999.999.999 XEM no total. Portanto o número máximo de usuários com alguma reputação associada é de 899,99. Apesar do número ser relativamente baixo, na prática, não é esperado que seja alcançado o número máximo por causa das variações de saldo e também pelo custo temporal do vesting.

O conceito de Vesting

No contexto de direito e negócios, vesting é um consenso contratual em que é oferecida a opção de obter direito a uma ação (ou ativos, propriedades, etc) sob determinadas condições ao longo do tempo. Essa prática oferece garantias importantes, principalmente para startups, ao vender as ações de sua empresa, que incentiva, e determina, a participação ativa do acionista sob condições descritas no contrato.

Baseado nisso, o NEM se beneficia desse conceito para construir uma confiança sobre o usuário e evitar Sybil attacks no momento que ele entra na rede e deposita XEM em sua carteira virtual pela primeira vez. Inicialmente nenhuma porcentagem do valor é considerado vested (vamos considerar, adquiridos). Após 24h, 10% do saldo é concedido ao usuário. Novamente, depois de 24h mais 10% são concedidos. Após alcançar um número suficiente de moedas adquiridas é que será possível iniciar a mineração, ou como eles denominam, colheita.

Cálculo da matriz de transações

Suponha que o cálculo de prova de importância é feito a uma altura h. Todas as contas que tiverem um saldo disponível de pelo menos 10.000 a uma altura h estão aptos a participar no cálculo de POI. Para cada conta, é coletado todas as operações de transefências efetuadas seguindo as seguintes condições

• A transferência é de um valor de pelo menos 1.000 XEM
• A transferência aconteceu nós últimos 43.200 blocos (aproximadamente 30 dias)
• O beneficiado é também elegível para o cálculo de POI

Para cada uma dessas transações T_k que transferiu uma quantia de 1.000 XEM de uma conta A_i para uma conta A_j e foi realizada a uma altura h_ijk, o peso então é calculado de acordo com a fórmula:

$w_{i,j,k}=quantia\cdot exp\left(ln(0.9)\left\lbrack {\frac {(h-h_{i,j,k})}{1440}}\right\rbrack \right)$

onde [x] é uma função piso. Naturalmente, a transação de uma quantia de 10 mil XEM é ponderada ao longo do tempo.

Esse comportamento é associado a:

${\tilde {w}}_{ij}=\sum _{k}w_{ijk}$

Aplicando:

${\tilde {o}}_{ij}={\begin{Bmatrix}{\tilde {w}}_{ji}-{\tilde {w}}_{ij}\quad se\quad {\tilde {w}}_{ji}-{\tilde {w}}_{ij}>0\\0\quad caso\ contrario\end{Bmatrix}}$

então, temos que a matriz de transações O é constituída de elementos o_ij, tal que:

$o_{ij}={\begin{Bmatrix}{\frac {{\tilde {o}}_{ij}}{\sum _{i}{\tilde {o}}_{ij}}}\quad se\quad \sum _{i}{\tilde {o}}_{ij}>0\\0\quad caso\ contrario\end{Bmatrix}}$

Logo, o elemento da matriz de transações o_ij descreve o fluxo de uma rede ponderada da moeda XEM de uma conta A_i para A_j durante os últimos 30 dias aproximadamente. Isso significa que apenas transferências entre redes contribuem para a importância de uma conta.

NCDawareRank

Para determinar a relevância de um nó na rede, o NEM, usa uma abordagem similar ao PageRank, o NCDawareRank, que calcula a distribuição de probabilidade estacionária de uma cadeia de Markov ergódica.  O objetivo da aplicação do NCDawareRank é convergir mais rápido comparado ao PageRank ao mesmo tempo que evita manipulação de pontuação de reputação, isso se dá porque o ranqueamento de nós de um mesmo nível são limitados a partir de uma matriz de proximidade.

Clusterização do grafo de transações

Para a clusterização do grafo, a Prova de Importância usa o algoritmo de clusterização chamado SCAN. Esse algoritmo clusteriza vértices baseado na similaridade entre grupos de nós que estão a dois níveis de distância, tais clusters são criados visitando cada nó relevante apenas uma vez e depois expandindo esses clusters. Depois de todo o processo de clusterização concluído, os clusters computados são usados para determinar os níveis da matriz de proximidade do NCDawareRank. Segundo o NEM, esses clusters são a representação praticamente decomposta do grafo de transações.

Cálculo de importância dos nós

Após todas as etapas feitas com o grafo de transições é possível, finalmente, calcular a pontuação de importância de um nó. O cálculo de importância é dado da seguinte forma:

$\psi =(normaliza_{1}(max(0,v+\sigma w_{o}))+{\tilde {\pi }}w_{i})_{X}$

onde,

$normaliza_{1}(v)$ é ${\frac {v}{\left\Vert v\right\Vert }}$

${\textstyle v}$ é a quantidade de XEM adquirida

$\sigma$ é a rede ponderada de transações XEM

${\tilde {\pi }}$ é a pontuação NCDawareRank

$X$ é o vetor de ponderação que considera a topologia estrutural do grafo

$w_{o},w_{i}$ são constantes

$X$ considera a topologia da rede e atribui um peso de altura maior para os nós que fazem parte de clusters, ao invés de outliers ou hubs.

Esses outliers e hubs são ponderados em 0,9 de sua pontuação, enquanto nós que estão em um cluster são ponderados em 1.0. NEM atribui a $w_{o},w_{i}$ os valores 1,25 e 0.1337.

Após o cálculo, as informações sobre quantia adquirida, XEM transferidos, e a topologia do grafo formam a heurística de avaliação de importância de usuários na rede NEM. Essas abordagens em conjunto reforçam o combate na tentativa de manipulação de importância na rede.

O problema de manipulação de reputação

Na rede NEM, há um incentivo em XEM para que usuários pratiquem a colheita (mineração) de blocos, e usuário com pontuação de importância alta tem mais chances de minerar um bloco. A prova de importância considerou o problema de ataques Sybil em sua construção desde o início. O uso de NCDawareRank, quantia adquirida do saldo, e pesos atribuídos na rede de transações ao longo do tempo, desempenham um papel importante para o combate de ataques Sybil.

Esses ataques incluem:

• divisão de contas e transações entre essas contas para aumentar a pontuação NCDawareRank;

• divisão de contas e transações entre contas aleatórias;

• envio de XEM entre contas em um loop para aumentar a pontuações em relação a transações.

Os componentes da prova de importância que combatem estão listados a seguir de forma resumida:

• a matriz de nível de proximidade do NCDawareRank torna o algoritmo resistente a spamming. No caso o cenário seria em que uma conta envia valores para outra e depois retornam para a conta principal;
• o Vesting faz com que o processo de direito de aquisição seja lento, ou seja, leva um tempo para que uma conta seja elegível e consiga iniciar os ataques a rede;
• a matriz da rede de transações apenas considera operações de saída. Portanto não há vantagem em operar transferências de uma conta para outra e retornar, pois as operações de entrada e saída de valores se excluem no cálculo;
• há uma ponderação ao longo do tempo sobre a matriz de transferência, portanto, após um período a pontuação de importância cai;
• o requisito mínimo para elegibilidade de 10.000 XEM oferece uma barreira considerável para possíveis ataques Sybil.

Esses e esses outros motivos que compõem um conjunto de algoritmos e teorias, dão base para que a Prova de Importância seja efetiva no combate a injeção de movimentações maliciosas na rede.