Scrypto

Scrypto 是一个开源的加密工具包，旨在使开发者在应用程序中使用加密更加容易和安全。

它从 Scorex 中提取而来，Scorex 是一个开源的模块化区块链和加密货币框架。

公有领域。

scorex_crypto_avltree 是 scrypto 包中 AVL 树的 Rust 版本。

认证数据结构

Scrypto 支持带有批处理压缩支持和保证验证器效率的两方认证 AVL+ 树，如 http://eprint.iacr.org/2016/994 中所述。实现可以在 scorex.crypto.authds.avltree.batch 包中找到。

总体方法是：证明者有一个 (键，值) 对的数据结构，可以使用 performOneOperation 方法对其执行操作。操作（见 scorex.crypto.authds.avltree.batch.Operation）要么是查找，要么是修改。我们提供了示例修改（如插入、删除以及从给定键的值中进行增加/减少），但使用此代码的用户可以定义自己的（如允许负值的减法，与我们的减法不同）。可以定义修改在某些条件下失败（例如，删除一个不存在的键，或者减法导致负值），在这种情况下，树不会被修改。如果操作成功，它将返回操作执行前的与键关联的值。证明者可以通过 digest 方法计算数据结构当前状态的摘要。在任何时候，证明者都可以使用 generateProof，这将生成一个覆盖从上次 generateProof 以来（除了失败的那些）的操作批次的证明。

校验器是由先于最新一批操作的消息摘要以及最新一批操作的证明构建的。校验器还可以提供可选参数，以最大操作数（以及其中最多有多少个是删除操作）来保证在恶意证明的情况下校验器运行时间的界限，从而减轻拒绝服务攻击。一旦构建完成，校验器可以回放相同的操作序列来计算新的摘要，并确保操作不会失败且它们的返回值是正确的。请注意，校验器不保证操作序列与证明者执行的操作序列相同——假设证明者和校验器就操作序列达成一致（当证明者和校验器就操作序列达成一致时，两方认证数据结构非常有用）。然而，如果操作序列之后的校验器摘要与证明者的摘要匹配，那么校验器可以确保数据结构的状态相同，不管导致此状态的操作序列是什么。

我们还为证明者提供了unauthenticatedLookup，以便允许证明者在不影响证明的情况下查找数据结构中的值。

以下是生成证明和检查证明的代码示例。在此示例中，我们演示了两批操作，从空树开始。在第一批操作中，证明者将三个值插入树中；在第二批操作中，证明者更改第一个值，试图从第二个值中减去太多（这将失败，因为我们的UpDateLongBy操作设计为在负值时失败），查找第三个值，并尝试删除一个不存在的值（这也失败）。为了简化，我们使用1字节键；在实际部署中，键会更长。

• 首先，我们创建一个证明者并从它那里获取一个初始摘要（在实际应用中，此值是一个公共常量，因为任何人，包括校验器，都可以通过使用相同的两行代码来计算它）

  use scorex_crypto_avltree::authenticated_tree_ops::*;
  use scorex_crypto_avltree::batch_node::*;
  use scorex_crypto_avltree::operation::*;
  use scorex_crypto_avltree::batch_avl_verifier::BatchAVLVerifier;
  use scorex_crypto_avltree::persistent_batch_avl_prover::*;

  let prover = BatchAVLProver::new(AVLTree::new(dummy_resolver, key_length=1, value_length=Some(8)));
  let initial_digest = prover.digest();

