Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

replace json on disk, with leveldb/sql/...? wallet file does not scale. partial writes #4823

Open
SomberNight opened this issue Nov 2, 2018 · 26 comments
Labels
enhancement ✨ topic-walletstorage 💾 not wallet itself but storage/db-related
Milestone

Comments

@SomberNight
Copy link
Member

json on disk does not scale to large files, as every time we need to flush, the whole file needs to be rewritten.

This is a problem for:

  • channel_db (routing table for LN)
  • watcher_db (also LN)
  • even the wallet file itself...
@neocogent
Copy link
Contributor

Would using sqlite3 be an option for this. I think it's pretty fast/efficient, though of course not a full blown sql server. I don't think installing a server is going to fly well for most users anyway but there are a lot of python apps that use sqlite3 as a backend (some even handling a lot of data like darktable). It has the advantage there are utils around for viewing/editing the db file (for advanced users doing fixes etc). The python module is widely available or often preinstalled. Anyway, just something to look at.

JSON has some advantages but only when files are small enough to visually inspect/edit.

@ecdsa
Copy link
Member

ecdsa commented May 16, 2019

this is done for channel_db and watchtower_db
we will not do it for the wallet file (not until we forward payments)

@ecdsa ecdsa closed this as completed May 16, 2019
@SomberNight SomberNight added the topic-walletstorage 💾 not wallet itself but storage/db-related label Aug 8, 2019
@SomberNight SomberNight changed the title replace json on disk, with leveldb/sql/...? replace json on disk, with leveldb/sql/...? wallet file does not scale. partial writes Aug 8, 2019
@SomberNight
Copy link
Member Author

SomberNight commented Aug 8, 2019

I looked at this again, specifically for the wallet file, to replace json. Being able to do partial writes will become necessary for large wallets, especially with lightning (and especially when we forward).

The main issue is that we currently encrypt the whole wallet file (by default). This is good for protecting metadata and also privacy reasons. This does not scale however: every time we need to make sure changes are persisted on disk, we serialize the whole wallet file json, compress it with zlib, encrypt it with AES, and write the whole thing to disk. (even with encryption disabled we write the whole json to disk every time)

We could simply replace json with sqlite/leveldb, but we could no longer simply encrypt the whole wallet file.

To be able to do partial writes, and have encryption, we either

  1. encrypt individual records (e.g. keys and values if using a kv store), or
  2. encrypt transparently between the filesystem layer and the db

The latter would be clearly preferred. (at the very least, there are many footguns and potential mistakes to be made with the first approach)

(note: ElectrumSV implemented option1 using sqlite)

