Subject: [bitcoin-dev] The Cryptographic Relay: An Electrical Device For Smart Transferable Hardware

From: ZmnSCPxj <[email-masked]>
Date: Mon, 20 Jul 2020 14:18:10 +0000

Introduction
============

An electrical relay is an electrically-controlled switch, often diagrammed as:

      +-------------o
      |
      |   \
      |    \
      +--o  o-------o

    o----  |
         ) |
         ) |
         ) |
    o----  |

The terminals at the left feed into a coil.
When electricity passes through the coil, it magnetizes a core, and the magnetism attracts a switch into a closed position, which would let electricity to pass through the terminals at the right.
This can be used to "turn on" or supply power to a different electrical device.

If no electricity is passing through the coil via the terminals on the left, then no electricity can pass through the terminals on the right, as the switch is an open position at default.

This is a fairly simple logic circuitry, upon which more complicated circuitry can be made.

Similarly, a Cryptographic Relay is a hardware electrical component that allows control of some electrical circuit.
It has two terminals which are the two terminals of a switch.
It can also be contacted, for example via Bluetooth, by an electronic computing device.
The Cryptographic Relay has a public key, which represents the current owner of the relay.
If the electronic device is able to provide a proof-of-knowledge of the private key (i.e. a signature) corresponding to the public key that the Cryptographic Relay knows, then it allows the switch to be controlled by that device.

Motivation
==========

Suppose I have a car I wish to sell to you, for Bitcoins.
This car, as it happens, has a Cryptographic Relay: it will only start its engine if it gets a signed message from me using a private key I have on my phone.
It knows my public key, and will only turn off and on at my command.

Now, you want to be able to know that by paying me Bitcoins, you get sole ownership of the car I am selling.

This is in fact, nothing more than a swap operation.
I have an asset, a car, and you have an asset, some Bitcoins.
We want to atomically swap one asset for the other asset, and those assets do not exist in a single asset-assignment system.

Paying Bitcoins For Cars Via Succinct Atomic Swaps
==================================================

Fortunately, there is an atomic swap operation, Succinct Atomic Swaps, which can be used to create an atomic swap between my car and your Bitcoins.

An important part of this Succinct Atomic Swap is that all timeouts are only in one asset-assignment system.
The original Succinct Atomic Swap discussion gives an example of swapping Bitcoins for Litecoins.
Each has its own distinct blockchain, which is a distinct distributed asset-assignment system.

A crucial part of the Succinct Atomic Swap is that all timelocks are only on one asset-assignment system.
The other asset-assignment system need not support anything other than assigning ownership of assets to (homomorphically additive) public keys.

This is important as a major simplification of the Cryptographic Relay:
The relay only needs to know its *current owner*, and does not need to know the current time!

Thus, in order for you to buy my car:

* You set up the Succinct Atomic Swap on the Bitcoin blockchain.
* We generate fresh private keys, then combine them via MuSig, and I transfer the ownership of the car to that MuSig public key.
* If I claim the funds, that atomically reveals my share of the private key to you, so you can claim the car using your private key plus my share and transfer the car to sole control of you.
* If I fail to claim the funds, then when you reclaim your funds at timeout, that atomically reveals your share of the private key to me, so that I can claim the car using my private key plus your share and transfer the car back to sole control of me.

This is in fact the same as the Succinct Atomic Swap example, except that instead of me swapping my Litecoins for your Bitcoins, I am swapping my Cryptographic Relay for your Bitcoins.

Cryptographic Relay Operations
==============================

Thus, a Cryptographic Relay needs to support only the following basic operations.
These operations are triggered by its owner sending a message, plus a signature verifiable by the public key, to the Cryptographic Relay.
(Cryptographer warning: if using Schnorr, the message hashed into the signature also has to include the public key that is signing it, since BIP32 nonhardened derivation allows a Schnorr signature created by one child private key to be trivially malleated into a signature for the same message by a sibling private key; this does not exist in ECDSA due to its nonlinearity.
message sends need not include the public key, it can be added by the cryptographic relay since it has to know the public key of the owner anyway.
Of note is that the bip-340 description of Schnorr includes the public key in the hash operation of signatures as well, and does not require this.)

The only operations necessary are:

1.  Turn on.
2.  Turn off.
3.  Transfer ownership to new pubkey ___.

Due to Succinct Atomic Swaps not requiring any kind of timelock on one asset-assignment system, the Cryptographic Relay need not have any concept of time, as mentioned above, and transfer of ownership can be done by a simple message signed by the current owner transferring ownership to a new public key.

(Cryptographer warning: turn-on/turn-off messages should be challenge-response: the Cryptographic Relay requests signing with a unique nonce included in the message, otherwise previous messages can be captured by third parties and replayed; ownership-transfer messages should probably also include a nonce, or otherwise we could require non-reuse of keys.
This can be implemented with a 64-bit incrementing nonce, which should work for the practical lifetime of any Cryptographic Relay.)

(Cryptographer warning: similarly, ownership-transfer messages should probably be indexed as well with an incrementing nonce, otherwise key reuse would allow signature replay; similarly again, each Cryptographic Relay should have a UUID that is included in message hashes, as otherwise key reuse would allow signature replay for commands to one device to be repeated for another device.)

Lightning
=========

Unfortunately, it seems not possible to transport Succinct Atomic Swap constructions over the Lightning Network.

Succinct Atomic Swaps have an asymmetric setup, unlike the traditional HTLC-based atomic swaps.
This asymmetry makes it difficult to reason about how a forwarding node on the Lightning Network would be able to accept a Succinct Atomic Swap and then send out another Succinct Atomic Swap.

An observation to make is that the Bitcoin-side construction in the Succinct Atomic Swap description has the following branches:

* B gets the money, and A learns a secret from B.
* After a timeout, A gets the money back, and B learns a secret from A.

Unfortunately, the above construction, while instantiatable in a single channel (any absolute-timelock contract enforceable on a blockchain can be instantiated in a channel anchored in that blockchain), cannot be safely *forwarded* over the Lightning Network in a sequence of channels forming a route.

This is because we need to have a different timeout at each forwarding hop, in order to allow a forwarding node enough time to discover an event and react accordingly.
This means that each forwarding node has to have a shorter timeout on its outgoing contract than its incoming contract.

But in the half-Succinct-Atomic-Swap contract, the forwarding node needs to provide a secret in order to reclaim the funds at the timeout.
And it can only discover that secret at the later timeout of the incoming contract.
Thus, it is not safe for the forwarding node to forward any half-Succinct-Atomic-Swap contract.

Thus, we either:

* Prevent old, low-value cryptographic cars from being bought using Lightning, reducing their economic veolocity and preventing moon and lambos.
* OR, we give the Cryptographic Relay a notion of time which makes it compatible with PTLCs that can be routed over Lightning.
  In essence, the PTLC "goes over one more hop", this time transferring ownership of the Cryptographic Relay.

A Cryptographic Notion of Time
==============================

Time stops for no one; it will not stop for thee.

Or, in more science-appropriate terms: the passage of time is the direction in which universal entropy increases.

Now, we can observe that block header hashes are, in fact, low-entropy.
This is because the higher bits of block header hashes are consistently 0; there are thus fewer bits of entropy you can extract from a block header hash.

Now, we can observe that temperature is largely itself also an expression of entropy.
Higher-entropy areas are higher temperature, and lower-entropy areas are lower temperature.
Overall, the temperature differential across the universe decreases in the direction of future time.

However, it is possible to implement a sort of Maxwell's Demon.
Maxwell's Demon is an entity that guards a hole between two containers containing air.
If a high-speed, high-tempreature molecule of air on the left side approaches the hole, Maxwell's Demon magically swats it away, but if a similar high-speed, high-temperature molecule of air on the right side approaches the hole, Maxwell's Demon lets it pass.
It has the reverse policy for low-temperature molecules of air, letting it go from the left container to the right container.

Over time, the temperature of the right container drops, because all the high-temperature molecules have been moved to the left container.

Of course, we already have implementations of Maxwell's Demon.
We call such implementations "refrigerators".

Refrigerators, to do their magic, must consume energy and emit heat.
Indeed, the total heat emitted by the refrigerator is much larger than the heat it removes in the cold part of the refrigerator.
We can verify that the refrigerator is working, trivially, by checking that the supposedly-cold part of the refrigerator is indeed cold.
But we know that refrigerators, to do their work, must consume energy and emit heat.

And we also know that, due to the heat emitted by the refrigerators, the universal level of entropy increases, and we know thereby a direction of time is equivalent to a refrigerator successfully freezing something.

Similarly, in order to create low-entropy ("cold") block header hashes, miners of Bitcoin must consume energy and emit heat.
Bitcoin miners then act similarly to Maxwell's Demon; they reject candidate blocks whose block header hashes are not "cold enough" (i.e. have entropy greater than the difficulty target), and only allow "cold" block headers to be broadcast over the blockchain.

And since we know that:

