加密散列元素树
Cryptographically hashing a tree of elements
我正在做一个项目，我有一个对象树。这个对象树可能非常大，并且可能会受到更多用户非常频繁的修改（例如添加或删除节点、更改节点的某些属性等）。现在，每次用户发布更新时，我都需要能够在用户修改后获得树的一些哈希值，以便用户可以使用他的 RSA 私钥对更新进行签名。因此，我显然需要哈希是加密安全的。但是，每次用户仅更改一个节点时，一遍又一遍地散列整个树的线性表示是不可行的。
我考虑过这个策略，但不确定是否会成功：
- 我给每个节点添加了一个新字段，即所有子节点的SHA256哈希值。
- 节点的散列现在是节点每个字段的散列，因此包括其子节点的散列。
现在，更新树应该很容易了：每次我更新一个节点时，我都会更改其父节点的哈希字段，然后是祖父节点等等，直到到达根节点，然后使用根节点的哈希值作为哈希值。这会将此操作的复杂度降低到 O(ln(N)) 而不是 O(N)。
但是，我知道相信自己对密码学的直觉是不安全的。那么这个过程安全吗？
我认为你的算法已经足够好了。
假设 SHA-256 是安全的（嗯，至少，它的名字是 "Secure Hash Algorithm"），可以通过对树的深度进行归纳来证明您的算法也是安全的。
这叫做hash tree or Merkle tree。这不是什么新鲜事，而且很安全。它通常用于并行化哈希，因为哈希方法本身在本质上是严格顺序的。
不要连接数据和散列，除非您明确包括数据的大小。最好只连接散列。
我正在做一个项目，我有一个对象树。这个对象树可能非常大，并且可能会受到更多用户非常频繁的修改（例如添加或删除节点、更改节点的某些属性等）。现在，每次用户发布更新时，我都需要能够在用户修改后获得树的一些哈希值，以便用户可以使用他的 RSA 私钥对更新进行签名。因此，我显然需要哈希是加密安全的。但是，每次用户仅更改一个节点时，一遍又一遍地散列整个树的线性表示是不可行的。
我考虑过这个策略，但不确定是否会成功：
- 我给每个节点添加了一个新字段，即所有子节点的SHA256哈希值。
- 节点的散列现在是节点每个字段的散列，因此包括其子节点的散列。
现在，更新树应该很容易了：每次我更新一个节点时，我都会更改其父节点的哈希字段，然后是祖父节点等等，直到到达根节点，然后使用根节点的哈希值作为哈希值。这会将此操作的复杂度降低到 O(ln(N)) 而不是 O(N)。
但是，我知道相信自己对密码学的直觉是不安全的。那么这个过程安全吗？
我认为你的算法已经足够好了。
假设 SHA-256 是安全的（嗯，至少，它的名字是 "Secure Hash Algorithm"），可以通过对树的深度进行归纳来证明您的算法也是安全的。
这叫做hash tree or Merkle tree。这不是什么新鲜事，而且很安全。它通常用于并行化哈希，因为哈希方法本身在本质上是严格顺序的。
不要连接数据和散列，除非您明确包括数据的大小。最好只连接散列。