diff --git a/app/src/main/java/com/stevesoltys/seedvault/metadata/Metadata.kt b/app/src/main/java/com/stevesoltys/seedvault/metadata/Metadata.kt
index 03f1568..3dacf69 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/metadata/Metadata.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/metadata/Metadata.kt
@@ -13,6 +13,7 @@
 data class BackupMetadata(
     internal val version: Byte = VERSION,
     internal val token: Long,
+    internal val salt: String,
     internal var time: Long = 0L,
     internal val androidVersion: Int = Build.VERSION.SDK_INT,
     internal val androidIncremental: String = Build.VERSION.INCREMENTAL,
@@ -23,6 +24,7 @@
 internal const val JSON_METADATA = "@meta@"
 internal const val JSON_METADATA_VERSION = "version"
 internal const val JSON_METADATA_TOKEN = "token"
+internal const val JSON_METADATA_SALT = "salt"
 internal const val JSON_METADATA_TIME = "time"
 internal const val JSON_METADATA_SDK_INT = "sdk_int"
 internal const val JSON_METADATA_INCREMENTAL = "incremental"
@@ -69,6 +71,7 @@
      */
     internal var time: Long = 0L,
     internal var state: PackageState = UNKNOWN_ERROR,
+    internal var backupType: BackupType? = null,
     internal val system: Boolean = false,
     internal val version: Long? = null,
     internal val installer: String? = null,
@@ -87,7 +90,10 @@
     // There's also a revisionCode, but it doesn't seem to be used just yet
 )
 
+enum class BackupType { KV, FULL }
+
 internal const val JSON_PACKAGE_TIME = "time"
+internal const val JSON_PACKAGE_BACKUP_TYPE = "backupType"
 internal const val JSON_PACKAGE_STATE = "state"
 internal const val JSON_PACKAGE_SYSTEM = "system"
 internal const val JSON_PACKAGE_VERSION = "version"
diff --git a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataManager.kt b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataManager.kt
index a006a30..648816b 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataManager.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataManager.kt
@@ -10,6 +10,8 @@
 import androidx.lifecycle.MutableLiveData
 import androidx.lifecycle.distinctUntilChanged
 import com.stevesoltys.seedvault.Clock
+import com.stevesoltys.seedvault.crypto.Crypto
+import com.stevesoltys.seedvault.encodeBase64
 import com.stevesoltys.seedvault.header.VERSION
 import com.stevesoltys.seedvault.metadata.PackageState.APK_AND_DATA
 import com.stevesoltys.seedvault.metadata.PackageState.NOT_ALLOWED
@@ -24,16 +26,18 @@
 
 @VisibleForTesting
 internal const val METADATA_CACHE_FILE = "metadata.cache"
+internal const val METADATA_SALT_SIZE = 32
 
 @WorkerThread
