Blockchain Theory Text

Blockchain.bib

@article{satoshi,
	title = {Bitcoin: A peer-to-peer electronic cash system},
	url = {http://www.cryptovest.co.uk/resources/Bitcoin%20paper%20Original.pdf},
	shorttitle = {Bitcoin},
	author = {Nakamoto, Satoshi},
	urldate = {2017-02-01},
	date = {2008},
	file = {[PDF] cryptovest.co.uk:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/JRRGC7JA/Nakamoto - 2008 - Bitcoin A peer-to-peer electronic cash system.pdf:application/pdf}
}

@thesis{konst,
	title = {Sichere Log-Dateien auf Grundlage kryptographisch verketteter Einträge},
	url = {http://www.iti.cs.tu-bs.de/TI-INFO/waetjen/Diplomarbeiten/Konst.pdf},
	institution = {Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig},
	type = {phdthesis},
	author = {Konst, Stefan},
	urldate = {2017-02-01},
	date = {2000},
	file = {[PDF] tu-bs.de:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/RP7BK9B7/Konst - 2000 - Sichere Log-Dateien auf Grundlage kryptographisch .pdf:application/pdf}
}

@article{pilkington,
	title = {Blockchain technology: principles and applications},
	url = {https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2728593},
	shorttitle = {Blockchain technology},
	journaltitle = {Browser Download This Paper},
	author = {Pilkington, Marc},
	urldate = {2017-02-01},
	date = {2015},
	file = {[PDF] sysu.edu.cn:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/86ASR8JZ/Pilkington - 2015 - Blockchain technology principles and applications.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/HCAKK48R/Papers.html:text/html}
}

@article{lamport,
	title = {The Byzantine generals problem},
	volume = {4},
	url = {http://dl.acm.org/citation.cfm?id=357176},
	pages = {382--401},
	number = {3},
	journaltitle = {{ACM} Transactions on Programming Languages and Systems ({TOPLAS})},
	author = {Lamport, Leslie and Shostak, Robert and Pease, Marshall},
	urldate = {2017-02-01},
	date = {1982},
	file = {[PDF] uchicago.edu:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/BD2H86EK/Lamport et al. - 1982 - The Byzantine generals problem.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/9NRJ784C/citation.html:text/html}
}

@article{baran,
	title = {On distributed communications networks},
	volume = {12},
	url = {http://ieeexplore.ieee.org/abstract/document/1088883/},
	pages = {1--9},
	number = {1},
	journaltitle = {{IEEE} transactions on Communications Systems},
	author = {Baran, Paul},
	urldate = {2017-02-01},
	date = {1964},
	file = {Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/RTSPUAGA/1088883.html:text/html}
}

@inproceedings{chaum,
	title = {Untraceable electronic cash},
	url = {http://dl.acm.org/citation.cfm?id=88969},
	pages = {319--327},
	booktitle = {Proceedings on Advances in cryptology},
	publisher = {Springer-Verlag New York, Inc.},
	author = {Chaum, David and Fiat, Amos and Naor, Moni},
	urldate = {2017-02-01},
	date = {1990},
	file = {[PDF] nccu.edu.tw:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/Z8BRAIRB/Chaum et al. - 1990 - Untraceable electronic cash.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/USWRE75S/citation.html:text/html}
}

@inproceedings{naor,
	title = {Universal one-way hash functions and their cryptographic applications},
	url = {http://dl.acm.org/citation.cfm?id=73011},
	pages = {33--43},
	booktitle = {Proceedings of the twenty-first annual {ACM} symposium on Theory of computing},
	publisher = {{ACM}},
	author = {Naor, Moni and Yung, Moti},
	urldate = {2017-02-01},
	date = {1989},
	file = {[PDF] psu.edu:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/IXBGG52S/Naor and Yung - 1989 - Universal one-way hash functions and their cryptog.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/C42K8EFV/citation.html:text/html}
}

@article{sha_standard,
	title = {{FIPS} {PUB} 180-2},
	url = {http://downloads.german-pavilion.com/downloads/pdf/exhibitor_16210.pdf},
	journaltitle = {National Institute of Standards and Technology},
	author = {Standard, Secure Hash},
	urldate = {2017-02-01},
	date = {2002},
	file = {Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/4G9PJD8G/exhibitor_16210.pdf:application/pdf}
}

@inproceedings{dobraunig,
	title = {Analysis of {SHA}-512/224 and {SHA}-512/256},
	rights = {©2015 International Association for Cryptologc Research},
	isbn = {978-3-662-48799-0 978-3-662-48800-3},
	url = {http://link.springer.com/chapter/10.1007/978-3-662-48800-3_25},
	series = {Lecture Notes in Computer Science},
	abstract = {In 2012, {NIST} standardized {SHA}-512/224 and {SHA}-512/256, two truncated variants of {SHA}-512, in {FIPS} 180-4. These two hash functions are faster than {SHA}-224 and {SHA}-256 on 64-bit platforms, while maintaining the same hash size and claimed security level. So far, no third-party analysis of {SHA}-512/224 or {SHA}-512/256 has been published. In this work, we examine the collision resistance of step-reduced versions of {SHA}-512/224 and {SHA}-512/256 by using differential cryptanalysis in combination with sophisticated search tools. We are able to generate practical examples of free-start collisions for 44-step {SHA}-512/224 and 43-step {SHA}-512/256. Thus, the truncation performed by these variants on their larger state allows us to attack several more rounds compared to the untruncated family members. In addition, we improve upon the best published collisions for 24-step {SHA}-512 and present practical collisions for 27 steps of {SHA}-512/224, {SHA}-512/256, and {SHA}-512.},
	eventtitle = {International Conference on the Theory and Application of Cryptology and Information Security},
	pages = {612--630},
	booktitle = {Advances in Cryptology – {ASIACRYPT} 2015},
	publisher = {Springer Berlin Heidelberg},
	author = {Dobraunig, Christoph and Eichlseder, Maria and Mendel, Florian},
	editor = {Iwata, Tetsu and Cheon, Jung Hee},
	urldate = {2017-02-01},
	date = {2014-12-07},
	langid = {english},
	note = {{DOI}: 10.1007/978-3-662-48800-3\_25},
	keywords = {Coding and Information Theory, Collisions, Cryptanalysis, Data Encryption, Free-start collisions, Hash functions, Management of Computing and Information Systems, Mathematics of Computing, {SHA}-2, {SHA}-512, {SHA}-512/224, {SHA}-512/256, Systems and Data Security, Theory of Computation},
	file = {Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/MVCTXM9F/978-3-662-48800-3_25.html:text/html}
}

@inproceedings{merkle,
	title = {Protocols for public key cryptosystems},
	url = {http://ieeexplore.ieee.org/abstract/document/6233691/},
	pages = {122--122},
	booktitle = {Security and Privacy, 1980 {IEEE} Symposium on},
	publisher = {{IEEE}},
	author = {Merkle, Ralph C.},
	urldate = {2017-02-01},
	date = {1980},
	file = {[PDF] semanticscholar.org:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/9FKX688Q/Merkle - 1980 - Protocols for public key cryptosystems.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/8NXUDHJX/6233691.html:text/html}
}

@inproceedings{barber,
	title = {Bitter to better—how to make bitcoin a better currency},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-32946-3_29},
	pages = {399--414},
	booktitle = {International Conference on Financial Cryptography and Data Security},
	publisher = {Springer},
	author = {Barber, Simon and Boyen, Xavier and Shi, Elaine and Uzun, Ersin},
	urldate = {2017-02-01},
	date = {2012},
	file = {[PDF] qut.edu.au:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/E2WIV5K4/Barber et al. - 2012 - Bitter to better—how to make bitcoin a better curr.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/6UAIIRFM/978-3-642-32946-3_29.html:text/html}
}

@inproceedings{bonneau,
	title = {Sok: Research perspectives and challenges for bitcoin and cryptocurrencies},
	url = {http://ieeexplore.ieee.org/abstract/document/7163021/},
	shorttitle = {Sok},
	pages = {104--121},
	booktitle = {Security and Privacy ({SP}), 2015 {IEEE} Symposium on},
	publisher = {{IEEE}},
	author = {Bonneau, Joseph and Miller, Andrew and Clark, Jeremy and Narayanan, Arvind and Kroll, Joshua A. and Felten, Edward W.},
	urldate = {2017-02-01},
	date = {2015},
	file = {[PDF] ieee-security.org:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/BMW6KXJX/Bonneau et al. - 2015 - Sok Research perspectives and challenges for bitc.pdf:application/pdf;Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/72QJCR8M/7163021.html:text/html}
}

@online{cohen,
	title = {Global Bitcoin Computing Power Now 256 Times Faster Than Top 500 Supercomputers, Combined!},
	url = {http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/},
	abstract = {I admit, like a lot of others, I’ve found myself with a bit of a bitcoin obsession lately. I find the vast amount of effort it takes to create something that doesn’t actually exist, completely fascinating. So I decided to find out how much computing power is exerted in the [...]},
	titleaddon = {Forbes},
	author = {Cohen, Reuven},
	urldate = {2017-02-01},
	file = {Snapshot:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/UBHCKJMG/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined.html:text/html}
}

@online{crypto_mining_blog,
	title = {The Size of the Bitcoin Blockchain Data Files Has Reached 60GB - Crypto Mining Blog},
	url = {http://cryptomining-blog.com/6397-the-size-of-the-bitcoin-blockchain-data-files-has-reached-60gb/},
	author = {{Crypto Mining Blog}},
	urldate = {2017-02-02},
	file = {The Size of the Bitcoin Blockchain Data Files Has Reached 60GB - Crypto Mining Blog:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/25EWC9JD/6397-the-size-of-the-bitcoin-blockchain-data-files-has-reached-60gb.html:text/html}
}

@article{king_ppcoin,
	title = {Ppcoin: Peer-to-peer crypto-currency with proof-of-stake},
	volume = {19},
	url = {http://peerco.in/assets/paper/peercoin-paper.pdf},
	shorttitle = {Ppcoin},
	journaltitle = {self-published paper, August},
	author = {King, Sunny and Nadal, Scott},
	urldate = {2017-02-02},
	date = {2012},
	file = {[PDF] peerco.in:/home/max/.mozilla/firefox/jeyuln4l.default/zotero/storage/NJ36ID78/King and Nadal - 2012 - Ppcoin Peer-to-peer crypto-currency with proof-of.pdf:application/pdf}
}

blockchain.tex

\section{Principles of Blockchain}
%% MOTIVATION
In order to understand the principles underlying blockchain technology, a
description of the problems being approached is certainly helpful.
At its core the blockchain apprends to solve a problem of consensus information
inside a network, where its individual participants, can not trust the other
participants.
This description is similar to the
\emph{Byzantine generals problem}~\cite{lamport}, where a positive consensus
outcome is hindered by the existence of \emph{traitors} trying to provoke a
negative outcome. Since the loyal generals have no way to know of the traitors,
other approaches have to be devised to optimize their outcomes.

The problem of generating consensus inside a network, can be straightforwardly
solved by introducing a \emph{central authority} confirming the veracity of the
distributed information. This is leaves a major attack point for tampering with
the network. 

By introducing hierarchical layers into the network, we can create a
\emph{decentralized network}, consisting of node-aggregations, which are then
connected on a wider scale with each other. These systems might introduce some
resilience to outages, but are still vulnerable to defects rising with its
grade in the hierarchy.

Removing hierarchy, whilst leaving a more even interconnection of node can lead
us to a \emph{distributed system}, where no single node has greater importance
than another. Single points of failure can thus be eliminated and the robustness
of the network is just dependent on the average number of interconnections
between the individual nodes.

The theoretical implications of these network problems have been studied before
from a telecommunications perspective.~\cite{baran}
They can be applied to a wide range of fields, where authencity of information
is of utmost value, but other participants can not necessesarily be trusted.

This commonly applies to currency, where a single central authority in form of a
national bank is commonly used, to control the integrity of the circulated
currency. Such a national bank is prone to manipulation and failure, which can
be dramatically observed in times of economic and politic instability.
The essential properties a currency system has to provide to its users is the
ability to record the amount each participant owns at every point in time. These
amounts can change with transactions between the participants in the network.
In order to avoid malicious tampering, the system has to agree on single state
at each point of tiem, so that all information inside the system is accounted
for. If this is not guaranteed, \emph{double spending} can occur.~\cite{chaum}
Whilst it is hard to imagine spending the same money twice, this is not
impossible in digital systems where copies can be generated at virtually no cost
at all. To prevent this, a robust mechanism for generating consensus is needed.

%% IMPLEMENTATION
The most prominent and earliest working solution of a blockchain system is
\emph{Bitcoin} by Nakamoto.~\cite{satoshi} Blockchains save data inside blocks,
which are connected to previous blocks spanning continuously back to the first
block.
Bitcoin avoids the requirement of a centralized authority overseeing
transactions, by accepting whichever chain of data is currently the longest.
Every participant is able to generate new blocks into the system, of
which the fastest one is incorporated into the system.
The data is saved in a consecutive chain of blocks, which are cryptographically
hashed with SHA-256. Each new block is hashed, containing information of the
preceding block. The hash function generates from the output a fixed length
string, which can be greatly altered even with small adjustments of the input
values. Since all inputs map to a fixed length string, multiple inputs can map
to a single hash. These collisions also mean, that one can not arrive at the
original input from the hash with perfect certainty and only with a high
performance penalty.~\cite{naor}
The hashing algorithm used by Bitcoin is SHA256, which is the SHA-2 algorithm
variant, producing an output size of 256bit.~\cite{sha_standard} This algorithm
standard has been published by the National Security Agency of the United States
of America and is considered to be secure.~\cite{dobraunig}

Only the header of the block is directly hashed as part of the blockchain. It
contains the hash of the previous block. Thus ensuring that our hash has to be
based on currently available information, preventing a pre-generation of
possible hashes. This hashing feature has been termed by Nakamoto as a
\emph{timestamp system}, ensuring that the block has been generated at least
after a certain time, similar to ``including newspaper or usenet
articles''~\cite{satoshi}.
Thereafter the header contains the merkle root hash. The transaction data in a
single block is saved inside a merkle tree.~\cite{merkle} This is a tree-like
structure, where the labels for the nodes are generated by concatenating the
hashes of its children and again hashing it. This is commonly realized as a
binary merkle tree, where each node only has two children. The integrity of a
merkel tree can be confirmed by each client by rehashing the values of all
elements, if the tree is intact, the client should arrive at the given merkle
root hash. All information on the whereabouts of currency is saved in individual
transactions, which are encrypted with Private-Public-Key Cryptography.
A bitcoin wallet, is thus simply a collection of private keys, with which a
certain number of transactions to this address can be accessed.
In order to realize the transfer of batches of currency, the transaction can
accept multiple outputs and inputs.
The header also contains a UNIX epoch time, marking the
time, when the miner has started to generate this certain hash, and a number
encoding the hardness of the problem to be solved. The header ends with a
\emph{nonce sequence} of 32bits, which can be procedurally changed by the miner,
as it tries to generate the correct hash to be accepted into the blockchain.

The process of generating new blocks, containing new transactions, and adding
them to the chain, is commonly called \emph{mining}. Since the system accepts
the longest chain published on the network, an attacker might simply try to
generate a large amount of blocks in a short time to try to overwhelm the
system. This is counteracted by introducing computational difficulty into the
process of block generation, called \emph{proof of work}. Bitcoin requires a
certain number of zeros preceding the generated hash for a block. Miners are
rewarded for completing this computational intensive task by the ability to
generate a certain number of bitcoin into the system, called \emph{coinbase},
and the collection of transaction fees of all transactions incorporated into the
processed block. Because of the one-way nature of the hashing function, many
different headers have to be tried by incrementing the nonce value, before the
miner can possibly arrive at a possible solution. If the 32bit range of nonce is
exhasted, other properties, such as the mining reward transaction can be
modified. Since the address of the coinbase is different for each miner, each is
working on a slightly different problem, thus further spreading the probability
of generating a correct hash onto all involved miners.
To regulate the transaction process the Bitcoin system targets to generate new
blocks at a constant pace, which is regulated by adjusting the difficulty of the
proof of work. It can be increased by increasing the needed preceding zeroes,
which lowers the probability exponentially.

The proof of work combined with the decentralized generation and storage of the
blockchain information enables us to solve the aforementioned double-spending
issue. Two obvious attack vectors exist.
First an attacker might simply try to generate blocks faster than the rest of
the system, thus being able to manipulate the transaction data. In order to
achieve this, the attacker would need to possess greater computing power, than
at least half of the network. Called \emph{50\% attack}, it requires a lot of
computing resources to realize, rendering it unfeasible, especially regarding
the reward of legitimate mining, which the attacker might have aquired.
The mining concept involving rewards for legitimate miners is able to counteract
other similar attacks based around the generation of fraudulent blocks, since
the generation of genuine or fraudulent blocks require the same amount of work.

%% LIMITATIONS
Although Bitcoin has been able to realize the concept of a decentralized
currency system with a proof of work, its limitations afford further
improvement.~\cite{barber,bonneau}

Especially proof-of-work itself has drawn criticism for its unsustainability at
larger scales~\cite{cohen} and specialization of mining system, basically
removing a part of the decentralization Bitcoin provides.

Other problems are essentially part of the bitcoin structure, since all
transactions are saved in the Blockchain, the size is continually growing. In
2016 it has already reached 60gb~\cite{crypto_mining_blog} and continues to grow
at a fast pace. A few countermeasures ameliorates the problem. For example
\emph{simplified payment verification}~\cite{satoshi} enables using clients,
which do not need to access the whole blockchain to process transactions. Since
the hashes are only generated from the header, the headers alone are sufficient
to verify new blocks. Transactions themselves can also be verified by just
accessing a single branch of the merkle tree, with all other hashes leading to
the tree root provided. These measures can reduce the amount of space needed for
Bitcoin transactions drastically, making the usage of Bitcoin on limited
hardware possible.


%% SOLUTIONS
Improving on the proof of work, a \emph{proof of stakes} has been
devised.~\cite{king_ppcoin} In this model, new blocks are selected in a
pseudorandom manner with a preference differing from implementation to
implementation. As a basis accounts with a high coin-balance are preferred in
the selection of the winning hash. Since the rules of the selection process are
known to each node, a verification is still possible, although no exact puzzle
solution is given.