Rhizome file list is too slow

[lakeman]

Servald is currently doing too much processing to determine which files you have published while retrieving the list of all files. We need to remove this check from the file listing, and add a separate command to perform this test that can be called from the file details activity.

[quixotique]

The problem occurs every time the Rhizome List activity is opened (select "Share" on the main screen then the "Find" button). It takes a very long time to populate the list of files, because the CPU is running at 100% checking signatures for every Rhizome file.

The reason for the check is for usability: it allows two different file lists to be presented to the user: the "Sent" list of files the user (or any currently open identity on the same phone) has shared, and the "Find" list of all other files received. Very analogous to the well-known "sent" and "inbox" email folders. For reasons of deniability, the Rhizome database does not record the authentic sender of bundles, so the servald rhizome list command must check every bundle against every Rhizome secret in the keyring to see if the bundle was authored here, and set the _selfsigned column to 0 or 1 accordingly.

The CPU cost of the _selfsigned column could be drastically reduced by (a) caching the result of the signature check in memory, so it only has to be computed once per session, and/or (b) introducing the concept of a "non deniable" or "secret" identity, and caching the _selfsigned result in the Rhizome database only for "non deniable" identities. Solution (b) would have the consequence that files shared by a secret identity would never appear in the "Sent" list, only the "Find" list, which is consistent with the notion of secrecy, so should not be too hard to explain in documentation or a FAQ.

The code where the CPU cost is incurred is https://github.com/servalproject/serval-dna/blob/7452c215e2cc1ee397497f469a8bf3d4083d279f/rhizome_database.c#L821

[gardners]

We should be able to disable the test for the "Find" list, because we don't care about authorship there, or do we want "Sent" and "Find" to be distinct lists?

[lakeman]

rhizome_list_manifests doesn't currently filter based on the selfsigned result. The user impact of selfsigned in Serval Mesh is only visible after the details of a file are examined.

The alternative is to remove the selfsigned column from the rhizome list command, and add a new command line query to perform this check for only one manifest.

Then Serval Mesh can delay this check until the detail window is opened. There wouldn't be any user visible impact and we wouldn't compromise the ideal of deniable publishing.

[gardners]

Sounds like a plan. WIll need to be integrated with Andrew's work on the test framework to make sure that we check it when we need to.

[quixotique]

Following further chat discussion with @gardners today, the plan is:

• Alter the rhizome list output as follows:
  • remove the _selfsigned column
  • add a sender column, the SID taken directly from the manifest sender field
  • add an _author column, the SID taken from a new MANIFESTS author table column that records the SID of the non-secret identity which added the manifest, and is NULL for received manifests or manifests added by a secret identity
  • (pending further design) add a _readonly column that indicates whether any currently unlocked identity may alter the manifest -- this is the inverse of the current _selfsigned column and is costly in CPU to compute, although it could take advantage of the sender and _author columns, and also of in-memory caching, which is why it is pending further design.
• The Batphone Rhizome List activity selects files for the "Sent" view whose bundles have an author or sender that matches any currently unlocked keyring identity (including secret identities).
• The Batphone Rhizome List actiivity updates whenever any identity is opened or closed.
• The validity of the sender and _author columns is not cryptographically checked by the rhizome list command, so it is not CPU heavy, but there is a possibility that a forged manifest sender field could put a file into the wrong Rhizome List view.
• Selecting a file in a Rhizome List view (ie, popping up the Rhizome Detail dialog) will perform the cryptographic validation of the sender and _author fields. Failure of the former will purge the offending manifest and mark it (somehow) as known bad. Failure of the latter will NULL the offending MANIFESTS author column.
• Whenever an identity is converted from non-secret to secret, the MANIFESTS table author column must be purged of its SID. Since that column can only ever contain the SIDs of local identities, ie, identities in the local keyring, the presence of a SID in that column betrays its existence, which compromises deniability.

[quixotique]

A slight modification of the design described above:

The MANIFESTS table author column records the cryptographically verified SID of the author that has write permission on the bundle, ie, possesses the Rhizome secret key that generated the BID, and hence can derive the Bundle Secret from the bundle's BK field:

• The MANIFESTS table author column is set to the author SID when a bundle is created locally, so no verification need ever be performed for own bundles (as long as they remain in the Rhizome store).
• When a bundle is imported, the author column is set to NULL to indicate that no verification has been performed yet.
• When an imported manifest with NULL author is examined closely, ie extracted, not merely listed, then the keyring is searched for an identity that is the author. If an author is found, the MANIFESTS table author column is updated. This allows one to regain the ability to overwrite one's own bundles that have been lost but recovered from an exterior Rhizome node.
• The above check automates the "own bundle recovery" mechanism at the expense of a CPU-heavy cryptographic check every time a foreign bundle is examined, but at least listing is fast. This will not scale as many identities are added to the keyring. It will eventually have to be replaced with a means to cache positive and negative verifications in the Rhizome db for local, non-secret identities

The sender is not stored as a MANIFESTS table column for the time being, just extracted from the manifest blob when needed.

The rhizome list command already had a sender column, so two new columns were added to replace the .selfsigned column:

• the .author column is taken directly from the MANIFESTS table author column
• the .fromhere column is 1 if either the author or the sender is present in the keyring; 0 otherwise

The rhizome extract manifest command has two new output fields:

• the .author field is only present if the MANIFESTS table author column contains a SID (after performing the checks described above)
• the .readonly field is 1 if .author is a SID that is present in the keyring; 0 otherwise

[quixotique]

After merging 839de7557c119328c56f07b0cbfa852da9ed02bd the new NaCl implementation and the Rhizome stress test branches, all tests PASS on Linux i686.

On Solaris, all tests PASS except the routing tests all FAIL and one directory_service test fails, due to an unrelated SIGBUS bug recently introduced in the servald mdp ping command.

Closing this issue.