1
$\begingroup$

I'm searching for ways of replacing a Merkle-tree with something more space-efficient.

I don't need any kind of authentication embedded - the accumulator value can be signed via a separate procedure.

Thanks!

$\endgroup$
2
  • $\begingroup$ Wouldn't the leafs of the tree need to be collision resistant? We are talking about validating elements in a set I presume? $\endgroup$
    – Maarten Bodewes
    Aug 25, 2022 at 21:50
  • $\begingroup$ @MaartenBodewes, yes for both questions. $\endgroup$ Aug 25, 2022 at 22:06

1 Answer 1

2
$\begingroup$

Answering my own question.

The simplest possible ec accumulator pseudo code goes like this:

accumulator = G

def add(x_scalar):
  witness = accumulator
  accumulator *= x_scalar

  return witness

def del(x_scalar):
  accumulator *= x_scalar.inverse()

def verify(accumulator, witness, x_scalar):
  expected = witness * x_scalar
  return expected == accumulator

But, since there is no authentication of the accumulator (no secret value used during scalar multiplication) this accumulator won't work, even if you sign it separately.

This is because everybody can create a witness to whatever the value they want. In order to make it work, you have to also sign the generated witness. You can compute it just before making the response, but if it is possible for you to do this in your environment, it may be a better idea to just sign the data entry itself and to give up on the accumulator at all.

$\endgroup$

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.