AlexiaChen.github.io

AlexiaChen.github.io copied to clipboard

# 基于Shamir Secret Sharing的各种改进 其实Secret Sharing方案出来后，就之后有两篇论文对其作出了改进，也就是后来的Verifiable Secret Sharing(VSS)，然后再到Publicly Verifiable Secret Sharing(PVSS)。 VSS的原始论文是《Verifiable Secret Sharig and achieving simultaneity in the Presence of Faults》 PVSS的原始论文是《Publicly Verifiable Secret Sharing》 PVSS的论文对VSS和Secret Sharing都做了简要介绍，并介绍了PVSS的非形式化描述。下面我们就对论文的具体的方法进行分析。看看这三篇论文是怎样一脉相承的，到最后我们再回过头看看MPVSS，也就是我们DPoS共识算法所基于的那篇论文。 ## Secret...

AlexiaChen

改注册表这个里面的值就行，还可以编辑路径 HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Lxss{xxxxxxxxx-YOUR-GUID-HERE-xxxxxxxx}\DistributionName 修改完了注意要重启windows系统。因为我目前的体验版修改完毕，WSL2启动失败，正式版就更别说了，重启就OK了

AlexiaChen

# 有关于秘密分片 ## 前言 写这篇文章的缘由是因为之前我提到过我们链的DPoS共识算法底层所依赖的一种PVSS机制，https://github.com/AlexiaChen/AlexiaChen.github.io/issues/104 ，我看了原论文，发现比较繁琐复杂，于是就往References中一直往上追溯，发现一篇shamir写的一篇引用超多的论文[《How to Share a Secret 》](http://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf)，可以算是鼻祖级别的论文了，而且非常短，短短两页道尽了了PVSS的基本核心机制。于是乎，心中有了点货，打算整理一下，其实都是很多secret sharing的核心。感兴趣可以拜读下这篇论文，下面我就不说过多的故事来过渡，直接步入核心。 ## 正文 假设一个秘密D，我们把秘密分散成N份分片，其中拿到任意至少K份秘密分片，你就可以把秘密D重构出来，这个就把秘密泄露的风险降低了（秘密D你可以理解为一段数据）。反之如果拿到的分片是k - 1份，或者更少，那么秘密D就不可能被重构出来。 这种方式就叫(k,n)门限方案(threshhold scheme)。 这种方式需要有一个前提就是 n >= 2*k - 1 好的，下面重点来了，概念懂了，但是要通过什么数学方式可以描述满足这样的需求呢？论文中给出了一个简单的方法，就是通过多项式插值。 随机给出一个次数为k - 1的多项式: ```...

AlexiaChen

# MPVSS [PVSS](https://en.bitcoinwiki.org/wiki/Publicly_Verifiable_Secret_Sharing)是一套publicky verifiable的Secret Sharing方案，但是我們的DPoS依賴的PVSS構造起來會更簡單。 項目裏面目錄簡稱MPVSS，論文叫做[《A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting》](https://www.win.tue.nl/~berry/papers/crypto99.pdf)。 這裏有個MPVSS的[Swift語言寫的實現](https://github.com/FabioTacke/PubliclyVerifiableSecretSharing) 你别说，这篇论文有400+个被引用，0个references，也就是完全自己从0构建编写，没有发表在哪里，从微软学术上搜索出来居然是Lecture Notes。其中一个在业内有名的一篇论文《Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol》（发表在Crypto上）就引用了这篇PVSS论文。对了，这论文就是Cardano区块链它们团队发表的PoS论文，嗯就是ADA币。 # References: -...

AlexiaChen

# 前言 有我自己读过（一部分），没有读过且计划阅读的。这里以语言和领域来划分，我不会什么都推荐，没有口碑和个人接触过的就不推荐了，即使某个项目星星很多，所以并不是简单的名词罗列，不然就把自己github上标注的星星全部搬运过来了。 ## 网络 - [TinyHttpd](https://github.com/EZLippi/Tinyhttpd), C语言编写。个人全部读过，并不觉得很好，500行太短，也不是什么精髓，就是别人写出的玩具，如果非要说适合学习，那么适合超级小白，也就是大一，大二的学生。 - [muduo](https://github.com/chenshuo/muduo), C++ 11/14编写，比较现代，一个事件驱动的多线程网络库（Reactor模型），陈硕的个人作品。个人没有全盘读过，只读过日志实现部分，也是口碑好，所以推荐了。 - [cnetpp](https://github.com/myjfm/cnetpp), 一个github用户个人作品，一个轻量的C++异步网络库，适合初学者，别人推荐的，我没有读过。 - [Webbench](https://github.com/EZLippi/WebBench), C语言编写的一个Linux下的网站压测工具，非常简单，使用fork()模拟多个客户端，个人完全读过，没有什么太多值得学习的，也是适合大一，大二的学生阅读 - [Libev, Libuv, Libevent](https://www.cnblogs.com/sunsky303/p/9094822.html), 这三个库都是C语言的异步事件库，工业级的，个人没有读过。Libevent最复杂，可能libev简单精炼点，看别人推荐也是libev多些。 - [seastar](https://github.com/scylladb/seastar), C++ 11编写的高性能异步事件驱动框架，整合了网络，文件等各个方面的异步，服务端的选择，别人推荐，个人没有看过。 - Nginx， 个人没有读过，估计现在代码规模也大到几十万行了，但是资料多，可以对照特定版本看，章亦春老师写的源码剖析很多。...

AlexiaChen

# 编译器前端 一般来说编译原理总体分成前端和后端两大部分，前端是指词法分析，语法分析，以及语义分析之类的类型检查。后端是代码生成，优化，寄存器分配等等。 现在前端的理论知识研究早已经基本完备，没多少值得研究的地方了，所以都是固定的套路和模式，性能差距都不会很大（递归下降的LL文法对CPU分支预测友好），后端还有很多可优化的地方。 ## 前端 很多很多大家平时常用的编译器的前端时至今日都还是手写的，所以连lex/yacc那种都不是，而更多是ad-hoc的手写lexer以及递归下降+运算符优先级的手写parser。这方面主流并没有特别积极的跟进技术的发展。 C++的就是手写递归下降LL（1）文法，但是C++的 LL（1）跟平常不一样，就是它有回溯，是变种。然后当然也还有一些前端是用lex/yacc系的做法，例如Ruby的parser；或者是用ANTLRv3那样的LL(∞)的做法，例如Groovy的parser。（注意ANTLR的LL(*)不是给定k的LL(k)而比后者更强，因为其lookahead允许无限多，本质上跟PEG类似）。ANTLRv4是ALL(∞)。 从语法分析上，自底向上方面其实GLR系的算法早就有了，实现上也越来越好，早就比yacc/bison用的LALR(1)好。 而自顶向下方面在2000后也有 PEG、LL(∞) （ANTLRv3）和 ALL(∞) （ANTLRv4）的发展，颇有抢回地盘的趋势。 Parsing 算法大致分为两派，自顶向下和自底向上。 其中自顶向下分析（可维护性，可读性更好，方便手写）也就是一般人认为的递归下降分析，一般实现自顶向下分析器都要求parsing 是线性运行时间，所以大多数top-down parser 也就是predict parser 即预测分析器，因为这种parser 在运行时每次都要至少向前看一个符号（然后去查每个产生式的predictive set）才能决定用哪个产生式（递归下降是把所有跳转条件都放在了if(lookhead == xxx) 上），即predict parser 是由“向前看”（预测）来驱动的。去看《Language...

AlexiaChen

算是复习了下大学的《编译原理》了，最近要给我们的链做一个合约语言，正在捡起一些东西。主要就是左递归的文法不满足LL(1)文法的定义，需要消除左递归的文法产生式。然后每个非终结符的产生式编写一个同名的对应的解析函数，直到遇到终结符开始识别和匹配。LL(1)意思就是Left 从左往右线性无回溯的扫描，第二个Left就是使用最左推导，1的意思是向前多看一个token是什么，这样才可以根据那个符号选择正确的产生式。 LL文法是不能解决左递归的，但是自然而然可以右递归，一般说到的递归下降分析就是指LL文法，自顶向下分析，有LL(1), LL(2)到LL(k),甚至到LL（∞）。LR文法反过来是不能解决右递归的，但是自然而然可以左递归，是自底向上分析，或者说规约更好。后面我会写一个文章专门梳理下Parser的体系。 ```cpp /* Author: MathxH Chen E-mail: [email protected] LL(1) grammer for calc: expr -> expr add term | term term -> term mul factor | factor factor...

AlexiaChen

把C++解释来用，不编译，支持JIT，交互式的，叫[Cling](https://root.cern/cling/)， CERN的项目，可能有科学家用作一些科研计算等用途。最近在做公司的智能合约语言相关的调研，实现等工作。搜出来的一个副产物。觉得比较有趣。但是考虑放弃它了，可能会打算自己用递归下降分析或者ANTLR实现一个小的语言，翻译到自己的VM上执行。再看看吧。

AlexiaChen

远程桌面的简要调研报告

2

--- title: 远程桌面的简要调研报告 date: 2017-12-01 09:41:15 tags: - 远程桌面 - VNC协议 - RFB协议 --- ## 前言 这篇调研报告原本是公司在今年四月份做的调研，当时是总结了篇Word文档，由于我有经常写博客和翻阅博客的习惯，所以发到这里，以方面查阅和回顾。 ## 介绍 远程桌面原本是从Windows 2000 Server开始由微软公司提供的，它的功能是当某台计算机开启了远程桌面服务后我们就可以在网络的另一端控制这台计算机了，通过远程桌面功能我们可以实时的操作这台计算机，在上面安装软件，运行程序，所有的一切都好像是直接在该计算机上操作一样。这就是远程桌面的最大功能。 ## 技术方案 远程桌面控制来源于微软，它可以有多种实现方式，网络上常见的一种就是Virtual Network Computing，也就是通常所说的[VNC](https://en.wikipedia.org/wiki/Virtual_Network_Computing)，VNC是采用[RFB(remote frame buffer)](https://en.wikipedia.org/wiki/RFB_protocol)协议图形化的桌面共享系统,它可以远程控制其他电脑。VNC在网络上有很多开源实现，比如[RealVNC](https://www.realvnc.com/en/)，[TightVNC](https://www.tightvnc.com/)。二者都是开源的。其中TightVNC还提供远程桌面客户端(Viewer)的SDK,遗憾的是目前只提供C#的，还有一个Java的Viewer，遗憾的不是SDK，而是整个客户端Viewer。 ##...

AlexiaChen

实现一个简单的高性能布隆过滤器

2

--- title: 实现一个简单的高性能布隆过滤器 date: 2019-03-17 12:26:00 tags: - Bloom Filter - 数据结构与算法 --- ## 布隆过滤器是什么 它是一个数据结构，而且一般传统的科班的算法书不会讲到。它可以用来判断某个元素是否在集合内，具有执行速度快和内存占用小的特点。 布隆过滤器高效的插入和查询代价就是：[Bloom Filter](https://en.wikipedia.org/wiki/Bloom_filter)是一个基于概率的数据结构：它只能告诉我们一个元素的以下两种查询结果： - 绝对不在集合内 - 可能在集合内 针对第二点，也就说可能会有false positive。朴素的布隆过滤器一般是不支持删除操作的，但是也有针对具体应用而产生支持删除操作的布隆过滤器。这个延伸问题我不打算涉及，感兴趣可以查找下相关论文。 ## 布隆过滤器的简单原理以及实现 ### 基本原理 布隆过滤器的一个基础的数据结构就是一个[Bit Vector](https://en.wikipedia.org/wiki/Bit_array)...

AlexiaChen