Past student projects in 2019

Proposed projects pages (archives): Spring-2019, Fall-2019

 


Master thesis and PhD projects

A Control Plane in Time and Space for Locality-Preserving Blockchains

Master Thesis – Arnaud Pannatier

Arnaud Pannatier – Master Thesis

Report, Presentation, Poster, Code

Abstract

Distributed ledgers were the trend of the last ten years. You might realize that when your hair- dresser starts to tell you that he plans to put his money into blockchains or when your little cousin asks to have some Bitcoin for Christmas. The research in this field is growing every year.

However, distributed ledgers still have weaknesses. The purpose of this work is to propose a solution concerning two well-known weaknesses. The first one is the time required to confirm a transaction. Indeed, in Bitcoin, validating a transaction can take around one hour, because it takes around ten minutes to validate a block, and it needs around six blocks to be convinced with a high probability that the ledger won’t be forked, and the transaction invalidated. This might be acceptable for some transactions of great value. For example, if somebody is buying a car using Bitcoin, this person might agree to wait one hour so that its transaction is validated. However, if somebody wants to use it to buy its daily coffee, he might be a bit annoyed to wait that long. The other weakness appears in World War III scenarios. If a third World War occurs, splitting the World in two, one can expect that the circumstances would cut the communication between the two sides. This is a problem for standard distributed ledgers as it is leading to forks that the system cannot resolve at the end of World War III.

Three Types of Money Creation

Haoqian Zhang – PhD semester project

Report, Presentation

Abstract

The financial crisis that happened in 2008 is considered by many economists to have been the worse financial crisis since the Great Depression. In the same year, the Bitcoin white paper was published by Satoshi Nakamoto. The coincidence seems to reveal that Bitcoin, or its underlying technology named blockchain, would change our financial system.
Twelve years have passed now. Bitcoin has gained a huge success and blockchain has become the focus not only in industry but also in academia. And yet, our monetary system remains fundamentally unchanged, with the possibility that the next financial crisis is coming within the next few years.
In this report, I first introduce how money is created in our current mon- etary system, revealing the fact that money can not be created without creating debt. Besides, the phenomenon of asset price inflation in recent decades could be related to our monetary policies that primarily focus on the general price of goods and services and pay little attention to asset price.

Featured projects – fall semester

Locality-preserving IPFS

Can the Inter Planetary File System (IPFS) be improved using locality preserving features? This project answers the question and provides an interesting analysis: pair interaction latency can be reduced for pair of nodes with low round trip times.

Performance enhancement of a javascript crypto library with big numbers

This project studies javascript optimisations in the context of the Kyber cryptographic library developed at DEDIS. The results show that the library can be more than 4 times faster with some clever optimisations.

Web content certification on the blockchain

The web is a rich but also very volatile source of information. This project provides a browser plugin that allows users to certify that some content once existed on the web using a quorum of witnessing nodes.

Fall semester

Improvement of a JavaScript cryptographic library performance with big numbers

Julien von Felten – Master semester project

Report, Presentation, Code

Abstract

The goal of this project is to optimize the library Kyber. Kyber is a package which provides a toolbox of advanced cryptographic primitives, implemented in Go. It is used in the Cothority project. This project is being developed by the DEDIS team which is working on projects related to large-scale collective authorities (cothorities), which distribute trust among a number of independent parties to allow scalable self-organizing communities. A part of Cothority, named Cothority client library, was implemented in JavaScript to offer a socket interface and the status of the SkipChain Explorer. Kyber was also adapted in JavaScript to have link verifications in this status. The problem with this adaptation is its slowness. Indeed, as a cryptography library needs to use big integers and JavaScript did not have any big integer type, Kyber is using bn.js for the big integers as the native type number supports only 53 bits. This turns out to be very slow especially when it comes to elliptic curve operations. Therefore, the link verifications are turned off on the SkipChain Explorer.

This project aims to improve the performance of the pairing cryptography such that it can be applied to the SkipChain Explorer so that the links could be turned on. The general idea is to find different possible optimizations and implement them. A benchmark is also implemented in order to compare the different optimizations and the actual library. The first optimization chosen is the use of the BigInt type instead of the bn.js library. The second one is to decrease the number of modulo operations. The last is to set up memory pools.

Speeding up the InterPlanetary FileSystem (IPFS)

Guillaume Michel – Cybersecurity semester project

Report, Presentation, Code

Abstract

