bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 3쪽 중 1쪽
Solana: A new architecture for a high
performance blockchain v0.8.13
Anatoly Yakovenko
anatoly@solana.io
Legal Disclaimer Nothing in this White Paper is an offer to sell, or the solicitation of an offer
to buy, any tokens. Solana is publishing this White Paper solely to receive feedback and comments from
the public. If and when Solana offers for sale any tokens (or a Simple Agreement for Future Tokens), it
will do so through definitive offering documents, including a disclosure document and risk factors. Those
definitive documents also are expected to include an updated version of this White Paper, which may
differ significantly from the current version. If and when Solana makes such an offering in the United
States, the offering likely will be available solely to accredited investors.
Nothing in this White Paper should be treated or read as a guarantee or promise of how Solanas
business or the tokens will develop or of the utility or value of the tokens. This White Paper outlines
current plans, which could change at its discretion, and the success of which will depend on many factors
outside Solanas control, including market-based factors and factors within the data and cryptocurrency
industries, among others. Any statements about future events are based solely on Solanas analysis of the
issues described in this White Paper. That analysis may prove to be incorrect.
Abstract
This paper proposes a new blockchain architecture based on Proof
of History (PoH) - a proof for verifying order and passage of time
between events. PoH is used to encode trustless passage of time into
a ledger - an append only data structure. When used alongside a
consensus algorithm such as Proof of Work (PoW) or Proof of Stake
(PoS), PoH can reduce messaging overhead in a Byzantine Fault Tol-
erant replicated state machine, resulting inn sub-second finality times.
This paper also proposes two algorithms that leverage the time keep-
ing properties of the PoH ledger - a PoS algorithm that can recover
from partitions of any size and an efficient streaming Proof of Replica-
tion (PoRep). The combination of PoRep and PoH provides a defense
against forgery of the ledger with respect to time (ordering) and stor-
age. The protocol is analyzed on a 1 gbps network, and this paper
shows that throughput up to 710k transactions per second is possible
with todays hardware.
1
1 Introduction
Blockchain is an implementation of a fault tolerant replicated state machine.
Current publicly available blockchains do not rely on time, or make a weak
assumption about the participants abilities to keep time [4, 5]. Each node in
the network usually relies on their own local clock without knowledge of any
other participants clocks in the network. The lack of a trusted source of time
means that when a message timestamp is used to accept or reject a message,
there is no guarantee that every other participant in the network will make
the exact same choice. The PoH presented here is designed to create a ledger
with verifiable passage of time, i.e. duration between events and message
ordering. It is anticipated that every node in the network will be able to rely
on the recorded passage of time in the ledger without trust.
2 Outline
The remainder of this article is organized as follows. Overall system design is
described in Section 3. In depth description of Proof of History is described
in Section 4. In depth description of the proposed Proof of Stake consensus
algorithm is described in Section 5. In depth description of the proposed
fast Proof of Replication is described in Section 6. System Architecture and
performance limits are analyzed in Section 7. A high performance GPU
friendly smart contracts engine is described in Section 7.5
3 Network Design
As shown in Figure 1, at any given time a system node is designated as
Leader to generate a Proof of History sequence, providing the network global
read consistency and a verifiable passage of time. The Leader sequences user
messages and orders them such that they can be efficiently processed by other
nodes in the system, maximizing throughput. It executes the transactions
on the current state that is stored in RAM and publishes the transactions
and a signature of the final state to the replications nodes called Verifiers.
Verifiers execute the same transactions on their copies of the state, and pub-
lish their computed signatures of the state as confirmations. The published
confirmations serve as votes for the consensus algorithm.
2
Figure 1: Transaction flow throughout the network.
In a non-partitioned state, at any given time, there is one Leader in the
network. Each Verifier node has the same hardware capabilities as a Leader
and can be elected as a Leader, this is done through PoS based elections.
Elections for the proposed PoS algorithm are covered in depth in Section 5.6.
In terms of CAP theorem, Consistency is almost always picked over Avail-
ability in an event of a Partition. In case of a large partition, this paper
proposes a mechanism to recover control of the network from a partition of
any size. This is covered in depth in Section 5.12.
4 Proof of History
Proof of History is a sequence of computation that can provide a way to
cryptographically verify passage of time between two events. It uses a cryp-
tographically secure function written so that output cannot be predicted
from the input, and must be completely executed to generate the output.
The function is run in a sequence on a single core, its previous output as the
3
current input, periodically recording the current output, and how many times
its been called. The output can then be re-computed and verified by external
computers in parallel by checking each sequence segment on a separate core.
Data can be timestamped into this sequence by appending the data (or a
hash of some data) into the state of the function. The recording of the state,
index and data as it was appended into the sequences provides a timestamp
that can guarantee that the data was created sometime before the next hash
was generated in the sequence. This design also supports horizontal scaling
as multiple generators can synchronize amongst each other by mixing their
state into each others sequences. Horizontal scaling is discussed in depth in
Section 4.4
4.1 Description
The system is designed to work as follows. With a cryptographic hash func-
tion, whose output cannot be predicted without running the function (e.g.
sha256, ripemd, etc.), run the function from some random starting value
and take its output and pass it as the input into the same function again.
Record the number of times the function has been called and the output at
each call. The starting random value chosen could be any string, like the
headline of the New York times for the day.
For example:
PoH Sequence
Index Operation Output Hash
1 sha256(”any random starting value”) hash1
2 sha256( hash1) hash2
3 sha256( hash2) hash3
Where hashN represents the actual hash output.
It is only necessary to publish a subset of the hashes and indices at an
interval.
For example:
4
PoH Sequence
Index Operation Output Hash
1 sha256(”any random starting value”) hash1
200 sha256( hash199) hash200
300 sha256( hash299) hash300
As long as the hash function chosen is collision resistant, this set of hashes
can only be computed in sequence by a single computer thread. This follows
from the fact that there is no way to predict what the hash value at index
300 is going to be without actually running the algorithm from the starting
value 300 times. Thus we can thus infer from the data structure that real
time has passed between index 0 and index 300.
In the example in Figure 2, hash 62f51643c1 was produced on count
510144806912 and hash c43d862d88 was produced on count 510146904064.
Following the previously discussed properties of the PoH algorithm, we can
trust that real time passed between count 510144806912 and count 510146904064.
Figure 2: Proof of History sequence
5
4.2 Timestamp for Events
This sequence of hashes can also be used to record that some piece of data
was created before a particular hash index was generated. Using a ‘combine‘
function to combine the piece of data with the current hash at the current
index. The data can simply be a cryptographically unique hash of arbitrary
event data. The combine function can be a simple append of data, or any
operation that is collision resistant. The next generated hash represents a
timestamp of the data, because it could have only been generated after that
specific piece of data was inserted.
For example:
PoH Sequence
Index Operation Output Hash
1 sha256(”any random starting value”) hash1
200 sha256( hash199) hash200
300 sha256( hash299) hash300
Some external event occurs, like a photograph was taken, or any arbitrary
digital data was created:
PoH Sequence With Data
Index Operation Output Hash
1 sha256(”any random starting value”) hash1
200 sha256( hash199) hash200
300 sha256( hash299) hash300
336 sha256(append( hash335, photograph sha256)) hash336
Hash336 is computed from the appended binary data of hash335 and the
sha256 of the photograph. The index and the sha256 of the photograph are
recorded as part of the sequence output. So anyone verifying this sequence
can then recreate this change to the sequence. The verifying can still be done
in parallel and its discussed in Section 4.3
Because the initial process is still sequential, we can then tell that things
entered into the sequence must have occurred sometime before the future
hashed value was computed.
6
POH Sequence
Index Operation Output Hash
1 sha256(”any random starting value”) hash1
200 sha256(hash199) hash200
300 sha256(hash299) hash300
336 sha256(append(hash335, photograph1 sha256)) hash336
400 sha256(hash399) hash400
500 sha256(hash499) hash500
600 sha256(append(hash599, photograph2 sha256)) hash600
700 sha256(hash699) hash700
Table 1: PoH Sequence With 2 Events
In the sequence represented by Table 1, photograph2 was created before
hash600, and photograph1 was created before hash336. Inserting the data
into the sequence of hashes results in a change to all subsequent values in the
sequence. As long as the hash function used is collision resistant, and the
data was appended, it should be computationally impossible to pre-compute
any future sequences based on prior knowledge of what data will be inte-
grated into the sequence.
The data that is mixed into the sequence can be the raw data itself, or
just a hash of the data with accompanying metadata.
In the example in Figure 3, input cfd40df8... was inserted into the
Proof of History sequence. The count at which it was inserted is 510145855488
and the state at which it was inserted it is 3d039eef3. All the future gen-
erated hashes are modified by this change to the sequence, this change is
indicated by the color change in the figure.
Every node observing this sequence can determine the order at which all
events have been inserted and estimate the real time between the insertions.
7
Figure 3: Inserting data into Proof of History
4.3 Verification
The sequence can be verified correct by a multicore computer in significantly
less time than it took to generate it.
For example:
Core 1
Index Data Output Hash
200 sha256( hash199) hash200
300 sha256( hash299) hash300
Core 2
Index Data Output Hash
300 sha256( hash299) hash300
400 sha256( hash399) hash400
Given some number of cores, like a modern GPU with 4000 cores, the
verifier can split up the sequence of hashes and their indexes into 4000 slices,
and in parallel make sure that each slice is correct from the starting hash to
the last hash in the slice. If the expected time to produce the sequence is
going to be:
8
Figure 4: Verification using multiple cores
Total number of hashes
Hashes per second for 1 core
The expected time to verify that the sequence is correct is going to be:
Total number of hashes
(Hashes per second per core * Number of cores available to verify)
In the example in Figure 4, each core is able to verify each slice of the
sequence in parallel. Since all input strings are recorded into the output, with
the counter and state that they are appended to, the verifiers can replicate
each slice in parallel. The red colored hashes indicate that the sequence was
modified by a data insertion.
4.4 Horizontal Scaling
Its possible to synchronize multiple Proof of History generators by mixing the
sequence state from each generator to each other generator, and thus achieve
horizontal scaling of the Proof of History generator. This scaling is done
without sharding. The output of both generators is necessary to reconstruct
the full order of events in the system.
9
PoH Generator A
Index Hash Data
1 hash1a
2 hash2a hash1b
3 hash3a
4 hash4a
PoH Generator B
Index Hash Data
1 hash1b
2 hash2b hash1a
3 hash3b
4 hash4b
Given generators A and B, A receives a data packet from B (hash1b),
which contains the last state from Generator B, and the last state generator
B observed from Generator A. The next state hash in Generator A then de-
pends on the state from Generator B, so we can derive that hash1b happened
sometime before hash3a. This property can be transitive, so if three gener-
ators are synchronized through a single common generator A↔ B↔ C,
we can trace the dependency between A and C even though they were not
synchronized directly.
By periodically synchronizing the generators, each generator can then
handle a portion of external traffic, thus the overall system can handle a
larger amount of events to track at the cost of true time accuracy due to
network latencies between the generators. A global order can still be achieved
by picking some deterministic function to order any events that are within
the synchronization window, such as by the value of the hash itself.
In Figure 5, the two generators insert each others output state and record
the operation. The color change indicates that data from the peer had mod-
ified the sequence. The generated hashes that are mixed into each stream
are highlighted in bold.
The synchronization is transitive. A↔ B↔ C There is a provable order
of events between A and C through B.
Scaling in this way comes at the cost of availability. 10 × 1 gbps connec-
tions with availability of 0.999 would have 0 .99910 = 0.99 availability.
4.5 Consistency
Users are expected to be able to enforce consistency of the generated se-
quence and make it resistant to attacks by inserting the last observed output
of the sequence they consider valid into their input.
10
Figure 5: Two generators synchronizing
PoH Sequence A
Index Data Output Hash
10 hash10a
20 Event1 hash20a
30 Event2 hash30a
40 Event3 hash40a
PoH Hidden Sequence B
Index Data Output Hash
10 hash10b
20 Event3 hash20b
30 Event2 hash30b
40 Event1 hash40b
A malicious PoH generator could produce a second hidden sequence with
the events in reverse order, if it has access to all the events at once, or is able
to generate a faster hidden sequence.
To prevent this attack, each client-generated Event should contain within
itself the latest hash that the client observed from what it considers to be
a valid sequence. So when a client creates the ”Event1” data, they should
append the last hash they have observed.
11
PoH Sequence A
Index Data Output Hash
10 hash10a
20 Event1 = append(event1 data, hash10a) hash20a
30 Event2 = append(event2 data, hash20a) hash30a
40 Event3 = append(event3 data, hash30a) hash40a
When the sequence is published, Event3 would be referencing hash30a,
and if its not in the sequence prior to this Event, the consumers of the
sequence know that its an invalid sequence. The partial reordering attack
would then be limited to the number of hashes produced while the client has
observed an event and when the event was entered. Clients should then be
able to write software that does not assume the order is correct for the short
period of hashes between the last observed and inserted hash.
To prevent a malicious PoH generator from rewriting the client Event
hashes, the clients can submit a signature of the event data and the last
observed hash instead of just the data.
PoH Sequence A
Index Data Output Hash
10 hash10a
20 Event1 = sign(append(event1 data, hash10a),Client Private Key) hash20a
30 Event2 = sign(append(event2 data, hash20a),Client Private Key) hash30a
40 Event3 = sign(append(event3 data, hash30a),Client Private Key) hash40a
Verification of this data requires a signature verification, and a lookup of
the hash in the sequence of hashes prior to this one.
Verify:
(Signature, PublicKey, hash30a, event3 data) = Event3
Verify(Signature, PublicKey, Event3)
Lookup(hash30a, PoHSequence)
In Figure 6, the user-supplied input is dependent on hash 0xdeadbeef...
existing in the generated sequence sometime before its inserted. The blue
12
Figure 6: Input with a back reference.
top left arrow indicates that the client is referencing a previously produced
hash. The clients message is only valid in a sequence that contains the hash
0xdeadbeef.... The red color in the sequence indicates that the sequence
has been modified by the clients data.
4.6 Overhead
4000 hashes per second would generate an additional 160 kilobytes of data,
and would require access to a GPU with 4000 cores and roughly 0.25-0.75
milliseconds of time to verify.
4.7 Attacks
4.7.1 Reversal
Generating a reverse order would require an attacker to start the malicious
sequence after the second event. This delay should allow any non malicious
peer to peer nodes to communicate about the original order.
13
4.7.2 Speed
Having multiple generators may make deployment more resistant to attacks.
One generator could be high bandwidth, and receive many events to mix
into its sequence, another generator could be high speed low bandwidth that
periodically mixes with the high bandwidth generator.
The high speed sequence would create a secondary sequence of data that
an attacker would have to reverse.
4.7.3 Long Range Attacks
Long range attacks involve acquiring old discarded client Private Keys, and
generating a falsified ledger [10]. Proof of History provides some protection
against long range attacks. A malicious user that gains access to old private
keys would have to recreate a historical record that takes as much time as the
original one they are trying to forge. This would require access to a faster
processor than the network is currently using, otherwise the attacker would
never catch up in history length.
Additionally, a single source of time allows for construction of a simpler
Proof of Replication (more on that in Section 6). Since the network is de-
signed so that all participants in the network will rely on a single historical
record of events.
PoRep and PoH together should provide a defense of both space and time
against a forged ledger.
5 Proof of Stake Consensus
5.1 Description
This specific instance of Proof of Stake is designed for quick confirmation of
the current sequence produced by the Proof of History generator, for voting
and selecting the next Proof of History generator, and for punishing any mis-
behaving validators. This algorithm depends on messages eventually arriving
to all participating nodes within a certain timeout.
14
5.2 Terminology
bonds Bonds are equivalent to a capital expense in Proof of Work. A miner
buys hardware and electricity, and commits it to a single branch in a
Proof of Work blockchain. A bond is coin that the validator commits
as collateral while they are validating transactions.
slashing The proposed solution to the nothing at stake problem in Proof
of Stake systems [7]. When a proof of voting for a different branch
is published, that branch can destroy the validators bond. This is an
economic incentive designed to discourage validators from confirming
multiple branches.
super majority A super majority is 23rds of the validators weighted by their
bonds. A super majority vote indicates that the network has reached
consensus, and at least 13rd of the network would have had to vote
maliciously for this branch to be invalid. T프로젝트로 돌아가기