Domain separators for key/value hashes in LeafOp
- Dominant language
- Rust
- Stars
- 129
- Forks
- 83
- PR merge metrics
- No merged PRs in 30d
Description
Hi, we're working on adding ICS23 support for a variant of the [Jellyfish Merkle Tree](https://rustdoc.penumbra.zone/main/jmt/) from Diem, modified slightly to be a generic, byte-oriented k/v store rather than a strongly typed object store (as in the original Diem code).
One issue we're running into is expressing the leaf node hashing using a `LeafOp`. Our leaf nodes are hashed as
```
SHA256( b"JMT::LeafNode" || SHA256(b"JMT::Key" || key) || SHA256(b"JMT::Value" || value) )
```
i.e., both key and value bytes are prehashed, with different domain separators.
We could *almost* express this as a `LeafOp` with `hash = SHA256`, `prefix = b"JMT::LeafNode"`, `prehash_key, prehash_value = SHA256`, `length = NO_PREFIX`, but that will compute
```
SHA256( b"JMT::LeafNode" || SHA256(key) || SHA256(value) )
```
without the domain separators on the key/value pairs.
It seems like there are two possible resolutions:
1. Remove the domain separators from the key and value hashes (this is less preferred, since domain separators are a good practice);
2. Change the `LeafOp` proto to add new prefix fields:
```proto
message LeafOp {
HashOp hash = 1;
HashOp prehash_key = 2;
HashOp prehash_value = 3;
LengthOp length = 4;
bytes prefix = 5;
// NEW: fixed bytes that may optionally be included as a domain separator for prehash_key
bytes prehash_key_prefix = 6;
// NEW: fixed bytes that may optionally be included as a domain separator for prehash_value
bytes prehash_value_prefix = 7;
}
```
The computation would then become
```
hkey = prehashKey(prehash_key_prefix || key)
hvalue = prehashValue(prehash_value_prefix || value)
output = hash(prefix || length(hkey) || hkey || length(hvalue) || hvalue)
```
This change would be backwards-compatible, because protos allow missing fields, and if the `prehash_*_prefix` fields are missing, the behavior is exactly the same as the current implementation.
Does (2) seem sensible, or is there something we're missing?
Contributor guide
No contributing guide indexed for this repository
Research direction
Begin at the LeafOp definition and the prehash_key/prehash_value behavior described in the issue; no file or test is named. Confirm with maintainers whether the proposed proto fields are wanted before implementation, with completion defined as an accepted resolution and any required compatibility coverage.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100