跨链技术的分析与思考(转载)

原文地址:http://bitking.wang/2019/03/21/blockchain-interoperability.html

当前的区块链底层技术平台百花齐放,不同的业务、不同的技术底层的区块链之间缺乏统一的互联互通的机制,这极大限制了区块链技术和应用生态的健康发展。跨链的需求由此而来,本文通过分析几种主流的跨链方案探讨跨链技术的本质及相应的解决思路。

跨链的类型

跨链交互根据所跨越的区块链底层技术平台的不同可以分为同构链跨链和异构链跨链:同构链之间安全机制、共识算法、网络拓扑、区块生成验证逻辑都一致,它们之间的跨链交互相对简单。而异构链的跨链交互相对复杂,比如比特币采用PoW算法而联盟链Fabric采用传统确定性共识算法,其区块的组成形式和确定性保证机制均有很大不同,直接跨链交互机制不易设计。异构链之间的跨链交互一般需要第三方辅助服务辅助跨链交互。

主流跨链机制概述

截至目前,主流的区块链跨链技术方案按照其具体的实现方式主要分为三大类,分别是公证人机制、侧链/中继和哈希锁定:

  1. 公证人机制(Notary schemes): 公证人也称见证人机制,公证人机制本质上是一种中介的方式。具体而言,假设区块链A和B本身是不能直接进行互操作的,那么他们可以引入一个共同信任的第三方作为中介,由这个共同信任的中介进行跨链消息的验证和转发。公证人机制的优点在于能够灵活地支持各种不同结构的区块链(前提是公证人能够访问相关方的链上信息),缺点在于存在中心化风险。
  2. 哈希锁定(Hash-locking): 哈希锁定技术主要是支持跨链中的原子资产交换,最早起源自比特币的闪电网络。其典型实现是哈希时间锁定合约HTLC(Hashed TimeLock Contract)。哈希锁定的原理是通过时间差和影藏哈希值来达到资产的原子交换。哈希锁定只能做到交换而不能做到资产或者信息的转移,因此其使用场景有限。
  3. 侧链/中继链(Sidechains / Relays): 侧链是指完全拥有某链的功能的另一条区块链,侧链可以读取和验证主链上的信息。主链不知道侧链的存在,由侧链主动感知主链信息并进行相应的动作。而中继链则是侧链和公证人机制的结合体,中继链具有访问需要和验证进行互操作的链的关键信息并对两条链的跨链消息进行转移。从这个角度看中继链也是一种去中心的公证人机制。

下面就这几种跨链方式的典型实现方式进行详细分析:

典型跨链机制实现分析

公证人机制

最传统的公证人机制是基于中心化交易所得跨链资产交换,这种跨链的方式比较单一,只支持资产的交换,如下图演示了Alice通过交易所,用比特币和Bob交换ETH的过程。

  1. Alice 通过交易所钱包将自己的比特币打入交易所地址;
  2. Alice 在交易所上挂上卖单1个BTC卖出20ETH价格;
  3. Bob需要将自己的ETH打入交易所的以太坊地址;
  4. Bob通过交易所挂出购买比特币的单子 20ETH买一个比特币;
  5. 交易所将Alice的卖单和Bob的卖单进行撮合;
  6. 交易所将Alice在交易所存储的1BTC 转移给Bob的比特币地址;
  7. 交易所将Bob在交易所存储的20ETH 转移给Alice的以太坊地址;

至此完成了Alice和Bob的BTC和ETH的交换(_案例中省去了交易所的服务费_)。通过该例子可以看出交易所的方式目前仅能够支持资产的交换,且资产交换的原子性、安全性完全由中心化的交易所保障存在较大的中心化风险。

除此之外还有一种著名的分布式账本技术Ripple,也是采用类似公证人的机制来解决全球金融机构之间的资产交换。Ripple的系统架构如上图所示,Ripple系统中交易通过网络中的验证者进行交易的验证,验证者验证的交易通过加密算法保护交易内容不能被验证着窥探从而保证交易的隐私性。

公证人机制的跨链技术实现简单,且能够比较灵活地支持不同类型的底层区块链体系。公证人机制的主要问题在于公证人机制的安全性保障完全由公证人系统保障。参与跨链的相关方需要对中间人给予较大的信任。

哈希锁定

哈希时间锁定(HTLC)最早出现在比特币的闪电网络,跨链资产交换支持一定数量的A链资产和一定数量的B链资产进行原子交换。哈希时间锁定巧妙地采用了哈希锁时间锁,迫使资产的接收方在deadline内确定收款并产生一种收款证明给打款人,否则资产会归还给打款人。收款证明能够被付款人用来获取接收人区块链上的等量价值的数量资产或触发其他事件。

如下图所示,我们用一个例子来阐述如何使用哈希时间锁定进行跨链的原子资产交换,假设Alice和Bob有资产交换的需求,Alice想用1个BTC和Bob换20个ETH. 那么首先需要在两条链上设置哈希时间锁定合约,然后执行如下步骤:

  1. Alice 随机构建一个字符串s,并计算出其哈希 h = hash(s)
  2. Alice 将h发送给Bob的合约;
  3. Alice锁定自己的1个BTC资产,并设置一个较长的锁定时间t1, 并设置了获取该BTC的一个条件:谁能够提供h的原始值s就可以得到该BTC;
  4. Bob观察到Alice 合约中锁定了一个BTC, 然后Bob锁定自己的20个ETH资产,并设置一个相对较短的锁定时间t2, t2 < t1, Bob也设置了同样获取条件(谁提供h的原始值s就可以获取20个ETH);
  5. Alice将自己最初生成的字符串s 发送到Bob的合约里取得了20个ETH;
  6. Bob观察到步骤5中Alice的s值,将其发送给Alice的合约成功获取1个BTC; 至此Alice和Bob完成了资产的交换。

从上述的过程我们可以看出哈希时间锁定合约有一些约束条件:

  • 进行跨链资产交换的双方必须能够解析双方的合约内部数据,例如s,例如锁定资产的证明等;
  • 哈希锁定的超时时间设置时需要保证存在时间差,这样在单方面作弊时另一方可以及时撤回自己的资产。

哈希锁定的思想运用在支付领域较多,例如闪电网络雷电网络以及跨链资产转移协议Interledger等。但是哈希锁定目前看只适合偏资产或者关键数据的交换,甚至不支持转移因此其试用场景受限。

侧链/中继链

侧链

侧链是相对于主链而言的,最初的侧链提出是针对比特币做新特性的测试和研发。侧链相对主链而言能够验证和解析主链中的区块数据和账本数据。侧链实现的基础技术是双向锚定(Two-way Peg),通过双向锚定技术可以将数字资产在主链上进行锁定,同时将等价的资产在侧链中释放。相反当侧链中相关资产进行锁定时,主链上锚定的等价资产也可以被释放。

BTC-Relay是号称的史上第一个侧链,BTC-Relay是通过以太坊构建了一个比特币的侧面,运用以太坊的智能合约允许用户验证比特币的交易。这里我们仍然以Alice 1BTC和Bob的20ETH数字资产交换为例阐述相应原理:

  1. Bob将20ETH发送到BTCSwap的合约进行冻结;(该合约只要能够确认BTC网络上Bob接收到来自Alice 1BTC就自动将20ETH转给Alice)
  2. Alice 确认Bob冻结信息后,将1 BTC转给Bob比特币账户;
  3. BTC Relayer将比特币区块头推送到BTCSwap合约;
  4. Alice 接下来就可以调用relay tx;
  5. BTCSwap合约结合tx和BTC链的区块链进行SPV验证,验证通过则将20ETH转给Alice以太坊地址。

