Skip to main content

Example: Millionaire Problem - Secure Comparison Protocol Based on TEE

There are two millionaires, Alice and Bob, who want to know who is richer, but at the same time they don't want to let each other or anyone else know how much money they have.They can agree on a secure protocol to compare the wealth of the two in a trusted execution environment. Below is part of the code. For the full code, please see https://github.com/Safeheron/ssgx/tree/main/sample/millionaire_problem.

Step 1: Alice, Bob and TEE each generate their own public and private key pairs​

After generating the public-private key pair, Alice and Bob send their public keys to each other and the Arbiter(TEE).

  • Alice: alice_wealth_amounts, alice_pri_key, alice_pub_key, bob_pub_key
  • Bob: bob_wealth_amounts, bob_pri_key, bob_pub_key, alice_pub_key
  • Arbiter(TEE): tee_pri_key, tee_pub_key, alice_pub_key, bob_pub_key

Main Process Code​

/// alice & bob both know the code content and the corresponding mr_enclave value
/// Note: Remote attestation in Intel SGX relies on the MRENCLAVE measurement to verify the identity of the enclave.
/// Therefore, it is essential to use the enclave built in release mode.
/// Using a debug build or any non-identical environment will result in a different MRENCLAVE, causing the attestation to fail.
const std::string Expected_MR_ENCLAVE_HEX = "381ad7d4591bcb47edfc666904fc6140b0f61b5cd0d466ed0344024828383087";
/// alice generates a key pair
Millionaire alice{"alice", "111.23", MR_ENCLAVE_HEX};

/// alice generates a key pair
Millionaire bob{"bob", "112.23", MR_ENCLAVE_HEX};

/// get TEE public key and remote attestation report
char* quote_report_ptr = nullptr;
char* arbiter_pubkey_hex_ptr = nullptr;
char* one_time_access_token = nullptr;
uint64_t timestamp;

sgx_status =
    ecall_create_tee_pubkey(enclave_id, &ret, alice.GetPublicKey().c_str(), bob.GetPublicKey().c_str(),
&arbiter_pubkey_hex_ptr, &quote_report_ptr, &timestamp, &one_time_access_token);
if (sgx_status != SGX_SUCCESS || ret != 0) {
    printf("Failed to obtain Arbiter public key. ret: %d, sgx message: %s\n", ret, strerror((int)sgx_status));
    return -2;
}
std::string quote_report{quote_report_ptr};
std::string arbiter_pubkey_hex{arbiter_pubkey_hex_ptr};

Function Code​

int ecall_create_tee_pubkey(const char* alice_pubkey_hex, const char* bob_pubkey_hex,
                            char** out_arbiter_public_key_hex_ptr, char** out_quote_report_ptr,
                            uint64_t* out_prep_timestamp, char** out_one_time_access_token_ptr) {
    std::string arbiter_pubkey_hex;
    std::string quote_report;
    int64_t prep_timestamp;
    std::string one_time_access_token;
    bool ok = TrustedArbiter::GetSingleInstance().Prepare(alice_pubkey_hex, bob_pubkey_hex, arbiter_pubkey_hex,
                                                          quote_report, prep_timestamp, one_time_access_token);
    if (!ok) {
        return -1;
    }
    *out_arbiter_public_key_hex_ptr =
        ssgx::utils_t::StrndupOutside(arbiter_pubkey_hex.c_str(), arbiter_pubkey_hex.length());
    if (*out_arbiter_public_key_hex_ptr == nullptr) {
        return -2;
    }

    *out_quote_report_ptr = ssgx::utils_t::StrndupOutside(quote_report.c_str(), quote_report.length());
    if (*out_quote_report_ptr == nullptr) {
        return -3;
    }

    *out_prep_timestamp = prep_timestamp;

    *out_one_time_access_token_ptr =
        ssgx::utils_t::StrndupOutside(one_time_access_token.c_str(), one_time_access_token.length());
    if (*out_one_time_access_token_ptr == nullptr) {
        return -4;
    }
    return 0;
}

Step 2: Securely pass the tee_pub_key to Alice and Bob​

Send tee_pub_key to Alice and Bob, and use remote attestation to ensure that tee_pub_key cannot be tampered with and that the two public keys in the enclave memory is Alice and Bob’s.

  • Alice: alice_wealth_amounts, alice_pri_key, alice_pub_key, bob_pub_key, tee_pub_key
  • Bob: bob_wealth_amounts, bob_pri_key, bob_pub_key, alice_pub_key, tee_pub_key
  • arbiter(TEE): tee_pri_key, tee_pub_key, alice_pub_key, bob_pub_key

Alice and Bob verify the tee_pub_key and report to prove that the tee_pub_key they obtained is from the specified enclave and has not been tampered with.

Main Process Code​

