Een Verkle-boom is een verbintenisschema dat vergelijkbaar is met een Merkle-boom, maar met veel kleinere getuigen. Het werkt door de hashes in een Merkle-boom te vervangen door een vectortoezegging, waardoor bredere vertakkingsfactoren efficiënter worden.
Met dank aan Kevaundray Wedderburn voor feedback op het bericht.
Voor details over hoe verkle bomen werken, zie:
Het doel van dit bericht is om de concrete lay-out van de conceptverkle tree EIP toe te lichten. Het is bedoeld voor klantontwikkelaars die verkle-trees willen implementeren en op zoek zijn naar een introductie voordat ze dieper in het EIP duiken.
Verkle bomen brengen een aantal wijzigingen aan in de boomstructuur. De belangrijkste wijzigingen zijn:
Als vectortoezeggingsschema voor de verkle-boom gebruiken we Pedersen-toezeggingen . De toezeggingen van Pedersen zijn gebaseerd op elliptische krommen. Zie hier voor een inleiding tot Pedersen-toezeggingen en hoe u ze kunt gebruiken als polynoom- of vectortoezeggingen met behulp van Inner Product Argumenten.
De curve die we gebruiken is Bandersnatch. Deze curve is gekozen omdat deze performant is, en ook omdat het efficiënte SNARK's in BLS12_381 zal toestaan om in de toekomst over de verkle tree te redeneren. Dit kan handig zijn voor rollups en maakt een upgrade mogelijk waarbij alle getuigen in één SNARK kunnen worden gecomprimeerd zodra dat praktisch wordt, zonder dat er een verdere update van de toezegging nodig is.
De curvevolgorde/scalaire veldgrootte van bandersnatch is p =13108968793781547619861935127046491459309155893440570251786403306729687672801 , wat een 253 bit priemgetal is. Als gevolg hiervan kunnen we ons alleen veilig vastleggen op bitstrings van maximaal 252 bits, anders loopt het veld over. We kozen een vertakkingsfactor (breedte) van 256 voor de verkle tree, wat betekent dat elke verplichting tot 256 waarden van elk 252 bits kan vastleggen (of om precies te zijn, gehele getallen tot p - 1 ). We schrijven dit als Commit(v₀, v₁, …, v₂₅₅) om je vast te leggen op de lijst v van lengte 256.
Een van de ontwerpdoelen met de verkle tree EIP is om toegang tot aangrenzende posities (bijvoorbeeld opslag met bijna hetzelfde adres of aangrenzende codeblokken) goedkoop toegankelijk te maken. Om dit te doen, bestaat een sleutel uit een stam van 31 bytes en een achtervoegsel van één byte voor een totaal van 32 bytes. Het sleutelschema is zo ontworpen dat "dichtbij" opslaglocaties worden toegewezen aan dezelfde stam en een ander achtervoegsel. Bekijk voor details het EIP-concept.
De verkle-boom zelf is dan samengesteld uit twee soorten knooppunten:
De verbintenis tot een uitbreidingsknooppunt is een verbintenis tot een vector met 4 elementen; de resterende posities zijn 0. Het is:
C₁ en C₂ zijn twee verdere toezeggingen die zich committeren aan alle waarden met stam gelijk aan stem . De reden dat we toezeggingen nodig hebben, is dat waarden 32 bytes hebben, maar we kunnen slechts 252 bits per veldelement opslaan. Een enkele verplichting zou dus niet voldoende zijn om 256 waarden op te slaan. Dus in plaats daarvan slaat C₁ de waarden op voor achtervoegsel 0 tot 127, en C₂ slaat 128 tot 255 op, waar de waarden in tweeën worden gesplitst om in de veldgrootte te passen (daar komen we later op terug.)
De extensie wordt samen met de toezeggingen C₁ en C₂ "extensie-en-achtervoegselboom" (kortweg EaS) genoemd.
Figuur 1 Voorstelling van een wandeling door een verkle tree voor de sleutel 0xfe0002abcd..ff04 :het pad gaat door 3 interne knooppunten met elk 256 kinderen (254, 0, 2), waarbij één extensieknooppunt abcd..ff vertegenwoordigt en de twee achtervoegselboomtoezeggingen, inclusief de waarde voor 04 , v₄. Merk op dat stam is eigenlijk de eerste 31 bytes van de sleutel, inclusief het pad door de interne knooppunten.
Elk extensie- en achtervoegselboomknooppunt bevat 256 waarden. Omdat een waarde 256 bits breed is en we maar 252 bits veilig in één veldelement kunnen opslaan, zouden er vier bits verloren gaan als we het gewoon zouden proberen om één waarde in één veldelement op te slaan.
Om dit probleem te omzeilen, hebben we ervoor gekozen om de groep van 256 waarden te verdelen in twee groepen van elk 128 waarden. Elke 32-byte-waarde in een groep wordt gesplitst in twee 16-byte-waarden. Dus een waarde vᵢ∈ 𝔹₃₂ wordt omgezet in v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ en v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ zodat v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ=vᵢ.
Een "bladmarkering" wordt toegevoegd aan de v⁽ˡᵒʷᵉʳ⁾ᵢ, om onderscheid te maken tussen een blad dat nog nooit is geopend en een blad dat is overschreven met nullen. Er wordt nooit een waarde verwijderd uit een verkle tree . Dit is nodig voor aanstaande vervalregelingen van de staat. Die markering wordt op het 129e bit gezet, dwz v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ =v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ als vᵢ eerder is gebruikt, en v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ =0 als vᵢ nog nooit is gebruikt.
De twee verplichtingen C₁ en C₂ worden dan gedefinieerd als
De verbintenis aan een extensieknooppunt bestaat uit een "extensiemarkering", die alleen het nummer 1 is, de twee subboomtoezeggingen C₁ en C₂, en de stam van de sleutel die naar dit extensieknooppunt leidt.
In tegenstelling tot uitbreidingsknooppunten in de Merkle-Patricia-structuur, die alleen het gedeelte van de sleutel bevatten dat de bovenliggende interne knoop naar de onderliggende interne knoop overbrugt, bedekt de stam de hele sleutel tot dat punt. Dit komt omdat verkle-bomen zijn ontworpen met staatloze bewijzen in gedachten:als een nieuwe sleutel wordt ingevoegd die de extensie in twee "splitst", hoeft de oudere broer of zus niet te worden bijgewerkt, wat een kleiner bewijs mogelijk maakt.
Interne knooppunten hebben de eenvoudigere berekeningsmethode voor hun verplichtingen:het knooppunt wordt gezien als een vector van 256 waarden, die de (veldrepresentatie van de) wortelverplichting zijn van elk van hun 256 subbomen. De verplichting voor een lege substructuur is 0. Als de substructuur niet leeg is, is de verplichting voor de interne knoop
waarbij de Cᵢ de kinderen van de interne knoop zijn, en 0 als een kind leeg is.
Afbeelding 2 is een illustratie van het proces van het invoegen van een nieuwe waarde in de boom, wat interessant wordt wanneer de stelen op verschillende initiële bytes botsen.
Figuur 2 Waarde v₁₉₂ wordt ingevoegd op locatie 0000010000...0000 in een verkle tree met alleen de waarde v₁₂₇ op locatie 0000000000...0000 . Omdat de stammen verschillen bij de derde byte, worden twee interne knooppunten toegevoegd tot de verschillende byte. Vervolgens wordt een andere "extensie-en-suffix" -boom ingevoegd, met een volledige stam van 31 bytes. Het initiële knooppunt is onaangeroerd en C²₀ heeft dezelfde waarde als C⁰₀ vóór de invoeging.
De verkle-boomstructuur zorgt voor ondiepere bomen, waardoor de hoeveelheid opgeslagen gegevens wordt verminderd. Zijn echte kracht komt echter van het vermogen om kleinere bewijzen te produceren, d.w.z. getuigen. Dit wordt uitgelegd in het volgende artikel.
Wat zijn signaaleffecten in de kapitaalstructuur?
Huiseigenarenverzekering voor het verwijderen van een door bliksem beschadigde boom
GEO-aandelen dalen omdat REIT-structuur daalt en C Corp. verandert
15 beste dingen om te kopen bij Dollar Stores (inclusief Dollar Tree)
Bedrijfsstructuur:wat het beste voor u werkt
Beïnvloedt uw bedrijfsstructuur uw vermogen om investeerders aan te trekken?
Starten met de juiste bedrijfsstructuur