Blockchain for Developers

Satoshi Nakamoto's Bitcoin

Ottobre 2008:

Bitcoin: A Peer-to-Peer Electronic Cash System

Fondamenta teoriche della blockchain

• Definizione di blocco, come unità del distributed timestamp server
• Definizione di transazione con il meccanismo di firme digitali
• Proof-of-Work

Rilascio del codice e live da gennaio 2009

Bitcoin P2P network

Ad alto livello:

• Una nuova transazione è diffusa a tutti i nodi
• Ogni peer controlla la tx e la mette in coda
• Un peer costruisce il suo blocco dalla coda e lo manda in broadcast
• Ogni peer riceve il nuovo blocco e ne controlla la validità
• I peer accettano implicitamente il blocco lavorando al successivo

Blockchain Internals

Block

type Block struct {
    // Metadata
    Timestamp time.Time
    Index     int

    // Payload
    tx []Transaction

    // Previous block's hash
    PrevHash []byte

    // Proof of work
    Difficulty int
    Nonce      int
}

PrevHash è ciò che forma la chain

Miner

I miner sono i peer che producono i blocchi
Qualunque peer può essere il miner di un blocco

• Assicurano che le nuove transazioni siano registrate in maniera sincrona

Incentivi:

• le transazioni immesse nel blocco hanno un costo di commissione
• i nuovi blocchi contengono una ricompensa (block reward)

Qual è il trucco?

Proof of Work

Proof of Work

Limitare artificialmente la capacità di creare blocchi

Un nodo accetta un blocco solo se il miner riesce a provare di aver risolto un problema

• il problema è difficile da risolvere
• la soluzione è facile da verificare

Il lavoro del miner viene convertito in token (ricompensa)

In caso di ambiguità un nodo sceglie la chain più lunga (+ lavoro)

Proof of Work

Grazie alla PoW:

• no Spam
• no (D)Denial of Service
• permette di stabilire il consenso
• resistenza ad attacchi fraudolenti
• no Spam
• throughput impostabile da protocollo
• no Spam
• no Spam
• lovely Spam

Proof of Work di Hashcash

Bitcoin ha mutuato la PoW da Hashcash [Dwork, Naor 1992]

Idea: il francobollo per la posta elettronica

• dà un peso all'email
• limita la capacità di mandarne enormi quantità (Spam)

Ricorda qualcosa?

Hashcash

Esempio di francobollo:

X-Hashcash: 1:24:180213122530:sergio@localhost::82gsa6jcvgsKQQ:fXAG

Campi:

type Header struct {
    version    int // always 1
    difficulty int
    date       Timestamp // YYMMDDhhmmss
    resource   string    // recipient
    extension  string    // unused
    random     string    // base64 encoded
    nonce      Nonce     // base64 encoded
}

Hashcash

Per essere valido l'header deve avere questa proprietà:

$ echo -n 1:24:180213122530:sergio@localhost::82gsa6jcvgsKQQ:fXAG | sha1sum
0000007a89c9a369092a1248b830aa5bd8db3d38  -

Il suo hash SHA-1 deve essere "piccolo"

• creare un bollo è eseguire un partial preimage attack
• lavoro = #bit più significativi uguali a 0

Non è triviale, computazionalmente, perché SHA-1 è una funzione di hash crittografica

Hashcash

package main

import (
	"crypto/rand"
	"crypto/sha1"
	"encoding/base64"
	"encoding/binary"
	"flag"
	"fmt"
	"io"
	"time"
)

type Header struct {
	version    int // always 1
	difficulty int
	date       Timestamp // YYMMDDhhmmss
	resource   string    // recipient
	extension  string    // unused
	random     string    // base64 encoded
	nonce      Nonce     // base64 encoded
}

func (h *Header) String() string {
	return fmt.Sprintf("%v:%v:%v:%v::%v:%v",
		h.version,
		h.difficulty, h.date,
		h.resource, h.random, h.nonce)
}

func (h *Header) Hash() [sha1.Size]byte {
	str := fmt.Sprintf("%v", h)
	return sha1.Sum([]byte(str))
}

func (h *Header) HashIsValid() bool {
	hash := h.Hash()

	// check first nbytes against 0
	nbytes := h.difficulty / 8

	for _, b := range hash[:nbytes] {
		if b != 0x00 {
			return false
		}
	}
	// check remaining bits
	nbits := h.difficulty - 8*nbytes
	if nbits > 0 {
		mask := uint(0xff) >> uint(nbits)
		b := uint(hash[nbytes])
		if (b | mask) != mask {
			return false
		}
	}
	return true
}

type Timestamp time.Time

func (ts Timestamp) String() string {
	t := time.Time(ts)
	yr, mon, day := t.Date()
	return fmt.Sprintf("%02d%02d%02d%02d%02d%02d",
		yr-2000, mon, day, t.Hour(), t.Minute(), t.Second())
}

type Nonce uint32

const (
	NonceByteSize = 3
	NonceMax      = 1<<20 - 1
)

func NewNonce() Nonce {
	buf := random(4)
	v := binary.LittleEndian.Uint32(buf) & NonceMax
	return Nonce(v)
}

func (c *Nonce) Next() error {
	*c++
	if *c > NonceMax {
		return fmt.Errorf("overflow")
	}
	return nil
}

func (c Nonce) String() string {
	buf := make([]byte, 4)
	binary.LittleEndian.PutUint32(buf, uint32(c))
	return fmt.Sprintf("%v", b64(buf[:NonceByteSize]))
}

func Hashcash(difficulty int, resource string, output chan<- *Header) {
    h := &Header{
        version:    1,
        difficulty: difficulty,
        date:       Timestamp(time.Now()),
        resource:   resource,
    }
    
setup:
    h.random = b64(random(10))
    h.nonce = NewNonce()

    for {
        if h.HashIsValid() {
            output <- h
            return
        }
        err := h.nonce.Next()
        if err != nil { // overflow
            goto setup
        }
    }
}

var cfg struct {
	rsc        string
	difficulty int
	njobs      int
	verbose    bool
	help       bool
}

func init() {
	flag.StringVar(&cfg.rsc, "r", "sergio@localhost", "resource")
	flag.IntVar(&cfg.difficulty, "d", 20, "difficulty (bits)")
	flag.IntVar(&cfg.njobs, "j", 1, "number of concurrent jobs")
	flag.BoolVar(&cfg.help, "h", false, "help")
}

func main() {
	flag.Parse()
	if cfg.help || cfg.difficulty < 0 || cfg.njobs <= 0 {
		flag.PrintDefaults()
		return
	}
	ch := make(chan *Header)
	for i := 0; i < cfg.njobs; i++ {
		go Hashcash(cfg.difficulty, cfg.rsc, ch)
	}
	clock := time.Tick(100 * time.Millisecond)
	for {
		select {
		case header := <-ch:
			fmt.Println()
			fmt.Println(header)
			return

		case <-clock:
			fmt.Printf(".")
		}
	}
}

func random(size int64) []byte {
	buf := make([]byte, size)
	r := io.LimitReader(rand.Reader, size)
	r.Read(buf)
	return buf
}

func b64(buf []byte) string {
	enc := base64.StdEncoding.WithPadding(base64.NoPadding)
	return enc.EncodeToString(buf)
}

Proof of Work nella Blockchain

func (m *miner) mine(output chan<- *Block) {
    block := m.prepareNextBlock()
    block.Nonce = rand.Int()

    for i := 0; i < maxRounds; i++ {
        if m.chain.ProofIsValid(block.Difficulty, block.Hash()) {
            output <- block
            return
        }
        block.Nonce++
    }
    output <- nil
}

Verifica della PoW

func (c *Chain) ProofIsValid(difficulty int, hash []byte) bool {
    // check first nbytes against 0
    nbytes := difficulty / 8
    for _, b := range hash[:nbytes] {
        if b != 0x00 {
            return false
        }
    }
    // check remaining bits
    nbits := uint(difficulty - 8*nbytes)
    if nbits == 0 {
        return true
    }
    if nbits > 0 {
        mask := uint(0xff >> nbits)
        b := uint(hash[nbytes])
        if (b | mask) != mask {
            return false
        }
    }
    return true
}

Proof of Stake

Alla Proof of Work (Waste?) c'è una possibile alternativa

funzione randomica che assegna il diritto di creare un blocco

La funzione è pesata proporzionalmente a quanto un candidato (validator) scommette di essere lui il prescelto

• candidati eseguono una transazione speciale che "deposita" una somma (stake)
• ogni nodo, usando f, sceglie un miner per il blocco successivo
• la chain converge per il via delle regole del consenso

