NEAR

Following Ready Layer One, the most anticipated upcoming conference in the blockchain space with speakers from Ethereum Foundation, NEAR, Polkadot and other layer one protocols, NEAR will be hosting a one week long hackathon with a $7500 prize pool.

Go to Hackathon

The last day of the conference will include multiple workshops that will help you to ramp up and get in shape to win. The hackathon is also a great opportunity to put the newly-learned skills to test.

Participation in the hackathon doesn’t require a ticket to Ready Layer One and is open to everybody. You can participate both solo and as part of a team.

Register to the hackathon early here!

The hackathon will be hosted on Gitcoin, with multiple challenges that include:

Best financial hack

At least in the United States, the economy has taken a turn for the worst. Many people are worried about the lasting economic impacts of this disruption across the globe. In the midst of this, bank branches are closed, so getting cash and/or depositing money is much more difficult.

We want the participants to come up with a product that adds a creative solution to local problems regarding the exchange or management of currency.

Best social interaction hack

“Social Distancing” is the phrase uttered by lonely wanderers on empty streets, but that doesn’t mean we need to sacrifice our social lives! This prize will go to the team or person with the best social hack.

Specifically, we want participants to build a product that provides a way for people to interact with each other in a meaningful way virtually, solving the social interaction challenge experienced due to the ongoing lockdowns.

Best accessibility hack

We want to see hacks for people that aren’t as mobile or can’t leave their homes, but still deserve the same access to activities, resources, and food.

We want the participants to build a product simple enough to be used by elderly people (by themselves or through an intermediary/relative) and solves a problem specific to someone who can’t leave their home easily, either in general or due to the ongoing outbreak.

Best global hack

This challenge is to make the most broadly applicable solution to any problem that affects a large percentage of the population today. The app that solves the biggest problem for the most number of people wins.

Best Ethereum Interoperability hack

NEAR maintains an Ethereum bridge and has partnered with Summa to add EVM support to its runtime. To win this challenge, you need to come up with the best hack that leverages the bridge, the EVM support, or both.

Best student hack

Are you a junior dev but still want to participate? This one is especially for you. We want to see the best and brightest minds who have a lot more to learn give their take on the problem as well.

Requirements

  • You are currently enrolled in university, school of some sort or in a similar position.
  • The application is thoughtfully designed and its use case is well developed
  • Rather than technical know-how, we are looking for supporting research, design of the application, and an MVP.

Win by integrating with companies that build on NEAR today!

A gaming marketplace (Stardust) and a prediction market company (Flux) will each be hosting a challenge during the hackathon to build the best integration with their platforms.

Register today!

The hackathon will be hosted here, register early to get notifications and make sure you don’t miss it!

Last week, we announced a collaboration with ZeroPool that will add support for private transactions to the NEAR Protocol. In NEAR today, all transactions are public—similar to Bitcoin and Ethereum. That means that—for every transaction—the sender, the receiver, and the amount transacted are all public. This is what allows everyone to audit the ledger and confirm that all the transactions are valid and no tokens are spent twice.

In many cases, it is desirable to transact in a way where only the participants involved in the transaction can have any insight into it. Achieving this while maintaining the ability to validate the correctness of the ledger is a complex task involving non-trivial cryptography.

In this blog post, I will dive deep into the internals of how private transactions will be implemented on NEAR so that no information about the participants or amounts are revealed—all without sacrificing the ability to validate the correctness.

UTXO tree

While NEAR generally uses the account model, private transactions use the unspect transaction output (UTXO) model instead. Each UTXO is a tuple (amount, receiver, salt) where amount is the amount of tokens transferred, receiver is the public key of the receiver of tokens, and salt is just some random number.

All the UTXOs are stored in a merkle tree of a predefined height. The height of the tree defines how many transactions the pool can process throughout its existence.

Each leaf of the tree is either an UTXO, or null, indicating a vacant spot that can in the future be occupied by a new UTXO. Once a spot is occupied, it never frees up. Initially, all the leaves are nulls.

The actual UTXO is never revealed to anyone but the receiver. Instead, the leaves of the merkle tree are hashes of the UTXOs—thus the need for the salt. Without the salt, if Alice knows Bob’s public key, she can brute-force different amounts and see if the hash of amount, Bob’s public key appears as the leaf of the tree, thus deanonymizing a transaction sent to Bob.

Transactions

Let’s say Alice wants to send some tokens privately to Bob. The tokens that belong to Alice are those in the UTXOs in which the receiver is equal to Alice’s public key. To make a private transfer, Alice creates a transaction of the following form:

The transaction has exactly two inputs and exactly two outputs (the exact number of input and output UTXOs doesn’t have to be two but does need to be the same for all the transactions). The inputs are some existing UTXOs that correspond to some leaves of the merkle tree, and the outputs are brand-new UTXOs that will be appended to the tree.

When Alice is sending the transaction, if she actually publishes the two input UTXOs that are being spent, she will link the transaction to the transactions that produced those UTXOs. The goal of the pool is to make sure that such links cannot be established and thus the input UTXOs cannot be published.

How can we implement the transactions in such a way that the validators can confirm that it spends some existing UTXOs without revealing the actual UTXOs being spent? 

ZeroPool, like many other privacy-preserving transaction engines, uses zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) for this purpose.

Zero-knowledge arguments of knowledge for a particular computation allow producing cryptographic proofs of the following form:

Given public input 1, public input 2 …

I know such private input 1, private input 2 …

That [some claim]

The way such arguments of knowledge work is outside the scope of this writeup. For more on this topic, this blog post provides a great overview with a lot of details.

For the purposes of the private transactions, in the most naive way, the argument of knowledge can have the following form:

Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2,

I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2 and a private key x,

That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to x, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2.

The transaction then consists of merkle_root, out_hash1, out_hash2, argument of knowledge, and nothing in the transaction reveals the recipients of the output UTXOs nor links the output UTXOs to the particular input UTXOs. Moreover, even the amount transacted is not revealed in the transaction.

For example, in the figure above, say the first and third UTXOs in the merkle tree have Alice as the recipient and amounts of $100 and $17 correspondingly. Alice knows those two UTXOs but has no insight into any other UTXO in the tree. If she wants to send $42 to Bob, she creates a transaction that uses both of her UTXOs as inputs and creates two new outputs: one sending $42 to Bob and another sending the remaining $75 to herself. She reveals the UTXO that is intended for Bob to Bob. But the remaining UTXOs are not known to anyone but her. Moreover, even the hashes of the input UTXOs are not revealed to anyone.

The smart contract that maintains the pool, once it receives such a transaction, verifies the argument of knowledge. If it checks out, it appends the two new UTXOs to the tree:

