Play MimbleWimble with klefki

[45]:

from klefki.types.algebra.concrete import (
    EllipticCurveGroupSecp256k1 as ECG,
    FiniteFieldSecp256k1 as F,
    FiniteFieldCyclicSecp256k1 as CF
)
import random
import hashlib
from klefki.utils import to_sha256int
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
def random_cf() -> CF: return CF(random.randint(1, N) % F.P)
G = ECG.G

[46]:

s = bytes.fromhex("0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8")
x = int(hashlib.sha256(s).hexdigest(),16)

[47]:

H = ECG.lift_x(F(x))

Transacting with MimbleWimble

The validation of MimbleWimble transactions relies on two basic properties:

  • Verification of zero sums.

The sum of outputs minus inputs always equals zero, proving that the transaction did not create new funds, without revealing the actual amounts.

  • Possession of private keys.

Like with most other cryptocurrencies, ownership of transaction outputs is guaranteed by the possession of ECC private keys. However, the proof that an entity owns those private keys is not achieved by directly signing the transaction.

Balance

If v is the value of a transaction input or output and H a point on the elliptic curve C, we can simply embed \(H^v\) instead of v in a transaction. This works because using the ECC operations, we can still validate that the sum of the outputs of a transaction equals the sum of inputs:

[48]:

v1, v2 = random_cf(), random_cf()

[49]:

v3 = v1 + v2
H@v3 == (H@v1) + (H@v2)

[49]:

True

[50]:

H@v3 == H@(v1+v2)

[50]:

True

An input or output value in a transaction can then be expressed as:

\[rG + vH\]

Where:

\(r\) is a private key used as a blinding factor.

\(v\) is the value of an input or output and H is another point on the elliptic curve C

As an example, let’s assume we want to build a transaction with two inputs and one output. We have (ignoring fees):

  • \(vi_1\) and \(vi_2\) as input values

  • \(vo_3\) as output value.

Such that:

\[vi_1 + vi_2 = vo_3\]

Generating a private key as a blinding factor for each input value and replacing each value with their respective Pedersen Commitments in the previous equation, we obtain:

\[(ri_1G + vi_1H) + (ri_2G + vi_2H) = (ro_3G + vo_3H)\]

Which as a consequence requires that:

\[ri_1 + ri_2 = ro_3\]
[51]:

v1, v2 = random_cf(), random_cf()
v3 = v1 + v2
assert v1 + v2 == v3

[52]:

r1, r2 = random_cf(), random_cf()

r3 = r1 + r2

[53]:

G@r1 + G@r2 == G@r3

[53]:

True

[54]:

H@v1 + H@v2 == H@v3

[54]:

True

[57]:

(G@r1 + H@v1) + (G@r2 + H@v2) == G@r3 + H@v3

[57]:

True

Ownership

In the previous section we introduced a private key as a blinding factor to obscure the transaction’s values. The second insight of Mimblewimble is that this private key can be leveraged to prove ownership of the value.

Alice sends you 3 coins and to obscure that amount, you chose 28 as your blinding factor (note that in practice the blinding factor, being a private key, is an extremely large number). Somewhere on the blockchain, the following output appears and should only be spendable by you:

\[X = 28G + 3H\]
[59]:

x = G@28 + H@3

\(X\), the addition result, is visible to everyone. The value 3 is only known to you and Alice, and 28 is only known to you.

To transfer those 3 coins again, the protocol requires 28 to be known somehow. To demonstrate how this works, let’s say you want to transfer those 3 same coins to Carol. You need to build a simple transaction such that:

\[Xi \rightarrow Y\]

Where \(Xi\) is an input that spends your \(X\) output and \(Y\) is Carol’s output. There is no way to build such a transaction and balance it without knowing your private key of 28. Indeed, if Carol is to balance this transaction, she needs to know both the value sent and your private key so that:

\[Y - Xi = (28G + 3H) - (28G + 3H) = 0G + 0H\]

By checking that everything has been zeroed out, we can again make sure that no new money has been created.

Wait! Stop! Now you know the private keys in Carol’s output (which, in this case, must be the same as yours to balance out) and so you could steal the money back from Carol!

To solve this, Carol uses a private key of her choosing. She picks 113 say, and what ends up on the blockchain is:

\[Y - Xi = (113G + 3H) - (28G + 3H) = 85G + 0H\]
[60]:

(G@113 + H@3) - (G@28+H@3) == G@85 + H@0

[60]:

True

Now the transaction no longer sums to zero and we have an excess value (85), which is the result of the summation (and correspondingly subtraction) of all blinding factors. Note that \(85G\) is a valid public key for the generator point \(G\).

Therefore, the protocol needs to verify that the transacting parties collectively can produce the private key (85 in the above example) for the resulting point Y - Xi (this should be the corresponding public key, for generator point \(G\); \(85G\) in the above example). A simple way of doing so is by using the public key \(Y - Xi (85G)\) to verify a signature, that was signed using the excess value (85). This ensures that:

  • The transacting parties collectively can produce the private key (the excess value) for the public key (\(Y - Xi\)).

  • The sum of values in the outputs minus the sum of values in the inputs is zero (otherwise there would be no correspondence between private and public keys, which is exactly the reason for having a signature).

This signature, attached to every transaction, together with some additional data (like mining fees), is called a transaction kernel and is checked by all validators.

[ ]: