Byzantine Generals And Building a More Trusted and Resiliant World

Byzantine Generals And Building a More Trusted and Resilient World

Consensus, Shamir’s Secret Shares and Multiparty Computation (MPC)

In my work with IOTA, I am privileged to work with some of the best people in the world on building a more trusted world. At the core of this is consensus. For me, our future will be built on trust, and in creating systems which are resilient. And in building trust into every single element of a transaction — from the lowest level of a transaction (in the CPU) to its high level agreement on whether it is valid or not.

As we become ever more dependent on our digital systems, we need to be able to cope with failures and security issues. With industrial systems, these are well defined, as water delivery system must cope with failures in any part of the infrastructure, and also where the security is breached. But in digital systems, we still often rely on a single version of the truth, and if that truth is wrong, then everything that results from it is also wrong.

A few generals

When I worked in an industrial plant, there were systems that check the outputs of the key part of the control system. If something went wrong, you could have another control system to take over. But what happens if that fails, too? In fact, what if an adversary has placed some malware on our system? For this we can turn to the Byzantine Generals Problem, and which was first defined by Leslie Lamport:

Within this, the generals of a Byzantine army have to agree to their battle plan, in the face of adversaries passing in order information. In the end, we aim to create a way of passing messages where if at least two out of three of the generals are honest, we will end up with the correct battle plan. So why don’t we build computer systems like this, and where we support failures in parts of the system, or where parts of the system may be taken over for malicious purposes? And the answer is … no reason, it just that we are stuck with our 1970s viewpoint of the computing world, and everything works perfectly, and security is someone else's problem to fix.

So, we need a system where we create a number of trusted nodes to perform a computation, and then an election process at the end to see if we have a consensus for a result. If we have three generals (Bob, Alice and Eve), we need two of them to be honest, which means we can cope with one of our generals turning bad:

In this case, Eve could try and sway Trent by sending the wrong command, but Bob and Alice will build a better consensus, and so Trent will go with them. The work can then be defined as MPC (Multiparty Computation) and where we have multiple nodes getting involved to produce the final result. In many cases, this result could just be as simple as a Yes or No, and as to whether a Bitcoin transaction is real or fake, or whether an IoT device has a certain voltage reading.

Secret shares and consensus

So let’s see if we can build a model where we can securely distribute value, and then get our nodes to perform the result of a calculation. None of the nodes should be able to compute the result without the help of others, and where Trent is trusted to distribute the inputs, watch the broadcasts, and then gather the results. For this we can use Shamir secret shares, and where a value can be split into t-from-n shares, and where we need t shares to rebuild our value. So, we could distribute a 2-from-3 to Bob, Alice and Eve, and they Bob and Alice, or Alice and Eve, could rebuild the value back again.

So let’s say we have two values: x and y, and we want to compute x*y. We then initially start with n parties, and where we define a threshold of t (the minimum number of shares required to rebuild any value. Initially, Trent (the trusted dealer) splits the input values of x and y into shares:

Shares_1 = x_1, x_2, … x_n
Shares_2 = y_1, y_2, … y_n

Next Trent sends one share of each to each of the node, such as x_i and y_i to node i. Each node then must gather at least t shares for the nodes, and then aim to add to its own share. Each node then is able to rebuild the values of x and y, and then compute x*y. Trent then receives all the results back and makes a judgement on the consensus. If we have 12 nodes, then if there are at least eight nodes that are fair, the result will be the correct one. So, let’s implement this in Go [here]:

A sample run gives [demo]:

a: 2000 b: 1000

Policy. Any 3 from 5

Share: 1 740b0148 Share: 2 352e1a92 Share: 3 73152bea 
Share: 1 b7cc8e15 Share: 2 8018a91e Share: 3 06e4173b

a*b= 2000000
a+b= 3000
a-b= 1000

Trent must make sure that the nodes conduct their broadcasts in an honest way.

Conclusions

And there you go. We need to build systems not with clients and servers, and where the server is the master, but systems which use trusted nodes, and where each node is trusted to deliver good work. If one or two fail, or are compromised, we can still operate correctly.

Here is my little demo of the Shamir sharing method for consensus:

https://asecuritysite.com/ob/go_mpc01?a1=20&b1=10&t1=3&n1=5

And here’s some of the great work that goes on in IOTA [here]: