Auto-compounding/Additive addresses — KIP10 draft

Consensus
1

The following proposal draft is intended for fostering discussion and gathering various conceptual and technical feedback before turning into a well-formed KIP.

This is a follow-up on the micropayments discussion initiated by KIP9.

The basic idea is to allow reception of coins in an additive way, where a UTXO owned by the recipient can be spent by the payer transaction (without a signature) as long as the same transaction creates a corresponding output UTXO with a larger amount going to the same recipient address. For an informal background see here.

Opt-in rather than opt-out

Allowing every UTXO to be spent this way is an opening for spam attacks, where a user trying to spend his own UTXOs can be outraced by an attacker spending the same UTXO through the new mechanism (by adding negligible amounts to it). This would essentially remove the underlying assumption of almost any wallet which assumes exclusive access to spending his own UTXOs.

Therefor our suggestion is to allow this only for special addresses (opt-in) where such an address can be configured in various ways to protect from concurrent-spending spam attacks. In the context of this document we’ll name such addresses additive addresses.

Minimum increment threshold The idea is to have the address (or more concretely, the script_pub_key) define a minimum increment value. Any transaction spending the UTXO and adding to it less than the threshold will be invalid. By the owner specifying this threshold depending on his use case and market value conditions, such spam attacks will become costly and reduced to the point they only benefit the owner.

Semi-signatures Another possibility is to allow spending only with a semi-sig which requires knowing some secret (which is not the full private key only known to the owner). This way the payee can share the secret only with trusted senders.

Technical aspects

Script public key format

At the consensus engine level, a Kaspa address is encoded into a ScriptPublicKey.

An additive address with a configured increment threshold can be encoded as a ScriptPublicKey in two possible ways: (i) a special version of p2pk with the threshold appended at the end (u64); (ii) using p2sh and hashing the usual spk + threshold to a single hash.

The first method has the following main advantage:

  • The new spk will have a known prefix (the version + the usual spk), which will allow easy searching for such addresses by wallets (possibly recreated from a seed w/o additional info). It’s worth noting that Kaspa nodes use key-value based databases which support prefix-key searches, thus allowing for such prefix queries in an efficient way.

The second method is more robust and general and fits into existing script engine schemes. We can also support both options.

New script-engine opcodes

The main missing component in the script engine is the ability to read from the transaction outputs. It seems that the most straightforward way is to add a new opcode which allows reading an output at index (and accessing the amount and recipient spk). This way, the script engine can make the required verification by accessing the spent spk, the recipient spk and the respective amounts. The signature can be used for adding any additional info needed such as providing proof of a semi-sig etc.

Additional remarks

  1. The transaction input index should be mapped to a known output index to avoid multiple spends being mapped to the same output (perhaps simply i to i, forcing such inputs to be first)
  2. It’ll be the first time that validating a sig requires looking at tx outputs (so broader context). This can be crucial. For instance such “signature” validations cannot be cached as valid
  3. Besides the aforementioned schemes there can be a type of special address which allows additive mining. Meaning miners can use this UTXO as input to coinbase txs and output the reward + previous balance. This can be seen as a minimum increment threshold where the threshold is dynamic and is equal to the current mining reward. To avoid any kind of attack, the input UTXO will be used only if it’s available at the time the coinbase tx is built (by the merging block), otherwise we fallback to normal behavior. This is an important feature for 10BPS where nearly 1M rewards will be mined per day.

This writeup is an intermediate summary of ongoing discussions with @ori, @Deshe2, @hashdag, @biryukovmaxim, @coderofstuff, @ey51

2 Likes
2

Technical detail that missed: should both ways(P2SH and new script class) be applied to both schemes: threshold, semi-signature?

I think P2SH works for both.
However Leaking of semi signature can lead to the same attack.
P2SH can add additional protection mechanisms like secret+min_threshold+lock_time or whatever logic allowed by engine/opcodes

P2pk is only okay for threshold.

3

Why would the semi signature leak the secret? can’t we provide same guarantees as usual sigs? you mean it’s leaked by showing it to the payer? if so, I don’t think that’s an issue, it’s a type of trust model

4

As mentioned, the minimum increment threshold [MIT, :)] will be readily adjustable. That is good. If i understand correctly, the MIT will be in units of Kaspa. Is this correct?