Transazioni

Transazione

Le transazioni hanno questa struttura:

type Transaction struct {
    Inputs  []UTXO
    Outputs []string // addresses
    Tokens  []int    // (not using a map just to look like bitcoin)

    PubKey    crypto.PublicKey
    Signature crypto.Signature
}

UTXO

I'oggetto di una transazione sono gli UTXO

• Non sono divisibili
• Sono l'analogo delle monete

type UTXO struct {
    OutputIndex int
    TxIndex     int
    BlockIndex  int
}

UTXO Set

• I nodi popolano un database locale per poter validare velocemente la transazioni

type UTXOSet struct {
    sync.RWMutex
    data map[string][]UTXO
}

func (set UTXOSet) Get(address string) []UTXO
func (set UTXOSet) Add(address string, utxo UTXO)
func (set UTXOSet) Remove(address string, utxo UTXO)
func (set UTXOSet) Contains(address string, utxo UTXO) bool

UTXO

Saldo di un conto sulla Toychain:

func (c *Chain) fundsFromUTXO(utxo UTXO) int {
    // ...
    b := c.Block(utxo.BlockIndex)
    tx := b.tx[utxo.TxIndex]
    return tx.Tokens[utxo.OutputIndex]
}

func (c *Chain) Funds(address string) int {
    funds := 0
    for _, utxo := range c.utxoset.Get(address) {
        funds += c.fundsFromUTXO(utxo)
    }
    return funds
}

UTXO

