Blinded Diffie–Hellman–Merkle for Ecash Mints

In 1982 David Chaum conceived the idea of anonymous cryptographic electronic cash using cryptographic proofs to mint electronic and melt electronic tokens.

The security proofs were guaranteed using blinded digital signature schemes that provided unlinkability between withdrawal and spending transactions. The concept of blind signatures can be explained by a scenario where a provider wants an entity to commit to a certain proof even though that entity does not know the proof. The provider can then reveal the proof later or send it to another provider who can reveal the proof to the entity.

Ecash has gained popularity in Bitcoin in projects like Cashu and Fedimint due to their anonymity and scalability properties.

In this article we will look at how to construct a simple Ecash token using Blinded Diffie–Hellman–Merkle key exchange.

Diffie–Hellman–Merkle key is a protocol for exchanging secrets between parties over a public channel where at least one of the party’s public keys is known.

Diffie-Hellman-Merkle Key Exchange (Source: https://upload.wikimedia.org/wikipedia/commons/c/c8/DiffieHellman.png)

Our algorithm for Blinded Diffie-Hellman-Merkle key exchange with comprise of:

1. a secret key and a public key for the mint
2. a secret key for the provider
3. a nonce generated by the provider
4. an algorithm to transform our secret into a point on an elliptic curve (blinding factor)
5. an algorithm to blind the provider secret (blinded message)
6. an algorithm to generate a blinded signature from the blinded message
7. an algorithm to unblind the token from the blinded signature

The steps to generate the token are:

Where we assume:

- Bob is the Mint
- Alice is the Provider
- Eve is another Provider 
  that can redeem the tokens generated by Alice 
  by sending the tokens to Bob
- Gnerator represented by G is a known point on the 
  elliptic curve, in our case 
  the Ristretto Point on Curve25519 algorithm
- hash_to_curve() is an algorithm that takes a 32 byte
  secret, hashes it with a cryptographically secure 
  hashing algorithm like SHA256 and computes a point
  on the elliptic curve using the result of the hashed
  bytes. The hashing algorithm blinds the secret 
  because one cannot guess the secret from the hash.
  This is known as preimage resistance.

1. Bob generates a secret key k from some 32 random bytes and then multiplies that by a generator G to generate a public key K and let’s all providers know K
K = k * G
2. Alice generates a secret key from 32 bytes
3. Alice generates a random nonce as the blinding_factor
4. Alice generates a point on the elliptic curve by running the hash to curve algorithm with her the secret key
   hash_to_curve_result = hash_to_curve(sha512_hash(secret))
5. Alice then computes a blinded_message by multiplying the blinding_factor by G and then adding it to the elliptic curve point of the hashed secret hash_to_curve
blinded_message = hash_to_curve_result + blinding_factor * G
6. Alice then sends the blinded_message
7. Bob who computes the blinded_signature by multiplying the blinded message with his secret k
blinded_signature = blinded_message * k
8. Bob then returns the blinded_signature to Alice
9. Alice computes the unblinded_secret by multiplying the blinding_factor with Bob’s K (public key) and the subtracting this from the blinded_signature
token = blinded_signature — binding_factor * K
10. Alice can now share her secret s and token secret with Carol
11. Carol can redeem the token by sending the secret s and token to Bob
12. Bob verifies that the token is authentic by running the hash_to_curve() algorithm with the secret key generated by Alice and passed to Carol
    hash_to_curve_result = hash_to_curve(sha512_hash(secret))
13. Bob then multiplies the hash_to_curve with his own secret key k
hash_to_curve_result * k
14. Bob then compares the result of the previous step with the token and rejects the token if the result of the comparison is false
assert( (hash_to_curve_result * k) == token )

Let’s implement these steps using the Rust programming language. We assume you have already installed Rust programming language toolchain and its cargo project manager.

Using the commandline create a new Rust project using cargo and switch to that directory

$ cargo new Blinded-Diffie-Hellman-Merkle --name blinded-dhm #Create a new project

$ cd Blinded-Diffie-Hellman-Merkle # Switch to the directory

Inside the Cargo.toml add the dependencies for cryptographically secure random number generation (rand) , elliptic curves) and hashing (sha2)

[dependencies]
curve25519-dalek = { version = "4.1.2", features = [
    "rand_core",
    "digest",
    "precomputed-tables",
] }
rand = "0.8.5"
sha2 = "0.10.8"

• In curve25519-dalek
  - the feature rand_core enables generation of random bytes from the operating system
  - the feature digest enables the SHA512 hashing algorithm when calling hash to curve
  -precomputed-tables enables faster multiplication of scalar points with points on the elliptic curve

Inside the main.rs file, lets create the code for our algorithm

1. Import all the data types and traits we will use

use curve25519_dalek::{ristretto::RistrettoPoint, scalar::Scalar, traits::Identity};
use rand::rngs::OsRng;
use sha2::Sha512;
use std::ops::{Mul, Sub};

2. Next, create a struct MintCryptoto perform cryptographic operations for the mint.

