Repository: LNP-BP/client_side_validation (language: rust)

Issue:
Increase multi-protocol commitment tree size limit
Currently, MPC trees (LNPBP-4) are limited to a maximum depth of 2^4 = 16, i.e. they may contain up to 2^16=65536 elements. The original design assumed that's enough to host all assets which may be allocated to a single UTXO.

However, tests do show that even 127 different assets may not UNIQUELY fit into a tree with width=655536 (the position of the asset is 256-bit asset id modulo size of the tree) and practically we can assume just around 64 assets to be assignable to the same UTXO.

Here I propose extending MPC tree depth to 32 and tree width to 2^32 such that the tree may host up to 16000 separate assets (no of assets < 2^(width / 2 - 2))


Discussion / hints:
With depth of 64 we will have 2^64 tree width and can safely have up to 1 billion of assets on the same UTXO (however the inclusion proofs for an asset may grow up to 64 * 256 = 16kB).
An alternative approach (or the one which may be combined with the proposed one) to achieve better packing efficiency if we allow non-power-2 tree width.
Is this a consensus-breaking change?

If we're going to extend it, would it be okay to make it 64? The reason I ask is for futureproofing purposes; one of the advantages of RGB is its capability to scale. The alternative of course is to have multiple UTXOs, but ideally this complexity isn't necessary to scale.

I can see assets getting into the billions one day if assets from other chains are bridgeburnt to RGB contracts often. There are likely applications we can't imagine, but billions offers a great deal of flexibility.
It is a consensus-breaking change, but we already had one in the required bugfix in https://github.com/LNP-BP/client_side_validation/pull/129 so I'd like to use the opportunity and make other improvements (like this one) as well.

I was also thinking about 64 bits - the only drawback is that it may worsen work with hardware and low-end devices. A tree of 64 depth will have 2^64+2^32+..., i.e. ~18 quintillions of nodes, which must be computed at state transition time. Sounds like a performance & scalability killer.

So I am also thinking about improving the "fitness" of the protocols into smaller-size trees by introducing a co-factor. I expect this approach will allow us to fit into a 16-bit depth tree up to 10000 assets - and up to a million into a 24-bit depth tree. Writing a PR demonstrating that.

