I sat down with Mahnush, who joined the DFINITY team a while ago, to discuss the various innovations that DFINITY will release. The topic covers terms such as threshold signatures, random beacons, and distributed key generation. We not only discuss these concepts, but also why they are so important.

Hello and welcome to another episode of Inside DFINITY. Today I'm going to be speaking with Mahnush, who joins us early on as a researcher. She comes from Yale University, and today we're going to hear about what she's doing at DFINITY, what she's done previously, and then she's also going to give us some insights into some of the technologies and innovations that DFINITY has developed.

Thank you, you joined DFINITY very early on. You've been a key part of our research team since the early days. Maybe for people who haven't heard of you yet, "What are you doing here?"

So I'm a researcher and what I do is help and design the consensus layer and prove the security of the consensus layer and the random beacon.

My day job is to collect ideas from the team, make them more formal so we can understand them among each other, write them up formally, and then I like to certify that they are safe so we can use them.

I think a great way you described me yesterday was, “I take everything we propose and I prove it’s secure.” I prove it’s secure, which I think is a very important property for what we’re trying to build with DFINITY.

What led you to this position? What did you do before? Where are you from?

Before joining DFINITY, I was a postdoc at Yale University. Before that, I was a PhD student. For my PhD, I worked on security research such as multi-party computation.

Secure multi-party computation

Secure multi-party computation is that you have to make sure that all parties reach an agreement. An important part of the computation is the output, and everyone should agree on the output. So consensus and Byzantine agreement are important parts of MPC protocols. That's why I'm interested in consensus protocols.

Then, while at Yale, I was trying to build a consensus protocol that scaled to millions of parties using a committee-based protocol. Then, I met Timo and Dominic, and I learned that DFINITY was trying to do the same thing, which was very interesting to me.

It’s been great to have you. I know we’ve made a lot of progress since you joined, including the white paper we published at the beginning of this year, which I know you spent many sleepless nights working on.

cloud computing

What are some of the hard problems or interesting problems that we are trying to solve here? I think what we are trying to do at DFINITY is a new version of cloud computing, which if you think about it, is really a state replication machine.

Because you have to have a lot of copies to make sure you don't lose computations or data, but all of those copies should agree on one thing. Because if some of them think something is final and some other copies think something else is final, then the user won't know which version is correct.

So making sure all of these replicas are consistent is a very important part of DFINITY. That's why the consensus protocol in general is very important to DFINITY.

Now, if all the replicas were honest, this would be a lot easier because we can ensure that, for example, if in Google Cloud, you have several replicas, and you're sure that all of them are controlled by Google, then… Right, so since they're all controlled by Google, you can ensure that every single computer can apply the same algorithm.

Is this what you mean by, “They’re all honest!” It’s true that since they’re all owned by one central group it’s a lot easier for them, but at the same time you have to trust Google to ensure that the algorithms they run are honest.

replica

But in DFINITY, we make sure that everyone in the world can have a copy, rather than assuming that all copies are owned by DFINITY. So it's like a more open way of doing cloud computing.

Users don't need to trust DFINITY, but they can trust the protocol that DFINITY runs. At some point, it will also be open source, right? What does it mean that everyone can look at the code and everyone can have a copy?

Basically, this means that everyone can become a miner in our system, and miners are still needed in DFINITY. Although they will not solve the proof-of-work puzzle, they constitute the distributed computing power on DFINITY.

They are helping with computation, they are helping with maintaining the data, and they are helping with maintaining computation on the data.

Practical Byzantine Fault Tolerant Protocol

If the replicas are different, like if the computers are on different domains, then some of them could be corrupt or adversarial. In computer science, we call this Byzantine because it comes from the Byzantine Generals Problem.

Well, solving this problem is a very hard problem, and it's been in computer science for the last 40 years. And everybody is trying to improve the solution because it's a very fundamental problem.

If you solve that problem effectively, you will solve a lot of problems on top of it. Now, trying something different is a new way to solve that problem.

So when you say the problem has been around for a long time, right in my head, one solution is if I have three independent copies, two say one thing and the third says something else, I always believe the majority. What is actually going on in the current network? What is the degree of disparity?

This is the first answer that computer scientists came up with, if you have multiple copies, like three copies, then you can't get a majority. So after you have a majority, everyone should send their input to everyone, which is like a circuit with a high communication depth.

Still because if you agree on just one similar opinion then majority works. But if you agree like a string then even an honest group may not agree. So one of the solutions for using PBFT protocol is to elect a leader.

PBFT (Byzantine Fault Tolerance) Protocol

What does PBFT mean? It’s like Byzantine Fault Tolerance (BFT), they call it “bad parties” or “Byzantine parties”, and the P in PBFT comes from practicality.

In this protocol, the replicas elect a leader, so, just like in the real world, if you want to reach an agreement, the best way is to elect a leader, and then the leader says what to do next, and everyone does the same thing, and they have an agreement.

So similar to the PBFT protocol, they elect a leader and if the leader is honest, he proposes the same value to everyone in the network and then they can come to agreement.

But the problem is that if the leader is dishonest then they can't reach consensus so the leader has to be changed. Checking if the leader is honest and presenting the same value to everyone and not changing the leader (they call it changing the view) is a very expensive protocol so it requires full communication which is very expensive.

Blockchain Protocol

Then, blockchain protocols came along like Bitcoin, and they decided not to change the leader as long as he's dishonest, and they decided, well, no, we need to actually change the leader only if the leader is dishonest, and we assume that the protocol is synchronous, so we change the leader in every new epoch, every new round.

Then they need a way to select a leader, because you have to select a leader, and then select the next leader, and then the next leader.

Instead of continuing to check if the leader is honest, you just continue to build on top of the protocol, on top of the log. There is a good chance that one of these leaders will reach agreement honestly and healthily. The problem now reduces to selecting a leader to selecting a leader which requires a random number.

Because if you have a random number, like a dice, then you can use that random number to select a leader, and this is where Proof of Work (POW) helps.

Proof of Work

Essentially, blockchain protocols are Byzantine agreements because they essentially use proof of work to select a leader. Just by running the proof of work, the first person to come up with a solution to the proof of work is the leader, and this is a random process.

So when I talk to parents or other people who are interested in blockchain, which I do all the time, I ask them: How do you randomly select a person among the people in this room, let’s say there are 10 people in the room?

First, everyone thinks it's easy, like we just roll the dice. I thought. So, who rolls the dice? They say, we just add all the birth dates, starting with yours, and then we circle until we get to that number. But then, how do you choose who to start with?

So it sounds like a very simple problem. But if you really want to make it random, it's hard. That's the big innovation of Bitcoin, finding a way among peers to basically agree on a random choice.

Essentially, using proof of work to create randomness is a very expensive way to create randomness because you have to consume a lot of electricity.

So for current work like Bitcoin, it's like a nation of electricity burning to solve the proof of work, which is why it's inherently very expensive.

We don’t actually use Bitcoin that much, if you want to scale to use Bitcoin for a lot of computation, you’d have to burn the world of it. If we compare where Bitcoin is now and where we have to go to achieve our vision, you’d still have to use ten or a hundred times as much Bitcoin.

You've mentioned that it basically consumes a lot of power. So we're looking for a more efficient way to do leader selection so that a random person is selected among the peers.

Proof of Work as a Synchronization Protocol

Another reason we tried to change the way Bitcoin creates randomness is that because proof of work is inherently a synchronous protocol, the time you have to spend to do the proof of work is essentially an order of magnitude greater than the network latency.

Otherwise, you don’t know if people prefer to burn electricity to solve the proof-of-work, or spend their time to solve the proof-of-work, or if their information is lost in the network.

By its very nature, a proof-of-work chain or proof-of-work consensus is low throughput, you can't do a fast tick because essentially you have to wait longer than the network latency for the next randomness to be created.

That's why you can't have a high throughput protocol on top of this, and that's why transactions also become very expensive because there's only a finite number of transactions that can fit in each block. We can't increase the number of blocks per time unit without messing up this protocol.

How DFINITY creates random numbers

DFINITY is trying to solve this problem, so the first idea is, now we need a new way to create randomness, but how do we create randomness now?

As I said, this is a very difficult problem. So one approach is to have a person create the randomness, but if that person is dishonest, he can't bias the randomness.

Now we need a group to create randomness, but if we choose a group, then if I am the first person to create randomness and you are the second, then the last person can look at our random numbers and choose his own randomness and the result will be what he wants, we call this last person bias.

We can't have a group where the randomness is chosen by the last person, that's why we use threshold cryptography.

Threshold Cryptography

Threshold cryptography means that instead of having a group of n people, all of whom need to create randomness, there is a group of n people, but only K of them need to participate.

If you are waiting for K people, then if you receive input from K minus 1 participants, then you are waiting for one input. But any n minus K other parties can be the last person. So there is no last person bias.

If the last person decides "I don't want to join", then there is another party joining, but that's not enough. Because now if the membership of this group of K people generates randomness, and the behavior of the other group of K people generates randomness, if these two randomnesses are different, then the adversary (by determining whether I want to join this group) can bias the protocol. This is why we need uniqueness.

Uniqueness

The uniqueness of randomness means that it doesn’t matter which K parties were involved in creating the randomness, the result is always unique, the result is always the same. This is an incredible property to begin with. It sounds so counterintuitive, “How did we get there?”

If you have a message, and if you use BLS signatures to threshold sign it, then you need K participants. If the threshold is K, then you need K participants to sign it, and no matter who the k participants are, then you get a unique identity result. This is the key property of BLS signatures.

It's pairing-based cryptography. So it's new, but not too new, because if it was too new, you'd be concerned about security and you'd be concerned about whether it's been proven properly. If enough people review it, comment on it, and test it.

At Stanford, enough people looked at it, and the group did a long time to make sure it was secure and like a very secure protocol with great implementations around it. So we have a very fast BLS implementation that's open source and everyone can use it.

Maybe, just give some overview and then we can also talk about random beacons and what exactly that is, but you mentioned that, and I think that's a good explanation of where to start and that proof of work doesn't go beyond a certain point in terms of throughput and energy usage.

And then the problem of creating this random number with the bias of the last person, we solve by having a k out of n threshold signature. And the BLS signature we use is unique to k out of n people and still random. These are two properties that I still have a hard time consistently seeing how they fit together.

So what do we do about this? Let's go back to Satoshi's blockchain and see how they work. So Nakamoto's blockchain is like creating randomness completely for every block, meaning for every block you solve the proof of work from the beginning and you don't reuse any randomness there.

That's one of the reasons why it's very expensive. So here we don't want to do that because we know that threshold cryptography is very expensive, just like the proof of work world. It's not as expensive, but it's still a very expensive operation.

We want to make sure that most of the expensive operations can be done offline, and then when we are online, we do very few operations. If you look at signature schemes, there are different methods that need to be handled, they need to work. So one of them is creating keys, and we call it distributed key generation (DKG).

DKG (Distributed Key Generation)

DKG (Distributed Key Generation) is a very expensive operation because you have to have everyone agree on the public key they are going to sign, and everyone should output a key for themselves that is part of one big key for the group, so they can use it to sign inputs.

All the process is an expensive process, you need to use a key to authenticate, so it's an expensive process. Just to quickly touch on this, which I think is also an interesting topic, it basically means we're all out there, we're all talking to each other, but we've all agreed on a non-public key.

It's amazing that we can talk about this thing... but it also means that we all correctly created private keys to go with that public key, and that all of our private keys somehow work together even though we haven't mentioned our private keys to anyone else.

The good thing is that you can run the DKG process once and then you can sign multiple times with the same key, which means you amortize the cost of the expensive DKG over multiple times. You can do one round and then run DKG with a group, and then, after they have their own key, they can use it to sign different inputs.

Every time they sign again, they get a new random number, it's a new pseudo-random number, it's actually not random anymore because the first one was random, but it's a pseudo-random function after that. It acts as a pseudo-random number for you.

Then, in this way, we can make the signature scheme non-interactive, which means "I don't need to talk to you in order to sign."

I do my part, I sign, you do your part, you sign, but we can put those signatures together and merge them together and get a merged signature without ever talking to each other.

This is what they call non-interactive. This is a nice property because it makes the signature scheme much faster than the non-interactive version.

The way DFINITY works is that we create this group, then we do a DKG, now we sign the first randomness, then we get a randomness in this round, and then in the next round, we sign the previous randomness to create a new randomness for the next round, and then, we keep signing.

How long are we going to reuse the same raw randomness? You can reuse it for a long time, you can reuse it for a few months, you can reuse it for about a month or two months. So as long as there are enough participants in the group, they are still active and honest, you can reuse the same randomness. You also mentioned the cohort.

Are there different groups in the way DFINITY operates? We have this threshold cryptography, we have the DKG process, but if you want to run this across a large number of participants like 5 million Bitcoins, it’s a very expensive process because you have to send a message to everybody and everybody has to sign.

It's still a very expensive process. We looked at the system and realized that you don't need everyone's signature, you don't need everyone to participate in the randomness. You can just randomly select the parties to participate in the randomness, just like you hold elections in a country.

