Topic: O Bitcoin e o Problema da Mochila (Read 320 times)

Devidamente meritado 

Já tinha lido superficialmente sobre isto, mas a preguiça mental está em estado agudo aqui ultimamente.

Bom texto.

Acrescentando um pouco de informçao, pode ser que seja útil.
Fiz uma disciplina no curso de ADM chamada "métodos quantitativos para tomada de decisão" que consistia, basicamente, em criar modelos matemáticos para encontrar soluções ótimas para funções baseadas em casos concretos.
Acho que se encaixa no assunto das mochilas. Os exemplos eram basicamente "eu só posso levar 10 caixas de laranja e 5 de maçã, porém a maçã custa X e a laranja custa Y, e eu só posso levar no máximo X caixas de  laranjas e Y caixas de maçã. Qual seria a solução ótima para tornar o frete mais lucrativo?" (mais ou menos isso. Tentei pegar na net um exercicio mas o passei direto agora exige baixar app ¬¬)

Só agora parei para ler o texto. Achei sensacional o assunto abordado. Nunca havia ouvido falar desse problema.

Enquanto a galera está discutindo o real problema, eu estou tentando encaixar os blocos da imagem na mochila. lol Parabéns pelo post, bem interessante.

PS: Gostei da solução do ETH. kkkkkkk

Tópico muito bom, parabéns por trazer isso pra comunidade.

Já havia pesquisado sobre isso antes, mas sempre fiquei naquele exemplo do caixeiro-viajante e nunca me toquei sobre a assoaciação com a parte de mineração.

Que texto bacana....

Eu também nunca havia pensado nesse problema (e olha que sou programador), sempre achei que a melhor escolha era pegar os "objetos" com a melhor relação Peso/R$.

Post muito didático, completo e simples.
Merece mais um Merit

Gostei da explicação e gostei da maneira simples de explicar. Vai ganhar uma "meritada" por isso.

Post bem completo. Não conhecia esse problema da mochila e gosto muito dessa forma de explanação que compara os objetos do mundo virtual com itens do mundo real. Facilita bastante o aprendizado de quem é leigo e quer se iniciar conhecendo um pouco mais. Parabéns!

Então, por isso que essa escolha em si não importa muito, porque o principal são os 12.5 BTC e as vezes até vemos blocos que os caras "encheram mal" ou simplesmente montar o bloco à maneira deles por causa da competividade entre os mineradores (~10 min pra achar).

Agora no futuro, teríamos que ver o quão usado vai ser essas soluções e principalmente o valor de mercado do bitcoin. Pensa que se todo mundo usar a LN, as transações na mainchain serão baratíssimos, equilibrando a balança sempre (na verdade a mainchain ia manter o mesmo numero de transações e a LN só aumentar), e sempre tendo um monte de transações como temos agora só que composta apenas dinheiro de pessoas que aceitaram a possível demora na confirmação e sem o desespero atual, mas resumindo, se o preço do bitcoin aumentar o suficiente, os mineradores com certeza buscarão formas de otimizar o modo como selecionam as transações para "encher a mochila direito".

Cara, será que dá tanta diferença assim se eles já pegam as transações por sat/byte? Difícil ter uma transação muito gigante (que ocupe 1/1000 do bloco) que talvez faça valer a pena o esforço.. Também tem a questão de que o minerador pode achar um bloco muito cedo, não enchendo a mochila..

E pro futuro, há as soluções de side-chain, LN, etc.. então esse problema seria esquecido..

Sim, eles sempre escolhem os com maior sat/byte, coloquei no exemplo pra ficar mais fácil de visualizar

UPD: acrescentei acima sobre os serviços de aceleração de transação e a comparação do O(nW) com o O(nlogn) do algoritmo guloso atual.

Existe um dilema parecido quando se trata de blocos e transações chamado maximum independent set problem, está no link acima, mas eu acho que escreverei mais tarde sobre.

valeu pelo texto, com certeza lerei os anexos, nunca tinha ouvido falar e gostei de pensar nesse dilema

Solução do Bitcoin Cash: Compre uma mochila maior.

Solução do XRB: Todo mundo é uma mochila e ninguém recebe por isso.

Solução do Ethereum: Compre uma mochila menor e faça mais viagens, além disso, roube as taxas mesmo sem levar o tijolo caso as mesmas sejam muito baixas.

Vitalik rei.


Interessante esse problema, nunca havia pensado nisso.. Naqueles tempos que uma transação custa 50 reais, deve dar uma boa diferença..


edit: pensando aqui, a configuração que o minero tem é qual? valores das taxas em BTC? O que ele define é uma taxa mínima e só? Não é só introduzir uma medida de sat/byte e ta resolvido o problema?


Ao invés de decidir qual transação pegar por "X sat de fee", escolher as transações por "xsat/kbyte".. não deve ser difícil fazer essa mudança..


edit2:

4$ - 12kg = 0,33$ por kg
2$ - 2kg = 1$ por kg
2$ - 1kg = 2$ por kg
10$ - 4kg = 2,5$ por kg
1$ - 1kg = 1$ por kg

Usar essa terceira medida, $ por kg.. não é a ideal, porém já melhora.. (embora nesse caso da elas por elas)

É disso que eu tô falando! Qualidade nos post! Boa garoto!.


Esse problema só se pode usar computação e algoritmos para resolver?

Olha só que coisa mais interessante.
Será que nos próximos Halvings teremos mineradores interessados na solução desse problema?

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".








     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_mochila
https://en.wikipedia.org/wiki/Knapsack_problem
https://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/