A proposal by Dr. Mark B Lundeberg, 2018 Feb 21
bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2
This is a proposal for reducing the risk of accepting unconfirmed (zero-conf) transactions in Bitcoin-like cryptocurrencies. Accepting such transactions is typically safe, however there is always the risk of double-spending by a malicious payer. Like many past systems proposed for avoiding double spending, this method involves trusted third parties, however the design here should simplify third party accountability as much as possible.
The core concept of the system is a sign-once guarantor: a simple unattended program run by a known reputable public figure or company, that has only one task: use its private key to sign all transactions submitted to it, except never sign the same transaction input twice.
A payment sender consigns temporary partial control of funds to one or more guarantors using a time-locked smart contract (InstaConf address). The sender keeps ownership of his funds at all times and does not need to trust the guarantor. In the worst cases of problems with the guarantor, the sender recovers full control after the fallback time encoded in the contract.
The only way to double-spend from this address would involve the guarantor signing two different transactions. In the such an event, the reputation of the guarantor would be immediately and automatically destroyed in the public space, as all observers on the network would see the conflicting guarantor signatures.
The payment receiver does not have to trust the sender, and can directly see from the smart contract which guarantors are involved and the duration of guarantee (sender fallback time). This allows the receiver to make a quick risk estimate and, for many everyday purposes, the receiver thus has a way to instantly accept unconfirmed payments with vanishing risk.
This proposal requires no changes to bitcoin protocol, however it will require the sender to use custom wallet software/plugins analogous to existing two-factor wallets. The receiver does not necessarily require custom software.
This phase is performed by the sender alone, using publicly available information from guarantors and from possible receivers. It should be performed in advance (at least an hour) of the next phase.
The sender funds a P2SH address (InstaConf address) corresponding to the following redeem script:
<SeKey> CHECKSIGVERIFY
DEPTH NOTIF
<FBTime> CHECKLOCKTIMEVERIFY
ELSE
<GuKey> CHECKSIG
ENDIF
where SeKey is a public key owned by the sender, GuKey is a guarantor's
public key, and FBTime is a fallback time. In words, a coin sent to this P2SH
address can be spent before FBTime with both sender and guarantor signatures.
It can also be spent after FBTime with the sender signature alone.
The sender should choose a guarantor service (GuKey) and fallback time value
FBTime which he believes will provide good coverage over the possible
receivers who he may want to pay over the next while. Receivers should somehow
advertise which set of guarantors they trust, and the minimum fallback
durations. A multisig guarantee can be used to strengthen the trust (see
Multisig guarantors). The sender does not need to decide any further details
just yet.
After the P2SH funding is confirmed on the blockchain, the sender now has a loaded InstaConf address. These addresses can be thought of as 'instant wallets' and a deterministic wallet procedure is possible (see Extensions section).
This phase is performed by the sender, in communication with a specific receiver.
Later on, the sender comes across a receiver who he wants to pay, but the payment has to get settled ASAP! Normal confirmation times are too long, but luckily, the receiver says he accepts InstaConf.
Once the receiver has requested a payment of a given amount to a particular address, the sender prepares the InstaConf transaction (called "Tx" from here on). This transaction inputs from one or more InstaConf addresses that were funded in the previous phase ; it outputs to the receiver and a change address.
The sender should structure this transaction in a way that will be acceptable to the receiver, i.e., satisfying conditions listed in Phase 4. This may involve the receiver's payment request also stating a certain minimum mining fee and a minimum fallback duration, and a list of allowed guarantors. Alternatively, it may involve a back-and-forth negotiation between sender and receiver software. Or, the sender can just make a guess and hope for the best.
This phase is performed by guarantor and sender.
The sender now connects to the guarantor and submits the Tx. After
authenticating the sender,1 the guarantor checks the inputs of the
Tx against its database of previously-signed inputs. Note that inputs are
defined as unspent transaction outputs (txid,outidx). If any inputs are found
matching, it refuses to proceed and returns an error to the sender ("attempt to
double-sign"). Otherwise, the guarantor records the inputs in its database,
signs the Tx, and returns the signatures to the sender.
The sender then himself signs the Tx (hashtype ALL), and broadcasts this
completed Tx to the bitcoin network. Once the receiver sees the full
transaction, he can evaluate the risks in accepting the InstaConf, as
described in next phase.
1 : Authentication of the sender's identity means confirming ownership of inputs; see Technical details section below.
The receiver examines the Tx and evaluates the overall risk of instantly accepting it without confirmation, considering the following factors:
-
Tx follows safety rules ensuring sender cannot double spend. (see Tx safety rules)
-
What is the probability of the Tx confirming before
FBTimeis reached? (based on transaction fees, network congestion, etc.) If it does not confirm soon, how much additional cost will be incurred with a Child-Pays-For-Parent transaction? (see Risk model) -
Is the guarantor reputable and in good standing? What are the risks if the guarantor is compromised? (see Risk model)
If the receiver lacks the ability to evaluate these risks, he can consult fourth-party verification websites (analogues of today's BlockCypher) that provide an expert evaluation; or, he can have payments directed to his payment processor who swallows the risk by insuring all incoming payments, for a fee.
If the Tx is unacceptable, the receiver will unfortunately have to inconvenience the sender by requiring him to wait for the transaction to confirm normally.
Up until the signing phase, the sender can quickly cancel his InstaConf
address any time by constructing an InstaConf payment to himself. Or, he can
ask the the guarantor to release control (guarantor signature with sighash flag
NONE|ANYONECANPAY).
If the guarantor becomes unresponsive or uncooperative, or if the sender
accidentally requests the wrong signature from the guarantor, then the sender
must wait until FBTime to recover control of the InstaConf input.
Replacing the CHECKSIG operation with CHECKMULTISIG allows a stronger
guarantee and/or permits for backup guarantors.
| Guarantee strength | No backups | One backup | Two backups |
|---|---|---|---|
| Single | 1-of-1 | 2-of-3 | 3-of-5 |
| Double | 2-of-2 | 3-of-4 | 4-of-6 |
| Triple | 3-of-3 | 4-of-5 | 5-of-7 |
i.e., a 3-of-3 multisig guarantee means that all three guarantors would have to misbehave (provide double signatures) in order to double spend. A 3-of-4 multisig means at least two guarantors would have to misbehave in order to double spend, and it allows for a backup --- in case one guarantor is temporarily unavailable, or not trusted by receiver.
If multiple guarantors are used, they should have diverse security/ownership so as to have uncorrelated risk of compromise.
The receiver should not trust any InstaConf transaction that would allow
senders to double-spend without a guarantor double-signature. Note that in the
case of multiple inputs, the risk is governed by the weakest input (smallest
FBTime, least trustworthy guarantor) since only one input needs to be
double-spent in order to invalidate the entire transaction. Thus, at minimum
-
All inputs must have trusted guarantor signatures.
-
Guarantor signatures must have hashtype
ALLorALL|ANYONECANPAY, such that they dedicate the input to the specific output list. -
All inputs must be confirmed several times on the blockchain, to avoid double-spend attacks by sender on the InstaConf address itself.
-
Input sequence numbers must be
MAX-1. There is no reason for a sincere sender to use replace-by-fee since he cannot get a second guarantor signature. -
All
FBTimevalues must be at least several hours in the future, due to how block timestamps are flexible. -
The Tx must be fully valid: broadcastable and mine-able.
The sender needs know a URL to communicate with the guarantor. To this end, there should be public databases where the guarantors can periodically publish a signed, time-stamped status message indicating one or more submission URLs. The sender's wallet software should periodically refresh this status message as to be ready at signing time.
Guarantors may also use the message to signal other status information: upcoming scheduled downtimes, permanent revocations in case of key loss/compromise/supercession, signed endorsements of other guarantors and child keys, expiry times, etc. In this way senders can decide whether they want to lock their funds with that particular guarantor key.
Receivers also need to periodically keep up to date on the status of the guarantor, specifically about whether the guarantor has been misbehaving. In order to rapidly spread the news of double-signature events, it's recommended that a kind of gossip network be available. When a double signature event happens, each node can spread the news. As long as this is restricted to a specific set of known guarantors, this gossip network is immune to spamming attacks (each node only propagates gossip after quickly verifying a double signature).
The sender submits the following request to the guarantor:
request body:
string literal: "SIGN_ONCE"
<Tx: the target Tx with empty scriptSig fields>
<I: list of instructions to guarantor, one per Tx input>
auth:
<S: list of authentication signatures>
The instructions list I indicates for each input in Tx, one of:
- "Skip", or,
- "Please sign this input using hashtype
N. The redeem script isR."
The authentication signatures list S is constructed by examining each input
and extracting the owner key SeKey, then using that key to sign the hash of
the request body.2
The guarantor examines the request for flaws:
- A requested input has already been signed by guarantor.
- Attempt to double sign via duplicated inputs.
- Unrecognized redeem script type (cannot identify
SeKeyfromR). - Input does not require guarantor signature (
Rdoesn't containGuKey). - Cannot find a transaction matching input txid.2
Rdoes not match P2SH address from input transaction.2- Invalid authentication signatures.
- (extensions) Insufficient fee to guarantor, forbidden hashtype, etc.
If there are no issues, the guarantor records all requested inputs into its database and signs them; signatures returned to sender.
To ease multisig guarantees, the protocol should allow for senders to initially request a test (e.g., sending an empty signature list). Instead of signing the inputs, the guarantor would examine the validity of the request and return "OK" if it had no flaws. After getting the "OK" from every guarantor, the sender then can authorize each one to sign the transaction. (this avoids lockups as would happen in a 2-of-2 if the first guarantor signs a transaction, but the second guarantor refuses.)
2 : The owner of the input must sign the request, otherwise anyone can
lock up an InstaConf input by a fake request. The guarantor needs access to
the previous transaction in order to observe that R (containing owner key)
truly matches the P2SH address from the previous transaction.
A reputable guarantor turned malicious, or a hacker who has copied the guarantor private key, can do serious damage by scamming with double-spend attacks. These scams however must all occur simultaneously, as it would be immediately apparent after the attack that the guarantor key cannot be trusted (due to publicly visible double signatures).
In-person small money sales would be quite safe. For an attacker, it would a huge waste of the key's reputation, since it cannot be repeated. Thus, I believe the classic "buying coffee" or restaurant use cases are the ideal application for single-guarantor InstaConf transactions.
The best target for an attacker would be: double-spending on a single high-value sale, or, patiently waiting to do a Finney attack simultaneously on thousands of online fast-service websites that instantly sell fungible products to clients (e.g., fast cryptocurrency exchanges like ShapeShift.io). Such sensitive receivers need a more cautious approach in accepting InstaConf:
-
require multisig guarantees, which are a threat only in the rare situation of simultaneous guarantor compromise, or,
-
refuse to instantly accept single-guarantor transactions above some value (e.g., $1000), and, be cautious if there is a sudden spike in the total unconfirmed value on network associated with that guarantor.
An expert risk model can combine these two approaches, by taking into account the probability of simultaneous compromise. For example with a 3-of-3 multisig where the three guarantors are known to be unaffiliated and run diverse security systems, the probability of simultaneous compromise is extremely low and hence much higher valued transactions can be trusted. For any given transaction, the risk model can evaluate the total unconfirmed value on network involving those guarantors, and thereby set an upper limit on the total profit that may be gained by an attack.
Network congestion can threaten to prevent confirmation of the transaction
before FBTime is reached, after which the sender may try to perform a
double spend (without involving the guarantor). In this case, the receiver
should use Child-Pays-For-Parent to clear the transaction more quickly. The
risk and cost of this eventuality should be accounted for by the receiver.
It is impossible for the guarantor or receiver to steal funds from the sender. Any misbehaviour on the part of guarantor results, at worst, in the temporary lockup of funds. The receiver has no power as his signature is not involved.
The guarantor follows a simple and automatic procedure and does not have to trust sender/receiver at all, nor even know who they are. The only mistake it can make is to destroy its reputation by double-signing an input. Naturally this means the guarantor's signing system must be protected with high security measures.
As the guarantor is a public entity, some spamming / DDOS protection will be prudent (see DDOS section below).
The sender should use a proxy to hide his true IP address from the guarantor.
To create some 'blending-into-crowd' anonymity, it is recommended that all
FBTime values be Unix times that are multiples of 86400 seconds.
In the best case, usage of InstaConf addresses leaks the following additional correlated information onto the blockchain:
-
Decision to use InstaConf.
-
Choice of guarantor / set of guarantors.
-
Guarantor signature hashtype -- guarantee (
ALL) or release (NONE). -
Account funding time, spending time, and
FBTime.
The method is closely related to GreenAddress,
which provides guarantees on zero-confirmation transactions through 2-of-2
multisig, plus providing a future-nLockTimed refund as fallback.
Some specific disadvantages of GreenAddress (which are overcome in InstaConf):
-
It requires setup communication or even account creation between sender and guarantor, which may frustrate anonymization.
-
If a receiver is scammed via GreenAddress, it is not trivially provable. By staking InstaConf reputation on a simple computer-testable fact (never signed twice) it means that the news of misbehaviour can be spread instantly.
-
Single point of failure: GreenAddress is designed to work with one guarantor only. In contrast many InstaConf guarantors can be in operation and the receiver is free to choose which subset of them he trusts, or to demand multisig guarantors.
-
Multisig wallets may (bizarrely) get snagged under KYC/AML regulations (1,2). If this happens, InstaConf may still fall outside of regulation.
-
The
nLockTimevalue for refund is not visible to the receiver, hence the receivers do not immediately know how long it is until the sender can trigger a refund. -
Technically the
nLockTimerefund is not perfectly safe for the sender as it can be withheld or invalidated by malleation (cf. BIP65). The possibility of sender losing the refund transaction also creates some danger (it cannot be held in a deterministic wallet).
Timelocked direct payment channels (equivalent to receiver acting as own guarantor) are superior when the sender may want to instantly-pay one specific receiver in the future. InstaConf is for the situation where Kelly wants instant payments but does not have prior knowledge about who will be receiving the payments.
Hashed timelocked payment channel networks, if correctly implemented on a wide scale, would allow trustless zero-confirmation payments when both sender and receiver are hooked in. If the receiver is not part of the network then he needs to indicate which exit node he trusts enough to mediate zero-confirmation payments.
Each funded address has a P2SH hash dependent on its SeKey, FBTime and on
the choice of guarantors (GuKeyA, GuKeyB, ...). In order to recover a
wallet, the user must know all of these data exactly, for every wallet address.
While GuKey is public information, the value of FBTime could be anything
(if the user chose it). We can solve this by deterministically associating each
SeKey with a specific FBTime. The following describes one possible
procedure for doing so:
To begin, let
R = Redeem script with SeKey and FBTime replaced by OP_0
H = RIPEMD160(SHA256(R))
then
-
User should save
Ror remember how to reconstruct it. If user has a favourite guarantor service, this is easy, since R is a deterministic function ofGuKey. -
Create a BIP44 path with
account' = H, with hardened derivation. (note: normally the indices in BIP32 are 32 bits, but we can abuse this without any problems) -
Using BIP44 notation (
purpose' / coin_type' / account' / change / i):Key
*/*/H/0/iis associated withFBTime = 86400*i. In other words, one account fallback per day, starting Jan 1 1970. (Indicesi <~ 5800are not used, due toCHECKLOCKTIMEVERIFYmechanics.) -
Change addresses
*/*/H/1/imay be useful as well, though note that such change outputs need to be confirmed before they become trustworthy inputs in a future InstaConf transaction.
The wallet is used as follows: after choosing the desired fallback time, the
sender must round it up to the nearest UTC-day and then find the appropriate
matching index i. This determines a particular SeKey and FBTime for
that day; combined with R, this gives the full redeem script.
This creates concerns about address re-use, if the user requests more than one address expiring on the same day. In this case the preferred solution is either to find the next unused address by adding days, or alternately, to increment the change-index.
Wallet recovery requires the seed, the value of R, a range of possible
FBTime days, and possible change-index values. Due to the construction
described above, this results in only having to search a reasonable number of
P2SH addresses for activity (hundreds per year of range provided).
The bottleneck in the guarantor system is the core signing system with its master database of already-signed inputs. This core database should not be parallelized, to avoid the danger of allowing simultaneous-request attacks that result in two distinct signatures on the same input.
There may however be multiple submission points, each of which acts as a shield and pre-verification step to stop spam attacks from reaching the core signing system and consuming its resources. Provided the core is only working on real authenticated inputs, the guarantor can handle a heavy load of users.
Although the guarantor service is extremely simple and requires no human involvement, it may be desirable to require a small fee to incentivise service quality or to fund an insurance bond in the event of a hack. Guarantors should include expected fee amounts in their public signed message, which the sender can consult before funding the InstaConf address.
An InstaConf transaction can guarantee unconfirmed contracts that are insensitive to malleability, e.g., hashlocks. As a result, this means that a pair of loaded InstaConf addresses can be used to instantly fund atomic swaps, as follows.
As a reminder, the usual atomic swap works as follows: Alice (A) prepares a
16-byte random secret k with H=HASH160(k) and then funds the following
contract (P2SH redeem script which she shows to Bob):4
IF
<BKey> CHECKSIGVERIFY
SIZE 16 EQUALVERIFY HASH160 <H> EQUALVERIFY
ELSE
<AKey> CHECKSIGVERIFY
<ATime> CHECKLOCKTIMEVERIFY
ENDIF
Bob (B) then funds the same contract on his blockchain with the same H, but
with A/B swapped, and BTime much less than ATime. When Alice redeems Bob's
contract she must reveal k in the process, allowing Bob to redeem Alice's
contract. If the deal is called off then both parties get refunded.
Normally, direct atomic swaps like this require Bob to first wait for Alice's
contract to confirm, then for Alice to wait for Bob's contract to confirm, then
she redeems via revealing k. Since the swap amounts are fixed at the start,
these slow atomic swaps are inconvenient in the presence of volatile exchange
rates. Using InstaConf transactions, there is no need to wait between steps.
4 : size verification with SIZE 16 EQUALVERIFY or somesuch must be
included in contracts so that Bob knows she can't do a k-size exploit on him:
https://gist.github.com/markblundeberg/7a932c98179de2190049f5823907c016