写给宝宝看的区块链与比特币

08年经典论文《Bitcoin: A Peer-to-Peer Electronic Cash System》

我一直在研究一种完全对等的,没有可信赖的第三方的新型电子现金系统… —— 中本聪

关键词:点对点,去中心化,防篡改,无可信第三方,多方互不信任,数据存证

平时用微信/支付宝给朋友转钱,或者银行转账,是怎么保证钱真的转过去了?答:有银行/支付宝这些大公司记录着呢。

银行、支付宝这些就是中间人,我们信任它们来帮我们记账、保管钱。但是,如果世界上没有银行、没有支付宝、没有微信支付,我们怎么在网上安全地把钱转给别人,并且保证对方收到了,钱不会被乱花(比如‘双花’问题,同一笔钱花两次)?怎么保证记账的人不作弊?

区块链就是一个能制约参与者的公共记账本。注意关键词:链,公共,制约。

链,约等于链表,顺着链,要能找到普天之下所有的历史交易。这是设计区块链的根本目的。(解决双花问题,要能知道这笔钱以前有没有花过)。

公共,所有人都能访问链且有机会新增一个链节(叫区块)。记账操作是,从内存池(里面都是待确认(待上链)的交易条目)中选择一些个条目,把这些作为新区块,寻找一个nonce值,寻找的过程是机械的、消耗巨大算力的,这个过程被称为工作量证明(Proof-of-Work)。当将这个nonce与当前区块所有数据结合并进行整体哈希运算后,生成的哈希值必须满足特定条件(如以若干个零位开头)。找到产生这种哈希的nonce需要大量计算资源,闷头算就好了。但nonce的验证非常简单。一旦某个矿机算好了,就把nonce值和区块头告诉其他矿机。大多数矿机验证无误后,新区块创建成功,成为公共的。算出nonce的矿机得到一些奖励(比特币),其他矿机放弃掉原先没算完的数,在新链的基础上,重新挑选一些待确认的交易条目进行计算。

不可篡改: 一旦一个区块被大家确认并加到链上,想改它就非常非常难!为什么?因为每个区块都像连环锁,包含了前一个区块的特殊哈希值。如果你想偷偷改掉很早以前的一个交易,你就必须把从那以后的所有区块都重新算一遍,而且要在所有矿机都还没更新到新账本之前,让超过一半的矿机都认可你改过的账本。这几乎是不可能的任务。

分叉问题:节点始终以最长链为正确版本。如果两个有效区块几乎同时到达形成临时分叉,节点通常会先处理最先收到的区块,但保留另一个分支。任何节点发现工作量证明后,会扩展其中一个分支,哪个分支被延长就会变得更长,而处理较短分支的节点只需切换,放弃较短的分支,转而处理更长的获胜链。

节省磁盘空间:使用默克尔树这种高效的数据结构,将交易成对哈希,构建类似树状结构,直到顶部得到单一哈希(默克尔根)。只有默克尔根哈希被包含在区块头中并与工作量证明链接,允许从后续区块中丢弃大部分旧交易数据,只需保留根部的区块头,节省磁盘空间。

简化支付验证(SPV):SPV客户端只需下载最长工作量证明链的区块头,通过获取将交易链接到区块的默克尔分支,从全节点获取时间戳,并使用区块头和该分支,可确认交易包含在被接受的链中,无需整个区块链。

总之,在比特币网络中,作弊在计算上不可行,实现点对点的直接交易,且交易难以被计算逆转,保护卖家免受欺诈,也方便买家实施托管服务。

Q & A

区块的粒度

一次交易就是一个区块吗?

答:不是。有三个层次:1)交易是最小单位(比如单笔转账)2)区块是容器,里面包含了多个交易。3)区块链是区块串成的链条。把一段时间内(比如10分钟)发生的很多笔交易(几十笔、几百笔甚至更多)收集起来,像打包一样,计算出nonce后,就形成了一个新的 ‘区块’。

矿工之间的竞争

所有矿工算同一个数据包吗?

答:不是。矿工的选择权是区块链去中心化特性的体现。 允许矿工自由选择高手续费交易,激励他们优先处理用户愿意多付钱的交易,提高了网络处理交易的效率(用户可以通过提高手续费让交易更快被确认)

假如一串交易的发生顺序是1,2,3,4,5,6,那么矿工可以选择4,5,6而跳过1,2,3。此时交易1、2、3只是暂时留在全网共享的“待确认池”(内存池/Mempool)里,后续的矿工在打包下一个区块时,依然能看到这些交易,并可能选择打包它们。区块链不记录交易的“自然发生时间”,只记录它们被打包进哪个区块。如果交易4、5、6先被打包进区块N,而交易1、2、3被打包进区块N+1,那么在账本上:交易4、5、6 的确认时间早于 交易1、2、3