Fix patch:
diff --git a/commit_verify/src/mpc/block.rs b/commit_verify/src/mpc/block.rs
index 5db27389..1eb3a55b 100644
--- a/commit_verify/src/mpc/block.rs
+++ b/commit_verify/src/mpc/block.rs
@@ -116,6 +116,11 @@ pub struct MerkleBlock {
     #[getter(as_copy)]
     depth: u4,
 
+    /// Cofactor is used as an additive to the modulo divisor to improve packing
+    /// of protocols inside a tree of a given depth.
+    #[getter(as_copy)]
+    cofactor: u16,
+
     /// Tree cross-section.
     #[getter(skip)]
     cross_section: SmallVec<TreeNode>,
@@ -148,6 +153,7 @@ impl From<&MerkleTree> for MerkleBlock {
 
         MerkleBlock {
             depth: tree.depth,
+            cofactor: tree.cofactor,
             cross_section,
             entropy: Some(tree.entropy),
         }
@@ -169,7 +175,7 @@ impl MerkleBlock {
         let mut pos = proof.pos;
         let mut width = proof.width() as u16;
 
-        if protocol_id_pos(protocol_id, width) != pos {
+        if protocol_id_pos(protocol_id, proof.cofactor, width) != pos {
             return Err(UnrelatedProof);
         }
 
@@ -201,6 +207,7 @@ impl MerkleBlock {
 
         Ok(MerkleBlock {
             depth: u4::with(path.len() as u8),
+            cofactor: proof.cofactor,
             cross_section,
             entropy: None,
         })
@@ -480,6 +487,7 @@ Changed commitment id: {}",
         );
         Ok(MerkleProof {
             pos: self.protocol_id_pos(protocol_id),
+            cofactor: self.cofactor,
             path: SmallVec::try_from_iter(map.into_values())
                 .expect("tree width guarantees are broken"),
         })
@@ -493,7 +501,7 @@ Changed commitment id: {}",
 
     /// Computes position for a given `protocol_id` within the tree leaves.
     pub fn protocol_id_pos(&self, protocol_id: ProtocolId) -> u16 {
-        protocol_id_pos(protocol_id, self.width())
+        protocol_id_pos(protocol_id, self.cofactor, self.width())
     }
 
     /// Computes the width of the merkle tree.
@@ -551,6 +559,10 @@ pub struct MerkleProof {
     #[getter(as_copy)]
     pos: u16,
 
+    /// Cofactor used by the Merkle tree.
+    #[getter(as_copy)]
+    cofactor: u16,
+
     /// Merkle proof path consisting of node hashing partners.
     #[getter(skip)]
     path: SmallVec<MerkleNode>,
diff --git a/commit_verify/src/mpc/tree.rs b/commit_verify/src/mpc/tree.rs
index 2880cb71..58abe424 100644
--- a/commit_verify/src/mpc/tree.rs
+++ b/commit_verify/src/mpc/tree.rs
@@ -30,6 +30,10 @@ use crate::mpc::atoms::Leaf;
 use crate::mpc::{Commitment, Message, MessageMap, Proof, ProtocolId, MERKLE_LNPBP4_TAG};
 use crate::{CommitmentId, Conceal, LIB_NAME_COMMIT_VERIFY};
 
+/// Number of cofactor variants tried before moving to the next tree depth.
+#[allow(dead_code)]
+const COFACTOR_ATTEMPTS: u16 = 500;
+
 type OrderedMap = SmallOrdMap<u16, (ProtocolId, Message)>;
 
 /// Complete information about LNPBP-4 merkle tree.
@@ -45,6 +49,10 @@ pub struct MerkleTree {
     /// Entropy used for placeholders.
     pub(super) entropy: u64,
 
+    /// Cofactor is used as an additive to the modulo divisor to improve packing
+    /// of protocols inside a tree of a given depth.
+    pub(super) cofactor: u16,
+
     /// Map of the messages by their respective protocol ids
     pub(super) messages: MessageMap,
 
@@ -124,40 +132,47 @@ mod commit {
             let mut map = BTreeMap::<u16, (ProtocolId, Message)>::new();
 
             let mut depth = source.min_depth;
+            let mut prev_width = 1;
             loop {
-                map.clear();
                 let width = 2usize.pow(depth.to_u8() as u32) as u16;
-                if source.messages.iter().all(|(protocol, message)| {
-                    let pos = protocol_id_pos(*protocol, width);
-                    map.insert(pos, (*protocol, *message)).is_none()
-                }) {
-                    break;
+                if width as usize >= msg_count {
+                    for cofactor in 0..=(prev_width.min(COFACTOR_ATTEMPTS)) {
+                        map.clear();
+                        if source.messages.iter().all(|(protocol, message)| {
+                            let pos = protocol_id_pos(*protocol, cofactor, width);
+                            map.insert(pos, (*protocol, *message)).is_none()
+                        }) {
+                            return Ok(MerkleTree {
+                                depth,
+                                entropy,
+                                cofactor,
+                                messages: source.messages.clone(),
+                                map: Confined::try_from(map).expect("MultiSource type guarantees"),
+                            });
+                        }
+                    }
                 }
 
+                prev_width = width;
                 depth = depth
                     .checked_add(1)
                     .ok_or(Error::CantFitInMaxSlots(msg_count))?;
             }
-
-            Ok(MerkleTree {
-                depth,
-                messages: source.messages.clone(),
-                entropy,
-                map: Confined::try_from(map).expect("MultiSource type guarantees"),
-            })
         }
     }
 }
 
-pub(super) fn protocol_id_pos(protocol_id: ProtocolId, width: u16) -> u16 {
-    let rem = u256::from_le_bytes((*protocol_id).into_inner()) % u256::from(width as u64);
+pub(super) fn protocol_id_pos(protocol_id: ProtocolId, cofactor: u16, width: u16) -> u16 {
+    debug_assert_ne!(width, 0);
+    let rem = u256::from_le_bytes((*protocol_id).into_inner()) %
+        u256::from(width.saturating_sub(cofactor as u16).max(1) as u64);
     rem.low_u64() as u16
 }
 
 impl MerkleTree {
     /// Computes position for a given `protocol_id` within the tree leaves.
     pub fn protocol_id_pos(&self, protocol_id: ProtocolId) -> u16 {
-        protocol_id_pos(protocol_id, self.width())
+        protocol_id_pos(protocol_id, self.cofactor, self.width())
     }
 
     /// Computes the width of the merkle tree.
@@ -209,7 +224,7 @@ pub(crate) mod test_helpers {
 
     pub fn make_random_tree(msgs: &BTreeMap<ProtocolId, Message>) -> MerkleTree {
         let src = MultiSource {
-            min_depth: u4::with(0),
+            min_depth: u4::ZERO,
             messages: Confined::try_from_iter(msgs.iter().map(|(a, b)| (*a, *b))).unwrap(),
         };
         MerkleTree::try_commit(&src).unwrap()
@@ -242,7 +257,7 @@ mod test {
             let msgs = make_random_messages(size);
             make_random_tree(&msgs);
         }
-        for exp in 5..=5 {
+        for exp in 5..=8 {
             let size = 2u16.pow(exp);
 
             let msgs = make_random_messages(size);
@@ -321,4 +336,20 @@ mod test {
 
         assert_ne!(id1, id2);
     }
+
+    #[test]
+    fn scalability() {
+        let mut depths = vec![];
+        let mut cofacs = vec![];
+        for _ in 0..10 {
+            let msgs = make_random_messages(500);
+            let tree = make_random_tree(&msgs);
+            depths.push(tree.depth.to_u8());
+            cofacs.push(tree.cofactor);
+        }
+        let davg = depths.iter().map(|v| *v as u32).sum::<u32>() as f32 / 10f32;
+        eprintln!("Depth: avg={davg:.2} {depths:?}");
+        eprintln!("Cofactors: {cofacs:?}");
+        assert!(davg <= 15f32);
+    }
 }
diff --git a/commit_verify/src/stl.rs b/commit_verify/src/stl.rs
index a8143633..7ef901c5 100644
--- a/commit_verify/src/stl.rs
+++ b/commit_verify/src/stl.rs
@@ -24,7 +24,7 @@ use strict_types::{CompileError, LibBuilder, TypeLib};
 use crate::{mpc, LIB_NAME_COMMIT_VERIFY};
 
 pub const LIB_ID_COMMIT_VERIFY: &str =
-    "admiral_brain_school_2HKGewudu2EevLRkSNmf2Dg3vmdmRWm9RtR8rJprwRbq";
+    "orca_galaxy_switch_5tHQbJnWw91SmUJ17cUbZn4dknk38tDadZLuxiMpyQVW";
 
 fn _commit_verify_stl() -> Result<TypeLib, CompileError> {
     LibBuilder::new(libname!(LIB_NAME_COMMIT_VERIFY), tiny_bset! {
diff --git a/stl/CommitVerify@0.1.0.sta b/stl/CommitVerify@0.1.0.sta
index 197b1e8b..219f2330 100644
--- a/stl/CommitVerify@0.1.0.sta
+++ b/stl/CommitVerify@0.1.0.sta
@@ -1,29 +1,30 @@
 -----BEGIN STRICT TYPE LIB-----
-Id: admiral_brain_school_2HKGewudu2EevLRkSNmf2Dg3vmdmRWm9RtR8rJprwRbq
+Id: voyage_cycle_habitat_CeJQJUUYQjdFbrb98rZshpekvQpdABbtrwzjbtZG8Cqb
 Name: CommitVerify
 Dependencies: 
   Std@left_pierre_food_5cmoZctpx98FbTzWTArm3G53pMzUXuRPXmMhuCd8zyXb
 
 DENvbW1pdFZlcmlmeQFEmLwV+shMOSrCdItrzFm26d5WHbcOcsiPPhNvMEQWZgNT
 dGQBA1N0ZAEAnhTM5rGFzKR3ukRjS/osWHGpfgwyt67B32qUUiqTGccCVTQIAApD
-b21taXRtZW50BQEABwAAQCAAC01lcmtsZUJsb2NrBgMFZGVwdGgCRJi8FfrITDkq
+b21taXRtZW50BQEABwAAQCAAC01lcmtsZUJsb2NrBgQFZGVwdGgCRJi8FfrITDkq
 wnSLa8xZtuneVh23DnLIjz4TbzBEFmaeFMzmsYXMpHe6RGNL+ixYcal+DDK3rsHf
-apRSKpMZxwxjcm9zc1NlY3Rpb24ACAEIhQr9zPLB1DQ3wG/TjJss+JZuApZgGezd
-omkHr4SwGwAAAAAAAAAA//8AAAAAAAAHZW50cm9weQAEAgAEbm9uZQAAAAEEc29t
-ZQAFAQAACApNZXJrbGVOb2RlBQEABwAAQCAAC01lcmtsZVByb29mBgIDcG9zAAAC
-BHBhdGgACAFVjTcH+EWGU4DuzEFVJOikmWBR05SCQ/GU9/GRVyPp5gAAAAAAAAAA
-//8AAAAAAAAKTWVya2xlVHJlZQYEBWRlcHRoAkSYvBX6yEw5KsJ0i2vMWbbp3lYd
-tw5yyI8+E28wRBZmnhTM5rGFzKR3ukRjS/osWHGpfgwyt67B32qUUiqTGccHZW50
-cm9weQAACAhtZXNzYWdlcwAKByAAATU3qVEVyOqF3FL3q4HycWVRBSZTlEJXr4kT
-6HvUm7HTAAAAAAAAAAD//wAAAAAAAANtYXAACgACAAUCATCVfuYdYTRZuwUI5OGv
-PWohv9b7+x0xgqd55UV04FaxATU3qVEVyOqF3FL3q4HycWVRBSZTlEJXr4kT6HvU
-m7HTAAAAAAAAAAD//wAAAAAAAAdNZXNzYWdlBQEABwAAQCAAClByb3RvY29sSWQF
-AQAHAABAIAAIVHJlZU5vZGUEAgANY29uY2VhbGVkTm9kZQAGAgVkZXB0aAJEmLwV
-+shMOSrCdItrzFm26d5WHbcOcsiPPhNvMEQWZp4UzOaxhcykd7pEY0v6LFhxqX4M
-Mreuwd9qlFIqkxnHBGhhc2gBVY03B/hFhlOA7sxBVSTopJlgUdOUgkPxlPfxkVcj
-6eYBDmNvbW1pdG1lbnRMZWFmAAYCCnByb3RvY29sSWQBMJV+5h1hNFm7BQjk4a89
-aiG/1vv7HTGCp3nlRXTgVrEHbWVzc2FnZQE1N6lRFcjqhdxS96uB8nFlUQUmU5RC
-V6+JE+h71Jux0w==
+apRSKpMZxwhjb2ZhY3RvcgAAAQxjcm9zc1NlY3Rpb24ACAEIhQr9zPLB1DQ3wG/T
+jJss+JZuApZgGezdomkHr4SwGwAAAAAAAAAA//8AAAAAAAAHZW50cm9weQAEAgAE
+bm9uZQAAAAEEc29tZQAFAQAACApNZXJrbGVOb2RlBQEABwAAQCAAC01lcmtsZVBy
+b29mBgMDcG9zAAACCGNvZmFjdG9yAAABBHBhdGgACAFVjTcH+EWGU4DuzEFVJOik
+mWBR05SCQ/GU9/GRVyPp5gAAAAAAAAAA//8AAAAAAAAKTWVya2xlVHJlZQYFBWRl
+cHRoAkSYvBX6yEw5KsJ0i2vMWbbp3lYdtw5yyI8+E28wRBZmnhTM5rGFzKR3ukRj
+S/osWHGpfgwyt67B32qUUiqTGccHZW50cm9weQAACAhjb2ZhY3RvcgAAAQhtZXNz
+YWdlcwAKByAAATU3qVEVyOqF3FL3q4HycWVRBSZTlEJXr4kT6HvUm7HTAAAAAAAA
+AAD//wAAAAAAAANtYXAACgACAAUCATCVfuYdYTRZuwUI5OGvPWohv9b7+x0xgqd5
+5UV04FaxATU3qVEVyOqF3FL3q4HycWVRBSZTlEJXr4kT6HvUm7HTAAAAAAAAAAD/
+/wAAAAAAAAdNZXNzYWdlBQEABwAAQCAAClByb3RvY29sSWQFAQAHAABAIAAIVHJl
+ZU5vZGUEAgANY29uY2VhbGVkTm9kZQAGAgVkZXB0aAJEmLwV+shMOSrCdItrzFm2
+6d5WHbcOcsiPPhNvMEQWZp4UzOaxhcykd7pEY0v6LFhxqX4MMreuwd9qlFIqkxnH
+BGhhc2gBVY03B/hFhlOA7sxBVSTopJlgUdOUgkPxlPfxkVcj6eYBDmNvbW1pdG1l
+bnRMZWFmAAYCCnByb3RvY29sSWQBMJV+5h1hNFm7BQjk4a89aiG/1vv7HTGCp3nl
+RXTgVrEHbWVzc2FnZQE1N6lRFcjqhdxS96uB8nFlUQUmU5RCV6+JE+h71Jux0w==
+
 
 -----END STRICT TYPE LIB-----
 
diff --git a/stl/CommitVerify@0.1.0.stl b/stl/CommitVerify@0.1.0.stl
index 0757e334..61d8c233 100644
Binary files a/stl/CommitVerify@0.1.0.stl and b/stl/CommitVerify@0.1.0.stl differ
diff --git a/stl/CommitVerify@0.1.0.sty b/stl/CommitVerify@0.1.0.sty
index 5a7f4d5e..44248b5f 100644
--- a/stl/CommitVerify@0.1.0.sty
+++ b/stl/CommitVerify@0.1.0.sty
@@ -1,5 +1,5 @@
 {-
-  Id: admiral_brain_school_2HKGewudu2EevLRkSNmf2Dg3vmdmRWm9RtR8rJprwRbq
+  Id: voyage_cycle_habitat_CeJQJUUYQjdFbrb98rZshpekvQpdABbtrwzjbtZG8Cqb
   Name: CommitVerify
   Version: 0.1.0
   Description: Client-side-validation deterministic commitments
@@ -18,17 +18,21 @@ import left_pierre_food_5cmoZctpx98FbTzWTArm3G53pMzUXuRPXmMhuCd8zyXb as Std
 
 -- ComplexSecondJason0F8mU5NPc8Z5CMnkSFGdF5UxrPsdcBS6B5DCyP5kJPgWc
 data Commitment       :: [Byte ^ 32]
--- GammaOreganoPercent0AQM6QXoLnc4uaWWEG1LotnkWXuSqc2p6kPRVuSBJ4Pa8
+-- CalypsoHorizonDrum0BMAswZq7JFahXpvDc3ykvYgNZL9wNqSo3uG8AYqEp5XG
 data MerkleBlock      :: depth Std.U4 {- LemonMimosaOrder0Be5p7K6Qec6irJPaXb91KNSg5S9bQRAbCaa88E1MmFTC -}
+                       , cofactor U8
                        , crossSection [TreeNode]
                        , entropy U64?
 -- BazaarOrchidJacket06kxYeCatpncbA9UiTdsFbxbxJdU56x6MdmTRkEeGAv6R
 data MerkleNode       :: [Byte ^ 32]
--- ApolloTeacherData0Febuvcuc9aB7ggdYN2snGcS8T2qbsC9KhV7BcAUEuM8G
-data MerkleProof      :: pos U16, path [MerkleNode]
--- SunsetDerbyLotus0FRXLDrgJRdG69ACAX7wUTwFjAGgjm99CjF7jZGN8sYv8
+-- AcrobatWesternRondo0ERsXQXKGftFKWFGLNpVc6EXue4sBLc27rbzH8GrMRrAm
+data MerkleProof      :: pos U16
+                       , cofactor U8
+                       , path [MerkleNode]
+-- StudioRocketSoviet08kSHwezrxSX871UmePuTnF8Dgmsk8HBg4X5hxszg1Ydr
 data MerkleTree       :: depth Std.U4 {- LemonMimosaOrder0Be5p7K6Qec6irJPaXb91KNSg5S9bQRAbCaa88E1MmFTC -}
                        , entropy U64
+                       , cofactor U8
                        , messages {[Byte ^ 32] -> Message}
                        , map {U16 -> ProtocolId, Message}
 -- LondonMagnetCake04ajqScXjJ6wQ5af2zgBFzzP7k1qzD6DXXU28taQidCcA


Test patch: