How to deterministically define output containing the tweaked key for P2C schemes

[dr-orlovsky]

The original problem is put forward by @giacomozucco: in order to avoid double spending with pay to contract commitment schemes, all future owners of the assets must be able to know exactly WHERE the proof-commitment is, in each step. Without it, one could create two versions of the same proof that commit to different outputs, allowing therefore double spends.

To demonstrate the problem he had provided such case:

Alice sends assets to Bob with Txa. Bob sends them to Carol with Txb. Carol to Daniel with Txc. In order to avoid double spending, ALL of them must to be able to know exactly WHERE the proof-commitment is, in each step. Bob may not know which output of Txa is the actual change of Alice (even if he COULD deduce it in trivial cases, by exclusion). Carol and Daniel would have NO IDEA of that. So, the rule must be deterministic for everybody.

Some of his suggestions are:

"First output" is ok, just as it's ok any deterministic mechanism. Actually, I'd prefer some simple deterministic way (like, count satoshis in the first output and use mod(N) to get to the right output) for the reason tha I don't like the idea of forcing the RGB wallet to always put the change in 1st position, since that may conflict with some future best practice in Bitcoin, like value-based ordering, lexicographic ordering, or ordering patterns that serve other porpuses in CoinJoins or wathever. But the point is that "change output" is NOT an alternative to "first output". We need a deterministic way to know WHICH output contains the commitment, AND, orthogonally, it would be often better IF that output was also a change by the spender, for many reasons.

@fedsten had the following argument regarding this:

Regarding the proposal of using the amount to deterministically identify the change output I don't really agree. Using satoshis to encode information only works until satoshis are irrelevant, which we cannot expect to be the case forever, but I'm sure we can find something else (eg unused space in the sequence or even some ugly brute force on the signature)

@giacomozucco:

We could use other fields, probably, like nsequence (but it could interfeer with RBF?). In general, anyway, I'd like the order of the output to tweek to leave some degree of freedom to spender in case of other ordering schemes.
So, to recap:

• in general, the UTXO which can be spent to move the asset NEXT is not necessarily (and I think shouldn't be in general) the same UTXO which contains the commitment NOW
• it must be possible for a receiver of proofs to deterministically know, from public info, which output contains the commitment BEFORE even opening the proof, or one could doublespend (but I'd like to avoid fixed orders)
• in general, it would be cool to have the default of the change as the proof container, since it's likely there anyway and the sender knows the tweaking secret by definition, since he created it.

@fedsten:

I was thinking that if we have a deterministic way to find the change output with on-chain data, than the same information is available to chain analyst attackers eliminating the benefits of not having a fixed outputs order. So anyway whatever we use, it cannot be something that could make the tx identifiable as RGB (so nsequence, version and unactivated timelock are to be excluded).

@giacomozucco:

Precisely. It should be something that IF one assumes that's an RGB transaction, THEN identifies uniquely the output

[dr-orlovsky]

I am thinking about this combined solution:

1. If the transaction uses RBF, then take the value of nseq from txid that has nseq < 0xffffe and compute nseq mod count(txouts)
2. Otherwise use the fee and compute fee mod count(txouts)

This will give users an option to safe satoshis on the fee when 1sat will be big money :)

RBF is a standard thing used by ~10% of all txs as of today, so it would not create a flaw to be tracked by chain analysis tools. If somebody still would like to reduce probability of assuming the tx as RGB tx they will use fee and will not create RBF transaction.

@fedsten:

I think a problem with this could be that most wallets that implement RBF set the nseq to a standard value (either 0 or max-2), not a random value, so using it to share other information may make them distinguishable

My own thought on this argument is the following: the usual transaction has two outputs, so nseq=0 and 1 will cover the most of cases, and both are used by usual RBF transactions

It will be interesting to check statistics on nseq rbf values for existing onchain txs, but I didn’t find which explorer is capable of getting that kind of information

@fedsten proposed to look for the statistics from his sources

[dr-orlovsky]

@giacomozucco:

I think the relationship between "UTXO which proofs say must be spent to move assets" and "UTXO which contains a commitment to proofs" is a very general topic. Regardless P2C specifically.

However, from my opinion it's not clear why we will have such an issue with OP_RETURN commitment scheme b/c in the current specification it is already defined that the first OP_RETURN output is the one used by RGB asset, so we have determinism here.

[inaltoasinistra]

I was thinking that if we have a deterministic way to find the change output with on-chain data, than the same information is available to chain analyst attackers eliminating the benefits of not having a fixed outputs order.

In order to avoid to provide information to chain analysis tools (e.i. which is the change address assuming the tx is a RGB one) we could include some off chain data to compute the output index.
We could use some bits included into the spent proofs added to some bits of the transaction.

[fedsten]

In order to avoid to provide information to chain analysis tools (e.i. which is the change address assuming the tx is a RGB one) we could include some off chain data to compute the output index.
We could use some bits included into the spent proofs added to some bits of the transaction.

If off-chain data is used to deterministically compute the output index, than we lose the double spending protection provided by the Bitcoin blockchain. I could for example create two versions of the same proof indicating a different index, making it possible to send the same assets to multiple parties, without them being able to detect the double-spending operation.

[inaltoasinistra]

I did not mean to use data of the current proof, sorry.
Let Ta a bitcoin rgb transaction and Pa the off chain proof committed into Ta.
Let Tb an rgb transaction that spends some assets moved by Ta, so Ta is an input of Tb.
If we use the field Pa.entropy to compute the commitment index of Pb we will avoid the double spend issue.
We are not committing the position of the proof inside the proof itself.

[fedsten]

I believe that double spending would still be possible with the scheme you propose. If I create two alternative versions of Pa, I can later show to different people a different output of Tb as the one containing the commitment Pb for the tokens coming from Ta. The two victims of the double spend attack will receive different versions of Pa, so they will compute a differe output of Tb as the one containing the commitment to Pb.
If it is not possible to know only with on-chain data where the tokens are sopposed to be, then we are not effectively leveraging the blockchain to protect from double spending and we could just avoid using Bitcoin altogether.

[inaltoasinistra]

It is not possible to create 2 versions of Pa, because the position of its commitment is computed with Pz.entropy (input proof of Pa) and Ta.
If Pz is valid also the commitment position of Pa will be

[dr-orlovsky]

From #95 it follows that nSeq will be required to spend one of the outputs of the LN commitment transaction, so at least we can't use nSeq from this case, which, basically, leaves us only with fees mod count(outputs) scheme...

[inaltoasinistra]

I did not mean to use data of the current proof, sorry.
Let Ta a bitcoin rgb transaction and Pa the off chain proof committed into Ta.
Let Tb an rgb transaction that spends some assets moved by Ta, so Ta is an input of Tb.
If we use the field Pa.entropy to compute the commitment index of Pb we will avoid the double spend issue.
We are not committing the position of the proof inside the proof itself.

Alekos:

That can probably be broken with send-to-utxo, you could change the "entropy" by spending only one of the proofs attached to your utxo (together with the tokens you want to double spend)

[dr-orlovsky]

FYI: I had today a discussion with @giacomozucco and here is an excerpt from it relating the issue under the question:

Basically, from the discussion we had it follows that we need something inside the actual tx (and not in the proof itself) that deterministically defines which tx output will be used for the proof commitment. There is not a lot of variable tx parts which may be modified w/o introducing new inputs/outputs and affecting the actual amount of funds being transacted. The list of the options is the following:

1. nTimeLock and nSequence (one per each input). These are used by LN in such a way, that we can't store any additional information into them w/o diminishing the existing LN protocol — not to say about it's future extensions and other L2 solutions.
2. Transaction version number: we can't play with it, it's part of SegWit and will cause soft fork at the very best case.
3. Transaction scripts for P2SH and P2WSH outputs: not each transaction has them, and introducing new bytes to them will be another way for an undesirable blockchain size bloat, also diminishing determinism of some scripts (like multisigs, LN commitments etc).
4. TxID, i.e. hash of the serialized transaction w/o signatures/public keys (in case of SegWit-enabled transactions, which we assume will be the main case in the future). We can affect TxID only by changing one of the tx fields outside of the witness script – but it brings us back to one of the listed solutions anyway, so it is not a solution per se.
5. Transaction fee – a computed parameter, representing the difference between inputs and outputs amounts, which can be changed w/o introducing new bytes/op-codes/inputs/outputs etc.

Analyzing all of the options, it seems that (5) is the only reasonable way forward.

One of the arguments against using the fee amount for determining tx output for commitment is that one day in the future (hopefully soon) each satoshi would become quite a sufficient value, and increasing the size of the fee even for a single satoshi can be an expensive measure! However,
a) the other ways (discussed above) are more risky/can't be standardized/more expensive under the same circumstances (adding bytes to the actual tx or adding additional tx outpus);
b) the spending party is not required to change the actual fee, it can just commit to the output which is being defined by the fee it is willing to pay originally – or ...
c) ... if it's not possible (due to some reasons) to commit to the output defined by a "comfortable fee", tx issuer can just reduce the fee by one or two satoshis – taking into account that the average transaction has two outputs (payment and change) or at most three, reducing the fee for two satoshis (not per byte but in absolute value) will allow to commit to a different output — while not affecting the speed of tx mining (1-2 satoshis divided by 500 bytes of tx average size will reduce the satoshi/byte ratio in very tiny way).

