ETH-gas 23x verminderen door arrays naar bytes te converteren

Deze maand (aug / sept 2017) bouwde ik mijn eerste Solidity-contract voor de Ethereum Virtual Machine en kwam ik allerlei valkuilen tegen. De eerste was het besef dat enkele van de meest triviale operaties tonnen gas kosten, vooral die waarbij Arrays en Loops betrokken zijn. Mijn contract zat er vol mee en kostte een arm en een been, maar ik realiseerde me een manier om de arrays om te zetten in Bit Strings en Bit Operators te gebruiken voor lezen en schrijven, en vervolgens ze uiteindelijk opslaan als bytes om miljoenen in gas te besparen.

Het contract vereist dat een gebruiker schaaknotatiezetten van een compleet spel Reversi (ook bekend als Othello) instuurt. Als de zetten een geldig spel spelen en als het eindspelbord visueel symmetrisch is, ontvangt de gebruiker een beloning in een ERC20-token. In wezen vervangt het traditionele mijnbouw door het doorzoeken van de enorme spelboom van Reversi als een bewijs van werk met een uitbetaling van een beloning op basis van de zeldzaamheid van de symmetrie (kijk voor meer details op de pagina over). Het zou niet goed zijn voor gebruikers om ongeldige maar symmetrische spellen in te dienen, dus validatie moest plaatsvinden op basis van het contract. (Als je benieuwd bent hoe het project is verlopen, kijk dan op Clovers.network)

Het spel Reversi is vrij eenvoudig te programmeren, maar heeft een erg grote spelboom (geschat op 10⁵⁴ mogelijke bladknooppunten). Daarom was het een goede uitdaging voor heuristisch onderzoek naar games dat dure lookahead wilde vermijden. Bij het modelleren van het spel gebruikt men typisch een tweedimensionale reeks om de toestand van het 8×8 bord bij te houden en een reeks van maximaal 60 zetten (die elk ook een reeks kolom- en rijposities kunnen zijn). Eerst heb ik de Board Array.

aangepakt

BoardArray naar ByteBoard

Ik begon lege vierkanten weer te geven met 0, zwart met 1 (aangezien zwart eerst beweegt) en wit als 2. Hierdoor kon alles binnen de 8×8 boardArray standaard correct worden toegewezen aan een lege 0 ( Solidity heeft geen ongedefinieerde eigenschap, alles staat standaard op een variatie van 0 of false). Dit creëerde een array die er in wezen als volgt uitzag:

Wat net zo goed een hele lange reeks had kunnen zijn, maar weergegeven als een binaire waarde of hexadecimale waarde:

Later op de weg raakte ik gefrustreerd door het voorvoegsel van het juiste aantal nullen als het bord gedeeltelijk leeg was, dus besloot ik de lege 0 te vervangen door een lege 3, want alle 3 passen nog steeds in 2 bits ( 0b11 ), wat alle ruimte was die ik voor elk vierkant op het bord wilde vrijmaken.

Deze nieuwe weergave van het bord is nu zo klein dat het past in 128 bits, wat slechts 16 bytes is (vergeet niet dat het 8 bits per byte is).

Nu hoefde ik alleen maar uit te zoeken hoe ik de bytestring moest lezen en schrijven!

Lezen en schrijven naar ByteBoard

Voor dit deel van het werk ben ik Maksym ongelooflijk dankbaar voor zijn artikel over bitwise-operators in Solidity. Het was eigenlijk de eerste keer dat ik begreep wat bit-operators waren en hoe ze te gebruiken – ik weet dat ik te laat ben, maar beter laat dan nooit. Nadat ik het idee van maskeren had doorgenomen, begon ik met het creëren van een methode om van mijn ByteBoard te lezen.

Lezen van ByteBoard

Om een ​​selectie van een binaire string te lezen, moet je eerst beslissen waar die sectie is, een masker van 1s maken, ze naar dat gewenste leespunt verplaatsen en een & amp; -operator gebruiken om extraheer ze. Schuif ze ten slotte hetzelfde bedrag terug en je hebt je waarde. Voordat ik het masker bouwde, moest ik weten waar mijn gewenste leespunt was.

