web analytics

Verifiable Delay Functions

Verifiable Delay Functions

Part of the IOTA Foundation research team that’s based in Berlin submitted a paper to arxiv this month. The topic is verifiable delay functions and their potential role in denial of service attacks in IoT environments.

Before we begin, let’s briefly meet the three authors. Vidal Attias has a mathematics and computer science background which helps inform his investigations of verifiable delay functions (VDF) for IOTA since 2019. Luigi Vigneri is a senior research scientist at IF leading the network team. Vassil Dimitrov holds a PhD in applied mathematics, has written a few books, and authored countless research papers. His three year anniversary with the IOTA Foundation will be this Fall.

Hopefully briefly meeting the team like this adds some personal intrigue as well as establishes credibility of what they have to say. This is a group of highly accomplished scholars and practitioners.


Background

A denial of service (DoS) attack occurs when a malicious actor launches an overwhelming amount of server requests to a server/network with the intention of flooding that server/network. If successful, the malicious actor carrying out the DoS attack will hinder the network enough to prevent legitimate users from accessing it. Think of DoS as spamming a website host.

You’ve probably heard the term “DDoS” since it’s the more common of the two. The difference between “DoS” vs “DDoS” simply refers to the origination of the attack – “DoS” coming from a single attacking device, “DDoS” coming from many attacking devices. DDoS can be thought of as being a sub-class of the DoS family.

Source: www.dnsstuff.com

Here’s a slightly deeper look into this class of network attacks, courtesy of Shyam Oza’s Security Boulevard

This is what it might look like when you’re trying to visit a website currently under a DoS or DDoS attack:


The Conundrum

Now we can get into the paper.

IOTA was founded on the premise that IoT was the future, and that a secure data and value transaction protocol was required to underlay it. IoT remains relatively novel, so some well established practices across the wider internet don’t apply.

The novelty and uniqueness of IoT environments especially factor in the handling of DoS attacks – which have been well studied and largely dealt with on the wider internet. IoT is already being pushed into pursuing cutting edge solutions for this otherwise simple problem.

The authors opine that the computationally intensive proof of work combine with high fees to make traditional block chains infeasible for use in IoT environments.

The conundrum seems to be the following. IoT devices aren’t capable of handling proof of work loads. Therefore, proof of work must be removed as a barrier to these small devices. However, removing barriers to transactions opens the door to DoS attacks (due to no incentive against sending lots of free transactions). The authors set out to implement VDFs in place of proof of work as a means of preventing DoS attacks.

The authors are quick to point out IOTA’s starting set of weird issues that must be accounted for. Namely, no fees and no miners make it vulnerable to a DoS attack vector without a solution.

A 2018 paper from Stanford simplifies VDFs as being functions that take a prescribed time to complete, even in parallel computation, and whose answers can be quickly verified by anyone. The paper contains 13 pages of good mathematical rigor, so check it out if you’re so inclined. A simpler resource might be something like this ELI5 VDF thread on Reddit. The IOTA research team uses a similar description of VDFs:

Apparently VDFs were conjured recently. This IOTA paper contains a few references to the VDF literature, the most senior of which dates back to only 2018 (it’s the Stanford paper we linked earlier). The team confirms that VDFs are very new … so new that this is one of the first actual implementations of the idea:

 

To reiterate, the importance of VDFs seems to be that they are evaluated in a certain number of steps and verified in a much shorter amount of time than that. The authors note the use of past techniques meant to quash DoS attacks in domains like email. We get further clarification on why VDFs are the focus:

We hit some turbulence at this point in the paper – a wild technical jargon has appeared. Let’s keep try to keep it simple. VDFs are based on “modular exponentations”

Pay attention to the difference in devices discussed. IOTA will be a mix of hardware, so accounting for the differences is important when assessing attack vectors and solutions. The authors do this by splitting hardware into standard vs specialized. We’ll see these analyzed visually later in the article.

Again, stressing the difference between IOTA and blockchains. Everything is a tradeoff, even zero fees. No fees opens IOTA to DoS attacks ceteris paribus.

We might think of VDF functions happening in stepwise fashion. Data from the previous transaction must be present before proof for the next transaction can be done. This seems to be exactly what shatters the ability of parallelization to game this system like it does for PoW. 

The nodes share public inputs including VDF difficulty, RSA modulus, and cryptographic hash function. These three inputs are the same for every node in the network so that everyone is on a level playing field.

When you put all of this together and insert it into the network, a diagram like the one below begins to emerge. The green boxes are transactions, and the blue boxes contain the stepwise process of evaluation to verification. The math behind this 

A couple rigorous mathematical proofs are provided following the above diagram. Those are much to detailed for our purposes, so we skip ahead to the illustrative chart which is great! Note that the data depicted below was collected from real C++ simulations on an Intel i7 laptop, so they’re coming from the actual world of bits.

The weird color scheme meshed with square vs circle meshed with solid vs empty made this a confusing visual at first. Let us simplify it for you:

Axes are labeled as increasing in cost along the x-axis and increasing in computation speed along the y-axis. All of the circles represent proof of work while all squares represent the new VDF function that this paper has focused on. Solid vs empty shapes represent individual device vs pool of devices. Colors represent devices with more granularity. Disregard colors and fill if it remains confusing.

Result: Using VDF, pooling any type of hardware will result in no change in speed of computation and a multiple order of magnitude increase in cost! This is in stark contrast to PoW, where ASICs cost a lot to pool but give more than 11 orders of magnitude improvement in speed of computation. 

VDFs maxed out at 3 orders of magnitude for speed of computation in this sim as compared to PoW’s maxed out 11 orders of magnitude. 

VDFs are clearly a very new subject in the space of cryptography. We’re not cryptography experts here at HelloIOTA, but after attempting to breakdown a highly technical paper, the results presented here are shockingly good. We might attempt to interview the team to obtain more context and set proper expectations for the community.

It seems as though this research starts us down the path of PoW obsolescence and ASIC obsolescence, yet an even more robust DoS prevention mechanism in the form of VDFs. 

SHARE IT!

Written by: Hello IOTA Staff