Trasferimento di UTXO

    for i, tx := range block.tx {
        // destroy inputs:
        for _, utxo := range tx.Inputs {
            addr := tx.PubKey.Address()
            c.utxoset.Remove(addr, utxo)
        }
        // distribute outputs:
        for j, output := range tx.Outputs {
            c.utxoset.Add(output, UTXO{
                BlockIndex:  block.Index,
                TxIndex:     i,
                OutputIndex: j,
            })
        }
        // ...

Indirizzi

La sicurezza di Bitcoin è basata sulla crittografia a chiave asimmetrica
L'indirizzo è derivato dalla chiave pubblica

func (k *publicKey) Address() string {
    str := fmt.Sprint(*k.data)
    hash := Hash([]byte(str))
    return encoder.EncodeToString(hash)
}

Esempi di indirizzi:

• Toychain: LnvGRRelRQFiUw0QaIbfzKO0yW4jebBcIpEcqjIejCI
• Bitcoin: 14v6afb9yYFmM3fozN54yxsEtBCLVmoRwx

Transazioni

Alice vuole pagare token a Bob:

• Bob ed Alice generano due coppie di chiavi asimmetriche
• Bob ed Alice si scambiano le chiavi pubbliche su un canale sicuro
• Alice crea una transazione verso l'hash della pubkey di Bob (indirizzo)
• Alice firma la transazione con la propria privkey

I token trasferiti saranno spendibili solo da chi possiede la chiave privata di Bob

Transazioni

PayToAddress

func (p *payer) PayToAddress(address string, amount int) error {
    myaddr := p.privKey.Public().Address()
    myutxo := p.chain.utxoset.Get(myaddr)
    if len(myutxo) == 0 {
        return fmt.Errorf("no utxo for %v", myaddr)
    }
    mytokens := make([]int, len(myutxo))
    for i, utxo := range myutxo {
        mytokens[i] = p.chain.fundsFromUTXO(utxo)
    }
    inputs, change, err := p.genInputs(myutxo, mytokens, amount)
    if err != nil {
        return err
    }
    outputs, tokens := []string{address}, []int{amount}
    if change > 0 { // give me back the change, no fees in toychain
        outputs = append(outputs, myaddr)
        tokens = append(tokens, change)
    }
    tx := NewTx(inputs, outputs, tokens)
    tx.Sign(p.privKey)
    p.chain.SubmitTransaction(tx)
    return nil
}

Transazioni

func (c *Chain) checkTransaction(tx Transaction) error {
    var funds, output int
    valid := tx.PubKey.Verify(tx.Hash(), tx.Signature)
    if !valid {
        return fmt.Errorf("invalid signature")
    }
    addr := tx.PubKey.Address()
    for _, utxo := range tx.Inputs {
        if c.utxoset.Contains(addr, utxo) == false {
            return fmt.Errorf("invalid inputs")
        }
        funds += c.fundsFromUTXO(utxo)
    }
    for i := range tx.Tokens {
        output += tx.Tokens[i]
    }
    if funds < output {
        return fmt.Errorf("not enough funds: %v < %v", funds, output)
    }
    return nil
}

Transazioni

Per evitare il double spending, sono previste le seguenti limitazioni:

• Un pagamento può essere accettato con sicurezza dopo circa 6 blocchi
• Per gli UTXO di una coinbase bisogna aspettare 100 blocchi (per protocollo)

2. Smart Contracts

Smart Contracts

Il termine Smart Contract viene introdotto da Nick Szabo nel 1996

Szabo descrive la possibilità di creare contratti tra estranei con la mediazione di protocolli software e l'aiuto di tecniche crittografiche

Questi contratti devono possedere:

• observability
• verifiability
• privity
• enforceability

Smart Contract

• È un programma
• Agisce all'interno di un protocollo con garanzie simili a quelle di un distributed ledger

Possiamo usare la blockchain?

Bitcoin scripting

In effetti abbiamo semplificato un po', la verifica delle transazioni è un po' più sofisticata

Ad una transazione è associato un lucchetto digitale sotto forma di programma

• il programma è eseguito da tutti i nodi
• se il programma, con un dato input, è valutato a true la transazione è sbloccata

Bitcoin VM

Ogni nodo esegue una VM

• macchina a stack
• isolata dall'host
• interpreta bytecode
• non Turing-completa

Un transazione viene effettuata tramite l'esecuzione di uno script

Bitcoin VM

Sketch di funzionamento della VM:

for {
    input := nextInput()
    if input.isEOF() {
       return stack.pop()
    }
    if input.isData() {
        stack.push(input.Data())
        continue
    }
    switch input.OPCode() {
    case OP_DUP:
        v := stack.pop()
        stack.push(v)
        stack.push(v)
    ...
    }
}

Script

Gli script per Bitcoin sono un'espressione RPN della forma:

[ DATO... ] [ DATO | OPCODE ]...
   input       programma

• predicato logico che permette l'utilizzo degli UTXO

• il più comune per le transazioni è Pay to Public Key Hash (P2PKH)

P2PKH

Scenario: Alice vuole pagare Bob

• Alice crea una transazione con script P2PKH:

OP_DUP OP_HASH160 $hash_pubkey_bob OP_EQUAL OP_VERIFY OP_CHECKSIG

Scenario: Bob vuole spendere i bitcoin ricevuti di Alice

• Bob crea una transazione con input gli UTXO creati dalla transazione di Alice
• Bob aggiunge alla transazione la sua chiave pubblica e firma la transazione
• I nodi eseguono lo script di Alice con gli input di Bob:

$signature_bob $pubkey_bob OP_DUP OP_HASH160 $hash_pubkey_bob OP_EQUAL OP_VERIFY OP_CHECKSIG

Se il risultato è true la transazione può essere confermata

Script alternativi

• M-of-N Multi Signature:

$m $pubkey_1 ... $pubkey_n $n OP_CHECKMULTISIG

• Sblocco mediante token privato:

OP_SHA256 OP_SHA256 $given_hash EQUAL

• Transazioni con vincoli temporali:

$expire_value OP_CHECKLOCKTIMEVERIFY OP_DROP

• Regalare bitcoin:

OP_TRUE

• Bruciare bitcoin:

OP_RETURN

Limitazioni

Gli Smart Contract su bitcoin non sembrano poi così "smart"

• Limitazioni di calcolabilità
• Mancanza di stato
• Blockchain-blindness

Ethereum

Ethereum

A Next-Generation Smart Contract and Decentralized Application Platform

Idea: Sfruttare la tecnologia della blockchain e generalizzarla

Non piattaforma che esegue contratti per potere scambiare valuta digitale
Ma una macchina distribuita per contratti arbitrari

Una sorta di blockchain universale (ERC20)

Accounts

Non ci sono UTXO

Ad un account Ethereum è invece associato uno stato:

• nonce
• saldo
• storage
• codice

Un transazione corrisponde ad un cambio di stato

Accounts

Esistono due tipi di account

Esterni

• Analoghi agli indirizzi bitcoin

Contratti

• possono effettuare transazioni solo in risposta a tx ricevute
• possono interagire con altri contratti
• devono essere creati con una tx particolare

Indirizzo

160 bit meno significativi dell'hash della chiave pubblica

indirizzo = SHA-3(pubKey) & (1<<160) - 1

Esempio: 0x627306090abaB3A6e1400e9345bC60c78a8BEf57

• No checksum
• Indipendente dal tipo di account

EVM

La EVM va a benzina (gas), in questo modo è possibile avere un upper bound per un dato programma

Un cambio di stato consuma gas

Per ogni tx bisogna specificare:

• Gas Limit: la massima quantità di benzina che si è disposti a comprare
• Gas Price: il prezzo a cui si è disposti a comprare un unità di gas

Se la benzina è sufficiente per la tx, l'eventuale avanzo viene rimborsato
Altrimenti la transazione è annullata (lo stato non cambia)

I costi di commissione sono il prodotto tra il gas consumato e il prezzo proposto

ether

Ethereum ha una moneta nativa: ether

Protocollo → Ethereum
Moneta → ether (ETH)

La blockchain di Ethereum non esiste per supportare la moneta, ma il contrario

Gli ether sono il meccanismo per regolare le risorse

• l'ether ha come più piccolo sottomultiplo il wei (10e-18 ETH)

• Il prezzo del gas è solitamente riportato in wei o Gwei

Solidity

Il linguaggio "contract-oriented" per lo sviluppo di Smart Contract su Ethereum

• sintassi "ispirata" a javascript
• staticamente tipato
• non ideato da esperti di linguaggi programmazione

Solidity

Does anybody remember DAO?

Alcuni problemi di design:

• tutto di default è mutabile
• nessun check a compile time delle annotazioni
• operazioni su interi non sono sicure (overflow)
• la gestione interi a virgola fissa è incompleta
• l'ordine di valutazione delle espressioni non è definita

In generale sono problemi ben affrontati in letteratura e molti risolti in linguaggi general purpose

Solidity

contract Voting {
  mapping (bytes32 => uint8) public votes;
  mapping (bytes32 => bool) public validCandidates;
  
  function Voting(bytes32[] candidates) public {
    for (uint i=0; i<candidates.length; i++) {
       validCandidates[candidates[i]] = true;
    }
  }

  function totalVotesFor(bytes32 candidate) view public returns (uint8) {
    require(isValid(candidate));
    return votes[candidate];
  }

  function voteFor(bytes32 candidate) public {
    require(isValid(candidate));
    votes[candidate] += 1;
  }

  function isValid(bytes32 candidate) view public returns (bool) {
     return validCandidates[candidate];
  }
}

Compilazione contratto

const fs = require('fs');
const solc = require('solc'); // npm install solc

module.exports = {
    compile: function(path, klass) {
        return new Promise((resolve, reject) => {
            fs.readFile(path, (err, data) => {
                if (err) {
                    return reject(err);
                }
                const output = solc.compile(data.toString());
                const compiledContract = output.contracts[`:${klass}`];
                if (compiledContract === undefined) {
                    return reject(`no contract class "${klass}" in "${path}"`);
                }
                resolve({
                    abi: compiledContract.interface,
                    bytecode: compiledContract.bytecode
                });
            });
        });
    }
};

Deploy sulla blockchain

const Web3 = require('web3');
const cc = require('./compile');
const provider = new Web3.providers.HttpProvider('http://localhost:7545')
const contractOwner = '0x627306090abaB3A6e1400e9345bC60c78a8BEf57';
const candidates = ['Zaphod Beeblebrox', 'Foobar', 'Qux'];

cc.compile('../sol/voting.sol', 'Voting').then(data => {
    const {abi, bytecode} = data;
    const web3 = new Web3(provider);
    const contract = new web3.eth.Contract(JSON.parse(abi));
    return contract.deploy({
        data: bytecode,
        arguments: [ candidates.map(Web3.utils.fromAscii) ]
    }).send({
        from: contractOwner,
        gas: 900000,
        gasPrice: '20000000000' // wei
    });
}).then(receipt => {
    /* ... */
}).catch(err => {
    /* ... */
});

Ganache

github.com/trufflesuite/ganache

Voting DAPP

Conclusioni

Bitcoin

• fondamentale dal punto di vista storico
• aiuta a definire i concetti generali della tecnologia

Ethereum

• focus sulla parte computativa
• piattaforma su cui poter sviluppare nuove idee

Ulteriori argomenti da approfondire:

• Token ERC721
• Off-chain Oracles

Thank you