Read Time:8 Minute
- The 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 Tolerant replicated state machine, resulting inn sub-second finality times.
- The paper also proposes two algorithms that leverage the time keeping properties of the PoH ledger – a PoS algorithm that can recover from partitions of any size and an efficient streaming Proof of Replication (PoRep).
- The combination of PoRep and PoH provides a defense against forgery of the ledger with respect to time (ordering) and storage.
- The protocol is analyzed on a 1 gbps network, and the paper shows that throughput up to 710k transactions per second is possible with todays hardware.
Proof of History
- Proof of History is a system for providing a sequence of hashes that can be used to record the order in which events have occurred.
- The system can be used to verify that some piece of data was created before a particular hash index was generated.
- The system can be scaled horizontally by synchronizing multiple Proof of History generators.
- Clients can enforce consistency of the generated sequence by inserting the last observed output of the sequence they consider valid into their input.
- The system is resistant to attacks by reversing the order of events or by generating a faster hidden sequence.
Proof of Stake Consensus
- The purpose of the Proof of Stake algorithm is to provide 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 misbehaving validators. This algorithm depends on messages eventually arriving to all participating nodes within a certain timeout.
- 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 is the proposed solution to the nothing at stake problem in Proof of Stake systems. 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.
- A super majority is 2/3rds of the validators weighted by their bonds. A super majority vote indicates that the network has reached consensus, and at least 1/3rd of the network would have had to vote maliciously for this branch to be invalid. This would put the economic cost of an attack at 1/3rd of the market cap of the coin.
- 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.
- 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.
- 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.
- 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 predefined schedule.
- Forked Proof of History generator PoH generators are designed with an identity that signs the generated sequence. 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.
- A network timeout would trigger an election.
- 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.
Streaming Proof of Replication
- Filecoin proposed a version of Proof of Replication in order to have fast and streaming verifications of Proof of Replication.
- 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.
- 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 in N hashes as they are generated by Proof of History generator, where N is approximately 1/2 the time it takes to encrypt the data.
- With N cores, each core can stream encryption for each identity.
- 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.
- 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.
- Hash is published at a periodic counter that is roughly equal to 1/2 the time it takes to encrypt the data set. Each replication identity must use the same 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.
- The Proof of History node is not expected to validate the submitted Proof of Replication proofs.
- 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.
- A malicious user could create many replicator identities and spam the network with bad proofs.
- A replicator node could attempt to partially erase some of the data to avoid storing the entire state.
- 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 predefined hash for random byte selection is generated.
- 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.
- The Leader is an elected Proof of History generator. It consumes arbitrary user transactions and outputs a Proof of History sequence of all the transactions 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.
- The Verifier nodes replicate the blockchain state and provide high availability of the blockchain state.
- The Validators are virtual nodes that consume bandwidth from Verifiers.
- The Leader is expected to be able to take incoming user packets, orders them the most efficient way possible, and sequences them into a Proof of History sequence that is published to downstream Verifiers.
- On a 1gbps network connection, the maximum number of transactions possible is 1 gigabit per second / 176 bytes = 710k tps max.
- A naive implementation of the state as a 50% full hashtable with 32 byte entries for each account, would theoretically fit 10 billion accounts into 640GB.
- Smart contracts are a generalized form of transactions. These are programs that run on each node and modify the state.
- In the above example, two different user programs call the same intrinsic. Each program is suspended until the batch execution of the intrinsics is complete.