前段时间，Gavin Wood要求我研究基于Substrate实施UTXO链的可能性，Substrate是目前最有前景的区块链技术底层架构，而且目前Polkadot是基于
前段时间，Gavin Wood要求我研究基于Substrate实施UTXO链的可能性，Substrate是目前最有前景的区块链技术底层架构，而且目前Polkadot是基于substrate进行开发的。
我们想知道Substrate的灵活性，而UTXO链似乎是进行测试的一个不错的选择，因为它与我们过去在实施Substrate时所考虑的完全不同。如果可行，则表明Substrate确实非常灵活且通用。我们可以更有信心，把Substrate应该到不同领域的区块链项目中。
与以太坊类似，Substrate保留一定数量的可用资金。从某种意义上讲，它类似于普通的银行系统，其中帐户余额用数字表示，并存储在数据库或计算机内存中的某个位置。
从历史上看，第一个成功的加密货币是比特币，它使用完全不同的方法。在比特币中，本身没有账户，余额也不是作为一个数字存储的。取而代之的是，可用资金是根据一组所谓的未用交易输出来定义的，简称为UTXO，这是一个非常简单的主意。
简而言之是UTXO
简而言之，UTXO非常类似于现金，或者更确切地说，是旅行支票。
当你用现金支付某人时，你通常会想到要支付的总价值，但是你用一组独特的、不可分割的单位(代币或钞票)来表示这个价值。例如如果Alice希望付给Bob$250美元，她可以给Bob2张价值$100美元的钞票和1张价值50美元的钞票，或五张面值$50的钞票，或总计为所需值的任何其他组合。
每一张钞票都是独一无二的。尽管有数百万张钞票具有相同的价值，但是每张钞票在物理上都是唯一的，并在其表面印有序列号。通常情况下，我们不太注意它，只是在支付东西的时候，把两张100美元的钞票视为相等，但这个数字对于银行控制资金流动和真伪检查是必不可少的。
因此每张钞票代表着具有预定和固定价值的独特且不可分割的资产，这些资产只能整体使用，即您不能将100美元的钞票撕成两张50美元的钞票。当然你可以要求某人找零，将价值分成较小的单位，但是您仍然需要花100美元的原始钞票。同样，购买咖啡时，您会花掉10美元的钞票，作为回报，您会得到咖啡和一些零钱。
UTXO的工作方式与此类似。要使用比特币付款，您的钱包中应该已经有一些未使用的资产。与法定货币一样，您可以结合使用多个UTXO以获得更大的价值。
与现金不同，每个UTXO都有自己的所有者。从这个意义上说，它类似于旅行支票，因为只有支票所有人才可以使用它。这是通过所有者签名增加单位来完成的。不同之处在于，旅行支票由所有者的手签名，而UTXO使用非对称加密，并且包含收件人而非发件人的公钥。而是钞票由政府印刷，UTXO由发起人创建。
目标
在我们的研究中，我们将尝试建立一个区块链模型，使用与比特币相同的原理将资金从一个所有者转移到另一个所有者。
当阅读文章时，请记住我们的主要目标是评估Substrate的灵活性，而不是比特币移植时使用端口的详细解释。在某些情况下，其实现几乎与Parity比特币的实现相同，而在其他情况下则不是。例如当前的实现不支持挖掘和coinbase事务;它只是重新分配在genesis块中初始化的“预先定义”UTXO集的值。
另外，请注意，所提供的实现还不能完全投入生产。它尚未经过正式验证，并且可能存在一些安全性或稳定性问题，因此，我不建议您在没有适当研究的情况下，将其用于任何关键基础架构。但是如果有人将这个原型制作成可行的解决方案，我会非常高兴。
话虽如此，让我们继续进行代码。
首先让我们谈谈Substrate如何允许您对其进行自定义。作为应用程序员，您应该提供一个runtime的运行逻辑，这些逻辑告诉Substrate如何处理链以及应采用的业务逻辑。所有这些都围绕着状态转换函数(简称STF)的概念。但现在我们只需说，每个区块链都可以表示为一个函数，接受当前状态和一个挂起的事务，然后生成另一个状态，反映在应用事务后所做的更改。
假设Alice和Bob都有10个代币，然后Alice向Bob发送了5个代币。应用此交易后，我们预计Alice现在将有5个代币，而Bob将有15个代币。如果Bob随后尝试向Claire支付20个代币，则该交易必须视为无效，因为根据最新的链条状态，Bob只有15个代币。
这正是runtime的意图-它定义了所有实体及其关系，验证了传入的事务并相应地更改了状态。
让我们从指定将用于定义UTXO链的业务逻辑的数据类型开始。首先是Transaction 类型。它表示要调度的单个UTXO事务：
/// Single transaction to be dispatched
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
#[derive(PartialEq, Eq, PartialOrd, Ord, Default, Clone, Encode, Decode, Hash)]
pub struct Transaction {
/// UTXOs to be used as inputs for current transaction
pub inputs: Vec
/// UTXOs to be created as a result of current transaction dispatch
pub outputs: Vec
}
这里没有什么特别的，只是一个简单的定义，即Transaction只是一堆输入和输出。如果您好奇，可以将其与Parity Bitcoin的版本进行比较，以了解相似之处。上面所有#[...]怪异都称为属性，它告诉Rust编译器为我们实现各种操作，例如比较运算符，哈希函数和序列化例程。您现在可以放心地忽略它们。
我留下了所有注释和属性，以表明即使将它们包括在内，代码仍会保持紧凑。我认为，即使与在成千上万行中做“同一件事”的Parity Bitcoin相比，这也是Substrate的可观成就。就像在用JavaScript为网络编写代码时一样，您并没有考虑过浏览器引擎或任何底层操作系统(包括操作系统)的复杂性。相反，您只是以高级形式制定业务逻辑，然后让系统完成其余工作。
好的，但是TransactionInput呢?
/// Single transaction input that refers to one UTXO
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
#[derive(PartialEq, Eq, PartialOrd, Ord, Default, Clone, Encode, Decode, Hash)]
pub struct TransactionInput {
/// Reference to an UTXO to be spent
pub parent_output: H256,
/// Proof that transaction owner is authorized to spend referred UTXO
pub signature: Signature,
}
TransactionInput汇总花费一个UTXO所需的所有数据。首先我们需要一种方法来引用一些现有的UTXO。最简单的方法是使用其哈希作为标识符。这是分布式系统世界中的一种普遍做法，并且只要哈希冲突的可能性可以忽略不计，它就可以很好地工作。为此我们使用256位Blake2。parent_output字段包含此类哈希。
如前所述，要使用UTXO，所有者必须使用与存储在该特定UTXO中的公钥匹配的秘密密钥对其进行签名。只要知道密钥的唯一人是所有者，这就是安全的。这种证明存储在签名字段中。
我们的实现与比特币之间的区别在于，我们直接通过其哈希值引用parent_output，而比特币则使用产生了UTXO的交易的哈希值以及一个索引来从交易输出列表中选择特定条目。原因是比特币是根据交易和区块定义的，而我们是根据业务逻辑和状态转换来定义的。在我们的例子中，Substrate事务只是辅助实体，它们促进了流程，并且大部分都超出了业务逻辑的范围。稍后再谈。
接下来是定义UTXO的TransactionOutput结构：
/// Single transaction output to create upon transaction dispatch
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Clone, Encode, Decode, Hash)]
pub struct TransactionOutput {
/// Value associated with this output
pub value: Value,
/// Public key associated with this output. In order to spend this output
/// owner must provide a proof by hashing whole `TransactionOutput` and
/// signing it with a corresponding private key.
pub pubkey: H256,
/// Unique (potentially random) value used to distinguish this
/// particular output from others addressed to the same public
/// key with the same value. Prevents potential replay attacks.
pub salt: u32,
}
value和pubkey字段的用途应该已经清楚。唯一值得解释的是salt。此字段提供了额外的熵，以使每个UTXO及其哈希真正唯一。想象一下这样的情况，我们有一个机器人每天向同一个收件人发送10个代币。为了简单起见，它可以使用相同的目的地地址，即接收者的公钥。因为value和pubkey字段都包含相同的数据，所以bot创建的所有UTXO看起来都完全相同，因此具有相同的散列。
没有salt，攻击者将能够记住所有者所用的第一个UTXO的签名，然后在所有者甚至没有注意到之前就花费所有后续的UTXO来窃取金钱，这称为重放攻击。同样还有另一种在源代码中尚未解决的重放攻击的可能性。
请注意，由于比特币实现依赖于交易哈希来精确定位UTXO，因此它不会遭受此问题的困扰，因此不需要salt。然而，这并不意味着比特币不可能进行重放攻击。这就是为什么为每一笔交易生成一个新的比特币地址是至关重要的。
状态
到目前为止，我们已经定义了表示内存中单个事务所需的所有数据结构。但是我们还需要告诉Substrate通过在一段时间内保留此信息，在状态数据库中存储什么以支持链的业务逻辑。
这是通过使用decl_storage定义模块存储来完成的!marco：
decl_storage! {
trait Store for Module
/// All valid unspent transaction outputs are stored in this map.
/// Initial set of UTXO is populated from the list stored in genesis.
UnspentOutputs build(|config: &GenesisConfig
config.initial_utxo
.iter()
.cloned()
.map(|u| (BlakeTwo256::hash_of(&u), u))
.collect::
}): map H256 => Option
/// Total leftover value to be redistributed among authorities.
/// It is accumulated during block execution and then drained
/// on block finalization.
LeftoverTotal: Value;
/// Outputs that are locked
LockedOutputs: map H256 => Option
}
add_extra_genesis {
config(initial_utxo): Vec
}
}
上面的代码实际上它仅定义了三件事：未使用的输出列表，当前剩余值量以及已锁定且除非解锁就无法使用的输出列表。除此之外，它还定义了在引导过程中如何使用一组初始的UTXO填充链。
需要要注意的是，状态存储与区块存储有很大不同。
区块存储是每个区块链节点的重要组成部分，用于存储该链中的区块。如今只有专用的存档节点将整个链存储在本地，而普通节点仅管理最近区块的临时子集。
另一方面，状态存储与业务逻辑有关。它包含反映业务实体及其关系的当前状态所需的所有数据。为了验证传入交易，您唯一需要知道的是所有受影响方的状态及其资金额。这就是为什么即使是轻度客户也能够验证交易的原因。
设计逻辑
当我们说Alice从Bob那里得到一些资金时，我们的意思是根据规则，Bob用来支付Alice的一组UTXO必须标记为已用(以防止Bob以后重复使用)。然后Bob为Alice创建的一组新UTXO现在必须被记住是有效的，这样Alice就可以在之后使用它们了。
这些规则是业务逻辑的本质，在验证和调度传入事务时需要考虑这些规则。
让我们看一下整个UTXO模块的入口点：
decl_module! {
pub struct Module
/// Dispatch a single transaction and update UTXO set accordingly
pub fn execute(origin, transaction: Transaction) -> Result {
ensure_inherent(origin)?;
let leftover = match Self::check_transaction(&transaction)? {
CheckInfo::MissingInputs(_) => return Err("all parent outputs must exist and be unspent"),
CheckInfo::Totals { input, output } => input - output
};
Self::update_storage(&transaction, leftover)?;
Self::deposit_event(Event::TransactionExecuted(transaction));
Ok(())
}
/// Handler called by the system on block finalization
fn on_finalise() {
let authorities: Vec<_> = Consensus::authorities().iter().map(|&a| a.into()).collect();
Self::spend_leftover(&authorities);
}
}
}
我们定义了两个函数：execute和on_finalize
execute函数是整个UTXO逻辑的关键。它接受单个事务，对其进行检查，如果有效，则通过更新存储应用该事务。最后它存储一个事件，表示一个事务刚刚被处理。
当刚刚形成一个充满交易的单个块时，将调用on_finalize事件处理程序。通过触发该事件处理程序，Substrate允许运行时根据需要采取一些措施。我们使用此处理程序从参与创建此块的验证程序之间的所有事务中重新分配合并的剩余价值，作为对其工作的奖励。
交易检查
为了验证传入事务，我们需要确保以下内容：
1. 输入和输出不为空。
2. 所有输入与现有的、未使用的和未锁定的输出匹配。
3. 每个输入只使用一次。
4. 每个输出只定义一次，并且有一个非零值。
5. 总产值不得超过总产值。
6. 新的输出不能与现有的冲突。
7. 输入和输出值之和不能溢出。
8. 提供的签名有效。
违反任何一项检查都可能导致连锁安全性问题，因此正确实施它们至关重要。幸运的是，逻辑非常简单明了：
pub fn check_transaction(transaction: &Transaction) -> CheckResult<'_> {
ensure!(!transaction.inputs.is_empty(), "no inputs");
ensure!(!transaction.outputs.is_empty(), "no outputs");
{
// Collecting inputs into a set where every element is unique.
// If two equal elements are inserted, only one will remain.
let input_set: BTreeMap<_, ()> = transaction
.inputs
.iter()
.map(|input| (input, ()))
.collect();
// Ensuring that the size of original collection and the set are equal.
// If they are not, then due to pigeonhole principle, some entries must
// have been maliciously mentioned several times.
ensure!(
input_set.len() == transaction.inputs.len(),
"each input must be used only once"
);
}
{
let output_set: BTreeMap<_, ()> = transaction
.outputs
.iter()
.map(|output| (output, ()))
.collect();
ensure!(
output_set.len() == transaction.outputs.len(),
"each output must be defined only once"
);
}
let mut total_input: Value = 0;
let mut missing_utxo = Vec::new();
for input in transaction.inputs.iter() {
// Fetch UTXO from the storage
if let Some(output) =
ensure!(!
// Check that we're authorized to spend this UTXO
ensure!(
ed25519_verify(
input.signature.as_fixed_bytes(),
input.parent_output.as_fixed_bytes(),
&output.pubkey
),
"signature must be valid"
);
// Add the value to the input total
total_input = total_input.checked_add(output.value).ok_or("input value overflow")?;
} else {
missing_utxo.push(&input.parent_output);
}
}
let mut total_output: Value = 0;
for output in transaction.outputs.iter() {
ensure!(output.value != 0, "output value must be nonzero");
let hash = BlakeTwo256::hash_of(output);
ensure!(!
total_output = total_output.checked_add(output.value).ok_or("output value overflow")?;
}
if missing_utxo.is_empty() {
ensure!(total_input >= total_output, "output value must not exceed input value");
Ok(CheckInfo::Totals { input: total_input, output: total_output })
} else {
Ok(CheckInfo::MissingInputs(missing_utxo))
}
}
您可能注意到，除了事务检查之外，此函数还收集一些信息。让我们看看它的定义：
/// Result of transaction verification
pub type CheckResult<'a> = rstd::result::Result
/// Information collected during transaction verification
pub enum CheckInfo<'a> {
/// Combined value of all inputs and outputs
Totals { input: Value, output: Value },
/// Some referred UTXOs were missing
MissingInputs(Vec<&'a H256>),
}
/// Representation of UTXO value
pub type Value = u128;
稍后将显示，我们使用总的 inputs和outputs来计算交易的优先级，并将剩余价值的一部分作为块式奖励在验证者之间重新分配。
但是如果交易未通过验证，谈论这些价值绝对没有任何意义。否则攻击者将能够通过淹没交易池并阻止正常交易被派发，从而故意制作具有最高优先级的交易并对链进行DoS。或者，它可能会“凭空产生”大量剩余价值以利用奖励系统。
通过将数据组织为Rust枚举，可以防止意外误用，因为只有在交易有效时值才可用。反之亦然，只有在发现事务引用状态数据库中不存在的某个UTXO时，才可以使用缺少输入的列表。这样一来，就不会滥用API，这有利于提高可读性和链安全性。
状态更新
如果交易经过验证并证明是正确的，那么我们要做的就是更改链状态以反映该交易所做的更改：
/// Update storage to reflect changes made by transaction
fn update_storage(transaction: &Transaction, leftover: Value) -> Result {
// Calculate new leftover total
let new_total =
.checked_add(leftover)
.ok_or("leftover overflow")?;
// Storing updated leftover value
// Remove all used UTXO since they are now spent
for input in &transaction.inputs {
}
// Add new UTXO to be used by future transactions
for output in &transaction.outputs {
let hash = BlakeTwo256::hash_of(output);
}
Ok(())
}
基本上，我们删除所有现在认为已用完的输入，并添加所有新输出以将其标记为可用。我们还将剩余的值累积在临时存储变量LeftoverTotal中，该变量将在区块确定期间使用。
阻止奖励
区块完成后，就该奖励创作该区块的节点了。这是通过重新分配从此区块中包括的所有事务中收集的剩余价值来完成的：
/// Redistribute combined leftover value evenly among authorities
fn spend_leftover(authorities: &[H256]) {
let leftover =
let share_value = leftover / authorities.len() as Value;
if share_value == 0 { return }
for authority in authorities {
let utxo = TransactionOutput {
pubkey: *authority,
value: share_value,
salt: System::block_number() as u32,
};
let hash = BlakeTwo256::hash_of(&utxo);
if !
runtime_io::print("leftover share sent to");
runtime_io::print(hash.as_fixed_bytes() as &[u8]);
} else {
runtime_io::print("leftover share wasted due to hash collision");
}
}
}
逻辑非常简单：我们接受一个权限列表，然后将剩余的总值除以权限数平均得出一个share_value。然后，我们为每个作者创建一个UTXO，并将其插入UnspentOutputs中。我们将当前区块号用作salt值，以防止上述潜在的重放攻击。
我们还通过将奖励UTXO插入UnspentOutputs来进行检查，以确保我们不会意外覆盖一些恰好具有相同哈希值的现有UTXO。这种情况在实践中极为罕见，但是不幸的是，如果有人因为常规奖励UTXO覆盖了他或她的UTXO而损失了数百万美元的UTXO，那将是不幸的。
乍一看，我们似乎是凭空创造价值，但仔细想想，人们可能会意识到，全局价值不会增加，因为交易所有者明确放弃了部分资金，以换取优先权。
最后，由于每个区块发起人都知道所有详细信息，例如区块编号，该特定时代使用的会话密钥，当然还有与该会话密钥匹配的秘密密钥，因此区块发起人将始终能够重构UTXO，计算其哈希值，即使没有将UTXO存储在任何地方也可以要求其奖励。
UTXO锁定
这就是与比特币不同的地方。
据我所知，比特币规范并没有规定哪些信息需要存储在磁盘上以及如何存储。唯一重要的是比特币协议本身，它是根据交易和区块来制定的。因此，每个节点必须建立自己的理解，在区块链历史的任何给定点上，哪些UTXO是有效的。
相反，根据定义，我们的UTXO实现具有所有参与节点都同意的全局状态数据库。众所周知，它用于存储UTXO状态和剩余的临时值。由于状态数据库是共识的一部分，因此我们可以在业务逻辑中依赖状态数据库的内容，并确保所有其他节点都将这样做。
但没有什么能阻止我们储存额外的东西。例如我们可以将现有UTXO的哈希映射映射到定义该UTXO的锁定状态的结构。如果UTXO被锁定，则不允许以通常的方式使用它：
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Debug))]
#[derive(Clone, Encode, Decode, Hash)]
pub enum LockStatus
// Referred UTXO is locked
Locked,
// Referred UTXO is locked until specified block
LockedUntil(T::BlockNumber),
}
decl_storage! {
trait Store for Module
...
/// Outputs that are locked
LockedOutputs: map H256 => Option
}
}
很像锁在保险箱里的现金：你可以最终使用它，但不早于你打开保险箱的时候。它是可用的，只是锁上了。
你可能在想，为什么一个人会需要这个?您会发现，在加密货币的世界中，有一种趋势是用贪婪程度更低，更有效的方法来代替旧的废物证明算法(proof-of-waste)。一种可能是将资金本身用作保证同peer行为正常的保证。
基本上，有人会说：“我发誓要遵守规则。这是我的钱。请把它锁在安全的地方。如果有人证明我的行为不当，那么我的钱就必须削减或在诚实的参与者之间分配。”当然，如果这样的人随后希望取回他或她的资金，则网络将检查是否没有恶意行为。在最后期限内提取，然后解锁资金。通常，锁定的资金越多，您获得的能力，投票权重或收入就越多。此类系统通常简称为权益证明或PoS。
只要网络中三分之二以上的节点没有恶意，并且按照协议操作，这就可以正常工作。除了执行常规任务外，这些节点还将支持PoS。
在类似以太坊的区块链中，在调度交易时，对可用资金的推论可能非常复杂：每个节点必须确保有足够的可用资金，尤其是因为可能存在与时间相关的复杂合约。
有趣的是，我们的UTXO实现以几行代码来完成。与以太坊式的链相反，类比特币的链的资金已经以自然的方式分配。我们可以轻松地锁定单个UTXO，并在满足某些解锁条件之前防止其被花费。
由于状态数据库不是其原始规范的一部分，因此在比特币中很难做到这一点。因此，很难在任何给定的时间点推断哪个UTXO被锁定，更不用说客户端兼容性问题了。
交易排序
在谈到链的业务逻辑时，我们提到Substrate为我们完成了所有肮脏的工作，例如处理块存储，执行网络交互和进行共识投票。但这并非总是如此。我们已经说过，我们的runtime原子性一次调度一个事务。因此如果该交易有效，则状态将相应更改。
但是如果两个从属事务在短时间内到达同一节点会发生什么呢?真实的网络是复杂且不可预测的。连接性问题和突然的拓扑更改可能会对传输的数据造成各种影响。值得注意的是，消息可能会丢失，延迟或重新排序。后一个事实对我们尤为重要。
想象一个情况，我们有两个事务，A和B，B依赖于A。在UTXO的情况下，这意味着B消耗了A创建的UTXO。如果B在A之前到达，我们可能会遇到这样的情况节点运行时将无法检查事务的有效性，因为它引用了看似不存在的UTXO。当然，我们确实知道它存在，但尚未交付，但是节点不知道。本质上，它有两个选择：
1. 只需将交易B视为无效即可。如果原始发送人重新广播该交易，它仍将有机会被应用，但不会早于A被调度。此解决方案可能有效，但它是肮脏且无效的。此外，一些严重的网络问题可能导致无法分配B的情况，从而使整个系统无用。我们可以做得更好。
2. 将事务B的分派推迟到有意义的时候。在我们的情况下，我们需要以某种方式等待A的发送。
第二种选择似乎更有趣，但是在实践中我们该如何做呢?通过其本身的设计，Substrate对运行时内部或链的业务逻辑一无所知。实际上，从其角度来看，Substrate就像不透明的字节数组一样“看到”我们的交易。
这里的解决方案是“解释” Substrate如何处理我们的交易以及如何正确排序它们。这是通过使用事务池向运行时公开的专用TaggedTransactionQueue API完成的。
在Substrate中，每个事务都与两组标签相关联：require和Provides。标签只是代表某个唯一值的任意字节向量。第一组描述此事务需要哪些标签，而第二组定义此事务提供的标签。
在上述情况下，我们需要通过声明A提供一些标签而B消耗与其要求相同的标签来将事务A和B链接在一起。为了简单起见，我们可以使用UTXO哈希作为标签。
通过遍历事务并查询其标记，事务池以一种顺序组织它们，以使每个事务都可以满足其要求。那些熟悉计算机科学的人可能会意识到这类似于拓扑顺序。
有时两个事务不相互依赖，但又依赖于第三次事务。例如我们可能有交易A产生两个输出，交易B和C分别花费这两个输出。这将导致B和C都依赖于A。拓扑排序状态规定必须在B和C之前调度A，但是未定义分发B和C的顺序。在这种情况下，事务池使用其他条件来确定事务的优先级。
经典解决方案是将剩余值的数量用作优先级。交易所有者有意留给当局的资金越多，交易优先级就越高，双赢。（链三丰）
让我们看看它如何在我们的链中实现：
impl runtime_api::TaggedTransactionQueue
fn validate_transaction(tx:
// A bunch of imports
use srml_support::IsSubType;
use runtime_primitives::{
traits::Hash,
transaction_validity::{TransactionLongevity, TransactionPriority, TransactionValidity},
};
// Extrinsics representing UTXO transaction need some special handling
if let Some(&utxo::Call::execute(ref transaction)) = IsSubType::
// List of tags to require
let requires;
// Transaction priority to assign
let priority;
match
// Verification failed
Err(e) => {
runtime_io::print(e);
return TransactionValidity::Invalid(1);
}
// Transaction was fully verified and is valid
Ok(utxo::CheckInfo::Totals { input, output }) => {
