跳转至

区块链

  • 分类于 区块链
  • 需要 2 分钟阅读时间

区块 DAG（Directed Acyclic Graph，有向无环图）

​区块 DAG（Directed Acyclic Graph，有向无环图）​​ 是一种数据结构，用于描述区块链或分布式账本中交易或区块之间的关联关系。与传统区块链的线性链式结构不同，DAG 通过​​网状拓扑​​组织交易，允许多个交易并行处理，从而提升系统的扩展性和吞吐量。

最早在区块链中引入 DAG 概念作为共识算法是在 2013 年，bitcointalik.org 由 ID 为 avivz78 的以色列希伯来大学学者提出，也就是 GHOST 协议，作为比特币的交易处理能力扩容解决方案；Vitalik 在以太坊紫皮书描述的 POS共识协议 Casper，也是基于 GHOST POW 协议的 POS 变种。

后来 NXT 社区有人提出用 DAG 的拓扑结构来存储区块，解决区块链的效率问题。区块链只有一条单链，打包出块无法并发执行。如果改变区块的链式存储结构，变成 DAG 的网状拓扑可以并发写入。在区块打包时间不变的情况下，网络中可以并行打包 N 个区块，网络中的交易就可以容纳 N 倍。

此时 DAG 跟区块链的结合依旧停留在类似侧链的解决思路，交易打包可以并行在不同的分支链条进行，达到提升性能的目的。此时 DAG 还是有区块的概念。

2015年9月，Sergio Demian Lerner 发表了 《DagCoin: a cryptocurrency without blocks》一文，提出了 DAG-Chain 的概念，首次把 DAG 网络从区块打包这样粗粒度提升到了基于交易层面，但 DagCoin 本身是一篇论文，没有代码实现。

DagCoin 的思路，让每一笔交易都直接参与维护全网的交易顺序。交易发起后，直接广播全网，跳过打包区块阶段，达到所谓的 Blockless。这样省去了打包交易出块的时间。如前文提到的，DAG 最初跟区块链的结合就是为了解决效率问题，现在不用打包确认，交易发起后直接广播网络确认，理论上效率得到了质的飞跃。DAG 进一步演变成了完全抛弃区块链的一种解决方案。

2016 年 7 月，基于 Bitcointalk 论坛公布的创世贴，IOTA 横空出世，随后 ByteBall 也闪亮登场，IOTA 和 Byteball 是头一次 DAG 网络真正技术实现，也是此领域最耀眼的领军者；此时，号称无块之链、独树一帜的 DAG 链家族雏形基本形成。

一句话来概括：DAG是面向未来的新一代区块链，从图论拓扑模型宏观看，从单链进化到树状和网状、从区块粒度细化到交易粒度、从单点跃迁到并发写入，这是区块链从容量到速度的一次革新。

  1. 非线性结构：交易（或区块）之间通过引用（指针）相互连接，形成网状图，而非单链。每个新交易需要引用多个历史交易的哈希值（类似“确认”前序交易；
  2. 有向性：图中的边具有方向性（例如，交易 A 引用交易 B，则边为 \(A \rightarrow B\)，不可以反向引用）；
  3. 无环性：不允许出现循环依赖（例如，交易 A 引用交易 B，交易 B 引用交易 C，交易 C 引用交易 A，则形成一个循环），确保数据一致性。
特性 传统区块链 DAG
结构 线性链式结构 网状拓扑结构
交易确认方式 顺序打包，线性链式结构，需要多个区块确认 并行处理，网状结构，交易之间相互引用，无需多个区块确认
吞吐量 受限于区块大小和出块速度 理论上可以无限扩展
延迟 高（需要等待区块确认） 低（交易即时传播）
典型应用 比特币、以太坊 IOTA、Nano、Hedera Hashgraph
  1. 交易创建：用户发起交易时，需引用多个已确认的历史交易（作为“基础”）。引用越多，交易的可信度越高（类似共识机制）。
  2. 交易传播：新交易广播到网络，其他节点验证其引用的历史交易是否有效。验证通过后，交易被加入DAG网络。
  3. 冲突解决：若两个交易互相矛盾（例如双花攻击），DAG通过​​拓扑排序​​或​​共识算法​​（如Tangle）决定最终状态。
  1. 高扩展：无需矿工打包区块，交易可并行处理，适合高频场景（如物联网支付）；
  2. 低延迟：交易即确认，无需等待区块生成；
  3. 去中心化：节点间直接交互，减少对中心化矿池对依赖。
  1. 数据存储：网状结构可能导致存储需求指数级增长；
  2. 双花攻击风险：若恶意用户持续发起冲突交易，可能破坏网络一致性（需依赖强共识机制）；
  3. 复杂性：开发难度高于传统区块链，需设计高效的冲突检测和解决算法。
  • 分类于 区块链
  • 需要 1 分钟阅读时间

