Subject: Re: [bitcoin-dev] Bitcoin vaults with anti-theft recovery/clawback mechanisms

From: Praveen Baratam <[email-masked]>
Date: Tue, 13 Aug 2019 08:14:03 +0530

Bryan,

This is very similar to *CoinVault - Secure Depository and Secure Exchange*
technologies that I have shared with you all.
ᐧ

On Wed, Aug 7, 2019 at 7:23 PM Bryan Bishop via bitcoin-dev <
[email-masked]> wrote:

> Hi,
>
> I have a proposal for implementing bitcoin vaults in a way that does not
> require any soft-forks or other software upgrades, although it could
> benefit
> from SIGHASH_NOINPUT which I'll describe later.
>
> I call them pre-signed vaults.
>
> Vault definition
> ================
>
> Here, a vault is defined as a transaction setup scheme that binds both the
> user
> and the attacker to always using a public observation and delay period
> before a
> weakly-secured hot key is allowed to arbitrarily spend coins. This is the
> same
> definition previously used[1]. During the delay period, there is an
> opportunity
> to initiate recovery/clawback which can either trigger deeper cold storage
> parameters or at least reset the delay period to start over again for the
> same
> keys.
>
> One of the important components of this is the delete-the-key pre-signed
> transaction concept, where only a single transaction is (pre)signed before
> deleting the key. This is basically an emulation of a covenant and
> enforces a
> certain outcome.
>
> Background and motivation
> =========================
>
> I was looking at Eyal and Sirer's 2016 vaults paper [1], and I saw this
> headscratcher:
>
> > Vault transactions use a delay mechanism. We note that vault transactions
> > cannot be implemented with existing timing mechanisms such as
> > CHECKLOCKTIMEVERIFY opcode or transaction locktime.
>
> This was probably written before the introduction of
> OP_CHECKSEQUENCEVERIFY.
> Still, a viable construction would have more steps than just using OP_CSV.
> They
> were probably not thinking about what those steps might be, because in the
> context of the paper they were proposing a bitcoin vault implemented using
> recursive consensus-enforced covenants via a new opcode, which obviously
> cannot
> be deployed without an upgrade fork. Covenants have been discussed for
> years,
> but require new opcodes or other consensus-enforcement changes.
>
> Relative locktimes are useful here because there is no knowledge as to
> when the
> transactions might be broadcasted in the future. The delays need to be
> relative
> to after the transaction is included in the blockchain, not to setup
> initialization time.
>
> Also, from [2]:
>
> > We show that a [vault transaction] mechanism is currently not possible
> in all
> > cryptocurrencies [...] Bitcoin's scripting language requires support for
> > covenants.
>
> I haven't seen any previous proposal for how to implement recursive bitcoin
> vaults without a fork and without a covenant. After asking around, I am
> pretty
> sure this is somewhat novel. The closest I guess is [3].
>
> Vaults are particularly interesting as a bitcoin cold storage security
> mechanism because they enable a publicly observable delay period during
> which
> time a user could be alerted by a watchtower that a thief might be in the
> process of stealing their coins, and then the user may take some actions to
> place the coins back into the vault before the relative timelock expires.
> There
> seems to be no way to get this notification or observation period without a
> vault construction. It might have been assumed it required a covenant.
>
> Having a vault construction might go a long way to discourage would-be
> attackers, on principle that the attacker might be incapable of recovering
> their cost-of-attack because the recovery mechanism can lock up the coins
> indefinitely. Griefing or denial-of-service would still be possible, of
> course,
> but with multisig there might be some ways to put a halt to that as well.
> I am
> working under the assumption that the attacker knows that the user is a
> vault
> user.
>
> Vaults
> ======
>
> The idea is to have a sequence of pre-generated pre-signed transactions
> that
> are generated in a certain way. The basic components are a vaulting
> transaction
> that locks coins into a vault, a delayed-spend transaction which is the
> only
> way to spend from a vault, and a re-vaulting transaction which can
> recover/clawback coins from the delayed-spend transaction. The security of
> this
> scheme is enforced by pre-signing transactions and deleting private keys,
> or
> with the help of SIGHASH_NOINPUT then there's another scheme where private
> keys
> are provably never known. This enforces that there's only a specific set of
> possible outcomes at every step of the vault.
>
> Some examples of what the set of broadcasted transactions might look like
> in
> regular usage:
>
>     coins -> VT -> DST -> exit via hot wallet key
>     coins -> VT -> DST -> RVT
>     coins -> VT -> DST -> RVT -> DST -> ...
>     coins -> VT -> ... -> RVT998 -> nuclear abort
>
> where:
>     VT = vault transaction
>     DST = delayed-spend transaction
>     RVT = re-vaulting transaction
>
> The delayed-spending transaction would have a single output with a script
> like:
> (
>     30 days AND hot wallet key
>  OR 10 days AND re-vaulting public key
>  OR 1 day AND 4-of-7 multisig
>  OR 0 days and super-secure nuclear abort ragequit key
> )
>
> Another diagram:
>
>     VT_100 -> DST -> (optionally) RVT -> coins are now in VT_99
>     VT_99 -> DST -> (optionally) RVT -> coins are now in VT_98
>     ...
>     VT_1 -> burn-all-coins nuclear abort ragequit (final)
>
> Definitions
> ===========
>
> Transactions and components:
>
> * Commitment/funding vault setup transaction. Signed after setting up the
> transaction tree, and it is broadcasted whenever funds are to be placed
> into
> the vault.
>
> * Delayed-spend transaction. Signed during the vault transaction tree
> setup,
> and it is broadcasted when the user wants to withdraw coins from cold
> storage
> or otherwise manipulate the coins. The output script template used by the
> delayed-spend transaction was defined earlier.
>
> * Hot wallet key: Somewhat insecure key. This can also be multisig using
> multiple hot keys.
>
> * Re-vaulting key: It is important to note that the private key either
> never
> existed (SIGHASH_NOINPUT + P2WPK for the re-vaulting transaction) or the
> private key was deleted after pre-signing the re-vaulting transaction.
>
> * 4-of-7 multisig: This is a group of differently-motivated individuals
> who are
> responsible for signing transactions. This multisig group is not necessry
> to
> describe the technique, I just think it's a useful feature for a vault to
> include.
>
> * Nuclear abort key: Also unnecessary. This is a key for which only a
> single
> signed transaction will ever exist, and that single transaction will spend
> to a
> proof-of-burn key like 0x00. This key must be extremely secure, and if
> there
> is any doubt about the ability to keep such a key secured, then it is
> better to
> not include this in the protocol. Alternatively, maybe include it as an
> option
> 50 layers down in the revaulting sequence.
>
> * Nuclear-abort pre-signed transaction. This is signed during transaction
> tree
> setup, before constructing the delayed-spend transaction. It is broadcasted
> only if the user wants to provably relinquish coins forever without giving
> the
> attacker any coins.
>
> * Re-vaulting transaction. This is where the magic happens. The re-vaulting
> transaction is signed during transaction tree setup, before constructing
> the
> delayed-spend transaction for the parent vault. The re-vaulting
> transaction is
> broadcasted when someone wants to prevent a coin withdrawal during the
> public
> observation delay period. The re-vaulting transaction spends the
> delayed-spend
> transaction outputs. It has a single output with a script created by
> running
> the entire vault setup function again. Hence, when the re-vaulting
> transaction
> is confirmed, all of the coins go back into a new identically-configured
> vault
> instead of being relinquished through the delayed-spend transaction
> timeout for
> hot wallet key signing.
>
> * Special case: final transaction. This is the very first pre-signed
> transaction during setup, and the transaction spends the coins using any
> provable burn technique. This is broadcasted only at the end of the game,
> as an
> ultimate abort and forfeiture of coins without giving in to an adversary.
> It's
> similar to the nuclear-abort ragequit transaction but it sits at the same
> place
> that a delayed-spend transaction would, at the very end of the rainbow or
> yellow brick road.
>
> Example log during vault setup
> ==============================
>
> When running the recursive vault setup function, the created artifacts (in
> order) will look like:
>
> 1) choose one of:
>    (first iteration) pre-signed burn-all-coins nuclear abort ragequit
> (final)
>    (all others) a new vault setup transaction spendable only by its
>                 delayed-spend transaction
>
> 2) pre-signed re-vaulting transaction sending to vault setup or final
> transaction, with a unique private key
>
> 3) pre-signed delayed-spend transaction, with a unique private key
>
> 4) vault transaction spendable only by the delayed-spend public key
>
> Pseudocode
> ==========
>
> In pseudocode (where PTX is a pre-signed transaction function with
> private key deletion):
>
>     VT(counter, *args, **kwargs) =
>         if counter == 0:
>             DST = PTX("burn-all-coins")
>         else:
>             next_vault = VT(counter-1, *args, **kwargs)
>             revaulting = PTX("only spendable by next_vault public key")
>             DST = PTX("DST policy including revaulting and other
> conditions")
>         vault = PTX("spendable only by this DST")
>         return vault
>
> Pre-signed transactions
> =======================
>
> What has been known for a while is that a covenant can be somewhat emulated
> using a pre-signed transaction where the user then deletes the private key,
> enforcing that the user's chosen policy must be enforced since there is
> only
> one existing option and there will only ever be one option.
>
> Such a scheme has been previously described for simple one-time and chained
> vaults [3]. I have learned that the author has an implementation that is in
> preparation, for a non-recursive version.
>
> Note that a series of pre-signed transactions can be considered to be an
> emulation of a covenant. Imagine a linear chain of pre-signed transactions
> where each hop has a relative locktime before being able to broadcast the
> next
> transaction. To recover the coins at the end of the rainbow, one would
> need to
> broadcast each sequential transaction in order and wait for the relative
> timelocks to expire each time. Here, covenants provide something like an
> undo
> for bitcoin, but only between pre-determined addresses and scripts.
>
> Fees for pre-signed transactions
> ================================
>
> There's a few different techniques to talk about:
>
> 1) SIGHASH_SINGLE|SIGHASH_ANYONECANPAY to let someone add inputs and
> outputs.
> This can get pretty complex though.
>
> 2) Add a zero-value OP_TRUE output and let anyone spend the zero-value
> output
> and attach a child-pays-for-parent (CPFP) transaction to pay for
> everything.
>
> 3) Pre-sign a variety of different possible fee rates. Unfortunately this
> involves an explosive blow-up in the amount of transaction data to
> generate. It
> might actually be a reasonable blow-up amount, only resulting in a few
> hundred
> megabytes of additional data. But given the other options, this is
> unnecessary.
>
> Delete the key (for pre-signed transactions)
> ============================================
>
> The delete-the-key trick is simple. The idea is to pre-sign at least one
> transaction and then delete the private key, thus locking in that course of
> action.
>
> Unfortunately, delete-the-key doesn't really work for multisig scenarios
> because nobody would trust that anyone else in the scheme has actually
> deleted
> the secret. If they haven't deleted the secret, then they have full
> unilateral
> control to sign anything in that branch of the transaction tree. The only
> time
> that delete-the-key might be appropriate would be where the user who
> deletes
> the key and controls the key during the setup process is also the sole
> beneficiary of the entire setup with the multisig participants.
>
> Alternative fee rates are easier to deal with using delete-the-key,
> compared to
> a technique where the private key never existed which can only be used to
> sign
> one fee rate per public key, requiring an entirely new vault subtree for
> each
> alternative fee rate. With delete-the-key, the alternative fee rates are
> signed
> with the private key before the private key is deleted.
>
> Multisig gated by ECDSA pubkey recovery for provably-unknown keys
> =================================================================
>
> A group can participate in a multisig scheme with provably-unknown ECDSA
> keys.
> Instead of deleting the key, the idea is to agree on a blockheight and then
> select the blockhash (or some function of the chosen blockhash like
> H(H(H(blockhash)))) as the signature. Next, the group agrees on a
> transaction
> and they recover the public key from the signature using ECDSA pubkey
> recovery.
> A pre-signed transaction is created, which will trigger the start of the
> public
> observation period described earlier and also start the clock for the
> bip112
> relative timelock on its output. In the output script, an OR branch
> is added that enables the use of a re-vaulting key which could also be its
> own
> separate multisig construction.
>
> This is incompatible with P2WPKH because the P2WPKH spending scriptSig
> needs to
> have the pubkey (to check the hash of the pubkey against the pubkeyhash in
> the
> scriptPubKey), which in turn makes it incompatible with ECDSA pubkey
> recovery
> which requires a hash of the message. However, with P2WPK and
> SIGHASH_NOINPUT
> instead of P2WPKH it could conceivably work. SIGHASH_NOINPUT is required
> because
> otherwise the input includes a txid which references the public key. With
> P2WPK,
> the scriptSig only needs a signature and not a public key. Note that what
> would
> be required is a version of SIGHASH_NOINPUT that does not commit to the
> public
> key, and I think a few of the NOINPUT proposals are committing to the
> public
> key.
>
> Alternatively, there may be some constructions using the 2-party ECDSA
> techniques or m-n party ECDSA techniques.
>
> Deploying exceedingly large scripts
> ===================================
>
> A brief interlude to share a somewhat obvious construction. I haven't seen
> this
> written down yet.
>
> Suppose there is a bitcoin script that someone is interested in using, but
> it
> far exceeds the size limits and sigop limits. To fix this, they would
> split up
> the script into usable chunks, and then use the delete-the-key mechanism
> (or
> the other one) to create an OR branch that is signable by a single key for
> which only a single signature is known. That new pre-signed transaction
> would
> spend to a script that has the output with the remainder of the script of
> interest. Re-vaulting or clawback clauses can be added to that output as
> well,
> but spending back to the original root script will only work by generating
> new
> scripts and keys (since the final hash isn't known until the whole tree is
> constructed, it's a dependency loop).
>
> Recursively-enforced multi-party multisig bitcoin vaults
> ========================================================
>
> Ideally, to enforce a covenant with impossible fairy dust magic, we would
> ask
> for a bitcoin transaction that could be self-referential because the
> only-one-signature-ever trick requires that the signed message be known
> before
> producing the signature, and the signature has to be known before the
> public
> key can be known, and the public key would have to be included in the
> self-referential message/transaction hash value. So, that's a dependency
> loop
> and it doesn't work. It would be interesting to explore a variation of this
> idea with masking, such that a value X can be replaced by a hash over the
> whole
> script with the X value, even though the real script will have the hash.
> Someone else can figure that one out for me :-).
>
> Instead of the self-referential values attempting to reference the same
> script that is in the process of being constructed, an alternative is to
> use
> the same script template but populate it with different parameters. The
> script
> template gets reused over and over again, all the way down the tree, until
> the
> final transaction which could be >100 years into the future once done
> adding up
> all the relative locktimes. In fact, to create and populate this terrifying
> recursive script tree, the final transaction needs to be created first, and
> then it is given as input to the script template function and that output
> is
> then given to the script template function itself-- and so on. At each
> stage,
> there are additional pre-signed transactions and values to remember.
>
> This can be written as:
>
>     final_transaction = TX(spend to 0x0000 to burn the coins)
>     initial_transaction = F(F(...F(final_transaction))
>
>     (This is missing parameters to indicate to the function what the
> spending
>     keys requirements are to be.)
>
> See earlier explanation for more details.
>
> Each call to the template populating function produces values that each
> must be
> preserved for a very long time. It is less safe to store all of the
> pre-signed
> transactions together at the same time, but more convenient. With less
> redundancy, there is an increased chance of losing data over time, which
> could
> render the coins completely frozen. This doesn't particularly worry me
> because
> forgetting a key has that property already, and this could be likened to
> hundreds of megabytes of extra key data or something. Unlike the much
> smaller
> covenant-based (opcode-based covenant) vault construction, the multiple
> layers
> here can be separately stored and protected, which might be able to protect
> against an adversary that has stolen some of the re-vaulting keys but not
> all
> of them.
>
> Optimizations can be made to store parameters for generating the remainder
> of
> the tree, such as using deterministic key derivation, such that megabytes
> of
> data wouldn't need to be long-term stored. Only the initial parameters
> would
> need to be stored.
>
> Financial privacy for custody
> =============================
>
> One of the concerns raised in [2] is that if all coins at an exchange are
> stored together in the same vault, then attackers would be able to learn
> about
> access control policies by observing scripts and keys. Some privacy can be
> recovered by using segregated vaults, at the cost of additional setup
> complexity and keeping more data in long-term storage.
>
> However, note that I think vaults are also useful for personal cold storage
> solutions.
>
> Fail-deadly mechanism
> =====================
>
> An early nuclear abort option can be added to these scripts. This idea was
> explored in [2]. This would be a very cold very secret key that would
> abort the
> re-vaulting procedure and send all coins to a (provably) nonsense key. This
> allows a vault user to destroy the coins instead of continuously
> monitoring the
> bitcoin blockchain for the rest of his life. The attacker can't recover
> their
> cost of attack if they never get the coins, and this eliminates an entire
> class
> of potential attackers who are directly interested only in financial gain.
> The
> disadvantage is that if the attacker finds the secret key for the
> fail-deadly
> mechanism and uses it, then all of the coins are gone forever.
>
> Multisig variations
> ===================
>
> The re-vaulting key could be the same key at each layer, or only sometimes
> the
> same key, or always a unique key stored separately in another secure
> location.
>
> Additionally, these re-vaulting keys could be subjected to multisig
> schemes, as
> well as Shamir secret sharing schemes or other secret sharing schemes.
>
> The idea of adding the 4-of-7 multisig component is to avoid griefing
> situations, at the cost of the additional security requirements for the
> 4-of-7
> multisig group.
>
> Key rotation for vaults
> =======================
>
> Keeping the same hot wallet key for 100 years is not advisable. Rotate the
> keys
> by setting up a new vault construction and initiating a withdrawal
> transaction
> from the old vault to the new vault.
>
> Single-use seals
> ================
>
> This proposal may have inadvertedly demonstrated a practical way to
> implement
> Peter Todd's single-use seals concept [4]. I am hesitant to say so, though,
> because I think he would ask for a more sophisticated way to verify seal
> closure.
>
> Paid defection
> ==============
>
> It might be advisable to add small rewards for evidence of defection
> amongst
> multiparty multisig setups. Besides amounts spendable by individual keys
> from a
> multisig setup, it may be possible to use a zero-knowledge contingent
> payment
> for a zero-knowledge statement like: I have a signature s over some
> message m
> which validates for pubkey pk where pk is a member of the multisig group.
> Then
> the zkcp transaction would pay for knowledge of defectors. The zkcp
> procedure
> would require interaction with the defector, while the direct pubkey method
> would not. This is similar to companies paying employees to quit when they
> value the payment over the value of continued employment.
>
> Handling change
> ===============
>
> It is important to note that this vault setup is one-time and once-only.
> There
> must only ever be one deposit into one vault. Also, spending some coins
> would
> require sending the change amount back into a new vault.  Alternatively,
> upfront work can be done to set a regular withdrawal stipend or assumption
> about how many coins are left, such that the transaction tree can be
> pre-generated for those possibilities, hence cutting down on future vault
> reinitializations. It would also be possible to commit upfront to only ever
> working in some minimum increment number of bitcoin or something.
>
> It is very important to only fund the vault once, and only with the amount
> that
> was configured when setting up the vault.
>
> References
> ==========
>
> [1] https://fc16.ifca.ai/bitcoin/papers/MES16.pdf
>
> [2]
> http://www0.cs.ucl.ac.uk/staff/P.McCorry/preventing-cryptocurrency-exchange.pdf
>
> [3]
> http://web.archive.org/web/20180503151920/https://blog.sldx.com/re-imagining-cold-storage-with-timelocks-1f293bfe421f?gi=da99a4a00f67
>
> [4]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015350.html
> or
> https://diyhpl.us/wiki/transcripts/building-on-bitcoin/2018/single-use-seals/
> or https://petertodd.org/2016/closed-seal-sets-and-truth-lists-for-privacy
>
> Acknowledgements
> ================
>
> * Jeremy Rubin for pointing out something embarrassingly broken in an
> earlier
> draft.
>
> * Bob McElrath for telling me to use SIGHASH_NOINPUT which I proceeded to
> promptly forget about.
>
> * Andrew Poelstra for the OP_TRUE trick.
>
> * Joe Rayhawk for paid defection.
>
> * Tadge Dryja for pointing out a few differences between SIGHASH_NOINPUT
> proposals.
>
>
>
> Thank you,
>
> - Bryan
> http://heybryan.org/
> _______________________________________________
> bitcoin-dev mailing list
> [email-masked]
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

-- 
Dr. Praveen Baratam

about.me <http://about.me/praveen.baratam>