A digital signature is a “virtual bond” of almost any blockchain project. The vast majority of projects use practically the same signature as used on the Bitcoin network (namely ECDSA on the curve secp256k1). However, for projects in which the privacy of users plays a significant role, the creation of a digital signature often turns into a complex acrobatic act based on the latest achievements in discrete mathematics and cryptography.

The fact is that unlike ordinary blockchain projects, where the transaction clearly indicates which coin from which wallet is being spent, privacy blockchains use different methods to obfuscate the “trace”. One of the first to solve this problem was the CryptoNote project, which implemented a ring signature scheme. Such a scheme, instead of explicitly indicating the source transaction of the coins, allows for the inclusion in the signature of a group of randomly chosen transactions that are not related to this transfer. Thus an outside observer does not know from which transaction source the money is actually taken, it is only known that the sender proved his right to spend one of them. These randomly chosen transactions are called “mixins” or “decoys”, and their number determines the so-called “anonymity set”.

The most recognizable project built on the basis of CryptoNote is Monero. They have made a number of improvements over several years, hidden the values ​​of the transfer amounts, and improved the signature itself. Nevertheless, a significant problem remains in that the size of the signature and its performance linearly depends on the number of ring signature elements, i.e. the size of the ring. This imposes certain restrictions on the level of anonymity (at the time of writing, Monero uses an anonymity set 10 by default).

We in the Zano project are currently working on creating a signature in which the dependence of its size on the number of decoys would be logarithmic, allowing us to increase the anonymity set by orders of magnitude and, therefore, raise the level of privacy. Anton Sokolov came up with an interesting way to implement such a signature a few months ago, and after he formulated it and published its basic theoretical aspects, we decided to bring together our efforts. Anton joined our team, and now we are actively exploring the possibilities of building technology based on this signature.

If you are proficient with mathematics, then you can familiarize yourself with this work here (the work is periodically revisioning as the reviewers comment), however, many members of our community, who are not engineers or mathematicians, have asked us to tell at the everyday level what the idea of this signature is and why it should work. We thought about how this could be done, and Anton came up with the offbeat idea of describing it in the form of a “bar metaphor”.

What you will read below may seem sort of surreal to you, and this is normal, because what is described there actually happens “in another dimension” and requires some abstract thought. We wrote this text to try to visually illustrate the starting concept of this work, and, of course, such a metaphor does not fully explain the whole essence — it’s a kind of teaser for the work itself, and might serve as a good starting point before diving into the full details later on.

Part 1: Bar Competition

There is a bar in town. The townspeople, visitors of the bar, have perfect taste and can always tell one drink from another by taste, if they are different drinks. Drinks are mixtures of different ingredients, for example, rum, vodka, wine, fruit juices, etc. Two drinks are considered the same if the proportion of all components in one of the drinks is perfectly equal to the proportion of all components in the other, otherwise the drinks are considered different.

The bar owner announces a competition: any visitor can participate in the competition to play against the bar owner. The visitor’s challenge is to reproduce the drink that the bartender makes, but at the same time the visitor must follow a predetermined procedure for mixing drinks, and if at the end of the whole procedure it turns out that the drink the visitor made matches the drink that the bartender made, then it is concluded that the visitor managed to “pass the validation procedure” (and if we get ahead of ourselves, he managed to break the signature and ruin the theory). If the visitor manages to pass the validation procedure and, at the same time, if his original glass(Z) contained alcoholic and citrus drinks, then he wins and the bar owner gives him all the drinks from the shelves for free.

In order to keep the narrative not too far from mathematical reasoning, let’s imagine there is a device in the bar that allows you to mix drinks in certain proportions. For example, you can put a bottle of vodka and a bottle of rum (or two containers with some other drinks) into the device, specify the ratio 449/17, and get a container with a drink containing vodka and rum in an exact ratio of 449/17. Also, the bar has a generator of random evenly distributed proportions from 1/100000 to 100000/1. The design of the mixing device and the proportion generator is open, no one doubts the correctness of their work. Also, for completeness, the bar has an electronic taster which, when poured two drinks, shows a green light if the drinks are the same, and a red one if the drinks are different. An electronic taster is never wrong, all residents of the city can confirm this.

