Appunti insegnamento: Blockchain and smart contracts

ECURE ULTI ARTY OMPUTATION

We want to allow the multiple users to compute a function of their own data but

without revealing to the other parties of the group what the data is

Secure Multi-Party Computation (MPC) provides means for multiple users to

 jointly compute a function of their inputs while keeping such inputs private

Unlike traditional cryptography, we want to keep these inputs private with

 respect to other users, not an external eavesdropper -> we are not interested in

hiding our data with respect to external other users (traditional model)

All the actor inside the network want to communicate one another. Although

 they communicate with people that they know belonging to the network, they

want to keep the data secret from the other parts in the network

Definition

Let us consider a number N of participants, each having private data that they

 want to hide

Participants want to compute a function of the private data of the whole group

 but without revealing the data to the other members

Example: I want to know who is the oldest in a group of people, but without

 revealing the age

Secure MPC – solution

Everything could be solvable by having a trusted third party -> a solution for

 the secure MPC is involving a trusted third-party (e.g. Tony)

Each members tells the age to Tony

 Tony computes the output and tells everyone

 Tony keeps the secret forever

 All parties learn from the interaction no more than what they learn from

 an incorruptible Tony

The purpose of MPC is to remove the need of Tony: the fact that Tony is there

 implies that somehow, we need to reveal the data to someone, and we need to

trust this someone to keep the data private

The difficulty in secure MPC lies in the security part

 Real world/ideal world paradigm:

 In the ideal world there exists an incorruptible trusted party to whom

 each protocol participant sends its input

In the real-world there is no trusted party, and all the parties can do is to

 exchange messages with each other

A protocol is secure if one can learn no more about users’ private input in the

 real world than she would have learnt in the ideal world

Problem origin: the adversary is a legitimate user of the network -> the fact that

 we want to protect or data with respect to other legitimate users in the network

is the origin of the security problem. All users inside the network may want to

see data of other users so the problem is that they might be able to compute

one another so we have to recognize those ones that are cheating in order to

remove them from the network

A single malicious user may collude with other users in the network to gain

 insights on users’ private data

It is common to assume that a majority of users is honest: a scheme has

 security guarantees if the majority of users is honest

The solutions using this assumption are different from those that don’t

 Important example for the latter: two party computation -> they create a circuit

 with logical ports

Types of Adversaries

Semi-honest (passive): the

 adversary(ies) do not deviate from the

protocol specification. This type of

security prevents inadvertent leakage of

information -> they don’t inject data in

the network: they just listen the communication and try to infer knowledge

about the data that users exchange

Malicious (active): the adversary(ies) may arbitrarily deviate from the protocol

 specification to cheat and take advantage of some implementation flaws ->

they disclose data of other users

A Practical Example

Private set intersection is a secure MPC technique

 Two parties holding sets compare them to see whether there exists and

 intersection

Neither party learns anything about the set of the other party

 Both (might) learn that an intersection exists together with the elements of this

 intersection

We know that there is an intersection of data with other users in the network but

without revealing the data

D S

ATA TRUCTURES

The blockchain needs to be stored on devices

 The blockchain has a specific structure (depending on the implementation) that

 needs to be recorded via data

We define as data structure the way in which we organize the content and

 explain the organization to a machine

The blockchain needs specific types of data structures



L L

INKED IST

A linked list is a list of blocks each containing a reference (pointer) to the

 previous block in the list

Part at the beginning = header -> it contains information about the index of the

 block and might contain information about the index of the previous block of the

list

Doubly linked lists: couples of block reference one another

 Using a simple linked list is not sufficient to provide a good data structure for

 blockchain

Blocks need to be secured in the way they are linked

 Example of attack: a malicious user crafts a block and manages to link it in

 between two consecutive blocks

The attacker can steal money from accounts



We need secure data structure: having single linked list -> each block inside the list

should contain information about the previous block and about the successive block. It

means that in the header there are two different fields:

1. First field, saying the previous block

2. Second block: block one and block three

H L

ASH IST

Instead of storing information inside the header of blocks, we use part of the security

technics: we use hash functions, that provide features used for security, in particular

the fact that they are resistance were attacks the pre-image (we cannot guess the

input of the hash function within the output)

List of hashes of data blocks in a file or set of files

 Take the hash of the data

 Take the hash of the hash and get the top

 hash

The top hash is used for data integrity

 check

Hash list: we have multiple blocks, that instead

of being linked one another just based on the

information of the previous block, it contains

the information stored through an hash function

Example: we have 3 blocks

1. The first block is Data 0

2. A way which we can securely link blocks in the list is storing the Hash of the

Data: the second block contains the hash of Data 0, that provides unique

information on what is the previous block

There is no two input that provide the same output on the hash function

3. Top hash

We want to see whether the data structure that

we downloaded provides integrity and if it is

the data structure connected to data 0: we

have to compute the different hash functions

and see whether their results match the

information stored in different blocks

Example: Lamport Chain

The hash function can be iteratively applied multiple times to provide security in

 an hostile environment

Denote h^N(pw) as the hashs of pw computed N times

 Suppose the receiver only knows h^N(pw)

 The sender willing to authentication sends h^(N-1)(pw)

 The receiver computes h(h^(N-1)(pw)) and checks whether it matches

 The attack is not able to produce numbers that match with that

 Replay is also not possible



In order to provide a security parameter to the receiver, we have to compute the hash

function multiple times: the adversary is not able to compute the pre-image -> we

send the pre-image such now the receiver knows we are talking about the second

communication. So, we compute the hash function and then the hash function again

and get the final value

M T

ERKLE REES

Also known as Hash tree: we a “tree”, so a data structure which has a root node

 (node where the tree begins). Starting form the root node we have several

connections that go through different blocks

Links between different nodes are created through hash functions: starting from

 the leafs we have data, and the parent of the leaf node contains the hash of the

data in the leaf

Tree in which every leaf is labelled with the cryptographic hash of a data block

 Every non-leaf is labelled with the cryptographic hash of the labels of its child

 nodes

Allows for the efficient and secure verification of the content of a large data

 structure

An example of commitment scheme: commit to a value without actually

 revealing it unless needed

The root contains the top hash

Before downloading a file, you connect to the root node to get the top hash

- The root is usually a trusted source

- The receiver can hence start reconstructing the whole tree

- The received tree and its hashes is checked against the top hash until we find a

match

- This confirms that the file has not been modified or damaged

We retrieve the top hash as a secure data source and then we can start downloading

the file and compute the different hashes and we can see whether they match with

what is contained in the top hash

What is in the TOP HASH is the result of the different/many iterative applications

 of the hash function

If all the pieces that we retrieve are correct, we will end up with the same top

 hash value

Advantages

Branches can be simultaneously received and verified, no need to wait the

 whole data structure before starting the verification

The verification time is proportional to the logarithm of the number of nodes

 (hence smaller than the number of nodes)

In a list, the verification time is proportional to the number of nodes: a tree data

 structure is more efficient in terms of searching

If we retrieve a file that is encoded in a list, we need to retrieve that whole list before

starting verifying if the file is correct: we need all the nodes inside the tree in order to

compute all the hash functions; if the data is encoded in a tree structure, we can start

verifying the correctness of the file as long as we get it so we need a path from the

root node to the leave in order to simultaneously verify different parts

In the trees, in order to find a value, we have a complexity which is proportional to the

number of nodes, that is smaller than the one we have in lists

Hash Chain vs. Blockchain

Both use hash functions to create a connection between two successive blocks

 Blockchain is intended to support distributed consensus in a public ledger

 Has additional rules for encapsulation and permissions



Lezione 29.03

Bitcoin

What is Bitcoin?

It’s a collection of concepts and technologies that form the basis of a digital

 money ecosystem

Bitcoin is the unit of currency used to store and transmit value among users in

 the Bitcoin network

Users communicate using the Bitcoin protocol over the internet (primarily)

 Such protocol can be run on multiple types of devices



Bitcoin uses the idea of list with hash functions but introducing a way to update the

content of lists. It was