2

If both the public key and the private key are known ahead of time (public knowledge), and the goal is to choose a message/nonce that generates a signature with, for example, a certain number of leading zeroes, is this a similarly computationally challenging task to traditional proof of work in that it is "hard to find" but "(relatively) easy to verify?"

It seems like the answer should be "yes," because if the answer is "no" then (I think?) it would imply that signatures are not pseudorandomly uniform for different messages.

Put perhaps more succinctly, can a signature also itself serve to represent a targeted proof-of-work?

Lastly, do answers to any of the above change when the signature scheme used is Schnorr rather than ECSDA?

edit: it seems that adapter signatures[1] may essentially allow for this, but I do not know enough about how they work to know for sure. [1] https://github.com/ElementsProject/scriptless-scripts

1 Answer 1

2

Not if you just do leading zeroes or just lowest value when interpreting as a very large integer.

To make things easier, let's just assume that you use compact signatures which are just the signature's R and s values concatenated with each other instead of other signature formats which have additional surrounding formatting bytes that would interfere with a direct comparison.

The compact signature format just concatenates the R and the s values. However this would be a trivially broken PoW scheme as soon as one person found a valid PoW, and that person would always be the winner. This is because the R value is just the X coordinate of a nonce which is multiplied by the curve's generator point. If someone finds a R value that works with the PoW, they can just keep reusing that nonce and always have the same valid R value. So this is obviously broken.

But if you were smarter about what is compared for the PoW by instead checking that the s value is lower than the target. The s value is computed using a formula which includes the nonce, the message hash, and the private key. In Schnorr, there are also multiple hashes and EC Curve point multiplications, which help to make it more random. So s should be pseudorandom.

But there are some other issues with a signature based PoW, although these are more directed at ECDSA specifically rather than signatures in general.

The public key to verify against must be known, and must be known to be "correct". This means that you can't just have each person participating in the PoW provide their own public key, it needs to be some fixed public key, and everyone has to know the private key.

This is because, given an ECDSA signature and a message, you can compute a public key that would validate that signature and message combo. This is why it is important that the public key is known before validating the signature. Note that this is not possible for the proposed Schnorr signature scheme as it is not possible to do public key recovery with it.

The message that is verified must be published and hash. That's pretty obvious as it's a crucial part of any PoW algorithm. But specifically with ECDSA, given a signature and a public key, you can compute a message hash that would would result in a valid signature. This is why it is important that the message is something that is hashed and not just the value that gets put into the signature algorithm. This shouldn't be possible with the Schnor signatures.

So you could use signatures as a PoW so long as you are checking s and not R for the actual PoW check. And I would suggest that you use Schnorr signatures rather than ECDSA.

1
  • Thank you for the very detailed answer. I'm glad you also clarified the specifics how the different signature schemes behave differently for this purpose. My original conception of "signature" was something more like what you describe as s in your answer. I will look into Schnorr signatures as you suggest (and apparently I also need to better understand ECDSA too!). Thanks again.
    – philbw4
    Commented Oct 19, 2019 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.