[DISCUSSION] - BRC-62 - Suggestion for applying sorting on BUMPs list

[dorzepowski]

BRC ID

62

Discussion

I would like to suggest that, when constructing a BEEF transaction, the set of BUMP entries MUST be sorted in ascending order by their respective block height field. This sorting step ensures that any two independent implementations, given the same set of BUMP inputs, will produce an identical ordered sequence of BUMPs and, consequently, the same final BEEF transaction structure.

Rationale and Benefits of Deterministic Ordering:

1. By enforcing a canonical order—sorting by block height—different wallet or node implementations are far more likely to arrive at the same transaction layout. This reduces the risk of discrepancies that might arise from arbitrary ordering choices.
2. Without a mandated ordering, developers could follow different heuristics for BUMP placement, leading to subtle incompatibilities or forcing consumers of the specification to guess the intended order. Deterministic sorting removes this complexity, making it crystal clear how BUMP entries should be arranged.
3. Deterministic ordering simplifies internal and external audits, regression tests, and troubleshooting. When every correctly implemented client will produce the same result, it becomes easier to pinpoint where and how differences occur. This consistency makes it simpler to confirm compliance with the specification.
4. In a multi-party ecosystem, it’s common for different participants to construct or validate BEEF transactions. A deterministic rule ensures that all parties—from miners to wallets—can rely on an unambiguous standard. This stability fosters greater interoperability and trust in the ecosystem.
5. As the specification evolves, having foundational deterministic rules in place reduces the risk that future changes introduce confusion or non-deterministic behavior. A stable, deterministic baseline makes it easier to incorporate new features or modifications down the line.

By integrating deterministic sorting of BUMP entries, the specification’s clarity, reliability, and maintainability improve, benefiting implementers and users alike.

[tonesnotes]

Since all BUMPs must be read from the serialization stream before any transaction that references them, there is no performance advantage obtainable through sort order.

There is no obvious advantage to a canonical ordering. I fail to see how ordering by height has any impact on transaction layout.

The requirements for BEEF validation are clear and unaffected by serialized BUMP ordering.

Perhaps I'm not grasping a critical point, can you give a specific example of what you see happening in a two BUMP BEEF between ordera AB and order BA?

[dorzepowski]

Thank you for your thoughtful engagement on this topic. I’d like to elaborate on the main motivation for introducing sorting of BUMPs within BEEF.

The primary goal is to facilitate broad and valid adoption across different programming languages. When the format is deterministic, it becomes significantly easier to prepare a set of well-defined test cases. These test cases can then be used by developers working in any language to verify that their implementation conforms to the described standard.

Additionally, a deterministic format enhances interoperability between languages. If all implementations conform to the same test cases, we can be nearly certain that a BEEF produced in one language will be correctly consumed and interpreted in another. This alignment is crucial for ensuring seamless data exchange and reducing the risk of compatibility issues.

Another important benefit is the improvement in debugging and auditing. Deterministic output simplifies the process of identifying and resolving discrepancies. This is especially valuable for binary formats like BEEF, where it’s challenging to visually compare two outputs or pinpoint why a difference exists and whether it impacts functionality.

Moreover, having a deterministic format can enable future optimizations in parsers and validators. By making assumptions about the structure of the input, developers can design faster or parallelized algorithms for processing BEEF. This can improve performance, particularly in high-throughput environments, and reduce resource overhead for validation.

Overall, I’d like to share my broader vision: I want to ensure that, one day, BSV will be easy to use in any programming language—from junior to senior developers. To make this a reality, we need to prepare understandable, intuitive, and clean APIs and tools. These should facilitate easy debugging, robust testing, and simple issue investigation. By prioritizing these qualities in our standards and tools, we can make BSV more accessible and developer-friendly across the board.

[tonesnotes]

I agree with the desirability for test cases that are easy to share across languages, visually inspect, and compare easily.

Then what would it take to canonicalize BEEF V1, V2, Atomic and is it justifiable.

First, I claim neither V2 or Atomic impact this discussion.

To Canonicalize V1:

1. BUMPs sort by height, leaves by offset, force no extra leaves.
2. Transactions sort by bump index, but then it gets complicated.

I can't see a way to canonicalize transaction ordering that doesn't add a great many requirements which only serve the canonicalization objective. This is on top of requirements on BUMPs.

Clearly the standard serialized BEEFs in the test suite should all read into any language, but comparing binary serialized BEEFs for binary equality seems too restrictive to be worth it.

The problem with being Transaction.fromBEEF focused in implementing and validating BEEF support is that it only supports the AtomicBEEF view of the data.

Perhaps with the existence of the Beef class which allows piecewise comparison of required BEEF content it is less critical to rely on binary comparison?

[dorzepowski]

Thank you for your insights.

1. I would like to clarify that my primary intention in proposing the sorting of BUMPs is to establish BEEF as a deterministic format. This determinism can be achieved through various sorting parameters. For instance, aligning the BUMP order with the sequence of well-sorted transactions could fulfill this goal and potentially minimize the impact on existing BEEF serializer implementations.

2. Additionally, while you've addressed the aspect of testability, I remain concerned about the implications for debugging and auditing. A deterministic format significantly enhances these processes by providing consistency and predictability, which are crucial for identifying and resolving issues effectively.

Perhaps with the existence of the Beef class which allows piecewise comparison of required BEEF content it is less critical to rely on binary comparison?

Could you elaborate further on how such a class might address the testing concerns I raised and how it could enhance multi-language support? A more concrete use case example would be helpful in evaluating its potential effectiveness.

[tonesnotes]

Could you elaborate further on how such a class might address the testing concerns I raised and how it could enhance multi-language support? A more concrete use case example would be helpful in evaluating its potential effectiveness.

The requirement to support testing in multi-language context can be recast as a requirement for a BEEF equality test function. This could be achieved either by requiring canonical serialization (in which case binary comparison does the trick) or by clearly specifying an equality comparison function.

If the existence of Beef class level functionality in each language is assumed, then we could define equality of Beef A and Beef B as the following, and perhaps we should add such a function to the class:

1. Both A and B conform to the necessary sorting requirement: dependencies before dependents.
2. They contain the same serialized raw transactions.
3. They contain the same txidOnly transactions.
4. Each transaction with a BUMP reference has a MerklePath that computes the same merkle root.

This would be a functional equality comparison check: The two beefs contain the same transaction data and validity support data.

Additional equality checks for specific use cases might include:

5. Both are encoded as the same BEEF version and if Atomic have the same txid.
6. If A is known to have minimally encoded BUMPS (no extra leaves), and the Beef serializations are equal length, then B is also minimally encoded.