零知识证明（Zero-Knowledge Proof, ZKP）详解

一、核心概念

零知识证明 是一种密码学协议，允许证明者（Prover）向验证者（Verifier）证明某个命题为真，而无需透露任何与该命题相关的额外信息。其核心目标是 在保证隐私的前提下验证真实性。

二、基本特性

  1. 完备性（Completeness） 若命题为真，诚实验证者会被证明者的论证说服。
  2. 可靠性（Soundness） 若命题为假，任何欺骗性证明者都无法通过诚实验证者的检验。
  3. 零知识性（Zero-Knowledgeness） 验证者无法获得命题之外的任何信息，仅知命题的真伪。

三、工作原理

  1. 交互式 ZKP

    • 步骤：

      1. 证明者发送初始信息（如承诺）。
      2. 验证者提出挑战（如随机数）。
      3. 证明者根据挑战生成响应。
      4. 验证者检查响应是否合法。

    • 示例：Feige-Fiat-Shamir 协议（基于平方剩余难题）。

  2. 非交互式 ZKP（NIZKP）

    • 特点：仅需一轮通信（如 zk-SNARKs）。
    • 技术基础：
      • 多项式承诺：将复杂计算转化为多项式形式。
      • 可信设置：生成公共参数（如 CRS，Common Reference String）。
      • 代表协议：zk-SNARKs（零知识简洁非交互式知识论证）、zk-STARKs。

四、应用场景

  1. 区块链与加密货币

    • Zcash：使用 zk-SNARKs 隐藏交易金额和参与者身份。
    • 以太坊：支持 ZKP 的 Layer 2 方案（如 zkRollups）提升隐私与扩展性。

  2. 身份验证

    • 匿名登录：用户证明拥有私钥，无需泄露密码。
    • KYC（了解你的客户）：在合规前提下保护用户身份数据。

  3. 安全协议

    • 安全多方计算（MPC）：多方协作计算时保护输入隐私。
    • 数字签名：结合 ZKP 实现匿名签名（如 DSA 的零知识变种）。

  4. 游戏与谜题

    • 数独验证：证明数独答案正确但不透露解法。
    • 谜题解锁：在游戏中证明拥有通关线索，避免剧透。

五、技术实现

  1. 数学基础

    • 困难问题假设：如离散对数、椭圆曲线离散对数（ECDLP）。
    • 同态加密：允许在密文上直接计算，保护数据隐私。

  2. 主流协议

    • zk-SNARKs：

      • 优势：验证速度快，证明尺寸小。
      • 局限：依赖可信设置（如 Groth16 协议）。

    • zk-STARKs：

      • 优势：无需可信设置，抗量子计算。
      • 局限：证明尺寸较大。

    • Bulletproofs：适用于短声明的简洁证明（如 Monero 隐私交易）。

  3. 工具与框架

    • Libsnark：开源 zk-SNARKs 库。
    • Circom：电路编译器，用于构建 zk-SNARKs 电路。
    • StarkWare：提供 zk-STARKs 商业解决方案。

六、优缺点分析

优点 缺点
1. 增强隐私：保护敏感数据不泄露。 1. 计算开销大：生成/验证证明耗时。
2. 安全性高：抵御中间人攻击。 2. 实现复杂：需密码学专业知识。
3. 灵活性强：适用于多种场景。 3. 可信设置风险：若参数泄露，安全性崩溃。

七、实际案例

  1. Zcash

    • 使用 zk-SNARKs 实现隐私交易，隐藏发送方、接收方和金额。
    • 挑战：需定期更新可信设置（如 Sprout→Sapling 升级）。

  2. 以太坊 Layer 2

    • zkRollups：将数千笔交易压缩为一个 ZKP，批量提交至主链。
    • 优势：降低 Gas 费用，提升吞吐量。

  3. 匿名身份系统

    • Algorand：结合 ZKP 实现去中心化身份认证。
    • 微软 ION：基于 Bitcoin 的去中心化标识符（DID）。

