An Idea for 1-sided Transactions

Development and Technical Discussion
1

Yesterday some conversation happened on keybase regarding 1-sided transactions, by aggregating a commitment with a recipient’s commitment to 0. I have a proposal that appears (to me) to accomplish this. I know David is working on something similar, so hopefully we are on the right track.

Either way, here are my thoughts so far. Maybe one of the crypto experts out there can shoot a hole in the concept :sweat_smile:

-------- Recieve Address
A recieve address will consist of a public key on X, where X = x*G, and a signature from this key, s_X: address = (X, s_X)
The public key will be treated as a commitment to 0: X = (x*G + 0*H)
The signature will be used later to verify that Bob knows the private key, x, and thus verify the commitment commits to value 0.


-------- 1-Sided Transaction
1-sided transaction looks like a classic MW transaction, except that the output is aggregated with the recipient's address key. For example:

Bob publishes his receive address: (B, s_B) = (b*G, s_B)

Alice wants to send Grin to Bob, by spending a UTXO she controls: In = (ri*G + vi*H)
A-1) First, she computes a new temporary output commitment:
  - Out = (ro*G + vo*H)
A-2) Second, she aggregates this with Bob's commitment to 0:
  - Out' = Out + B = (ro*G + B + vo*H + 0*H) = ((ro + b)*G + vo*H)

Notice, this resultant commitment (Out') is blinded by Bob's private key, b, which ony Bob knows. Therefore, if Bob can learn ro, Bob can now own this commitment. To accomplish this, Alice must select ro in a way that Bob can recover.

Also, note, step A-1 is identical to a classical MW transaction. Step A-2 is an optional modification to a classic UTXO, to give ownership to Bob. I think of this as "Bob commits to vo 'by proxy' through Alice".

There are a few possibilities for Alice to select r0, but I suggest this:
B-1) Alice generate ephemeral private key e, and corresponding public key E, where E = e*G.
B-2) Alice computes ECDH shared secret with Bob's key: ss = ecdh(e, B)
B-3) Alice computes ro as hash of this secret (any strong hash works): ro = hash(ss)
B-4) Alice then includes the ephemeral public key, E, in the transaction, so that Bob can also compute ro.

Lastly, Bob must learn the value, vo, to be able to control the commitment. Alice can also share this information with Bob, encrypted using a key derived similarly to ro, and also shared with the transaction.

Note, this requires Alice to include a lot of data in the transaction kernel, for Bob to recover the output:
- 33 bytes -- E as compressed pubkey
- 16 bytes -- v0 encrypted (AES256)
This exceeds the amount of data that can be stored in a bulletproof, so I am still working on a to reduce the amount of information Alice must share with Bob.


-------- Transaction Validation
To validate a transaction, a node must perform the following checks:
C-1) Verify Out - In = 0
  - This check is identical to classic MW. Alice must provide a signature from private key (ro - ri).
C-2) Verify all rangeproofs to prevent negative outputs
  - This check is also identical to current transaction validation.
C-3) Verify Bob's address truly commits to zero, given Bob's address (B, s_B)
  - This holds if s_B is a valid signature from B.

Note, this requires Alice to include the intermediate output (Out) and Bob's address (B, s_B) in the transaction. To prevent a miner from mutating the transaction and stealing funds for himself, Alice should sign the entire transaction (including the expected resultant Out') with the signature she provides in step C-1.

So the transaction data that must be published to the network is:
- Input commitment(s) to be spent (In_0, In_1, ..., In_N)
- Output commitment(s) to be created (Out_0, Out_1, ..., Out_N)
- Recieve addresses for any 1-sided transaction outputs (addr_0, addr_1, ..., addr_n). Note, these are optional. Any output without a specified receive address can be validated like a classic MW transaction.
- Excess signatures for step C-1. Note: these may possibly be aggregated.
- Rangeproofs for step C-2.


-------- View Only Wallets
I will only touch on this quickly, but if the encryption key for the value information is derived appropriately, it is possible a view only wallet could exist, which can detect outputs and view the value field, but not be able to spend the committment. I plan to research this further, but this is not the primary objective.


-------- Confidential Addresses
I will only touch on this quickly, but it is possible to perform the above transaction on a derived address for Bob, instead of his publicly published address. IE, Alice selects a nonce, n, and send's the transaction to Bob's derived address: (B', s_B'), where B' = B + n*G, and s_B' = s_B + n. This is possible since both fields of an address are homomorphic.

Note, this also depends on Bob being able to derive the appropriate address, and thus depends on the shared secret computation mentioned in steps B-2 through B-4.


-------- Concluding Thoughts
Pros:
 - Enables 1-sided transactions (duh)
 - Bacwards compatible with current MW transactions (ie cut-through still possible)
 - Requires no new security assumptions, only ECDLP assumption which already exists
 - Transaction authorization and lifetime/finality are the same as classic MW transactions (ie, no re-org can claim this output)

