Understanding Proof-of-Work

I was curious to study the behaviour of the Proof-of-Work protocol in block-chains. The essence of POW is the use of a nonce as part of the payload being signed. In order to do this, I decided to test it out with a simple signing test program. The signature algorithm chosen uses a 512-bit RSA key with a SHA-224 hash. A stronger hash algorithm would just take longer but it wouldn’t really deviate too much from the characteristics.

The example code used is as below.

void run() {
        const std::string msg = "THE BIG BROWN FOX JUMPS OVER A LAZY DOG";
        Poco::Crypto::RSAKey key(Poco::Crypto::RSAKey::KL_512, Poco::Crypto::RSAKey::EXP_SMALL);
        Poco::Crypto::RSADigestEngine dgst(key, "SHA224");
        long nonce;

        for(nonce = 0; dgst.signature()[0]; nonce++) {
                dgst.reset();
                dgst.update(msg);
                dgst.update(&nonce, sizeof(long));
        }

        std::cout << --nonce << std::endl;
}

A fixed message is used as the payload as the only difference it would make would be to the duration of time it takes to perform the signature operation. A larger payload would take longer to compute the hash but all else being equal, the characteristics would be the same.

A small note needs to be made about the difficulty level i.e. the number of leading-zeros in the signature. Tuning the difficulty level would change the amount of time it takes to compute the signature significantly. Although changing the hash and key size will change the compute time too, but this is the main factor.

A sample of the results are shown below for 100 samples of RSA512-SHA224 with a 8/16-bit leading-zero difficulty level.

The results show that 85% of the samples taken fall within a single standard deviation of the mean in terms of the number of iterations needed to compute a valid signature. This shows that most proof-of-work signing operations will take a similar amount of effort, all else equal.

It is unnecessary to use a random nonce each iteration because the keys themselves are already randomly generated. Therefore, the nonce could serve as a score of difficulty as it is embedded in the block-chain itself. It could potentially be used as a score of stake as well, if we consider the amount of effort expended as the stake in the chain and distributing the workload to the machine with the smallest stake, thus evenly spreading things out.