思维之海

——在云端,寻找我的星匙。

区块链

区块链是一种基于算法的账本,也就是数字账本。其它种种区块链的特性,无非是为了优化这个账本而产生的,包括去中心化、安全性保证等等。区块链代表的是一种新形式的经济活动,因此除了从数学技术的角度加以解释,也要从经济思维的角度思考。比如,比特币的挖矿行为,是一种“毫无意义”的计算行为,但却创造了经济价值——提供信用保证来维护币值。

开放、自主、安全、可信、高效。

References

学堂在线 - 区块链和加密数字货币

课程 - 赛博智能经济与区块链 - 徐恪陈康,……

前端:vue.js。Django。

基础概念

区块链:使用密码技术将共识确认的区块按顺序追加形成的分布式账本

公链、联盟链、私链。

双花(Double spending):同一笔钱经过不当操作消费了两次。

淘宝通过中间存储货币来避免双花。

共识机制:最长链;工作量证明机制(POW)。

比特币用共识机制来避免双花。一个比特币网络的总算力越大,网络就越安全,就越不可能成功双花。

反对工作量证明机制

  • 能源耗费
  • 算力集中
  • 毫无意义的计算:这是对比特币的网络安全的最重要因素,对攻击者来说“杀敌一千,自损八百”。如果是有意义的计算,那么攻击者就会得到激励。

矿机设备的评价指标:算力、价格、耗电。

矿机的销售量和价格受到比特币的币价的影响非常大。

矿池:控制系统性风险,所有人的矿机的算力集合获得记账权的可能性更稳定。

以太坊:“世界计算机”。

  • 点对点的支付
  • 虚拟机运行合约/程序
  • 不断更新的区块链网络

权益证明机制(POS):权益与持币的数目,持币的时间,稳定在线相关。

委托权益证明机制(DPOS):选取固定的几个节点进行记账。商业应用平台;点对点,不需要中间人;支付转账+智能合约。

博弈论

https://vel.life/博弈论

比特币中的非合作博弈

两个矿池(蓝矿池红矿池)都在想办法最大化它们的挖矿奖励。

红色矿池的管理者决定潜入蓝色矿池。潜入节点提交部分工作证明赚取回报,但是拒绝任何发现的有效区块并且不给蓝色矿池贡献任何生产性工作。

如图所示,在新的收益分配机制下,红色矿池的主部获得1/3收益,其潜入部获得2/3*1/3=2/9收益,故总共获得5/9收益,高于最开始不潜入时的1/2收益。

比特币中的合作博弈

  • 通过工作量证明争夺记账权
  • 通过奖励记账权比特币的方式激励矿工
  • 矿工有合作动机共同维护比特币的币值
  • 特别是即使有大矿池算力超过51%,也没有动力破坏共识
    • 破坏共识会导致币值崩溃

比特币系统是合作博弈的成功典范。它成功建立了群体上的一个稳定契约约束。

P2P系统

P2P(Peer to Peer)为点对点的网络架构,它是分布式或者无中心化应用的核心拓扑。

P2P强调所有节点之间的对等性。C/S则通常需要中心化的服务器来维持应用工作。

分布式哈希表 DHT

DHT的问题

  • 只能进行 精确 匹配,实用价值有局限
  • 适应节点动态变化的能力低
  • 经过哈希之后,节点的位置信息被破坏了,来自同一个子网的站点很可能节点号相距甚远,这不利于查询性能的优化
  • 基于哈希表的系统不能利用应用本身的信息,许多应用(比如文件系统)的数据本身是按照层次结构组织的,而使用哈希函数后,这些层次信息就丢失了

比特币

https://bitcoin.info/

Bitcoin:

  • 货币系统
    • 发行:价值——央行
    • 交易:结算
      • 支付
      • 确认——第三方
      • 真实性
    • double speed(双花)
      • (曾经校园卡是可以double spending的【双离线】

区块链交易的冷热分离。(冷交易、热交易……)

共识机制

阅《Untangling Blockchain A Data Processing View of Blockchain Systems》

智能合约

https://vel.life/北斗UMA专项/

比特币的区块链只有转账这一基本功能。

联盟链

零知识证明

https://vel.life/零知识证明简记/

传统网络系统的安全基础:”可信“第三方

CA认证、DNS、路由表、手机运营商、微信、支付宝……

第三方的问题:

  • 单点故障
  • 欺诈
  • 用户信息滥用
  • 用户隐私泄露

区块链是否可以解决可信第三方的问题?

区块链的本质是模拟了一个可信第三方。

VDF(可验证延迟函数)。


一些应用

  • 数字签名
  • 验证协议
  • ……

隐私计算

零知识证明保证一个远程计算过程的完整性机密性

可以用于:

  • 证明:数据满足一定条件,但是不暴露数据本身

zkRollup 零知折叠

zkRollup——区块链二层扩容协议

把大量交易打包成一个transaction来验证

一百次的修改世界状态,合并为一次修改状态。产生一个零知识证明,证明这个合并是有效的

可以达到300 TPS到10000 TPS

精简区块链

用zkp把区块链压缩成一个极小的证据。(22kB)

支持递归的zkp。

无状态客户端

stateless client:矿工只需要保存承诺(commitment),用户只需要保存自己的状态。

每个区块都带有一个witness,可以证明自身的真实性。

可能是以太坊未来的一个中心的技术。

zkPoD

基于区块链的零信任公平交易协议

郭宇老师团队在做,github上有开源项目

证明

产生证明的过程非常困难,但是一旦证明有了之后,检验证明的正确性很容易的(可以机械化地检验,因为每个步骤都是已知的)。

不适用于所有问题,比如求解三体问题的瞬时解。

有些场景验证过程时是比较耗时的,所以不适用于零知识证明。一般应用区块链社区中,需要验证的时间必须非常小,在$O(log^2n)$以内。

机器证明领域一直在发展。

交互式证明

图灵测试。

三色问题不一定有解。目前只能暴力求解。

模拟器 simulator

以下是对证明模拟器零知识的一个反驳。

虽然我无法区分究竟是在哪个世界、哪个角色。

但是,simulator的确从真实世界获得了所有的必要的交互验证信息。

也就是说,如果simulator可以一直保持这样的超能力。

那么无论simulator知不知道证明,它对我来说都具有有效的证明力。

也就是,当模拟器具有证明力的时候,它必须与真实世界有连接。一旦它失去连接,它就失去了证明力。也就是说,模拟器相当于真实世界的一个接口 / Interface它们是一体的不可分的)。模拟器不知道,但是模拟器和真实世界的联合体是知道证明的。

说模拟器不知道证明,就好像在说,我的手不知道我脑袋的想法一样。

就算对于真实世界来说,也不是真实角色的所有的结构都拥有零知识证明的信息。

也就是这样的证明方法是不足的。

应该用多重宇宙的方法,在无穷多的平行空间中,存在一个随机宇宙,它不能作弊,但是它也能做出跟真实世界一样的证明。这时,双方就没有连接了。

Random Oracle

NIZK。把交互证明的过程给第三方(一个Hash的随机证明序列)。

没有Trusted setup通常算法会比较慢,因为缺少了一些优化过程。

zkSNARK

https://vel.life/区块链隐私保护专题论文阅读/

算术电路

算术电路的可满足性问题是一个NPC问题。

把一个可计算过程转换为等效的算术电路。(R1CS是算术电路的一种表示方式)

用信息论中的多项式编码(拉格朗日插值),把N次检验压缩到1次。

高阶多项式的插值是不稳定的,插值点稍微变化,曲线的形状、零点就会发生显著的变化。

但是,一次多项式运算,不就是把所有的插值点一起并行检查么。虽然形式上打包成“一次检查”,但在计算量上会更小吗?


把多项式运算同态映射到椭圆曲线群上。

椭圆曲线会提供一定的单向性,很难恢复出原始的多项式信息。

这一步实现了信息的隐藏。

有一类特殊的椭圆曲线群可以很好地适配多项式乘法。


从有限域到实数域——还是需要在底层转化为有限域。

除法需要一般还是需要利用费马小定理。(似乎有直接做实数域乘法的paper)

应用

【信用分发】供应链金融