Cryptographic Sortition in Blockchains: the importance of VRFs

When crypto can be the system gamer

As I read and understand more and more about blockchain technologies as part of my researcher job in Witnet I start realizing the importance that cryptographic protocols and schemes have on their designs. It is amazing how a small design decision can influence the way users interact with the system and, potentially , take advantage of it.

PoE as part of Blockchain Protocols

Proof of Eligibilities (PoEs) are becoming increasingly popular in Blockchain technology. In fact PoEs give us the opportunity to decide who is responsible for performing an action. When the eligibility is discovered by each peer individually we usually refer to it as a cryptographic sortition scheme, i.e., the ability of discovering whether you are the winner of a “lottery” by yourself.

Cryptographic Sortition based on digital signatures

Usually cryptographic sortition schemes base their eligibility on the luck of getting a random number that falls below a given target value. The difficulty obviously depends on the target value; the higher the value is, the more chances peers have to become eligible. The target value, might indeed vary for different peers, perhaps depending on how well they behaved in previous tasks. This is precisely the approach described by Witnet. The cryptographic sortition in Witnet is defined as:

Image for post
Image for post
Cryptographic Sortition in Witnet

The problem: non-unique output for ECDSA

Before giving an answer to the previous question, let me give a brief introduction to how Elliptic Curve Cryptography works.

  • if two points P and Q are distinct then the result of adding P and Q is
    computed by drawing a line crossing P and Q, which will intersect in a
    third point −R in the curve. R is computed by taking the reflection of −R
    with respect to the x axis.
  • P + P is computed by drawing a tangent line to the curve at P , which
    again will intersect in a third point in the curve −2P . 2P is just the
    reflection over the x axis
Image for post
Image for post
Elliptic Curve Addition Example
Image for post
Image for post
ECDSA signature generation

The solution: VRFs as cryptographic sortition

Despite the problem mentioned, we would not like to renounce to all the advantages that digital signatures offer to our scheme. Therefore, we need to add the uniqueness property to our cryptographic sortition, as if it was a “public key version of a keyed HMAC”. Verifiable Random Functions (VRFs) seem to do the trick (and in fact, they are used in Algorand). VRFs were firstly introduced by Silvio Micali in [1]. VRFs generate two outputs: a so-called “unique-signature” β and a proof π. In addition to been a public key cryptosystem, they have the following properties:

  • Pseudorandomness, i.e., the output is indistinguishable from random by anyone not knowing the secret key.
  • Trusted uniqueness, that requires that, given a public key, a VRF input m corresponds to a unique output β.
Image for post
Image for post
VRF example
Image for post
Image for post
ECC-VRF proof generation
Image for post
Image for post
ECC-VRF proof verifcation
  • The value v=βc+Hs = βc+H(t-kc) = βc+Ht-Hkc=βc+Ht-βc=Ht

Conclusions

In this post I shared why digital signature based cryptographic sortition schemes might pose a big incentive for peers to game the system, specifically when the eligibility for a task depends on them. In the case of Witnet, both mining and data request tasks depend on the output of the sortition, and thus, we can not pose such an incentive for peers. We can reach a situation where the reward of a data request is high enough to incentivize peers to persistently generate signatures for it until the hash is low enough, thus performing a sort of Proof of Work underisable for data requests. In fact, if nodes put all the resources on a generous data request then the rest will be forgotten and the performance of the system would be severily affected.

References

Researcher at Witnet Foundation. Crypto and football lover

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store