Tak Google: Sådan mines Bitcoin på Googles BigQuery

Udnyttelse af SQL's magt til at miner cryptocurrency i skyen

Jeg elsker Google BigQuery. Det er en administreret, meget skalerbar dataplatform, hvilket betyder, at du kan spørge enorme mængder data meget hurtigt (f.eks. 4 Terabyte på mindre end 30 sekunder!). Jeg bruger det regelmæssigt mine projekter (som den spanske lektionshandling til Google Assistant), og jeg er altid forbløffet over den høje ydelse.

Sidste uge arrangerede vi en Dev.IL Meetup om Blockchain, teknologien bag Bitcoin, og jeg blev ramt af en af ​​forhandlingerne fra Asaf Nadler, hvor jeg forklarede mekanismerne bag teknologien, der får Bitcoin til at krydse (se gerne her , men fair advarsel, det er på hebraisk :-). Da jeg gik hjem efter mødet, havde jeg min BigQuery-konsol åben med nogle analytiske forespørgsler, jeg skrev dagen før, og jeg fik denne idé: Hvad hvis jeg kunne bruge BigQuery til minedrift af Bitcoin? Er det endda muligt? Kan dette være omkostningseffektivt? I betragtning af BigQuerys imponerende skalerbarhed så det ud til, at det kunne være en god kamp.

(Spoiler: det var! Op til 25 Giga-hashes / sekund, gratis og meget sjovt! Læs videre for at finde ud af, hvordan ...)

Jeg var meget fascineret, og derfor besluttede jeg at prøve det. Jeg havde været interesseret i at eksperimentere med Blockchain-teknologien i et stykke tid, og dette var en fantastisk mulighed for at gøre det. Det tog at læse masser af artikler og et par timers arbejde, men jeg havde en vis succes! (Eller rettere, proof-of-concept succes ;-)

Jeg troede, det kunne være interessant, hvis jeg deler min rejse med dig ved at gøre en dataanalysemaskine til en Bitcoin-minemaskine. Jeg blev ganske overrasket over resultaterne. og jeg vedder på, at du også bliver!

Men først ting først: lad os gøre en supersnabb oversigt over, hvordan Bitcoin-minedrift fungerer.

Minedrift Bitcoins i et nøddeskal

Du har sandsynligvis hørt, at minedrift af Bitcoin indebærer at løse et beregningsmæssigt hårdt matematisk problem, og dette er sandt: Bitcoin-systemet består af transaktioner (det vil sige overføre penge mellem brugere), og disse transaktioner er registreret i en offentlig hovedbog, kaldet blockchain. Blockchain er, som navnet antyder, en linket liste over blokke med transaktionsdata.

Minedrift Bitcoin involverer i det væsentlige at finde en gyldig næste blok, som igen giver dig, miner, en præmie - i øjeblikket 12,5 BTC for hver blok, du finder.

