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

• injective homomorphism

  • https://groupprops.subwiki.org/wiki/Injective_homomorphism