矿工之间的竞争2

有没有矿工为了每次都抢在所有人前面算出nonce值,而选择每次只挑出一个交易进行区块的创建?这是否算作弊?

答:技术上矿工可以这样做(只打包1笔交易甚至空区块),但这通常不是作弊,而是极不划算的愚蠢策略。因为很多人以为打包交易越多,计算nonce越慢。但实际计算nonce的速度与区块中的交易数量几乎无关。矿工在解题时,实际反复计算的是区块头的哈希值。

关于什么是区块头,约等于整个区块的校验值。包含了这个区块:前一区块哈希值,本区块打包了哪些交易(叫Merkle根)、区块创建时间(时间戳)、nonce等。矿工反复、疯狂的做一件事:改变Nonce → 计算区块头哈希值 → 是否等于某个特殊值,比如前18位都是0

所以无论打包1笔或4000笔交易,矿工要计算的哈希值都是80字节区块头,所以没人打空包创建空区块。

经济模型问题

奖励与货币必须一致吗?

答:是。在比特币系统中,矿工创建新区块获得的奖励必须是比特币本身,不能是别的钱。这是精心设计的:新比特币只能这样产生、矿工需要被激励、系统完全自循环

补充:代码规定:区块奖励每4年减半(如2009年奖励50 BTC → 现在6.25 BTC → 2024年后3.125 BTC)2140年左右全部挖完,之后矿工只赚交易手续费。

论文翻译:https://zhuanlan.zhihu.com/p/180315198

mempool.space

BOINC: A Platform for Volunteer Computing

请求-响应循环

概括:志愿者通过客户端连接到项目服务器(也就是说,如果有人想让别人为自己的项目贡献算力,那么就需要自己有一个服务器,并且自己设置任务如何拆分),服务器下发任务,志愿者完成后把结果传回去。

  1. 客户端定期向服务器发送rpc请求,询问有没有新任务/报告已经完成的任务
  2. 如果有新任务,服务器则把任务描述和必要的输入文件打包,通过http下载给客户端
  3. 客户端下载后在本地计算,完成后把结果上传回服务器
  4. 服务器验证无误后给客户端增加积分

额外设计

  1. 由于是客户端主动发起http请求,所以防火墙不会阻挡
  2. 如果服务器宕机,客户端设计了指数退避机制,避免广播风暴

帐户管理器(AM,用户端的中控)

  • 如果想参加多个项目。只需在AM上注册一个帐号,勾选多个项目,AM自动的动态调整项目分配(依照用户设置,比如只在晚上运行 or 某项目优先级最高)

用户偏好

  • 关键词偏好:志愿者可对一系列领域关键词选择是或否,表达对特定领域 or 项目的偏好。
    • 物理、天文、亚洲……
  • 计算偏好
    • 限制CPU使用率
    • 任务运行时段
    • 磁盘内存网络的占用
    • ……

硬件异构性的应对方案

  1. 对于同一个科学应用,需要项目方编译出多个不同版本,每个版本对应一种特定的处理器+OS组合
    • win + x64
    • linux + arm64
    • ……
    • 客户端上报自己的平台环境,服务器根据此给客户端发送不同版本的程序
  2. 更精确的控制:特定版本的cpu

plan class(由项目方定义)

输入:电脑的硬件和软件描述

输出

  1. 这个App版本是否能在该电脑上运行?

  2. 如果能跑,大概需要多少CPU、GPU资源

  3. 资源运算的峰值 FLOPS大概是多少?

比如一个plan class可以规定,“只有具备了NVIDIA RTX 30系列显卡且驱动大于某个特定版本的电脑才能运行这个APP版本”

Job

app+输入文件的集合

job属性设计:flops估计(用于预测运行时间)、最大flops、ram工作集大小、磁盘使用上限、关键词

Instance

任务执行的具体单元。一个job被分成多个instance

结果验证

志愿者的设备匿名且不可控

复制验证、同质冗余、自适应复制、项目方提供自定义验证函数

运行时隔离

安装程序创建一个专门的用户来运行boinc,保护用户原有的文件

客户端还要能控制应用程序的生命周期(暂停、恢复、终止)

boinc实现了一套基于消息传递的机制,通过共享内存来实现客户端和应用程序之间的通信、发送控制指令、接收状态信息

图形化程序

让用户感到酷炫,展示计算进度

实在没有合适的APP版本怎么办

boinc包装器

提交任务