The bartender has four large boxes of pure rum, vodka, lemon and orange juices respectively. Everyone knows that if you compose a drink from these four components, then you can never reproduce a drink of the same taste from other components or from the same components with a different percentage. “Other components” are drinks made from other products, such as pomegranate or milk. Mixtures of the above four components ( rum, vodka, lemon and orange juices) are not considered to be other components.

Step 1: So, the game begins when the visitor puts on the table a glass marked with the letter Z, containing a drink that only he knows. The visitor knows the ratio of the components of the drink in this glass, i.e. he knows the recipe for how to make the contents of Z, but keeps this recipe a secret. It is only known that according to the conditions, the visitor must add citrus and alcohol to Z. In addition, the visitor puts on the table a second glass marked as H1 with some content that he chooses and the recipe for which he may or may not know, i.e. the visitor is free to pour anything into the H1 glass.

Step 2: The bartender receives a ratio c11 from the generator of random proportions, mixes rum and vodka in this proportion and places a glass R1 with the resulting alcoholic drink on the bar counter. Then, the bartender receives a c13 ratio from a random proportion generator, mixes lemon and orange juices in this proportion and places an R2 glass with the resulting citrus drink on the bar counter. All visitors to the bar, including the visitor-participant, see the values ​​of c11 and c13, and also see that the bartender prepares the contents of glasses R1 and R2 from the specified components in the specified proportions.

Step 3: The visitor, knowing the proportions c11 and c13, takes part of the contents of his glasses Z and H1 and mixes them in a certain proportion r1 determined by him, and places the third glass, S1, with the resulting mixture on the table. The visitor can show the r1 value to everyone, including the bartender, although the bartender is not interested in it. Everyone, including the bartender, only makes sure that the S1 glass contains a mixture of only the contents of Z and H1. Then, the visitor prepares the contents of a fourth glass, H2, and puts it on the table. The visitor can show everyone how he prepares the content of H2, or he can not show it. The visitor is free to pour anything into the H2 glass in any proportions, and even, as in the H1 glass, pour a completely unknown liquid.

Step 4: The bartender receives the ratio c2 from the generator of random proportions, mixes the contents of glasses R1 and R2 in this proportion, and places the glass R with the resulting alcoholic-citrus drink on the bar counter. Everyone sees the proportion of c2, and also that the content of R is obtained honestly from the content of R1 and R2 in this proportion.

Step 5: The visitor, now knowing also c2, mixes the contents of glasses S1 and H2 in a certain proportion r2 determined by him and pours the result into the fifth glass, S2, which he places on the table. Everyone makes sure that only the contents of S1 and H2 are poured into S2.

Step 6: The electronic taster is poured drinks from the R and S2 glasses. If the red light is on, then the game ends and the visitor only pays for the consumed drinks. If the green light is on, then the validation procedure is considered passed.

Now the final check is carried out: the visitor informs everyone of the recipe, i.e. the components and percentage of the contents of his glass Z. The bartender prepares the indicated composition and openly compares it on the electronic taster with the remaining contents in glass Z, thereby certifying to everyone that the visitor has correctly named the recipe for the contents of Z. If the visitor has named it incorrectly, the game ends and the visitor only pays for consumed drinks. If, according to the recipe, it turns out that both alcohol and citrus juice are present in glass Z, then the visitor wins and takes all the drinks from the shelves of the bar, of which there are a lot.

