Eve Does Some Magic with Nothing Up Her Sleeve
Eve Does Some Magic with Nothing Up Her Sleeve
Right. Eve The Magician asks the audience for a value of G, and Carol shouts out “5”. Eve then asks Alice to think of a number (a) and multiply the two values together to give y:
y = aG
“Don’t tell me the result”, says Eve. She now asks for another number from the audience, and they shout out “7”. Eve writes something on a piece of paper, and shouts out that her answer is “38”. She turns to Alice and asks her for the result of her calculation, and she says that y is “10”. The audience are worried that Eve has failed in her trick.
“But”, she says, “my card says a value of ‘4’”, and she shows this to the audience, “Now please calculate z, and which is aG + bH”. What is the value that you get?”. Alice calculates and shows her calculation:
“38”
“And that is the answer that I showed you before I knew Alice’s value”, says Eve to great applause. This the Pedersen Commitment in action, and where Eve committed to a value, and then blinding her guess. She then revealed her blinding factor, and showed that she knew the answer all along.
In this case Alice’s secret was “2” and Eve’s blinding factor was “4”, so Eve got:
z = aG + bH = 2*5 + 4 * 7 = 38
Eve knew that Alice was going to pick “2” (don’t ask why, as she is a magician), so she blinded it with “4”, and was able to show that she knew Alice’s value.
This is known as Pedersen Commitment — or nothing up my sleeve (NUMS) — and where we produce our commitment and then show the message that matches the commitment. In its core form, we can implement a Pedersen Commitment in discrete logs [here]. But blockchain, IoT, Tor, and many other application areas, now use elliptic curve methods, so let’s see if we can make a commitment with them.
Adding a blinding value
For this, we can obscure the values in a transaction by adding a blinding value. Let’s say that we have a transaction value of v, we can now define this as a point on the elliptic curve (H) as:
v×H
If we have three transactions (v1, v2 and v3), we can create a sum total of:
Total=v1×H+v2×H+v3×H=(v1+v2+v3)×H
We can thus determine the sum of the transactions. But we could eventually find-out the values of v1, v2 and v3, as they would always appear as the same value when multiplied by H. We can now add a blinding factor by adding a second point on another elliptic curve (G) and a private key (r). A transaction value is then (as defined as a Pedersen Commitment):
C = v×H+r×G
Let’s say that Bob has two input values (v1 and v2) and one output value (v3), and where v3= v1+v2. We can then create a blinding factor for each transaction:
C = (ri1×G+vi1×H)+(ri2×G+vi2×H)=(ro3×G+vo3×H)
Then:
ri1+ri2=ro3
In this case if we can prove this, we have proven that the inputs are equal to the outputs. A sample run is [here]:
Alice's secret key: 110672200165973757670706606013807185435784586203078289927107093258368544244209
Alice's public key: (97877912897005737218928527353789673381377340700475699151216756276689766435015L, 87838438629927847912046825769741818157159420065666269753906778707978168856075L)
==========================
Transaction (r1*G + v1*G) + (r2*G +v2*G): (75012975245730542912551430086949413769034689023115807054516566426350436876319L, 42840948626806857828893112378852997190784128370121817339191672098791182051629L)
Transaction (r3*G + v3*G): (75012975245730542912551430086949413769034689023115807054516566426350436876319L, 42840948626806857828893112378852997190784128370121817339191672098791182051629L)
Now let's compare...
Success!
The code is:
import collections
import hashlib
import random
import binascii
import sys
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')curve = EllipticCurve(
'secp256k1',
# Field characteristic.
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f,
# Curve coefficients.
a=0,
b=7,
# Base point.
g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8),
# Subgroup order.
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141,
# Subgroup cofactor.
h=1,
)
# Modular arithmetic ##########################################################
def inverse_mod(k, p):
"""Returns the inverse of k modulo p.
This function returns the only integer x such that (x * k) % p == 1.
k must be non-zero and p must be a prime.
"""
if k == 0:
raise ZeroDivisionError('division by zero')
if k < 0:
# k ** -1 = p - (-k) ** -1 (mod p)
return p - inverse_mod(-k, p)
# Extended Euclidean algorithm.
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, k
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
assert gcd == 1
assert (k * x) % p == 1
return x % p
# Functions that work on curve points #########################################
def is_on_curve(point):
"""Returns True if the given point lies on the elliptic curve."""
if point is None:
# None represents the point at infinity.
return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_add(point1, point2):
"""Returns the result of point1 + point2 according to the group law."""
assert is_on_curve(point1)
assert is_on_curve(point2)
if point1 is None:
# 0 + point2 = point2
return point2
if point2 is None:
# point1 + 0 = point1
return point1
x1, y1 = point1
x2, y2 = point2
if x1 == x2 and y1 != y2:
# point1 + (-point1) = 0
return None
if x1 == x2:
# This is the case point1 == point2.
m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
else:
# This is the case point1 != point2.
m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % curve.p,
-y3 % curve.p)
assert is_on_curve(result)
return result
def scalar_mult(k, point):
"""Returns k * point computed using the double and point_add algorithm."""
assert is_on_curve(point)
if k % curve.n == 0 or point is None:
return None
if k < 0:
# k * point = -k * (-point)
return scalar_mult(-k, point_neg(point))
result = None
addend = point
while k:
if k & 1:
# Add.
result = point_add(result, addend)
# Double.
addend = point_add(addend, addend)
k >>= 1
assert is_on_curve(result)
return result
# Keypair generation ################################################
def make_keypair():
"""Generates a random private-public key pair."""
private_key = random.randrange(1, curve.n)
public_key = scalar_mult(private_key, curve.g)
return private_key, public_key
r1=10
r2=15
v1=5
v2=7
r3=r1+r2
v3=v1+v2
aliceSecretKey, alicePublicKey = make_keypair()
bobSecretKey, bobPublicKey = make_keypair()
print "\nAlice\'s secret key:\t", aliceSecretKey
print "Alice\'s public key:\t", alicePublicKey
print "\n=========================="
va = point_add(scalar_mult(r1*bobSecretKey,curve.g),scalar_mult(v1*bobSecretKey ,curve.g))
vb = point_add(scalar_mult(r2*bobSecretKey ,curve.g),scalar_mult(v2*bobSecretKey ,curve.g))
vr1 = point_add(va,vb)
print "Transaction (r1*G + v1*G) + (r2*G +v2*G): ",vr1
vr2 = point_add(scalar_mult(r3*bobSecretKey ,curve.g),scalar_mult(v3*bobSecretKey,curve.g))
print "Transaction (r3*G + v3*G): ",vr2
print "\nNow let's compare..."
if (vr1[0]==vr2[0]):
print "Success!"
else:
print "Failure!"
So what?
The method we have just defined creates a whole new world which respects privacy. In this example, you can replace a transaction value with anything … the cost of your cup of coffee, the time our get up in the morning, your vote in an election, the number of miles you drive, and so on. For all our data we can add blinding values, and where the value used to blind the transaction value is not revealed. Perhaps it could be a single blinding value for a whole lot of transactions, such as in a bank, or where every transaction is blinding?
In a blockchain world, this is a perfect solution, and where we can show our commitments to things, without actually revealing our data. Let’s say you take a test, and you answer each question, and store your answers as commitments onto the blockchain. The blockchain then gives the evidence that you submitted your commitments before the test ended. When the answers are revealed, you can then show your answers to the questions that were correct, and only by revealing the blinding value.
The Pedersen Commitment is thus fit for a GDPR world, and we must move towards it in order to rebuild the Internet in a trusted way. Blockchain will thus provide us with a way to store our commitments, without giving any of our data away, and where we can reveal things as required, and for them to be trustworthy. At the core, is the control of the data, and that it will be in the hands of those with the blinding factors.