Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Buy your coffee with InstaConf: nearly trustless zero-confirmation guarantees

Buy your coffee with InstaConf: nearly trustless zero-confirmation guarantees

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.

Procedure

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.

Phase 1: The setup

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).

Phase 2: The deal

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.

Phase 3: The signing

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.

Phase 4: Verification and risk acceptance

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 FBTime is 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.

Cancel / refund of InstaConf address

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.

Technical details

Multisig guarantors

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.

Tx safety rules

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 ALL or ALL|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 FBTime values 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.

Discovery of guarantor information

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).

Sender-guarantor communication

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 is R."

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 SeKey from R).
  • Input does not require guarantor signature (R doesn't contain GuKey).
  • Cannot find a transaction matching input txid.2
  • R does 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.

Evaluation

Attack resistance

Risk model: malicious guarantor key owner

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.

Risk model: congestion

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.

Attacks on sender

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.

Attacks on guarantor

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).

Anonymity

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.

Comparison to GreenAddress

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 nLockTime value 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 nLockTime refund 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).

Comparison to payment channels

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.

Extensions / enhancements

InstaConf deterministic wallet

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

  1. User should save R or remember how to reconstruct it. If user has a favourite guarantor service, this is easy, since R is a deterministic function of GuKey.

  2. 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)

  3. Using BIP44 notation (purpose' / coin_type' / account' / change / i):

    Key */*/H/0/i is associated with FBTime = 86400*i. In other words, one account fallback per day, starting Jan 1 1970. (Indices i <~ 5800 are not used, due to CHECKLOCKTIMEVERIFY mechanics.)

  4. Change addresses */*/H/1/i may 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).

Guarantor DDOS/spam protection; scaling

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.

Guarantor fees

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.

Instant atomic swaps

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


Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.