• 其次，我们创建第一批树修改，插入键1、2和3，值分别为10、20和30。我们使用com.google.common.primitives.Longs.toByteArray从长整型中获取8字节值。

  let key1 = [1u8; 1];
  let key2 = [2u8; 1];
  let key3 = [3u8; 1];
  let op1 = Operation::Insert(KeyValue {key: key1.clone(), value: 10u64.to_be_bytes()};
  let op2 = Operation::Insert(KeyValue {key: key2.clone(), value: 20u64.to_be_bytes()};
  let op3 = Operation::Insert(KeyValue {key: key3.clone(), value: 30u64.to_be_bytes()};

• 证明者将三个修改应用于空树，获得第一批证明，并宣布下一个摘要digest1。

  prover.perform_one_operation(&op1).unwrap();
  prover.perform_one_operation(&op2).unwrap();
  prover.perform_one_operation(&op3).unwrap();
  let proof1 = prover.generate_proof();
  let digest1 = prover.digest();

• 证明只是一个字节数组，因此您可以立即通过一条线发送它或将它保存到磁盘上。

• 接下来，证明者试图执行五个更多修改：将第一个值更改为50，从第二个值中减去40（这将失败，因为我们的UpDateLongBy操作设计为在负值时失败），查找第三个值，删除键5（这将也失败，因为键5不存在），并删除第三个值。在四个操作之后，证明者获得第二个证明，并宣布新的摘要digest2。

  let op4 = Operation::Update(KeyValue {key: key1.clone(), value: 50u64.to_be_bytes()});
  let op5 = Operation::UpdateLongBy(KeyDelta {key: key2.clone(), delta: -40});
  let op6 = Operation::Lookup(key3.clone());
  let op7 = Operation::Remove([5u8; 1]);
  let op8 = Operation::Remove(key3.clone());
  prover.perform_one_operation(&op4).unwrap();
  // Here we can, for example, perform prover.unauthenticated_lookup(&key1) to get 50
  // without affecting the proof or anything else
  prover.perform_one_operation(&op5).unwrap();
  prover.perform_one_operation(&op6).unwrap();
  prover.perform_one_operation(&op7).unwrap();
  prover.perform_one_operation(&op8).unwrap();
  let proof2 = prover.generate_proof(); // Proof only for op4 and op6
  let digest2 = prover.digest();

• 我们现在验证这些证明。对于每一批，我们首先使用先于批次的摘要和批次的证明来构建一个校验器；我们还提供批次中操作的数量上限以及这些操作中删除操作的数量上限。请注意，操作的数量可以是None，在这种情况下没有保证的运行时间界限；此外，删除操作的数量可以是None，在这种情况下，如果提供了删除操作数量的良好上限，保证的运行时间界限不会像可以的那样小。

• 一旦构建了特定批次的验证器，我们就依次执行验证者相同的操作（但不包括那些对验证者失败的）。如果在任何一点（构建时间或操作过程中）验证失败，验证器的摘要将从该点开始等于 None，并且没有进一步的验证器操作会改变摘要。否则，验证器的新摘要是对验证器修改后的树的正确摘要。此外，如果验证器执行了与验证者相同的修改，那么验证器和验证者的摘要将匹配。

  let verifier1 = BatchAVLVerifier::new(
        &initial_digest, &proof1,
		AVLTree::new(dummy_resolver, key_length=1, value_length=Some(8)),
		Some(2),
		Some(0));
  verifier1.perform_one_operation(&op1).unwrap();
  verifier1.perform_one_operation(&op2).unwrap();
  verifier1.perform_one_operation(&op3).unwrap();
  match verifier1.digest() {
    Some(d1) if d1 == digest1 => {
      // If digest1 from the prover is already trusted, then verification of the second batch can simply start here
      let verifier2 = BatchAVLVerifier::new(
        &d1, &proof2,
		AVLTree::new(dummy_resolver, key_length=1, value_length=Some(8)),
		Some(3),
		Some(1));

      verifier2.perform_one_operation(&op4).unwrap();
      verifier2.perform_one_operation(&op6).unwrap();
      verifier2.perform_one_operation(&op8).unwrap();
	  match verifier2.digest() {
        Some(d2) if d2 == digest2 => println!("first and second digest value and proofs are valid"),
		_ => println!("second proof or announced digest NOT valid"),
      }
	}
    case _ =>
      println!("first proof or announced digest NOT valid")
  }

测试

从包含框架的文件夹中运行 cargo test 启动测试。

许可

代码处于公共领域 CC0 许可之下，这意味着你可以用它做任何事情。完整的许可文本在 COPYING 文件 中。

贡献

您的贡献总是受欢迎的！请提交一个拉取请求或创建一个问题，以添加新的加密原语或更好的实现。