Distributed data stores are widely used for different purposes and require in most cases strong responsiveness and partition resistance. Geo-replication is a solution for providing locality and decreasing interaction latency, in which data replicas are stored close to the users interacting with it. The close metric is a distance defined in term of ping latency, or the Round Trip Time (RTT ) between two peers. The protocol Crux developed by the DEDIS lab at EPFL enhances existing data stores with efficient locality techniques. It aims to provide low interaction latency, resilience to network partition, while keeping a low storage overhead. Crux has proven to be efficient on these aspects, when implemented and evaluated on top of two popular data stores: Redis an eventually consistent system, and CockroachDB, a strongly consistent system.

ALINE – Attestation that Online Content Existed

Charline Montial – Semester project

Report, Presentation, Code

Abstract

The Web is a rich source of information but is not a stable one, unfortunately. Indeed, one might read a controversial blog post, make a case against it to finally see its original content updated or removed with no way to prove what has been originally posted. This is only one of the many cases where having a proof that some online content was once available at some point would be a great help for users. We can think of journalists who could then cite online articles, or online victims who could prove they have been harassed, even if the actual content has been removed. The aim of this project is to propose a browser plugin that allows users to certify the content of some web pages at anytime.

ONet Implementation of Gossip-based Signature Aggregation

Elias Manuel Poroma Wiri – Master semester project

Report, Presentation, Code

Abstract

Decentralized cosigning protocols have the main purpose of collecting digital signatures of a message from many peers. This type of protocols is used in two existing implementations. The first one is BLS CoSi which uses trees to get the signatures and aggregate them, the second one is a gossip protocol.

This semester project develops and compares alternative implementations of the gossip-based aggregation. The main goal of the new implementations is to reduce the bandwidth used and to be relatively fast.

Furthermore, this project adds an hybrid implementation of trees and gossiping inside Cothority’s ONet library, which is used for a new implementation of signature aggregation. Finally, there is an analysis of this protocol, measuring its performance and finding possible future improvements.

Experimenting with Matrix federation over Yggdrasil

Timothée Floure – Bachelor semester project

Report, PresentationCode

Abstract

Matrix is a federated event-based communication protocol largely used for instant messaging, which appeared in 2014 and reached its first stable release during the first half of 2019. It has been steadily gaining adoption – especially among free software groups – over the past few years, as its ecosystem supports many modern features such as media content, message history and synchronization, end-to-end encryption and easy integration with external services (audio and video call via Jitsi, bridging with other IM networks). While decentralized to some extend given its federated structure, Matrix heavily depends on global and centralized – both from technical and governance point of views – infrastructure for name addressing (DNS) and routing. The aim of this project was to develop a proof-of-concept of Matrix federation over a peer-to-peer system, which has been done with Yggdrasil, an experimental end-to-end encrypted peer-to-peer overlay network featuring routing logic akin to compact routing.

Spring semester

Key Agreement in Peer-to-Peer Collaboration Systems

Charles Parzy-Turlat – Semester project

Report

Abstract

Nowadays, online platforms providing editing of files shared with other users are widespread and used by lots of people. The most popular example is Google Doc. It allows the people to create and modify online documents while collaborating with other users in real time. It simplifies the lives of its users by dealing with all the concurrency issues introduced by having several users contributing to the same file at the same time.

However, despite its usefulness, it relies on a central server to operate properly. Thus it is a centralized system. These kind of systems have some flaws.

Implementation of auctions in the context of ByzCoin

Makléwa Téta Diana Harena – Master semester project

Report, Presentation, Code

Abstract

In this project, I designed and implemented an open ascending auction system using the Byzcoin-blockchain and the Cothority framework. The designed client application works well with the Byzcoin service and users through it can set up auctions and place bids. The conducted evaluation of the system shows that the system can create more than 200 simultaneous auctions per 20s and allows a maximum of 180 simultaneous bids per 20s.

How Local Are Ripple Transactions

Etienne Caquot – Semester project

Report, Presentation, Code

Abstract

We already know that economic activity is strongly correlated with distance: the closer two companies are, the higher the flow of transactions between them (all else equal). The question is, do blockchain transactions show the same pattern? We base our work on the Ripple blockchain to investigate the answer to this question.

BLS Cosigning via a Gossip Protocol

Lukas Gelbmann – Semester project

Report, Presentation, Code

Abstract

Decentralized cosigning protocols, which collect digital signatures of a message from many peers, play a central role in several applications. In this semester project, a new gossip-based cosigning protocol using Boneh-Lynn-Shacham (BLS) signatures is designed, built and tested in simulations. The main goals are for the new protocol to be highly fault tolerant, relatively fast and not to overwhelm any node. The new gossip protocol is compared with BLS CoSi, an existing cosigning protocol, in experiments, with the new protocol performing better in the most important metrics, but not in terms of efficiency. The new protocol’s performance is then analyzed, showing possible avenues for future improvement.

Threshold Logical Clocks

Manuel Vidigueira – Semester project

Report, PresentationCode