高级特性

  1. 对于运行时间很长的任务可以提前上传中间结果
  2. 如果某个job需要很大的输入文件,且这个文件会被很多instance用到,那么局部性调度——将任务分配给已经下载了这个文件的志愿者,减少网络传输。

  3. 由于不同电脑存在性能差异,服务器可根据主机性能历史,动态分配调整instance的大小,确保每个instance的运行时间都是差不多的,例如1小时

  4. 对于非cpu密集型任务的优先级调度

参数设计

一个任务除了“成功返回“,还有很多其他结局:程序崩溃、硬件故障、恶意篡改、任务丢失……

  • delay_bound( J ): 任务截止时间,超时则视为失败并重试。
  • min_quorum( J ): 验证所需成功实例数,多数一致则采纳。
  • init_ninstances( J ): 初始并行实例数,加速达成验证。
  • max_error_instances( J ): 最大允许失败次数,防止程序崩溃。
  • max_success_instances( J ): 最大允许成功次数,防止非确定性结果。

调度策略(重要)

虽然是项目服务器进行集中任务分发,但各种调度发生在客户端。因为是用户主动进行请求,客户端要多少,服务器给多少,然后服务器进行预估时间与验证正确性。

策略:

  1. 客户端:决定当前运行哪些任务
  2. 客户端:决定何时、向哪个项目请求更多任务。

  3. 服务器:根据客户端请求,选择发送哪些任务

目标:

  1. 最终完成所有任务。

  2. 最大化吞吐量 (避免空闲、按时完成、使用最佳版本)。

  3. 遵循志愿者的资源分配和偏好。

客户端:决定当前运行哪些任务

  • 资源
    • 类型:CPU 、 GPU
    • 利用率: 估计峰值 FLOPS (Whetstone for CPU, vendor estimate for GPU)
  • 任务队列:
    • 类型:待运行、执行中、挂起、抢占的任务
    • 资源需求: 每个任务对 CPU/GPU 的使用量
  • 内存占用: 估计 RAM 工作集大小 (est_wss(J))
  • 目标
    • 可行性: 任务集合满足资源和内存约束
    • 最大可行性: 在可行的前提下,尽可能多地运行任务
  • 策略:加权轮询 (WRR)
    • 权重(或叫优先级):是动态的,根据志愿者为不同项目分配的资源份额以及近期使用情况进行调整
    • 时间切片: 默认每 1 小时重新计算优先级,运行高优先级项目的任务,目的是防止某个项目长期独占资源
    • 针对截止时间,进行剩余运行时间估计
    • 静态估计: 任务 FLOP 估计 / 服务器 FLOPs/s 估计
    • 动态估计: 当前运行时间 / 已完成比例
    • 把以上二者加权平均(或单纯平均)
    • WRR 模拟: 定期模拟 WRR 执行,预测哪些任务会错过截止时间
  • EDF (最早截止时间优先)
    • 如果预测到截止时间错过,则采用 EDF 策略

优先级排序

  1. 预测会错过截止时间的任务 (EDF)
  2. GPU 任务优先于 CPU 任务
  3. 时间切片中间或未检查点的任务
  4. 使用更多 CPU 的任务
  5. 项目调度优先级高的任务

客户端:决定何时、向哪个项目请求更多任务

缓冲区存一些已经下载好的任务,留着一会用。缓冲区有B_LO (下限), B_HI (上限)。触发条件: 当前缓冲工作量 < B_LO 时,向项目服务器请求补充工作

  • 这样设计的原因:
    • 保证网络断开、服务器宕机或项目无任务时,仍有足够工作保持资源忙碌
    • 每次 RPC 获取尽可能多的任务,减少 RPC 频率,也就减轻了项目服务器压力

WRR 模拟用于估计缓冲区持续时间,以便缓冲缺口计算,(T(A)是资源实例 A 的预计使用时间)

\operatorname{shortfall}(R)=\sum_{i n s t a n c e s A \text { of } R} \max \left(0, B_{H I}-T(A)\right)

工作请求参数

  • 缓冲缺口,服务器应发送足够工作以填补缺口。req_runtime(R)

  • 空闲资源实例数,服务器应发送能充分利用这些空闲资源的任务。 req_idle(R)

  • 队列中待处理任务的预计剩余运行时间,用于估计新任务完成时间。queue_dur(R)

  • 可获取性 (Fetchability) 项目 P 是否能提供资源 R 的任务 (非暂停、非回退、有可用版本、用户允许)。

工作获取逻辑

  1. WRR 模拟,判断是否需要补充工作。
  2. 按项目调度优先级降序扫描。
  3. 找到第一个满足条件的项目 P,向其发送工作请求。
  4. “搭便车” (Piggybacking): 在其他 RPC 请求中,如果 P 是最高优先级且可获取资源 R 的项目,也请求工作。

服务器:根据客户端请求,选择发送哪些任务