Crypto in Crypto

Stefan Dziembowski

17th SFI IT Academic Festival, Cracow�March 15^th, 2022

Crypto

Unit recently:

​

Crypto = a short name for cryptography

​

Also: the name of the leading annual conference in cryptography.

Now:

Crypto = cryptocurrencies�(e.g., Bitcoin)

Googling “crypto”:

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research

​

Main goal of cryptographic research

Make the digital world more secure

Part of a larger picture

digital law

secure software design

usable security

cryptography

economics of security

secure hardware design

number theory

Of course: lots of interactions!

computational complexity theory

quantum physics

Tools from other areas

Cryptography

• in the past:
• used mostly by the military and diplomacy�(since the ancient times),
• often considered a part of linguistics

​

​

​

• nowadays (from 1970s):
• lots of civilian and commercial applications
• usually considered a part of computer science

​

​

​

​

​

​

​

Caesar

Historical cryptography

cryptography ≈ encryption

main applications: military and diplomacy

Modern cryptography

cryptography = much more than encryption!

sevenites

now

public-key cryptography

e-cash

electronic voting

multiparty-computations

mental poker

zero-knowledge

key agreement

electronic auctions

signature schemes

Traditional goal of cryptography: emulate “secure channels”

reality:

ideal world:

???

Encryption is used to emulate the�“ideal world” in the “real world”

New directions in cryptography

Idea: extend the “emulation” paradigm beyond the secure communication.

​

​

Example: Distributed Cryptography protocols (in particular: Multiparty Computations).

Multiparty Computation protocols

Protocols where the users don’t trust each other but nevertheless

they want to achieve a common goal

Two-party case:

bfa1406343bb49

ga63w234349aa

bfa144534555d9

Alice

Bob

I don’t trust Bob

I don’t trust Alice

common goal achieved!

this is called a “cryptographic protocol”

Example 1: coin tossing

bfa1406343bb49

ga63w234349aa

bfa144534555d9

output:

Y

Y

where

Y =

with probability 1/2

with probability 1/2

Example 2: marriage proposal

bfa1406343bb49

ga63w234349aa

bfa144534555d9

output:

Y

Y

input:

A =

1 if Alice loves Bob

0 otherwise

B =

1 if Bob loves Alice

0 otherwise

With a “trusted third party” – it’s easy

A

B

Y

Y

bfa1406343bb49

ga63w234349aa

bfa144534555d9

But can we do it without a trusted third party?

In other words: can we “emulate” the ideal world in the real world?

ideal world:

real world:

Note the difference

encryption: the adversary is external

secure computation: the adversary is “internal”

Alice’s point of view:

Bob’s point of view:

An example of a multiparty protocol

voting: n parties connected by pairwise channels vote yes/no

yes

yes

yes

no

no

output:

3 yes

2 no

security requirements:

• votes are secret
• the votes are correctly counted
• in particular: there is a consensus about the outcome

Non-cryptographic voting

The parties send their votes to a trusted authority, who computes the output, and publishes it.

yes

yes

yes

no

no

publishes the output

Cryptographic voting

yes

yes

yes

no

no

1agf30

1af154

1aa55

output

output

output

output

output

1. The parties exchange messages.

​

​

​

​

​

​

​

• Everybody learns the output.

Can such protocols be constructed?

In other words: can we emulate an “ideal” trusted party in a “real” world?

real world

ideal world

Answer: yes!

“Distributed cryptography”

�Every can be “emulated” in a secure way.

​

And we can prove the security mathematically!

Basic research in cryptography starting from 1980s:

Caveat: these protocols are not very efficient.

Typically: assuming that the majority of the participants is honest.

Possible applications

​

• e-voting

​

​

• cloud computing

​

​

• online auctions

​

​

The situation until recently

in practice: �

• it’s too inefficient,
• using trusted third parties is ok

​

it’s philosophy, not computer science

And then in 2008

e4ac7dec3e2c

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research

​

Cryptocurrencies

The most famous one: Bitcoin.

​

​

Based on the assumption that “the majority of the computing power is honest”.

​

Implemented using a technology called “blockchain”.

​

​

Blockchain?

Blockchain = a distributed protocol for emulating an ideal “ledger”

maintans a �write-only�public database

this database contains transactions for transferring virtual “coins”

Most crucial property: there is a consensus between the parties on the ledger’s contents.

Main idea of Bitcoin

