What are the thresholds for various threshold signatures?

Developers
1

Hi everyone,

I am not confident.

The following is implemented through BLS threshold signatures:

  • signature of certified state (2/3 or more?)
  • signature of catch-up package（CUP）(2/3 or more?)
  • signature of random beacon (1/3 or more?)
  • signature of random tape (1/3 or more?)

The following is implemented through aggregation of BLS signatures:

  • aggregating multiple notarization shares into a single signature notarization (2/3 or more?)
  • aggregating multiple finalization shares into a single signature finalization (2/3 or more?)

signature of certified state
On the whitepaper, it is written as (n - f)-out-of-n. Does this actually mean 2/3 or more?

catch-up package (CUP)
On the whitepaper, it is written as (n - f)-out-of-n. Does this actually mean 2/3 or more?

signature of random beacon
On the whitepaper, it is written as (f + 1)-out-of-n. Does this actually mean 1/3 or more?

signature of random tape
On the whitepaper, it is written as (f + 1)-out-of-n. Does this actually mean 1/3 or more?

aggregating multiple notarization shares into a single signature notarization
On the whitepaper, it is written as n-f. Does this actually mean 2/3 or more?

aggregating multiple finalization shares into a single signature finalization
On the whitepaper, it is written as n-f. Does this actually mean 2/3 or more?

1 Like
2

Could anyone please provide an answer to my question? I’m still waiting for a response. Thank you.

1 Like
3

Hi @tokuryoo!

The assumption on subnets is that strictly less than 1/3rd nodes are faulty, or in other words, f = floor((n-1)/3). Let’s as a concrete example use n=13, then f = 4.

Anything that is signed with “high threshold” requires n-f signature shares, which for our example of n=13, f=4 means 9 nodes need to sign, so strictly more than 2/3rds.

Anything that is signed with “low threshold” requires strictly more than f signatures, so again with n=13 and f=4, it means 5 nodes need to sign, i.e. strictly more than 1/3rd.

You are correct that certifications, CUPs, notarizations and finalizations use high threshold, and random beacon and random tape use low threshold.

5 Likes
4

Thanks, I understand now.