mimblewimble-cheque.md

Mimblewimble-cheque: Scalable blockchain with 2-step transactions

We present Mimblewimble-cheque (MWC), a modification of the Mimblewimble (MW) transaction protocol that preserves its main properties, does not require additional security assumptions and allows transactions to be constructed without a communication round trip. Payments in MWC resemble cheques, i.e. Alice can make a payment to Bob by "writing a cheque", which Bob can "cash" by submitting it to the blockchain.

• 1. Introduction
  • 1.1 Previous work
  • 1.2 Contribution
• 2. Cryptographic primitives
  • 2.1 Notation
  • 2.2 Hash functions
    • 2.2.1 Tagging
  • 2.3 Pedersen commitments
  • 2.4 Range proofs
  • 2.5 Diffie-Hellman key exchange
  • 2.6 Schnorr signatures
    • 2.6.1 Standard Schnorr
    • 2.6.2 Sequentially half-aggregated Schnorr (SASchnorr)
• 3. Protocol description
  • 3.1 Addresses
  • 3.2 Transaction input and output format
  • 3.3 Kernel format
  • 3.4 Transaction construction
    • 3.4.1 Send
    • 3.4.2 Receive
  • 3.5 Validation rules
    • 3.5.1 Kernel signature verification
    • 3.5.2 Balance equation
    • 3.5.3 Kernel uniqueness
  • 3.6 Payment proof
  • 3.7 Multiple recipients
    • 3.7.1 Batch transaction
    • 3.7.2 Cascade transaction
• 4. Security analysis
  • 4.1 Breaking supply security
  • 4.2 Breaking ownership security
    • 4.2.1 Blinding factor reuse
    • 4.2.2 Malicious sending keys
  • 4.3 Linking a kernel to an address
  • 4.4 Forging payment proofs
• References
  • Acknowledgements
  • Changelog

1. Introduction

The Mimblewimble protocol (MW), proposed in 2016 by an anonymous researcher [1], makes blockchains much more efficient, while providing the same security properties as Bitcoin.

However, the efficiency and elegance of MW comes at a cost. Constructing a MW transaction typically requires 3 rounds of communication between the sender (Alice) and the recipient (Bob):

1. Send - Alice builds her half of the transaction and includes her half of the kernel public key Ka and the nonce Ra.
2. Receive - Bob contributes his half of the transaction, selects his half of the kernel public key Kb and the nonce Rb, calculates K = Ka + Kb, R = Ra + Rb and attaches his half-signature sb.
3. Finalize - Alice calculates her half of the signature sa and submits the whole transaction to the network with the complete signature s = sa + sb.

The third step is needed because in the first step, Alice doesn't know the full kernel public key K and the nonce R, which are required for the signature challenge e = Hq(R, K, m), where m is the message being signed.

The 3-step transaction construction is considered to be a major usability hurdle because it either forces both Alice and Bob to be online at the same time or possibly face long delays caused by either party to complete the transaction.

1.1 Previous work

Previous work mostly focused on 1-step (non-interactive) transactions, but in 2020, research began to consider 2-step constructions that would eliminate the finalization step [2]. However, most of the initial proposals turned out to be insecure. Notably, removing the kernel public key K from the signature challenge leads to an attack on the MW balance equation, resulting in undetectable inflation [3].

The only 2-step transaction protocol that doesn't seem to be broken was published by Kurt on the Grin forum in September 2020 [4]. It doesn't aggregate the kernel public key but instead includes both Ka and Kb in the transaction kernel using a modified verification equation. While this protocol only requires additional 32 bytes in the kernel, it has the following drawbacks:

1. It uses a non-standard signature algorithm that lacks a formal security proof.
2. It requires stronger cryptographic assumptions, namely the hash function Hq() used in the signature algorithm must be collision resistant because hash collisions cause a catastrophic failure of the protocol (undetectable inflation). The standard Schnorr signature algorithm only requires a preimage-resistant hash function, which is a much weaker requirement.
3. The protocol does not scale beyond 1 recipient due to the Wagner attack.

1.2 Contribution

This work presents a new 2-step protocol for MW that has the following properties:

1. It uses a provably secure signature scheme.
2. It does not require any new security assumptions.
3. It supports payment proofs.
4. It supports an arbitrary number of recipients.

The costs of the protocol, compared to MW, are:

1. The kernel size is increased by 64 bytes per recipient.
2. The kernel signature verification requires an additional double-base scalar multiplication per recipient.

2. Cryptographic primitives

2.1 Notation

We assume that 𝔾 is a cyclic group of prime order q ≈ 2256, corresponding to the 128-bit security level. Uppercase letters usually refer to group elements (public keys, commitments) and lowercase letters usually refer to numbers in 𝒵q (scalars, private keys). We will use the additive notation for group operations.

Let G be the generator of 𝔾 and H be another element of 𝔾 with unknown discrete logarithm relationship to G.

2.2 Hash functions

We assume the existence of the following hash functions:

• Hb is a hash function {0,1}* -> {0,1}b. Typically, b = 256.
• Hq is a hash function {0,1}* -> Zq

These hash functions are modeled as random oracles with uniform outputs over their domains.

2.2.1 Tagging

Tags are used to prevent the outputs of hash functions from being misused in a different context than intended. Tags will be denoted by capital letter T with a lower index specifying the name of the tag. Tags are passed to hash functions alongside other input fields. For example, Tsend is a tag specifies that the input is used in the context of sending funds.

2.3 Pedersen commitments

Pedersen commitment C is an element of 𝔾 constructed as:

C = r * G + v * H

where r is the blinding factor and v is the value of the commitment. Pedersen commitments are homomorphic, which means that adding two commitments C1 and C2 to values v1 and v2 produces a commitment to (v1 + v2) mod q

2.4 Range proofs

When adding Pedersen commitments, their values are added modulo q. To prevent overflow, we need to restrict the possible values of v to a range much smaller than q. Range proofs are a special kind of zero-knowledge proofs that prove a commitment C is of the form r*G + v*H where 0 <= v < 2n and n is the required precision in bits, without revealing the values r or v. For monetary operations, 64-bit precision is more than enough to represent the possible range of values.

2.5 Diffie-Hellman key exchange

If Alice owns a keypair (xa, Pa) and Bob owns a key pair (xb, Pb), then xa* Pb = xb* Pa is a secret that only Alice and Bob can compute after sharing their public keys Pa and Pb. This is called the Diffie-Hellman (DH) key exchange protocol. [5]

2.6 Schnorr signatures

Schnorr signatures are a family of digital signatures based on the discrete logarithm problem (DLP).

2.6.1 Standard Schnorr

To sign a message m using the private key x (corresponding to the public key P), the signer selects a random nonce value r and calculates R = r*G. The signature then consists of the pair (R,s), where s = r + e*x with e = Hq(R, P, m). The signature size is 64 bytes at the 128-bit security level.

A signature (R,s) of the message m can be verified with the public key P by checking s*G ?= R + Hq(R, P, m)*P.

This signature scheme has been proven secure in the random oracle model (ROM), assuming the hash function Hq() is preimage-resistant [6].

2.6.2 Sequentially half-aggregated Schnorr (SASchnorr)

A variant of the Schnorr signature algorithm with N signers allows the signatures to be sequentially half-aggregated, resulting in a total size of 32*N+32 bytes at the 128-bit security level. Each signer can use a different signing key Ki and sign a different message mi. The only requirement is that the signers aggregate the partial signatures sequentially, i.e. the first signer generates a signature σ1 and sends it to the second signer, who transforms it into the aggregated signature σ2 and so on until the N-th signer produces the final aggregated signature σN.

