TransactionProtocol

Transaction Protocol

status: draft

Maintainer(s): Cayle Sharrock

Licence

The 3-Clause BSD Licence.

Copyright 2019 The Tari Development Community

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of this document must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS DOCUMENT IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS", AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Language

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY" and "OPTIONAL" in this document are to be interpreted as described in BCP 14 (covering RFC2119 and RFC8174) when, and only when, they appear in all capitals, as shown here.

Disclaimer

This document and its content are intended for information purposes only and may be subject to change or update without notice.

This document may include preliminary concepts that may or may not be in the process of being developed by the Tari community. The release of this document is intended solely for review and discussion by the community of the technological merits of the potential system outlined herein.

Goals

This Request for Comment (RFC) describes the transaction protocol for peer-to-peer Tari payments using the Mimblewimble protocol. It also considers some attacks that may be launched against the protocol and offers some discussion around those attacks and potential alternatives to the protocol.

The goal is to describe a transaction protocol that:

  • permits multiple recipients;
  • preserves privacy regarding how many parties are involved in the transaction; and
  • is secure against all reasonable attacks.

Related Requests for Comment

Description

The Tari base layer is built using Mimblewimble, which requires that all parties involved in a Tari transfer must interact to construct a valid Mimblewimble transaction.

A valid transaction involves:

  • a set of one or more inputs being spent by the Sender;
  • a set of zero or more outputs being sent to the Sender;
  • a set of recipients, each of whom MUST construct exactly one output; and
  • a set of partial Schnorr signatures which, when aggregated, validates the transaction construction and indicates every party's satisfaction with the terms.

The Issue with Multiple Recipients

Each party involved in a Tari transaction must produce a partial signature, signing the same challenge. This challenge is defined as

$$ e = H(\Sigma R_i \Vert \Sigma P_i \Vert m) $$

where \(R_i\) are public nonces generated by each party for this signature; \(P_i\) are the public Spending Keys; and m is the additional metadata for the transaction. \(\Sigma P_i\) is the value of the (pre-offset) excess that is stored in the transaction kernel.

Notice that every signing party needs to know the sum of all the nonces and public spending keys. This suggests that every party knows how many parties are involved in the transaction, which is not an ideal privacy scenario. It would be preferable if a secure scheme could be found where each recipient interacts only with the sender and does not need to calculate these sums themselves.

Unfortunately, as discussed below, it seems that using any known scheme, it's not possible to satisfy this privacy goal while achieving the desired security level.

The Issue with Multiple Senders

To increase privacy, the public excess values are offset by a constant random value. The choice of this value, as well as fee selection, can only be set once per transaction. The privilege of selecting these values is generally bestowed on the sender, since the sender pays the fee. Allowing multiple sending parties (or equivalently, allowing recipients to provide inputs) would require a negotiation round to set the fee and offset before the transaction could be constructed. This is a complication we don't want to deal with, and so all schemes presented here allow exactly one sender.

Two-party Transactions

Two-party transactions are fairly straightforward and are described in detail by Tari Labs University (TLU). (Refer to Mimblewimble Transaction.)

It is proposed that Tari implement this single-round two-party transaction scheme as a special case to support both online two-party transactions as well as "offline" transactions such as via email, text message and carrier pigeon.

Multiple-recipient Transaction Scheme

sequenceDiagram participant Sender participant Receivers # Sender Initializes the transaction activate Sender Sender-->>Sender: initialize deactivate Sender # Sender transmits initial data to all receivers activate Sender Sender-->>+Receivers: [tx_id, amt_i,H(Rs||Xs),m] note left of Sender: CollectingCommitments note right of Receivers: SendingCommitment Receivers-->>-Sender: [tx_id, H(Ri||Pi)] deactivate Sender # Receiving Outputs activate Sender Sender-->>+Receivers: [tx_id, [Hashed commitments]] note left of Sender: CollectingPubKeys note right of Receivers: SendingOutput Receivers-->>-Sender: [tx_id, Pi, Ri, C_i, RP_i] deactivate Sender alt inflation_error()? Sender--XReceivers: [tx-id, failed] end # Signature collection activate Sender Sender-->>+Receivers: [tx_id, [Rs, Ri] [Xs, Pi]] note left of Sender: CollectingSignatures note right of Receivers: Signing Receivers-->>Receivers: validate nonces, pubkeys and pubkey sum alt invalid Receivers--XSender: failed end Receivers-->>Receivers: Sign Receivers-->>-Sender: [tx_id, s_i] deactivate Sender # Sender sends final notification of result note left of Sender: Finalizing alt is_valid() Sender-->>Receivers: [tx_id, OK] else invalid Sender--XReceivers: [tx_id, Failed] end

** Legend **

SymbolMeaning
tx_idTransaction identifier
amt_iAmount sent to i-th recipient
Rs, RiPublic nonce
Xs, PiPublic excess/key
mMessage metadata
C_iCommitment
RP_iRange proof
[..]Vector of data

Transaction ID

The scheme above makes use of a tx_id field in every peer-to-peer message. Since all messages are stateless and asynchronous, peers need some way of figuring out which message refers to which transaction. The transaction ID fulfils this role.

The ID does not appear on the blockchain in any manner; is purely used to disambiguate Tari transaction messages and can be discarded after the transaction is broadcast to the network.

The tx_id is unique for every receiver so that any observers of the communication will not be able to group receivers together (however, the communication should be over secure channels in general).

The format of the transaction ID is a four-byte, little-endian integer (u64) and is calculated as

H(Rs||i)[0..4]

where i is the i-th recipient in the transaction. The sender can use the tx_id as a hash map key to identify and differentiate recipients.

Replay Attacks

If any party can be convinced to sign a different message with the same nonce, its private keys will be lost. One way of achieving this would be if a virtual machine could be "snapshotted" or otherwise cloned at any point between sharing the public nonce and signing the message. Both copies of the victim's machine will now continue, unaware that there's a copy participating in a signature round. What then happens is:

$$ \begin{align} &\text{Clone A} & &\text{Clone B} \\ e_1 &= H(r_1 \Vert r_s \Vert \dots) & e_2 &= H(r_1 \Vert r_s^* \Vert \dots) \\ s_1 &= r_1 + e_1 \cdot k_1 & s_2 &= r_1 + e_2 \cdot k_1 \\ \end{align} $$

The attacker receives both signatures and trivially calculates the secret key:

$$ \begin{align} \Delta s &= s_1 - s_2 \\ &= k_1(e_1 - e_2) = k_1\Delta e \\ \Rightarrow k_1 &= \frac{\Delta s}{\Delta e} \end{align} $$

We've demonstrated this with the attacker changing their nonce, but literally any alteration to the challenge will provide a new challenge \(e_2\), enabling the attack.

What can we do about this? In fact, it's not possible to eliminate this attack at all! The reason sits with the proof that the Schnorr scheme works as a zero-knowledge protocol; the demonstration of this proof is precisely the attack we're trying to avoid [GOL19]. If we could eliminate this attack, we'd need to come up with a completely different way of proving the zero-knowledge property.

So we can't stop it, but we can make it as tricky as possible for the attacker to trick the receiver into replaying the signature. MuSig does this by requiring parties to share the hash of their nonces beforehand. At its extreme: in the two-party, single-round scheme, for example, the attacker would need to be able to control the victim's machine code execution (like running a debugger), at which point one might think the attacker could read the private key directly from memory anyway.

Rogue Key Attacks

Rogue Key attacks are another type of attack that can occur in multi-signature schemes.

In this case, the attacker has the freedom to choose a key or nonce after the victim has already disclosed theirs. This may allow the attacker to forge a valid signature on behalf of the victim. A recent paper, [DRI19], suggests that any Schnorr-based, two-round multi-signature scheme is vulnerable to a rogue key attack.

How this might apply in an insecure two-round Tari multi-signature scheme is as follows: A receiver sends their public nonce; output commitment and range proof; and public spending key to the sender, but then decides to cancel the transaction by refusing to provide a signature and sending an "Abort" message to the sender instead. The sender could, if they wanted, forge the 2-of-2 signature using this rogue key attack and broadcast the transaction anyway.

Note: This attack is not applicable in the one-round, two-party scheme, since the receiver returns their information in an all-or-nothing manner. However, the receiver could attempt to forge a signature, since they have the Sender's public nonce, but there's nothing they can really do with this signature; they certainly cannot broadcast a transaction with it because they don't have any of the transaction data at this stage.

We avoid rogue-key attacks in the Tari multi-recipient scheme by employing three rounds. In the first round, parties share a hash of their public nonces, which each party can later use to verify that no nonces were changed after the actual public nonces were shared.