So if you want to decide something, you don't need everyone to come up with a law or make a decision, you can have a committee, you can have representatives instead of having everyone, we should choose a group, but how do we choose a group?

Still we can reuse our own randomness, so because a group is chosen randomly, then that group has similar properties to the actual total number of parties. Instead of running the entire protocol on 5 million people, we can run it on 500 people, and it's ten times faster.

Whether there are 100,000 people participating in the entire network or 100 million people participating, the process that the group goes through is always similar because the size of the group is constant. Another benefit of choosing a group is that you not only get scalability, but you also get parallelism because now we can have multiple chains instead of just one chain.

Fragmentation

Each group is responsible for one chain, so you can create multiple chains in parallel, which we call sharding in blockchain in general. This is a very natural way of sharding.

So that's why I think DFINITY has a very good way of sharding, it's inherent in DFINITY because we have groups and then each group can have its own shard. So what are the bigger problems that we are dealing with right now?

Currently, we have a complete proof in the synchronous setting. In a synchronous computation or synchronous communication model, when an honest party sends a message, it will be received by all honest parties within Delta range.

For example, in Bitcoin, when an honest party sends a message, it is received in about a minute, and for everyone in the world, less than a minute. The protocol knows about it and uses it.

So in Bitcoin, the length of the proof of work depends on the latency of the network, and it should be a lot longer, so it's about 10 minutes for Bitcoin, because they assume that Bitcoin is 10 times longer.

The synchronization assumption works, but the problem is that if the synchronization assumption is not true in a real network, the protocol is now no longer secure.

Complete Proofs in Asynchronous Networks

What we’ve done in DFINITY is we have a proof of security in the full synchronous model, and we’re updating our proof to make it usable for asynchronous networks as well.

That's one of the areas I'm working on right now, and the other area I'm working on is the interactive DKG process that we're currently doing in the DKG process, which means that every participant who wants to participate in the activity should be able to use DKG when they run the DKG protocol.

Non-interactive DKG (Distributed Key Generation)

We want to make it non-interactive, meaning parties can participate and come back and come back when the agreement is done. So it's like a more natural way to run it, DKG is a non-interactive version, not an interactive version.

The third thing I’m working on is the sharding part, which I just talked about. We are designing a sharding system for DFINITY. We have designed a sharding system for a Bitcoin-like network, and we use the same concepts, and our paper will be published at CCS. It’s a good paper, so you should read it.

Maybe just to wrap this up, “What are the requirements for DFINITY? How many people can be dishonest and the network still survive?” That’s a good question.

Typically, if you're working in an asynchronous environment or a semisynchronous environment, the number of parties that a protocol can tolerate is one third. So the fraction of dishonest parties is always one third in the asynchronous model, and that's the lower bound, so it can't tolerate anything higher than that.

DFINTY's Sharding System

DFINITY is working in this model, which means that the proportion of dishonest parties in the entire network should be one-third, but within each group we can only tolerate half, so we go from one-third to half. “Do we already know how big these groups are going to be?”

The size of the group depends on how big the security level you want to get, the bigger the group, the better security you get. Currently, a group size from 400 to 800 seems logical for a security level of around 86-90, which means the error probability will be around 86. You will never lose a token.

Block times and finality

Another question before I wrap up is, we talked about energy efficiency and mentioned some of the block times on the Bitcoin blockchain, and you mentioned that it was about ten minutes. So what is the block time that we are achieving in DFINITY?

Currently, in our test network, the block time is about one second, less than one second.

Another difference between DFINITY and Bitcoin is that to reach finality with Bitcoin, since they don’t have an actual consensus protocol, you need to wait six blocks. With DFINITY, we need two blocks.

So that means 2 seconds, 1 second per block, 2 seconds finality, which means we have 2 seconds of finality, while Bitcoin has about 1 hour of finality.

Basically, this is what it's like to implement a transaction similar to a credit card on DFINITY vs. Bitcoin and complete the transaction, if I go to a coffee shop to buy a coffee, in the worst case scenario, I have to wait an hour before I can use my Bitcoin. I have to wait to make sure that the transaction actually went through, while on DFINITY it might take two seconds.

In the best case, if block producers are optimistic and honest, you only have to wait two seconds for finality in DFINITY, then it feels like a high throughput system.

Thank you Mahnush for taking the time to walk us through some of the challenges and innovations at DFINITY.

IC content you care about

Technology Progress | Project Information | Global Activities

Collect and follow IC Binance Channel

Get the latest news