bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 2쪽 중 1쪽
Tezos — a self-amending crypto-ledger
White paper
L.M Goodman
September 2, 2014
Changes between the original paper and our current implementation are
indicated in red.
“Our argument is not flatly
circular, but something like it. ”
— Willard van Orman Quine
Abstract
We present Tezos, a generic and self-amending crypto-ledger. Tezos
can instantiate any blockchain based ledger. The operations of a regular
blockchain are implemented as a purely functional module abstracted into
a shell responsible for network operations. Bitcoin, Ethereum, Cryptonote,
etc. can all be represented within Tezos by implementing the proper in-
terface to the network layer.
Most importantly, Tezos supports meta upgrades: the protocols can
evolve by amending their own code. To achieve this, Tezos begins with
a seed protocol defining a procedure for stakeholders to approve amend-
ments to the protocol, including amendments to the voting procedure
itself. This is not unlike philosopher Peter Suber’s Nomic[ 3], a game built
around a fully introspective set of rules.
In addition, Tezos’s seed protocol is based on a pure proof-of-stake
system and supports Turing complete smart contracts. Tezos is imple-
mented in OCaml, a powerful functional programming language offering
speed, an unambiguous syntax and semantic, and an ecosystem making
Tezos a good candidate for formal proofs of correctness.
Familiarity with the Bitcoin protocol and basic cryptographic primi-
tives are assumed in the rest of this paper.
1
Contents
1 Introduction 3
2 Self-amending cryptoledger 3
2.1 Mathematical representation . . . . . . . . . . . . . . . . . . . . 3
2.2 The network shell . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Chain selection algorithm . . . . . . . . . . . . . . . . . . 4
2.2.3 Network level defense . . . . . . . . . . . . . . . . . . . . 5
2.3 Functional representation . . . . . . . . . . . . . . . . . . . . . . 5
2.3.1 Validating the chain . . . . . . . . . . . . . . . . . . . . . 5
2.3.2 Amending the protocol . . . . . . . . . . . . . . . . . . . . 6
2.3.3 RPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Seed protocol 8
3.1 Economy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.1 Coins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.2 Mining and signing rewards . . . . . . . . . . . . . . . . . 8
3.1.3 Lost coins . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.4 Amendment rules . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Proof-of-stake mechanism . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.3 Generating the random seed . . . . . . . . . . . . . . . . . 11
3.2.4 Follow-the-coin procedure . . . . . . . . . . . . . . . . . . 12
3.2.5 Mining blocks . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.6 Signing blocks . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.7 Weight of the chain . . . . . . . . . . . . . . . . . . . . . 14
3.2.8 Denunciations . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Smart contracts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.1 Contract type . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3.2 Origination . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3.3 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3.4 Storage fees . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.5 Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.6 Fees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Conclusion 17
2
1 Introduction
In the first part of this paper, we will discuss the concept of abstract blockchains
and the implementation of a self-amending crypto-ledger. In the second part,
we will describe our proposed seed protocol.
2 Self-amending cryptoledger
A blockchain protocol can be decomposed into three distinct protocols:
- The network protocol discovers blocks and broadcasts transactions.
- The transaction protocol specifies what makes a transaction valid.
- The consensus protocol forms consensus around a unique chain.
Tezos implements a generic network shell. This shell is agnostic to the
transaction protocol and to the consensus protocol. We refer to the transaction
protocol and the consensus protocol together as a “blockchain protocol” . We
will first give a mathematical representation of a blockchain protocol and then
describe some of the implementation choices in Tezos.
2.1 Mathematical representation
A blockchain protocol is fundamentally a monadic implementation of concurrent
mutations of a global state. This is achieved by defining “blocks” as operators
acting on this global state. The free monoid of blocks acting on the genesis state
forms a tree structure. A global, canonical, state is defined as the minimal leaf
for a specified ordering.
This suggests the following abstract representation:
- Let (S;) be a totally ordered, countable, set of possible states.
- Let⊘ /2 S represent a special, invalid, state.
- Let B SS[f⊘g be the set of blocks. The set of valid blocks is B\ SS.
The total order on S is extended so that 8s2 S;⊘ < s . This order deter-
mines which leaf in the block tree is considered to be the canonical one. Blocks
in B are seen as operators acting on the state.
All in all, any blockchain protocol 1 (be it Bitcoin, Litecoin, Peercoin, Ethereum,
Cryptonote, etc) can be fully determined by the tuple:
(
S;;⊘; B SS[f⊘g
)
1GHOST is an approach which orders the leafs based on properties of the tree. Such an
approach is problematic for both theoretical and practical reasons. It is almost always better
to emulate it by inserting proofs of mining in the main chain.
3
The networking protocol is fundamentally identical for these blockchains.
“Mining” algorithms are but an emergent property of the network, given the
incentives for block creation.
In Tezos, we make a blockchain protocol introspective by letting blocks act
on the protocol itself. We can then express the set of protocols recursively as
P =
{(
S;;⊘; B S(SP)[f⊘g
)}
2.2 The network shell
This formal mathematical description doesn’t tell us how to build the block tree.
This is the role of the network shell, which acts as an interface between a gossip
network and the protocol.
The network shell works by maintaining the best chain known to the client.
It is aware of three type of objects. The first two are transactions and blocks,
which are only propagated through the network if deemed valid. The third are
protocols, OCaml modules used to amend the existing protocol. They will be
described in more details later on. For now we will focus on transaction and
blocks.
The most arduous part of the network shell is to protect nodes against
denial-of-service attacks.
2.2.1 Clock
Every block carries a timestamp visible to the network shell. Blocks that appear
to come from the future are buffered if their timestamps are within a few minutes
of the system time and rejected otherwise. The protocol design must tolerate
reasonable clock drifts in the clients and must assume that timestamps can be
falsified.
2.2.2 Chain selection algorithm
The shell maintains a single chain rather than a full tree of blocks. This chain
is only overwritten if the client becomes aware of a strictly better chain.
Maintaining a tree would be more parsimonious in terms of network commu-
nications but would be susceptible to denial-of-service attacks where an attacker
produces a large number of low-scoring but valid forks.
Yet, it remains possible for a node to lie about the score of a given chain, a
lie that the client may only uncover after having processed a potentially large
number of blocks. However, such a node can be subsequently ignored.
Fortunately, a protocol can have the property that low scoring chains exhibit
a low rate of block creation. Thus, the client would only consider a few blocks
of a “weak” fork before concluding that the announced score was a lie.
4
2.2.3 Network level defense
In addition, the shell is “defensive” . It attempts to connect to many peers across
various IP ranges. It detects disconnected peers and bans malicious nodes.
To protect against certain denial of service attacks, the protocol provides
the shell with context dependent bounds on the size of blocks and transactions.
2.3 Functional representation
2.3.1 V alidating the chain
We can efficiently capture almost all the genericity of our abstract blockchain
structure with the following OCaml types. To begin with, a block header is
defined as:
type raw_block_header = {
pred: Block_hash.t;
header: Bytes.t;
operations: Operation_hash.t list;
timestamp: float;
}
We are purposefully not typing the header field more strongly so it can
represent arbitrary content. However, we do type the fields necessary for the
operation of the shell. These include the hash of the preceding block, a list of
operation hashes and a timestamp. In practice, the operations included in a
block are transmitted along with the blocks at the network level. Operations
themselves are represented as arbitrary blobs.
type raw_operation = Bytes.t
The state is represented with the help of a Context module which encap-
sulates a disk-based immutable key-value store. The structure of a key-value
store is versatile and allows us to efficiently represent a wide variety of states.
module Context = sig
type t
type key = string list
val get: t -> key -> Bytes.t option Lwt.t
val set: t -> key -> Bytes.t -> t Lwt.t
val del: t -> key -> t Lwt.t
(*...*)
end
To avoid blocking on disk operations, the functions use the asynchronous
monad Lwt[ 4]. Note that the operations on the context are purely functional:
get uses the option monad rather than throwing an exception while set and
del both return a new Context. The Context module uses a combination
of memory caching and disk storage to efficiently provide the appearance of an
immutable store.
We can now define the module type of an arbitrary blockchain protocol:
5
type score = Bytes.t list
module type PROTOCOL = sig
type operation
val parse_block_header : raw_block_header -> block_header option
val parse_operation : Bytes.t -> operation option
val apply :
Context.t ->
block_header option ->
(Operation_hash.t * operation) list ->
Context.t option Lwt.t
val score : Context.t -> score Lwt.t
(*...*)
end
We no longer compare states directly as in the mathematical model, instead
we project the Context onto a list of bytes using the score function. List of
bytes are ordered first by length, then by lexicographic order. This is a fairly
generic structure, similar to the one used in software versioning, which is quite
versatile in representing various orderings.
Why not define a comparison function within the protocol modules? First
off it would be hard to enforce the requirement that such a function represent a
total order. The score projection always verifies this (ties can be broken based on
the hash of the last block). Second, in principle we need the ability to compare
states across distinct protocols. Specific protocol amendment rules are likely to
make this extremely unlikely to ever happen, but the network shell does not
know that.
The operations parse_block_header and parse_operation are exposed
to the shell and allow it to pass fully typed operations and blocks to the protocol
but also to check whether these operations and blocks are well-formed, before
deciding to relay operations or to add blocks to the local block tree database.
The apply function is the heart of the protocol:
- When it is passed a block header and the associated list of operations, it
computes the changes made to the context and returns a modified copy.
Internally, only the difference is stored, as in a versioning system, using
the block’s hash as a version handle.
- When it is only passed a list of operations, it greedily attempts to apply
as many operations as possible. This function is not necessary for the
protocol itself but is of great use to miners attempting to form valid blocks.
2.3.2 Amending the protocol
Tezos’s most powerful feature is its ability to implement protocol capable of
self-amendment. This is achieved by exposing two procedures functions to the
protocol:
- set_test_protocol which replaces the protocol used in the testnet with
6
a new protocol (typically one that has been adopted through a stakeholder
voter).
- promote_test_protocol which replaces the current protocol with the
protocol currently being tested
These functions transform a Context by changing the associated protocol.
The new protocol takes effect when the following block is applied to the chain.
module Context = sig
type t
(*...*)
val set_test_protocol: t -> Protocol_hash.t Lwt.t
val promote_test_protocol: t -> Protocol_hash.t -> t Lwt.t
end
The protocol_hash is the sha256 hash of a tarball of .ml and .mli files.
These files are compiled on the fly. They have access to a small standard library
but are sandboxed and may not make any system call.
These functions are called through the apply function of the protocol which
returns the new Context.
Many conditions can trigger a change of protocol. In its simplest version,
a stakeholder vote triggers a change of protocol. More complicated rules can
be progressively voted in. For instance, if the stakeholder desire they may pass
an amendment that will require further amendments to provide a computer
checkable proof that the new amendment respects certain properties. This is
effectively and algorithmic check of “constitutionality” .
2.3.3 RPC
In order to make the GUI building job’s easier, the protocol exposes a JSON-
RPC API. The API itself is described by a json schema indicating the types
of the various procedures. Typically, functions such as get_balance can be
implemented in the RPC.
type service = {
name : string list ;
input : json_schema option ;
output : json_schema option ;
implementation : Context.t -> json -> json option Lwt.t
}
The name is a list of string to allow namespaces in the procedures. Input
and output are optionally described by a json schema.
Note that the call is made on a given context which is typically a recent
ancestor of the highest scoring leaf. For instance, querying the context six
blocks above the highest scoring leaf displays the state of the ledger with six
confirmations.
The UI itself can be tailored to a specific version of the protocol, or generi-
cally derived from the JSON specification.
7
3 Seed protocol
Much like blockchains start from a genesis hash, Tezos starts with a seed pro-
tocol. This protocol can be amended to reflect virtually any blockchain based
algorithm.
3.1 Economy
3.1.1 Coins
There are initially 10 000 000 000 (ten billion) coins (the initial extent of the
token supply will be the number of tokens issued during the crowdsale and not
specifically “10 billion”, which was merely a placeholder. This change in size
has no effect on the principal at hand) , divisible up to two decimal places (for
the sake of precision we may in actuality be using eight digits after the decimal) .
We suggest that a single coin be referred to as a “tez” and that the smallest
unit simply as a cent. We also suggest to use the symbol ꜩ (\ua729, “Latin
small letter tz”) to represent a tez. Therefore 1 cent = ꜩ0:01 = one hundreth
of a tez.
3.1.2 Mining and signing rewards
Principle We conjecture that the security of any decentralised currency re-
quires to incentivize the participants with a pecuniary reward (we are in the
process of finalizing the rewards schedule at the moment) . As explained in the
position paper, relying on transaction costs alone suffers from a tragedy of the
commons. In Tezos, we rely on the combination of a bond and a reward.
Bonds are one year (bonds will now only last a single cycle, given the high
opportunity cost and little benefit to security of extending the bonding period
past one cycle) security deposits purchased by miners (endorsers will also be
required to purchase bonds) . In the event of a double signing, these bonds are
forfeited.
After a year (cycle), the miners (and endorsers) receive a reward along with
their bond to compensate for their opportunity cost. The security is primarily
being provided by the value of the bond and the reward need only be a small
percentage of that value.
The purpose of the bonds is to diminish the amount of reward needed, and
perhaps to use the loss aversion effect to the network’s advantage.
Specifics In the seed protocol, mining a block offers a reward of ꜩ512 and
requires a bond of ꜩ1536. Signing a block offers a reward of 32∆T 1 tez where
∆T is the time interval in minutes between the block being signed and its
predecessor. There are up to 16 signatures per block and signing requires no
bond.These numbers were based on a supply of 10 billions tokens and we will
tweak them accordingly. We may increase the number of signatures per block
as well as we’ve found in simulations it can strongly increase the difficulty of
forks.
8
Thus, assuming a mining rate of one block per minute, about 8% of the
initial money mass should be held in the form of safety bonds after the first
year. subject to change based on the adjustment of the parameters above .
The reward schedule implies at most a 5.4% nominal inflation rate (the
total block rewards will still start at about 5% per year, but we may add an
asymptotic cap to the total number of tokens. We think it’s irrelevant when the
governance model is aligned with the token holder’s interest, but it is important
to some people so we’re reluctantly considering it) . Nominal inflation is neutral,
it neither enrishes nor impoverishes anyone 2.
Note that the period of a year is determined from the block’s timestamps,
not from the number of blocks. This is to remove uncertainty as to the length
of the commitment made by miners.
Looking forward The proposed reward gives miners a 33% return on their
bond (we’re currently revising these parameters but will soon finalize a method
that makes sense for all parties) . This return needs to be high in the early days
as miners and signers commit to hold a potentially volatile asset for an entire
year (bonds will only last for a cycle and not a full year) .
However, as Tezos mature, this return could be gradually lowered to the
prevailing interest rate. A nominal rate of inflation below 1% could safely be
achieved, though it’s not clear there would be any point in doing so.
3.1.3 Lost coins
In order to reduce uncertainty regarding the monetary mass, addresses showing
no activity for over a year (as determined by timestamps) are destroyed along
with the coins they contain (inactive addresses will no longer lose their funds
after one year as initially proposed in the white paper, they will only lose their
staking rights until they become active again. What it means is that if an
address is inactive, it will not be selected to create blocks (which would slow
down the consensus algorithm), and it will not be allowed to vote until it is
reactivated (to avoid uncertainty about participation rate) .
3.1.4 Amendment rules
Amendments are adopted over election cycles lasting N = 2 17 = 131 072 blocks
each. Given the a one minute block interval, this is about three calendar months.
The election cycle is itself divided in four quarters of 215 = 32 768 blocks. This
cycle is relatively short to encourage early improvements, but it is expected that
further amendments will increase the length of the cycle (protocol upgrade votes
will be much more frequent in the first year in order to allow for rapid iteration.
As a security measure, the Tezos foundation will have a veto power expiring after
twelve months, until we rule out any kinks in the voting procedure) . Adoption
requires a certain quorum to be met. This quorum starts at Q = 80 % but
2In 프로젝트로 돌아가기