MimbleWimble Without the Scary Math

The basic ideas of MimbleWimble originated in 2016, proposed by the pseudonymous Tom Elvis Jedusor. In 2019, two groups (GRIN and BEAM) had launched cryptocurrency systems implementing the ideas outlined in the original proposal. Privacy technologies such as ZK-SNARKs are spectacularly complex, shrouded in deep mathematical mysteries, and tainted by conspiracies because of their reliance on trusted setups.

In comparison, MimbleWimble’s design is much simpler, and even without a cryptography background, it’s still possible to learn the basics of how it works.

The goal of this article is to give an overview of how privacy works in MimbleWimble. We will start with a Bitcoin transaction, where all the numbers being sent and received are publicly known, and try different ways to obscure/hide the numbers. In the end, we will be able to build a MimbleWimble transaction by hand.

All the math you need to know is multiplication!

Bitcoin Transaction Structure

MimbleWimble transactions are structurally similar to Bitcoin transactions. In MimbleWimble the numbers being sent/received are hidden, but in Bitcoin the numbers are in the clear.

A transaction consists of n inputs (the money being sent) and m outputs (the money being received):

Input1 Output1
Input2 Output2
       Output3

You can’t receive more money than being sent, therefore the inputs MUST equal to outputs:

Input1 + Input2 = Output1 + Output2 + Output3

All nodes would verify that this equation is indeed true, and no new money had been created from thin air.

With Bitcoin, you can see what the values of these inputs and outputs are:

Input(10) + Input(10) = Output(5) + Output(5) + Output(10)

It’s easy to verify this transaction, simply by adding all the numbers up, and see if the final result is 0:

10 + 10 + (-5) + (-5) + (-10) = 0

Hiding The Numbers

The only thing that the public need to verify is that that no new money had been created. It doesn’t really matter if the numbers themselves are known or not.

Could we somehow hide the amounts, yet still make it possible to check that the equation is 0?

How about let’s transform the numbers:

十 + 十 + 负五 + 负五 + 负十 = 零

If an observer does not understand Chinese characters, we have successfully “hidden” the amounts. It is easy to design a function to verify if the result is zero when operating on these Chinese characters.

But of course, this privacy scheme is useless to anyone that understands Chinese.

Can we do better to hide the numbers? One idea, perhaps, is to hide the amounts by hashing them with md5:

md5(10) = 31d30eea8d0968d6458e0ad0027c9f80
md5(-5) = 3c2d7129f782f00f91e06d0acbc86ee6
md5(-10) = 55e14d2eebc71f250aec8e273775240e

Then we build an equation with these md5 hashes:

0x31d30eea8d0968d6458e0ad0027c9f80 +
0x31d30eea8d0968d6458e0ad0027c9f80 +
0x3c2d7129f782f00f91e06d0acbc86ee6 +
0x3c2d7129f782f00f91e06d0acbc86ee6 +
0x55e14d2eebc71f250aec8e273775240e

It looks like that MD5 does a pretty good job hiding the numbers. An observer looking at these numbers would have a hard time figuring out what the original number was. But there is a big problem: the equation is no longer zero.

What we want is a way to hash these numbers, yet adding the hashes still “equals to zero”:

hash(10) + hash(10) + hash(-5) + hash(-5) + hash(-10) = hash(0)

I use the word “hash” here loosely, because it’s a familiar idea to programmers. The key idea is to transform a number to another (big) number, but it’s very difficult to go in reverse. Giving you the hash “0x55e14d2eebc71f250aec8e273775240e”, it’s difficult to guess that it’s md5(-10).

Hashes That You Can Do Math With

The key problem with MD5, is that it’s not designed so you can add the hashes together in a meaningful way. We want a special kind of hashing function, so an equation is still valid AFTER hashing your original numbers:

a + b = c
hash(a) + hash(b) = hash(c)

If we can find such a hashing function, then we can hide the numbers, yet still, obey the “sum to zero” requirement.

How about raising our numbers to the power of 2?

2^10 * 2^10 * 2^-5 * 2^-5 * 2^-10 = 2^0

Our numbers are now hidden as powers of 2, and “equals to zero”, where “zero” is 2⁰.

inputs = 1024 * 1024
outputs = 32 * 32 * 1024
inputs / outputs = 2^0

While it’s still easy to figure out what numbers would translate to 1024 and 32, at least we have an equation that’s equal to zero, and that’s the most important thing!

We can easily improve on this idea. Instead of 2, let’s use the prime number 131:

inputs = 1488377021731616101801 * 1488377021731616101801
outputs = 38579489651 * 38579489651 * 1488377021731616101801
inputs / outputs == 2^0

Now it’s not so trivial to figure out what the original numbers are, yet it’s still easy to verify that the equation is zero.

This trick is called a “homomorphic hashing”. Homo meaning “same”, and “morph” meaning shape.

To make the hashing secure, you could either use very large prime numbers or use more advanced mathematical objects such as elliptic curve points. In either case, the algebra is the same, hiding the amounts by making them the exponents of a base.

Adding Random Salts To Amounts

Even if it’s hard to figure out in reverse what number is hidden by “1488377021731616101801”, there is still the problem that “10” is a very common number, and many people would try to hash 10, and get exactly the same number “1488377021731616101801”.

For example, I could precompute the hashes of all the popular numbers, say 1–10:

131, 17161, 2248091, 294499921, 38579489651, 5053913144281,
662062621900811, 86730203469006241, 11361656654439817571,
1488377021731616101801

Then it’s just a simple task of matching the hidden values on-chain to these known hashes. Some rare numbers (1.19481172) would be hard to reveal, but I bet I can reveal a lot of the common numbers.

Password hashing has the same problem. If a hacker steals a database of hashed passwords, it might be possible to reverse some password hashes by testing for common passwords such as “12345678”, “nopassword”, or “19890604”.

The typical way to fix is to add random data to the hash as salt, so that hashing the same data would still produce different results:

md5(IFNQKQP-10) = ee12b21ef289223cd1d8a0c8aff28d92
md5(UQYNBBZ-10) = aa588a4450e286d80b89adc5d489745e

Let’s add “random salt” to our previous design so the same amount hashes to different numbers. In the literature, this salt is called the “hiding factor”.

Encode the amounts as powers of 2, and multiply these numbers by random powers of 3, like this:

inputs = (3^15*2^10)*(3^48*2^10)
outputs =(3^91*2^5)*(3^87*2^5)*(3^44*2^10)

Each component of the equation is now different:

(3^15*2^10) == 14693280768
(3^48*2^10) == 81680837710717450100081664
(3^87*2^5) == 10344253117733585097352767383083528699308384
(3^91*2^5) == 837884502536420392885574158029765824643979104
(3^44*2^10) == 1008405403836017902470144

And the transaction looks like:

inputs = 14693280768*81680837710717450100081664
outputs = 10344253117733585097352767383083528699308384*
    837884502536420392885574158029765824643979104*
    1008405403836017902470144

We expect all the powers of 2 to cancel out, and leaving only the powers of 3:

inputs = (3^15*3^48)*(2^10*2^10);
outputs = (3^91*3^87*3^44)*(2^5*2^5*2^10);
inputs / outputs = (3^15*3^48)/(3^91*3^87*3^44) = 3^15*3^48*3^-91*3^-87*3^-44

Instead of testing for zero, we now test if the equation is equal to the products of the powers of 3. MimbleWimble calls this final number “the kernel”:

kernel=1/7282483350946404208076885500996745047522350034970917293604274649554310785067

Combining everything, you can now build a MimbleWimble transaction:

{
   inputs: [14693280768, 81680837710717450100081664],
   outputs: [
    10344253117733585097352767383083528699308384,
    837884502536420392885574158029765824643979104,
    1008405403836017902470144
   ],
   kernel: 1/7282483350946404208076885500996745047522350034970917293604274649554310785067
}

Indeed, if you peek into Grin’s source code, you’ll see that its Transaction type has this structure:

pub struct TransactionBody {
    /// List of inputs spent by the transaction.
    pub inputs: Vec<Input>,
    /// List of outputs the transaction produces.
    pub outputs: Vec<Output>,
    /// List of kernels that make up this transaction (usually a single kernel).
    pub kernels: Vec<TxKernel>, 
}

Elliptic Curve Points As “Numbers”

So far, we’ve used plain integers to create the inputs and outputs, following this equation:

H^amount * G^salt

But if we could abstract this equation, in an OOP sort of way, so that whatever object types that satisfy the basic rules of multiplication could also work:

h.exponent(amount).multiply(g.exponent(salt))

In programming, we could accomplish this with polymorphism. As long as an object quacks like a number, you can use it like a number. “Group theory” is a subject of abstract algebra, and it gives you the definitions and theorems to think about mathematical operations in a polymorphic way.

Classic cryptographic systems like RSA are based on numbers we are used to, but modern cryptography (since 1980s) had moved on to using elliptic curve points instead. A general rule of thumb is that if you use 1024-bit prime numbers for security, you could get the same amount of security with just 128-bit elliptic curve points.

Elliptic curves are defined by the following equation:

y^2 = x^3 + a x + b

You get different curves for different values of a and b:

Bitcoin (as well as Grin) uses the curve y^2 = x^3 + 7

By a freak mathematical coincidence, there’s a way to create functions that add points on the elliptic curve. Issac Newton first figured this out.

And since elliptic curve points can support arithmetic operations (in group theory jargon, the points form a Group), you could just drop them in as numbers into the same equations.

In other words, we can go from numbers:

// 3^15 * 2^10
h^value * g^salt

To using elliptic curve points:

// H is a base point on an elliptical curve
// G is a different base point on an ellipitcal curve
H^value * G^salt

This representation of a value (G^n), mixed with a random hiding factor (H^m) is called the Pedersen Commitment.

MutliAssets Transaction

To support different kinds of assets in the same transaction, we can simply choose a different basis (base points, or power bases) to hide the values for different assets. For example, we could use 7 for one asset, and 11 for another:

inputs = 7^5*11^5
outputs = 7^3*7^2*11^3*11^2
inputs/outputs = 1

As expected, the inputs and outputs cancel out to 1.

It is important that the two bases (7 & 11) share no common factors, otherwise, it might be possible to convert one type of asset to another, yet keeping the equation 0. Let’s see what might go wrong if we choose 2 and 4 as the basis:

inputs = 4^2 // asset B
outputs = 2^4 // asset A
inputs/outputs = 1

We’ve secretly converted 2 asset B to 4 asset A.

If we are using elliptical curve points as bases, the same precaution must apply. If we choose A, B, C, D and base points cannot be known as “common factors” to relate these base points to one another. We don’t know a solution to the equation A^n == B, or between any other pairs of A & C, A & D, B & C, etc…

To allow users to publish confidential assets, we must have a way to ensure that they choose base points that have no known factoring relationship with any other base points. To ensure this, we use the Shallue and van de Woestijne hashing algorithm, which “hashes” any chosen data to a base point.

We could generate three base points by hashing the symbols of the assets:

BTC = ShallueWoestijne("BTC")
ETH = ShallueWoestijne("ETH")
QTUM = ShallueWoestijne("QTUM")

Then we could construct transactions using these base points:

inputs = BTC^2 * ETH^4 * QTUM^6
outputs = BTC^1 * BTC^1 * ETH^2 * ETH^2 * QTUM^3 * QTUM^3
inputs / outputs == 1

Notational Difference

If you go on to read more about MimbleWimble, you may see that the Pedersen Commitment is defined using addition to combine two products::

value*H + salt*G

Whereas in this article we’ve use multiplications to combine two exponents:

H^value * G^salt

Reading cryptographic papers, you’ll often see these two alternative forms, expressing the same idea. The Bulletproof paper uses the exponentiation form:

Whereas the Rust implementation of Bulletproof uses the additive form:

Previously, we’ve seen that elliptic curve points could be used as numbers, “satisfying the multiplication interface”:

h.exponent(amount).multiply(g.exponent(salt))

Suppose the exponent and multiply methods are implemented on the “ECCPoint” class, we could refactor the code by renaming exponent as “multiply”, and multiply as “add”:

h.multiply(amount).add(g.multiply(salt))

Simply renaming the methods obviously doesn’t make a difference. Although this seems like a silly argument, it captures the deeper truth that we are operating on these objects, but it doesn’t matter what names we give to the actual operation.

If we expand the two equations in terms of the basic operations being done, we can see that the two forms are structurally the same:

// value*H + salt*G
H+H+H...(value times) + G+G+G...(salt times)
// H^value * G^salt
H*H*H...(value times) * G*G*G...(salt times)

The words “exponent”, “multiply”, “add” strongly reminds us of the arithmetic operations on ordinary numbers we are familiar with. When using ordinary numbers, they ARE addition and multiplication. When operating on ECC points, vectors, matrices, polynomials, or other exotic objects, “add” or “multiply” are just convenient names for operations that satisfy some rules.

It is common to see mathematicians using the more generic, and less misleading symbol ★:

H★H★H...(value times) ★ G★G★G...(salt times)

Mixing programming and math metaphors again, we could say that the class “ECCPoint” is a group, if you can apply the “★” operation on the base points H and G repeatedly:

h = H
for i to amount:
   h = h ★ H
g = G
for i to salt:
   g = g ★ G

Furthermore, to be a “group”, there needs to be a zero, and inverse for every element, and the operation must be associative. If you want to know the nitty-gritty details, there is a nice set of Abstract Algebra video lectures from Socratica.

So, why do some people prefer to use + and some people prefer to use *?

Don’t ask, Holy Wars had been started on lesser controversies than that!

Summary

This concludes a simple tour of the basic cryptographic principles of MimbleWimble. Aside from its simplicity, there are many interesting implications we did not get into. For example, it’s possible to combine transactions together, removing intermediary inputs and outputs.

We also didn’t get into rangeproof, which must be provided for each input and output to ensure that the amount hidden is in the expected range (i.e. non-negative).

But with some simple mathematics, we now understand the following MimbleWimble jargon:

• Kernel
• Blinding factor
• Pedersen commitment
• Homomorphic hashing

There are a lot more details and little problems to take care of, and for all that, I recommend reading the Grin intro:

mimblewimble/grin

And if you like to read code, @jaspervdm has some Python code that generates a Grin transaction:
https://github.com/GrinSwap/proof-of-concept/blob/master/examples/simple_tx.py#L18