Abstract

In this work, we analyze a novel threshold logical clock (TLC) ab- straction that seeks to close the gap between synchronous and asyn- chronous protocols, keeping the simplicity of the former while providing the stronger guarantees of the latter. TLC provides an illusion of synchronicity by allowing subsets of nodes to make progress as a group, despite operating in a fully asynchronous and/or byzantine network. We focus on the particular application of TLC for the problem of asynchronous consensus, and give an overview of how it can be implemented in a simple and efficient way with a modular architecture. Lastly, we compare the performance of different implementations of TLC and present the results of our experiments.

Locality-Preserving Blockchain Implementation

Maxime Sierro – Bachelor semester project

Report, PresentationCode

Abstract

The goal of this project is to create a blockchain implementation in the context of the locality-focused Nyle system. The implementation is done with DEDIS Lab’s Cothority platform, written in Go. The consensus layer is based on ByzCoinX which uses a practical Byzantine fault tolerance algorithm and is already implemented. For this reason, the project is more focused on the higher layers, such as the sending and storing of transactions and signatures. Those functionalities, however, are implemented from scratch.

Know-Thy-Neighbour: Approximate Proof-of Location

Sabrina Kall – Semester project

Report, PresentationCode

Abstract

Applications such as the sharing economy would become more efficient with a ‘proof- of-location’, which can provide a weaker, temporary validation to speed up small transactions while stronger proofs are still being computed. Relying on GPS coordinates, however, is not secure, because nodes could provide fake information. What if we simply instruct each participant to specify its location with respect to other participants? For example, Alice says she is 30 ms round-trip time from Bob and 50 ms from Carol, and publishes this information on the blockchain. Alice could still lie, but Bob and Carol can verify Alice’s claim and thus reinforce the information, or, on the contrary, infirm it. Although latencies do not exactly map to geographical distances, very small latencies are, with high probability, between nearby nodes.

Therefore, assuming an accurate and up-to-date exchange of latencies between nodes, nodes with small latencies between them would make an adequate consensus group for two nodes seeking a low-latency validation to perform a fast, low-value transaction.

The main issue for a proof-of-location is the potential for a malicious node to craft inaccurate latencies to give to other nodes, or for a malicious node to tamper with another node’s latencies. Below, we describe a scheme that allows nodes to securely exchange latencies with each other and then, based on these latencies published in the blockchain, identify the malicious nodes whose behavior is most damaging.

Compact routing on low earth orbit satellites

Stefan Rotarus – Semester project

Report, PresentationCode

Abstract

Recently, a couple of companies decided to invest into low earth orbit satellite (LEOs) to achieve very low latency on internet transmissions. The first purpose of such technologies will be to achieve high-frequency transmissions, in particular for financial operations.

The second and more altruistic goal would be to provide better latency to remote areas, cargo boats and many other places where a terrestrial infrastructure appears hard to build.

The architecture of such satellites networks appears to be very regular and offers a low amount of unpredictable events. For this reason, we decided to simulate the efficiency of Compact Routing algorithms in order to achieve smaller routing tables and fewer computations than a Dijkstra algorithm. Of course, this has a cost, and we are here looking at how the total routing distance will be affected by the use of Compact Routing.

Decentralising a Mobile Application

Yann Gabbud – Bachelor project

Report, Presentation

Abstract

The goal of this project is to identify a category of application where decentralization can be beneficial and to adapt an android application to operate in a decentralized context. The fist step consists to identify the parts of the app where data is stored, and then find a way to store that data in Cothority instead.

The motivations of this project are to see if it is possible to achieve such a task using Cothority, Calypso and Byzcoin and to see what are the limitations.

Network Partitioning Effects on Ripple Transactions

Yoan Martin – Semester project

Report, PresentationCode

Abstract

Blockchain is a hot topic. It is used for many activities, but sending money is a significant one. Ripple is a blockchain based network that allows anyone to transfer money across the globe. Since this network is widely used by banks and financial institutions, it becomes attractive to attackers. This project considers network attacks executed by a malicious Autonomous System (AS). The latter is a subnetwork of the internet managed by one or more operators. The goal is to understand if an attack on the internet network can affect the behaviour of the Ripple network. To analyse this effect, the Ripple network will be recovered and matched with existing IP data. Then, using a dataset of transactions, the behaviour of the Ripple network can be simulated and analysed. Consequently, this project is a combination of data-analysis and security. Having a good understanding of data-analysis tools and network security is a main requirement to understand and lead this project. This report will explain the implementation of this project. I will start by defining what is the Ripple network and how it is working. Then, the implementation of the graph recovery will be explained. I describe the main strategy and the limitations encountered. Finally, I will analyse this graph by considering different network attacks.