Hver blok består af to dele: en header på 80 byte efterfulgt af en liste over transaktioner. Overskriften inkluderer identifikatoren for den forrige blok (dvs. hash'en for den forrige blokkehoved) samt en SHA256-hash på listen over transaktioner såvel som nogle andre oplysninger. Som minearbejder skal du dybest set på en eller anden måde sørge for, at blokens overskrift, når hashet to gange ved hjælp af SHA256-hashfunktionen, er mindre end et givet nummer, også benævnt "vanskeligheden" - eller hvor svært det er at finde målet nummer (dvs. den gyldige næste blok).

Bitcoin-blokke udvindes med en hastighed på ca. 1 blok hvert 10. minut. For at sikre, at frekvensen forbliver konstant, justeres vanskeligheden automatisk hver 2016-blokering (omtrent hver anden uge), så den er mere eller mindre proportional med den samlede computerkraftgruvearbejdere, der er sat i processen.

Minedrift involverer dybest set at prøve forskellige variationer for header, hovedsageligt i nonce-feltet (de sidste 4 byte af header), indtil du til sidst finder en header, hvis hash starter med et givet antal nuller (eller for at sige det anderledes - mindre end nogle nummer, som jeg sagde før).

Hvis du ønsker en mere detaljeret forklaring, kan du tjekke Ken Shirriffs blogindlæg om Bitcoin-minedrift eller bare følge med og indsamle de oplysninger, jeg nævner i hele indlægget.

Minedrift med BigQuery

Du inviteres til at følge mine fodspor og køre eksemplerne i denne blog. Nogle af de forespørgsler, der er præsenteret her, kan ligne på dele af Bitcoin-mineprocessen. Hvis du har en Google Cloud Platform-gratis prøvekonto, forbyder deres betingelser dig at deltage i minedrift cryptocurrency. Selvom ingen af ​​eksemplerne, der er præsenteret i dette indlæg rent faktisk vil miner nogen cryptocurrency, anbefaler jeg dig stadig at spille det sikkert og have en betalt Google Cloud Platform-konto, som efter min bedste viden ikke forbyder minedrift af cryptocurrencies på nogen måde.

Første ting først: Ser på en blokkehoved

Lad os starte med at se, hvordan minedrift foregår i praksis. Vi vil se på overskriften på en blok fra Bitcoin blockchain og forsøge at beregne hash selv for at se, hvordan det er gjort (og derefter også bekræfte, at vi kan gøre hash-delen med BigQuery).

Men hvor finder vi en blok?

Det viser sig, du kan finde hele Blockchain i BigQuery. Men til vores formål bruger vi en anden kilde, som også giver os en måde at få de rå binære data på blokken: et websted, der hedder blockchain.info. Jeg valgte tilfældigt en af ​​de nylige blokke, nummer 514868:

Du kan få de binære data for denne blok (hex kodet) ved at klikke på blokens hash og derefter tilføje? Format = hex til URL'en, hvilket resulterer i dette link. Blokvisningen viser også den komplette liste over transaktioner og andre interessante data, og jeg inviterer dig til at udforske på egen hånd.

Lad os fortsat fokusere på overskriften. Vi kopierer de første 160 tegn fra blokens data (det vil være de første 80 byte):

000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491b55a494a5117ac997500

Denne Bitcoin Wiki-side forklarer, hvordan hash-algoritmen fungerer: vi skal dybest set tage denne header og køre SHA256-funktionen på den og derefter køre den igen på resultatet af den første kørsel. Dette skulle resultere i hash af blokken.

Så første ting, hvis vi ville gøre dette i BigQuery, ville vi have brug for en SHA256-funktion. Heldigvis blev den introduceret i version 2 af BigQuery (a.k.a. Standard SQ). Vi har også brug for en metode til at konvertere disse hex-værdier til faktiske bytes. Heldigvis fik en funktion kaldet FROM_HEX os dækket. Så langt så godt.

Nu kan vi prøve at skrive den aktuelle forespørgsel (som en enkelt linje):

VÆLG TO_HEX (SHA256 (SHA256 (FROM_HEX)
'000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491b55a494a5117ac997500'))))

(Hvis du vil følge med, kan du prøve at køre denne forespørgsel på BigQuery-konsollen. Du bliver også nødt til at fjerne markeringen af ​​"Brug Legacy SQL" -forespørgselsindstillinger. Hvis du får en fejl, der lyder: "Ukendt funktion til_hex", er det betyder, at du ikke fjernede markeringen i denne boks.)

Ved at køre ovenstående forespørgsel får vi følgende resultat:

Jeg forventede at se “000000000000000000082fac02f1bf91ad4e024e6a5a1537936e9d518f827a53”

Da jeg gjorde det første gang, blev jeg ganske skuffet, fordi det så ud til, at hash var anderledes end den oprindelige hash af blokken. Jeg indså dog hurtigt, at det bare var vendt! (Tilsyneladende opbevares Bitcoin-hashes little-endian).

