Graphite

We are addressing the challenge of implementing efficient and accessible graph computations on-chain. Currently, performing graph computations on-chain is both painful and costly, despite their immense utility in various applications. Additionally, the developer experience (UX) for writing validity circuits, such as those in circom and halo2, is cumbersome and largely inaccessible to individuals not specialized in this field. This complexity limits wider adoption and innovation. Furthermore, collecting relevant data for these graph computations, particularly when dealing with extensive on-chain data, poses significant difficulties. Our solution aims to simplify these processes, making graph computations more feasible and user-friendly, thus opening up new possibilities for developers across various disciplines.

Links

• https://github.com/AlexCheema/Graphite
• https://pypi.org/project/pygraphite/

One of the challenges in using Noir (and domain-specific languages, or DSLs, in general) is the absence of support for indeterminate loops, a common feature in traditional programming. This limitation necessitates a different approach to thinking about and implementing algorithms. For instance, many graph algorithms, like breadth-first search, typically employ while loops and continue until a condition, such as an empty queue, is met, making their loop lengths indeterminate. We addressed this challenge by carefully determining the maximum possible lengths for our inputs and then tailoring our circuits to handle these lengths. In cases where an input was shorter than our maximum length, we adapted by padding the input and performing extra, albeit redundant, operations on these padded input elements.