nearcore
nearcore copied to clipboard
Published
20 hours ago •
near
near
Provide state proofs from contract state
Ref to comment explaining the need for this: https://github.com/near/nearcore/issues/2076#issuecomment-1157406269
Fixes: #2076
@mina86 from your comments, the only part I'm still uncertain is the return of get_proof
https://github.com/near/nearcore/pull/7205#discussion_r926581021
None would mean -> Key wasn't find
vec![]-> ?
Empty vector is an invalid proof. The function would not return it.
I don't have strong feelings here. If it is more ergonomic for the function to return Option<Vec<>> then that is fine with me.
Can we use RawTrieNodeWithSize structure to avoid code duplication? It feels it satisfies the same needs as TrieProofLeaf/Extension/Branch. If we modify trie impl at some point, it will be enough to change less structures. For example, in the future we may introduce maximal tree depth field near memory_usage.
Due to the same reason, I think get_proof and lookup can be merged in some way. What do others think?
Can we use RawTrieNodeWithSize structure to avoid code duplication?
There’s one difference which I don’t know if I understand fully. The Branch variant has child index in the proof. This means that the proof can be verified without knowing the key. But I don’t think this is actually needed? And if we know the key when verifying proof, we don’t need that index and we’re just storing the exact same nodes.
This does bring the format of the proof again. If proof is just RawTrieNodeWithSize than we maybe we should go ahead and use binary encoding RawTrieNodeWithSize uses and base64-encode it. (Though even then, we should change the type to Vec<Vec
@blasrodri - thanks a lot for the PR.
yes, I think that we could reuse RawTrieNodeWithSize.
For the format - I'm leaning towards BorshEncoding + base64. Yes, as @mina86 mentioned - the JSON readers would have to parse & decode -- but at the same time, if they really want to verify the proof, they have to do even more work (as they have to check that these hashes match).
There’s one difference which I don’t know if I understand fully. The Branch variant has child index in the proof. This means that the proof can be verified without knowing the key. But I don’t think this is actually needed? And if we know the key when verifying proof, we don’t need that index and we’re just storing the exact same nodes.
Yeah, it is a good point. Index is not needed, and it can be retrieved using the key.
Once we expose state proofs to users, it will be hard to refactor their structure without breaking external logic relying on them, and reusing RawTrieNodeWithSize should make it simpler.
I'm leaning towards BorshEncoding + base64.
I’m still tempted to switch from String to Vec
but at the same time, if they really want to verify the proof, they have to do even more work (as they have to check that these hashes match).
Yes, I just realised this as well.
TrieProofPath
Would this mean that ViewRuntimeAdapter::view_state would need to have a parameter that flags whether the proof should or not be included?
Can certainly change Vec<String> to Vec<Vec<u8>> encoded in base64.
I'm uncertain on how to proceed with regards to merging the logic of get_proof and lookup plus re-using RawTrieNodeWithSize. Haven't been able to figure out that part. Any help there would be big. @mm-near @Longarithm
Would this mean that ViewRuntimeAdapter::view_state would need to have a parameter that flags whether the proof should or not be included?
Yes. And also QueryRequest::ViewState and possibly some other methods in between.
Can certainly change
Vec<String>toVec<Vec<u8>>encoded in base64.
Sounds good though now that I look at it we don’t have vector_base64_format serialiser (see core/primitives-core/src/serialize.rs). (We’re not using wrappers or serde_with crate for serialisation at the moment). You’re welcome to add it but perhaps for now let’s keep the proof as Vec<String> after all. We can change it later and for now this is probably distracting.
As for changing it to Option<Vec<String>> I’m not really sure. While we don’t need to care about borsh, if we start sending null as proof that might break existing users. I’d still be tempted to do it though I dunno how widely used is the view state RPC.
I'm uncertain on how to proceed with regards to merging the logic of get_proof and lookup plus re-using RawTrieNodeWithSize. Haven't been able to figure out that part. Any help there would be big.
Since we want to proof of the prefix key rather than keys we’re looking up, I think we actually want to add code for getting the proof into TrieIterator instead. After we seek the prefix, iterator has crumbs indicating how to get to the node and we just need to follow those.
Something like:
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
index 12ab35adb..6fa83b994 100644
--- a/core/store/src/trie/iterator.rs
+++ b/core/store/src/trie/iterator.rs
@@ -69,6 +69,21 @@ impl<'a> TrieIterator<'a> {
self.seek_nibble_slice(NibbleSlice::new(key.as_ref())).map(drop)
}
+ pub fn trail_proof(&self) -> Vec<String> {
+ let mut buffer = Vec::new();
+ self.trail
+ .iter()
+ .filter_map(move |crumb| {
+ buffer.clear();
+ if crumb.node.encode_into(&mut buffer) {
+ Some(near_primitives::serialize::to_base64(&buffer))
+ } else {
+ None
+ }
+ })
+ .collect()
+ }
+
/// Returns the hash of the last node
pub(crate) fn seek_nibble_slice(
&mut self,
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
index a087c030c..f9513b215 100644
--- a/core/store/src/trie/mod.rs
+++ b/core/store/src/trie/mod.rs
@@ -82,6 +82,15 @@ enum ValueHandle {
HashAndSize(u32, CryptoHash),
}
+impl ValueHandle {
+ fn unwrap_length_and_hash(&self) -> (u32, &CryptoHash) {
+ match self {
+ Self::HashAndSize(length, hash) => (*length, hash),
+ Self::InMemory(_handle) => todo!(),
+ }
+ }
+}
+
#[derive(Clone, Hash, Debug)]
enum TrieNode {
/// Null trie node. Could be an empty root or an empty branch entry.
@@ -116,6 +125,31 @@ impl TrieNodeWithSize {
fn empty() -> TrieNodeWithSize {
TrieNodeWithSize { node: TrieNode::Empty, memory_usage: 0 }
}
+
+ pub fn encode_into(&self, out: &mut Vec<u8>) -> bool {
+ let node = match &self.node {
+ TrieNode::Empty => return false,
+ TrieNode::Leaf(key, handle) => {
+ let (length, hash) = handle.unwrap_length_and_hash();
+ RawTrieNode::Leaf(key.clone(), length, hash.clone())
+ }
+ TrieNode::Branch(children, value) => {
+ let mut new_children: [Option<CryptoHash>; 16] = [None; 16];
+ for (i, child) in children.iter().enumerate() {
+ new_children[i] = child.as_ref().map(|handle| handle.unwrap_hash().clone());
+ }
+ let value = value.as_ref().map(|handle| {
+ let (length, hash) = handle.unwrap_length_and_hash();
+ (length, hash.clone())
+ });
+ RawTrieNode::Branch(new_children, value)
+ }
+ TrieNode::Extension(key, node) => RawTrieNode::Extension(key.clone(), node.unwrap_hash().clone()),
+ };
+ let raw = RawTrieNodeWithSize { node, memory_usage: self.memory_usage };
+ raw.encode_into(out).unwrap();
+ true
+ }
}
impl TrieNode {
diff --git a/runtime/runtime/src/state_viewer/mod.rs b/runtime/runtime/src/state_viewer/mod.rs
index 013142885..32c378e8c 100644
--- a/runtime/runtime/src/state_viewer/mod.rs
+++ b/runtime/runtime/src/state_viewer/mod.rs
@@ -145,6 +145,7 @@ impl TrieViewer {
let acc_sep_len = query.len() - prefix.len();
let mut iter = state_update.trie.iter(&state_update.get_root())?;
iter.seek(&query)?;
+ let proof = Some(iter.trail_proof());
for item in iter {
let (key, value) = item?;
if !key.starts_with(query.as_ref()) {
@@ -157,10 +158,9 @@ impl TrieViewer {
});
}
// TODO(2076): Add proofs for the storage items.
- let trie = state_update.trie();
- let root = state_update.get_root();
-
- let proof = trie.get_proof(&root, &query)?;
+ // let trie = state_update.trie();
+ // let root = state_update.get_root();
+ //let proof = trie.get_proof(&root, &query)?;
Ok(ViewStateResult { values, proof })
}
OK, sorry, I keep just throwing ideas some of which may make no sense, but it just ocured to me that maybe we’re thinking about it wrong? Rather than adding proofs to view state, maybe we should have view trie call which would return all the nodes? So have a proof from state root to prefix and then just straight up all the nodes. If we’re assuming client is able to decode the nodes, they can also extract the values.
A few updates on this PR (thanks @vmarkushin)
- Reuse
RawTrieNodeWithSizein favor ofTrieProofItem - Introduce non-membership proofs. This means that we can request proof that a key value is not present in the trie. Not only that a key value is present.
- Fixed some bugs in the proof verification function
- Added more tests both on membership and non-membership proofs.
I'd like to know what you think about this and to define a final way of integrating into the RPC in a clean way without breaking compatiblity.
@mina86 Went through your comments. I'm not sure how to re-use the iterator logic with the current code. If you still want to go that way, I'd ask you to help me on that.
That’s this comment:
Since we want to proof of the prefix key rather than keys we’re looking up, I think we actually want to add code for getting the proof into TrieIterator instead. After we seek the prefix, iterator has crumbs indicating how to get to the node and we just need to follow those.
Something like:
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
index 12ab35adb..6fa83b994 100644
--- a/core/store/src/trie/iterator.rs
+++ b/core/store/src/trie/iterator.rs
@@ -69,6 +69,21 @@ impl<'a> TrieIterator<'a> {
self.seek_nibble_slice(NibbleSlice::new(key.as_ref())).map(drop)
}
+ pub fn trail_proof(&self) -> Vec<String> {
+ let mut buffer = Vec::new();
+ self.trail
+ .iter()
+ .filter_map(move |crumb| {
+ buffer.clear();
+ if crumb.node.encode_into(&mut buffer) {
+ Some(near_primitives::serialize::to_base64(&buffer))
+ } else {
+ None
+ }
+ })
+ .collect()
+ }
+
/// Returns the hash of the last node
pub(crate) fn seek_nibble_slice(
&mut self,
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
index a087c030c..f9513b215 100644
--- a/core/store/src/trie/mod.rs
+++ b/core/store/src/trie/mod.rs
@@ -82,6 +82,15 @@ enum ValueHandle {
HashAndSize(u32, CryptoHash),
}
+impl ValueHandle {
+ fn unwrap_length_and_hash(&self) -> (u32, &CryptoHash) {
+ match self {
+ Self::HashAndSize(length, hash) => (*length, hash),
+ Self::InMemory(_handle) => todo!(),
+ }
+ }
+}
+
#[derive(Clone, Hash, Debug)]
enum TrieNode {
/// Null trie node. Could be an empty root or an empty branch entry.
@@ -116,6 +125,31 @@ impl TrieNodeWithSize {
fn empty() -> TrieNodeWithSize {
TrieNodeWithSize { node: TrieNode::Empty, memory_usage: 0 }
}
+
+ pub fn encode_into(&self, out: &mut Vec<u8>) -> bool {
+ let node = match &self.node {
+ TrieNode::Empty => return false,
+ TrieNode::Leaf(key, handle) => {
+ let (length, hash) = handle.unwrap_length_and_hash();
+ RawTrieNode::Leaf(key.clone(), length, hash.clone())
+ }
+ TrieNode::Branch(children, value) => {
+ let mut new_children: [Option<CryptoHash>; 16] = [None; 16];
+ for (i, child) in children.iter().enumerate() {
+ new_children[i] = child.as_ref().map(|handle| handle.unwrap_hash().clone());
+ }
+ let value = value.as_ref().map(|handle| {
+ let (length, hash) = handle.unwrap_length_and_hash();
+ (length, hash.clone())
+ });
+ RawTrieNode::Branch(new_children, value)
+ }
+ TrieNode::Extension(key, node) => RawTrieNode::Extension(key.clone(), node.unwrap_hash().clone()),
+ };
+ let raw = RawTrieNodeWithSize { node, memory_usage: self.memory_usage };
+ raw.encode_into(out).unwrap();
+ true
+ }
}
impl TrieNode {
diff --git a/runtime/runtime/src/state_viewer/mod.rs b/runtime/runtime/src/state_viewer/mod.rs
index 013142885..32c378e8c 100644
--- a/runtime/runtime/src/state_viewer/mod.rs
+++ b/runtime/runtime/src/state_viewer/mod.rs
@@ -145,6 +145,7 @@ impl TrieViewer {
let acc_sep_len = query.len() - prefix.len();
let mut iter = state_update.trie.iter(&state_update.get_root())?;
iter.seek(&query)?;
+ let proof = Some(iter.trail_proof());
for item in iter {
let (key, value) = item?;
if !key.starts_with(query.as_ref()) {
@@ -157,10 +158,9 @@ impl TrieViewer {
});
}
// TODO(2076): Add proofs for the storage items.
- let trie = state_update.trie();
- let root = state_update.get_root();
-
- let proof = trie.get_proof(&root, &query)?;
+ // let trie = state_update.trie();
+ // let root = state_update.get_root();
+ //let proof = trie.get_proof(&root, &query)?;
Ok(ViewStateResult { values, proof })
}
This might not be the best approach. It could be better to add raw_bytes: Arc<[u8]> to Crumb and as the iterator gets into the nodes it would store the raw bytes making it easy to retrieve them later. So something along the lines of:
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
index 0582ece59..f08c959b5 100644
--- a/core/store/src/trie/iterator.rs
+++ b/core/store/src/trie/iterator.rs
@@ -8,6 +8,7 @@ use crate::{StorageError, Trie};
struct Crumb {
node: TrieNodeWithSize,
status: CrumbStatus,
+ raw_bytes: Option<Arc<[u8]>>,
}
#[derive(Clone, Eq, PartialEq, Debug)]
@@ -57,8 +58,7 @@ impl<'a> TrieIterator<'a> {
trail: Vec::with_capacity(8),
key_nibbles: Vec::with_capacity(64),
};
- let node = trie.retrieve_node(&trie.root)?;
- r.descend_into_node(node);
+ r.descend_into_node(&trie.root)?
Ok(r)
}
@@ -76,8 +76,7 @@ impl<'a> TrieIterator<'a> {
self.key_nibbles.clear();
let mut hash = self.trie.root;
loop {
- let node = self.trie.retrieve_node(&hash)?;
- self.trail.push(Crumb { status: CrumbStatus::Entering, node });
+ let node = self.descend_into_node(&hash);
let Crumb { status, node } = self.trail.last_mut().unwrap();
match &node.node {
TrieNode::Empty => break,
@@ -124,8 +123,10 @@ impl<'a> TrieIterator<'a> {
Ok(hash)
}
- fn descend_into_node(&mut self, node: TrieNodeWithSize) {
- self.trail.push(Crumb { status: CrumbStatus::Entering, node });
+ fn descend_into_node(&mut self, hash: &CryptoHash) -> Result<TrieNodeWithSize, StorageError> {
+ let (raw_bytes, node) = self.trie.retrieve_node(hash)?;
+ self.trail.push(Crumb { status: CrumbStatus::Entering, raw_bytes, node });
+ Ok(node)
}
fn key(&self) -> Vec<u8> {
@@ -277,8 +278,7 @@ impl<'a> TrieIterator<'a> {
if self.key_nibbles[prefix..] >= path_end[prefix..] {
break;
}
- let node = self.trie.retrieve_node(&hash)?;
- self.descend_into_node(node);
+ self.descend_into_node(&hash)?;
nodes_list.push(TrieTraversalItem { hash, key: None });
}
IterStep::Continue => {}
@@ -312,9 +312,9 @@ impl<'a> Iterator for TrieIterator<'a> {
IterStep::PopTrail => {
self.trail.pop();
}
- IterStep::Descend(hash) => match self.trie.retrieve_node(&hash) {
- Ok(node) => self.descend_into_node(node),
- Err(e) => return Some(Err(e)),
+ IterStep::Descend(hash) => match self.descend_into_node(&hash) {
+ Ok(_) => (),
+ Err(err) => return Some(Err(err)),
},
IterStep::Continue => {}
IterStep::Value(hash) => {
@@ -457,10 +457,7 @@ mod tests {
IterStep::PopTrail => {
iterator.trail.pop();
}
- IterStep::Descend(hash) => match iterator.trie.retrieve_node(&hash) {
- Ok(node) => iterator.descend_into_node(node),
- Err(e) => panic!("Unexpected error: {}", e),
- },
+ IterStep::Descend(hash) => iterator.descend_into_node(&hash).unwrap(),
_ => {}
}
}
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
index 0912b2f50..ccf3a5f26 100644
--- a/core/store/src/trie/mod.rs
+++ b/core/store/src/trie/mod.rs
@@ -615,10 +615,10 @@ impl Trie {
}
}
- fn retrieve_node(&self, hash: &CryptoHash) -> Result<TrieNodeWithSize, StorageError> {
+ fn retrieve_node(&self, hash: &CryptoHash) -> Result<(Option<std::sync::Arc<[u8]>>, TrieNodeWithSize), StorageError> {
match self.retrieve_raw_node(hash)? {
- None => Ok(TrieNodeWithSize::empty()),
- Some((_bytes, node)) => Ok(TrieNodeWithSize::from_raw(node)),
+ None => Ok((None, TrieNodeWithSize::empty())),
+ Some((bytes, node)) => Ok((bytes, TrieNodeWithSize::from_raw(node))),
}
And then getting the proof will be just fetching raw_bytes from the trail.
@mina86 defeated We tried, and tried... but honestly cannot figure this out.
Our latest state of mind (a dump)
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
index 030608390..4fa39876a 100644
--- a/core/store/src/trie/iterator.rs
+++ b/core/store/src/trie/iterator.rs
@@ -68,8 +68,10 @@ impl<'a> TrieIterator<'a> {
}
/// Position the iterator on the first element with key => `key`.
- pub fn seek<K: AsRef<[u8]>>(&mut self, key: K) -> Result<(), StorageError> {
- self.seek_nibble_slice(NibbleSlice::new(key.as_ref())).map(drop)
+ pub fn seek<'b, K: AsRef<[u8]>>(&mut self, key: K) -> Result<bool, StorageError> {
+ let mut key_nibble = NibbleSlice::new(key.as_ref());
+ self.seek_nibble_slice(&mut key_nibble)?;
+ Ok(key_nibble.is_empty())
}
/*
@@ -105,52 +107,37 @@ impl<'a> TrieIterator<'a> {
};
*/
- pub fn trail_proof(&self) -> (ProofPresence, Vec<String>) {
- let mut value_presence = None;
- let key = self.key();
- let mut key = NibbleSlice::new(&key);
- let proof = self
- .trail
+ pub fn trail_proof(&self) -> Vec<String> {
+ self.trail
.iter()
.filter_map(|crumb| {
- match &crumb.node.node {
- TrieNode::Empty => {
- todo!();
- }
- TrieNode::Leaf(existing_key, _) => {
- let found = NibbleSlice::from_encoded(&existing_key).0 == key;
- if value_presence.is_none() {
- value_presence = Some(ProofPresence::from_found(found));
- }
- }
- TrieNode::Branch(_, value) => {
- if key.is_empty() && value.is_some() && value_presence.is_none() {
- value_presence = Some(ProofPresence::Present);
- }
- }
- TrieNode::Extension(existing_key, _) => {
- let existing_key_nibble = NibbleSlice::from_encoded(&existing_key).0;
- let found = key.starts_with(&existing_key_nibble);
+ // dbg!(&crumb.node.node);
+ // if num_crumbs == current_index + 1 {
+ // match &crumb.node.node {
+ // TrieNode::Empty => value_presence = ProofPresence::Absent,
+ // TrieNode::Leaf(_, _) => {
+ // value_presence = ProofPresence::from_found(self.key().is_empty());
+ // }
+ // TrieNode::Branch(_, value) => {
+ // value_presence =
+ // ProofPresence::from_found(value.is_some() && self.key().is_empty());
+ // }
+ // TrieNode::Extension(_, _) => {}
+ // };
+ // }
- key = key.mid(existing_key_nibble.len());
- if !found {
- value_presence = Some(ProofPresence::Absent);
- }
- }
- };
match &crumb.raw_bytes {
None => None,
Some(bytes) => Some(near_primitives::serialize::to_base64(&bytes)),
}
})
- .collect();
- (value_presence.unwrap(), proof)
+ .collect()
}
/// Returns the hash of the last node
pub(crate) fn seek_nibble_slice(
&mut self,
- mut key: NibbleSlice<'_>,
+ key: &mut NibbleSlice<'_>,
) -> Result<CryptoHash, StorageError> {
self.trail.clear();
self.key_nibbles.clear();
@@ -158,14 +145,15 @@ impl<'a> TrieIterator<'a> {
loop {
self.descend_into_node(&hash)?;
let Crumb { status, node, .. } = self.trail.last_mut().unwrap();
- match &node.node {
+ match dbg!(&node.node) {
TrieNode::Empty => break,
TrieNode::Leaf(leaf_key, _) => {
let existing_key = NibbleSlice::from_encoded(leaf_key).0;
- if existing_key < key {
+ if existing_key < *key {
self.key_nibbles.extend(existing_key.iter());
*status = CrumbStatus::Exiting;
}
+ *key = key.mid(leaf_key.len());
break;
}
TrieNode::Branch(children, _) => {
@@ -177,8 +165,9 @@ impl<'a> TrieIterator<'a> {
*status = CrumbStatus::AtChild(idx as usize);
if let Some(child) = &children[idx] {
hash = *child.unwrap_hash();
- key = key.mid(1);
+ *key = key.mid(1);
} else {
+ *key = key.mid(1);
break;
}
}
@@ -186,15 +175,16 @@ impl<'a> TrieIterator<'a> {
TrieNode::Extension(ext_key, child) => {
let existing_key = NibbleSlice::from_encoded(ext_key).0;
if key.starts_with(&existing_key) {
- key = key.mid(existing_key.len());
+ *key = key.mid(existing_key.len());
hash = *child.unwrap_hash();
*status = CrumbStatus::At;
self.key_nibbles.extend(existing_key.iter());
} else {
- if existing_key < key {
+ if existing_key < *key {
*status = CrumbStatus::Exiting;
self.key_nibbles.extend(existing_key.iter());
}
+ *key = key.mid(existing_key.len());
break;
}
}
@@ -304,7 +294,8 @@ impl<'a> TrieIterator<'a> {
path_end: &[u8],
) -> Result<Vec<TrieItem>, StorageError> {
let path_begin_encoded = NibbleSlice::encode_nibbles(path_begin, false);
- self.seek_nibble_slice(NibbleSlice::from_encoded(&path_begin_encoded).0)?;
+ let mut key = NibbleSlice::from_encoded(&path_begin_encoded).0;
+ self.seek_nibble_slice(&mut key)?;
let mut trie_items = vec![];
for item in self {
@@ -327,7 +318,8 @@ impl<'a> TrieIterator<'a> {
path_end: &[u8],
) -> Result<Vec<TrieTraversalItem>, StorageError> {
let path_begin_encoded = NibbleSlice::encode_nibbles(path_begin, true);
- let last_hash = self.seek_nibble_slice(NibbleSlice::from_encoded(&path_begin_encoded).0)?;
+ let last_hash =
+ self.seek_nibble_slice(&mut NibbleSlice::from_encoded(&path_begin_encoded).0)?;
let mut prefix = Self::common_prefix(path_end, &self.key_nibbles);
if self.key_nibbles[prefix..] >= path_end[prefix..] {
return Ok(vec![]);
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
index c7c7e859e..86e982512 100644
--- a/core/store/src/trie/mod.rs
+++ b/core/store/src/trie/mod.rs
@@ -765,54 +765,64 @@ impl Trie {
root: &CryptoHash,
key: &[u8],
) -> Result<(ProofPresence, Vec<Arc<Vec<u8>>>), StorageError> {
- let mut key = NibbleSlice::new(key);
- let mut hash = *root;
- if hash == Trie::EMPTY_ROOT {
- return Ok((ProofPresence::from_found(key.is_empty()), vec![]));
- }
-
- let mut levels: Vec<Arc<Vec<u8>>> = vec![];
- loop {
- let bytes = self.storage.retrieve_raw_bytes(&hash)?;
- let node = RawTrieNodeWithSize::decode(&bytes).map_err(|err| {
- StorageError::StorageInconsistentState(format!(
- "RawTrieNode decode failed with {}",
- err.to_string()
- ))
- })?;
- levels.push(Arc::new(bytes.to_vec()));
-
- match node.node {
- RawTrieNode::Leaf(existing_key, ..) => {
- let found = NibbleSlice::from_encoded(&existing_key).0 == key;
- return Ok((ProofPresence::from_found(found), levels));
- }
- RawTrieNode::Extension(existing_key, child_hash) => {
- let existing_key_nibble = NibbleSlice::from_encoded(&existing_key).0;
- let found = key.starts_with(&existing_key_nibble);
-
- key = key.mid(existing_key_nibble.len());
- hash = child_hash;
- if !found {
- return Ok((ProofPresence::Absent, levels));
- }
- }
- RawTrieNode::Branch(children, value) => {
- if key.is_empty() {
- return Ok((ProofPresence::from_found(value.is_some()), levels));
- }
-
- let idx = key.at(0) as usize;
- match children[idx] {
- Some(child) => {
- hash = child;
- key = key.mid(1);
- }
- None => return Ok((ProofPresence::Absent, levels)),
- }
- }
- };
- }
+ let mut iter = self.iter(root)?;
+ let value_presence = ProofPresence::from_found(iter.seek(key)?);
+ let proof_str = iter.trail_proof();
+ Ok((
+ value_presence,
+ proof_str
+ .into_iter()
+ .map(|x| Arc::new(near_primitives::serialize::from_base64(&x).unwrap()))
+ .collect(),
+ ))
+ // let mut key = NibbleSlice::new(key);
+ // let mut hash = *root;
+ // if hash == Trie::EMPTY_ROOT {
+ // return Ok((ProofPresence::from_found(key.is_empty()), vec![]));
+ // }
+
+ // let mut levels: Vec<Arc<Vec<u8>>> = vec![];
+ // loop {
+ // let bytes = self.storage.retrieve_raw_bytes(&hash)?;
+ // let node = RawTrieNodeWithSize::decode(&bytes).map_err(|err| {
+ // StorageError::StorageInconsistentState(format!(
+ // "RawTrieNode decode failed with {}",
+ // err.to_string()
+ // ))
+ // })?;
+ // levels.push(Arc::new(bytes.to_vec()));
+
+ // match node.node {
+ // RawTrieNode::Leaf(existing_key, ..) => {
+ // let found = NibbleSlice::from_encoded(&existing_key).0 == key;
+ // return Ok((ProofPresence::from_found(found), levels));
+ // }
+ // RawTrieNode::Extension(existing_key, child_hash) => {
+ // let existing_key_nibble = NibbleSlice::from_encoded(&existing_key).0;
+ // let found = key.starts_with(&existing_key_nibble);
+
+ // key = key.mid(existing_key_nibble.len());
+ // hash = child_hash;
+ // if !found {
+ // return Ok((ProofPresence::Absent, levels));
+ // }
+ // }
+ // RawTrieNode::Branch(children, value) => {
+ // if key.is_empty() {
+ // return Ok((ProofPresence::from_found(value.is_some()), levels));
+ // }
+
+ // let idx = key.at(0) as usize;
+ // match children[idx] {
+ // Some(child) => {
+ // hash = child;
+ // key = key.mid(1);
+ // }
+ // None => return Ok((ProofPresence::Absent, levels)),
+ // }
+ // }
+ // };
+ // }
}
}
diff --git a/core/store/src/trie/state_parts.rs b/core/store/src/trie/state_parts.rs
index 33fe5f245..c206aed76 100644
--- a/core/store/src/trie/state_parts.rs
+++ b/core/store/src/trie/state_parts.rs
@@ -61,7 +61,7 @@ impl Trie {
if part_id.idx + 1 != part_id.total {
let mut iterator = self.iter(root_hash)?;
let path_end_encoded = NibbleSlice::encode_nibbles(&path_end, false);
- iterator.seek_nibble_slice(NibbleSlice::from_encoded(&path_end_encoded[..]).0)?;
+ iterator.seek_nibble_slice(&mut NibbleSlice::from_encoded(&path_end_encoded[..]).0)?;
if let Some(item) = iterator.next() {
item?;
}
@@ -418,7 +418,8 @@ mod tests {
let mut iterator = self.iter(root_hash)?;
let path_begin_encoded = NibbleSlice::encode_nibbles(&path_begin, false);
- iterator.seek_nibble_slice(NibbleSlice::from_encoded(&path_begin_encoded[..]).0)?;
+ iterator
+ .seek_nibble_slice(&mut NibbleSlice::from_encoded(&path_begin_encoded[..]).0)?;
loop {
match iterator.next() {
None => break,
@mina86 : do you have a few cycles to review this PR again please? And help @blasrodri with the above question.
How about this:
core/primitives/src/views.rs | 11 ++++----
core/store/src/trie/iterator.rs | 32 ++++++++++++++++++++--
core/store/src/trie/mod.rs | 17 +++++++++---
core/store/src/trie/state_parts.rs | 16 +++++------
.../src/tests/runtime/state_viewer.rs | 2 +-
runtime/runtime/src/state_viewer/mod.rs | 7 +++--
6 files changed, 62 insertions(+), 23 deletions(-)
diff --git a/core/primitives/src/views.rs b/core/primitives/src/views.rs
index 2594023b9..49df85d40 100644
--- a/core/primitives/src/views.rs
+++ b/core/primitives/src/views.rs
@@ -193,9 +193,6 @@ impl From<AccessKeyView> for AccessKey {
}
}
-/// Set of serialized TrieNodes that are encoded in base64. Represent proof of inclusion of some TrieNode in the MerkleTrie.
-pub type TrieProofPath = Vec<String>;
-
/// Item of the state, key and value are serialized in base64 and proof for inclusion of given state item.
#[cfg_attr(feature = "deepsize_feature", derive(deepsize::DeepSizeOf))]
#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
@@ -204,14 +201,18 @@ pub struct StateItem {
pub key: Vec<u8>,
#[serde(with = "base64_format")]
pub value: Vec<u8>,
- pub proof: TrieProofPath,
+ /// Deprecated, always empty, eventually will be deleted.
+ // TODO(mina86): This was made deprecated at protocol version 56. Remove it
+ // once we’re at 59.
+ #[serde(default)]
+ pub proof: Vec<()>,
}
#[cfg_attr(feature = "deepsize_feature", derive(deepsize::DeepSizeOf))]
#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
pub struct ViewStateResult {
pub values: Vec<StateItem>,
- pub proof: TrieProofPath,
+ pub proof: Vec<Arc<[u8]>>,
}
#[cfg_attr(feature = "deepsize_feature", derive(deepsize::DeepSizeOf))]
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
index 88c9fb213..555b96e4a 100644
--- a/core/store/src/trie/iterator.rs
+++ b/core/store/src/trie/iterator.rs
@@ -36,6 +36,9 @@ pub struct TrieIterator<'a> {
trie: &'a Trie,
trail: Vec<Crumb>,
pub(crate) key_nibbles: Vec<u8>,
+
+ /// If not `None`, a list of all nodes that the iterator has visited.
+ visited_nodes: Option<Vec<std::sync::Arc<[u8]>>>,
}
pub type TrieItem = (Vec<u8>, Vec<u8>);
@@ -56,6 +59,7 @@ impl<'a> TrieIterator<'a> {
trie,
trail: Vec::with_capacity(8),
key_nibbles: Vec::with_capacity(64),
+ visited_nodes: None,
};
r.descend_into_node(&trie.root)?;
Ok(r)
@@ -66,6 +70,24 @@ impl<'a> TrieIterator<'a> {
self.seek_nibble_slice(NibbleSlice::new(key.as_ref())).map(drop)
}
+ /// Configures whether the iterator should remember all the nodes its
+ /// visiting.
+ ///
+ /// List of visited nodes can be retrieved by [`Self::visited_nodes`] method.
+ pub fn remember_visited_nodes(&mut self, remember: bool) {
+ self.visited_nodes = remember.then(|| Vec::new());
+ }
+
+ /// Consumes iterator and returns list of nodes it’s visited.
+ ///
+ /// By default the iterator *doesn’t* remember nodes it visits. To enable
+ /// that feature use [`Self::remember_visited_nodes`] method. If the
+ /// feature is disabled, this method returns an empty list. Otherwise
+ /// it returns list of nodes visited since the feature was enabled.
+ pub fn into_visited_nodes(self) -> Vec<std::sync::Arc<[u8]>> {
+ self.visited_nodes.unwrap_or(Vec::new())
+ }
+
/// Returns the hash of the last node
pub(crate) fn seek_nibble_slice(
&mut self,
@@ -124,9 +146,15 @@ impl<'a> TrieIterator<'a> {
/// Fetches block by its hash and adds it to the trail.
///
- /// The node is stored as the last [`Crumb`] in the trail.
+ /// The node is stored as the last [`Crumb`] in the trail. If iterator is
+ /// configured to remember all the nodes its visiting (which can be enabled
+ /// with [`Self::remember_visited_nodes`]), the node will be added to the
+ /// list.
fn descend_into_node(&mut self, hash: &CryptoHash) -> Result<(), StorageError> {
- let node = self.trie.retrieve_node(hash)?;
+ let (bytes, node) = self.trie.retrieve_node(hash)?;
+ if let (Some(bytes), Some(nodes)) = (bytes, &mut self.visited_nodes) {
+ nodes.push(bytes);
+ }
self.trail.push(Crumb { status: CrumbStatus::Entering, node });
Ok(())
}
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
index 0912b2f50..adf905985 100644
--- a/core/store/src/trie/mod.rs
+++ b/core/store/src/trie/mod.rs
@@ -533,7 +533,7 @@ impl Trie {
}
let TrieNodeWithSize { node, memory_usage } = match handle {
NodeHandle::InMemory(h) => memory.node_ref(h).clone(),
- NodeHandle::Hash(h) => self.retrieve_node(&h).expect("storage failure"),
+ NodeHandle::Hash(h) => self.retrieve_node(&h).expect("storage failure").1,
};
let mut memory_usage_naive = node.memory_usage_direct(memory);
@@ -615,10 +615,19 @@ impl Trie {
}
}
- fn retrieve_node(&self, hash: &CryptoHash) -> Result<TrieNodeWithSize, StorageError> {
+ /// Retrieves decoded node alongside with its raw bytes representation.
+ ///
+ /// Note that because Empty nodes (those which are referenced by
+ /// [`Self::EMPTY_ROOT`] hash) aren’t stored in the database, they don’t
+ /// have a bytes representation. For those nodes the first return value
+ /// will be `None`.
+ fn retrieve_node(
+ &self,
+ hash: &CryptoHash,
+ ) -> Result<(Option<std::sync::Arc<[u8]>>, TrieNodeWithSize), StorageError> {
match self.retrieve_raw_node(hash)? {
- None => Ok(TrieNodeWithSize::empty()),
- Some((_bytes, node)) => Ok(TrieNodeWithSize::from_raw(node)),
+ None => Ok((None, TrieNodeWithSize::empty())),
+ Some((bytes, node)) => Ok((Some(bytes), TrieNodeWithSize::from_raw(node))),
}
}
diff --git a/core/store/src/trie/state_parts.rs b/core/store/src/trie/state_parts.rs
index 9477543c3..1baff2681 100644
--- a/core/store/src/trie/state_parts.rs
+++ b/core/store/src/trie/state_parts.rs
@@ -71,7 +71,7 @@ impl Trie {
if part_id == num_parts {
return Ok(vec![16]);
}
- let root_node = self.retrieve_node(&self.root)?;
+ let (_bytes, root_node) = self.retrieve_node(&self.root)?;
let total_size = root_node.memory_usage;
let size_start = (total_size + num_parts - 1) / num_parts * part_id;
self.find_path(&root_node, size_start)
@@ -106,7 +106,7 @@ impl Trie {
Some(NodeHandle::InMemory(_)) => {
unreachable!("only possible while mutating")
}
- Some(NodeHandle::Hash(h)) => self.retrieve_node(h)?,
+ Some(NodeHandle::Hash(h)) => self.retrieve_node(h)?.1,
};
if *size_skipped + child.memory_usage <= size_start {
*size_skipped += child.memory_usage;
@@ -136,7 +136,7 @@ impl Trie {
TrieNode::Extension(key, child_handle) => {
let child = match child_handle {
NodeHandle::InMemory(_) => unreachable!("only possible while mutating"),
- NodeHandle::Hash(h) => self.retrieve_node(h)?,
+ NodeHandle::Hash(h) => self.retrieve_node(h)?.1,
};
let (slice, _is_leaf) = NibbleSlice::from_encoded(key);
key_nibbles.extend(slice.iter());
@@ -319,7 +319,7 @@ mod tests {
return Ok(());
}
let mut stack: Vec<(CryptoHash, TrieNodeWithSize, CrumbStatus)> = Vec::new();
- let root_node = self.retrieve_node(&self.root)?;
+ let (_bytes, root_node) = self.retrieve_node(&self.root)?;
stack.push((self.root.clone(), root_node, CrumbStatus::Entering));
while let Some((hash, node, position)) = stack.pop() {
if let CrumbStatus::Entering = position {
@@ -360,7 +360,7 @@ mod tests {
}
if i < 16 {
if let Some(NodeHandle::Hash(h)) = children[i].clone() {
- let child = self.retrieve_node(&h)?;
+ let (_bytes, child) = self.retrieve_node(&h)?;
stack.push((hash, node, CrumbStatus::AtChild(i + 1)));
stack.push((h, child, CrumbStatus::Entering));
} else {
@@ -384,7 +384,7 @@ mod tests {
unreachable!("only possible while mutating")
}
NodeHandle::Hash(h) => {
- let child = self.retrieve_node(&h)?;
+ let (_bytes, child) = self.retrieve_node(&h)?;
stack.push((hash, node, CrumbStatus::Exiting));
stack.push((h, child, CrumbStatus::Entering));
}
@@ -401,7 +401,7 @@ mod tests {
size_start: u64,
size_end: u64,
) -> Result<(), StorageError> {
- let root_node = self.retrieve_node(&self.root)?;
+ let (_bytes, root_node) = self.retrieve_node(&self.root)?;
let path_begin = self.find_path(&root_node, size_start)?;
let path_end = self.find_path(&root_node, size_end)?;
@@ -431,7 +431,7 @@ mod tests {
part_id: PartId,
) -> Result<PartialState, StorageError> {
assert!(self.storage.as_caching_storage().is_some());
- let root_node = self.retrieve_node(&self.root)?;
+ let (_bytes, root_node) = self.retrieve_node(&self.root)?;
let total_size = root_node.memory_usage;
let size_start = (total_size + part_id.total - 1) / part_id.total * part_id.idx;
let size_end = std::cmp::min(
diff --git a/integration-tests/src/tests/runtime/state_viewer.rs b/integration-tests/src/tests/runtime/state_viewer.rs
index f8f32a807..419b066ea 100644
--- a/integration-tests/src/tests/runtime/state_viewer.rs
+++ b/integration-tests/src/tests/runtime/state_viewer.rs
@@ -132,7 +132,7 @@ fn test_view_state() {
let state_update = tries.new_trie_update(shard_uid, new_root);
let trie_viewer = TrieViewer::default();
let result = trie_viewer.view_state(&state_update, &alice_account(), b"").unwrap();
- assert_eq!(result.proof, Vec::<String>::new());
+ assert_eq!(result.proof, Vec::new());
assert_eq!(
result.values,
[
diff --git a/runtime/runtime/src/state_viewer/mod.rs b/runtime/runtime/src/state_viewer/mod.rs
index 1f72d098b..49ca37727 100644
--- a/runtime/runtime/src/state_viewer/mod.rs
+++ b/runtime/runtime/src/state_viewer/mod.rs
@@ -143,8 +143,9 @@ impl TrieViewer {
let query = trie_key_parsers::get_raw_prefix_for_contract_data(account_id, prefix);
let acc_sep_len = query.len() - prefix.len();
let mut iter = state_update.trie().iter()?;
+ iter.remember_visited_nodes(true);
iter.seek(&query)?;
- for item in iter {
+ for item in &mut iter {
let (key, value) = item?;
if !key.starts_with(query.as_ref()) {
break;
@@ -155,8 +156,8 @@ impl TrieViewer {
proof: vec![],
});
}
- // TODO(2076): Add proofs for the storage items.
- Ok(ViewStateResult { values, proof: vec![] })
+ let proof = iter.into_visited_nodes();
+ Ok(ViewStateResult { values, proof })
}
pub fn call_function(
I think here the proof will include a spurious node but that can be addressed by minor additional logic to TrieIterator where we mark a crumb as anchor and when the iterator goes back to that crumb it stops rather than trying to iterate further.
Hey @mina86, we've applied your patch, but got some tests failing (e.g. test_view_state)
Index: core/primitives/src/views.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/primitives/src/views.rs b/core/primitives/src/views.rs
--- a/core/primitives/src/views.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/core/primitives/src/views.rs (date 1661862657786)
@@ -204,7 +204,11 @@
pub key: Vec<u8>,
#[serde(with = "base64_format")]
pub value: Vec<u8>,
- pub proof: TrieProofPath,
+ /// Deprecated, always empty, eventually will be deleted.
+ // TODO(mina86): This was made deprecated at protocol version 56. Remove it
+ // once we’re at 59.
+ #[serde(default)]
+ pub proof: Vec<()>,
}
/// A value can be present or absent on the state trie. [ProofPresence] encodes these different states.
@@ -229,7 +233,7 @@
#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
pub struct ViewStateResult {
pub values: Vec<StateItem>,
- pub proof: Option<(ProofPresence, Vec<String>)>,
+ pub proof: Vec<Arc<[u8]>>,
}
#[cfg_attr(feature = "deepsize_feature", derive(deepsize::DeepSizeOf))]
Index: runtime/near-vm-runner/src/tests/rs_contract.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/runtime/near-vm-runner/src/tests/rs_contract.rs b/runtime/near-vm-runner/src/tests/rs_contract.rs
--- a/runtime/near-vm-runner/src/tests/rs_contract.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/runtime/near-vm-runner/src/tests/rs_contract.rs (date 1661862657788)
@@ -254,8 +254,7 @@
let prepaid_gas = 100 * 10u64.pow(12);
context.prepaid_gas = prepaid_gas;
config.limit_config.max_gas_burnt = context.prepaid_gas / 3;
- let runtime = vm_kind.runtime(config).expect("runtime has not been compiled");
-
+ let mut runtime = vm_kind.runtime(config).expect("runtime has not been compiled");
let (outcome, err) = runtime
.run(
&code,
Index: core/store/src/trie/mod.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/store/src/trie/mod.rs b/core/store/src/trie/mod.rs
--- a/core/store/src/trie/mod.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/core/store/src/trie/mod.rs (date 1661862705775)
@@ -511,7 +511,7 @@
}
let TrieNodeWithSize { node, memory_usage } = match handle {
NodeHandle::InMemory(h) => memory.node_ref(h).clone(),
- NodeHandle::Hash(h) => self.retrieve_node(&h).expect("storage failure"),
+ NodeHandle::Hash(h) => self.retrieve_node(&h).expect("storage failure").1,
};
let mut memory_usage_naive = node.memory_usage_direct(memory);
@@ -593,10 +593,19 @@
}
}
- fn retrieve_node(&self, hash: &CryptoHash) -> Result<TrieNodeWithSize, StorageError> {
+ /// Retrieves decoded node alongside with its raw bytes representation.
+ ///
+ /// Note that because Empty nodes (those which are referenced by
+ /// [`Self::EMPTY_ROOT`] hash) aren’t stored in the database, they don’t
+ /// have a bytes representation. For those nodes the first return value
+ /// will be `None`.
+ fn retrieve_node(
+ &self,
+ hash: &CryptoHash,
+ ) -> Result<(Option<Arc<[u8]>>, TrieNodeWithSize), StorageError> {
match self.retrieve_raw_node(hash)? {
- None => Ok(TrieNodeWithSize::empty()),
- Some((_bytes, node)) => Ok(TrieNodeWithSize::from_raw(node)),
+ None => Ok((None, TrieNodeWithSize::empty())),
+ Some((bytes, node)) => Ok((Some(bytes), TrieNodeWithSize::from_raw(node))),
}
}
@@ -751,12 +760,27 @@
pub fn get_proof(
&self,
root: &CryptoHash,
- key: &[u8],
- ) -> Result<(ProofPresence, Vec<Arc<Vec<u8>>>), StorageError> {
- let mut key = NibbleSlice::new(key);
+ raw_key: &[u8],
+ ) -> Result<Vec<Arc<Vec<u8>>>, StorageError> {
+ let mut key = NibbleSlice::new(raw_key);
+ // let mut query_key = NibbleSlice::new(raw_key);
let mut hash = *root;
+
+ // let mut iter = self.iter(root)?;
+ // iter.remember_visited_nodes(true);
+ // iter.seek_nibble_slice(query_key)?;
+ // for item in &mut iter {
+ // let (key, _) = item?;
+ // if !key.starts_with(raw_key) {
+ // break;
+ // }
+ // }
+ // let proof =
+ // iter.into_visited_nodes().into_iter().map(|x| Arc::new(x.to_vec())).collect::<Vec<_>>();
+ // Ok(proof)
+
if hash == Trie::EMPTY_ROOT {
- return Ok((ProofPresence::from_found(key.is_empty()), vec![]));
+ return Ok(vec![]);
}
let mut levels: Vec<Arc<Vec<u8>>> = vec![];
@@ -772,8 +796,7 @@
match node.node {
RawTrieNode::Leaf(existing_key, ..) => {
- let found = NibbleSlice::from_encoded(&existing_key).0 == key;
- return Ok((ProofPresence::from_found(found), levels));
+ return Ok(levels);
}
RawTrieNode::Extension(existing_key, child_hash) => {
let existing_key_nibble = NibbleSlice::from_encoded(&existing_key).0;
@@ -782,12 +805,12 @@
key = key.mid(existing_key_nibble.len());
hash = child_hash;
if !found {
- return Ok((ProofPresence::Absent, levels));
+ return Ok(levels);
}
}
- RawTrieNode::Branch(children, value) => {
+ RawTrieNode::Branch(children, ..) => {
if key.is_empty() {
- return Ok((ProofPresence::from_found(value.is_some()), levels));
+ return Ok(levels);
}
let idx = key.at(0) as usize;
@@ -796,7 +819,7 @@
hash = child;
key = key.mid(1);
}
- None => return Ok((ProofPresence::Absent, levels)),
+ None => return Ok(levels),
}
}
};
@@ -1342,11 +1365,8 @@
);
for (k, v) in changes {
- let (found, raw_proof) = trie.get_proof(&root, &k).unwrap();
+ let raw_proof = trie.get_proof(&root, &k).unwrap();
let proof = raw_proof.iter().map(|p| RawTrieNodeWithSize::decode(p).unwrap()).collect();
-
- assert_eq!(found, ProofPresence::Present);
- dbg!(&k);
assert!(verify_proof(&k, proof, v.as_deref(), root));
}
@@ -1354,18 +1374,16 @@
[b"white_horse".as_ref(), b"white_rose".as_ref(), b"doge_elon".as_ref(), b"".as_ref()];
for non_existing_key in non_existing_keys {
- let (found, raw_proof) = trie.get_proof(&root, non_existing_key).unwrap();
+ let raw_proof = trie.get_proof(&root, non_existing_key).unwrap();
let proof = raw_proof.iter().map(|p| RawTrieNodeWithSize::decode(p).unwrap()).collect();
assert!(verify_proof(non_existing_key, proof, None, root));
- assert_eq!(found, ProofPresence::Absent);
}
for non_existing_key in non_existing_keys {
- let (found, raw_proof) = trie.get_proof(&root, non_existing_key).unwrap();
+ let raw_proof = trie.get_proof(&root, non_existing_key).unwrap();
let proof = raw_proof.iter().map(|p| RawTrieNodeWithSize::decode(p).unwrap()).collect();
// duplicating this because RawTrieNodeWithSize does not implement Clone
assert!(!verify_proof(non_existing_key, proof, Some(b"0_value"), root));
- assert_eq!(found, ProofPresence::Absent);
}
}
}
Index: tools/indexer/example/src/main.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/tools/indexer/example/src/main.rs b/tools/indexer/example/src/main.rs
--- a/tools/indexer/example/src/main.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/tools/indexer/example/src/main.rs (date 1661862657789)
@@ -11,7 +11,9 @@
mod configs;
async fn listen_blocks(mut stream: mpsc::Receiver<near_indexer::StreamerMessage>) {
+ println!("11");
while let Some(streamer_message) = stream.recv().await {
+ println!("12");
// TODO: handle data as you need
// Example of `StreamerMessage` with all the data (the data is synthetic)
//
@@ -264,11 +266,15 @@
"nearcore=info,indexer_example=info,tokio_reactor=info,near=info,\
stats=info,telemetry=info,indexer=info,near-performance-metrics=info",
);
+
let runtime = tokio::runtime::Runtime::new().unwrap();
- let _subscriber = runtime.block_on(async {
- near_o11y::default_subscriber(env_filter, &Default::default()).await.global();
- });
+ // let _subscriber = runtime.block_on(async {
+ // near_o11y::default_subscriber(env_filter, &Default::default()).await.global();
+ // });
+ near_o11y::tracing_subscriber::fmt::init();
+ info!(target: "my", "1");
let opts: Opts = Opts::parse();
+ println!("1");
let home_dir = opts.home_dir.unwrap_or(near_indexer::get_default_home());
Index: runtime/runtime/src/state_viewer/mod.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/runtime/runtime/src/state_viewer/mod.rs b/runtime/runtime/src/state_viewer/mod.rs
--- a/runtime/runtime/src/state_viewer/mod.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/runtime/runtime/src/state_viewer/mod.rs (date 1661862657789)
@@ -2,7 +2,6 @@
use crate::{actions::execute_function_call, ext::RuntimeExt};
use near_crypto::{KeyType, PublicKey};
use near_primitives::runtime::config_store::RuntimeConfigStore;
-use near_primitives::serialize::to_base64;
use near_primitives::{
account::{AccessKey, Account},
borsh::BorshDeserialize,
@@ -144,8 +143,9 @@
let query = trie_key_parsers::get_raw_prefix_for_contract_data(account_id, prefix);
let acc_sep_len = query.len() - prefix.len();
let mut iter = state_update.trie.iter(&state_update.get_root())?;
+ iter.remember_visited_nodes(true);
iter.seek(&query)?;
- for item in iter {
+ for item in &mut iter {
let (key, value) = item?;
if !key.starts_with(query.as_ref()) {
break;
@@ -157,13 +157,15 @@
});
}
// TODO(2076): Add proofs for the storage items.
- let trie = state_update.trie();
- let root = state_update.get_root();
+ // let trie = state_update.trie();
+ // let root = state_update.get_root();
- let (proof_state, raw_proof) = trie.get_proof(&root, &query)?;
- let serialized_proof = raw_proof.iter().map(|p| to_base64(&**p)).collect();
+ // let (proof_state, raw_proof) = trie.get_proof(&root, &query)?;
+ // let serialized_proof = raw_proof.iter().map(|p| to_base64(&**p)).collect();
- Ok(ViewStateResult { values, proof: Some((proof_state, serialized_proof)) })
+ let proof = iter.into_visited_nodes();
+ Ok(ViewStateResult { values, proof })
+ // Ok(ViewStateResult { values, proof: Some((proof_state, serialized_proof)) })
}
pub fn call_function(
Index: chain/chain/src/test_utils.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/chain/chain/src/test_utils.rs b/chain/chain/src/test_utils.rs
--- a/chain/chain/src/test_utils.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/chain/chain/src/test_utils.rs (date 1661862657785)
@@ -983,7 +983,7 @@
QueryRequest::ViewState { .. } => Ok(QueryResponse {
kind: QueryResponseKind::ViewState(ViewStateResult {
values: Default::default(),
- proof: None,
+ proof: vec![],
}),
block_height,
block_hash: *block_hash,
Index: core/store/src/trie/state_parts.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/store/src/trie/state_parts.rs b/core/store/src/trie/state_parts.rs
--- a/core/store/src/trie/state_parts.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/core/store/src/trie/state_parts.rs (date 1661862657787)
@@ -82,7 +82,7 @@
if part_id == num_parts {
return Ok(vec![16]);
}
- let root_node = self.retrieve_node(state_root)?;
+ let root_node = self.retrieve_node(state_root)?.1;
let total_size = root_node.memory_usage;
let size_start = (total_size + num_parts - 1) / num_parts * part_id;
self.find_path(&root_node, size_start)
@@ -117,7 +117,7 @@
Some(NodeHandle::InMemory(_)) => {
unreachable!("only possible while mutating")
}
- Some(NodeHandle::Hash(h)) => self.retrieve_node(h)?,
+ Some(NodeHandle::Hash(h)) => self.retrieve_node(h)?.1,
};
if *size_skipped + child.memory_usage <= size_start {
*size_skipped += child.memory_usage;
@@ -147,7 +147,7 @@
TrieNode::Extension(key, child_handle) => {
let child = match child_handle {
NodeHandle::InMemory(_) => unreachable!("only possible while mutating"),
- NodeHandle::Hash(h) => self.retrieve_node(h)?,
+ NodeHandle::Hash(h) => self.retrieve_node(h)?.1,
};
let (slice, _is_leaf) = NibbleSlice::from_encoded(key);
key_nibbles.extend(slice.iter());
@@ -329,7 +329,7 @@
return Ok(());
}
let mut stack: Vec<(CryptoHash, TrieNodeWithSize, CrumbStatus)> = Vec::new();
- let root_node = self.retrieve_node(root)?;
+ let (_bytes, root_node) = self.retrieve_node(root)?;
stack.push((*root, root_node, CrumbStatus::Entering));
while let Some((hash, node, position)) = stack.pop() {
if let CrumbStatus::Entering = position {
@@ -370,7 +370,7 @@
}
if i < 16 {
if let Some(NodeHandle::Hash(h)) = children[i].clone() {
- let child = self.retrieve_node(&h)?;
+ let (_bytes, child) = self.retrieve_node(&h)?;
stack.push((hash, node, CrumbStatus::AtChild(i + 1)));
stack.push((h, child, CrumbStatus::Entering));
} else {
@@ -394,7 +394,7 @@
unreachable!("only possible while mutating")
}
NodeHandle::Hash(h) => {
- let child = self.retrieve_node(&h)?;
+ let (_bytes, child) = self.retrieve_node(&h)?;
stack.push((hash, node, CrumbStatus::Exiting));
stack.push((h, child, CrumbStatus::Entering));
}
@@ -412,7 +412,7 @@
size_start: u64,
size_end: u64,
) -> Result<(), StorageError> {
- let root_node = self.retrieve_node(root_hash)?;
+ let root_node = self.retrieve_node(root_hash)?.1;
let path_begin = self.find_path(&root_node, size_start)?;
let path_end = self.find_path(&root_node, size_end)?;
@@ -443,7 +443,7 @@
state_root: &StateRoot,
) -> Result<PartialState, StorageError> {
assert!(self.storage.as_caching_storage().is_some());
- let root_node = self.retrieve_node(state_root)?;
+ let root_node = self.retrieve_node(state_root)?.1;
let total_size = root_node.memory_usage;
let size_start = (total_size + part_id.total - 1) / part_id.total * part_id.idx;
let size_end = std::cmp::min(
Index: integration-tests/src/tests/runtime/state_viewer.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/integration-tests/src/tests/runtime/state_viewer.rs b/integration-tests/src/tests/runtime/state_viewer.rs
--- a/integration-tests/src/tests/runtime/state_viewer.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/integration-tests/src/tests/runtime/state_viewer.rs (date 1661862657788)
@@ -11,9 +11,11 @@
types::{EpochId, StateChangeCause},
version::PROTOCOL_VERSION,
};
+use near_primitives_core::serialize::from_base64;
use near_store::set_account;
use node_runtime::state_viewer::errors;
use node_runtime::state_viewer::*;
+use std::sync::Arc;
use testlib::runtime_utils::{alice_account, encode_int};
#[test]
@@ -134,7 +136,7 @@
let state_update = tries.new_trie_update(shard_uid, new_root);
let trie_viewer = TrieViewer::default();
let result = trie_viewer.view_state(&state_update, &alice_account(), b"").unwrap();
- assert_eq!(result.proof, Some((ProofPresence::Absent, ["AwEAAAAQeCC3sbe18vLEata/zo1C7+9cOijOmZrI27xJZ+SpzzMyCgAAAAAAAA==", "AQUCv3bNFVGGZS/TOlpHqqXRpxPXvaRlFU+gE8BM4GyIwpWnmEa/D1YpSfNTICSr1f0dUsULk38MJm2erDf0wtl3y9UgieFjNRmdMjEmjaSTnbCR/ZHWttN1jN2YfNYMc+q5/gkAAAAAAAA=", "AwMAAAAWFsbwm2TFX4GHLT5G1LSpF8UkG7zQV1ohXBMR/OQcUAKZ3gwDAAAAAAAA", "ASAC7S1KwgLNl0HPdSo8soL8sGOmPhL7O0xTSR8sDDR5pZrzu0ty3UPYJ5UKrFGKxXoyyyNG75AF9hnJHO3xxFkf5NQCAAAAAAAA", "AwEAAAAW607KPj2q3O8dF6XkfALiIrd9mqGir2UlYIcZuLNksTsvAgAAAAAAAA==", "AQhAP4sMdbiWZPtV6jz8hYKzRFSgwaSlQKiGsQXogAmMcrLOl+SJfiCOXMTEZ2a1ebmQOEGkRYa30FaIlB46sLI2IPsBAAAAAAAA", "AwwAAAAWUubmVhcix0ZXN0PKtrEndk0LxM+qpzp0PVtjf+xlrzz4TT0qA+hTtm6BLlYBAAAAAAAA"].into_iter().map(String::from).collect())));
+ assert_eq!(result.proof.into_iter().map(|x| x.to_vec()).collect::<Vec<_>>(), ["AwEAAAAQeCC3sbe18vLEata/zo1C7+9cOijOmZrI27xJZ+SpzzMyCgAAAAAAAA==", "AQUCv3bNFVGGZS/TOlpHqqXRpxPXvaRlFU+gE8BM4GyIwpWnmEa/D1YpSfNTICSr1f0dUsULk38MJm2erDf0wtl3y9UgieFjNRmdMjEmjaSTnbCR/ZHWttN1jN2YfNYMc+q5/gkAAAAAAAA=", "AwMAAAAWFsbwm2TFX4GHLT5G1LSpF8UkG7zQV1ohXBMR/OQcUAKZ3gwDAAAAAAAA", "ASAC7S1KwgLNl0HPdSo8soL8sGOmPhL7O0xTSR8sDDR5pZrzu0ty3UPYJ5UKrFGKxXoyyyNG75AF9hnJHO3xxFkf5NQCAAAAAAAA", "AwEAAAAW607KPj2q3O8dF6XkfALiIrd9mqGir2UlYIcZuLNksTsvAgAAAAAAAA==", "AQhAP4sMdbiWZPtV6jz8hYKzRFSgwaSlQKiGsQXogAmMcrLOl+SJfiCOXMTEZ2a1ebmQOEGkRYa30FaIlB46sLI2IPsBAAAAAAAA", "AwwAAAAWUubmVhcix0ZXN0PKtrEndk0LxM+qpzp0PVtjf+xlrzz4TT0qA+hTtm6BLlYBAAAAAAAA"].into_iter().map(|x| from_base64(x).unwrap()).collect::<Vec<_>>());
assert_eq!(
result.values,
[
@@ -150,7 +152,7 @@
[StateItem { key: b"test123".to_vec(), value: b"123".to_vec(), proof: vec![] }]
);
- assert_eq!(result.proof, Some((ProofPresence::Present, ["AwEAAAAQeCC3sbe18vLEata/zo1C7+9cOijOmZrI27xJZ+SpzzMyCgAAAAAAAA==", "AQUCv3bNFVGGZS/TOlpHqqXRpxPXvaRlFU+gE8BM4GyIwpWnmEa/D1YpSfNTICSr1f0dUsULk38MJm2erDf0wtl3y9UgieFjNRmdMjEmjaSTnbCR/ZHWttN1jN2YfNYMc+q5/gkAAAAAAAA=", "AwMAAAAWFsbwm2TFX4GHLT5G1LSpF8UkG7zQV1ohXBMR/OQcUAKZ3gwDAAAAAAAA", "ASAC7S1KwgLNl0HPdSo8soL8sGOmPhL7O0xTSR8sDDR5pZrzu0ty3UPYJ5UKrFGKxXoyyyNG75AF9hnJHO3xxFkf5NQCAAAAAAAA", "AwEAAAAW607KPj2q3O8dF6XkfALiIrd9mqGir2UlYIcZuLNksTsvAgAAAAAAAA==", "AQhAP4sMdbiWZPtV6jz8hYKzRFSgwaSlQKiGsQXogAmMcrLOl+SJfiCOXMTEZ2a1ebmQOEGkRYa30FaIlB46sLI2IPsBAAAAAAAA", "AwwAAAAWUubmVhcix0ZXN0PKtrEndk0LxM+qpzp0PVtjf+xlrzz4TT0qA+hTtm6BLlYBAAAAAAAA", "AQoAVWCdny7wv/M1LvZASC3Fw0D/NNhI1NYwch9Ux+KZ2qRdQXPC1rNsCGRJ7nd66SfcNmRUVVvQY6EYCbsIiugO6gwBAAAAAAAA", "AAMAAAAgMjMDAAAApmWkWSBCL51Bfkhn79xPuKBKHz//H6B+mY6G9/eieuNtAAAAAAAAAA=="].into_iter().map(String::from).collect())));
+ assert_eq!(result.proof.into_iter().map(|x| x.to_vec()).collect::<Vec<_>>(), ["AwEAAAAQeCC3sbe18vLEata/zo1C7+9cOijOmZrI27xJZ+SpzzMyCgAAAAAAAA==", "AQUCv3bNFVGGZS/TOlpHqqXRpxPXvaRlFU+gE8BM4GyIwpWnmEa/D1YpSfNTICSr1f0dUsULk38MJm2erDf0wtl3y9UgieFjNRmdMjEmjaSTnbCR/ZHWttN1jN2YfNYMc+q5/gkAAAAAAAA=", "AwMAAAAWFsbwm2TFX4GHLT5G1LSpF8UkG7zQV1ohXBMR/OQcUAKZ3gwDAAAAAAAA", "ASAC7S1KwgLNl0HPdSo8soL8sGOmPhL7O0xTSR8sDDR5pZrzu0ty3UPYJ5UKrFGKxXoyyyNG75AF9hnJHO3xxFkf5NQCAAAAAAAA", "AwEAAAAW607KPj2q3O8dF6XkfALiIrd9mqGir2UlYIcZuLNksTsvAgAAAAAAAA==", "AQhAP4sMdbiWZPtV6jz8hYKzRFSgwaSlQKiGsQXogAmMcrLOl+SJfiCOXMTEZ2a1ebmQOEGkRYa30FaIlB46sLI2IPsBAAAAAAAA", "AwwAAAAWUubmVhcix0ZXN0PKtrEndk0LxM+qpzp0PVtjf+xlrzz4TT0qA+hTtm6BLlYBAAAAAAAA", "AQoAVWCdny7wv/M1LvZASC3Fw0D/NNhI1NYwch9Ux+KZ2qRdQXPC1rNsCGRJ7nd66SfcNmRUVVvQY6EYCbsIiugO6gwBAAAAAAAA", "AAMAAAAgMjMDAAAApmWkWSBCL51Bfkhn79xPuKBKHz//H6B+mY6G9/eieuNtAAAAAAAAAA=="].into_iter().map(|x| from_base64(x).unwrap()).collect::<Vec<_>>());
}
#[test]
Index: core/store/src/trie/iterator.rs
IDEA additional info:
Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
<+>UTF-8
===================================================================
diff --git a/core/store/src/trie/iterator.rs b/core/store/src/trie/iterator.rs
--- a/core/store/src/trie/iterator.rs (revision dd0650dae8613f5093b5696344e3a3c124aeb583)
+++ b/core/store/src/trie/iterator.rs (date 1661862657786)
@@ -37,6 +37,8 @@
trail: Vec<Crumb>,
pub(crate) key_nibbles: Vec<u8>,
root: CryptoHash,
+ /// If not `None`, a list of all nodes that the iterator has visited.
+ visited_nodes: Option<Vec<std::sync::Arc<[u8]>>>,
}
pub type TrieItem = (Vec<u8>, Vec<u8>);
@@ -57,10 +59,10 @@
trie,
trail: Vec::with_capacity(8),
key_nibbles: Vec::with_capacity(64),
+ visited_nodes: None,
root: *root,
};
- let node = trie.retrieve_node(root)?;
- r.descend_into_node(node);
+ r.descend_into_node(&root)?;
Ok(r)
}
@@ -69,6 +71,24 @@
self.seek_nibble_slice(NibbleSlice::new(key.as_ref())).map(drop)
}
+ /// Configures whether the iterator should remember all the nodes its
+ /// visiting.
+ ///
+ /// List of visited nodes can be retrieved by [`Self::visited_nodes`] method.
+ pub fn remember_visited_nodes(&mut self, remember: bool) {
+ self.visited_nodes = remember.then(|| Vec::new());
+ }
+
+ /// Consumes iterator and returns list of nodes it’s visited.
+ ///
+ /// By default the iterator *doesn’t* remember nodes it visits. To enable
+ /// that feature use [`Self::remember_visited_nodes`] method. If the
+ /// feature is disabled, this method returns an empty list. Otherwise
+ /// it returns list of nodes visited since the feature was enabled.
+ pub fn into_visited_nodes(self) -> Vec<std::sync::Arc<[u8]>> {
+ self.visited_nodes.unwrap_or(Vec::new())
+ }
+
/// Returns the hash of the last node
pub(crate) fn seek_nibble_slice(
&mut self,
@@ -78,7 +98,7 @@
self.key_nibbles.clear();
let mut hash = self.root;
loop {
- let node = self.trie.retrieve_node(&hash)?;
+ let node = self.trie.retrieve_node(&hash)?.1;
self.trail.push(Crumb { status: CrumbStatus::Entering, node });
let Crumb { status, node } = self.trail.last_mut().unwrap();
match &node.node {
@@ -126,8 +146,19 @@
Ok(hash)
}
- fn descend_into_node(&mut self, node: TrieNodeWithSize) {
+ /// Fetches block by its hash and adds it to the trail.
+ ///
+ /// The node is stored as the last [`Crumb`] in the trail. If iterator is
+ /// configured to remember all the nodes its visiting (which can be enabled
+ /// with [`Self::remember_visited_nodes`]), the node will be added to the
+ /// list.
+ fn descend_into_node(&mut self, hash: &CryptoHash) -> Result<(), StorageError> {
+ let (bytes, node) = self.trie.retrieve_node(hash)?;
+ if let (Some(bytes), Some(nodes)) = (bytes, &mut self.visited_nodes) {
+ nodes.push(bytes);
+ }
self.trail.push(Crumb { status: CrumbStatus::Entering, node });
+ Ok(())
}
fn key(&self) -> Vec<u8> {
@@ -279,8 +310,7 @@
if self.key_nibbles[prefix..] >= path_end[prefix..] {
break;
}
- let node = self.trie.retrieve_node(&hash)?;
- self.descend_into_node(node);
+ self.descend_into_node(&hash)?;
nodes_list.push(TrieTraversalItem { hash, key: None });
}
IterStep::Continue => {}
@@ -314,9 +344,9 @@
IterStep::PopTrail => {
self.trail.pop();
}
- IterStep::Descend(hash) => match self.trie.retrieve_node(&hash) {
- Ok(node) => self.descend_into_node(node),
- Err(e) => return Some(Err(e)),
+ IterStep::Descend(hash) => match self.descend_into_node(&hash) {
+ Ok(_) => (),
+ Err(err) => return Some(Err(err)),
},
IterStep::Continue => {}
IterStep::Value(hash) => {
@@ -471,10 +501,7 @@
IterStep::PopTrail => {
iterator.trail.pop();
}
- IterStep::Descend(hash) => match iterator.trie.retrieve_node(&hash) {
- Ok(node) => iterator.descend_into_node(node),
- Err(e) => panic!("Unexpected error: {}", e),
- },
+ IterStep::Descend(hash) => iterator.descend_into_node(&hash).unwrap(),
_ => {}
}
}
Well, yes, failures with test_view_state are expected since I didn’t update the state there so the tests expect it to be empty when it isn’t. My diff was by no means complete, there are a few things that need to happen:
- Ideally as a separate PR, replace TrieIterator::seek by TrieIterator::seek_to_prefix which would limit the iterator to stop iteration as soon as it tries to exit the node it seeked to. This would mean that
key.starts_with(query.as_ref())check in view_state would no longer be necessary and that the iterator would not visit unnecessary nodes. - Add a
want_proofparameter to the view state call so that we don’t collect nor send the data the user doesn’t care about. - Add a view state test which verifies the proof.