这两天看了一篇来自于密码学报的《区块链共识机制研究综述》，觉得归纳的很全，写的也很不错，虽然没有特别细致地描述每种共识算法的工作原理，不过也可以让读者对目前共识机制种类的发展有一个整体的把握，有兴趣的同学可以读一读原文。因此，我画了一个区块链共识机制思维导图，比较直观地展示目前共识机制的种类和发展路线，在此分享出来。

共识算法并不是区块链系统特有的，其早已在分布式系统中存在，而区块链也是属于分布式系统中的一种。根据容错的目标不同，可以分为只能容忍崩溃节点一类的算法，例如经典的Paxos和Raft算法；以及可以容忍恶意节点的拜占庭容错协议（BFT）。BFT类型的算法常被用于区块链的共识机制中。

区块链的共识机制从大体上分为两大类：非授权共识机制和授权共识机制。

授权共识机制

授权共识机制一般用于许可连、联盟链这种需要经过身份认证之后才能加入的区块链系统，这类的共识机制基本上是BFT一类的变种、改进，比较出名的就是IBM的Hyperledger Fabric。

非授权共识机制

非授权共识机制目前在研究领域还是占多数，这类的共识允许节点随意的加入退出，而且无需身份认证，例如比特币、以太坊等区块链系统都是采用非授权共识机制。而非授权共识机制由可以进一步细分为基于工作量证明（PoW）的共识机制、基于权益证明（PoS）的共识机制、以及PoW/PoS混合的共识机制。还有一小部分其他的研究尝试，比如基于可信硬件设计（例如Intel SGX）的共识、基于存储空间的共识等等。

区块链共识机制的种类繁多，但是大体上可以按这样的划分归类，更加具体的分类可以参考上述文献和思维导图。我在看这篇综述的时候，也看到了针对各类共识机制的攻击模型和其假设的网络模型，下一次可以总结一下攻击模型和网络模型方面的知识。

比较懒，只挑了比较有代表性的9张图~

2018是十分精彩的一年，去了好多地方，新学了好多东西。

希望2019年也要天天开心，学业有成呀！大家也是！

一、熵

① 什么是熵

可以看到，在概率不均匀的时候，熵是小于2^3, i.e. 3bit，采用了概率大的马匹编码短的原则，这和二元哈夫曼编码应该是一个道理。

② 数学定义

可以注意到，Eg(X)其实就是熵，所以熵又解释为随机变量log 1/p(X)的期望值。

③ 性质

1
2
3

· H(X)≥0
· H_b(X)=(log_b a)H_a(X) 其实就是个换底公式
· H(X)分布为凹函数，可以看下图所示

另外可以从上图看到，当p=1/2时H(p)取得最大值，1比特，当p=0,1的时候H(p)=0，因为变量这时不再是随机的，所以不具有不确定度。

Read More

推荐一篇好文章，>>原文传送门

虽然IOTA目前还是有不少缺点，不过其DAG的新颖架构，以及没有交易费，为高频的微交易创造了条件。因为IoT设备所属方本身就比较明确，所以并无需引入外来miner，由所属组织自行控制，所以就不用特别考虑incentive mechanism的设计，所以没有交易费并不算是缺点。

文章里提到密码学中的一条黄金法则

The golden rule of cryptographic systems is “don’t roll your own crypto.”

永远不要自己发明加密算法！IOTA自己推出的curl哈希算法被爆出可能产生哈希碰撞的问题，所以为了安全起见，他们又将算法切换回SHA3。

另外，看新闻说IOTA下一步/即将支持智能合约，希望快点release :)

keyword: NDN, blockchain, ICN

演讲主题列表：Program

区块链技术与应用论坛（2018.8.14）

• 区块链系统运维与落地应用（严挺）

带宽提升，单点计算能力提升，分布式技术的应用
tamper-proof 防篡改，应用于审计、管控
数据半共享、带条件的共享

他强调一个区块链应用的理念，就是技术+业务，更多业务上的了解，对客户以及应用落地比较友好。更多做的也是金融方面的应用，应该是基于Hyperledger Fabric区块链开发的。

• 区块链打破互联网垄断（田鸿飞）

传统互联网的垄断商业模式（FANG，BAT）
数据孤岛（i.e., lack of sharing）和隐私侵犯，集中式存储的弊端
同态加密技术，在加密数据上进行统计数理计算，但是性能可能是问题
用户数据与互联网公司独立开，公链

key idea 数字资产化（区块链应用场景），资产数字化

• YeeCall，区块链时代的基础设施（江周平）

节点状态同步，共识 分布式网络、丢包
自组网（区块链+车联网） PBFT
zkSNARKs 隐私保护

YeeChain（github开源），新共识机制（Tetris俄罗斯方块）

• Hyperledger Fabric数据隐私保护（赵振华）

mutichannel 多条链

节点权限控制，是否可访问数据，校验哈希值

• 从信息系统看区块链的未来演进（斯雪明）

Is blockchain technology practical for data process platform? 利弊
网络层 得：分布式 失：监管难度大
共识层 得：安全性 失：效率低
应用层 DApp 用户发布的智能合约存在漏洞
高度同构 高度冗余 高度关联 （往异构、不那么冗余、不那么关联发展）
避免智能合约的图灵完备，作何理解？大部分智能合约存在漏洞

性能和安全存在矛盾，PoW消耗资源大，安全；PoS，DPoS性能高，安全性比较低，根据不同的安全、性能需求选择不同的模型。

Read More

手机定位有多种方式，一般有这几种方式：

卫星定位

GPS（Global Positioning System）即全球定位系统，是由美国建立的一个卫星导航定位系统，利用该系统，用户可以在全球范围内实现全天候、连续、实时的三维导航定位和测速；另外，利用该系统，用户还能够进行高精度的时间传递和高精度的精密定位。

基站定位

移动电话测量不同基站的下行导频信号，得到不同基站下行导频的TOA（到达时刻）或 TDOA(到达时间差)，根据该测量结果并结合基站的坐标，一般采用三角公式估计算法，就能够计算出移动电话的位置。实际的位置估计算法需要考虑多基站(3个或3个以上)定位的情况，因此算法要复杂很多。一般而言，移动台测量的基站数目越多，测量精度越高，定位性能改善越明显。

WiFi定位

每一个无线AP（路由器）都有一个全球唯一的MAC地址，并且一般来说无线AP在一段时间内不会移动；

设备在开启Wi-Fi的情况下，无线路由器默认都会进行SSID广播（除非用户手动配置关闭该功能），在广播帧包含了该路由器的MAC地址；采集装置可以通过接收周围AP发送的广播信息获取周围AP的MAC信息和信号强度信息，将这些信息上传到服务器，经过服务器的计算，保存为“MAC-经纬度”的映射，当采集的信息足够多时候就在服务器上建立了一张巨大的WiFi信息网络；

当一个设备处在这样的网络中时，可以将收集到的这些能够标示AP的数据发送到位置服务器，服务器检索出每一个AP的地理位置，并结合每个信号的强弱程度，计算出设备的地理位置并返回到用户设备，其计算方式和基站定位位置计算方式相似，也是利用三点定位或多点定位技术；位置服务商要不断更新、补充自己的数据库，以保证数据的准确性。当某些WiFi信息不在数据库中时，可以根据附近其他的WiFi位置信息推断出未知WiFi的位置信息，并上传服务器。

AGPS定位

AGPS（AssistedGPS：辅助全球卫星定位系统）是结合GSM/GPRS与传统卫星定位，利用基地台代送辅助卫星信息，以缩减GPS芯片获取卫星信号的延迟时间，受遮盖的室内也能借基地台讯号弥补，减轻GPS芯片对卫星的依赖度。AGPS利用手机基站的信号，辅以连接远程定位服务器的方式下载卫星星历 (英语：Almanac Data)，再配合传统的GPS卫星接受器，让定位的速度更快。是一种结合网络基站信息和GPS信息对移动台进行定位的技术，既利用全球卫星定位系统GPS，又利用移动基站，解决了GPS覆盖的问题，可以在2代的G、C网络和3G网络中使用。

上交计算机外校保研总的来说有三个时间点：

• 六月初的直博生面试
• 七月份的夏令营（大概三天左右，直硕和直博在这个时间点都有）
• 九月份的推免面试（直硕和直博都有）

一般来说这三个时间点，六月份和七月份的面试你只能报名参加一个，若第一次面试没有通过，可以选择再报名九月份的面试。下面说说这三个时间点有什么异同。

六月初的直博生面试

首先最早的是六月初的直博生面试，面试地点在全国分布好几个面试点，很幸运成都也是面试点之一，所以参加六月份的直博生面试只需要在成都面试就好了，不用跑去上海，比较方便。有意愿参加直博生面试的同学，需要注意以下几点：

• 考虑清楚自己是否真的下决心读博。读博和读硕不一样，并没有一个固定的毕业期限，上交的直博生一般是五年可以正常毕业。如果读博期间坚持不下去放弃了那你只有本科的学历了，所以一定要慎重考虑。应该会有很多人关心会不会延毕的问题，我觉得这个主要看导师吧，一般来说，只要不是你的问题（学习态度之类的），正常毕业不会有太大问题。反正要慎重考虑！
• 提前联系好导师。这个很重要，一般四月份就可以开始邮件联系导师了，导师的联系方式以及个人主页在计算机系的主页上都有（http://www.cs.sjtu.edu.cn/Faculty.aspx），选好自己未来打算研究的方向，根据方向来挑选心仪的导师。我们可以从导师个人主页了解到导师的方向以及近几年的论文发表情况，如果有打算未来研究某方向的话，面试前看一些相关的论文也是有必要的。
• 直博生入围面试条件。去年（2017）给的报名条件（看这里http://yjwb.seiee.sjtu.edu.cn/yjwb/info/12554.htm）是排名年级前10%，六级480以上额昨天看了下官网，貌似六级过了就行，480+应该是浙大直博的要求，至于那个排名好像也没有硬性要求，10%那个我也忘了是哪里看的，最好满足吧，在这个条件范围内的都可以试一试。理论上是这样的，如果条件差一些但也很想报的也可以试一试。

  Read More

做安卓开发的同学一定知道Genymotion这一著名的安卓模拟器，可惜下载它的ova镜像实在是太太太太慢了！所以，在这里给大家分享一个用迅雷来下载镜像的好方法。

以最新版的2.12.0为例，首先，我们可以发现，Genymotion下载的镜像会保存在C:/Users/你的用户名/AppData/Local/Genymobile/Genymotion/ova大概是这样子的路径下，你每次选择一个安卓镜像下载的时候都会在这个目录下创建一个临时文件，比如我下载一个安卓5.1.0的镜像，这个目录下的临时文件名字就是genymotion_vbox86p_5.1_180219_000000.ova.partial，可以看到是一个部分下载的文件。

这个时候，我们先取消镜像的下载，然后复制上这个临时文件的名字（除了.partial）,加上一个前缀，还是以上面这个为例，那么完整的下载地址就是http://files2.genymotion.com/dists/5.1.0/ova/genymotion_vbox86p_5.1_180219_000000.ova，复制到迅雷中下载，速度非常快！

大概可以发现规律，下载链接的组成：http://files2.genymotion.com/dists/<安卓版本号>/ova/目录下临时文件的名字.ova，下载完成后替换掉ova目录下的临时文件，然后再去Genymotion选择下载这个镜像，就会发现已经下载好啦，进入自动部署的阶段了，就可以用啦~

然后关于Genymotion不能安装arm架构的应用，我们可以使用Genymotion-ARM-Translation进行转换，我这边有适用4.x，5.0，5.1的translation工具包，如果有需要的朋友可以通过github的邮件向我要一份~

在Win10下安装OSMnx库异常艰难，虽然官方推荐的是用python3以及conda包管理器，但是我还是想用python2+pip来安装，也不是不行，就是坑有点多，摸索之后总算总结了一个经验出来。

我的环境是python27，先提一句，最好用64位的python，因为到后面运行数据的时候，因为我的数据量比较大，其实也不大，反正用32位的python运行，一旦运存超过2GB就会报Memory Error错误，很是蛋疼。

首先，先去下载这个安装一下，安装OSMnx需要VC 9.0的环境，Download Microsoft Visual C++ Compiler for Python 2.7 from Official Microsoft Download Center

然后，去Unofficial Windows Binaries for Python Extension Packages下载几个whl包，直接安装，因为这几个用pip装不上，会报错…安装包名字为Rtree，Fiona，Shapely，GDAL。

1

pip install ./path/to/*.whl

直接装就行了。其实Rtree用pip直接在线安装不会报错，但是后面你运行的时候就会发现报错说缺少一个DLL，所以还是手动下载，就没问题了。

然后就安装OSMnx

1

pip install osmnx

就可以顺利安装上OSMnx，因为官方的例子都是在jupyter notebook上运行，所以我们也装一下。

Read More

原文出处：经纬度转平面坐标的算法（米勒投影）

地图组件是前端数据可视化非常重要的一个组成部分，根据geoJSON这种通用数据格式来生成地图是比较便捷的做法。不过对于地图坐标转换的算法，还是了解一些比较好，对于设定高阶地图组件会有帮助。这里介绍一下在米勒投影的地图上，如何将经纬度转换为平面坐标的算法，这个算法在生成世界地图的时候比较常见。（维基百科-米勒投影）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// lon 经度，西经为负数
// lat 纬度，南纬是负数
function millerXY (lon, lat){
     var L = 6381372 * Math.PI * 2,     // 地球周长
         W = L,     // 平面展开后，x轴等于周长
         H = L / 2,     // y轴约等于周长一半
         mill = 2.3,      // 米勒投影中的一个常数，范围大约在正负2.3之间
         x = lon * Math.PI / 180,     // 将经度从度数转换为弧度
         y = lat * Math.PI / 180;     // 将纬度从度数转换为弧度
     // 这里是米勒投影的转换
     y = 1.25 * Math.log( Math.tan( 0.25 * Math.PI + 0.4 * y ) );
     // 这里将弧度转为实际距离
     x = ( W / 2 ) + ( W / (2 * Math.PI) ) * x;
     y = ( H / 2 ) - ( H / ( 2 * mill ) ) * y;
     // 转换结果的单位是公里
     // 可以根据此结果，算出在某个尺寸的画布上，各个点的坐标
     return {
          x : x,
          y : y
     };
}

Read More