LIP: 004 Layer: Consensus (soft fork) Title: One-Sided Transactions in Mimblewimble (Consensus layer) Author: David Burkett <[email protected]> Comments-Summary: No comments yet. Comments-URI: https://github.com/litecoin/lips/wiki/Comments:LIP-0004 Status: Draft Type: Standards Track Created: 2020-02-28 License: PD
This LIP introduces a method for sending transactions on the Mimblewimble Extension Block (MW EB) without the need to build a transaction interactively with the receiving party.
In the traditional approach to Mimblewimble, sending coins from one person to another requires the sender and receiver to interact in order to build a valid transaction. This can be a source of frustration, since it requires users to be online and listening in order to receive coins. This also makes cold storage much more difficult, and opens up additional opportunities for metadata leakage or MITM attacks.
Non-interactive transactions are favorable in most situations, since private keys only need to be accessible when spending funds. They also allow for on-chain payment proofs, which is something possible for most blockchains, but not for chains using traditional Mimblewimble.
This section will detail the transaction model changes and consensus rules for implementing one-sided MW transactions. This specification builds upon the mimblewimble proposal detailed in LIP-0003.
A stealth address is a pair (Ai = ai*G, B = bi*G) where Ai is the scan key and Bi the spend key. There's no practical limit to the number of subaddresses wallets can generate from a single seed.
At the moment, no known method exists for supporting parent/child addresses.
Unique stealth addresses should be generated deterministically from a wallet's seed using the following formula:
- Generate master scan keypair (a, A) using HD keychain path m/1/0/100'
- Generate master spend keypair (b, B) using HD keychain path m/1/0/101'
- Choose the lowest unused address index i
- Calculate one-time spend keypair (bi, Bi) as:
- bi = b + HASH32(A||i||a)
- Bi = bi*G
- Calculate one-time scan keypair (ai, Ai) as:
- ai = a*bi
- Ai = ai*G
A list of outputs: tuples of the form [C, π, v', n', Ks, Ko, Ke, ρ] associated to an output address (Ai, Bi) composed of:
- an ephemeral key Ks = ks*G, chosen by the sender
- an output public key Ko = ko*G whose private key is known only by the receiver
- A key exchange public key Ke = s*Bi = s*bi*G, where s can be calculated by sender and receiver, but bi is known only by the receiver
- a masked value v' which is the value v encrypted by a shared secret t
- a masked nonce n' which is a one-time nonce n encrypted by a shared secret t
- a coin C = v*H + q*G for its value v, the opening q of the coin is shared between the sender and recipient of the coin (see section 3.1)
- a rangeproof π that attests that C is a commitment to a value v < vmax and also commits to a message (C||v'||n'||Ks||Ko||Ke||ρ)
- a signature ρ, valid under verification key Ks and message (C||v'||n'||Ks||Ko||Ke)
A list of inputs: tuples of the form [Ki, C, Ko, σ] referencing a previously unspent output (C), composed of:
- an ephemeral key Ki = ki*G randomly chosen
- a reference to a previously unspent output commitment C and its corresponding output public key Ko
- a schnorr signature σ of the message HASH32(C) under input key Kinput = Ki + HASH32(Ki||Ko)*Ko
A kernel, which is composed of:
- the amount a, indicating the money pegged-in as part of the transaction
- the fee f, indicating the fee paid for the transaction
- the excess E = (∑Cout + f*H) - (∑Cin + x*G) where x is the transaction's transaction offset
- (optional) the stealth excess E' = ∑Ks + (∑Ki - ∑Ko) - x'*G where x' is the transaction's stealth offset
- a signature ψ, valid for message (a||f)
- for transactions with stealth excesses, the signatures must be valid under verification key HASH32(E||E')*E + E'
- for transactions without stealth excesses, the signatures must be valid under verification key E
A transaction must also have 2 associated offsets(scalars), easily summed when aggregating transactions:
- a transaction offset x*G = (∑Cin - ∑Cout) + (f - a)*H - ∑E
- a stealth offset x'*G = ∑Ks + (∑Ki - ∑Ko) - ∑E'
To create an output for value v to a receiver's stealth address pair (Ai, Bi), the sender must:
- Randomly generate the sender's keypair (ks, Ks)
- Derive the nonce n = HASH16(Tnonce||ks)
- Derive the sending key s = HASH32(Tsend||Ai||Bi||v||n)
- Derive the shared secret t = HASH32(Tderive||s*Ai)
- Compute the receiver's one-time public key Ko = Bi * HASH32(Trecv||t)
- Compute the key exchange public key Ke = s*Bi
- Encrypt the value v' = v ^ HASH8(Tvmask||t)
- Encrypt the nonce n' = n ^ HASH16(Tnmask||t)
- Generate the signature ρ for message (v'||n'||Ks||Ko||Ke) using the sender's key ks
- Compute the commitment C = v*H + q*G where q = SWITCH(v, HASH32(Tblind||t))
- Generate the rangeproof π, proving v < vmax, while also committing to the message (C||v'||n'||Ks||Ko||Ke||ρ)
For each input, a sender key is chosen at random ks <-$ Zp.
Using the sender key (ks) and the private key (ko) of the output being spent, create a Schnorr signature σ of the message m = HASH32(Cin) under key:
- Kinput = Ki + HASH32(Ki||Ko)*Ko
As with vanilla MW, the total "excess" is split between a kernel excess (E) and the transaction offset (x).
The offset is chosen at random x <-$ Zp, and then the excess is calculated as:
- E = (∑Cout - ∑Cin) + (f - a)*H - x*G
Though it should be rare (section 8.3.1 for scenario), kernels can also contain a stealth excess, in which case the signature should be valid under verification key HASH32(E||E')*E + E'.
The stealth offset x' is calculated by the sender as x' = ∑ks + (∑ki - ∑ko) - ∑e' where E' = e'*G.
In the vanilla Mimblewimble protocol, the chain state can be aggregated into a single transaction with no inputs, all historical kernels, and all unspent outputs (the UTXO set).
With our proposal however, inputs are kept until they have been buried under a sufficient amount of PoW. In particular, we define a horizon height h for which all inputs & stealth excesses must be kept, and their signatures verified.
To aggregate multiple transactions together, create a new transaction with the combination of all inputs, all outputs, all kernels, all stealth excesses, and calculate:
- transaction offset xagg = ∑x (mod p)
- stealth offset x'agg = ∑x' (mod p)
A transaction (or aggregated transaction) is valid iff:
- (1) all input signatures are valid schnorr signatures under verification key Kinput of the corresponding UTXO for message HASH32(C)
- (2) all range proofs are valid, and commit to the associated output data (C||v'||n'||Ks||Ko||Ke||ρ)
- (3) all output signatures ρ are valid under verification key Ks and message (C||v'||n'||Ks||Ko||Ke)
- (4) all kernel signatures ψ are valid under for message (a||f)
- (a) for transactions with stealth excesses, the signatures are valid under verification key HASH32(E||E')*E + E'
- (b) for transactions without stealth excesses, the signatures are valid under verification key E
- (5) all kernels referenced (λ) by stealth excesses must be present in the transaction
- (6) values are balanced: (∑Cout + (∑f - ∑a)*H) - ∑Cin = ∑E + x*G
- (7) stealth excesses are balanced: (∑Ks + ∑Ki - ∑Ko) = ∑E' + x'*G
- (8) all inputs reference valid UTXOs
While in vanilla MW, outputs could be cut-through as soon as a block spends them, or for unconfirmed transactions, before ever even being included in a block, our proposal explicitly prevents this.
Cut-through (pruning of spent outputs) does not occur until the spend has occured h blocks in the past (i.e. beyond the horizon). Without knowledge of ks, which only the sender (output originator) knows, neither receiver nor adversarial observer is able to cut-through an output while still balancing the stealth excess equation (8).
Wallets must keep a map Bi->i of all used spend pubkeys and the next few unused ones.
To check if an output belongs to a wallet:
- Calculate the view tag t[0] = HASH32(Ttag||a*Ke)
- If the view tag t[0] does not match the view tag of the output, it does not belong to the wallet.
- Calculate the ECDHE shared secret t = HASH32(Tderive||a*Ke)
- Calculate the one-time spend pubkey: Bi = Ko * HASH32(Trecv||t)-1
- Lookup the index i that generates Bi from the wallet's map Bi->i. If not found, the output does not belong to the wallet.
- Decrypt the value v = v' ^ HASH8(Tvmask||t)
- Verify that v*H + SWITCH(v, q)*G ?= Co where q = HASH32(Tblind||t)
- Decrypt the nonce n = n' ^ HASH16(Tnmask||t)
- Calculate the send key s = HASH32(Tsend||Ai||Bi||v||n)
- Verify that Ke ?= s*Bi.
The spend key can be recovered by ko = HASH32(Trecv||t) * bi.
Our design for non-interactive transactions only adds additional validation rules to MW. It does not loosen or remove any previous rules. Therefore, the same mechanisms that protect MW from inflation continue to prevent inflation in our scheme.
That is, the MW balance equation, valid signatures for all historical kernels, and valid rangeproofs for all UTXOs is still all that's required to prevent inflation.
Proving theft resistance under our design is more complicated than before. Rather than everyone choosing their own blinding factors for their outputs, the sender is now responsible for choosing for the receiver's outputs. The sender then encrypts the blinding factor into the output using an ECDH scheme.
Anyone with knowledge of the receiver's subaddress (Ai, Bi), the value v, and the nonce n is able to recover the blinding factor. Anyone without access to the nonce is already prevented from stealing an output by the existing MW validation rules.
The nonce is encrypted in the output such that anyone with knowledge of the receiving wallet's private scan key a may decrypt it. Therefore, in addition to the receiver, the nonce and blinding factor of an output typically would be known by:
- The sender that generated the nonce
- Auditors with access to the receiving wallet's private view key a
- Arbiters that were given the nonce to prove payment (section 11)
The new stealth offset equation is the key to ensuring that only an output's receiver (i.e. knowledge of bi) is able to spend the output.
∑Ks + ∑(Ki - Ko) = ∑E' + x'*G
This states that the sum of the sender keys (Ks) of the outputs, plus the sum of the difference between each input's pubkey and its corresponding output's pubkey (Ki - Ko), must equal the sum of the stealth excesses (E') plus the stealth offset times the base point G (x'*G).
The signature on each input proves knowledge of both Ki and the Ko of the output it spends. The signature on each output being created proves knowledge of Ks. By proving knowledge of all private keys, rogue key attacks are prevented.
While the Ki of each input and the Ks of each output can be set to any pubkey, knowledge of the sum of all secret keys for the Ko's is still required to make the stealth offset equation balance.
Horizon attacks work as follows:
- Alice creates a transaction containing an output for Bob.
- Bob sends Alice the goods she purchased.
- Several weeks (or perhaps even years) pass where Bob has not yet spent his coins.
- Alice forces a large reorg beyond the horizon. She can then send Bob's output back to herself, since she knows the blinding factor, and the stealth balance equation and input signatures aren't validated for transactions in blocks beyond the horizon.
Given a valid transaction, we need to ensure the transaction inputs or outputs can not be modified or reused by a third party in any way without invalidating the whole transaction. That is, only the transaction originator (sender) has knowledge of the secrets necessary to modify or replace any of the inputs or outputs.
If Bob were to receive an output from Alice, and spend it to Charlie in a 1-1 transaction, Alice and Charlie could work together to learn the kernel commitment's blinding factor, allowing them to replace the kernel altogether. This could allow them to modify lock height, steal part of the fee, or in the case of a peg-out kernel, change the pegout address of the coins.
For any transactions where you have a change output (most transactions), or are spending at least 1 of your previous change outputs, the kernel's blinding factor is only known by you, and therefore the kernel is non-malleable. For the rare cases not spending or creating a change output though, a stealth excess can be added to the kernel to prevent its modification.
By including a stealth excess in the kernel, and using it also to sign the kernel, the kernel cannot be modified without invalidating the whole transaction.
Replay attacks are not fully prevented with this LIP, but a number of techniques exist for identifying and preventing replays in the future.
A wallet-level solution would be to require output messages that specify an expected block- or time-frame for confirmation. Outputs falling outside of that range shall be treated with extra caution, and can be immediately respent to prevent the possibility of replay.
We also have the option to soft-fork in additional rules in the future that would enforce confirmation within a specific block or time window, and preventing duplicates in that same window. This would completely eliminate all known replay attacks.
An important property of MW is that transactions can be combined into a single aggregated transaction. This is an important component of MW's privacy, so we carefully preserve that property.
- To aggregate n transactions (tx1...n) into a single aggregated transaction (txagg):
- include and sort all inputs, outputs, and kernels in the new aggregated transaction.
- set transaction offset (x) as the sum of the individual transactions' kernel offsets: xagg = ∑x1...n
- set stealth offset (x') as the sum of the individual transactions' stealth offsets: xagg' = ∑x'1...n
There are 3 ways the Mimblewimble protocol improves privacy over transparent chains (like BTC and LTC):
- Hidden Amounts
- This property is clearly still preserved, since values remain hidden by Pedersen commitments.
- No Address Reuse
- By supporting stealth addresses, whose sole purpose is to prevent address reuse, we are also able to continue providing this property.
- Non-interactive CoinJoins
- Transactions remain aggregable (section 9). The stealth offset helps ensure that transactions can not be broken back apart once they've been aggregated.
A payment proof shall consist of the output, a merkle proof proving the output is in the TXO PMMR, the output's value v, the output's nonce n, and a signature proving knowledge of ks.
To verify, the arbiter must:
- Verify the merkle proof is valid for the output and the blockchain's TXO PMMR
- Calculate the send key:
- s = HASH32(Tsend||Ai||Bi||v||n)
- Calculate the shared secret:
- t = HASH32(Tderive||s*Ai)
- Verify the output's commitment:
- C ?= v*H + SWITCH(v, HASH32(Tblind||t))
- Verify the output's public key:
- Ko ?= Bi + HASH32(Trecv||t)*G
- Verify the output's key exchange public key:
- Ke ?= s*Bi
- Verify the encrypted value:
- v' ?= v ^ HASH8(Tvmask||t)
- Verify the encrypted nonce:
- n' ?= n ^ HASH8(Tnmask||t)
This will be activated alongside LIP-0003.
Special thanks to Hansie Odendaal, Phyro, John Tromp, and Kurt Coolman for their valuable feedback on earlier iterations of this design. Thanks also to Michele Orrù, Georg Fuchsbauer, and the team at MWC for collaborating while they worked on their own NITX scheme.
https://gist.github.com/DavidBurkett/32e33835b03f9101666690b7d6185203
This document is placed in the public domain.