In other words, in this game, the validation procedure is created by the bar owner in such a way that it would be impossible for the visitor to find the right mix ratios to obtain an analogue of R if the Z glass contains the components of both mixes: strong alcohol (rum and vodka) and citrus (lemon and orange juice). The green light never comes on when comparing R and S2, if Z contains, for example, a mixture of orange juice-rum or rum-vodka-lemon juice or vodka-lemon-orange juice, etc. Rather, in such cases, it can light up only with a negligible probability, and the owner of the bar, who fumbles a little in mathematics, knows this.

This may not be obvious to the bar visitors, they reason something like this: let’s say we will not add any other components to the Z glass except rum, vodka, lemon and orange juices, because if we add something else, for example, milk, then it will necessarily be present in S2 and, thus, in S2 there will always be something different from R. But if we pour into Z, for example, rum and lemon juice, then knowing c11, c13, c2 and having the ability to choose the content H1, H2 and the proportions r1, r2, we can always balance the composition of S2 so that it is the same as in R.

Thus, bar visitors begin to participate in the competition, trying to cheat the validation procedure. But, alas, none of them is able to determine H1, then r1 and H1 in response to c11 and c13, then r2 in response to c2 so that the compositions of S2 and R are the same if Z contains alcohol and citrus juice in non-zero proportions …

Over time, it becomes clear that if you pour into glass Z, for example, only alcohol, i.e. a mixture of rum and vodka, pour pure vodka into H1, then select r1 so that in S1 it turns out the same as in R1, and in H2 pour a lemon-orange mixture in a proportion of c13, then in S2 it is easy to get the same composition as that in R.

Part 2: Bar Competition Re-mix

Seeing fading interest in the game, the bar owner announces: now, if the game has not ended at the fifth step of the validation procedure, the final check will be softer. Now the final check will be as follows: if it is proved that there is only alcohol in the glass Z, then it is enough to provide evidence that citrus juice is present in one of the glasses H1 or S1, and then the visitor wins. If it is proved that only a citrus component is in Z, then it is enough to provide evidence that alcohol is present in one of the glasses H1 or S1, and then the visitor also wins.

But again, no one is able to win and take all the drinks off the shelves of the bar. Then, the owner brings and installs in the bar a device called a “Beverage Inverter”. This device accepts a glass of any, even unknown, drink as input and provides a glass with the same amount of “anti-drink” as a result. For example, if you input a glass of vodka to the Beverage Inverter, you will get a glass with the same amount of “anti-vodka”, or “minus-vodka”. Now if you pour some units of vodka and the same amount of “minus-vodka” into a glass, you get an empty glass. Likewise, if you add a unit of “minus-vodka” to a glass containing three units of gin and rum, and then add the result to a glass with four units of vodka, you get a glass with three units of gin, rum and vodka each.

The bar owner announces: it is now possible to use the anti-drink generator in the game when mixing the contents of all glasses. Negative proportions are added to the random proportion generator, which means that one of the components is passed through the anti-generator when mixed. The validation procedure remains the same, with only one condition: none of the ratios r1 and r2 should be zero, and no glasses should be empty during validation. An ”alcohol-only” mixture is now understood as a mixture consisting only of alcoholic components in a positive or negative proportion, just like for a “citrus-only” mixture.

Well, now, it would seem, the validation procedure and weakened verification can be bypassed and the game won. However, still no one is able to determine H1, then r1 and H1 in response to c11 and c13, then r2 in response to c2 so that the compositions of S2 and R are the same if there is something in Z, H1 and S1 different from either only a rum-vodka mixture, or from only lemon-orange.

Part 3: Wait a second! Is that an element of a cyclic group of prime order that you’re drinking?!

The validation procedure invented by the bar owner is similar to the Lin2-Xor cryptographic scheme of the lemma in the draft on eprint. Noticing this similarity, the townspeople ask why the mixes of drinks in glasses behave like elements of a cyclic group of prime order, where the discrete logarithm problem is hard, or even as points of the main subgroup of the cryptographic curve ed25519 used in the Zano system?

