Leader Election Problem

In the no-longer-as-niche world of distributed systems, there is always a fundamental problem whose solution came to be the building block of modern day massively distributed computation platforms. Of course I'm talking about consensus. Past versions of achieving this include algorithms like Paxos and Raft, which have seen much adoption in today’s distributed services. Before we get any further though let’s get some term definitions out of the way.

Transaction - A state change that needs to be broadcasted throughout the distributed network

Peer - A computer or server that participates either in generating a transaction (e.g. peer A sends some money to peer B) or validating the transaction

These algorithms may not seem like much hype outside of the fact that they form the backbone of how applications are able to handle terabytes of concurrent data, but you may have heard about Bitcoin and their Proof-of-work (POW) algorithm. At the heart of Bitcoin is a very expensive and fault-tolerant solution to the consensus problem. It has often been the complaint of many that the Proof-of-work algorithm is too costly and woefully inefficient. As a result, new consensus algorithms like Proof-of-stake (POS) have been invented to fundamentally alter how the consensus problem is solved in massively distributed open networks such as Ethereum.

Even then the chance of misconduct still remains. Each view of the transactions may not match that of other peers in the network, giving opportunity for double spending attacks until the overall system reaches eventual consistency (majority of peers agree on a state change in the system) after a couple of blocks. Since the validators are less in number the question of correct and unbiased processing of transactions.

With this adoption of POS come new challenges. The peer with more stake in the system that functions as a validator may still choose to bias against certain transactions without being penalized. One method to avoid this bias is to run part of the block generation process in a trusted execution environment, where the chosen transactions are guaranteed to be chosen fairly. We can show this via a simple leader election demo to showcase how easy it is to leverage Cape to do this.

This demo is done as part of an internal hackathon and serves to showcase how a part of the protocol can be migrated into confidential computation for more trusted output. The goal is to have the secure execution environment decide on who is the leader of peers in a network. Currently in this example we did not add fault tolerance as there is no timeout value set. For each peer started in the demo, it will try to gossip with other peers in the network and rely on Cape for determining who is the leader amongst the peers.

Why use Cape for this solution

Cape brings the power of confidential computing alongside modern day encryption to keep the data confidential. In this use case, we focus on the confidential computing aspect that Cape offers. The deployed function with Cape is validated during invocation to make sure that the function is the one intended to be called. This guarantee in execution logic is what allows for trusted output. An example of this is illustrated below.

Cape deploy returns the function checksum, if the checksum validation fails, the data is never submitted for running the function.

Implementation

A running example of this code can be seen here on github.

This example is run using the PyCape and function is deployed using CapeCLI.

Setup

Dependencies

Make sure you have CLI installed by running:

curl -fsSL https://raw.githubusercontent.com/capeprivacy/cli/main/install.sh | sh

Make sure you have PyCape installed by running:

pip install pycape

Create the function

The function is created with a public/private key pair and returns a result that is signed with the private key.

In a python environment run:

key = RSA.generate(2048)
private_key_bytes = key.export_key('PEM')
public_key_bytes = key.publickey().exportKey('PEM')
with open("private.pem", "wb") as f:
    f.write(private_key_bytes)

with open("public.pem", "wb") as f:
    f.write(public_key_bytes)

Copy the generated public and private key into a function folder with the following files:

app.py

import json
from unicodedata import name
from Crypto import Random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Hash import SHA256
from Crypto.PublicKey import RSA
from Crypto.Signature import PKCS1_v1_5

def cape_handler(arg):
    user_input = json.loads(arg)
    if "node_list" not in user_input:
        raise Exception("node list is missing")

    nodes = user_input.get("node_list")
    nodes.sort()
    message = str(nodes[-1])
    digest = SHA256.new()
    digest.update(message.encode("utf-8"))
    private_key = RSA.importKey(open("private.pem").read())
    signer = PKCS1_v1_5.new(private_key)
    sig = signer.sign(digest)
    return_val = {}
    return_val["message"] = message
    return_val["signature"] = sig.hex()
    return json.dumps(return_val)

requirements.txt

pycryptodome==3.15.0

at this point the function directory should look like this:

function/
   - app.py
   - private.pem
   - public.pem (not necessary, included for convenience later)
   - requirements.txt

Before deploying this function, we have to install the dependencies with the function by calling (from the parent directory of function)

pip install -r function/requirements.txt --target function/

This will install the dependencies required to run the function.

Deploy the function

To deploy the function use the cape binary that has been downloaded from the CLI step and run:
cape login

This will give you a prompt to open up a browser and login to your github account.

To deploy the function run:

cape deploy function/

You will see an output like the following:

Function ID ➜  YmoDB35PKxZS9v6eaU84YR

Function Checksum ➜  6b6d1c8b21f896269554cf633da084b25b49706a8efb41463687f353e0395171`

Then run:

`cape token <FUNCTION_ID> --function-checksum <FUNCTION _CHECKSUM> -o json >  leader_election.json

Running

Note the functionID and functionChecksum fields in the previous step as they will be important in getting the example working.

In your local environment copy the folder gossip from here and make sure you have this file.

Now you are ready to try out running the example by calling in two separate terminals with your deployed functionID and functionChecksum:

python start_node.py -p 5000 -n 5001 -f-fh`

python start_node.py -p 5001 -n 5000 -f <FUNCTION_ID> -fh <FUNCTION_CHECKSUM>`

This will start the gossip protocol between two peers in the local environment and have them send UDP packets with each other and print out who the leader is between the nodes. You can also add new peers and see how the algorithm works with more peers in the system.

Final thoughts

This is just a simple example of how to migrate a part of the consensus logic into a TEE for guaranteed correctness of execution. Bitcoin and Ethereum took this concept to a globally distributed peer system and found huge success. Fundamentally the value of these systems rely on generating trust. TEEs give you similar levels of execution guarantee without the need to have lots of graphics cards or lots of Ethereum.

With a more complete example in the future we can devise a more efficient consensus algorithm using TEE and showcase that the number of messages can be reduced dramatically even under Byzantine conditions.

Check out the Getting Started Docs to try Cape for free. We’d love to hear what you think.