This scheme is described as SASchnorr in ref. [7], chapter 5. Notably, the security proof tightly reduces to the security of the standard Schnorr signature without the need for additional assumptions.

3. Protocol description

3.1 Addresses

In order to support payment proofs, MWC introduces addresses. An address consists of two public keys P = x*G and Q = y*G where x and y are the associated private keys. MWC addresses are reusable, i.e. they can be used to received multiple payments that can't be linked together by external observers.

3.2 Transaction input and output format

The input and output format is the same as in MW, i.e. each transaction output consists of a Perdersen commitment and a range proof and each input is the commitment of a previous output.

3.3 Kernel format

The kernel format in MWC is changed:

1. The kernel contains a separate public key Ki for every participant.
2. The kernel signature is a SASchnorr multisignature.

In the typical case when Alice is sending a payment to a single recipient (Bob), the kernel format is as follows:

field	description	size
Ka	Alice's one-time kernel key	32
Kb	Bob's one-time kernel key	32
R	Aggregated nonce	32
sa	Alice's signature scalar	32
sb	Bob's signature scalar	32
	total	160

3.4 Transaction construction

Let's suppose that Alice and Bob have agreed in advance on an amount vb to be sent and Bob has provided his public address (Pb, Qb).

3.4.1 Send

1. Alice must first select an existing output Ci = ci*G + vi*H to be spent such that vi >= vb.
2. Alice selects a 256-bit nonce n uniformly at random.
3. Alice calculates a unique sending key ks = Hq(Tsend, Pb, Qb, vb, n, ts, dc), where ts is the current timestamp and dc is the payment description.
4. Alice constructs Bob's one-time kernel key Kb = ks*Pb + vb*Qb.
5. Alice selects her one-time kernel key Ka = ka*G and a nonce Ra = ra*G.
6. Alice calculates ea = Hq(Tsas, Ra, Ka, Kb, s0, 0) where s0 is the zero scalar.
7. Alice calculates sa = ra + ea*ka
8. Alice constructs her change output commitment Ca = ca*G + va*H where va = vi - vb and a range proof RP(Ca).
9. Alice calculates the offset oa = ci - (ca + ka)
10. Alice selects a private key u, calculates U = u*G and derives a symmetric encryption key ke = H256(Tenc, u*Pb).
11. Alice sends to Bob: U, {vb, n, ts, dc, Ka, Ra, sa, Ci, Ca, RP(Ca), oa}, where everything inside the curly braces is encrypted using the symmetric key ke.

3.4.2 Receive

1. Bob derives the encryption key ke = H256(Tenc, xb*U).
2. Bob decrypts vb, n, ts, dc, Ka, Ra, sa, Ci, Ca, RP(Ca), oa.
3. Bob verifies that the values of vb, ts and dc are acceptable.
4. Bob verifies that Ci is a valid UTXO.
5. Bob verifies that Ci - Ca ?= Ka + oa*G + vb*H and RP(Ca) is valid.
6. Bob calculates the unique sending key ks = Hq(Tsend, Pb, Qb, vb, n, ts, dc).
7. Bob derives his one-time kernel key Kb = ks*Pb + vb*Qb.
8. Bob calculates ea = Hq(Tsas, Ra, Ka, Kb, s0, 0).
9. Bob verifies that sa*G ?= Ra + ea*Ka.
10. Bob selects a nonce Rb = rb*G.
11. Bob calculates R = Ra + Rb.
12. Bob calculates eb = H(Tsas, R, Kb, "", sa, 1).
13. Bob calculates sb = rb + eb*(ks*xb + vb*yb)
14. Bob constructs his output commitment Cb = cb*G + vb*H and a range proof RP(Cb).
15. Bob adjusts the offset o = oa - (cb + ks*xb + vb*yb)
16. Bob can submit the final transaction with the input Ci, outputs Ca, RP(Ca) and Cb, RP(Cb), kernel (Ka, Kb, R, sa, sb) and offset o.

(Note: Bob can optionally include an input of his own, making the transaction a payjoin. This would only require modifying the commitment Cb and the final offset o.).

3.5 Validation rules

MWC requires three consensus changes compared to MW.

3.5.1 Kernel signature verification

The kernel signature is verified as a SASchnorr multisignature (§ 2.6.2). For a single recipient kernel (Ka, Kb, R, sa, sb), the process is as follows:

1. Calculate eb = H(Tsas, R, Kb, "", sa, 1)
2. Calculate Rb = sb*G - eb*Kb
3. Calculate Ra = R - Rb
4. Calculate ea = H(Tsas, Ra, Ka, Kb, s0, 0) where s0 is the zero scalar.
5. Check that sa*G ?= Ra + ea*Ka

If the last check succeeds, it proves the validity of both Alice's and Bob's signatures, proving that neither Ka nor Kb contains any value. This algorithm corresponds to the SASchnorr verification algorithm with N=2 signers where Alice signs Bob's public key Kb and Bob signs an empty string.

3.5.2 Balance equation

When verifying the transaction balance, all the kernel public keys are summed. In the case when Alice is sending a payment to Bob, the balance equation is:

Ci - Ca - Cb ?= Ka + Kb + o*G

where Ci is the input commitment, Ca is Alice's change output, Cb is Bob's output and o is the transaction offset (fees are omitted for clarity).

3.5.3 Kernel uniqueness

The first public key in every transaction kernel must be unique. This prevents replay attacks, which could be used to steal funds under some circumstances.

3.6 Payment proof

To prove that she sent money to Bob, Alice can provide an arbiter with:

• Bob's public address (Pb, Qb).
• The transaction amount vb.
• The one-time nonce n, the timestamp ts and the description dc.

The arbiter can verify Alice's claim by:

1. Calculating the sending key ks = Hq(Tsend, Pb, Qb, vb, n, ts, dc).
2. Constructing the corresponding one-time kernel key for Bob: Kb = ks*Pb + vb*Qb.
3. Checking that there is a valid kernel that contains Kb.

3.7 Multiple recipients

MWC can support multi-party transactions. For example, with Alice, Bob and Carol, the communication flow would be:

Alice -> Bob -> Carol

with Carol submitting the complete transaction to the blockchain. In this case, the transaction kernel would include three keys Ka, Kb and Kc and the aggregated signature (R, sa, sb, sc). While this leaks the number of parties that participate in the transaction, the inputs and outputs are mixed and the resulting kernel is smaller than the sum of kernels of individual transactions would be.

The kernel signature is again verified in reverse order:

1. Calculate ec = H(Tsas, R, Kc, mc, sb, 2)
2. Calculate Rc = sc*G - ec*Kc
3. Calculate R' = R - Rc
4. Calculate eb = H(Tsas, R', Kb, mb, sa, 1)
5. Calculate Rb = sb*G - eb*Kb
6. Calculate Ra = R' - Rb
7. Calculate ea = H(Tsas, Ra, Ka, ma, s0, 0) where s0 is the zero scalar.
8. Check that sa*G ?= Ra + ea*Ka

Here ma, mb and mc are the messages signed by Alice, Bob and Carol, respectively. The contents of these messages depend on the type of transaction. There are two main types: batch transactions and cascade transactions.

3.7.1 Batch transaction

In a batch transaction, Alice is paying both Bob and Carol. In this case, it's Alice who constructs the public keys Kb and Kc and she signs ma = (Kb, Kc). Both mb and mc are empty strings. Alice sends to Bob a partial transaction with an excess amount of vb+vc. Bob must add his output of value vb and forward the partial transaction with an excess value of vc to Carol in order to secure her signature.

3.7.2 Cascade transaction

In a cascade transaction, Alice is paying Bob and Bob is paying Carol. Alice only constructs the public key Kb exactly as described in § 3.4.1 and signs ma = Kb. In fact, Alice doesn't need to know that Carol will be involved. Bob then adjusts his output amount, constructs Carol's key Kc and signs mb = Kc. Carol will sign mc = "" and submit the final transaction.

4. Security analysis

4.1 Breaking supply security

There are two avenues for breaking the supply security:

1. Constructing a valid range proof with a negative amount.
2. Forging a signature with a kernel public key that contains an H component.

The only relevant difference between MW and MWC is the kernel signature algorithm. Since the security proof in ref. [7] proves that SASchnorr is as secure as standard Schnorr, there is no difference between the supply security of MW and MWC.

4.2 Breaking ownership security

Compared to MW, there are two caveats in MWC that must be taken into account.

4.2.1 Blinding factor reuse

If Mallory makes two payments to Bob's address (Pb, Qb), she can take advantage of the balance relation and construct 2 equations with 3 unknowns: Bob's private key xb and the two blinding factors of Bob's outputs cb1 and cb2. While Mallory is unable to solve these equations, Bob must be careful not to reveal or reuse any of his blinding factors, otherwise his private key might be leaked. Blinding factors must be treated like nonces.

4.2.2 Malicious sending keys

Mallory can take advantage of existing algorithms to solve the generalized birthday problem [8] and produce two sets of malicious sending keys A = {ksa,1, ksa,2, ...} and B = {ksb,1, ksb,2, ...} such that ∑ ksa,i = ∑ ksb,i. She can then make payments to Bob with each of these keys, making sure that the sum of the payment amounts for keys in set A is the same as the sum of the payment amounts in set B. Using the balance equation, Mallory will be able to calculate the difference of the blinding factors between Bob's outputs in set A and set B. However, this won't allow Mallory to steal any funds from Bob because both sets of payments contain equal amounts and past transactions can't be replayed due to rule §3.5.3.

4.3 Linking a kernel to an address

Even if Mallory knew Bob's address (Pb, Qb), the amount vb that Alice sent, the timestamp ts and the payment description dc, she would need to guess the secret nonce n in order to learn Bob's kernel key and find the payment in the blockchain. This is intractable.

4.4 Forging payment proofs

Mallory might try to forge a payment proof with a value of vm to Bob's address (Pb, Qb). To do this, she would need to search the 256-bit nonce space to find a nonce n such that Km = sn*Pb + vm*Qb is an existing kernel key. This is intractable.

References

[1] Mimblewimble: https://github.com/mimblewimble/docs/wiki/MimbleWimble-Origin

[2] Eliminating finalize step: https://forum.grin.mw/t/eliminating-finalize-step/7621

[3] Undetectable inflation vulnerability: https://forum.grin.mw/t/eliminating-finalize-step/7621/91

[4] Eliminating finalize step ReLoAdEd: https://forum.grin.mw/t/eliminating-finalize-step-reloaded/7817

[5] Diffie-Hellman: https://www.cs.utexas.edu/~shmat/courses/cs380s/dh.pdf

[6] Schnorr signatures: https://eprint.iacr.org/2012/029.pdf

[7] Half-Aggregation of Schnorr Signatures: https://eprint.iacr.org/2022/222.pdf.

[8] Generalized Birthday Problem: http://people.eecs.berkeley.edu/~daw/papers/genbday.html

Acknowledgements

Special thanks to tromp for discovering security issues in the previous versions of the protocol.

Changelog

Revision 2: Fixed typos.

Revision 3: Wagner's attack mitigations; removed uniqueness check for the sending key.

Revision 4: Replay attack mitigations.

Revision 5: Acknowledgements.

Note: It might be possible to prevent the Wagner's attack by using the accumulated nonce R in the balance equation instead of the kernel keys. The SASchnorr signature also proves that the signers collectively know the discrete logarithm of R, so this should not affect supply security, but it needs to be investigated further.