Crypto

发表于 更新于 分类于

…

区块链技术与应用（肖臻）

BTC密码学原理

  • cryptographic hash function
    • collision resistance：x不等于y，H(x) = H(y)。一般很难找到如何制造哈希碰撞，用来检验是否篡改
    • hiding: x—> H(x)，实践中难以反推
    • puzzle friendly：事先不知道哪些输入更有可能得到某一范围的哈希值
      比特币中用的哈希函数是SHA-256。不对称的通讯用接受者的公钥加密，接受者用其私钥解密。
  • 签名：发起者用私钥签名，别人再用其（同一人）公钥验证。

哈希指针：除了保存一个结构体的地址，还有其哈希值。区块链和普通列表的一个区别就是用哈希指针代替了普通指针。

Merkle tree：和binary tree的区别是用哈希指针替代普通指针，用来提供merkle proof

这种证明也叫proof of membership

BTC数据结构

  • block header: version, hash of previous block header, merkle root hash, target, nonce
  • block body: transaction list

比特币交易的实现：

  • transaction-based ledger: 不显性记录每个账户有多少币，要根据历史交易去计算。全节点维护UTXO数据结构，包含所有未花费的币的信息。每个交易有多个输入，也可以有多个输出，所有输入加总的金额略大于所有输出加总的金额，多出来作为交易费。发布新区块的人除了能获得区块奖励，把别人的交易打包进新区块中也可以从中来获得交易费。区块奖励大约每隔4年减半，到一定时间主要的收入就是交易费了。

  • account-based ledger（以太坊应用）：显式地记录了每个账户的币。

  • 全节点：

    • 一直在线
    • 在本地硬盘上维护完整的区块链信息
    • 在内存里维护UTXO集合，一边快速验证交易的正确性
    • 监听比特币网络上的交易信息，验证每个交易的合法性
    • 决定哪些交易会被打包到区块里
    • 监听别的矿工挖出的区块，验证其合法性
    • 决定沿着哪条链挖下去
    • 出现等长分叉时，选择哪个分支
  • 轻节点
    • 不是一直在线
    • 不用保存整个区块链，只要保存每个区块的块头
    • 不用保存全部交易，只保存与自己相关的交易
    • 无法验证大多数交易的合法性，只能检验与自己相关的交易的合法性
    • 无法检测网上发布的区块的正确性
    • 可以验证挖矿的难度
    • 只能检测哪个是最长链，但不知道哪个是最长合法链

BTC挖矿
H(block header) <= target，比特币的输出空间是$2^{256}$，比特币出块儿时间约为10分钟，出块儿时间太短，在网络上传播需要一定时间，就会出现分叉。所以需要调整挖矿难度，来使得出块儿时间保持稳定，不能无限减小下去。比特币每2016个区块调整一次，调整公式为$target = target * \frac{actual\ time}{expected\ time}$。

挖矿设备越来越趋向专业化，第一代设备是CPU挖矿，第二代转入GPU挖矿，第三代用ASIC芯片，专为挖矿设计，且为某一种加密货币设计的ASIC芯片，只能挖该加密货币，除非其他加密货币用一样的mining puzzle（称为merge mining）。芯片研发周期长，如果这期间该加密货币价值波动大，容易造成亏损。

矿池的架构一般为一个全节点驱动很多个矿机。矿工的分配用工作量证明，原来单个矿工收入不稳定是因为挖到一个块的难度可能很高。现在搞一个把难度降低到一定程度的almost valid block（这个block是不合法的），矿工挖这个块儿，挖到之后提交给矿主，矿主拿到这个块儿不能发布，但可以依据比例来决定矿工的贡献率，等到真正挖矿分配收入时按这个贡献量分配。

BTC分叉

  • state fork：比如同时挖到区块分叉，forking attack也属于此类。
  • protocal fork：对协议修改的意见不同，用不同版本出现分叉
    • 硬分叉：对协议增加新的特征，没有升级软件的节点不认可新的协议，出现硬分叉。比如区块大小限制，BTC规定每个区块最多1M个字节，大概4000个交易，一个区块10分钟，平均每秒7个交易。有人认为这个数量有点过低。
    • 软分叉：对协议加一些限制，原来合法的区块现在可能变得不再合法。比如把区块size改小了，出现新旧节点分叉时，旧节点也是认可新链的，新链长他就会放弃挖出的大区块，接到新链上，但在新链上，他依然可能挖出大区块，是不被新节点认可的，新链那时候又会避开他再次分叉。这种分叉是暂时性的，系统不会出现永久性分叉。

BTC匿名性

  • 一个人创立不同账户，不同账户之间可能关联起来
  • 比特币账户可能和现实世界身份关联起来，最明显的就是资金的转入和转出

零知识证明：一方（证明者）向另一方（验证者）证明一个陈述是正确的，而无需透露除该陈述是正确的外的任何信息。

同态隐藏：

  • 如果x,y不同，那么它们的加密函数值E(x)和E(y)也不相同
  • 给定E(x)的值，很难反推出x的值
  • 给定E(x)和E(y)的值，我们可以很容易计算出某些关于x,y的加密函数值
    • 通过E(x)和E(y)计算出E(x+y)
    • 通过E(x)和E(y)计算出E(xy)
    • 扩展到多项式

