spekalsg3/zk-stark-tutor

Learning implementation of zero-knowledge STARK protocol

zk-Stark

This repository is created to learn implementations of zero-knowledge STARK protocol.

Credits

Great tutorial by aszepieniec explains the math behind this proof system.

TODO's for Production Ready

• There is no compression of transition constraints into one master constraint
• In production systems the length of the codeword is often reduced not by a factor 2 but a small power of 2. This optimization reduces the proof size and might even generate running time improvements
• Arithmetization step, which transforms the initial computation into an arithmetic constraint system
• Extension fields. EthSTARK operates over the finite field defined by a 62-bit prime, but the FRI step operates over a quadratic extension field thereof in order to target a higher security level.
• Advanced STARKs may define more constraint types (referring to AIR) in order to deal with memory or with consistency of registers within one cycle
• The code supporting the tutorial achieves scalability through preprocessing as opposed to group theory. Preprocessing is arguably not scalable if counted as verifier's work.

zk-stark-tutor's Issues

MDS and Round Constants are hardcoded

But they can be easily computated. Paper

Field::sample doesn't work

Shl can handle only 128 bits when using maximum std unsigned int (u128). But python has no limit for integer size and thus shl can handle any number of bits. Because I'm using 512 bits for hash functions, samples result as 512 bit integers.

def sample( byte_array ):
      acc = 0
      for b in byte_array:
          acc = (acc << 8) ^ int(b)
      return acc

arr = bytes.fromhex('ec784925b52067bce01fd820f554a34a3f8522b337f82e00ea03d3fa2b207ef9c2c1b9ed900cf2bbfcd19a232a94c6121e041615305c4155d46d52f58a8cff1c')

assert(len(arr) == 64)

assert(sample(arr) == 12384931821925374805714873153556176341982265672553534219028848380488219810490628971054595361699590844731724413469580443958856257743152219185511336904556316)

assert(len(bin(sample(arr)[2:])) == 512)

Two solutions:

• Optimized - find an algorithm to do such calculations in finite field
• Easiest - implement 512 integers

Optimize hex proof

u128 is necessary to represent the prime field but most of the time this value is much less. This results in a lot of 0's when serializing the proof stream wasting a lot of space.

One idea is to trim leading zeros and add u8 to signal the size of the number. If only half of u128 is used, this will result in 7 bytes profit (1u 8 for size and 8 u8 for the number itself).