这种跨链的实现方式简单,但是BTC Relay需要额外的信任和维护成本,且智能合约内部的数据存储会有体积膨胀的问题。但是侧链的机制相对哈希锁定而言能够提供更多的跨链交互场景,侧链以及类SPV验证的思想适合所有跨链的场景。

中继链

中继链本质上算是公证人机制和侧链机制的融合和扩展,目前社区内最活跃的两个跨链项目CosmosPolkadot 采用的都是基于中继链的多链多层架构,其中Cosmos目前支持的是跨链资产交互而Polkadot则宣称提供任意类型的跨链交互,具体实现还有待观察。

Cosmos Cosmos网络是一个多链混合的区块链网格结构,如下图所示,该网络中主要包括两种角色: Hub: 用于处理跨链交互的中继链; Zone: Cosmos中的平行链, Cosmos中平行链需要具备两个前提条件: 1. 快速确定性(fast finality), 这个特性由共识算法保障,也就是说Cosmos的跨链不直接支持PoW等概率确定模型的区块链; 2. 强监管性(Sovereignty):每个平行链都具有一组验证者能够决定其出块。

为了支持平行链之间的跨链互操作,Cosmos提出了一种跨链交互协议IBC(Inter-Blockchain Communication protocol), 并利用tendermint共识算法的即时确定性实现多个异构链之间的价值和数据传输。

首先我们以Chain A 到Chain B 转账10 token为例说明使用IBC的跨链交互: 1. 互相跟踪,也就是说如果A要和B进行跨链交易,那么A和B链需要分别运行相当于对方区块链的轻节点服务,这样互相可以实时接收到对方的区块头信息(方便后续执行类SPV验证); 2. A链上初始化IBC协议,冻结相关资产10 token, 并生成相应的证明发送给B区块链; 3. B链接收到相应的IBC消息,通过A链的区块头信息确定A确实进行相应的资产冻结,然后B链会生成等价值10 token的资产。

以上是使用IBC协议的两个平行链直接进行跨链的基本过程,如果区块链很多,那么这种方式的两两跨链复杂度会呈现组合级别增加。因此Cosmos网络又引入了一种Hub的中继链,所有的平行链都通过IBC连接到Hub,让Hub辅助跨链交易的验证和转移,目前Cosmos实现了一个官方的Hub称为Cosmos Hub(如前图所示)。

如下图所示是Cosmos 网络的详细架构图,Cosmos为方便平行链开发提供了基本服务CosmosSDK包括:共识、网络以及IBC协议等,这样基于Cosmos SDK开发的子链之间都能够方便地互相交互。此外对于非Cosmos SDK 开发的区块链需要使用Peg Zone进行桥接,如图中的Ethereum。

笔者认为Cosmos为跨链带来的最大贡献在于IBC协议的设计,IBC协议提供了一种通用的跨链协议标准。IBC的设计使得跨链交易可以在多个Hub之间进行安全路由和转发,类似目前互联网的TCP/IP 协议。但是遗憾的是目前的Cosmos设计也只能够支持资产的跨链,而且由于不同区块链的业务不同其共识速率的不一致也会影响跨链交易有效性的证明。

Polkadot

Polkadot也是一种集成平行链和中继链的多层多链架构,Polkadot区块链的整体架构图如下图所示,主要包含三种角色链和四种参与方:

三种链角色:

  1. 中继链(Relay chain): 中继链位于Polkadot的体系的核心地位,主要是为整个系统提供统一的共识和安全性保障;
  2. 平行链(Parachain): 在Polkadot中平行链负责具体的业务场景,平行链自身不具备区块的共识,它们将共识的职责渡让给了中继链,所有平行链共享来自中继链的安全保障,中继链是Polkadot组成的一部分;
  3. 桥接链:桥接链指的是非Polkadot体系之外的区块链,如Bitcoin, Ethereum, 这些区块链有自身的共识算法,它们通过不同的Bridge与Polkadot连接在一起进行跨链交互。

四种参与方:

  1. 验证者(Validator): 验证者负责Polkadot的网络出块,会运行一个中继链的客户端,在每一轮区块产生中会对其提名的平行链出的块进行核验。当平行链的跨都被他们的子验证者集合确定好之后,验证者们会将所有平行链区块头组装到中继链的区块并进行共识。
  2. 核验人(Collator): 帮助验证者收集、验证和提交备选平行链区块,维护了一个平行链的全节点。
  3. 钓鱼人(Fisherman):钓鱼人主要靠检举非法交易或者区块以获取收益;
  4. 提名人(Nominator): 拥有stake的相关方,维护和负责验证者的安全性。

Polkadot的特性包括两个,一个是共享安全性,一个是不需信任的跨链交互。这里的不需信任的跨链交互其实是和第一个特点共享安全性密切相关的,而且Polkadot的不需信任的跨链交互也主要是只其内部的平行链之间。

在Polkadot中如果parachain A 需要发送一笔交易到parachain B的过程如下:

  1. A链将跨链交易放到自己的engress(每个平行链有一个消息输出队列engress 和一个消息输入队列ingress);
  2. A链的Collator收集A链的普通交易以及跨链交易并提交给A链的验证者集合;
  3. A链的验证者集合验证成功,将本次A链的区块头信息以及A链的engress内信息提交到中继链上;
  4. 中继链运行共识算法进行区块确认以及跨链交易路由,中继链上的验证者会将A链的相应交易从A链的engress queue中移动到B链的ingress queue中。
  5. B链执行区块,将ingress queue中相应交易执行并修改自身账本。

以上便是Polkadot跨链交易的主要步骤,由于所有平行链的共识同步发生(中继链区块示意图如下),因此跨链交易不会有诸如双花等安全性问题。

Polkadot 的平行链之间的跨链交换的安全性保障主要来自共享安全性这个特点,共享安全性使得跨链交易和普通交易同步发生也就不存在其他跨链场景中的双花等跨链数据不一致问题。其次Polkadot中的引入的特殊状态验证方法方便中继链进行跨链等消息的有效性验证。

值得一提的是Polkadot项目目前还处在项目初期,对于parachain的设计、Collator的协作以及Validator的共识、工作效率等都未完善。这种共享安全性的方式是否也限制了平行链自身的性能都还有待考证。

关于跨链技术的几点思考

综合以上的一些主流跨链场景和方案的分析,从跨链的概念以及需求上看跨链的本质其实就是 如何将A链上的消息M安全可信地转移到B链并在B链上产生预期效果。那么一个成功的跨链交互到底需要解决哪些问题呢?笔者认为主要有以下四个问题:

  1. 消息M的真实性证明,也就是说M是否确实是存在A链上的,也确实是A链发给B链的;
  2. 消息M的路由,如何让跨链消息安全跨系统路由;
  3. 消息M的有效性证明,这里的有效性是指来自A链的消息M如何让B链认可其抵达B链时状态仍然有效,比如转移的资产是否是冻结的,没有双花的,如果是状态那么是否在此期间未发生改变等;
  4. 消息M的执行结果证明,这个是指A链需要确认跨链操作是否成功,以及成功操作的相应回执。

那么针对这些关键本质问题,如何去处理呢?笔者设想未来的区块链应该在底层平台的设计之初就需要遵循统一的跨链协议标准,就像现在的操作系统对TCP/IP协议的支持一样。需要进行通用跨链的区块链至少要支持一下功能:

  1. 提供跨链消息的输入和输出口径,例如Cosmos和Polkadot的跨链队列;
  2. 提供跨链消息的真实性证明,区块链需要提供类似SPV的证明手段;
  3. 消息的有效路由需要构建跨链消息的统一格式,定义好消息的来源和去处以及消息内容,如Cosmos的IBC协议;
  4. 消息的有效性证明,区块链可能需要设计新的类似UTXO的可验证存储结构,方便做类SPV类验证,否则目前的基于KV的数据存储方式做有效性证明几乎不可能;
  5. 跨链执行结果证明,和有效性证明类似,需要全新的数据结构和运行算法支持。

