Vor kurzem habe ich begonnen, die UTXO-Set-Daten zu analysieren, die jeder vollständige Knoten in chainstate
einem Ordner (einer LevelDB
Datenbank) speichert.
Durch einen Blick in den Code können Sie mehr oder weniger erfahren, wie die Dateneinträge formatiert sind. Um jedoch so viel Platz wie möglich zu sparen, werden einige der Daten komprimiert und als varint
.
Wie Daten komprimiert werden, kann im Code gefunden und auch analysiert werden . Ich habe jedoch Schwierigkeiten zu verstehen, wie die Varint-Codierung/Decodierung durchgeführt wird. Laut dem Entwicklerhandbuch ist die dafür zuständige KlasseCVarint
, und ich konnte die Methode nachverfolgen, von der ich denke, dass sie dies tut . Da ich jedoch nicht weiß, in welchem Format die Daten codiert sind, kann ich nicht verstehen, was sie tun.
Hat jemand eine Ahnung, wie die gespeicherten Daten formatiert sind?
Klarstellung: Ich beziehe mich auf das CVarint-Format, das in UTXOs entlang des Bitcoin-Kerns verwendet wird, nicht auf das Varint-Format, das zum Codieren von Informationen in txs-Skripten verwendet wird.
Das CVarInt-Format ist in serialize.h implementiert
Da der Kommentar umfangreich ist, zitiere ich ihn hier einfach:
Ganzzahlen variabler Länge: Bytes sind eine MSB-Base-128-Codierung der Zahl. Das High-Bit in jedem Byte gibt an, ob eine weitere Ziffer folgt. Um sicherzustellen, dass die Codierung eins zu eins ist, wird eins von allen bis auf die letzte Ziffer subtrahiert. Somit kodiert die Bytefolge a[] mit der Länge len, bei der bis auf das letzte Byte Bit 128 gesetzt ist, die Zahl:
(a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))
Eigenschaften:
- Sehr klein (0-127: 1 Byte, 128-16511: 2 Bytes, 16512-2113663: 3 Bytes)
- Jede ganze Zahl hat genau eine Kodierung
- Die Codierung hängt nicht von der Größe des ursprünglichen Integer-Typs ab
- Keine Redundanz: Jede (unendliche) Bytefolge entspricht einer Liste codierter Ganzzahlen.
Beispiele:
- 0: [0x00]
- 1: [0x01]
- 127: [0x7F]
- 128: [0x80 0x00]
- 255: [0x80 0x7F]
- 256: [0x81 0x00]
- 16383: [0xFE 0x7F]
- 16384: [0xFF 0x00]
- 16511: [0xFF 0x7F]
- 65535: [0x82 0xFE 0x7F]
- 2^32: [0x8E 0xFE 0xFE 0xFF 0x00]
Um CAmount-Werte (Ganzzahlen, die die Anzahl der Satoshis darstellen) zu speichern, wird zuvor eine Transformation angewendet , die häufigere Zahlen (Vielfache von Zehnerpotenzen) zuerst in kleinere Zahlen umwandelt:
MyByteArray& MyByteArray::putVarInt ( const unsigned value )
{
return ( value < 0xFD ) ? putInt8 ( value ) :
( value <= 0xFFFF ) ? putInt8 ( 0xFD ).putInt16 ( value ) :
putInt8 ( 0xFE ).putInt32 ( value );
}
Little-Endian-Codierung
MyByteArray& MyByteArray::putPush ( const QByteArray& value )
{
if ( value.size ( ) < OP_PUSHDATA1 )
return putInt8 ( value.size ( ) ).putArray ( value );
if ( value.size ( ) <= 0xFF )
return putInt8 ( OP_PUSHDATA1 ).putInt8 ( value.size ( ) ).putArray ( value );
return putInt8 ( OP_PUSHDATA2 ).putInt16 ( value.size ( ) ).putArray ( value );
}
sr-gi