sgx_status =
    ecall_create_tee_pubkey(enclave_id, &ret, alice.GetPublicKey().c_str(), bob.GetPublicKey().c_str(),
                            &arbiter_pubkey_hex_ptr, &quote_report_ptr, &timestamp, &one_time_access_token);
if (sgx_status != SGX_SUCCESS || ret != 0) {
    printf("Failed to obtain Arbiter public key. ret: %d, sgx message: %s\n", ret, strerror((int)sgx_status));
    return -2;
}
std::string quote_report{quote_report_ptr};
std::string arbiter_pubkey_hex{arbiter_pubkey_hex_ptr};

/// alice and bob exchange their public keys and assemble the same Userinfo.
/// They both verify the quote and the report with the same data.
if (0 != alice.VerifyQuoteAndSaveArbiterPublicKey(one_time_access_token, quote_report, timestamp, arbiter_pubkey_hex,
                                              bob.GetPublicKey())) {
    printf("Failed ocall_verify_quote_untrusted.\n\n");
    return -3;
}

if (0 != bob.VerifyQuoteAndSaveArbiterPublicKey(one_time_access_token, quote_report, timestamp, arbiter_pubkey_hex,
                                            alice.GetPublicKey())) {
    printf("Failed ocall_verify_quote_untrusted.\n\n");
    return -3;
}

Function Code​

int Millionaire::VerifyQuoteAndSaveArbiterPublicKey(const std::string& one_time_access_token, const std::string& quote,
                                                    uint64_t timestamp, const std::string& arbiter_public_key, 
                                                    const std::string& peer_millionaire_public_key) {
    std::string user_info;
    /// user_info = min_pubkey + max_pubkey + arbiter_public_key_hex + one_time_access_token
    if (public_key_hex_ < peer_millionaire_public_key) {
        user_info.append(public_key_hex_);
        user_info.append(peer_millionaire_public_key);
    } else {
        user_info.append(peer_millionaire_public_key);
        user_info.append(public_key_hex_);
    }
    user_info.append(arbiter_public_key);
    user_info.append(one_time_access_token);
    if (0 != VerifyQuoteUntrusted(quote, timestamp, user_info, mr_enclave_hex_)) {
        return -1;
    }
    arbiter_public_key_hex_ = arbiter_public_key;
    printf("\n%s Save Arbiter public key succeeded\n", name_.c_str());
    return 0;
}

Step 3: Alice and Bob securely transmit their respective wealth amounts into the TEE​

Alice and Bob encrypt their respective wealth amounts using tee_pub_key and then sign with their respective private keys, then send the ciphertext and signature to Arbiter(TEE).

  • Alice: ECDSA::sign(alice_pri_key, P256, ECIES::encrypt(tee_pub_key, P256, alice_wealth_amounts)) -> alice_wealth_amounts_signature, alice_wealth_amounts_ciphertext
  • Bob: ECDSA::sign(bob_pri_key, P256, ECIES::encrypt(tee_pub_key, P256, bob_wealth_amounts)) -> bob_wealth_amounts_signature, bob_wealth_amounts_ciphertext

Main Process Code​

/// alice encrypts her wealth and signs it
std::string alice_ciphertext;
std::string alice_signature;
if (0 != alice.EncryptAndSignWealth(alice_ciphertext, alice_signature)) {
    printf("Failed in alice.EncryptAndSignWealth(alice_ciphertext, alice_signature).\n\n");
    return -3;
}

/// bob encrypts his wealth and signs it
std::string bob_ciphertext;
std::string bob_signature;
if (0 != bob.EncryptAndSignWealth(bob_ciphertext, bob_signature)) {
    printf("Failed in bob.EncryptAndSignWealth(bob_ciphertext, bob_signature).\n\n");
    return -3;
}

Function Code​

int Millionaire::EncryptAndSignWealth(std::string& ciphertext, std::string& signature) {
    bool pass = false;

    // Parse the Arbiter public key
    std::string arbiter_pubkey_full = safeheron::encode::hex::DecodeFromHex(arbiter_public_key_hex_);
    CurvePoint arbiter_pubkey;
    pass = arbiter_pubkey.DecodeFull(arbiter_pubkey_full, CurveType::P256);
    if (!pass)
        return -1;

    // Encrypt the wealth value
    ECIES ecies;
    ecies.set_curve_type(CurveType::P256);
    std::string ciphertext_bin;
    pass = ecies.EncryptPack(arbiter_pubkey, wealth_, ciphertext_bin);
    if (!pass)
        return -2;
    ciphertext = safeheron::encode::hex::EncodeToHex(ciphertext_bin);

    // Compute hash of ciphertext
    uint8_t md[safeheron::hash::CSHA256::OUTPUT_SIZE] = {0};
    safeheron::hash::CSHA256 sha256;
    sha256.Write((unsigned char*)ciphertext.c_str(), ciphertext.length());
    sha256.Finalize(md);

    // Generate signature
    uint8_t signature_bin[64];
    safeheron::curve::ecdsa::Sign(CurveType::P256, private_key_, md, signature_bin);
    signature = safeheron::encode::hex::EncodeToHex(std::string(reinterpret_cast<const char*>(signature_bin), 64));

    printf("\n%s signing and encryption succeeded\n", name_.c_str());
    return 0;
}

