Group Theory

Notes

  • Groth16 - most widely used although it came out in 2016 (tornado cash)

  • goal - tornado cash verifier contract

  • groth 16 only requires 4 heavy math operations - most practical on blockchain

  • new ones are either quantum resistant or dont require trusted setup

  • if something is a group, binary operator will never leave that set

  • binary operators - addition, multiplication etc. between two numbers

  • groups

    • only have 1 binary operator - closed, associative

    • e.g. multiplication over a set of vectors is not closed because the result vector is not of the same dimensions

    • division over vectors also not closed because we may up end with fractions

    • associative - can ignore parentheses/order of executing operations

    • exists an identity element

    • exists an inverse (groups without inverses are called monoids)

  • a group of strings do not have inverses (bc infinite field)

  • Elliptic curves are a group

    • because it only has addition, no multiplication (basically repeated additional/scalar multiplication)

  • cyclic groups have an additional condition - existence of a generator

    • most integers are cyclic groups - can all be multiplied by 1

  • rings - groups with more restrictions

    • must be abelian under the group’s binary operator (commutative)

    • must have a second closed and associative binary operator

    • has to exist an identity element, but not an inverse

    • technically polynomials are rings (kiv)

    • if you’re adding polynomials, what is the identity element - polynomial of zero degree (coefficient zero)

    • identity element for multiplication - 1

  • polynomials with positive degree have no inverse under multiplication

    • because we cannot do negative degree polynomials

    • they have an inverse under addition because we can just flip the coefficients

  • fields

  • finite field - number of elements are finite

  • prime field - a set of prime numbers

  • homomorphism

    • a map between two groups - ring & ring, or field & field

    • exists some transformation that phi of elements in a with their binary operator is equal to phi of the other

    • homomorphic encryption - encrypt private data

    • a lot of transformations are not input preserving

    • keccak256 is not structure preserving - hash(2) + hash(5) =/= hash(7)

    • because hashes basically destroy information

  • field homomorphism

  • map any integer to integer modulo prime

  • the set of rational numbers is also a field homomorphism

  • for any two rational numbers, their binary operators will produce the same modulo inside of the prime field

  • prime field → integers modulo prime

  • isomorphisms

    • we can go from Z to Zp but not in the reverse direction, since there will be many Zs that map to one Zp

    • if you can go backwards, it’ll be called an isomorphism

  • discrete log

  • we can compute $g^n mod p$ , but not the other way round

  • g and p have to be chosen very carefully, and be very large numbers

  • quantum computers could potentially invert big log numbers in future

  • constructing a simple zk proof

  • homomorphic multiplication

PreviousSecurity ModelNextECDSA

Last updated