-class MetadataManager(
+internal class MetadataManager(
     private val context: Context,
     private val clock: Clock,
+    private val crypto: Crypto,
     private val metadataWriter: MetadataWriter,
     private val metadataReader: MetadataReader
 ) {
 
-    private val uninitializedMetadata = BackupMetadata(token = 0L)
+    private val uninitializedMetadata = BackupMetadata(token = 0L, salt = "")
     private var metadata: BackupMetadata = uninitializedMetadata
         get() {
             if (field == uninitializedMetadata) {
@@ -57,8 +61,9 @@
     @Synchronized
     @Throws(IOException::class)
     fun onDeviceInitialization(token: Long, metadataOutputStream: OutputStream) {
+        val salt = crypto.getRandomBytes(METADATA_SALT_SIZE).encodeBase64()
         modifyMetadata(metadataOutputStream) {
-            metadata = BackupMetadata(token = token)
+            metadata = BackupMetadata(token = token, salt = salt)
         }
     }
 
@@ -121,7 +126,11 @@
      */
     @Synchronized
     @Throws(IOException::class)
-    fun onPackageBackedUp(packageInfo: PackageInfo, metadataOutputStream: OutputStream) {
+    fun onPackageBackedUp(
+        packageInfo: PackageInfo,
+        type: BackupType,
+        metadataOutputStream: OutputStream
+    ) {
         val packageName = packageInfo.packageName
         modifyMetadata(metadataOutputStream) {
             val now = clock.time()
@@ -129,10 +138,12 @@
             if (metadata.packageMetadataMap.containsKey(packageName)) {
                 metadata.packageMetadataMap[packageName]!!.time = now
                 metadata.packageMetadataMap[packageName]!!.state = APK_AND_DATA
+                metadata.packageMetadataMap[packageName]!!.backupType = type
             } else {
                 metadata.packageMetadataMap[packageName] = PackageMetadata(
                     time = now,
                     state = APK_AND_DATA,
+                    backupType = type,
                     system = packageInfo.isSystemApp()
                 )
             }
@@ -150,7 +161,8 @@
     internal fun onPackageBackupError(
         packageInfo: PackageInfo,
         packageState: PackageState,
-        metadataOutputStream: OutputStream
+        metadataOutputStream: OutputStream,
+        backupType: BackupType? = null
     ) {
         check(packageState != APK_AND_DATA) { "Backup Error with non-error package state." }
         val packageName = packageInfo.packageName
@@ -161,6 +173,7 @@
                 metadata.packageMetadataMap[packageName] = PackageMetadata(
                     time = 0L,
                     state = packageState,
+                    backupType = backupType,
                     system = packageInfo.isSystemApp()
                 )
             }
diff --git a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataModule.kt b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataModule.kt
index 1ba64b3..68c723a 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataModule.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataModule.kt
@@ -4,7 +4,7 @@
 import org.koin.dsl.module
 
 val metadataModule = module {
-    single { MetadataManager(androidContext(), get(), get(), get()) }
+    single { MetadataManager(androidContext(), get(), get(), get(), get()) }
     single<MetadataWriter> { MetadataWriterImpl(get()) }
     single<MetadataReader> { MetadataReaderImpl(get()) }
 }
diff --git a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataReader.kt b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataReader.kt
index d1e30ac..99598fb 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataReader.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataReader.kt
@@ -112,6 +112,13 @@
                     WAS_STOPPED.name -> WAS_STOPPED
                     else -> UNKNOWN_ERROR
                 }
+                val pBackupType = when (p.optString(JSON_PACKAGE_BACKUP_TYPE)) {
+                    BackupType.KV.name -> BackupType.KV
+                    BackupType.FULL.name -> BackupType.FULL
+                    // we can't fail when format version is 0,
+                    // because when only backing up the APK for example, there's no type
+                    else -> null
+                }
                 val pSystem = p.optBoolean(JSON_PACKAGE_SYSTEM, false)
                 val pVersion = p.optLong(JSON_PACKAGE_VERSION, 0L)
                 val pInstaller = p.optString(JSON_PACKAGE_INSTALLER)
@@ -127,6 +134,7 @@
                 packageMetadataMap[packageName] = PackageMetadata(
                     time = p.getLong(JSON_PACKAGE_TIME),
                     state = pState,
+                    backupType = pBackupType,
                     system = pSystem,
                     version = if (pVersion == 0L) null else pVersion,
                     installer = if (pInstaller == "") null else pInstaller,
@@ -138,6 +146,7 @@
             return BackupMetadata(
                 version = version,
                 token = token,
+                salt = if (version == 0.toByte()) "" else meta.getString(JSON_METADATA_SALT),
                 time = meta.getLong(JSON_METADATA_TIME),
                 androidVersion = meta.getInt(JSON_METADATA_SDK_INT),
                 androidIncremental = meta.getString(JSON_METADATA_INCREMENTAL),
diff --git a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataWriter.kt b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataWriter.kt
index 9ace924..1359c11 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataWriter.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/metadata/MetadataWriter.kt
@@ -30,6 +30,7 @@
             put(JSON_METADATA, JSONObject().apply {
                 put(JSON_METADATA_VERSION, metadata.version.toInt())
                 put(JSON_METADATA_TOKEN, metadata.token)
+                put(JSON_METADATA_SALT, metadata.salt)
                 put(JSON_METADATA_TIME, metadata.time)
                 put(JSON_METADATA_SDK_INT, metadata.androidVersion)
                 put(JSON_METADATA_INCREMENTAL, metadata.androidIncremental)
@@ -42,6 +43,11 @@
                 if (packageMetadata.state != APK_AND_DATA) {
                     put(JSON_PACKAGE_STATE, packageMetadata.state.name)
                 }
+                // We can't require a backup type in metadata at this point,
+                // only when version > 0 and we have actual restore data
+                if (packageMetadata.backupType != null) {
+                    put(JSON_PACKAGE_BACKUP_TYPE, packageMetadata.backupType!!.name)
+                }
                 if (packageMetadata.system) {
                     put(JSON_PACKAGE_SYSTEM, packageMetadata.system)
                 }
diff --git a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/ApkBackup.kt b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/ApkBackup.kt
index adf2eb6..b38fbc7 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/ApkBackup.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/ApkBackup.kt
@@ -25,7 +25,7 @@
 private val TAG = ApkBackup::class.java.simpleName
 
 @Suppress("BlockingMethodInNonBlockingContext")
-class ApkBackup(
+internal class ApkBackup(
     private val pm: PackageManager,
     private val settingsManager: SettingsManager,
     private val metadataManager: MetadataManager
diff --git a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinator.kt b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinator.kt
index 3b934af..e0b0a93 100644
--- a/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinator.kt
+++ b/app/src/main/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinator.kt
@@ -21,6 +21,7 @@
 import androidx.annotation.WorkerThread
 import com.stevesoltys.seedvault.Clock
 import com.stevesoltys.seedvault.MAGIC_PACKAGE_MANAGER
+import com.stevesoltys.seedvault.metadata.BackupType
 import com.stevesoltys.seedvault.metadata.MetadataManager
 import com.stevesoltys.seedvault.metadata.PackageState
 import com.stevesoltys.seedvault.metadata.PackageState.NOT_ALLOWED
@@ -334,7 +335,7 @@
             TAG, "Cancel full backup of ${packageInfo.packageName}" +
                 " because of ${state.cancelReason}"
         )
-        onPackageBackupError(packageInfo)
+        onPackageBackupError(packageInfo, BackupType.FULL)
         full.cancelFullBackup()
     }
 
@@ -381,14 +382,16 @@
             check(!full.hasState()) {
                 "K/V backup has state, but full backup has dangling state as well"
             }
-            onPackageBackedUp(kv.getCurrentPackage()!!) // not-null because we have state
+            // getCurrentPackage() not-null because we have state
+            onPackageBackedUp(kv.getCurrentPackage()!!, BackupType.KV)
             kv.finishBackup()
         }
         full.hasState() -> {
             check(!kv.hasState()) {
                 "Full backup has state, but K/V backup has dangling state as well"
             }
-            onPackageBackedUp(full.getCurrentPackage()!!) // not-null because we have state
+            // getCurrentPackage() not-null because we have state
+            onPackageBackedUp(full.getCurrentPackage()!!, BackupType.FULL)
             full.finishBackup()
         }
         state.expectFinish -> {
@@ -456,10 +459,10 @@
         }
     }
 
-    private suspend fun onPackageBackedUp(packageInfo: PackageInfo) {
+    private suspend fun onPackageBackedUp(packageInfo: PackageInfo, type: BackupType) {
         try {
             plugin.getMetadataOutputStream().use {
-                metadataManager.onPackageBackedUp(packageInfo, it)
+                metadataManager.onPackageBackedUp(packageInfo, type, it)
             }
         } catch (e: IOException) {
             Log.e(TAG, "Error while writing metadata for ${packageInfo.packageName}", e)
@@ -468,13 +471,13 @@
         }
     }
 
-    private suspend fun onPackageBackupError(packageInfo: PackageInfo) {
+    private suspend fun onPackageBackupError(packageInfo: PackageInfo, type: BackupType) {
         // don't bother with system apps that have no data
         if (state.cancelReason == NO_DATA && packageInfo.isSystemApp()) return
         val packageName = packageInfo.packageName
         try {
             plugin.getMetadataOutputStream().use {
-                metadataManager.onPackageBackupError(packageInfo, state.cancelReason, it)
+                metadataManager.onPackageBackupError(packageInfo, state.cancelReason, it, type)
             }
         } catch (e: IOException) {
             Log.e(TAG, "Error while writing metadata for $packageName", e)
diff --git a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataManagerTest.kt b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataManagerTest.kt
index 0aae411..0e120ff 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataManagerTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataManagerTest.kt
@@ -9,6 +9,8 @@
 import androidx.test.ext.junit.runners.AndroidJUnit4
 import com.stevesoltys.seedvault.Clock
 import com.stevesoltys.seedvault.TestApp
+import com.stevesoltys.seedvault.crypto.Crypto
+import com.stevesoltys.seedvault.encodeBase64
 import com.stevesoltys.seedvault.getRandomByteArray
 import com.stevesoltys.seedvault.getRandomString
 import com.stevesoltys.seedvault.metadata.PackageState.APK_AND_DATA
@@ -46,10 +48,11 @@
 
     private val context: Context = mockk()
     private val clock: Clock = mockk()
+    private val crypto: Crypto = mockk()
     private val metadataWriter: MetadataWriter = mockk()
     private val metadataReader: MetadataReader = mockk()
 
-    private val manager = MetadataManager(context, clock, metadataWriter, metadataReader)
+    private val manager = MetadataManager(context, clock, crypto, metadataWriter, metadataReader)
 
     private val time = 42L
     private val token = Random.nextLong()
@@ -58,7 +61,9 @@
         packageName = this@MetadataManagerTest.packageName
         applicationInfo = ApplicationInfo().apply { flags = FLAG_ALLOW_BACKUP }
     }
-    private val initialMetadata = BackupMetadata(token = token)
+    private val saltBytes = Random.nextBytes(METADATA_SALT_SIZE)
+    private val salt = saltBytes.encodeBase64()
+    private val initialMetadata = BackupMetadata(token = token, salt = salt)
     private val storageOutputStream = ByteArrayOutputStream()
     private val cacheOutputStream: FileOutputStream = mockk()
     private val cacheInputStream: FileInputStream = mockk()
@@ -72,6 +77,7 @@
     @Test
     fun `test onDeviceInitialization()`() {
         every { clock.time() } returns time
+        every { crypto.getRandomBytes(METADATA_SALT_SIZE) } returns saltBytes
         expectReadFromCache()
         expectModifyMetadata(initialMetadata)
 
@@ -233,10 +239,10 @@
         every { clock.time() } returns time
         expectModifyMetadata(initialMetadata)
 
-        manager.onPackageBackedUp(packageInfo, storageOutputStream)
+        manager.onPackageBackedUp(packageInfo, BackupType.FULL, storageOutputStream)
 
         assertEquals(
-            packageMetadata.copy(state = APK_AND_DATA, system = true),
+            packageMetadata.copy(state = APK_AND_DATA, backupType = BackupType.FULL, system = true),
             manager.getPackageMetadata(packageName)
         )
         assertEquals(time, manager.getLastBackupTime())
@@ -254,14 +260,15 @@
             time = updateTime,
             packageMetadataMap = PackageMetadataMap() // otherwise this isn't copied, but referenced
         )
-        updatedMetadata.packageMetadataMap[packageName] = PackageMetadata(updateTime, APK_AND_DATA)
+        updatedMetadata.packageMetadataMap[packageName] =
+            PackageMetadata(updateTime, APK_AND_DATA, BackupType.KV)
 
         expectReadFromCache()
         every { clock.time() } returns updateTime
         every { metadataWriter.write(updatedMetadata, storageOutputStream) } throws IOException()
 
         try {
-            manager.onPackageBackedUp(packageInfo, storageOutputStream)
+            manager.onPackageBackedUp(packageInfo, BackupType.KV, storageOutputStream)
             fail()
         } catch (e: IOException) {
             // expected
@@ -294,7 +301,7 @@
         every { clock.time() } returns time
         expectModifyMetadata(updatedMetadata)
 
-        manager.onPackageBackedUp(packageInfo, storageOutputStream)
+        manager.onPackageBackedUp(packageInfo, BackupType.FULL, storageOutputStream)
 
         assertEquals(time, manager.getLastBackupTime())
         assertEquals(PackageMetadata(time), manager.getPackageMetadata(cachedPackageName))
diff --git a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReadWriteTest.kt b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReadWriteTest.kt
index db9881b..f0afbb8 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReadWriteTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReadWriteTest.kt
@@ -4,6 +4,7 @@
 import com.stevesoltys.seedvault.crypto.CryptoImpl
 import com.stevesoltys.seedvault.crypto.KEY_SIZE_BYTES
 import com.stevesoltys.seedvault.crypto.KeyManagerTestImpl
+import com.stevesoltys.seedvault.getRandomBase64
 import com.stevesoltys.seedvault.getRandomString
 import com.stevesoltys.seedvault.header.HeaderReaderImpl
 import com.stevesoltys.seedvault.header.VERSION
@@ -33,8 +34,8 @@
     private val reader = MetadataReaderImpl(cryptoImpl)
 
     private val packages = HashMap<String, PackageMetadata>().apply {
-        put(getRandomString(), PackageMetadata(Random.nextLong(), APK_AND_DATA))
-        put(getRandomString(), PackageMetadata(Random.nextLong(), WAS_STOPPED))
+        put(getRandomString(), PackageMetadata(Random.nextLong(), APK_AND_DATA, BackupType.FULL))
+        put(getRandomString(), PackageMetadata(Random.nextLong(), WAS_STOPPED, BackupType.KV))
     }
 
     @Test
@@ -55,6 +56,7 @@
         return BackupMetadata(
             version = VERSION,
             token = Random.nextLong(),
+            salt = getRandomBase64(32),
             time = Random.nextLong(),
             androidVersion = Random.nextInt(),
             androidIncremental = getRandomString(),
diff --git a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReaderTest.kt b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReaderTest.kt
index a49e9f0..8b9216a 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReaderTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataReaderTest.kt
@@ -2,6 +2,7 @@
 
 import com.stevesoltys.seedvault.Utf8
 import com.stevesoltys.seedvault.crypto.Crypto
+import com.stevesoltys.seedvault.getRandomBase64
 import com.stevesoltys.seedvault.getRandomString
 import com.stevesoltys.seedvault.metadata.PackageState.QUOTA_EXCEEDED
 import com.stevesoltys.seedvault.metadata.PackageState.UNKNOWN_ERROR
@@ -90,6 +91,7 @@
                 "org.example", PackageMetadata(
                     time = Random.nextLong(),
                     state = QUOTA_EXCEEDED,
+                    backupType = BackupType.FULL,
                     version = Random.nextLong(),
                     installer = getRandomString(),
                     sha256 = getRandomString(),
@@ -123,6 +125,7 @@
         json.put("org.example", JSONObject().apply {
             put(JSON_PACKAGE_TIME, Random.nextLong())
             put(JSON_PACKAGE_STATE, getRandomString())
+            put(JSON_PACKAGE_BACKUP_TYPE, BackupType.FULL.name)
             put(JSON_PACKAGE_VERSION, Random.nextLong())
             put(JSON_PACKAGE_INSTALLER, getRandomString())
             put(JSON_PACKAGE_SHA256, getRandomString())
@@ -130,7 +133,9 @@
         })
         val jsonBytes = json.toString().toByteArray(Utf8)
         val metadata = decoder.decode(jsonBytes, metadata.version, metadata.token)
+        assertEquals(this.metadata.salt, metadata.salt)
         assertEquals(UNKNOWN_ERROR, metadata.packageMetadataMap["org.example"]!!.state)
+        assertEquals(BackupType.FULL, metadata.packageMetadataMap["org.example"]!!.backupType)
     }
 
     @Test
@@ -142,6 +147,7 @@
         val jsonBytes = json.toString().toByteArray(Utf8)
         val metadata = decoder.decode(jsonBytes, metadata.version, metadata.token)
         assertFalse(metadata.packageMetadataMap["org.example"]!!.system)
+        assertNull(metadata.packageMetadataMap["org.example"]!!.backupType)
     }
 
     @Test
@@ -149,12 +155,14 @@
         val json = JSONObject(metadataByteArray.toString(Utf8))
         json.put("org.example", JSONObject().apply {
             put(JSON_PACKAGE_TIME, Random.nextLong())
+            put(JSON_PACKAGE_BACKUP_TYPE, BackupType.KV.name)
         })
         val jsonBytes = json.toString().toByteArray(Utf8)
         val result = decoder.decode(jsonBytes, metadata.version, metadata.token)
 
         assertEquals(1, result.packageMetadataMap.size)
         val packageMetadata = result.packageMetadataMap.getOrElse("org.example") { fail() }
+        assertEquals(BackupType.KV, packageMetadata.backupType)
         assertNull(packageMetadata.version)
         assertNull(packageMetadata.installer)
         assertNull(packageMetadata.signatures)
@@ -166,6 +174,7 @@
         return BackupMetadata(
             version = 1.toByte(),
             token = Random.nextLong(),
+            salt = getRandomBase64(METADATA_SALT_SIZE),
             time = Random.nextLong(),
             androidVersion = Random.nextInt(),
             androidIncremental = getRandomString(),
diff --git a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataV0ReadTest.kt b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataV0ReadTest.kt
index 0cf33d5..d5796ae 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataV0ReadTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataV0ReadTest.kt
@@ -54,6 +54,7 @@
     ) = BackupMetadata(
         version = 0x00,
         token = 1337L,
+        salt = "",
         time = 2342L,
         androidVersion = 30,
         androidIncremental = "sdfqefpojlfj",
diff --git a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataWriterDecoderTest.kt b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataWriterDecoderTest.kt
index a85bbe6..aa1c23f 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataWriterDecoderTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/metadata/MetadataWriterDecoderTest.kt
@@ -1,6 +1,7 @@
 package com.stevesoltys.seedvault.metadata
 
 import com.stevesoltys.seedvault.crypto.Crypto
+import com.stevesoltys.seedvault.getRandomBase64
 import com.stevesoltys.seedvault.getRandomString
 import com.stevesoltys.seedvault.metadata.PackageState.APK_AND_DATA
 import com.stevesoltys.seedvault.metadata.PackageState.NOT_ALLOWED
@@ -35,8 +36,8 @@
     fun `encoded metadata matches decoded metadata (with package, no apk info)`() {
         val time = Random.nextLong()
         val packages = HashMap<String, PackageMetadata>().apply {
-            put(getRandomString(), PackageMetadata(time, APK_AND_DATA))
-            put(getRandomString(), PackageMetadata(time, WAS_STOPPED))
+            put(getRandomString(), PackageMetadata(time, APK_AND_DATA, BackupType.FULL))
+            put(getRandomString(), PackageMetadata(time, WAS_STOPPED, BackupType.KV))
         }
         val metadata = getMetadata(packages)
         assertEquals(
@@ -52,6 +53,7 @@
                 getRandomString(), PackageMetadata(
                     time = Random.nextLong(),
                     state = APK_AND_DATA,
+                    backupType = BackupType.FULL,
                     version = Random.nextLong(),
                     installer = getRandomString(),
                     splits = listOf(
@@ -78,6 +80,7 @@
                 getRandomString(), PackageMetadata(
                     time = Random.nextLong(),
                     state = QUOTA_EXCEEDED,
+                    backupType = BackupType.FULL,
                     system = Random.nextBoolean(),
                     version = Random.nextLong(),
                     installer = getRandomString(),
@@ -89,6 +92,7 @@
                 getRandomString(), PackageMetadata(
                     time = Random.nextLong(),
                     state = NO_DATA,
+                    backupType = BackupType.KV,
                     system = Random.nextBoolean(),
                     version = Random.nextLong(),
                     installer = getRandomString(),
@@ -121,6 +125,7 @@
         return BackupMetadata(
             version = Random.nextBytes(1)[0],
             token = Random.nextLong(),
+            salt = getRandomBase64(32),
             time = Random.nextLong(),
             androidVersion = Random.nextInt(),
             androidIncremental = getRandomString(),
diff --git a/app/src/test/java/com/stevesoltys/seedvault/transport/CoordinatorIntegrationTest.kt b/app/src/test/java/com/stevesoltys/seedvault/transport/CoordinatorIntegrationTest.kt
index 234e8d9..52f20e4 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/transport/CoordinatorIntegrationTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/transport/CoordinatorIntegrationTest.kt
@@ -13,6 +13,7 @@
 import com.stevesoltys.seedvault.encodeBase64
 import com.stevesoltys.seedvault.header.HeaderReaderImpl
 import com.stevesoltys.seedvault.header.MAX_SEGMENT_CLEARTEXT_LENGTH
+import com.stevesoltys.seedvault.metadata.BackupType
 import com.stevesoltys.seedvault.metadata.MetadataReaderImpl
 import com.stevesoltys.seedvault.metadata.PackageMetadata
 import com.stevesoltys.seedvault.metadata.PackageState.UNKNOWN_ERROR
@@ -33,7 +34,6 @@
 import com.stevesoltys.seedvault.transport.restore.KVRestorePlugin
 import com.stevesoltys.seedvault.transport.restore.OutputFactory
 import com.stevesoltys.seedvault.transport.restore.RestoreCoordinator
-import com.stevesoltys.seedvault.transport.restore.RestorePlugin
 import com.stevesoltys.seedvault.ui.notification.BackupNotificationManager
 import io.mockk.CapturingSlot
 import io.mockk.Runs
@@ -93,7 +93,6 @@
         notificationManager
     )
 
-    private val restorePlugin = mockk<RestorePlugin>()
     private val kvRestorePlugin = mockk<KVRestorePlugin>()
     private val kvRestore = KVRestore(kvRestorePlugin, outputFactory, headerReader, cryptoImpl)
     private val fullRestorePlugin = mockk<FullRestorePlugin>()
@@ -172,13 +171,11 @@
             backupPlugin.getOutputStream(token, FILE_BACKUP_METADATA)
         } returns metadataOutputStream
         every {
-            metadataManager.onApkBackedUp(
-                packageInfo,
-                packageMetadata,
-                metadataOutputStream
-            )
+            metadataManager.onApkBackedUp(packageInfo, packageMetadata, metadataOutputStream)
         } just Runs
-        every { metadataManager.onPackageBackedUp(packageInfo, metadataOutputStream) } just Runs
+        every {
+            metadataManager.onPackageBackedUp(packageInfo, BackupType.KV, metadataOutputStream)
+        } just Runs
 
         // start and finish K/V backup
         assertEquals(TRANSPORT_OK, backup.performIncrementalBackup(packageInfo, fileDescriptor, 0))
@@ -252,7 +249,9 @@
         coEvery {
             backupPlugin.getOutputStream(token, FILE_BACKUP_METADATA)
         } returns metadataOutputStream
-        every { metadataManager.onPackageBackedUp(packageInfo, metadataOutputStream) } just Runs
+        every {
+            metadataManager.onPackageBackedUp(packageInfo, BackupType.KV, metadataOutputStream)
+        } just Runs
 
         // start and finish K/V backup
         assertEquals(TRANSPORT_OK, backup.performIncrementalBackup(packageInfo, fileDescriptor, 0))
@@ -314,7 +313,9 @@
                 metadataOutputStream
             )
         } just Runs
-        every { metadataManager.onPackageBackedUp(packageInfo, metadataOutputStream) } just Runs
+        every {
+            metadataManager.onPackageBackedUp(packageInfo, BackupType.FULL, metadataOutputStream)
+        } just Runs
 
         // perform backup to output stream
         assertEquals(TRANSPORT_OK, backup.performFullBackup(packageInfo, fileDescriptor, 0))
diff --git a/app/src/test/java/com/stevesoltys/seedvault/transport/TransportTest.kt b/app/src/test/java/com/stevesoltys/seedvault/transport/TransportTest.kt
index 6691804..74795d5 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/transport/TransportTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/transport/TransportTest.kt
@@ -10,8 +10,10 @@
 import com.stevesoltys.seedvault.Clock
 import com.stevesoltys.seedvault.MAGIC_PACKAGE_MANAGER
 import com.stevesoltys.seedvault.crypto.Crypto
+import com.stevesoltys.seedvault.getRandomBase64
 import com.stevesoltys.seedvault.getRandomString
 import com.stevesoltys.seedvault.metadata.BackupMetadata
+import com.stevesoltys.seedvault.metadata.METADATA_SALT_SIZE
 import com.stevesoltys.seedvault.metadata.MetadataManager
 import com.stevesoltys.seedvault.settings.SettingsManager
 import io.mockk.every
@@ -45,6 +47,7 @@
     }
     protected val metadata = BackupMetadata(
         token = token,
+        salt = getRandomBase64(METADATA_SALT_SIZE),
         androidVersion = Random.nextInt(),
         androidIncremental = getRandomString(),
         deviceName = getRandomString()
diff --git a/app/src/test/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinatorTest.kt b/app/src/test/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinatorTest.kt
index bac93f4..089c573 100644
--- a/app/src/test/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinatorTest.kt
+++ b/app/src/test/java/com/stevesoltys/seedvault/transport/backup/BackupCoordinatorTest.kt
@@ -15,6 +15,7 @@
 import com.stevesoltys.seedvault.MAGIC_PACKAGE_MANAGER
 import com.stevesoltys.seedvault.coAssertThrows
 import com.stevesoltys.seedvault.getRandomString
+import com.stevesoltys.seedvault.metadata.BackupType
 import com.stevesoltys.seedvault.metadata.PackageMetadata
 import com.stevesoltys.seedvault.metadata.PackageState.NOT_ALLOWED
 import com.stevesoltys.seedvault.metadata.PackageState.NO_DATA
@@ -254,7 +255,9 @@
         every { kv.getCurrentPackage() } returns packageInfo
         every { settingsManager.getToken() } returns token
         coEvery { plugin.getOutputStream(token, FILE_BACKUP_METADATA) } returns metadataOutputStream
-        every { metadataManager.onPackageBackedUp(packageInfo, metadataOutputStream) } just Runs
+        every {
+            metadataManager.onPackageBackedUp(packageInfo, BackupType.KV, metadataOutputStream)
+        } just Runs
         every { kv.finishBackup() } returns result
         every { metadataOutputStream.close() } just Runs
 
@@ -272,7 +275,9 @@
         every { full.getCurrentPackage() } returns packageInfo
         every { settingsManager.getToken() } returns token
         coEvery { plugin.getOutputStream(token, FILE_BACKUP_METADATA) } returns metadataOutputStream
-        every { metadataManager.onPackageBackedUp(packageInfo, metadataOutputStream) } just Runs
+        every {
+            metadataManager.onPackageBackedUp(packageInfo, BackupType.FULL, metadataOutputStream)
+        } just Runs
         every { full.finishBackup() } returns result
         every { metadataOutputStream.close() } just Runs
 
@@ -302,7 +307,8 @@
             metadataManager.onPackageBackupError(
                 packageInfo,
                 QUOTA_EXCEEDED,
-                metadataOutputStream
+                metadataOutputStream,
+                BackupType.FULL
             )
         } just Runs
         coEvery { full.cancelFullBackup() } just Runs
@@ -325,7 +331,12 @@
         assertEquals(0L, backup.requestFullBackupTime())
 
         verify(exactly = 1) {
-            metadataManager.onPackageBackupError(packageInfo, QUOTA_EXCEEDED, metadataOutputStream)
+            metadataManager.onPackageBackupError(
+                packageInfo,
+                QUOTA_EXCEEDED,
+                metadataOutputStream,
+                BackupType.FULL
+            )
         }
         verify { metadataOutputStream.close() }
     }
@@ -341,7 +352,8 @@
             metadataManager.onPackageBackupError(
                 packageInfo,
                 NO_DATA,
-                metadataOutputStream
+                metadataOutputStream,
+                BackupType.FULL
             )
         } just Runs
         coEvery { full.cancelFullBackup() } just Runs
@@ -361,7 +373,12 @@
         assertEquals(0L, backup.requestFullBackupTime())
 
         verify(exactly = 1) {
-            metadataManager.onPackageBackupError(packageInfo, NO_DATA, metadataOutputStream)
+            metadataManager.onPackageBackupError(
+                packageInfo,
+                NO_DATA,
+                metadataOutputStream,
+                BackupType.FULL
+            )
         }
         verify { metadataOutputStream.close() }
     }