At tilføje en REVERSE-funktion lige inden du ringede til TO_HEX gjorde det trick:

VÆLG TO_HEX (REVERSE (SHA256 (SHA256 (FROM_HEX)
'000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491b55a494a5117ac997500')))))
Nu virker det legit!

Så det er allerede en præstation: vi ved nu, at vi kan verificere hasherne for Bitcoin-blokke på BigQuery. Hvis vi ønskede at bruge BigQuery til at mine, ville vi gerne bruge det samme sæt funktioner, bortset fra at vi ikke havde den komplette header: vi skulle søge efter en gyldig header med en lille nok hashværdi.

En gyldig header består af 6 felter:

  1. version - Værdier på 2, 3 og 4 er fælles (nye værdier tilføjes)
  2. hashPrevBlock - Hash fra den forrige blok i kæden
  3. hashMerkleRoot - Hash af alle transaktioner i blokken (forklarer)
  4. tid - tidsstempel fra hvornår blokken blev oprettet
  5. vanskelighed - Problemet med blokken, der er gemt som et flydende punktnummer
  6. nonce - 4 byte, som vi kan variere for at påvirke headerværdien

Minedrift er dybest set at prøve alle mulige kombinationer for nonce, og derefter kontrollere hash for hver, indtil hash er under målværdien. Målværdien kan let afledes fra blokens vanskelighed:

mål = (0xffff * 2 ** (256-48)) / vanskeligheder

Den mindste vanskelighed for enhver blok er 1. Derfor vil ethvert mål have mindst 48 førende nuller. Så da vanskelighedsnummeret for vores blok var 3462542391191.563, var målet: 000000000000000000514a4900000000000000000000000000000000000000000000

Du kan finde den aktuelle vanskelighed og målværdi her (linket giver dig også en lidt mere forklaring om forholdet mellem vanskelighederne og målværdien).

Så hvis vi ønskede at gengive mineprocessen for denne blok, ville vi bare prøve alle de forskellige kombinationer for overskridelsen, de sidste 4 byte i overskriften, indtil vi fandt en, hvis hash er mindre end ovenstående nummer.

Re-Mining the Block

Jeg besluttede at starte med det lille ved bare at søge efter den sidste byte, da vi allerede har svaret i dette tilfælde. Først tænkte jeg på at uploade en lille tabel med alle numrene mellem 0 og 255 (de gyldige værdier for den byte), men så fandt jeg ud af, at denne tabel faktisk kan efterlignes ved at kombinere to SQL-funktioner: UNNEST () og GENERATE_ARRAY ():

VÆLG * FRA UNNEST (GENERATE_ARRAY (0, 255)) num;

Bevæbnet med denne viden oprettede jeg min første forespørgsel, der prøvede at gengive mineprocessen i BigQuery:

VÆLG
  TO_HEX (CODE_POINTS_TO_BYTES ([0xac, 0x99, 0x75, num])) AS nonce
FRA
  UNNEST (GENERATE_ARRAY (0, 255)) num
HVOR
  TO_HEX (REVERSE (SHA256 (SHA256 (CONCAT (FROM_HEX (
'000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491b55a494a5117'), CODE_POINTS_TO_BYTES ([0xac, 0x99, 0x75, num])))))) LIKE '000.000.000 milliarder%'

Okay, lad det drille det lidt!

Grundlæggende, da vi kun søger efter at rette manglen, fjernede jeg den del fra overskriften (du kan kontrollere - den lange hexstreng i forespørgslen er kun 152 tegn lang, der repræsenterer 76 byte, det vil sige overskriften uden nonce). Hvad vores forespørgsel leder efter, er en værdi på 4 byte, der, når den er tilføjet til overskriften, resulterer i en hash, der er mindre end måltallet.

