Nothing Up My Sleeve — Creating A More Trust World with the Elliptic Curve Pedersen Commitment
Nothing Up My Sleeve — Creating A More Trusted World with the Elliptic Curve Pedersen Commitment
We give away too many of our secrets for free. Unfortunately, the data world we have created has become a watering hole for companies picking off our data, and using it for free and often without our full consent. Google, for example, knows where you like to buy your coffee in the morning, when you get up in the morning, what you are likely to buy next, and so many things about your life. Their whole business model is based on a data world where they pass on your data searches on to others, and then they pay to push adverts to you. But when was the last time that Google or Facebook paid you a commission for pushing an advert in front of you?
So could we create a world which blinded Google, governments, and others, and where no-one could see our purchases, or, in fact, anything about our lives? It would be a world where we can reveal things only to those that we trust. In this world, companies, governments, and others would have to ask us for permission to see our data, and not just push one-sided T&Cs to us. Then, if we had audit/compliance regimes, we could create blinding factors so that only they could see the required information.
So how do we create a world where we can store our secrets in a trusted and then reveal them when required? Let’s say I predict the outcome of an election, but I don’t want to reveal my prediction until after the election. Well, I could store a commitment to my prediction, and then at some time in the future I could reveal it to you, and you can check against the commitment I have made. Anyone who views my commitment should not be able to see what my prediction is.
This is known as Pedersen Commitment, 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. The classic paper is here:
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.
Unfortunately, the world we have built is NOT GDPR compliant, and don’t let your CIO tell you so. We must change, and change fast, otherwise, the whole fabric of the Internet will fall apart and be ever more untrusted. We need to put the ownership and consent of data back into the hands of those who created it … and that’s you!
Go support companies building a new world … in Scotland we have companies such as Maidsafe, Spiritus, Trisent, Wallet Services, and who put trust at the core of their world.
Here’s a quick demo on the method I’ve outlined: