Cryptographic Sortition in Blockchains: the importance of VRFs

When crypto can be the system gamer

Published in

The Witnet Oracle Blog

9 min readJan 25, 2019

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.

In this post I would like to share some internal research we conducted at Witnet, and how we realized that our cryptographic assumptions were not strong enough for our initial purposes.

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.

There are several properties that a cryptographic sortition needs to fullfil. First, nodes individually should be able to determine whether they are eligible to perform a certain action. Second, the eligibility should be cryptographically verifiable by other peers. Third, a cryptographic sortition is associated with a single identity, i.e., peers need to be sure that the proof was generated by the peer claiming it. Additionally, one would also like that the proof is indistinguishable from random.

We observed several cryptographic sortition schemes being proposed as part of a blockchain design, from the well known Proof of Work in Bitcoin to new proposals like, e.g.: Algorand, Filecoin or Witnet. In this post, I will put our focus on the cryptographic sortition described in Witnet and its possible improvements. I hope the information posted here is helpful for other blockchains with the same purpose.

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:

Cryptographic Sortition in Witnet

Where <> denotes the signature over the key M, and I refers to the influence of peer i at time t. The influence refers to the reputation of the node, i.e., how well it behaved in previous tasks. Essentially, if the hash of the signature of the task a peer wants to perform falls below the target value, then she becomes eligible to perform the task. We observe how each peer can individually figure out its sortition without interacting with any other peer in the network. The random value is commont to all peers (might well be the hash of the previous block).

In order to verify the eligibility of a node, the rest of the nodes first check that the signature was generated with the appropriate parameters (random value associated to the current epoch and task for which the node is opting). Then, they hash the signature to see whether it falls below the target value. If so, the eligibility of the peer for the task is verified.

Cryptographic sortitions that are based on digital signatures (i.e., the signature of a given message) fullfil the above defined statements: they are generated by a given peer, they are verifiable through the public key and their output appears random without the public key.

But digital signature based cryptographic sortition schemes tend to fullfil (as in Witnet) another requirement that I did not mention : each peer should have a single eligibility shot for an input message. Otherwise, peers could just run the lottery as many times as they wanted until they become eligible. The question we asked ourselves in Witnet was: do digital signatures fullfil this property?

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.

In a nutshell, Elliptic Curve Cryptography (ECC) is a public key cryptosystem in which each peer holds a private-public key pair. The private key is only known by the owner, while the public key is known to every peer. The communication peers have first to agree on the ECC curve that they
are going to utilize. A curve is just the set of points defined by an equation,
e.g., y ^2 = x^3 + ax + b. The curve is defined, among other parameters, by a generator point thanks to which we can reach any other point in the curve. In order to construct such a system, ECC constructs the following arithmetic:

if P is a point in the curve, -P is its reflection over the x axis
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

Note that with this arithmetic, we can already add points and consequently, multiply points with escalars (5P is just 2P+2P+P). The private-public key pair is constructed by choosing first a random integer that will serve us the private key. The public key is just the multiplication of the integer with the generator point. The security of the scheme relies on the difficulty or retrieving the integer that originate the public key point. This is, given the public key Q, the problem to find the integer k that multiplied the generator to reach Q is equivalent to the Discrete Logarithm Problem.

With such a system one can already perform several cryptographic approaches. One of them is the ability to generate digital signatures. The overall picture of ECDSA siganture generation can be seen in the following picture

Essentially, the input message m is first hashed. Later, a random number u is chosen such that, when multiplied with the generator point G, maps to a point in the curve whose x-coordinate is 0. If this condition is not satisfied, the value u is chosen again. If it is, then the inverse of u is multiplied with (e+dr) until the value is non-zero. The signature is the tuple (r,s).

In fact, we do not fully need to understand the algorithm to realize that the signature (r,s) heavily depends on the random value u selected in line 5. This is, the signature value will depend on a random value, and therefore, a given message can map to several different signatures.

This is already in conflict with what we ideally described for a cryptographic sortition. If the eligibility of a peer will depend on the hash of a signature that can take different values depending on the random value u chosen, we can expect that peers will continuously compute signatures until they find one for which the hash is sufficiently low, and thus become eligible. Interestingly, the crypto scheme utilized gives the peers the opportunity to game the system.

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:

Collision resistance, i.e., its hard to find two inputs that map to the same output.
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 β.

The last statement is quite important. It means that β will always be unique for a given input message and a public key, while the proof might be randomized. Thus, peers can not generate several signatures until they reach a sufficiently low value, as for the same input they will always get the same value. This is, they only run the lottery once per input message.

The question of course is how to construct those schemes. We follow the scheme proposed in [2], which describes VRF constructions for both RSA and ECC. For the sake of brevity, we omit the RSA construction description. Indeed, ECC offers crypto schemes advantages in terms of key and signature sizes compared to RSA to achieve the same level of security.

The ECC-VRF signature verification algorithm can be seen below. ECVRF_hash_to_curve is a function that hashes an integer to a point in the curve. On the contrary, ECVRF_hash_points is a function that hashes several points in the curve to an integer. With those two auxiliary functions we can construct the following signature generation scheme:

The output β is later hashed to check whether the digest is below the target value, while the proof π is used by the verifier to check that the output was indeed computed with the associated public key and for the given message in the following manner:

If we take a look at the algorithm, if and only if c’ is equal to c the proof is verified. Comparing step 15 from the verification and step 4 from the signature generation, we can see that the equality will hold as long as u=Gt and v=Ht. Can the verifier validate this without knowing the secret key k? In the following we demonstrate the correcteness of the equality:

The value u=Qc+Gs = Qc+G(t-kc) = Qc+Gt-Gkc=Qc+Gt -Qc=Gt
The value v=βc+Hs = βc+H(t-kc) = βc+Ht-Hkc=βc+Ht-βc=Ht

It can be verified that equality holds without having to know the secret value k.

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.

Verifiable Random Functions seem to solve the issue described above. Indeed they maintain all the benefits of digital signatures, with an additional fact: the “signature” is unique for a given public key and message. Additionally VRFs generate the proof thanks to which the verifier can check the validity of the transaction. Thus, VRFs seems the right approach for systems like Witnet.