Once Bob receives the UTXO from Alice, he waits until the hash of the UTXO appears in the tree. Once it does, Bob has the tokens.

The problem with this naive approach is that the same input UTXO can be spent twice. Since nobody but Alice knows the hashes of the input UTXOs, the pool cannot remove the spent UTXOs from the merkle tree because it doesn’t know what to remove to begin with. 

If Alice creates two different zero-knowledge arguments that both spend the same two inputs, everybody will be able to verify that both transactions spend some UTXOs existing in the merkle tree but will have no insight into the fact that those UTXOs are the same in the two transactions.

To address this problem, we add a concept of a nullifier. In the simplest form for a particular UTXO the nullifier is a hash of the UTXO and the private key of the receiver of that UTXO. We then change the argument of knowledge for the transaction to the following:

Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2, and two more hashes NULLIFIER1 and NULLIFIER2

I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2 and a private key x,

That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to x, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2, and hash (IN1, x) is equal to NULLIFIER1 and hash (IN2, x) is equal to NULLIFIER2

Note that any transaction that spends a particular UTXO will have the same NULLIFIER computed because the NULLIFIER only depends on the hash of the UTXO and the private key that uniquely corresponds to the public key in the UTXO. And since the NULLIFIER in the argument of knowledge above is in the “Given” clause, which is public, if two transactions that spend the same UTXO are ever published, everybody will be able to observe that they have the same NULLIFIER and discard the later of the two transactions.

Also note that, for as long as the hash used to compute it is preimage resistant, the NULLIFIER reveals nothing about either the input UTXO or the private key of the receiver.

Depositing, Withdrawing

The transactions described above work great to move assets within the pool. But for the pool to be of any use, there must be a way to move assets from outside the pool into the pool and from the pool back outside of it.

To that extent, the private transaction format is extended to have an extra field called delta, such that the sum of the amounts in input UTXOs is equal to the sum of the amounts in the output UTXOs plus delta:

Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2, two more hashes NULLIFIER1 and NULLIFIER2 and a value delta

I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2 and a private key x,

That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to x, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2 plus delta, and hash (IN1, x) is equal to NULLIFIER1 and hash (IN2, x) is equal to NULLIFIER2

Note that the delta is in the given clause and is thus public.

When such a transaction is processed on NEAR, if the delta is negative (i.e., so that more tokens enter the private transaction than exit it), the extra tokens are deposited to the sender’s account. If the delta is positive (i.e., more tokens exit the transaction than enter it), such a transaction is only valid if the remaining tokens are attached to it.

Transaction fees

Private transactions do not allow linking between the newly created UTXOs and the UTXOs that were used as inputs. However, for any transaction to be included on the NEAR chain, the transaction sender must pay for gas and thus must have native NEAR tokens in the sending account. Those tokens somehow got to that account, which creates linkability and largely defeats the purpose of the private transactions.

To address the problem, we introduce a new role in the system called relayer

Say Alice wants to send a transaction to Bob and wants to use Ryan as the relayer. The gas fee for the transaction is less than Ⓝ1 and Alice is willing to pay Ryan Ⓝ1 for submitting the transaction to the chain.

Alice, who might not have an account on NEAR at all, creates a private transaction in which the sum of the two input UTXO amounts is Ⓝ1 less than the sum of the output UTXO amounts. The remaining Ⓝ1 is withdrawn to the account of the submitter of the transaction. Ryan collects the transaction from Alice, confirms the validity of the transaction, and submits it from his account, spending less than Ⓝ1 in gas but receiving Ⓝ1 as the result of the transaction.

Alice ends up submitting the transaction without revealing herself and Ryan receives a small payout. Note that no party needs to trust the other in this interaction: Ryan cannot tamper with the transaction in any way and thus can only either submit it or do nothing. So, the biggest risk for Alice is the possibility that her transaction is not submitted (in which case she can ask another relayer to submit it). Ryan verifies the transaction before submitting it and thus doesn’t risk spending gas and not receiving his payment unless another relayer front ran them.

Further improvements

The model described so far is a fully functional pool for private transactions. In this section, I will briefly mention several other aspects that improve the security or usability of the pool:

Discovering payments

When describing the transactions above, I mentioned that when Alice sends tokens privately to Bob, she shares the newly created UTXO with him. This requires Alice communicating with Bob off-chain, which is undesirable. Instead, the pool can be extended to store all the UTXOs encrypted with the public keys of their recipients. When Alice sends money to Bob and creates two new UTXOs, she encrypts the UTXO that has Bob as the recipient with Bob’s public key.

On his end, Bob monitors all the newly created UTXOs and tries to decrypt each one with his private key. Once he gets to the UTXO created by Alice, the decryption succeeds, and Bob discovers their UTXO using exclusively on-chain communication.

Decoupling signing and proving

When Alice creates a transaction, she needs to create a complex proof that in particular uses the knowledge of her private key. Thus, the machine that computes the proof needs access to the private key, which is undesirable. 

Generally, it is preferable to have the private keys on some external hardware device that only has limited functionality, such as signing messages. Computing arguments of knowledge is generally way outside the capabilities of such hardware devices.

To accommodate these devices, we make the key generation create three keys instead of two:

Private Key, Decryption Key, Public Key

Here, a message encrypted with the Public Key can be decrypted with the Decryption Key. Similarly, a signature created with the Private Key can be verified having access to the Decryption Key. Only the public key is revealed publicly. The decryption key is stored on the device that computes transaction proofs and the private key is stored on the external device that can only sign messages.

We can then alter the argument of knowledge in the following way:

Given the merkle root, and two hashes OUT_HASH1 and OUT_HASH2, and two more hashes NULLIFIER1 and NULLIFIER2

I know four such UTXOs IN1, IN2, OUT1, OUT2, two merkle proofs P1 and P2, a decryption key d and a signature s,

That hashes of OUT1 and OUT2 are correspondingly OUT_HASH1 and OUT_HASH2, and the receiver in IN1 and IN2 is equal to the public key X that corresponds to d, and the merkle proofs P1 and P2 are valid proofs of inclusion of IN1 and IN2 in a tree with the given merkle root, and the sum of amounts in IN1 and IN2 is equal to the sum of amounts in OUT1 and OUT2, and hash (IN1, d) is equal to NULLIFIER1 and hash (IN2, d) is equal to NULLIFIER2, and s is a signature on a message (IN1, IN2, OUT1, OUT2) that is valid against d

When Alice then wants to create a transaction, she uses the hardware device to sign (IN1, IN2, OUT1, OUT2). She then uses the signature s to generate the proof on the machine that only has access to the decryption key.

Note that without access to the hardware device one cannot generate s and thus cannot spend money—even if they get access to the machine that is used for proving.

Supporting more tokens

The private transactions are not limited to the native NEAR tokens. With a very slight modification, the pool can be generalized to support any tokens using the same anonymity pool for all of them. The exact construction is outside the scope of this write-up, however.

Outro

Besides collaborating with NEAR, ZeroPool also builds private transactions for Ethereum and is primarily funded by the community. Consider supporting them on Gitcoin.

Educational Materials

This write-up is part of an ongoing effort to create high-quality educational materials about blockchain protocols. Check out this video series in which we dive deep into the design of various protocols—such as Ethereum, Cosmos, Polkadot, and others—as well as our other technical write-ups.

Supporting Early Stage Blockchain Companies

If you are an entrepreneur in the web3 space, consider joining our accelerator with mentors from tier1 companies and investment firms in the space: http://openwebcollective.com/. We help with all the aspects of building the business, including identifying the market, business development, marketing, and fundraising.

Stay in Touch

We are NEAR, an open source sharded blockchain protocol. You can deploy your first fully functional decentralized application to NEAR within minutes from our fully functional web-based IDE.

 

Follow us on Twitter to get updates about our new educational materials, while keeping tabs on our progress toward the decentralized future.

Introduction

Back in 2015, DFinity made the community extremely excited with their design of a randomness beacon that was leveraging BLS threshold signatures to produce a randomness output that is both unbiased and unpredictable.

As of 2020 building an unbiased and unpredictable randomness beacon remains extremely challenging, and very few protocols have one live. Threshold signatures are not the only proposed approach, and we previously published a short overview of various other approaches to randomness, including an approach that we considered back then in this blog post. Refer to it for the details on what the randomness beacon is, what it means to be unbiased and unpredictable, and what approaches besides threshold signatures were proposed.

After multiple iterations of design, we ultimately ended up building something very similar to what DFinity uses, and that is a great opportunity to dive deep into how such randomness beacons work.

In this article, we will describe the complex protocol of using threshold signatures to generate random numbers in very simple terms. Let’s dive in!

Crypto Fundamentals

For the purpose of understanding randomness beacons in this article, we will need to understand some very basic cryptography. We need to differentiate between two concepts: scalars, or just regular numbers, which throughout this article we will denote with lowercase letters (e.g. x, y) and elliptic curve points, which we will denote with uppercase letters.

We don’t need to understand much about elliptic curve points, besides a few properties:

  1. Elliptic curve points can be added together, and an elliptic curve point can be multiplied by a scalar (we will denote it as xG, though a notation Gx is also very common). The result of both operations is another elliptic curve point.
  2. Knowing G and xG it is computationally infeasible to derive x.

We will also be using a concept of a polynomial p(x) of degree k-1. For the purposes of this article it is sufficient to think about it as a function p(x) such that if one knows the value of p(x) at any k distinct values of x, they can also derive p(x) at any other x as well.

Interestingly, for the same function, and some elliptic curve point G, if one knows the value of p(x)G at any k distinct values of x, they can also derive p(x)G at any other x.

Those are the only properties of elliptic curve points we will need to understand on the high level how randomness beacons work.

The Randomness Beacon

Say there are n participants, and say we want to require that it takes at least k of them to generate a random number and that an adversary that controls up to k-1 of the participants cannot predict the output of the randomness beacon, and cannot influence it in any way.

Say there exists some polynomial p(x) of degree k-1 such that the first participant knows p(1), the second participant knows p(2), and the n-th participant knows p(n). Also, say that for some agreed-upon elliptic curve point G everybody knows p(x)G for all values of x. We will call p(i) a private share of participant i (because the only participant i knows it), and p(i)G public share of participant i (because everybody knows it). Recall from the previous section that the knowledge of p(i)G is not sufficient to derive p(i).

Generating such a polynomial in a way that each participant knows their private share, but has no insight into the private shares of other participants is the most complex part of the randomness beacon, and is what is called Distributed Key Generation. We will cover it in the next section. For now, let’s assume such a polynomial exists, and all the participants know their shares.

Let’s see how to use it to have a randomness beacon in the context of a blockchain protocol. Say a block with hash h is produced, and the participants collectively want to generate a random number seeded by h. The way they proceed is first to use some agreed-upon function to convert h into an elliptic curve point:

H = scalarToPoint(h)

Then each participant i computes H_i = p(i)H, which they can do because they know p(i) and H. Revealing H_i will not reveal their private share, so the same private shares can be reused for each block, thus the DKG only needs to be performed once.

When at least k participants revealed their shares H_i = p(i)H, everyone can reconstruct any share H_x = p(x)H for any x due to the third property in the previous section. At this point, each participant can locally compute H_0 = p(0)H, and use the hash of it as the randomness beacon output. Note that since no participant knows p(0), the only way to compute p(0)H is to interpolate p(x)H, which is only possible if at least k of p(i)H were revealed. Revealing any smaller number of p(i)H gives no insight into the value of p(0)H.

The beacon above has all the properties we desire: an adversary controlling k-1 or fewer participants cannot get any insight into the final output of the randomness beacon, while any k participants can compute the final output, and any subset of k or more participants will always arrive at the same value.

There is one issue we ignored above. For the interpolation to work, we need to make sure that the value H_i that the i-th participant revealed is indeed equal to p(i)H. Since no other participant knows p(i), they cannot naively verify that H_i is indeed correct, and without some cryptographic proof alongside H_i a malicious actor can reveal arbitrary value, and other participants will have no way of detecting it.

There are at least two ways to provide a cryptographic proof of H_i being correct, we will cover both of the two sections below after we talk about DKG.

Distributed Key Generation

For the randomness beacon in the previous section to work, we needed n participants to collectively come up with a polynomial p(x) of degree k-1 such that each participant i knows the value of p(i), but no other participant has any insight into that value. For the constructions in the next section, it will also be necessary that all the participants know p(x)G for some agreed-upon G and all x.

Throughout this section, we assume that every participant has some private key x_i associated with them, and all the participants know the public key X_i that corresponds to such a private key.

One way to go about DKG is then the following:

  1. Each participant i locally computes some polynomial p_i(x) of degree k-1. They then send p_i(j) to each participant j encrypted with the public key X_j, so that only j-th participant can decode p_i(j). Participant i also publicly announces p_i(j)G for all j from 1 to k inclusive.
  2. All the participants collectively agree on some set of at least k such committed polynomials. Since some participants can be offline, they can’t wait until all n of them commit, but once at least k have committed, they can use any sort of consensus algorithm (for example Tendermint) to agree on some subset Z of at least k polynomials.
  3. The participants collectively verify that the encrypted p_i(j) corresponds to the publicly announced p_i(j)G. The polynomials for which it is not the case are removed from Z.
  4. Each participant j computes their private share p(j) as the sum of p_i(j) for each i in Z. Each participant can also compute each public share p(x)G as the sum of p_i(x)G for each i in Z.