* The future is where the universal entropy is larger than the past.
* Miners producing blocks must consume energy and emit waste heat (increasing universal entropy).

...then we know that a longer proof-of-work header chain represents more actual physical time passing.

Proof-of-work is therefore also an unforgeable proof-of-time-passing.

Thus, all we need for a cryptographically-secure *measure of time* is a header chain.

Crucially, this is better than SPV security, since we are only measuring the passage of time and do not particularly care about reorgs and the transactions in the block.
The longest chain wins, so the "largest blockheight" can only grow monotonically even if a reorg happens.
Even if the transactions in a reorg are ultimately disconfirmed (double-spent), or turn out to be invalid, the Cryptographic Relay does not depend on their validity, it only cares about time passing in order to implement a timeout.

This is significantly better than having to implement a stable clock on the Cryptographic Relay to implement a timeout.
Clocks may drift, and the Cryptographic Relay might not want to tr\*st external sources to give it a true notion of time.
Loss of power supply may also cause the Cryptographic Relay to lose its clock as well.
Thus, it must use this cryptographic notion of time.

Giving Cryptographic Relays a Notion of Time
============================================

In order to implement timelocks, we can add an `nLockTime` field to ownership-transfer messages for the Cryptographic Relay.

On manufacturing a Cryptographic Relay, the manufacturer stores in unchangeable memory (e.g. burned diode non-erasable PROMs) the block header hash of a sufficiently-deep block (for example, one that has been buried for 6 or so difficulty adjustment periods), its blockheight, and the difficulty target for the adjustment period.

If the Cryptographic Relay receives an ownership-transfer message with `nLockTime` greater than this recorded block height, it demands a header chain rooted at the prerecorded block up to the specified `nLockTime`.
It then validates that the header chain has sufficient difficulty for each adjustment period covered, and also emulates the difficulty adjustment at appropriate blockheights.
This is sufficient proof to it that time has passed since its manufacture, as a header chain is a cryptographic proof of time passing.

This allows me to sell a cryptographic car to you, over Lightning, by this ritual:

* First, we generate fresh keypairs and their combined MuSig pubkey.
* We perform a MuSig signing operation, signing an ownership-transfer message with a future `nLockTime`, transferring ownership from the MuSig pubkey back to my unilateral pubkey.
* I transfer control of the car to the MuSig pubkey.
* We partially perform a second MuSig signing operation, signing an ownership-transfer message with a 0 `nLockTime`, transferring ownership from the MuSig pubkey back to you, but pausing after the `R` exchange.
  * Specifically, after the `R` exchange, you generate the point corresponding to my share of the signature `s`, which you can get from my `R`, your `R`, my public key, and your public key, and the message we agreed on.
* I generate an invoice for the above signature share point (i.e. pay for signature).
* You pay the invoice, making sure that the maximum cltv-delta for the outgoing payment does not exceed the pre-agreed timeout (minus some time margin you deem safe).

Then:

* If you successfully pay the invoice (i.e. I release my share of the signature) you can now complete the signature for the transfer to your unilateral control.
* If you are unable to pay the invoice, then once the future blockheight is reached, I download the Bitcoin block header chain and feed it and the backout ownership-transfer message to the car and regain control of my vehicle.

This provides Lightning-with-PTLCs compatibility (which we expect to be deployed on the network anyway), while still requiring relatively low resources on the Cryptographic Relay hardware (at the cost that timelocked backouts require much bandwidth; but since such backouts are expected to be rare, this may be an acceptable tradeoff).

A Cryptographic Relay accepting this notion of time can continue to be used with Succinct Atomic Swaps, by using ownership-transfer messages with a 0 `nLockTime`, with the advantage that backouts need not download a block header chain to the Cryptographic Relay.

A Case Against Blockchain Proliferation
=======================================

We can argue that the Cryptographic Relay is a device tr\*sted to actually do what we claim it does here.
In particular, its users tr\*st that its manufacturer does not have a secret backdoor, a special public key recognized by every Cryptographic Relay by which the manufacturer can gain ownership of every piece of smart hardware in the world.

This may lead some to propose that a publicly-auditable blockchain can be used to manage the assignment of ownership of Cryptographic Relay devices.
That way, the source code that performs the ownership-assignment can be openly audited, and independent observers can check that the asset-assignment blockchain indeed works using the published source code by compiling it themselves and running it, and checking that it remains in synchrony with the asset-assignment blockchain.

However, I should point out that merely because some blockchain somewhere considers asset X to be owned by pubkey Y, does not mean that the actual real-world asset X will have a control system that responds to pubkey Y.

Or in other words, the manufacturer of the actual real-world asset X can still insert a secret backdoor that ignores the public asset-assignment blockchain anyway.

And since blockchains are massive bandwidth hogs, we should avoid using them unless we gain some actual benefit.

On the other hand, the proposed Cryptographic Relay here is reasonably simple, requires no consensus system.

The best that can be done would be to standardize Cryptographic Relays and encourage multiple manufacturers to follow the same standard.
Such a standard would include communication protocols between the Cryptographic Relay and the controlling devices, but would also include details like voltage levels, current limits, normally-closed vs normally-open vs make-before-break SPDT/DPDT vs break-before-make SPDT/DPDT, physical dimensions of the package(s), etc.

Tr\*st in manufacturers can be acquired, at very high expense, by using cut-and-choose: get a number of Cryptographic Relays, randomly select some of them, then open those and analyze if there are any backdoors, then utilize the rest if the randomly-opened ones do not have any discovered backdoors or other security issues.

Delegated Operators
===================

Another useful capability to add to Cryptographic Relays would be to allow adding operators, which are additional public keys that can turn it on or off, but cannot authorize a transfer of ownership or the addition of new operators.

Only the owner of the Cryptographic Relay can add or delete operators.

For example, suppose you, the buyer of my cryptographic car, represent a typical family share-owned between you and all of your husbands.
Then when purchasing the car from me, you can transfer ownership of the car to a MuSig n-of-n between you and your husbands, rather than unilateral control of yourself.

Of course, practically speaking, only one of you or your husbands can operate the car at once.
Thus, while the ownership of the vehicle is an n-of-n MuSig, you can assign individual keys of yourself and each of your husbands, as operators of the car.

The Cryptographic Relay would need to allocate a fixed amount of space for the number of allowed operators, thus imposing a practical limit on the number of husbands you can have simultaneously.
Unfortunately, the Cryptographic Relay cannot store an arbitrary number of public keys, thus there are limits on the number of husbands a human can have.

Whenever an ownership transfer is performed, all operators are deleted, thus preventing one of the previous operators attempting to start the car and drive it off even though it is semantically owned by someone else.

A car purchased by an extended family, such as a company, might be owned by a k-of-n of the stakeholders of the company, and then employees of the company might be assigned as operators.

Practical Deployment
====================

By focusing on developing the most basic Cryptographic Relay, this provides us with a practical deployment for smart devices that can recognize their owner and be used only by the owner (and its delegated operators).

In particular, any existing non-smart electrical device can be modified post-warranty into a smart device that knows its owner, by adding a Cryptographic Relay hardware device somewhere along the path to its power supply.
For example, a Cryptographic Relay could replace a power switch, or be spliced onto the power cord.

Now, of course such a jury-rigging could be easily bypassed, by simply splicing a wire across its terminals.
Similarly, many existing cars can be started without keys by hot-wiring.
Ultimately, the same can be said of almost any end-user appliance; possession remains 9/10ths of the law.

A Cryptographic Relay is a simple device:

* The design of the device is simple, requiring support for only a few operations.
* The interface of the device is simple: it is only a switch, and easy to integrate into more complex applications.
  The switch may be used as the route for the power supply, or it may be used simply for an electrical connection that is detected by some control system of the appliance to know whether it should act as "on" or "off".
  This simplicity and generality allows simple interfacing with a variety of electrical devices.

The intent is that:

* It is easy to implement and subsequently manufacture the device, so that risks of backdoors being installed by centralized manufacturers is mitigated by having multiple Cryptographic Relay manufacturers competing and incentivized to discover backdoors and other security failures of their competitors.
* It is easy to integrate the device into the design of a more complex device intended for use by an end-user.
  It is also easy to integrate the device, post-design, to a more complex existing device that did not include it.

Collateralizing Cryptographic Relay Devices
===========================================

Giving Cryptographic Relays a notion of time allows them to be used in more complicated contracts.

Suppose after purchasing the cryptographic car from me, you and your husbands find yourselves in tight financial straits.
You and your husbands might then want to take a loan from some entity.

Obviously, that entity will not simply loan out precious Bitcoins unless you promise to pay it back with *more* Bitcoins than what it gave out.
And that entity might want to accept your cryptographic car as collateral for the loan, so that if you are unable to pay, the entity can partially recoup losses by reselling your cryptographic car.

With `SIGHASH_ANYPREVOUT` and Taproot, it becomes possible to trustlessly arrange a collateralized loan on the cryptographic car (to the extent the loan shark tr\*sts that none of you or any of your husbands have replaced the Cryptographic Relay with a backdoored device, at least).

