Open wojake opened 1 year ago
Related, you can hack in prehashed leaf nodes into the ShaMAP pretty easily for verifying. There's methods on the SHAMap already like getProofPath
/ visitLeaves
etc for building.
diff --git a/src/ripple/shamap/SHAMapPreHashedLeafNode.h b/src/ripple/shamap/SHAMapPreHashedLeafNode.h
new file mode 100644
index 000000000..a00884471
--- /dev/null
+++ b/src/ripple/shamap/SHAMapPreHashedLeafNode.h
@@ -0,0 +1,87 @@
+//------------------------------------------------------------------------------
+/*
+ This file is part of rippled: https://github.com/ripple/rippled
+ Copyright (c) 2012, 2013 Ripple Labs Inc.
+
+ Permission to use, copy, modify, and/or distribute this software for any
+ purpose with or without fee is hereby granted, provided that the above
+ copyright notice and this permission notice appear in all copies.
+
+ THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ ANY SPECIAL , DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+//==============================================================================
+
+#ifndef RIPPLE_SHAMAP_SHAMAPPREHASHEDLEAFNODE_H_INCLUDED
+#define RIPPLE_SHAMAP_SHAMAPPREHASHEDLEAFNODE_H_INCLUDED
+
+#include <ripple/basics/CountedObject.h>
+#include <ripple/protocol/HashPrefix.h>
+#include <ripple/protocol/digest.h>
+#include <ripple/shamap/SHAMapItem.h>
+#include <ripple/shamap/SHAMapLeafNode.h>
+#include <ripple/shamap/SHAMapNodeID.h>
+namespace ripple {
+
+/** A leaf node with a pre-hashed item. */
+class SHAMapPreHashedLeafNode final
+ : public SHAMapLeafNode,
+ public CountedObject<SHAMapPreHashedLeafNode>
+{
+public:
+ SHAMapPreHashedLeafNode(
+ std::shared_ptr<SHAMapItem const> item,
+ std::uint32_t cowid)
+ : SHAMapLeafNode(std::move(item), cowid)
+ {
+ updateHash();
+ }
+
+ SHAMapPreHashedLeafNode(
+ std::shared_ptr<SHAMapItem const> item,
+ std::uint32_t cowid,
+ SHAMapHash const& hash)
+ : SHAMapLeafNode(std::move(item), cowid, hash)
+ {
+ }
+
+ std::shared_ptr<SHAMapTreeNode>
+ clone(std::uint32_t cowid) const final override
+ {
+ return std::make_shared<SHAMapPreHashedLeafNode>(item_, cowid, hash_);
+ }
+
+ SHAMapNodeType
+ getType() const final override
+ {
+ return SHAMapNodeType::tnNON_BACKED_PH;
+ }
+
+ void
+ updateHash() final override
+ {
+ hash_ = SHAMapHash{uint256(item_->slice())};
+ }
+
+ void
+ serializeForWire(Serializer& s) const final override
+ {
+ assert(false);
+ throw new std::runtime_error("use for un-backed map only");
+ }
+
+ void
+ serializeWithPrefix(Serializer& s) const final override
+ {
+ assert(false);
+ throw new std::runtime_error("use for un-backed map only");
+ }
+};
+
+} // namespace ripple
+#endif
diff --git a/src/ripple/shamap/SHAMapTreeNode.h b/src/ripple/shamap/SHAMapTreeNode.h
index 8e351cce9..d0615b90b 100644
--- a/src/ripple/shamap/SHAMapTreeNode.h
+++ b/src/ripple/shamap/SHAMapTreeNode.h
@@ -47,7 +47,8 @@ enum class SHAMapNodeType {
tnINNER = 1,
tnTRANSACTION_NM = 2, // transaction, no metadata
tnTRANSACTION_MD = 3, // transaction, with metadata
- tnACCOUNT_STATE = 4
+ tnACCOUNT_STATE = 4,
+ tnNON_BACKED_PH = 5 // non-backed pre-hashed
};
class SHAMapTreeNode
diff --git a/src/ripple/shamap/impl/CMakeLists.txt b/src/ripple/shamap/impl/CMakeLists.txt
deleted file mode 100644
index e69de29bb..000000000
diff --git a/src/ripple/shamap/impl/SHAMap.cpp b/src/ripple/shamap/impl/SHAMap.cpp
index ce031003c..d3c3a6a63 100644
--- a/src/ripple/shamap/impl/SHAMap.cpp
+++ b/src/ripple/shamap/impl/SHAMap.cpp
@@ -21,6 +21,7 @@
#include <ripple/shamap/SHAMap.h>
#include <ripple/shamap/SHAMapAccountStateLeafNode.h>
#include <ripple/shamap/SHAMapNodeID.h>
+#include <ripple/shamap/SHAMapPreHashedLeafNode.h>
#include <ripple/shamap/SHAMapSyncFilter.h>
#include <ripple/shamap/SHAMapTxLeafNode.h>
#include <ripple/shamap/SHAMapTxPlusMetaLeafNode.h>
@@ -44,13 +45,18 @@ makeTypedLeaf(
return std::make_shared<SHAMapAccountStateLeafNode>(
std::move(item), owner);
+ if (type == SHAMapNodeType::tnNON_BACKED_PH)
+ return std::make_shared<SHAMapPreHashedLeafNode>(
+ std::move(item), owner);
+
LogicError(
"Attempt to create leaf node of unknown type " +
std::to_string(
static_cast<std::underlying_type_t<SHAMapNodeType>>(type)));
}
-SHAMap::SHAMap(SHAMapType t, Family& f)
+SHAMap::
+SHAMap(SHAMapType t, Family& f)
: f_(f), journal_(f.journal()), state_(SHAMapState::Modifying), type_(t)
{
root_ = std::make_shared<SHAMapInnerNode>(cowid_);
@@ -60,7 +66,8 @@ SHAMap::SHAMap(SHAMapType t, Family& f)
// from the parameters that this is the constructor to use when the hash is
// known. The fact that the parameter is unused is an implementation detail that
// should not change the interface.
-SHAMap::SHAMap(SHAMapType t, uint256 const& hash, Family& f)
+SHAMap::
+SHAMap(SHAMapType t, uint256 const& hash, Family& f)
: f_(f), journal_(f.journal()), state_(SHAMapState::Synching), type_(t)
{
root_ = std::make_shared<SHAMapInnerNode>(cowid_);
diff --git a/src/ripple/shamap/impl/SHAMapTreeNode.cpp b/src/ripple/shamap/impl/SHAMapTreeNode.cpp
index 480a560a2..dc5ef3f4d 100644
--- a/src/ripple/shamap/impl/SHAMapTreeNode.cpp
+++ b/src/ripple/shamap/impl/SHAMapTreeNode.cpp
@@ -30,6 +30,7 @@
#include <ripple/shamap/SHAMapTreeNode.h>
#include <ripple/shamap/SHAMapTxLeafNode.h>
#include <ripple/shamap/SHAMapTxPlusMetaLeafNode.h>
+#include <ripple/shamap/SHAMapPreHashedLeafNode.h>
#include <mutex>
#include <openssl/sha.h>
diff --git a/src/test/shamap/SHAMap_test.cpp b/src/test/shamap/SHAMap_test.cpp
index 182b443ce..99aab3469 100644
--- a/src/test/shamap/SHAMap_test.cpp
+++ b/src/test/shamap/SHAMap_test.cpp
@@ -398,7 +398,36 @@ class SHAMapPathProof_test : public beast::unit_test::suite
}
};
+class SHAMapPreHashed_test : public beast::unit_test::suite
+{
+ void
+ run() override
+ {
+ testcase(
+ "test synthesize txTreeHash txResultHash from txId/txResultHash");
+ test::SuiteJournal journal("SHAMapPreHashed_test", *this);
+
+ tests::TestNodeFamily tf{journal};
+ SHAMap map{SHAMapType::FREE, tf};
+ map.setUnbacked();
+
+ auto txTreeHash = uint256(
+ "35DDF481D97D15D4F03E0B180C8B7A1AC59C39B20E6116172035D723CC273943");
+ auto txId = uint256(
+ "F300B5885B54CBA2F72ACE9B8299969F12203E167CA623F0CF23D22C9E9C0FFC");
+ auto txResultHash = strUnHex(
+ "825707D738FBD15D3BF01C21304595264A393762121982106AD30BDBD98F50C9");
+
+ map.addItem(
+ SHAMapNodeType::tnNON_BACKED_PH,
+ SHAMapItem{txId, makeSlice(*txResultHash)});
+
+ BEAST_EXPECT(map.getHash().as_uint256() == txTreeHash);
+ }
+};
+
BEAST_DEFINE_TESTSUITE(SHAMap, ripple_app, ripple);
BEAST_DEFINE_TESTSUITE(SHAMapPathProof, ripple_app, ripple);
+BEAST_DEFINE_TESTSUITE(SHAMapPreHashed, ripple_app, ripple);
} // namespace tests
} // namespace ripple
Oops, the diff got messed up before.
Worth considering to keep ledger header + validations & co as an entity distinct from the transaction[s] of interest. Given they are "reusable"?
@nbougalis
Ideas? With this you can use hashes of serialized inners as "leaves" for verifying abbreviated trees?
edit: Now a little more familiar with the rippled SHAMap I can see you can just use:
SHAMap::getProofPath(uint256 const& key) SHAMap::verifyProofPath(
or something like it
Though not sure how easy it would be to create abbreviated maps with multiple entries, without getting too entangled in the node store. Unbacked and ?
https://github.com/XRPLF/XRPL-Standards/discussions/107#discussioncomment-7097514 by @sublimator