English
Schnorr Signature Algorithm of Wisdom Chain DocumentKnowledge Base
This article comes from the official Twitter of Wisdom Chain
URL：
https://twitter.com/Wisdom_Chain/status/1301382987762806784?s=20
In the last chapter, we talked about the aggregatesignature used in WisdomChain is the signature aggregation of each key generated by the parties using Schnorr signature. Now let's learn about the past and present of the Schnorr signature algorithm.
Schnorr Signature Algorithm was first proposed by German Cryptologist Claus Schnorr in 2008. In cryptography, it is a digital signature scheme, which is famous for its simplicity and efficiency. Its security is based on the intractability of some discrete logarithm problems. Schnorr's principle is described as follows:
The numbers are represented in lowercase letters, for example: a = 42. At the same time, we will use some points on the elliptic curve. These points are pairs of large numbers satisfying elliptic curve equation.
We will use capital letters to represent these points, such as A= (4,68). Some algebraic operations can be performed on points on elliptic curves. The above two points can be added together and we can get approximately random third points, which is expressed as: C=A+B. A point can be added to itself many times: D = C + C + C.
When we talk about a point adding itself many times, we call it "multiply by a number": D = 3 C. Obviously, if we add a point A to itself many times (or multiplied by a large number) and get a point B, if we only know the original point A and the result point B, it is quite difficult to calculate the large number multiplied by A. The "difficulty" here means that if we want to calculate this "big number", we can not simply divide B by A, we can only guess a value x continuously and calculate whether x A equals B.
So if the value of X is very large, even greater than the sum of all the atoms in the universe, it will take an unacceptable time to guess the value of X. At the same time, if someone holds the correct x, calculating x*A is very fast. This asymmetry will be the premise of our discussion.
Alice holds the private key x, then selects a random number r and the origin G on the elliptic curve, calculates R: = r G, public key X: = xG, uses the hash function to obtain a random number e: = Hash (R,X, message), and then calculates s: = e * x + r.
Alice sends Bob R, X, message, and point values s, Bob verifies s G equals R+e X. In fact, not only is Bob, but anyone in the world can prove this proof by itself. Once s G=R+e X passes validation, it can prove that Alice holds X of private key and generates a legal signature: (s, e).
Finally, to create a signature from this proof, Alice needs to customize a hash function to hash the message she signed. In this case, it is necessary to make sure that the signature calculated for one message cannot be reused for another message.
This customization process can be achieved by simply hashing R, X and signature information
e:=Hash(R,X,Message)
A good hash function will return a completely different hash value even if only one character is changed, making it impossible to calculate the value of S.
The brief description of Schnorr Signature Protocol is as follows:
Setup:x: random number (aka private key)G := common pointX: x*G(aka public key)Sign:r : random number (aka nonce)R: r* G(aka commitment)e : Hash(R, x, message)(aka challenge)s:=r+e*x(aka response)return (R, x, s, message)((S, e) aka signature)Verify:receive (R, x, s, message)e := Hash(R, x, message)S1:= R+e*XS2 :=s*Greturn OK if S1 qeuals S2
Based on this, developers can add more complex concepts in the future, such as WisdomChain aggregated signatures. The advantage of aggregatesignature is that all the input involved in a transaction can be completed by only one merge signature, which greatly reduces the amount of data processing and makes the network faster and more efficient.
簡體中文
本文來自Wisdom Chain官方Twitter
URL：
https://twitter.com/Wisdom_Chain/status/1301382987762806784?s=20
01
Schnorr籤名算法簡介
Schnorr籤名算法最初是由德國密碼學家ClausSchnorr於2008年提出的，在密碼學中，它是一種數字籤名方案，以其簡單高效著稱，其安全性基於某些離散對數問題的難處理性。
02
Schnorr的原理描述
下面用小寫字母表示數字，比如：a=42。同時我們將使用一些橢圓曲線(ellipticcurve)上的點。這些點是一些滿足橢圓曲線方程的大數對。
我們將用大寫字母來表示這些點，比如：A=(4,68)。橢圓曲線上的點可進行一些代數運算。其上兩個點可以相加可以得到近似隨機的第三個點，表示為：C=A+B。某個點可以與自身相加多次：D=C+C+C。
當我們講一個點與自身相加多次時，我們稱其為「乘以一個數」：D=3 C。顯而易見的，如果將一個點A與自身相加很多次（或者說將其乘以一個很大的數）然後得到一個點B，如果我們只是知道原始點A和結果點B，計算出與A相乘的這個大數是相當困難的。這裡的「困難」意思是，如果要計算出這個「大數」，我們不能簡單的用B除以A，只能不斷的猜測一個值x，計算是否x A等於B。
所以如果這個x的值非常大，甚至大於宇宙中所有原子數目的和，猜測這個x的值將花費一個難以接受的時間。同時如果某人持有正確的x，計算x*A是非常迅速的。這種非對稱性將作為我們討論的前提。
Alice持有私鑰x，然後選擇一個隨機數r，以及橢圓曲線上的原點G，計算出R:=r G，公鑰X:=xG，使用哈希函數獲取一個隨機的用於驗證的數字e:=Hash(R,X,message)，然後計算s:=e*x+r。
Alice給Bob發送點R,X,message，和點數值s，Bob驗證s G等於R+e X。事實上，不僅是Bob，這個世界上的任何人都可以獨自對這一證明進行驗證。一旦s G=R+e X通過了驗證，既可以證明Alice持有私鑰x，並生成了一個合法的籤名：(s,e)。
最終，如果要將籤名從這一證明中創造出來，Alice需要定製一個哈希函數來對她籤名的消息的進行哈希計算。這樣的話需要確定針對一個消息所計算出的籤名，不能被復用給另外一個消息。
03
R,X與籤名信息
這個定製過程可以簡單的通過將R,X和籤名信息進行哈希來做到：
e:=Hash(R,X,Message)
一個良好的哈希函數，會在哪怕僅有一個字符有更改的情況下，也會返回完全不同的哈希值，使得計算出s的值是不可能的任務。
Schnorr籤名協議的簡潔描述如下：
Setup:x: random number (aka private key)G := common pointX: x*G(aka public key)Sign:r : random number (aka nonce)R: r* G(aka commitment)e : Hash(R, x, message)(aka challenge)s:=r+e*x(aka response)return (R, x, s, message)((S, e) aka signature)Verify:receive (R, x, s, message)e := Hash(R, x, message)S1:= R+e*XS2 :=s*Greturn OK if S1 qeuals S2
基於此，開發者在未來可以添加更複雜的概念，比如WisdomChain聚合籤名。聚合籤名優勢就在於將一筆交易中所有涉及的輸入只需要一個合併籤名就可以完成，大大減少了數據處理量，使網絡速度更快，更加高效。
關注Wisdom Chain動態
Twitter：@Wisdom_Chain微博：WisdomChain知乎：智慧鏈技術社區Facebook：WisdomChainTelegram：@WisdomPublicChain相關資源
WIsdom Chain公鏈文檔知識庫：https://docs.wisdchain.com/#/
Wisdom Chain官網：
https://wisdchain.io/
Wisdom Chain技術論壇：
http://tech.wisdchain.io/
Wisdom Chain開原始碼庫：
https://github.com/WisedomChainGroup
Wisdom Chain區塊瀏覽器：
https://scan.wisdchain.com
本文來源： 微信公眾號/ 作者：WisdomChain中文社區