Ledger is maintained in a “voting” process (also called “mining”).

The “majority” decides about the state of the ledger.

​

​

​

​

​

​

​

​

“Is this the correct contents of the ledger?”

...

yes

yes

yes

no

no

This works under the assumption that the majority is honest.

Problem

How to define “majority” in �a situation where �everybody can join the network?

​

The Bitcoin solution

Define the “majority” as

the majority of the computing power

Now creating multiple identities does not help!

How is the “computing power” measured?

Bitcoin uses so-called:

Proofs-of-Work

Nowadays executed mostly on dedicated hardware

Alternative blockchains

1. based on other resources than the “computing power”
2. closed systems maintained by a fixed set of parties (also called: “consortium” or “permissioned” blockchains”)��For example:

Extensions of the blockchain ledger

Smart contracts

Informally:

agreements written on the ledger that are enforced by the mechanics of the cryptocurrency.

Simplest example: “assurance contracts”:

• A group of parties pays 1 coin each to some account.
• Each payment happens if and only if all the other ones happened.

The most popular blockchain platform that fully support smart contracts:

Potential applications: financial services, energy trading, logistics, land registers, internet of things, smart cities, decentralized organizations,…

​

And now suddenly:

We distributed cryptography, relying on a single trusted party is not acceptable

A question

Why are they called the “cryptocurrencies”?

​

Not completely clear (cryptography is just a part of this technology)….

​

Good or bad news for cryptographers?

​

​

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research

​

In a nutshell

Work on the cryptographic aspects of cryptocurrencies (“crypto in crypto”).

“if you can't beat them, join them”

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research�
1. Better “consensus mechanism”

​

• Smart contracts

​

• Off-chain protocols

​

​

​

Bitcoin blockchain properties

• slow: transaction confirmation time at least 10 minutes�
• expensive: currently around USD 0.10 per transaction

​

• consumes a lot of energy: estimated to be equivalent to the electricity consumption of Ireland.

​

Our idea: Proofs-of-Space

​

Main idea: Replace work by disk space.

�

​

​

[D., Faust, Kolmogorov, and Pietrzak, CRYPTO 2015]

Advantages

• more energy-efficient�
• no “hardware acceleration”�
• cheaper (user can devote their unused disk space)

Real-life implementation

Chia – a cryptocurrency that uses these ideas.

​

​

Creator: Bram Cohen

�

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research�
1. Better “consensus mechanism”

​

• Smart contracts

​

• Off-chain protocols

​

​

​

Andrychowicz, D., Malinowski, Mazurek: Secure multiparty computations on Bitcoin

multiparty computation protocols

connection

Example: lotteries

Two party lotteries

• a random party earns 1 BTC
• the other one loses 1 BTC

bfa1406343bb49

ga63w234349aa

bfa144534555d9

Looks similar to the “coin-tossing problem”.

bfa1406343bb49

ga63w234349aa

bfa144534555d9

output:

Y

Y

where

Y =

with probability 1/2

with probability 1/2

Idea

1. The parties execute the coin-tossing protocol
2. The looser pays 1 BTC to the winner.

​

Problem: wow to force the looser to “respect to outcome”?

​

In our paper we solve this problem by using the mechanics of the Bitcoin transaction system.

​

​

Plan

1. Cryptography – past and present�
2. Bitcoin and other cryptocurrencies�
3. My research�
1. Better “consensus mechanism”

​

• Smart contracts

​

• Off-chain protocols

​

​

​

Off-chain technology

Move massive bulk of transactions off-chain.

Payment channels:

• User carry out transactions off-chain between each other
• In case of disagreement, rely on blockchain to resolve dispute.

Off-chain transactions

Resolve dispute

Resolve dispute

the “dispute resolution” is done using smart contracts

Our work on this topic: �the Perun system

S. Dziembowski, L. Eckey, S. Faust, and D. Malinowski: PERUN: Virtual Payment Hubs over Cryptographic Currencies

S. Dziembowski, S. Faust, and K. Hostakova: Foundations of State Channel Networks

S. Dziembowski, L. Eckey, S. Faust, J. Hesse, and K. Hostáková: Multi-party Virtual State Channels.

​

See: perun.network

​

Interested in working with me?

Send me an email (S.Dziembowski@crypto.edu.pl)�

​

​

​

Positions are available both at the University of Warsaw and at IDEAS NCBR.

Thank you!