Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

[Jonas Nick <jonasd.nick@gmail.com>]

Hi waxwing,

Thanks again for your comments.

 > My initial reaction would be, since it's not worsening the scaling of the
 > verifier, does it matter?

I think saving time in signing does matter (3 group exponentiations requiring
O(1) group operations in total vs. O(n/log n) group operations); for example, in
constrained signing devices as you mention. In particular, the "single-b"
variant with the larger signing cost doesn't appear to have advantages (see
below) compared to "multi-b" which has lower signing cost.

 > The scheme is explicitly not limited to Bitcoin, nor blockchains, though,
 > so there's that; is that relevant here?

The scheme is not limited to Bitcoin, but the main application we designed for
is Bitcoin. I agree that verification performance is of primary importance. We
would choose a scheme with lower signing performance, if it gives us a better
verification performance in return (if the trade-off is reasonable).

 > Yes, those are some interesting points to consider. On one detail: "In any
 > case, identifying disruptive participants will work reliably only if the
 > coordinator is honest, so let's assume this." -- this could also be addressed
 > with proofs of knowledge, no?

Maybe I misunderstand what you're getting at, but I don't understand how proofs
of knowledge would get rid of the honest coordinator requirement for identifying
disruptive signers. Moreover, both R_{2,i} and R_{2,j} could have a valid proof
of knowledge attached (for example, if parties i and j share the dlog of R_{2,i}
= R_{2,j}).

 > Anyway, for me it was more a sort of preference for purely algebraic
 > algorithms. It's a little fanciful, but algebraic algorithms are easier to
 > encode in circuits in zero knowledge (though things like equality checks are
 > entirely doable ofc!) and maybe easier to "encode" into modular schemes that
 > use them as a building block. Maybe. Less conditional branches / loops to
 > traverse in the code?

Why exactly would it be easier to encode the multi-b variant in a circuit? The
single-b variant requires checking whether there exists i such that R_{2,i}
matches a fixed R_{2,j}. In the multi-b variant we'd need to compute the product
of all R_{2,i}^{b_i}, which, even with a multiexp implementation, requires at
least visiting all elements plus the actual multiexponentiation involving
O(n/log n) group operations. So encoding the single-b variant appears to be
strictly easier.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/e15cf0db-bc04-454d-8d63-029bd864d08b%40gmail.com.