关键|《WisdomChasdfsin文档知识库》之Schnorr签名算法

English

Schnorr Signature Algorithm of Wisdom Chain DocumentKnowledge Base

This article comes from the official Twitter of Wisdom Chain

URL：

Schnorr Signature Algorithm of Wisdom Chain DocumentKnowledge Base pic.twitter.com/CGpagBXqQF

— Wisdom Chain Foundation (@Wisdom_Chain) September 3, 2020

In the last chapter, we talked about the aggregate signature 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 aggregate signature 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：

Schnorr Signature Algorithm of Wisdom Chain DocumentKnowledge Base pic.twitter.com/CGpagBXqQF

— Wisdom Chain Foundation (@Wisdom_Chain) September 3, 2020

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：WisdomChain

Telegram：@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