And now a really uneducated question:

  1. Could the merchant provide the MIT in units of $ or €, £ and the system automatically converts to Kaspa. Cryptocurrencies fluctuate wildly (often within minutes) and widely (intraday moves of up to 100% or more), so it could make sense for some merchants to put a floor in some desired fiat currencies. Obviously the system would need instantaneous knowledge of the fiat value per Kaspa, as well as conversion ratios between variousnfiat currencies.

Best.

1 Like
5

@biryukovmaxim has mentioned this elsewhere, but I think it’s worth noting here that we’d need to consider the experience for recovering P2SH addresses created for this purpose when recovering wallets. Since normally, we only recover P2PK addresses in those.

The opt-out mechanism isn’t discussed above, so I’ll mention it: The owner can always use their regular private key, sign the UTXO and spend it like any other UTXO. When they do, they effectively opt-out of allowing to use that UTXO for further micropayments.

I want to explore further the P2PK route. spk + threshold is mentioned above with the intent that threshold is a deterrent for spamming.

Consider this scenario where a wallet has a single 200M Kaspa UTXO and the owner uses this KIP10 mechanism to convert (“KIP10’ize”) that into a 200M UTXO that can be used for micropayments by others, with threshold set to 0.00000001 KAS. A dedicated “hater” with a budget of 10,001 KAS can deny the use of that 200M UTXO by creating a chain of 100,000,000 transactions each reusing the 200M UTXO one after another after adding a small amount to it (2 utxos, 2 outputs; assume fee = 0.0001, increment = 0.00000001) for a duration of time. At 1 BPS, that should be ~1157 days since chained transactions can’t go in the same block so they’d have to go in (at best) consecutive blocks. The “hater” may have paid a hefty amount, but they have denied the use of the UTXO for a significant period of time enough to adversely affect another.

My main questions with the above absurd scenario are:

  1. Should there be a maximum amount for the UTXO that can be KIP10’ized? Likely the answer should be no, since arbitrary thresholds are bad. But this brings up a UX concern: wallets should warn users about using this mechanism when they try to convert large utxos to the KIP10’ized ones. Maybe ask the owner to create a smaller UTXO then KIP10’ize that.
  2. Should there be a limit (set by the user) to the number of times a KIP10’ized UTXO can keep getting reused? Possibly by adding a counter to the SPK. Maybe spk + threshold + limit. Upon use of this UTXO, the limit must also be decreased. When limit reaches 0, it can no longer be reused. The owner then can opt-in again and re-KIP10’ize this UTXO, setting a new limit (or even a new threshold)
  3. If the owner attempts to spend a KIP10’ized UTXO (so they’ll have their signature from their private key), should their transaction be prioritized over another that uses the UTXO but doesn’t have a signature?
1 Like
6

If the owner attempts to spend a KIP10’ized UTXO (so they’ll have their signature from their private key), should their transaction be prioritized over another that uses the UTXO but doesn’t have a signature?

It would be nice to have the priority. Not sure how easy is to implement it on probably mempool level.

Should there be a limit (set by the user) to the number of times a KIP10’ized UTXO can keep getting reused? Possibly by adding a counter to the SPK. Maybe spk + threshold + limit. Upon use of this UTXO, the limit must also be decreased. When limit reaches 0, it can no longer be reused. The owner then can opt-in again and re-KIP10’ize this UTXO, setting a new limit (or even a new threshold)

Another ideas: frequency ratio, or time_lock/sequence_lock.
Frequency in meaning that utxos can be collected once per x blocks from not a signer.
Time_lock/sequence_lock - can be collected up to the time/sequence number, then work as regular p2pk

1 Like
7

Fyi I’m not a Blockchain expert, simply making observations from a general perspective. Feel free to ignore or criticise if there’s a technical detail invalidating me :slight_smile:

The problem with the threshold model is that it doesn’t solve this problem: For a high tx volume business, they could be outraced by their non-malicious clients for their additive UTXO too.

The problem with Semi Sigs is that it does not prevent malicious actors.

The problem here essentially stems from the inability to have a Critical Section in a decentralised multi-threaded world. In an ideal world, one would have a RW-Lock or something similar where the owner of the wallet would have their Mutex take precedence.