Observe that p(x) is indeed a polynomial of degree k-1, because it is the sum of individual p_i(x), each of which is a polynomial of degree k-1. Then, note that while each participant j knows p(j), they have no insight into the values of other p(x) for x ≠ j. Indeed, to know such a value they’d need to know all p_i(x), and for as long as the participant j doesn’t know at least one of the committed polynomials, they don’t have any information about p(x).

This constitutes the entirety of the DKG process. Steps 1, 2 and 4 above are relatively straightforward. Step 3 is where DKG gets tricky.

Specifically, we need some way to prove that each encrypted p_i(j) indeed corresponds to the publicly broadcasted p_i(j)G. Without a way to verify it, an adversary i can send some gibberish information to participant j instead of actually encrypted p_i(j), and participant j will have no way to compute their private share later.

There’s a way to create a cryptographic proof of the correctness of the encrypted share. However, the size of such a proof is prohibitively large, and given that O(nk) such proofs need to be published, the size of the proof becomes a bottleneck.

Instead of proving cryptographically that p_i(j) corresponds to p_i(j)G in NEAR we instead allocate a lot of time during DKG between the moment the set of polynomials is agreed upon and the moment the final shares are aggregated, during which each participant can provide a cryptographic proof that the encrypted share p_i(j) sent to them doesn’t correspond to the publicly broadcasted p_i(j)G. It makes an assumption that each participant will go online at least once during that time frame (which spans approximately half a day), and that the challenge they submit will make it to the blockchain. In the case of block producers, both assumptions are rather realistic, since the block producers are expected to remain online throughout the epoch, and for a message to be censored majority of block producers need to collude and not include it in their blocks, in which case they have significantly more profitable ways to attack the system.

If a particular block producer does receive an invalid share and then fails to show up during DKG and challenge it, they will not be able to participate in generating random numbers during the same epoch. Note that for as long as k other honest participants have their shares (by either not receiving any invalid shares, or challenging all the invalid shares in time), the protocol will still function.

Proofs

The last part of the randomness beacon that is still left uncovered is how one can prove that a published value H_i is equal to p(i)H without revealing p(i).

Recall that the values H, G, p(i)G are all known to everybody. The operation that computes p(i) given p(i)G and G is called discrete logarithm, or dlog for short, and what each participant wants to prove to others is that

dlog(p(i)G, G) = dlog(H_i, H)

Without revealing p(i). Constructions for such proof do exist, one such construction is called Schnorr Protocol.

With such a construction, whenever a participant submits H_i, they also submit proof of correctness of H_i.

Recall that the final randomness beacon output is the interpolated value of H_0. What information needs to be distributed along with H_0 for external participants that didn’t participate in the generation of it to be able to verify its correctness? Since everybody can locally interpolate G_0, a proof that

dlog(G_0, G) = dlog(H_0, H)

would suffice, but we cannot use the Schnorr Protocol to create such a proof since it requires the knowledge of p(0), and the randomness beacon relies on nobody knowing the value. Thus, one needs to keep all the values of H_i along with the corresponding proofs to prove the correctness of H_0 to external observers.

However, if there was some operation that semantically resembled multiplication on elliptic curve points, proving that H_0 was computed correctly would become trivial, by just verifying that

H_0 × G = G_0 × H

If the chosen elliptic curve supports so-called elliptic curve pairings, such a proof becomes possible. In such a case H_0 not only serves as an output of the randomness beacon that can be trivially verified by anyone who knows G, H and G_0 but also it serves as a collective multi-signature that attests that at least k out of n block producer signed the block.

We do not use elliptic curve pairings in NEAR today, though we might use them in the future, and then the neat trick discussed above would replace the individual signatures we use today. DFinity, on the other hand, uses BLS signatures and can leverage the pairings to make such multi signatures work.

Outro

The implementation of the randomness beacon is mostly complete in our reference client implementation (see this commit), however, the first version of the NEAR Protocol will likely launch without it, to allow more time for stabilization of the beacon. Once it is shipped, however, all the contracts on NEAR will enjoy access to unbiasable and unpredictable random number generator, which enables many uses cases not possible today on other networks.

The first release of the NEAR Protocol will use a significantly simpler randomness beacon (see this pull request), where the random value is just the output of a verifiable random function on the previous output of the random beacon by the current block producer. Such a randomness beacon is unpredictable, but is not unbiasable: the current block producer has one bit of influence because they can choose not to produce a block. It happens to be very similar to the randomness beacon that Ethereum 2.0 will use before they have the VDFs beacon available (the randomness output is the VRF by the current block producer on the epoch hash), and is also the way the randomness beacon works in Elrond.

If you are interested in how blockchain protocols work, check out our Whiteboard Series with NEAR, in which we talk to the founders and core developers of other protocols, such as Ethereum Serenity, Cosmos, Polkadot and many others, and dive deep into the details of their technology. All the video episodes are conveniently assembled into a playlist here.

NEAR Protocol is an infrastructure for the open web and a sharded blockchain protocol. You can learn more about our technology in our sharding design paper, through deep-dive videos, or by exploring our Rust reference client implementation.

Follow @NEARprotocol on Twitter to get notified about new content we post and get the latest updates on the development of the protocol

If you want to get involved, please join the conversation here!

In this blog post, we will see how Doomslug, our new block production technique, compares to PBFT, Tendermint, and Hotstuff. We will also dig relatively deep into how PBFT, Tendermint and Hotstuff work, cover view changes, pipelining, responsiveness and some other details.

On the last day of the previous decade, we published a paper called Doomslug in which we proposed a new way of producing blocks that allows us to achieve some sense of practical finality after just one round of communication, with a finality gadget providing full BFT finality after the second round.

What we refer to as practical finality, or doomslug finality is that a block produced by Doomslug is irreversible unless at least one participant is slashed. Doomslug also has a nice property that it continues producing and finalizing blocks for as long as just over half of all the participants are online and honest, not ⅔ as required by BFT consensus algorithms (though the finality gadget of course stalls if less than ⅔ of participants are online).

Now that the Doomslug implementation in NEAR is completed, it is a good time to discuss how it works, and how it compares to other approaches. Specifically, we will compare it to Tendermint and HotStuff.

If you have questions while you read, feedback is encouraged. Ask your questions and join the discussion here.

How Doomslug works