The loan shark arranges a loan in a multi-step process involving multiple PTLC-like constructions:

* First, all of you (you and your husbands, and the loan shark) generate two fresh keypairs.
  * Call the first the "loan-out" keypair.
  * Call the second the "loan-payback" keypair.
* You generate (but do not sign!) a command to transfer control of the car from you to a MuSig(you, your husbands ..., loan shark) using the "loan-out" pubkeys.
* Generate the initial backout command, which transfers from the MuSig loan-out pubkey above, back to you and your husbands, but with an `nLockTime` in the future.
  Get a complete signature for this command with the loan shark and your husbands and you.
  * This backout timeout period should be short, and is needed only if the loan shark suddenly aborts before it hands over the loan to you.
* Sign the transfer of the car from you to the MuSig loan-out and feed it to the car.
* Generate (but do not sign!) the collateralization command, which transfers from the MuSig loan-out pubkey, to a new MusSig(you, your husbands ..., loan shark) using the "loan-payback" pubkeys.
* Generate the collateral-claim command, which transfers from the MuSig loan-payback pubkey to the loan shark, but with an `nLockTime` a little after the due date of your loan.
  Generate a complete signature for this command to the loan shark, which the loan shark will now hold and use in case you do not pay back the loan.
* Generate the collateral-reclaim command, which transfers from the MuSig loan-payback pubkey back to you and your husbands.
  Generate a partial signature for this command from you and your husbands, but with a missing share from the loan shark, and keep this partial signature.
* Generate a Taproot address (called the loan-payback Taproot address) with two SCRIPT branches, with an internal public key equal to the loan-payback pubkey.
  * One SCRIPT branch allows signing by the internal public key with `SIGHASH_ANYPREVOUT`.
  * The other SCRIPT branch imposes a short `OP_CHECKSEQUENCEVERIFY` timeout, and claiming by the MuSig of you and your husbands.
* Generate loan-payback Bitcoin transaction, which spends using a `SIGHASH_ANYPREVOUT` signature on the first branch of the above Taproot address, an amount equal to your loan plus interest, and sending unilateral control to the loan shark.
  Demand an adaptor signature for this transaction, which would reveal to you the loan shark signature share of the collateral-reclaim command.
  Then provide the signature shares for you and your husband to the loan shark.
  * If the loan shark completes this signature and reclaims the loan plus interest, you learn the share to complete the collateral-reclaim command and thereby reclaim your car after paying back the loan.
* Now the loan shark creates (but does not sign!) the loan-out transaction, which pays out the MuSig loan-out pubkey the amount being loaned.
* Generate the loan-out-revert transaction, which spends the loan-out transaction and pays it back to the loan shark, but with an `nLockTime` in the future, nearer than the `nLockTime` of the initial backout command.
  Sign this transaction with you and your husbands and the loan shark.
* The loan shark generates a partial signature for the collateralization command, missing the shares from you and your husbands.
* Generate the loan-out-claim transaction, which spends the loan-out transaction and pays it to you and your husbands.
  The loan shark will demand an adaptor signature for this transaction, which lets it learn the sum of the missing signatures shares for the collateralization command.
  Then the loan shark provides its share of the signature for the loan-out-claim transaction.
* The loan shark signs the loan-out transaction and broadcasts it.
* You now complete the signature for the loan-out-claim transaction and broadcast it.
  The loan shark learns the missing signature shares for the collateralization command and performs it, locking your car into collateralization (where it cannot be transferred unless you, your husbands, and the loan shark agree).
  With the loan-out-claim transaction valid, you can now take the loan.

Then, if you are able to pay back the loan before the due date:

* Send the loan amount plus interest, exactly, to the loan-payback Taproot address.
* If the loan shark accepts the payback of the loan, it reanchors the loan-payback Bitcoin transaction and completes the signature, then claims the paid back loan.
* With the loan-payback signature completed, you learn the partial signature needed to complete the signature for the collateral-reclaim command, and you can now feed it to the car and regain ownership over it.
* If the loan shark does not accept payback of the loan, you can at least recover the loan and interest by the second branch of the loan-payback Taproot address.

If you are unable to pay back the loan:

* The collateral-claim command becomes valid a little after the loan due date, and the loan shark takes unilateral possession of your car to recoup its losses.

The above uses onchain Bitcoins.
Similar setups may be possible over Lightning (there is no need for a `SIGHASH_ANYPREVOUT` in this case, as the loan shark may issue a long-lived invoice that lets you learn its signature share for the collateral-reclaim command signature).