I have some off-the-cuff ideas for exploring this problem:

  1. Have a designated UTXO which can be the only source of any micro-payments. Once that UTXO is used in a transaction, the output UTXO becomes the next Exclusive Additive UTXO (EAU). If an account has no balance or no previous EAU, create one with a value of 0(?). When the user wants to have exclusive access to the EAU, they simply create a new one and wait for future additive transactions to point to that one.
    This also avoids the possibility of chaining attacks as described above, as it allows a user to gain exclusive access to the EAU by rerouting traffic away from it in advance.

  2. Any transaction by the user involving an EAU could be composed of 2 sub-transactions:

  • A signal to lock the EAU from any unsigned transactions until the next signed transaction
  • The actual transaction signed by the wallet owner, which unlocks UTXO after
8

A high tx volume business can manage a set of additive addresses per some local unit, like a checkout in the supermarket, or a server session, etc. Basically, If malicious users get penalized and all you need is management of resources, it can be managed by the wallet owner in many ways.

9

It sounds to me like both options are are too prone to human error/selfish behavior.
Minimum increment threshold: the problem is a merchant wouldn’t care about the security of the network as a whole. She would care about her own security, followed by ease of usage, and the easiest usage, the one that will require the least action for both for her and her customers, would be having as little a threshold as possible. It might be bad for the network as a whole, but it’s good for her as an individual user, she has no incentive to set a high threshold as far as I can tell.
Semi-signatures: Similarly, I think leakage of the semi-sig will happen by the merchant herself. After a while of dealing with the back and forth of sending every customer the semi-key, merchants will lose patience and just advertise this on their web page. Why shouldn’t they? they don’t risk anything.

Sure, the above will not occur for all the additive addresses, but it can happen with enough addresses, and a spammer could then use those to spam. The users of these addresses wouldn’t be individually effected from the attack, you can only get them to move to a safer address by asking for their good will.

10

The network cares nothing about such spam. It simply means the UTXO is spent (and increased) by the spammer rather than by an actual customer. The only one who should care is the merchant which cannot carry on deals

2 Likes
11

Ok. I completely misunderstood the suggested problem then. I thought the worry was that state bloaters could piggyback on these inputs to artificially bloat the number/budget of input. How exactly are these addresses to be dealt with by the storage mass formula? are they completely ignored? if they are just added as both inputs and outputs, doesn’t that allow a way to artificially increase the budget? taking a naive look at the bound provided in kip9 (\sum_tx(storage_mass(tx)>=C*growth^2(G)/budget), by substantially increasing the budget you would need less storage mass. Would a more tight analysis apply only to the attacker’s own budget and disregard the budget coming from the additive addresses?

12

Nice observation. Yes, a tighter analysis would show exactly that. In fact, it’s part of a more general phenomena where the budget needs to be equally spread across the growth in order to reach the bound tightly (where in the case of additive addresses they only increase in budget while keeping the same number of entries)

The tighter analysis is also required for showing that sufficient budget is locked through time (with correlation to the growth is consumes). The relevant bound is a more complicated expression which is still wip.

14

Not a full answer but here is some back-of-the-envelope math:
Say we have an attacker that wants to break one input with b KAS into k inputs with b/k KAS. Then (using C=1) this should cost (k-1)^2/b mass.

Your concern is if they use extra budget (from an additive UTXO or otherwise) of a KAS then they break (a+b) kas into k UTXOs with b/k KAS and a single UTXO with a KAS, and the bound only implies that this would cost k^2/(a+b) mass. So if a\gg b the cost greatly decreases (and additive UTXOs mean they wouldn’t even have to obtain the a KAS themselves).

However, we can easily prove that any attack that breaks a+b KAS into k UTXOs of size b/k and a single UTXO of size a actually costs at least k^2/b mass, regardless of a: Say that the attack costs v, then if I have a+nb KAS I can repeat the attack n times to create nk inputs of size b/k and a single input of size a for a cost of nv. However, the original bound tells us that such an attack must cost at least (nk)^2/(a+nb) mass, so it holds that nv\ge(nk)^2/(a+nb). Rearranging we get n\left(k^{2}-vb\right)\le va and this inequality is obviously violated for a sufficiently large n unless k^2-vb\le 0.

15

you can pick out users that opt into a better peel chain?

16

I’m sorry, I didn’t understand the question. What do you mean by a “peel chain”?