Cons:
 - Still a few unanswered questions (ie, how to more efficiently derive shared secrets for steps B-2 to B-4)
 - More communication overhead (more data necessary to validate transaction, and more data necessary for Bob to detect the output)
 - More computations for transaction validators
3 Likes
2

This suggests tx kernels and tx outputs are now linked in some way.
I suspect this might be the stumbling point with this approach.

1 Like
3

IMO it links outputs with public addresses, defeating one of the privacy advantages of MW (no addresses).

2 Likes
4

How? Surely you need to compute the shared secret in order to see to what address it was sent.

5

Did you miss the sentence below?

6

I missed everything after the first section. Lol

7

Out' needs a range proof. How would you construct it using Out and B? That would require non-interactive range proofs merging, but I don’t know if it’s possible.

8

Non interactive bulletproof merging is not possible :frowning:
you can do a single bulletproof for several Pedersen commitments, and this single bulletproof will be smaller in size than the aggregation of the individual bulletproofs, but you need to know all blinding factors (and values) to do that

9

Problem

In the above schema, output creation is described in A-1, and A-2.
The problem is that it’s not possible to create standard range proof for Out', because b is not known to Alice.

Solution

I think I have a solution for it.

Given:

  • (B, s_B) = (b*G, s_B)
  • Out = ro*G + vo*H
  • Out’ = Out + B = (ro*G + B + vo*H + 0*H) = ((ro + b)*G + vo*H)

Algorithm:

D-1) Create a new commitment with the same vo and a new blinding and a corresponding range proof.

  • X = rx*G + vo*H
  • X_proof = bulletproof(rx, vo)

D-2) Compute Z = Out' - X.

  • Z = Out’ - X = ((ro + b)*G + vo*H) - (rx*G + vo*H) = (ro - rx)*G + b*G

D-3) Create Schnorr signature s_Z for Z.

  • s_R = shnorr(ro-rx)
  • s_Z = s_R + s_B

D-4) Delegated Range Proof for Out' is: (X, X_proof, s_Z).

D-5) Verification. Everyone can verify that Out' is not negative because:

  1. s_Z is a valid signature signed by Z. It means that Z is in the form of r*G + 0*H,
  2. so X and Out' has the same vo, and becasue X_proof proves X is in range it also proves Out' is in range.
10

If you have (B,s_B) along with a bulletproof for Out (that Alice can produce at transaction time) on Bob’s output, then you are convinced that Out’ = Out + B has a positive value because the valid signature on B insures that B is proportional to G.

11

I try to build a model where Alice doesn’t have to reveal B in the transaction.

12

What would be the interest of that ?
It seems like a stealth address system would insure privacy

13

I’ve read that: https://hackernoon.com/blockchain-privacy-enhancing-technology-series-stealth-address-i-c8a3eb4e4e43
It seams that the recipient needs to know the sender’s public key, right?

14

Yes, there must have a shared secret between Alice and Bob, and this is typically encoded in sender’s public keys, on the sender’s side, that Alice includes in Bob’s outputs when she creates the transaction

15

Indeed, these transactions are linked to addresses, which is much less private. However, it is an optional feature, and those who choose this feature still contribute to the overall anonymity set, helping those who create standard interactive transactions. So really it is a marginally less private transacting option that plays nice with the standard no-address transactions of today. Potentially interesting,but I don’t think it should be the default transaction mechanism

16

I should mention, @DrazenV raised a good point on Keybase. Every operation in my proposal is reversible, so Alice can create a “take back” transaction to steal the funds back from bob.

With this in mind, my proposal essentially becomes a non-interactive 1 of 2 multisig output. This could still be useful to allow Alice to reclaim a transaction if Bob doesn’t claim after some time… But alas it is not a solution for truly final 1-sided transactions as I had thought.

@Kurt has some interesting ideas to address finality though. Perhaps there is something to find here.

17

As Kurt mentioned, we do not need a rangeproof for Out'. Alice can provide a rangeproof for Out, and we know B is zero value, so we know the sum Out' = Out + B is positive

18

Could it be possible to make 1-sided transactions with a prepared replay transaction pipeline?
Bob prepares the pipeline to receive fixed amount single sided transactions.
1st Bob creates a fixed amount (for example 10 grin) output.
Than Bob makes a couple of transactions sending this output (10 grin minus fee) to him self again and again (for example 100 times).
Now the replay pipeline is created. Bob reveals the secret of creating the first output to the public (or at least to Alice).
Now Alice can fill the pipeline by replaying all the transactions. Bob can harvest the pipeline anytime, by mixing all transactions with other coins to prevent further replays.
Would something like that be possible? One flaw might be, that the recreation of 10 Grin output from Alice, could get stolen from anyone who knows the secret too.

19

Creating 100 kernels for 1 transaction would make chain size grow very fast. Even 2 kernels would in the long-term make the chain size twice as big