idea, unfinished and unreviewed

Storage:

* Input password and name from user. The name is a combination of their
  own name and a more obscure name (such as the name of their high-school
  sweetheart).
* Generate N by argon2(name), tuned to take 10 minutes.
* Generate list I by sha256 of N+1,2,3.. , hashes truncated to 10 bytes.
* Generate P, a byte chosen at random.
* Generate K by argon2(password+name, salt=P), tuned to take 0.195 (50/256)
  minutes.
* Generate padding to obscure the length of the data. For example,
  pad all keys to be as long as a rsa4096 gpg secret key as exported by
  paperkey (2724 bytes), to prevent targeting types of keys by size.
* AES encrypt (length + checksum + data + padding) with K as the key,
  generating D.
* Split D into 70 byte chunks, call this list C.
* Generate 36 item list T of 80 byte values
  (size of bitcoin's `OP_RETURN`), by concating I[x] with D[x].
* Generate 36 bitcoin transactions storing list T in `OP_RETURN`
* Store the transactions in bitcoin blockchain.

Retrieval:

* Input password and name from user.
* Generate N by argon2(name) (takes 10 minutes)
* Generate list I by sha256 of N+1,2,3.. , hashes truncated to 10 bytes.
* Begin retrieving transactions from bitcoin blockchain, looking for ones
  with `OP_RETURN` starting with values from I. Extract the 70 byte
  chunks from the `OP_RETURN`, generating ordered list C.
* At the same time, generate K by argon2(password+name, salt=p), guessing
  values for P until the right one is found (takes 25 minutes on average)
* Once K and C are available, decrypt (concat C) with K and verify
  checksum.

Password guessing:

Password guessing cost is unchanged from original keysafe. Eg, 25 CPU-years
for a super-weak 19 entropy password.

Before password guessing can begin, the keysafe transactions for a key
need to be found in the blockchain.

The attacker can assume that transactions from around the same time are
grouped together. But, the attacker needs to order the transactions
correctly to recover D. If they get the order wrong, their password
cracking will never succeed. With 36 transactions, and 36 factorial possible
combinations, guessing the right order is infeasible. So, grouping
transactions does not benefit an attacker. The attacker needs to guess the
name and generate I to find the right ordering.

Each guess of a name takes 10 minutes CPU work. This is the same attack
cost as guessing names to download shares from keysafe servers, and a
name that attackers are unlikely to guess prevents this attack, and so
prevents password cracking from starting.

(keysafe servers also impose a proof of work when lots of requests for
shares are being made, which adds to the cost. That PoW is capped at 8
minutes per request. This new design doesn't have that so is somewhat weaker.
To get equal strength as original keysafe, could increase the
work needed to guess a name to 18 minutes?)

Storage servers:

A storage server can be sent the bitcoin transactions, 
and broadcast them to the bitcoin network. This way keysafe does not
need to run a full bitcoin node. It may be possible to use eg, electrum
servers as keysafe storage servers.

Keysafe would need to verify that the transactions reached the
network (by querying retrieval servers).

Retrieval servers:

Retrieval could download the entire bitcoin blockchain and scan it, but
that would be gigabytes of download and take probably days. So instead,
there can be retrieval servers, which the user connects to via tor and
requests keysafe transactions tagged with I.

Retrieval servers learn which transactions contain keys with still active
users who have needed to restore their key. These might be more interesting
transations to try to guess the passwords of. For example, if people are
using keysafe to safely transit borders with their gpg keys, a government
might focus on transactions retrieved soon after a person of interest
crossed a border.

Retrieval servers could provide innaccurate or slow results, or too many
transactions, to try to prevent key restore. But keysafe can know about a
lot of retrieval servers, and query several at once. Get a list of
transaction ids from each, and then go through all the lists in parallel
and request transactions from each server until it has retrieved enough.

Storage cost:

Current cost per bitcoin transaction is $1, so storing a key in keysafe
would cost $36.

Of course, keysafe could also use a blockchain other than bitcoin, eg
lightcoin or dodgecoin have much smaller transaction fees. Using those
would allow storing the whole gpg public+private key, not only the paperkey
minimised private key.

The risk is that all copies of a less widely used blockchain could be lost,
preventing restore of a gpg key. Litecoin is probably big enough and
dodgecoin amusing enough to avoid such a fate for long enough for keysafe
backups to be useful.

Name collisions:

If an attacker can guess the name that a user used with keysafe, and their
password, then as well as decrypting their gpg key, they can add new
transactions using the same name and encrypred with the same password.
Keysafe won't be able to tell which to use, and so the user might restore
a gpg key controlled by the attacker.

Keysafe could prevent this by preferring earlier bitcoin transactions to
later ones.

On the other hand, a user might reuse a name and password when storing an
updated/new gpg key. Then they might expect keysafe to restore the newest
version of the key they stored. 

Keysafe might want to try to retrieve old transactions when storing a key,
to detect if the user is doing that. It could tell the user they need to
pick a different name if it finds any transactions using the name they
chose. This would also guard against several of users picking the same name,
which could otherwise make keysafe restore need to download a lot of
transactions.