MathxH Chen
# 从群环域到椭圆曲线密码学 > *干了区块链这行当，快一年了，还没有写过有关于区块链相关的密码学呢，之前是没有仔细研究这块内容，再不自己写写总结，总有点对不住自己。如果以后不做这行了，哪敢跟别人说我曾经做过区块链啊* ## 从集合到群 首先还是从集合说起吧。 最早的时候，我记得我们应该是在初中的时候就引入集合的概念了。我们知道很多种关于数字的集合（以下字母均为大写字母）： - N表示所有自然数集合 {1,2,3,4,5 ...} - Z是所有整数的集合 {... -3, -2, -1, 0, 1, 2, 3 ...} - Q是所有有理数的集合 （有理数可以写为两个整数的比 a/b 其中a，b为整数，且b不等于0） - R是所有实数的集合...
编写设计文档，有助于设计者能理清思路，理清系统背后的各种取舍，这样也可以帮助新人快速了解整个系统。在Google里面，软件工程师在开始一项功能，从小到大都需要编写一份设计文档的，而且设计文档还需要被其他工程师review。[谷歌软件工程师是怎样写设计文档的？ - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/219907381) [(19 封私信 / 80 条消息) 在谷歌（Google）工作是怎样一番体验？ - 知乎 (zhihu.com)](https://www.zhihu.com/question/24290336/answer/1542971035) 我当时在harmony工作的时候，我发现我的直属Boss(他是从google出来的)，他也会有习惯先写一份设计文档，只是没有Google那么严格规范，比较随意。都是都有一份类似的蓝图设计，以及一些问题和取舍被描述。比如这一份设计文档 [Design Change and Optimizations for 1-Second Finality · Issue #3722 · harmony-one/harmony (github.com)](https://github.com/harmony-one/harmony/issues/3722) 我的前前Boos，也是一位区块链架构师，我第一次入门区块链，就是进去他自己从零开始写的FnFn区块链项目开始的，我也问过他相关的问题，怎样build system，他说了除了大量看别人的源码之外，就是在写代码前，先梳理下需求和功能，先想清楚怎样实现，其实大意也就是要写一份设计文档了，因为设计文档的内容也需要包含这些。 我看了几篇文章的理解就是，编写Design...
因为博客文章管理起来比较麻烦，我又换了好几台机器了，所以后面知识性和学习性的一些笔记，我会写在我的笔记里面 https://github.com/AlexiaChen/my-notes 其中觉得内容可以作为一个博客文章的，我再发布到这个仓库下的issue里面。这样我可以作为自己的知识沉淀，也好通过一些开源的笔记系统整理我的知识脉络，因为我发现Obsidian太好用了！！！！ 所以我会把我目前博客中觉得不适合作为文章的issue给它closed掉。
零知识证明综述
--- title: 零知识证明综述 date: 2019-08-20 10:14:16 tags: - 密码学 --- ## 前言 零知识证明看样子是很复杂的一个过程，其实不是，网络上对这个概念的讲解杂七杂八，质量参差不齐，今天我就打算讲一讲有关话题，我会循序渐进，每个小节我会逐渐加深理解难度，然后最后导出工业界的做法。所以读者最终要的是，首先要做到不要畏惧。实在想不明白可以用手稿纸画一画，推一推。我写文章通常的做法会在专业的名词用括号注释英文，目的是让读者不混淆，并且英文搜索到的资料更准确。 ## 研究背景 传统的通信协议中的一个共同弱点就是容易遭遇到信道的窃听，所以零知识证明（又叫零知识协议Zero Knownledge protocol，ZKP）就这样诞生了。目的是构造这样一个系统，该系统中的证明人（Prover）可以在不暴露任何信息（Zero Knowledge）的情况下，让验证者（Verifer）进行验证。简而言之，对于监听者，就是你监听了，也没用，你监听到的信息也推导不出来任何有用的东西。 ## 简介 这里要注意下，虽说到这里反复提到了证明（Proof）这个词，但是这个证明不是数学上的证明，数学证明是严格的，使用自证陈述或从预先建立好的证明中获得陈述。ZKP更类似于人类在信息交换过程中建立一个陈述的动态过程，所以它是互交式的（当然，也有非互交式的，这个到后面会提到，而工业界的zk-SNARK用的就是非互交式的）。 简而言之，在ZKP中，所谓互交式就是证明者（Prover）不为它持有的秘密（Secret）直接提供证据，而是双方在一个互交来回“对话”的过程中证明者（Prover）逐渐的说服验证者（Verfier）他持有某个秘密是真实的。Prover也不用暴露秘密就可以说服对方，这样太好了。比如，我可以宣称对外界粉丝说，刘亦菲是我老婆，也不用把结婚证（Secret）拿出来，就能向粉丝们证明我说的是真的（刘亦菲是我老婆），即真命题。哈哈，结婚证是我的秘密隐私啊，怎么可能拿出来给粉丝看。 ### ZKP中的参与者 在ZKP中，参与者也就是2方： - Alice （Prover） Alice想向Bob传达某种知识的证明，但是同时又不想暴露她的秘密...
数学学习路线图
# 数学学习路线图 ## 前言 尽量学以致用，虽然当今现代数学的发展速度超乎普通人的想象，前沿的数学理论早已经可能不能应用了。但是作为非纯数学专业的人还是尽量以应用为目的的方式，来罗列一些数学领域的学习顺序，顺带我查找资料推荐的书籍，能够应用到科技领域的数学，我也会顺带一提，数学主流还是分四研究大方向: 分析，代数，几何，拓扑。每个大方向又有无数子领域，但是学习初期，它们依赖的知识点，概念互相独立而又统一联系。所以尽量不分开讲。 但是这几个方向，还是有特点的，几何重图形与结构。分析重逼近与主次，代数重抽象与统一。可以看出来，分析是精细化推理与计算，代数更加抽象和一般化，直觉很重要，需要积累大量具体例子，几何主要就是图像了，也需要直觉。至于拓扑，其实就是几何的一个分支。 ## 正文路线图 ### 基础不牢地动山摇之数分，高代，解几 首先，还是走数学流派，国内本科大一，一般最开始是先学《数学分析》和《高等代数》了，所谓的数分高代，当然，在此之前，其实可以业余先学习了解下《数理逻辑》《集合论》（朴素集合论，公理集合论），这样是有好处的，因为数学越到后面越抽象，很多各种空间，映射等概念几乎是由集合论的描述语言外延扩展出去的，对你将来理解一些数学语言，概念有帮助。 《数学分析》其实就是高级，更严谨的《高等数学》和《微积分》，在某些观念上看，其实它们是一样的。《高等代数》其实就是更高级，更严谨的《线性代数》。这个就是数学系和工科专业的差别所在。这里会问，有没有微分方程的教材，其实一般《数学分析》里面，到后期的内容，就会涵盖一些基本的微分方程了。微分方程分为《常微分方程》（ODE）和《偏微分方程》（PDE）可深可浅，当然是先学ODE，再学PDE，本科级别的PDE不会深。 《解析几何》延续了前苏联的风格，美国大学数学系基础课一般不会开设这门课了，这门课其实我们在高中的时候就接触过一点，比如圆锥曲线，双曲线等。这是一门高中到大学的过渡课程，为后续的《射影几何》再到古典的《微分几何》（曲线与曲面的微分几何）铺垫路子。当然，大学开设的解析几何可能后续会提到射影几何里面的射影，仿射变换。如果觉得自己基础扎实，这门课可以不学，如果不扎实，可以一学，但是不要花太多功夫。它的意义也不是说没有，就是为二维，三维空间提供具体的例子，为以后铺路。当然，从大多数人士的观点来看，觉得这门课没意义，也没打什么基础，计算量还特别大（想想高考时候的压轴题），他们可以直接学《射影几何》《代数曲线》，或者用线性代数的矩阵来解决解析几何中，二维，三维空间的问题，也就是《解析几何》与《高等代数》《射影几何》某些内容合并一下。比如，我所在的区块链密码学里面涉及到的椭圆曲线就是射影几何的内容，还有一些椭圆曲线上双线性配对，双有理等价的概念是《代数几何》的内容。 数学分析我推荐的是张筑生的《数学分析新讲》，这本教材从观点上看更现代化一些。或者看普林斯顿的《微积分》或者也可以是《托马斯微积分》。这些都是分析流派的基础。基础不好，你后面就学不下去了。 《高等代数》我推荐复旦姚慕生的《高等代数学》，或者《程序员的数学--线性代数》，MIT的《线性代数及其应用》，《3D数学》，《线性代数应该这样学》，《线性代数的几何意义》。这些教材可以互相辅助来看，加深理解。当然，可能不同人的观点不同，有些人建议，在入门《线性代数》之前应该先稍微学习下《抽象代数》的前几章（不要全部学习），这样能以更加高观点的形式下理解线性空间等概念，这样接触到一些概念不会显得突兀。线性空间实际上不就是个环上模结构？这样结合的教材有《近世代数观点下的高等代数》陈辉著 《解析几何》推荐《曲线论》《曲面论》相关的书籍 ### 计算机流派的基础之离散数学 显然，数学系是不学离散数学的，数学里面也没有这个领域，这个主要是给计算机系学的，挺有用的，计算机所用的数学，几乎出自《离散数学》。但是，离散数学太杂，其实是一本大杂烩，把计算机所需要的数学，什么都讲一点，但不会太深，里面涉及的群，环，域就出自《抽象代数》，还有一些简单的《组合数学》，《图论》，《集合论》，《数理逻辑》等内容，这些内容在早期人工智能，编译器技术，程序语言理论，理论计算机，数据结构与算法等领域都有用到。《离散数学》与数分高代不冲突，可以同时学，没有什么强制的先后顺序。如果你学不好，后面的编译器设计这门课的前端，词法分析，语法分析你是学不了的，那几章都是动不动就是有限状态机，抽象语法树等抽象点的知识，后端的机器码，寄存器分配，可能还会涉及《图论》的内容。 因为离散数学学好了，你才可以按照先后学《数理逻辑》，《公理集合论》，《模态逻辑》，《计算理论》，《计算复杂性理论》等等，学完离散以后，也可以直接学《概率论》，《数理统计》等。这是两条岔路，也可能有多条岔路，毕竟离散数学真只是大杂烩。 教材我推荐《离散数学及其应用》，《数据结构与算法分析》都可以结合着看。 ### 刘姥姥进大观园之抽代，复变，实变 现在开始，开始慢慢进入现代数学的大门了，不过离前沿还太远太远。数学一直都是从具象到抽象，过渡到一般化的过程。从《抽象代数》（又叫近世代数）开始你接触的概念就慢慢开始抽象起来，不好理解，一个老师的建议就是学抽代，要试图积累尽量多的具体例子，然后才能理解抽象的概念。其实我也是学了椭圆曲线上的点的加法，才知道上面构造了一个交换群（阿贝尔群）的，这个就是具体例子，后来对交换群理解更深刻了，居然有应用，不是那么虚无缥缈的概念了。抽代里面的群，环，域，格也是《密码学》，《程序语言理论》的基础工具，如果你Haskell语言等函数式语言学深入了，也多多少少会接触点抽代。 《复变函数》《复分析》有时候两者是等价的，其实就是在复平面上研究问题，学好数分的情况下，导数自然会过渡到复平面，基础是复数的四则运算等。解析函数，级数（前提学好数学分析，里面有泰勒展开等等），留数是这门课的关键，这门课学好了，才能先后学《信号与系统》《信号处理》等应用型课程内容（傅里叶分析，可以放到复变之前学习：傅里叶分析->复分析->信号与系统）。虽然这么说，其实在工程里面的信号处理，对这门课要求并不是很高，并不需要你多么厉害的数学能力，但要知道先修课程的基本概念，会做点简单的推导就可以了。其实《信号与系统》用了复变函数，简单的微积分和一点粗浅的线性代数知识，都不会要求先修课程要学得很好，当然，你能学得更好，那自然是更好，我在这里想说，没你想象中那么难，反过来其实是说，用到的这些基础，其实都是些皮毛知识。教材推荐《复分析：可视化方法》 《实变函数》《实分析》有时候这两者也是等价的，有人说，复变是激情的爱，实变是长情的陪伴，复变容易，实变很难，复变研究性质好的函数，实变研究点集测度上性质奇奇怪怪的函数。但是两者并没有强制的先后顺序，当然，如果你担心智力问题，可以先学复变，再学实变，这是个普通人学习的自然过渡。实分析学习好了，才能学之后的《一般拓扑学》去研究拓扑空间之类的，实分析学好了也才能继续学习《泛函分析》。另外，《一般拓扑学》之前先自己学下《点集拓扑》也许会更好。 ### 本科数学系的终结之泛函分析 《泛函分析》基本是大四时候的数学课程了，首先它很难，它需要数分高代，复分析，实分析，抽代来作为基础，为什么叫泛函分析，泛函就是广泛的函数，函数的泛化，也就是函数的函数，主要研究无穷维上的线性代数。分析这个路子，基本是以Stein的教材来学习。...
# Schnorr盲签名 ## 前言 之前有写过Schnorr签名其实就是一种零知识证明协议，都会一个challenge生成 https://github.com/AlexiaChen/AlexiaChen.github.io/issues/123 也写过盲签名的大概原理，就是让签名者不知道所 签名的明文消息m，也不知道签名后的签名数据是什么。https://github.com/AlexiaChen/AlexiaChen.github.io/issues/132 下面我们就讲解一种基于Schnorr的盲化签名方案。盲化签名本质上就是要对盲化函数和去盲函数进行选择。 ## 实现 因为盲签名一般是两方协议，有客户和签名者的概念，我们这里把客户变成User（Client），签名者变成Server，来讨论。 前提条件: 假设Server有一个私钥$x$，公钥 $X = x * G$. 当然，G就是椭圆曲线上的生成元(基点)。 1. Server生成随机数nonce Server生成一个随机的秘密值$k$和公有nonce $R = k*G$ 。 R当然就是一个曲线上的随机点了，然后把着两个值保存下来。然后把nonce $R$和公钥$X$发送给User(Client)。 2....
之前在https://github.com/AlexiaChen/AlexiaChen.github.io/issues/120 这里写过Chaum-Pedersen 零知识证明方案，所以提到过Sigma Protocol 中的Equality of discrete logs 关系证明。我们来看看Schnorr签名与它有什么关系，其实Schnorr签名可以看作是proof of knowledge of secret key corresponding to a public key ( x in g^x)，而被签名的消息m增加作为hash函数的输入，以此来生成challenge。而且它们的原型就是交互式的，用hash函数生成了challenge而已，所以Schnorr签名我感觉也是一种零知识证明。 先来看Schnorr签名，再看Sigma Protocol中的proof of knowledge of discrete log吧。...
## 前言 最近在学ROS，个人写了一波学习笔记，学到TF变换那里的时候，需要用到欧拉角和四元数这些知识，欧拉角的roll, pitch, yaw倒是很好理解，更接近人的理解（欧拉角是说人话），同时也理解欧拉角造成的万向锁问题，但是我看example上的3D角度旋转都是把欧拉角转换成四元数，再通过四元数来旋转。因为四元数没有欧拉角的万向锁问题，可以做全姿态变换。我会尽可能参考很多资料，用历史的脉络来尝试讲解是四元数是怎么联系到3D旋转的，因为它不好直观形象的理解，目前从代数形式上反而容易。 ## 正文 ### 复数(二元数)与2D的关系 大家查过资料的都知道四元数(quatiernion),是复数(Complex Number)的推广(扩展)。所以我们先要从复数入手，以及推导它与二维平面旋转之间的关系。 先来回顾一下复数的定义把，任意一个复数 $z \in \mathbb{C}$,都可以表示为$z = a + bi$的形式，其中$a, b \in \mathbb{R}$ 两个都是实数，a是实部，b是虚部。当你仔细观察这个公式定义，你会发现，它是一个线性的，如果学过线性代数的都知道，这样的线性组合形式可以引出向量空间和基(Basis)的概念，所以从这个公式出发，你可以认为其实任意的复数z都可以是$(1, i)$这个基的线性组合来表示，$1和i$就是这个复数空间的基向量，基向量的线性组合张成(span)了整个线性空间,当然，这个空间是一个二维的复平面。为了简化二维复平面的概念，我们可以只用实部和虚部的标量来化简，所以我们也可以用一个二维向量来表示复数: $$ z = \begin{bmatrix} a \\...
# 系统架构之高并发 ## 场景分类 ### 侧重于高并发读的系统 1. 搜索引擎 拿熟悉的百度举例，在搜索框里面搜索关键词，展示结果网页列表，这个过程中，用户只是浏览，没有修改网页内容。 - 数量级。读的一端，C端用户，各种手机，电脑，其他App调用搜索引擎的接口，数量级是上亿，或者数十亿。写的一端（把网页数据纳入搜索引擎的存储系统中），数量级绝对是远远低于读的。 - 响应时间。读的一端通常要求在毫秒级别，最差情况为1-2s内返回结果，写的一端可能是分钟或者小时甚至天。一些网页结果甚至都不会被搜索引擎检索到。 - 频率。 读的频率远比写的高，显而易见。 2. 电商的商品搜索，描述，价格 与百度搜索之类的类似，发布商品本来频率就更低，搜索浏览淘宝之类的更多。 ### 侧重于高并发写的系统 典型的就是广告计费系统，现在各种App都有广告，点击浏览计费，就会在数据库中扣除广告主的余额。Update很多。相当于就是读多写少的大流量转化成了点击量，最终导致写多。 ### 高并发读写二者兼备的系统 1. 电商的库存和秒杀系统 库存系统和秒杀系统的一个典型特征是：C端用户要对数据库同时进行高并发读写，我买了这件衣服，那么库存中只能在另一个用户看着一定是少了一件，信息要近乎实时的更新。12306的系统也是这样，春运买火车票，想想都可怕。 2. 支付系统和微信红包 支付系统也是高并发读写，查询余额和转入转出，并且查询余额也要很实时准确，钱这一类的信息是金融相关的数据，对数据一致性要求很高，也不能延迟。从支付扩展到红包，业务场景会更复杂，一个用户发红包，群里多个人墙。全国那么多群。一个账号发生扣减，多个人的账号加钱，并且这个过程大部分人还会查看哪些人抢到了红包。...
# 椭圆曲线的Koblitz形式 之前我写过一篇关于在有限域GP(p)椭圆曲线的文章， p是素数，所以GF(p)也叫素域。还有一种在GF(2^n)这样的有限域下的曲线。如果大家知道有限域的定义就明白了，这种形式的有限域显然适用更广，是更generalize的表示。因为有限域的定义是GF(p^k)，这里的p就是素数，素数的k次方。所以GF(2^n)显然是有限域，2是素数，这种特有的有限域又叫二元域(binary field)。 这种形式有什么优点呢？ 下面有个Quora上的密码学博士[这样回答](https://www.quora.com/What-are-the-advantages-of-elliptic-curve-cryptography-using-binary-fields-over-prime-fields-and-vice-versa): ```txt Security: There are no known attacks that greatly weaken either class of curves. However, there is some concern about binary curves because...