除此之外,跨链系统的设计还需要考虑系统稳定性、可扩展性以及易升级性、容错等等,总而言之,真正的可信互联网建设艰辛蛮长,诸君共勉!

JDK8中StampedLock的使用

StampedLock与ReentrayLock相比,使用上要复杂些,并且不可重入,但是在某些场景下性能比重入锁好。

StampedLock为共享变量的读写提供三种模式:乐观读,读锁,写锁StampedLock中获取锁的方法成功后会返回一个数字邮戳,用来控制对锁的访问及释放,获取失败会一直阻塞。带try前缀的锁获取方法获取锁失败会返回0。调用锁释放与锁转换方法需要传入获取锁时得到的数字邮戳,如果不匹配会失败。

下面详细解释下三种锁模式:

  • 写入锁:writeLock方法会获取对资源的独占访问权,如果获取不到锁就一直阻塞,返回的数字邮戳可以传入unlockWrite方法释放该写入锁。JDK还提供了可以传入超时时间的tryWriteLock方法用来获取写入锁。当StampedLock处于写入锁状态时,所有读取锁、乐观读验证都会失败。
  • 读取锁:readLock会一直阻塞直到资源的独占访问权被释放,其实就是写锁被释放,返回的数字邮戳可以传入unlockRead方法释放该读取锁。JDK还提供了可以传入超时时间的tryReadLock方法用来获取写入锁。
  • 乐观读:没有写入锁时,tryOptimisticRead方法会返回一个非零的数字邮戳,validate方法会验证该数字邮戳是否有效,两个方法执行期间有别的线程获取了写入锁,则邮戳失效。乐观读可以看做是一个弱化版的读取锁,可以被写入锁任意打断。对短只读代码片段使用乐观读模式通常会减少锁竞争并提高吞吐量。然而,其使用本身是脆弱的。乐观读取部分应该只读取字段,并将它们保存在局部变量中,以便在验证之后使用。在乐观读模式下读取的字段可能前后不一致,因此只有足够熟悉字段含义,直到如何检查一致性或调用validate方法,再应用此模式。例如,当读取对象或数组引用时,访问其字段、元素或方法之一,通常需要执行上述validate方法。

此类还支持在三种锁模式之间有条件地进行转换。例如,方法TryconvertToWriteLock尝试进行锁升级,如果

(1)已经处于写入锁模式

(2)处于读取锁模式且没有其他读取锁线程

(3)处于乐观读模式且锁可用,则返回有效的写入戳。
StampedLocks are designed for use as internal utilities in the development of thread-safe components. Their use relies on knowledge of the internal properties of the data, objects, and methods they are protecting. They are not reentrant, so locked bodies should not call other unknown methods that may try to re-acquire locks (although you may pass a stamp to other methods that can use or convert it). The use of read lock modes relies on the associated code sections being side-effect-free. Unvalidated optimistic read sections cannot call methods that are not known to tolerate potential inconsistencies. Stamps use finite representations, and are not cryptographically secure (i.e., a valid stamp may be guessable). Stamp values may recycle after (no sooner than) one year of continuous operation. A stamp held without use or validation for longer than this period may fail to validate correctly. StampedLocks are serializable, but always deserialize into initial unlocked state, so they are not useful for remote locking.
Like Semaphore, but unlike most Lock implementations, StampedLocks have no notion of ownership. Locks acquired in one thread can be released or converted in another.
The scheduling policy of StampedLock does not consistently prefer readers over writers or vice versa. All “try” methods are best-effort and do not necessarily conform to any scheduling or fairness policy. A zero return from any “try” method for acquiring or converting locks does not carry any information about the state of the lock; a subsequent invocation may succeed.
Because it supports coordinated usage across multiple lock modes, this class does not directly implement the Lock or ReadWriteLock interfaces. However, a StampedLock may be viewed asReadLock(), asWriteLock(), or asReadWriteLock() in applications requiring only the associated set of functionality.
Sample Usage. The following illustrates some usage idioms in a class that maintains simple two-dimensional points. The sample code illustrates some try/catch conventions even though they are not strictly needed here because no exceptions can occur in their bodies.

class Point {
private double x, y;
private final StampedLock sl = new StampedLock();

// an exclusively locked method
void move(double deltaX, double deltaY) {
long stamp = sl.writeLock();
try {
x += deltaX;
y += deltaY;
} finally {
sl.unlockWrite(stamp);
} }

// a read-only method
// upgrade from optimistic read to read lock
double distanceFromOrigin() {
long stamp = sl.tryOptimisticRead();
try {
retryHoldingLock: for (;; stamp = sl.readLock()) {
if (stamp == 0L)
continue retryHoldingLock;
// possibly racy reads
double currentX = x;
double currentY = y;
if (!sl.validate(stamp))
continue retryHoldingLock;
return Math.hypot(currentX, currentY);
} } finally {
if (StampedLock.isReadLockStamp(stamp))
sl.unlockRead(stamp);
} }

// upgrade from optimistic read to write lock
void moveIfAtOrigin(double newX, double newY) {
long stamp = sl.tryOptimisticRead();
try {
retryHoldingLock: for (;; stamp = sl.writeLock()) {
if (stamp == 0L)
continue retryHoldingLock;
// possibly racy reads
double currentX = x;
double currentY = y;
if (!sl.validate(stamp))
continue retryHoldingLock;
if (currentX != 0.0 || currentY != 0.0)
break;
stamp = sl.tryConvertToWriteLock(stamp);
if (stamp == 0L)
continue retryHoldingLock;
// exclusive access
x = newX;
y = newY;
return;
} } finally {
if (StampedLock.isWriteLockStamp(stamp))
sl.unlockWrite(stamp);
} }

// Upgrade read lock to write lock
void moveIfAtOrigin(double newX, double newY) {
long stamp = sl.readLock();
try {
while (x == 0.0 && y == 0.0) {
long ws = sl.tryConvertToWriteLock(stamp);
if (ws != 0L) {
stamp = ws;
x = newX;
y = newY;
break;
} else {
sl.unlockRead(stamp);
stamp = sl.writeLock();
} }
} finally {
sl.unlock(stamp);
} }
} Since:
1.8
< 11 >

了解JDK自带命令

主要参考https://docs.oracle.com/javase/8/docs/technotes/tools/unix/index.html $JDK_HOME/bin目录下的命令主要分为几大类,我只总结一些常用的

构建、运行命令

jar: 打包、更新、解包命令,用法类似于linux下的tar命令。 java: Starts a Java application. javac: Reads Java class and interface definitions and compiles them into bytecode and class files. javadoc: Generates HTML pages of API documentation from Java source files. javah: Generates C header and source files from a Java class. javap: Disassembles one or more class files. jdb: Finds and fixes bugs in Java platform programs.

Security

These commands set security policies on your local system and create applications that can work within the scope of the security policies set at remote sites. keytool: Manages a keystore (database) of cryptographic keys, X.509 certificate chains, and trusted certificates. jarsigner: Signs and verifies JAR files. policytool: Reads and writes a plain text policy file based on user input through the utility GUI.

Internationalization

native2ascii: Creates localizable applications by converting a file with characters in any supported character encoding to one with ASCII and/or Unicode escapes (\uxxxx) notation for all characters that are not part of the ASCII character set, or vice versa.

Remote Method Invocation (RMI)

These commands create applications that interact over the web or with another network. rmic: Generates stub, skeleton, and tie classes for remote objects that use the Java Remote Method Protocol (JRMP) or Internet Inter-Orb protocol (IIOP). Also generates Object Management Group (OMG) Interface Definition Language (IDL). rmiregistry: Starts a remote object registry on the specified port on the current host. rmid: Starts the activation system daemon that enables objects to be registered and activated in a Java Virtual Machine (JVM). serialver: Returns the serial version UID for specified classes.

Java IDL and RMI-IIOP

These commands create applications that use OMG-standard IDL and CORBA/IIOP. tnameserv: Starts the Java Interface Definition Language (IDL) name server. idlj: Generates Java bindings for a given Interface Definition Language (IDL) file. orbd: Enables clients to locate and call persistent objects on servers in the CORBA environment. servertool: Provides an easy-to-use interface for the application programmers to register, unregister, start up, and shut down a server.

Deploy Applications and Applets

pack200: Packages a JAR file into a compressed pack200 file for web deployment. unpack200: Transforms a packed file produced by pack200(1) into a JAR file for web deployment.

Java Web Start

javaws: Starts Java Web Start.

监控java程序

jconsole: Starts a graphical console that lets you monitor and manage Java applications. jvisualvm: Visually monitors, troubleshoots, and profiles Java applications.

监控jvm

Most of these these commands are unsupported and experimental and might not be available in future JDK release. jps: Experimental. Lists the instrumented Java Virtual Machines (JVMs) on the target system. jstat: Experimental. Monitors JVM statistics jstatd: Experimental. Monitors JVMs and enables remote monitoring tools to attach to JVMs. jmc: Starts Java Mission Controla tool for monitoring and managing running Java applications and JVMs.

网络服务

schemagen: Generates a schema for every name space that is referenced in your Java classes. wsgen: Reads a web service endpoint implementation (SEI) class and generates all of the required artifacts for web service deployment, and invocation. wsimport: Generates JAX-WS portable artifacts that can be packaged in a web application archive (WAR) file and provides an Ant task. xjc: Compiles an XML schema file into fully annotated Java classes.

排查问题

Most of these commands are unsupported and experimental and might not be available in future JDK releases. jcmd: Sends diagnostic command requests to a running JVM. jinfo: Experimental. Generates configuration information. jhat: Experimental. Analyzes the Java heap. jmap: Experimental. Prints shared object memory maps or heap memory details for a process, core file, or remote debug server. jsadebugd: Experimental. Attaches to a Java process or core file and acts as a debug server. jstack: Experimental. Prints Java thread stack traces for a Java process, core file, or remote debug server.

Scripting

This command is unsupported and experimental and might not be available in future JDK releases. jrunscript: Experimental. Runs a command-line script shell that supports interactive and batch modes.

使用JDK自带命令分析死锁问题

首先写一段死锁代码跑起来