八、未来趋势

  1. 硬件加速

    • GPU/FPGA 优化：加速证明生成与验证。
    • 可信执行环境（TEE）：如 Intel SGX，增强隐私保护。

  2. 标准化与互操作性

    • 通用标准制定：推动 ZKP 协议跨平台兼容。
    • 跨链隐私：实现不同区块链间的隐私资产转移。

  3. 抗量子 ZKP

    • Lattice-based ZKP：基于格密码学，抵御量子计算攻击。

总结

零知识证明通过密码学手段，在不泄露隐私的前提下验证信息真实性，已成为区块链、隐私计算和网络安全的核心技术。尽管面临计算开销和实现复杂性等挑战，但随着硬件优化和标准化进展，ZKP 将在更多领域重塑数据隐私的未来。

  • 分类于 区块链
  • 需要 3 分钟阅读时间

高频 R/W 场景下的性能设计方案

对于这个问题我们需要回归到计算机读写的核心上，计算机的读写速度是有限的，所以需要把数据缓存起来，来提高读写速度。为什么要使用缓存呢？从硬件角度我们知道计算机是有多级缓存架构的，每一级存储设备的读写速度是指数级下降的，越靠近终端存储设备（机械硬盘、固态硬盘）其读写速度越慢，越靠近 CPU 的存储设备其读写速度越快。

缓存是一个有着更快的查询速度的存储技术，这里的更快是指比起从初始的数据源查询（比如数据库，以下都称作数据库）而言。我们经常会把频繁请求的或是耗时计算的数据缓存起来，在程序收到请求这些数据的时候可以直接从缓存中查询数据返回给客户端来提高系统的吞吐量，现在我们来看看有哪些缓存模式可以考虑。

  • 分类于 区块链
  • 需要 1 分钟阅读时间

比特币的创新设计

比特币在创新上提出了很多亮点，值得我们去学习。主要考虑了避免作恶、负反馈调节和共识机制三个方面。

避免作恶

避免作恶基于经济博弈原理。在一个开放的网络中，无法通过技术手段来保证每个人都是合作的。但是可以通过经济博弈来让合作者受益，让非合作者遭受损失和风险。

  • 分类于 区块链
  • 需要 2 分钟阅读时间

分布式系统的核心问题

分布式系统是计算机科学中十分重要的一个研究领域。随着现代计算机集群规模的不断增长，所处理的数据量越来越大，同时对于性能、可靠性的要求越来越高，分布式系统相关技术已经变得越来越重要，起到的作用也越来越关键。

分布式系统中如何保证共识是个经典的技术问题，无论在学术上还是工程上都存在很高的研究价值。令人遗憾地是，理想的（各项指标均最优）解决方案并不存在。在现实各种约束条件下，往往需要通过牺牲掉某些需求，来设计出满足特定场景的协议。

实际上，工程领域中不少问题都不存在一劳永逸的通用解法；而实用的解决思路是，合理地在实际需求和条件限制之间进行灵活的取舍。

更新于 2025-03-18 15:26

  • 分类于 区块链
  • 需要 6 分钟阅读时间

PBFT（Practical Byzantine Fault Tolerance）共识算法

PBFT是 Practical Byzantine Fault Tolerance 的缩写，意为实用拜占庭容错算法。该算法是 Miguel Castro（卡斯特罗）和Barbara Liskov（利斯科夫）在 1999 年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。没错，这个 Loskov 就是提出著名的里氏替换原则（LSP）的人，2008年图灵奖得主。

  • 分类于 区块链
  • 需要 2 分钟阅读时间

拜占庭问题解析

拜占庭问题（Byzantine Generals Problem）是分布式系统领域的一个经典问题，旨在解决 在存在不可靠或恶意节点 的情况下，如何让分布式系统中的各个参与者（节点）就某一决策达成一致行动。以下是系统性解析：

一、问题起源与核心场景

  1. 军事隐喻

    莱斯利·兰伯特（Leslie Lamport）在1982年提出该问题时，以拜占庭帝国（东罗马帝国）的将军围攻敌城为背景：

    • 目标：所有忠诚将军需在同一时间发起总攻或撤退。
    • 挑战：部分将军可能是叛徒，会向不同阵营发送矛盾指令（如“进攻”或“撤退”）。
    • 关键约束：
      • 每个将军只能通过信使传递口头命令。
      • 信使可能被叛徒截获或篡改。
      • 最终所有忠诚将军必须采取相同行动，否则战斗失败。