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:
- a secret key and a public key for the mint
- a secret key for the provider
- a nonce generated by the provider
- an algorithm to transform our secret into a point on an elliptic curve (blinding factor)
- an algorithm to blind the provider secret (blinded message)
- an algorithm to generate a blinded signature from the blinded message
- 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.
- Bob generates a secret key
k
from some 32 random bytes and then multiplies that by a generatorG
to generate a public keyK
and let’s all providers knowK
K = k * G - Alice generates a
secret
key from 32 bytes - Alice generates a random nonce as the
blinding_factor
- Alice generates a point on the elliptic curve by running the hash to curve algorithm with her the
secret
keyhash_to_curve_result = hash_to_curve(sha512_hash(secret))
- Alice then computes a
blinded_message
by multiplying theblinding_factor
byG
and then adding it to the elliptic curve point of the hashed secrethash_to_curve
blinded_message = hash_to_curve_result + blinding_factor * G
- Alice then sends the
blinded_message
- Bob who computes the
blinded_signature
by multiplying the blinded message with his secretk
blinded_signature = blinded_message * k
- Bob then returns the
blinded_signature
to Alice - Alice computes the
unblinded_secret
by multiplying theblinding_factor
with Bob’sK
(public key) and the subtracting this from theblinded_signature
token = blinded_signature — binding_factor * K
- Alice can now share her secret
s
andtoken
secret with Carol - Carol can redeem the token by sending the secret
s
andtoken
to Bob - Bob verifies that the
token
is authentic by running thehash_to_curve()
algorithm with thesecret
key generated by Alice and passed to Carol
hash_to_curve_result= hash_to_curve(sha512_hash(secret))
- Bob then multiplies the
hash_to_curve
with his own secret keyk
hash_to_curve_result * k
- 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 featurerand_core
enables generation of random bytes from the operating system
- the featuredigest
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
- 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
}
}
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
- https://en.wikipedia.org/wiki/Ecash
- http://www.hit.bme.hu/~buttyan/courses/BMEVIHIM219/2009/Chaum.BlindSigForPayment.1982.PDF
- https://gist.github.com/callebtc/557e4cc15f9e43d7474c7cb3d31ee8ed
- https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
- https://en.wikipedia.org/wiki/Curve25519
- https://en.wikipedia.org/wiki/Montgomery_curve
- https://ristretto.group/