what is a ledger?
account holder balance
alice 100
bob 200
carol 300
dan 400
let’s start with a table of account balances
not actually a ledger
5
a ledger records transactions
debit account credit account amount
initial deposit alice 100
initial deposit bob 200
initial deposit carol 300
initial deposit dan 400
this is now a ledger
6
now suppose bob pays alice ₿100
debit account credit account amount
initial deposit alice 100
initial deposit bob 200
initial deposit carol 300
initial deposit dan 400
bob alice 100
7
and alice pays carol ₿125
debit account credit account amount
initial deposit alice 100
initial deposit bob 200
initial deposit carol 300
initial deposit dan 400
bob alice 100
alice carol 125
8
and so on ..
debit account credit account amount
initial deposit alice 100
initial deposit bob 200
initial depositall transactions
carol are recorded 300
initial deposit by appending
dan to the ledger 400
bob alice 100
alice carol 125
… … …
9
ledger to account balances?
sender receiver amount
initial deposit alice 100
initial deposit bob 200
initial deposit carol 300
initial deposit dan 400
bob alice 100
alice carol 125
account amount
alice 100+100-125=75
bob 200-100=100
carol 300+125=425
dan 400
10
but not all transactions are valid
sender receiver amount account amount
initial deposit alice 100
alice 75
initial deposit bob 200
bob 100
initial deposit carol 300
initial deposit dan 400
carol 425
bob alice 100 dan 400
alice carol 125
bob dan 200
bob doesn’t have ₿200
in his account
11
definition: transaction validity (v1)
transaction valid if sender’s balance is >= amount being sent
to receiver
12
definition: ledger validity (v1)
ledger valid if all transactions in it are valid
that is, every sender has the appropriate balance to conduct
every transaction
13
blockchain: ledger of transactions
tx1 tx2 tx3 tx4 tx5 tx6 …
monday’s txns tuesday’s txns wednesday’s txns
• each block has txns from specific time period
• blockchain = linked list of blocks
14
let’s see some code
class txn_t {
account_t sender;
account_t receiver; …
uint64_t amount;
};
class block_t {
std::vector<txn_t*> txns;
block_t* prev_block;
};
std::list<block_t*> blockchain;
15
std::vector<T>: resizeable array
• insertion
vec.push_back(elem); • resize to have n elements:
vec.resize(n);
• size
vec.size() • delete all elems and set size = 0
vec.clear();
• element access
vec[i] = blah; • iteration
for (auto elem : vec) {
• access to raw array inside // do s’th with elem;
vec.data() }
16
std::list<T>: linked list
• iteration (v1):
• insertion for (auto p = lst.begin();
lst.push_back(elem); p != lst.end(); p++)
{
• size // do s’th with *p;
}
lst.size()
• iteration (v2)
• delete all elems and set size = 0 for (auto elem : vec) {
lst.clear(); // do s’th with elem;
}
17
in modern c++ (c++’11 and c++’14)
class txn_t {
account_t sender;
…
account_t receiver;
uint64_t amount;
};
class block_t {
std::vector<std::shared_ptr<txn_t> > txns;
std::shared_ptr<block_t> prev_block;
};
std::list<std::shared_ptr<block_t> > blockchain;
18
use smart pointers
std::shared_ptr<T> is a reference counted smart pointer
creation:
• shared_ptr<block_t> ptr(new block_t(…));
deletion:
• do nothing! auto deleted when out of scope
access:
• ptr->member (just like a pointer)
copying:
• shared_ptr<block_t> ptr2 = ptr;
19
blockchain validation code (v1)
bool validate(list<shared_ptr<block_t> >& blockchain) {
balances.clear();
for (auto blk : blockchain) { iterate over
for (auto tx : blk.txns) { each transaction
if (tx.sender == INIT_DEPOSIT ||
balances[tx.sender] >= tx.amount) check balance
{
balances[tx.sender] -= tx.amount; update balances
balances[tx.receiver] += tx.amount;
} else {
return false;
}
}
}
return true;
}
20
unordered_map<K,V>: hashtable
• iteration:
• insertion for (auto p = m.begin();
p != m.end(); p++)
m [key] = elem; {
// use p.first (key)
• size // and p.second (val)
m.size() }
• delete all elems and set • search
auto p = m.find(k);
size = 0 // returns m.end() or can
m.clear(); // use p.first, p.second
21
set<T>: set of elements
• iteration:
• insertion for (auto p = m.begin();
m.insert(elem) p != m.end(); p++)
{
• size // use *p or p->fld;
}
m.size()
• search
• delete all elems and set auto p = m.find(elm);
size = 0 // returns m.end() or can
// use *p or p->fld
m.clear();
22
but we said that
a blockchain is a ledger of transactions
that is verifiable and permanent
23
verifiability problem #1: repudiation
sender receiver amount
initial deposit alice 100 hey SBI, I
initial deposit bob 200 never paid
initial deposit carol 300 dan ₿100!
initial deposit dan 400
bob alice 100
alice carol 125
carol dan 100
dan alice 50
alice bob 25
bob dan 75
24
solution in today’s banks?
yes, you did!
hey SBI, I here is your
never paid signature
TS ₹6493!
25
in blockchains: digital signatures
alice’s private key
alice pays
sign signature
dan ₿100
verify
alice’s public key
26
in blockchains: digital signatures
bob’s private key
alice pays
sign signature
dan ₿100
verify
alice’s public key
nobody else can forge signature without alice’s private key
27
in blockchains: digital signatures
alice’s private key
alice pays
sign signature
dan ₿100
alice pays
verify
dan ₿200
alice’s public key
verification will fail if the message is changed
28
a non-repudiable ledger
sender receiver amount digital signature
initial deposit alice 100 0xFAD10A8DC
initial deposit bob 200 0xBA2DC311C
initial deposit carol 300 0x122938FAA1
initial deposit dan 400 0x71123FFCB1
bob alice 100 0x4801FFC3D1
alice carol 125 0x8182830ABC
carol dan 100 0xD1382C0124
dan alice 50 0xFF14285714
alice bob 25 0x91984B7521
bob dan 75 0xBB0B304512
29
definition: transaction validity (v2)
transaction is valid if
• sender’s balance is >= the amount being
sent to receiver and
• and tx signature validation with sender’s
public key succeeds
30
code for verifying signatures
rsa_public_key_t pubkey(
DEREncodedKey.data(),
DEREncodedKey.size());
bool success = pubKey.verify(
(const uint8_t*) msg.data(), msg.size(),
signature.data(), signature.size());
31
what’s the problem with the scheme?
where will the public keys come from?
what if bank maintains them?
• bank will be able to forge sign (how?)
32
solution: tie a/c nos. and pubkeys
all account numbers = hash(public key)
• customer chooses a/c no based on priv/pub keypair
• provides this account number to the bank
• transactions are signed using corresponding privkey
33
what is a cryptographic hash fn?
space of
messages
hashes (fixed
with
size digests)
arbitrary
sizes
a mapping from arbitrary bytes to some
fixed size (typically 16/32byte) digest
34
properties of crypto hash functions
space of hashes (fixed
messages size digests)
pre-image resistance
• can’t find message given a hash
collision resistance
• if two messages are different, very likely hashes are
different
35
blockchain transactions
send pubkey send addr recv addr amt digital signature
0xFFA1288… 0x18471C… 0x13831… 100 0xFAD10A8DC
… … … … …
… … … … …
a/c numbers are hashes of public keys
• from now on, we will call a/c nos. as addresses
public key is included in the transaction
• question: why not just use public keys as addresses?
36
problem: replay attacks
# send pubkey send addr recv addr amt digital signature
1 0xFFA1288… 0x18471C… 0x13831… 100 0xFAD10A8DC
2 0x98B5B33.. 0x13831… 0x32112… 50 0xD1ABC31A6
3 … … … … …
4 … … … … …
• after tx #1, 0x13831… has (at least) ₿100
• she spends some of this by giving 0x32112… ₿50
so what is the problem?
37
problem: replay attacks
# send pubkey send addr recv addr amt digital signature
1 0xFFA1288… 0x18471C… 0x13831… 100 0xFAD10A8DC
2 0x98B5B33.. 0x13831… 0x32112… 50 0xD1ABC31A6
3 0x98B5B33.. 0x13831… 0x32112… 50 0xD1ABC31A6
4 … … … … …
• after tx #1, 0x13831… has (at least) ₿100
• she spends some of this by giving 0x32112… ₿50
so what is the problem?
• 0x32112 can replay the txn and get ₿50 again!
38
what’s the fix?
send pubkey send addr recv addr change amt digital signature
addr
0xFFA1288… 0x18471C… 0x13831… 0x4AC1.. 100 0xFAD10A8..
0x98B5B33… 0x13831… 0x32112… 0xD1A2… 50 0x98B5B33..
… … … … …
• create a new address to send “change” (remaining
balance) with each transaction
• after tx 2:
0x13831 has ₿0; 0x32112 has ₿50; 0xD1A2 has ₿50
39
one last minor detail
send pubkey send recv change amt tx hash digital
addr addr addr signature
0xFFA1288… 0x18471 0x13831 0xB11A 100 0x331A… 0xFAD10A8DC
C… … …
… … … … …
… … … … …
• tx hash = hash(pubkey, send addr, recv addr, change
addr, amt)
• tx sign = sign(tx hash, privkey)
the hash is needed for certain technical reasons in bitcoin
40
final transaction structure
class txn_t {
vector<uint8_t> public_key;
hash_result_t source_addr;
hash_result_t dest_addr;
hash_result_t change_addr;
uint64_t amount;
hash_result_t tx_hash;
vector<uint8_t> tx_sign;
};
41
definition: transaction validity (v3)
send pubkey send addr recv addr amt tx hash digital signature
0xFFA1288… 0x18471C 0x13831… 100 0x331A… 0xFAD10A8DC
…
… … … … …
… … … … …
your first task is to implement these two checks in transaction.cpp
1. tx hash == hash(pubkey, send addr, recv addr,
change addr, amt)
2. pubkey.verify(tx hash, tx sign) == 1
3. send addr (sender’s account) must have enough
balance
42
code for computing hashes
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, public_key.data(), public_key.size());
SHA256_Update(&sha256, source_addr.data(), source_addr.size());
SHA256_Update(&sha256, dest_addr.data(), dest_addr.size());
SHA256_Update(&sha256, change_addr.data(), change_addr.size());
SHA256_Update(&sha256, &amount, sizeof(amount));
SHA256_Final(tx_hash.data(), &sha256);
tx_hash = SHA256(public_key, source_addr, dest_addr, change_addr, amount)
43
back to the blockchain
a blockchain is a ledger of transactions
that is verifiable and permanent
44
permanence via public distribution
tx1 tx2 tx3 tx4 tx5 tx6 …
alice
tx1 tx2 tx3 tx4 tx5 tx6 …
bob
tx1 tx2 tx3 tx4 tx5 tx6 …
carol
tx1 tx2 tx3 tx4 tx5 tx6 …
dan
• all participants in the blockchain have a copy of it
• so every transaction is broadcast to everyone
• need a consensus algorithm to make sure everyone sees the
same state when multiple people are using but we won’t go
into this part
45
but now we have a problem
…
class block_t {
vector<shared_ptr<txn_t> > txns;
shared_ptr<block_t> prev_block;
};
how do we maintain prev_block pointers across
different machines?
46
solution: hash pointers
prev prev prev
0 hash hash hash
• pointers refer to hashes of the data they point to
• not memory addresses
47
finally, where do bitcoins come from?
new bitcoins are created with each block
• reason has to do with the consensus operation
newly created bitcoins go to a “reward” address
• think of it as someone getting paid for taking the trouble of
maintaining the ledger
• this payment is called a “block reward”
48
final block structure
class block_t {
vector<shared_ptr<txn_t> > transactions;
hash_result_t reward_addr;
hash_result_t prev_hash;
shared_ptr<block_t> prev_ptr; // why?
};
49
your tasks
• review code in cryptotest.cpp to see use of API functions
• implement txn_t::validate() [50 pts]
• (challenge) implement block_t::validate() [30 pts]
• (challenge) fix perf. bug in txn_t::update_balances [20]
git@git.cse.iitk.ac.in:spramod/bootcamp-day1.git
50
task #1: txn_t::validate()
write code for the following checks:
1. send addr == hash(pubkey)
2. tx hash == hash(pubkey, send addr, recv addr, change addr, amt)
3. pubkey.verify(tx hash, tx sign) = 1
51
task #2: block_t::validate()
write code for the following checks:
1. check each transactions validate() returns true
2. update the balances after each valid transaction
• call txn_t::update_balances for this
3. check blk_hash == hash(tx1->tx_hash, tx2->tx_hash, … , txn-
>tx_hash, reward_addr, prev_hash)
4. Add the block reward to the balances
52
testing your code
• have given three tests cases: tests/t1.dat, t2.dat and t3.dat
• expected output is in tests/t1.txt, t2.txt and t3.txt
• will release three more after lunch
• scoring is based on correctness (correct output) and speed
53
Outline of blockchain.h
class block_t {
private:
bool valid;
balance_map_t balances;
public:
unsigned length;
block_t();
block_t(std::shared_ptr<block_t> prev_block);
hash_result_t reward_addr;
std::vector< std::shared_ptr<txn_t> > transactions;
hash_result_t prev_hash;
hash_result_t blk_hash;
std::shared_ptr<block_t> prev_block; ….
Outline of transactions.h
typedef std::map<hash_result_t, uint64_t> balance_map_t;
struct txn_t {
uint8_vector_t public_key;
hash_result_t source_addr;
hash_result_t dest_addr;
hash_result_t change_addr;
uint64_t amount;
hash_result_t tx_hash;
uint8_vector_t tx_sign;
bool valid;
……
Outline of crypto.h
typedef std::vector<uint8_t> uint8_vector_t;
class hash_result_t {
uint8_t bytes[SHA256_DIGEST_LENGTH];
public:
static const int SIZE;
hash_result_t();
hash_result_t(uint8_t bytesIn[SHA256_DIGEST_LENGTH]);
hash_result_t(const hash_result_t& other);
void set_hash_from_data(const uint8_vector_t& data);
void set_hash_from_data(const uint8_t* data, size_t sz);
hash_result_t& operator=(const hash_result_t& other) {
std::copy(other.bytes, other.bytes + size(), bytes);
return *this;
}
bool operator==(const hash_result_t& other) const;
bool operator!=(const hash_result_t& other) const { return !(*this == other); }
bool operator<(const hash_result_t& other) const;
uint8_t& operator[](unsigned i);
Creating coinbase Block & Regular Block
block_t::block_t()
: valid(false)
, length(1)
, prev_block(NULL)
{
reset_balances();
}
block_t::block_t(std::shared_ptr<block_t> prev)
: valid(false)
, length(prev->length + 1)
, prev_hash(prev->blk_hash)
, prev_block(prev)
{
reset_balances();
}
Steps you need to do
• Download Ubuntu 18.04 from ubuntu site if you are already not using
ubuntu
• If you do not want your machine to be dual-booted, install Vbox from
oracle and use virtual machine to run Ubuntu
• When you get into ubuntu, please clone openressl library from github
https://github.com/libressl-portable/portable
• Use sudo apt-get install for the followings libboost-dev, automake,
autoconf, git, libtool, perl, g++
• After you have installed the above, you have to follow the instructions in
README.md that is in the directory portable-manager to build and install
this library
• This is the SSL and Crypto library that you will need to do all the crypto
functions required
Steps (2)
• Then download the code for blockchain exercise – and follow the
README.md file within the src directory to build it
• You will need to then write the functions required for the homework.
