Blinded Diffie–Hellman–Merkle for Ecash Mints

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

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.

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

• Generator 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 yielding 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 to Bob

7. Bob who computes the blinded_signature by multiplying the blinded message with his secret k

   blinded_signature = blinded_message * k

8. Bob then responds to Alice with the blinded_signature

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 MintCrypto to 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
        }
    }
   

5. 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.

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/