To encrypt transparently below the db (option2), we would probably need the db itself to know about the encryption and do it for us. (I guess it's not strictly needed as you could create a virtual filesystem and do the encryption there yourself (see e.g. TrueCrypt/VeraCrypt) but that might be even more complicated)

I have found two viable ways to do option2.


Option2A: SQLCipher

https://github.com/sqlcipher/sqlcipher
https://www.zetetic.net/sqlcipher/design/
SQLCipher is an extension to sqlite that allows encrypting the db (using e.g. AES-CBC for each page).
It looks maintained and to have a long track record.
It's a C project, like sqlite, so we would need python bindings.
There seem to be a few competing projects (but none of them seems too reassuring):
https://github.com/leapcode/pysqlcipher
https://github.com/coleifer/pysqlite3
https://github.com/coleifer/sqlcipher3

Option2B: RocksDB

RocksDB is a key-value store (like LevelDB).
It has support for the kind of encryption we want since this PR. Well, except not the whole thing is implemented, so it does not work out of the box.
AFAICT we would need to subclass the BlockCipher class and implement (probably) AES.
Frustratingly, I could not find any examples of using RocksDB with this encryption option.
The PR author has likely contributed this to be used in arangodb, but there it is an feature only available in the Enterprise edition; I could not find the relevant code.

In any case, RocksDB is a C++ project, so we would then need python-bindings, see e.g. https://github.com/twmht/python-rocksdb
We would need to expose the encryption functionality through these bindings.

@ysangkok
Copy link
Contributor

ysangkok commented Oct 24, 2019

Your proposed solutions are difficult because they both exchange the storage layer and add encryption in one go, it is going to be difficult to get it right and have it be robust on all platforms (especially since the proposed alternatives need native code).

I think "event sourcing" should be considered as an alternative. What that means, is storing only changes. This is simple, but requires more disk space. But a typical big wallet pretty much only grows, so it shouldn't be too bad. Event sourcing is extremely inefficient when data is deleted/replaced. This is space-inefficient like a CoW filesystem where snapshots are made after each change.

Let's imagine the wallet file is now

{ "seed": "9dk",
  "qt_window_position": [500, 250]
  "transactions": ["01000000..."]}

Each time "qt_window_position" is changed, we need to reencrypt all the transactions, which are way larger.

In event sourcing, the final database state is implicit from a bunch of changes:

initial_state:

{"seed": "9dk"}

change0:

[["add", {"qt_window_position": [100, 100]}],["add", {"transactions": "010000..."}] ]

change1:

[["replace", {"qt_window_position": [500, 250]}]]

Something like json-path can be used to identify keys in a deep structure. EDIT: or json-patch which has an IETF spec.

The change files can be encrypted individually and never change. On wallet startup, they are all decrypted and applied serially, the wallet lives unencrypted in memory as before, as a plain Python object (as before). In contrast to migrating to LevelDB, it doesn't require switching to a flatter DB layout.

A naive implementation would write a single change file every single time save() is called. By introducing a transaction object (using the with construct of Python), the code can be migrated to having less transactions which will then require less change files.

EDIT: There is a heavy-weight Python-based event sourcing library that even supports encryption: eventsourcing#Application-level encryption

@ecdsa
Copy link
Member

ecdsa commented Oct 28, 2019

I like the idea of event sourcing
does json-patch require multiple files?
it seems that the changes could be added serially to the wallet file

@ysangkok
Copy link
Contributor

The spec json-patch is concerned with encoding of the changes, not how to store them. The library json-patch takes JSON objects or strings (simply encoded objects). So one would have to develop a framing mechanism to put it in one file.

@ecdsa
Copy link
Member

ecdsa commented Oct 30, 2019

I can see how this would work with encryption, but one issue is what to do with the compression currently performed before encryption.

  • option 1: no compression at all. in that case only the last cypher block will need to be rewritten when we append something to the file
  • option 2: we compress only the main json, and patches added to the wallet file are not compressed.

@rt121212121
Copy link

ElectrumSV will be dropping it's encryption except for things like private key data. My research led me to believe that most encryption options were unproven and would impose too much development overhead, and likely risk. At least for now, we'll be leaving it up to the user to ensure their wallets are secured appropriately if they require privacy.

@ecdsa
Copy link
Member

ecdsa commented Nov 24, 2019

I have implemented "append to encrypted" here: f28ebf9

@ecdsa
Copy link
Member

ecdsa commented Nov 25, 2019

Here is a proof of concept for storage using jsonpatch: 4f3b0bf

To make it efficient, we might want to replace all lists with dicts in the wallet file.

@ecdsa
Copy link
Member

ecdsa commented Nov 27, 2019

Here is my jsonpatch branch: https://github.com/spesmilo/electrum/commits/jsonpatch
It is still a draft, and I have not tested it with lightning.
I think should probably not be part of the next release.

@SomberNight
Copy link
Member Author

Rotonen on IRC suggested using persistent, potentially with ZODB. There is a module for these that can be used to have encryption at rest.

@ecdsa ecdsa modified the milestones: Lightning release2, backlog May 30, 2020
SomberNight added a commit that referenced this issue Jul 5, 2021
Fixes: after adding a payment request, if the process was killed,
the payreq might get lost. In case of using the GUI, neither the
callee nor the caller called wallet.save_db().

Unclear where wallet.save_db() should be called...
Now each method tries to persist their changes by default,
but as an optimisation, the caller can pass write_to_disk=False
e.g. when calling multiple such methods and then call wallet.save_db() itself.

If we had partial writes, which would either rm the need for wallet.save_db()
or at least make it cheaper, this code might get simpler...

related: #6435
related: #4823
@ln2max
Copy link

ln2max commented Sep 14, 2021

I am still looking into the background and previous proposals for this issue. Based on skimming the comments so far here and in #5999 , I would like to propose unifying the wallet format to internally-tagged JSON-per-line objects, which can be written incrementally and periodically "squashed" down to a single snapshot entry. Using @ysangkok 's example above, a wallet with an initial snapshot entry and several incremental entries would look something like:

{"entry_format": "unencrypted", "entry_type": "snapshot", "data": {"seed": "9dk"}, "version": 1}
{"entry_format": "unencrypted", "entry_type": "incremental_update", "operations":  [{"type": "add", "data": {"qt_window_position": [100, 100]}],{"type": "add", "data": {"transactions": "010000..."}} ], "version": 1}
{"entry_format": "unencrypted", "entry_type": "incremental_update", "operations": [{"type": "replace", "data": {"qt_window_position": [500, 250]}}], "version": 1}

Conversely, an unencrypted wallet might look like:

{"entry_format": "encrypted", "mac": "d3adbeef", "ciphertext": "foobarbaz", "version": 1, "wallet_type": "xpubpw", "ephemeral_pubkey_bytes": "12ab"}

where the ciphertext block encapsulates an unencrypted-format entry, so that the parsing logic is exactly the same. We would merely add encrypt/decrypt operations to the existing pipeline.

Note the above is very much a sketch of how it might work and by no means complete. More fields will almost certainly be necessary.

Rather than computing the MAC over the entire entry (or entire wallet) as we do now, the MAC would be computed over the ciphertext and other relevant fields in a defined fashion, e.g:

DIGESTMOD = 'sha512_256'

def _entry_mac_version_1(key, ciphertext: str, version: int, wallet_type: str, ephemeral_pubkey_bytes: str):
    msg = "+".join((ciphertext, version, wallet_type, ephemeral_pubkey_bytes))
    return hmac.digest(key, msg, DIGESTMOD)

def _entry_mac_version_2(key, ciphertext: str, version: int, wallet_type: str, ephemeral_pubkey_bytes: str, some_new_fancy_parameter: str):
    msg = "+".join((ciphertext, version, wallet_type, ephemeral_pubkey_bytes, some_new_fancy_parameter))
    return hmac.digest(key, msg, DIGESTMOD)

def entry_mac(version, *args):
    if version == 1:
        return _entry_mac_version_1(*args)
    elif version == 2:
        return _entry_mac_version_2(*args)
    else:
        raise NotImplementedError("Unknown version {}".format(version))

This approach provides some major benefits:

  • it is extremely robust to system crashes and other sudden write interruptions. We can simply parse the wallet by iterating over the lines, and stop when we reach invalid JSON
  • JSON parsing is highly optimized and some very good, very fast libraries are available (ujson). Despite the very verbose proposed format, performance impact will (hopefully) be negligible
  • the format is modular and easy to expand as needs change in the future, we just add fields
  • while the format is less human-readable than the pretty-print JSON plaintext the wallet currently uses, it is reasonably human-readable both in the encrypted and unencrypted modes
  • unlike array-indexing based approaches, everything is extremely explicit, which reduces the chances that bugs or mistakes will happen in the wallet parsing. This also makes it easier for 3rd-party implementers to work with.

@ecdsa
Copy link
Member

ecdsa commented Sep 21, 2021

I think you have a good point about robustness to crashes and write interruptions.
I am in the process of rebasing the jsonpatch branch against the current codebase.
That branch is 2 years old, it is more a rewrite than a rebase..

@ecdsa
Copy link
Member

ecdsa commented Sep 22, 2021

@ln2max, I have updated and pushed the jsonpatch branch:
https://github.com/spesmilo/electrum/commits/jsonpatch
The work has been split in four separate commits, only the last commit deals with the encryption scheme.

I think we can improve it with your idea of using standalone encrypted blobs, one per update. This indeed makes it robust to crashes.

I do not like the extra layer of JSON in your proposal. Basically, you are embedding encrypted JSON in another layer of JSON. This is unnecessarily complex, and it leaks some info about the wallet.

I think we could use a sequence of encrypted binary blobs, without separator, each with its own MAC and length info.
Someone who has access to the file but does not have the password would not be able to see the separation between blobs.

@ln2max
Copy link

ln2max commented Sep 22, 2021 via email

@ecdsa
Copy link
Member

ecdsa commented Sep 23, 2021

No, the length of a cipher block does not need to be in the previous block, it is possible to put it inside at the beginning of each block. But actually, we might not need it at all (see below).

What I am concerned about is not only a lack of privacy, but the possibility that an adversary who has access to the encrypted wallet file could remove part of it, and the result would still be seen as valid. For example, they could delete a channel update, which would cause the wallet to use a revoked state.

Note that this attack is also possible with the encrypted blobs method I proposed above. In order to avoid that, @SomberNight suggested that we use a single MAC at the beginning of the file, instead of one per encrypted blob.

To illustrate this, assume that the file contains text1 and we want to append text2.
This is what the current jsonpatch branch is doing, when text2 is added:

before:        [magic | ephemeral_pubkey | cipher(text1) | mac1]
after:         [magic | ephemeral_pubkey | cipher(text1+text2) | mac2]

The new proposal would look like this:

before:         [magic | ephemeral_pubkey | mac1] [cipher(text1)]
after:          [magic | ephemeral_pubkey | mac2] [cipher(text1)][cipher(text2)]   

The write method would first append the new cipher, then update the MAC. The new MAC is obtained by hashing the previous MAC and the new ciphertext. When decrypting, one would compare the MAC at the beginning of the file to the MAC obtained at the end of each cipher block, and stop when they match.

Note that each cipher block has its own PKCS7 padding, so its length is a multiple of 16. The length of each cipher block does not need to be included in the block, if we add a separator at the end of the encrypted text (for example \n). We could also use no separator at all and recompute the hash every 16 bytes.

@ecdsa
Copy link
Member

ecdsa commented Sep 23, 2021

One of the original considerations was to provide an extensible header
format for encrypted wallets, so that new fields/descriptors/metadata
can be added later while ensuring backwards compatibility.

Indeed, but a header should remain a header (magic bytes at the beginning of the file).
I would not call "header" the operation of embedding every cipherblock in JSON...

@SomberNight
Copy link
Member Author

SomberNight commented Sep 23, 2021

The write method would first append the new cipher, then update the MAC. The new MAC is obtained by hashing the previous MAC and the new ciphertext.

We need to be mindful that the attacker might delete some updates from the end and then try to recalculate and update the MAC.
Note that if the MAC is cleartext and is calculated over the ciphertexts, then the attacker can recalculate and update it.
So maybe the MAC should be over the plaintexts. (EDIT: or it could be encrypted somehow)

@ln2max
Copy link

ln2max commented Sep 23, 2021 via email

@ln2max
Copy link

ln2max commented Sep 23, 2021 via email

@ln2max
Copy link

ln2max commented Sep 23, 2021 via email

@SomberNight
Copy link
Member Author

The write method would first append the new cipher, then update the MAC. The new MAC is obtained by hashing the previous MAC and the new ciphertext.

We need to be mindful that the attacker might delete some updates from the end and then try to recalculate and update the MAC.
Note that if the MAC is cleartext and is calculated over the ciphertexts, then the attacker can recalculate and update it.
So maybe the MAC should be over the plaintexts.

I certainly hope not... as far as I know, HMAC is calculated using a key
so that an attacker cannot recalculate a plaintext MAC. The idea being
that Bob can verify the HMAC before decrypting the ciphertext, in order
to ensure the ciphertext has not been modified to e.g exploit the
decryption process.

You are right, using an HMAC addresses my concern.

The write method would first append the new cipher, then update the
MAC. When decrypting, one would compare the MAC at the beginning of the
file to the MAC obtained at the end of each cipher block, and stop
when they match.

What is the computational overhead associated with computing the MAC
many times over, is it going to slow down wallet reads significantly?

No, reads would be done purely in memory in any of the json-based scemes. Reads from the file are ~only done when opening/loading a wallet file.
Writes would be append-only to the file (apart from maybe updating a fixed position global MAC), with the occasional consolidation ("apply all updates"). Writes would also update the in-memory representation of course.

That is, the whole wallet file is loaded into memory; writes update both the in-memory representation and the file on disk; reads only touch the in-memory representation. (This is btw how it works already, the goal is to optimise the writes updating the file on disk to not have to rewrite the whole file.)

@ln2max
Copy link

ln2max commented Sep 24, 2021 via email

@SomberNight
Copy link
Member Author

Ah, sorry, I meant overhead with respect to computing HMAC
length_of_file_in_bytes / 16 times, every time the file is read. I
don't know how fast Python's HMAC implementation is.

Well, every time the file is read (i.e. wallet gets opened), we decrypt it. I imagine decrypting it and hashing it has comparable performace. I would not be concerned about hashing the whole file once when opening it taking too long. In any case, we have been doing this for years (the current encryption scheme has an HMAC over the whole file already).

Writes would be append-only to the file (apart from maybe updating a fixed position global MAC)

How good is Python's random-access write, i.e altering just the fixed
position global MAC?

As far as I know, it would be necessary to use the "w" file mode, and
thereby re-write the whole file every time we update the fixed position
global MAC. That would eliminate ~all the benefits of the
append-oriented format.

We have similar logic that updates short chunks of a raw file at fixed positions for the block header storage. It performs well.
See:

with open(filename, 'rb+') as f:
if truncate and offset != self._size * HEADER_SIZE:
f.seek(offset)
f.truncate()
f.seek(offset)
f.write(data)
f.flush()
os.fsync(f.fileno())

Come to think of it, if in-memory operations are not a bottleneck here,
then the only bottleneck which justifies an append-based format would be
if the "a" (append-only) file open mode offers better performance than
"w".

Has anyone benchmarked this to confirm it's the case?

I have not benchmarked the different file open modes;
but I have some stats for writing a large wallet file (~17 MB) to disk on master,
and as you can see, the actual filesystem write is the least of our concerns.

Still, I believe, in principle, partial writes (e.g. appending updates to the end) should help with each of these steps.

@ln2max
Copy link

ln2max commented Oct 15, 2021 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement ✨ topic-walletstorage 💾 not wallet itself but storage/db-related
Projects
None yet
Development

No branches or pull requests

6 participants