Consider accepting new Phragmén solutions if they are _significantly_ better

[kianenigma]

I have some interesting dumps from kusama blocks and the solutions that are being submitted.

Two concerns:

1. It seems like solutions that not strictly better are also being submitted. The logs are from recent to old, so as we go back, for example score[3] should always increase. This is not the case all the time and it could potentially be a bug. Although I can't see how we could have done this wrong:

pub fn is_score_better(this: PhragmenScore, that: PhragmenScore) -> bool {
	match that
		.iter()
		.enumerate()
		.map(|(i, e)| e.cmp(&this[i]))
		.collect::<Vec<Ordering>>()
		.as_slice()
	{
		[Ordering::Greater, _, _] => true,
		[Ordering::Equal, Ordering::Greater, _] => true,
		[Ordering::Equal, Ordering::Equal, Ordering::Less] => true,
		_ => false,
	}
}

and we run this in the validate_unsigned, hence validators can only include this transaction if it is better than the on chain value.. which does not make a lot sense here. Sadly the logs of staking are currently native only and we cannot see them on kusama. I will have to move them to wasm as they make debugging this easier.

UPDATE: looking more into the logs, I see even solutions that are submitted but are evidently worse than the ones submitted before (score[0] is worse). I should scrape the events of these blocks as well and see of these were successful calls. But I am not sure how they could have failed? maybe due to re-org they were seeing the wrong state? if so, this means that validators could submit wrong solutions and we should be careful and not fix #5980 before we figure out what is going on here.

2. Perhaps we could only accept solutions if they are considerably better? we have already discussed this and now's a good time to do it.

---

