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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/17143 |
| Date | 02 February 2016 |
| Creators | OLIVEIRA FILHO, Márcio Barbosa de |
| Contributors | OLIVEIRA, Anjolina Grisi de, QUEIROZ, Ruy J. Guerra B. De |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds