Submitted by Irene Nascimento (irene.kessia@ufpe.br) on 2016-06-22T17:04:20Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Utilizando o Protocolo Bitcoin para Condução de Computações Multilaterais Seguras e Justas.pdf: 1665447 bytes, checksum: 2ff437be55e080c80d97e0d6582cb360 (MD5) / Made available in DSpace on 2016-06-22T17:04:20Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Utilizando o Protocolo Bitcoin para Condução de Computações Multilaterais Seguras e Justas.pdf: 1665447 bytes, checksum: 2ff437be55e080c80d97e0d6582cb360 (MD5) Previous issue date: 2016-02-02 / Suponha que dois milionários desejam descobrir quem é o mais rico sem que, para isso, um descubra o valor da fortuna do outro. Esse problema pode ser facilmente resolvido se ambos concordarem sobre um juiz a quem eles possam confiar a tarefa de calcular a resposta sem quebrar a privacidade de nenhum dos dois. O desafio, no entanto, é substituir esse juiz por uma interação multilateral, ou protocolo, que alcance o mesmo grau de segurança. Isso significa conduzir uma computação multilateral segura. Esse exemplo é conhecido como o problema dos milionários de Yao e foi proposto por Andrew Yao em um dos primeiros esforços para desenvolver uma forma geral de se conduzir computações multilaterais seguras. Desde lá, na década de 1980, vários avanços foram feitos nesse sentido e, hoje, já é um resultado bem estabelecido que qualquer função multilateral pode ser computada de maneira segura. Esse importante resultado, no entanto, vem com uma importante ressalva: a justiça não pode ser alcançada de maneira geral. Entende-se por justiça a garantia de que, no final de uma computação, ou todos os participantes recebem suas respostas ou nenhum deles recebe. Motivadas por esse resultado de impossibilidade, várias definições alternativas de justiça foram concebidas. Uma delas considera uma computação como sendo justa se os participantes que agirem desonestamente forem monetariamente penalizados. Ou seja, se alguns participantes receberem o resultado da computação e privarem os demais de receberem, então esse conluio é penalizado e os demais participantes, compensados. Com essa definição, uma computação justa pode ser vista como o cumprimento de um contrato, no qual cada participante se compromete a agir honestamente ou a pagar uma multa. Sob essa perspectiva, trabalhos recentes mostram como criptomoedas podem ser utilizadas para escrever esses contratos e, portanto, servir para condução de computações multilaterais seguras e monetariamente justas. Uma criptomoeda é um sistema monetário que se baseia em princípios criptográficos para alcançar segurança e controlar a taxa de emissão de novas moedas. O Bitcoin, criado em 2008 por Satoshi Nakamoto, foi a primeira realização dessa ideia. Ele se baseia em uma estrutura de dados pública chamada blockchain, que armazena o histórico de todas as transações já realizadas. A segurança da blockchain, incluindo sua não-maleabilidade, é garantida pela dificuldade da prova de trabalho exigida para que novas informações sejam adicionadas nessa estrutura. Cada transferência de moedas no Bitcoin é feita de maneira que um usuário só pode recebê-las mediante a apresentação de uma entrada que satisfaça um script especificado pelo remetente. Contratos escritos através desses scripts se fazem cumprir sem a necessidade de intervenção de uma parte confiável externa. Essa característica é o que faz o Bitcoin ser adequado e atrativo para se conferir justiça para computações multilaterais seguras. Um dos nossos objetivos neste trabalho é a realização de um estudo sobre os resultados que permitem a computação segura de uma função qualquer e dos que estabelecem a impossibilidade de se alcançar justiça de maneira geral. Tentaremos manter o rigor matemático para evitar uma apresentação estritamente panorâmica. Além disso, analisaremos criticamente uma construção proposta para utilizar o Bitcoin como plataforma para condução de computações multilaterais seguras e justas. Por fim, a partir dos pontos positivos e negativos levantados, apresentaremos uma proposta nossa com a mesma finalidade. / Suppose that two millionaires want to find out which one is the richest, but without revealing how much their fortunes are worth in the process. This problem can be easily solved if they trust a judge to compute the desired answer without compromising their privacy. The challenge, however, is to replace such a judge by a multiparty interaction, or protocol, that achieves the same level of security. That is, the challenge is to carry out a secure multiparty computation. The previous example is known as Yao’s millionaires’ problem and was stated by Andrew Yao in one of the first efforts to develop a general algorithm to carry out secure multiparty computations. Since then, in the 1980s, several advances were made to achieve this goal and, nowadays, it is a well-established result that any multiparty function can be securely computed. This important result, however, comes with an important restriction: fairness cannot be achieved in general. Fairness is the guarantee that, at the end of a computation, either all parties receive their outputs or none of them does. Motivated by this impossibility, several alternative definitions of fairness have been proposed. One of them considers a computation to be fair if the dishonest parties are monetarily penalized and the honest ones are monetarily compensated. According to this definition, a fair computation can be viewed as the enforcement of a contract, in which the parties agree on paying a penalty if they misbehave. Recent works have shown how cryptocoins can be used to write those contracts and, therefore, to be used for carrying out secure and monetarily fair multiparty computations. A cryptocoin is a monetary system that relies on cryptographic principles for achieving security and controlling the coin issuing rate. Bitcoin, created in 2008 by Satoshi Nakamoto, was the first practical realization of this idea. In its core, there is a publicly maintained data structure called blockchain, which works as a ledger and stores every transaction ever made. The security of the blockchain, including its non-malleability, is guaranteed by the difficulty of the proof of work required to add new data to it. A Bitcoin transaction can only be redeemed by a user that presents an input satisfying a script specified by the issuer of the transaction. Contracts written on these scripts are enforced without an external trusted third-party to intervene. This makes Bitcoin suitable and interesting to confer monetary fairness to multiparty computations. One of the goals of this work is to present the results that allow any function to be securely computed and the ones that show the impossibility of achieving fairness in general. We will try to present these results with the appropriate mathematical rigor to avoid giving just an overview of them. We will also analyze a recently proposed construction that uses Bitcoin as a platform to carry out fair multiparty computations. Finally, based on its positive and negative points, we will propose a construction with the same goal.