It’s very simple: drink mixtures in glasses have, if we have an anti-drink generator, the same properties as the points of the main subgroup of the ed25519 curve. Rather, the points on ed25519, of course, have more interesting properties, but the properties used in the Lin2-Xor lemma are the same.

Therefore, if any of the visitors in the competition can still win all the booze from the shelves, this would mean a disproof of the Lin2-Xor lemma. But, since no one has succeeded so far, it means that no one has yet been able to disprove it in this way (can the reader succeed in this?).

And how do pure drinks (rum, vodka, lemon and orange juices) in the bartender’s containers correspond to points (group elements) P1, Q1, P2, Q2 in the lemma condition? They correspond directly. Points P1, Q1, P2, Q2 must be such that none of them is a linear combination (mixture) of others from the same set. This is achieved by applying an ideal hash function on the points of the curve. The same is true with base drinks: lemon juice, for example, should not be obtainable by mixing rum, vodka and orange juice in any (including negative) proportions, and this is the case.

This is in many ways similar to the metaphor of mixing paints, only with paints the problem is that there are only three basic colors from which, according to general belief, all other colors are composed. It is easier with drinks: you can add as many as you like to these four, and it is convenient to combine them in pairs, for example, red and white wine, milk and yogurt …, even Coca-Cola with Pepsi-Cola. Obviously, pairing is figurative, for clarity.

Theoretically, multidimensional linear spaces could be used for the explanation, but mathematicians say that trying to visualize four-dimensional space is unhealthy, so drinks have been chosen for now. However, frankly, the equations for bar drinks are the same as for multidimensional linear spaces.

It is necessary to clarify what the “unit of drink” means in terms of points on the cryptographic curve, because we cannot measure the “unit of a point on the curve”, we can operate only with the point itself, that is, multiply it by a number, divide, invert, and add it with other points. Yes, there is no concept of “unit of a point on a curve”, but in all procedures of the competition “units of a drink” are taken only in relation to “units of another drink”, i.e. “units” are used for proportioning purposes only. Proportions can also be created from the points of the curve, because they might be multiplied by numbers and added.

Both for drinks and for points of the curve, if the proportion of two drinks (points) is set, then it is not considered possible to guess the ratio of the components in it without having some additional information, for example, without having a recipe for preparation. Referring to linear spaces, for the linear space of drinks with a basis of components such as vodka, rum, juices, etc., as well as for the linear space of points of a cryptographic curve with a basis of hashes of points on the curve, the inner product function is not specified, so the projections and the lengths in these spaces are not defined.

Is comparison of drinks on an electronic taster a comparison of points for equality? Almost, with the difference that the electronic taster is less critical of drinks than the equality test. The electronic taster is not sensitive to the volume of drinks at the input, i.e. in terms of points, it compares two points up to some known number, by which one of them is multiplied. Thus, the taster does not diminish the chances of the visitor cheating on the verification procedure, compared to using a pure equality test for points.

Part 4: The Lin2-Selector Lemma

Another important element of the new signature is the Lin2-Selector lemma, and in order to describe it in the context of the same bar metaphor, we will change the game again as follows: now the bartender has not four, but eight basic drinks: rum and vodka, lemon and orange juices, red and white wine, Schweppes and Coca-Cola. If a visitor manages to compose something different from one of the four in glass Z: only strong alcohol, only citrus juice, only a wine mixture, only soda, and pass the validation procedure with a final check, then he wins.

The validation procedure is now slightly lengthened. Instead of the first two steps, on which, on the one hand, the bartender generates random proportions first (c11, c13), and then c2, and accordingly mixes the base drinks, while on the other hand, the visitor first composes the proportion and the glass (r1, H2), and then the proportion r2, and mixes his drinks, now there are three steps. From the bartender’s side, these three steps look like generation (c11, c13), then (c21, c23), then c3, and mixing accordingly. From the visitor side, the three steps look like composing (r1, H2), then (r2, H3), then r3, and mixing.

