offline transactions via "public" outputs

[antiochp]

@GandalfThePink posted a link to a this -https://github.com/mimblewimble/grin/files/2905763/MWpp.pdf

In the issue tracking BLS Signatures -
#2504 (comment)

But I pulled this out here as there are some things in the paper that we may want to discuss outside of the BLS signatures conversation.

Specifically "public outputs" and "offline transactions".

(Hope you don't mind me starting a discussion here @GandalfThePink).
Maybe we should consider moving this to grin-forum but might be worth some up front discussion here first.

[antiochp]

Paraphrasing poorly (given my limited understanding) -

• propose adding public keys (maybe optionally?) to Grin outputs
• add consensus rule to require a signature to the public key when spending a "public" output
• allow "hanging outputs" to be created - outputs that have been spent but not yet replaced with corresponding spendable outputs (decouple spending of outputs from creation of new outputs)
• track the imbalance (funds destroyed and not yet replaced) in a similar way to how we track kernel excess currently?
• a hanging output is represented as a commitment C = vL + kG (v is the value, k is the private key, kG is the corresponding public key), no corresponding rangeproof and no signature

At this point, if a recipient publishes a a public key (a public address) kG anyone can produce the hanging output by spending an output and creating C = vL + kG by choosing an appropriate value v.

i.e. If Bob publishes a public key, Alice can use it to send an arbitrary number of Grin non-interactively.

Bob could then "claim" the "hanging output" at a later date, allowing the output to be put on-chain as a regular output.

To claim (or complete or finalize?) the hanging output the recipient would build the necessary rangeproof (given v and k and C = vL + kG) and provide the necessary signature to the public key kG to allow the output to be put on-chain.

[ignopeverell]

Did you mean to separate this thinking implementation could be done separately or just for the discussion of hanging transactions? Practically they're not separatable from BLS because it all relies on the ability to aggregate signatures non-interactively.

I do have some questions though regarding the privacy of the hanging output commitments. It seems they could easily leak amounts or even more.

[antiochp]

I'm trying to get my head around if this can be done without needing to aggregate signatures (presumably ending up with multiple kernels).

Didn't want to pollute the BLS Sig issue with an attempt to do something not using BLS sigs.

[antiochp]

I think this is a slightly simpler but along the same lines approach to "public outputs and offline transactions".

This does not require "hanging outputs", both transactions (the "send" and the "claim") are valid and can be accepted on-chain (with modified consensus rules).

We decouple the "send" from the "claim" allowing the sender to select the value v and to construct the necessary rangeproof themselves without interaction with the recipient.

An output currently consists of a commitment C and an associated rangeproof P, where r is a private key and v is the value -

C = rG + vH, P = rangeproof(r, v)

Rangeproof P can be verified given the commitment C.

Introduce the concept of a public key kG to MW.
Given a commitment C and a public key kG we can "sum" them to produce a modified commitment C' -

C' = kG + rG + vH

Introduce the concept of a "public" output, one with a public key associated with it -

kG, C' = kG + rG + vH, rangeproof(r, v)

i.e. A public key, a commitment using both r and k and a rangeproof for r and v.

Note: we can still verify the rangeproof as we can reconstruct C using the public key.

So recipient publishes kG (their public key aka "address").

Sender (unilaterally) creates a transaction creating an output with the following properties -

• sender chooses value v to send
• sender uses a private key of their choosing r
• sender includes the published public key kG and attaches it to the output
• commitment C' = kG + rG + vH
• rangeproof rangeproof(r, v)

Note: The sender uses their own private key r and they have chosen the value v.
The recipient is not involved in this transaction (except for the inclusion of their public key).

This is effectively a tx that spends an output and sends it back to the sender,
but this is a "public" output with a public key associated with it.

Modify the consensus rules such that a public output can only be spent by the owner of the private key k, corresponding to the attached public key kG.

So the output is valid in terms of MW, kernels still sum correctly if we account for both kG and rG correctly. But not spendable via key r, only by key k.

When the recipient comes to "claim" this output and spend it the MW rules can account
for this additional rG because we can identify it as a "public" output.

Modify the spending rules -
This "public" output would not participate in the interactive signature building.
i.e. key r would not be involved.
Instead we would require an additional signature for this individual output based on k.

To create a public output -
send to yourself but tag the output with a public key.

To spend a public output -
provide a signature to the associated public key

• The transaction originally creating the public output is valid and can be accepted on chain
  • modified consensus rules to account for kG
  • this would necessitate a kernel offset to account for rG?
• The transaction spending the public output will be similarly valid
  • modified consensus rules requiring additional signature for output

---

But there is a problem with this though. Same problem with timelocked outputs (and any other attempt we have made at encumbering an output) -

We are attaching additional data (the public key) to an output.
A malicious miner with a large enough re-org could replace this public key with one of their choosing.

This is probably doubly bad because the malicious miner could add a public key to any output and "claim" it.

[GandalfThePink]

There are a few issues to be discussed.

First the problem of deep reorgs. I personally think that this is not a very big problem. The required depth can be chosen such that any such reorg would be disastrous for many other reasons and it is mostly a theoretical problem.
Even then, we are keeping a fundamental part of grin, and that is the verification that no coins were created. Any new user that wants to join can make that proof and trust the network. What a new user cannot trust is that all transactions that lead to the current state did follow all rules, but it is simple to see that the current state has the correct amount of coins. Plus valid states corresponding to a certain kernel offset are not trivial to create. Then when the new user joins, they are able to from that point onwards verify full compliance.

Then there is the question about BLS. Public transactions work without BLS. But the offline solution I describe using hanging outputs requires signature aggregation. Otherwise when the receiver wants to claim, the sender would need to participate and in that case the payment is just an empty promise to pay.

The modification that you describe above avoids that, but I think that it has its own flaws. In particular there is a weakness similar to what I describe in section 4.1. Making a transaction from a third-party commit back to the same person can be done without that persons involvement, potentially adding a public key and I think the way the rangeproofs are set up these can still be created. To avoid this the sender would need to prove possession of the private key in some way.

[GandalfThePink]

Let me summarise your idea in my words to see if I did correctly understand it.

In essence we are looking at a MW transaction that pays from Alice C_A = v L + k_A G to Carol C_C = v L + k_C G.
But instead of directly writing this transaction we take a 'detour' over an intermediary public address. Where Alice spends to herself and commits to a public key P_B = k_B G of Bob. Then Bob can sign to that key to spend the commit to Carol. After Bob has spent the public output this allows him to be cut out of the native MW chain, which then records directly the transaction from Alice to Carol.

In that case in order to validate the chain however we need to have Alice interact with Carol, or store the intermediary data (Bobs public key, the signature and the related commits) forever. This means that each time an offline transaction is used we no longer scale as UTXO size, but with the transaction history.

Another somewhat related question to the implementation of rangeproofs. Are we sure that given a valid rangeproof for C = v L + k G I cannot forge a rangeproof for C = v L + (k+1) G without knowing k. What are the security assumptions. Is this a well understood problem?

[tevador]

In that case in order to validate the chain however we need to have Alice interact with Carol, or store the intermediary data (Bobs public key, the signature and the related commits) forever. This means that each time an offline transaction is used we no longer scale as UTXO size, but with the transaction history.

Correct. Non-interactive transactions require keeping 96 bytes for each spent input. This results in similar blockchain size as Bitcoin, but with vastly better privacy. See https://gist.github.com/tevador/f3a66a2f15a8a3a04a1dde1ea65f9205