In short, Doomslug works by having a set of participants take turns to produce and broadcast  blocks. Once a block at height h is received by other participants, they send endorsements on such a block to the participant assigned to the next height h+1. If after some predetermined time the participant assigned to h+1 hasn’t produced a block, the participants who sent an endorsement to her send another message to the participant assigned to h+2 indicating that they suggest skipping the block at h+1.

Once a participant has endorsements or skip-messages from more than half of other participants, they can produce their block.

With careful handling of message delays and exact slashing conditions, this rather simple technique can provide the property that we discussed above: if a block produced by Doomslug contains endorsements on the previous block from more than half of the block producers, the previous block is irreversible unless at least one of the block producers is slashed. Moreover, it is guaranteed that even if the network is slow, and messages are delayed, a block that contains endorsements from more than half the block producers will be created at some point, so the algorithm never stalls.

As mentioned above, there’s a finality gadget that operates together with Doomslug. Under normal circumstances once a block at height `h+1` is produced, and the block at height `h` has doomslug finality, the block at height `h-1` will have a full BFT finality. In other words, at least ⅓ of the total stake would need to be slashed to revert it. We will see how it compares to other consensus algorithms two sections below.

Both Doomslug and the finality gadget guarantees around blocks irreversibility do not make any assumptions about how slow or reliable the network is. In other words, both Doomslug and the finality gadget have safety under asynchronous network assumption. However, the guarantee that they cannot stall (a property called “liveness”) assumes a partially synchronous network. It is a rather common assumption, and all the consensus algorithms discussed in this post make this assumption in their liveness proofs. Having both guaranteed safety and liveness under asynchronous network is impossible, a limitation known as FLP impossibility.

A Short primer on PBFT, Tendermint, and Hotstuff

Before we dig into the comparison of Doomslug with Tendermint and Hotstuff, let’s do a quick review of how they work.

In a good case PBFT, Tendermint and Hotstuff all work in a very similar manner:

The consensus protocol happens over multiple views, optimistically in just one view. In each view there’s a particular leader who is assigned to carry out the consensus. The leader proposes a particular outcome. In the first view the choice of outcome is arbitrary. The leader sends the proposed outcome to all the remaining participants, and they send back their pre-vote on the outcome. The participants wait until there are pre-votes on the outcome from ⅔ of them, and then each participant sends a pre-commit on the outcome. Once there are pre-commit messages from ⅔ of participants, the consensus is reached.

The way the participants exchange messages differs between protocols. In Tendermint the participants use the gossip protocol, and each participant accumulates the pre-vote and pre-commit messages locally, while in Hotstuff the leader accumulates messages and sends them back.

The entire process can be made with just a linear amount of network overhead. Indeed, if the leader accumulates the pre-votes and pre-commits, then the initial broadcast of the proposed outcome, as well as other participants communicating back their pre-votes and pre-commits is already linear. The only quadratic overhead naively is sending accumulated pre-votes and accumulated pre-commits, but this can be done with linear overhead as well, if the accumulated messages are compressed using e.g. BLS signatures.

If for any reason the leader fails to carry out the consensus, it moves to the next view, in which the next leader will attempt again. The view change is where Hotstuff and Tendermint differ significantly from PBFT. In PBFT each participant has a timer that measures how much time has passed since the beginning of the view, and once the timer crosses a certain threshold, they send a view-change message to the next leader. The next leader needs to accumulate the view-change messages from ⅔ of the participants and send back a new-view message to them. This entire procedure requires at least cubic network overhead, and is also rather hard to implement correctly.

Tendermint and Hotstuff handle the view changes differently. Instead, there are timeouts in each phase (pre-vote and pre-commit), and whenever such a timeout is triggered, the participant sends a corresponding pre-vote or a pre-commit on nil, and moves to the next phase or view locally. Thus, the view-change is not an orchestrated process, and is rather implicit. Importantly, the mechanism for the view-change and for committing the block is essentially the same, which significantly simplifies the algorithm.

There are two major differences between Tendermint and Hotstuff. One is that Hotstuff is pipelined, meaning that a pre-commit of one view is a pre-vote for the next one, requiring almost twice as few phases as a non-pipelined version. There are proposals to make Tendermint pipelined, but the way it is implemented in Cosmos and presented in the paper are not pipelined. Second, and more frequently discussed, the difference is the fact that Hotstuff has so-called responsiveness, in other words, that an honest leader will always have the consensus reached in time bounded by the network delays, not timeouts. In Tendermint it is not the case, because in the pre-commit phase if a participant observes pre-commits on nil from ⅔ of the participants, they cannot move to the next view until the timeout expires, otherwise, an adversary with careful control of the network can make the algorithm switch between views indefinitely.

The responsiveness, while a neat feature, is somewhat misleading. Specifically, it only guarantees that the time it will take for the consensus to be reached will be bound by network delays if the leader is online and honest. If the leader is offline, the system will still wait the full timeout to move to the next view. In practice in Cosmos, which has been running a large instance of Tendermint for a long time presently, all the view-changes that ever occurred were due to the offline leader, and never due to the pre-commit on nil, thus the responsiveness of Hotstuff would have never mattered in Cosmos up to date.

I’m also not diving deep here into the fact that Hotstuff requires an extra round of communication to achieve responsiveness. In the first view, such an extra round can be omitted, and in the second view it is compensated with pipelining, thus the extra round rarely becomes an issue.

Doomslug vs Tendermint and Hotstuff

The optimistic case

Now let’s compare how Doomslug with a finality gadget compares to Tendermint and Hotstuff under various conditions. First, let’s consider the case in which no view-changes occur, and all the messages reach the leaders in time.

In the figure above, grey blocks are proposed blocks, blue blocks are blocks that have BFT finality, and yellow blocks are blocks that have doomslug finality.

Under normal circumstances Hotstuff and Tendermint behave exactly the same way: after a block is proposed, within two rounds of communication the block is final, and after two more rounds the block that immediately follows it is also final. Note that Hotstuff doesn’t pipeline across blocks, only across views, and thus producing two blocks still requires four rounds, not three.

Doomslug doesn’t improve on latency to full BFT finality, and thus since the moment the first block is produced, it still takes two rounds of communication until it has the full BFT finality. As discussed above, however, after the first round of communication the block already has a weaker than BFT sense of finality that we refer to as “doomslug finality”, in other words, it is irreversible unless at least one block producer is slashed.

Also note that by nature of finality gadgets, their throughput is the same as the underlying block production, and thus after three rounds of communication there are already two blocks that have full BFT finality, and after four rounds there are three such blocks. In other words, while it takes the same time for Doomslug with the finality gadget to reach full BFT finality on a single block, it finalizes twice as many blocks as Tendermint or Hotstuff per long period of time. While it doesn’t improve on latency, it improves the throughput by a factor of two.