Da dette var min første prøve, brugte jeg de værdier, jeg allerede kender, fra blokken til de første 3 byte i nonce, og havde kun BigQuery-søgning efter den endelige byte. Dette fungerede som en charme, og det fandt hurtigt den korrekte nonce-værdi:

Du spekulerer måske på, hvorfor jeg brugte LIKE inde i WHERE-bestemmelsen til at filtrere det rigtige resultat. Jeg gør dette, fordi vi simpelthen leder efter hasjer, der er mindre end målværdien. Da målværdien starter med 18 nuller, filtrerer vi simpelthen et hvilket som helst tal, der ikke starter med 18 nuller (da det tydeligvis er større end målværdien). Dette betyder, at vi muligvis får nogle falske positiver (f.eks. Antal, der starter med 18 nuller og derefter et hvilket som helst ciffer, der er større end 5), men vi kan hurtigt filtrere dem ud manuelt.

Så nu, når vi ved, hvordan vi søger efter den luskede nonce, kan vi hurtigt udvide søgningen til flere byte:

VÆLG
  TO_HEX (CODE_POINTS_TO_BYTES ([0xac, num2, num3, num4])) AS nonce
FRA
  UNNEST (GENERATE_ARRAY (0, 255)) num2,
  UNNEST (GENERATE_ARRAY (0, 255)) num3,
  UNNEST (GENERATE_ARRAY (0, 255)) num4
HVOR
  TO_HEX (REVERSE (SHA256 (SHA256 (CONCAT (FROM_HEX (
'000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491b55a494a5117'), CODE_POINTS_TO_BYTES ([0xac, num2, num3, num4])))))) LIKE '000.000.000 milliarder%'

Mens denne forespørgsel gør det trick og finder de 3 bytes, var der et problem: det kører langsomt! Det tog ca. 30 sekunder at afslutte denne forespørgsel. Hvis vi skulle søge efter alle de 4 byte, ville det tage omkring to timer med denne hastighed. Jeg nævnte ovenfor, at en ny blok udvindes hvert 10. minut, så da vi fandt et resultat, var vi allerede bagud, og det ville ikke være relevant.

Dette var lidt skuffende (hvad skete der med BigQuery's "meget skalerbare" løfte?), Så jeg besluttede at undersøge yderligere og prøve at se, om jeg kunne gøre noget for at forbedre dette.

Fra min tidligere BigQuery-oplevelse huskede jeg, at det var en dyre operation at medbringe forskellige tabeller, der fik forespørgsler til at køre meget længere. Jeg prøvede at fjerne sammenføjningstrinnet ved at generere en større tabel (dvs. fortælle GENERATE_ARRAY at generere flere numre), men efter en vis prøve og fejl så det ud til, at den maksimale størrelse på bordet stadig ville være omkring 1 million rækker, hvilket betyder, at jeg ' d er stadig nødt til at deltage i tabeller eller kun søge efter 1 million hash hver gang (hvilket er slags meningsløst, da min computers CPU kan gøre dette på mindre end et sekund).

Så det så ud som om det ville være muligt at mine Bitcoin med BigQuery, men næppe praktisk.

Jeg er stadig ikke så glad for at give op, så jeg prøvede et par flere tilgange. Og en af ​​dem virkede faktisk!

Minedrift hurtigere

Jeg huskede, at BigQuery havde nogle meget store offentlige datasæt indeholdende enorme tabeller. Efter at have scannet et par af dem, fandt jeg en der indeholdt 5,3 milliarder rækker, hvilket er lige over 4.294.967.296, antallet af det forskellige antal kombinationer for nonce. Hvis jeg kunne konstruere en forespørgsel, der skulle gå over denne tabel og prøve en anden kombination for hver række i tabellen, ville jeg være i stand til at dække alle mulige kombinationer.

Jeg prøvede at bruge ROW_NUMBER () OVER () SQL-funktionen til dette, som skulle returnere det aktuelle rækkenummer (så kunne jeg udlede et andet sæt bytes for hver række i henhold til rækkenummeret), men det døde hurtigt med følgende fejl:

Ressourcer overskredet under udførelse af forespørgsel: Forespørgslen kunne ikke udføres i den tildelte hukommelse ..

Øv bøv! Men så begyndte jeg at tænke - hvad hvis jeg bare prøvede tilfældige tal? til sidst er der en meget god chance for, at hvis der er et matchende hash, finder jeg det, da antallet af forsøg er større end antallet af kombinationer.

Så jeg kom med denne forespørgsel:

SELECT TO_HEX (nonce)
FRA (
  VÆLG
    CODE_POINTS_TO_BYTES ([
      KAST (TRUNC (256 * RAND ()) AS INT64),
      KAST (TRUNC (256 * RAND ()) AS INT64),
      KAST (TRUNC (256 * RAND ()) AS INT64),
      KAST (TRUNC (256 * RAND ()) AS INT64)
    ]) AS nonce
  FRA
    `Fh-bigquery.wikipedia.wikipedia_views_201308`
)
HVOR
  TO_HEX (REVERSE (SHA256 (SHA256 (CONCAT (FROM_HEX (
'000000204a4ef98461ee26898076e6a2cfc7c764d02b5f8d670832000000000000000000f99f5c4d5025979fcb33d245536a55b628d4564c075c0210cbbc941ad79fdbc5e491ce115)) 5)

CAST (TRUNC (256 * RAND ()) AS INT64) genererer et tilfældigt tal mellem 0 og 255, og derefter genererer den indre SELECT-del ganske enkelt en tabel med ~ 5,3 milliarder rækker af fire tilfældige værdier. Derefter sørger den ydre forespørgsel for, at vi kun får værdier, der faktisk resulterer i en lav nok hash - hvilket er, hvad vi leder efter!

Til min behagelige overraskelse vendte denne forespørgsel tilbage på kun 20,9 sekunder - og den fandt faktisk den korrekte nonce-værdi (den fandt den endda to gange!):

Dette betyder, at jeg var i stand til at kontrollere næsten 4 milliarder hash på 20 sekunder, eller omkring 200 mega-hashes per sekund. Det er ikke så dårligt - i betragtning af at GPU'er kun vil få dig ca. 30-60 mega-hash / sekund (CPU'er endnu mindre, for ikke at nævne minedrift med blyant og papir).

Så dette får os naturligvis intetsteds nær en dedikeret minedrifthardware hurtigt, men der var stadig et trick, som jeg havde under ærmet ...

samtidighed

Hvis du er en skarpskytte inden for kombinatorik, har du måske bemærket, at det at kontrollere alle mulige værdier for nonce ikke garanterer en meget god chance for at finde en lille nok hash (som jeg sagde i begyndelsen, det er et hårdt problem!).

I skrivende stund var målet omtrent 2¹⁸² (se hvordan vi beregner målet ud fra vanskeligheder ovenfor), hvilket betyder, at der er 2 ¹⁸ gyldige hashkombinationer ud af 2²⁵⁶ totalt muligt, eller med andre ord - chancen for en vilkårlig hash er lavere end målet er 1 ud af 2⁷⁴.

Dette betyder dybest set, at hvis vi kun varierer fra hinanden, tjekker vi 2³² muligheder, og vores chance for faktisk at finde en ønsket hash er super lille: så vi har brug for flere byte at lege med.

Hvis vi ser et andet på overskriftsstrukturen, vil du bemærke, at vi let kan ændre tidsfeltet (andre noder accepterer stadig blokken, hvis tiden er lidt væk), eller vi kan ændre noget på listen over vores blok transaktioner, hvilket vil resultere i en helt anden værdi for markle root hash-feltet.

En måde at variere transaktionslisten (og dermed generere en anden markle-hash) er ved at tilføje en ekstra nyttelast til den første transaktion, kaldet extraNonce, som kan have op til 100 byte. En anden måde ville bare være at vælge et andet sæt transaktioner, der skal inkluderes i blokken.

Pointen er, for at være en succesfuld miner, er man nødt til at prøve forskellige kombinationer af transaktionsliste og / eller variere tidsfeltet ud over nonce. Dette betyder, at vi kan køre forespørgslen, som vi fandt flere gange, parallelt, hver gang med en anden blokhoved. Men hvor mange samtidige forespørgsler tillader BigQuery?

I henhold til kvotesiden kan du læse op til 50 samtidige forespørgsler, som teoretisk kan resultere i op til 50 gange hurtigere hashing. Virker det virkelig? Jeg ved ikke, jeg har ikke prøvet det. I øjeblikket var mit bedste resultat med en enkelt forespørgsel 500 Mega-hash pr. Sekund (ved hjælp af dette 106-billion rækker wikipedia datasæt som en kildetabel), hvilket betyder med en grænse på 50 samtidige forespørgsler, vi teoretisk kan få op til 25 Giga- hashes / sekund. Som en moderat dedikeret minedrifthardware - hvilket ikke er så dårligt, i betragtning af at det i det væsentlige er gratis.

Så hvad koster det?

BigQuery hævder at være en omkostningseffektiv løsning. På det tidspunkt var jeg allerede overbevist om deres skalerbarhedskrav, men deres prisstruktur var også en overraskelse for mig. En meget god overraskelse.

Prismodellen for BigQuery er udelukkende baseret på den mængde data, du forespørger: du faktureres dybest set af byten. Sagen er, at du ikke fakturerer for behandlingsstyrken eller mellemliggende data, som din forespørgsel genererede - bare for byte, du læser fra kildetabellen.

I vores tilfælde bruger vi enorme kildetabeller, men vi bruger dem bare til at generere et stort antal tilfældige talkombinationer - vi læser faktisk ingen data til tabellerne. BigQuery har en dejlig funktion, hvor den viser den anslåede pris for en forespørgsel (som det antal byte, som du vil blive faktureret for). Den første 1 Terabyte er gratis hver måned, og du betaler 5 $ for hver ekstra Tetabyte, du spørger efter. Ikke dårligt!

Så hvis vi tjekker, hvad BigQuery estimerer for vores store forespørgsel, er det dette, vi finder:

Så dybest set kan vi køre så mange sådanne forespørgsler, som vi ønsker, gratis! De måler helt sikkert op til deres krav om omkostningseffektivitet (i det mindste i dette tilfælde).

Resumé og konklusioner

Dette startede som en sjov øvelse med det formål at lære bedre hvordan blockchain fungerer. Da jeg startede, var jeg temmelig sikker på, at jeg ville ramme en hård grænse (måske noget CPU-tidskvote eller noget), og jeg må sige, at jeg stadig er ret overrasket over, at jeg kunne få al denne beregningskraft gratis.

Mens min forskning viser, at det i teorien burde være muligt at omdanne BigQuery til en minemaskine, er der stadig en betydelig mængde arbejde, der skulle udføres, hvis jeg ville automatisere mineprocessen. En rå beregning viser, at selv hvis en sådan minearbejder blev bygget, når jeg konkurrerer med al den dedikerede minedriftens hardware, der kører rundt om i verden, ville det tjene mig omkring $ 5 om året. Ikke desto mindre ved jeg nu, at Bitcoin kan udvindes med SQL, hvilket er uvurderligt ;-)

Men vigtigst af alt, dette eksperiment gav mig et helt nyt perspektiv om den enorme computerkraft, der bruges til minedrift af Bitcoin. Vi taler om 26 milliarder giga-hashes pr. Sekund - det er 2,6 * 10¹⁹, hvilket er mere end antallet af sandkorn på jorden. Hvert sekund. Du bliver nødt til at undre dig over, hvad vi ville opnå, hvis vi i stedet brugte en brøkdel af denne computerkraft til medicinsk forskning i stedet ...