AOS Ring Signatures: The Builder of Transaction Privacy
AOS Ring Signatures: The Builder of Transaction Privacy
Well, it’s a New Year (2024), and my New Year’s resolution is to get more in-depth with methods and try and analyse and implement privacy in a mathematical way. And, so, for the 15 years of advancement of blockchain methods, I want to understand the theoretical underpinning of transactional privacy.
One of the best implementations of this is with the Monero cryptocurrency, and which anoymises the sender and the receiver, along with the transaction amount. But, to understand the method that Monero uses, we need to go back to the original ring method produced by Abe, Okhubo and Suzki (AOS), and which produced an elegant solution for elliptic curve methods:
Up to this time, ring signatures used the RSA method, and was rather cumbersome. With AOS, we now had an elliptic curve method:
AOS ring signatures
AOS ring signatures are used in confidential transactions, and where we can hide the signer of a transaction. The method has been used to integrate into the Borromean Ring Signature method, and was published as “1-out-of-n signatures from a variety of keys” [1]. It has since been expanded by Maxwell [2] with multiple rings and which creates the Borromean ring signature methods, and which has then been used by Monero to create a privacy-preserving cryptrocurrency [3].
We initially have a number of public keys for n partipants: [P0,P1,…Pn−1]. With this there is an associated private key of x_i for a public key of:
P_i=x_i.G
and where G is the base point on the curve. We then have a message of M and have a participant j, initially select a random value of α to get:
Q=α.G
and then:
e_{j+1}=H(Q||M)
and where “||” is a concatenation of the byte values. At j+1, we select a random value of s_i and then let:
e_{i+1}=H(s_i.G+s_i.P_i || M)
Finally, we complete the ring with:
sj=α−ej.xj
This is achieved using the Schnorr signature approach. The signature is then:
σ=(e0,s0,s1…sn1)
This is illustrated in Figure 1 [4].
Practical example
The theory section may have been a little difficult to follow, so let’s break it down into steps for three participants (N=3). First, we create the key pairs of {P_0, P_1, P_2])} and where we will sign with \(x_1 and where:
P_1=x_1.G
The code for this is then:
// Make key pairs
priv := make([]*btcec.PrivateKey, N)
pub := make([]*btcec.PublicKey, N) for i := 0; i < N; i++ {
priv[i], _ = btcec.NewPrivateKey(curve)pub[i] = priv[i].PubKey()
}
Next we start at index 2, and let α equal to a random value, and:
e2=H(α.G||M)
The code to compute Q=α.G
is then:
alpha, _ := rand.Int(rand.Reader, curve.N)
Qx, Qy := curve.ScalarBaseMult(alpha.Bytes())Next, we can hash the message (and all of the public keys) with:
Parr := []*btcec.PublicKey{}
for i := range pub {
Parr = append(Parr, pub[i])
}
M := HashMsgVerificationKey([]byte(msg), Parr)The value of e2 is then created with:
e2=H(α.G||M)
This can be coded with:
e := make([]*big.Int, N)
e[2] = HashBigInt(
[]*big.Int{
M,
Qx,
Qy,
},
)Now we select a random value s2 and compute:
e_0=H(s_2.G+e_2.P_2||M)
This can be achieved with [5]:
s := make([]*big.Int, N)
s[2], _ = rand.Int(rand.Reader, curve.N)
sGx, sGy := curve.ScalarBaseMult(s[2].Bytes())
ePx, ePy := curve.ScalarMult(pub[2].X, pub[2].Y, e[2].Bytes())
sumx, sumy := curve.Add(sGx, sGy, ePx, ePy)
e[0] = HashBigInt(
[]*big.Int{
M,
sumx,
sumy,
},
)Next we select a randome value s_0 and compute:
e_1=H(s_0.G+e_0.P_0||M)
This can be achieved with [5]:
s[0], _ = rand.Int(rand.Reader, curve.N)
sGx, sGy = curve.ScalarBaseMult(s[0].Bytes())
ePx, ePy = curve.ScalarMult(pub[0].X, pub[0].Y, e[0].Bytes())
sumx, sumy = curve.Add(sGx, sGy, ePx, ePy)
e[1] = HashBigInt(
[]*big.Int{
M,
sumx,
sumy,
},
)Finally, to complete the ring we compute with the private key of participant 1 (x_1):
s_1=α=e_1.x_1
This is implemented as:
s[1] = new(big.Int).Sub(alpha, new(big.Int).Mul(e[1], priv[1].D))
s[1] = new(big.Int).Mod(s[1], curve.N)and we should have completed the ring.
Verification
The signature is then:
σ=(e0,s0,s1…sn1)
The verifier now computes:
e1=H(s0.G+e0.P0||M)
e2=H(s1.G+e1.P1||M)
e′0=H(s2.G+e2.P2||M)
and then checks:
e′0=e0
Coding
The coding is [5]:
package main
import (
"crypto/rand"
"crypto/sha256"
"fmt"
"math/big"
"os"
"github.com/btcsuite/btcd/btcec"
)
func HashBigInt(a []*big.Int) *big.Int {
digest := sha256.New()
for i := range a {
digest.Write(a[i].Bytes())
}
output := digest.Sum(nil)
tmp := output[0:len(output)]
return new(big.Int).SetBytes(tmp)
}
func HashMsgVerificationKey(msg []byte, keys []*btcec.PublicKey) *big.Int {
a := []*big.Int{}
for i := range keys {
a = append(a, keys[i].X)
a = append(a, keys[i].Y)
}
return HashMsg(msg, a)
}
func HashMsg(msg []byte, a []*big.Int) *big.Int {
digest := sha256.New()
digest.Write(msg)
for i := range a {
digest.Write(a[i].Bytes())
}
output := digest.Sum(nil)
tmp := output[0:len(output)]
return new(big.Int).SetBytes(tmp)
}
func main() {
curve := btcec.S256()
msg := "Hello"
argCount := len(os.Args[1:])
if argCount > 0 {
msg = os.Args[1]
}
N := 3 /// Three participants
e := make([]*big.Int, N)
// Make key pairs
priv := make([]*btcec.PrivateKey, N)
pub := make([]*btcec.PublicKey, N)
for i := 0; i < N; i++ {
priv[i], _ = btcec.NewPrivateKey(curve)
pub[i] = priv[i].PubKey()
}
alpha, _ := rand.Int(rand.Reader, curve.N)
Qx, Qy := curve.ScalarBaseMult(alpha.Bytes())
Parr := []*btcec.PublicKey{}
for i := range pub {
Parr = append(Parr, pub[i])
}
M := HashMsgVerificationKey([]byte(msg), Parr)
e[2] = HashBigInt(
[]*big.Int{
M,
Qx,
Qy,
},
)
fmt.Printf("e[%d]=%s\n", 2, e[2])
s := make([]*big.Int, N)
s[2], _ = rand.Int(rand.Reader, curve.N)
sGx, sGy := curve.ScalarBaseMult(s[2].Bytes())
ePx, ePy := curve.ScalarMult(pub[2].X, pub[2].Y, e[2].Bytes())
sumx, sumy := curve.Add(sGx, sGy, ePx, ePy)
e[0] = HashBigInt(
[]*big.Int{
M,
sumx,
sumy,
},
)
fmt.Printf("e[%d]=%s\n", 0, e[0])
s[0], _ = rand.Int(rand.Reader, curve.N)
sGx, sGy = curve.ScalarBaseMult(s[0].Bytes())
ePx, ePy = curve.ScalarMult(pub[0].X, pub[0].Y, e[0].Bytes())
sumx, sumy = curve.Add(sGx, sGy, ePx, ePy)
e[1] = HashBigInt(
[]*big.Int{
M,
sumx,
sumy,
},
)
fmt.Printf("e[%d]=%s\n", 1, e[1])
s[1] = new(big.Int).Sub(alpha, new(big.Int).Mul(e[1], priv[1].D))
s[1] = new(big.Int).Mod(s[1], curve.N)
fmt.Printf("\ns[%d]=%s\n", 0, s[0])
fmt.Printf("s[%d]=%s\n", 1, s[1])
fmt.Printf("s[%d]=%s\n", 2, s[2])
fmt.Printf("\n=== Now let's check by computing e[2] ===\n")
sGx, sGy = curve.ScalarBaseMult(s[1].Bytes())
ePx, ePy = curve.ScalarMult(pub[1].X, pub[1].Y, e[1].Bytes())
sumx, sumy = curve.Add(sGx, sGy, ePx, ePy)
edash := HashBigInt(
[]*big.Int{
M,
sumx,
sumy,
},
)
fmt.Printf("e'=%s\n", edash)
if edash.Cmp(e[2]) == 0 {
fmt.Printf("We have completed the ring!!!")
}
}A sample run is:
Message=Hello
e[2]=63654016903249411012303649920469463006138687211019865082155716856050232921888
e[0]=26302213551057003222608573543787744695110919031953547029702649636253204670271
e[1]=68997527827376829165644562694489787475916230339423968316646679158127858638263
s[0]=114648186897421511854486873774394865580491178505478529924136211954212449292567
s[1]=91895294096620934283941049881346625911739049453005969823054756922952285688798
s[2]=18883104233748514607788066489644147200962604662396668107588378604112601386008
=== Now let's check by computing e[2] ===
e'=63654016903249411012303649920469463006138687211019865082155716856050232921888
We have completed the ring!!!Conclusions
If you want to learn more about bulletproofs and rangeproofs, try here:
https://asecuritysite.com/bulletproof
References
[1] Abe, M., Ohkubo, M., & Suzuki, K. (2002, November). 1-out-of-n signatures from a variety of keys. In International conference on the theory and application of cryptology and information security (pp. 415–432). Berlin, Heidelberg: Springer Berlin Heidelberg.
[2] Maxwell, G., and Poelstra, A. (2015). Borromean ring signatures. Accessed: Jun, 8, 2019.
[3] Ren, Y., Zhao, Q., Guan, H., & Lin, Z. (2020). On design of single-layer and multilayer code-based linkable ring signatures. IEEE Access, 8, 17854–17862.
[5] https://github.com/blockchain-research/crypto/tree/master/brs