[Era 817] Submit election solution with score [15916084254215304, 5451470256512367441, 123039029234580089427706980618599821]
[Era 817] Submit election solution with score [15916084254215304, 5451470256512367441, 123043934568722704366203240019953661]
[Era 816] Submit election solution with score [15916084254215304, 5418938198020661168, 121617825361826979619997948514236550]
[Era 816] Submit election solution with score [15916084254215304, 5418938198020661168, 121599494548091058466750880588585294]
[Era 816] Submit election solution with score [15916084254215304, 5418938198020661168, 121605926185214904093798747492082646]
[Era 815] Submit election solution with score [15264072350652323, 5425703221578011057, 122747961347662072618349837621633179]
[Era 815] Submit election solution with score [15264072350652323, 5425703221578011057, 122756333711055503020492328372220493]
[Era 815] Submit election solution with score [15264072350652323, 5425703221578011057, 122772146469471221914815014319314117]
[Era 815] Submit election solution with score [15264072350652323, 5425703221578011057, 122843499819676101598492044159085471]
[Era 815] Submit election solution with score [15264072350652323, 5425703221578011057, 123087341468947963343023154537560033]
[Era 814] Submit election solution with score [15264072350652323, 5434228288291962619, 123072369250362404868259941192465897]
[Era 814] Submit election solution with score [15264072350652323, 5434228288291962619, 123083351673445131173657109850691091]
[Era 814] Submit election solution with score [15264072350652323, 5434228288291962619, 123484879745905350876999583900066019]
[Era 814] Submit election solution with score [15264072350652323, 5434228288291962619, 123110872104516293442507970168682407]
[Era 814] Submit election solution with score [15264072350652323, 5434228288291962619, 123484879745905350876999583900066019]
[Era 814] Submit election solution with score [15122365774888700, 5434228288291962619, 128013126955357685575874068133334527]
[Era 813] Submit election solution with score [15264072350652323, 5392749348582584246, 121014648647272365719225363288676038]
[Era 813] Submit election solution with score [15264072350652323, 5392749348582584246, 121024589536812484682042802249930022]
[Era 812] Submit election solution with score [15125497825589380, 5422391586917954590, 122316609687103436729041205953798664]
[Era 812] Submit election solution with score [15125497825589380, 5422391586917954590, 122343158930150489846851671286022722]
[Era 811] Submit election solution with score [15125497825589380, 5414775639531972444, 122034166029946369460064346558578808]
[Era 811] Submit election solution with score [15125497825589380, 5414775639531972444, 122063230341387544762365899087744606]
[Era 811] Submit election solution with score [15125497825589380, 5414775639531972444, 122172955129676419132524144871488840]
[Era 811] Submit election solution with score [14733245325588070, 5414775639531972444, 127003124887109880983951542753252906]
[Era 810] Submit election solution with score [15125497825589380, 5414040589241860236, 122002801398816969910619825563968380]
[Era 810] Submit election solution with score [15125497825589380, 5414040589241860236, 122010899638890473288033522667796888]
[Era 809] Submit election solution with score [15125497825589380, 5387106563066224256, 122022172643311052620182940238441506]
[Era 809] Submit election solution with score [15125497825589380, 5387106563066224256, 122419299074691067016669004304868174]
[Era 809] Submit election solution with score [13811377767374729, 5387106563066224256, 127475608273106591847141468911710078]
[Era 808] Submit election solution with score [13877751320468823, 5340835763226877621, 125903337480972032946849165587569879]
[Era 808] Submit election solution with score [15125497825589380, 5340835763226877621, 120208836484365386449026804736239257]
[Era 808] Submit election solution with score [15125497825589380, 5340835763226877621, 120226616231414461171982896149529161]
[Era 808] Submit election solution with score [15125497825589380, 5340835763226877621, 120256046700645792695682185856685473]
[Era 807] Submit election solution with score [15125497825589380, 5344934041546056628, 120690846337491189845388851711222032]
[Era 807] Submit election solution with score [15125497825589380, 5344934041546056628, 120181554562933994576119854641408370]
[Era 807] Submit election solution with score [15125497825589380, 5344934041546056628, 120199890272556578241165741329900558]
[Era 806] Submit election solution with score [15125497825589380, 5341174100063245678, 120134902275702640063079106270432442]
[Era 806] Submit election solution with score [13526891004510898, 5341174100063245678, 126338599694426717757686642536065356]
[Era 806] Submit election solution with score [15125497825589380, 5341174100063245678, 120164637287617400009648173590593272]
[Era 806] Submit election solution with score [15125497825589380, 5341174100063245678, 120794947137807609818014136107468436]
[Era 805] Submit election solution with score [15000000000000000, 5340716340720047515, 120119373757137287895828227244995911]
[Era 805] Submit election solution with score [15000000000000000, 5340716340720047515, 120149275051841355039537758186802385]
[Era 805] Submit election solution with score [15000000000000000, 5340716340720047515, 120196730233880627927881249175329347]
[Era 804] Submit election solution with score [15000000000000000, 5319044037790430074, 118558679911536602628440203437745672]
[Era 803] Submit election solution with score [15000000000000000, 5321487138291321978, 118677873572788353441766938010965978]
[Era 803] Submit election solution with score [14766795539566894, 5321487138291321978, 119331296758049017863987013256996986]
[Era 802] Submit election solution with score [15000000000000000, 5319999193739990118, 118031926029924432618805080240677492]
[Era 802] Submit election solution with score [15000000000000000, 5319999193739990118, 118101973481723499889904252171680270]
[Era 801] Submit election solution with score [15000000000000000, 5318294042317167609, 117996207647827778581067587018073181]
[Era 801] Submit election solution with score [15000000000000000, 5318294042317167609, 117968896213714142123351050377143487]
[Era 800] Submit election solution with score [15000000000000000, 5317739903862014284, 117933463439538521946443830397642014]
[Era 800] Submit election solution with score [15000000000000000, 5317739903862014284, 117869660914714302429403296782741292]
[Era 800] Submit election solution with score [15000000000000000, 5317739903862014284, 117892787649995506559662369371066442]
[Era 800] Submit election solution with score [15000000000000000, 5317739903862014284, 117933463439538521946443830397642014]
[Era 799] Submit election solution with score [14188686967424092, 5302800399850640636, 117685179360908234604606617279985546]
[Era 799] Submit election solution with score [15000000000000000, 5302800399850640636, 116980998982747130130116075192448356]
[Era 798] Submit election solution with score [14331510673157584, 5302400749776089056, 117772482306555171148475730627713582]
[Era 798] Submit election solution with score [14331510673157584, 5302400749776089056, 117812376613610639506592205695178538]
[Era 798] Submit election solution with score [9669876530992787, 5302400749776089056, 126914811124408741962938678223815188]
[Era 798] Submit election solution with score [14331510673157584, 5302400749776089056, 117888952461605435805771210796323728]
[Era 798] Submit election solution with score [14228873043535375, 5302400749776089056, 118086040574286917202445459728661752]
[Era 798] Submit election solution with score [9669876530992787, 5302400749776089056, 126914811124408741962938678223815188]
[Era 797] Submit election solution with score [11551065764257152, 5296858374460426634, 117604461670041331783052073029567992]
[Era 797] Submit election solution with score [11551065764257152, 5296858374460426634, 117857326930915593203928134112547972]
[Era 796] Submit election solution with score [15853357618066682, 5254508822571199278, 126879406270047054559714457575598830]
[Era 796] Submit election solution with score [15853357618066682, 5254508822571199278, 126900998686204598950456298002749376]
[Era 796] Submit election solution with score [15853357618066682, 5254508822571199278, 127297799945337620017845157514900138]
[Era 795] Submit election solution with score [15853357618066682, 5245742282968681254, 126568076671353242290650081626764246]
[Era 795] Submit election solution with score [15853357618066682, 5245742282968681254, 127032313204718591080508243144196784]
[Era 794] Submit election solution with score [15853357618066682, 5278071634321877954, 147116986780831340677130000058483708]
[Era 794] Submit election solution with score [15853357618066682, 5278071634321877954, 147215266014156555702848357325558338]
[Era 794] Submit election solution with score [15853357618066682, 5278071634321877954, 147416180819196025273455643834769896]
[Era 793] Submit election solution with score [15853357618066682, 5221846860011783907, 144630032330321563982874172403879989]
[Era 793] Submit election solution with score [15853357618066682, 5221846860011783907, 144632172520194994414983964371669027]
[Era 792] Submit election solution with score [15853357618066682, 5225542664082556878, 145244120115100533519039648847989834]
[Era 792] Submit election solution with score [15853357618066682, 5225542664082556878, 144988468029508117731708142563503142]
[Era 792] Submit election solution with score [15853357618066682, 5225542664082556878, 144990407275959074239631352392513548]
[Era 791] Submit election solution with score [15507128696316519, 5169059106142058405, 142592150549225695004917611536648941]
[Era 791] Submit election solution with score [15507128696316519, 5169059106142058405, 142570346964113885711695884814281265]
[Era 791] Submit election solution with score [15507128696316519, 5169059106142058405, 142592150549225695004917611536648941]
[Era 790] Submit election solution with score [16496000000000000, 5182073369607702862, 122969675606770689419129318594141226]
[Era 790] Submit election solution with score [16496000000000000, 5182073369607702862, 122988842254949505608782263990486832]
[Era 790] Submit election solution with score [16496000000000000, 5182073369607702862, 123067880998930478162936952186480060]
[Era 790] Submit election solution with score [16496000000000000, 5182073369607702862, 126891826545859764816411298107682722]
[Era 789] Submit election solution with score [16494980000000000, 5184570910203613673, 122960097393468769220181487559522655]
[Era 789] Submit election solution with score [16494980000000000, 5184570910203613673, 122960097393468769220181487559522655]
[Era 789] Submit election solution with score [16494980000000000, 5184570910203613673, 122968336336105625643395490317109997]
[Era 788] Submit election solution with score [15853371868467231, 5179535057145903726, 128453082041194795761033807596290180]
[Era 788] Submit election solution with score [15853357618066682, 5179535057145903726, 122895411358252738232894666955473302]
[Era 787] Submit election solution with score [16494980000000000, 5163633325258202236, 122173560312219012094939450526050238]
[Era 787] Submit election solution with score [16494980000000000, 5163633325258202236, 122765799188339506850424066670717034]
[Era 787] Submit election solution with score [16494980000000000, 5163633325258202236, 122188162578814280854263264188281880]
[Era 787] Submit election solution with score [16494980000000000, 5163633325258202236, 122268835575179069347722467680489250]
[Era 786] Submit election solution with score [15853357618066682, 5166173876969009513, 122552193700336129515326533870466217]
[Era 786] Submit election solution with score [15853357618066682, 5166173876969009513, 122587572070834293254263555450851593]
[Era 785] Submit election solution with score [16494980000000000, 5172348320065473252, 122693849411190160155742747018214444]
[Era 784] Submit election solution with score [16494980000000000, 5191912541598247960, 123391840932746222961136968421384202]
[Era 784] Submit election solution with score [16494980000000000, 5191912541598247960, 123397481117961203380688498871763210]
[Era 784] Submit election solution with score [16494980000000000, 5191912541598247960, 123517238650158172843416002282967826]
[Era 783] Submit election solution with score [16494980000000000, 5165929019146530255, 122247288247191027024525674666364279]
[Era 783] Submit election solution with score [16494980000000000, 5165929019146530255, 122252411451825947610804368176312225]
[Era 782] Submit election solution with score [16494980000000000, 5165361708531457829, 122237851176134324919020172722277433]
[Era 782] Submit election solution with score [16494980000000000, 5165361708531457829, 122262381505206784541844574433815609]
[Era 782] Submit election solution with score [16494980000000000, 5165361708531457829, 122335934238493626818124782446644033]
[Era 781] Submit election solution with score [16494980000000000, 5165200801726277589, 122233844836299391878311891447013133]
[Era 781] Submit election solution with score [16494980000000000, 5165200801726277589, 122241123131373248029054820730664397]
[Era 781] Submit election solution with score [16494980000000000, 5165200801726277589, 122259337842437186878397472121662981]
[Era 780] Submit election solution with score [16494980000000000, 5097408639603403347, 118304746244429960858394409414750749]
[Era 780] Submit election solution with score [16494980000000000, 5097408639603403347, 118366183345271864155684396436138445]
[Era 780] Submit election solution with score [16494980000000000, 5097408639603403347, 118490437562755718173921719943700217]
[Era 779] Submit election solution with score [16494980000000000, 5082907921119631328, 117653577871674091392529028249232492]
[Era 779] Submit election solution with score [16494980000000000, 5082907921119631328, 117659719343625900499835628668987420]
[Era 779] Submit election solution with score [16494980000000000, 5082907921119631328, 117995688219777003658955289918233262]
[Era 779] Submit election solution with score [15643065941479813, 5082907921119631328, 122135798078031382929947569371748368]
[Era 778] Submit election solution with score [16494980000000000, 5106223372111364343, 118642492409243177636426410204646251]
[Era 777] Submit election solution with score [16494980000000000, 5084878642965987696, 117717500377690459052744639134681958]
[Era 777] Submit election solution with score [16494980000000000, 5084878642965987696, 117741674800510153962809478165265508]
[Era 777] Submit election solution with score [16494980000000000, 5084878642965987696, 117725157305880769774516578018028480]
[Era 776] Submit election solution with score [16494980000000000, 5084435767193590072, 117737923783952073733425033520168996]
[Era 776] Submit election solution with score [16494980000000000, 5084435767193590072, 117757704861666003051324107631864544]
[Era 775] Submit election solution with score [16494980000000000, 5098804886800565244, 118440719406481060232150706565650678]
[Era 775] Submit election solution with score [16494980000000000, 5098804886800565244, 118458085611062131862130823273075394]
[Era 775] Submit election solution with score [16494980000000000, 5098804886800565244, 118491743863585716958515409335947580]
[Era 774] Submit election solution with score [16494980000000000, 5093013411332946299, 118045233172398309319310084699047581]
[Era 774] Submit election solution with score [16494980000000000, 5093013411332946299, 118047993436451693390213635136658583]
[Era 774] Submit election solution with score [16494980000000000, 5093013411332946299, 118096619795674647016597538811091717]
[Era 774] Submit election solution with score [16494980000000000, 5093013411332946299, 118286808768679825006751339749134063]
[Era 773] Submit election solution with score [16494980000000000, 5109910916386815131, 118771117482304025239654430086959755]
[Era 772] Submit election solution with score [15398645681900949, 5065020142276310529, 123589867646000335255748576014789779]
[Era 772] Submit election solution with score [16494980000000000, 5065020142276310529, 118327442692336319291186073210050639]
[Era 772] Submit election solution with score [16494980000000000, 5065020142276310529, 118329324166650115868821872399578959]
[Era 772] Submit election solution with score [15398645681900949, 5065020142276310529, 123589867646000335255748576014789779]
[Era 771] Submit election solution with score [16494980000000000, 5001530217552564530, 114598398130820864523206469782463796]
[Era 771] Submit election solution with score [16494980000000000, 5001530217552564530, 114637104621300844740853805815268452]
[Era 771] Submit election solution with score [16494980000000000, 5001530217552564530, 114602060738931328136524396872557484]
[Era 770] Submit election solution with score [16494980000000000, 5001865040328822172, 115422009446117911377468564125087462]
[Era 770] Submit election solution with score [16494980000000000, 5001865040328822172, 115433043683942831116668041434071832]
[Era 770] Submit election solution with score [16494980000000000, 5001865040328822172, 115476465004004743497215917671893088]
[Era 769] Submit election solution with score [16494980000000000, 4978457305264751700, 114396127897883099836507660350388334]
[Era 769] Submit election solution with score [16494980000000000, 4978457305264751700, 114407461622796173185643494928034530]
[Era 768] Submit election solution with score [16494980000000000, 4965423631927940122, 112780242140088255899208193880743022]
[Era 767] Submit election solution with score [16494980000000000, 4963652704259776774, 112753885028233165655871922146676180]
[Era 767] Submit election solution with score [16494980000000000, 4963652704259776774, 112715678148438749367835212754812696]
[Era 767] Submit election solution with score [16494980000000000, 4963652704259776774, 112730351708104768319649222693051066]
[Era 766] Submit election solution with score [16494980000000000, 4963130070605945758, 112729240524102844089382279182345216]
[Era 766] Submit election solution with score [16494980000000000, 4963130070605945758, 112729240524102844089382279182345216]
[Era 766] Submit election solution with score [16483432878636022, 4963130070605945758, 112869896375584478961482092537518404]
[Era 765] Submit election solution with score [16494980000000000, 4952340056015398396, 112186996232916930476439743481479544]
[Era 764] Submit election solution with score [15801189902139231, 4949664041742509782, 112175277861040614967259394941150894]
[Era 764] Submit election solution with score [15801189902139231, 4949664041742509782, 112223002168334109547257303269371400]
[Era 764] Submit election solution with score [15542640430754455, 4949664041742509782, 112534991650103808668211652158275396]
[Era 763] Submit election solution with score [15759560317553036, 4981618458285740769, 113605302636800213384187158247263255]
[Era 763] Submit election solution with score [15518436660015930, 4981618458285740769, 113962662399712356714549770641009455]
[Era 762] Submit election solution with score [15607768392173518, 4941279906148416450, 111972383589454050006306150271904774]
[Era 762] Submit election solution with score [15604360461184721, 4941279906148416450, 111985091646371852852425062248813054]
[Era 762] Submit election solution with score [15596884074831016, 4941279906148416450, 112006797274739447621164868686086496]
[Era 762] Submit election solution with score [15578232990270611, 4941279906148416450, 112071272451361016014149961056511824]
[Era 761] Submit election solution with score [15492295656106959, 4943979072848648868, 112048798489228851666182550077773104]
[Era 760] Submit election solution with score [15210741979996813, 4936156685093265908, 111983091626547750423649327219908660]
[Era 760] Submit election solution with score [13947075959482550, 4936156685093265908, 117702768585941328297764201257032450]
[Era 760] Submit election solution with score [15210741979996813, 4936156685093265908, 111985729893410050751534332657799808]

