Epidemic broadcast algorithms in a Byzantine environment

Abstract

Peer-to-peer broadcasting algorithms are a scalable and cheap way of disseminating information to a large number of participants. However, most of these algorithms do not consider the possibility of some members acting in an unintended way, with malicious or selfish motives. In order to be useful in a real world scenario, these algorithms must be secure, robust and efficient, even in the presence of adversaries. This thesis presents an overview of the challenges that peer-to-peer broadcasting algorithms face, as well as some of the security mechanisms that can be employed to mitigate them. Thus, we present Bycast, a secure and efficient peer-topeer broadcasting algorithm that is able to tolerate up to 45% of malicious nodes in the system. In order to achieve a high level of security, Bycast relies on strong membership integrity guarantees that make it harder for attackers to successfully compromise other nodes. In order to force nodes to cooperate, and contribute to the good performance of the system, Bycast employs an innovative auditing scheme that is able to detect nodes that are not cooperating with their resources, and evict them from the system.

Os algoritmos de transmissão “peer-to-peer” são uma maneira escalável e barata de disseminar informação para um grande número de participantes. No entanto, a maioria desses algoritmos não considera a possibilidade de alguns participantes agirem de forma imprevista face à especificação do algoritmo, quer por motivos maliciosos quer egoístas. Para serem úteis num cenário do mundo real, esses algoritmos devem ser seguros, robustos e eficientes, mesmo na presença de adversários. Esta tese proporciona uma visão geral dos desafios que os algoritmos de disseminação peer-to-peer enfrentam, bem como alguns dos mecanismos de segurança que podem ser utilizados para mitigá-los. Assim, apresentamos o Bycast, um algoritmo de transmissão peer-to-peer seguro e eficiente, capaz de tolerar até 45% de nodos maliciosos no sistema. Para alcançar um alto nível de segurança, o Bycast conta com fortes garantias de integridade no sistema de membership que torna mais difícil para os atacantes comprometerem outros nodos com sucesso. Para forçar os nodos a cooperarem e contribuir para o bom desempenho do sistema, o Bycast emprega um esquema de auditoria inovador que é capaz de detectar nodos que não estão a cooperar com os seus recursos de forma a removê-los do sistema.