Privacy is one of the most concerning issues in the 21st century and the subject of a lot of internal research and discussion at PPIO. Given the importance of this issue, there are many technologies related to privacy protection in the blockchain world. Our previous article, The A-to-Z on zkSnarks discussed why a zero-knowledge proof is ideal for authentication so no one else knows what you’re communicating. Today we will analyze another technology related to privacy: Ring Signatures.
To recap a zero-knowledge proof means that the prover must convince the verifier that an assertion is correct without revealing any useful information to the verifier. In other words, I need to prove to you that I know a secret, however, I can’t let you know what that secret is. Ring signatures, on the other hand, is where you hear a secret, however, you don’t know which person in a group has said it to you. A ring signature achieves the purpose of protecting the identity of the signer by hiding his public key into a set of public keys.
Ring signatures were first proposed in 2001 by the three cryptographers: Rivest, Shamir, and Tauman. A ring signature, also known as CryptoNote, originally evolved from group signatures. Group signatures are a method for verification by using a group public key and a group signature. The verifier can verify the correctness of the group signature by using the group public key, but cannot determine the formal signer in the group. However, the problem with this method is that the group administrator can revoke the signature and expose the real signer of the group signature.
Using a ring signature removes the group administrator and does not require cooperation between ring members. The signer can sign independently by using his private key and the public key of the other members in the group. The other members of the group may not know that they are included in it. The advantage of this is that besides the unconditional anonymity of the signer, other members of the ring cannot forge the true signer’s signature. An external attacker also cannot forge a signature even if it is based on a valid ring signature.
Application Scenario
Currently, several projects that use ring signatures include Monero, Boolberry, StealthCoin, XCurrency, and others. The Ethereum platform also adds a CryptoNote-like ring signature.
Monero: Monero is a typical representative of the application of ring signatures. The ring signature technology makes Monero a public-private, untraceable cryptocurrency. The ring signature helps Monero realize the privacy of transactions as unrelated nodes on the blockchain cannot trace the sender of the transaction. When other nodes verify the transaction, they can only determine that the signature is one of many public keys, they cannot locate which public key is the specific sender.
One-Vote Veto Scenarios: For example, a chairman of an association proposes a motion, however, if someone in the association raises an objection, then the bill must be canceled. If in this case, the member who voted against it does not want to reveal his identity, he can use ring signature technology to sign his negative vote with his private key and the public key of the other members of the association. After signing, all members of the association can see that some of the members of the association opposed the bill, however, they do not know who exactly opposed it.
So how does ring signature do all this? In the next section, we will use elliptic curves to illustrate the key points and principles of a ring signature.
Interested in understanding elliptic curves? As part of our Code Talks series, we made a presentation on elliptic curves that even a beginner can understand. Click the link to see how they work.
How Is A Ring Signature Generated?
Suppose the signer has a private key sk and a public key pk. Where:
pk = sk·g
- g is the base point on the elliptic curve; also known as a generator
- “·” is scalar multiplication
- sk·g means that sk g points are added on the elliptic curve
- For convenience, everything bolded is represented by points on the elliptic curve
Steps To Generate A Ring Signature:
● First, the hash function must be defined. The hash function input is a point on the message m to be signed and point A on an elliptic curve, i.e., Hash (m, A). This hash function, like the elliptic curve, is a prerequisite for the signature and verification system.
A reference implementation of the hash function is that the byte data of M and A are spliced together, then the values obtained by using the traditional hash function (such as keccak256) are modular to N (where N is the order of a finite group on an elliptic curve).
● Next, the signing party wants to sign a message m, but does not want to let others know their identity while signing. The signing party then hides in a group by means of a ring signature. The signing party finds the public keys of n-1 people (keys which have appeared and been used in the system before, otherwise the signer can be easily identified by hiding amongst a group of new people). The signer numbers these keys, and randomly inserts his own public keys into a collection of n public keys. Let’s assume that the n public keys are:
pk[0], pk[1], pk[2], …, pk[i-1], pk[i], pk[i+1], …, pk[n-1]
Where pk[i] is the public key of the signing party.
● The signer randomly generates n-1 random numbers s[0], s[1], …, s[i-1] , s[i+1], …, s[n-1] respectively. They correspond to n-1 public keys except for pk[i].
Note: This step does not need to generate s[i] randomly, because s[i] will be calculated later.
● Next, the signer randomly generates k and calculates k·g. We can assume:
Equation 1：k·g = s[i]·g + c[i]·pk[i]
According to Equation 1, we can determine that if we have the private key sk[i]of pk[i] and if c[i] and k are known, we can find s[i] in reverse.
Note: c[i] here is the hash value calculated from the previous public key pk[i-1] and message m
● Next is the introduction of the second formula,
Equation 2: c[x] = Hash(m, s[x-1]·g + c[x-1]·pk[x-1])
Equation 2 is a recursive formula, and the second parameter form of Hash function is the same as the right side of Equation 1. This recursive formula means that when the s[x-1] and hash value c[x-1] corresponding to the x-1 public key are known, the hash value c[x] corresponding to the next public key will be calculated. Note that when x = 0, the previous x is actually n-1, because the subscript also takes a module for n.
● For equation 1, we define k · g = s[i] · g + c[i] · pk[i], therefore c[i +1] can be obtained directly from the calculation:
c[i+1] = Hash(m, s[i]·g + c[i]·pk[i]) = Hash(m, k·g)
Note: At this time, we do not yet know s[i] and c[i] when calculating c[i+1]. Once c[i] is calculated, we can find s[i].
Next we can sequentially calculate c[i+2] , … , c[n-1] , c[0] , …, c[i-1], c[i]: (Figure 1)
c[i+2]= Hash(m, s[i+1]·g +c[i+1]·pk[i+1])
…
c[n-1] = Hash(m, s[n-2]·g +c[n-2]·pk[n-2])
c[0]= Hash(m, s[n-1]·g +c[n-1]·pk[n-1])
c[1]= Hash(m, s[0]·g +c[0]·pk[0])
…
c[i]= Hash(m, s[i-1]·g +c[i-1]·pk[i-1])
Figure 1: Computational c[i+1], … , c[n-1], c[0], …, c[i-1], c[i] Process
● Now that c[i] is solved, we can look back at Equation 1. As we know that the private key of pk[i] is:
pk[i] = sk[i] · g
Thus Equation 1 can be written as
k·g = s[i]·g +c[i]*sk[i]·g
We can then remove g on both sides
k = s[i] + c[i] *sk[i]
Thus k, c[i] , sk[i] can be obtained s[i] (Fig 2), i.e.,
s[i] = k - c[i] *sk[i]
Note: The private key sk[i] plays a role here. If there is no sk[i], then s[i] cannot be found.
Figure 2 solves the s[i] process based on the private key sk[i] , k, c[i]
● Once s[i] is calculated by k, c[i] and sk[i], the “ring” is established; we can then drop k, because it is not needed anymore.
In other words, because we have the private key sk[i], we can find s[i] with the randomly generated s[0] , s[1] , …, s[i-1] , s[i+1] , …, s[n-1], which makes the following formulas true:
c[0] = Hash(m, s[n-1]·g +c[n-1]·pk[n-1])
c[1] = Hash(m, s[0]·g +c[0]·pk[0])
…
c[n-1] = Hash(m, s[n-2]·g +c[n-2]·pk[n-2])
On the other hand, if the signer doesn’t have any private keys of the n public keys, he cannot calculate s[i] which makes {c[0], pk[0], …. pk[n-1], s[0], …., s[n-1]} and is needed to form a ring.
Therefore, if the above n equations are true, it also means that the person who generates the n equations has at least one private key of the n public keys.
● The ring signature data of the last message m is:
Signature = {c[0], pk[0], …. pk[n-1], s[0], …., s[n-1]}
Signature Verification Process
The verifier obtains c[0], pk[0], …. pk[n-1], s[0], …., s[n-1], message m, and Equation 2, then finds c[1] , c[2] , …., c[n-1]. Finally, c[0]’ is calculated according to c[n-1] and judged
c[0] ?= c[0]’
If they are equal, the signature is valid; if not, the signature is invalid.
In Summary
Looking back at the entire process of generating a ring signature, if you know the private key sk[i], then you can deduce s[i] so that c[1] , c[2] , …., c[n-1] forms a ring. Another way of thinking about it is if you want to loop a wire. The mathematics guarantees that only the person with the private key can connect the two ends of the wire to form a loop. Moreover, once it becomes a loop, there is no trace at the joint, which makes it impossible for someone to judge where the wire was connected.
Although the ring signature can be used to achieve a certain degree of anonymity, the real signer will still be exposed in the ring. In the current public chain market, the zero-knowledge proof is still one of the best means to stay anonymous. That is not to say that ring signatures do not have their place or are not helpful — they are. If privacy requirements are not so high, or the signing party’s computing power is weak, a ring signature is an excellent choice.