例：A向B证明A知道x和y使得x+y=7，同时不告诉B具体的x和y的值。A把E(x)和E(y)数值发给B，B计算出E(x+y)，和E(7)比较。

应用有零币和零钞。

ETH账户
以太坊设计的mining puzzle对内存要求很高，一定程度上避免了ASIC芯片的使用，致力于用权益证明代替工作量证明。出矿时间也由比特币的十分钟缩减为十几秒。除此以外，以太坊支持智能合约。

Account-based ledger：显式记录每个账户有多少以太币，对于double spending attack有天然的防御作用。但相对的有replay attack，比如A给B转账，过一段时间B又把交易重放了一遍，double spending attack是发起者不诚实，replay attack是接收者不诚实。应对这个问题是加一个交易次数，每次交易时合并到交易内容中。

以太坊中有两类账户

  • externally owned account：通过公私钥对控制，有账户余额balance，还有交易次数计数器nance
  • smart contract account：内容有调用次数nance，但不能主动发起交易，还有代码code和相关状态storage

ETH数据结构

1.状态树

  • trie：查找效率取决于Key值的长度，应用中所有的key值都是40位（以太坊地址，公钥取哈希，前面截一段）

  • Patricia tree

  • Merkle partricia tree: 普通指针换成哈希指针，最后得到一个根哈希值写在块头里

2.交易树和收据树

数据结构上，交易树和收据树都是MPT，而比特币中的收据树就是普通的Merkle Tree。

Bloom filter：支持高效地查找某个元素是否在某个集合中。给大的集合计算出一个摘要digest，有可能出现false positive，即有可能出现误报，但不会出现漏报。

ETH共识机制

比特币出现分叉时，只有最后最长合法链的区块奖励才有效。但对以太坊出现暂时分叉是很常见的，orphan block的区块奖励作废对个体矿工来说就很不公平。

以太坊采用Ghost协议

  • 最初版本：对orphan block（以太坊中叫uncle block）给$\frac{7}{8}$个区块奖励，而最长链把uncle block包括进来会得到$\frac{1}{32}$个区块奖励，最多包含2个uncle block
  • 更新版本：如果最长链最新的块没有包含uncle block，下一个区块依然可以包括该uncle block。再往前推一代的uncle block包含进来可以得到$\frac{6}{8}$，再往前一代$\frac{5}{8}$，以此类推，直到$\frac{2}{8}$，再往前一代不算
  • 不是最长链只有第一个区块能得到uncle reward的，后面的区块就不会有了，否则会降低forking attack的成本

ETH挖矿

挖矿设备的专业化，ASIC芯片的大量使用偏离了去中心化的初心。可以设计mining puzzle来做ASIC resistance，之前的一个例子就是LiteCoin。

ETH用两个数据集（Ethash)

  • 小的dataset Cache，轻节点保持就行
  • 大的dataset DAG

以太坊采用了pre-mining和pre-sale，预留了一部分币给初始开发者。

Proof of Stake：

  • 基于工作量证明的一个普遍批评是浪费电。比特币每年能耗大概70TWh($10^{12}$)。权益证明省去了挖矿的过程，减少能耗。从安全性方面看，基于工作量证明挖矿所需的资源是外部来的，即花钱买矿机，则可以大量花钱买算力恶意攻击。而用权益证明是一个闭环，发动攻击首先要买到足够的币，一旦大量买入，币的价格会大涨。
  • 早期权益证明机制遇到的一个问题是nothing at stake。当出现分叉时，基于工作量证明会选一条链挖，而不会分散算力两边都挖，而权益证明则会两边都投票，因为币不受影响
  • 以太坊权益证明协议叫Casper the Friendly Finality Gadget（FFG），在过渡阶段也要和工作量证明协作。

智能合约

智能合约是运行在区块链上的一段代码，代码的逻辑定义了合约的内容。账户保存了当前的运行状态：balance, nonce, code, storage。Solidity语言一般是智能合约的常用语言。

创建合约：外部账户发起一个转账交易到0*0的地址，转账金额是0，但要支付Gas fee，合约的代码放在data域里。矿工把这个合约发布出去后，返回一个合约的地址。
智能合约运行在EVM上。如果出现错误会导致回滚，在嵌套调用中，被调用合约错误有些会引起连锁式回滚，有些则不会。
全节点要先执行所有交易，包括智能合约，得到哈希值，然后才能挖矿。但是先执行了交易，最后挖不倒矿不会得到任何补偿。而且必须验证发布出来的交易，才能更新本地数据得到哈希值继续挖。发布的区块不一定都是成功执行的，即使智能合约交易失败了，也要发布才能成功地得到gas fee。

TheDAO

TheDAO众筹投资，并设计拆分的操作，少数投资者可以用代币赎回以太币到子基金中。但黑客利用漏洞重入攻击，社区分为要不要回滚补救的两派。补救措施升级了软件，和TheDAO相关的交易不予执行。但有个bug是对这类交易不收gas fee，出现了很多与TheDAO相关的交易攻击，矿工受不了回滚到升级前。这时候子基金28天锁定期快到了。最后以太坊团队上线了硬分叉的设计，通过投票后上线。最后导致了硬分叉，旧链上继续挖出的叫ETC。

应用

现有体系中国际支付不方便，加密货币可在在互联网价值交换方面应用。