Lets quickly build up a ECC system so that we are all on the same page.
First, define a finate field F_q where q is a large prime.
Operations in F_q are all done modulo q.
We have a standard algebra over this field:
let a ∈ F_q Zero Element: 0 ∈ F_q One Element: 1 ∈ F_q Add. Inverse: -a ∈ F_q where a + (-a) = 0 (denoted a - a) Mult. Inverse: if a ≠ 0 then a^-1 ∈ F_q where a ⋅ a^-1 = 1
Addition and multiplication follow the standard algebra laws (commute., assoc., distributive)
We have a standard algebra over this field:
let a ∈ F_q Zero Element: 0 ∈ F_q One Element: 1 ∈ F_q Add. Inverse: -a ∈ F_q where a + (-a) = 0 (denoted a - a) Mult. Inverse: if a ≠ 0 then a^-1 ∈ F_q where a ⋅ a^-1 = 1
Addition and multiplication follow the standard algebra laws (commute., assoc., distributive)
i.e. q = 5
F_5 = { 0, 1, 2, 3, 4 }
2 + 3 = 0 mod 5 2 * 3 = 1 mod 5 ==> 2^-1 = 3
The curves we work with in ECC take the form of
y^2 = x^3 + ax + b
where y, x, a, b ∈ F_q
Choices for a and b defines the curve shape.
e.g. Bitcoin uses a = 0, b = 7
y^2 = x^3 + ax + b
Points (x, y) that satisify the curve equation are part of the Curve Group E(F_q):
E(F_q) = { (x,y) | y^2 = x^3 + ax + b }
E(F_q) forms an abelian (commutative) group, which means:
Let P, Q ∈ E(F_q)
Identity Element: O ∈ E(F_q) where O + P = P Inverse Element: -P ∈ E(F_q) where P + (-P) = P - P = O Closure: P + Q ∈ E(F_q) Commutative: P + Q = Q + P
Point Doubling: P + P
We can denote this doubling as 2P, similarly P + P + P = 3P
2P + 3P = (2 + 3)P = 5P
Note 2, 3, 5 ∈ F_q .
Point Doubling: P + P
We can denote this doubling as 2P, similarly P + P + P = 3P
2P + 3P = (2 + 3)P = 5P
Note 2, 3, 5 ∈ F_q .
We can abuse this notation and can pick arbitrary scalar x ∈ F_q
xP = P + P + \cdots + P – P added to itself x times
xP + yP = (x + y)P
let G ∈ E(F_q)
G is said to be a generator of E(F_q) if we can generate all points in E(F_q) by repeatedly adding G
E(F_q) = {G, G + G, G + G + G, G + G + \cdots + G, \cdots }
We can check if G is a generator by multiplying by q ∈ F_q, simply check
qG = O
Given generator G ∈ E(F_q) and point P ∈ E(F_q)
finding an x ∈ F_q s.t. xG = P is considered difficult
This is the hard problem that underpins ECC.
Alright. that’s it for the basics
Secret Key: x ∈ F_q – drawn at random Public Key: P = xG
We can do math on these keys, e.g. simple aggregate keys:
P_1 + P_2 = x_1 G + x_2 G = (x_1 + x_2)G = P_agg
Setup:
Say we have a DBC we’d like to spend but we don’t want to expose ourselves.
Plan: mix our key in with a ring of n other decoys to obfuscate exactly who is spending the DBC
Setup:
Say we have a DBC we’d like to spend but we don’t want to expose ourselves.
Plan: mix our key in with a ring of n other decoys to obfuscate exactly who is spending the DBC
n ∈ Z – the size of our ring x ∈ F_q – our secret key msg = <dbc reissue bytes>
n ∈ Z msg = <dbc reissue bytes> x ∈ F_q
We’d also like to detect double spends without exposing our public key. To do this, we define the key-image:
I = xHp(xG) = xHp(P)
Where Hp: E(F_q) → E(F_q) is a hash function from point to point
We’ll include `I` in our ring signature as proof that we are the owner of the secret key.
Verifiers will log these key-images in a spentbook to detect double spends.
n ∈ Z msg = <dbc reissue bytes> x ∈ F_q I = xHp(xG)
Choose a random index π ∈ 1..n, keep this secret.
This will be your position in the ring.
P_π = xG
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π)
Find n-1 decoy keys to hide our key in:
P = {P_1, P_2, \cdots P_π, \cdots P_n}
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n}
We must now generate some random blinding values:
s = {s_1, \cdots, s_π, \cdots s_n} – where s_i ∈ F_q are random values (i ≠ π) α ∈ F_q – random
We will fix s_π later.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
We now have all the material we need to generate the ring signature.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
We start the ring at π, computing cπ+1
L_π = α G R_π = α Hp(P_π) cπ+1 = Hs(msg, L_π, R_π)
Where Hs : (bytes, E(F_q), E(F_q)) -> F_q is a hash function to field elements.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
We then move along the ring, using the previous hash c_i to compute ci+1.
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
If we study this loop, we can see that only, `s`, `c`, `I`, `P` and `msg` are used.
This should give us a hint of what our signatures should be.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
`P` and `msg` will be the public key and message components of our signature scheme.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
Leaving `s`, `c`, `I` and indeed our signature will end up being:
sig = (s, c, I)
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
Better yet, since ci+1 is computed in terms of c_i, we can shorten our signature to
sig = (s, c_1, I)
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
Better yet, since ci+1 is computed in terms of c_i, we can shorten our signature to
sig = (s, c_1, I)
To verify the signature, one would iterate starting at index 1, computing the ring of hashes c_i
for i in 1 \cdots n { L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
And finally check that
cn+1 = c_1
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
If (s, c_1, I) is to be our signature, we need a way to compute cπ+1 using only s_π and c_π. That is we need:
L_π = s_π G + c_π P_π R_π = s_π Hp(P_π) + c_π I cπ+1 = Hs(msg, L_π, R_π)
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
L_π = s_π G + c_π P_π R_π = s_π Hp(P_π) + c_π I cπ+1 = Hs(msg, L_π, R_π)
But, recall, we had initialized the ring with:
L_π = α G R_π = α Hp(P_π) cπ+1 = Hs(msg, L_π, R_π)
Luckily, s_π has not yet been defined! We have one crucial degree of freedom to make this work.
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
L_π = s_π G + c_π P_π
L_π = α G
Pairing up L_π’s
α G = s_π G + c_π P_π = s_π G + c_π (xG) α G = (s_π + c_π x)G α = s_π + c_π x α - c_π x = s_π !!!
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
R_π = s_π Hp(P_π) + c_π I
R_π = α Hp(P_π)
Let’s check our math with R_π
R_π = s_π Hp(P_π) + c_π I = (α - c_π x) Hp(P_π) + c_π I = α Hp(P_π) - (c_π x) Hp(P_π) + c_π I = α Hp(P_π) - c_π (xHp(P_π)) + c_π I = α Hp(P_π) - c_π I + c_π I = α Hp(P_π) !!!
It works!
n ∈ Z π ∈ 1..n msg = <dbc reissue bytes> x ∈ F_q I = xHp(P_π) P = {P_1, P_2, \cdots P_π, \cdots P_n} s = {s_1, \cdots, s_π, \cdots s_n} α ∈ F_q
Tieing it all together:
L_π = α G R_π = α Hp(P_π) cπ+1 = Hs(msg, L_π, R_π)
for offset in 1 \cdots n-1 { i = π + offset mod n
L_i = s_i G + c_i P_i R_i = s_i Hp(P_i) + c_i I ci+1 = Hs(msg, L_i, R_i) }
s_π = α - c_π x
signature = ({s_1, \cdots s_π, \cdots s_n}, c_1, I)
Input: P, (s, c_1, I), msg: <bytes>,
c’_1 = c_1
for i in 1 \cdots n { L_i = s_i G + c’_i P_i R_i = s_i Hp(P_i) + c’_i I c’i+1 = Hs(msg, L_i, R_i) }
assert c’n+1 = c_1
LSAG Ring Singatures