Ik heb een functie gemaakt die kolom- en rijposities nam om me te helpen het leespunt te bepalen. Ik weet dat elke tegel uit twee bits bestaat om een ​​zwarte tegel 0x01 een witte tegel 0x10 of een lege tegel 0x11 te vormen, dus wat mijn positie ook is is dat ik het uiteindelijk moet verdubbelen. Ik weet ook dat elke rij 8 tegels heeft, dus mijn plaatsing is (8 * col) + rij . Dat alles is een beschrijving van hoe ver het vanaf het begin van de binaire string zou zijn, maar ik moet weten hoe ver het van het einde is, dus ik trek die waarde af van de totale lengte van het 8×8 bord ( 64 - (8 * col) + rij) . Dit zou me aan het einde van mijn gewenste leeslocatie brengen, dus ik tel 1 plaats terug voor de overspanning van het masker en vermenigvuldig met 2 voor elk bit:

Nu bouw ik een masker van twee bits lang met beide bits ingeschakeld ( 0x11 ). Dit wordt verplaatst naar het leespunt van mijn doelreeks in een nieuwe en anders lege tekenreeks. De & amp; bitsgewijze operator zal een nieuwe string retourneren waar de enige bits on aanwezig zullen zijn in beide voorgaande strings. Op die manier zullen alle tegels rond mijn doel resulteren in 0, en alleen de bits die ook aanwezig waren in mijn doel zullen blijven bestaan:

En nu weten we of de tegel in kolom X en rij Y gelijk is aan zwart, wit of leeg. (Als je meer informatie wilt over de schakelfuncties, bekijk dan het artikel van Maksym)

Schrijven naar ByteBoard

Om een ​​nieuwe waarde naar een specifiek punt op ons binaire bord te schrijven, volgen we dezelfde stappen als lezen, maar gebruiken we alleen andere bitoperatoren. Deze keer extraheren we de waarde niet met een masker, maar gebruiken we het om een ​​spatie vrij te maken voor onze nieuwe tegel met XOR, en schrijven we ernaar met OR.

In dit geval gebruiken we XOR om een ​​kopie te maken van het bord, alleen omgekeerd bij het masker. Nadat EN op die kopie met het origineel is gebruikt, wordt het gewijzigde maskergedeelte volledig gewist, waardoor er ruimte overblijft voor de nieuwe tegel. Vervolgens gebruiken we de OR-operator op onze verschoven nieuwe tegelwaarde en geven we het hele bord terug met onze nieuw omgedraaide tegel 🎉

Conclusie

We hebben ervoor gezorgd dat de 8×8-array van gehele getallen is teruggebracht tot één Bytes16-waarde en dezelfde techniek kan worden gebruikt om andere arrays te converteren. Ik had ook een reeks kolom- en rijposities voor zetten in het spel. Ik kon dat omzetten in een paar Bytes28-waarden met een aangepaste naamgevingsconventie. Ik bewaar de details over precies hoe voor een andere dag, maar de basis was hetzelfde. Nadat ik beide had gedaan, nam ik mijn contract, dat 95.000.000 gas kostte om een ​​spel te valideren tot 4.109.875 . Ergens in de fluctuerende kosten van ETH- en gasprijzen was dat een verschil tussen $ 566,60 en $ 26,26. Nu is natuurlijk $ 26,26 om een ​​enkele game te valideren nog steeds niet ideaal. Een oplossing in de maak is om een ​​Oracle te gebruiken om het spel te valideren. Anders zullen we moeten wachten op Proof of Work of de acceptatie van Ethermint om de gasprijs te verlagen.

Totdat die gebeuren gebruiken we het Rinkeby Test-netwerk waar Ether gratis is voor iedereen met een github-account. Als je wilt proberen om een ​​symmetrisch bord van Reversi te minen, ga dan naar Clovers.network of de opslagplaats naar de mijne.