The less optimistic case

Now let’s see what happens in a less optimistic case, in which either some participants are offline, or a view fails for another reason. In the figure above, we show the case in which two consecutive views have failed. In the case of Tendermint, each failed view adds two rounds of communication, and thus it will take six rounds of communication to finalize a block. In the case of Hotstuff, the pipelining kicks in, and the block will be finalized after just four rounds of communication. Due to finality gadgets having the same throughput as the underlying block production, Doomslug with the finality gadget enjoys the same pipelining, and will also finalize the block after four rounds of communication. It is the case, however, that after the first three rounds the block will already have “doomslug finality”, and after the fourth round together with the first block reaching BFT finality, a block built on top of it will already have doomslug finality as well.

Other considerations

Above we covered one dimension on which block production and consensus algorithms can be compared: the number of rounds to finality under different conditions. There are other considerations. For example, while all the consensus algorithms discussed in this post have liveness (in other words are guaranteed not to stall under certain practical conditions), their exact behavior in presence of network delays and interruptions differs. The amount of time it takes to recover after a period of long loss of connectivity can vary noticeably. Our simulated tests show that Doomslug recovers quickly after long periods of network inactivity (the simulation code can be found here), but generally, very little research was done on comparing the consensus protocols from this perspective.

Another dimension is implementation complexity. With an assumption that ⅓ of all the block producers, weighted by stake, can never become corrupted, a protocol built on Tendermint or Hotstuff doesn’t need to implement any logic to handle forks. Doomslug finalizes blocks slower than it produces them, and therefore forks are possible until the blocks are actually final. Correspondingly, the protocol needs to be able to handle such forks, which noticeably increases the complexity of the implementation. In case of NEAR, we switched to Doomslug from a flavor of longest chain protocol, and thus already had all the logic of handling forks and an intensive test coverage for it implemented, but for a new effort to build a protocol not having to deal with forks can result in a considerable reduction of implementation cost.

Outro

Check out our Whiteboard Series with NEAR, in which we talk to the founders and core developers of other protocols, such as Ethereum Serenity, Cosmos, Polkadot and many others, and dive deep into the details of their technology. All the video episodes are conveniently assembled into a playlist here.

NEAR Protocol is an infrastructure for open web and a sharded blockchain protocol. You can learn more about our technology in our sharding design paper, through deep-dive videos, or by exploring our Rust reference client implementation.

Follow @NEARprotocol on Twitter to get notified about new content we post, and get the latest updates on the development of the protocol.

If you want to get involved, please join the conversation here!

Thanks to Zaki Manian and Ethan Buchman from Tendermint for reviewing an early draft of this post and providing feedback!

In this blog post we briefly discuss the concept of long range attacks, which is considered to be one of the biggest unsolved problems in Proof-of-Stake protocols. We then cover two solutions presently used in live or proposed protocols, namely weak subjectivity and forward-secure keys. Finally, we present a new fork choice rule that makes long range attacks significantly more expensive. The fork choice rule presented can be combined with either or both existing solutions, and can serve as an extra measure against the long range attacks.

This write-up is part of an ongoing effort to create high quality technical content about blockchain protocols and related topics. See our blog posts on Layer 2 approaches, Randomness, and our sharding paper that includes a great overview of the current state of the art.

Follow us on Twitter or join our discord channel to make sure you don’t miss the updates.

Long Range Attacks

Proof-of-Work with the heaviest chain fork choice rule has a very desirable property that no matter what malicious actors do, unless they control more than 50% of the hash power, they cannot revert a block that was finalized sufficiently long ago.

Proof-of-Stake systems do not have the same property. In particular, after the block producers that created blocks at some point in the past get their staked tokens back, the keys that they used to create blocks no longer have value for them. Thus, an adversary can attempt to buy such keys for a price significantly lower than the amount of tokens that was staked when the key was used to produce blocks. Since, unlike in Proof-of-Work, Proof-of-Stake has no mechanism to force a delay between produced blocks, the adversary can then in minutes create a chain that is longer than the canonical chain, and have such chain chosen by the fork choice rule.

There are two primary ways to get around this problem:

Weak subjectivity. Require that all the nodes in the network periodically check what is the latest produced block, and disallow reorgs that go too far into the past. If the nodes check the chain more frequently than the time it takes to unstake tokens, they will never choose a longer chain produced by an adversary who acquired keys for which the tokens were unstaked.

The weak side of the weak subjectivity approach is that while the existing nodes won’t be fooled by the attacker, all the new nodes that spin up for the first time will have no information to tell which chain was created first, and will choose the longer chain produced by the attacker. To avoid it, they need to somehow learn off-chain about the canonical chain, effectively forcing them to identify someone whom they trust in the network.

Forward-secure keys. Another approach is to make the block producers destroy the keys that they used to produce blocks immediately or shortly after the blocks were produced. This can be done by either creating a new key pair every time the participant creates blocks, or by using a construction called Forward-secure keys, which allows a secret key to change while the corresponding public key remains constant.

This approach relies on nodes being honest and following protocol strictly. There’s no incentive for them to destroy their keys, since they know in the future someone might attempt to buy them, thus the key has some non-zero value. While it is unlikely that a large percentage of block producers at a certain moment all decide to alter their binaries and remove the logic that wipes the keys, a protocol that relies on the majority of participants being honest has different security guarantees than a protocol that relies on the majority of participants being reasonable. Proof-of-work works for as long as more than half of the participants are reasonable and do not cooperate, and it is desirable to have the fork choice rule and a Sybil resistance mechanism that have the same property.

Proposed Fork-Choice Rule

Consider the figure below. There’s a block B sufficiently far in the past on the canonical chain such that the majority (or all) the block producers who were building the chain back when B was produced have their stake unstaked.

The adversary reaches out to all those block producers and acquires the private keys of ~⅔ of them. At that point the keys have no value to the block producers, so the adversary can purchase them for a price significantly lower than the actual amount that was staked.

The adversary then uses the keys to build a longer chain. Since no scarce resource is used in a Proof-of-Stake system, the adversary can do it very quickly.

We want a fork choice rule such that no matter how long the chain the adversary has built is, and how many of the corrupted validators signed on it, no client, including the clients that start for the first time, will see the chain built by the adversary as the canonical.

The proposed fork choice rule is the following: start from the genesis, and at each block greedily choose one of its children as the next block by doing the following:

  1. Snapshot the state as of after the current block is applied.
  2. Enumerate all the accounts that have tokens at that moment, as a list of pairs (public key, amount).
  3. For each child block, identify all the public keys from the set that signed at least one transaction in the subtree of that child block.
  4. Choose the child block for which the score, computed as the sum of the amounts on the accounts that signed at least one transaction in its subtree, is the largest.