cc @tomusdrw @AlfonsoCev

[tomusdrw]

Are all these solutions included in blocks? Isn't that just output of validate_transaction?
If we have a bunch of transactions that submit the solution present in the pool at the same time validate_transaction is only comparing each one of them against the current state in isolation - so we can't figure out that there are some other solutions in the pool that are better.

If that is a problem perhaps having a two-phase approach would help, where you first only commit the score and only if you win this on-chain auction are you required to reveal the actual solution?

[tomusdrw]

Perhaps we could only accept solutions if they are considerably better? we have already discussed this and now's a good time to do it.

That sound sensible as well, since afaiu accepting a solution is quite costly and the score improvement might not be worth the cost of the change.

[gui1117]

1. It seems like solutions that not strictly better are also being submitted. The logs are from recent to old, so as we go back, for example score[3] should always increase. This is not the case all the time and it could potentially be a bug. Although I can't see how we could have done this wrong:

I think this is not an issue, I can double check but I'm pretty sure that weak solution are not successful, also including a weak solution is cheap it is just comparing the scores. and with #6032 it won't even consume weight.

Having some extrinsic which returns error in pre_dispatch_checks can happen, I don't think this is a bug.

EDIT: I doubled check with queryStorage, the queuedscore only change with better score. so the weak submission doesn't change the queued score.

2. Perhaps we could only accept solutions if they are considerably better? we have already discussed this and now's a good time to do it.

Actually in your data set there is:

• 58 eras, 19 weak submission and 141 not weak submission.
  So we have 2.5 submission per era, 0.33 invalid weak submission per era.

I think these number are quite fine already.

EDIT: this message has been edited, I mixed myself in my tests but I'm confident with result now

[kianenigma]

Are all these solutions included in blocks? Isn't that just output of validate_transaction?

I scraped the getBlock RPC, so as far as I know, yes they are included. But perhaps some were not successful and caused error? For that I have to scrape the events of each block as well.

If we have a bunch of transactions that submit the solution present in the pool at the same time validate_transaction is only comparing each one of them against the current state in isolation - so we can't figure out that there are some other solutions in the pool that are better.

Yeah, but this will never happen anyhow because we will not propagate anything. In each node's transaction pool, there will ever be the state and potentially one and only one solution transaction that the next block author intends to add to the block.

If that is a problem perhaps having a two-phase approach would help, where you first only commit the score and only if you win this on-chain auction are you required to reveal the actual solution?

Maybe, but I first want to decode what is going on here and with the current system.

---

Actually in your data set there is:

58 eras, 19 weak submission and 141 not weak submission.
So we have 2.5 submission per era, 0.33 invalid weak submission per era.

