A digital signature is a “virtual bond” of almost any blockchain project. In the overwhelming majority of projects, a signature is used that practically does not differ from the signature used in the Bitcoin network (namely, ECDSA on the secp256k1 curve). However, digital signature creation for projects in which the "privacy" of users plays a significant role often turns into a complex acrobatic act based on the advanced achievements in the field of discrete mathematics and cryptography.
, -, , , “”. , , CryptoNote, . , - , , . , , - . , . “” “mixins” “decoys”, “anonymity set”.
, CryptoNote, Monero. , , . , , , ( , Monero anonymity set 10).
, Zano , decoys , anonymity set, , , . Anton Sokolov , , , , .
, - , , .. “ ” . , , , , , , .
. , , . , , , , , .. , . , .
, , . , , , , , , , , “ ” ( ). , , , , .
, , , , . , ( - ), 449/17, , 449 17 . 1/100000 100000/1. , . , , , , , , , . , .
, , , . , - , . , , , . .
1: , , , Z, , . , .. Z, . , , Z , . , H1 , , , .. H1 .
2: 11 , R1 . , 13 , R2 . , , 11 13, , R1 R2 .
3: , 11 13, Z H1 r1, S1 c . r1 , , . , , , S1 Z H1. , - H2 . , H2, . H2 , , H1, .
4: 2 , R1 R2 R - . 2, , R R1 R2.
5: , 2, S1 H2 r2 S2, . , S2 S1 H2.
6: R S2. , , . , .
: , .. Z. Z, , Z. , , . , Z , , .
, , R , Z , : ( ) ( ). R S2, Z , , - -- , -- , .. , , , , .
, : , Z , , , - , , , S2 , , S2 -, R. Z, , , c11, c13, c2 H1, H2 r1, r2, S2 , R.
, , . , , H1, r1 H1 c11 c13, r2 c2 , S2 R , Z .
, Z, , , .. , H1 , r1 , S1 , R1, H2 - c13, S2 , R.
2
, , , , . : , Z , , H1 S1 , . , Z , , H1 S1 , .
, . “ ”. , -. , , - -. -, . , - , , . , .
, -. , , -. , : r1 r2 , . , , , .
, , . , - H1, r1 H1 c11 c13, r2 c2 , S2 R , Z, H1 S1 -, , .
3
, , Lin2-Xor eprint. , , , discrete logarithm problem is hard, ed25519, Zano?
: -, , ed25519. , ed25519, , , , Lin2-Xor , .
, - - , Lin2-Xor-.
, , , ( ) P1, Q1, P2, Q2 ? P1, Q1, P2, Q2 , () . - . . , , , .
, , . : , , , , …, - -. , , .
, , , , - . , , , .
“ ” , “ ”, , .., , , , . , “ ” , “ ” “ ”, .. “” . , .. , .
, , (), - , , . , , , .., , “inner product”, .
? , , , . , .. - , . , .
4
Lin2-Selector , : , : , , , -. Z - : , , , , , .
. , , , (11, 13), 2, , , , , (r1, H2), r2, , . (11, 13), (21, 23), 3, , , . Co (r1, H2), (r2, H3), r3, .
, , , . , (11, 13), (21, 23), (31, 33), 4, (r1, H2), (r2, H3), (r3, H4), r4, . 32 , 64, 128 .., , , 16, 32, 64 . Lin2-Selector .
. , , 1024 , 512 , Lin2-Selector , . log(1024) , .. .
Merkle Tree, , , , . , Merkle Tree , . Lin2-Selector , .
, Merkle Tree R, , Merkle tree . Z log H1, H2, H3, …. Merkle tree , . , Lin2-Selector , . Merkle Tree .
, Merkle tree , Lin2-Selector - , ? , , , -. , , Lin2-Xor Lin2-Selector . .. Lin2-Selector Merkle tree.
Lin2-Selector , , , - , . .. , , , , 1/379 , 1/379 . ? , , , , , . , discrete logarithm problem is hard .
, ? , Lin2-Xor Lin2-Selector , . , , . , .
How does the above relate to the linking tag, have we forgotten about it? And 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 a linearly independent base element that we need in Lin2-Xor and Lin2-Selector lemmas. To get a log-size ring signature, we compose the base elements of the ring in this way, and then the sender anonymously proves that he knows the private key of one of these elements.
Conclusion
Hope you enjoyed the article. Well, if someone noticed mistakes here or in the work itself, write to us - we are always glad to opponents!