Fix: Correct Select Median Implementation

[msgmaxim]

Pull Request

Closes: PRO-805

Checklist

Please conduct a thorough self-review before opening the PR.

• I am confident that the code works.
• I have updated documentation where appropriate.

Summary

As proposed in PRO-805, I changed the code to decode values before select_median (which now requires Ord rather than Encode/Decode), so now the comparison is done on integers correctly. For BTC, the median is selected for each field independently.

[linear]

PRO-805 [BUG] Median value is computed incorrectly in witnessing

select_median from decompose_recompose.rs which we use to derive a value "agreed on" by all witnessers is using Scale encoded values when sorting, but that doesn't really work. Specifically for integers Scale uses little endian which means the bytes are "out of order".

For example, given values [1, 8, 32, 256, 768] it returns 1 (the smallest value in this case):

#[test]
fn select_median_test() {
	let mut values = [1_u16, 8, 32, 256, 768].into_iter().map(|v| v.encode()).collect::<Vec<_>>();
	assert_eq!(select_median::<u16>(&mut values).unwrap(), 1);
}

I noticed that we have test_medians tests, but we only test values < 255 where byte order doesn't matter.

For multi-field values (e.g. BitcoinFeeInfo used in bitcoin witnessing) this obviously doesn't work either since sorting will essentially be done on the field encoded first, and the other two will effectively be selected arbitrarily. (This means for example, that you can keep submitting rubbish for the other fields and we will eventually accept them).

daniel kylezs

[codecov]

Codecov Report

Merging #3934 (d2a5ee2) into main (3cfdab0) will increase coverage by 1%.
Report is 9 commits behind head on main.
The diff coverage is 98%.

@@          Coverage Diff           @@
##            main   #3934    +/-   ##
======================================
+ Coverage     71%     73%    +1%     
======================================
  Files        366     367     +1     
  Lines      56773   56037   -736     
  Branches   56773   56037   -736     
======================================
+ Hits       40554   40634    +80     
+ Misses     14210   13345   -865     
- Partials    2009    2058    +49     

Files Changed	Coverage Δ
...chain/runtime/src/chainflip/decompose_recompose.rs	98% <98%> (+3%)	⬆️
state-chain/pallets/cf-witnesser/src/lib.rs	80% <100%> (+2%)	⬆️

... and 77 files with indirect coverage changes

📣 We’re building smart automated test selection to slash your CI/CD build times. Learn more

[kylezs]

we should also test when they're not in order

[kylezs]

also here, good practice to test base case of empty (especially when removing the empty check would result in a panic)

[kylezs]

we should have a test for when the input is empty, that it returns None + doesn't panic