bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 3쪽 중 2쪽
his would put the economic
cost of an attack at 13rd of the market cap of the coin.
5.3 Bonding
A bonding transaction takes a amount of coin and moves it to a bonding
account under the users identity. Coins in the bonding account cannot be
spent and have to remain in the account until the user removes them. The
user can only remove stale coins that have timed out. Bonds are valid after
super majority of the current stakeholders have confirmed the sequence.
5.4 Voting
It is anticipated that the Proof of History generator will be able to publish
a signature of the state at a predefined period. Each bonded identity must
confirm that signature by publishing their own signed signature of the state.
The vote is a simple yes vote, without a no.
If super majority of the bonded identities have voted within a timeout,
then this branch would be accepted as valid.
15
5.5 Unbonding
Missing N number of votes marks the coins as stale and no longer eligible for
voting. The user can issue an unbonding transaction to remove them.
N is a dynamic value based on the ratio of stale to active votes. N
increases as the number of stale votes increases. In an event of a large
network partition, this allows the larger branch to recover faster then the
smaller branch.
5.6 Elections
Election for a new PoH generator occur when the PoH generator failure is
detected. The validator with the largest voting power, or highest public key
address if there is a tie is picked as the new PoH generator.
A super majority of confirmations are required on the new sequence. If
the new leader fails before a super majority confirmations are available, the
next highest validator is selected, and a new set of confirmations is required.
To switch votes, a validator needs to vote at a higher PoH sequence
counter, and the new vote needs to contain the votes it wants to switch.
Otherwise the second vote will be slashable. Vote switching is expected to
be designed so that it can only occur at a height that does not have a super
majority.
Once a PoH generator is established, a Secondary can be elected to take
over the transactional processing duties. If a Secondary exists, it will be
considered as the next leader during a Primary failure.
The platform is designed so that the Secondary becomes Primary and
lower rank generators are promoted if an exception is detected or on a pre-
defined schedule.
5.7 Election Triggers
5.7.1 Forked Proof of History generator
PoH generators are designed with an identity that signs the generated se-
quence. A fork can only occur in case the PoH generators identity has been
compromised. A fork is detected because two different historical records have
been published on the same PoH identity.
16
5.7.2 Runtime Exceptions
A hardware failure or a bug, or a intentional error in the PoH generator could
cause it to generate an invalid state and publish a signature of the state that
does not match the local validators result. Validators will publish the correct
signature via gossip and this event would trigger a new round of elections.
Any validators who accept an invalid state will have their bonds slashed.
5.7.3 Network Timeouts
A network timeout would trigger an election.
5.8 Slashing
Slashing occurs when a validator votes two separate sequences. A proof of
malicious vote will remove the bonded coins from circulation and add them
to the mining pool.
A vote that includes a previous vote on a contending sequence is not
eligible as proof of malicious voting. Instead of slashing the bonds, this vote
removes remove the currently cast vote on the contending sequence.
Slashing also occurs if a vote is cast for an invalid hash generated by the
PoH generator. The generator is expected to randomly generate an invalid
state, which would trigger a fallback to Secondary.
5.9 Secondary Elections
Secondary and lower ranked Proof of History generators can be proposed
and approved. A proposal is cast on the primary generators sequence. The
proposal contains a timeout, if the motion is approved by a super majority
of the vote before the timeout, the Secondary is considered elected, and will
take over duties as scheduled. Primary can do a soft handover to Secondary
by inserting a message into the generated sequence indicating that a handover
will occur, or inserting an invalid state and forcing the network to fallback
to Secondary.
If a Secondary is elected, and the primary fails, the Secondary will be
considered as the first fallback during an election.
17
5.10 Availability
CAP systems that deal with partitions have to pick Consistency or Avail-
ability. Our approach eventually picks Availability, but because we have
an objective measure of time, Consistency is picked with reasonable human
timeouts.
Proof of Stake verifiers lock up some amount of coin in a stake, which
allows them to vote for a particular set of transactions. Locking up coin is a
transaction that is entered into a PoH stream, just like any other transaction.
To vote, a PoS verifier has to sign the hash of the state, as it was computed
after processing all the transactions to a specific position in the PoH ledger.
This vote is also entered as a transaction into the PoH stream. Looking at
the PoH ledger, we can then infer how much time passed between each vote,
and if a partition occurs, for how long each verifier has been unavailable.
To deal with partitions with reasonable human timeframes, we propose
a dynamic approach to unstake unavailable verifiers. When the number of
verifiers is high and above 23, the unstaking process can be fast. The number
of hashes that must be generated into the ledger is low before the unavailable
verifiers stake is fully unstaked and they are no longer counted for consensus.
When the number of verifiers is below23rds but above 12, the unstaking timer is
slower, requiring a larger number of hashes to be generated before the missing
verifiers are unstaked. In a large partition, like a partition that is missing 12
or more of the verifiers, the unstaking process is very very slow. Transactions
can still be entered into the stream, and verifiers can still vote, but full 23rds
consensus will not be achieved until a very large amount of hashes have been
generated and the unavailable verifiers have been unstaked. The difference
in time for a network to regain liveness allows us as customers of the network
human timeframes to pick a partition that we want to continue using.
5.11 Recovery
In the system we propose, the ledger can be fully recovered from any failure.
That means, anyone in the world can pick any random spot in the ledger and
create a valid fork by appending newly generated hashes and transactions.
If all the verifiers are missing from this fork, it would take a very very long
time for any additional bonds to become valid and for this branch to achieve
2
3rds super majority consensus. So full recovery with zero available validators
would require a very large amount of hashes to be appended to the ledger,
18
and only after all the unavailable validators have been unstaked will any new
bonds be able to validate the ledger.
5.12 Finality
PoH allows verifiers of the network to observe what happened in the past with
some degree of certainty of the time of those events. As the PoH generator is
producing a stream of messages, all the verifiers are required to submit their
signatures of the state within 500ms. This number can be reduced further
depending on network conditions. Since each verification is entered into the
stream, everyone in the network can validate that every verifier submitted
their votes within the required timeout without actually observing the voting
directly.
5.13 Attacks
5.13.1 Tragedy of Commons
The PoS verifiers simply confirm the state hash generated by the PoH gen-
erator. There is an economic incentive for them to do no work and simply
approve every generated state hash. To avoid this condition, the PoH gener-
ator should inject an invalid hash at a random interval. Any voters for this
hash should be slashed. When the hash is generated, the network should
immediately promote the Secondary elected PoH generator.
Each verifier is required to respond within a small timeout - 500ms for
example. The timeout should be set low enough that a malicious verifier has
a low probability of observing another verifiers vote and getting their votes
into the stream fast enough.
5.13.2 Collusion with the PoH generator
A verifier that is colluding with the PoH generator would know in advance
when the invalid hash is going to be produced and not vote for it. This
scenario is really no different than the PoH identity having a larger verifier
stake. The PoH generator still has to do all the work to produce the state
hash.
19
5.13.3 Censorship
Censorship or denial of service could occur when a 13rd of the bond holders
refuse to validate any sequences with new bonds. The protocol can defend
against this form of attack by dynamically adjusting how fast bonds become
stale. In the event of a denial of service, the larger partition will be designed
to fork and censor the Byzantine bond holders. The larger network will re-
cover as the Byzantine bonds become stale with time. The smaller Byzantine
partition would not be able to move forward for a longer period of time.
The algorithm would work as follows. A majority of the network would
elect a new Leader. The Leader would then censor the Byzantine bond
holders from participating. Proof of History generator would have to continue
generating a sequence, to prove the passage of time, until enough Byzantine
bonds have become stale so the bigger network has a super majority. The rate
at which bonds become stale would be dynamically based on what percentage
of bonds are active. So the Byzantine minority fork of the network would have
to wait much longer than the majority fork to recover a super majority. Once
a super majority has been established, slashing could be used to permanently
punish the Byzantine bond holders.
5.13.4 Long Range Attacks
PoH provides a natural defense against long range attacks. Recovering the
ledger from any point in the past would require the attacker to overtake the
valid ledger in time by outpacing the speed of the PoH generator.
The consensus protocol provides a second layer of defense, as any attack
would have to take longer then the time it takes to unstake all the valid
validators. It also creates an availability gap in the history of the ledger.
When comparing two ledgers of the same height, the one with the smallest
maximum partition can be objectively considered as valid.
5.13.5 ASIC Attacks
Two opportunities for an ASIC attacks exist in this protocol - during parti-
tion, and cheating timeouts in Finality.
For ASIC attacks during Partitions, the Rate at which bonds are unstaked
is non-linear, and for networks with large partitions the rate is orders of
magnitude slower then expected gains from an ASIC attack.
20
For ASIC attacks during Finality, the vulnerability allows for byzantine
validators who have a bonded stake wait for confirmations from other nodes
and inject their votes with a collaborating PoH generator. The PoH gener-
ator can then use its faster ASIC to generate 500ms worth of hashes in less
time, and allow for network communication between PoH generator and the
collaborating nodes. But, if the PoH generator is also byzantine, there is no
reason why the byzantine generator wouldnt have communicated the exact
counter when they expect to insert the failure. This scenario is no different
than a PoH generator and all the collaborators sharing the same identity and
having a single combined stake and only using 1 set of hardware.
6 Streaming Proof of Replication
6.1 Description
Filecoin proposed a version of Proof of Replication [6]. The goal of this
version is to have fast and streaming verifications of Proof of Replication,
which are enabled by keeping track of time in Proof of History generated
sequence. Replication is not used as a consensus algorithm, but is a useful
tool to account for the cost of storing the blockchain history or state at a
high availability.
6.2 Algorithm
As shown in Figure 7 CBC encryption encrypts each block of data in se-
quence, using the previously encrypted block to XOR the input data.
Each replication identity generates a key by signing a hash that has been
generated Proof of History sequence. This ties the key to a replicators iden-
tity, and to a specific Proof of History sequence. Only specific hashes can be
selected. (See Section 6.5 on Hash Selection)
The data set is fully encrypted block by block. Then to generate a proof,
the key is used to seed a pseudorandom number generator that selects a
random 32 bytes from each block.
A merkle hash is computed with the selected PoH hash prepended to the
each slice.
The root is published, along with the key, and the selected hash that
was generated. The replication node is required to publish another proof
21
Figure 7: Sequential CBC encryption
Figure 8: Fast Proof of Replication
22
in N hashes as they are generated by Proof of History generator, where N
is approximately 12 the time it takes to encrypt the data. The Proof of
History generator will publish specific hashes for Proof of Replication at a
predefined periods. The replicator node must select the next published hash
for generating the proof. Again, the hash is signed, and random slices are
selected from the blocks to create the merkle root.
After a period of N proofs, the data is re-encrypted with a new CBC key.
6.3 Verification
With N cores, each core can stream encryption for each identity. Total space
required is 2blocks∗ N cores, since the previous encrypted block is necessary
to generate the next one. Each core can then be used to generate all the
proofs that derived from the current encrypted block.
Total time to verify proofs is expected to be equal to the time it takes to
encrypt. The proofs themselves consume few random bytes from the block,
so the amount of data to hash is significantly lower then the encrypted block
size. The number of replication identities that can be verified at the same
time is equal to the number of available cores. Modern GPUs have 3500+
cores available to them, albeit at 12- 13 the clock speed of a CPU.
6.4 Key Rotation
Without key rotation the same encrypted replication can generate cheap
proofs for multiple Proof of History sequences. Keys are rotated periodically
and each replication is re-encrypted with a new key that is tied to a unique
Proof of History sequence.
Rotation needs to be slow enough that its practical to verify replication
proofs on GPU hardware, which is slower per core than CPUs.
6.5 Hash Selection
Proof of History generator publishes a hash to be used by the entire network
for encrypting Proofs of Replication, and for using as the pseudorandom
number generator for byte selection in fast proofs.
Hash is published at a periodic counter that is roughly equal to 12 the time
it takes to encrypt the data set. Each replication identity must use the same
23
hash, and use the signed result of the hash as the seed for byte selection, or
the encryption key.
The period that each replicator must provide a proof must be smaller than
the encryption time. Otherwise the replicator can stream the encryption and
delete it for each proof.
A malicious generator could inject data into the sequence prior to this
hash to generate a specific hash. This attack is discussed more in 5.13.2.
6.6 Proof Validation
The Proof of History node is not expected to validate the submitted Proof
of Replication proofs. It is expected to keep track of number of pending and
verified proofs submitted by the replicators identity. A proof is expected to
be verified when the replicator is able to sign the proof by a super majority
of the validators in the network.
The verifications are collected by the replicator via p2p gossip network,
and submitted as one packet that contains a super majority of the validators
in the network. This packet verifies all the proofs prior to a specific hash gen-
erated by the Proof of History sequence, and can contain multiple replicator
identities at once.
6.7 Attacks
6.7.1 Spam
A malicious user could create many replicator identities and spam the net-
work with bad proofs. To facilitate faster verification, nodes are required
to provide the encrypted data and the entire merkle tree to the rest of the
network when they request verification.
The Proof of Replication that is designed in this paper allows for cheap
verification of any additional proofs, as they take no additional space. But
each identity would consume 1 core of encryption time. The replication target
should be set to a maximum size of readily available cores. Modern GPUs
ship with 3500+ cores.
6.7.2 Partial Erasure
A replicator node could attempt to partially erase some of the data to avoid
storing the entire state. The number of proofs and the randomness of the
24
seed should make this attack difficult.
For example, a user storing 1 terabyte of data erases a single byte from
each 1 megabyte block. A single proof that samples 1 byte out of every
megabyte would have a likelihood of collision with any erased byte 1 − (1−
1/1, 000, 0000)1,000,000 = 0.63. After 5 proofs the likelihood is 0 .99.
6.7.3 Collusion with PoH generator
The signed hash is expected to be used to seed the sample. If a replicator
could select a specific hash in advance then the replicator could erase all
bytes that are not going to be sampled.
A replicator identity that is colluding with the Proof of History generator
could inject a specific transaction at the end of the sequence before the pre-
defined hash for random byte selection is generated. With enough cores, an
attacker could generate a hash that is preferable to the replicators identity.
This attack could only benefit a single replicator identity. Since all the
identities have to use the same exact hash that is cryptographically signed
with ECDSA (or equivalent), the resulting signature is unique for each repli-
cator identity, and collision resistant. A single replicator identity would only
have marginal gains.
6.7.4 Denial of Service
The cost of adding an additional replicator identity is expected to be equal
to the cost of storage. The cost of adding extra computational capacity to
verify all the replicator identities is expected to be equal to the cost of a CPU
or GPU core per replication identity.
This creates an opportunity for a denial of service attack on the network
by creating a large number of valid replicator identities.
To limit this attack, the consensus protocol chosen for the network can
select a replication target, and award the replication proofs that meet the de-
sired characteristics, like availability on the network, bandwidth, geolocation
etc...
6.7.5 Tragedy of Commons
The PoS verifiers could simply confirm PoRep without doing any work. The
economic incentives should be lined up with the PoS verifiers to do work,
25
Figure 9: System Architecture
like by splitting the mining payout between the PoS verifiers and the PoRep
replication nodes.
To further avoid this scenario, the PoRep verifiers can submit false proofs
a small percentage of the time. They can prove the proof is false by providing
the function that generated the false data. Any PoS verifier that confirmed
a false proof would be slashed.
7 System Architecture
7.1 Components
7.1.1 Leader, Proof of History generator
The Leader is an elected Proof of History generator. It consumes arbitrary
user transactions and outputs a Proof of History sequence of all the transac-
tions that guarantees a unique global order in the system. After each batch
of transactions the Leader outputs a signature of the state that is the result
of running the transactions in that order. This signature is signed with the
identity of the Leader.
26
7.1.2 State
A naive hash table indexed by the users address. Each cell contains the full
users address and the memory required for this computation. For example
Transaction table contains:
프로젝트로 돌아가기