/// Cryptographic operations for the mint (Bob)
pub struct MintCrypto {
    // the secret key for a particular Ecash denomination
    secret: Scalar,
    // the public key for the Ecash denomination
    // specific to the secret key above
    public: RistrettoPoint,
}

impl MintCrypto {
    /// Instantiate our struct
    pub fn new() -> Self {
        // generate a secret key and store it in a `Scalar`
        let secret = Scalar::random(&mut OsRng);
        // Generate the public key
        let public = RistrettoPoint::identity().mul(&secret);

        Self { secret, public }
    }

    /// Generate a blinded token to return to Alice
    pub fn blinded_token(&self, blinded_message: RistrettoPoint) -> RistrettoPoint {
        blinded_message.mul(self.secret)
    }

    /// Prove that the unblinded token is valid
    pub fn proof(&self, unblinded_token: UnblindedToken) -> bool {
        // Compute the point on elliptic curve
        let hash_to_curve =
            RistrettoPoint::hash_from_bytes::<Sha512>(unblinded_token.secret.as_bytes());
        // Check if multiplying the elliptic curve point
        // equals the token
        self.secret.mul(hash_to_curve) == unblinded_token.proof
    }

    /// Fetch the public key of the mint
    pub fn public_key(&self) -> RistrettoPoint {
        self.public
    }
}

3. Next, create a struct UnblindedToken which contains the secret key of Alice and the token issued by the mint. UnblindedToken is what is shared with Carol.

/// Contains the unblinded token from the mint and providers secret key
pub struct UnblindedToken {
    /// Provider's secret key
    pub secret: Scalar,
    /// The unblinded token from the mint
    pub proof: RistrettoPoint,
}

4. Next, we create the cryptographic primitives for the provider

/// Cryptographic operations for the Provider (Alice)
pub struct ProviderCrypto {
    // The secret known to the provider
    secret: Scalar,
    // A random nonce that guarantees each mint token is unique (nonce)
    blinding_factor: Scalar,
    // The blinded message
    blinded_message: RistrettoPoint,
    // The public key of the mint which can be for a particular token's denomination
    ecash_token_public: RistrettoPoint,
}

impl ProviderCrypto {
    /// instantiate the struct by passing in the public key of the mint
    pub fn new(ecash_token_public: RistrettoPoint) -> Self {
        // Generate 32 cryptographically secure bytes
        let secret = Scalar::random(&mut OsRng);
        // Generate 32  cryptographically secure bytes (nonce)
        let blinding_factor = Scalar::random(&mut OsRng);
        // Run the `secret` first through a SHA512 hash and then generate a point on the elliptic curve
        let hash_to_curve_result = RistrettoPoint::hash_from_bytes::<Sha512>(secret.as_bytes());
        // Generate a `blinded_message` that is unique by adding the `hash_to_curve_result`
        // to a point on the elliptic curve generated by the multiplying the `blinding_factor` by a generator `G`
        let blinded_message =
            hash_to_curve_result + (RistrettoPoint::identity().mul(&blinding_factor));

        Self {
            secret,
            blinding_factor,
            blinded_message,
            ecash_token_public,
        }
    }

    /// Unblind a token from the mint
    pub fn unblind(&self, token: RistrettoPoint) -> UnblindedToken {
        // Performs the unblinding operation `token - blinding_factor * K` where `K` is the public key of the mint
        let proof = token.sub(self.blinding_factor.mul(self.ecash_token_public));

        UnblindedToken {
            secret: self.secret,
            proof,
        }
    }

    /// Get the unblinded token and provider secret
    pub fn blinded_message(&self) -> RistrettoPoint {
        self.blinded_message
    }
}

4. Lastly, in the main function, we use our data structures to generate and verify a token

fn main() {
    // Generate primitives for the mint
    let mint = MintCrypto::new();

    // Generate primitives for the provider
    let provider = ProviderCrypto::new(mint.public_key());

    // The mint generates a blinded token from the provider's `blinded_message`
    let blinded_token = mint.blinded_token(provider.blinded_message());

    // The provider unblinds the token
    let unblinded_token = provider.unblind(blinded_token);

    // The mint proves whether the token is valid or not
    assert!(mint.proof(unblinded_token));
}

That’s it. We have created an algorithm for generating Ecash tokens using the blinded Diffie-Hellman-Merkle algorithm.

The source code can be found at — https://github.com/448-OG/Blinded-Diffie-Hellman-merkle/blob/master/src/main.rs

References

1. https://en.wikipedia.org/wiki/Ecash
2. http://www.hit.bme.hu/~buttyan/courses/BMEVIHIM219/2009/Chaum.BlindSigForPayment.1982.PDF
3. https://gist.github.com/callebtc/557e4cc15f9e43d7474c7cb3d31ee8ed
4. https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
5. https://en.wikipedia.org/wiki/Curve25519
6. https://en.wikipedia.org/wiki/Montgomery_curve
7. https://ristretto.group/