it might be fine as in it is not burning the chain 😀 but the intention here is that ideally, the validators, unless if they are stuck in some fork or out of sync for any reason, must always submit strictly better solutions, because the code in validate_unsigned should prevent it in ideal conditions.

Preferably we must minimise failure before #5980

---

I will try and update this next week with scraping some events. Should give more insight.

[kianenigma]

I have a new log. Note the block and era numbers to get the ordering correct. The order of logs top to bottom is new to old, but within an era, the line of logs is top to bottom old to new. Prefix meanings:

• 🤑: first submission of era.
• ✅: better submission
• ❌: worse submission.

https://gist.github.com/kianenigma/d331a7de720bb87c96c661d6221c861e

and as for the errors, 16 is indeed WeakSubmission error, Although I see one EarlySubmission as well.
and as expected all the worse ones fail. So the logic is sound, but I was a bit worried why our validators do this. @tomusdrw my best suspect is simply that they were out of sync on a fork. WDYT?

[AlfonsoCev]

For the comparison function, we can define an improvement parameter x, for instance x = 1.01, and then do the following comparison:

IF (
( this.score1 > x * that.score1 )
OR ( this.score1 >= that.score1 AND this.score2 > x * that.score2 )
OR ( this.score1 >= that.score1 AND this.score2 >= that.score2 AND x * this.score3 < that.score3 )
)
THEN accept.

Looking at the log, it looks like most new submissions are only better off by a tiny amount, less than 0.2 percent in one of the scores, with respect to the current best solution. So if we require an improvement of at least 1 percent in one of the scores, we'd have a lot fewer submissions.

[tomusdrw]

After chatting with @kianenigma we have a theory why this happens.

1. The validator executes OCW code and produces a transaction.
2. The solution is valid and is better than the one currently on-chain.
3. Few external blocks are imported, also ones that contain a better solution.
4. Then it's finally our validator's turn to produce a block, so it takes the transactions from the pool, but their's validity is stale already.

Now usually, when we push such transaction to a block, we will end up running pre_dispatch, which by default calls validate_transaction again. If the transaction is invalid, we won't go to dispatch phase, but rather restrain from putting such transaction to a block.
However in case of phragmén solutions, the pre_dispatch of UnsignedValidator is overwritten so that it always return Ok, which causes the transaction to fail only during dispatch phase, but at this point we have to keep such transaction in the block.

So it seems that the solution to ❌ transactions is to remove the pre_dispatch optimization, but having a minimal score improvement is sensible as well.