DEPRECATED: Proof of Claim Explained: Part 1 — The Election Algorithm
This article is deprecated and no longer accurate. Visit https://versatus.io/blog for Versatus updates and news.
On Wednesday, February 8th, we introduced Versatus to the world. The reception has been incredible, and many have asked us what Proof of Claim (PoC) is, and how it works. First, a couple things about PoC, it is both the name of an election algorithm, and the namesake of the Versatus consensus algorithm, of which the election algorithm is an integral part of.
When we refer to PoC as an election we typically say “Proof of Claim Elections” and we will stick to that here in this multi-part series. This first article is about elections, the role they serve in Versatus consensus and why Proof of Claim, as compared to other election algorithms.
The word election comes from the old latin word eligere, which means “pick out” or “choose”. Elections occur for all sorts of reasons, from picking what your family will have for dinner, which bar you and your friends will go to, to picking the leader of a governance organization. Elections in a network of computers working together to operate and manage a program are not dissimilar.
Elections are used throughout distributed and decentralized systems as a component of, if not the core component of, consensus mechanisms. Elections are found in other blockchain consensus algorithms as well. Proof of Stake and Proof of Work are just forms of leader elections. In both cases a node is chosen to propose a block of transactions, other nodes then validate those transactions.
The proposed block from the elected node can be rejected by other nodes, or it can be accepted. In the case of Proof of Work, nodes decide, locally, if they will be the leader for a given round. Nodes then use a simple majority to determine if the block is confirmed, each node checking the validity of every transaction, and the other data in the block.
Under Ethereum Proof of Stake, “the protocol” elects the validator that proposes the block, and then other validators submit weighted votes on the validity of the block, including all the transactions included in the block, where the weight is determined by the size of their stake. A weighted majority is required to confirm a given block.
Proof of Claim elections works differently, instead of relying on “the protocol”, under a PoC election the local node runs the PoC Election algorithm and determines whether it has been elected or not, similar to how, in PoW networks, nodes do the “work” locally. Like PoS block builder elections, however, the election is random, and is not determined by the computational power a given node has. (More on the differences between PoC, PoW and PoS in the future parts to this series).
With this high level overview out of the way, let’s dig into some of the components so we can circle back to the concept with a better understanding of precisely how these elections work.
The Claim
What is a claim?
The word claim, when used as a noun in the English language, has a number of definitions that can be somewhat related, but have some key differences relative to the context of how it is used. The definition we are interested in here for the purpose of Versatus PoC elections is the following.
a right or title to something.
Every consensus participating node in the Versatus network has a claim. What is a claim, in the Versatus network, exactly? It’s just a custom data structure with some specific fields that allow the rest of the network to know it is indeed valid. Let’s take a look at what it looks like in the vrrb_core/claim module.
#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq, Hash)]
pub struct Claim {
pub public_key: String,
pub address: String,
pub hash: String,
pub nonce: u128,
...
}The claim is build as a struct a custom data type in the Rust programming language that allows us to combine a number of different types, including potentially other structs and custom data types. The Versatus Claim struct is pretty straightforward. It has fields (some of which have been left out for the sake of brevity), most of which are standard data types such as String and u128 or bool types. For the sake of elections, the important one is the hash field which is a hexadecimal string representation of a nested SHA256 hash of node information. The node information is hashed n times where n is a 10(nonce + 1).
When a node joins the network it submits its claim to the rest of the network, once the claim is validated and confirmed in a block, and thus saved to state, the claim is then eligible for mining elections, and if it includes the minimum required stake for the given node, eligible for validator quorum elections.
Now that the claim is saved in the network state, the other nodes in the network can include it when they run elections locally. For miner elections, there is always only 1 winner. For quorum elections, depending on the number of validator nodes, there are between 10 and 50 winners per quorum.
So what happens when the a node runs an election?
impl Claim {
...
pub fn get_pointer_sum(&self, block_seed: u64) -> Option<u128> {
// Convert the number to a hexadecimal string
let block_seed_hex = format!("{block_seed:x}");
// Initalize an empty vector to save each matching characters "pointer"
// value to.
let mut pointers = vec![];
// Iterate through all of the characters in the block seed string
block_seed_hex.chars().enumerate().for_each(|(idx, c)| {
// Search for the same character in the hash and retrieve
// the index position
let res = self.hash.find(c);
// If there is a match raise it to the power of the index
// position of the current character in the block seed
if let Some(n) = res {
let n = n as u128;
let n = n.checked_pow(idx as u32);
// If there is no integer overflow, push it to the vector
// we initialized earlier
if let Some(n) = n {
pointers.push(n);
}
} else {
// If a match is not found, return early, current node
// has a claim that is disqualified for this round
return None
}
});
// Sum the values in the pointer together
let pointer_sum: u128 = pointers.iter().sum();
Some(pointer_sum)
}
...
}In Rust, a struct can implement methods in what is known as an impl block. What you are looking at in the code block above is the get_pointer_sum method implemented on the Claim struct. The method takes an unsigned integer that can be up to 64 bits (the maximum size for next block seed). The 64 bit number is first converted to a hexadecimal string. The length (number of characters) of the string is then saved in a separate variable for verification later in the method. An empty vector is then initialized to save data in.
Then, the characters in the hexadecimal block seed string are iterated over, and for each character, that same character is searched for in the hash field of the Claim struct. If a match is found, the index position of the character in the hash is raised to the power of the index position of the character in the block_seed and the result is saved to that vector that we initialized earlier.
If any character does not match, i.e., not all characters in the seed were also in the claim hash, then the claim is disqualified for the current election. This node will have to wait until the next round.
If they do match, we still have a little work left to do. Next we sum all the values in the vector, and then return the summed value. This is the process for calculating the value necessary to conduct the election for a single node.
This process is then repeated for every node eligible for the current election (mining nodes for miner elections, validator nodes for quorum elections, proposers for conflict resolution). While this seems like a lot of work, because of the short maximum length of the block seed (16 characters) and the short fixed length of the claim hash (64 characters), its quite fast. This algorithm can be run on every claim in the network concurrently to further optimize for speed, if needed.
To read a more detailed technical explanation of Proof of Claim elections, check out the VRRB whitepaper.
To be continued
About the Author
Andrew N. Smith, CAIA is the founder of Versatus Labs, Inc. and is a two-time founder, a strong motivator and leader. At his first startup, Andrew spent 5 years as the sole engineer and data scientist building out the full stack of Machine Learning and Deep Learning models. Andrew began working on Versatus, invented Proof of Claim and single-handedly built the Versatus prototype. Andrew’s vision for Versatus is to not only provide a better, more decentralized, secure and stable blockchain, cryptocurrency and smart contracts platform, but to also actively bridge the gap between the “real economy” and the “crypto economy” by providing developers the most flexible, extensible and composable smart contract platform in the world.
About Versatus Labs, Inc.
Versatus Labs is the development company building Versatus , an innovative blockchain protocol. Versatus is a fast, scalable Layer 1 built on top of a novel consensus mechanism called Proof of Claim. Versatus aims to make the developer experience frictionless by bringing ‘Build, Ship, Run’ DevOps to Web3 with its isolated, composable smart contracts containers, complete with a unikernel VM enabling developers to build in the language of their choice.