It turns out that the validation procedure skips only the above four mixtures and nothing else; it is not known how to deceive it. Moreover, if the bartender has 16 basic drinks and generates (c11, c13), (c21, c23), (c31, c33), c4, and the participant generates (r1, H2), (r2, H3), (r3, H4), r4, then the validation procedure will skip only eight mixes of base beverage pairs. In the same way, you can use 32 base drinks, 64, 128, etc., and get one of, respectively, 16, 32, 64 mixtures of pairs of drinks. This is the Lin2-Selector protocol lemma.

Let’s go back to the points on the cryptographic curve. If we take, say, 1024 base points combined into 512 pairs, then the Lin2-Selector protocol of the lemma allows you to select a linear combination of points from exactly one pair, without missing any other points or combinations. This requires about log (1024) steps, since each doubling of the base set of points requires adding one step to the verification procedure.

If we make an analogy with the Merkle Tree, then, without going into the details of the implementation, there, too, to prove that some element belongs to some fixed set of elements, it is required to take log steps. The main difference is that in the Merkle Tree we are revealing the element for which we prove that it belongs to a fixed set. In the Lin2-Selector protocol of the lemma, we can quite easily hide the element for which we are proving belonging to a set.

In bar terms, the root of the Merkle Tree is like the bartender’s R glass, although the bartender’s actions for the Merkle Tree are different. And the proof of the belonging of the drink in the glass Z to the set of basic drinks is a sequence of log numbers of glasses H1, H2, H3, …. At the same time, both the composition of the contents of the glasses and the exact volume of the contents are critically important for the Merkle Tree. For the Lin2-Selector protocol of the lemma, the volume of the contents of the glasses is not important, only the proportions of the components are important. For the Merkle Tree, you can’t do with proportions alone.

But wait, the Merkle Tree is a non-interactive data structure, and the Lin2-Selector lemma protocol and the bar contest are interactive games between two participants. How do we compare a non-interactive structure with an interactive game? The fact is that in cryptography, many interactive games are transformed into non-interactive ones using a technique called the Fiat-Shamir Heuristic. This is such a widely used technique that we do not stop at it, and consider the non-interactive and interactive versions of the Lin2-Xor and Lin2-Selector lemma protocols simultaneously. Thus, we compare the non-interactive version of the Lin2-Selector lemma protocol and the non-interactive Merkle Tree.

According to the Lin2-Selector lemma, in order to hide an element of a set, the prover provides not the element of the set itself, but this element multiplied by some secret scalar, and provides a proof for it. Thus, the prover does not provide that particular glass of orange juice that he has, but, say, 1/379 of that glass, and keeps the number 1/379 a secret. Does that hide the orange juice well in the glass? Well, specifically orange juice it does not hide in any way, but if we are talking about the points of the cryptographic curve, it absolutely hides them, just like, for example, the public key completely hides the private key. This is due to the discrete logarithm problem having no efficient solution on the elliptic curve.

A logical question may arise, why do we need pairs of elements? Pairs of elements are only needed to apply the Lin2-Xor and Lin2-Selector lemma: this is a technical necessity. We make one of the elements in each pair so that the prover cannot mix it with other elements, and this is easy to do. By the way, this technical element only adds anonymity.

And, to finish, a few words about “linking tags” — the linking tag of the CryptoNote format (quite a bit modified) only helps us, because if we mix this linking tag with a public stealth address, then we get just the linearly independent base element that we need in the Lin2-Xor and Lin2-Selector lemmas. To get the log-size ring signature, we compose the basic elements of the ring in this way, and then the sender anonymously proves that he knows the private key of one of these elements.

Afterword

If you made it this far (and understood all of the above) then congratulations! You’ve proven yourself to be just the kind of determined, mathematically-minded privacy advocate that we at Zano love (maybe you belong among us!). We hope it was interesting. If anyone found any mistakes here or in the paper itself — please write to us or jump into Discord for a chat, we‘d be glad to have your input!