@electrumsv is on PowPing!

PowPing is a place where you can earn Bitcoin simply by socializing, for FREE.
Never tried Bitcoin? It's OK! Just come, socialize, and earn Bitcoin.
Check out electrumsv's activities

ElectrumSV Development

visit channel home
Total Economy: 0.02 USD

Derivation paths as a database column

If I wanted to select the oldest unused key, or even a sequence of unused keys and order them from oldest to newest, I need a database column that exposes it. This requires two pieces of information, how to serialise a sortable BIP32 derivation path, and whether the databases we would use can make use of them.

A serialisation format

ElectrumSV, through it’s inheritance of Electrum Core code, already has a way of serialising derivation sub-paths as bytes. This can be seen in our residual support for incomplete transactions packed with signing metadata, to be used in external signing, whether multi-signature co-signing, or offline signing.

This is not good enough to use as-is because:

  • It limits the derivation sub-path to two levels.
  • It uses 2 byte storage for the child index at each given level.

I did write a version of this about a year ago, when I was looking at extending this form of incomplete transaction serialisation, but gave up and went with JSON as a temporary measure given we should be using a standard format for that, and there is not yet any.

Let’s just go with packing the child index at each level as 4-byte big endian unsigned integers, in order of descent. So given a derivation path of “m/1/2'/3'/0” we get the following values “[0x1, 0x80000002, 0x80000003, 0x0]” which pack as “00000001800000028000000300000000”.

But more usefully, we might consider a key that has the relative derivation sub-path of “0/1010” which is the 1011th (given we start from 0) key intended for receiving external funds, and this would give us the column value of “00000000000003f2”.

Sorting with the SQLite database

What we need to be able to do, is filter for the rows that have the parent sub-path we are interested in which would be the “0” or “00000000” as packed bytes, ensure that it is not a longer sub-path by ignoring ros with a different length and then ordering based on the column value. This should ensure we only get rows that are relevant to us.

We need to know that several database functions work the way we need them to:

  • BLOB substring.
  • Length of a BLOB field.
  • Ordering in expected directions for both hardened and unhardened child indexes.

Just going ahead and testing this in SQLite gives the following syntax that does what we need:

>>> db = sqlite3.connect(":memory:")
>>> db.execute("CREATE TABLE Keys (derivation_path BLOB NOT NULL)")

>>> def mdp(path_text):
...     return b''.join(pack_be_uint32(v) for v in bip32_decompose_chain_string(path_text))

>>> db.executemany("INSERT INTO Keys (derivation_path) VALUES (?)", [ (mdp("m/0/1"),), (mdp("m/0/2"),), (mdp("m/0/1010"),), (mdp("m/1/0"),), (mdp("m/1/1"),), (mdp("m/1/1010"),) ])

>>> receiving_parent_prefix = pack_be_uint32(0)
>>> db.execute("SELECT * FROM Keys WHERE substr(derivation_path, 1, 4)=?", (receiving_parent_prefix,)).fetchall()
[(b'\x00\x00\x00\x00\x00\x00\x00\x01',), (b'\x00\x00\x00\x00\x00\x00\x00\x02',), (b'\x00\x00\x00\x00\x00\x00\x03\xf2',)]

>>> db.execute("SELECT * FROM Keys WHERE length(derivation_path)=? AND substr(derivation_path, 1, ?)=? ORDER BY derivation_path DESC", (8, 4, receiving_parent_prefix,)).fetchall()
[(b'\x00\x00\x00\x00\x00\x00\x03\xf2',), (b'\x00\x00\x00\x00\x00\x00\x00\x02',), (b'\x00\x00\x00\x00\x00\x00\x00\x01',)]

It can be easily demonstrated that hardened values work as expected too.

Sorting with the PostgreSQL database

We do not currently support this database, so we have no Python bindings that we use with it. But the following SQL demonstrates the same functionality as shown for SQLite.

CREATE TABLE Keys (derivation_path bytea)
INSERT INTO Keys (derivation_path) VALUES ('\x0000000000000000')
INSERT INTO Keys (derivation_path) VALUES ('\x0000000000000001')
INSERT INTO Keys (derivation_path) VALUES ('\x00000000000003f2')
INSERT INTO Keys (derivation_path) VALUES ('\x0000000100000000')
INSERT INTO Keys (derivation_path) VALUES ('\x0000000100000001')
INSERT INTO Keys (derivation_path) VALUES ('\x00000001000003f2')

SELECT encode(derivation_path, 'hex') FROM Keys WHERE octet_length(derivation_path) = 8 AND substring(derivation_path FOR 4) = '\x00000001' ORDER BY derivation_path DESC

Summing up

A final decision needs to be made as to whether we should store derivation paths as a database column that we can query against. But this shows that there is no technical limitation preventing us from doing so, and if we decide that the value in not double handling key state in the Python layer is worth it we can proceed to implement this as part of the larger migration for the second refactoring effort.

A topic that touches on similar database operations, is where we have added the offset and length fields to transaction inputs and outputs. The goal with that was being able to store the complete transaction data in the database, and to use the substring operator to pick out the script data with one query avoiding having to read and parse the whole transaction.

powered by powpress
link Tip
pete tipped:
0.02 USD
2 years ago