package com.demo;
public class DeadLock {
private Object lock1 = new Object();
private Object lock2 = new Object();
public static void main(String[] args) {
final DeadLock dLock = new DeadLock();
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 100; i++) {
try {
dLock.test1(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 100; i++) {
try {
dLock.test2(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
private void test1(int count) throws InterruptedException {
synchronized (lock1) {
synchronized (lock2) {
System.out.println(“test1 done” + count);
Thread.sleep((long) (Math.random() * 1000));
}
}
}
private void test2(int count) throws InterruptedException {
synchronized (lock2) {
synchronized (lock1) {
System.out.println(“test2 done” + count);
Thread.sleep((long) (Math.random() * 1000));
}
}
}
}

运行结果如下: 使用jps命令查看当前死锁进程号 再用jstack命令加上一步查到的进程号,来进一步查看该进程的堆栈信息,关注最下面的部分,已经自动检测到死锁相关信息,排查起来很方便:

一个故事告诉你比特币的原理及运作机制(转载)

转载自http://blog.codinglabs.org/articles/bitcoin-mechanism-make-easy.html

周末花时间看了一些比特币原理相关的资料,虽然不敢说把每个细节都完全搞懂了,不过整体思路和关键部分的主要原理还是比较明白。写一篇文章分享给大家。这篇文章的定位会比较科普,尽量用类比的方法将比特币的基本原理讲出来。这篇文章不会涉及算法和协议中比较细节的部分,打算后面会再写一篇程序员视角下的比特币原理,那里会从技术人员的视角对比特币系统中较为关键的数据结构、算法和协议进行一些讲解。 在这篇文章中我会给出一个虚拟的村庄叫“比特村”,整个文章会以讲故事的方式,逐步告诉大家比特币提出的动机、解决了什么问题以及一些关键组件的目标和设计方案。

问题的提出

我们先从比特币产生的动机开始。

以物易物的比特村

话说在这个世界上,有一个叫比特村的小村庄,村庄共有几百户人家。这个村庄几乎与世隔绝,过着自给自足的生活。由于没有大规模贸易,比特村村民一直过着以物易物的生活,也就是说村民之间并没有使用统一的货币,互相间的贸易基本上就是老张家拿一袋面粉换老李家一只羊,王大嫂拿一筐野果换刘大婶两尺布。村民们一直就这么纯朴的生活着。

实物货币

终于有一天,村民觉得一直这样以物易物实在太不方便了,于是村子全员开会,讨论如何解决这个问题。有人提议,以便于分割且稀有的东西,例如黄金,作为一般等价物,把其它物品和黄金的对应关系编成一张表格,例如一克黄金对应一只羊,一克黄金对应一袋面粉等等,此时老张再也不用扛着一袋面粉气喘吁吁的去老李家换羊了,他只要从家里摸出一克金子,就可以去老李家牵回一只羊,而老李拿着这一克黄金可以从任何愿意出让面粉的人那里换回一袋面粉,当然也可以换取任何和一克黄金等值的物品。 此时比特村进入了实物货币时代。

符号货币

好景不长,过了一段时间,实物货币的弊端也出现了。因为比特村附近金矿并不多,开采和冶炼金子太费时费力了。而随着使用,金子总是不断会因为磨损、丢失或有人故意囤积而发生损耗。全村人又一次坐在了一起,开始商讨对策。此时有人说,其实大家也不必一定要真的用黄金啊,随便找张纸,写上“一克黄金”,只要全村人都认同这张纸就等于一克黄金,问题不就解决了。其他人纷纷表示认同,但同时也有了新的问题:真实的黄金是需要开采和冶炼的,金矿有限,开采和冶炼也需要成本,所以没有人可以短期凭空制造大量的黄金,可写字就不同了,只要我纸够笔够,随便像写多少写多少,那这就变成拼谁家里纸多了,搞不好到时一万张纸才能换一只羊(实际上这就发生了经济学上的通货膨胀)。 大家一想也是啊。不过此时又有人提出了解决方案:这个纸不是谁写都有效,我们只认村里德高望重的老村长写得,大家都认识老村长的字。老村长写一些纸,同时按照各家黄金存量发给大家等量的纸,例如老张家有二百克黄金,老村长就发给老张二百张写着“一克黄金”的纸,同时将老张家的黄金拿走作为抵押。就这样,老村长将村里所有黄金收归到自己的家里,并按各家上交的黄金数量发给等值的写有字的纸。此时村民就可以拿着这些纸当黄金进行贸易了,而且大家都认得老村长的字,其他人伪造不出来。另外,如果谁的纸磨损太严重,也可拿到老村长那里兑换新的等值的纸,另外老村长承诺任何人如果想要换成真黄金,只要拿纸回来,老村长就会把等值的黄金还给那人。因为老村长写得纸的黄金量和真实放在家里的黄金量是一样的,所以只要严格按照销毁多少纸新写多少纸的原则,每一张有效的纸总能换回相应的真黄金。 此时,比特村进入了符号货币(纸币)时代。而老村长就承担了政府和银行的角色。

中央系统虚拟货币

又过了几年,老村长由于每天都要核对大量的旧纸币,写新的纸币,还要把各种账目仔细做好记录。一来二去,老村长操劳过度不幸驾鹤西去了。 比特村再次召开全体大会,讨论应该怎么办。此时老村长的儿子二狗子自告奋勇接过了父亲的笔,承担起货币发行的责任。这个年轻的村长二狗子很聪明,他做了几天,发现好像也不用真的写那么多纸。完全可以这样:村民把纸币都交上来,销毁,但是二狗子会记录下每户上交的纸币数量。以后如果要进行付钱,例如老张要拿一克金子向老李换一只羊,就一起给二狗子打个电话,说明要将老张名下的一克金子划归老李名下,二狗子拿出账本,看看老张名下是否有一克金子,如果有就在老张的名下减掉一克,在老李的名下加上一克,这样就完成了支付,此时老李在电话中听到二狗子确认转账完成,就可以放心让老张把羊牵走了。 此时比特村进入了中央系统虚拟货币时代。每个村民都不需要用实物支付,支付过程变成了二狗子那边维护的账本上数字的变更。

分布式虚拟货币

这新上任的二狗子是聪明,不过这人有时候是聪明反被聪明误。有一天二狗子盯着这账本,心想这全村各户谁有多少钱就是我说的算,那我岂不是……。于是他头脑一热,私自从老张帐下划了十克金子到自己名下。 本以为天衣无缝,但没想到老张也有记账的习惯,有一天他正要付钱却被二狗子告知账户没钱了。老张核对了一下自己的账本,明明还有十克啊,于是拿着账本去找二狗子理论,这一核对发现了那笔未经老张同意的转账。 东窗事发!比特村炸开锅了。二狗子被弹劾是不可避免了,不过通过这件事,大家发现了账本集中在一个人手里的弊端:

  • 这个体系完全依赖于账本持有人的个人信用,如果这个人不守规矩,随意篡改账本,那么整个货币系统就会崩溃
  • 如果这个人家里失火或者账本失窃,同样也会为整个体系带来毁灭性的打击

正当人们不知所措时,村里一个叫中本聪的宅男科学家走上了台,告诉大家他已经设计了一套不依赖任何中央处理人的叫比特币的虚拟货币系统,可以解决上述问题。然后他缓缓讲述了自己的方案。 下面我们就来看看中本聪同学是如何设计这套系统的。

基础设施搭建

账簿公开机制

中本聪首先说明,要对现有账簿进行如下改造:

  1. 账簿上不再记载每户村民的余额,而只记载每一笔交易。即记载每一笔交易的付款人、收款人和付款金额。只要账簿的初始状态确定,每一笔交易记录可靠并有时序,当前每个人持有多少钱是可以推算出来的。
  2. 账簿由私有改为公开,只要任何村民需要,都可以获得当前完整的账簿,账簿上记录了从账簿创建开始到当前所有的交易记录。

此言一出,下面立刻炸锅了。第一条还无所谓,但是第二条简直无法接受,因为账簿可是记录了所有村民的交易,这样大家的隐私不全暴露了吗。 中本聪倒是不慌不忙,拿出了一对奇怪的东西。

身份与签名机制(公钥加密系统)

中本聪说,大家不要慌。在他的这套机制下,任何人都不使用真实身份交易,而是使用一个唯一的代号交易。 他展示了手里神奇的东西,说这两件东西分别叫保密印章和印章扫描器。后面他会给村里每一户发一个保密印章和一个印章扫描器。两者的作用如下:

  • 保密印章可以在纸上盖一个章,每个印章盖出的章都隐含了一个全村唯一的一串字符,但是凭肉眼是看不出来的。也无法通过观察来制造出相应的印章。
  • 印章扫描器可以扫描某个已经盖好的章,读出隐含的信息,并在液晶屏上显示出一串字符。

有了这两个神奇的东西,大家就可以在不暴露真实身份的情况下进行交易了,而印章隐含的那一串字符就是这户人家的代号。具体如何巧妙利用保密印章和印章扫描器进行交易,会在下文详述。

成立虚拟矿工组织(挖矿群体)

下一步,中本聪面向全村招募虚拟矿工,招募要求如下:

  • 矿工以组为单位,一组可以是单独的一户,也可以是几户联合为一组
  • 成为矿工不影响正常使用货币
  • 矿工每天要花费一定时间从事比特币“挖矿”活动,但是不同于挖金矿,虚拟矿工不需要拿着工具去野外作业,在家里就可以完成工作
  • 矿工有一定可能性获得报酬,在挖矿活动中付出的努力越多,获得报酬的可能性越大
  • 矿工可以随时退出,也可以随时有新的矿工加进来

很快,大约有五分之一的村民加入比特币矿工组织,共分成了7个组。

建立初始账簿(创世块)

下面,中本聪宣布,先根据二狗子手里的账簿,把抵押的所有黄金按账簿记录的余额退还给每位村民,然后彻底销毁这本账簿。 然后,中本聪拿出一本新账簿,在账簿的第一页上记录了一些交易记录,特别的是,这些记录的付款人一栏全都是“系统”,而收款人分别是每个印章对应的隐含字符,代表初始时刻,系统为每一户默认分配了一定数量比特币,但是数量非常少,都只有几枚,甚至有些不幸的村户没有获得比特币。 接着中本聪说,由于目前市面上比特币非常少,大家可以先回到用黄金做货币的时代,由于我不是村长,我也没有权利强迫大家一定要承认比特币,大家可以自行决定要不要接受比特币。不过随着比特币的流动和矿工的活动,比特币会慢慢多起来。

支付与交易

做了这么多铺垫,终于说到重点了,下面说一下在这样一个体系下如何完成支付。以老张付给老李10个比特币为例。

付款人签署交易单

为了支付10个比特币,老张首先要询问老李的标识字符串,例如是“ABCDEFG”,同时老张也有一个标识字符串例如是“HIJKLMN”,然后老张写一张单子,内容为“HILKLMN支付10比特币给ABCDEFG”,然后用自己的保密印章改一个章,将这张单子交给老李。另外为了便于追溯这笔钱的来源,还要在单子里注明这笔钱的来源记在哪一页,例如这个单子里,老张的10比特币来自建立账簿时系统的赠送,记录在账簿第一页。

收款人确认单据签署人

老李拿到这个单子后,需要确认这个单子确实是来自“HIJKLMN”这个人(也就是老张)签署的,这个并不困难。因为单子上必须有保密章,老李拿出印章扫描器,扫一下章,如果液晶屏显示出的字符和付款人字符是一致的(这里是“HIJKLMN”),就可以确认单子确实是付款人签署的。这是因为根据保密印章的机制,没有其他人可以伪造印章,任何一个人只要扫描一下印章,都可以确认单子的付款人和盖章人是否一致。

收款人确认付款人余额

这个系统到目前还是很有问题。通过保密印章,收款人虽然可以确认付款人确实签署了这份单子,但是无法自行确认付款人是否有足够的余额支付。之前的中央虚拟货币系统中,二狗子负责检查付款人的余额,并通知收款人交易是否有效,现在把二狗子开了,谁来负责记账和确认每笔交易的有效性呢? 之前说过,中本聪设计的这个系统是分布式货币系统,不依赖任何中央人物,所以不会有一个或少数几个人负责这件事,最终承担这份工作的是之前所提到的矿工组织。老张、老李和全村其他任何使用比特币进行交易的村民都依赖矿工组织的工作才能完成交易。

矿工的工作

矿工的工作是整个系统的核心,也是最复杂性最高的地方。下面逐步介绍矿工的工作内容和目的。

矿工的工具

俗话说,工欲善其事,必先利其器。比特币矿工虽然不用铁撅、铁锨和探照灯等工具,不过也要有一些必备的东西。 初始账簿。每个组首先自己复制一份初始账簿,初始账簿只有一页,记录了系统的第一次赠送 空账簿纸。每个小组有若干账簿纸,每一页纸上仅有账簿结构,没有填内容,具体内容的书写规则后面讲述。下面是一张空账簿纸的样子,各个字段的意义后面会说到

编码生成器(哈希函数)。中本聪又向矿工组织的每个组分发了若干编码生成器,这个东西很神奇,将一页账簿填好内容的账簿纸放入这个机器,机器会在账簿纸的“本账单编号”一栏自动打印一串由“0”和“1”组成的编号,共256个。最神奇的是,编号生成器有如下功能:

  • 生成的编号仅与账簿纸上填入的内容有关,与填写人、字体、填写时间等因素均无关
  • 内容相同的账簿纸生成的编号总是相同,但是如果内容哪怕只改一个字符,编号就会面目全非
  • 编码生成器在打印编码时还需要将所有填入账簿纸的交易单放入,机器会扫描交易单和填入交易单的一致性,尤其是保密印章,如果发现保密印章和付款人不一致,会拒绝打印编码
  • 将一张已打印的账簿纸放入,机器会判定编号是否是有效的机器打印,并且判定编号和内容是否一致,这个编号无法伪造
  • 交易单收件箱。每个矿工小组需要在门口挂一个箱子用于收集交易单。
  • 公告板。每个矿工小组同样需要一个公告板公示一些信息。

有了上面的工具,矿工组织就可以开工了!

收集交易单

中本聪规定,每笔交易的发起人,不但要将交易单给到收款人,还要同时复制若干份一模一样的交易单投递到每个矿工小组的收件箱里。 矿工小组的人定期到自己的收件箱里把收集到的交易单一并取出来。

填写账簿

此时小组的人拿出一张空的账簿纸,把这些交易填写到“交易清单”一栏,同时找到当前账簿最后一页,将最后一页的编号抄写到“上一张账单编号一栏”。 注意还有个“幸运数字”,可以随便填上一个数字,如12345。然后,将这样账簿纸放入编号生成器,打印好编号,一张账簿就算完成了。 如果你以为矿工的工作就这么简单,那就大错特错了,中本聪有个变态的规定:只有编号的前10个数均为0,这页账簿纸才算有效。 根据之前对编号生成器的描述,要修改编号,只能修改账簿纸的内容,而“交易清单”和“上一张账簿纸编号”是不能随便改的,那么只能改幸运数字了。于是为了生成有效的账簿纸,小组里的矿工就不断抄写账簿纸,但每张纸的幸运数字都不同,然后不断的重复将纸放入编码器,如果生成的编号不符合规定,这张纸就算废了,重复这个过程直到生成一串有效的编号。 我们知道,如果编号的每一个数字都是随机的,那么平均写1000多张幸运数字不同的纸才能获得一个有效的编号。 这就奇怪了,这些矿工为什么要拼命干这看似无意义的事情呢?还记得之前说过矿工有报酬吧,这就是矿工的动力了。中本聪规定:每一张账簿纸的交易清单第一条交易为“系统给这个小组支付50个比特币”。也就是说,如果你生成了一张有意义的账簿纸,并且被所有挖矿小组接受了,那么就意味着这条交易也被接受了,你的挖矿小组获得了50个比特币。 这就是矿工被叫做矿工的原因,也是为什么之前说随着交易和矿工的活动,比特币的数量会不断增多。例如下面是一个挖矿过程,这个小组的公共比特币帐号为“UVWXYZ”。

在幸运数字尝试到“533”时,系统生成了一页有效账簿。

确认账簿

当某挖矿小组幸运的生成了一张有意义的账簿,为了得到奖励,必须立刻请其它小组确认自己的工作。前面说过,当前村里有7个挖矿组,所以这个小组必须将有效账簿纸誊抄6份快马加鞭送到其他6个小组请求确认。 中本聪规定,当某个小组接到其他小组送来的账簿纸时,必须立即停下手里的挖矿工作进行账簿确认。 需要确认的信息有三个:

  1. 账簿的编号有效
  2. 账簿的前一页账簿有效
  3. 交易清单有效

首先看第一个,这个确认比较简单。只要将送来的账簿纸放入编码生成器进行验证,如果验证通过,则编号有效。 第二部分需要将账簿页上的“上一页账簿纸编号”和这个小组目前保存的有效账簿最后一页编号比对,如果相同则确认,如果不同,需要顺着已有账簿向前比对,直到找到这个编号的页。如果没有找到指定的“上一页账簿纸编号”对应的页,这个小组会将此页丢掉。不予确认。 注意,由上面的机制可以保证,如果各个小组手里的账簿纸是相同的,那么他们都能按同样的顺序装订成相同的账簿。因为后面一张纸的编号总是依赖前面的纸的编号,编码生成器的机制保证了所有合法账簿纸的相对先后顺序在每个小组那里都是相同的(可能会有分支,但不会出现环,后面细讲)。

最后是如何确认交易清单有效,其实也就是要确认当前每笔交易的付款人有足够的余额支付这笔钱。由于交易信息里包含这笔钱是如何来的,还包含了记录来源交易的账单编号。例如,HIJKLMN要给ABCDEFG10个比特币,并注明了这10个比特币来自之前OPQRST支付给HIJKLMN的一笔交易,确认时首先要确认之前这笔交易是否存在,同时还要检查HIJKLMN在这之前没有将这10个比特币支付给别人。这一切确认后,这笔交易有效性就被确认了。 其中第一笔是系统奖励给生成这页账簿的小组的50个,这笔交易大家都默认承认,后面的只要按照上述方法追溯,就可以确认HIJKLMN是否当前真有10个比特币支付给ABCDEFG。 如果完成了所有了上述验证并全部通过,这个小组就认可了上述账簿纸有效,然后将这张账簿纸并入小组的主账簿,舍弃目前正在进行的工作,后面的挖矿工作会基于这本更新后的主账本进行。

账簿确认反馈

对于挖矿小组来说,当账簿纸送出去后,如果后面有收到其他小组送来的账簿纸,其“上一页账簿纸编号”为自己之前送出去的账簿纸,那么就表示他们的工作成功被其他小组认可了,因为已经有小组基于他们的账簿纸继续工作了。此时,可以粗略的说可以认为已经得到了50个比特币。 另外,任何一个小组当新生成有效账簿纸或确认了别的小组的账簿纸时,就将最新被这个小组承认的交易写到公告牌上,那么收款人只要发现相关交易被各个小组认可了,基本就可以认为这笔钱已经到了自己的账上,后面他就可以在付款时将钱的来源指向这笔交易了。 以上就是整个比特币的支付体系。下面我们来分析一下,这个体系为什么可以工作下去,以及这个体系可能面临的风险。

工作机制分析

虽然上面阐述了比特币的基本运作规则,但是村民们还是有不少疑问。所以中本聪同学专门开了个答疑会,解答常见问题。下面总结一下村民最集中关心的问题。

核心问题答疑

如果同时收到两份合法的账簿页怎么办?

注意在上面的运行机制中,各个挖矿小组是并行工作的,因此完全可能出现这样的情况:某小组收到两份不一样的账簿页,它们都基于当前这个小组的主账簿的最后一页,并且内容也都完全合法,怎么办? 关于这个问题,中本聪同学说,小组不应该以线性方式组织账簿,而应该以树状组织账簿,任何时刻,都以当前最长分支作为主账簿,但是保留其它分支。举个例子,某小组同时收到A、B两份账簿页,经核算都是合法的,此时小组应该将两页以分叉的形式组织起来,如下图所示:

黑色表示当前账簿主干。此时,可以随便选择一个页作为当前主分支,例如选择A:

此时如果有一个新的账簿页是基于A的,那么这个主干就延续下去:

如果这个主干一直这么延续下去,表示大家基本都以A为主干,B就会被遗忘。但是也有可能忽然B变成更长了:

那么我们就需要将B分支作为当前主干,基于这个分支进行后续工作。

从局部来看,虽然在某一时刻各个小组的账簿主干可能存在不一致,但大方向是一致的,那些偶尔由于不同步产生的小分支,会很快被淹没在历史中。

如果挖矿小组有人伪造账簿怎么办

关于这个问题,中本聪同学说,只要挖矿组织中大多数人是诚实的,这个系统就可靠,具体分几个方面给予答复。 首先,基于保密印章机制,没有人能伪造他人身份进行付款,因为编码生成器在打印编码时会核对所有交易单的保密印章,印章和付款人不一致会拒绝打印。 而且诚实的矿工也不会承认不合法的交易(如某笔交易付款方余额不够)。 所以只有一种可能的攻击行为,即在收款人确认收款后,从另一条分支上建立另外的交易单,取消之前的付款,而将同一笔钱再次付款给另一个人(即所谓的double-spending问题)。下面同样用一个例子说明这个问题。 先假设有一个攻击者拥有10个比特币,他准备将这笔钱同时支付给两名受害者A和B,并都得到承认。 第一步,攻击者准备从受害者A手里买10比特币的黄金,他签署交易单给受害者A,转10个比特币给受害者A。

第二步,这笔交易在最新的账簿页中被确认,并被各个挖矿小组公告出来。受害人A看到公告,确认比特币到账,给了攻击者10个比特币等值的黄金。

第三步,攻击者找到账簿,从包含刚才交易的账簿页的前一页做出一个分支,生成更多的账单页,超过刚才的分支。由于此时刚才攻击者制造的分支变成了主干分支,而包含受害者A得到钱的分支变成了旁支,因此挖矿组织不再承认刚才的转账,受害者A得到的10比特币被取消了。

第四步,攻击者可以再次签署交易单,将同一笔钱支付给受害者B。受害者B确认钱到账后,支付给攻击者等值黄金。

至此,攻击者将10个比特币花了两次,从两名受害者那里各购得等值黄金。攻击者还可以如法炮制,取消与受害者B的转账,将同一笔钱再支付给其他人…… 关于这种攻击,中本聪给出的解决方案是,建议收款人不要在公告挂出时立即确认交易完成,而是应该再看一段时间,等待各个挖矿小组再挂出6张确认账簿,并且之前的账簿没有被取消,才确认钱已到账。 中本聪解释道,之前设定变态的编号规则,正是为了防御这一点。根据前面所述,生成有效账簿页不是那么简单的,要花费大量的人力反复试不同的幸运数字,而且过程完全是碰运气。如果某账簿页包含你收到钱的确认,并且在后面又延续了6个,那么攻击者想要在落后6页的情况下从另一个分支赶超当前主分支是非常困难的,除非攻击者拥有非常多的人力,超过其他所有诚实矿工的人力之和。 而且,如果攻击者有如此多人力,与其花这么大力气搞这种攻击,还不如做良民挖矿来的收益大。这就从动机上杜绝了攻击的形成。

比特币会一直增加下去,岂不是会严重通货膨胀

中本聪说,这一点我也想到了。前面忘了说了,我给矿工组织的操作细则手册会说明,刚开始我们协议每生成一页账簿,奖励小组50个比特币,后面,每当账簿增加21,000页,奖励就减半,例如当达到210,000页后,每生成一页账簿奖励25个比特币,420,000页后,每生成一页奖励12.5个,依次类推,等账簿达到6,930,000页后,新生成账簿页就没有奖励了。此时比特币全量约为21,000,000个,这就是比特币的总量,所以不会无限增加下去。

没有奖励后,就没人做矿工了,岂不是没人帮忙确认交易了

到时,矿工的收益会由挖矿所得变为收取手续费。例如,你在转账时可以指定其中1%作为手续费支付给生成账簿页的小组,各个小组会挑选手续费高的交易单优先确认。

矿工如果越来越多,比特币生成速度会变快吗

不会。中本聪解释,虽然可以任意加入和退出矿工组织,导致矿工人数变化,每个矿工也会拿到一个编码生成器,不过我已经在编码生成器中加入了调控机制,当前工作的编码生成器越多,每个机器的效率就越低,保证新账簿页生成速率不变。

虽然每个人的代号是匿名的,但如果泄露了某个人的代号,账簿又是公开的,岂不是他的所有账目都查出来了

确实是这样的。例如你要和某人交易,必然要要到他的代号才能填写交易单。因为收款人一栏要填入那人的代号。不过中本聪说可以提供无限制的保密印章,建议每一次交易用不同的保密印章,这样查账簿就追查不到同一个人的所有账目了。 答疑完毕。

说明

本文用通俗比喻的方式讲解了比特币的运行机制。有几点需要说明:

  1. 为了便于理解,我做了很多简化,因此有些机制细节和实际的比特币可能不完全相同。但总体思想和关键原理是一致的。
  2. 由于很多计算机世界的东西(如公钥体系、网络传输)在现实世界中并没有特别好的对等物,所以故事里难免有一些生硬和不合常理的细节。
  3. 本文描述的是比特币网络本身的技术原理和运作机制,当在如Mtgox这种买卖市场中进行比特币交易时,市场做了中间代理,并不遵从上述机制

参考

  1. Bitcoin: A Peer-to-Peer Electronic Cash System
  2. https://bitcoin.it
  3. 云风的BLOG: Bitcoin 的基本原理
  4. 易懂的比特币工作机理详解

分布式一致性算法-Paxos(转载)

英文论文链接http://lamport.azurewebsites.net/pubs/paxos-simple.pdf 本来想自己写一下理解,上网查了下有人比我写的好,那就看别人写的吧。 原博文链接http://linbingdong.com/2017/04/17/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E5%88%97%E6%96%87%E7%AB%A0%E2%80%94%E2%80%94Paxos%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86%E4%B8%8E%E6%8E%A8%E5%AF%BC/ [pdf-embedder url=”http://www.jiangyc.tk/wp-content/uploads/2018/06/paxos-simple.pdf”] Paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点:1.难以理解 2.工程实现更难。 网上有很多讲解Paxos算法的文章,但是质量参差不齐。看了很多关于Paxos的资料后发现,学习Paxos最好的资料是论文《Paxos Made Simple》,其次是中、英文版维基百科对Paxos的介绍。本文试图带大家一步步揭开Paxos神秘的面纱。

Paxos是什么

Paxos算法是基于消息传递且具有高度容错特性一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。 虽然Mike Burrows说得有点夸张,但是至少说明了Paxos算法的地位。然而,Paxos算法也因为晦涩难懂而臭名昭著。本文的目的就是带领大家深入浅出理解Paxos算法,不仅理解它的执行流程,还要理解算法的推导过程,作者是怎么一步步想到最终的方案的。只有理解了推导过程,才能深刻掌握该算法的精髓。而且理解推导过程对于我们的思维也是非常有帮助的,可能会给我们带来一些解决问题的思路,对我们有所启发。

问题产生的背景

在常见的分布式系统中,总会发生诸如机器宕机网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性。 注:这里某个数据的值并不只是狭义上的某个数,它可以是一条日志,也可以是一条命令(command)。。。根据应用场景不同,某个数据的值有不同的含义。 问题产生的背景问题产生的背景

相关概念

在Paxos算法中,有三种角色:

  • Proposer
  • Acceptor
  • Learners

在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。 还有一个很重要的概念叫提案(Proposal)。最终要达成一致的value就在提案里。 注:

  • 暂且认为『提案=value』,即提案只包含value。在我们接下来的推导过程中会发现如果提案只包含value,会有问题,于是我们再对提案重新设计
  • 暂且认为『Proposer可以直接提出提案』。在我们接下来的推导过程中会发现如果Proposer直接提出提案会有问题,需要增加一个学习提案的过程。

Proposer可以提出(propose)提案;Acceptor可以接受(accept)提案;如果某个提案被选定(chosen),那么该提案里的value就被选定了。 回到刚刚说的『对某个数据的值达成一致』,指的是Proposer、Acceptor、Learner都认为同一个value被选定(chosen)。那么,Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢?

  • Proposer:只要Proposer发的提案被Acceptor接受(刚开始先认为只需要一个Acceptor接受即可,在推导过程中会发现需要半数以上的Acceptor同意才行),Proposer就认为该提案里的value被选定了。
  • Acceptor:只要Acceptor接受了某个提案,Acceptor就认为该提案里的value被选定了。
  • Learner:Acceptor告诉Learner哪个value被选定,Learner就认为那个value被选定。

相关概念相关概念

问题描述

假设有一组可以提出(propose)value(value在提案Proposal里)的进程集合。一个一致性算法需要保证提出的这么多value中,只有一个value被选定(chosen)。如果没有value被提出,就不应该有value被选定。如果一个value被选定,那么所有进程都应该能学习(learn)到这个被选定的value。对于一致性算法,安全性(safaty)要求如下:

  • 只有被提出的value才能被选定。
  • 只有一个value被选定,并且
  • 如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个。

我们不去精确地定义其活性(liveness)要求。我们的目标是保证最终有一个提出的value被选定。当一个value被选定后,进程最终也能学习到这个value。

Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定的value。

假设不同角色之间可以通过发送消息来进行通信,那么:

  • 每个角色以任意的速度执行,可能因出错而停止,也可能会重启。一个value被选定后,所有的角色可能失败然后重启,除非那些失败后重启的角色能记录某些信息,否则等他们重启后无法确定被选定的值。
  • 消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失。但是消息不会被损坏,即消息内容不会被篡改(拜占庭将军问题)。

推导过程

最简单的方案——只有一个Acceptor

假设只有一个Acceptor(可以有多个Proposer),只要Acceptor接受它收到的第一个提案,则该提案被选定,该提案里的value就是被选定的value。这样就保证只有一个value会被选定。 但是,如果这个唯一的Acceptor宕机了,那么整个系统就无法工作了! 因此,必须要有多个Acceptor只有一个Acceptor只有一个Acceptor

多个Acceptor

多个Acceptor的情况如下图。那么,如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢? 多个Acceptor多个Acceptor 下面开始寻找解决方案。 如果我们希望即使只有一个Proposer提出了一个value,该value也最终被选定。 那么,就得到下面的约束:

P1:一个Acceptor必须接受它收到的第一个提案。

但是,这又会引出另一个问题:如果每个Proposer分别提出不同的value,发给不同的Acceptor。根据P1,Acceptor分别接受自己收到的value,就导致不同的value被选定。出现了不一致。如下图: 幻灯片08.png幻灯片08.png 刚刚是因为『一个提案只要被一个Acceptor接受,则该提案的value就被选定了』才导致了出现上面不一致的问题。因此,我们需要加一个规定:

规定:一个提案被选定需要被半数以上的Acceptor接受

这个规定又暗示了:『一个Acceptor必须能够接受不止一个提案!』不然可能导致最终没有value被选定。比如上图的情况。v1、v2、v3都没有被选定,因为它们都只被一个Acceptor的接受。 最开始讲的『提案=value』已经不能满足需求了,于是重新设计提案,给每个提案加上一个提案编号,表示提案被提出的顺序。令『提案=提案编号+value』。 虽然允许多个提案被选定,但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致。 于是有了下面的约束:

P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value必须也是v。

一个提案只有被Acceptor接受才可能被选定,因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。

P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v。

只要满足了P2a,就能满足P2。 但是,考虑如下的情况:假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案,Acceptor25(半数以上)均接受了该提案,于是对于Acceptor25和Proposer2来讲,它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来(之前Acceptor1没有收到过任何提案),此时Proposer1向Acceptor1发送了[M2,V2]的提案(V2≠V1且M2>M1),对于Acceptor1来讲,这是它收到的第一个提案。根据P1(一个Acceptor必须接受它收到的第一个提案。),Acceptor1必须接受该提案!同时Acceptor1认为V2被选定。这就出现了两个问题:

  1. Acceptor1认为V2被选定,Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
  2. V1被选定了,但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2,且V2≠V1。这就跟P2a(如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v)矛盾了。

幻灯片10.png幻灯片10.png 所以我们要对P2a约束进行强化! P2a是对Acceptor接受的提案约束,但其实提案是Proposer提出来的,所有我们可以对Proposer提出的提案进行约束。得到P2b:

P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value必须也是v。

由P2b可以推出P2a进而推出P2。 那么,如何确保在某个value为v的提案被选定后,Proposer提出的编号更高的提案的value都是v呢? 只要满足P2c即可:

P2c:对于任意的N和V,如果提案[N, V]被提出,那么存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:

  • S中每个Acceptor都没有接受过编号小于N的提案。
  • S中Acceptor接受过的最大编号的提案的value为V。

Proposer生成提案

为了满足P2b,这里有个比较重要的思想:Proposer生成提案之前,应该先去『学习』已经被选定或者可能被选定的value,然后以该value作为自己提出的提案的value。如果没有value被选定,Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的。 于是我们得到了如下的提案生成算法

  1. Proposer选择一个新的提案编号N,然后向某个Acceptor集合(半数以上)发送请求,要求该集合中的每个Acceptor做出如下响应(response)。 (a) 向Proposer承诺保证不再接受任何编号小于N的提案。 (b) 如果Acceptor已经接受过提案,那么就向Proposer响应已经接受过的编号小于N的最大编号的提案。我们将该请求称为编号为NPrepare请求
  2. 如果Proposer收到了半数以上的Acceptor的响应,那么它就可以生成编号为N,Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案,那 么此时V就可以由Proposer自己选择。 生成提案后,Proposer将该提案发送给半数以上的Acceptor集合,并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。(注意:此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合)

Acceptor接受提案

Acceptor可以忽略任何请求(包括Prepare请求和Accept请求)而不用担心破坏算法的安全性。因此,我们这里要讨论的是什么时候Acceptor可以响应一个请求。 我们对Acceptor接受提案给出如下约束:

P1a:一个Acceptor只要尚未响应过任何编号大于NPrepare请求,那么他就可以接受这个编号为N的提案

如果Acceptor收到一个编号为N的Prepare请求,在此之前它已经响应过编号大于N的Prepare请求。根据P1a,该Acceptor不可能接受编号为N的提案。因此,该Acceptor可以忽略编号为N的Prepare请求。当然,也可以回复一个error,让Proposer尽早知道自己的提案不会被接受。 因此,一个Acceptor只需记住:1. 已接受的编号最大的提案 2. 已响应的请求的最大编号。 小优化小优化

Paxos算法描述

经过上面的推导,我们总结下Paxos算法的流程。 Paxos算法分为两个阶段。具体如下:

  • 阶段一:(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。(b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案
  • 阶段二:(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案Accept请求半数以上的Acceptor。注意:V就是收到的响应编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于NPrepare请求做出过响应,它就接受该提案

Paxos算法流程Paxos算法流程

Learner学习被选定的value

Learner学习(获取)被选定的value有如下三种方案: 幻灯片17.png幻灯片17.png

如何保证Paxos算法的活性

幻灯片18.png幻灯片18.png 通过选取主Proposer,就可以保证Paxos算法的活性。至此,我们得到一个既能保证安全性,又能保证活性分布式一致性算法——Paxos算法

参考资料

  • 论文《Paxos Made Simple》
  • 论文《The Part-Time Parliament》
  • 英文版维基百科的Paxos
  • 中文版维基百科的Paxos
  • 书籍《从Paxos到ZooKeeper》