Step 4: Arbiter(TEE) obtains and compares the wealth of Alice and Bob​

Arbiter(TEE) verifies the signature and decrypts the ciphertext to obtain the wealth of Alice and Bob.

  • arbiter(TEE): ECDSA::verify(alice_pub_key, P256, alice_wealth_amounts_ciphertext, alice_wealth_amounts_signature) & ECIES::decrypt(tee_pri_key, P256, alice_wealth_amounts_ciphertext) -> alice_wealth_amounts
  • arbiter(TEE): ECDSA::verify(bob_pub_key, P256, bob_wealth_amounts_ciphertext, bob_wealth_amounts_signature) & ECIES::decrypt(tee_pri_key, P256, bob_wealth_amounts_ciphertext) -> bob_wealth_amounts

Arbiter(TEE) compares the wealth amounts of Alice and Bob, and then uses remote attestation to ensure that the result will not be tampered with during transmission.

Main Process Code​

/// ask Arbiter to compare the two values and return the result along with a remote attestation report.
/// (Alternatively, the Arbiter can sign the result with its key to prove authenticity)
char* alice_vs_bob_result_ptr = nullptr;
char* result_quote_report_ptr = nullptr;
sgx_status = ecall_who_is_richer(enclave_id, &ret, one_time_access_token, alice_ciphertext.c_str(),
                                 alice_signature.c_str(), bob_ciphertext.c_str(), bob_signature.c_str(),
                                 &alice_vs_bob_result_ptr, &result_quote_report_ptr, &timestamp);
if (sgx_status != SGX_SUCCESS || ret != 0) {
    printf("Failed to obtain alice vs bob result. ret=%d,sgx_status=%s\n\n", ret, strerror((int)sgx_status));
    return -3;
}

Function Code​

int ecall_who_is_richer(const char* one_time_access_token, const char* alice_ciphertext, const char* alice_signature,
                        const char* bob_ciphertext, const char* bob_signature, char** out_alice_vs_bob_result_ptr,
                        char** out_quote_report_ptr, uint64_t* out_compare_timestamp) {

    bool ok = TrustedArbiter::GetSingleInstance().IsReady();
    if (!ok) {
        return -5;
    }

    std::string comparison_result;
    std::string quote_report;
    uint64_t compare_timestamp;
    ok = TrustedArbiter::GetSingleInstance().Compare(one_time_access_token, alice_ciphertext, alice_signature,
                                                     bob_ciphertext, bob_signature, comparison_result, quote_report,
                                                     compare_timestamp);

    if (!ok) {
        return -6;
    }

    *out_alice_vs_bob_result_ptr = ssgx::utils_t::StrndupOutside(comparison_result.c_str(), comparison_result.length());
    if (*out_alice_vs_bob_result_ptr == nullptr) {
        return -7;
    }

    *out_quote_report_ptr = ssgx::utils_t::StrndupOutside(quote_report.c_str(), quote_report.length());
    if (*out_quote_report_ptr == nullptr) {
        return -8;
    }

    *out_compare_timestamp = compare_timestamp;

    return 0;
}

// Simulate comparison function (real version should decrypt and verify signatures)
bool TrustedArbiter::Compare(const std::string& one_time_access_token, const std::string& alice_ciphertext,
                            const std::string& alice_signature, const std::string& bob_ciphertext,
                            const std::string& bob_signature, std::string& out_comparison_result,
                            std::string& out_quote_report, uint64_t& out_compare_timestamp) {
    std::lock_guard<std::mutex> lock(mutex_);
    is_ready_ = false;

    // one_time_access_token can be used once.
    if (one_time_access_token != one_time_access_token_) {
        return false;
    }

    // Get Alice's wealth
    std::string alice_plaintext;
    bool ok = VerifySignatureAndDecrypt(alice_pubkey_, alice_ciphertext, alice_signature, alice_plaintext);
    if (!ok) {
        return false;
    }
    const BigDecimal alice_wealth(alice_plaintext.c_str());

    // Get Bob's wealth
    std::string bob_plaintext;
    ok = VerifySignatureAndDecrypt(bob_pubkey_, bob_ciphertext, bob_signature, bob_plaintext);
    if (!ok) {
        return false;
    }
    const BigDecimal bob_wealth(bob_plaintext.c_str());

    // Compare and generate result
    if (alice_wealth > bob_wealth) {
        out_comparison_result = "Alice is richer";
    } else {
        out_comparison_result = "Alice is not richer than Bob";
    }

    compare_timestamp_ = ssgx::utils_t::DateTime::Now().GetTimestamp();
    out_compare_timestamp = compare_timestamp_;

    // Create remote attestation report
    // user_info = out_comparison_result + one_time_access_token
    RemoteAttestor attestor;
    std::string user_info = out_comparison_result + one_time_access_token_;

    ok = attestor.CreateReport(user_info, compare_timestamp_, out_quote_report);
    if (!ok) {
        return false;
    }

    ssgx::utils_t::Printf("\nArbiter performs a comparison:\n");
    ssgx::utils_t::Printf("one time access token: %s\n", one_time_access_token_.c_str());
    ssgx::utils_t::Printf("remote attestation quote: %s\n\n", out_quote_report.c_str());
    ssgx::utils_t::Printf("\n\n");

    return true;
}

