Segundo a Wikipedia: "
O problema da mochila (em inglês, Knapsack problem) é um problema de otimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo."
E o legal deste problema é que faz parte de um dos 21 problemas NP-completos que se você conseguir criar um algoritmo que consiga resolve-los rapidamente (os algoritmos atuais são extremamente lentos), você pode clamar por um premio de 1 milhão de dólares proposto por uma universidade, além de criar uma nova era para matemática e da computação, e consequentemente ferrando uma boa parte dos algoritmos criptográficos que temos hoje em dia...
Certo, e o que isso tem a ver com o Bitcoin ? Bem, pra fazer essa ligação é preciso antes lembrar de algumas coisas:
1) Os blocos de mineração só comportam 1MB de informação (ou 4 milhões de weight units, mas isso não tem relevância agora).
2) Os mineradores podem escolher as transações que irão colocar no bloco, e irão ganhar as taxas de transação delas.
Ou seja, os mineradores escolhem quais transações colocar no bloco, dependendo de seu tamanho e suas taxas.
Ok, e o que tem de mais nisso ? Bom, antes de explicar como é resolvido o problema do knapsak, é preciso entender a verdadeira dificuldade de resolver ela.
Então já colocando ela no contexto do Bitcoin, olhe este exemplo:
Digamos que o minerador tenha apenas essas 4 transações na sua mempool:
1) 300 kbytes com 300 sat de fee (1sat/kbyte)
2) 500 kbytes com 600 sat de fee (1.2sat/kbyte)
3) 600 kbytes com 800 sat de fee (1.33sat/kbyte)
4) 200 kbytes com 400 sat de fee (2sat/kbyte)
A solução trivial seria simplesmente pegar as transações com o maior sat/byte e escolher elas até que o bloco fique cheio, mas nesse caso vemos que seria as opções 4 e 3 (400+800 =1200 sat), enquanto que a solução ótima seria escolher as opções 1, 2 e 4 (300+600+400 =1300 sat), ou seja, a coisa não é tão simples quanto parece.
Se o problema é tão difícil de resolver, como os mineradores o fazem ? A solução atual que temos para este problema faria impossível de o minerador montar o bloco dele e achar o hash do PoW em um tempo bom o suficiente para competir com os outro, então o que o minerador faz é simplesmente ignorar ele e fazer a escolha gulosa: pegar as transações com o maior sat/byte e ignorar uma possível escolha melhor.
Mas por que ? Eles não querem saber de mais dinheiro ? Sim, por isso mesmo, tempo=dinheiro, levando em conta que o bloco dá 12.5 BTC de "prêmio" e que as taxas de transação nao passam de uns 5 BTC, e que calcular a escolha ótima simplesmente demora e o ganho extra seria bem pequeno (sei lá, estimo que 1 BTC no máximo ?), simplesmente vale a pena só caçar o hash com os zeros e incluir as transações no bloco só quando conseguem.
UPD: um ótimo exemplo de que os mineradores não estão muito aí para as taxas são os aceleradores de transação, que colocam a sua transação no bloco mesmo não tendo a melhor taxa (marketing).
Conclusão No futuro, quando a geração de bitcoins realmente se tornar escassa, aí sim teríamos que pensar em como resolver melhor este problema, mas por enquanto isso é algo menos preocupante que a computação quântica.
E mais, não resolver este problema ainda é uma ótima ideia para o bitcoin, já que isso incentiva aos usuários a escolher taxas sempre maiores, estimulando a competitividade e fazendo com que aquelas transações com 0.1sat/byte simplesmente não seja confirmada por "sorte".
parte um pouquinho mais técnica para os curiosos:
O cálculo do knapsack 0-1 descrito tem uma complexidade de O(nW), onde n é o número de objetos (transações), e W é o tamanho da mochila (1.000.000 bytes), e uma média boa de transações não confirmadas é de 5000. Ou seja, o algoritmo teria que fazer 5000*10^9 operações, e supondo que um computador faça ~10^9 cálculos por segundo, temos 5000 segundos > 1 hora só para calcular a montagem do bloco (o cara ainda tem que calcular os hashs depois).
Já o cálculo do algoritmo guloso tem uma complexidade de O(nlogn), que dá 5000*10 = 5*10^4 operações, que acarreta em um tempo < 1 segundo de cálculo.
É claro que existem otimizações nisso, se alguém quiser discutir sobre elas sinta se a vontade.
Fontes:
https://pt.wikipedia.org/wiki/Problema_da_mochilahttps://en.wikipedia.org/wiki/Knapsack_problemhttps://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/
