Apr 7, 2024

That sounds right. But to be accurate it’s only certain subsets (by length).

Any duplication presents the possibility. But the actuality is more specific.

Restricted to repetition of 2^i for some nonnegative i

Presumably capable at something. Certainly 1/2 the size of the set. But probably less

Yes, but further restricted such that at depth “i” the set has been collapsed to an odd length.

And not before

Not sure the sizing constraints to be applied. But a linear walk of the TX set can detect the duplicate match. And if there's a first duplicate without subsequent match its already invalid and we can bail.

If a subset is found, then we need a size relation to validate against.

Some invariant between size of set s, size of nonrepeating elements p, and the length of the repeated Txs r such that r itself would require duplication to merge relative to p. So s = p + 2r or s = 2^p + 2^(r-1) is valid and s = 2^p + 2^r is the mallied block

Note that the two forms define p and r differently, not sure which is more convenient for teasing out the relation

In fact, the exponent version is necessarily incorrect or overly restrictive

I'll keep thinking about it. Trying to catch any bad fall right now

s = v + 2r where v = 2^a + 2^b and 2r = 2^b and r is odd?

Re your earlier comments. Detection of the possibility is trivial. A duplicated tx is necessary for the possibility and also invalidates the block. That’s not the problem however. We need to be able to know that the cause of the invalidation is malleation, since that alone precludes caching the invalidity.

Also detecting duplication is expensive relative to a function of set size.

Yes, the comment was that the first failure to match the repetition point after first duplicate is an ejection from detection of the subset. There is no, we'll maybe it has a smaller repeating duplicate later on if scanned from the front. If scanned from the tail I suppose there's no gain

Was intended anyway

K

But even that is wrong I suppose, as the repeating subset could be performed more than once

Or no, that can't be can it due to the size limitations to produce the tree

Lot of thinking in text here, sorry

The exponent of the repeated set length must match the depth of the first odd row in the binary reduction.

Otherwise the merkle duplication either doesn’t occur or occurs too early or late to match the repetition (ie at the necessary depth).

That’s the purpose of the inner loop in the algorithm above.

So repetition of a TX can occur as many times as the padding attempts up the Merkle tree

So if the repetition is 4 hashes (2^2) then the third (0..1..2) reduction must be an odd length set, and the first and second must not be.

Yes, but not a given tx hash, since as you move up the tree you are duplicating a peer leaf node that is a combined hash.

Well, as many times as 2^d where d is the number of duplication points

Merkle is a simple iteration until 1 hash remains, where pairs of leave are hashed into a new row. If the row is odd the last pair is a duplicate.

The mallied TXs could maximally contain a single hash 2^d times

No, because it would not match the hash of the valid block.

When the duplicates are dropped.

The ambiguity results only from a single automatic substitution by Merkle.

So the dups in the original set target that “odd depth” by their width.

A single hash dup implies a valid set with one less node and must be odd length.

So that dup gets applied on the first iteration.

But a 2 hash dup (as in the doc) will only work at an odd depth 2 (second iteration).

So depths must be all even until the target depth, which must be odd. Where the target depth is determined by the dup set length base 2 exponent.

Sounds like you're telling me that the only mallied set can contain a single duplicate sequence of hashes, cool

Yes

The writeups on it are sparse on details, I’ve had to work out the general case rules.

Core scans each entire row for duplicated peers. That would create false positives. In other words, failure to invalidate a hash that has no valid variant.

And it’s inefficient.

The simplest specification I can think of is the iterative algorithm, which I don’t like :/.

Also, there can be more than one mallied set for a malleable valid block. But only one dup set per mallied block is feasible.

Unless of course I’ve missed something.