bool TrustedArbiter::VerifySignatureAndDecrypt(const safeheron::curve::CurvePoint& pubkey,
                                            const std::string& ciphertext, const std::string& signature,
                                            std::string& plaintext) {
    bool pass = false;

    // Get hash of ciphertext
    uint8_t md[safeheron::hash::CSHA256::OUTPUT_SIZE] = {0};
    // sha256
    safeheron::hash::CSHA256 sha256;
    sha256.Write((unsigned char*)ciphertext.c_str(), ciphertext.length());
    sha256.Finalize(md);

    // Verify signature
    pass = safeheron::curve::ecdsa::Verify(CurveType::P256, pubkey, md,
        (const uint8_t*)safeheron::encode::hex::DecodeFromHex(signature).c_str());
    if (!pass) {
        return false;
    }

    std::string ciphertext_bin = safeheron::encode::hex::DecodeFromHex(ciphertext);
    // Decrypt ciphertext using TEE private key
    ECIES enc;
    enc.set_curve_type(CurveType::P256);
    pass = enc.DecryptPack(arbiter_privkey_, ciphertext_bin, plaintext);
    if (!pass) {
        return false;
    }
    return true;
}

Step 5: Alice and Bob get the results​

Alice and Bob verify the result and report to prove that they are from the specified enclave and have not been tampered with.

Main Process Code​

/// ask Arbiter to compare the two values and return the result along with a remote attestation report.
/// (Alternatively, the Arbiter can sign the result with its key to prove authenticity)
char* alice_vs_bob_result_ptr = nullptr;
char* result_quote_report_ptr = nullptr;
sgx_status = ecall_who_is_richer(enclave_id, &ret, one_time_access_token, alice_ciphertext.c_str(),
    alice_signature.c_str(), bob_ciphertext.c_str(), bob_signature.c_str(),
&alice_vs_bob_result_ptr, &result_quote_report_ptr, &timestamp);
if (sgx_status != SGX_SUCCESS || ret != 0) {
    printf("Failed to obtain alice vs bob result. ret=%d,sgx_status=%s\n\n", ret, strerror((int)sgx_status));
    return -3;
}

std::string alice_vs_bob_result = std::string(alice_vs_bob_result_ptr);
std::string result_quote_report = std::string(result_quote_report_ptr);
/// alice verifies the result to prove its authenticity
if ( 0 != alice.VerifyQuoteAndShowResult(one_time_access_token, result_quote_report, timestamp, alice_vs_bob_result)) {
    printf("Failed in alice.VerifyQuoteAndShowResult(one_time_access_token, result_quote_report, timestamp, alice_vs_bob_result).\n\n");
    return -3;
}
/// bob verifies the result to prove its authenticity
if (0 != bob.VerifyQuoteAndShowResult(one_time_access_token, result_quote_report, timestamp, alice_vs_bob_result)) {
    printf("Failed in bob.VerifyQuoteAndShowResult(one_time_access_token, result_quote_report, timestamp, alice_vs_bob_result).\n\n");
    return -3;
}

Function Code​

int Millionaire::VerifyQuoteAndShowResult(const std::string& one_time_access_token, const std::string& quote,
                                          uint64_t timestamp, const std::string& alice_vs_bob_result) {
    std::string user_info = alice_vs_bob_result + one_time_access_token;
    if (0 != VerifyQuoteUntrusted(quote, timestamp, user_info, mr_enclave_hex_)) {
        return -1;
    }
    printf("\n%s presentation results:%s\n", name_.c_str(), alice_vs_bob_result.c_str());
    return 0;
}

At this point, Alice and Bob already know who is richer between the two of them, but they don't know how much money the other has. Others also don't know how much money Alice and Bob have, because the plaintext of their wealth amounts only appears in the enclave.