So, our proposal is to stick with a simple commitment scheme defining the committing output as a fee mod count(outputs)

[dr-orlovsky]

Copying here from #93 as it is relevant in the context of this issue:

Me and @giacomozucco had a phone discussion on these issues and we came to the following conclusion: at RGB/Spectrum v1 we need to count all outputs and do not exclude any non-P2(W)PKH outputs from the count(outputs) value – but for now (in v1) treat all proofs that commit to non-P2(W)PKH outputs as invalid, i.e these proofs will "burn" the assets inside them.

In the future (v2?), when we consider how to work with all possible cases of P2(W)SH and other possible (future) types of outputs, including all these beautiful Schnorrs-scriptless-tapgrafroots, we may "soft-fork" the spec and introduce new rule(s) that will not treat non-P2(W)PKH outputs as invalid, but will provide some options to interpret them. This is the only possible way forward, b/c if we do the other way around (exlude non-P2(W)PKH outputs from counting in v1), we will face a kind of "hard-fork" problem in the future introducing a way to double-spend RGB assets by exploring the fact that un-updated RGB nodes will not count non-P2(W)PKH outputs, and commit to the other outputs than updated RGB nodes – giving an ability to present different proofs depending to the nodes running different software versions.

[dr-orlovsky]

The updated proposal taking into account the last discussion during the dev's call:

The algorithm is designed in a way that helps to keep information of the output containing commitment private from any party which may assume that the transaction must contain such commitment. The function combines two parameters:

• fee amount (fee): a public factor, which may be changed by the party changing the state (i.e. unsealing an output with a previous state),
• entropy from previous proof (entropy): a private factor, known only to those who has an access to the history of the proofs. This implies that such factor can't be changed by the party changing the state, since it's predefined at the moment of sealing the parent state.

The committed output number n is determined by the following formula:
n = (fee * entropy) mod count(outputs)

The current version of the specification uses RIPMD160 hash of the serialized proof as a source of entropy. For P2C proofs the proof is serialized including the original public key field (pubkey). This different serialization and different hash type comparing to SHA256 hash used to create the commitment itself further reduces probability for some third-party to guess the number of the actual committed output.