Sha3 Proof of Work Algorithms
Proof of Work is not a single consensus algorithm.
Rather it is a class of algorithms represented in Substrate by the
PowAlgorithm
trait. Before we
can build a PoW node we must specify a concrete PoW algorithm by implementing this trait. In this
recipe we specify two concrete PoW algorithms, both of which are based on the
sha3 hashing algorithm.
Minimal Sha3 PoW
First we turn our attention to a minimal working implementation. This consensus engine is kept intentionally simple. It omits some features that make Proof of Work practical for real-world use such as difficulty adjustment.
Begin by creating a struct that will implement the PowAlgorithm Trait
.
/// A minimal PoW algorithm that uses Sha3 hashing.
/// Difficulty is fixed at 1_000_000
#[derive(Clone)]
pub struct MinimalSha3Algorithm;
Because this is a minimal PoW algorithm, our struct can also be quite simple. In fact, it is a unit struct. A more complex PoW algorithm that interfaces with the runtime would need to hold a reference to the client. An example of this (on an older Substrate codebase) can be seen in Kulupu's RandomXAlgorithm.
Difficulty
The first function we must provide returns the difficulty of the next block to be mined. In our minimal sha3 algorithm, this function is quite simple. The difficulty is fixed. This means that as more mining power joins the network, the block time will become faster.
impl<B: BlockT<Hash=H256>> PowAlgorithm<B> for Sha3Algorithm {
type Difficulty = U256;
fn difficulty(&self, _parent: &BlockId<B>) -> Result<Self::Difficulty, Error<B>> {
// This basic PoW uses a fixed difficulty.
// Raising this difficulty will make the block time slower.
Ok(U256::from(1_000_000))
}
// --snip--
}
Verification
Our PoW algorithm must also be able to verify blocks provided by other authors. We are first given the pre-hash, which is a hash of the block before the proof of work seal is attached. We are also given the seal, which testifies that the work has been done, and the difficulty that the block author needed to meet. This function first confirms that the provided seal actually meets the target difficulty, then it confirms that the seal is actually valid for the given pre-hash.
fn verify(
&self,
_parent: &BlockId<B>,
pre_hash: &H256,
_pre_digest: Option<&[u8]>,
seal: &RawSeal,
difficulty: Self::Difficulty
) -> Result<bool, Error<B>> {
// Try to construct a seal object by decoding the raw seal given
let seal = match Seal::decode(&mut &seal[..]) {
Ok(seal) => seal,
Err(_) => return Ok(false),
};
// See whether the hash meets the difficulty requirement. If not, fail fast.
if !hash_meets_difficulty(&seal.work, difficulty) {
return Ok(false)
}
// Make sure the provided work actually comes from the correct pre_hash
let compute = Compute {
difficulty,
pre_hash: *pre_hash,
nonce: seal.nonce,
};
if compute.compute() != seal {
return Ok(false)
}
Ok(true)
}
Mining
Finally our proof of work algorithm needs to be able to mine blocks of our own.
fn mine(
&self,
_parent: &BlockId<B>,
pre_hash: &H256,
_pre_digest: Option<&[u8]>,
difficulty: Self::Difficulty,
round: u32 // The number of nonces to try during this call
) -> Result<Option<RawSeal>, Error<B>> {
// Get a randomness source from the environment; fail if one isn't available
let mut rng = SmallRng::from_rng(&mut thread_rng())
.map_err(|e| Error::Environment(format!("Initialize RNG failed for mining: {:?}", e)))?;
// Loop the specified number of times
for _ in 0..round {
// Choose a new nonce
let nonce = H256::random_using(&mut rng);
// Calculate the seal
let compute = Compute {
difficulty,
pre_hash: *pre_hash,
nonce,
};
let seal = compute.compute();
// If we solved the PoW then return, otherwise loop again
if hash_meets_difficulty(&seal.work, difficulty) {
return Ok(Some(seal.encode()))
}
}
// Tried the specified number of rounds and never found a solution
Ok(None)
}
Notice that this function takes a parameter for the number of rounds of mining it should attempt. If no block has been successfully mined in this time, the method will return. This gives the service a chance to check whether any new blocks have been received from other authors since the mining started. If a valid block has been received, then we will start mining on it. If no such block has been received, we will go in for another try at mining on the same block as before.
Realistic Sha3 PoW
Having understood the fundamentals, we can now build a more realistic sha3 algorithm. The primary difference here is that this algorithm will fetch the difficulty from the runtime via a runtime api. This change allows the runtime to dynamically adjust the difficulty based on block time. So if more mining power joins the network, the diffculty adjusts, and the blocktime remains constant.
Defining the Sha3Algorithm
Struct
We begin as before by defining a struct that will implement the PowAlgorithm
trait. Unlike before,
this struct must hold a reference to the
Client
so it can call the
appropriate runtime APIs.
/// A complete PoW Algorithm that uses Sha3 hashing.
/// Needs a reference to the client so it can grab the difficulty from the runtime.
pub struct Sha3Algorithm<C> {
client: Arc<C>,
}
Next we provide a new
method for conveniently creating instances of our new struct.
impl<C> Sha3Algorithm<C> {
pub fn new(client: Arc<C>) -> Self {
Self { client }
}
}
And finally we manually implement Clone
. We cannot derive clone as we did for the
MinimalSha3Algorithm
.
// Manually implement clone. Deriving doesn't work because
// it'll derive impl<C: Clone> Clone for Sha3Algorithm<C>. But C in practice isn't Clone.
impl<C> Clone for Sha3Algorithm<C> {
fn clone(&self) -> Self {
Self::new(self.client.clone())
}
}
It isn't critical to understand why the manual
Clone
implementation is necessary, just that it is necessary.
Implementing the PowAlgorithm
trait
As before we implement the PowAlgorithm
trait for out Sha3Algorithm
. This time we supply more
complex trait bounds to ensure that the client the algorithm holds a reference to actually provides
the DifficultyAPI
necessary
to fetch the PoW difficulty from the runtime.
// Here we implement the general PowAlgorithm trait for our concrete Sha3Algorithm
impl<B: BlockT<Hash=H256>, C> PowAlgorithm<B> for Sha3Algorithm<C> where
C: ProvideRuntimeApi<B>,
C::Api: DifficultyApi<B, U256>,
{
type Difficulty = U256;
// --snip
}
Difficulty
The implementation of PowAlgorithm
's difficulty
function, no longer returns a fxed value, but
rather calls into the runtime API which is guaranteed to exist because of the trait bounds. It also
maps any errors that may have occurred when using the API.
fn difficulty(&self, parent: B::Hash) -> Result<Self::Difficulty, Error<B>> {
let parent_id = BlockId::<B>::hash(parent);
self.client.runtime_api().difficulty(&parent_id)
.map_err(|e| sc_consensus_pow::Error::Environment(
format!("Fetching difficulty from runtime failed: {:?}", e)
))
}
Verify and Mine
The verify
and mine
functions are unchanged from the MinimalSha3Algorithm
implementation.