2

If I have, let's say 1000 numbers or 10k numbers, and they all add up to 100 when combined, what would be the most efficient way to verify that in fact the sum of all of them is 100?

I was thinking on Open Zeppelin's Merkle Tree sol and js libraries, but I'm not really sure how to apply them in this case.

I could just do n + n1 + n2 + n3....+ n10k, but that's not really scalable nor efficient.

Thanks!

EDIT:

When a new number comes into place, it's not added to the sum (which is always 100, never 101 or 99). It dilutes the participation of all other numbers, so the sum of all of them keeps resulting in 100.

So, for example, if I have 1+1+1=100 and a new "1" comes in, it's not going to be 1+1+1+1=101. It'd be something like 0.7+0.7+0.7+0.7=100. Long story short, the state of 100 + something never occurs.

This is in fact what I'm trying to achieve, the verification that the diluting mechanism of 1+1+1=100 works, and that the algorithm is not broken like 1+1.1+1=100.

2
  • Store the sum separately. Each time you add a number, add it onto the sum. When you remove a number subtract it from the sum. To check that it's 100, just read the sum and see. Dec 5, 2022 at 23:42
  • I added an edit to my post mentioning why this approach wouldn't work in my case. Let me know if I didn't got your answer right @user253751
    – dNyrM
    Dec 6, 2022 at 10:21

2 Answers 2

0

This is done in many, many protocols, such as AMM liquidity pools, and it's done by NOT making the sum 100.

Instead, you can just say that 1 is whatever percentage it is. If the sum is 200, then 1 is only 0.5%, not 1%. If you like, your user interface can calculate that 1 is 0.5% and then display 0.5% instead of displaying 1.

When you want to distribute some benefit, such as an airdrop, to users based on their balance, you distribute it based on the percentages. If you distribute 100 airdrop tokens and someone has a balance of 1, that is 0.5%, they get 0.5 airdrop tokens. There's no need to make the balances actually add to 100.

2
  • Yeah, my approach is different and I'd have to explain why the sum is 100 in my case (I already did it btw, my approach). I didn't want to get into the details to not add noise to the question, but one of the invariants is the 100 sum
    – dNyrM
    Dec 7, 2022 at 9:47
  • @dNyrM then change the invariants. You can calculate the 100 sum when you need it, and the rest of the time, not have the 100 sum Dec 8, 2022 at 2:15
0

Let's say you have N variables : v1, v2...vN. If you need the sum of the variables to be equal to 100 when you add an N+1 variable, you can define vn as the product of a variable "base" and a fixed number.

When you add a new variable, you'll adjust the base such that the sum of (base*number_n) is still equal to 100. You can do new_base = 100/(100+new_variable).

Example:

We have v1 = 3*base, v2 = 4*base, v3=3*base. Base = 10, v1+v2+v3 = 100

We add v4 = 20

Now, if we adjust the base to 8, we have v1 = 24, v2=32, v3=24, v4 = 20, or 2.5*new_base. The sum is still 100.

This method is similar to the one used for rebase tokens, where your balance varies with the operations done on top of it.

4
  • The thing with this approach is that I would always have to compute off-chain the new sum every time a new number comes into play. My system is 100% onchain with no offchain computation. So I'm trying to find a way that wouldn't merit the iteration over every number to come up with the sum. That's why I mentioned the possibility with Merkle Trees.
    – dNyrM
    Dec 6, 2022 at 10:27
  • @dNyrM I rewrote the answer, I hope this solves your problem.
    – Yakitori
    Dec 7, 2022 at 13:41
  • This has the same original issue I have. To verify that the sum is 100, you have to add up all the values (aka iterate over each one v1+v2…vn, what I’m trying to avoid)…unless I got it wrong. Let me know
    – dNyrM
    Dec 7, 2022 at 23:07
  • You don't, since you know that the initial sum is 100. Then you just have to compute new_base = 100/(100+new_variable) when you want to add a value to get everything right, since the previous numbers' value is automatically adjusted using the base. As for the initial sum, either it's an array you load at the start that you can verify off-chain, or it's added incrementally and the cost of adding a number is linear.
    – Yakitori
    Dec 7, 2022 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.