In the example above if the current block we consider is B, its child blocks are C1 and C2. The subtree of C1 is all the blocks ever built on the canonical chain, while the subtree of C2 is all the blocks built by the adversary.

The score of the canonical chain will be the sum of all the amounts on the accounts in the snapshot that issued at least one transaction throughout the history of the canonical chain starting from B, including all the money transfers and staking transactions.

The score of the adversarial chain will be the sum of all the amounts on the accounts that made a transaction on the adversarial chain. With a proper replay protection it means that all such transactions will have to be issued by the adversary.

Say the total amount on all the accounts that exist in the snapshot that made at least one transaction on the canonical chain since B is p. Say the adversary managed to purchase the keys for a subset of such accounts such that the total amount on them adds up to q, q < p. Since for the adversary to have a heavier chain they need the total amount of accounts that issued transactions to be more than p, they need to also get a hold of some keys that correspond to accounts with more than p – q tokens for which no transaction was issued on the canonical chain. But since for those accounts no transaction was issued on the canonical chain, the keys for those accounts cannot be acquired for less than the value that was on such accounts in the snapshot, since those accounts still have all the funds that were in the snapshot as of the latest block on the canonical chain.

Thus, if the adversary can realistically acquire the keys as of block B that correspond to 80% of all the accounts that issued at least one transaction on the canonical chain at a discount, they still need to pay the amount of money that is at least 0.2p.

Note that this fork choice rule only works for long range fork decisions, since for the canonical chain to be resilient to forks, it needs to accumulate a large number of accounts issuing transactions. One way to combine it with more classic fork choice rules would be to first build a subset of the blockchain that only consists of blocks finalized by a BFT finality gadget, run the fork choice rule described above on such a sub-blockchain, and then starting from the last finalized block on the chain chosen by the fork choice rule use a more appropriate fork choice rule, such as LMD GHOST.

Outro

The fork choice rule described above provides an extra level of protection against long range attacks.

This particular fork choice rule, while has interesting properties, needs to be researched further before becoming usable in practice. For instance, it is unclear without further analysis if it provides economic finality.

We are actively researching the approaches to defend against long range attacks presently, and will likely be publishing more materials soon, so stay tuned.

In our continuous effort to create high quality technical content, we run a video series in which we talk to the founders and core developers of other protocols, we have episodes with Ethereum Serenity, Cosmos, Polkadot, Ontology, QuarkChain and many others. All the episodes are conveniently assembled into a playlist here.

If you are interested to learn more about technology behind NEAR Protocol, make sure to check out our sharding paper and our randomness beacon. NEAR is one of the very few protocols that addresses the state validity and data availability problems in sharding, and the sharding paper contains great overview of sharding in general and its challenges besides presenting our approach.

While scalability is a big concern for blockchains today, a bigger concern is usability. We invest a lot of effort into building the most usable blockchain. We published an overview of the challenges that the blockchain protocols face today with usability, and how they can be addressed here.

Follow us on Twitter and join our Discord chat where we discuss all the topics related to tech, economics, governance and other aspects of building a protocol.

We have published today a short paper that describes the randomness beacon that is used in NEAR Protocol. In this accompanying blog post we discuss why randomness is important, why it is hard, and how it is addressed in other protocols.

Many modern blockchain protocols, including NEAR, rely on a source of randomness for selecting participants that carry out certain actions in the protocol. If a malicious actor can influence such source of randomness, they can increase their chances of being selected, and possibly compromise the security of the protocol.

Distributed randomness is also a crucial building block for many distributed applications built on the blockchain. For example, a smart contract that accepts a bet from a participant, and pays out twice the amount with 49% and nothing with 51% assumes that it can get an unbiasable random number. If a malicious actor can influence or predict the random number, they can increase their chance to get the payout in the smart contract, and deplete it.

When we design a distributed randomness algorithm, we want it to have three properties:

  1. It needs to be unbiasable. In other words, no participant shall be able to influence in any way the outcome of the random generator.
  2. It needs to be unpredictable. In other words, no participant shall be able to predict what number will be generated (or reason about any properties of it) before it is generated.
  3. The protocol needs to tolerate some percentage of actors that go offline or try to intentionally stall the protocol.

In this article we will cover the basics of distributed random beacons, discuss why simple approaches do not work. Finally, we will cover the approaches used by DFinity, Ethereum Serenity, and NEAR and discuss their advantages and disadvantages.

RANDAO

RANDAO is a very simple, and thus quite commonly used, approach to randomness. The general idea is that the participants of the network first all privately choose a pseudo-random number, submit a commitment to such privately chosen number, all agree on some set of commitments using some consensus algorithm, then all reveal their chosen numbers, reach a consensus on the revealed numbers, and have the XOR of the revealed numbers to be the output of the protocol.

It is unpredictable, and has the same liveness as the underlying consensus protocol, but is biasable. Specifically, a malicious actor can observe the network once others start to reveal their numbers, and choose to reveal or not to reveal their number based on XOR of the numbers observed so far. This allows a single malicious actor to have one bit of influence on the output, and a malicious actor controlling multiple participants have as many bits of influence as the number of participants they are controlling.

RANDAO + VDFs

To make RANDAO unbiasable, one approach would be to make the output not just XOR, but something that takes more time to execute than the allocated time to reveal the numbers. If the computation of the final output takes longer than the reveal phase, the malicious actor cannot predict the effect of them revealing or not revealing their number, and thus cannot influence the result.

While we want the function that computes the randomness to take a long time for the participants that generate the random number, we want the users of the random number to not have to execute the same expensive function again. Thus, they need to somehow be able to quickly verify that the random number was generated properly without redoing the expensive computation.

Such a function that takes a long time to compute, is fast to verify the computation, and has a unique output for each input is called a verifiable delay function (VDF for short) and it turns out that designing one is extremely complex. There’ve been multiple breakthroughs recently, namely this one and this one that made it possible, and Ethereum presently plans to use RANDAO with VDF as their randomness beacon. Besides the fact that this approach is unpredictable and unbiasable, it has an extra advantage that is has liveness even if only two participants are online (assuming the underlying consensus protocol has liveness with so few participants).

The biggest challenge with this approach is that the VDF needs to be configured in such a way that even a participant with very expensive specialized hardware cannot compute the VDF before the reveal phase ends, and ideally have some meaningful safety margin, say 10x. The figure below shows an attack by a participant that has a specialized ASIC that allows them to run the VDF faster than the time allocated to reveal RANDAO commitments. Such a participant can still compute the final output with and without their share, and choose to reveal or not to reveal based on those outputs:

For the family of VDFs linked above a specialized ASIC can be 100+ times faster than conventional hardware. Thus, if the reveal phase lasts 10 seconds, the VDF computed on such an ASIC must take longer than 100 seconds to have 10x safety margin, and thus the same VDF computed on the conventional hardware needs to take 100 x 100 seconds = ~3 hours.

The way Ethereum Foundation plans to address it is to design its own ASICs and make them publicly available for free. Once this happens, all other protocols can take advantage of the technology, but until then the RANDAO + VDFs approach is not as viable for protocols that cannot invest in designing their own ASICs.

This website accumulates lots of articles, videos and other information on VDFs.

Threshold Signatures

Another approach to randomness, pioneered by Dfinity, is to use so-called threshold BLS signatures. (Fun fact, Dfinity employs Ben Lynn, who is the L in BLS).

BLS signatures is a construction that allows multiple parties to create a single signature on a message, which is often used to save space and bandwidth by not requiring sending around multiple signatures. A common usage for BLS signatures in blockchains is signing blocks in BFT protocols. Say 100 participants create blocks, and a block is considered final if 67 of them sign on it. They can all submit their parts of the BLS signatures, and then use some consensus algorithm to agree on 67 of them and then aggregate them into a single BLS signature. Any 67 parts can be used to create an accumulated signature, however the resulting signature will not be the same depending on what 67 signatures were aggregated.

Turns out that if the private keys that the participants use are generated in a particular fashion, then no matter what 67 (or more, but not less) signatures are aggregated, the resulting multisignature will be the same. This can be used as a source of randomness: the participants first agree on some message that they will sign (it could be an output of RANDAO, or just the hash of the last block, doesn’t really matter for as long as it is different every time and is agreed upon), and create a multisignature on it. Until 67 participants provide their parts, the output is unpredictable, but even before the first part is provided the output is already predetermined and cannot be influenced by any participant.

This approach to randomness is completely unbiasable and unpredictable, and is live for as long as 2/3 of participants are online (though can be configured for any threshold). While ⅓ offline or misbehaving participants can stall the algorithm, it takes at least ⅔ participants to cooperate to influence the output.

There’s a caveat, however. Above, I mentioned that the private keys for this scheme need to be generated in a particular fashion. The procedure for the key generation, called Distributed Key Generation, or DKG for short, is extremely complex and is an area of active research. In one of the recent talks, Dfinity presented a very complex approach which involved zk-SNARKs, a very sophisticated and not time tested cryptographic construction, as one of the steps. Generally, the research on threshold signatures and DKGs in particular is not in a state where it can be easily applied in practice.

RandShare

The NEAR approach is influenced by yet another algorithm called RandShare. RandShare is an unbiasable and unpredictable protocol that can tolerate up to ⅓ of the actors being malicious. It is relatively slow, and the paper linked also describes two ways to speed it up, called RandHound and RandHerd, but unlike RandShare itself RandHound and RandHerd are relatively complex, while we wish the protocol to be extremely simple.

The general problems with RandShare besides the large number of messages exchanged (the participants together will exchange O(n^3) messages), is the fact that while ⅓ is a meaningful threshold for liveness in practice, it is low for the ability to influence the output. There are several reasons for it:

  1. The benefit from influencing the output can significantly outweigh the benefit of stalling randomness.
  2. If a participant controls more than ⅓ of participants in RandShare and uses this to influence the output, it leaves no trace. Thus a malicious actor can do it without ever being revealed. Stalling a consensus is naturally visible.
  3. The situations in which someone controls ⅓ of hashpower / stake are not impossible, and given (1) and (2) above someone having such control is unlikely to attempt to stall the randomness, but can and likely will attempt to influence it.

NEAR Approach

NEAR Approach is described in a paper we recently published. It is unbiasable and unpredictable, and can tolerate up to ⅓ malicious actors for liveness, i.e. if someone controls ⅓ or more participants, they can stall the protocol.

However, unlike RandShare, it tolerates up to ⅔ malicious actors before one can influence the output. This is significantly better threshold for practical applications.

The core idea of the protocol is the following (for simplicity assuming there are exactly 100 participants):

  1. Each participant comes up with their part of the output, splits it into 67 parts, erasure codes it to obtain 100 shares such that any 67 are enough to reconstruct the output, assigns each of the 100 shares to one of the participants and encodes it with the public key of such participant. They then share all the encoded shares.
  2. The participants use some consensus (e.g. Tendermint) to agree on such encoded sets from exactly 67 participants.
  3. Once the consensus is reached, each participant takes the encoded shares in each of the 67 sets published this way that is encoded with their public key, then decodes all such shares and publishes all such decoded shares at once.
  4. Once at least 67 participants did the step (3), all the agreed upon sets can be fully decoded and reconstructed, and the final number can be obtained as an XOR of the initial parts the participants came up with in (1).

The idea why this protocol is unbiasable and unpredictable is similar to that of RandShare and threshold signatures: the final output is decided once the consensus is reached, but is not known to anyone until ⅔ of the participants decrypt shares encrypted with their public key.

Handling all the corner cases and possible malicious behaviors make it slightly more complicated (for example, the participants need to handle the situation when someone in step (1) created an invalid erasure code), but overall the entire protocol is very simple, such that the entire paper that describes it with all the proofs, the corresponding cryptographic primitives and references is just 7 pages long. Make sure to check it out if you want to read a more formal description of the algorithm, or the analysis of its liveness and resistance to influence.

Similar idea that leverages erasure codes is already used in the existing infrastructure of NEAR, in which the block producers in a particular epoch create so-called chunks that contain all the transaction for a particular shard, and distribute erasure-coded versions of such chunks with merkle proofs to other block producers to ensure data availability (see section 3.4 of our sharding paper here).

Outro

This write-up is part of an ongoing effort to create high quality technical content about blockchain protocols and related topics. We also run a video series in which we talk to the founders and core developers of many protocols, we have episodes with Ethereum Serenity, Cosmos, Polkadot, Ontology, QuarkChain and many other protocols. All the episodes are conveniently assembled into a playlist here.

If you are interested to learn more about technology behind NEAR Protocol, make sure to check out the above-mentioned sharding paper. NEAR is one of the very few protocols that addresses the state validity and data availability problems in sharding, and the paper contains great overview of sharding in general and its challenges besides presenting our approach.

While scalability is a big concern for blockchains today, a bigger concern is usability. We invest a lot of effort into building the most usable blockchain. We published an overview of the challenges that the blockchain protocols face today with usability, and how they can be addressed here.

Follow us on Twitter and join our Discord chat where we discuss all the topics related to tech, economics, governance and other aspects of building a protocol.

No spam. Never shared. Opt out at any time.